[FastISel] Fix local value sinking algorithmic complexity

Now local value sinking only scans and numbers instructions added
between the current flush point and the last flush point. This ensures
that ISel is overall linear in the size of the BB.

Fixes PR37010 and re-enables local value sinking by default.

llvm-svn: 331087

1 files changed, 12 insertions, 3 deletions

diff --git a/llvm/lib/CodeGen/SelectionDAG/FastISel.cpp b/llvm/lib/CodeGen/SelectionDAG/FastISel.cpp
index 84196062491..23a7798f867 100644
--- a/llvm/lib/CodeGen/SelectionDAG/FastISel.cpp
+++ b/llvm/lib/CodeGen/SelectionDAG/FastISel.cpp
@@ -215,6 +215,7 @@ void FastISel::flushLocalValueMap() {
   LastLocalValue = EmitStartPt;
   recomputeInsertPt();
   SavedInsertPt = FuncInfo.InsertPt;
+  LastFlushPoint = FuncInfo.InsertPt;
 }
 
 static bool isRegUsedByPhiNodes(unsigned DefReg,
@@ -228,7 +229,8 @@ static bool isRegUsedByPhiNodes(unsigned DefReg,
 /// Build a map of instruction orders. Return the first terminator and its
 /// order. Consider EH_LABEL instructions to be terminators as well, since local
 /// values for phis after invokes must be materialized before the call.
-void FastISel::InstOrderMap::initialize(MachineBasicBlock *MBB) {
+void FastISel::InstOrderMap::initialize(
+    MachineBasicBlock *MBB, MachineBasicBlock::iterator LastFlushPoint) {
   unsigned Order = 0;
   for (MachineInstr &I : *MBB) {
     if (!FirstTerminator &&
@@ -237,6 +239,10 @@ void FastISel::InstOrderMap::initialize(MachineBasicBlock *MBB) {
       FirstTerminatorOrder = Order;
     }
     Orders[&I] = Order++;
+
+    // We don't need to order instructions past the last flush point.
+    if (I.getIterator() == LastFlushPoint)
+      break;
   }
 }
 
@@ -266,13 +272,16 @@ void FastISel::sinkLocalValueMaterialization(MachineInstr &LocalMI,
   // Number the instructions if we haven't yet so we can efficiently find the
   // earliest use.
   if (OrderMap.Orders.empty())
-    OrderMap.initialize(FuncInfo.MBB);
+    OrderMap.initialize(FuncInfo.MBB, LastFlushPoint);
 
   // Find the first user in the BB.
   MachineInstr *FirstUser = nullptr;
   unsigned FirstOrder = std::numeric_limits<unsigned>::max();
   for (MachineInstr &UseInst : MRI.use_nodbg_instructions(DefReg)) {
-    unsigned UseOrder = OrderMap.Orders[&UseInst];
+    auto I = OrderMap.Orders.find(&UseInst);
+    assert(I != OrderMap.Orders.end() &&
+           "local value used by instruction outside local region");
+    unsigned UseOrder = I->second;
     if (UseOrder < FirstOrder) {
       FirstOrder = UseOrder;
       FirstUser = &UseInst;