[LSR] Fix for pre-indexed generated constant offset

[stelios-arm]

Summary

This patch changed the isLegalUse check to ensure that
LSRInstance::GenerateConstantOffsetsImpl generates an
offset that results in a legal addressing mode and
formula. The check is changed to look similar to the
assert check used for illegal formulas.

Currently when building a bootstrap build with the following flags:

-DCMAKE_C_FLAGS="${CMAKE_C_FLAGS} -mllvm -lsr-preferred-addressing-mode=preindexed"  -DCMAKE_CXX_FLAGS="${CMAKE_C_FLAGS} -mllvm -lsr-preferred-addressing-mode=preindexed"

, it fails at compiling TargetLoweringBase.cpp because it generates an illegal formula.

This patch fixes this and allows to build a bootstrap build with the aforementioned flags.

[SjoerdMeijer]

I am afraid we need to add a test case for this because this doesn't seem to be covered by existing tests. So, I think you need to make a minimal reproducer of the input file that triggers the assertion failure.

[dmgreen]

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

3794–3795

This looks like it's already checking isLegalUse. Should it be without the -Offset?

[stelios-arm]

In D100383#2685704, @SjoerdMeijer wrote:

I am afraid we need to add a test case for this because this doesn't seem to be covered by existing tests. So, I think you need to make a minimal reproducer of the input file that triggers the assertion failure.

I will add one in the next revision. For the meantime, here is one.

[stelios-arm]

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

3794–3795

Yes that will do. I am not sure whether such change will result in any side effects. I will test it, and if there are none I will update it in the next revision accordingly.

[stelios-arm]

1. Added a test that triggers the assertion failure.
2. Changed the isLegalUse parameters in LSRInstance::GenerateConstantOffsetsImpl to look the same as the assertion used for illegal formulas.

[stelios-arm]

In this link you can see how it results in an error.

[SjoerdMeijer]

llvm/test/Transforms/LoopStrengthReduce/AArch64/pre-inc-offset-check.ll

7

Thanks for adding this, nice reproducer!

I think this tests could benefit from some comments explaining what exactly we are testing here. I.e., from the test name one might expect preindexed loads/store, but they don't appear in the codegen.

[SjoerdMeijer]

And forgot to add, and just double checking, this passes your bootstrap build and test again?

[stelios-arm]

In D100383#2688643, @SjoerdMeijer wrote:

And forgot to add, and just double checking, this passes your bootstrap build and test again?

Yes this compiles the bootstrap build and the test-suite too.

llvm/test/Transforms/LoopStrengthReduce/AArch64/pre-inc-offset-check.ll

7

I will add some in the next revision.

[stelios-arm]

1. Added comments to the new test.
2. Fixed the failing AMDGPU tests.

[SjoerdMeijer]

llvm/test/Transforms/LoopStrengthReduce/AMDGPU/atomics.ll

95

What happened to these atomics? I think this is crucial for these tests, and we still need to match them.
Same for the atomic reads/writes in tests above and also below here.

[stelios-arm]

Added back some of the atomic tests.

[stelios-arm]

llvm/test/Transforms/LoopStrengthReduce/AMDGPU/atomics.ll

95

Oh yes. They just changed a bit, I added them back.

[SjoerdMeijer]

Thanks, looks like a good bug fix to me.

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

 /// Helper function for LSRInstance::GenerateConstantOffsets.
 void LSRInstance::GenerateConstantOffsetsImpl(
     LSRUse &LU, unsigned LUIdx, const Formula &Base,
     const SmallVectorImpl<int64_t> &Worklist, size_t Idx, bool IsScaledReg) {
 
   auto GenerateOffset = [&](const SCEV *G, int64_t Offset) {
     Formula F = Base;
     F.BaseOffset = (uint64_t)Base.BaseOffset - Offset;
 
-    if (isLegalUse(TTI, LU.MinOffset - Offset, LU.MaxOffset - Offset, LU.Kind,
-                   LU.AccessTy, F)) {
+    if (isLegalUse(TTI, LU.MinOffset, LU.MaxOffset, LU.Kind, LU.AccessTy, F)) {
       // Add the offset to the base register.
       const SCEV *NewG = SE.getAddExpr(SE.getConstant(G->getType(), Offset), G);
       // If it cancelled out, drop the base register, otherwise update it.
       if (NewG->isZero()) {
         if (IsScaledReg) {
           F.Scale = 0;
           F.ScaledReg = nullptr;
         } else

llvm/test/CodeGen/AMDGPU/cf-loop-on-constant.ll

 ; RUN: llc -march=amdgcn -verify-machineinstrs < %s | FileCheck -check-prefix=GCN %s
 ; RUN: llc -march=amdgcn -verify-machineinstrs -O0 < %s
 
 ; GCN-LABEL: {{^}}test_loop:
-; GCN: s_and_b64 vcc, exec, -1
+; GCN: s_and_b64 s[0:1], exec, -1
 ; GCN: [[LABEL:BB[0-9]+_[0-9]+]]: ; %for.body{{$}}
 ; GCN: ds_read_b32
 ; GCN: ds_write_b32
 ; GCN: s_cbranch_vccnz [[LABEL]]
 ; GCN: s_endpgm
 define amdgpu_kernel void @test_loop(float addrspace(3)* %ptr, i32 %n) nounwind {
 entry:
   %cmp = icmp eq i32 %n, -1
for.body:
   store float %add, float addrspace(3)* %arrayidx, align 8
   %inc = add i32 %indvar, 1
   br i1 undef, label %for.body, label %for.exit
 }
 
 ; GCN-LABEL: {{^}}loop_arg_0:
 ; GCN: v_and_b32_e32 v{{[0-9]+}}, 1, v{{[0-9]+}}
 ; GCN: v_cmp_eq_u32{{[^,]*}}, 1,
+; GCN: s_add_i32 s2, s0, 0x80
 
 ; GCN: [[LOOPBB:BB[0-9]+_[0-9]+]]
-; GCN: s_add_i32 s{{[0-9]+}}, s{{[0-9]+}}, 0x80
-; GCN: s_add_i32 s{{[0-9]+}}, s{{[0-9]+}}, 4
-
+; GCN: _add_i32_e32 v0, vcc, 4, v0
 ; GCN: s_cbranch_{{vccz|vccnz}} [[LOOPBB]]
 ; GCN-NEXT: ; %bb.2
 ; GCN-NEXT: s_endpgm
 define amdgpu_kernel void @loop_arg_0(float addrspace(3)* %ptr, i32 %n) nounwind {
 entry:
   %cond = load volatile i1, i1 addrspace(3)* null
   br label %for.body
 

llvm/test/Transforms/LoopStrengthReduce/AArch64/pre-inc-offset-check.ll

+; RUN: llc -mtriple=aarch64-none-eabi -lsr-preferred-addressing-mode=preindexed %s -o - | FileCheck %s
+
+; In LSR for constant offsets and steps, we can generate pre-inc
+; accesses by having the offset equal the step and generate a reuse
+; formula. However, there are cases where the step, results in an
+; illegal addressing mode.
+
+; In this test, we set the preferred addressing mode to be preindexed,
+; in order to test a scenario where the step results in an illegal
+; addressing mode and because of that it should not generate a reuse formula.
+
+; This test was created in order to reproduce a bug that was observed
+; when building a bootstrap build on an AArch64 machine, where the
+; preferred addresing mode is preindexed.
+
+
+%"Type" = type <{[166 x [338 x i8]]}>
+define void @test_lsr_pre_inc_offset_check(%"Type"* %p) {
+; CHECK-LABEL: test_lsr_pre_inc_offset_check:
+; CHECK:       // %bb.0: // %entry
+; CHECK-NEXT:    add x8, x0, #340 // =340
+; CHECK-NEXT:    mov w9, #165
+; CHECK-NEXT:    mov w10, #2
+; CHECK-NEXT:  .LBB0_1: // %main
+; CHECK-NEXT:    // =>This Inner Loop Header: Depth=1
+; CHECK-NEXT:    stur wzr, [x8, #-1]
+; CHECK-NEXT:    strb w10, [x8]
+; CHECK-NEXT:    subs x9, x9, #1 // =1
+; CHECK-NEXT:    add x8, x8, #338 // =338
+; CHECK-NEXT:    b.ne .LBB0_1
+; CHECK-NEXT:  // %bb.2: // %exit
+; CHECK-NEXT:    ret
+entry:
+  br label %main
+exit:
+  ret void
+if.then:
+  %arrayidx.i = getelementptr inbounds %"Type", %"Type"* %p, i64 0, i32 0, i64 %indvars, i64 1
+  %0 = bitcast i8* %arrayidx.i to i32*
+  store i32 0, i32* %0, align 1
+  br label %if.end
+if.end:
+  %arrayidx.p = getelementptr inbounds %"Type", %"Type"* %p, i64 0, i32 0, i64 %indvars, i64 2
+  store i8 2, i8* %arrayidx.p, align 1
+  %indvars.iv.next = add nuw nsw i64 %indvars, 1
+  %add.i = add nuw i8 %begin, 1
+  %cmp.i.not = icmp eq i64 %indvars.iv.next, 166
+  br i1 %cmp.i.not, label %exit, label %main
+main:
+  %begin = phi i8 [ 1, %entry ], [ %add.i, %if.end ]
+  %indvars = phi i64 [ 1, %entry ], [ %indvars.iv.next, %if.end ]
+  br label %if.then
+}

llvm/test/Transforms/LoopStrengthReduce/AMDGPU/atomics.ll

 ; RUN: opt -S -mtriple=amdgcn-- -mcpu=bonaire -loop-reduce < %s | FileCheck -check-prefix=OPT %s
 
 target datalayout = "e-p:64:64-p1:64:64-p2:32:32-p3:32:32-p4:64:64-p5:32:32-p6:32:32-i64:64-v16:16-v24:32-v32:32-v48:64-v96:128-v192:256-v256:256-v512:512-v1024:1024-v2048:2048-n32:64-S32-A5"
 
 ; Make sure the pointer / address space of AtomicRMW is considered
 
 ; OPT-LABEL: @test_local_atomicrmw_addressing_loop_uniform_index_max_offset_i32(
 
-; OPT-NOT: getelementptr
-
+; OPT: .lr.ph.preheader:
+; OPT: %scevgep2 = getelementptr i32, i32 addrspace(3)*  %arg1, i32 16383
+; OPT: br label %.lr.ph
 ; OPT: .lr.ph:
-; OPT: %lsr.iv2 = phi i32 addrspace(3)* [ %scevgep3, %.lr.ph ], [ %arg1, %.lr.ph.preheader ]
-; OPT: %lsr.iv1 = phi i32 addrspace(3)* [ %scevgep, %.lr.ph ], [ %arg0, %.lr.ph.preheader ]
-; OPT: %lsr.iv = phi i32 [ %lsr.iv.next, %.lr.ph ], [ %n, %.lr.ph.preheader ]
-; OPT: %scevgep4 = getelementptr i32, i32 addrspace(3)* %lsr.iv2, i32 16383
-; OPT: %tmp4 = atomicrmw add i32 addrspace(3)* %scevgep4, i32 undef seq_cst
-; OPT: %tmp7 = atomicrmw add i32 addrspace(3)* %lsr.iv1, i32 undef seq_cst
-; OPT: %0 = atomicrmw add i32 addrspace(3)* %lsr.iv1, i32 %tmp8 seq_cst
+; OPT: %lsr.iv3 = phi i32 addrspace(3)* [ %scevgep4, %.lr.ph ], [ %scevgep2, %.lr.ph.preheader ]
+; OPT: %scevgep4 = getelementptr i32, i32 addrspace(3)* %lsr.iv3, i32 1
 ; OPT: br i1 %exitcond
 define amdgpu_kernel void @test_local_atomicrmw_addressing_loop_uniform_index_max_offset_i32(i32 addrspace(3)* noalias nocapture %arg0, i32 addrspace(3)* noalias nocapture readonly %arg1, i32 %n) #0 {
 bb:
   %tmp = icmp sgt i32 %n, 0
   br i1 %tmp, label %.lr.ph.preheader, label %._crit_edge
 
 .lr.ph.preheader:                                 ; preds = %bb
   br label %.lr.ph
.lr.ph:                                           ; preds = %.lr.ph, %.lr.ph.preheader
   %tmp8 = add nsw i32 %tmp7, %tmp4
   atomicrmw add i32 addrspace(3)* %tmp6, i32 %tmp8 seq_cst
   %indvars.iv.next = add nuw nsw i32 %indvars.iv, 1
   %exitcond = icmp eq i32 %indvars.iv.next, %n
   br i1 %exitcond, label %._crit_edge.loopexit, label %.lr.ph
 }
 
 ; OPT-LABEL: test_local_cmpxchg_addressing_loop_uniform_index_max_offset_i32(
-; OPT-NOT: getelementptr
 
+; OPT: .lr.ph.preheader:
+; OPT: %scevgep2 = getelementptr i32, i32 addrspace(3)*  %arg1, i32 16383
+; OPT: br label %.lr.ph
 ; OPT: .lr.ph:
-; OPT: %lsr.iv2 = phi i32 addrspace(3)* [ %scevgep3, %.lr.ph ], [ %arg1, %.lr.ph.preheader ]
-; OPT: %lsr.iv1 = phi i32 addrspace(3)* [ %scevgep, %.lr.ph ], [ %arg0, %.lr.ph.preheader ]
-; OPT: %lsr.iv = phi i32 [ %lsr.iv.next, %.lr.ph ], [ %n, %.lr.ph.preheader ]
-; OPT: %scevgep4 = getelementptr i32, i32 addrspace(3)* %lsr.iv2, i32 16383
-; OPT: %tmp4 = cmpxchg i32 addrspace(3)* %scevgep4, i32 undef, i32 undef seq_cst monotonic
+; OPT: %lsr.iv3 = phi i32 addrspace(3)* [ %scevgep4, %.lr.ph ], [ %scevgep2, %.lr.ph.preheader ]
+; OPT: %scevgep4 = getelementptr i32, i32 addrspace(3)* %lsr.iv3, i32 1
+
 define amdgpu_kernel void @test_local_cmpxchg_addressing_loop_uniform_index_max_offset_i32(i32 addrspace(3)* noalias nocapture %arg0, i32 addrspace(3)* noalias nocapture readonly %arg1, i32 %n) #0 {
 bb:
   %tmp = icmp sgt i32 %n, 0
   br i1 %tmp, label %.lr.ph.preheader, label %._crit_edge
 
 .lr.ph.preheader:                                 ; preds = %bb
   br label %.lr.ph
 
.lr.ph:                                           ; preds = %.lr.ph, %.lr.ph.preheader
   %tmp8 = add nsw i32 %tmp7.0, %tmp4.0
   atomicrmw add i32 addrspace(3)* %tmp6, i32 %tmp8 seq_cst
   %indvars.iv.next = add nuw nsw i32 %indvars.iv, 1
   %exitcond = icmp eq i32 %indvars.iv.next, %n
   br i1 %exitcond, label %._crit_edge.loopexit, label %.lr.ph
 }
 
 ; OPT-LABEL: @test_local_atomicinc_addressing_loop_uniform_index_max_offset_i32(
-; OPT-NOT: getelementptr
 
+; OPT: .lr.ph.preheader:
+; OPT: %scevgep2 = getelementptr i32, i32 addrspace(3)*  %arg1, i32 16383
+; OPT: br label %.lr.ph
 ; OPT: .lr.ph:
-; OPT: %lsr.iv2 = phi i32 addrspace(3)* [ %scevgep3, %.lr.ph ], [ %arg1, %.lr.ph.preheader ]
-; OPT: %lsr.iv1 = phi i32 addrspace(3)* [ %scevgep, %.lr.ph ], [ %arg0, %.lr.ph.preheader ]
-; OPT: %lsr.iv = phi i32 [ %lsr.iv.next, %.lr.ph ], [ %n, %.lr.ph.preheader ]
-; OPT: %scevgep4 = getelementptr i32, i32 addrspace(3)* %lsr.iv2, i32 16383
-; OPT: %tmp4 = call i32 @llvm.amdgcn.atomic.inc.i32.p3i32(i32 addrspace(3)* %scevgep4, i32 undef, i32 0, i32 0, i1 false)
-; OPT: %tmp7 = call i32 @llvm.amdgcn.atomic.inc.i32.p3i32(i32 addrspace(3)* %lsr.iv1, i32 undef, i32 0, i32 0, i1 false)
+; OPT: %lsr.iv3 = phi i32 addrspace(3)* [ %scevgep4, %.lr.ph ], [ %scevgep2, %.lr.ph.preheader ]
+; OPT: %scevgep4 = getelementptr i32, i32 addrspace(3)* %lsr.iv3, i32 1
 define amdgpu_kernel void @test_local_atomicinc_addressing_loop_uniform_index_max_offset_i32(i32 addrspace(3)* noalias nocapture %arg0, i32 addrspace(3)* noalias nocapture readonly %arg1, i32 %n) #0 {
 bb:
   %tmp = icmp sgt i32 %n, 0
   br i1 %tmp, label %.lr.ph.preheader, label %._crit_edge
 
 .lr.ph.preheader:                                 ; preds = %bb
   br label %.lr.ph
 
.lr.ph:                                           ; preds = %.lr.ph, %.lr.ph.preheader
   %tmp8 = add nsw i32 %tmp7, %tmp4
   atomicrmw add i32 addrspace(3)* %tmp6, i32 %tmp8 seq_cst
   %indvars.iv.next = add nuw nsw i32 %indvars.iv, 1
   %exitcond = icmp eq i32 %indvars.iv.next, %n
   br i1 %exitcond, label %._crit_edge.loopexit, label %.lr.ph
 }
 
 ; OPT-LABEL: @test_local_atomicdec_addressing_loop_uniform_index_max_offset_i32(
-; OPT-NOT: getelementptr
-
+; OPT: .lr.ph.preheader:
+; OPT: %scevgep2 = getelementptr i32, i32 addrspace(3)*  %arg1, i32 16383
+; OPT: br label %.lr.ph
 ; OPT: .lr.ph:
-; OPT: %lsr.iv2 = phi i32 addrspace(3)* [ %scevgep3, %.lr.ph ], [ %arg1, %.lr.ph.preheader ]
-; OPT: %lsr.iv1 = phi i32 addrspace(3)* [ %scevgep, %.lr.ph ], [ %arg0, %.lr.ph.preheader ]
-; OPT: %lsr.iv = phi i32 [ %lsr.iv.next, %.lr.ph ], [ %n, %.lr.ph.preheader ]
-; OPT: %scevgep4 = getelementptr i32, i32 addrspace(3)* %lsr.iv2, i32 16383
-; OPT: %tmp4 = call i32 @llvm.amdgcn.atomic.dec.i32.p3i32(i32 addrspace(3)* %scevgep4, i32 undef, i32 0, i32 0, i1 false)
-; OPT: %tmp7 = call i32 @llvm.amdgcn.atomic.dec.i32.p3i32(i32 addrspace(3)* %lsr.iv1, i32 undef, i32 0, i32 0, i1 false)
+; OPT: %lsr.iv3 = phi i32 addrspace(3)* [ %scevgep4, %.lr.ph ], [ %scevgep2, %.lr.ph.preheader ]
+; OPT: %scevgep4 = getelementptr i32, i32 addrspace(3)* %lsr.iv3, i32 1
 define amdgpu_kernel void @test_local_atomicdec_addressing_loop_uniform_index_max_offset_i32(i32 addrspace(3)* noalias nocapture %arg0, i32 addrspace(3)* noalias nocapture readonly %arg1, i32 %n) #0 {
 bb:
   %tmp = icmp sgt i32 %n, 0
   br i1 %tmp, label %.lr.ph.preheader, label %._crit_edge
 
 .lr.ph.preheader:                                 ; preds = %bb
   br label %.lr.ph
 

llvm/test/Transforms/LoopStrengthReduce/AMDGPU/different-addrspace-addressing-mode-loops.ll

 ; RUN: opt -S -mtriple=amdgcn-- -mcpu=bonaire -loop-reduce < %s | FileCheck -check-prefix=OPT %s
 
 ; Test that loops with different maximum offsets for different address
 ; spaces are correctly handled.
 
 target datalayout = "e-p:64:64-p1:64:64-p2:32:32-p3:32:32-p4:64:64-p5:32:32-p6:32:32-i64:64-v16:16-v24:32-v32:32-v48:64-v96:128-v192:256-v256:256-v512:512-v1024:1024-v2048:2048-n32:64-S32-A5"
 
 ; OPT-LABEL: @test_global_addressing_loop_uniform_index_max_offset_i32(
+; OPT: .lr.ph.preheader:
+; OPT: %scevgep2 = getelementptr i8, i8 addrspace(1)* %arg1, i64 4095
+; OPT: br label %.lr.ph
 ; OPT: {{^}}.lr.ph:
-; OPT: %lsr.iv2 = phi i8 addrspace(1)* [ %scevgep3, %.lr.ph ], [ %arg1, %.lr.ph.preheader ]
-; OPT: %scevgep4 = getelementptr i8, i8 addrspace(1)* %lsr.iv2, i64 4095
-; OPT: load i8, i8 addrspace(1)* %scevgep4, align 1
+; OPT: %lsr.iv3 = phi i8 addrspace(1)* [ %scevgep4, %.lr.ph ], [ %scevgep2, %.lr.ph.preheader ]
+; OPT: %scevgep4 = getelementptr i8, i8 addrspace(1)* %lsr.iv3, i64 1
 define amdgpu_kernel void @test_global_addressing_loop_uniform_index_max_offset_i32(i32 addrspace(1)* noalias nocapture %arg0, i8 addrspace(1)* noalias nocapture readonly %arg1, i32 %n) #0 {
 bb:
   %tmp = icmp sgt i32 %n, 0
   br i1 %tmp, label %.lr.ph.preheader, label %._crit_edge
 
 .lr.ph.preheader:                                 ; preds = %bb
   br label %.lr.ph
 
.lr.ph:                                           ; preds = %.lr.ph, %.lr.ph.preheader
   store i32 %tmp7, i32 addrspace(1)* %tmp5, align 4
   %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
   %lftr.wideiv = trunc i64 %indvars.iv.next to i32
   %exitcond = icmp eq i32 %lftr.wideiv, %n
   br i1 %exitcond, label %._crit_edge.loopexit, label %.lr.ph
 }
 
 ; OPT-LABEL: @test_local_addressing_loop_uniform_index_max_offset_i32(
+; OPT: .lr.ph.preheader:
+; OPT: %scevgep2 = getelementptr i8, i8 addrspace(3)* %arg1, i32 65535
+; OPT: br label %.lr.ph
 ; OPT: {{^}}.lr.ph
-; OPT: %lsr.iv2 = phi i8 addrspace(3)* [ %scevgep3, %.lr.ph ], [ %arg1, %.lr.ph.preheader ]
-; OPT: %scevgep4 = getelementptr i8, i8 addrspace(3)* %lsr.iv2, i32 65535
-; OPT: %tmp4 = load i8, i8 addrspace(3)* %scevgep4, align 1
+; OPT: %lsr.iv3 = phi i8 addrspace(3)* [ %scevgep4, %.lr.ph ], [ %scevgep2, %.lr.ph.preheader ]
+; OPT: %scevgep4 = getelementptr i8, i8 addrspace(3)* %lsr.iv3, i32 1
 define amdgpu_kernel void @test_local_addressing_loop_uniform_index_max_offset_i32(i32 addrspace(1)* noalias nocapture %arg0, i8 addrspace(3)* noalias nocapture readonly %arg1, i32 %n) #0 {
 bb:
   %tmp = icmp sgt i32 %n, 0
   br i1 %tmp, label %.lr.ph.preheader, label %._crit_edge
 
 .lr.ph.preheader:                                 ; preds = %bb
   br label %.lr.ph