[HardwareLoops] remove loops which has undef count

[shchenz]

Summary

Remove the loop which has the loop count undef. This aligns with opt behavior.

For the PowerPC code gen changes, to keep the original test point, I add a valid count for the loop in the input IR instead of changing the assembly based on the current IR.

[samparker]

llvm/lib/CodeGen/HardwareLoops.cpp

158

nit: I'd prefer that these were references.

247

I see the same logic is used in LoopDeletion, so should this be factored out into deleteDeadLoop?

[nikic]

Can you please explain what the motivation for this change is?

[fhahn]

llvm/lib/CodeGen/HardwareLoops.cpp

447

I doubt this is enough. I think you would at least have to ensure that the branch on undef is executed unconditionally in the loop. Also, shouldn't those dead loops be cleaned up earlier?

[shchenz]

In D137758#3918978, @nikic wrote:

Can you please explain what the motivation for this change is?

This is from https://reviews.llvm.org/D135847#inline-1327746, in that patch, we found the loop being changed "invalidly" and then we found this is caused by undef loop count, so the "invalid" change is also OK.
And furthermore, we should be able to eliminate the undef count loop. This is what the LLVM opt component does, so we want to make llc align with opt.

llvm/lib/CodeGen/HardwareLoops.cpp

447

I think you would at least have to ensure that the branch on undef is executed unconditionally in the loop.

For hardware loops, the exiting block which contains the compare with loop count will be executed in each loop iteration.

Also, shouldn't those dead loops be cleaned up earlier?

OPT has the pass that can clean up this kind of loop. But in LLC pipeline, there is no such pass.

[shchenz]

llvm/lib/CodeGen/HardwareLoops.cpp

158

Thanks for review.
But I am a little confused by this comment, do you mean SmallVector<Loop &, 1> DeadLoops;? Seems this can not pass the build

247

There are two callers for deleteDeadLoop in LoopDeletion. And for my understanding, these two callers are handling two different scenarios. The first one is like what we do here, the loop is never be executed, so we can just remove the loop and set the phi incoming value from exiting block to poison. And the other one is for loops which act like executing only once, i.e. all instructions in the loop are invariant. So we can make the incoming value from exiting block be invariant and then set it as the new value from preheader after deleting the phi.

I agree we can handle these two scenarios in deleteDeadLoop, but that would require a non-trivial work and not sure it is desirable. For example, we may also need to move some of the logic in isLoopDead() to deleteDeadLoop as the new incoming value for scenario 2 is calculated there. And for the new incoming value poison for scenario 1, we currently calculate just before we call deleteDeadLoop.

Thoughts?

[samparker]

llvm/lib/CodeGen/HardwareLoops.cpp

158

Whooops, sorry, shows I haven't written much C++ recently!

247

Okay, sounds like more effort than it's worth then.

447

Is there a blocker on adding the pass to the llc pipeline?

[shchenz]

llvm/lib/CodeGen/HardwareLoops.cpp

447

hmm, to be honest, I didn't think about adding the pass to the llc pipeline. I am not sure if it is OK.

In OPT, for the case remove-loop-count-undef-loop.ll, the loops are optimized out by two passes, instcombine and loop deletion (Seems like loop deletion can only delete a simple loop optimized after instcombine)

• opt -loop-deletion -S remove-loop-count-undef-loop.ll, the loop is kept
• opt -instcombine -loop-deletion -S remove-loop-count-undef-loop.ll, the loop will be deleted.

I am thinking adding instcombine pass to llc pipeline is not a good idea and doing nested instruction combining to reduce loop complexity first in loop deletion pass also seems strange?

[nikic]

llvm/lib/CodeGen/HardwareLoops.cpp

447

Generally speaking, if opt optimizes something, then llc should not optimize it, unless the optimization is only possible as a result of legalization. It doesn't sound like that's the case here?

The input to llc is assumed to be optimized IR -- if it isn't, it's sufficient to not crash or miscompile it, but there is no need to produce good code.

[samparker]

llvm/lib/CodeGen/HardwareLoops.cpp

447

Is adding the necessary pass(es) into the backend pipeline an option?

[shchenz]

llvm/lib/CodeGen/HardwareLoops.cpp

447

I think @nikic comment suggest llc should not be changed if the opt is able to do the expected optimization, unless the suboptimal IR is result of opt/llc.

I created this patch because I thought llc might be used standalone as llc itself is a functionality complete binary that consumes LLVM IR. But if that is not the case, I am ok to abandon this.

Thanks for all your comments.

[shchenz]

Thanks again for your review, I'll abandon this patch.

llvm/lib/CodeGen/HardwareLoops.cpp

private:
     OptimizationRemarkEmitter *ORE = nullptr;
     const TargetTransformInfo *TTI = nullptr;
     DominatorTree *DT = nullptr;
     bool PreserveLCSSA = false;
     AssumptionCache *AC = nullptr;
     TargetLibraryInfo *LibInfo = nullptr;
     Module *M = nullptr;
     bool MadeChange = false;
+    SmallVector<Loop *, 1> DeadLoops;
   };
 
   class HardwareLoop {
     // Expand the trip count scev into a value that we can use.
-    Value *InitLoopCount();
+    Value *InitLoopCount(SmallVector<Loop *, 1> &DeadLoops);
 
     // Insert the set_loop_iteration intrinsic.
     Value *InsertIterationSetup(Value *LoopCountInit);
 
     // Insert the loop_decrement intrinsic.
     void InsertLoopDec();
 
     // Insert the loop_decrement_reg intrinsic.
HardwareLoop(HardwareLoopInfo &Info, ScalarEvolution &SE,
       SE(SE), DL(DL), ORE(ORE), L(Info.L), M(L->getHeader()->getModule()),
       ExitCount(Info.ExitCount),
       CountType(Info.CountType),
       ExitBranch(Info.ExitBranch),
       LoopDecrement(Info.LoopDecrement),
       UsePHICounter(Info.CounterInReg),
       UseLoopGuard(Info.PerformEntryTest) { }
 
-    void Create();
+    void Create(SmallVector<Loop *, 1> &DeadLoops);
 
   private:
     ScalarEvolution &SE;
     const DataLayout &DL;
     OptimizationRemarkEmitter *ORE = nullptr;
     Loop *L                 = nullptr;
     Module *M               = nullptr;
     const SCEV *ExitCount   = nullptr;
bool HardwareLoops::runOnFunction(Function &F) {
   PreserveLCSSA = mustPreserveAnalysisID(LCSSAID);
   AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
   M = F.getParent();
 
   for (Loop *L : *LI)
     if (L->isOutermost())
       TryConvertLoop(L);
 
+  for (Loop *L : DeadLoops) {
+    BasicBlock *ExitBlock = L->getUniqueExitBlock();
+    assert(ExitBlock && "Dead loop should have a unique exit block!\n");
+    assert(L->hasDedicatedExits() &&
+           "Dead loop should have a dedicated exit block!\n");
+
+    if (!L->isRecursivelyLCSSAForm(*DT, *LI))
+      formLCSSARecursively(*L, *DT, LI, SE);    
+
+    // Set incoming value to poison for phi nodes in the exit block.
+    for (PHINode &P : ExitBlock->phis()) {
+      std::fill(P.incoming_values().begin(), P.incoming_values().end(),
+                PoisonValue::get(P.getType()));
+    }
+    deleteDeadLoop(L, DT, SE, LI);
+    MadeChange = true;
+  }
+
   return MadeChange;
 }
 
 // Return true if the search should stop, which will be when an inner loop is
 // converted and the parent loop doesn't support containing a hardware loop.
 bool HardwareLoops::TryConvertLoop(Loop *L) {
   // Process nested loops first.
   bool AnyChanged = false;
bool HardwareLoops::TryConvertLoop(HardwareLoopInfo &HWLoopInfo) {
 
   // If we don't have a preheader, then insert one.
   if (!Preheader)
     Preheader = InsertPreheaderForLoop(L, DT, LI, nullptr, PreserveLCSSA);
   if (!Preheader)
     return false;
 
   HardwareLoop HWLoop(HWLoopInfo, *SE, *DL, ORE);
-  HWLoop.Create();
+  HWLoop.Create(DeadLoops);
   ++NumHWLoops;
   return true;
 }
 
-void HardwareLoop::Create() {
+void HardwareLoop::Create(SmallVector<Loop *, 1> &DeadLoops) {
   LLVM_DEBUG(dbgs() << "HWLoops: Converting loop..\n");
 
-  Value *LoopCountInit = InitLoopCount();
+  Value *LoopCountInit = InitLoopCount(DeadLoops);
   if (!LoopCountInit) {
     reportHWLoopFailure("could not safely create a loop count expression",
                         "HWLoopNotSafe", ORE, L);
     return;
   }
 
   Value *Setup = InsertIterationSetup(LoopCountInit);
 
static bool CanGenerateTest(Loop *L, Value *Count) {
 
   unsigned SuccIdx = ICmp->getPredicate() == ICmpInst::ICMP_NE ? 0 : 1;
   if (BI->getSuccessor(SuccIdx) != Preheader)
     return false;
 
   return true;
 }
 
-Value *HardwareLoop::InitLoopCount() {
+Value *HardwareLoop::InitLoopCount(SmallVector<Loop *, 1> &DeadLoops) {
   LLVM_DEBUG(dbgs() << "HWLoops: Initialising loop counter value:\n");
   // Can we replace a conditional branch with an intrinsic that sets the
   // loop counter and tests that is not zero?
 
   SCEVExpander SCEVE(SE, DL, "loopcnt");
   if (!ExitCount->getType()->isPointerTy() &&
       ExitCount->getType() != CountType)
     ExitCount = SE.getZeroExtendExpr(ExitCount, CountType);
if (!SCEVE.isSafeToExpandAt(ExitCount, BB->getTerminator())) {
     LLVM_DEBUG(dbgs() << "- Bailing, unsafe to expand ExitCount "
                << *ExitCount << "\n");
     return nullptr;
   }
 
   Value *Count = SCEVE.expandCodeFor(ExitCount, CountType,
                                      BB->getTerminator());
 
+  // Remove the loop which has a undef loop count.
+  // For now deleteDeadLoop() can only delete a loop which has a unique and
+  // dedicated exit block, so we just delete these loops.
+  if (isa<UndefValue>(Count)) {
+    LLVM_DEBUG(dbgs() << " - Bailing, loop count is undef\n");
+    if (L->getUniqueExitBlock() && L->hasDedicatedExits())
+      DeadLoops.push_back(L);
+    return nullptr;
+  }
+
   // FIXME: We've expanded Count where we hope to insert the counter setting
   // intrinsic. But, in the case of the 'test and set' form, we may fallback to
   // the just 'set' form and in which case the insertion block is most likely
   // different. It means there will be instruction(s) in a block that possibly
   // aren't needed. The isLoopEntryGuardedByCond is trying to avoid this issue,
   // but it's doesn't appear to work in all cases.
 
   UseLoopGuard = UseLoopGuard && CanGenerateTest(L, Count);

llvm/test/CodeGen/PowerPC/pr48519.ll

bb3:                                              ; preds = %bb1
   %i7 = fcmp uno float %i6, 0.000000e+00
   %i8 = or i1 %i7, false
   br i1 %i8, label %bb1, label %bb9
 
 bb9:                                              ; preds = %bb3, %bb1
   ret void
 }
 
-define void @func_48786() #0 {
+define void @func_48786(i64 %count) #0 {
 ; CHECK-LABEL: func_48786:
 ; CHECK:       # %bb.0: # %bb
 ; CHECK-NEXT:    mfocrf r12, 32
 ; CHECK-NEXT:    mflr r0
 ; CHECK-NEXT:    std r0, 16(r1)
 ; CHECK-NEXT:    stw r12, 8(r1)
 ; CHECK-NEXT:    stdu r1, -48(r1)
-; CHECK-NEXT:    ld r3, 0(r3)
+; CHECK-NEXT:    ld r4, 0(r3)
 ; CHECK-NEXT:    std r30, 32(r1) # 8-byte Folded Spill
-; CHECK-NEXT:    # implicit-def: $x30
-; CHECK-NEXT:    cmpdi r3, 0
+; CHECK-NEXT:    mr r30, r3
+; CHECK-NEXT:    cmpdi r4, 0
 ; CHECK-NEXT:    crnot 4*cr2+lt, eq
 ; CHECK-NEXT:    bc 12, 4*cr5+lt, .LBB2_3
 ; CHECK-NEXT:    .p2align 4
 ; CHECK-NEXT:  .LBB2_1: # %bb4
 ; CHECK-NEXT:    lhz r3, 0(r3)
 ; CHECK-NEXT:    bl __gnu_h2f_ieee
 ; CHECK-NEXT:    nop
 ; CHECK-NEXT:    bc 4, 4*cr2+lt, .LBB2_6

 ; CHECK-NEXT:    lwz r12, 8(r1)
 ; CHECK-NEXT:    mtocrf 32, r12
 ; CHECK-NEXT:    mtlr r0
 ; CHECK-NEXT:    blr
 ; CHECK-NEXT:  .LBB2_6: # %bb15
 ;
 ; CHECK-P9-LABEL: func_48786:
 ; CHECK-P9:       # %bb.0: # %bb
-; CHECK-P9-NEXT:    ld r3, 0(r3)
-; CHECK-P9-NEXT:    cmpdi r3, 0
+; CHECK-P9-NEXT:    ld r4, 0(r3)
+; CHECK-P9-NEXT:    subfic r3, r3, 1
 ; CHECK-P9-NEXT:    mtctr r3
 ; CHECK-P9-NEXT:    li r3, 0
+; CHECK-P9-NEXT:    cmpdi r4, 0
 ; CHECK-P9-NEXT:    crnot 4*cr5+lt, eq
 ; CHECK-P9-NEXT:    b .LBB2_2
 ; CHECK-P9-NEXT:    .p2align 5
 ; CHECK-P9-NEXT:  .LBB2_1: # %bb10
 ; CHECK-P9-NEXT:    #
 ; CHECK-P9-NEXT:    bdzlr
 ; CHECK-P9-NEXT:  .LBB2_2: # %bb2
 ; CHECK-P9-NEXT:    #

 ; CHECK-P9-NEXT:    b .LBB2_1
 ; CHECK-P9-NEXT:  .LBB2_5: # %bb15
 bb:
   %i = load i64, ptr addrspace(11) undef, align 8
   %i1 = load i64, ptr addrspace(11) undef, align 8
   br label %bb2
 
 bb2:                                              ; preds = %bb12, %bb
-  %i3 = phi i64 [ undef, %bb ], [ %i13, %bb12 ]
+  %i3 = phi i64 [ %count, %bb ], [ %i13, %bb12 ]
   br i1 undef, label %bb10, label %bb4
 
 bb4:                                              ; preds = %bb2
   switch i32 undef, label %bb9 [
     i32 1426063360, label %bb5
     i32 1275068416, label %bb5
   ]
 

llvm/test/CodeGen/PowerPC/sms-iterator.ll

 ; REQUIRES: asserts
 ; RUN: llc < %s -mtriple=powerpc64le-unknown-linux-gnu -verify-machineinstrs\
 ; RUN:       -mcpu=pwr9 --ppc-enable-pipeliner -debug-only=pipeliner 2>&1 \
 ; RUN:       >/dev/null | FileCheck %s
 
 %0 = type { i32, [16 x double] }
 
 ; CHECK: MII = 3 MAX_II = 13 (rec=3, res=2)
 
-define dso_local fastcc double @_ZN3povL9polysolveEiPdS0_() unnamed_addr #0 {
+define dso_local fastcc double @_ZN3povL9polysolveEiPdS0_(i64 %count) unnamed_addr #0 {
   br label %1
 
 1:                                                ; preds = %1, %0
   br i1 undef, label %2, label %1
 
 2:                                                ; preds = %1
   br i1 undef, label %14, label %3
 
 3:                                                ; preds = %3, %2
   %4 = phi i64 [ %7, %3 ], [ undef, %2 ]
   %5 = phi double [ %11, %3 ], [ undef, %2 ]
-  %6 = phi i64 [ %12, %3 ], [ undef, %2 ]
+  %6 = phi i64 [ %12, %3 ], [ %count, %2 ]
   %7 = add nsw i64 %4, -1
   %8 = fmul fast double %5, 1.000000e+07
   %9 = getelementptr inbounds %0, ptr null, i64 1, i32 1, i64 %7
   %10 = load double, ptr %9, align 8
   %11 = fadd fast double %10, %8
   %12 = add i64 %6, -1
   %13 = icmp eq i64 %12, 0
   br i1 %13, label %14, label %3
 
 14:                                               ; preds = %3, %2
   %15 = phi double [ undef, %2 ], [ %11, %3 ]
   %16 = fmul fast double %15, undef
   ret double %16
 }

llvm/test/CodeGen/PowerPC/sms-phi-3.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc < %s -mtriple=powerpc64le-unknown-linux-gnu -verify-machineinstrs\
 ; RUN:       -mcpu=pwr9 --ppc-enable-pipeliner 2>&1 | FileCheck %s
 
 %0 = type { double, double, double, i32, i32 }
 declare i8* @malloc() local_unnamed_addr
 
-define void @phi3(i32*) nounwind {
+define void @phi3(i32*, i64 %count) nounwind {
 ; CHECK-LABEL: phi3:
 ; CHECK:       # %bb.0:
 ; CHECK-NEXT:    mflr 0
+; CHECK-NEXT:    std 28, -32(1) # 8-byte Folded Spill
 ; CHECK-NEXT:    std 29, -24(1) # 8-byte Folded Spill
 ; CHECK-NEXT:    std 30, -16(1) # 8-byte Folded Spill
 ; CHECK-NEXT:    std 0, 16(1)
 ; CHECK-NEXT:    stdu 1, -64(1)
-; CHECK-NEXT:    mr 30, 3
+; CHECK-NEXT:    mr 30, 4
+; CHECK-NEXT:    mr 29, 3
 ; CHECK-NEXT:    bl malloc
 ; CHECK-NEXT:    nop
-; CHECK-NEXT:    mr 29, 3
+; CHECK-NEXT:    mr 28, 3
 ; CHECK-NEXT:    bl malloc
 ; CHECK-NEXT:    nop
-; CHECK-NEXT:    addi 7, 30, -4
-; CHECK-NEXT:    mtctr 3
-; CHECK-NEXT:    addi 4, 29, -8
+; CHECK-NEXT:    addi 7, 29, -4
+; CHECK-NEXT:    mtctr 30
+; CHECK-NEXT:    addi 4, 28, -8
 ; CHECK-NEXT:    li 5, 0
 ; CHECK-NEXT:    lwzu 8, 4(7)
 ; CHECK-NEXT:    bdz .LBB0_5
 ; CHECK-NEXT:  # %bb.1:
 ; CHECK-NEXT:    extswsli 6, 5, 5
 ; CHECK-NEXT:    add 5, 8, 5
 ; CHECK-NEXT:    lwzu 8, 4(7)
 ; CHECK-NEXT:    bdz .LBB0_4
 ; CHECK-NEXT:  # %bb.2:
 ; CHECK-NEXT:    add 6, 3, 6
 ; CHECK-NEXT:    stdu 6, 8(4)
 ; CHECK-NEXT:    extswsli 6, 5, 5
 ; CHECK-NEXT:    add 5, 8, 5
 ; CHECK-NEXT:    lwzu 8, 4(7)
 ; CHECK-NEXT:    bdz .LBB0_4
 ; CHECK-NEXT:    .p2align 5
-; CHECK-NEXT:  .LBB0_3: #
+; CHECK-NEXT:  .LBB0_3:
 ; CHECK-NEXT:    add 9, 3, 6
 ; CHECK-NEXT:    extswsli 6, 5, 5
 ; CHECK-NEXT:    add 5, 8, 5
 ; CHECK-NEXT:    lwzu 8, 4(7)
 ; CHECK-NEXT:    stdu 9, 8(4)
 ; CHECK-NEXT:    bdnz .LBB0_3
 ; CHECK-NEXT:  .LBB0_4:
 ; CHECK-NEXT:    add 6, 3, 6
 ; CHECK-NEXT:    stdu 6, 8(4)
 ; CHECK-NEXT:  .LBB0_5:
 ; CHECK-NEXT:    extswsli 5, 5, 5
 ; CHECK-NEXT:    add 3, 3, 5
 ; CHECK-NEXT:    stdu 3, 8(4)
 ; CHECK-NEXT:    addi 1, 1, 64
 ; CHECK-NEXT:    ld 0, 16(1)
 ; CHECK-NEXT:    ld 30, -16(1) # 8-byte Folded Reload
 ; CHECK-NEXT:    ld 29, -24(1) # 8-byte Folded Reload
+; CHECK-NEXT:    ld 28, -32(1) # 8-byte Folded Reload
 ; CHECK-NEXT:    mtlr 0
 ; CHECK-NEXT:    blr
   %2 = tail call noalias i8* @malloc()
   %3 = bitcast i8* %2 to %0**
   %4 = tail call noalias i8* @malloc()
   %5 = bitcast i8* %4 to %0*
   br label %6
 
 6:                                                ; preds = %6, %1
   %7 = phi i64 [ %16, %6 ], [ 0, %1 ]
   %8 = phi i32 [ %15, %6 ], [ 0, %1 ]
-  %9 = phi i64 [ %17, %6 ], [ undef, %1 ]
+  %9 = phi i64 [ %17, %6 ], [ %count, %1 ]
   %10 = sext i32 %8 to i64
   %11 = getelementptr inbounds %0, %0* %5, i64 %10
   %12 = getelementptr inbounds %0*, %0** %3, i64 %7
   store %0* %11, %0** %12, align 8
   %13 = getelementptr inbounds i32, i32* %0, i64 %7
   %14 = load i32, i32* %13, align 4
   %15 = add nsw i32 %14, %8
   %16 = add nuw nsw i64 %7, 1
   %17 = add i64 %9, -1
   %18 = icmp eq i64 %17, 0
   br i1 %18, label %19, label %6
 
 19:                                               ; preds = %6
   ret void
 }

llvm/test/Transforms/HardwareLoops/remove-loop-count-undef-loop.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -hardware-loops -force-hardware-loops=true -hardware-loop-decrement=1  -hardware-loop-counter-bitwidth=32 -S | FileCheck %s
 
 define void @foo1() #0 {
 ; CHECK-LABEL: @foo1(
 ; CHECK-NEXT:  bb:
-; CHECK-NEXT:    call void @llvm.set.loop.iterations.i32(i32 undef)
-; CHECK-NEXT:    br label [[BB1:%.*]]
-; CHECK:       bb1:
-; CHECK-NEXT:    [[TMP0:%.*]] = phi i32 [ [[TMP2:%.*]], [[BB1]] ], [ undef, [[BB:%.*]] ]
-; CHECK-NEXT:    [[TMP1:%.*]] = sitofp i32 [[TMP0]] to double
-; CHECK-NEXT:    [[TMP2]] = fptosi double [[TMP1]] to i32
-; CHECK-NEXT:    [[TMP3:%.*]] = call i1 @llvm.loop.decrement.i32(i32 1)
-; CHECK-NEXT:    br i1 [[TMP3]], label [[BB1]], label [[BB8:%.*]]
+; CHECK-NEXT:    br label [[BB8:%.*]]
 ; CHECK:       bb8:
-; CHECK-NEXT:    call void @bar(i32 [[TMP2]])
+; CHECK-NEXT:    [[DOTLCSSA:%.*]] = phi i32 [ poison, [[BB:%.*]] ]
+; CHECK-NEXT:    call void @bar(i32 [[DOTLCSSA]])
 ; CHECK-NEXT:    ret void
 ;
 bb:
   br label %bb1
 
 bb1:
   %0 = phi i32 [ %4, %bb1 ], [ undef, %bb ]
   %1 = phi i32 [ %2, %bb1 ], [ undef, %bb ]