From a6f86fc6fa98a4b6386f3d9cbe756be0556709cb Mon Sep 17 00:00:00 2001 From: Hal Finkel Date: Sat, 17 Nov 2012 02:33:15 +0000 Subject: [PATCH] Phi speculation improvement for BasicAA This is a partial solution to PR14351. It removes some of the special significance of the first incoming phi value in the phi aliasing checking logic in BasicAA. In the context of a loop, the old logic assumes that the first incoming value is the interesting one (meaning that it is the one that comes from outside the loop), but this is often not the case. With this change, we now test first the incoming value that comes from a block other than the parent of the phi being tested. llvm-svn: 168245 --- llvm/lib/Analysis/BasicAliasAnalysis.cpp | 15 ++++-- llvm/test/Analysis/BasicAA/phi-spec-order.ll | 71 ++++++++++++++++++++++++++++ 2 files changed, 83 insertions(+), 3 deletions(-) create mode 100644 llvm/test/Analysis/BasicAA/phi-spec-order.ll diff --git a/llvm/lib/Analysis/BasicAliasAnalysis.cpp b/llvm/lib/Analysis/BasicAliasAnalysis.cpp index 4bb93ee..e8b3063 100644 --- a/llvm/lib/Analysis/BasicAliasAnalysis.cpp +++ b/llvm/lib/Analysis/BasicAliasAnalysis.cpp @@ -1065,9 +1065,15 @@ BasicAliasAnalysis::aliasPHI(const PHINode *PN, uint64_t PNSize, 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(0), PNSize, PNTBAAInfo, - PN2->getIncomingValueForBlock(PN->getIncomingBlock(0)), + aliasCheck(PN->getIncomingValue(f), PNSize, PNTBAAInfo, + PN2->getIncomingValueForBlock(PN->getIncomingBlock(f)), V2Size, V2TBAAInfo); if (Alias == MayAlias) return MayAlias; @@ -1096,7 +1102,10 @@ BasicAliasAnalysis::aliasPHI(const PHINode *PN, uint64_t PNSize, ArePhisAssumedNoAlias = true; } - for (unsigned i = 1, e = PN->getNumIncomingValues(); i != e; ++i) { + 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)), diff --git a/llvm/test/Analysis/BasicAA/phi-spec-order.ll b/llvm/test/Analysis/BasicAA/phi-spec-order.ll new file mode 100644 index 0000000..27d47bc --- /dev/null +++ b/llvm/test/Analysis/BasicAA/phi-spec-order.ll @@ -0,0 +1,71 @@ +target datalayout = "E-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-f128:128:128-v128:128:128-n32:64" +target triple = "powerpc64-bgq-linux" +; RUN: opt < %s -basicaa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s + +@X = external global [16000 x double], align 32 +@Y = external global [16000 x double], align 32 + +define signext i32 @s000() nounwind { +entry: + br label %for.cond2.preheader + +for.cond2.preheader: ; preds = %for.end, %entry + %nl.018 = phi i32 [ 0, %entry ], [ %inc9, %for.end ] + br label %for.body4 + +for.body4: ; preds = %for.body4, %for.cond2.preheader + %lsr.iv4 = phi [16000 x double]* [ %i11, %for.body4 ], [ bitcast (double* getelementptr inbounds ([16000 x double]* @Y, i64 0, i64 8) + to [16000 x double]*), %for.cond2.preheader ] + %lsr.iv1 = phi [16000 x double]* [ %i10, %for.body4 ], [ @X, %for.cond2.preheader ] + +; CHECK: NoAlias:{{[ \t]+}}[16000 x double]* %lsr.iv1, [16000 x double]* %lsr.iv4 + + %lsr.iv = phi i32 [ %lsr.iv.next, %for.body4 ], [ 16000, %for.cond2.preheader ] + %lsr.iv46 = bitcast [16000 x double]* %lsr.iv4 to <4 x double>* + %lsr.iv12 = bitcast [16000 x double]* %lsr.iv1 to <4 x double>* + %scevgep11 = getelementptr <4 x double>* %lsr.iv46, i64 -2 + %i6 = load <4 x double>* %scevgep11, align 32, !tbaa !0 + %add = fadd <4 x double> %i6, + store <4 x double> %add, <4 x double>* %lsr.iv12, align 32, !tbaa !0 + %scevgep10 = getelementptr <4 x double>* %lsr.iv46, i64 -1 + %i7 = load <4 x double>* %scevgep10, align 32, !tbaa !0 + %add.4 = fadd <4 x double> %i7, + %scevgep9 = getelementptr <4 x double>* %lsr.iv12, i64 1 + store <4 x double> %add.4, <4 x double>* %scevgep9, align 32, !tbaa !0 + %i8 = load <4 x double>* %lsr.iv46, align 32, !tbaa !0 + %add.8 = fadd <4 x double> %i8, + %scevgep8 = getelementptr <4 x double>* %lsr.iv12, i64 2 + store <4 x double> %add.8, <4 x double>* %scevgep8, align 32, !tbaa !0 + %scevgep7 = getelementptr <4 x double>* %lsr.iv46, i64 1 + %i9 = load <4 x double>* %scevgep7, align 32, !tbaa !0 + %add.12 = fadd <4 x double> %i9, + %scevgep3 = getelementptr <4 x double>* %lsr.iv12, i64 3 + store <4 x double> %add.12, <4 x double>* %scevgep3, align 32, !tbaa !0 + +; CHECK: NoAlias:{{[ \t]+}}<4 x double>* %scevgep11, <4 x double>* %scevgep7 +; CHECK: NoAlias:{{[ \t]+}}<4 x double>* %scevgep10, <4 x double>* %scevgep7 +; CHECK: NoAlias:{{[ \t]+}}<4 x double>* %scevgep7, <4 x double>* %scevgep9 +; CHECK: NoAlias:{{[ \t]+}}<4 x double>* %scevgep11, <4 x double>* %scevgep3 +; CHECK: NoAlias:{{[ \t]+}}<4 x double>* %scevgep10, <4 x double>* %scevgep3 +; CHECK: NoAlias:{{[ \t]+}}<4 x double>* %scevgep3, <4 x double>* %scevgep9 + + %lsr.iv.next = add i32 %lsr.iv, -16 + %scevgep = getelementptr [16000 x double]* %lsr.iv1, i64 0, i64 16 + %i10 = bitcast double* %scevgep to [16000 x double]* + %scevgep5 = getelementptr [16000 x double]* %lsr.iv4, i64 0, i64 16 + %i11 = bitcast double* %scevgep5 to [16000 x double]* + %exitcond.15 = icmp eq i32 %lsr.iv.next, 0 + br i1 %exitcond.15, label %for.end, label %for.body4 + +for.end: ; preds = %for.body4 + %inc9 = add nsw i32 %nl.018, 1 + %exitcond = icmp eq i32 %inc9, 400000 + br i1 %exitcond, label %for.end10, label %for.cond2.preheader + +for.end10: ; preds = %for.end + ret i32 0 +} + +!0 = metadata !{metadata !"double", metadata !1} +!1 = metadata !{metadata !"omnipotent char", metadata !2} +!2 = metadata !{metadata !"Simple C/C++ TBAA"} -- 2.7.4