From 50f424c3d079d4774bb323de1e0b77cf4627be69 Mon Sep 17 00:00:00 2001 From: Dan Gohman Date: Mon, 28 Jun 2010 21:16:52 +0000 Subject: [PATCH] Fix Value::stripPointerCasts and BasicAA to avoid trouble on code in unreachable blocks, which have have use-def cycles. This fixes PR7514. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@107071 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Analysis/BasicAliasAnalysis.cpp | 38 +++++++++++++++++++++++------- lib/VMCore/Value.cpp | 10 +++++++- test/Analysis/BasicAA/unreachable-block.ll | 16 +++++++++++++ 3 files changed, 54 insertions(+), 10 deletions(-) create mode 100644 test/Analysis/BasicAA/unreachable-block.ll diff --git a/lib/Analysis/BasicAliasAnalysis.cpp b/lib/Analysis/BasicAliasAnalysis.cpp index 0bfa4dab0db..1bf32ced6c1 100644 --- a/lib/Analysis/BasicAliasAnalysis.cpp +++ b/lib/Analysis/BasicAliasAnalysis.cpp @@ -189,9 +189,9 @@ namespace { BasicAliasAnalysis() : NoAA(&ID) {} AliasResult alias(const Value *V1, unsigned V1Size, const Value *V2, unsigned V2Size) { - assert(VisitedPHIs.empty() && "VisitedPHIs must be cleared after use!"); + assert(Visited.empty() && "Visited must be cleared after use!"); AliasResult Alias = aliasCheck(V1, V1Size, V2, V2Size); - VisitedPHIs.clear(); + Visited.clear(); return Alias; } @@ -213,8 +213,8 @@ namespace { } private: - // VisitedPHIs - Track PHI nodes visited by a aliasCheck() call. - SmallPtrSet VisitedPHIs; + // Visited - Track instructions visited by a aliasPHI, aliasSelect(), and aliasGEP(). + SmallPtrSet Visited; // aliasGEP - Provide a bunch of ad-hoc rules to disambiguate a GEP // instruction against another. @@ -440,6 +440,13 @@ BasicAliasAnalysis::aliasGEP(const GEPOperator *GEP1, unsigned V1Size, const Value *V2, unsigned V2Size, const Value *UnderlyingV1, const Value *UnderlyingV2) { + // If this GEP has been visited before, we're on a use-def cycle. + // Such cycles are only valid when PHI nodes are involved or in unreachable + // code. The visitPHI function catches cycles containing PHIs, but there + // could still be a cycle without PHIs in unreachable code. + if (!Visited.insert(GEP1)) + return MayAlias; + int64_t GEP1BaseOffset; SmallVector, 4> GEP1VariableIndices; @@ -550,6 +557,13 @@ BasicAliasAnalysis::aliasGEP(const GEPOperator *GEP1, unsigned V1Size, AliasAnalysis::AliasResult BasicAliasAnalysis::aliasSelect(const SelectInst *SI, unsigned SISize, const Value *V2, unsigned V2Size) { + // If this select has been visited before, we're on a use-def cycle. + // Such cycles are only valid when PHI nodes are involved or in unreachable + // code. The visitPHI function catches cycles containing PHIs, but there + // could still be a cycle without PHIs in unreachable code. + if (!Visited.insert(SI)) + return MayAlias; + // If the values are Selects with the same condition, we can do a more precise // check: just check for aliases between the values on corresponding arms. if (const SelectInst *SI2 = dyn_cast(V2)) @@ -570,11 +584,17 @@ BasicAliasAnalysis::aliasSelect(const SelectInst *SI, unsigned SISize, // If both arms of the Select node NoAlias or MustAlias V2, then returns // NoAlias / MustAlias. Otherwise, returns MayAlias. AliasResult Alias = - aliasCheck(SI->getTrueValue(), SISize, V2, V2Size); + aliasCheck(V2, V2Size, SI->getTrueValue(), SISize); if (Alias == MayAlias) return MayAlias; + + // If V2 is visited, the recursive case will have been caught in the + // above aliasCheck call, so these subsequent calls to aliasCheck + // don't need to assume that V2 is being visited recursively. + Visited.erase(V2); + AliasResult ThisAlias = - aliasCheck(SI->getFalseValue(), SISize, V2, V2Size); + aliasCheck(V2, V2Size, SI->getFalseValue(), SISize); if (ThisAlias != Alias) return MayAlias; return Alias; @@ -586,7 +606,7 @@ AliasAnalysis::AliasResult BasicAliasAnalysis::aliasPHI(const PHINode *PN, unsigned PNSize, const Value *V2, unsigned V2Size) { // The PHI node has already been visited, avoid recursion any further. - if (!VisitedPHIs.insert(PN)) + if (!Visited.insert(PN)) return MayAlias; // If the values are PHIs in the same block, we can do a more precise @@ -636,10 +656,10 @@ BasicAliasAnalysis::aliasPHI(const PHINode *PN, unsigned PNSize, for (unsigned i = 1, e = V1Srcs.size(); i != e; ++i) { Value *V = V1Srcs[i]; - // If V2 is a PHI, the recursive case will have been caught in the + // If V2 is visited, the recursive case will have been caught in the // above aliasCheck call, so these subsequent calls to aliasCheck // don't need to assume that V2 is being visited recursively. - VisitedPHIs.erase(V2); + Visited.erase(V2); AliasResult ThisAlias = aliasCheck(V2, V2Size, V, PNSize); if (ThisAlias != Alias || ThisAlias == MayAlias) diff --git a/lib/VMCore/Value.cpp b/lib/VMCore/Value.cpp index 645dd5a21c7..585edf09c9e 100644 --- a/lib/VMCore/Value.cpp +++ b/lib/VMCore/Value.cpp @@ -322,7 +322,13 @@ void Value::replaceAllUsesWith(Value *New) { Value *Value::stripPointerCasts() { if (!getType()->isPointerTy()) return this; + + // Even though we don't look through PHI nodes, we could be called on an + // instruction in an unreachable block, which may be on a cycle. + SmallPtrSet Visited; + Value *V = this; + Visited.insert(V); do { if (GEPOperator *GEP = dyn_cast(V)) { if (!GEP->hasAllZeroIndices()) @@ -338,7 +344,9 @@ Value *Value::stripPointerCasts() { return V; } assert(V->getType()->isPointerTy() && "Unexpected operand type!"); - } while (1); + } while (Visited.insert(V)); + + return V; } Value *Value::getUnderlyingObject(unsigned MaxLookup) { diff --git a/test/Analysis/BasicAA/unreachable-block.ll b/test/Analysis/BasicAA/unreachable-block.ll new file mode 100644 index 00000000000..3382188f4bb --- /dev/null +++ b/test/Analysis/BasicAA/unreachable-block.ll @@ -0,0 +1,16 @@ +; RUN: opt -aa-eval -disable-output < %s >& /dev/null + +; BasicAA shouldn't infinitely recurse on the use-def cycles in +; unreachable code. + +define void @func_2() nounwind { +entry: + unreachable + +bb: + %t = select i1 undef, i32* %t, i32* undef + %p = select i1 undef, i32* %p, i32* %p + %q = select i1 undef, i32* undef, i32* %p + %a = getelementptr i8* %a, i32 0 + unreachable +} -- 2.11.0