[DDG] Data Dependence Graph - Ordinals

Summary:
This patch associates ordinal numbers to the DDG Nodes allowing
the builder to order nodes within a pi-block in program order. The
algorithm works by simply assuming the order in which the BBList
is fed into the builder. The builder already relies on the blocks being
in program order so that it can compute the dependencies correctly.
Similarly the order of instructions in their parent basic blocks
determine their program order.

Authored By: bmahjour

Reviewer: Meinersbur, fhahn, myhsu, xtian, dmgreen, kbarton, jdoerfert

Reviewed By: Meinersbur

Subscribers: ychen, arphaman, simoll, a.elovikov, mgorny, hiraditya, jfb, wuzish, llvm-commits, jsji, Whitney, etiotto, ppc-slack

Tags: #llvm

Differential Revision: https://reviews.llvm.org/D70986

1 files changed, 21 insertions, 0 deletions

diff --git a/llvm/lib/Analysis/DependenceGraphBuilder.cpp b/llvm/lib/Analysis/DependenceGraphBuilder.cpp
index 98bb09d792b..e8a1a2fff91 100644
--- a/llvm/lib/Analysis/DependenceGraphBuilder.cpp
+++ b/llvm/lib/Analysis/DependenceGraphBuilder.cpp
@@ -37,6 +37,15 @@ using InstructionListType = SmallVector<Instruction *, 2>;
 //===--------------------------------------------------------------------===//
 
 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");
@@ -44,6 +53,7 @@ void AbstractDependenceGraphBuilder<G>::createFineGrainedNodes() {
     for (Instruction &I : *BB) {
       auto &NewNode = createFineGrainedNode(I);
       IMap.insert(std::make_pair(&I, &NewNode));
+      NodeOrdinalMap.insert(std::make_pair(&NewNode, getOrdinal(I)));
       ++TotalFineGrainedNodes;
     }
 }
@@ -107,6 +117,13 @@ template <class G> void AbstractDependenceGraphBuilder<G>::createPiBlocks() {
     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;
 
@@ -200,6 +217,10 @@ template <class G> void AbstractDependenceGraphBuilder<G>::createPiBlocks() {
     }
   }
 
+  // Ordinal maps are no longer needed.
+  InstOrdinalMap.clear();
+  NodeOrdinalMap.clear();
+
   LLVM_DEBUG(dbgs() << "==== End of Creation of Pi-Blocks ===\n");
 }