From edd62b14e5284182231ecb4eb3850205167c4076 Mon Sep 17 00:00:00 2001 From: Arnold Schwaighofer Date: Mon, 10 Dec 2012 23:02:41 +0000 Subject: [PATCH] Optimistically analyse Phi cycles Analyse Phis under the starting assumption that they are NoAlias. Recursively look at their inputs. If they MayAlias/MustAlias there must be an input that makes them so. Addresses bug 14351. llvm-svn: 169788 --- llvm/lib/Analysis/BasicAliasAnalysis.cpp | 54 ++++++---------------- llvm/test/Analysis/BasicAA/phi-speculation.ll | 65 ++++++++++++++++++++++++++- 2 files changed, 76 insertions(+), 43 deletions(-) diff --git a/llvm/lib/Analysis/BasicAliasAnalysis.cpp b/llvm/lib/Analysis/BasicAliasAnalysis.cpp index 279ff06..b0578b9 100644 --- a/llvm/lib/Analysis/BasicAliasAnalysis.cpp +++ b/llvm/lib/Analysis/BasicAliasAnalysis.cpp @@ -1064,48 +1064,20 @@ BasicAliasAnalysis::aliasPHI(const PHINode *PN, uint64_t PNSize, Location(V2, V2Size, V2TBAAInfo)); if (PN > V2) std::swap(Locs.first, Locs.second); - - // Find the first incoming phi value not from its parent. - unsigned f = 0; - while (PN->getIncomingBlock(f) == PN->getParent() && - f < PN->getNumIncomingValues()-1) - ++f; - - AliasResult Alias = - aliasCheck(PN->getIncomingValue(f), PNSize, PNTBAAInfo, - PN2->getIncomingValueForBlock(PN->getIncomingBlock(f)), - V2Size, V2TBAAInfo); - if (Alias == MayAlias) - return MayAlias; - - // If the first source of the PHI nodes NoAlias and the other inputs are - // the PHI node itself through some amount of recursion this does not add - // any new information so just return NoAlias. - // bb: - // ptr = ptr2 + 1 - // loop: - // ptr_phi = phi [bb, ptr], [loop, ptr_plus_one] - // ptr2_phi = phi [bb, ptr2], [loop, ptr2_plus_one] - // ... - // ptr_plus_one = gep ptr_phi, 1 - // ptr2_plus_one = gep ptr2_phi, 1 - // We assume for the recursion that the the phis (ptr_phi, ptr2_phi) do - // not alias each other. - bool ArePhisAssumedNoAlias = false; - AliasResult OrigAliasResult = NoAlias; - if (Alias == NoAlias) { - // Pretend the phis do not alias. - assert(AliasCache.count(Locs) && - "There must exist an entry for the phi node"); - OrigAliasResult = AliasCache[Locs]; - AliasCache[Locs] = NoAlias; - ArePhisAssumedNoAlias = true; - } + // Analyse the PHIs' inputs under the assumption that the PHIs are + // NoAlias. + // If the PHIs are May/MustAlias there must be (recursively) an input + // operand from outside the PHIs' cycle that is MayAlias/MustAlias or + // there must be an operation on the PHIs within the PHIs' value cycle + // that causes a MayAlias. + // Pretend the phis do not alias. + AliasResult Alias = NoAlias; + assert(AliasCache.count(Locs) && + "There must exist an entry for the phi node"); + AliasResult OrigAliasResult = AliasCache[Locs]; + AliasCache[Locs] = NoAlias; for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { - if (i == f) - continue; - AliasResult ThisAlias = aliasCheck(PN->getIncomingValue(i), PNSize, PNTBAAInfo, PN2->getIncomingValueForBlock(PN->getIncomingBlock(i)), @@ -1116,7 +1088,7 @@ BasicAliasAnalysis::aliasPHI(const PHINode *PN, uint64_t PNSize, } // Reset if speculation failed. - if (ArePhisAssumedNoAlias && Alias != NoAlias) + if (Alias != NoAlias) AliasCache[Locs] = OrigAliasResult; return Alias; diff --git a/llvm/test/Analysis/BasicAA/phi-speculation.ll b/llvm/test/Analysis/BasicAA/phi-speculation.ll index 21c6592..5e1e118 100644 --- a/llvm/test/Analysis/BasicAA/phi-speculation.ll +++ b/llvm/test/Analysis/BasicAA/phi-speculation.ll @@ -4,9 +4,9 @@ target datalayout = ; RUN: opt < %s -basicaa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s ; ptr_phi and ptr2_phi do not alias. +; CHECK: test_noalias_1 ; CHECK: NoAlias: i32* %ptr2_phi, i32* %ptr_phi - -define i32 @test_noalias(i32* %ptr2, i32 %count, i32* %coeff) { +define i32 @test_noalias_1(i32* %ptr2, i32 %count, i32* %coeff) { entry: %ptr = getelementptr inbounds i32* %ptr2, i64 1 br label %while.body @@ -31,3 +31,64 @@ while.body: the_exit: ret i32 %add } + +; CHECK: test_noalias_2 +; CHECK: NoAlias: i32* %ptr_outer_phi, i32* %ptr_outer_phi2 +; CHECK: NoAlias: i32* %ptr2_phi, i32* %ptr_phi +define i32 @test_noalias_2(i32* %ptr2, i32 %count, i32* %coeff) { +entry: + %ptr = getelementptr inbounds i32* %ptr2, i64 1 + br label %outer.while.header + +outer.while.header: + %ptr_outer_phi = phi i32* [%ptr_inc_outer, %outer.while.backedge], [ %ptr, %entry] + %ptr_outer_phi2 = phi i32* [%ptr2_inc_outer, %outer.while.backedge], [ %ptr2, %entry] + %num.outer = phi i32 [ %count, %entry ], [ %dec.outer, %outer.while.backedge ] + br label %while.body + +while.body: + %num = phi i32 [ %count, %outer.while.header ], [ %dec, %while.body ] + %ptr_phi = phi i32* [ %ptr_outer_phi, %outer.while.header ], [ %ptr_inc, %while.body ] + %ptr2_phi = phi i32* [ %ptr_outer_phi2, %outer.while.header ], [ %ptr2_inc, %while.body ] + %result.09 = phi i32 [ 0 , %outer.while.header ], [ %add, %while.body ] + %dec = add nsw i32 %num, -1 + %0 = load i32* %ptr_phi, align 4 + store i32 %0, i32* %ptr2_phi, align 4 + %1 = load i32* %coeff, align 4 + %2 = load i32* %ptr_phi, align 4 + %mul = mul nsw i32 %1, %2 + %add = add nsw i32 %mul, %result.09 + %tobool = icmp eq i32 %dec, 0 + %ptr_inc = getelementptr inbounds i32* %ptr_phi, i64 1 + %ptr2_inc = getelementptr inbounds i32* %ptr2_phi, i64 1 + br i1 %tobool, label %outer.while.backedge, label %while.body + +outer.while.backedge: + %ptr_inc_outer = getelementptr inbounds i32* %ptr_phi, i64 1 + %ptr2_inc_outer = getelementptr inbounds i32* %ptr2_phi, i64 1 + %dec.outer = add nsw i32 %num.outer, -1 + %br.cond = icmp eq i32 %dec.outer, 0 + br i1 %br.cond, label %the_exit, label %outer.while.header + +the_exit: + ret i32 %add +} + +; CHECK: test_noalias_3 +; CHECK: MayAlias: i8* %ptr2_phi, i8* %ptr_phi +define i32 @test_noalias_3(i8* noalias %x, i8* noalias %y, i8* noalias %z, + i32 %count) { +entry: + br label %while.body + +while.body: + %num = phi i32 [ %count, %entry ], [ %dec, %while.body ] + %ptr_phi = phi i8* [ %x, %entry ], [ %z, %while.body ] + %ptr2_phi = phi i8* [ %y, %entry ], [ %ptr_phi, %while.body ] + %dec = add nsw i32 %num, -1 + %tobool = icmp eq i32 %dec, 0 + br i1 %tobool, label %the_exit, label %while.body + +the_exit: + ret i32 1 +} -- 2.7.4