From cb21190cbd8ae1aece5b833ebe3814ada4260627 Mon Sep 17 00:00:00 2001 From: Owen Anderson Date: Tue, 31 Aug 2010 07:36:34 +0000 Subject: [PATCH] More Chris-inspired JumpThreading fixes: use ConstantExpr to correctly constant-fold undef, and be more careful with its return value. This actually exposed an infinite recursion bug in ComputeValueKnownInPredecessors which theoretically already existed (in JumpThreading's handling of and/or of i1's), but never manifested before. This patch adds a tracking set to prevent this case. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@112589 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Transforms/Scalar/JumpThreading.cpp | 90 ++++++++++++++------- .../JumpThreading/2010-08-31-InfiniteRecursion.ll | 91 ++++++++++++++++++++++ 2 files changed, 155 insertions(+), 26 deletions(-) create mode 100644 test/Transforms/JumpThreading/2010-08-31-InfiniteRecursion.ll diff --git a/lib/Transforms/Scalar/JumpThreading.cpp b/lib/Transforms/Scalar/JumpThreading.cpp index 7a4c685516e..afc1661bf8e 100644 --- a/lib/Transforms/Scalar/JumpThreading.cpp +++ b/lib/Transforms/Scalar/JumpThreading.cpp @@ -16,7 +16,6 @@ #include "llvm/IntrinsicInst.h" #include "llvm/LLVMContext.h" #include "llvm/Pass.h" -#include "llvm/Analysis/ConstantFolding.h" #include "llvm/Analysis/InstructionSimplify.h" #include "llvm/Analysis/LazyValueInfo.h" #include "llvm/Analysis/Loads.h" @@ -25,6 +24,7 @@ #include "llvm/Transforms/Utils/SSAUpdater.h" #include "llvm/Target/TargetData.h" #include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/DenseSet.h" #include "llvm/ADT/Statistic.h" #include "llvm/ADT/STLExtras.h" #include "llvm/ADT/SmallPtrSet.h" @@ -78,6 +78,7 @@ namespace { #else SmallSet, 16> LoopHeaders; #endif + DenseSet > RecursionSet; public: static char ID; // Pass identification JumpThreading() : FunctionPass(ID) {} @@ -270,12 +271,17 @@ void JumpThreading::FindLoopHeaders(Function &F) { /// bool JumpThreading:: ComputeValueKnownInPredecessors(Value *V, BasicBlock *BB,PredValueInfo &Result){ + if (!RecursionSet.insert(std::make_pair(V, BB)).second) + return false; + // If V is a constantint, then it is known in all predecessors. if (isa(V) || isa(V)) { ConstantInt *CI = dyn_cast(V); for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) Result.push_back(std::make_pair(CI, *PI)); + + RecursionSet.erase(std::make_pair(V, BB)); return true; } @@ -310,9 +316,11 @@ ComputeValueKnownInPredecessors(Value *V, BasicBlock *BB,PredValueInfo &Result){ Result.push_back(std::make_pair(dyn_cast(PredCst), P)); } + RecursionSet.erase(std::make_pair(V, BB)); return !Result.empty(); } + RecursionSet.erase(std::make_pair(V, BB)); return false; } @@ -328,10 +336,15 @@ ComputeValueKnownInPredecessors(Value *V, BasicBlock *BB,PredValueInfo &Result){ PN->getIncomingBlock(i), BB); // LVI returns null is no value could be determined. if (!CI) continue; - ConstantInt *CInt = dyn_cast(CI); - Result.push_back(std::make_pair(CInt, PN->getIncomingBlock(i))); + if (ConstantInt *CInt = dyn_cast(CI)) + Result.push_back(std::make_pair(CInt, PN->getIncomingBlock(i))); + else if (isa(CI)) + Result.push_back(std::make_pair((ConstantInt*)0, + PN->getIncomingBlock(i))); } } + + RecursionSet.erase(std::make_pair(V, BB)); return !Result.empty(); } @@ -346,8 +359,10 @@ ComputeValueKnownInPredecessors(Value *V, BasicBlock *BB,PredValueInfo &Result){ ComputeValueKnownInPredecessors(I->getOperand(0), BB, LHSVals); ComputeValueKnownInPredecessors(I->getOperand(1), BB, RHSVals); - if (LHSVals.empty() && RHSVals.empty()) + if (LHSVals.empty() && RHSVals.empty()) { + RecursionSet.erase(std::make_pair(V, BB)); return false; + } ConstantInt *InterestingVal; if (I->getOpcode() == Instruction::Or) @@ -374,6 +389,8 @@ ComputeValueKnownInPredecessors(Value *V, BasicBlock *BB,PredValueInfo &Result){ Result.back().first = InterestingVal; } } + + RecursionSet.erase(std::make_pair(V, BB)); return !Result.empty(); } @@ -382,38 +399,48 @@ ComputeValueKnownInPredecessors(Value *V, BasicBlock *BB,PredValueInfo &Result){ isa(I->getOperand(1)) && cast(I->getOperand(1))->isOne()) { ComputeValueKnownInPredecessors(I->getOperand(0), BB, Result); - if (Result.empty()) + if (Result.empty()) { + RecursionSet.erase(std::make_pair(V, BB)); return false; + } // Invert the known values. for (unsigned i = 0, e = Result.size(); i != e; ++i) if (Result[i].first) Result[i].first = cast(ConstantExpr::getNot(Result[i].first)); + + RecursionSet.erase(std::make_pair(V, BB)); return true; } // Try to simplify some other binary operator values. } else if (BinaryOperator *BO = dyn_cast(I)) { - // AND or OR of a value with itself is that value. ConstantInt *CI = dyn_cast(BO->getOperand(1)); - if (CI && (BO->getOpcode() == Instruction::And || - BO->getOpcode() == Instruction::Or)) { + if (CI) { SmallVector, 8> LHSVals; ComputeValueKnownInPredecessors(BO->getOperand(0), BB, LHSVals); - for (unsigned i = 0, e = LHSVals.size(); i != e; ++i) + + // Try to use constant folding to simplify the binary operator. + for (unsigned i = 0, e = LHSVals.size(); i != e; ++i) { + Constant *Folded = 0; if (LHSVals[i].first == 0) { - ConstantInt *Zero = - cast(ConstantInt::get(BO->getType(), 0)); - Result.push_back(std::make_pair(Zero, LHSVals[i].second)); - } else if (Constant *Folded = ConstantExpr::get(BO->getOpcode(), - LHSVals[i].first, CI)) { - Result.push_back(std::make_pair(cast(Folded), - LHSVals[i].second)); + Folded = ConstantExpr::get(BO->getOpcode(), + UndefValue::get(BO->getType()), + CI); + } else { + Folded = ConstantExpr::get(BO->getOpcode(), LHSVals[i].first, CI); } - - return !Result.empty(); + + if (ConstantInt *FoldedCInt = dyn_cast(Folded)) + Result.push_back(std::make_pair(FoldedCInt, LHSVals[i].second)); + else if (isa(Folded)) + Result.push_back(std::make_pair((ConstantInt*)0, LHSVals[i].second)); + } } + + RecursionSet.erase(std::make_pair(V, BB)); + return !Result.empty(); } // Handle compare with phi operand, where the PHI is defined in this block. @@ -446,6 +473,7 @@ ComputeValueKnownInPredecessors(Value *V, BasicBlock *BB,PredValueInfo &Result){ Result.push_back(std::make_pair(CI, PredBB)); } + RecursionSet.erase(std::make_pair(V, BB)); return !Result.empty(); } @@ -472,25 +500,32 @@ ComputeValueKnownInPredecessors(Value *V, BasicBlock *BB,PredValueInfo &Result){ Result.push_back(std::make_pair(cast(ResC), P)); } + RecursionSet.erase(std::make_pair(V, BB)); return !Result.empty(); } - // Try to find a constant value for the LHS of an equality comparison, + // Try to find a constant value for the LHS of a comparison, // and evaluate it statically if we can. if (Constant *CmpConst = dyn_cast(Cmp->getOperand(1))) { SmallVector, 8> LHSVals; ComputeValueKnownInPredecessors(I->getOperand(0), BB, LHSVals); for (unsigned i = 0, e = LHSVals.size(); i != e; ++i) { + Constant * Folded = 0; if (LHSVals[i].first == 0) - Result.push_back(std::make_pair((ConstantInt*)0, - LHSVals[i].second)); - else if (Constant *Folded = ConstantExpr::getCompare( - Cmp->getPredicate(), LHSVals[i].first, CmpConst)) - Result.push_back(std::make_pair(cast(Folded), - LHSVals[i].second)); + Folded = ConstantExpr::getCompare(Cmp->getPredicate(), + UndefValue::get(CmpConst->getType()), CmpConst); + else + Folded = ConstantExpr::getCompare(Cmp->getPredicate(), + LHSVals[i].first, CmpConst); + + if (ConstantInt *FoldedCInt = dyn_cast(Folded)) + Result.push_back(std::make_pair(FoldedCInt, LHSVals[i].second)); + else if (isa(Folded)) + Result.push_back(std::make_pair((ConstantInt*)0,LHSVals[i].second)); } + RecursionSet.erase(std::make_pair(V, BB)); return !Result.empty(); } } @@ -505,9 +540,11 @@ ComputeValueKnownInPredecessors(Value *V, BasicBlock *BB,PredValueInfo &Result){ Result.push_back(std::make_pair(CInt, *PI)); } + RecursionSet.erase(std::make_pair(V, BB)); return !Result.empty(); } + RecursionSet.erase(std::make_pair(V, BB)); return false; } @@ -1126,8 +1163,9 @@ bool JumpThreading::ProcessThreadableEdges(Value *Cond, BasicBlock *BB) { return false; SmallVector, 8> PredValues; - if (!ComputeValueKnownInPredecessors(Cond, BB, PredValues)) + if (!ComputeValueKnownInPredecessors(Cond, BB, PredValues)) { return false; + } assert(!PredValues.empty() && "ComputeValueKnownInPredecessors returned true with no values"); diff --git a/test/Transforms/JumpThreading/2010-08-31-InfiniteRecursion.ll b/test/Transforms/JumpThreading/2010-08-31-InfiniteRecursion.ll new file mode 100644 index 00000000000..390948a3aec --- /dev/null +++ b/test/Transforms/JumpThreading/2010-08-31-InfiniteRecursion.ll @@ -0,0 +1,91 @@ +; RUN: opt < %s -jump-threading -disable-output +; ModuleID = 'bugpoint-reduced-simplified.bc' +target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64" +target triple = "x86_64-apple-darwin10.4" + +define void @encode_one_macroblock_highfast() nounwind ssp { +entry: + switch i32 undef, label %bb13 [ + i32 1, label %bb10 + i32 2, label %bb12 + ] + +bb10: ; preds = %entry + unreachable + +bb12: ; preds = %entry + unreachable + +bb13: ; preds = %entry + br i1 undef, label %bb137, label %bb292 + +bb137: ; preds = %bb13 + br i1 undef, label %bb150, label %bb154 + +bb150: ; preds = %bb137 + unreachable + +bb154: ; preds = %bb137 + br i1 undef, label %bb292, label %bb246 + +bb246: ; preds = %bb154 + br i1 undef, label %bb292, label %bb247 + +bb247: ; preds = %bb246 + br i1 undef, label %bb248, label %bb292 + +bb248: ; preds = %bb247 + br i1 undef, label %bb249, label %bb292 + +bb249: ; preds = %bb248 + br i1 undef, label %bb254, label %bb250 + +bb250: ; preds = %bb249 + unreachable + +bb254: ; preds = %bb249 + br i1 undef, label %bb292, label %bb255 + +bb255: ; preds = %bb288.bb289.loopexit_crit_edge, %bb254 + br i1 undef, label %bb.nph.split.us, label %bb269 + +bb.nph.split.us: ; preds = %bb255 + br i1 undef, label %bb.nph.split.us.split.us, label %bb269.us.us31 + +bb.nph.split.us.split.us: ; preds = %bb.nph.split.us + br i1 undef, label %bb269.us.us, label %bb269.us.us.us + +bb269.us.us.us: ; preds = %bb287.us.us.us, %bb.nph.split.us.split.us + %indvar = phi i64 [ %indvar.next, %bb287.us.us.us ], [ 0, %bb.nph.split.us.split.us ] ; [#uses=1] + %0 = icmp eq i16 undef, 0 ; [#uses=1] + br i1 %0, label %bb287.us.us.us, label %bb286.us.us.us + +bb287.us.us.us: ; preds = %bb269.us.us.us + %indvar.next = add i64 %indvar, 1 ; [#uses=2] + %exitcond = icmp eq i64 %indvar.next, 4 ; [#uses=1] + br i1 %exitcond, label %bb288.bb289.loopexit_crit_edge, label %bb269.us.us.us + +bb286.us.us.us: ; preds = %bb269.us.us.us + unreachable + +bb269.us.us: ; preds = %bb287.us.us, %bb.nph.split.us.split.us + br i1 undef, label %bb287.us.us, label %bb286.us.us + +bb287.us.us: ; preds = %bb269.us.us + br i1 undef, label %bb288.bb289.loopexit_crit_edge, label %bb269.us.us + +bb286.us.us: ; preds = %bb269.us.us + unreachable + +bb269.us.us31: ; preds = %bb.nph.split.us + unreachable + +bb269: ; preds = %bb255 + unreachable + +bb288.bb289.loopexit_crit_edge: ; preds = %bb287.us.us, %bb287.us.us.us + br i1 undef, label %bb292, label %bb255 + +bb292: ; preds = %bb288.bb289.loopexit_crit_edge, %bb254, %bb248, %bb247, %bb246, %bb154, %bb13 + unreachable +} -- 2.11.0