From 8c11ed7fff8d07010e27d0374a2b9caa8fe95a54 Mon Sep 17 00:00:00 2001 From: Evan Cheng Date: Tue, 13 Oct 2009 22:02:20 +0000 Subject: Teach basic AA about PHI nodes. If all operands of a phi NoAlias another value than it's safe to declare the PHI NoAlias the value. Ditto for MustAlias. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@84038 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Analysis/BasicAliasAnalysis.cpp | 81 +++++++++++++++++++++++++++++++------ 1 file changed, 69 insertions(+), 12 deletions(-) (limited to 'lib/Analysis') diff --git a/lib/Analysis/BasicAliasAnalysis.cpp b/lib/Analysis/BasicAliasAnalysis.cpp index 900a5b6..75fd0e8 100644 --- a/lib/Analysis/BasicAliasAnalysis.cpp +++ b/lib/Analysis/BasicAliasAnalysis.cpp @@ -27,6 +27,7 @@ #include "llvm/Operator.h" #include "llvm/Pass.h" #include "llvm/Target/TargetData.h" +#include "llvm/ADT/SmallSet.h" #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/STLExtras.h" #include "llvm/Support/Compiler.h" @@ -201,7 +202,10 @@ namespace { static char ID; // Class identification, replacement for typeinfo BasicAliasAnalysis() : NoAA(&ID) {} AliasResult alias(const Value *V1, unsigned V1Size, - const Value *V2, unsigned V2Size); + const Value *V2, unsigned V2Size) { + SmallSet VisitedPHIs; + return aliasCheck(V1, V1Size, V2, V2Size, VisitedPHIs); + } ModRefResult getModRefInfo(CallSite CS, Value *P, unsigned Size); ModRefResult getModRefInfo(CallSite CS1, CallSite CS2); @@ -218,7 +222,16 @@ namespace { // aliasGEP - Provide a bunch of ad-hoc rules to disambiguate a GEP instruction // against another. AliasResult aliasGEP(const Value *V1, unsigned V1Size, - const Value *V2, unsigned V2Size); + const Value *V2, unsigned V2Size, + SmallSet &VisitedPHIs); + + AliasResult aliasPHI(const Value *V1, unsigned V1Size, + const Value *V2, unsigned V2Size, + SmallSet &VisitedPHIs); + + AliasResult aliasCheck(const Value *V1, unsigned V1Size, + const Value *V2, unsigned V2Size, + SmallSet &VisitedPHIs); // CheckGEPInstructions - Check two GEP instructions with known // must-aliasing base pointers. This checks to see if the index expressions @@ -339,7 +352,8 @@ BasicAliasAnalysis::getModRefInfo(CallSite CS1, CallSite CS2) { // AliasAnalysis::AliasResult BasicAliasAnalysis::aliasGEP(const Value *V1, unsigned V1Size, - const Value *V2, unsigned V2Size) { + const Value *V2, unsigned V2Size, + SmallSet &VisitedPHIs) { // If we have two gep instructions with must-alias'ing base pointers, figure // out if the indexes to the GEP tell us anything about the derived pointer. // Note that we also handle chains of getelementptr instructions as well as @@ -359,8 +373,8 @@ BasicAliasAnalysis::aliasGEP(const Value *V1, unsigned V1Size, GEP1->getOperand(0)->getType() == GEP2->getOperand(0)->getType() && // All operands are the same, ignoring the base. std::equal(GEP1->op_begin()+1, GEP1->op_end(), GEP2->op_begin()+1)) - return alias(GEP1->getOperand(0), V1Size, GEP2->getOperand(0), V2Size); - + return aliasCheck(GEP1->getOperand(0), V1Size, + GEP2->getOperand(0), V2Size, VisitedPHIs); // Drill down into the first non-gep value, to test for must-aliasing of // the base pointers. @@ -377,7 +391,8 @@ BasicAliasAnalysis::aliasGEP(const Value *V1, unsigned V1Size, const Value *BasePtr2 = GEP2->getOperand(0); // Do the base pointers alias? - AliasResult BaseAlias = alias(BasePtr1, ~0U, BasePtr2, ~0U); + AliasResult BaseAlias = aliasCheck(BasePtr1, ~0U, BasePtr2, ~0U, + VisitedPHIs); if (BaseAlias == NoAlias) return NoAlias; if (BaseAlias == MustAlias) { // If the base pointers alias each other exactly, check to see if we can @@ -413,7 +428,7 @@ BasicAliasAnalysis::aliasGEP(const Value *V1, unsigned V1Size, SmallVector GEPOperands; const Value *BasePtr = GetGEPOperands(V1, GEPOperands); - AliasResult R = alias(BasePtr, V1Size, V2, V2Size); + AliasResult R = aliasCheck(BasePtr, V1Size, V2, V2Size, VisitedPHIs); if (R == MustAlias) { // If there is at least one non-zero constant index, we know they cannot // alias. @@ -462,12 +477,47 @@ BasicAliasAnalysis::aliasGEP(const Value *V1, unsigned V1Size, return MayAlias; } -// alias - Provide a bunch of ad-hoc rules to disambiguate in common cases, such -// as array references. +AliasAnalysis::AliasResult +BasicAliasAnalysis::aliasPHI(const Value *V1, unsigned V1Size, + const Value *V2, unsigned V2Size, + SmallSet &VisitedPHIs) { + // The PHI node has already been visited, avoid recursion any further. + if (!VisitedPHIs.insert(V1)) + return MayAlias; + + SmallSet UniqueSrc; + SmallVector V1Srcs; + const PHINode *PN = cast(V1); + for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { + Value *PV1 = PN->getIncomingValue(i); + if (isa(PV1)) + // If any of the source itself is a PHI, return MayAlias conservatively + // to avoid compile time explosion. + return MayAlias; + if (UniqueSrc.insert(PV1)) + V1Srcs.push_back(PV1); + } + + // If all sources of the PHI node NoAlias or MustAlias V2, then returns + // NoAlias / MustAlias. Otherwise, returns MayAlias. + AliasResult Alias = aliasCheck(V1Srcs[0], V1Size, V2, V2Size, VisitedPHIs); + for (unsigned i = 1, e = V1Srcs.size(); i != e; ++i) { + Value *V = V1Srcs[i]; + AliasResult ThisAlias = aliasCheck(V, V1Size, V2, V2Size, VisitedPHIs); + if (ThisAlias != Alias) + return MayAlias; + } + + return Alias; +} + +// aliasCheck - Provide a bunch of ad-hoc rules to disambiguate in common cases, +// such as array references. // AliasAnalysis::AliasResult -BasicAliasAnalysis::alias(const Value *V1, unsigned V1Size, - const Value *V2, unsigned V2Size) { +BasicAliasAnalysis::aliasCheck(const Value *V1, unsigned V1Size, + const Value *V2, unsigned V2Size, + SmallSet &VisitedPHIs) { // Strip off any casts if they exist. V1 = V1->stripPointerCasts(); V2 = V2->stripPointerCasts(); @@ -521,7 +571,14 @@ BasicAliasAnalysis::alias(const Value *V1, unsigned V1Size, std::swap(V1Size, V2Size); } if (isGEP(V1)) - return aliasGEP(V1, V1Size, V2, V2Size); + return aliasGEP(V1, V1Size, V2, V2Size, VisitedPHIs); + + if (isa(V2) && !isa(V1)) { + std::swap(V1, V2); + std::swap(V1Size, V2Size); + } + if (isa(V1)) + return aliasPHI(V1, V1Size, V2, V2Size, VisitedPHIs); return MayAlias; } -- cgit v1.1