Avoid skipping instructions in IndVarSimplify::sinkUnusedInvariants

[rmorylev]

Summary

Fix a bug when every second instruction wasn't sinked because the iterator was incremented over it

[rmorylev]

lib/Transforms/Scalar/IndVarSimplify.cpp

2290

At the end of the loop I is pointing at the next instruction to consider, so this decrement will skip it

test/Transforms/IndVarSimplify/sink-all.ll

23

Verify that all 3 instructions from preheader are sinked

[sanjoy]

lib/Transforms/Scalar/IndVarSimplify.cpp

2344

I'd instead do this change as:

• Remove the isa<DbgInfoIntrinsic>(I) related complexity here (i.e. lines 2344-2354, and the if (Done) break; bits), since we check for DbgInfoIntrinsic and continue over them anyway.
• Do I++ right after Instruction *ToMove = &*I;.

This would make the entry invariant into the loop "I points to one past the instruction we want to sink", and the I-- in the beginning of the loop body would do the right thing.

[rmorylev]

lib/Transforms/Scalar/IndVarSimplify.cpp

2344

Agree. I was just trying to make the patch simple.

lib/Transforms/Scalar/IndVarSimplify.cpp

void IndVarSimplify::sinkUnusedInvariants(Loop *L) {
   if (!ExitBlock) return;
 
   BasicBlock *Preheader = L->getLoopPreheader();
   if (!Preheader) return;
 
   BasicBlock::iterator InsertPt = ExitBlock->getFirstInsertionPt();
   BasicBlock::iterator I(Preheader->getTerminator());
   while (I != Preheader->begin()) {
     --I;
     // New instructions were inserted at the end of the preheader.
     if (isa<PHINode>(I))
       break;
 
     // Don't move instructions which might have side effects, since the side
     // effects need to complete before instructions inside the loop.  Also don't
     // move instructions which might read memory, since the loop may modify
     // memory. Note that it's okay if the instruction might have undefined
while (I != Preheader->begin()) {
     // If there is, the def must remain in the preheader.
     if (UsedInLoop)
       continue;
 
     // Otherwise, sink it to the exit block.
     Instruction *ToMove = &*I;
     bool Done = false;
 
     if (I != Preheader->begin()) {
       // Skip debug info intrinsics.
       do {
         --I;
       } while (isa<DbgInfoIntrinsic>(I) && I != Preheader->begin());
 
       if (isa<DbgInfoIntrinsic>(I) && I == Preheader->begin())
         Done = true;
     } else {
       Done = true;
     }
 
     ToMove->moveBefore(*ExitBlock, InsertPt);
     if (Done) break;
     InsertPt = ToMove->getIterator();
+    ++I; // Do not skip instructions
   }
 }
 
 //===----------------------------------------------------------------------===//
 //  IndVarSimplify driver. Manage several subpasses of IV simplification.
 //===----------------------------------------------------------------------===//
 
 bool IndVarSimplify::run(Loop *L) {

test/Transforms/IndVarSimplify/exit_value_test3.ll

 ; RUN: opt < %s -indvars -loop-deletion -S |FileCheck %s
 
 ; Check IndVarSimplify should replace exit value even if the expansion cost
 ; is high because the loop can be deleted after the exit value rewrite.
 ;
 ; CHECK-LABEL: @_Z3fooPKcjj(
+; CHECK: br label %[[LABEL:[a-zA-Z0-9_.]+]]
+; CHECK: [[LABEL]]:
 ; CHECK: udiv
-; CHECK: [[LABEL:^[a-zA-Z0-9_.]+]]:
 ; CHECK-NOT: br {{.*}} [[LABEL]]
 
 define i32 @_Z3fooPKcjj(i8* nocapture readnone %s, i32 %len, i32 %c) #0 {
 entry:
   br label %while.cond
 
 while.cond:                                       ; preds = %while.cond, %entry
   %klen.0 = phi i32 [ %len, %entry ], [ %sub, %while.cond ]
   %cmp = icmp ugt i32 %klen.0, 11
   %sub = add i32 %klen.0, -12
   br i1 %cmp, label %while.cond, label %while.end
 
 while.end:                                        ; preds = %while.cond
   %klen.0.lcssa = phi i32 [ %klen.0, %while.cond ]
   ret i32 %klen.0.lcssa
 }

test/Transforms/IndVarSimplify/loop_evaluate_1.ll

 }
 
 
 ; PR12377
 ; CHECK-LABEL: @test2
 ; CHECK: [[VAR1:%.+]] = add i32 %arg, -11
 ; CHECK: [[VAR2:%.+]] = lshr i32 [[VAR1]], 1
 ; CHECK: [[VAR3:%.+]] = add i32 [[VAR2]], 1
-; CHECK: [[VAR4:%.+]] = phi i32 [ 0, %bb ], [ [[VAR3]], %bb1.preheader ]
+; CHECK: [[VAR4:%.+]] = phi i32 [ 0, %bb ], [ [[VAR3]], %bb7.loopexit ]
 ; CHECK: ret i32 [[VAR4]]
 define i32 @test2(i32 %arg) {
 bb:
   %tmp = icmp ugt i32 %arg, 10
   br i1 %tmp, label %bb1, label %bb7
 
 bb1:                                              ; preds = %bb1, %bb
   %tmp2 = phi i32 [ %tmp5, %bb1 ], [ 0, %bb ]

test/Transforms/IndVarSimplify/sink-all.ll

+; RUN: opt < %s -indvars -S | FileCheck %s
+
+declare i1 @cond()
+
+define i32 @foo(i32 %x) nounwind {
+entry:
+    %a = mul i32 %x, 2
+    %b = mul i32 %x, 4
+    %c = mul i32 %x, 8
+  br label %for.body
+
+for.body:
+    %cmp = call i1 @cond()
+  br i1 %cmp, label %for.body, label %for.end
+
+for.end:
+    %d = add i32 %a, %b
+    %e = add i32 %c, %d
+  ret i32 %e
+}
+
+; CHECK: for.end:
+; CHECK: mul
+; CHECK: mul
+; CHECK: mul
+; CHECK: add
+; CHECK: add
+; CHECK: ret