Try to harden the recursive simplification still further. This is again

spotted by inspection, and I've crafted no test case that triggers it on
my machine, but some of the windows builders are hitting what looks like
memory corruption, so *something* is amiss here.

This patch takes a more generalized approach to eliminating
double-visits. Imagine code such as:

  %x = ...
  %y = add %x, 1
  %z = add %x, %y

You can imagine that if we simplify %x, we would add %y and %z to the
list. If the use-chain order happens to cause us to add them in reverse
order, we could pull %y off first, and simplify it, adding %z to the
list. We now have %z on the list twice, and will reference it after it
is deleted.

Currently, all my test cases happen to not trigger this, likely due to
the use-chain ordering, but there seems no guarantee that such
a situation could not occur, so we should handle it correctly.

Again, if anyone knows how to craft a testcase that actually triggers
this, please let me know.

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

diff --git a/lib/Analysis/InstructionSimplify.cpp b/lib/Analysis/InstructionSimplify.cpp
index c8fb6ae595b9cc04adaad12eca57054563d24883..aaf9de28da40ff2e6982992ae8b3ce8fba812805 100644 (file)
--- a/lib/Analysis/InstructionSimplify.cpp
+++ b/lib/Analysis/InstructionSimplify.cpp
@@ -21,6 +21,7 @@
 #include "llvm/GlobalAlias.h"
 #include "llvm/Operator.h"
 #include "llvm/ADT/Statistic.h"
+#include "llvm/ADT/SetVector.h"
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/ConstantFolding.h"
@@ -2834,7 +2835,7 @@ static bool replaceAndRecursivelySimplifyImpl(Instruction *I, Value *SimpleV,
                                               const TargetLibraryInfo *TLI,
                                               const DominatorTree *DT) {
   bool Simplified = false;
-  SmallVector<Instruction *, 8> Worklist;
+  SmallSetVector<Instruction *, 8> Worklist;
 
   // If we have an explicit value to collapse to, do that round of the
   // simplification loop by hand initially.
@@ -2842,7 +2843,7 @@ static bool replaceAndRecursivelySimplifyImpl(Instruction *I, Value *SimpleV,
     for (Value::use_iterator UI = I->use_begin(), UE = I->use_end(); UI != UE;
          ++UI)
       if (*UI != I)
-        Worklist.push_back(cast<Instruction>(*UI));
+        Worklist.insert(cast<Instruction>(*UI));
 
     // Replace the instruction with its simplified value.
     I->replaceAllUsesWith(SimpleV);
@@ -2852,11 +2853,12 @@ static bool replaceAndRecursivelySimplifyImpl(Instruction *I, Value *SimpleV,
     if (I->getParent())
       I->eraseFromParent();
   } else {
-    Worklist.push_back(I);
+    Worklist.insert(I);
   }
 
-  while (!Worklist.empty()) {
-    I = Worklist.pop_back_val();
+  // Note that we must test the size on each iteration, the worklist can grow.
+  for (unsigned Idx = 0; Idx != Worklist.size(); ++Idx) {
+    I = Worklist[Idx];
 
     // See if this instruction simplifies.
     SimpleV = SimplifyInstruction(I, TD, TLI, DT);
@@ -2870,8 +2872,7 @@ static bool replaceAndRecursivelySimplifyImpl(Instruction *I, Value *SimpleV,
     // uses of To on the recursive step in most cases.
     for (Value::use_iterator UI = I->use_begin(), UE = I->use_end(); UI != UE;
          ++UI)
-      if (*UI != I)
-        Worklist.push_back(cast<Instruction>(*UI));
+      Worklist.insert(cast<Instruction>(*UI));
 
     // Replace the instruction with its simplified value.
     I->replaceAllUsesWith(SimpleV);