From 86acaa9457d3957cbe303e1e801f1e727f66ca89 Mon Sep 17 00:00:00 2001
From: Bardia Mahjour <bmahjour@ca.ibm.com>
Date: Thu, 19 Dec 2019 10:56:44 -0500
Subject: [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
---
 llvm/lib/Analysis/DependenceGraphBuilder.cpp | 21 +++++++++++++++++++++
 1 file changed, 21 insertions(+)

(limited to 'llvm/lib/Analysis/DependenceGraphBuilder.cpp')

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
@@ -36,6 +36,15 @@ 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;
@@ -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");
 }
 
-- 
cgit v1.2.3