From e987fbdd85d6bb5964d9db7a729d6ec8b1dc2322 Mon Sep 17 00:00:00 2001 From: Nikita Popov Date: Sat, 21 Nov 2020 17:29:13 +0100 Subject: [PATCH] [BasicAA] Generalize recursive phi alias analysis For recursive phis, we skip the recursive operands and check that the remaining operands are NoAlias with an unknown size. Currently, this is limited to inbounds GEPs with positive offsets, to guarantee that the recursion only ever increases the pointer. Make this more general by only requiring that the underlying object of the phi operand is the phi itself, i.e. it it based on itself in some way. To compensate, we need to use a beforeOrAfterPointer() location size, as we no longer have the guarantee that the pointer is strictly increasing. This allows us to handle some additional cases like negative geps, geps with dynamic offsets or geps that aren't inbounds. Differential Revision: https://reviews.llvm.org/D91914 --- llvm/lib/Analysis/BasicAliasAnalysis.cpp | 35 +++++++------------------ llvm/test/Analysis/BasicAA/recphi.ll | 8 +++--- llvm/test/CodeGen/Thumb2/mve-float32regloops.ll | 4 +-- 3 files changed, 16 insertions(+), 31 deletions(-) diff --git a/llvm/lib/Analysis/BasicAliasAnalysis.cpp b/llvm/lib/Analysis/BasicAliasAnalysis.cpp index 2e4ee1c..2fb353e 100644 --- a/llvm/lib/Analysis/BasicAliasAnalysis.cpp +++ b/llvm/lib/Analysis/BasicAliasAnalysis.cpp @@ -1516,27 +1516,16 @@ AliasResult BasicAAResult::aliasPHI(const PHINode *PN, LocationSize PNSize, } SmallVector V1Srcs; - // For a recursive phi, that recurses through a contant gep, we can perform - // aliasing calculations using the other phi operands with an unknown size to - // specify that an unknown number of elements after the initial value are - // potentially accessed. + // If a phi operand recurses back to the phi, we can still determine NoAlias + // if we don't alias the underlying objects of the other phi operands, as we + // know that the recursive phi needs to be based on them in some way. bool isRecursive = false; auto CheckForRecPhi = [&](Value *PV) { if (!EnableRecPhiAnalysis) return false; - if (GEPOperator *PVGEP = dyn_cast(PV)) { - // 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. Handle this case specially - // below. We need to ensure that the phi is inbounds and has a constant - // positive operand so that we can check for alias with the initial value - // and an unknown but positive size. - if (PVGEP->getPointerOperand() == PN && PVGEP->isInBounds() && - PVGEP->getNumIndices() == 1 && isa(PVGEP->idx_begin()) && - !cast(PVGEP->idx_begin())->isNegative()) { - isRecursive = true; - return true; - } + if (getUnderlyingObject(PV) == PN) { + isRecursive = true; + return true; } return false; }; @@ -1582,15 +1571,11 @@ AliasResult BasicAAResult::aliasPHI(const PHINode *PN, LocationSize PNSize, if (V1Srcs.empty()) return MayAlias; - // If this PHI node is recursive, set the size of the accessed memory to - // unknown to represent all the possible values the GEP could advance the - // pointer to. + // If this PHI node is recursive, indicate that the pointer may be moved + // across iterations. We can only prove NoAlias if different underlying + // objects are involved. if (isRecursive) - // TODO: We are checking above that the addrec GEP has a positive offset - // and can thus assume that all accesses happen after the base pointer. - // It might be better to drop the offset requirement and use - // beforeOrAfterPointer(). - PNSize = LocationSize::afterPointer(); + PNSize = LocationSize::beforeOrAfterPointer(); // In the recursive alias queries below, we may compare values from two // different loop iterations. Keep track of visited phi blocks, which will diff --git a/llvm/test/Analysis/BasicAA/recphi.ll b/llvm/test/Analysis/BasicAA/recphi.ll index 26114fc..13a58fb 100644 --- a/llvm/test/Analysis/BasicAA/recphi.ll +++ b/llvm/test/Analysis/BasicAA/recphi.ll @@ -141,10 +141,10 @@ if.end: ; preds = %f.exit ; CHECK: NoAlias: [3 x i16]* %int_arr.10, i16** %argv.6.par ; CHECK: NoAlias: i16* %_tmp1, i16** %argv.6.par ; CHECK: PartialAlias: [3 x i16]* %int_arr.10, i16* %_tmp1 -; CHECK: MayAlias: i16* %ls1.9.0, i16** %argv.6.par +; CHECK: NoAlias: i16* %ls1.9.0, i16** %argv.6.par ; CHECK: MayAlias: [3 x i16]* %int_arr.10, i16* %ls1.9.0 ; CHECK: MayAlias: i16* %_tmp1, i16* %ls1.9.0 -; CHECK: MayAlias: i16* %_tmp7, i16** %argv.6.par +; CHECK: NoAlias: i16* %_tmp7, i16** %argv.6.par ; CHECK: MayAlias: [3 x i16]* %int_arr.10, i16* %_tmp7 ; CHECK: MayAlias: i16* %_tmp1, i16* %_tmp7 ; CHECK: NoAlias: i16* %_tmp7, i16* %ls1.9.0 @@ -191,9 +191,9 @@ bb5: ; preds = %bb3, %bb4 ; CHECK-LABEL: Function: dynamic_offset ; CHECK: NoAlias: i8* %a, i8* %p.base ; CHECK: MayAlias: i8* %p, i8* %p.base -; CHECK: MayAlias: i8* %a, i8* %p +; CHECK: NoAlias: i8* %a, i8* %p ; CHECK: MayAlias: i8* %p.base, i8* %p.next -; CHECK: MayAlias: i8* %a, i8* %p.next +; CHECK: NoAlias: i8* %a, i8* %p.next ; CHECK: MayAlias: i8* %p, i8* %p.next define void @dynamic_offset(i1 %c, i8* noalias %p.base) { entry: diff --git a/llvm/test/CodeGen/Thumb2/mve-float32regloops.ll b/llvm/test/CodeGen/Thumb2/mve-float32regloops.ll index b0fa52b..167a17c 100644 --- a/llvm/test/CodeGen/Thumb2/mve-float32regloops.ll +++ b/llvm/test/CodeGen/Thumb2/mve-float32regloops.ll @@ -1439,12 +1439,12 @@ define arm_aapcs_vfpcc void @arm_biquad_cascade_stereo_df2T_f32(%struct.arm_biqu ; CHECK-NEXT: @ => This Inner Loop Header: Depth=2 ; CHECK-NEXT: vldrw.u32 q4, [r1, q0, uxtw #2] ; CHECK-NEXT: vldrw.u32 q5, [r4, q0, uxtw #2] +; CHECK-NEXT: vldrw.u32 q3, [sp, #8] ; CHECK-NEXT: adds r1, #8 ; CHECK-NEXT: vfma.f32 q5, q4, r5 +; CHECK-NEXT: vfma.f32 q3, q5, q2 ; CHECK-NEXT: vstmia r7, {s20, s21} ; CHECK-NEXT: adds r7, #8 -; CHECK-NEXT: vldrw.u32 q3, [sp, #8] -; CHECK-NEXT: vfma.f32 q3, q5, q2 ; CHECK-NEXT: vfma.f32 q3, q4, q1 ; CHECK-NEXT: vstrw.32 q3, [r4] ; CHECK-NEXT: le lr, .LBB17_3 -- 2.7.4