Index: lib/Analysis/BasicAliasAnalysis.cpp =================================================================== --- lib/Analysis/BasicAliasAnalysis.cpp +++ lib/Analysis/BasicAliasAnalysis.cpp @@ -42,6 +42,10 @@ #include using namespace llvm; +/// Enable analysis of recursive PHI nodes. +static cl::opt EnableRecPhiAnalysis("basicaa-recphi", + cl::Hidden, cl::init(false)); + /// Cutoff after which to stop analysing a set of phi nodes potentially involved /// in a cycle. Because we are analysing 'through' phi nodes we need to be /// careful with value equivalence. We use reachability to make sure a value @@ -953,11 +957,13 @@ AssumptionCacheTracker &ACT = getAnalysis(); AssumptionCache *AC1 = nullptr, *AC2 = nullptr; if (auto *GEP1I = dyn_cast(GEP1)) - AC1 = &ACT.getAssumptionCache( - const_cast(*GEP1I->getParent()->getParent())); + if (GEP1I->getParent()) + AC1 = &ACT.getAssumptionCache( + const_cast(*GEP1I->getParent()->getParent())); if (auto *I2 = dyn_cast(V2)) - AC2 = &ACT.getAssumptionCache( - const_cast(*I2->getParent()->getParent())); + if (I2->getParent()) + AC2 = &ACT.getAssumptionCache( + const_cast(*I2->getParent()->getParent())); DominatorTreeWrapperPass *DTWP = getAnalysisIfAvailable(); @@ -1291,6 +1297,7 @@ SmallPtrSet UniqueSrc; SmallVector V1Srcs; + GEPOperator *LoopGEP = nullptr; for (Value *PV1 : PN->incoming_values()) { if (isa(PV1)) // If any of the source itself is a PHI, return MayAlias conservatively @@ -1298,12 +1305,47 @@ // sides are PHI nodes. In which case, this is O(m x n) time where 'm' // and 'n' are the number of PHI sources. return MayAlias; + + if (EnableRecPhiAnalysis) + if (GEPOperator *PV1GEP = dyn_cast(PV1)) { + // Check whether the incoming value is a GEP that advances the pointer + // result of this PHI node (e.g. in a loop). If this is the case, we + // would recurse and always get a MayAlias. It will be sufficient to + // check for aliasing with an undef GEP on the other incoming values. + if (PV1GEP->getPointerOperand() == PN && + PV1GEP->getNumIndices() == 1 && + isa(PV1GEP->idx_begin())) { + LoopGEP = PV1GEP; + continue; + } + } + if (UniqueSrc.insert(PV1).second) V1Srcs.push_back(PV1); } + SmallVector, 4> TmpInsts; + if (LoopGEP) { + // This PHI node contains a loop to itself through a GEP. For each + // non-looping incoming value %v, pretend there is an incoming value + // getelementptr %v, load undef. + for (int I = 0, E = V1Srcs.size(); I < E; ++I) { + Type *Ty = PointerType::getUnqual((*LoopGEP->idx_begin())->getType()); + Value *UndefVal = UndefValue::get(Ty); + LoadInst *TmpLoad = new LoadInst(UndefVal, "TmpLoad"); + GetElementPtrInst *TmpGEP = + GetElementPtrInst::Create(LoopGEP->getSourceElementType(), + V1Srcs[I], { TmpLoad }); + TmpGEP->setIsInBounds(LoopGEP->isInBounds()); + V1Srcs.push_back(TmpGEP); + TmpInsts.push_back(std::unique_ptr(TmpLoad)); + TmpInsts.push_back(std::unique_ptr(TmpGEP)); + } + } + AliasResult Alias = aliasCheck(V2, V2Size, V2AAInfo, V1Srcs[0], PNSize, PNAAInfo); + // Early exit if the check of the first PHI source against V2 is MayAlias. // Other results are not possible. if (Alias == MayAlias) Index: test/Analysis/BasicAA/phi-loop.ll =================================================================== --- /dev/null +++ test/Analysis/BasicAA/phi-loop.ll @@ -0,0 +1,75 @@ +; RUN: opt < %s -basicaa -basicaa-recphi=1 -gvn -S | FileCheck %s +; +; Check that section->word_ofs doesn't get reloaded in every iteration of the +; for loop. +; +; Code: +; +; typedef struct { +; unsigned num_words; +; unsigned word_ofs; +; const unsigned *data; +; } section_t; +; +; +; void test2(const section_t * restrict section, unsigned * restrict dst) {; +; while (section->data != NULL) { +; const unsigned *src = section->data; +; for (unsigned i=0; i < section->num_words; ++i) { +; dst[section->word_ofs + i] = src[i]; +; } +; +; ++section; +; } +; } +; + +; CHECK-LABEL: for.body: +; CHECK-NOT: load i32, i32* %word_ofs + +%struct.section_t = type { i32, i32, i32* } + +define void @test2(%struct.section_t* noalias nocapture readonly %section, i32* noalias nocapture %dst) { +entry: + %data13 = getelementptr inbounds %struct.section_t, %struct.section_t* %section, i32 0, i32 2 + %0 = load i32*, i32** %data13, align 4 + %cmp14 = icmp eq i32* %0, null + br i1 %cmp14, label %while.end, label %for.cond.preheader + +for.cond.preheader: ; preds = %entry, %for.end + %1 = phi i32* [ %6, %for.end ], [ %0, %entry ] + %section.addr.015 = phi %struct.section_t* [ %incdec.ptr, %for.end ], [ %section, %entry ] + %num_words = getelementptr inbounds %struct.section_t, %struct.section_t* %section.addr.015, i32 0, i32 0 + %2 = load i32, i32* %num_words, align 4 + %cmp211 = icmp eq i32 %2, 0 + br i1 %cmp211, label %for.end, label %for.body.lr.ph + +for.body.lr.ph: ; preds = %for.cond.preheader + %word_ofs = getelementptr inbounds %struct.section_t, %struct.section_t* %section.addr.015, i32 0, i32 1 + br label %for.body + +for.body: ; preds = %for.body.lr.ph, %for.body + %arrayidx.phi = phi i32* [ %1, %for.body.lr.ph ], [ %arrayidx.inc, %for.body ] + %i.012 = phi i32 [ 0, %for.body.lr.ph ], [ %inc, %for.body ] + %3 = load i32, i32* %arrayidx.phi, align 4 + %4 = load i32, i32* %word_ofs, align 4 + %add = add i32 %4, %i.012 + %arrayidx3 = getelementptr inbounds i32, i32* %dst, i32 %add + store i32 %3, i32* %arrayidx3, align 4 + %inc = add i32 %i.012, 1 + %5 = load i32, i32* %num_words, align 4 + %cmp2 = icmp ult i32 %inc, %5 + %arrayidx.inc = getelementptr i32, i32* %arrayidx.phi, i32 1 + br i1 %cmp2, label %for.body, label %for.end + +for.end: ; preds = %for.body, %for.cond.preheader + %incdec.ptr = getelementptr inbounds %struct.section_t, %struct.section_t* %section.addr.015, i32 1 + %data = getelementptr inbounds %struct.section_t, %struct.section_t* %section.addr.015, i32 1, i32 2 + %6 = load i32*, i32** %data, align 4 + %cmp = icmp eq i32* %6, null + br i1 %cmp, label %while.end, label %for.cond.preheader + +while.end: ; preds = %for.end, %entry + ret void +} +