Add ability to detect no-alias between different fields of the same structure

[pawosm01]

Summary

BasicAliasAnalysis tends to give up on proving no-aliasing between
two memory accesses when they share the same underlying object (e.g
when they are fields of the same structure). Such simplified approach
results in losing optimization opportunities that competing compilers
are able to exploit. Namely, when a loop invariant is loaded from the
i-th element of some array being a field of some global structure and
on each iteration i-th element of another array being a different
field of the same global structure is written to, the load is not
hoisted resulting in tragic performance at -O3 comparing to what
other compiler can achieve at the same optimization level.

This patch adds some additional logic that checks just for that:
it returns NoAlias when accessed elements of the same underlying
object are two different fields of the same structure.

Some of the test cases had to be modified in global_alias.ll which
represented the situation addressed by this patch.

This patch may seem somewhat constrained as it was focused on
improving performance of the particular loop I was working with. Doing
it any more general results in a certain number of failing test cases.

[nikic]

BasicAA doesn't do this because it's wrong. It is legal to overindex an array in a structure, as long as the bounds of the underlying object are not exceeded, even for inbounds GEP.

[lebedev.ri]

This is valid given C++ semantics, but not LLVM IR semantics.
I have it my queue to encode the C++ semantics, hang on.

[pawosm01]

I do realize that this patch isn't the best solution for this problem, but I wonder what it would be. Maybe LICM (where the decision whether to hoist is made) should rely on something more than BasicAA, but which pass should do such analysis and basing on what criteria?

[nikic]

In D110642#3030411, @pawosm01 wrote:

I do realize that this patch isn't the best solution for this problem, but I wonder what it would be. Maybe LICM (where the decision whether to hoist is made) should rely on something more than BasicAA, but which pass should do such analysis and basing on what criteria?

The correct solution for this is implemented in D109746, but still needs to be combined with additional range information encoded by the frontend and/or stronger range analysis.

[lebedev.ri]

This review may be stuck/dead, consider abandoning if no longer relevant.
Removing myself as reviewer in attempt to clean dashboard.

llvm/lib/Analysis/BasicAliasAnalysis.cpp

if (O1 != O2) {
     // location if that memory location doesn't escape. Or it may pass a
     // nocapture value to other functions as long as they don't capture it.
     if (isEscapeSource(O1) &&
         AAQI.CI->isNotCapturedBeforeOrAt(O2, cast<Instruction>(O1)))
       return AliasResult::NoAlias;
     if (isEscapeSource(O2) &&
         AAQI.CI->isNotCapturedBeforeOrAt(O1, cast<Instruction>(O2)))
       return AliasResult::NoAlias;
+  } else {
+    // In case the underlying object is a pointer to a structure and the GEP
+    // operators refer two different fields of it.
+    // Let's return NoAlias only when there is no doubt about it.
+    if (const PointerType *PtrTy = dyn_cast<PointerType>(O1->getType())) {
+      if (!(PtrTy->isOpaque())) {
+        if (PtrTy->getElementType()->isStructTy()) {
+          const GEPOperator *GEP1 = dyn_cast<GEPOperator>(V1);
+          const GEPOperator *GEP2 = dyn_cast<GEPOperator>(V2);
+          if (GEP1 && GEP2) {
+            if ((GEP1->hasIndices() && GEP2->hasIndices()) &&
+                ((GEP1->getNumIndices() <= 3U) &&
+                 (GEP2->getNumIndices() <= 3U))) {
+              const auto &Ids1 = GEP1->idx_begin();
+              const auto &Ids2 = GEP2->idx_begin();
+              for (int i = 0; i < 2; i++) {
+                const ConstantInt *Idx1 = dyn_cast<ConstantInt>(Ids1[i]);
+                const ConstantInt *Idx2 = dyn_cast<ConstantInt>(Ids2[i]);
+                if (Idx1 && Idx2) {
+                  int64_t id1 = Idx1->getSExtValue();
+                  int64_t id2 = Idx2->getSExtValue();
+                  switch (i) {
+                  case 0: // Make sure it is 'the same' struct
+                    if (id1 == id2)
+                      continue;
+                    break;
+                  case 1: // Make sure it is different field of the same struct
+                    if (id1 != id2) // It is not: no alias possible!
+                      return AliasResult::NoAlias;
+                    break;
+                  }
+                }
+                break; // We can't continue analyzing that...
+              }
+            }
+          }
+        }
+      }
+    }
   }
 
   // If the size of one access is larger than the entire object on the other
   // side, then we know such behavior is undefined and can assume no alias.
   bool NullIsValidLocation = NullPointerIsDefined(&F);
   if ((isObjectSmallerThan(
           O2, getMinimalExtentFrom(*V1, V1Size, DL, NullIsValidLocation), DL,
           TLI, NullIsValidLocation)) ||

llvm/test/Transforms/LoopVectorize/global_alias.ll

for.end:                                          ; preds = %for.cond
   %7 = load i32, i32* %arrayidx5, align 4
   ret i32 %7
 }
 
 
 ;; === Now, the tests that we could vectorize with induction changes or run-time checks ===
 
 
-; /// Different objects, swapped induction, alias at the end
+; /// Different objects, swapped induction, assuming no alias
 ; int mayAlias01 (int a) {
 ;   int i;
 ;   for (i=0; i<SIZE; i++)
 ;     Foo.A[i] = Foo.B[SIZE-i-1] + a;
 ;   return Foo.A[a];
 ; }
 ; CHECK-LABEL: define i32 @mayAlias01(
-; CHECK-NOT: add nsw <4 x i32>
+; CHECK: add nsw <4 x i32>
 ; CHECK: ret
 
 define i32 @mayAlias01(i32 %a) nounwind {
 entry:
   %a.addr = alloca i32, align 4
   %i = alloca i32, align 4
   store i32 %a, i32* %a.addr, align 4
   store i32 0, i32* %i, align 4

 
 for.end:                                          ; preds = %for.cond
   %6 = load i32, i32* %a.addr, align 4
   %arrayidx3 = getelementptr inbounds [100 x i32], [100 x i32]* getelementptr inbounds (%struct.anon, %struct.anon* @Foo, i32 0, i32 0), i32 0, i32 %6
   %7 = load i32, i32* %arrayidx3, align 4
   ret i32 %7
 }
 
-; /// Different objects, swapped induction, alias at the beginning
+; /// Different objects, swapped induction, assuming no alias
 ; int mayAlias02 (int a) {
 ;   int i;
 ;   for (i=0; i<SIZE; i++)
 ;     Foo.A[SIZE-i-1] = Foo.B[i] + a;
 ;   return Foo.A[a];
 ; }
 ; CHECK-LABEL: define i32 @mayAlias02(
-; CHECK-NOT: add nsw <4 x i32>
+; CHECK: add nsw <4 x i32>
 ; CHECK: ret
 
 define i32 @mayAlias02(i32 %a) nounwind {
 entry:
   %a.addr = alloca i32, align 4
   %i = alloca i32, align 4
   store i32 %a, i32* %a.addr, align 4
   store i32 0, i32* %i, align 4

 
 ; int mustAlias01 (int a) {
 ;   int i;
 ;   for (i=0; i<SIZE; i++)
 ;     Foo.A[i+10] = Foo.B[SIZE-i-1] + a;
 ;   return Foo.A[a];
 ; }
 ; CHECK-LABEL: define i32 @mustAlias01(
-; CHECK-NOT: add nsw <4 x i32>
+; CHECK: add nsw <4 x i32>
 ; CHECK: ret
 
 define i32 @mustAlias01(i32 %a) nounwind {
 entry:
   %a.addr = alloca i32, align 4
   %i = alloca i32, align 4
   store i32 %a, i32* %a.addr, align 4
   store i32 0, i32* %i, align 4

 
 ; int mustAlias02 (int a) {
 ;   int i;
 ;   for (i=0; i<SIZE; i++)
 ;     Foo.A[i] = Foo.B[SIZE-i-10] + a;
 ;   return Foo.A[a];
 ; }
 ; CHECK-LABEL: define i32 @mustAlias02(
-; CHECK-NOT: add nsw <4 x i32>
+; CHECK: add nsw <4 x i32>
 ; CHECK: ret
 
 define i32 @mustAlias02(i32 %a) nounwind {
 entry:
   %a.addr = alloca i32, align 4
   %i = alloca i32, align 4
   store i32 %a, i32* %a.addr, align 4
   store i32 0, i32* %i, align 4

 
 ; int mustAlias03 (int a) {
 ;   int i;
 ;   for (i=0; i<SIZE; i++)
 ;     Foo.A[i+10] = Foo.B[SIZE-i-10] + a;
 ;   return Foo.A[a];
 ; }
 ; CHECK-LABEL: define i32 @mustAlias03(
-; CHECK-NOT: add nsw <4 x i32>
+; CHECK: add nsw <4 x i32>
 ; CHECK: ret
 
 define i32 @mustAlias03(i32 %a) nounwind {
 entry:
   %a.addr = alloca i32, align 4
   %i = alloca i32, align 4
   store i32 %a, i32* %a.addr, align 4
   store i32 0, i32* %i, align 4