PointsToGraph.hpp

Go to the documentation of this file.

/*
 * Copyright 2020 Nico Reißmann <nico.reissmann@gmail.com>
 * Copyright 2025 Håvard Krogstie <krogstie.havard@gmail.com>
 * See COPYING for terms of redistribution.
 */
 
#ifndef JLM_LLVM_OPT_ALIAS_ANALYSES_POINTSTOGRAPH_HPP
#define JLM_LLVM_OPT_ALIAS_ANALYSES_POINTSTOGRAPH_HPP
 
#include <jlm/llvm/ir/operators/delta.hpp>
#include <jlm/llvm/ir/operators/lambda.hpp>
#include <jlm/rvsdg/node.hpp>
#include <jlm/util/common.hpp>
#include <jlm/util/HashSet.hpp>
#include <jlm/util/iterator_range.hpp>
#include <jlm/util/Math.hpp>
 
#include <memory>
#include <optional>
#include <string>
#include <unordered_map>
 
namespace jlm::util::graph
{
class Writer;
}
 
namespace jlm::llvm
{
 
class LlvmRvsdgModule;
 
namespace aa
{
 
class PointsToGraph final
{
public:
  using NodeIndex = uint32_t;
 
  // The external node, representing all memory not represented by any other memory node
  static constexpr NodeIndex externalMemoryNode = 0;
 
  enum class NodeKind : uint8_t
  {
    // Register nodes can never be the target of pointers, and cannot be externally available
    RegisterNode = 0,
    // All other kinds of nodes are memory nodes, representing one or more memory locations
    AllocaNode,
    DeltaNode,
    ImportNode,
    LambdaNode,
    MallocNode,
    // Only one external node exists. It represents all memory not represented by any other node.
    ExternalNode,
    COUNT
  };
 
private:
  struct NodeData
  {
    // The kind of node
    NodeKind kind : util::BitWidthOfEnum(NodeKind::COUNT);
 
    // When set, the node is available from other modules in the program
    uint8_t isExternallyAvailable : 1;
 
    // When set, the points-to graph node implicitly targets all externally available nodes
    uint8_t isTargetingAllExternallyAvailable : 1;
 
    // When set, the node represents constant memory / a constant register
    uint8_t isConstant : 1;
 
    // The size of the memory allocation(s) represented by the node.
    // If the size is unknown, or too large to represent, it is set to UnknownMemorySize
    uint16_t memorySize : 10;
    static constexpr uint16_t UnknownMemorySize = (1 << 10) - 1;
 
    NodeData(
        NodeKind kind,
        bool externallyAvailable,
        bool targetsAllExternallyAvailable,
        bool isConstant,
        std::optional<size_t> memorySize)
        : kind(kind),
          isExternallyAvailable(externallyAvailable),
          isTargetingAllExternallyAvailable(targetsAllExternallyAvailable),
          isConstant(isConstant),
          memorySize(
              memorySize.has_value() && *memorySize < UnknownMemorySize ? *memorySize
                                                                        : UnknownMemorySize)
    {}
  };
 
  static_assert(sizeof(NodeData) == sizeof(uint16_t), "NodeData must fit in 16 bits");
 
  using AllocaNodeMap = std::unordered_map<const rvsdg::SimpleNode *, NodeIndex>;
  using DeltaNodeMap = std::unordered_map<const rvsdg::DeltaNode *, NodeIndex>;
  using ImportNodeMap = std::unordered_map<const rvsdg::GraphImport *, NodeIndex>;
  using LambdaNodeMap = std::unordered_map<const rvsdg::LambdaNode *, NodeIndex>;
  using MallocNodeMap = std::unordered_map<const rvsdg::SimpleNode *, NodeIndex>;
  using RegisterNodeMap = std::unordered_map<const rvsdg::Output *, NodeIndex>;
 
  using AllocaNodeIterator = util::MapValueIterator<const NodeIndex, AllocaNodeMap::const_iterator>;
  using AllocaNodeRange = util::IteratorRange<AllocaNodeIterator>;
 
  using DeltaNodeIterator = util::MapValueIterator<const NodeIndex, DeltaNodeMap::const_iterator>;
  using DeltaNodeRange = util::IteratorRange<DeltaNodeIterator>;
 
  using ImportNodeIterator = util::MapValueIterator<const NodeIndex, ImportNodeMap::const_iterator>;
  using ImportNodeRange = util::IteratorRange<ImportNodeIterator>;
 
  using LambdaNodeIterator = util::MapValueIterator<const NodeIndex, LambdaNodeMap::const_iterator>;
  using LambdaNodeRange = util::IteratorRange<LambdaNodeIterator>;
 
  using MallocNodeIterator = util::MapValueIterator<const NodeIndex, MallocNodeMap::const_iterator>;
  using MallocNodeRange = util::IteratorRange<MallocNodeIterator>;
 
  using RegisterNodeIterator = std::vector<NodeIndex>::const_iterator;
  using RegisterNodeRange = util::IteratorRange<RegisterNodeIterator>;
 
  using ExternallyAvailableIterator = std::vector<NodeIndex>::const_iterator;
  using ExternallyAvailableRange = util::IteratorRange<ExternallyAvailableIterator>;
 
  PointsToGraph();
 
public:
  PointsToGraph(const PointsToGraph &) = delete;
 
  PointsToGraph(PointsToGraph &&) = delete;
 
  PointsToGraph &
  operator=(const PointsToGraph &) = delete;
 
  PointsToGraph &
  operator=(PointsToGraph &&) = delete;
 
  AllocaNodeRange
  allocaNodes() const noexcept;
 
  DeltaNodeRange
  deltaNodes() const noexcept;
 
  ImportNodeRange
  importNodes() const noexcept;
 
  LambdaNodeRange
  lambdaNodes() const noexcept;
 
  MallocNodeRange
  mallocNodes() const noexcept;
 
  NodeIndex
  getExternalMemoryNode() const noexcept;
 
  RegisterNodeRange
  registerNodes() const noexcept;
 
  size_t
  numAllocaNodes() const noexcept
  {
    return allocaMap_.size();
  }
 
  size_t
  numDeltaNodes() const noexcept
  {
    return deltaMap_.size();
  }
 
  size_t
  numImportNodes() const noexcept
  {
    return importMap_.size();
  }
 
  size_t
  numLambdaNodes() const noexcept
  {
    return lambdaMap_.size();
  }
 
  size_t
  numMallocNodes() const noexcept
  {
    return mallocMap_.size();
  }
 
  [[nodiscard]] size_t
  numRegisterNodes() const noexcept
  {
    return registerNodes_.size();
  }
 
  [[nodiscard]] size_t
  numMappedRegisters() const noexcept
  {
    return registerMap_.size();
  }
 
  size_t
  numMemoryNodes() const noexcept
  {
    return numAllocaNodes() + numDeltaNodes() + numImportNodes() + numLambdaNodes()
         + numMallocNodes() + 1; // The external node
  }
 
  size_t
  numNodes() const noexcept
  {
    JLM_ASSERT(nodeData_.size() == nodeExplicitTargets_.size());
    JLM_ASSERT(nodeData_.size() == nodeObjects_.size());
    return nodeData_.size();
  }
 
  [[nodiscard]] bool
  hasNodeForAlloca(const rvsdg::SimpleNode & node) const
  {
    return allocaMap_.find(&node) != allocaMap_.end();
  }
 
  [[nodiscard]] bool
  hasNodeForDelta(const rvsdg::DeltaNode & node) const
  {
    return deltaMap_.find(&node) != deltaMap_.end();
  }
 
  [[nodiscard]] bool
  hasNodeForImport(const rvsdg::GraphImport & argument) const
  {
    return importMap_.find(&argument) != importMap_.end();
  }
 
  [[nodiscard]] bool
  hasNodeForLambda(const rvsdg::LambdaNode & node) const
  {
    return lambdaMap_.find(&node) != lambdaMap_.end();
  }
 
  [[nodiscard]] bool
  hasNodeForMalloc(const rvsdg::SimpleNode & node) const
  {
    return mallocMap_.find(&node) != mallocMap_.end();
  }
 
  [[nodiscard]] bool
  hasNodeForRegister(const rvsdg::Output & output) const
  {
    return registerMap_.find(&output) != registerMap_.end();
  }
 
  [[nodiscard]] NodeIndex
  getNodeForAlloca(const rvsdg::SimpleNode & node) const
  {
    return allocaMap_.at(&node);
  }
 
  NodeIndex
  getNodeForDelta(const rvsdg::DeltaNode & node) const
  {
    return deltaMap_.at(&node);
  }
 
  NodeIndex
  getNodeForImport(const rvsdg::GraphImport & argument) const
  {
    return importMap_.at(&argument);
  }
 
  NodeIndex
  getNodeForLambda(const rvsdg::LambdaNode & node) const
  {
    return lambdaMap_.at(&node);
  }
 
  NodeIndex
  getNodeForMalloc(const rvsdg::SimpleNode & node) const
  {
    return mallocMap_.at(&node);
  }
 
  NodeIndex
  getNodeForRegister(const rvsdg::Output & output) const
  {
    return registerMap_.at(&output);
  }
 
  [[nodiscard]] std::optional<NodeIndex>
  tryGetNodeForRegister(const rvsdg::Output & output) const noexcept
  {
    auto it = registerMap_.find(&output);
    if (it != registerMap_.end())
      return it->second;
    return std::nullopt;
  }
 
  [[nodiscard]] NodeKind
  getNodeKind(NodeIndex index) const
  {
    JLM_ASSERT(index < nodeData_.size());
    return nodeData_[index].kind;
  }
 
  [[nodiscard]] bool
  isRegisterNode(NodeIndex index) const
  {
    return getNodeKind(index) == NodeKind::RegisterNode;
  }
 
  [[nodiscard]] bool
  isMemoryNode(NodeIndex index) const
  {
    return !isRegisterNode(index);
  }
 
  [[nodiscard]] bool
  isExternallyAvailable(NodeIndex index) const
  {
    JLM_ASSERT(index < nodeData_.size());
    return nodeData_[index].isExternallyAvailable;
  }
 
  [[nodiscard]] bool
  isTargetingAllExternallyAvailable(NodeIndex index) const
  {
    JLM_ASSERT(index < nodeData_.size());
    return nodeData_[index].isTargetingAllExternallyAvailable;
  }
 
  [[nodiscard]] bool
  isNodeConstant(NodeIndex index) const noexcept
  {
    JLM_ASSERT(index < nodeData_.size());
    return nodeData_[index].isConstant;
  }
 
  [[nodiscard]] std::optional<size_t>
  tryGetNodeSize(NodeIndex index) const noexcept
  {
    JLM_ASSERT(index < nodeData_.size());
    const auto size = nodeData_[index].memorySize;
    if (size == NodeData::UnknownMemorySize)
      return std::nullopt;
    return size;
  }
 
  [[nodiscard]] const util::HashSet<NodeIndex> &
  getExplicitTargets(NodeIndex index) const
  {
    JLM_ASSERT(index < nodeExplicitTargets_.size());
    return nodeExplicitTargets_[index];
  }
 
  [[nodiscard]] bool
  isTargeting(NodeIndex source, NodeIndex target) const
  {
    if (isTargetingAllExternallyAvailable(source) && isExternallyAvailable(target))
      return true;
    return getExplicitTargets(source).Contains(target);
  }
 
  const std::vector<NodeIndex> &
  getExternallyAvailableNodes() const noexcept
  {
    return externallyAvailableNodes_;
  }
 
  size_t
  numExternallyAvailableNodes() const noexcept
  {
    return externallyAvailableNodes_.size();
  }
 
  size_t
  numNodesTargetingAllExternallyAvailable() const noexcept
  {
    return numNodesTargetingAllExternallyAvailable_;
  }
 
  const rvsdg::SimpleNode &
  getAllocaForNode(NodeIndex index) const
  {
    JLM_ASSERT(index < nodeObjects_.size());
    if (nodeData_[index].kind != NodeKind::AllocaNode)
      throw std::logic_error("PointsToGraph node is not an AllocaNode");
    return *static_cast<const rvsdg::SimpleNode *>(nodeObjects_[index]);
  }
 
  const rvsdg::DeltaNode &
  getDeltaForNode(NodeIndex index) const
  {
    JLM_ASSERT(index < nodeObjects_.size());
    if (nodeData_[index].kind != NodeKind::DeltaNode)
      throw std::logic_error("PointsToGraph node is not a DeltaNode");
    return *static_cast<const rvsdg::DeltaNode *>(nodeObjects_[index]);
  }
 
  const rvsdg::GraphImport &
  getImportForNode(NodeIndex index) const
  {
    JLM_ASSERT(index < nodeObjects_.size());
    if (nodeData_[index].kind != NodeKind::ImportNode)
      throw std::logic_error("PointsToGraph node is not an ImportNode");
    return *static_cast<const rvsdg::GraphImport *>(nodeObjects_[index]);
  }
 
  const rvsdg::LambdaNode &
  getLambdaForNode(NodeIndex index) const
  {
    JLM_ASSERT(index < nodeObjects_.size());
    if (nodeData_[index].kind != NodeKind::LambdaNode)
      throw std::logic_error("PointsToGraph node is not a LambdaNode");
    return *static_cast<const rvsdg::LambdaNode *>(nodeObjects_[index]);
  }
 
  const rvsdg::SimpleNode &
  getMallocForNode(NodeIndex index) const
  {
    JLM_ASSERT(index < nodeObjects_.size());
    if (nodeData_[index].kind != NodeKind::MallocNode)
      throw std::logic_error("PointsToGraph node is not a MallocNode");
    return *static_cast<const rvsdg::SimpleNode *>(nodeObjects_[index]);
  }
 
  NodeIndex
  addNodeForAlloca(const rvsdg::SimpleNode & allocaNode, bool externallyAvailable);
 
  NodeIndex
  addNodeForDelta(const rvsdg::DeltaNode & deltaNode, bool externallyAvailable);
 
  NodeIndex
  addNodeForImport(const rvsdg::GraphImport & argument, bool externallyAvailable);
 
  NodeIndex
  addNodeForLambda(const rvsdg::LambdaNode & lambdaNode, bool externallyAvailable);
 
  NodeIndex
  addNodeForMalloc(const rvsdg::SimpleNode & mallocNode, bool externallyAvailable);
 
  [[nodiscard]] NodeIndex
  addNodeForRegisters();
 
  void
  mapRegisterToNode(const rvsdg::Output & output, NodeIndex nodeIndex);
 
  void
  markAsTargetsAllExternallyAvailable(NodeIndex index);
 
  bool
  addTarget(NodeIndex source, NodeIndex target);
 
  [[nodiscard]] std::pair<size_t, size_t>
  numEdges() const noexcept;
 
  [[nodiscard]] std::string
  getNodeDebugString(NodeIndex index, char separator = ' ') const;
 
  [[nodiscard]] bool
  isSupergraphOf(const PointsToGraph & subgraph) const;
 
  static void
  dumpGraph(util::graph::Writer & graphWriter, const PointsToGraph & pointsToGraph);
 
  static std::string
  dumpDot(const PointsToGraph & pointsToGraph);
 
  static std::unique_ptr<PointsToGraph>
  create()
  {
    return std::unique_ptr<PointsToGraph>(new PointsToGraph());
  }
 
private:
  NodeIndex
  addNode(
      NodeKind kind,
      bool externallyAvailable,
      bool isConstant,
      std::optional<size_t> memorySize,
      const void * object);
 
  // Vectors containing information per node
  std::vector<NodeData> nodeData_;
  // For each node, the set of memory nodes that it explicitly targets
  std::vector<util::HashSet<NodeIndex>> nodeExplicitTargets_;
  // For each memory node, this vector contains a pointer to the associated RVSDG object.
  std::vector<const void *> nodeObjects_;
 
  // Mappings from RVSDG objects to their corresponding PointsToGraph NodeIndex
  AllocaNodeMap allocaMap_;
  DeltaNodeMap deltaMap_;
  ImportNodeMap importMap_;
  LambdaNodeMap lambdaMap_;
  MallocNodeMap mallocMap_;
 
  // RegisterNode is the only kind of PointsToGraph nodes where multiple
  // \ref rvsdg::Output* can be mapped to the same PointsToGraph node.
  RegisterNodeMap registerMap_;
 
  // In-order list of node indices containing all nodes of RegisterNode kind
  std::vector<NodeIndex> registerNodes_;
  // In-order list of node indices containing all nodes that are flagged isExternallyAvailable
  std::vector<NodeIndex> externallyAvailableNodes_;
  // The number of nodes that have the isTargetingAllExternallyAvailable flag
  size_t numNodesTargetingAllExternallyAvailable_ = 0;
};
 
}
}
 
#endif