[BasicAliasAnalysis] Allow idAddofNonZero() for values coming from the same loop iteration.

[Farhana]

Summary

This is a fix for the case in PR33549.

Current basic alias analysis is very conservative when it tries to analyze two GEP indices with the same base pointers. This patch tries to relax it a bit. It makes the assumption that the values(GEP indices) are from the same iteration if the analysis has not visited any phi's yet.

[• dberlin]

"It makes the assumption that the values(GEP indices) are from the same iteration if the analysis has not visited any phi's yet."

Can you prove that this is actually true for all codepaths through here?

I'm still of the mind the right answer is to rip more of this code out, and let scev-aa handle base + loop variant ptr, rather than try to have a half-working implementation of loop analysis in basicaa.
SCEV was made for this. It knows what it is doing, and is used widely enough that it is likely to be correct.

This cycle handling is also the most expensive part of basicaa. I have testcases where basicaa takes as long to answer simple intraprocedural queries in the same time it takes cfl-steens to do whole-module interprocedural analysis :)

[Farhana]

In D34478#787319, @dberlin wrote:

"It makes the assumption that the values(GEP indices) are from the same iteration if the analysis has not visited any phi's yet."

Can you prove that this is actually true for all codepaths through here?

I agree that my comment about loop iteration is misleading.

In order to call isAddOfNonZero() on index1 and index2 and check whether index2 equals to index1 + x( and, vice versa), we need to prove that we are working on the same copy of index1. Which means the instance that used in index1 is the same as the one used in index2.
If we haven’t visited any phis yet, we can assume that part of the code is flat and we have the same copy, right?

I'm still of the mind the right answer is to rip more of this code out, and let scev-aa handle base + loop variant ptr, rather than try to have a half-working implementation of loop analysis in basicaa.
SCEV was made for this. It knows what it is doing, and is used widely enough that it is likely to be correct.

This cycle handling is also the most expensive part of basicaa. I have testcases where basicaa takes as long to answer simple intraprocedural queries in the same time it takes cfl-steens to do whole-module interprocedural analysis :)

I totally agree with you. I was just thinking we might want a temporary solution(specifically a cheap one) while we are waiting on that.

[• dberlin]

In D34478#787355, @Farhana wrote:

In D34478#787319, @dberlin wrote:

"It makes the assumption that the values(GEP indices) are from the same iteration if the analysis has not visited any phi's yet."

Can you prove that this is actually true for all codepaths through here?

I agree that my comment about loop iteration is misleading.

In order to call isAddOfNonZero() on index1 and index2 and check whether index2 equals to index1 + x( and, vice versa), we need to prove that we are working on the same copy of index1. Which means the instance that used in index1 is the same as the one used in index2.
If we haven’t visited any phis yet, we can assume that part of the code is flat and we have the same copy, right?

This is precisely my question: Are you guaranteed that all codepaths end up here only in that situation?

I'm still of the mind the right answer is to rip more of this code out, and let scev-aa handle base + loop variant ptr, rather than try to have a half-working implementation of loop analysis in basicaa.
SCEV was made for this. It knows what it is doing, and is used widely enough that it is likely to be correct.

This cycle handling is also the most expensive part of basicaa. I have testcases where basicaa takes as long to answer simple intraprocedural queries in the same time it takes cfl-steens to do whole-module interprocedural analysis :)

I totally agree with you. I was just thinking we might want a temporary solution(specifically a cheap one) while we are waiting on that.

With no offense meant (and i'm happy to accept the patch if we can prove it right): This is precisely how BasicAA got into this situation.
We add stuff thinking "well, it's probably right", and then it turns out not to be ;)

So i want to be super careful that we can prove to ourselves that this is right.

[Farhana]

In D34478#789005, @dberlin wrote:

In D34478#787355, @Farhana wrote:

In D34478#787319, @dberlin wrote:

"It makes the assumption that the values(GEP indices) are from the same iteration if the analysis has not visited any phi's yet."

Can you prove that this is actually true for all codepaths through here?

I agree that my comment about loop iteration is misleading.

In order to call isAddOfNonZero() on index1 and index2 and check whether index2 equals to index1 + x( and, vice versa), we need to prove that we are working on the same copy of index1. Which means the instance that used in index1 is the same as the one used in index2.
If we haven’t visited any phis yet, we can assume that part of the code is flat and we have the same copy, right?

This is precisely my question: Are you guaranteed that all codepaths end up here only in that situation?

Sorry, I misunderstood your question earlier.

Yes, it is guaranteed that BasicAA hasn't done any phi translation so far for these two GEP indices when the code path reached in that situation. It not only guarantees that the phi translation has not happened for these two indices, it also guarantees that the phi-translation hasn't happened any of its parent expressions either starting from the two root memory locations.

More Details:

After each alias analysis for a pair of memory locations BasicAA always clears out the VisitedPhiBBs. Checking only for whether VisitedPhiBBs is empty leaves the analysis still pretty conservative since we don't really check whether the phi translation has anything to do with these two GEP indices but it's probably good enough for a short term solution. Since there is a tradeoff, checking for GEP indices in phi translation will induce more compile time.

AliasResult BasicAAResult::alias(..) {
         ...
VisitedPhiBBs.clear();
return Alias;
}

alias():
VisitedPhiBBs = empty

    MemLoc1           
     /  \                    
 base idx1            
        |                                
       phi                           
   
  
   MemLoc2                                        
    /   \                                                                   
base  idx2 
       /  \
   idx1   N
     |
   phi  (no phis are translated so far. Therefore, idx1 in memloc2 and idx1 in memloc1 have the same live in value)

I'm still of the mind the right answer is to rip more of this code out, and let scev-aa handle base + loop variant ptr, rather than try to have a half-working implementation of loop analysis in basicaa.
SCEV was made for this. It knows what it is doing, and is used widely enough that it is likely to be correct.

This cycle handling is also the most expensive part of basicaa. I have testcases where basicaa takes as long to answer simple intraprocedural queries in the same time it takes cfl-steens to do whole-module interprocedural analysis :)

I totally agree with you. I was just thinking we might want a temporary solution(specifically a cheap one) while we are waiting on that.

With no offense meant (and i'm happy to accept the patch if we can prove it right): This is precisely how BasicAA got into this situation.
We add stuff thinking "well, it's probably right", and then it turns out not to be ;)

So i want to be super careful that we can prove to ourselves that this is right.

I understand your concern :).

[Farhana]

Hi Daniel,

Any news on this?

Farhana

[• dberlin]

I'm fine with this for the moment, but, as you know, i think we gotta stop thinking "bandaids" :)

[chapuni]

Reverted in r307613. This caused miscompilation.
See http://bb.pgr.jp/builders/bootstrap-clang-libcxx-lld-i686-linux/builds/172
(Note, reproduced locally w/o modules)

include/llvm/Analysis/BasicAliasAnalysis.h

private:
   void GetIndexDifference(SmallVectorImpl<VariableGEPIndex> &Dest,
                           const SmallVectorImpl<VariableGEPIndex> &Src);
 
   AliasResult aliasGEP(const GEPOperator *V1, uint64_t V1Size,
                        const AAMDNodes &V1AAInfo, const Value *V2,
                        uint64_t V2Size, const AAMDNodes &V2AAInfo,
                        const Value *UnderlyingV1, const Value *UnderlyingV2);
 
+  AliasResult aliasSameBasePointerGEPs(const GEPOperator *GEP1,
+                                       uint64_t V1Size,
+                                       const GEPOperator *GEP2,
+                                       uint64_t V2Size,
+                                       const DataLayout &DL);
+
   AliasResult aliasPHI(const PHINode *PN, uint64_t PNSize,
                        const AAMDNodes &PNAAInfo, const Value *V2,
                        uint64_t V2Size, const AAMDNodes &V2AAInfo,
                        const Value *UnderV2);
 
   AliasResult aliasSelect(const SelectInst *SI, uint64_t SISize,
                           const AAMDNodes &SIAAInfo, const Value *V2,
                           uint64_t V2Size, const AAMDNodes &V2AAInfo,

lib/Analysis/BasicAliasAnalysis.cpp

if (isIntrinsicCall(CS2, Intrinsic::experimental_guard))
     return getModRefBehavior(CS1) & MRI_Mod ? MRI_Mod : MRI_NoModRef;
 
   // The AAResultBase base class has some smarts, lets use them.
   return AAResultBase::getModRefInfo(CS1, CS2);
 }
 
 /// Provide ad-hoc rules to disambiguate accesses through two GEP operators,
 /// both having the exact same pointer operand.
-static AliasResult aliasSameBasePointerGEPs(const GEPOperator *GEP1,
+AliasResult BasicAAResult::aliasSameBasePointerGEPs(const GEPOperator *GEP1,
                                                     uint64_t V1Size,
                                                     const GEPOperator *GEP2,
                                                     uint64_t V2Size,
                                                     const DataLayout &DL) {
 
   assert(GEP1->getPointerOperand()->stripPointerCastsAndBarriers() ==
              GEP2->getPointerOperand()->stripPointerCastsAndBarriers() &&
          GEP1->getPointerOperandType() == GEP2->getPointerOperandType() &&
          "Expected GEPs with the same pointer operand");
 
   // Try to determine whether GEP1 and GEP2 index through arrays, into structs,
   // such that the struct field accesses provably cannot alias.
for (unsigned i = 0, e = GEP1->getNumIndices() - 1; i != e; ++i)
       if (GEP1->getOperand(i + 1) != GEP2->getOperand(i + 1))
         return MayAlias;
 
     // Now we know that the array/pointer that GEP1 indexes into and that
     // that GEP2 indexes into must either precisely overlap or be disjoint.
     // Because they cannot partially overlap and because fields in an array
     // cannot overlap, if we can prove the final indices are different between
     // GEP1 and GEP2, we can conclude GEP1 and GEP2 don't alias.
-    
     // If the last indices are constants, we've already checked they don't
     // equal each other so we can exit early.
     if (C1 && C2)
       return NoAlias;
     {
       Value *GEP1LastIdx = GEP1->getOperand(GEP1->getNumOperands() - 1);
       Value *GEP2LastIdx = GEP2->getOperand(GEP2->getNumOperands() - 1);
-      if (isa<PHINode>(GEP1LastIdx) || isa<PHINode>(GEP2LastIdx)) {
+      if ((isa<PHINode>(GEP1LastIdx) || isa<PHINode>(GEP2LastIdx)) &&
+          VisitedPhiBBs.size() != 0) {
         // If one of the indices is a PHI node, be safe and only use
         // computeKnownBits so we don't make any assumptions about the
         // relationships between the two indices. This is important if we're
         // asking about values from different loop iterations. See PR32314.
+        // But, with zero visitedPhiBBs we can guarantee that the values are
+        // from the same iteration. Therefore, we can avoid doing this
+        // conservative check.
         // TODO: We may be able to change the check so we only do this when
         // we definitely looked through a PHINode.
         KnownBits Known1 = computeKnownBits(GEP1LastIdx, DL);
         KnownBits Known2 = computeKnownBits(GEP2LastIdx, DL);
         if (Known1.Zero.intersects(Known2.One) ||
             Known1.One.intersects(Known2.Zero))
           return NoAlias;
       } else if (isKnownNonEqual(GEP1LastIdx, GEP2LastIdx, DL))

lib/Analysis/ValueTracking.cpp

else if (match(V, m_Shr(m_Value(X), m_Value(Y)))) {
     // out are known to be zero, and X is known non-zero then at least one
     // non-zero bit must remain.
     if (ConstantInt *Shift = dyn_cast<ConstantInt>(Y)) {
       auto ShiftVal = Shift->getLimitedValue(BitWidth - 1);
       // Is there a known one in the portion not shifted out?
       if (Known.countMaxLeadingZeros() < BitWidth - ShiftVal)
         return true;
       // Are all the bits to be shifted out known zero?
-      if (Known.countMinTrailingZeros() >= ShiftVal)
+      if (Known.isUnknown() || Known.countMinTrailingZeros() >= ShiftVal)
         return isKnownNonZero(X, Depth, Q);
     }
   }
   // div exact can only produce a zero if the dividend is zero.
   else if (match(V, m_Exact(m_IDiv(m_Value(X), m_Value())))) {
     return isKnownNonZero(X, Depth, Q);
   }
   // X + Y.

test/Transforms/GVN/pr33549.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -S -gvn < %s | FileCheck %s
+
+; The purpose of this test is to make sure that the load(%2) is pre'd.
+
+; ModuleID = 'test.c'
+source_filename = "test.c"
+target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-a:0:32-n32-S64"
+target triple = "thumbv7em-arm-none-eabi"
+
+@Data = common local_unnamed_addr global [32 x i32] zeroinitializer, align 4
+
+; Function Attrs: norecurse nounwind
+define void @testshl() local_unnamed_addr #0 {
+; CHECK-LABEL: @testshl(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
+; CHECK:       for.body:
+; CHECK-NEXT:    [[K_031:%.*]] = phi i32 [ 1, [[ENTRY:%.*]] ], [ [[INC9:%.*]], [[FOR_INC8:%.*]] ]
+; CHECK-NEXT:    [[SHL:%.*]] = shl i32 1, [[K_031]]
+; CHECK-NEXT:    [[SHR:%.*]] = ashr exact i32 [[SHL]], 1
+; CHECK-NEXT:    [[CMP229:%.*]] = icmp slt i32 [[SHL]], 64
+; CHECK-NEXT:    br i1 [[CMP229]], label [[FOR_BODY3_PREHEADER:%.*]], label [[FOR_INC8]]
+; CHECK:       for.body3.preheader:
+; CHECK-NEXT:    [[DIV:%.*]] = sdiv i32 [[SHR]], 2
+; CHECK-NEXT:    br label [[FOR_BODY3:%.*]]
+; CHECK:       for.body3:
+; CHECK-NEXT:    [[I_030:%.*]] = phi i32 [ [[INC:%.*]], [[FOR_BODY3]] ], [ [[DIV]], [[FOR_BODY3_PREHEADER]] ]
+; CHECK-NEXT:    [[ADD:%.*]] = add nsw i32 [[I_030]], [[SHR]]
+; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds [32 x i32], [32 x i32]* @Data, i32 0, i32 [[ADD]]
+; CHECK-NEXT:    [[ARRAYIDX4:%.*]] = getelementptr inbounds [32 x i32], [32 x i32]* @Data, i32 0, i32 [[I_030]]
+; CHECK-NEXT:    [[TMP0:%.*]] = load i32, i32* [[ARRAYIDX]], align 4, !tbaa !3
+; CHECK-NEXT:    [[TMP1:%.*]] = load i32, i32* [[ARRAYIDX4]], align 4, !tbaa !3
+; CHECK-NEXT:    [[SUB:%.*]] = sub nsw i32 [[TMP1]], [[TMP0]]
+; CHECK-NEXT:    store i32 [[SUB]], i32* [[ARRAYIDX]], align 4, !tbaa !3
+; CHECK-NEXT:    [[ADD7:%.*]] = add nsw i32 [[TMP1]], [[TMP0]]
+; CHECK-NEXT:    store i32 [[ADD7]], i32* [[ARRAYIDX4]], align 4, !tbaa !3
+; CHECK-NEXT:    [[INC]] = add nsw i32 [[I_030]], 1
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp slt i32 [[I_030]], 15
+; CHECK-NEXT:    br i1 [[CMP2]], label [[FOR_BODY3]], label [[FOR_INC8]]
+; CHECK:       for.inc8:
+; CHECK-NEXT:    [[INC9]] = add nuw nsw i32 [[K_031]], 1
+; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i32 [[INC9]], 8
+; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_END10:%.*]], label [[FOR_BODY]]
+; CHECK:       for.end10:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %for.body
+
+for.body:                                         ; preds = %for.inc8, %entry
+  %k.031 = phi i32 [ 1, %entry ], [ %inc9, %for.inc8 ]
+  %shl = shl i32 1, %k.031
+  %shr = ashr exact i32 %shl, 1
+  %cmp229 = icmp slt i32 %shl, 64
+  br i1 %cmp229, label %for.body3.preheader, label %for.inc8
+
+for.body3.preheader:                              ; preds = %for.body
+  %div = sdiv i32 %shr, 2
+  br label %for.body3
+
+for.body3:                                        ; preds = %for.body3.preheader, %for.body3
+  %i.030 = phi i32 [ %inc, %for.body3 ], [ %div, %for.body3.preheader ]
+  %add = add nsw i32 %i.030, %shr
+  %arrayidx = getelementptr inbounds [32 x i32], [32 x i32]* @Data, i32 0, i32 %add
+  %arrayidx4 = getelementptr inbounds [32 x i32], [32 x i32]* @Data, i32 0, i32 %i.030
+  %0 = load i32, i32* %arrayidx, align 4, !tbaa !3
+  %1 = load i32, i32* %arrayidx4, align 4, !tbaa !3
+  %sub = sub nsw i32 %1, %0
+  store i32 %sub, i32* %arrayidx, align 4, !tbaa !3
+  %2 = load i32, i32* %arrayidx4, align 4, !tbaa !3
+  %add7 = add nsw i32 %2, %0
+  store i32 %add7, i32* %arrayidx4, align 4, !tbaa !3
+  %inc = add nsw i32 %i.030, 1
+  %cmp2 = icmp slt i32 %i.030, 15
+  br i1 %cmp2, label %for.body3, label %for.inc8
+
+for.inc8:                                         ; preds = %for.body3, %for.body
+  %inc9 = add nuw nsw i32 %k.031, 1
+  %exitcond = icmp eq i32 %inc9, 8
+  br i1 %exitcond, label %for.end10, label %for.body
+
+for.end10:                                        ; preds = %for.inc8
+  ret void
+}
+
+attributes #0 = { norecurse nounwind "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="cortex-m7" "target-features"="+d16,+dsp,+fp-armv8,+hwdiv,+strict-align,+thumb-mode" "unsafe-fp-math"="false" "use-soft-float"="false" }
+
+!llvm.module.flags = !{!0, !1}
+!llvm.ident = !{!2}
+
+!0 = !{i32 1, !"wchar_size", i32 4}
+!1 = !{i32 1, !"min_enum_size", i32 4}
+!2 = !{!"clang version 5.0.0 (http://llvm.org/git/clang.git 100ecde90ef26ee81763214d5fb335415ffc2b53) (http://llvm.org/git/llvm.git f2fe26d60eb81a699f2d565e8baabcaf32f9c5ea)"}
+!3 = !{!4, !4, i64 0}
+!4 = !{!"int", !5, i64 0}
+!5 = !{!"omnipotent char", !6, i64 0}
+!6 = !{!"Simple C/C++ TBAA"}