[HardwareLoops] Change order of SCEV expression construction for InitLoopCount.

[JanekvO]

Summary

Putting the +1 before the zero-extend will allow scalar evolution to fold the expression in some cases such as the one shown in PowerPC's shrink-wrap.ll test.

[samparker]

LGTM, thanks!

[samparker]

Out of curiosity, did you try performing the +1 in HardwareLoopInfo::isHardwareLoopCandidate instead? Looking back through the code, I think it would be more clear to rename 'ExitCount' to 'TripCount' and perform this addition outside of the pass.

[JanekvO]

In D91724#2404880, @samparker wrote:

Out of curiosity, did you try performing the +1 in HardwareLoopInfo::isHardwareLoopCandidate instead? Looking back through the code, I think it would be more clear to rename 'ExitCount' to 'TripCount' and perform this addition outside of the pass.

I hadn't considered the +1 in isHardwareLoopCandidate until you mentioned it. I can add these changes in this diff, but I wonder whether the zero-extend should also be moved to isHardwareLoopCandidate at this point. That way only the uses of ExitCount (or TripCount, after renaming) will remain in the pass (as far as I can see).

[samparker]

I wonder whether the zero-extend should also be moved to isHardwareLoopCandidate at this point.

Nice, sounds good to me.

[samparker]

llvm/lib/CodeGen/HardwareLoops.cpp

385–386

Could you also double check that this PointerTy check is necessary, it seems a little odd to me but I don't know much about the PPC implementation.

[JanekvO]

Rename ExitCount to TripCount and move SCAV expression construction outside of HardwareLoops pass into isHardwareLoopCandidate.

[JanekvO]

Diff against HEAD

[JanekvO]

Sorry, one more try to diff against the right branch

[JanekvO]

llvm/lib/CodeGen/HardwareLoops.cpp

385–386

I did a quick check and removed the PointerTy check and it seems all tests still run fine. However, I don't know enough about either PPC nor scalar evolution to confidently remove the check. Intuitively, it sounds unlikely for getExitCount to return a pointer type but I'm not sure.

[samparker]

Intuitively, it sounds unlikely for getExitCount to return a pointer type but I'm not sure.

Indeed, thanks for checking. LGTM, thanks.

[reames]

Glanced at this due to being CCed on pr51714.

This patch does not look correct on first glance. If backedge taken count is UINT_MAX for the narrower type, doing the increment in the narrow type produces zext(0) e.g. zero, whereas doing the zext(BTC)+1 does not. Unless there's something in the code which prevents BTC=UINT_MAX/TC=0, I suspect that's the cause of the miscompile being observed in that bug and this patch should be reverted.

[shchenz]

In D91724#2981131, @reames wrote:

Glanced at this due to being CCed on pr51714.

This patch does not look correct on first glance. If backedge taken count is UINT_MAX for the narrower type, doing the increment in the narrow type produces zext(0) e.g. zero, whereas doing the zext(BTC)+1 does not. Unless there's something in the code which prevents BTC=UINT_MAX/TC=0, I suspect that's the cause of the miscompile being observed in that bug and this patch should be reverted.

Thanks @reames
reverted in 34badc409cc452575c538c4b6449546adc38f121

[samparker]

Unless there's something in the code which prevents BTC=UINT_MAX/TC=0

And I thought there was!

Thanks both.

llvm/include/llvm/Analysis/TargetTransformInfo.h

 
 /// 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;
+  const SCEV *TripCount = nullptr;
   IntegerType *CountType = nullptr;
   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?
   bool CounterInReg = false;      // Should loop counter be updated in
                                   // the loop via a phi?
   bool PerformEntryTest = false;  // Generate the intrinsic which also performs

llvm/lib/Analysis/TargetTransformInfo.cpp

if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
 
       ExitBranch = BI;
     } else
       continue;
 
     // Note that this block may not be the loop latch block, even if the loop
     // has a latch block.
     ExitBlock = BB;
-    ExitCount = EC;
+    TripCount = SE.getAddExpr(EC, SE.getOne(EC->getType()));
+
+    if (!EC->getType()->isPointerTy() && EC->getType() != CountType)
+      TripCount = SE.getZeroExtendExpr(TripCount, CountType);
+
     break;
   }
 
   if (!ExitBlock)
     return false;
   return true;
 }
 

llvm/lib/CodeGen/HardwareLoops.cpp

class HardwareLoop {
     PHINode *InsertPHICounter(Value *NumElts, Value *EltsRem);
 
     // Create a new cmp, that checks the returned value of loop_decrement*,
     // and update the exit branch to use it.
     void UpdateBranch(Value *EltsRem);
 
   public:
     HardwareLoop(HardwareLoopInfo &Info, ScalarEvolution &SE,
                  const DataLayout &DL,
                  OptimizationRemarkEmitter *ORE) :
       SE(SE), DL(DL), ORE(ORE), L(Info.L), M(L->getHeader()->getModule()),
-      ExitCount(Info.ExitCount),
+      TripCount(Info.TripCount),
       CountType(Info.CountType),
       ExitBranch(Info.ExitBranch),
       LoopDecrement(Info.LoopDecrement),
       UsePHICounter(Info.CounterInReg),
       UseLoopGuard(Info.PerformEntryTest) { }
 
     void Create();
 
   private:
     ScalarEvolution &SE;
     const DataLayout &DL;
     OptimizationRemarkEmitter *ORE = nullptr;
     Loop *L                 = nullptr;
     Module *M               = nullptr;
-    const SCEV *ExitCount   = nullptr;
+    const SCEV *TripCount   = nullptr;
     Type *CountType         = nullptr;
     BranchInst *ExitBranch  = nullptr;
     Value *LoopDecrement    = nullptr;
     bool UsePHICounter      = false;
     bool UseLoopGuard       = false;
     BasicBlock *BeginBB     = nullptr;
   };
 }
if (!HWLoopInfo.isHardwareLoopCandidate(*SE, *LI, *DT, ForceNestedLoop,
     // TODO: there can be many reasons a loop is not considered a
     // candidate, so we should let isHardwareLoopCandidate fill in the
     // reason and then report a better message here.
     reportHWLoopFailure("loop is not a candidate", "HWLoopNoCandidate", ORE, L);
     return false;
   }
 
   assert(
-      (HWLoopInfo.ExitBlock && HWLoopInfo.ExitBranch && HWLoopInfo.ExitCount) &&
+      (HWLoopInfo.ExitBlock && HWLoopInfo.ExitBranch && HWLoopInfo.TripCount) &&
       "Hardware Loop must have set exit info.");
 
   BasicBlock *Preheader = L->getLoopPreheader();
 
   // If we don't have a preheader, then insert one.
   if (!Preheader)
     Preheader = InsertPreheaderForLoop(L, DT, LI, nullptr, PreserveLCSSA);
   if (!Preheader)
static bool CanGenerateTest(Loop *L, Value *Count) {
   return true;
 }
 
 Value *HardwareLoop::InitLoopCount() {
   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);
-
-  ExitCount = SE.getAddExpr(ExitCount, SE.getOne(CountType));
 
   // If we're trying to use the 'test and set' form of the intrinsic, we need
   // to replace a conditional branch that is controlling entry to the loop. It
   // is likely (guaranteed?) that the preheader has an unconditional branch to
   // the loop header, so also check if it has a single predecessor.
-  if (SE.isLoopEntryGuardedByCond(L, ICmpInst::ICMP_NE, ExitCount,
-                                  SE.getZero(ExitCount->getType()))) {
+  if (SE.isLoopEntryGuardedByCond(L, ICmpInst::ICMP_NE, TripCount,
+                                  SE.getZero(TripCount->getType()))) {
     LLVM_DEBUG(dbgs() << " - Attempting to use test.set counter.\n");
     UseLoopGuard |= ForceGuardLoopEntry;
   } else
     UseLoopGuard = false;
 
   BasicBlock *BB = L->getLoopPreheader();
   if (UseLoopGuard && BB->getSinglePredecessor() &&
       cast<BranchInst>(BB->getTerminator())->isUnconditional()) {
     BasicBlock *Predecessor = BB->getSinglePredecessor();
     // If it's not safe to create a while loop then don't force it and create a
     // do-while loop instead
-    if (!isSafeToExpandAt(ExitCount, Predecessor->getTerminator(), SE))
+    if (!isSafeToExpandAt(TripCount, Predecessor->getTerminator(), SE))
         UseLoopGuard = false;
     else
         BB = Predecessor;
   }
 
-  if (!isSafeToExpandAt(ExitCount, BB->getTerminator(), SE)) {
-    LLVM_DEBUG(dbgs() << "- Bailing, unsafe to expand ExitCount "
-               << *ExitCount << "\n");
+  if (!isSafeToExpandAt(TripCount, BB->getTerminator(), SE)) {
+    LLVM_DEBUG(dbgs() << "- Bailing, unsafe to expand TripCount "
+               << *TripCount << "\n");
     return nullptr;
   }
 
-  Value *Count = SCEVE.expandCodeFor(ExitCount, CountType,
+  Value *Count = SCEVE.expandCodeFor(TripCount, CountType,
                                      BB->getTerminator());
 
   // 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.

llvm/test/CodeGen/PowerPC/shrink-wrap.ll

 ; CHECK-NEXT:    cmpwi
 ; Prolog code
 ; CHECK:         std 
 ; CHECK:         std 
 ; CHECK:         std 
 ; CHECK:         std 
 ; CHECK:         blt 0, .LBB0_3
 ; CHECK:       # %bb.1:
-; CHECK-NEXT:    addi
 ; CHECK-NEXT:    clrldi
-; CHECK-NEXT:    addi
 ; CHECK-NEXT:    mtctr
 ; CHECK-NEXT:    li 
 ; CHECK:       .LBB0_2: 
 ; CHECK:         add
 ; CHECK:         bdnz .LBB0_2 
 ; CHECK-NEXT:    b .LBB0_4
 ; CHECK:       .LBB0_3: 
 ; CHECK-NEXT:    li