PointerObjectSet.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_POINTEROBJECTSET_HPP
#define JLM_LLVM_OPT_ALIAS_ANALYSES_POINTEROBJECTSET_HPP
 
#include <jlm/llvm/ir/operators/call.hpp>
#include <jlm/llvm/ir/operators/delta.hpp>
#include <jlm/llvm/ir/operators/lambda.hpp>
#include <jlm/llvm/ir/RvsdgModule.hpp>
#include <jlm/util/BijectiveMap.hpp>
#include <jlm/util/common.hpp>
#include <jlm/util/GraphWriter.hpp>
#include <jlm/util/HashSet.hpp>
#include <jlm/util/Math.hpp>
 
#include <cstdint>
#include <optional>
#include <unordered_map>
#include <variant>
#include <vector>
 
namespace jlm::llvm::aa
{
 
enum class PointerObjectKind : uint8_t
{
  // Registers can not be pointed to, only point.
  Register = 0,
  // All other pointer objects represent storage instances in memory
  AllocaMemoryObject,
  MallocMemoryObject,
  GlobalMemoryObject,
  // Represents functions, they can not point to any memory objects.
  FunctionMemoryObject,
  // Represents functions and global variables imported from other modules.
  ImportMemoryObject,
 
  COUNT
};
 
using PointerObjectIndex = uint32_t;
 
class PointerObjectSet final
{
  struct PointerObject final
  {
    // The kind of pointer object
    PointerObjectKind Kind : util::BitWidthOfEnum(PointerObjectKind::COUNT);
 
    // If set, this pointer object may point to other pointer objects.
    // If unset, the analysis should make no attempt at tracking what this PointerObject may target.
    // The final PointsToGraph will not have any outgoing edges for this object.
    const uint8_t CanPointFlag : 1;
 
    // This memory object's address is known outside the module.
    // Can only be true on memory objects.
    uint8_t HasEscaped : 1;
 
    // Any pointee of this PointerObject has its address escaped.
    // The unification root is the source of truth for this flag!
    // This flag is implied by HasEscaped
    uint8_t PointeesEscaping : 1;
 
    // If set, this pointer object is pointing to external.
    // The unification root is the source of truth for this flag!
    // This flag is implied by HasEscaped
    uint8_t PointsToExternal : 1;
 
    // If set, any pointee of this object should point to external.
    // The unification root is the source of truth for this flag!
    uint8_t StoredAsScalar : 1;
 
    // If set, any pointee of this object should mark its pointees as escaping.
    // The unification root is the source of truth for this flag!
    uint8_t LoadedAsScalar : 1;
 
    explicit PointerObject(PointerObjectKind kind, bool canPoint)
        : Kind(kind),
          CanPointFlag(canPoint),
          HasEscaped(0),
          PointeesEscaping(0),
          PointsToExternal(0),
          StoredAsScalar(0),
          LoadedAsScalar(0)
    {
      JLM_ASSERT(kind != PointerObjectKind::COUNT);
 
      // Ensure that certain kinds of PointerObject always CanPoint or never CanPoint
      if (kind == PointerObjectKind::FunctionMemoryObject)
        JLM_ASSERT(!CanPoint());
      else if (kind == PointerObjectKind::Register)
        JLM_ASSERT(CanPoint());
 
      if (!CanPoint())
      {
        // No attempt is made at tracking pointees, so use these flags to inform others
        PointeesEscaping = 1;
        PointsToExternal = 1;
      }
    }
 
    [[nodiscard]] bool
    CanTrackPointeesImplicitly() const noexcept
    {
      return PointsToExternal && PointeesEscaping;
    }
 
    [[nodiscard]] bool
    CanPoint() const noexcept
    {
      return CanPointFlag;
    }
 
    [[nodiscard]] bool
    IsRegister() const noexcept
    {
      return Kind == PointerObjectKind::Register;
    }
  };
 
  // All PointerObjects in the set
  std::vector<PointerObject> PointerObjects_;
 
  // The parent of each PointerObject in the disjoint-set forest. Roots are their own parent.
  // Marked as mutable to allow path compression in const qualified methods.
  mutable std::vector<PointerObjectIndex> PointerObjectParents_;
 
  // Metadata enabling union by rank, where rank is an upper bound for tree height
  // Size of a disjoint set is at least 2^rank, making a uint8_t plenty big enough.
  std::vector<uint8_t> PointerObjectRank_;
 
  // For each PointerObject, a set of the other PointerObjects it points to
  // Only unification roots may have a non-empty set,
  // other PointerObjects refer to their root's set.
  std::vector<util::HashSet<PointerObjectIndex>> PointsToSets_;
 
  // Mapping from register to PointerObject
  // Unlike the other maps, several rvsdg::output* can share register PointerObject
  std::unordered_map<const rvsdg::Output *, PointerObjectIndex> RegisterMap_;
 
  std::unordered_map<const rvsdg::SimpleNode *, PointerObjectIndex> AllocaMap_;
 
  std::unordered_map<const rvsdg::SimpleNode *, PointerObjectIndex> MallocMap_;
 
  std::unordered_map<const rvsdg::DeltaNode *, PointerObjectIndex> GlobalMap_;
 
  util::BijectiveMap<const rvsdg::LambdaNode *, PointerObjectIndex> FunctionMap_;
 
  std::unordered_map<const LlvmGraphImport *, PointerObjectIndex> ImportMap_;
 
  // How many items have been attempted added to explicit points-to sets
  size_t NumSetInsertionAttempts_ = 0;
 
  // How many pointees have been removed from points-to sets.
  // Explicit pointees can only be removed through unification, and the remove method
  size_t NumExplicitPointeesRemoved_ = 0;
 
  [[nodiscard]] PointerObjectIndex
  AddPointerObject(PointerObjectKind kind, bool canPoint);
 
  template<typename NewPointeeFunctor>
  bool
  PropagateNewPointees(
      PointerObjectIndex superset,
      PointerObjectIndex subset,
      NewPointeeFunctor & onNewPointee);
 
public:
  PointerObjectSet() = default;
 
  [[nodiscard]] size_t
  NumPointerObjects() const noexcept;
 
  [[nodiscard]] size_t
  NumPointerObjectsOfKind(PointerObjectKind kind) const noexcept;
 
  [[nodiscard]] size_t
  NumRegisterPointerObjects() const noexcept;
 
  [[nodiscard]] size_t
  NumMemoryPointerObjects() const noexcept;
 
  [[nodiscard]] size_t
  NumMemoryPointerObjectsCanPoint() const noexcept;
 
  [[nodiscard]] PointerObjectIndex
  CreateRegisterPointerObject(const rvsdg::Output & rvsdgOutput);
 
  [[nodiscard]] PointerObjectIndex
  GetRegisterPointerObject(const rvsdg::Output & rvsdgOutput) const;
 
  [[nodiscard]] std::optional<PointerObjectIndex>
  TryGetRegisterPointerObject(const rvsdg::Output & rvsdgOutput) const;
 
  void
  MapRegisterToExistingPointerObject(
      const rvsdg::Output & rvsdgOutput,
      PointerObjectIndex pointerObject);
 
  [[nodiscard]] PointerObjectIndex
  CreateDummyRegisterPointerObject();
 
  [[nodiscard]] PointerObjectIndex
  CreateAllocaMemoryObject(const rvsdg::SimpleNode & allocaNode, bool canPoint);
 
  [[nodiscard]] PointerObjectIndex
  CreateMallocMemoryObject(const rvsdg::SimpleNode & mallocNode, bool canPoint);
 
  [[nodiscard]] PointerObjectIndex
  CreateGlobalMemoryObject(const rvsdg::DeltaNode & deltaNode, bool canPoint);
 
  [[nodiscard]] PointerObjectIndex
  CreateFunctionMemoryObject(const rvsdg::LambdaNode & lambdaNode);
 
  [[nodiscard]] PointerObjectIndex
  GetFunctionMemoryObject(const rvsdg::LambdaNode & lambdaNode) const;
 
  [[nodiscard]] const rvsdg::LambdaNode &
  GetLambdaNodeFromFunctionMemoryObject(PointerObjectIndex index) const;
 
  [[nodiscard]] PointerObjectIndex
  CreateImportMemoryObject(const LlvmGraphImport & importNode, bool canPoint);
 
  const std::unordered_map<const rvsdg::Output *, PointerObjectIndex> &
  GetRegisterMap() const noexcept;
 
  const std::unordered_map<const rvsdg::SimpleNode *, PointerObjectIndex> &
  GetAllocaMap() const noexcept;
 
  const std::unordered_map<const rvsdg::SimpleNode *, PointerObjectIndex> &
  GetMallocMap() const noexcept;
 
  const std::unordered_map<const rvsdg::DeltaNode *, PointerObjectIndex> &
  GetGlobalMap() const noexcept;
 
  const util::BijectiveMap<const rvsdg::LambdaNode *, PointerObjectIndex> &
  GetFunctionMap() const noexcept;
 
  const std::unordered_map<const LlvmGraphImport *, PointerObjectIndex> &
  GetImportMap() const noexcept;
 
  [[nodiscard]] PointerObjectKind
  GetPointerObjectKind(PointerObjectIndex index) const noexcept;
 
  [[nodiscard]] bool
  CanPoint(PointerObjectIndex index) const noexcept;
 
  [[nodiscard]] bool
  IsPointerObjectRegister(PointerObjectIndex index) const noexcept;
 
  [[nodiscard]] bool
  HasEscaped(PointerObjectIndex index) const noexcept;
 
  bool
  MarkAsEscaped(PointerObjectIndex index);
 
  [[nodiscard]] bool
  HasPointeesEscaping(PointerObjectIndex index) const noexcept;
 
  bool
  MarkAsPointeesEscaping(PointerObjectIndex index);
 
  [[nodiscard]] bool
  IsPointingToExternal(PointerObjectIndex index) const noexcept;
 
  bool
  MarkAsPointingToExternal(PointerObjectIndex index);
 
  [[nodiscard]] bool
  CanTrackPointeesImplicitly(PointerObjectIndex index) const noexcept;
 
  bool
  MarkAsStoringAsScalar(PointerObjectIndex index);
 
  [[nodiscard]] bool
  IsStoredAsScalar(PointerObjectIndex index) const noexcept;
 
  bool
  MarkAsLoadingAsScalar(PointerObjectIndex index);
 
  [[nodiscard]] bool
  IsLoadedAsScalar(PointerObjectIndex index) const noexcept;
 
  [[nodiscard]] PointerObjectIndex
  GetUnificationRoot(PointerObjectIndex index) const noexcept;
 
  [[nodiscard]] bool
  IsUnificationRoot(PointerObjectIndex index) const noexcept;
 
  PointerObjectIndex
  UnifyPointerObjects(PointerObjectIndex object1, PointerObjectIndex object2);
 
  [[nodiscard]] const util::HashSet<PointerObjectIndex> &
  GetPointsToSet(PointerObjectIndex index) const;
 
  bool
  AddToPointsToSet(PointerObjectIndex pointer, PointerObjectIndex pointee);
 
  bool
  MakePointsToSetSuperset(PointerObjectIndex superset, PointerObjectIndex subset);
 
  bool
  MakePointsToSetSuperset(
      PointerObjectIndex superset,
      PointerObjectIndex subset,
      util::HashSet<PointerObjectIndex> & newPointees);
 
  void
  RemoveAllPointees(PointerObjectIndex index);
 
  bool
  IsPointingTo(PointerObjectIndex pointer, PointerObjectIndex pointee) const;
 
  [[nodiscard]] std::unique_ptr<PointerObjectSet>
  Clone() const;
 
  [[nodiscard]] bool
  HasIdenticalSolAs(const PointerObjectSet & other) const;
 
  [[nodiscard]] size_t
  GetNumSetInsertionAttempts() const noexcept;
 
  [[nodiscard]] size_t
  GetNumExplicitPointeesRemoved() const noexcept;
};
 
class SupersetConstraint final
{
  PointerObjectIndex Superset_;
  PointerObjectIndex Subset_;
 
public:
  SupersetConstraint(PointerObjectIndex superset, PointerObjectIndex subset)
      : Superset_(superset),
        Subset_(subset)
  {}
 
  [[nodiscard]] PointerObjectIndex
  GetSuperset() const noexcept
  {
    return Superset_;
  }
 
  void
  SetSuperset(PointerObjectIndex superset)
  {
    Superset_ = superset;
  }
 
  [[nodiscard]] PointerObjectIndex
  GetSubset() const noexcept
  {
    return Subset_;
  }
 
  void
  SetSubset(PointerObjectIndex subset)
  {
    Subset_ = subset;
  }
 
  bool
  ApplyDirectly(PointerObjectSet & set);
};
 
class StoreConstraint final
{
  PointerObjectIndex Pointer_;
  PointerObjectIndex Value_;
 
public:
  StoreConstraint(PointerObjectIndex pointer, PointerObjectIndex value)
      : Pointer_(pointer),
        Value_(value)
  {}
 
  [[nodiscard]] PointerObjectIndex
  GetValue() const noexcept
  {
    return Value_;
  }
 
  void
  SetValue(PointerObjectIndex value)
  {
    Value_ = value;
  }
 
  [[nodiscard]] PointerObjectIndex
  GetPointer() const noexcept
  {
    return Pointer_;
  }
 
  void
  SetPointer(PointerObjectIndex pointer)
  {
    Pointer_ = pointer;
  }
 
  bool
  ApplyDirectly(PointerObjectSet & set);
};
 
class LoadConstraint final
{
  PointerObjectIndex Value_;
  PointerObjectIndex Pointer_;
 
public:
  LoadConstraint(PointerObjectIndex value, PointerObjectIndex pointer)
      : Value_(value),
        Pointer_(pointer)
  {}
 
  [[nodiscard]] PointerObjectIndex
  GetValue() const noexcept
  {
    return Value_;
  }
 
  void
  SetValue(PointerObjectIndex value)
  {
    Value_ = value;
  }
 
  [[nodiscard]] PointerObjectIndex
  GetPointer() const noexcept
  {
    return Pointer_;
  }
 
  void
  SetPointer(PointerObjectIndex pointer)
  {
    Pointer_ = pointer;
  }
 
  bool
  ApplyDirectly(PointerObjectSet & set);
};
 
class FunctionCallConstraint final
{
  PointerObjectIndex Pointer_;
 
  const rvsdg::SimpleNode & CallNode_;
 
public:
  FunctionCallConstraint(PointerObjectIndex pointer, const rvsdg::SimpleNode & callNode)
      : Pointer_(pointer),
        CallNode_(callNode)
  {
    JLM_ASSERT(is<CallOperation>(callNode.GetOperation()));
  }
 
  [[nodiscard]] PointerObjectIndex
  GetPointer() const noexcept
  {
    return Pointer_;
  }
 
  void
  SetPointer(PointerObjectIndex pointer)
  {
    Pointer_ = pointer;
  }
 
  [[nodiscard]] const rvsdg::SimpleNode &
  GetCallNode() const noexcept
  {
    return CallNode_;
  }
 
  bool
  ApplyDirectly(PointerObjectSet & set);
};
 
class EscapeFlagConstraint final
{
public:
  EscapeFlagConstraint() = delete;
 
  static bool
  PropagateEscapedFlagsDirectly(PointerObjectSet & set);
};
 
class EscapedFunctionConstraint final
{
public:
  EscapedFunctionConstraint() = delete;
 
  static bool
  PropagateEscapedFunctionsDirectly(PointerObjectSet & set);
};
 
class PointerObjectConstraintSet final
{
public:
  using ConstraintVariant =
      std::variant<SupersetConstraint, StoreConstraint, LoadConstraint, FunctionCallConstraint>;
 
  enum class WorklistSolverPolicy
  {
    LeastRecentlyFired,
 
    TwoPhaseLeastRecentlyFired,
 
    TopologicalSort,
 
    FirstInFirstOut,
 
    LastInFirstOut
  };
 
  [[nodiscard]] static const char *
  WorklistSolverPolicyToString(WorklistSolverPolicy policy);
 
  struct WorklistStatistics
  {
    explicit WorklistStatistics(WorklistSolverPolicy policy)
        : Policy(policy)
    {}
 
    WorklistSolverPolicy Policy;
 
    size_t NumWorkItemsPopped{};
 
    size_t NumWorkItemNewPointees{};
 
    std::optional<size_t> NumTopologicalWorklistSweeps;
 
    std::optional<size_t> NumOnlineCyclesDetected;
 
    std::optional<size_t> NumOnlineCycleUnifications;
 
    std::optional<size_t> NumHybridCycleUnifications;
 
    std::optional<size_t> NumLazyCyclesDetectionAttempts;
    std::optional<size_t> NumLazyCyclesDetected;
    std::optional<size_t> NumLazyCycleUnifications;
 
    std::optional<size_t> NumPipExplicitPointeesRemoved;
  };
 
  explicit PointerObjectConstraintSet(PointerObjectSet & set)
      : Set_(set),
        Constraints_(),
        ConstraintSetFrozen_(false)
  {}
 
  PointerObjectConstraintSet(const PointerObjectConstraintSet & other) = delete;
 
  PointerObjectConstraintSet(PointerObjectConstraintSet && other) = delete;
 
  PointerObjectConstraintSet &
  operator=(const PointerObjectConstraintSet & other) = delete;
 
  PointerObjectConstraintSet &
  operator=(PointerObjectConstraintSet && other) = delete;
 
  [[nodiscard]] bool
  IsFrozen() const noexcept;
 
  void
  AddPointerPointeeConstraint(PointerObjectIndex pointer, PointerObjectIndex pointee);
 
  void
  AddPointsToExternalConstraint(PointerObjectIndex pointer);
 
  void
  AddRegisterContentEscapedConstraint(PointerObjectIndex registerIndex);
 
  void
  AddConstraint(ConstraintVariant c);
 
  [[nodiscard]] const std::vector<ConstraintVariant> &
  GetConstraints() const noexcept;
 
  [[nodiscard]] size_t
  NumBaseConstraints() const noexcept;
 
  [[nodiscard]] std::pair<size_t, size_t>
  NumFlagConstraints() const noexcept;
 
  util::graph::Graph &
  DrawSubsetGraph(util::graph::Writer & writer) const;
 
  size_t
  PerformOfflineVariableSubstitution(bool storeRefCycleUnificationRoot);
 
  size_t
  NormalizeConstraints();
 
  WorklistStatistics
  SolveUsingWorklist(
      WorklistSolverPolicy policy,
      bool enableOnlineCycleDetection,
      bool enableHybridCycleDetection,
      bool enableLazyCycleDetection,
      bool enableDifferencePropagation,
      bool enablePreferImplicitPropation);
 
  size_t
  SolveNaively();
 
  std::pair<std::unique_ptr<PointerObjectSet>, std::unique_ptr<PointerObjectConstraintSet>>
  Clone() const;
 
private:
  std::tuple<size_t, std::vector<util::HashSet<PointerObjectIndex>>, std::vector<bool>>
  CreateOvsSubsetGraph();
 
  template<
      typename Worklist,
      bool EnableOnlineCycleDetection,
      bool EnableHybridCycleDetection,
      bool EnableLazyCycleDetection,
      bool EnableDifferencePropagation,
      bool EnablePreferImplicitPointees>
  void
  RunWorklistSolver(WorklistStatistics & statistics);
 
  // The PointerObjectSet being built upon
  PointerObjectSet & Set_;
 
  // Lists of all constraints, of all different types
  std::vector<ConstraintVariant> Constraints_;
 
  // When true, no new constraints can be added.
  // Only offline processing is allowed to modify the constraint set.
  bool ConstraintSetFrozen_;
 
  // Offline Variable Substitution can determine that all pointees of a node p,
  // should be unified together, possibly with some other PointerObjects.
  // This happens when *p is in a cycle with regular nodes
  std::unordered_map<PointerObjectIndex, PointerObjectIndex> RefNodeUnificationRoot_;
};
 
} // namespace jlm::llvm::aa
 
#endif