Andersen.hpp

Go to the documentation of this file.

/*
 * Copyright 2023, 2024 Håvard Krogstie <krogstie.havard@gmail.com>
 * See COPYING for terms of redistribution.
 */
 
#ifndef JLM_LLVM_OPT_ALIAS_ANALYSES_ANDERSEN_HPP
#define JLM_LLVM_OPT_ALIAS_ANALYSES_ANDERSEN_HPP
 
#include <jlm/llvm/ir/operators.hpp>
#include <jlm/llvm/ir/RvsdgModule.hpp>
#include <jlm/llvm/opt/alias-analyses/PointerObjectSet.hpp>
#include <jlm/llvm/opt/alias-analyses/PointsToAnalysis.hpp>
#include <jlm/rvsdg/gamma.hpp>
#include <jlm/rvsdg/theta.hpp>
 
namespace jlm::llvm::aa
{
 
class Andersen final : public PointsToAnalysis
{
  class Statistics;
 
public:
  static inline const char * const ENV_TEST_ALL_CONFIGS = "JLM_ANDERSEN_TEST_ALL_CONFIGS";
 
  static inline const char * const ENV_USE_EXACT_CONFIG = "JLM_ANDERSEN_USE_EXACT_CONFIG";
 
  static inline const char * const ENV_DOUBLE_CHECK = "JLM_ANDERSEN_DOUBLE_CHECK";
 
  static inline const char * const ENV_DUMP_SUBSET_GRAPH = "JLM_ANDERSEN_DUMP_SUBSET_GRAPH";
 
  class Configuration
  {
    Configuration() = default;
 
  public:
    enum class Solver
    {
      Naive,
      Worklist
    };
 
    void
    SetSolver(Solver solver) noexcept
    {
      Solver_ = solver;
    }
 
    [[nodiscard]] Solver
    GetSolver() const noexcept
    {
      return Solver_;
    }
 
    void
    SetWorklistSolverPolicy(PointerObjectConstraintSet::WorklistSolverPolicy policy) noexcept
    {
      WorklistSolverPolicy_ = policy;
    }
 
    [[nodiscard]] PointerObjectConstraintSet::WorklistSolverPolicy
    GetWorklistSoliverPolicy() const noexcept
    {
      return WorklistSolverPolicy_;
    }
 
    void
    EnableOfflineVariableSubstitution(bool enable) noexcept
    {
      EnableOfflineVariableSubstitution_ = enable;
    }
 
    [[nodiscard]] bool
    IsOfflineVariableSubstitutionEnabled() const noexcept
    {
      return EnableOfflineVariableSubstitution_;
    }
 
    void
    EnableOfflineConstraintNormalization(bool enable) noexcept
    {
      EnableOfflineConstraintNormalization_ = enable;
    }
 
    [[nodiscard]] bool
    IsOfflineConstraintNormalizationEnabled() const noexcept
    {
      return EnableOfflineConstraintNormalization_;
    }
 
    void
    EnableOnlineCycleDetection(bool enable) noexcept
    {
      EnableOnlineCycleDetection_ = enable;
    }
 
    [[nodiscard]] bool
    IsOnlineCycleDetectionEnabled() const noexcept
    {
      return EnableOnlineCycleDetection_;
    }
 
    void
    EnableHybridCycleDetection(bool enable) noexcept
    {
      EnableHybridCycleDetection_ = enable;
    }
 
    [[nodiscard]] bool
    IsHybridCycleDetectionEnabled() const noexcept
    {
      return EnableHybridCycleDetection_;
    }
 
    void
    EnableLazyCycleDetection(bool enable) noexcept
    {
      EnableLazyCycleDetection_ = enable;
    }
 
    [[nodiscard]] bool
    IsLazyCycleDetectionEnabled() const noexcept
    {
      return EnableLazyCycleDetection_;
    }
 
    void
    EnableDifferencePropagation(bool enable) noexcept
    {
      EnableDifferencePropagation_ = enable;
    }
 
    [[nodiscard]] bool
    IsDifferencePropagationEnabled() const noexcept
    {
      return EnableDifferencePropagation_;
    }
 
    void
    EnablePreferImplicitPointees(bool enable) noexcept
    {
      EnablePreferImplicitPointees_ = enable;
    }
 
    [[nodiscard]] bool
    IsPreferImplicitPointeesEnabled() const noexcept
    {
      return EnablePreferImplicitPointees_;
    }
 
    [[nodiscard]] std::string
    ToString() const;
 
    static Configuration
    DefaultConfiguration()
    {
      Configuration config;
      config.EnableOfflineVariableSubstitution(true);
      // Constraints are normalized inside the Worklist's representation either way
      config.EnableOfflineConstraintNormalization(false);
      config.SetSolver(Solver::Worklist);
      config.SetWorklistSolverPolicy(
          PointerObjectConstraintSet::WorklistSolverPolicy::LeastRecentlyFired);
      config.EnableOnlineCycleDetection(false);
      config.EnableHybridCycleDetection(true);
      config.EnableLazyCycleDetection(true);
      config.EnableDifferencePropagation(true);
      config.EnablePreferImplicitPointees(true);
      return config;
    }
 
    [[nodiscard]] static Configuration
    NaiveSolverConfiguration() noexcept
    {
      Configuration config;
      config.EnableOfflineVariableSubstitution(false);
      config.EnableOfflineConstraintNormalization(false);
      config.SetSolver(Solver::Naive);
      return config;
    }
 
    [[nodiscard]] static std::vector<Configuration>
    GetAllConfigurations();
 
  private:
    // All techniques are turned off by default
    bool EnableOfflineVariableSubstitution_ = false;
    bool EnableOfflineConstraintNormalization_ = false;
    Solver Solver_ = Solver::Naive;
    PointerObjectConstraintSet::WorklistSolverPolicy WorklistSolverPolicy_ =
        PointerObjectConstraintSet::WorklistSolverPolicy::LeastRecentlyFired;
    bool EnableOnlineCycleDetection_ = false;
    bool EnableHybridCycleDetection_ = false;
    bool EnableLazyCycleDetection_ = false;
    bool EnableDifferencePropagation_ = false;
    bool EnablePreferImplicitPointees_ = false;
  };
 
  Andersen();
 
  ~Andersen() noexcept override;
 
  Andersen(const Andersen &) = delete;
 
  Andersen(Andersen &&) = delete;
 
  Andersen &
  operator=(const Andersen &) = delete;
 
  Andersen &
  operator=(Andersen &&) = delete;
 
  void
  SetConfiguration(Configuration config);
 
  [[nodiscard]] const Configuration &
  GetConfiguration() const;
 
  std::unique_ptr<PointsToGraph>
  Analyze(const rvsdg::RvsdgModule & module, util::StatisticsCollector & statisticsCollector)
      override;
 
  std::unique_ptr<PointsToGraph>
  Analyze(const LlvmRvsdgModule & module);
 
  [[nodiscard]] static std::unique_ptr<PointsToGraph>
  ConstructPointsToGraphFromPointerObjectSet(const PointerObjectSet & set, Statistics & statistics);
 
  [[nodiscard]] static std::unique_ptr<PointsToGraph>
  ConstructPointsToGraphFromPointerObjectSet(const PointerObjectSet & set);
 
private:
  void
  AnalyzeRegion(rvsdg::Region & region);
 
  void
  AnalyzeSimpleNode(const rvsdg::SimpleNode & node);
 
  void
  AnalyzeAlloca(const rvsdg::SimpleNode & node);
 
  void
  AnalyzeMalloc(const rvsdg::SimpleNode & node);
 
  void
  AnalyzeLoad(const rvsdg::SimpleNode & node);
 
  void
  AnalyzeStore(const rvsdg::SimpleNode & node);
 
  void
  AnalyzeCall(const rvsdg::SimpleNode & callNode);
 
  void
  AnalyzeGep(const rvsdg::SimpleNode & node);
 
  void
  AnalyzeBitcast(const rvsdg::SimpleNode & node);
 
  void
  AnalyzeBits2ptr(const rvsdg::SimpleNode & node);
 
  void
  AnalyzePtrToInt(const rvsdg::SimpleNode & node);
 
  void
  AnalyzeConstantPointerNull(const rvsdg::SimpleNode & node);
 
  void
  AnalyzeUndef(const rvsdg::SimpleNode & node);
 
  void
  AnalyzeMemcpy(const rvsdg::SimpleNode & node);
 
  void
  AnalyzeConstantArray(const rvsdg::SimpleNode & node);
 
  void
  AnalyzeConstantStruct(const rvsdg::SimpleNode & node);
 
  void
  AnalyzeConstantAggregateZero(const rvsdg::SimpleNode & node);
 
  void
  AnalyzeExtractValue(const rvsdg::SimpleNode & node);
 
  void
  AnalyzeValist(const rvsdg::SimpleNode & node);
 
  void
  AnalyzePointerToFunction(const rvsdg::SimpleNode & node);
 
  void
  AnalyzeFunctionToPointer(const rvsdg::SimpleNode & node);
 
  void
  AnalyzeIOBarrier(const rvsdg::SimpleNode & node);
 
  void
  AnalyzeStructuralNode(const rvsdg::StructuralNode & node);
 
  void
  AnalyzeLambda(const rvsdg::LambdaNode & node);
 
  void
  AnalyzeDelta(const rvsdg::DeltaNode & node);
 
  void
  AnalyzePhi(const rvsdg::PhiNode & node);
 
  void
  AnalyzeGamma(const rvsdg::GammaNode & node);
 
  void
  AnalyzeTheta(const rvsdg::ThetaNode & node);
 
  void
  AnalyzeRvsdg(const rvsdg::Graph & graph);
 
  void
  AnalyzeModule(const rvsdg::RvsdgModule & module, Statistics & statistics);
 
  static void
  SolveConstraints(
      PointerObjectConstraintSet & constraints,
      const Configuration & config,
      Statistics & statistics);
 
  Configuration Config_ = Configuration::DefaultConfiguration();
 
  std::unique_ptr<PointerObjectSet> Set_ = {};
  std::unique_ptr<PointerObjectConstraintSet> Constraints_ = {};
};
 
}
 
#endif