[SimpleLoopBoundSplit] Split Bound of Loop which has conditional branch with IV

[jaykang10]

Summary

This pass transforms loops that contain a conditional branch with induction variable. For example, it transforms left code to right code:

                            newbound = min(n, c)
while (iv < n) {            while(iv < newbound) {
  A                           A
  if (iv < c)                 B
    B                         C
  C                         }
}                           if (iv != n) {
                              while (iv < n) {
                                A
                                C
                              }
                            }

[mkazantsev]

This comment has been deleted.

llvm/lib/Transforms/Scalar/SimpleLoopBoundSplit.cpp

46

Why signed only? TODO unsigned?

62

I think this is a natural place where you could apply PatternMatch.

72

Assert that one of them is an addrec and another is available at loop entry?

75

It looks natural to encapsulate Pred, AddRec, Bound and nowrap flags into a structure (e.g. some BoundInfo) and pass const BoundInfo & here. WDYT?

92

1. Why do you prefer signed predicates over unsigned? Other parts of LLVM (e.g. indvars) tend to canonicalize everything as unsigned if they can prove it.
2. Isn't AddRecSCEV->hasNoSignedWrap() a same thing as HasNoSignedWrap? If so, remove one of them.

102

1. This is just wrong, it should be AddRec < Bound + 1.
2. It is only correct if you can prove that Bound + 1 does not overflow. Simple exapmle is X <= SINT_MAX --> X < SINT_MIN is wrong.

120

Check isAffine before it to save compile time in case of really complex AddRecs.

127

I understand that zero step is impossible, but still, being negative and being non-positive is't the same thing is general. :)

131

1. This check makes the check above meaningless.
2. Reading the code, I think the only place where it matters is replacing Eq condition with Lt. Do we beed this for something else?
3. Please add a TODO to add negative step support. We've stuggled a lot with it in IndVars, and I see this pain coming again.

139

Check this before you construct SCEVs to save compile time.

160

It's innermost loop, so I thing "recursive" check is an overkill. Or do we plan to support outer loops for it?

168

This is a very restrictive thing. Why is it required?

174

Use pattern match.

185

Pls add /*IsExitCond*/

220

Logicaly, this check should go last. You may discard the candidate by conditions below.
Anyways, why is that a problem at all? If we have at least one candidate we can get rid of it and then proceed with the other ones.

229

Why not continue?

232

Break?

239

Do we ever check they are against the same AddRec?
If it's supposed to be same, I think we can just assert on it.
If not, I'm not catching how the rest of logic is going to work.

244

I think it's a too strong statement. Getting rid of a branch in a critical loop may be useful even without vectorization. If you want to be that restrictive, place add an option to ignore this check.

263

any_of?
I believe we don't vectorize volatile load/stores (or do we?) Maybe check at least this.
It looks like the transform is also profitable if one of these instructions is side exiting. We don't vectorize them so far, but if you get rid of it, the loop may become vectorizable.

273

It looks like it can be an utility function usable by other parts of LLVM. Consider factoring it out.

337

Same question about preference of signed over unsigned. LLVM does otherwise in other parts. Let's not create more self-contradictions.

411

This can be expensive. Can't we do a more surgical update?

I'm fine if it's a TODO with follow-up fix.

435

Please verify loop info too.

[mkazantsev]

General question: does this pass do something that IRCE doesn't? From what I've read, it looks a very limited version of InductiveRangeCheckElimination, with only difference that it works for non-loop-existing conditions.

Maybe what you are looking for is to add a flag into IRCE that it works with such conditions.

[jaykang10]

In D102234#2758839, @mkazantsev wrote:

General question: does this pass do something that IRCE doesn't? From what I've read, it looks a very limited version of InductiveRangeCheckElimination, with only difference that it works for non-loop-existing conditions.

Maybe what you are looking for is to add a flag into IRCE that it works with such conditions.

@mkazantsev I appreciate your comments. I will update code following them.

Yep, you are right. It is a limited version of IRCE pass. For the first time, I tried to extend IRCE pass with extending SCEV or changing the population order of loop in new pass manager in order to handle my motivational examples. You can see the discussion with below patches.
https://reviews.llvm.org/D101409
https://reviews.llvm.org/D100566
https://reviews.llvm.org/D99774

During discussion, @reames recommended to write a limited pass to handle my motivational example rather than extending IRCE pass because he feels IRCE pass has some problems and it is overkill to handle my motivational example. You can see the discussion with below email thread.
https://lists.llvm.org/pipermail/llvm-dev/2021-April/150281.html

I am aiming to enable transformation like IRCE pass or something like that in the pipeline of new pass manager. If it is possible to enable IRCE pass in the pipeline of new pass manager, I am OK to add the new flag to IRCE pass. If it is not possible, I would try to write transformation pass like this patch or alternative which can be accepted into upstream.

[mkazantsev]

Got it, thanks. The biggest problem IRCE has is how it's written. So indeed, if we can make a simpler version of this, and then expand it to be as powerful as IRCE, that might be a better approach.

[SjoerdMeijer]

Some drive by comments:

• Bike shedding names: SimpleLoopBoundSplit. How about just LoopBoundSplit? I understand the current implementation has restrictions/limitations, but personally I think it looks a bit silly all these SimpleLoopXYZ passes/names.
• You probably want to add this to the optimisation pipeline somewhere, off by default for now,
• I guess we want to skip with this transformation with OptForSize,
• I haven't looked into much details, but I guess you look only at one if-statement and thus we don't support things like if ( i > c1 && i < c2)?

[jaykang10]

In D102234#2762711, @SjoerdMeijer wrote:

Some drive by comments:

@SjoerdMeijer Thanks for comments.

• Bike shedding names: SimpleLoopBoundSplit. How about just LoopBoundSplit? I understand the current implementation has restrictions/limitations, but personally I think it looks a bit silly all these SimpleLoopXYZ passes/names.

Yep, I am ok with the name. I just imitated the LoopUnswitch and SimpleLoopUnswitchPass because this pass is a limited version of IRCE.

• You probably want to add this to the optimisation pipeline somewhere, off by default for now,

Yep, I have enabled this pass after SimpleLoopUnswitch experimentally and I am checking the impact from benchmarks. It seems the isProfitableToTransform needs to be updated.

• I guess we want to skip with this transformation with OptForSize,

Yep, it is already being checked with below code.

// Skip function with optsize.
if (L.getHeader()->getParent()->hasOptSize())
  return false;

• I haven't looked into much details, but I guess you look only at one if-statement and thus we don't support things like if ( i > c1 && i < c2)?

At this stage, I am aiming this pass as simple as possible. As @reames mentioned on the email discussion, it is very hard to generalize the cases. Later, we could create new transformation passes or extend this pass to handle more cases as @mkazantsev mentioned.

[jaykang10]

llvm/lib/Transforms/Scalar/SimpleLoopBoundSplit.cpp

46

You are right! I will add unsigned one too.

62

Sorry... I am not sure how I can use PatternMatch to extract information from ICmp instruction...

72

The AddRec is checked on HasProcessableCondition. I will add code to check whether the bound is available at loop entry on HasProcessableCondition.

75

Yep, you are right. I could pass the ConditionInfo directly. I will update it.

92

1. Why do you prefer signed predicates over unsigned? Other parts of LLVM (e.g. indvars) tend to canonicalize everything as unsigned if they can prove it.

I just tried to follow the AddRec's flag. I will update the code with unsigned one.

2. Isn't AddRecSCEV->hasNoSignedWrap() a same thing as HasNoSignedWrap? If so, remove one of them.

Yep, I will remove the AddRecSCEV->hasNoSignedWrap().

102

1. This is just wrong, it should be AddRec < Bound + 1.

Oops, sorry. I will update it.

2. It is only correct if you can prove that Bound + 1 does not overflow. Simple exapmle is X <= SINT_MAX --> X < SINT_MIN is wrong.

You are right!!! I will add code to check the overflow.

120

Yep, I will check it.

127

Yep, I will check zero step too.

131

1. This check makes the check above meaningless.

I agree.

2. Reading the code, I think the only place where it matters is replacing Eq condition with Lt. Do we beed this for something else?

No, it is for the EQ condition. I will update code to check the one step with EQ condition.

3. Please add a TODO to add negative step support. We've stuggled a lot with it in IndVars, and I see this pain coming again.

Yep, I will add the TODO for negative step.

139

um... I think we need to check it after CalculateUpperBoundWithLT in order to check only LT condition... We could add more conversions of conditions like 'EQ` --> LT', LE' --> LT later. If I missed something, please let me know.

160

You are right!!! I will update it with isLCSSAForm.

168

I wanted to make this pass as simple as possible at this stage to figure out basic problems. If we support multiple exiting blocks, we could have to consider below things.

1. Multiple exit conditions
2. We could need more min/max operations to create new bounds.
3. Update first loop's exit blocks to preheader of second loop.

There could be something more to be considered.
If possible, I would like to consider multiple exits after finishing to support single exit.

174

Yep, I will update it with pattern match.

185

Yep, I will update it.

220

It is not problem. As I mentioned before, I wanted to make this pass as simple as possible at this stage to figure out basic problems. I will remove this check.

229

Oops, You are right!!! I will update it.

232

It was to avoid multiple split candidates. I will add break.

239

You are right. It is supposed to be same. However, we can not compare the AddRec directly because the AddRec of exit cond is different with split candidate's one because inc++ is followed by exit cond. The start value of AddRec is different as below.

ExitCond AddRec
{1,+,1}<nuw><nsw><%loop>

SplitCandidateCond AddRec
{0,+,1}<nuw><nsw><%loop>

I think we have checked the step of AddRec and need to check its start value and signedness more to say they are same AddRec. I forgot to check the start value. I will add the check. If I missed something or you feel something wrong, please let me know.

244

Yep, you are right. I will remove this check. I am checking performance impact with this pass. Maybe, I could add something more here.

263

any_of?
I believe we don't vectorize volatile load/stores (or do we?) Maybe check at least this.

Yep, I will update it.

It looks like the transform is also profitable if one of these instructions is side exiting. We don't vectorize them so far, but if you get rid of it, the loop may become vectorizable.

um... if the condition of the side exit is related to induction variable, we could handle it.

273

Once the basic version of this pass is stabilized, I would consider it.

337

Yep, I will update it.

411

Yep, I will add TODO and try to fix it later.

435

Yep, I will update it.

[jaykang10]

Following the comments of @mkazantsev, updated code.

[reames]

I want to make a very high level suggestion on this. This isn't really about the code per se, and more about the approach to writing the code.

I'd start with a really trivially transform for the loop:
for (i = 0; i < N; i++) { body }

Build a mechanism to produce a form which looks like so:
for (i = 0; i < N; i++) { body }
if (i != N) {

for (; i < N; i++) { body }

}

This should (rightfully) look fairly odd as the second loop is dead. However, once we have that, iteration splitting becomes much more straight forward. A few observations:

• The "if (i != N)" is a loop guard and can be identified by getLoopGuardBranch.
• N is the exit value of the i addrec, and can be gotten from SCEV for any arbitrary AddRec for a known exit count.

Once we have this form, we can restrict the iteration space of the pre-loop without modifying the post loop at all. (Provided we haven't run any optimization in between. A slightly safer form would be to have the guard condition be an unknown value to prevent accidental optimization.)

The next core primitive is a routine which uses an Exact Exit Count (as defined in SCEV today) to *reduce* the number of iterations in a loop. A key thing to note is that mutating existing IR is an optimization, but the routine is always allowed to introduce a new IV and clamp if needed. That helps a lot in making the code robust. Being able to use SCEVAddRecExpr::evaluateAtIteration also helps to simplify things a lot.

The final primitive is to generalize the existing exit count logic to work for when an arbitrary monotonic condition toggles. (There's a bunch of ways of computing an "exit" count for the branch of interest. This is merely one.)

Once we have both of those, we'd

1. Determine if splitting is worthwhile. Pick a set of branches to eliminate. (Must be able to compute "exit" counts.)
2. Produce dead loop form
3. For each branch we want to remove from the pre-loop, compute an "exit" count.
4. Then constrain the preloop by the umin of all the desired exit counts.
5. Simplify branches out of pre-loop. Leave all generality of control flow in preloop.

Note carefully what this approach *doesn't* do. It doesn't require the pass (as opposed to scev) to reason about conditions, signed vs unsigned, overflow, or whether two IVs are congruent. It heavily reuses the existing logic in SCEV which (mostly) gets all those cases right already.

This works for any condition which is "monotonic" (e.g. transitions from true to false (or vice versa) at most once in the original iteration space). It does not work for branch conditions which can transition or more times without a bit more generalization.

Where this approach fails a bit is in handling multiple branches to be pruned. As described above, it runs the preloop until *any* of the conditions are hit, and then the post-loop for the remainder. That may or may not have been what was desired.

I think this approach can be used to formulate IRCE, but it requires a bit of care for the case where you don't know an index is in bounds or not on the first iteration.

For a profitability check, I'd start specifically with the case where the condition precisely splits a loop into two halves. e.g. for ... { if (C) { body1 } else { body2 }. This is the easiest to believe is generally profitable, and we can generalize the heuristic selection later.

[mkazantsev]

Thanks for the update, I will try to find some time to wrap my head about it within next few days.

llvm/lib/Transforms/Scalar/SimpleLoopBoundSplit.cpp

62

It will be something like

ICmpInst::Predicate Pred;
Value *LHS, RHS;
match(condition, m_ICmp(Pred, m_Value(LHS), m_Value(RHS)))

You can grep examples of this in many places, just grep by "m_ICmp". It just simplifies code a lot.

139

Ah ok, you're right.

239

Maybe we should assert the preconditions here to make sure we are doing the right thing. :)

263

It's never possible to say. For example, it may be some call to a method that has its own iteration counter (not related to the IV) and still have very subtle dependence on it that is impossible to fugire out.

273

Fair enough!

[jaykang10]

Following comments of @mkazantsev, updated code.
Fixed some bugs from previous diff.

[jaykang10]

@reames I appreciate your suggestion.

It looks your suggestion with existing SCEV logic is more general. Once I update this patch with your suggestion, I will let you and @mkazantsev know.

P.S I am feeling unwell after getting covid vaccination jab so it could take some time to implement your suggestion. Please understand it.

llvm/lib/Transforms/Scalar/SimpleLoopBoundSplit.cpp

62

Ah, Thanks for letting me know. I will update it.

239

Yep, I will update it.

263

Ah, Thanks for sharing the info.

[mkazantsev]

@jaykang10 hope you get well, I have same aftermath after 2nd dose. :) Could you please mark patch as "planned changes" so that it doesn't hightlight on my review list?

[jaykang10]

In D102234#2776326, @mkazantsev wrote:

@jaykang10 hope you get well, I have same aftermath after 2nd dose. :) Could you please mark patch as "planned changes" so that it doesn't hightlight on my review list?

Thanks @mkazantsev I am ok now. I hope you also get well soon. Let me mark this patch as "planned changes".

[jaykang10]

Following comments of @reames, updated code.

[jaykang10]

@reames @mkazantsev I have tried to update this patch following the new suggestion.

I have kept below things from previous patch.

1. ICmp of conditional branch for AddRec and its step.
2. Chosen one split candidate to remove conditional branch
3. If we do not choose one split candidate, we need a logic which conditional branch has the min bound.
4. The branch condition, which is removed, is changed to true or false to avoid same transformation with same conditional branch during next run of this pass.

This update could not be enough for the new suggestion. If you feel something wrong from this update, please let me know.

[jaykang10]

Invalidate cached SE information.

[jaykang10]

Fixed typo

[mkazantsev]

llvm/lib/Transforms/Scalar/LoopBoundSplit.cpp

47 ↗

(On Diff #348500)

Instead of this, consider flipping the predicate.

76 ↗

(On Diff #348500)

General notion: all this code is very hard of read because of all lambdae inlined. Can they be separate functions?

97 ↗

(On Diff #348500)

You can sink this computation under the condition bound < max.

157 ↗

(On Diff #348500)

How about checking isSCEVableType for comparison arguments right here?

238 ↗

(On Diff #348500)

1. It is already checked by IsProcessableCondBI , you can use cast instead of dyn_cast.
2. isa<IntegerType> --> SE.isSCEVableType and move it inside of IsProcessableCondBI.

252 ↗

(On Diff #348500)

That would be more natural to just return BI or nullptr from it (might also require function renaming).

278 ↗

(On Diff #348500)

What if both of them are nullptr?

[mkazantsev]

llvm/lib/Transforms/Scalar/LoopBoundSplit.cpp

278 ↗

(On Diff #348500)

Ah I see, they will fail the next check.

[jaykang10]

Following comments of @mkazantsev, updated code.

llvm/lib/Transforms/Scalar/LoopBoundSplit.cpp

47 ↗

(On Diff #348500)

Yep, let me change it.

76 ↗

(On Diff #348500)

Sorry for inconvenient. I will move them to functions.

97 ↗

(On Diff #348500)

Yep, I will move it.

157 ↗

(On Diff #348500)

Yep, I will add checks with isSCEVable(Type) for the comparison arguments.

238 ↗

(On Diff #348500)

Yep, I will update it.

252 ↗

(On Diff #348500)

Yep, I will update it.

[mkazantsev]

Looking much better now. Few more nits & a question regarding ne, which is a potential correctness concern.

llvm/lib/Transforms/Scalar/LoopBoundSplit.cpp

28 ↗

(On Diff #348925)

namespace llvm {

88 ↗

(On Diff #348925)

nit: I'd suggest resturure it as

if (pred != ULE && pred != SLE)
  return false;

this will reduce the nest for the biggest code piece. Just an idea.

108 ↗

(On Diff #348925)

Please add a TODO to handle ICMP_NE/EQ (I guess it was in the earlier versions of this patch and still good to support, but not necessarily in this revision).

131 ↗

(On Diff #348925)

ConstantInt *StepCI = dyn_cast<SCEVConstant>(StepRecSCEV)->getValue();
if (!StepCI || !StepCI->isPositive())
  return false;
...

152 ↗

(On Diff #348925)

Could declare as Value *LHS, *RHS; Just an idea.

157 ↗

(On Diff #348925)

It's enough to check LHS type and assert on RHS type.

166 ↗

(On Diff #348925)

canSplit...

167 ↗

(On Diff #348925)

Consider making params const where suitable.

217 ↗

(On Diff #348925)

Why is that needed?

221 ↗

(On Diff #348925)

This is still a very strict limitation I think. I can always split critical edges if you need it. I'm fine if you just add a TODO to consider it in the future.

244 ↗

(On Diff #348925)

Consider marking params as const where suitable.

[mkazantsev]

llvm/lib/Transforms/Scalar/LoopBoundSplit.cpp

355 ↗

(On Diff #348925)

Two points here:

1. Functional concern. Will NE work ok for step other than 1?
2. lt generally gives more info to the opt than ne (at least because lt implies ne). Any reason for ne here?

[jaykang10]

llvm/lib/Transforms/Scalar/LoopBoundSplit.cpp

28 ↗

(On Diff #348925)

Yep, I will update it.

88 ↗

(On Diff #348925)

Yep, I will update it.

108 ↗

(On Diff #348925)

Yep, I will add ToDo for it.

131 ↗

(On Diff #348925)

It looked there is no isPositive in ConstantInt. I will update it with isNegative() and isZero(),

152 ↗

(On Diff #348925)

Yep, I will update it.

157 ↗

(On Diff #348925)

Yep, I will update it.

166 ↗

(On Diff #348925)

sorry for inconvenient. I will update it.

167 ↗

(On Diff #348925)

Yep, let me try to add it.

217 ↗

(On Diff #348925)

Ah, I have tried to follow the below comment from @reames.

For a profitability check, I'd start specifically with the case where the condition precisely splits a loop into two halves. e.g. for ... { if (C) { body1 } else { body2 }. This is the easiest to believe is generally profitable, and we can generalize the heuristic selection later.

For the condition precisely splits a loop into two halves, I have checked that the conditional branch is in header and the join point is latch. Let me remove them.

221 ↗

(On Diff #348925)

Yep, I will remove the checks with single predecessor.

244 ↗

(On Diff #348925)

Yep, I will update it.

355 ↗

(On Diff #348925)

I have tried to follow below comment from @reames.

The "if (i != N)" is a loop guard and can be identified by getLoopGuardBranch.

I was also not sure whether ne is better than lt here...

[jaykang10]

Following comments from @mkazantsev, updated code.

• The ne code will be updated after more discussion.

[jaykang10]

llvm/lib/Transforms/Scalar/LoopBoundSplit.cpp

131 ↗

(On Diff #348925)

Sorry, I have found a test which has StepRecSCEV is not SCEVConstant. In this case, the nullptr->getValue() causes segment fault. I will re-update it.

[jaykang10]

Fixed a bug

[mkazantsev]

llvm/lib/Transforms/Scalar/LoopBoundSplit.cpp

355 ↗

(On Diff #348925)

I heard (and this info may be imprecise, out-of-date etc) that some parts of vectorization treat ne as its canonical form and don't recognize lt. As for me, it should never be a problem (lt always implies ne), but in practice it could be, just because how things are written now. I was asking if you are trying to deal with one of such cases, or it doesn't really matter. If it doesn't, lt is definitely better because it gives more info.

[mkazantsev]

I'm getting incline towards accepting this, but the fact that you keep finding bugs worries me. Please give me some time, I will run a corpus of Fuzzer tests with this pass locally to see if something breaks. If yes, I will try to give you a reproducer.

[mkazantsev]

My fuzzer didn't reveal any new failures, so there is a chance it's working as expected. :) LGTM with some nits.

llvm/lib/Transforms/Scalar/LoopBoundSplit.cpp

32 ↗

(On Diff #349291)

Please lock it in anonymous namespace (see how it's done e.g. in InstSimplifypass.cpp), https://llvm.org/docs/CodingStandards.html#anonymous-namespaces

423 ↗

(On Diff #349291)

Please delete this.

[mkazantsev]

llvm/lib/Transforms/Scalar/LoopBoundSplit.cpp

423 ↗

(On Diff #349291)

UPD: never mind, I didn't notice it was used for begug print.

[jaykang10]

In D102234#2801815, @mkazantsev wrote:

My fuzzer didn't reveal any new failures, so there is a chance it's working as expected. :) LGTM with some nits.

Thanks for your kind help! @mkazantsev :)

I have tried to enable this pass in the pipeline of new pass manager after loop unroll experimentally.

if (Phase != ThinOrFullLTOPhase::ThinLTOPreLink || !PGOOpt ||
    PGOOpt->Action != PGOOptions::SampleUse)
  LPM2.addPass(LoopFullUnrollPass(Level.getSpeedupLevel(),
                                  /* OnlyWhenForced= */ !PTO.LoopUnrolling,
                                  PTO.ForgetAllSCEVInLoopUnroll));
LPM2.addPass(LoopBoundSplitPass());

I found some failures from it and I fixed them. At this moment, there is no failure from llvm-test-suite and spec bencharmarks with enabling this pass as above.

Maybe, I will try to enable this pass in the pipeline of new pass manager later. If you have a idea about the location of this pass, please let me know. It will be very helpful.

After updating code following your comments, I will push this patch.

llvm/lib/Transforms/Scalar/LoopBoundSplit.cpp

32 ↗

(On Diff #349291)

Yep, I will update it.

[jaykang10]

Following comments of @mkazantsev, updated code.

[fhahn]

I'm seeing crashes when trying to build 471.omnetpp with -O3 -flto on X86 when running the pass just before the vectorizer (as below). Please take a look.

diff --git a/llvm/lib/Passes/PassBuilder.cpp b/llvm/lib/Passes/PassBuilder.cpp
index b07f966e3b7e..a3e3ed093ecb 100644
--- a/llvm/lib/Passes/PassBuilder.cpp
+++ b/llvm/lib/Passes/PassBuilder.cpp
@@ -1195,6 +1195,7 @@ PassBuilder::buildModuleSimplificationPipeline(OptimizationLevel Level,
 /// TODO: Should LTO cause any differences to this set of passes?
 void PassBuilder::addVectorPasses(OptimizationLevel Level,
                                   FunctionPassManager &FPM, bool IsLTO) {
+  FPM.addPass(createFunctionToLoopPassAdaptor(LoopBoundSplitPass()));
   FPM.addPass(LoopVectorizePass(
       LoopVectorizeOptions(!PTO.LoopInterleaving, !PTO.LoopVectorization)));

[jaykang10]

In D102234#2802193, @fhahn wrote:

I'm seeing crashes when trying to build 471.omnetpp with -O3 -flto on X86 when running the pass just before the vectorizer (as below). Please take a look.

diff --git a/llvm/lib/Passes/PassBuilder.cpp b/llvm/lib/Passes/PassBuilder.cpp
index b07f966e3b7e..a3e3ed093ecb 100644
--- a/llvm/lib/Passes/PassBuilder.cpp
+++ b/llvm/lib/Passes/PassBuilder.cpp
@@ -1195,6 +1195,7 @@ PassBuilder::buildModuleSimplificationPipeline(OptimizationLevel Level,
 /// TODO: Should LTO cause any differences to this set of passes?
 void PassBuilder::addVectorPasses(OptimizationLevel Level,
                                   FunctionPassManager &FPM, bool IsLTO) {
+  FPM.addPass(createFunctionToLoopPassAdaptor(LoopBoundSplitPass()));
   FPM.addPass(LoopVectorizePass(
       LoopVectorizeOptions(!PTO.LoopInterleaving, !PTO.LoopVectorization)));

Ah, Thanks @fhahn! I will have a look.

[Allen]

llvm/include/llvm/Transforms/Scalar/LoopBoundSplit.h

28 ↗

(On Diff #350215)

hi @jaykang10:

Excuse me, as *while (iv < n)* will guard the split loop body doesn't execute, so the insert condition *if (iv != n)* is good for performance?

[Allen]

I add a MR, try to remove the loop guard in loop guard D143705.

llvm/include/llvm/Transforms/Scalar/SimpleLoopBoundSplit.h

+//===- SimpleLoopBoundSplit.h - Split Loop Bound ----------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TRANSFORMS_SCALAR_SIMPLELOOPBOUNDSPLIT_H
+#define LLVM_TRANSFORMS_SCALAR_SIMPLELOOPBOUNDSPLIT_H
+
+#include "llvm/Analysis/LoopAnalysisManager.h"
+#include "llvm/Analysis/LoopInfo.h"
+#include "llvm/IR/PassManager.h"
+#include "llvm/Transforms/Scalar/LoopPassManager.h"
+
+namespace llvm {
+
+/// This pass transforms loops that contain a conditional branch with induction
+/// variable. In order to make this pass as simple as possible, it handles
+/// a condition which is mainly "AddRec < Bound" and its variants. For example,
+/// it transforms left code to right code:
+///
+///                              newbound1 = min(n, c)
+///                              newbound2 = max(n, c)
+///  while (iv < n) {            while(iv < newbound1) {
+///    A                           A
+///    if (iv < c)                 B
+///      B                         C
+///    C                         }
+///  }                           iv = newbound1
+///                              while (iv < newbound2) {
+///                                A
+///                                C
+///                              }
+class SimpleLoopBoundSplitPass : public PassInfoMixin<SimpleLoopBoundSplitPass> {
+public:
+  PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM,
+                        LoopStandardAnalysisResults &AR, LPMUpdater &U);
+};
+
+} // end namespace llvm
+
+#endif // LLVM_TRANSFORMS_SCALAR_SIMPLELOOPBOUNDSPLIT_H

llvm/lib/Passes/PassBuilder.cpp

 #include "llvm/Transforms/Scalar/Reassociate.h"
 #include "llvm/Transforms/Scalar/Reg2Mem.h"
 #include "llvm/Transforms/Scalar/RewriteStatepointsForGC.h"
 #include "llvm/Transforms/Scalar/SCCP.h"
 #include "llvm/Transforms/Scalar/SROA.h"
 #include "llvm/Transforms/Scalar/ScalarizeMaskedMemIntrin.h"
 #include "llvm/Transforms/Scalar/Scalarizer.h"
 #include "llvm/Transforms/Scalar/SeparateConstOffsetFromGEP.h"
+#include "llvm/Transforms/Scalar/SimpleLoopBoundSplit.h"
 #include "llvm/Transforms/Scalar/SimpleLoopUnswitch.h"
 #include "llvm/Transforms/Scalar/SimplifyCFG.h"
 #include "llvm/Transforms/Scalar/Sink.h"
 #include "llvm/Transforms/Scalar/SpeculateAroundPHIs.h"
 #include "llvm/Transforms/Scalar/SpeculativeExecution.h"
 #include "llvm/Transforms/Scalar/StraightLineStrengthReduce.h"
 #include "llvm/Transforms/Scalar/StructurizeCFG.h"
 #include "llvm/Transforms/Scalar/TailRecursionElimination.h"

llvm/lib/Passes/PassRegistry.def

 LOOP_PASS("loop-unroll-full", LoopFullUnrollPass())
 LOOP_PASS("print-access-info", LoopAccessInfoPrinterPass(dbgs()))
 LOOP_PASS("print<ddg>", DDGAnalysisPrinterPass(dbgs()))
 LOOP_PASS("print<iv-users>", IVUsersPrinterPass(dbgs()))
 LOOP_PASS("print<loopnest>", LoopNestPrinterPass(dbgs()))
 LOOP_PASS("print<loop-cache-cost>", LoopCachePrinterPass(dbgs()))
 LOOP_PASS("loop-predication", LoopPredicationPass())
 LOOP_PASS("guard-widening", GuardWideningPass())
+LOOP_PASS("simple-loop-bound-split", SimpleLoopBoundSplitPass())
 LOOP_PASS("simple-loop-unswitch", SimpleLoopUnswitchPass())
 LOOP_PASS("loop-reroll", LoopRerollPass())
 LOOP_PASS("loop-versioning-licm", LoopVersioningLICMPass())
 #undef LOOP_PASS
 
 #ifndef LOOP_PASS_WITH_PARAMS
 #define LOOP_PASS_WITH_PARAMS(NAME, CREATE_PASS, PARSER)
 #endif
 LOOP_PASS_WITH_PARAMS("unswitch",
                            [](bool NonTrivial) {
                              return SimpleLoopUnswitchPass(NonTrivial);
                            },
                            parseLoopUnswitchOptions)
 #undef LOOP_PASS_WITH_PARAMS

llvm/lib/Transforms/Scalar/CMakeLists.txt

add_llvm_component_library(LLVMScalarOpts
   Reg2Mem.cpp
   RewriteStatepointsForGC.cpp
   SCCP.cpp
   SROA.cpp
   Scalar.cpp
   Scalarizer.cpp
   ScalarizeMaskedMemIntrin.cpp
   SeparateConstOffsetFromGEP.cpp
+  SimpleLoopBoundSplit.cpp
   SimpleLoopUnswitch.cpp
   SimplifyCFGPass.cpp
   Sink.cpp
   SpeculativeExecution.cpp
   SpeculateAroundPHIs.cpp
   StraightLineStrengthReduce.cpp
   StructurizeCFG.cpp
   TailRecursionElimination.cpp

llvm/lib/Transforms/Scalar/SimpleLoopBoundSplit.cpp

+//===- SimpleLoopBoundSplit.cpp - Split Loop Bound --------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Transforms/Scalar/SimpleLoopBoundSplit.h"
+#include "llvm/Analysis/LoopAccessAnalysis.h"
+#include "llvm/Analysis/LoopAnalysisManager.h"
+#include "llvm/Analysis/LoopInfo.h"
+#include "llvm/Analysis/LoopIterator.h"
+#include "llvm/Analysis/LoopPass.h"
+#include "llvm/Analysis/MemorySSA.h"
+#include "llvm/Analysis/MemorySSAUpdater.h"
+#include "llvm/Analysis/ScalarEvolution.h"
+#include "llvm/Analysis/ScalarEvolutionExpressions.h"
+#include "llvm/Transforms/Utils/Cloning.h"
+#include "llvm/Transforms/Utils/LoopSimplify.h"
+#include "llvm/Transforms/Utils/LoopUtils.h"
+#include "llvm/Transforms/Utils/ScalarEvolutionExpander.h"
+
+#define DEBUG_TYPE "simple-loop-bound-split"
+
+using namespace llvm;
+
+struct ConditionInfo {
+  /// Branch instruction with this condition
+  BranchInst *BI;
+  /// ICmp instruction with this condition
+  ICmpInst *ICmp;
+  /// Preciate info
+  ICmpInst::Predicate Pred;
+  /// AddRec llvm value
+  Value *AddRecValue;
+  /// Bound llvm value
+  Value *BoundValue;
+  /// AddRec SCEV
+  const SCEV *AddRecSCEV;
+  /// Bound SCEV
+  const SCEV *BoundSCEV;
+  /// Has been swapped LHS and RHS for AddRec and Bound
+  bool OpsSwapped;
+  /// Signedness info
+  bool HasNoSignedWrap;
+
+  ConditionInfo()
+      : BI(nullptr), ICmp(nullptr), Pred(ICmpInst::BAD_ICMP_PREDICATE),
+        AddRecValue(nullptr), BoundValue(nullptr), AddRecSCEV(nullptr),
+        BoundSCEV(nullptr), OpsSwapped(false), HasNoSignedWrap(false) {}
+};
+
+static bool splitLoopBound(Loop &L, const LoopAccessInfo &LAI,
+                           DominatorTree &DT, LoopInfo &LI, AssumptionCache &AC,
+                           AAResults &AA, TargetTransformInfo &TTI,
+                           ScalarEvolution &SE, LPMUpdater &U) {
+  auto AnalyzeICmp = [&SE](ICmpInst *ICmp, ConditionInfo &Cond) {
+    Cond.ICmp = ICmp;
+    Cond.Pred = ICmp->getPredicate();
+    Cond.AddRecValue = ICmp->getOperand(0);
+    Cond.BoundValue = ICmp->getOperand(1);
+    Cond.AddRecSCEV = SE.getSCEV(Cond.AddRecValue);
+    Cond.BoundSCEV = SE.getSCEV(Cond.BoundValue);
+    // Locate AddRec in LHSSCEV and Bound in RHSSCEV.
+    if (isa<SCEVAddRecExpr>(Cond.BoundSCEV) &&
+        !isa<SCEVAddRecExpr>(Cond.AddRecSCEV)) {
+      std::swap(Cond.AddRecValue, Cond.BoundValue);
+      std::swap(Cond.AddRecSCEV, Cond.BoundSCEV);
+      Cond.Pred = ICmpInst::getSwappedPredicate(Cond.Pred);
+      Cond.OpsSwapped = true;
+    }
+  };
+
+  auto CalculateUpperBoundWithLT = [&SE](ICmpInst::Predicate &Pred,
+                                         const SCEVAddRecExpr *&AddRecSCEV,
+                                         const SCEV *&BoundSCEV,
+                                         bool &HasNoSignedWrap,
+                                         bool IsExitCond) {
+    // This function calculates upper bound from loop's exit condition and
+    // non-exit condition. If possible, it tries to canonicalize predicates to
+    // LT like 'AddRec < Bound'. For non-exit condtion, it tries to convert LE
+    // to LT. For exit condition, the predicates are inversed normally except EQ
+    // and then follows same conversion with non-exit condition. EQ is handled a
+    // bit differently.
+
+    HasNoSignedWrap = AddRecSCEV->hasNoSignedWrap();
+
+    //  Exit condition            Range
+    // AddRec == Bound  -->  AddRec < Bound
+    if (IsExitCond && Pred == ICmpInst::ICMP_EQ) {
+      Pred = AddRecSCEV->hasNoSignedWrap() ? ICmpInst::ICMP_SLT
+                                           : ICmpInst::ICMP_ULT;
+      return;
+    }
+
+    // Inverse exit condtion's pred for bound.
+    if (IsExitCond)
+      Pred = ICmpInst::getInversePredicate(Pred);
+
+    //      Range                 Range
+    // AddRec <= Bound  -->  AddRec < Bound - 1
+    if (Pred == ICmpInst::ICMP_ULE || Pred == ICmpInst::ICMP_SLE) {
+      BoundSCEV = SE.getMinusSCEV(BoundSCEV, SE.getOne(BoundSCEV->getType()));
+      Pred = ICmpInst::isSigned(Pred) ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT;
+    }
+  };
+
+  auto HasProcessableCondition =
+      [&SE, &AnalyzeICmp, &CalculateUpperBoundWithLT](
+          ICmpInst *ICmp, ConditionInfo &Cond, bool IsExitCond) {
+        AnalyzeICmp(ICmp, Cond);
+
+        const SCEVAddRecExpr *AddRecSCEV =
+            dyn_cast<SCEVAddRecExpr>(Cond.AddRecSCEV);
+        // Allowed AddRec as induction variable.
+        if (!AddRecSCEV)
+          return false;
+
+        const SCEV *StepRecSCEV = AddRecSCEV->getStepRecurrence(SE);
+        // Allowed constant step.
+        if (!isa<SCEVConstant>(StepRecSCEV))
+          return false;
+
+        ConstantInt *StepCI = cast<SCEVConstant>(StepRecSCEV)->getValue();
+        // Allowed positive step.
+        if (StepCI->isNegative())
+          return false;
+
+        // Allowed step is one.
+        if (!StepCI->isOne())
+          return false;
+
+        CalculateUpperBoundWithLT(Cond.Pred, AddRecSCEV, Cond.BoundSCEV,
+                                  Cond.HasNoSignedWrap, IsExitCond);
+
+        // Allowed only 'AddRec < Bound' because the pred has been canonicalized
+        // by CalculateUpperBoundWithLT.
+        if (Cond.Pred != ICmpInst::ICMP_ULT && Cond.Pred != ICmpInst::ICMP_SLT)
+          return false;
+
+        return true;
+      };
+
+  auto CanSplitLoopBound = [&L, &LI, &DT,
+                            &HasProcessableCondition](ConditionInfo &Cond) {
+    // Skip function with optsize.
+    if (L.getHeader()->getParent()->hasOptSize())
+      return false;
+
+    // Split only innermost loop.
+    if (!L.isInnermost())
+      return false;
+
+    // Check loop is in simplified form.
+    if (!L.isLoopSimplifyForm())
+      return false;
+
+    // Check loop is in LCSSA form.
+    if (!L.isRecursivelyLCSSAForm(DT, LI))
+      return false;
+
+    // Skip loop that cannot be cloned.
+    if (!L.isSafeToClone())
+      return false;
+
+    BasicBlock *ExitingBB = L.getExitingBlock();
+    // Assumed only one exiting block.
+    if (!ExitingBB)
+      return false;
+
+    BranchInst *ExitingBI = dyn_cast<BranchInst>(ExitingBB->getTerminator());
+    // Allowed only conditional branch.
+    if (!ExitingBI || !ExitingBI->isConditional() ||
+        isa<Constant>(ExitingBI->getCondition()) ||
+        ExitingBI->getSuccessor(0) == ExitingBI->getSuccessor(1))
+      return false;
+
+    ICmpInst *ICmp = dyn_cast<ICmpInst>(ExitingBI->getCondition());
+    // Assumed ICmp instruction for condition.
+    if (!ICmp)
+      return false;
+
+    // Check the condition is processable.
+    if (!HasProcessableCondition(ICmp, Cond, true))
+      return false;
+
+    Cond.BI = ExitingBI;
+    return true;
+  };
+
+  ConditionInfo ExitingCond;
+  ConditionInfo SplitCandidateCond;
+
+  // Check we can split this loop's bound.
+  if (!CanSplitLoopBound(ExitingCond))
+    return false;
+
+  // Find a split candidate.
+  bool FoundCandidate = false;
+  for (auto *BB : L.blocks()) {
+    // Skip condition of backedge.
+    if (L.getLoopLatch() == BB)
+      continue;
+
+    // Skip unconditional branch.
+    auto *BI = dyn_cast<BranchInst>(BB->getTerminator());
+    if (!BI || !BI->isConditional() || isa<Constant>(BI->getCondition()) ||
+        BI->getSuccessor(0) == BI->getSuccessor(1))
+      continue;
+
+    // Skip loop invariant condition.
+    if (L.isLoopInvariant(BI->getCondition()))
+      continue;
+
+    // Conservatively, allowed only one conditional branch with induction
+    // variable in loop. If we have already found a split candidate, skip this
+    // loop.
+    if (FoundCandidate)
+      return false;
+
+    // Allowed ICmp.
+    ICmpInst *ICmp = dyn_cast<ICmpInst>(BI->getCondition());
+    if (!ICmp || !isa<IntegerType>(ICmp->getOperand(0)->getType()))
+      continue;
+
+    // Check the condition is processable.
+    if (!HasProcessableCondition(ICmp, SplitCandidateCond, false))
+      return false;
+
+    SplitCandidateCond.BI = BI;
+    FoundCandidate = true;
+  }
+
+  if (!FoundCandidate)
+    return false;
+
+  // Assumed same signedness.
+  if (ExitingCond.HasNoSignedWrap != SplitCandidateCond.HasNoSignedWrap)
+    return false;
+
+  auto isProfitableToTransform = [&L, &LAI, &DT](BranchInst *BI) {
+    // This transformation aims mainly to help loop vectorizer. If we can not
+    // vectorize the loop, it is not profitable.
+    if (!LAI.canVectorizeMemory())
+      return false;
+
+    // If there is conditional branch inside loop, loop vectorizer could try to
+    // predicate  the conditional branch's successors. In this case, if the
+    // successor to be predicated has load/store instructions and target machine
+    // does not support masked vector load/store, loop vectorizer assigns big
+    // cost to the load/store instruction. It causes to block vectorize loop. We
+    // check the conditional branch's target blocks have load/store instruction.
+    // If the block has load/store instructions, we consider this transformation
+    // is profitable.
+    //
+    // ToDo: check something more here according to benchmarks' score
+    for (auto *Succ : BI->successors()) {
+      // Skip block which do not need predication.
+      if (DT.dominates(Succ, L.getLoopLatch()))
+        continue;
+      for (auto &Inst : *Succ) {
+        if (isa<LoadInst>(Inst) || isa<StoreInst>(Inst))
+          return true;
+      }
+    }
+    return false;
+  };
+
+  if (!isProfitableToTransform(SplitCandidateCond.BI))
+    return false;
+
+  // Now, we have a split candidate. Let's split loop bound with it as below.
+  //    +--------------------+
+  //    |     preheader      |
+  //    |  set up newbound1  |
+  //    |         newbound2  |
+  //    +--------------------+
+  //             |     /----------------\
+  //    +--------v----v------+          |
+  //    |      header        |---\      |
+  //    | conditional branch |   |      |
+  //    | with true condition|   |      |
+  //    +--------------------+   x      |
+  //             |               x      |
+  //    +--------v-----------+   x      |
+  //    |     if.then.BB     |   |      |
+  //    +--------------------+   |      |
+  //             |               |      |
+  //    +--------v-----------<---/      |
+  //    |       latch        >----------/
+  //    |   with newbound1   |
+  //    +--------------------+
+  //             |
+  //    +--------v-----------+
+  //    |     preheader2     |--------------\
+  //    | if (orig bound >   |              |
+  //    |     newbound1)     |              |
+  //    +--------------------+              |
+  //             |     /----------------\   |
+  //    +--------v----v------+          |   |
+  //    |      header2       |---\      |   |
+  //    |   iv starts with   |   |      |   |
+  //    |      newbound1     |   |      |   |
+  //    | conditional branch |   |      |   |
+  //    |with false condition|   |      |   |
+  //    +--------------------+   |      |   |
+  //             x               |      |   |
+  //    +--------v-----------+   |      |   |
+  //    |    if.then.BB2     |   |      |   |
+  //    +--------------------+   |      |   |
+  //             |               |      |   |
+  //    +--------v-----------<---/      |   |
+  //    |       latch2       >----------/   |
+  //    |   with newbound2   |              |
+  //    +--------v-----------+              |
+  //             |                          |
+  //             |  +---------------+       |
+  //             +-->     exit      <-------/
+  //                +---------------+
+  SCEVExpander Expander(
+      SE, L.getHeader()->getParent()->getParent()->getDataLayout(), "split");
+  BasicBlock *PreHeader = L.getLoopPreheader();
+  Instruction *InsertPt = PreHeader->getTerminator();
+
+  // Let's create second loop.
+  SmallVector<BasicBlock *, 8> SecondLoopBlocks;
+  Loop *SecondLoop;
+  ValueToValueMapTy VMap;
+  SecondLoop = cloneLoopWithPreheader(L.getExitBlock(), PreHeader, &L, VMap,
+                                      ".split", &LI, &DT, SecondLoopBlocks);
+  remapInstructionsInBlocks(SecondLoopBlocks, VMap);
+
+  // Calculate new loop bounds and add them into preheader of first loop which
+  // is orignial loop.
+  const SCEV *NewBound1 =
+      SplitCandidateCond.HasNoSignedWrap
+          ? SE.getSMinExpr(ExitingCond.BoundSCEV, SplitCandidateCond.BoundSCEV)
+          : SE.getUMinExpr(ExitingCond.BoundSCEV, SplitCandidateCond.BoundSCEV);
+  const SCEV *NewBound2 =
+      SplitCandidateCond.HasNoSignedWrap
+          ? SE.getSMaxExpr(ExitingCond.BoundSCEV, SplitCandidateCond.BoundSCEV)
+          : SE.getUMaxExpr(ExitingCond.BoundSCEV, SplitCandidateCond.BoundSCEV);
+
+  Value *NewBound1Value =
+      Expander.expandCodeFor(NewBound1, NewBound1->getType(), InsertPt);
+  Value *NewBound2Value =
+      Expander.expandCodeFor(NewBound2, NewBound2->getType(), InsertPt);
+  NewBound1Value->setName("new.bound1");
+  NewBound2Value->setName("new.bound2");
+
+  // Add conditional branch to check we can skip second loop in its preheader.
+  BasicBlock *SecondLoopPreHeader = SecondLoop->getLoopPreheader();
+  IRBuilder<> Builder(SecondLoopPreHeader);
+  Instruction *OrigBI = SecondLoopPreHeader->getTerminator();
+  ICmpInst::Predicate Pred = SplitCandidateCond.HasNoSignedWrap
+                                 ? ICmpInst::ICMP_SGE
+                                 : ICmpInst::ICMP_UGE;
+  Value *Cond =
+      Builder.CreateICmp(Pred, NewBound1Value, ExitingCond.BoundValue);
+  Builder.CreateCondBr(Cond, SecondLoop->getExitBlock(),
+                       SecondLoop->getHeader());
+  OrigBI->eraseFromParent();
+
+  // Replace exiting bound value of first loop, which is original loop, by
+  // NewBound1.
+  if (ExitingCond.OpsSwapped)
+    ExitingCond.ICmp->setOperand(0, NewBound1Value);
+  else
+    ExitingCond.ICmp->setOperand(1, NewBound1Value);
+
+  // Replace IV's start value of second loop by NewBound1.
+  for (PHINode &PN : L.getHeader()->phis()) {
+    // Find PHI with exiting condition from first loop.
+    if (isa<SCEVAddRecExpr>(SE.getSCEV(&PN))) {
+      for (Value *Op : PN.incoming_values()) {
+        if (Op == ExitingCond.AddRecValue) {
+          // Find cloned PHI for second loop.
+          PHINode *SecondLoopPN = cast<PHINode>(VMap[&PN]);
+          SecondLoopPN->setIncomingValueForBlock(SecondLoopPreHeader,
+                                                 NewBound1Value);
+        }
+      }
+    }
+  }
+
+  // Replace SplitCandidateCond.BI's condition of first loop, which is original
+  // loop, by True.
+  LLVMContext &Context = PreHeader->getContext();
+  SplitCandidateCond.BI->setCondition(ConstantInt::getTrue(Context));
+
+  // Replace cloned SplitCandidateCond.BI's condition in second loop by False.
+  BranchInst *ClonedSplitCandidateBI =
+      cast<BranchInst>(VMap[SplitCandidateCond.BI]);
+  ClonedSplitCandidateBI->setCondition(ConstantInt::getFalse(Context));
+
+  // Replace exit branch target of first loop, which is original loop, by second
+  // loop's preheader.
+  if (L.getExitBlock() == ExitingCond.BI->getSuccessor(0))
+    ExitingCond.BI->setSuccessor(0, SecondLoopPreHeader);
+  else
+    ExitingCond.BI->setSuccessor(1, SecondLoopPreHeader);
+
+  // Update dominator tree.
+  DT.changeImmediateDominator(SecondLoopPreHeader, L.getExitingBlock());
+  DT.changeImmediateDominator(SecondLoop->getExitBlock(), SecondLoopPreHeader);
+
+  // Canonicalize loops
+  formLCSSARecursively(L, DT, &LI, &SE);
+  simplifyLoop(&L, &DT, &LI, &SE, nullptr, nullptr, true);
+  formLCSSARecursively(*SecondLoop, DT, &LI, &SE);
+  simplifyLoop(SecondLoop, &DT, &LI, &SE, nullptr, nullptr, true);
+
+  // Add new second loop to loop pass manager.
+  U.addSiblingLoops(SecondLoop);
+
+  return true;
+}
+
+PreservedAnalyses SimpleLoopBoundSplitPass::run(Loop &L,
+                                                LoopAnalysisManager &AM,
+                                                LoopStandardAnalysisResults &AR,
+                                                LPMUpdater &U) {
+  Function &F = *L.getHeader()->getParent();
+  (void)F;
+
+  LLVM_DEBUG(dbgs() << "Spliting bound of loop in " << F.getName() << ": " << L
+                    << "\n");
+
+  const LoopAccessInfo &LAI = AM.getResult<LoopAccessAnalysis>(L, AR);
+
+  if (!splitLoopBound(L, LAI, AR.DT, AR.LI, AR.AC, AR.AA, AR.TTI, AR.SE, U))
+    return PreservedAnalyses::all();
+
+  assert(AR.DT.verify(DominatorTree::VerificationLevel::Fast));
+
+  return getLoopPassPreservedAnalyses();
+}

llvm/test/Transforms/SimpleLoopBoundSplit/simple-loop-bound-split.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt  -passes=simple-loop-bound-split -S < %s | FileCheck %s
+
+define void @split_loop_bound_inc_with_sgt(i64 %a, i64* noalias %src, i64* noalias %dst, i64 %n) {
+; CHECK-LABEL: @split_loop_bound_inc_with_sgt(
+; CHECK-NEXT:  loop.ph:
+; CHECK-NEXT:    [[TMP0:%.*]] = add i64 [[N:%.*]], -1
+; CHECK-NEXT:    [[NEW_BOUND1:%.*]] = call i64 @llvm.smin.i64(i64 [[A:%.*]], i64 [[TMP0]])
+; CHECK-NEXT:    [[NEW_BOUND2:%.*]] = call i64 @llvm.smax.i64(i64 [[A]], i64 [[TMP0]])
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ [[INC:%.*]], [[FOR_INC:%.*]] ], [ 0, [[LOOP_PH:%.*]] ]
+; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i64 [[IV]], [[A]]
+; CHECK-NEXT:    br i1 true, label [[IF_THEN:%.*]], label [[FOR_INC]]
+; CHECK:       if.then:
+; CHECK-NEXT:    [[SRC_ARRAYIDX:%.*]] = getelementptr inbounds i64, i64* [[SRC:%.*]], i64 [[IV]]
+; CHECK-NEXT:    [[VAL:%.*]] = load i64, i64* [[SRC_ARRAYIDX]], align 4
+; CHECK-NEXT:    [[DST_ARRAYIDX:%.*]] = getelementptr inbounds i64, i64* [[DST:%.*]], i64 [[IV]]
+; CHECK-NEXT:    store i64 [[VAL]], i64* [[DST_ARRAYIDX]], align 4
+; CHECK-NEXT:    br label [[FOR_INC]]
+; CHECK:       for.inc:
+; CHECK-NEXT:    [[INC]] = add nuw nsw i64 [[IV]], 1
+; CHECK-NEXT:    [[COND:%.*]] = icmp sgt i64 [[INC]], [[NEW_BOUND1]]
+; CHECK-NEXT:    br i1 [[COND]], label [[LOOP_PH_SPLIT:%.*]], label [[LOOP]]
+; CHECK:       loop.ph.split:
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp sge i64 [[NEW_BOUND1]], [[N]]
+; CHECK-NEXT:    br i1 [[TMP1]], label [[EXIT:%.*]], label [[LOOP_SPLIT_PREHEADER:%.*]]
+; CHECK:       loop.split.preheader:
+; CHECK-NEXT:    br label [[LOOP_SPLIT:%.*]]
+; CHECK:       loop.split:
+; CHECK-NEXT:    [[IV_SPLIT:%.*]] = phi i64 [ [[INC_SPLIT:%.*]], [[FOR_INC_SPLIT:%.*]] ], [ [[NEW_BOUND1]], [[LOOP_SPLIT_PREHEADER]] ]
+; CHECK-NEXT:    [[CMP_SPLIT:%.*]] = icmp slt i64 [[IV_SPLIT]], [[A]]
+; CHECK-NEXT:    br i1 false, label [[IF_THEN_SPLIT:%.*]], label [[FOR_INC_SPLIT]]
+; CHECK:       if.then.split:
+; CHECK-NEXT:    [[SRC_ARRAYIDX_SPLIT:%.*]] = getelementptr inbounds i64, i64* [[SRC]], i64 [[IV_SPLIT]]
+; CHECK-NEXT:    [[VAL_SPLIT:%.*]] = load i64, i64* [[SRC_ARRAYIDX_SPLIT]], align 4
+; CHECK-NEXT:    [[DST_ARRAYIDX_SPLIT:%.*]] = getelementptr inbounds i64, i64* [[DST]], i64 [[IV_SPLIT]]
+; CHECK-NEXT:    store i64 [[VAL_SPLIT]], i64* [[DST_ARRAYIDX_SPLIT]], align 4
+; CHECK-NEXT:    br label [[FOR_INC_SPLIT]]
+; CHECK:       for.inc.split:
+; CHECK-NEXT:    [[INC_SPLIT]] = add nuw nsw i64 [[IV_SPLIT]], 1
+; CHECK-NEXT:    [[COND_SPLIT:%.*]] = icmp sgt i64 [[INC_SPLIT]], [[N]]
+; CHECK-NEXT:    br i1 [[COND_SPLIT]], label [[EXIT_LOOPEXIT:%.*]], label [[LOOP_SPLIT]]
+; CHECK:       exit.loopexit:
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+loop.ph:
+  br label %loop
+
+loop:
+  %iv = phi i64 [ %inc, %for.inc ], [ 0, %loop.ph ]
+  %cmp = icmp slt i64 %iv, %a
+  br i1 %cmp, label %if.then, label %for.inc
+
+if.then:
+  %src.arrayidx = getelementptr inbounds i64, i64* %src, i64 %iv
+  %val = load i64, i64* %src.arrayidx
+  %dst.arrayidx = getelementptr inbounds i64, i64* %dst, i64 %iv
+  store i64 %val, i64* %dst.arrayidx
+  br label %for.inc
+
+for.inc:
+  %inc = add nuw nsw i64 %iv, 1
+  %cond = icmp sgt i64 %inc, %n
+  br i1 %cond, label %exit, label %loop
+
+exit:
+  ret void
+}
+
+define void @split_loop_bound_inc_with_eq(i64 %a, i64* noalias %src, i64* noalias %dst, i64 %n) {
+; CHECK-LABEL: @split_loop_bound_inc_with_eq(
+; CHECK-NEXT:  loop.ph:
+; CHECK-NEXT:    [[NEW_BOUND1:%.*]] = call i64 @llvm.smin.i64(i64 [[N:%.*]], i64 [[A:%.*]])
+; CHECK-NEXT:    [[NEW_BOUND2:%.*]] = call i64 @llvm.smax.i64(i64 [[N]], i64 [[A]])
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ [[INC:%.*]], [[FOR_INC:%.*]] ], [ 0, [[LOOP_PH:%.*]] ]
+; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i64 [[IV]], [[A]]
+; CHECK-NEXT:    br i1 true, label [[IF_THEN:%.*]], label [[FOR_INC]]
+; CHECK:       if.then:
+; CHECK-NEXT:    [[SRC_ARRAYIDX:%.*]] = getelementptr inbounds i64, i64* [[SRC:%.*]], i64 [[IV]]
+; CHECK-NEXT:    [[VAL:%.*]] = load i64, i64* [[SRC_ARRAYIDX]], align 4
+; CHECK-NEXT:    [[DST_ARRAYIDX:%.*]] = getelementptr inbounds i64, i64* [[DST:%.*]], i64 [[IV]]
+; CHECK-NEXT:    store i64 [[VAL]], i64* [[DST_ARRAYIDX]], align 4
+; CHECK-NEXT:    br label [[FOR_INC]]
+; CHECK:       for.inc:
+; CHECK-NEXT:    [[INC]] = add nuw nsw i64 [[IV]], 1
+; CHECK-NEXT:    [[COND:%.*]] = icmp eq i64 [[INC]], [[NEW_BOUND1]]
+; CHECK-NEXT:    br i1 [[COND]], label [[LOOP_PH_SPLIT:%.*]], label [[LOOP]]
+; CHECK:       loop.ph.split:
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp sge i64 [[NEW_BOUND1]], [[N]]
+; CHECK-NEXT:    br i1 [[TMP0]], label [[EXIT:%.*]], label [[LOOP_SPLIT_PREHEADER:%.*]]
+; CHECK:       loop.split.preheader:
+; CHECK-NEXT:    br label [[LOOP_SPLIT:%.*]]
+; CHECK:       loop.split:
+; CHECK-NEXT:    [[IV_SPLIT:%.*]] = phi i64 [ [[INC_SPLIT:%.*]], [[FOR_INC_SPLIT:%.*]] ], [ [[NEW_BOUND1]], [[LOOP_SPLIT_PREHEADER]] ]
+; CHECK-NEXT:    [[CMP_SPLIT:%.*]] = icmp slt i64 [[IV_SPLIT]], [[A]]
+; CHECK-NEXT:    br i1 false, label [[IF_THEN_SPLIT:%.*]], label [[FOR_INC_SPLIT]]
+; CHECK:       if.then.split:
+; CHECK-NEXT:    [[SRC_ARRAYIDX_SPLIT:%.*]] = getelementptr inbounds i64, i64* [[SRC]], i64 [[IV_SPLIT]]
+; CHECK-NEXT:    [[VAL_SPLIT:%.*]] = load i64, i64* [[SRC_ARRAYIDX_SPLIT]], align 4
+; CHECK-NEXT:    [[DST_ARRAYIDX_SPLIT:%.*]] = getelementptr inbounds i64, i64* [[DST]], i64 [[IV_SPLIT]]
+; CHECK-NEXT:    store i64 [[VAL_SPLIT]], i64* [[DST_ARRAYIDX_SPLIT]], align 4
+; CHECK-NEXT:    br label [[FOR_INC_SPLIT]]
+; CHECK:       for.inc.split:
+; CHECK-NEXT:    [[INC_SPLIT]] = add nuw nsw i64 [[IV_SPLIT]], 1
+; CHECK-NEXT:    [[COND_SPLIT:%.*]] = icmp eq i64 [[INC_SPLIT]], [[N]]
+; CHECK-NEXT:    br i1 [[COND_SPLIT]], label [[EXIT_LOOPEXIT:%.*]], label [[LOOP_SPLIT]]
+; CHECK:       exit.loopexit:
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+loop.ph:
+  br label %loop
+
+loop:
+  %iv = phi i64 [ %inc, %for.inc ], [ 0, %loop.ph ]
+  %cmp = icmp slt i64 %iv, %a
+  br i1 %cmp, label %if.then, label %for.inc
+
+if.then:
+  %src.arrayidx = getelementptr inbounds i64, i64* %src, i64 %iv
+  %val = load i64, i64* %src.arrayidx
+  %dst.arrayidx = getelementptr inbounds i64, i64* %dst, i64 %iv
+  store i64 %val, i64* %dst.arrayidx
+  br label %for.inc
+
+for.inc:
+  %inc = add nuw nsw i64 %iv, 1
+  %cond = icmp eq i64 %inc, %n
+  br i1 %cond, label %exit, label %loop
+
+exit:
+  ret void
+}
+
+define void @split_loop_bound_inc_with_sge(i64 %a, i64* noalias %src, i64* noalias %dst, i64 %n) {
+; CHECK-LABEL: @split_loop_bound_inc_with_sge(
+; CHECK-NEXT:  loop.ph:
+; CHECK-NEXT:    [[NEW_BOUND1:%.*]] = call i64 @llvm.smin.i64(i64 [[N:%.*]], i64 [[A:%.*]])
+; CHECK-NEXT:    [[NEW_BOUND2:%.*]] = call i64 @llvm.smax.i64(i64 [[N]], i64 [[A]])
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ [[INC:%.*]], [[FOR_INC:%.*]] ], [ 0, [[LOOP_PH:%.*]] ]
+; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i64 [[IV]], [[A]]
+; CHECK-NEXT:    br i1 true, label [[IF_THEN:%.*]], label [[FOR_INC]]
+; CHECK:       if.then:
+; CHECK-NEXT:    [[SRC_ARRAYIDX:%.*]] = getelementptr inbounds i64, i64* [[SRC:%.*]], i64 [[IV]]
+; CHECK-NEXT:    [[VAL:%.*]] = load i64, i64* [[SRC_ARRAYIDX]], align 4
+; CHECK-NEXT:    [[DST_ARRAYIDX:%.*]] = getelementptr inbounds i64, i64* [[DST:%.*]], i64 [[IV]]
+; CHECK-NEXT:    store i64 [[VAL]], i64* [[DST_ARRAYIDX]], align 4
+; CHECK-NEXT:    br label [[FOR_INC]]
+; CHECK:       for.inc:
+; CHECK-NEXT:    [[INC]] = add nuw nsw i64 [[IV]], 1
+; CHECK-NEXT:    [[COND:%.*]] = icmp sge i64 [[INC]], [[NEW_BOUND1]]
+; CHECK-NEXT:    br i1 [[COND]], label [[LOOP_PH_SPLIT:%.*]], label [[LOOP]]
+; CHECK:       loop.ph.split:
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp sge i64 [[NEW_BOUND1]], [[N]]
+; CHECK-NEXT:    br i1 [[TMP0]], label [[EXIT:%.*]], label [[LOOP_SPLIT_PREHEADER:%.*]]
+; CHECK:       loop.split.preheader:
+; CHECK-NEXT:    br label [[LOOP_SPLIT:%.*]]
+; CHECK:       loop.split:
+; CHECK-NEXT:    [[IV_SPLIT:%.*]] = phi i64 [ [[INC_SPLIT:%.*]], [[FOR_INC_SPLIT:%.*]] ], [ [[NEW_BOUND1]], [[LOOP_SPLIT_PREHEADER]] ]
+; CHECK-NEXT:    [[CMP_SPLIT:%.*]] = icmp slt i64 [[IV_SPLIT]], [[A]]
+; CHECK-NEXT:    br i1 false, label [[IF_THEN_SPLIT:%.*]], label [[FOR_INC_SPLIT]]
+; CHECK:       if.then.split:
+; CHECK-NEXT:    [[SRC_ARRAYIDX_SPLIT:%.*]] = getelementptr inbounds i64, i64* [[SRC]], i64 [[IV_SPLIT]]
+; CHECK-NEXT:    [[VAL_SPLIT:%.*]] = load i64, i64* [[SRC_ARRAYIDX_SPLIT]], align 4
+; CHECK-NEXT:    [[DST_ARRAYIDX_SPLIT:%.*]] = getelementptr inbounds i64, i64* [[DST]], i64 [[IV_SPLIT]]
+; CHECK-NEXT:    store i64 [[VAL_SPLIT]], i64* [[DST_ARRAYIDX_SPLIT]], align 4
+; CHECK-NEXT:    br label [[FOR_INC_SPLIT]]
+; CHECK:       for.inc.split:
+; CHECK-NEXT:    [[INC_SPLIT]] = add nuw nsw i64 [[IV_SPLIT]], 1
+; CHECK-NEXT:    [[COND_SPLIT:%.*]] = icmp sge i64 [[INC_SPLIT]], [[N]]
+; CHECK-NEXT:    br i1 [[COND_SPLIT]], label [[EXIT_LOOPEXIT:%.*]], label [[LOOP_SPLIT]]
+; CHECK:       exit.loopexit:
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+loop.ph:
+  br label %loop
+
+loop:
+  %iv = phi i64 [ %inc, %for.inc ], [ 0, %loop.ph ]
+  %cmp = icmp slt i64 %iv, %a
+  br i1 %cmp, label %if.then, label %for.inc
+
+if.then:
+  %src.arrayidx = getelementptr inbounds i64, i64* %src, i64 %iv
+  %val = load i64, i64* %src.arrayidx
+  %dst.arrayidx = getelementptr inbounds i64, i64* %dst, i64 %iv
+  store i64 %val, i64* %dst.arrayidx
+  br label %for.inc
+
+for.inc:
+  %inc = add nuw nsw i64 %iv, 1
+  %cond = icmp sge i64 %inc, %n
+  br i1 %cond, label %exit, label %loop
+
+exit:
+  ret void
+}
+
+define void @split_loop_bound_inc_with_step_is_not_one(i64 %a, i64* noalias %src, i64* noalias %dst, i64 %n) {
+; CHECK-LABEL: @split_loop_bound_inc_with_step_is_not_one(
+; CHECK-NEXT:  loop.ph:
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ [[INC:%.*]], [[FOR_INC:%.*]] ], [ 0, [[LOOP_PH:%.*]] ]
+; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i64 [[IV]], [[A:%.*]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[IF_THEN:%.*]], label [[FOR_INC]]
+; CHECK:       if.then:
+; CHECK-NEXT:    [[SRC_ARRAYIDX:%.*]] = getelementptr inbounds i64, i64* [[SRC:%.*]], i64 [[IV]]
+; CHECK-NEXT:    [[VAL:%.*]] = load i64, i64* [[SRC_ARRAYIDX]], align 4
+; CHECK-NEXT:    [[DST_ARRAYIDX:%.*]] = getelementptr inbounds i64, i64* [[DST:%.*]], i64 [[IV]]
+; CHECK-NEXT:    store i64 [[VAL]], i64* [[DST_ARRAYIDX]], align 4
+; CHECK-NEXT:    br label [[FOR_INC]]
+; CHECK:       for.inc:
+; CHECK-NEXT:    [[INC]] = add nuw nsw i64 [[IV]], 2
+; CHECK-NEXT:    [[COND:%.*]] = icmp sgt i64 [[INC]], [[N:%.*]]
+; CHECK-NEXT:    br i1 [[COND]], label [[EXIT:%.*]], label [[LOOP]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+loop.ph:
+  br label %loop
+
+loop:
+  %iv = phi i64 [ %inc, %for.inc ], [ 0, %loop.ph ]
+  %cmp = icmp slt i64 %iv, %a
+  br i1 %cmp, label %if.then, label %for.inc
+
+if.then:
+  %src.arrayidx = getelementptr inbounds i64, i64* %src, i64 %iv
+  %val = load i64, i64* %src.arrayidx
+  %dst.arrayidx = getelementptr inbounds i64, i64* %dst, i64 %iv
+  store i64 %val, i64* %dst.arrayidx
+  br label %for.inc
+
+for.inc:
+  %inc = add nuw nsw i64 %iv, 2
+  %cond = icmp sgt i64 %inc, %n
+  br i1 %cond, label %exit, label %loop
+
+exit:
+  ret void
+}
+
+define void @split_loop_bound_inc_with_ne(i64 %a, i64* noalias %src, i64* noalias %dst, i64 %n) {
+; CHECK-LABEL: @split_loop_bound_inc_with_ne(
+; CHECK-NEXT:  loop.ph:
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ [[INC:%.*]], [[FOR_INC:%.*]] ], [ 0, [[LOOP_PH:%.*]] ]
+; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i64 [[IV]], [[A:%.*]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[IF_THEN:%.*]], label [[FOR_INC]]
+; CHECK:       if.then:
+; CHECK-NEXT:    [[SRC_ARRAYIDX:%.*]] = getelementptr inbounds i64, i64* [[SRC:%.*]], i64 [[IV]]
+; CHECK-NEXT:    [[VAL:%.*]] = load i64, i64* [[SRC_ARRAYIDX]], align 4
+; CHECK-NEXT:    [[DST_ARRAYIDX:%.*]] = getelementptr inbounds i64, i64* [[DST:%.*]], i64 [[IV]]
+; CHECK-NEXT:    store i64 [[VAL]], i64* [[DST_ARRAYIDX]], align 4
+; CHECK-NEXT:    br label [[FOR_INC]]
+; CHECK:       for.inc:
+; CHECK-NEXT:    [[INC]] = add nuw nsw i64 [[IV]], 1
+; CHECK-NEXT:    [[COND:%.*]] = icmp ne i64 [[INC]], [[N:%.*]]
+; CHECK-NEXT:    br i1 [[COND]], label [[EXIT:%.*]], label [[LOOP]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+loop.ph:
+  br label %loop
+
+loop:
+  %iv = phi i64 [ %inc, %for.inc ], [ 0, %loop.ph ]
+  %cmp = icmp slt i64 %iv, %a
+  br i1 %cmp, label %if.then, label %for.inc
+
+if.then:
+  %src.arrayidx = getelementptr inbounds i64, i64* %src, i64 %iv
+  %val = load i64, i64* %src.arrayidx
+  %dst.arrayidx = getelementptr inbounds i64, i64* %dst, i64 %iv
+  store i64 %val, i64* %dst.arrayidx
+  br label %for.inc
+
+for.inc:
+  %inc = add nuw nsw i64 %iv, 1
+  %cond = icmp ne i64 %inc, %n
+  br i1 %cond, label %exit, label %loop
+
+exit:
+  ret void
+}
+
+define void @split_loop_bound_dec_with_slt(i64 %a, i64* noalias %src, i64* noalias %dst, i64 %n) {
+; CHECK-LABEL: @split_loop_bound_dec_with_slt(
+; CHECK-NEXT:  loop.ph:
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ [[DEC:%.*]], [[FOR_DEC:%.*]] ], [ 0, [[LOOP_PH:%.*]] ]
+; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i64 [[IV]], [[A:%.*]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[IF_THEN:%.*]], label [[FOR_DEC]]
+; CHECK:       if.then:
+; CHECK-NEXT:    [[SRC_ARRAYIDX:%.*]] = getelementptr inbounds i64, i64* [[SRC:%.*]], i64 [[IV]]
+; CHECK-NEXT:    [[VAL:%.*]] = load i64, i64* [[SRC_ARRAYIDX]], align 4
+; CHECK-NEXT:    [[DST_ARRAYIDX:%.*]] = getelementptr inbounds i64, i64* [[DST:%.*]], i64 [[IV]]
+; CHECK-NEXT:    store i64 [[VAL]], i64* [[DST_ARRAYIDX]], align 4
+; CHECK-NEXT:    br label [[FOR_DEC]]
+; CHECK:       for.dec:
+; CHECK-NEXT:    [[DEC]] = sub nuw nsw i64 [[IV]], 1
+; CHECK-NEXT:    [[COND:%.*]] = icmp slt i64 [[DEC]], [[N:%.*]]
+; CHECK-NEXT:    br i1 [[COND]], label [[EXIT:%.*]], label [[LOOP]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+loop.ph:
+  br label %loop
+
+loop:
+  %iv = phi i64 [ %dec, %for.dec ], [ 0, %loop.ph ]
+  %cmp = icmp slt i64 %iv, %a
+  br i1 %cmp, label %if.then, label %for.dec
+
+if.then:
+  %src.arrayidx = getelementptr inbounds i64, i64* %src, i64 %iv
+  %val = load i64, i64* %src.arrayidx
+  %dst.arrayidx = getelementptr inbounds i64, i64* %dst, i64 %iv
+  store i64 %val, i64* %dst.arrayidx
+  br label %for.dec
+
+for.dec:
+  %dec = sub nuw nsw i64 %iv, 1
+  %cond = icmp slt i64 %dec, %n
+  br i1 %cond, label %exit, label %loop
+
+exit:
+  ret void
+}
+
+define void @split_loop_bound_dec_with_sle(i64 %a, i64* noalias %src, i64* noalias %dst, i64 %n) {
+; CHECK-LABEL: @split_loop_bound_dec_with_sle(
+; CHECK-NEXT:  loop.ph:
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ [[DEC:%.*]], [[FOR_DEC:%.*]] ], [ 0, [[LOOP_PH:%.*]] ]
+; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i64 [[IV]], [[A:%.*]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[IF_THEN:%.*]], label [[FOR_DEC]]
+; CHECK:       if.then:
+; CHECK-NEXT:    [[SRC_ARRAYIDX:%.*]] = getelementptr inbounds i64, i64* [[SRC:%.*]], i64 [[IV]]
+; CHECK-NEXT:    [[VAL:%.*]] = load i64, i64* [[SRC_ARRAYIDX]], align 4
+; CHECK-NEXT:    [[DST_ARRAYIDX:%.*]] = getelementptr inbounds i64, i64* [[DST:%.*]], i64 [[IV]]
+; CHECK-NEXT:    store i64 [[VAL]], i64* [[DST_ARRAYIDX]], align 4
+; CHECK-NEXT:    br label [[FOR_DEC]]
+; CHECK:       for.dec:
+; CHECK-NEXT:    [[DEC]] = sub nuw nsw i64 [[IV]], 1
+; CHECK-NEXT:    [[COND:%.*]] = icmp sle i64 [[DEC]], [[N:%.*]]
+; CHECK-NEXT:    br i1 [[COND]], label [[EXIT:%.*]], label [[LOOP]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+loop.ph:
+  br label %loop
+
+loop:
+  %iv = phi i64 [ %dec, %for.dec ], [ 0, %loop.ph ]
+  %cmp = icmp slt i64 %iv, %a
+  br i1 %cmp, label %if.then, label %for.dec
+
+if.then:
+  %src.arrayidx = getelementptr inbounds i64, i64* %src, i64 %iv
+  %val = load i64, i64* %src.arrayidx
+  %dst.arrayidx = getelementptr inbounds i64, i64* %dst, i64 %iv
+  store i64 %val, i64* %dst.arrayidx
+  br label %for.dec
+
+for.dec:
+  %dec = sub nuw nsw i64 %iv, 1
+  %cond = icmp sle i64 %dec, %n
+  br i1 %cond, label %exit, label %loop
+
+exit:
+  ret void
+}
+
+

llvm/utils/gn/secondary/llvm/lib/Transforms/Scalar/BUILD.gn

sources = [
     "Reg2Mem.cpp",
     "RewriteStatepointsForGC.cpp",
     "SCCP.cpp",
     "SROA.cpp",
     "Scalar.cpp",
     "ScalarizeMaskedMemIntrin.cpp",
     "Scalarizer.cpp",
     "SeparateConstOffsetFromGEP.cpp",
+    "SimpleLoopBoundSplit.cpp",
     "SimpleLoopUnswitch.cpp",
     "SimplifyCFGPass.cpp",
     "Sink.cpp",
     "SpeculateAroundPHIs.cpp",
     "SpeculativeExecution.cpp",
     "StraightLineStrengthReduce.cpp",
     "StructurizeCFG.cpp",
     "TailRecursionElimination.cpp",
     "WarnMissedTransforms.cpp",
   ]
 }