Index: include/llvm/Transforms/Scalar/JumpThreading.h =================================================================== --- include/llvm/Transforms/Scalar/JumpThreading.h +++ include/llvm/Transforms/Scalar/JumpThreading.h @@ -89,22 +89,9 @@ #else SmallSet, 16> LoopHeaders; #endif - DenseSet> RecursionSet; unsigned BBDupThreshold; - // RAII helper for updating the recursion stack. - struct RecursionSetRemover { - DenseSet> &TheSet; - std::pair ThePair; - - RecursionSetRemover(DenseSet> &S, - std::pair P) - : TheSet(S), ThePair(P) {} - - ~RecursionSetRemover() { TheSet.erase(ThePair); } - }; - public: JumpThreadingPass(int T = -1); @@ -128,11 +115,21 @@ bool DuplicateCondBranchOnPHIIntoPred( BasicBlock *BB, const SmallVectorImpl &PredBBs); + bool ComputeValueKnownInPredecessorsImpl( + Value *V, BasicBlock *BB, jumpthreading::PredValueInfo &Result, + jumpthreading::ConstantPreference Preference, + DenseSet> &RecursionSet, + Instruction *CxtI = nullptr); bool ComputeValueKnownInPredecessors(Value *V, BasicBlock *BB, jumpthreading::PredValueInfo &Result, jumpthreading::ConstantPreference Preference, - Instruction *CxtI = nullptr); + Instruction *CxtI = nullptr) { + DenseSet> RecursionSet; + return ComputeValueKnownInPredecessorsImpl(V, BB, Result, Preference, + RecursionSet, CxtI); + } + bool ProcessThreadableEdges(Value *Cond, BasicBlock *BB, jumpthreading::ConstantPreference Preference, Instruction *CxtI = nullptr); Index: lib/Transforms/Scalar/JumpThreading.cpp =================================================================== --- lib/Transforms/Scalar/JumpThreading.cpp +++ lib/Transforms/Scalar/JumpThreading.cpp @@ -574,9 +574,11 @@ /// BB in the result vector. /// /// This returns true if there were any known values. -bool JumpThreadingPass::ComputeValueKnownInPredecessors( +bool JumpThreadingPass::ComputeValueKnownInPredecessorsImpl( Value *V, BasicBlock *BB, PredValueInfo &Result, - ConstantPreference Preference, Instruction *CxtI) { + ConstantPreference Preference, + DenseSet> &RecursionSet, + Instruction *CxtI) { // This method walks up use-def chains recursively. Because of this, we could // get into an infinite loop going around loops in the use-def chain. To // prevent this, keep track of what (value, block) pairs we've already visited @@ -584,10 +586,6 @@ if (!RecursionSet.insert(std::make_pair(V, BB)).second) return false; - // An RAII help to remove this pair from the recursion set once the recursion - // stack pops back out again. - RecursionSetRemover remover(RecursionSet, std::make_pair(V, BB)); - // If V is a constant, then it is known in all predecessors. if (Constant *KC = getKnownConstant(V, Preference)) { for (BasicBlock *Pred : predecessors(BB)) @@ -657,7 +655,8 @@ Value *Source = CI->getOperand(0); if (!isa(Source) && !isa(Source)) return false; - ComputeValueKnownInPredecessors(Source, BB, Result, Preference, CxtI); + ComputeValueKnownInPredecessorsImpl(Source, BB, Result, Preference, + RecursionSet, CxtI); if (Result.empty()) return false; @@ -677,10 +676,10 @@ I->getOpcode() == Instruction::And) { PredValueInfoTy LHSVals, RHSVals; - ComputeValueKnownInPredecessors(I->getOperand(0), BB, LHSVals, - WantInteger, CxtI); - ComputeValueKnownInPredecessors(I->getOperand(1), BB, RHSVals, - WantInteger, CxtI); + ComputeValueKnownInPredecessorsImpl(I->getOperand(0), BB, LHSVals, + WantInteger, RecursionSet, CxtI); + ComputeValueKnownInPredecessorsImpl(I->getOperand(1), BB, RHSVals, + WantInteger, RecursionSet, CxtI); if (LHSVals.empty() && RHSVals.empty()) return false; @@ -715,8 +714,8 @@ if (I->getOpcode() == Instruction::Xor && isa(I->getOperand(1)) && cast(I->getOperand(1))->isOne()) { - ComputeValueKnownInPredecessors(I->getOperand(0), BB, Result, - WantInteger, CxtI); + ComputeValueKnownInPredecessorsImpl(I->getOperand(0), BB, Result, + WantInteger, RecursionSet, CxtI); if (Result.empty()) return false; @@ -733,8 +732,8 @@ && "A binary operator creating a block address?"); if (ConstantInt *CI = dyn_cast(BO->getOperand(1))) { PredValueInfoTy LHSVals; - ComputeValueKnownInPredecessors(BO->getOperand(0), BB, LHSVals, - WantInteger, CxtI); + ComputeValueKnownInPredecessorsImpl(BO->getOperand(0), BB, LHSVals, + WantInteger, RecursionSet, CxtI); // Try to use constant folding to simplify the binary operator. for (const auto &LHSVal : LHSVals) { @@ -879,8 +878,8 @@ // Try to find a constant value for the LHS of a comparison, // and evaluate it statically if we can. PredValueInfoTy LHSVals; - ComputeValueKnownInPredecessors(I->getOperand(0), BB, LHSVals, - WantInteger, CxtI); + ComputeValueKnownInPredecessorsImpl(I->getOperand(0), BB, LHSVals, + WantInteger, RecursionSet, CxtI); for (const auto &LHSVal : LHSVals) { Constant *V = LHSVal.first; @@ -900,8 +899,8 @@ Constant *FalseVal = getKnownConstant(SI->getFalseValue(), Preference); PredValueInfoTy Conds; if ((TrueVal || FalseVal) && - ComputeValueKnownInPredecessors(SI->getCondition(), BB, Conds, - WantInteger, CxtI)) { + ComputeValueKnownInPredecessorsImpl(SI->getCondition(), BB, Conds, + WantInteger, RecursionSet, CxtI)) { for (auto &C : Conds) { Constant *Cond = C.first; Index: test/Transforms/JumpThreading/crash.ll =================================================================== --- test/Transforms/JumpThreading/crash.ll +++ test/Transforms/JumpThreading/crash.ll @@ -564,3 +564,58 @@ declare i8* @PR14233.f1() declare i8* @PR14233.f2() + +; Make sure the following compiles in a sane amount of time, as opposed +; to taking exponential time. +define void @almost_infinite_loop(i1 %x0) { +entry: + br label %if.then57.i + +if.then57.i: + %x1 = or i1 %x0, %x0 + %x2 = or i1 %x1, %x1 + %x3 = or i1 %x2, %x2 + %x4 = or i1 %x3, %x3 + %x5 = or i1 %x4, %x4 + %x6 = or i1 %x5, %x5 + %x7 = or i1 %x6, %x6 + %x8 = or i1 %x7, %x7 + %x9 = or i1 %x8, %x8 + %x10 = or i1 %x9, %x9 + %x11 = or i1 %x10, %x10 + %x12 = or i1 %x11, %x11 + %x13 = or i1 %x12, %x12 + %x14 = or i1 %x13, %x13 + %x15 = or i1 %x14, %x14 + %x16 = or i1 %x15, %x15 + %x17 = or i1 %x16, %x16 + %x18 = or i1 %x17, %x17 + %x19 = or i1 %x18, %x18 + %x20 = or i1 %x19, %x19 + %x21 = or i1 %x20, %x20 + %x22 = or i1 %x21, %x21 + %x23 = or i1 %x22, %x22 + %x24 = or i1 %x23, %x23 + %x25 = or i1 %x24, %x24 + %x26 = or i1 %x25, %x25 + %x27 = or i1 %x26, %x26 + %x28 = or i1 %x27, %x27 + %x29 = or i1 %x28, %x28 + %x30 = or i1 %x29, %x29 + %x31 = or i1 %x30, %x30 + %x32 = or i1 %x31, %x31 + %x33 = or i1 %x32, %x32 + %x34 = or i1 %x33, %x33 + %x35 = or i1 %x34, %x34 + %x36 = or i1 %x35, %x35 + %x37 = or i1 %x36, %x36 + %x38 = or i1 %x37, %x37 + %x39 = or i1 %x38, %x38 + br i1 %x39, label %dest1, label %dest2 + +dest1: + unreachable + +dest2: + unreachable +}