[CodeGen] Check for HardwareLoop Latch ExitBlock

[samparker]

Summary

The HardwareLoops pass finds exit blocks with a scevable exit count. If the target specifies to update the loop counter in a register, through a phi, we need to ensure that the exit block is a latch so that we can insert the phi with the correct value for the incoming edge.

[dmgreen]

lib/CodeGen/HardwareLoops.cpp

247

Maybe "RequiresLoopExitingLatch" as a more descriptive name?

lib/Target/ARM/ARMTargetTransformInfo.cpp

706

Is it worth just checking for the LoopExitingLatch here, as opposed to adding a parameter for it?

(Put another way, why would one be a parameter and the other be something for the backend to figure out?)

[samparker]

Cheers Dave. I've removed the ExitBlock check in the ARM backend. Also, currently we'd need CounterInReg == RequiresLoopLatchExit so I've just switched to querying CounterInReg instead of introducing a new parameter. If, later, there's another target which has a separate requirement, then we can re-add the option.

[dmgreen]

Am I correct in saying that this loop will find the first exiting block that dominates all the latches in the loop (with some other conditions like a loop invariant non zero exit count). Plus is now also a latch?

But the loop may have other exits and other latches?

The "other exits" sounds like it should be OK for arm low overhead loops. At least I can't think of a reason right now why they are not OK. For vector tail predicated loops I imagine that you would need to ensure that a "LCTP" is placed on the other exits, to ensure the tail predicate doesn't pollute extra instructions after the loop.

I'm not sure about the "other latches" part. Is that something that's OK? I imagine it doesn't come up very often.

[dmgreen]

Actually, looking at it, because we can compute the BETC, we will only have a single latch. Ignore me about that bit.

For scalar low overhead loops, this LGTM. Vector loops we are looking into later, as far as I understand.

include/llvm/Analysis/TargetTransformInfo.h

public:
   };
 
   /// Get target-customized preferences for the generic loop unrolling
   /// transformation. The caller will initialize UP with the current
   /// target-independent defaults.
   void getUnrollingPreferences(Loop *L, ScalarEvolution &,
                                UnrollingPreferences &UP) const;
 
-  /// Attributes of a target dependent hardware loop. Here, the term 'element'
-  /// describes the work performed by an IR loop that has not been vectorized
-  /// by the compiler.
+  /// Attributes of a target dependent hardware loop.
   struct HardwareLoopInfo {
     HardwareLoopInfo()        = delete;
     HardwareLoopInfo(Loop *L) : L(L) { }
     Loop *L                   = nullptr;
     BasicBlock *ExitBlock     = nullptr;
     BranchInst *ExitBranch    = nullptr;
     const SCEV *ExitCount     = nullptr;
     IntegerType *CountType    = nullptr;
-    Value *LoopDecrement      = nullptr;  // The maximum number of elements
-                                          // processed in the loop body.
+    Value *LoopDecrement      = nullptr;  // Decrement the loop counter by this
+                                          // value in every iteration.
     bool IsNestingLegal       = false;    // Can a hardware loop be a parent to
-                                          // another hardware loop.
+                                          // another hardware loop?
     bool CounterInReg         = false;    // Should loop counter be updated in
                                           // the loop via a phi?
+    bool RequiresLatch        = false;    // Does the loop decrement need to be
+                                          // in a loop latch?
   };
 
   /// Query the target whether it would be profitable to convert the given loop
   /// into a hardware loop.
   bool isHardwareLoopProfitable(Loop *L, ScalarEvolution &SE,
                                 AssumptionCache &AC,
                                 TargetLibraryInfo *LibInfo,
                                 HardwareLoopInfo &HWLoopInfo) const;

lib/CodeGen/HardwareLoops.cpp

 static cl::opt<unsigned>
 LoopDecrement("hardware-loop-decrement", cl::Hidden, cl::init(1),
             cl::desc("Set the loop decrement value"));
 
 static cl::opt<unsigned>
 CounterBitWidth("hardware-loop-counter-bitwidth", cl::Hidden, cl::init(32),
                 cl::desc("Set the loop counter bitwidth"));
 
+static cl::opt<bool>
+RequiresLatch("hardware-loop-latch", cl::Hidden, cl::init(false),
+              cl::desc("Force loop decrement to be placed in loop latch"));
+
 STATISTIC(NumHWLoops, "Number of loops converted to hardware loops");
 
 namespace {
 
   using TTI = TargetTransformInfo;
 
   class HardwareLoops : public FunctionPass {
   public:
bool HardwareLoops::TryConvertLoop(TTI::HardwareLoopInfo &HWLoopInfo) {
   Loop *L = HWLoopInfo.L;
   LLVM_DEBUG(dbgs() << "HWLoops: Try to convert profitable loop: " << *L);
 
   SmallVector<BasicBlock*, 4> ExitingBlocks;
   L->getExitingBlocks(ExitingBlocks);
 
   for (SmallVectorImpl<BasicBlock *>::iterator I = ExitingBlocks.begin(),
        IE = ExitingBlocks.end(); I != IE; ++I) {
-    const SCEV *EC = SE->getExitCount(L, *I);
+    BasicBlock *BB = *I;
+
+    if (!L->isLoopLatch(BB)) {
+      if (RequiresLatch.getNumOccurrences() && RequiresLatch)
+        continue;
+      if (HWLoopInfo.RequiresLatch)
+        continue;
+    }
+
+    const SCEV *EC = SE->getExitCount(L, BB);
     if (isa<SCEVCouldNotCompute>(EC))
       continue;
     if (const SCEVConstant *ConstEC = dyn_cast<SCEVConstant>(EC)) {
       if (ConstEC->getValue()->isZero())
         continue;
     } else if (!SE->isLoopInvariant(EC, L))
       continue;
 
     if (SE->getTypeSizeInBits(EC->getType()) >
         HWLoopInfo.CountType->getBitWidth())
       continue;
 
     // If this exiting block is contained in a nested loop, it is not eligible
     // for insertion of the branch-and-decrement since the inner loop would
     // end up messing up the value in the CTR.
-    if (!HWLoopInfo.IsNestingLegal && LI->getLoopFor(*I) != L &&
+    if (!HWLoopInfo.IsNestingLegal && LI->getLoopFor(BB) != L &&
         !ForceNestedLoop)
       continue;
 
     // We now have a loop-invariant count of loop iterations (which is not the
     // constant zero) for which we know that this loop will not exit via this
     // existing block.
 
     // We need to make sure that this block will run on every loop iteration.
for (pred_iterator PI = pred_begin(L->getHeader()),
         break;
       }
     }
 
     if (NotAlways)
       continue;
 
     // Make sure this blocks ends with a conditional branch.
-    Instruction *TI = (*I)->getTerminator();
+    Instruction *TI = BB->getTerminator();
     if (!TI)
       continue;
 
     if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
       if (!BI->isConditional())
         continue;
 
       HWLoopInfo.ExitBranch = BI;

lib/Target/ARM/ARMTargetTransformInfo.cpp

                                           TargetLibraryInfo *LibInfo,
                                           TTI::HardwareLoopInfo &HWLoopInfo) {
   // Low-overhead branches are only supported in the 'low-overhead branch'
   // extension of v8.1-m.
   if (!ST->hasLOB() || DisableLowOverheadLoops)
     return false;
 
   // For now, for simplicity, only support loops with one exit block.
   if (!L->getExitBlock())
     return false;
 
   if (!SE.hasLoopInvariantBackedgeTakenCount(L))
     return false;
 
   const SCEV *BackedgeTakenCount = SE.getBackedgeTakenCount(L);
   if (isa<SCEVCouldNotCompute>(BackedgeTakenCount))
     return false;

     return false;
 
   // TODO: Check whether the trip count calculation is expensive. If L is the
   // inner loop but we know it has a low trip count, calculating that trip
   // count (in the parent loop) may be detrimental.
 
   LLVMContext &C = L->getHeader()->getContext();
   HWLoopInfo.CounterInReg = true;
+  HWLoopInfo.RequiresLatch = true;
   HWLoopInfo.IsNestingLegal = false;
   HWLoopInfo.CountType = Type::getInt32Ty(C);
   HWLoopInfo.LoopDecrement = ConstantInt::get(HWLoopInfo.CountType, 1);
   return true;
 }
 
 void ARMTTIImpl::getUnrollingPreferences(Loop *L, ScalarEvolution &SE,
                                          TTI::UnrollingPreferences &UP) {

test/Transforms/HardwareLoops/ARM/structure.ll

while.cond1.while.end_crit_edge.us:
   %inc6.us = add nuw i32 %i.021.us, 1
   %exitcond23 = icmp eq i32 %inc6.us, %N
   br i1 %exitcond23, label %while.end7, label %while.cond1.preheader.us
 
 while.end7:
   ret void
 }
 
+; CHECK-LABEL: not_rotated
+; CHECK-NOT: call void @llvm.set.loop.iterations
+; CHECK-NOT: call i32 @llvm.loop.decrement.i32
+define void @not_rotated(i32, i16* nocapture, i16 signext) {
+  br label %4
+
+4:
+  %5 = phi i32 [ 0, %3 ], [ %19, %18 ]
+  %6 = icmp eq i32 %5, %0
+  br i1 %6, label %20, label %7
+
+7:
+  %8 = mul i32 %5, %0
+  br label %9
+
+9:
+  %10 = phi i32 [ %17, %12 ], [ 0, %7 ]
+  %11 = icmp eq i32 %10, %0
+  br i1 %11, label %18, label %12
+
+12:
+  %13 = add i32 %10, %8
+  %14 = getelementptr inbounds i16, i16* %1, i32 %13
+  %15 = load i16, i16* %14, align 2
+  %16 = add i16 %15, %2
+  store i16 %16, i16* %14, align 2
+  %17 = add i32 %10, 1
+  br label %9
+
+18:
+  %19 = add i32 %5, 1
+  br label %4
+
+20:
+  ret void
+}
+
 declare void @llvm.set.loop.iterations.i32(i32) #0
 declare i32 @llvm.loop.decrement.reg.i32.i32.i32(i32, i32) #0
 

test/Transforms/HardwareLoops/unconditional-latch.ll

+; RUN: opt -force-hardware-loops=true -hardware-loop-decrement=1 -hardware-loop-counter-bitwidth=32 -hardware-loops -S %s -o - | FileCheck %s --check-prefix=CHECK --check-prefix=CHECK-ALLOW
+; RUN: opt -force-hardware-loops=true -hardware-loop-decrement=1 -hardware-loop-counter-bitwidth=32 -hardware-loop-latch=true -hardware-loops -S %s -o - | FileCheck %s --check-prefix=CHECK --check-prefix=CHECK-LATCH
+
+; CHECK-LABEL: not_rotated
+; CHECK-LATCH-NOT: call void @llvm.set.loop.iterations
+; CHECK-LATCH-NOT: call i1 @llvm.loop.decrement
+
+; CHECK: 8:
+; CHECK-ALLOW: call void @llvm.set.loop.iterations.i32(i32 %4)
+; CHECK-ALLOW: br label %10
+; CHECK: 10:
+; CHECK-ALLOW: [[CMP:%[^ ]+]] = call i1 @llvm.loop.decrement.i32(i32 1)
+; CHECK-ALLOW: br i1 [[CMP]], label %13, label %19
+
+define void @not_rotated(i32, i16* nocapture, i16 signext) {
+  br label %4
+
+4:
+  %5 = phi i32 [ 0, %3 ], [ %19, %18 ]
+  %6 = icmp eq i32 %5, %0
+  br i1 %6, label %20, label %7
+
+7:
+  %8 = mul i32 %5, %0
+  br label %9
+
+9:
+  %10 = phi i32 [ %17, %12 ], [ 0, %7 ]
+  %11 = icmp eq i32 %10, %0
+  br i1 %11, label %18, label %12
+
+12:
+  %13 = add i32 %10, %8
+  %14 = getelementptr inbounds i16, i16* %1, i32 %13
+  %15 = load i16, i16* %14, align 2
+  %16 = add i16 %15, %2
+  store i16 %16, i16* %14, align 2
+  %17 = add i32 %10, 1
+  br label %9
+
+18:
+  %19 = add i32 %5, 1
+  br label %4
+
+20:
+  ret void
+}