[HardwareLoops] put +1 for loop count before zero extension

[shchenz]

Summary

Putting the +1 before the zero-extend will allow scalar evolution to fold the expression in some cases.

This issue is first tried in https://reviews.llvm.org/D91724 and seems there is some issue with that patch. This patch fixes the issues in that patch.

[reames]

llvm/lib/Analysis/TargetTransformInfo.cpp

171

You're using a variable called TripCount to store an ExitCount (e.g. BTC) before adding the appropriate offset. I strongly suggest using two variables.

179

There appears to be an unasserted assumption that CountType is of a wider type than the exitcount's type. The code structure does not make it clear this is true, at a minimum, please assert.

179

I'd suggest turning the pointer type check into an early return false unless you have a motivating case for the complexity. Pointer typed trip counts should be rare.

[reames]

llvm/lib/Analysis/TargetTransformInfo.cpp

186

Please use a comparison of the exit count against maximum unsigned value instead. The optimizer will probably turn it into the same, but the form you've written has potential interaction with SCEVs flag inference which is best avoided.

194

If you use getNoopOrZeroExtend, you don't need the explicit else case.

[shchenz]

address comments

[shchenz]

@reames Thanks for your review. Updated accordingly.

llvm/lib/Analysis/TargetTransformInfo.cpp

171

Good catch

179

The code already make sure that TripCount->getType() not bigger than CountType. See line 124 ~ 125 in the same function isHardwareLoopCandidate. But yeah, an assertion will be more clear here.

186

This was my first thought too. We can get the maximum num for ExitCount and if it is less than the maximum unsigned value for that type, we can safely do the +1. Unfortunately, for the case changes, they are all not such cases.

One case I was looking at is:

define dso_local signext i32 @testNestedPHI(i32 signext %cond, i32 signext %count, <512 x i1>* nocapture %ptr, <16 x i8> %vc) #1 {                     

for.body:                                         ; preds = %for.body.preheader, %for.body
  %i.011 = phi i32 [ %inc, %for.body ], [ 0, %for.body.preheader ]              
  %vq.110 = phi <512 x i1> [ %1, %for.body ], [ %vq.0, %for.body.preheader ]    
  %1 = tail call <512 x i1> @llvm.ppc.mma.xvf32gernp(<512 x i1> %vq.110, <16 x i8> %vc, <16 x i8> %vc)
  %inc = add nuw nsw i32 %i.011, 1                                              
  %exitcond.not = icmp eq i32 %inc, %count                                      
  br i1 %exitcond.not, label %for.cond.cleanup, label %for.body                 
}

SCEV for the ExitCount is %count - 1, bacause there is no wrap flag, so getRangeRef will return full-set as the range for ExitCount.

For ExitCount, I think we should add nuw flag for the above SCEV expression? But that should be out of this patch's scope?

194

Good idea.

[shchenz]

rebase and fix Lint warnings

[reames]

llvm/lib/Analysis/TargetTransformInfo.cpp

179

This is wrong. Please return false here instead, pointer typed trip counts should never happen.

186

To make sure I'm following you, you're saying that we manage to prove ExitCount != 0 in this example? That's interesting, I actually won't expect us to get that.

I'll drop the point about not checking for zero. Just be aware there is some risk there. The good news is that we're rapidly reducing that risk via work on pr51817.

llvm/lib/CodeGen/HardwareLoops.cpp

187–192

Please remove the white space diff. If you want to reflow the code, do so in a separate change.

200–208

Same.

386–387

Hm, hadn't noticed this before.

An actual trip count is never zero. This appears to have been trying to handle the overflow in BTC to TC conversion. I haven't looked at this to see what it's doing and why, but this is likely dead code now and you should understand why this was insufficient previously.

[shchenz]

address comments

llvm/lib/Analysis/TargetTransformInfo.cpp

179

Thanks. I am not aware that loop exit count can not be a pointer type. I change this to assert instead of returning false.

186

Yes, the case is from the below test changes. Now we can put +1 before the zero extend.

llvm/lib/CodeGen/HardwareLoops.cpp

187–192

I was doing this on purpose. Some Lint warnings are emitted for this patch after I rename ExitCount to TripCount. Should I fix the Lint warnings in this patch?

386–387

I don't think it is used to detect overflow in the original patch. It should be used to detect the possibility that the loop count can be zero. If it can not be a zero(for example, explicitly check the loop count and constant zero in the IR), some targets like ARM can use 'test and set' form loop count intrinsic, so that we can delete the explicitly check instruction in the IR. See one example in test/Transforms/HardwareLoops/loop-guards.ll @test6(). After the change, instruction %cmp = icmp ne i32 %N, 0 has no user.

For the previous bug in https://reviews.llvm.org/D91724, this check does not help. On PowerPC, there is no test and set form loop count intrinsic, so no matter what the result of isLoopEntryGuardedByCond is, UseLoopGuard is always false. And the loop count value may still be changed from umax_32 + 1(if we extend to u64) to 0 after D91724.

At last, yes, after this patch, this check should not be done two times. I have updated the patch.

[samparker]

llvm/lib/CodeGen/HardwareLoops.cpp

386–387

There's a comment of line 417 about this. I was trying to familiarise, again, with this code the other day and it confused me... SCEV didn't seem to help much here and so we use pattern matching in CanGenerateTest to achieve what we want. But yes, looks like dead code now.

[shchenz]

fix lint warning

[reames]

I posted a SCEV cleanup change inspired by this review. It shouldn't block this one. See https://reviews.llvm.org/D110587

llvm/lib/CodeGen/HardwareLoops.cpp

386–387

I'm not following this comment.

My best guess is that you believe that the trip count of a loop which is not entered is zero. This is not necessarily true. A trip count (as returned by SCEV) is the number of times the loop header is executed if the loop is reached. As such, a trip count is always 1 or greater.

[shchenz]

llvm/lib/CodeGen/HardwareLoops.cpp

386–387

Sorry for the confusion.

I was trying to explain why even with the guard isLoopEntryGuardedByCond, we still fail after committing D91724.

The check isLoopEntryGuardedByCond here will not stop the hardware loop pass to convert a loop to a hardware loop. And the trip count changing from umax_32 + 1(if we extend to u64) to 0 after D91724 is not impacted by this check. So that's why we still hit the bug on PowerPC.

We need to do this check when we put +1 before the extension.

[shchenz]

Hi @reames , do you have further comments for this patch? Thanks.

[reames]

In D109676#3039130, @shchenz wrote:

Hi @reames , do you have further comments for this patch? Thanks.

Sorry, your last response didn't parse for me. I know the SCEV side of this, but the client pieces are going over my head.

My general suggestion is to rebase over D110587 (which I'm about to land), and cleanup any downstream handling of zero trip counts separately.

We've about hit the limit of my ability to provide useful review on this, JFYI.

[shchenz]

In D109676#3055431, @reames wrote:

In D109676#3039130, @shchenz wrote:

Hi @reames , do you have further comments for this patch? Thanks.

Sorry, your last response didn't parse for me. I know the SCEV side of this, but the client pieces are going over my head.

My general suggestion is to rebase over D110587 (which I'm about to land), and cleanup any downstream handling of zero trip counts separately.

We've about hit the limit of my ability to provide useful review on this, JFYI.

Hi @reames , seems for this client side, Modified getTripCountFromExitCount in D110587 can not be used. getTripCountFromExitCount always return a wider type(1 bit larger than ExitCount->type size). Because of hardware loop counter register length limitation, the ExitCount->type must be not larger than loop counter register length(For example on 64-bit PowerPC, loop counter register length is 64-bit).
So without calling the API in D110587, we can use a i64 type ExitCount, if we can prove ExitCount + 1 does not overflow by calling isLoopEntryGuardedByCond. But if we call getTripCountFromExitCount with parameter Extend=true, the i64 exitcount/tripcount will be extended to i65 which is not a right loop counter type, so we can not use this i64 type ExitCount even it will not overflow after +1.

Thoughs? Please take your time.

[shchenz]

remove the dead code

[shchenz]

llvm/test/Transforms/HardwareLoops/scalar-while.ll

311–312

The test changes is due to isLoopEntryGuardedByCond can not determine that SCEV (1 + (-1 * %N) + %i) is at least 1 before. But now, we assume that the TripCount is at least 1 if we enter the loop. And we also check that TripCount will not overflow when we set TripCount.

[lebedev.ri]

Can't you teach SCEV::getAddExpr() that? (to fold zext(x)+C to zext(x+C) iff that doesn't alter the result: https://alive2.llvm.org/ce/z/5ZQ_X_)

[reames]

In D109676#3060551, @shchenz wrote:

Thoughs? Please take your time.

Proving that EC + 1 does not overflow is a proof that extension is not needed. The method has a boolean parameter for exactly that fact. It was written with exactly this case in mind.

[shchenz]

In D109676#3060697, @lebedev.ri wrote:

Can't you teach SCEV::getAddExpr() that? (to fold zext(x)+C to zext(x+C) iff that doesn't alter the result: https://alive2.llvm.org/ce/z/5ZQ_X_)

To prove zext(x)+C not overflow, we need to pass a parameter for a specific loop to SCEV::getAddExpr(), will it be a little strange? AddExpr should not be connected with any loop.

If you still think this is a requirement, I'd be happy to do this refactor in another patch.

[shchenz]

rebased based on D110587

[shchenz]

llvm/lib/Analysis/TargetTransformInfo.cpp

191

Legacy code also does not consider the overflow when ExitCount->getType() is same with CountType, since it works well on all platforms, so I think it should be OK to treat it as not overflow when SE.getTypeSizeInBits(ExitCount->getType()) == CountType->getBitWidth().

if (!ExitCount->getType()->isPointerTy() &&
    ExitCount->getType() != CountType)
  ExitCount = SE.getZeroExtendExpr(ExitCount, CountType);

ExitCount = SE.getAddExpr(ExitCount, SE.getOne(CountType));

[reames]

Removing self as reviewer. The SCEV change has been made and looks reasonable, the rest of the review requires context for the hardware loop detection feature I don't have.

[shchenz]

In D109676#3065312, @reames wrote:

Removing self as reviewer. The SCEV change has been made and looks reasonable, the rest of the review requires context for the hardware loop detection feature I don't have.

Thanks very much for your review about the SCEV part @reames

@samparker Hi Sam, do you think the change in HardwareLoop pass is reasonable especially the changes in the hardware loop test cases. Thanks in advance.

[samparker]

llvm/lib/Analysis/TargetTransformInfo.cpp

188

This comment is making me uneasy... I'm don't think target specific stuff should be referenced in this generic layer. But either way, why would a count register ever have a value of -1, especially when we're expending quite some effort to test against zero in this transform?

llvm/lib/CodeGen/HardwareLoops.cpp

416–417

Let's now remove this comment about isLoopEntryGuardedByCond.

llvm/test/Transforms/HardwareLoops/scalar-while.ll

311–312

These are minor regressions, but they're inline with the other previous sub-optimal cases so I think it's okay.

[shchenz]

llvm/lib/Analysis/TargetTransformInfo.cpp

188

PowerPC don't have test and set form. On PowerPC, if the count register is 0 before being decremented, it will be wrapped to -1(all bits are 1) afterward, so we can handle the overflow case when ExitCount type is same with CountType. The total loop count is u64_MAX + 1

But on other targets like ARM, the hardware loops pass handles the overflow case for ExitCount = SE.getAddExpr(ExitCount, SE.getOne(CountType)); when ExitCount type is same with CountType with test and set form? If this is the case, yes, the comments is not right, we need to update it for different targets.

But for all targets, making SE.getAddExpr(ExitCount, SE.getOne(CountType)); as not overflow when SE.getTypeSizeInBits(ExitCount->getType()) == CountType->getBitWidth() should be OK. Right?

llvm/lib/CodeGen/HardwareLoops.cpp

416–417

Thanks, will do this later.

llvm/test/Transforms/HardwareLoops/scalar-while.ll

311–312

Thanks for confirmation.

[shchenz]

address comments

[samparker]

llvm/lib/Analysis/TargetTransformInfo.cpp

188

Regardless of test.set support, all the intrinsics which set the counter use the trip count. So, if this is zero, as you're suggesting, the loop should never execute and so your counter should never be decremented to -1. What am I missing here? Could you point me at a test for an example?

The test.set forms, for ARM, are just so we can try to map on to 'while' loops and we can't presume anything in this method about test.set being successfully generated.

But for all targets, making SE.getAddExpr(ExitCount, SE.getOne(CountType)); as not overflow when SE.getTypeSizeInBits(ExitCount->getType()) == CountType->getBitWidth() should be OK. Right?

Yes, this sounds fine and I think this would be the only condition needed for the overflow check.

[shchenz]

llvm/lib/Analysis/TargetTransformInfo.cpp

188

Hi, let me describe the issue a little bit. Sorry for the long comment and appreciate your patience. @samparker

1. Without any change:

if (!ExitCount->getType()->isPointerTy() &&
    ExitCount->getType() != CountType)
  ExitCount = SE.getZeroExtendExpr(ExitCount, CountType);

ExitCount = SE.getAddExpr(ExitCount, SE.getOne(CountType));

Suppose CountType is i64

For ExitCount type smaller than i64, it will be zero-extended to i64, so there will be no overflow issue;
For ExitCount type same with i64, it will add one directly without checking overflow. This should be functionality right since no issue was found so far. Technically speaking, SE.getAddExpr(ExitCount, SE.getOne(CountType)); could be overflow if ExitCount is u64_max before adding one. This case can work right on PowerPC, because when TripCount(after adding one and overflow) is zero, the loop execution count is u64_max + 1 according to PowerPC count register semantic. So I guess other targets like ARM should have the same hardware behavior or there is some other place to handle the overflow zero case?

2. With the change in D91724:

TripCount = SE.getAddExpr(EC, SE.getOne(EC->getType()));

if (!EC->getType()->isPointerTy() && EC->getType() != CountType)
  TripCount = SE.getZeroExtendExpr(TripCount, CountType);

This is not right as we found regression pr51714 and the root cause was identified by Philip:
For narrower type, like i32, if ExitCount is u32_max before adding one, before the change(zero extend first and the add one), the loop count is u32_max + 1 (represented in i64), but after the change, the loop count is 0(overflow on type i32).
patch D91724 is not right.

3. Now with this patch D109676:

For ExitCount type smaller than i64, if we can prove that ExitCount + 1 will not overflow, we can put +1 before zero-extension. Otherwise, we have to first do zero-extension and then do +1;
For ExitCount type same with i64, according to the legacy logic, we can treat it as not-overflow even though it can be overflow technically. But like the above comments for Without any change, all targets can handle the overflow with some mechanism.

For your question:

So, if this is zero, as you're suggesting, the loop should never execute and so your counter should never be decremented to -1. What am I missing here? Could you point me at a test for an example?

I think the TripCount is zero if ExitCount is u64_max before adding one, so hardware loop pass will set hardware count register to 0 as the result of overflow on type i64, and on PowerPC this is a valid loop, the loop execution count is u64_max + 1. No test case in hand, I did some experiments on PowerPC, set loop count register to 0 and after the first decrement (bdnz instruction), the loop count register is changed to u64_max(0xffffffffffffffff, -1).

I think this would be the only condition needed for the overflow check.

Do you mean we don't need the isLoopEntryGuardedByCond for the overflow check? I think isLoopEntryGuardedByCond is still needed for types smaller than i64, otherwise, all smaller types are treated as WillNotOverflow and we will not zero extend the type in getTripCountFromExitCount, we may still meet the same issue with what we met in patch D91724?

[samparker]

llvm/lib/Analysis/TargetTransformInfo.cpp

188

Sigh, sorry, I forgot (again) that we haven't checked against ExitCount == UMAX . There's the static function 'mustBeFiniteCountedLoop' in PlaceSafePoints, maybe this could be moved somewhere so we could use it? Or has that kind of check already been tried? Sorry for my confusion and continued questioning.

[shchenz]

llvm/lib/Analysis/TargetTransformInfo.cpp

188

Haha, don't worry about your continued questions. They are making this patch be more reasonable and clear.

Here, we wouldn't get infinite loop error at least on PowerPC target. When the initial loop count register is 0, the loop execution count is u64_max + 1.

A typical pattern for a hardware loop on PowerPC is like this:

mtctr $gpr  ; move the loop count from $gpr to loop count regsiter CTR
loop_start:  ; start of loop header 
...   ; loop body
...
bdnz loop_start  ; loop latch

The semantic of the PowerPC bdnz instructions is "Decrement CTR and branch if it is still nonzero". So if the initial value is 0, after the first decrement, the loop count register is changed to 0xffffffffffffffff. and then after decrement 0xffffffffffffffff times, it will be changed to zero and then the loop is exiting.

Do we meet infinite loop issue on ARM? I think here we only care about overflow.

[samparker]

llvm/lib/Analysis/TargetTransformInfo.cpp

188

Okay, so I've tried going through the Arm spec and it's not immediately clear to me, so I have asked for some clarification. I suspect our behaviour is the same, but I will confirm once I know.

[samparker]

llvm/lib/Analysis/TargetTransformInfo.cpp

188

So, unfortunately it looks like the behaviour isn't the same as PPC. We only decrement the counter, and perform the backwards branch, if the counter has a value > 1. So setting our loop counter to a value of either zero or one, will result in a single trip and no backedge taken.

[samparker]

I would like to start a top-level discussion so everything isn't lost within the review comments, and pull in the Arm people who still work on this... @dmgreen @samtebbs

It appears as though PPC and Arm have different semantics for their loop backedge control. To summarize @shchenz, PPC will 'Decrement CTR and branch if it is still nonzero'. On Arm, AFAICT, we don't perform the decrement when the counter (LR) is <= 1.

So, do we need to tighten the semantics of the loop intrinsics for their overflow behaviour? Arm and PPC use different intrinsics so I can't see why defining them slightly differently would anyone.

[shchenz]

llvm/lib/Analysis/TargetTransformInfo.cpp

188

If so, would it be a potential issue even without this patch?

if (!ExitCount->getType()->isPointerTy() &&
    ExitCount->getType() != CountType)
  ExitCount = SE.getZeroExtendExpr(ExitCount, CountType);

ExitCount = SE.getAddExpr(ExitCount, SE.getOne(CountType));

If ExitCount type is same with CountType and ExitCount is UMAX before +1, after +1, it will be overflow and set to 0. For this case, does current behavior match ARM's hardware loop's expection?

[samparker]

llvm/lib/Analysis/TargetTransformInfo.cpp

188

Yes, it will cause us problems, which is why I think we probably need some better intrinsic semantics and varying logic here. With the current representation in the loop, we can't enter the loop with the counter (trip count) set to zero. This sounds, to me, rather sensible. I thought (and seemingly keep forgetting that it's not true) that this transform found 'countable' loops which would terminate, so that a trip count could have a max value of UMAX but ExitCount (BTC) could only ever reach UMAX - 1.

[dmgreen]

Everything tends to be i32's in Arm, so we only rarely see extends in the induction variables in the Hardware loop pass. Even if the IV was previously in i8/i16 it will likely already have been extended to a i32 by indvarsimplify.

In D109676#3077185, @samparker wrote:

I would like to start a top-level discussion so everything isn't lost within the review comments, and pull in the Arm people who still work on this... @dmgreen @samtebbs

It appears as though PPC and Arm have different semantics for their loop backedge control. To summarize @shchenz, PPC will 'Decrement CTR and branch if it is still nonzero'. On Arm, AFAICT, we don't perform the decrement when the counter (LR) is <= 1.

So, do we need to tighten the semantics of the loop intrinsics for their overflow behaviour? Arm and PPC use different intrinsics so I can't see why defining them slightly differently would anyone.

It's true we don't need to add 1 to the loop counter (if I'm understanding this correctly). When running our downstream benchmarks the only changes I saw from this patch is instructions that were in the preheader are now in the pre-preheader (the guard block). That makes things better or worse by ~1%, depending on the benchmark.

llvm/test/Transforms/HardwareLoops/scalar-while.ll

311–312

It's only small, but it does mean we execute more instructions if the branch is taken..

[shchenz]

In D109676#3083540, @dmgreen wrote:

Everything tends to be i32's in Arm, so we only rarely see extends in the induction variables in the Hardware loop pass. Even if the IV was previously in i8/i16 it will likely already have been extended to a i32 by indvarsimplify.

Thanks, that is the possible reason why we don't see any regressions after patch D91724 on ARM.

It's true we don't need to add 1 to the loop counter (if I'm understanding this correctly). When running our downstream benchmarks the only changes I saw from this patch is instructions that were in the preheader are now in the pre-preheader (the guard block). That makes things better or worse by ~1%, depending on the benchmark.

Thanks for your test on ARM. The performance impact should be small as it only affects the loop count expansion outside of the loop.

So for this patch, we need to wait for ARM experts find out the solution for overflow issue when ExitCount type is same with CountType?

llvm/test/Transforms/HardwareLoops/scalar-while.ll

311–312

Putting the loop count in pre-preheader is required by UseLoopGuard = true? If so, this should be positive, because now we use more loop guards?

[shchenz]

So for this patch, we need to wait for ARM experts find out the solution for the overflow issue when ExitCount type is same with CountType?

Not sure if there is any solution for the above issue? @samparker @dmgreen .

This patch is required by the PowerPC as it can generate better instructions shown in the test changes. And this should not introduce any regression on ARM, because the codes before this patch also have the potential issue. See https://reviews.llvm.org/D109676#3077240

So, is it possible to get this in first? Thanks in advance.

[shchenz]

gentle ping

[samparker]

As I said previously, the behaviour of the intrinsics should better defined and then this transform should adhere to those semantics. We're already using different pairs of intrinsics for each backend, so this shouldn't be a problem; however, we may have to ensure the Arm backend rejects the 'old' set.loop.iterations just to be safe.

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

 
 bool HardwareLoopInfo::isHardwareLoopCandidate(ScalarEvolution &SE,
                                                LoopInfo &LI, DominatorTree &DT,
                                                bool ForceNestedLoop,
                                                bool ForceHardwareLoopPHI) {
   SmallVector<BasicBlock *, 4> ExitingBlocks;
   L->getExitingBlocks(ExitingBlocks);
 
+  const SCEV *ExitCount = nullptr;
   for (BasicBlock *BB : ExitingBlocks) {
     // If we pass the updated counter back through a phi, we need to know
     // which latch the updated value will be coming from.
     if (!L->isLoopLatch(BB)) {
       if (ForceHardwareLoopPHI || CounterInReg)
         continue;
     }
 
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;
     break;
   }
 
   if (!ExitBlock)
     return false;
+
+  assert(ExitCount->getType()->isIntegerTy() &&
+         "Count type must be integer!\n");
+
+  assert((SE.getTypeSizeInBits(ExitCount->getType()) <=
+          CountType->getBitWidth()) &&
+         "Invalid loop count type!\n");
+
+  // Check if ExitCount + 1 will overflow.
+  // Please note, if the ExitCount type is same with CountType, we also treat it
+  // as not overflow. Hareware count register will handle the count 0 case well.
+  // For example, on PowerPC, if the value in the Count Register is 0 before
+  // being decremented, it is -1 afterward.
+  bool WillNotOverflow =
+      (SE.getTypeSizeInBits(ExitCount->getType()) ==
+       CountType->getBitWidth()) ||
+      SE.isLoopEntryGuardedByCond(
+          L, ICmpInst::ICMP_NE,
+          SE.getAddExpr(ExitCount, SE.getOne(ExitCount->getType())),
+          SE.getZero(ExitCount->getType()));
+
+  TripCount = SE.getTripCountFromExitCount(ExitCount, !WillNotOverflow);
+
+  assert((SE.getTypeSizeInBits(TripCount->getType()) <=
+          CountType->getBitWidth()) &&
+         "Invalid loop trip count!\n");
+
+  TripCount = SE.getNoopOrZeroExtend(TripCount, CountType);
+
   return true;
 }
 
 TargetTransformInfo::TargetTransformInfo(const DataLayout &DL)
     : TTIImpl(new Model<NoTTIImpl>(NoTTIImpl(DL))) {}
 
 TargetTransformInfo::~TargetTransformInfo() {}
 

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),
-      CountType(Info.CountType),
-      ExitBranch(Info.ExitBranch),
-      LoopDecrement(Info.LoopDecrement),
+                 const DataLayout &DL, OptimizationRemarkEmitter *ORE)
+        : SE(SE), DL(DL), ORE(ORE), L(Info.L), M(L->getHeader()->getModule()),
+          TripCount(Info.TripCount), CountType(Info.CountType),
+          ExitBranch(Info.ExitBranch), LoopDecrement(Info.LoopDecrement),
           UsePHICounter(Info.CounterInReg),
-      UseLoopGuard(Info.PerformEntryTest) { }
+          UseLoopGuard(Info.PerformEntryTest) {}
 
     void Create();
 
   private:
     ScalarEvolution &SE;
     const DataLayout &DL;
     OptimizationRemarkEmitter *ORE = nullptr;
-    Loop *L                 = nullptr;
-    Module *M               = nullptr;
-    const SCEV *ExitCount   = nullptr;
-    Type *CountType         = nullptr;
-    BranchInst *ExitBranch  = nullptr;
-    Value *LoopDecrement    = nullptr;
-    bool UsePHICounter      = false;
-    bool UseLoopGuard       = false;
-    BasicBlock *BeginBB     = nullptr;
+    Loop *L = nullptr;
+    Module *M = nullptr;
+    const SCEV *TripCount = nullptr;
+    Type *CountType = nullptr;
+    BranchInst *ExitBranch = nullptr;
+    Value *LoopDecrement = nullptr;
+    bool UsePHICounter = false;
+    bool UseLoopGuard = false;
+    BasicBlock *BeginBB = nullptr;
   };
 }
 
 char HardwareLoops::ID = 0;
 
 bool HardwareLoops::runOnFunction(Function &F) {
   if (skipFunction(F))
     return false;
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()))) {
-    LLVM_DEBUG(dbgs() << " - Attempting to use test.set counter.\n");
-    UseLoopGuard |= ForceGuardLoopEntry;
-  } else
-    UseLoopGuard = false;
+
 
+  // If we're trying to use the 'test and set' form of the intrinsic, it is
+  // likely (guaranteed?) that the preheader has an unconditional branch to the
+  // loop header, so also check if it has a single predecessor.
   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))
-        UseLoopGuard = false;
+    if (!isSafeToExpandAt(TripCount, Predecessor->getTerminator(), SE))
     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,
-                                     BB->getTerminator());
+  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.
+  // aren't needed.
 
   UseLoopGuard = UseLoopGuard && CanGenerateTest(L, Count);
   BeginBB = UseLoopGuard ? BB : L->getLoopPreheader();
   LLVM_DEBUG(dbgs() << " - Loop Count: " << *Count << "\n"
                     << " - Expanded Count in " << BB->getName() << "\n"
                     << " - Will insert set counter intrinsic into: "
                     << BeginBB->getName() << "\n");
   return Count;

llvm/test/CodeGen/PowerPC/loop-instr-prep-non-const-increasement.ll

 
 define i64 @foo(i8* %p, i32 signext %n, i32 signext %count) {
 ; CHECK-LABEL: foo:
 ; CHECK:       # %bb.0: # %entry
 ; CHECK-NEXT:    cmpwi r4, 1
 ; CHECK-NEXT:    blt cr0, .LBB0_4
 ; CHECK-NEXT:  # %bb.1: # %for.body.preheader
 ; CHECK-NEXT:    addi r6, r3, 5
-; CHECK-NEXT:    addi r3, r4, -1
+; CHECK-NEXT:    clrldi r3, r4, 32
 ; CHECK-NEXT:    extsw r5, r5
-; CHECK-NEXT:    clrldi r3, r3, 32
-; CHECK-NEXT:    addi r3, r3, 1
 ; CHECK-NEXT:    mtctr r3
 ; CHECK-NEXT:    li r3, 0
 ; CHECK-NEXT:    .p2align 5
 ; CHECK-NEXT:  .LBB0_2: # %for.body
 ; CHECK-NEXT:    #
 ; CHECK-NEXT:    ld r4, 0(r6)
 ; CHECK-NEXT:    add r3, r4, r3
 ; CHECK-NEXT:    ld r4, 4(r6)

 ; CHECK-LABEL: foo1:
 ; CHECK:       # %bb.0: # %entry
 ; CHECK-NEXT:    cmpwi r4, 1
 ; CHECK-NEXT:    blt cr0, .LBB1_4
 ; CHECK-NEXT:  # %bb.1: # %for.body.preheader
 ; CHECK-NEXT:    extsw r5, r5
 ; CHECK-NEXT:    sub r3, r3, r5
 ; CHECK-NEXT:    addi r6, r3, 1000
-; CHECK-NEXT:    addi r3, r4, -1
-; CHECK-NEXT:    clrldi r3, r3, 32
-; CHECK-NEXT:    addi r3, r3, 1
+; CHECK-NEXT:    clrldi r3, r4, 32
 ; CHECK-NEXT:    mtctr r3
 ; CHECK-NEXT:    li r3, 0
 ; CHECK-NEXT:    .p2align 4
 ; CHECK-NEXT:  .LBB1_2: # %for.body
 ; CHECK-NEXT:    #
 ; CHECK-NEXT:    lbzux r4, r6, r5
 ; CHECK-NEXT:    add r3, r4, r3
 ; CHECK-NEXT:    bdnz .LBB1_2

llvm/test/CodeGen/PowerPC/mma-phi-accs.ll

 ; CHECK-NEXT:    cmpwi r4, 1
 ; CHECK-NEXT:    bge cr0, .LBB3_3
 ; CHECK-NEXT:    b .LBB3_5
 ; CHECK-NEXT:  .LBB3_2:
 ; CHECK-NEXT:    # implicit-def: $acc0
 ; CHECK-NEXT:    cmpwi r4, 1
 ; CHECK-NEXT:    blt cr0, .LBB3_5
 ; CHECK-NEXT:  .LBB3_3: # %for.body.preheader
-; CHECK-NEXT:    addi r3, r4, -1
-; CHECK-NEXT:    clrldi r3, r3, 32
-; CHECK-NEXT:    addi r3, r3, 1
+; CHECK-NEXT:    clrldi r3, r4, 32
 ; CHECK-NEXT:    mtctr r3
 ; CHECK-NEXT:    .p2align 4
 ; CHECK-NEXT:  .LBB3_4: # %for.body
 ; CHECK-NEXT:    #
 ; CHECK-NEXT:    xvf32gernp acc0, v2, v2
 ; CHECK-NEXT:    bdnz .LBB3_4
 ; CHECK-NEXT:  .LBB3_5: # %for.cond.cleanup
 ; CHECK-NEXT:    li r3, 0

 ; CHECK-BE-NEXT:    cmpwi r4, 1
 ; CHECK-BE-NEXT:    bge cr0, .LBB3_3
 ; CHECK-BE-NEXT:    b .LBB3_5
 ; CHECK-BE-NEXT:  .LBB3_2:
 ; CHECK-BE-NEXT:    # implicit-def: $acc0
 ; CHECK-BE-NEXT:    cmpwi r4, 1
 ; CHECK-BE-NEXT:    blt cr0, .LBB3_5
 ; CHECK-BE-NEXT:  .LBB3_3: # %for.body.preheader
-; CHECK-BE-NEXT:    addi r3, r4, -1
-; CHECK-BE-NEXT:    clrldi r3, r3, 32
-; CHECK-BE-NEXT:    addi r3, r3, 1
+; CHECK-BE-NEXT:    clrldi r3, r4, 32
 ; CHECK-BE-NEXT:    mtctr r3
 ; CHECK-BE-NEXT:    .p2align 4
 ; CHECK-BE-NEXT:  .LBB3_4: # %for.body
 ; CHECK-BE-NEXT:    #
 ; CHECK-BE-NEXT:    xvf32gernp acc0, v2, v2
 ; CHECK-BE-NEXT:    bdnz .LBB3_4
 ; CHECK-BE-NEXT:  .LBB3_5: # %for.cond.cleanup
 ; CHECK-BE-NEXT:    li r3, 0

llvm/test/Transforms/HardwareLoops/loop-guards.ll

 if.end:                                           ; preds = %do.body, %entry
   ret void
 }
 
 ; CHECK-LABEL: test4
 ; CHECK: entry:
 ; CHECK-LATCH:  br i1 %brmerge.demorgan, label %while.cond
 ; CHECK-LATCH-NOT: @llvm{{.*}}loop.iterations 
+; CHECK-EXIT:   [[COUNT:%[^ ]+]] = add i32 %N, 1
 ; CHECK-EXIT:   br i1 %brmerge.demorgan, label %while.cond.preheader
 ; CHECK-EXIT: while.cond.preheader:
-; CHECK-EXIT:   [[COUNT:%[^ ]+]] = add i32 %N, 1
 ; CHECK-EXIT:   call void @llvm.set.loop.iterations.i32(i32 [[COUNT]])
 ; CHECK-EXIT:   br label %while.cond
 define void @test4(i1 zeroext %t1, i1 zeroext %t2, i32* nocapture %a, i32* nocapture readonly %b, i32 %N) {
 entry:
   %brmerge.demorgan = and i1 %t1, %t2
   br i1 %brmerge.demorgan, label %while.cond, label %if.end
 
 while.cond:                                       ; preds = %while.body, %entry

llvm/test/Transforms/HardwareLoops/scalar-while.ll

 ; CHECK-NESTED-NEXT:    [[TMP2:%.*]] = call i1 @llvm.loop.decrement.i32(i32 1)
 ; CHECK-NESTED-NEXT:    br i1 [[TMP2]], label [[WHILE_BODY]], label [[WHILE_END]]
 ; CHECK-NESTED:       while.end:
 ; CHECK-NESTED-NEXT:    ret void
 ;
 ; CHECK-GUARD-LABEL: @while_gte(
 ; CHECK-GUARD-NEXT:  entry:
 ; CHECK-GUARD-NEXT:    [[CMP4:%.*]] = icmp slt i32 [[I:%.*]], [[N:%.*]]
-; CHECK-GUARD-NEXT:    br i1 [[CMP4]], label [[WHILE_END:%.*]], label [[WHILE_BODY_PREHEADER:%.*]]
-; CHECK-GUARD:       while.body.preheader:
 ; CHECK-GUARD-NEXT:    [[TMP0:%.*]] = add i32 [[I]], 1
 ; CHECK-GUARD-NEXT:    [[TMP1:%.*]] = sub i32 [[TMP0]], [[N]]
+; CHECK-GUARD-NEXT:    br i1 [[CMP4]], label [[WHILE_END:%.*]], label [[WHILE_BODY_PREHEADER:%.*]]
+; CHECK-GUARD:       while.body.preheader:
 ; CHECK-GUARD-NEXT:    call void @llvm.set.loop.iterations.i32(i32 [[TMP1]])
 ; CHECK-GUARD-NEXT:    br label [[WHILE_BODY:%.*]]
 ; CHECK-GUARD:       while.body:
 ; CHECK-GUARD-NEXT:    [[I_ADDR_05:%.*]] = phi i32 [ [[DEC:%.*]], [[WHILE_BODY]] ], [ [[I]], [[WHILE_BODY_PREHEADER]] ]
 ; CHECK-GUARD-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds i32, i32* [[A:%.*]], i32 [[I_ADDR_05]]
 ; CHECK-GUARD-NEXT:    store i32 [[I_ADDR_05]], i32* [[ARRAYIDX]], align 4
 ; CHECK-GUARD-NEXT:    [[DEC]] = add nsw i32 [[I_ADDR_05]], -1
 ; CHECK-GUARD-NEXT:    [[TMP2:%.*]] = call i1 @llvm.loop.decrement.i32(i32 1)
 ; CHECK-GUARD-NEXT:    br i1 [[TMP2]], label [[WHILE_BODY]], label [[WHILE_END]]
 ; CHECK-GUARD:       while.end:
 ; CHECK-GUARD-NEXT:    ret void
 ;
 ; CHECK-PHIGUARD-LABEL: @while_gte(
 ; CHECK-PHIGUARD-NEXT:  entry:
 ; CHECK-PHIGUARD-NEXT:    [[CMP4:%.*]] = icmp slt i32 [[I:%.*]], [[N:%.*]]
-; CHECK-PHIGUARD-NEXT:    br i1 [[CMP4]], label [[WHILE_END:%.*]], label [[WHILE_BODY_PREHEADER:%.*]]
-; CHECK-PHIGUARD:       while.body.preheader:
 ; CHECK-PHIGUARD-NEXT:    [[TMP0:%.*]] = add i32 [[I]], 1
 ; CHECK-PHIGUARD-NEXT:    [[TMP1:%.*]] = sub i32 [[TMP0]], [[N]]
+; CHECK-PHIGUARD-NEXT:    br i1 [[CMP4]], label [[WHILE_END:%.*]], label [[WHILE_BODY_PREHEADER:%.*]]
+; CHECK-PHIGUARD:       while.body.preheader:
 ; CHECK-PHIGUARD-NEXT:    [[TMP2:%.*]] = call i32 @llvm.start.loop.iterations.i32(i32 [[TMP1]])
 ; CHECK-PHIGUARD-NEXT:    br label [[WHILE_BODY:%.*]]
 ; CHECK-PHIGUARD:       while.body:
 ; CHECK-PHIGUARD-NEXT:    [[I_ADDR_05:%.*]] = phi i32 [ [[DEC:%.*]], [[WHILE_BODY]] ], [ [[I]], [[WHILE_BODY_PREHEADER]] ]
 ; CHECK-PHIGUARD-NEXT:    [[TMP3:%.*]] = phi i32 [ [[TMP2]], [[WHILE_BODY_PREHEADER]] ], [ [[TMP4:%.*]], [[WHILE_BODY]] ]
 ; CHECK-PHIGUARD-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds i32, i32* [[A:%.*]], i32 [[I_ADDR_05]]
 ; CHECK-PHIGUARD-NEXT:    store i32 [[I_ADDR_05]], i32* [[ARRAYIDX]], align 4
 ; CHECK-PHIGUARD-NEXT:    [[DEC]] = add nsw i32 [[I_ADDR_05]], -1