[LSR] Don't try and create post-inc expressions on non-rotated loops

[jmolloy]

Summary

If a loop is not rotated (for example when optimizing for size), the latch is not the backedge. If we promote an expression to post-inc form, we not only increase register pressure and add a COPY for that IV expression but for all IVs!

Motivating testcase:

void f(float *a, float *b, float *c, int n) {
  while (n-- > 0)
    *c++ = *a++ + *b++;
}

It's imperative that the pointer increments be located in the latch block and not the header block; if not, we cannot use post-increment loads and stores and we have to keep both the post-inc and pre-inc values around until the end of the latch which bloats register usage.

Brendan, this change makes the Hexagon test "hwloop-crit-edge.ll" fail. To me it looks like the HexagonLoopOptimizer is perhaps a little too rigid in what it expects? I think the change in output of LSR is good, as it reduces register pressure and should be producing one less COPY. Could you please take a look and see what you think?

[bcahoon]

Hi James - I think your patch is reasonable. You're correct about our hardware loop pass. We would need to improve it to catch this case. I'm not sure how easy/hard it is to do that without a little more investigation. Until we do that, I'm fine with either xfailing or removing the test (or some other suggestion?).

[junbuml]

test/Transforms/LoopStrengthReduce/post-inc-optsize.ll

7

For me the comment is little confusing. I think the post-inc transformation was avoided only in "%n.addr.0" so that IV increments stay in latch block instead of being moved up before icmp.

12

Don't you think you also need to check that icmp is not in the post-inc form, so pre-inc form in while.cond?

[jmolloy]

Thanks Jun and Brendon.

I've XFAILed the test and I've updated the comments and checks according to Jun's review.

[jmolloy]

Adding another slew of reviewers.

[junbuml]

lib/Transforms/Scalar/LoopStrengthReduce.cpp

2084

Did you want to specifically handle this for a loop with only one exiting block? Why not doing this within the if statement below in line 2130 ?

test/Transforms/LoopStrengthReduce/post-inc-optsize.ll

7

I think this test checks if IV increments (incdec.ptr, incdec.ptr1, and incdec.ptr2) are not moved to the exiting block(while.cond) because this patch avoid transforming %cmp to the post-inc form that update IVIncInsertPos to %cmp.

[jmolloy]

Hi Jun,

Thanks very much for the review! I've addressed your comments, I think.

With regards multiple exiting blocks, you're right. I hadn't considered that.

[junbuml]

This looks good to me, but I want to let Andrew take the final review on it.

[jmolloy]

Hi Jun,

Thanks! Andy hasn't been very active recently - is there anyone else who you feel could give the final review on this?

Cheers,

James

[qcolombet]

Hi James,

The patch looks sensible, but why do we have to XFAIL the hexagon test?

BTW, I like the effort you put in the comments to explain the heuristic!

Couple of comments inlined.

Cheers,
-Quentin

test/CodeGen/Hexagon/hwloop-crit-edge.ll

2

That does not seem right.

test/Transforms/LoopStrengthReduce/post-inc-optsize.ll

2

Although you have check lines, you do not have a call to FileCheck :).

33

opt -instnamer first, please.

[jmolloy]

Hi Quentin,

Thanks for finding the test problems! With regards the XFAIL, it's due to a deficiency in Hexagon's hardware loops pass. I asked a Hexagon dev earlier up the comments list on this patch about it and he said:

Hi James - I think your patch is reasonable. You're correct about our hardware loop pass. We would need to improve it to catch this case. I'm not sure how easy/hard it is to do that without a little more investigation. Until we do that, I'm fine with either xfailing or removing the test (or some other suggestion?).

Cheers,

James

[jmolloy]

Ping! Quentin, are you happy with the rationale for XFAILing the test?

[qcolombet]

Hi James,

Thanks for your patience.

LGTM.

Cheers,
-Quentin

[jmolloy]

Thanks! r278658

lib/Transforms/Scalar/LoopStrengthReduce.cpp

ICmpInst *LSRInstance::OptimizeMax(ICmpInst *Cond, IVStrideUse* &CondUse) {
   return NewCond;
 }
 
 /// Change loop terminating condition to use the postinc iv when possible.
 void
 LSRInstance::OptimizeLoopTermCond() {
   SmallPtrSet<Instruction *, 4> PostIncs;
 
+  // We need a different set of heuristics for rotated and non-rotated loops.
+  // If a loop is rotated then the latch is also the backedge, so inserting
+  // post-inc expressions just before the latch is ideal. To reduce live ranges
+  // it also makes sense to rewrite terminating conditions to use post-inc
+  // expressions.
+  //
+  // If the loop is not rotated then the latch is not a backedge; the latch
+  // check is done in the loop head. Adding post-inc expressions before the
+  // latch will cause overlapping live-ranges of pre-inc and post-inc expressions
+  // in the loop body. In this case we do *not* want to use post-inc expressions
+  // in the latch check, and we want to insert post-inc expressions before
+  // the backedge.
   BasicBlock *LatchBlock = L->getLoopLatch();
   SmallVector<BasicBlock*, 8> ExitingBlocks;
   L->getExitingBlocks(ExitingBlocks);
+  if (llvm::all_of(ExitingBlocks, [&LatchBlock](const BasicBlock *BB) {
+        return LatchBlock != BB;
+      })) {
+    // The backedge doesn't exit the loop; treat this as a head-tested loop.
+    IVIncInsertPos = LatchBlock->getTerminator();
+    return;
+  }
 
+  // Otherwise treat this as a rotated loop.
   for (BasicBlock *ExitingBlock : ExitingBlocks) {
 
     // Get the terminating condition for the loop if possible.  If we
     // can, we want to change it to use a post-incremented version of its
     // induction variable, to allow coalescing the live ranges for the IV into
     // one register value.
 
     BranchInst *TermBr = dyn_cast<BranchInst>(ExitingBlock->getTerminator());

test/CodeGen/ARM/2011-03-23-PeepholeBug.ll

entry:
   br label %bb2
 
 bb:                                               ; preds = %bb2
   %0 = tail call i32 @rand() nounwind
   %1 = icmp eq i32 %0, 50
   br i1 %1, label %bb3, label %bb1
 
 bb1:                                              ; preds = %bb
+; CHECK: bb1
+; CHECK: subs [[REG:r[0-9]+]], #1
   %tmp = tail call i32 @puts() nounwind
   %indvar.next = add i32 %indvar, 1
   br label %bb2
 
 bb2:                                              ; preds = %bb1, %entry
 ; CHECK: bb2
-; CHECK: subs [[REG:r[0-9]+]], #1
 ; CHECK: cmp [[REG]], #0
 ; CHECK: ble
   %indvar = phi i32 [ %indvar.next, %bb1 ], [ 0, %entry ]
   %tries.0 = sub i32 2147483647, %indvar
   %tmp1 = icmp sgt i32 %tries.0, 0
   br i1 %tmp1, label %bb, label %bb3
 
 bb3:                                              ; preds = %bb2, %bb
   ret i32 0
 }
 
 declare i32 @rand()
 
 declare i32 @puts() nounwind

test/CodeGen/Hexagon/hwloop-crit-edge.ll

 ; RUN: llc -O3 -march=hexagon -mcpu=hexagonv5 < %s | FileCheck %s
+; XFAIL: *
 ;
 ; Generate hardware loop when loop 'latch' block is different
 ; from the loop 'exiting' block.
 
 ; CHECK: loop0(.LBB{{.}}_{{.}}, r{{[0-9]+}})
 ; CHECK: endloop0
 
 define void @test(i32* nocapture %pFL, i16 signext %nBS, i16* nocapture readonly %pHT) #0 {

test/CodeGen/Hexagon/hwloop-loop1.ll

 ; RUN: llc -march=hexagon -mcpu=hexagonv5 < %s | FileCheck %s
 ;
 ; Generate loop1 instruction for double loop sequence.
 
-; CHECK: loop0(.LBB{{.}}_{{.}}, #100)
-; CHECK: endloop0
 ; CHECK: loop1(.LBB{{.}}_{{.}}, #100)
 ; CHECK: loop0(.LBB{{.}}_{{.}}, #100)
 ; CHECK: endloop0
 ; CHECK: endloop1
 
 define i32 @main() #0 {
 entry:
   %array = alloca [100 x i32], align 8

test/CodeGen/X86/lsr-loop-exit-cond.ll

 ; RUN: llc -mtriple=x86_64-darwin -mcpu=generic < %s | FileCheck %s
 ; RUN: llc -mtriple=x86_64-darwin -mcpu=atom < %s | FileCheck -check-prefix=ATOM %s
 
 ; CHECK-LABEL: t:
 ; CHECK: movl (%r9,%rax,4), %e{{..}}
-; CHECK-NEXT: decq
+; CHECK-NEXT: testq
 ; CHECK-NEXT: jne
 
 ; ATOM-LABEL: t:
 ; ATOM: movl (%r9,%r{{.+}},4), %e{{..}}
-; ATOM-NEXT: decq
+; ATOM-NEXT: testq
 ; ATOM-NEXT: jne
 
 @Te0 = external global [256 x i32]    ; <[256 x i32]*> [#uses=5]
 @Te1 = external global [256 x i32]    ; <[256 x i32]*> [#uses=4]
 @Te3 = external global [256 x i32]    ; <[256 x i32]*> [#uses=2]
 
 define void @t(i8* nocapture %in, i8* nocapture %out, i32* nocapture %rk, i32 %r) nounwind {
 entry:

test/Transforms/LoopStrengthReduce/post-inc-optsize.ll

+; RUN: opt < %s -loop-reduce -S | FileCheck %s
+
+target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-a:0:32-n32-S64"
+target triple = "thumbv7m-arm-none-eabi"
+
+; Check that the IV updates (incdec.ptr{,1,2}) are kept in the latch block
+; and not moved to the header/exiting block. Inserting them in the header
+; doubles register pressure and adds moves.
+
+; CHECK-LABEL: @f
+; CHECK: while.cond:
+; CHECK: icmp sgt i32 %n.addr.0, 0
+; CHECK: while.body:
+; CHECK: incdec.ptr =
+; CHECK: incdec.ptr1 =
+; CHECK: incdec.ptr2 =
+; CHECK: dec = 
+define void @f(float* nocapture readonly %a, float* nocapture readonly %b, float* nocapture %c, i32 %n) {
+entry:
+  br label %while.cond
+
+while.cond:                                       ; preds = %while.body, %entry
+  %a.addr.0 = phi float* [ %a, %entry ], [ %incdec.ptr, %while.body ]
+  %b.addr.0 = phi float* [ %b, %entry ], [ %incdec.ptr1, %while.body ]
+  %c.addr.0 = phi float* [ %c, %entry ], [ %incdec.ptr2, %while.body ]
+  %n.addr.0 = phi i32 [ %n, %entry ], [ %dec, %while.body ]
+  %cmp = icmp sgt i32 %n.addr.0, 0
+  br i1 %cmp, label %while.body, label %while.end
+
+while.body:                                       ; preds = %while.cond
+  %incdec.ptr = getelementptr inbounds float, float* %a.addr.0, i32 1
+  %tmp = load float, float* %a.addr.0, align 4
+  %incdec.ptr1 = getelementptr inbounds float, float* %b.addr.0, i32 1
+  %tmp1 = load float, float* %b.addr.0, align 4
+  %add = fadd float %tmp, %tmp1
+  %incdec.ptr2 = getelementptr inbounds float, float* %c.addr.0, i32 1
+  store float %add, float* %c.addr.0, align 4
+  %dec = add nsw i32 %n.addr.0, -1
+  br label %while.cond
+
+while.end:                                        ; preds = %while.cond
+  ret void
+}