Fix LSR compile time.
authorAndrew Trick <atrick@apple.com>
Sat, 25 Oct 2014 19:42:07 +0000 (19:42 +0000)
committerAndrew Trick <atrick@apple.com>
Sat, 25 Oct 2014 19:42:07 +0000 (19:42 +0000)
This is a simple fix that brings the compilation time from 5min to 5s
on a specific real-world example. It's a large chain of computation in
a crypto routine (always a problem for SCEV). A unit test is not
feasible and there would be no way to check it. The fix is just basic
good practice for dealing with SCEVs, there's no risk of regression.

Patch by Daniel Reynaud!

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@220622 91177308-0d34-0410-b5e6-96231b3b80d8

lib/Transforms/Scalar/LoopStrengthReduce.cpp

index fbc8e0e..e1d18e8 100644 (file)
@@ -3117,10 +3117,15 @@ void
 LSRInstance::CollectLoopInvariantFixupsAndFormulae() {
   SmallVector<const SCEV *, 8> Worklist(RegUses.begin(), RegUses.end());
   SmallPtrSet<const SCEV *, 8> Inserted;
+  SmallPtrSet<const SCEV *, 32> Done;
 
   while (!Worklist.empty()) {
     const SCEV *S = Worklist.pop_back_val();
 
+    // Don't process the same SCEV twice
+    if (!Done.insert(S))
+      continue;
+
     if (const SCEVNAryExpr *N = dyn_cast<SCEVNAryExpr>(S))
       Worklist.append(N->op_begin(), N->op_end());
     else if (const SCEVCastExpr *C = dyn_cast<SCEVCastExpr>(S))