diff options
| -rw-r--r-- | include/llvm/Analysis/ScalarEvolution.h | 5 | ||||
| -rw-r--r-- | lib/Analysis/ScalarEvolution.cpp | 24 | ||||
| -rw-r--r-- | test/Analysis/ScalarEvolution/2012-05-18-LoopPredRecurse.ll | 30 |
3 files changed, 58 insertions, 1 deletions
diff --git a/include/llvm/Analysis/ScalarEvolution.h b/include/llvm/Analysis/ScalarEvolution.h index 72408f7738..8f87b58fe7 100644 --- a/include/llvm/Analysis/ScalarEvolution.h +++ b/include/llvm/Analysis/ScalarEvolution.h @@ -30,7 +30,7 @@ #include "llvm/Support/Allocator.h" #include "llvm/Support/ConstantRange.h" #include "llvm/ADT/FoldingSet.h" -#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/DenseSet.h" #include <map> namespace llvm { @@ -250,6 +250,9 @@ namespace llvm { /// ValueExprMapType ValueExprMap; + /// Mark predicate values currently being processed by isImpliedCond. + DenseSet<Value*> PendingLoopPredicates; + /// ExitLimit - Information about the number of loop iterations for /// which a loop exit's branch condition evaluates to the not-taken path. /// This is a temporary pair of exact and max expressions that are diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp index d1ad8e02d6..4e3dc60ed5 100644 --- a/lib/Analysis/ScalarEvolution.cpp +++ b/lib/Analysis/ScalarEvolution.cpp @@ -6039,12 +6039,34 @@ ScalarEvolution::isLoopEntryGuardedByCond(const Loop *L, return false; } +/// RAII wrapper to prevent recursive application of isImpliedCond. +/// ScalarEvolution's PendingLoopPredicates set must be empty unless we are +/// currently evaluating isImpliedCond. +struct MarkPendingLoopPredicate { + Value *Cond; + DenseSet<Value*> &LoopPreds; + bool Pending; + + MarkPendingLoopPredicate(Value *C, DenseSet<Value*> &LP) + : Cond(C), LoopPreds(LP) { + Pending = !LoopPreds.insert(Cond).second; + } + ~MarkPendingLoopPredicate() { + if (!Pending) + LoopPreds.erase(Cond); + } +}; + /// isImpliedCond - Test whether the condition described by Pred, LHS, /// and RHS is true whenever the given Cond value evaluates to true. bool ScalarEvolution::isImpliedCond(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS, Value *FoundCondValue, bool Inverse) { + MarkPendingLoopPredicate Mark(FoundCondValue, PendingLoopPredicates); + if (Mark.Pending) + return false; + // Recursively handle And and Or conditions. if (BinaryOperator *BO = dyn_cast<BinaryOperator>(FoundCondValue)) { if (BO->getOpcode() == Instruction::And) { @@ -6571,6 +6593,8 @@ void ScalarEvolution::releaseMemory() { I->second.clear(); } + assert(PendingLoopPredicates.empty() && "isImpliedCond garbage"); + BackedgeTakenCounts.clear(); ConstantEvolutionLoopExitValue.clear(); ValuesAtScopes.clear(); diff --git a/test/Analysis/ScalarEvolution/2012-05-18-LoopPredRecurse.ll b/test/Analysis/ScalarEvolution/2012-05-18-LoopPredRecurse.ll new file mode 100644 index 0000000000..52e6683c9f --- /dev/null +++ b/test/Analysis/ScalarEvolution/2012-05-18-LoopPredRecurse.ll @@ -0,0 +1,30 @@ +; RUN: opt < %s -iv-users -S -disable-output +; +; PR12868: Infinite recursion: +; getUDivExpr()->getZeroExtendExpr()->isLoopBackedgeGuardedBy() +; +; We actually want SCEV simplification to fail gracefully in this +; case, so there's no output to check, just the absense of stack overflow. + +@c = common global i8 0, align 1 + +define i32 @func() { +entry: + br label %for.cond + +for.cond: ; preds = %for.body, %entry + %storemerge = phi i8 [ -1, %entry ], [ %inc, %for.body ] + %ui.0 = phi i32 [ undef, %entry ], [ %div, %for.body ] + %tobool = icmp eq i8 %storemerge, 0 + br i1 %tobool, label %for.end, label %for.body + +for.body: ; preds = %for.cond + %conv = sext i8 %storemerge to i32 + %div = lshr i32 %conv, 1 + %tobool2 = icmp eq i32 %div, 0 + %inc = add i8 %storemerge, 1 + br i1 %tobool2, label %for.cond, label %for.end + +for.end: ; preds = %for.body, %for.cond + ret i32 0 +} |