DependenceGraphBuilder.cpp

//===- DependenceGraphBuilder.cpp ------------------------------------------==//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
// This file implements common steps of the build algorithm for construction
// of dependence graphs such as DDG and PDG.
//===----------------------------------------------------------------------===//

#include "llvm/Analysis/DependenceGraphBuilder.h"
#include "llvm/ADT/DepthFirstIterator.h"
#include "llvm/ADT/EnumeratedArray.h"
#include "llvm/ADT/PostOrderIterator.h"
#include "llvm/ADT/SCCIterator.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/DDG.h"

using namespace llvm;

#define DEBUG_TYPE "dgb"

STATISTIC(TotalGraphs, "Number of dependence graphs created.");
STATISTIC(TotalDefUseEdges, "Number of def-use edges created.");
STATISTIC(TotalMemoryEdges, "Number of memory dependence edges created.");
STATISTIC(TotalFineGrainedNodes, "Number of fine-grained nodes created.");
STATISTIC(TotalPiBlockNodes, "Number of pi-block nodes created.");
STATISTIC(TotalConfusedEdges,
          "Number of confused memory dependencies between two nodes.");
STATISTIC(TotalEdgeReversals,
          "Number of times the source and sink of dependence was reversed to "
          "expose cycles in the graph.");

using InstructionListType = SmallVector<Instruction *, 2>;

//===--------------------------------------------------------------------===//
// AbstractDependenceGraphBuilder implementation
//===--------------------------------------------------------------------===//

template <class G>
void AbstractDependenceGraphBuilder<G>::computeInstructionOrdinals() {
  // The BBList is expected to be in program order.
  size_t NextOrdinal = 1;
  for (auto *BB : BBList)
    for (auto &I : *BB)
      InstOrdinalMap.insert(std::make_pair(&I, NextOrdinal++));
}

template <class G>
void AbstractDependenceGraphBuilder<G>::createFineGrainedNodes() {
  ++TotalGraphs;
  assert(IMap.empty() && "Expected empty instruction map at start");
  for (BasicBlock *BB : BBList)
    for (Instruction &I : *BB) {
      auto &NewNode = createFineGrainedNode(I);
      IMap.insert(std::make_pair(&I, &NewNode));
      NodeOrdinalMap.insert(std::make_pair(&NewNode, getOrdinal(I)));
      ++TotalFineGrainedNodes;
    }
}

template <class G>
void AbstractDependenceGraphBuilder<G>::createAndConnectRootNode() {
  // Create a root node that connects to every connected component of the graph.
  // This is done to allow graph iterators to visit all the disjoint components
  // of the graph, in a single walk.
  //
  // This algorithm works by going through each node of the graph and for each
  // node N, do a DFS starting from N. A rooted edge is established between the
  // root node and N (if N is not yet visited). All the nodes reachable from N
  // are marked as visited and are skipped in the DFS of subsequent nodes.
  //
  // Note: This algorithm tries to limit the number of edges out of the root
  // node to some extent, but there may be redundant edges created depending on
  // the iteration order. For example for a graph {A -> B}, an edge from the
  // root node is added to both nodes if B is visited before A. While it does
  // not result in minimal number of edges, this approach saves compile-time
  // while keeping the number of edges in check.
  auto &RootNode = createRootNode();
  df_iterator_default_set<const NodeType *, 4> Visited;
  for (auto *N : Graph) {
    if (*N == RootNode)
      continue;
    for (auto I : depth_first_ext(N, Visited))
      if (I == N)
        createRootedEdge(RootNode, *N);
  }
}

template <class G> void AbstractDependenceGraphBuilder<G>::createPiBlocks() {
  if (!shouldCreatePiBlocks())
    return;

  LLVM_DEBUG(dbgs() << "==== Start of Creation of Pi-Blocks ===\n");

  // The overall algorithm is as follows:
  // 1. Identify SCCs and for each SCC create a pi-block node containing all
  //    the nodes in that SCC.
  // 2. Identify incoming edges incident to the nodes inside of the SCC and
  //    reconnect them to the pi-block node.
  // 3. Identify outgoing edges from the nodes inside of the SCC to nodes
  //    outside of it and reconnect them so that the edges are coming out of the
  //    SCC node instead.

  // Adding nodes as we iterate through the SCCs cause the SCC
  // iterators to get invalidated. To prevent this invalidation, we first
  // collect a list of nodes that are part of an SCC, and then iterate over
  // those lists to create the pi-block nodes. Each element of the list is a
  // list of nodes in an SCC. Note: trivial SCCs containing a single node are
  // ignored.
  SmallVector<NodeListType, 4> ListOfSCCs;
  for (auto &SCC : make_range(scc_begin(&Graph), scc_end(&Graph))) {
    if (SCC.size() > 1)
      ListOfSCCs.emplace_back(SCC.begin(), SCC.end());
  }

  for (NodeListType &NL : ListOfSCCs) {
    LLVM_DEBUG(dbgs() << "Creating pi-block node with " << NL.size()
                      << " nodes in it.\n");

    // SCC iterator may put the nodes in an order that's different from the
    // program order. To preserve original program order, we sort the list of
    // nodes based on ordinal numbers computed earlier.
    llvm::sort(NL, [&](NodeType *LHS, NodeType *RHS) {
      return getOrdinal(*LHS) < getOrdinal(*RHS);
    });

    NodeType &PiNode = createPiBlock(NL);
    ++TotalPiBlockNodes;

    // Build a set to speed up the lookup for edges whose targets
    // are inside the SCC.
    SmallPtrSet<NodeType *, 4> NodesInSCC(NL.begin(), NL.end());

    // We have the set of nodes in the SCC. We go through the set of nodes
    // that are outside of the SCC and look for edges that cross the two sets.
    for (NodeType *N : Graph) {

      // Skip the SCC node and all the nodes inside of it.
      if (*N == PiNode || NodesInSCC.count(N))
        continue;

      enum Direction {
        Incoming,      // Incoming edges to the SCC
        Outgoing,      // Edges going ot of the SCC
        DirectionCount // To make the enum usable as an array index.
      };

      // Use these flags to help us avoid creating redundant edges. If there
      // are more than one edges from an outside node to inside nodes, we only
      // keep one edge from that node to the pi-block node. Similarly, if
      // there are more than one edges from inside nodes to an outside node,
      // we only keep one edge from the pi-block node to the outside node.
      // There is a flag defined for each direction (incoming vs outgoing) and
      // for each type of edge supported, using a two-dimensional boolean
      // array.
      using EdgeKind = typename EdgeType::EdgeKind;
      EnumeratedArray<bool, EdgeKind> EdgeAlreadyCreated[DirectionCount]{false,
                                                                         false};

      auto createEdgeOfKind = [this](NodeType &Src, NodeType &Dst,
                                     const EdgeKind K) {
        switch (K) {
        case EdgeKind::RegisterDefUse:
          createDefUseEdge(Src, Dst);
          break;
        case EdgeKind::MemoryDependence:
          createMemoryEdge(Src, Dst);
          break;
        case EdgeKind::Rooted:
          createRootedEdge(Src, Dst);
          break;
        default:
          llvm_unreachable("Unsupported type of edge.");
        }
      };

      auto reconnectEdges = [&](NodeType *Src, NodeType *Dst, NodeType *New,
                                const Direction Dir) {
        if (!Src->hasEdgeTo(*Dst))
          return;
        LLVM_DEBUG(
            dbgs() << "reconnecting("
                   << (Dir == Direction::Incoming ? "incoming)" : "outgoing)")
                   << ":\nSrc:" << *Src << "\nDst:" << *Dst << "\nNew:" << *New
                   << "\n");
        assert((Dir == Direction::Incoming || Dir == Direction::Outgoing) &&
               "Invalid direction.");

        SmallVector<EdgeType *, 10> EL;
        Src->findEdgesTo(*Dst, EL);
        for (EdgeType *OldEdge : EL) {
          EdgeKind Kind = OldEdge->getKind();
          if (!EdgeAlreadyCreated[Dir][Kind]) {
            if (Dir == Direction::Incoming) {
              createEdgeOfKind(*Src, *New, Kind);
              LLVM_DEBUG(dbgs() << "created edge from Src to New.\n");
            } else if (Dir == Direction::Outgoing) {
              createEdgeOfKind(*New, *Dst, Kind);
              LLVM_DEBUG(dbgs() << "created edge from New to Dst.\n");
            }
            EdgeAlreadyCreated[Dir][Kind] = true;
          }
          Src->removeEdge(*OldEdge);
          destroyEdge(*OldEdge);
          LLVM_DEBUG(dbgs() << "removed old edge between Src and Dst.\n\n");
        }
      };

      for (NodeType *SCCNode : NL) {
        // Process incoming edges incident to the pi-block node.
        reconnectEdges(N, SCCNode, &PiNode, Direction::Incoming);

        // Process edges that are coming out of the pi-block node.
        reconnectEdges(SCCNode, N, &PiNode, Direction::Outgoing);
      }
    }
  }

  // Ordinal maps are no longer needed.
  InstOrdinalMap.clear();
  NodeOrdinalMap.clear();

  LLVM_DEBUG(dbgs() << "==== End of Creation of Pi-Blocks ===\n");
}

template <class G> void AbstractDependenceGraphBuilder<G>::createDefUseEdges() {
  for (NodeType *N : Graph) {
    InstructionListType SrcIList;
    N->collectInstructions([](const Instruction *I) { return true; }, SrcIList);

    // Use a set to mark the targets that we link to N, so we don't add
    // duplicate def-use edges when more than one instruction in a target node
    // use results of instructions that are contained in N.
    SmallPtrSet<NodeType *, 4> VisitedTargets;

    for (Instruction *II : SrcIList) {
      for (User *U : II->users()) {
        Instruction *UI = dyn_cast<Instruction>(U);
        if (!UI)
          continue;
        NodeType *DstNode = nullptr;
        if (IMap.find(UI) != IMap.end())
          DstNode = IMap.find(UI)->second;

        // In the case of loops, the scope of the subgraph is all the
        // basic blocks (and instructions within them) belonging to the loop. We
        // simply ignore all the edges coming from (or going into) instructions
        // or basic blocks outside of this range.
        if (!DstNode) {
          LLVM_DEBUG(
              dbgs()
              << "skipped def-use edge since the sink" << *UI
              << " is outside the range of instructions being considered.\n");
          continue;
        }

        // Self dependencies are ignored because they are redundant and
        // uninteresting.
        if (DstNode == N) {
          LLVM_DEBUG(dbgs()
                     << "skipped def-use edge since the sink and the source ("
                     << N << ") are the same.\n");
          continue;
        }

        if (VisitedTargets.insert(DstNode).second) {
          createDefUseEdge(*N, *DstNode);
          ++TotalDefUseEdges;
        }
      }
    }
  }
}

template <class G>
void AbstractDependenceGraphBuilder<G>::createMemoryDependencyEdges() {
  using DGIterator = typename G::iterator;
  auto isMemoryAccess = [](const Instruction *I) {
    return I->mayReadOrWriteMemory();
  };
  for (DGIterator SrcIt = Graph.begin(), E = Graph.end(); SrcIt != E; ++SrcIt) {
    InstructionListType SrcIList;
    (*SrcIt)->collectInstructions(isMemoryAccess, SrcIList);
    if (SrcIList.empty())
      continue;

    for (DGIterator DstIt = SrcIt; DstIt != E; ++DstIt) {
      if (**SrcIt == **DstIt)
        continue;
      InstructionListType DstIList;
      (*DstIt)->collectInstructions(isMemoryAccess, DstIList);
      if (DstIList.empty())
        continue;
      bool ForwardEdgeCreated = false;
      bool BackwardEdgeCreated = false;
      for (Instruction *ISrc : SrcIList) {
        for (Instruction *IDst : DstIList) {
          auto D = DI.depends(ISrc, IDst, true);
          if (!D)
            continue;

          // If we have a dependence with its left-most non-'=' direction
          // being '>' we need to reverse the direction of the edge, because
          // the source of the dependence cannot occur after the sink. For
          // confused dependencies, we will create edges in both directions to
          // represent the possibility of a cycle.

          auto createConfusedEdges = [&](NodeType &Src, NodeType &Dst) {
            if (!ForwardEdgeCreated) {
              createMemoryEdge(Src, Dst);
              ++TotalMemoryEdges;
            }
            if (!BackwardEdgeCreated) {
              createMemoryEdge(Dst, Src);
              ++TotalMemoryEdges;
            }
            ForwardEdgeCreated = BackwardEdgeCreated = true;
            ++TotalConfusedEdges;
          };

          auto createForwardEdge = [&](NodeType &Src, NodeType &Dst) {
            if (!ForwardEdgeCreated) {
              createMemoryEdge(Src, Dst);
              ++TotalMemoryEdges;
            }
            ForwardEdgeCreated = true;
          };

          auto createBackwardEdge = [&](NodeType &Src, NodeType &Dst) {
            if (!BackwardEdgeCreated) {
              createMemoryEdge(Dst, Src);
              ++TotalMemoryEdges;
            }
            BackwardEdgeCreated = true;
          };

          if (D->isConfused())
            createConfusedEdges(**SrcIt, **DstIt);
          else if (D->isOrdered() && !D->isLoopIndependent()) {
            bool ReversedEdge = false;
            for (unsigned Level = 1; Level <= D->getLevels(); ++Level) {
              if (D->getDirection(Level) == Dependence::DVEntry::EQ)
                continue;
              else if (D->getDirection(Level) == Dependence::DVEntry::GT) {
                createBackwardEdge(**SrcIt, **DstIt);
                ReversedEdge = true;
                ++TotalEdgeReversals;
                break;
              } else if (D->getDirection(Level) == Dependence::DVEntry::LT)
                break;
              else {
                createConfusedEdges(**SrcIt, **DstIt);
                break;
              }
            }
            if (!ReversedEdge)
              createForwardEdge(**SrcIt, **DstIt);
          } else
            createForwardEdge(**SrcIt, **DstIt);

          // Avoid creating duplicate edges.
          if (ForwardEdgeCreated && BackwardEdgeCreated)
            break;
        }

        // If we've created edges in both directions, there is no more
        // unique edge that we can create between these two nodes, so we
        // can exit early.
        if (ForwardEdgeCreated && BackwardEdgeCreated)
          break;
      }
    }
  }
}

template <class G> void AbstractDependenceGraphBuilder<G>::simplify() {
  if (!shouldSimplify())
    return;
  LLVM_DEBUG(dbgs() << "==== Start of Graph Simplification ===\n");

  // This algorithm works by first collecting a set of candidate nodes that have
  // an out-degree of one (in terms of def-use edges), and then ignoring those
  // whose targets have an in-degree more than one. Each node in the resulting
  // set can then be merged with its corresponding target and put back into the
  // worklist until no further merge candidates are available.
  SmallPtrSet<NodeType *, 32> CandidateSourceNodes;

  // A mapping between nodes and their in-degree. To save space, this map
  // only contains nodes that are targets of nodes in the CandidateSourceNodes.
  DenseMap<NodeType *, unsigned> TargetInDegreeMap;

  for (NodeType *N : Graph) {
    if (N->getEdges().size() != 1)
      continue;
    EdgeType &Edge = N->back();
    if (!Edge.isDefUse())
      continue;
    CandidateSourceNodes.insert(N);

    // Insert an element into the in-degree map and initialize to zero. The
    // count will get updated in the next step.
    TargetInDegreeMap.insert({&Edge.getTargetNode(), 0});
  }

  LLVM_DEBUG({
    dbgs() << "Size of candidate src node list:" << CandidateSourceNodes.size()
           << "\nNode with single outgoing def-use edge:\n";
    for (NodeType *N : CandidateSourceNodes) {
      dbgs() << N << "\n";
    }
  });

  for (NodeType *N : Graph) {
    for (EdgeType *E : *N) {
      NodeType *Tgt = &E->getTargetNode();
      auto TgtIT = TargetInDegreeMap.find(Tgt);
      if (TgtIT != TargetInDegreeMap.end())
        ++(TgtIT->second);
    }
  }

  LLVM_DEBUG({
    dbgs() << "Size of target in-degree map:" << TargetInDegreeMap.size()
           << "\nContent of in-degree map:\n";
    for (auto &I : TargetInDegreeMap) {
      dbgs() << I.first << " --> " << I.second << "\n";
    }
  });

  SmallVector<NodeType *, 32> Worklist(CandidateSourceNodes.begin(),
                                       CandidateSourceNodes.end());
  while (!Worklist.empty()) {
    NodeType &Src = *Worklist.pop_back_val();
    // As nodes get merged, we need to skip any node that has been removed from
    // the candidate set (see below).
    if (!CandidateSourceNodes.erase(&Src))
      continue;

    assert(Src.getEdges().size() == 1 &&
           "Expected a single edge from the candidate src node.");
    NodeType &Tgt = Src.back().getTargetNode();
    assert(TargetInDegreeMap.find(&Tgt) != TargetInDegreeMap.end() &&
           "Expected target to be in the in-degree map.");

    if (TargetInDegreeMap[&Tgt] != 1)
      continue;

    if (!areNodesMergeable(Src, Tgt))
      continue;

    // Do not merge if there is also an edge from target to src (immediate
    // cycle).
    if (Tgt.hasEdgeTo(Src))
      continue;

    LLVM_DEBUG(dbgs() << "Merging:" << Src << "\nWith:" << Tgt << "\n");

    mergeNodes(Src, Tgt);

    // If the target node is in the candidate set itself, we need to put the
    // src node back into the worklist again so it gives the target a chance
    // to get merged into it. For example if we have:
    // {(a)->(b), (b)->(c), (c)->(d), ...} and the worklist is initially {b, a},
    // then after merging (a) and (b) together, we need to put (a,b) back in
    // the worklist so that (c) can get merged in as well resulting in
    // {(a,b,c) -> d}
    // We also need to remove the old target (b), from the worklist. We first
    // remove it from the candidate set here, and skip any item from the
    // worklist that is not in the set.
    if (CandidateSourceNodes.erase(&Tgt)) {
      Worklist.push_back(&Src);
      CandidateSourceNodes.insert(&Src);
      LLVM_DEBUG(dbgs() << "Putting " << &Src << " back in the worklist.\n");
    }
  }
  LLVM_DEBUG(dbgs() << "=== End of Graph Simplification ===\n");
}

template <class G>
void AbstractDependenceGraphBuilder<G>::sortNodesTopologically() {

  // If we don't create pi-blocks, then we may not have a DAG.
  if (!shouldCreatePiBlocks())
    return;

  SmallVector<NodeType *, 64> NodesInPO;
  using NodeKind = typename NodeType::NodeKind;
  for (NodeType *N : post_order(&Graph)) {
    if (N->getKind() == NodeKind::PiBlock) {
      // Put members of the pi-block right after the pi-block itself, for
      // convenience.
      const NodeListType &PiBlockMembers = getNodesInPiBlock(*N);
      llvm::append_range(NodesInPO, PiBlockMembers);
    }
    NodesInPO.push_back(N);
  }

  size_t OldSize = Graph.Nodes.size();
  Graph.Nodes.clear();
  append_range(Graph.Nodes, reverse(NodesInPO));
  if (Graph.Nodes.size() != OldSize)
    assert(false &&
           "Expected the number of nodes to stay the same after the sort");
}

template class llvm::AbstractDependenceGraphBuilder<DataDependenceGraph>;
template class llvm::DependenceGraphInfo<DDGNode>;