From 6231d5be410e2d7967352b29ad01522fda15680d Mon Sep 17 00:00:00 2001 From: Chandler Carruth Date: Sat, 24 Mar 2012 22:34:26 +0000 Subject: 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 --- lib/Analysis/InstructionSimplify.cpp | 15 ++++++++------- 1 file changed, 8 insertions(+), 7 deletions(-) (limited to 'lib/Analysis') diff --git a/lib/Analysis/InstructionSimplify.cpp b/lib/Analysis/InstructionSimplify.cpp index c8fb6ae..aaf9de2 100644 --- 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 Worklist; + SmallSetVector 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(*UI)); + Worklist.insert(cast(*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(*UI)); + Worklist.insert(cast(*UI)); // Replace the instruction with its simplified value. I->replaceAllUsesWith(SimpleV); -- cgit v1.1