[Attributor] Track a GEP Instruction in align deduction

[uenoku]

Summary

This patch enables us to track GEP instruction in align deduction.
If a pointer B is defined as A+Offset and known to have alignment C, there exists some integer Q such that

A + Offset = C * Q = B

So we can say that the maximum power of two which is a divisor of gcd(Offset, C) is an alignment.

[lebedev.ri]

llvm/test/Transforms/FunctionAttrs/align.ll

352–359

Is there test coverage where this is a store instead of load,
and maybe there is a call to a function that expects certain aliment of it's pointer argument?

[uenoku]

Fix a call handling and add tests for store and calls.

[uenoku]

llvm/test/Transforms/FunctionAttrs/align.ll

352–359

Thank you for the comment. I added tests for store(12-3, 12-4) and call(12-5, 12-6).

[jdoerfert]

Looks fine from my side. @lebedev.ri please feel free to comment and please accept once satisfied.

[lebedev.ri]

In D70392#1755334, @jdoerfert wrote:

Looks fine from my side. @lebedev.ri please feel free to comment and please accept once satisfied.

No further comments from me; i'm not really familiar with the code in question to review.

llvm/lib/Transforms/IPO/Attributor.cpp

 };
 
 // ------------------------ Align Argument Attribute ------------------------
 
 static unsigned int getKnownAlignForUse(Attributor &A,
                                         AbstractAttribute &QueryingAA,
                                         Value &AssociatedValue, const Use *U,
                                         const Instruction *I, bool &TrackUse) {
+  // We need to follow common pointer manipulation uses to the accesses they
+  // feed into.
+  if (isa<CastInst>(I)) {
+    TrackUse = true;
+    return 0;
+  }
+  if (auto *GEP = dyn_cast<GetElementPtrInst>(I)) {
+    if (GEP->hasAllConstantIndices()) {
+      TrackUse = true;
+      return 0;
+    }
+  }
+
+  unsigned Alignment = 0;
   if (ImmutableCallSite ICS = ImmutableCallSite(I)) {
     if (ICS.isBundleOperand(U) || ICS.isCallee(U))
       return 0;
 
     unsigned ArgNo = ICS.getArgumentNo(U);
     IRPosition IRP = IRPosition::callsite_argument(ICS, ArgNo);
     // As long as we only use known information there is no need to track
     // dependences here.
     auto &AlignAA = A.getAAFor<AAAlign>(QueryingAA, IRP,
                                         /* TrackDependence */ false);
-    return AlignAA.getKnownAlign();
-  }
-
-  // We need to follow common pointer manipulation uses to the accesses they
-  // feed into.
-  // TODO: Consider gep instruction
-  if (isa<CastInst>(I)) {
-    TrackUse = true;
-    return 0;
+    Alignment = AlignAA.getKnownAlign();
   }
 
+  const Value *UseV = U->get();
   if (auto *SI = dyn_cast<StoreInst>(I))
-    return SI->getAlignment();
+    Alignment = SI->getAlignment();
   else if (auto *LI = dyn_cast<LoadInst>(I))
-    return LI->getAlignment();
+    Alignment = LI->getAlignment();
 
+  if (Alignment <= 1)
     return 0;
+
+  auto &DL = A.getDataLayout();
+  int64_t Offset;
+
+  if (const Value *Base = GetPointerBaseWithConstantOffset(UseV, Offset, DL)) {
+    if (Base == &AssociatedValue) {
+      // BasePointerAddr + Offset = Alignment * Q for some integer Q.
+      // So we can say that the maximum power of two which is a divisor of
+      // gcd(Offset, Alignment) is an alignment.
+
+      uint32_t gcd =
+          greatestCommonDivisor(uint32_t(abs((int32_t)Offset)), Alignment);
+      Alignment = llvm::PowerOf2Floor(gcd);
+    }
+  }
+
+  return Alignment;
 }
 struct AAAlignImpl : AAAlign {
   AAAlignImpl(const IRPosition &IRP) : AAAlign(IRP) {}
 
   /// See AbstractAttribute::initialize(...).
   void initialize(Attributor &A) override {
     SmallVector<Attribute, 4> Attrs;
     getAttrs({Attribute::Alignment}, Attrs);

llvm/test/Transforms/FunctionAttrs/align.ll

 
 
 ; ATTRIBUTOR: define i64 @test11(i32* nocapture nofree nonnull readonly align 8 dereferenceable(8) %p)
 define i64 @test11(i32* %p) {
   %p-cast = bitcast i32* %p to i64*
   %ret = load i64, i64* %p-cast, align 8
   ret i64 %ret
 }
+
+; TEST 12
+; Test for deduction using must-be-executed-context and GEP instruction 
+
+; FXIME: %p should have nonnull
+; ATTRIBUTOR: define i64 @test12-1(i32* nocapture nofree readonly align 16 %p)
+define i64 @test12-1(i32* align 4 %p) {
+  %p-cast = bitcast i32* %p to i64*
+  %arrayidx0 = getelementptr i64, i64* %p-cast, i64 1
+  %arrayidx1 = getelementptr i64, i64* %arrayidx0, i64 3
+  %ret = load i64, i64* %arrayidx1, align 16
+  ret i64 %ret
+}
+
+; FXIME: %p should have nonnull
+; ATTRIBUTOR: define i64 @test12-2(i32* nocapture nofree readonly align 16 %p)
+define i64 @test12-2(i32* align 4 %p) {
+  %p-cast = bitcast i32* %p to i64*
+  %arrayidx0 = getelementptr i64, i64* %p-cast, i64 0
+  %ret = load i64, i64* %arrayidx0, align 16
+  ret i64 %ret
+}
+
+; FXIME: %p should have nonnull
+; ATTRIBUTOR: define void @test12-3(i32* nocapture nofree writeonly align 16 %p)
+define void @test12-3(i32* align 4 %p) {
+  %p-cast = bitcast i32* %p to i64*
+  %arrayidx0 = getelementptr i64, i64* %p-cast, i64 1
+  %arrayidx1 = getelementptr i64, i64* %arrayidx0, i64 3
+  store i64 0, i64* %arrayidx1, align 16
+  ret void 
+}
+
+; FXIME: %p should have nonnull
+; ATTRIBUTOR: define void @test12-4(i32* nocapture nofree writeonly align 16 %p)
+define void @test12-4(i32* align 4 %p) {
+  %p-cast = bitcast i32* %p to i64*
+  %arrayidx0 = getelementptr i64, i64* %p-cast, i64 0
+  store i64 0, i64* %arrayidx0, align 16
+  ret void 
+}
+
+declare void @use(i64*) willreturn nounwind
+
+; ATTRIBUTOR: define void @test12-5(i32* align 16 %p)
+define void @test12-5(i32* align 4 %p) {
+  %p-cast = bitcast i32* %p to i64*
+  %arrayidx0 = getelementptr i64, i64* %p-cast, i64 1
+  %arrayidx1 = getelementptr i64, i64* %arrayidx0, i64 3
+  tail call void @use(i64* align 16 %arrayidx1)
+  ret void 
+}
+
+; ATTRIBUTOR: define void @test12-6(i32* align 16 %p)
+define void @test12-6(i32* align 4 %p) {
+  %p-cast = bitcast i32* %p to i64*
+  %arrayidx0 = getelementptr i64, i64* %p-cast, i64 0
+  tail call void @use(i64* align 16 %arrayidx0)
+  ret void 
+}
+
 attributes #0 = { nounwind uwtable noinline }
 attributes #1 = { uwtable noinline }

llvm/test/Transforms/FunctionAttrs/arg_nocapture.ll

 ; TEST "captured" only through return
 ;
 ; long *not_captured_but_returned_1(long *a) {
 ;   *(a+1) = 1;
 ;   return a + 1;
 ; }
 ;
 ; There should *not* be a no-capture attribute on %a
-; FIXME: %a should have align 8
-; CHECK: define nonnull align 8 dereferenceable(8) i64* @not_captured_but_returned_1(i64* nofree nonnull writeonly dereferenceable(16) "no-capture-maybe-returned" %a)
+; CHECK: define nonnull align 8 dereferenceable(8) i64* @not_captured_but_returned_1(i64* nofree nonnull writeonly align 8 dereferenceable(16) "no-capture-maybe-returned" %a)
 define i64* @not_captured_but_returned_1(i64* %a) #0 {
 entry:
   %add.ptr = getelementptr inbounds i64, i64* %a, i64 1
   store i64 1, i64* %add.ptr, align 8
   ret i64* %add.ptr
 }
 
 ; TEST calls to "captured" only through return functions

llvm/test/Transforms/FunctionAttrs/nocapture.ll

 ; FNATTR: define void @test_atomicrmw(i32* nocapture %p)
 ; ATTRIBUTOR: define void @test_atomicrmw(i32* nocapture nofree nonnull dereferenceable(4) %p)
 define void @test_atomicrmw(i32* %p) {
   atomicrmw add i32* %p, i32 1 seq_cst
   ret void
 }
 
 ; FNATTR: define void @test_volatile(i32* %x)
-; ATTRIBUTOR: define void @test_volatile(i32* nofree %x)
+; ATTRIBUTOR: define void @test_volatile(i32* nofree align 4 %x)
 define void @test_volatile(i32* %x) {
 entry:
   %gep = getelementptr i32, i32* %x, i64 1
   store volatile i32 0, i32* %gep, align 4
   ret void
 }
 
 ; EITHER: nocaptureLaunder(i8* nocapture %p)

llvm/test/Transforms/InferFunctionAttrs/dereferenceable.ll

; ATTRIBUTOR-LABEL: @PR21780(double* nocapture nofree nonnull readonly align 8 dereferenceable(32) %ptr)
   %vecinit3 = insertelement <4 x double> %vecinit2, double %t3, i32 3
   %shuffle = shufflevector <4 x double> %vecinit3, <4 x double> %vecinit3, <4 x i32> <i32 0, i32 0, i32 2, i32 2>
   ret <4 x double> %shuffle
 }
 
 
 define double @PR21780_only_access3_with_inbounds(double* %ptr) {
 ; CHECK-LABEL: @PR21780_only_access3_with_inbounds(double* %ptr)
-; FIXME: %ptr should have align 8
-; ATTRIBUTOR-LABEL: @PR21780_only_access3_with_inbounds(double* nocapture nofree nonnull readonly dereferenceable(32) %ptr)
+; ATTRIBUTOR-LABEL: @PR21780_only_access3_with_inbounds(double* nocapture nofree nonnull readonly align 8 dereferenceable(32) %ptr)
 
   %arrayidx3 = getelementptr inbounds double, double* %ptr, i64 3
   %t3 = load double, double* %arrayidx3, align 8
   ret double %t3
 }
 
 define double @PR21780_only_access3_without_inbounds(double* %ptr) {
 ; CHECK-LABEL: @PR21780_only_access3_without_inbounds(double* %ptr)
-; FIXME: %ptr should have align 8
-; ATTRIBUTOR-LABEL: @PR21780_only_access3_without_inbounds(double* nocapture nofree readonly %ptr)
+; ATTRIBUTOR-LABEL: @PR21780_only_access3_without_inbounds(double* nocapture nofree readonly align 8 %ptr)
   %arrayidx3 = getelementptr double, double* %ptr, i64 3
   %t3 = load double, double* %arrayidx3, align 8
   ret double %t3
 }
 
 define double @PR21780_without_inbounds(double* %ptr) {
 ; CHECK-LABEL: @PR21780_without_inbounds(double* %ptr)
 ; FIXME: this should be @PR21780_without_inbounds(double* nonnull dereferenceable(32) %ptr)