[Hexagon] Memoize instruction positions in BitTracker

llvm-svn: 324250

2 files changed, 22 insertions, 10 deletions

diff --git a/llvm/lib/Target/Hexagon/BitTracker.cpp b/llvm/lib/Target/Hexagon/BitTracker.cpp
index 15d6a05a007..378aafbc8dd 100644
--- a/llvm/lib/Target/Hexagon/BitTracker.cpp
+++ b/llvm/lib/Target/Hexagon/BitTracker.cpp
@@ -779,15 +779,18 @@ bool BT::UseQueueType::Cmp::operator()(const MachineInstr *InstA,
     return BA->getNumber() > BB->getNumber();
   }
 
-  MachineBasicBlock::const_iterator ItA = InstA->getIterator();
-  MachineBasicBlock::const_iterator ItB = InstB->getIterator();
-  MachineBasicBlock::const_iterator End = BA->end();
-  while (ItA != End) {
-    if (ItA == ItB)
-      return false;   // ItA was before ItB.
-    ++ItA;
-  }
-  return true;
+  auto getDist = [this] (const MachineInstr *MI) {
+    auto F = Dist.find(MI);
+    if (F != Dist.end())
+      return F->second;
+    MachineBasicBlock::const_iterator I = MI->getParent()->begin();
+    MachineBasicBlock::const_iterator E = MI->getIterator();
+    unsigned D = std::distance(I, E);
+    Dist.insert(std::make_pair(MI, D));
+    return D;
+  };
+
+  return getDist(InstA) > getDist(InstB);
 }
 
 // Main W-Z implementation.
@@ -1138,6 +1141,7 @@ void BT::run() {
     runEdgeQueue(BlockScanned);
     runUseQueue();
   }
+  UseQ.reset();
 
   if (Trace)
     print_cells(dbgs() << "Cells after propagation:\n");
diff --git a/llvm/lib/Target/Hexagon/BitTracker.h b/llvm/lib/Target/Hexagon/BitTracker.h
index 6004dbe1fbf..058225c0d81 100644
--- a/llvm/lib/Target/Hexagon/BitTracker.h
+++ b/llvm/lib/Target/Hexagon/BitTracker.h
@@ -73,6 +73,8 @@ private:
   // Priority queue of instructions using modified registers, ordered by
   // their relative position in a basic block.
   struct UseQueueType {
+    UseQueueType() : Uses(Dist) {}
+
     unsigned size() const {
       return Uses.size();
     }
@@ -90,12 +92,18 @@ private:
       Set.erase(front());
       Uses.pop();
     }
+    void reset() {
+      Dist.clear();
+    }
   private:
     struct Cmp {
+      Cmp(DenseMap<const MachineInstr*,unsigned> &Map) : Dist(Map) {}
       bool operator()(const MachineInstr *MI, const MachineInstr *MJ) const;
+      DenseMap<const MachineInstr*,unsigned> &Dist;
     };
     std::priority_queue<MachineInstr*, std::vector<MachineInstr*>, Cmp> Uses;
-    DenseSet<MachineInstr*> Set; // Set to avoid adding duplicate entries.
+    DenseSet<const MachineInstr*> Set; // Set to avoid adding duplicate entries.
+    DenseMap<const MachineInstr*,unsigned> Dist;
   };
 
   void reset();