[LICM] Don't duplicate instructions just because they're free

[nikic]

Summary

D37076 makes LICM duplicate instructions into exit blocks if the instruction is free. For GEPs, the motivation appears to be that this allows the GEP to be folded into addressing modes, while non-foldable users outside the loop might prevent this. TBH I don't think LICM is the place to do this (why doesn't CGP apply this heuristic itself?) but at least I understand the motivation.

However, the transform is also applied to all other "free" instructions, which are just that (removed during lowering and not "folded" in some way). For such instruction, this transform seems somewhere between useless, counter-productive (undoing CSE/GVN) and actively incorrect. For example, this transform can duplicate freeze instructions, which is illegal.

This patch limits the transform to just foldable GEPs, though we might want to drop it from LICM entirely as a followup.

This is a small compile-time improvement, because querying TTI cost model for every single instruction is expensive: http://llvm-compile-time-tracker.com/compare.php?from=057b5f1f3573ddceb04d9eb6fb9973358d53fece&to=1211bdf470f784888b8bef867e1e613539998e9b&stat=instructions:u

[mkazantsev]

llvm/lib/Transforms/Scalar/LICM.cpp

1379

This function has a very clear semantics of checking cost, and I don't think that legality concerns should be taken into account here. The legality check seems missing here:

// Check to see if we can sink this instruction to the exit blocks
// of the loop.  We can do this if the all users of the instruction are
// outside of the loop.  In this case, it doesn't even matter if the
// operands of the instruction are loop invariant.
//
bool FreeInLoop = false;
bool LoopNestMode = OutermostLoop != nullptr;
if (!I.mayHaveSideEffects() &&
    isNotUsedOrFreeInLoop(I, LoopNestMode ? OutermostLoop : CurLoop,
                          SafetyInfo, TTI, FreeInLoop, LoopNestMode) &&
    canSinkOrHoistInst(I, AA, DT, CurLoop, MSSAU, true, Flags, ORE)) {
  if (sink(I, LI, DT, CurLoop, SafetyInfo, MSSAU, ORE)) {
    if (!FreeInLoop) {
      ++II;
      salvageDebugInfo(I);
      eraseInstruction(I, *SafetyInfo, MSSAU);
    }
    Changed = true;
  }
}

There should be check on legality of duplication somewhere around here.

[mkazantsev]

I also agree that we should possibly consider dropping this transform at all.

[nikic]

llvm/lib/Transforms/Scalar/LICM.cpp

1379

This is intended as a change of the cost model (i.e. don't do it for anything but GEP), which also fixes the legality issue by dint of this always being legal for GEPs and it not handling anything else anymore.

We don't have a generic way to check legality of this transform, as far as I know.

[nikic]

Rename Free -> Foldable to make the name match the new implementation.

[mkazantsev]

LG, thanks!

llvm/lib/Transforms/Scalar/LICM.cpp

if (IncValue != &I)
       return false;
 
   return true;
 }
 
 /// Return true if the instruction is free in the loop.
 static bool isFreeInLoop(const Instruction &I, const Loop *CurLoop,
                          const TargetTransformInfo *TTI) {
+  if (auto *GEP = dyn_cast<GetElementPtrInst>(&I)) {
     InstructionCost CostI =
         TTI->getInstructionCost(&I, TargetTransformInfo::TCK_SizeAndLatency);
-
-  if (auto *GEP = dyn_cast<GetElementPtrInst>(&I)) {
     if (CostI != TargetTransformInfo::TCC_Free)
       return false;
     // For a GEP, we cannot simply use getInstructionCost because currently
     // it optimistically assumes that a GEP will fold into addressing mode
     // regardless of its users.
     const BasicBlock *BB = GEP->getParent();
     for (const User *U : GEP->users()) {
       const Instruction *UI = cast<Instruction>(U);
       if (CurLoop->contains(UI) &&
           (BB != UI->getParent() ||
            (!isa<StoreInst>(UI) && !isa<LoadInst>(UI))))
         return false;
     }
     return true;
   }
 
-  return CostI == TargetTransformInfo::TCC_Free;
+  return false;
 }
 
 /// Return true if the only users of this instruction are outside of
 /// the loop. If this is true, we can sink the instruction to the exit
 /// blocks of the loop.
 ///
 /// We also return true if the instruction could be folded away in lowering.
 /// (e.g.,  a GEP can be folded into a load as an addressing mode in the loop).

llvm/test/CodeGen/PowerPC/atomicrmw-uinc-udec-wrap.ll

; CHECK-NEXT:    blr
   ret i16 %result
 }
 
 define i32 @atomicrmw_uinc_wrap_i32(ptr %ptr, i32 %val) {
 ; CHECK-LABEL: atomicrmw_uinc_wrap_i32:
 ; CHECK:       # %bb.0:
 ; CHECK-NEXT:    sync
 ; CHECK-NEXT:    li 6, 0
-; CHECK-NEXT:    lwz 7, 0(3)
+; CHECK-NEXT:    lwz 5, 0(3)
 ; CHECK-NEXT:    b .LBB2_2
 ; CHECK-NEXT:  .LBB2_1: # %atomicrmw.start
 ; CHECK-NEXT:    #
 ; CHECK-NEXT:    cmplw 5, 7
-; CHECK-NEXT:    mr 7, 5
 ; CHECK-NEXT:    beq 0, .LBB2_7
 ; CHECK-NEXT:  .LBB2_2: # %atomicrmw.start
 ; CHECK-NEXT:    # =>This Loop Header: Depth=1
 ; CHECK-NEXT:    # Child Loop BB2_5 Depth 2
-; CHECK-NEXT:    addi 5, 7, 1
+; CHECK-NEXT:    mr 7, 5
+; CHECK-NEXT:    addi 5, 5, 1
 ; CHECK-NEXT:    cmplw 7, 4
 ; CHECK-NEXT:    bc 12, 0, .LBB2_4
 ; CHECK-NEXT:  # %bb.3: # %atomicrmw.start
 ; CHECK-NEXT:    #
 ; CHECK-NEXT:    ori 8, 6, 0
 ; CHECK-NEXT:    b .LBB2_5
 ; CHECK-NEXT:  .LBB2_4: # %atomicrmw.start
 ; CHECK-NEXT:    #
; CHECK-NEXT:    blr
   %result = atomicrmw uinc_wrap ptr %ptr, i32 %val seq_cst
   ret i32 %result
 }
 
 define i64 @atomicrmw_uinc_wrap_i64(ptr %ptr, i64 %val) {
 ; CHECK-LABEL: atomicrmw_uinc_wrap_i64:
 ; CHECK:       # %bb.0:
 ; CHECK-NEXT:    sync
-; CHECK-NEXT:    ld 7, 0(3)
+; CHECK-NEXT:    ld 5, 0(3)
 ; CHECK-NEXT:    li 6, 0
 ; CHECK-NEXT:    b .LBB3_2
 ; CHECK-NEXT:  .LBB3_1: # %atomicrmw.start
 ; CHECK-NEXT:    #
 ; CHECK-NEXT:    cmpld 5, 7
-; CHECK-NEXT:    mr 7, 5
 ; CHECK-NEXT:    beq 0, .LBB3_7
 ; CHECK-NEXT:  .LBB3_2: # %atomicrmw.start
 ; CHECK-NEXT:    # =>This Loop Header: Depth=1
 ; CHECK-NEXT:    # Child Loop BB3_5 Depth 2
-; CHECK-NEXT:    addi 5, 7, 1
+; CHECK-NEXT:    mr 7, 5
+; CHECK-NEXT:    addi 5, 5, 1
 ; CHECK-NEXT:    cmpld 7, 4
 ; CHECK-NEXT:    bc 12, 0, .LBB3_4
 ; CHECK-NEXT:  # %bb.3: # %atomicrmw.start
 ; CHECK-NEXT:    #
 ; CHECK-NEXT:    ori 8, 6, 0
 ; CHECK-NEXT:    b .LBB3_5
 ; CHECK-NEXT:  .LBB3_4: # %atomicrmw.start
 ; CHECK-NEXT:    #
; CHECK-NEXT:    blr
   %result = atomicrmw udec_wrap ptr %ptr, i16 %val seq_cst
   ret i16 %result
 }
 
 define i32 @atomicrmw_udec_wrap_i32(ptr %ptr, i32 %val) {
 ; CHECK-LABEL: atomicrmw_udec_wrap_i32:
 ; CHECK:       # %bb.0:
 ; CHECK-NEXT:    sync
-; CHECK-NEXT:    lwz 6, 0(3)
+; CHECK-NEXT:    lwz 5, 0(3)
 ; CHECK-NEXT:    b .LBB6_2
 ; CHECK-NEXT:  .LBB6_1: # %atomicrmw.start
 ; CHECK-NEXT:    #
 ; CHECK-NEXT:    cmplw 5, 6
-; CHECK-NEXT:    mr 6, 5
 ; CHECK-NEXT:    beq 0, .LBB6_7
 ; CHECK-NEXT:  .LBB6_2: # %atomicrmw.start
 ; CHECK-NEXT:    # =>This Loop Header: Depth=1
 ; CHECK-NEXT:    # Child Loop BB6_5 Depth 2
+; CHECK-NEXT:    mr 6, 5
 ; CHECK-NEXT:    cmpwi 6, 0
 ; CHECK-NEXT:    cmplw 1, 6, 4
-; CHECK-NEXT:    addi 5, 6, -1
+; CHECK-NEXT:    addi 5, 5, -1
 ; CHECK-NEXT:    cror 20, 2, 5
 ; CHECK-NEXT:    bc 12, 20, .LBB6_4
 ; CHECK-NEXT:  # %bb.3: # %atomicrmw.start
 ; CHECK-NEXT:    #
 ; CHECK-NEXT:    ori 7, 5, 0
 ; CHECK-NEXT:    b .LBB6_5
 ; CHECK-NEXT:  .LBB6_4: # %atomicrmw.start
 ; CHECK-NEXT:    #
; CHECK-NEXT:    blr
   %result = atomicrmw udec_wrap ptr %ptr, i32 %val seq_cst
   ret i32 %result
 }
 
 define i64 @atomicrmw_udec_wrap_i64(ptr %ptr, i64 %val) {
 ; CHECK-LABEL: atomicrmw_udec_wrap_i64:
 ; CHECK:       # %bb.0:
 ; CHECK-NEXT:    sync
-; CHECK-NEXT:    ld 6, 0(3)
+; CHECK-NEXT:    ld 5, 0(3)
 ; CHECK-NEXT:    b .LBB7_2
 ; CHECK-NEXT:  .LBB7_1: # %atomicrmw.start
 ; CHECK-NEXT:    #
 ; CHECK-NEXT:    cmpld 5, 6
-; CHECK-NEXT:    mr 6, 5
 ; CHECK-NEXT:    beq 0, .LBB7_7
 ; CHECK-NEXT:  .LBB7_2: # %atomicrmw.start
 ; CHECK-NEXT:    # =>This Loop Header: Depth=1
 ; CHECK-NEXT:    # Child Loop BB7_5 Depth 2
-; CHECK-NEXT:    cmpdi 6, 0
+; CHECK-NEXT:    mr. 6, 5
 ; CHECK-NEXT:    cmpld 1, 6, 4
-; CHECK-NEXT:    addi 5, 6, -1
+; CHECK-NEXT:    addi 5, 5, -1
 ; CHECK-NEXT:    cror 20, 2, 5
 ; CHECK-NEXT:    bc 12, 20, .LBB7_4
 ; CHECK-NEXT:  # %bb.3: # %atomicrmw.start
 ; CHECK-NEXT:    #
 ; CHECK-NEXT:    ori 7, 5, 0
 ; CHECK-NEXT:    b .LBB7_5
 ; CHECK-NEXT:  .LBB7_4: # %atomicrmw.start
 ; CHECK-NEXT:    #

llvm/test/Transforms/LICM/pr23608.ll

 ; NO_ASSUME:       bb:
 ; NO_ASSUME-NEXT:    call void @__msan_warning_noreturn()
 ; NO_ASSUME-NEXT:    unreachable
 ; NO_ASSUME:       bb2:
 ; NO_ASSUME-NEXT:    [[TMP4:%.*]] = ptrtoint ptr [[TMP]] to i64
 ; NO_ASSUME-NEXT:    [[TOBOOL:%.*]] = icmp eq i64 [[TMP4]], 0
 ; NO_ASSUME-NEXT:    br i1 [[TOBOOL]], label [[BB13:%.*]], label [[BB15:%.*]]
 ; NO_ASSUME:       bb13:
-; NO_ASSUME-NEXT:    [[F_IBLOCK_LCSSA:%.*]] = phi ptr [ [[TMP]], [[BB2]] ]
-; NO_ASSUME-NEXT:    [[TMP4_LE:%.*]] = ptrtoint ptr [[F_IBLOCK_LCSSA]] to i64
-; NO_ASSUME-NEXT:    [[TMP8_LE:%.*]] = inttoptr i64 [[TMP4_LE]] to ptr
+; NO_ASSUME-NEXT:    [[TMP4_LCSSA:%.*]] = phi i64 [ [[TMP4]], [[BB2]] ]
+; NO_ASSUME-NEXT:    [[TMP8_LE:%.*]] = inttoptr i64 [[TMP4_LCSSA]] to ptr
 ; NO_ASSUME-NEXT:    call void @__msan_warning_noreturn()
 ; NO_ASSUME-NEXT:    unreachable
 ; NO_ASSUME:       bb15:
 ; NO_ASSUME-NEXT:    br i1 [[TOBOOL]], label [[WHILE_END:%.*]], label [[WHILE_COND:%.*]]
 ; NO_ASSUME:       while.end:
 ; NO_ASSUME-NEXT:    ret void
 ; NO_ASSUME:       indirectgoto:
 ; NO_ASSUME-NEXT:    indirectbr ptr null, [label [[INDIRECTGOTO]], label %while.cond]

 ; USE_ASSUME-NEXT:    call void @__msan_warning_noreturn()
 ; USE_ASSUME-NEXT:    unreachable
 ; USE_ASSUME:       bb2:
 ; USE_ASSUME-NEXT:    call void @llvm.assume(i1 true) [ "dereferenceable"(ptr [[TMP]], i64 4), "nonnull"(ptr [[TMP]]), "align"(ptr [[TMP]], i64 4) ]
 ; USE_ASSUME-NEXT:    [[TMP4:%.*]] = ptrtoint ptr [[TMP]] to i64
 ; USE_ASSUME-NEXT:    [[TOBOOL:%.*]] = icmp eq i64 [[TMP4]], 0
 ; USE_ASSUME-NEXT:    br i1 [[TOBOOL]], label [[BB13:%.*]], label [[BB15:%.*]]
 ; USE_ASSUME:       bb13:
-; USE_ASSUME-NEXT:    [[F_IBLOCK_LCSSA:%.*]] = phi ptr [ [[TMP]], [[BB2]] ]
-; USE_ASSUME-NEXT:    [[TMP4_LE:%.*]] = ptrtoint ptr [[F_IBLOCK_LCSSA]] to i64
-; USE_ASSUME-NEXT:    [[TMP8_LE:%.*]] = inttoptr i64 [[TMP4_LE]] to ptr
+; USE_ASSUME-NEXT:    [[TMP4_LCSSA:%.*]] = phi i64 [ [[TMP4]], [[BB2]] ]
+; USE_ASSUME-NEXT:    [[TMP8_LE:%.*]] = inttoptr i64 [[TMP4_LCSSA]] to ptr
 ; USE_ASSUME-NEXT:    call void @__msan_warning_noreturn()
 ; USE_ASSUME-NEXT:    unreachable
 ; USE_ASSUME:       bb15:
 ; USE_ASSUME-NEXT:    br i1 [[TOBOOL]], label [[WHILE_END:%.*]], label [[WHILE_COND:%.*]]
 ; USE_ASSUME:       while.end:
 ; USE_ASSUME-NEXT:    ret void
 ; USE_ASSUME:       indirectgoto:
 ; USE_ASSUME-NEXT:    indirectbr ptr null, [label [[INDIRECTGOTO]], label %while.cond]

llvm/test/Transforms/LICM/sink-foldable.ll

 ; CHECK-NEXT:    [[L1:%.*]] = load ptr, ptr [[ARRAYIDX1]], align 8
 ; CHECK-NEXT:    [[CMP4:%.*]] = icmp ugt ptr [[L1]], [[Q]]
 ; CHECK-NEXT:    [[I_ADD]] = add nsw i32 [[I0]], 2
 ; CHECK-NEXT:    br i1 [[CMP4]], label [[LOOPEXIT1:%.*]], label [[FOR_BODY]]
 ; CHECK:       loopexit0:
 ; CHECK-NEXT:    [[P1:%.*]] = phi ptr [ [[ARRAYIDX0]], [[FOR_BODY]] ]
 ; CHECK-NEXT:    br label [[RETURN]]
 ; CHECK:       loopexit1:
-; CHECK-NEXT:    [[ADD_LCSSA:%.*]] = phi i64 [ [[ADD]], [[IF_END]] ]
+; CHECK-NEXT:    [[TRUNC_LCSSA1:%.*]] = phi i32 [ [[TRUNC]], [[IF_END]] ]
 ; CHECK-NEXT:    [[P_ADDR_LCSSA:%.*]] = phi ptr [ [[P_ADDR]], [[IF_END]] ]
-; CHECK-NEXT:    [[TRUNC_LE:%.*]] = trunc i64 [[ADD_LCSSA]] to i32
-; CHECK-NEXT:    [[ARRAYIDX1_LE:%.*]] = getelementptr inbounds ptr, ptr [[P_ADDR_LCSSA]], i32 [[TRUNC_LE]]
-; CHECK-NEXT:    call void @dummy(i32 [[TRUNC_LE]])
+; CHECK-NEXT:    [[TRUNC_LCSSA:%.*]] = phi i32 [ [[TRUNC]], [[IF_END]] ]
+; CHECK-NEXT:    [[ARRAYIDX1_LE:%.*]] = getelementptr inbounds ptr, ptr [[P_ADDR_LCSSA]], i32 [[TRUNC_LCSSA1]]
+; CHECK-NEXT:    call void @dummy(i32 [[TRUNC_LCSSA]])
 ; CHECK-NEXT:    br label [[RETURN]]
 ; CHECK:       return:
 ; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi ptr [ [[P1]], [[LOOPEXIT0]] ], [ [[ARRAYIDX1_LE]], [[LOOPEXIT1]] ], [ null, [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    ret ptr [[RETVAL_0]]
 ;
 entry:
   %cmp0 = icmp slt i64 0, %j
   br i1 %cmp0, label %for.body.lr.ph, label %return

llvm/test/Transforms/LICM/sinking.ll

 
 out:
   ret i32 %x
 }
 
 declare void @use.i32(i32)
 declare void @use.i64(i64)
 
+; Don't duplicate freeze just because it's free.
 define i32 @duplicate_freeze(i1 %c, i32 %x) {
 ; CHECK-LABEL: @duplicate_freeze(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[FR:%.*]] = freeze i32 [[X:%.*]]
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    call void @use.i32(i32 [[FR]])
 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[LOOP]], label [[EXIT:%.*]]
 ; CHECK:       exit:
-; CHECK-NEXT:    [[FR_LE:%.*]] = freeze i32 [[X]]
-; CHECK-NEXT:    ret i32 [[FR_LE]]
+; CHECK-NEXT:    [[FR_LCSSA:%.*]] = phi i32 [ [[FR]], [[LOOP]] ]
+; CHECK-NEXT:    ret i32 [[FR_LCSSA]]
 ;
 entry:
   br label %loop
 
 loop:
   %fr = freeze i32 %x
   call void @use.i32(i32 %fr)
   br i1 %c, label %loop, label %exit
 
 exit:
   ret i32 %fr
 }
 
+; Don't duplicate ptrtoint just because it's free.
 define i64 @duplicate_ptrtoint(i1 %c, ptr %p) {
 ; CHECK-LABEL: @duplicate_ptrtoint(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[PI:%.*]] = ptrtoint ptr [[P:%.*]] to i64
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    call void @use.i64(i64 [[PI]])
 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[LOOP]], label [[EXIT:%.*]]
 ; CHECK:       exit:
-; CHECK-NEXT:    [[PI_LE:%.*]] = ptrtoint ptr [[P]] to i64
-; CHECK-NEXT:    ret i64 [[PI_LE]]
+; CHECK-NEXT:    [[PI_LCSSA:%.*]] = phi i64 [ [[PI]], [[LOOP]] ]
+; CHECK-NEXT:    ret i64 [[PI_LCSSA]]
 ;
 entry:
   br label %loop
 
 loop:
   %pi = ptrtoint ptr %p to i64
   call void @use.i64(i64 %pi)
   br i1 %c, label %loop, label %exit