[JumpThreading] Fix exponential time algorithm computing known values.

[efriedma]

Summary

ComputeValueKnownInPredecessors has a "visited" set to prevent infinite loops, since a value can be visited more than once. However, the implementation didn't prevent the algorithm from taking exponential time. Instead of removing elements from the RecursionSet one at a time, we should keep around the whole set until ComputeValueKnownInPredecessors finishes, then discard it.

The testcase is synthetic because I was having trouble effectively reducing the original. But it's basically the same idea.

Instead of failing, we could theoretically cache the result instead. But I don't think it would help substantially in practice.

[mkazantsev]

LGTM.

It seems that the initial design of this algorithm wasn't intended to make 2 recursive calls from 1 place. The interesting bit is that we only can have an exponential explosion here:

// Handle some boolean conditions.
if (I->getType()->getPrimitiveSizeInBits() == 1) {
  assert(Preference == WantInteger && "One-bit non-integer type?");
  // X | true -> true
  // X & false -> false
  if (I->getOpcode() == Instruction::Or ||
      I->getOpcode() == Instruction::And) {
    PredValueInfoTy LHSVals, RHSVals;

    ComputeValueKnownInPredecessors(I->getOperand(0), BB, LHSVals,
                                    WantInteger, CxtI);
    ComputeValueKnownInPredecessors(I->getOperand(1), BB, RHSVals,
                                    WantInteger, CxtI);

In all other places, we seem to make just 1 recursive call and therefore no growth in width. In your particular case the obvious fix would be to just check that operand(0) == operand(1), but I guess that it's easy enough to construct a test when they won't match with same effect, e.g.

%x1 = or i1 %x0, %x0
%x2 = or i1 %x1, %x1
%x3 = or i1 %x1, %x2
%x4 = or i1 %x2, %x3

Do you mind adding such test as well? Just to make sure that no one rules it out with a trivial partial fix.

[brzycki]

+1 for me as well. JumpThreading, as it stands today, is quite haphazard in how it attacks a function and anything that helps reduce time spent recomputing known values is desirable.

I'm curious if you have compile time deltas from test-suite CTMark to see the results.

llvm/trunk/include/llvm/Transforms/Scalar/JumpThreading.h

class JumpThreadingPass : public PassInfoMixin<JumpThreadingPass> {
   std::unique_ptr<BranchProbabilityInfo> BPI;
   bool HasProfileData = false;
   bool HasGuards = false;
 #ifdef NDEBUG
   SmallPtrSet<const BasicBlock *, 16> LoopHeaders;
 #else
   SmallSet<AssertingVH<const BasicBlock>, 16> LoopHeaders;
 #endif
-  DenseSet<std::pair<Value *, BasicBlock *>> RecursionSet;
 
   unsigned BBDupThreshold;
 
-  // RAII helper for updating the recursion stack.
-  struct RecursionSetRemover {
-    DenseSet<std::pair<Value *, BasicBlock *>> &TheSet;
-    std::pair<Value *, BasicBlock *> ThePair;
-
-    RecursionSetRemover(DenseSet<std::pair<Value *, BasicBlock *>> &S,
-                        std::pair<Value *, BasicBlock *> P)
-        : TheSet(S), ThePair(P) {}
-
-    ~RecursionSetRemover() { TheSet.erase(ThePair); }
-  };
-
 public:
   JumpThreadingPass(int T = -1);
 
   // Glue for old PM.
   bool runImpl(Function &F, TargetLibraryInfo *TLI_, LazyValueInfo *LVI_,
                AliasAnalysis *AA_, DomTreeUpdater *DTU_, bool HasProfileData_,
                std::unique_ptr<BlockFrequencyInfo> BFI_,
                std::unique_ptr<BranchProbabilityInfo> BPI_);
 
   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
 
   void releaseMemory() {
     BFI.reset();
     BPI.reset();
   }
 
   void FindLoopHeaders(Function &F);
   bool ProcessBlock(BasicBlock *BB);
   bool ThreadEdge(BasicBlock *BB, const SmallVectorImpl<BasicBlock *> &PredBBs,
                   BasicBlock *SuccBB);
   bool DuplicateCondBranchOnPHIIntoPred(
       BasicBlock *BB, const SmallVectorImpl<BasicBlock *> &PredBBs);
 
+  bool ComputeValueKnownInPredecessorsImpl(
+      Value *V, BasicBlock *BB, jumpthreading::PredValueInfo &Result,
+      jumpthreading::ConstantPreference Preference,
+      DenseSet<std::pair<Value *, BasicBlock *>> &RecursionSet,
+      Instruction *CxtI = nullptr);
   bool
   ComputeValueKnownInPredecessors(Value *V, BasicBlock *BB,
                                   jumpthreading::PredValueInfo &Result,
                                   jumpthreading::ConstantPreference Preference,
-                                  Instruction *CxtI = nullptr);
+                                  Instruction *CxtI = nullptr) {
+    DenseSet<std::pair<Value *, BasicBlock *>> RecursionSet;
+    return ComputeValueKnownInPredecessorsImpl(V, BB, Result, Preference,
+                                               RecursionSet, CxtI);
+  }
+
   bool ProcessThreadableEdges(Value *Cond, BasicBlock *BB,
                               jumpthreading::ConstantPreference Preference,
                               Instruction *CxtI = nullptr);
 
   bool ProcessBranchOnPHI(PHINode *PN);
   bool ProcessBranchOnXOR(BinaryOperator *BO);
   bool ProcessImpliedCondition(BasicBlock *BB);
 

llvm/trunk/lib/Transforms/Scalar/JumpThreading.cpp

 }
 
 /// ComputeValueKnownInPredecessors - Given a basic block BB and a value V, see
 /// if we can infer that the value is a known ConstantInt/BlockAddress or undef
 /// in any of our predecessors.  If so, return the known list of value and pred
 /// 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<std::pair<Value *, BasicBlock *>> &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
   // and terminate the search if we loop back to them
   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))
       Result.push_back(std::make_pair(KC, Pred));
 
     return !Result.empty();
   }
 
bool JumpThreadingPass::ComputeValueKnownInPredecessorsImpl(
   }
 
   // Handle Cast instructions.  Only see through Cast when the source operand is
   // PHI or Cmp to save the compilation time.
   if (CastInst *CI = dyn_cast<CastInst>(I)) {
     Value *Source = CI->getOperand(0);
     if (!isa<PHINode>(Source) && !isa<CmpInst>(Source))
       return false;
-    ComputeValueKnownInPredecessors(Source, BB, Result, Preference, CxtI);
+    ComputeValueKnownInPredecessorsImpl(Source, BB, Result, Preference,
+                                        RecursionSet, CxtI);
     if (Result.empty())
       return false;
 
     // Convert the known values.
     for (auto &R : Result)
       R.first = ConstantExpr::getCast(CI->getOpcode(), R.first, CI->getType());
 
     return true;
   }
 
   // Handle some boolean conditions.
   if (I->getType()->getPrimitiveSizeInBits() == 1) {
     assert(Preference == WantInteger && "One-bit non-integer type?");
     // X | true -> true
     // X & false -> false
     if (I->getOpcode() == Instruction::Or ||
         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;
 
       ConstantInt *InterestingVal;
       if (I->getOpcode() == Instruction::Or)
         InterestingVal = ConstantInt::getTrue(I->getContext());
       else
if (I->getOpcode() == Instruction::Or ||
 
       return !Result.empty();
     }
 
     // Handle the NOT form of XOR.
     if (I->getOpcode() == Instruction::Xor &&
         isa<ConstantInt>(I->getOperand(1)) &&
         cast<ConstantInt>(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;
 
       // Invert the known values.
       for (auto &R : Result)
         R.first = ConstantExpr::getNot(R.first);
 
       return true;
     }
 
   // Try to simplify some other binary operator values.
   } else if (BinaryOperator *BO = dyn_cast<BinaryOperator>(I)) {
     assert(Preference != WantBlockAddress
             && "A binary operator creating a block address?");
     if (ConstantInt *CI = dyn_cast<ConstantInt>(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) {
         Constant *V = LHSVal.first;
         Constant *Folded = ConstantExpr::get(BO->getOpcode(), V, CI);
 
         if (Constant *KC = getKnownConstant(Folded, WantInteger))
           Result.push_back(std::make_pair(KC, LHSVal.second));
if (isa<Constant>(CmpRHS) && !CmpType->isVectorTy()) {
             return !Result.empty();
           }
         }
       }
 
       // 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;
         Constant *Folded = ConstantExpr::getCompare(Pred, V, CmpConst);
         if (Constant *KC = getKnownConstant(Folded, WantInteger))
           Result.push_back(std::make_pair(KC, LHSVal.second));
       }
 
       return !Result.empty();
     }
   }
 
   if (SelectInst *SI = dyn_cast<SelectInst>(I)) {
     // Handle select instructions where at least one operand is a known constant
     // and we can figure out the condition value for any predecessor block.
     Constant *TrueVal = getKnownConstant(SI->getTrueValue(), Preference);
     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;
 
         // Figure out what value to use for the condition.
         bool KnownCond;
         if (ConstantInt *CI = dyn_cast<ConstantInt>(Cond)) {
           // A known boolean.
           KnownCond = CI->isOne();

llvm/trunk/test/Transforms/JumpThreading/crash.ll

-; RUN: opt < %s -jump-threading -disable-output
+; RUN: opt < %s -jump-threading -S | FileCheck %s
 ; PR2285
 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"
 target triple = "x86_64-unknown-linux-gnu"
   %struct.system__secondary_stack__mark_id = type { i64, i64 }
 
 define void @_ada_c35507b() {
 entry:
   br label %bb

 
 ur:
   unreachable
 }
 
 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.
+; (CHECK to make sure the condition doesn't get simplified somehow;
+; if it does, the testcase will need to be revised.)
+; CHECK-LABEL: define void @almost_infinite_loop
+; CHECK: %x39 = or i1 %x38, %x38
+; CHECK: br i1 %x39, label %dest1, label %dest2
+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
+}