[InstCombine] Don't push operation across loop phi

[nikic]

Summary

When pushing an operation across a phi node, we should avoid doing so across a loop backedge. This is generally non-profitable, because it does not reduce the number of times the operation is executed, and could lead to an infinite combine loop.

The code was already guarding against this, but using an insufficiently strong condition, which did not cover the case where the operation was originally outside the loop (in which case the transform moves the operation from outside the loop into the loop, which is particularly undesirable).

[spatel]

LGTM - thanks!

Note: I think we should still do the narrowing transform that I suggested in D123408, but that's independent of this fix. That narrowing commit ran into its own infinite loop due to a conflict matching constant expressions, but I can fix that.

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

for (unsigned i = 0; i != NumPHIValues; ++i) {
     NonConstBB = PN->getIncomingBlock(i);
 
     // If the InVal is an invoke at the end of the pred block, then we can't
     // insert a computation after it without breaking the edge.
     if (isa<InvokeInst>(InVal))
       if (cast<Instruction>(InVal)->getParent() == NonConstBB)
         return nullptr;
 
-    // If the incoming non-constant value is in I's block, we will remove one
-    // instruction, but insert another equivalent one, leading to infinite
-    // instcombine.
-    if (isPotentiallyReachable(I.getParent(), NonConstBB, nullptr, &DT, LI))
+    // If the incoming non-constant value is reachable from the phis block,
+    // we'll push the operation across a loop backedge. This could result in
+    // an infinite combine loop, and is generally non-profitable (especially
+    // if the operation was originally outside the loop).
+    if (isPotentiallyReachable(PN->getParent(), NonConstBB, nullptr, &DT, LI))
       return nullptr;
   }
 
   // If there is exactly one non-constant value, we can insert a copy of the
   // operation in that block.  However, if this is a critical edge, we would be
   // inserting the computation on some other paths (e.g. inside a loop).  Only
   // do this if the pred block is unconditionally branching into the phi block.
   // Also, make sure that the pred block is not dead code.

llvm/test/Transforms/InstCombine/cast_phi.ll

 }
 
 define i8 @trunc_in_loop_exit_block() {
 ; CHECK-LABEL: @trunc_in_loop_exit_block(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP_LATCH:%.*]] ]
-; CHECK-NEXT:    [[PHI:%.*]] = phi i8 [ 1, [[ENTRY]] ], [ [[PHI_CAST:%.*]], [[LOOP_LATCH]] ]
+; CHECK-NEXT:    [[PHI:%.*]] = phi i32 [ 1, [[ENTRY]] ], [ [[IV_NEXT]], [[LOOP_LATCH]] ]
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i32 [[IV]], 100
 ; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP_LATCH]], label [[EXIT:%.*]]
 ; CHECK:       loop.latch:
 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
-; CHECK-NEXT:    [[PHI_CAST]] = trunc i32 [[IV_NEXT]] to i8
 ; CHECK-NEXT:    br label [[LOOP]]
 ; CHECK:       exit:
-; CHECK-NEXT:    ret i8 [[PHI]]
+; CHECK-NEXT:    [[TRUNC:%.*]] = trunc i32 [[PHI]] to i8
+; CHECK-NEXT:    ret i8 [[TRUNC]]
 ;
 entry:
   br label %loop
 
 loop:
   %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop.latch ]
   %phi = phi i32 [ 1, %entry ], [ %iv.next, %loop.latch ]
   %cmp = icmp ult i32 %iv, 100
   br i1 %cmp, label %loop.latch, label %exit
 
 loop.latch:
   %iv.next = add i32 %iv, 1
   br label %loop
 
 exit:
   %trunc = trunc i32 %phi to i8
   ret i8 %trunc
 }
 
 define i32 @zext_in_loop_and_exit_block(i8 %step, i32 %end) {
 ; CHECK-LABEL: @zext_in_loop_and_exit_block(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
-; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[PHI_CAST:%.*]], [[LOOP_LATCH:%.*]] ]
-; CHECK-NEXT:    [[CMP_NOT:%.*]] = icmp eq i32 [[IV]], [[END:%.*]]
+; CHECK-NEXT:    [[IV:%.*]] = phi i8 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP_LATCH:%.*]] ]
+; CHECK-NEXT:    [[IV_EXT:%.*]] = zext i8 [[IV]] to i32
+; CHECK-NEXT:    [[CMP_NOT:%.*]] = icmp eq i32 [[IV_EXT]], [[END:%.*]]
 ; CHECK-NEXT:    br i1 [[CMP_NOT]], label [[EXIT:%.*]], label [[LOOP_LATCH]]
 ; CHECK:       loop.latch:
-; CHECK-NEXT:    [[STEP_EXT:%.*]] = zext i8 [[STEP:%.*]] to i32
-; CHECK-NEXT:    [[IV_NEXT:%.*]] = add nuw nsw i32 [[IV]], [[STEP_EXT]]
-; CHECK-NEXT:    [[PHI_CAST]] = and i32 [[IV_NEXT]], 255
+; CHECK-NEXT:    [[IV_NEXT]] = add i8 [[IV]], [[STEP:%.*]]
 ; CHECK-NEXT:    br label [[LOOP]]
 ; CHECK:       exit:
-; CHECK-NEXT:    ret i32 [[IV]]
+; CHECK-NEXT:    [[EXT:%.*]] = zext i8 [[IV]] to i32
+; CHECK-NEXT:    ret i32 [[EXT]]
 ;
 entry:
   br label %loop
 
 loop:
   %iv = phi i8 [ 0, %entry ], [ %iv.next.trunc, %loop.latch ]
   %iv.ext = zext i8 %iv to i32
   %cmp = icmp ne i32 %iv.ext, %end