[WIP][LoopIdiom] Teach LNIR to versioning loops and add runtime check

[eopXD]

Summary

Teach LNIR to add runtime upon the loop nest for runtime-determined store size.
Only versioning on the top-level loop is a trade-off between this optimization
and the exponential growth of versioning.

LNIR will perform identical to the current LIR if the runtime detects negative
value or too-large values.

[lebedev.ri]

Why is this beneficial?

llvm/test/Transforms/LoopIdiom/memset-runtime-lnir.ll

1

Please use update script to autogenerate check lines

[eopXD]

In D104636#2830325, @lebedev.ri wrote:

Why is this beneficial?

I shall quote from D104179 as @qianzhen stated this optimization clearly:

When the loop idiom transformation processes a memset instruction in a loop, currently it only handles the memset with a compile-time constant size. The motivation of this work is to relax this limitation, so that a memset with a variable size in a loop may still be processed and promoted to a larger memset if it passes all the eligibility checks. Performance-wise, promoting the memset in a loop to a larger memset reduces the number of calls to memset; hence reducing the overall call overhead.
A similar technique may also apply to the memcpy with a variable size in a loop.

[eopXD]

llvm/test/Transforms/LoopIdiom/memset-runtime-lnir.ll

1

I have never auto-generated check lines before. May I ask if there is some resource for me to explore this?

[lebedev.ri]

In D104636#2830333, @eopXD wrote:

In D104636#2830325, @lebedev.ri wrote:

Why is this beneficial?

I shall quote from D104179 as @qianzhen stated this optimization clearly:

When the loop idiom transformation processes a memset instruction in a loop, currently it only handles the memset with a compile-time constant size. The motivation of this work is to relax this limitation, so that a memset with a variable size in a loop may still be processed and promoted to a larger memset if it passes all the eligibility checks. Performance-wise, promoting the memset in a loop to a larger memset reduces the number of calls to memset; hence reducing the overall call overhead.
A similar technique may also apply to the memcpy with a variable size in a loop.

This only reiterates what this patch does, which was pretty obvious, and does not answer my question.
More concretely, can the scalar loop be expected to clear more than i64 -1 bytes of memory?
If not, why can't the byte count to be cleared can't be calculated by promoting to i64, and multiplying with saturation?

[xbolva00]

I am quite skeptical how useful this can be in practise. Any motivation examples from real world codes/benchmarks?

llvm/test/Transforms/LoopIdiom/memset-runtime-lnir.ll

7

LoopFlatten pass could convert two loops to one, no? Than you dont need to teach this pass about this pattern.

Btw, is this common pattern? Can you show us some motivation examples? Some hits in benchmarks?

22

So we have original loops and memset, which could be expanded to series of stores. Nightmare for codesize..

[eopXD]

Make testcase more precise to optimization this patch provides.

[eopXD]

Thank you @lebedev.ri and @xbolva00 for leaving comments.
I would follow up with benchmarks of the patch.

llvm/test/Transforms/LoopIdiom/memset-runtime-lnir.ll

7

Yes, LoopFlatten does convert two loops into one. Sorry that my example is misleading. I have adjusted the test case so LoopFlatten is irrelevant.

In the new test case the memset is runtime determined and cannot be optimized by current LoopIdiomRecognize, which this patch deals with the scenario.

To deal with the scenario there should be runtime checks to make sure the optimization is safe, so versioning is needed. To avoid exponential versioning growths, we can do 1 versioning for every nested loop. That is where the LoopNestPass comes in handy. The pass runs on LoopNest which constructs on a whole nested loop (doesn't run on a sub-loop).

22

I think this pass does the opposite. It processes series of store of a loop into a single memset.

The code size increase scenario by this patch is when versioning happens.
(Original LoopIdiomRecognize doesn't involve versioning)

[lebedev.ri]

llvm/test/Transforms/LoopIdiom/memset-runtime-lnir.ll

22

The code size increase scenario by this patch is when versioning happens.

Isn't that the @xbolva00's comment in the first place?

[eopXD]

Accidentally marked done, undone-ed it.
No bad intentions there.

llvm/test/Transforms/LoopIdiom/memset-runtime-lnir.ll

22

I think I have misunderstood the english. I originally thought series of store are multiple store instructions.

Yes, the versioning would make code size increase. I think it should be on the user whether they want this optimization to be turnt on. I added ForceNoLoopVersion as a compile option. If ForceNoLoopVersion = true, then no runtime checks will be added and the pass will only process on constant sizes.

[eopXD]

Fix some clang-format.

[fhahn]

llvm/test/Transforms/LoopIdiom/memset-runtime-lnir.ll

1

You can use the llvm/utils/update_test_checks.py script to automatically generate check lines.

36

I'm not sure if I am missing something, but this test has just a single loop, so it's a 'trivial' loop nest, right?

Couldn't this case be handled without making it a loop nest pass, by just checking if there's no parent loop? And even if there's a parent loop, wouldn't it also be possible to transform the inner loop to a wider memset, without the parents being perfectly nested?

[eopXD]

update code to let it run correctly.

[eopXD]

Generate check lines with script.

[eopXD]

llvm/test/Transforms/LoopIdiom/memset-runtime-lnir.ll

36

Yes you are right. This example does not show why LoopNest is needed.

Current LIR only deals with constant store size (or memset size). This patch uses SCEV to let LIR deal with runtime sizes. If we deal with runtime sizes, we will need to add runtime check for it.

if (runtime_check) {
  //optimized code
} else 
  // code that does not optimize runtime variables
}

With LIR, we can certainly transfer loops from inner loop to a wider one until it reaches the outer most. However if we perform it layer by layer, the total versions created will increase exponentially. To prevent this from happening, we create only 1 if-else for versioning at the top-loop. This is where LoopNest comes in.

Thank you for reminding, I shall add an example to show this.

[eopXD]

Address comments.

1. Make processLoopMemset able to deal with smax expressions with constant operands that are loop guards.
   
   How: If operands are constant, we can fold them and add runtime checks when we version and make sure our folding on smax is safe.

2. Added nested testcase that shows the necessity of using LoopNest.
   
   Why: If we use the current LIR with this patch, which seeks to optimize on runtime determined variables, the versioning would happen loop-by-loop. In other word, the pass would need to generate versioning for every loop until the pass hoists the memset to the outermost-loop's preheader. The LNIR (LoopNestIdiomRecognize) would make only 1 versioning outside of the outer-most loop to prevent this from happening.

[eopXD]

@lebedev.ri

May I ask what is your main concern to this patch?
I would be glad to discuss and resolve it.

[eopXD]

llvm/test/Transforms/LoopIdiom/memset-runtime-lnir.ll

36

Hi @fhahn,
I have added nested test-case which shows improvement of this patch (support IdiomRecognize optimization to runtime-determined variables) and the necessity of LoopNest structure (version on top-level loop).
May I mark thread as done?

[yurai007]

Just minor comment regarding potential benefits and benchmarking. If I understand patch correctly it flatten multilevel loop with memset into one memset. According simple microbenchmarks: https://godbolt.org/z/MTnYcvvYo on my x86-64 Skylake flattening memset in double loop (memset_3D) into 1 memset gives between even 800% performance boost (on small WS) to ~80% boost (when WS > LLC).
But how useful such transformation would be in practice? I'm not sure. We need to keep in mind that memset is usually just part of initialization/reusing memory code so in real world benchmarks flattening memsets loop may be less beneficial than microbenchmarks shows.

[eopXD]

gentle ping

[eopXD]

In D104636#2879853, @yurai007 wrote:

But how useful such transformation would be in practice? I'm not sure. We need to keep in mind that memset is usually just part of initialization/reusing memory code so in real world benchmarks flattening memsets loop may be less beneficial than microbenchmarks shows.

In Fortran, initialization of multi-dimensional arrays uses one liners like

A = 0.0

When A is multi-dimensional, it would be converted to loop-nests in LLVM-IR. For example if A is 3-D then the LLVM IR would be like the following. This nested store operation pattern is a common pattern to exist in the language of Fortran.

for i ...
  for j ...
    for k ...
      A[i][j][k] = 0;

[efriedma]

I'm not sure we actually need to version the loop to handle overflow.

In any given address-space, there are at most 2^N bytes addressable by "gep ptr, i" where N is DataLayout::getIndexTypeSizeInBits(). Assuming the memset isn't volatile, there isn't any point to storing to an address more than once. So we only actually need to memset min(2^N, TotalBytes) bytes. You should be able to pass that number to memset.

[lebedev.ri]

In D104636#2886251, @efriedma wrote:

I'm not sure we actually need to version the loop to handle overflow.

That was my comment, too, and i've yet to see a concise explanation why that isn't the case.

In any given address-space, there are at most 2^N bytes addressable by "gep ptr, i" where N is DataLayout::getIndexTypeSizeInBits(). Assuming the memset isn't volatile, there isn't any point to storing to an address more than once. So we only actually need to memset min(2^N, TotalBytes) bytes. You should be able to pass that number to memset.

[eopXD]

Hi @efriedma,

I am not sure consecutive memory won't exceed 2^N bytes, but we cannot think of a scenario that it can. Thank you for stating this valid point.

However the current code inside LoopIdiomRecognize::processLoopMemset , for the constant size the pass would also check for size overflow. I am curious of why it is originally needed here? Do you have any idea why is the check needed? (the commit history is out of the Phabricator's reach)

// Reject memsets that are so large that they overflow an unsigned.
  uint64_t SizeInBytes = cast<ConstantInt>(MSI->getLength())->getZExtValue();
  if ((SizeInBytes >> 32) != 0)
    return false;

---

Assume we don't need runtime check for size overflow, we still need runtime checks for the assumptions made to fold SCEV expressions that enable the optimization. So versioning would still be needed.

[efriedma]

In D104636#2896872, @eopXD wrote:

However the current code inside LoopIdiomRecognize::processLoopMemset , for the constant size the pass would also check for size overflow. I am curious of why it is originally needed here? Do you have any idea why is the check needed? (the commit history is out of the Phabricator's reach)

Code originates from rG8643810eded6eef8ad2753478a8403437695228f . As for why, not sure. There isn't any obvious reason it's necessary.

Assume we don't need runtime check for size overflow, we still need runtime checks for the assumptions made to fold SCEV expressions that enable the optimization. So versioning would still be needed.

Why can't we use the SCEV expression for the trip count as-is?

[eopXD]

Assume we don't need runtime check for size overflow, we still need runtime checks for the assumptions made to fold SCEV expressions that enable the optimization. So versioning would still be needed.

Why can't we use the SCEV expression for the trip count as-is?

The SCEV of trip count may contain smax which would make the memset size not comparable in processLoopMemset. To conservatively fold the smax expression a runtime check is added.

In a do-while loop of the following, the trip-count SCEV would be (1 smax (sext i32 %n to i64)). To fold the SCEV we add run-check condition for n >= 1, and fold the expression into sext i32 %n to i64.

int i = 0;
do {
  ++i;
}  while (i < n);

---

An example would be the 2nd test case in memset-runtime.ll.
For the inner-loop, the optimized memset instruction would have the memsetSizeSCEV contain smax expression since NumBytesSCEV = TripCountSCEV * StoreSizeSCEV

Calculate NumBytesSCEV = TripCountSCEV * StoreSizeSCEV
  TripCountSCEV: (1 smax (sext i32 %m to i64))
  StoreSizeSCEV: (4 * (sext i32 %o to i64))<nsw>
  NumBytesSCEV: (4 * (sext i32 %o to i64) * (1 smax (sext i32 %m to i64)))

Then in the outer-loop when the pass want to compare check whether memsetSizeSCEV == pointerStrideSCEV we need to fold the expression to eliminate smax so that the comparison can be performed. If the folded expression is successful then the pass would proceed to perform the optimization for the outer loop.

MemsetSizeSCEV: (4 * (sext i32 %o to i64) * (1 smax (sext i32 %m to i64)))
PositiveStrideSCEV: (4 * (sext i32 %m to i64) * (sext i32 %o to i64))
Try to convert SCEV expression and compare again
  MemsetSCEVConv: (4 * (zext i32 %m to i64) * (zext i32 %o to i64))
  PositiveStrideSCEVConv: (4 * (zext i32 %m to i64) * (zext i32 %o to i64))

[efriedma]

Yes, I guess you need to version to handle that case in particular. I'd like to avoid versioning in simpler cases, though.

I have to ask; is that case actually showing up in real code? Usually, people prefer for loops over do-while loops in situations like that. If you write an equivalent test using for loops, SCEV should simplify the backedge-taken count.

[eopXD]

Address comments.

• no need to check overflow, the assumption is no consecutive memory exceeds 2^N (where N is DataLayout::getIndexTypeSizeInBits()).
• add nested for-loop to testcase

[eopXD]

SCEV folding is still needed for for-loop test case.

void test(int n, int m, int o, int *ar) {
  for (int i=0; i<n; ++i) {
    for (int j=0; j<m; ++j) {
      int *arr = ar + i * m * o + j * o;
      memset(arr, 0, o * sizeof(int));      
    }
  }
}

For the inner loop:

MemsetSizeSCEV: (4 * (sext i32 %o to i64))<nsw>
PositiveStrideSCEV: (4 * (sext i32 %o to i64))<nsw>
Calculate NumBytesS = TripCountS * StoreSizeSCEV
  TripCountS: (zext i32 %m to i64)
  StoreSizeSCEV: (4 * (sext i32 %o to i64))<nsw>
  NumBytesS: (4 * (zext i32 %m to i64) * (sext i32 %o to i64))

Then in the outer-loop, to compare MemsetSizeSCEV to the PointerStrideSCEV, the pass should convert sext to zext for comparison, which is the SCEV folding and runtime check is added.

MemsetSizeSCEV: (4 * (zext i32 %m to i64) * (sext i32 %o to i64))
PositiveStrideSCEV: (4 * (sext i32 %m to i64) * (sext i32 %o to i64))
Try to convert SCEV expression and compare again
  MemsetSCEVConv: (4 * (zext i32 %m to i64) * (zext i32 %o to i64))
  PositiveStrideSCEVConv: (4 * (zext i32 %m to i64) * (zext i32 %o to i64))

[efriedma]

Oh, hmm. Yes, you need to do some sort of SCEV folding to handle that case, but you can perform the check at compile-time using something like ScalarEvolution::isLoopEntryGuardedByCond.

In D104636#2902181, @eopXD wrote:

• no need to check overflow, the assumption is no consecutive memory exceeds 2^N (where N is DataLayout::getIndexTypeSizeInBits()).

Maybe to be conservative, restrict this to memset in address-space zero.

[efriedma]

In D104636#2905451, @efriedma wrote:

In D104636#2902181, @eopXD wrote:

• no need to check overflow, the assumption is no consecutive memory exceeds 2^N (where N is DataLayout::getIndexTypeSizeInBits()).

Maybe to be conservative, restrict this to memset in address-space zero.

The reason for this is that in other address-spaces, you might need to saturate the memset amount, instead of just ignoring overflow, I think.

[eopXD]

This comment was removed by eopXD.

[eopXD]

Revert to previous edition.

[eopXD]

Address comments.

For SCEV expression MemsetSize and PointerStride of a memset instruction, the pass
would first fold expressions that is already guarded by the loop guard. If the
folded expressions are not equal, LoopIdiomRecognize will abort. LoopNestIdiomRecognize
would proceed to try convert the SCEV and add appropriate runtime checks.
If the converted expression are equal, LNIR would proceed the optimization and do
versioning at the outer-most loop.

Added separate testcase files for LIR and LNIR.
For LIR, it can deal with runtime determined variables when runtime check is required.
For LNIR, it will do versioning and add runtime check if needed.

[lebedev.ri]

High-level comment: let's not convolute things too much.
I'm honestly already at loss with the current diff, and (to me!) not very clear answers to the questions.
Let's at least deal with proper loop-idiom patch first,
and maybe follow-up with a loop-nest loop idiom changes.

[eopXD]

In D104636#2921989, @lebedev.ri wrote:

High-level comment: let's not convolute things too much.
I'm honestly already at loss with the current diff, and (to me!) not very clear answers to the questions.
Let's at least deal with proper loop-idiom patch first,
and maybe follow-up with a loop-nest loop idiom changes.

Sure.
Let me open a new patch on the proper loop-idiom and maybe come back here after that.
Thank you for following up with this patch.

[eopXD]

Created a new patch D107353 that deals with the proper loop-idiom.
Will come back and modify after D107353 is accepted.

[lebedev.ri]

Patch description does not explain why versioning is needed in the first place.

[eopXD]

In D104636#3196900, @lebedev.ri wrote:

Patch description does not explain why versioning is needed in the first place.

Yes you are right. I will need some time to rebase and update this patch.

[eopXD]

Also, I understand that the LNIR idea might not ultimately justify itself to be merged into upstream.
So after this patch is ready for review maybe we can have a discussion on the LoopOpt Work Group.

[lebedev.ri]

This review seems to be stuck/dead, consider abandoning if no longer relevant.

llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp

 //===- LoopIdiomRecognize.cpp - Loop idiom recognition --------------------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 //
static cl::opt<bool> ForceNoLoopVersion(
     cl::desc("Force not to create loop versions if the user guarantees that"
              "the length of each array dimension is positive value, and"
              "the multiplication of lengths of all array dimensions does not"
              "exceeds the range of type size_t"),
     cl::init(false), cl::Hidden);
 
 namespace {
 
-typedef SmallSet<const SCEV *, 10> SCEVSet;
 typedef DenseMap<const SCEV *, int> SCEVConstValPairMap;
 
 /// A helper class to do the following SCEV expression conversions.
 ///   1) "sext %val" to "zext %val"
 ///   2) "SOME_CONSTANT_VALUE smax %val" to "%val"
 class SCEVExprConverter {
 public:
+  Loop *CurLoop;
   ScalarEvolution &SE;
   SCEVConstValPairMap CheckSltMap;
 
   SCEVExprConverter(ScalarEvolution &SE)
       : SE(SE) {}
 
-  const SCEV *convertSCEV(const SCEV *Expr);
+  const SCEV *convertSCEV(const SCEV *Expr, bool AddRuntimCheck);
 };
 
 class LoopIdiomRecognize {
   Loop *CurLoop = nullptr;
   LoopNest *LN;
   Loop *TopLoop = nullptr;
   Loop *FallBackLoop = nullptr;
   BasicBlock *RuntimeCheckBB = nullptr;
void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.addPreserved<MemorySSAWrapperPass>();
     getLoopAnalysisUsage(AU);
   }
 };
 
 } // end anonymous namespace
 
 /// Implementation of SCEVExprConverter.
-const SCEV *SCEVExprConverter::convertSCEV(const SCEV *Expr) {
+/// Tries to fold the SCEV with regard to loop guards of CurLoop
+const SCEV *SCEVExprConverter::convertSCEV(const SCEV *Expr, bool AddRuntimeCheck) {
   switch (Expr->getSCEVType()) {
     case scConstant:
     case scUnknown:
     case scCouldNotCompute:
       return Expr;
     case scTruncate: {
       const SCEVTruncateExpr *Trunc = cast<SCEVTruncateExpr>(Expr);
       Type *Ty = Trunc->getType();
-      const SCEV *NewTrunc = convertSCEV(Trunc->getOperand());
+      const SCEV *NewTrunc = convertSCEV(Trunc->getOperand(), AddRuntimeCheck);
       return SE.getTruncateExpr(NewTrunc, Ty);
     }
     case scZeroExtend: {
       const SCEVZeroExtendExpr *Zext = cast<SCEVZeroExtendExpr>(Expr);
       Type *Ty = Zext->getType();
-      const SCEV *NewZext = convertSCEV(Zext->getOperand());
+      const SCEV *NewZext = convertSCEV(Zext->getOperand(), AddRuntimeCheck);
       return SE.getZeroExtendExpr(NewZext, Ty);
     }
     case scSignExtend: {
-      // Record the original SCEV sext expression, and
-      // convert it to zext.
+      // Return original SCEV if expression is not guarded by loop with Zero and
+      // dont want to add runtime check. Otherwise we fold constant and add appropriate
+      // runtime check.
       const SCEVSignExtendExpr *Sext = cast<SCEVSignExtendExpr>(Expr);
+      if (SE.isLoopEntryGuardedByCond(CurLoop, ICmpInst::ICMP_SGE, Sext, SE.getZero(Sext->getType())) == false) {
+        if (AddRuntimeCheck == false)
+          return Sext;
         if (CheckSltMap[Sext] < 0)
           CheckSltMap[Sext] = 0;
-      Type *Ty = Sext->getType();
-      const SCEV *NewZext = convertSCEV(Sext->getOperand());
-      return SE.getZeroExtendExpr(NewZext, Ty);
+      }
+      const SCEV *NewZext = convertSCEV(Sext->getOperand(), AddRuntimeCheck);
+      return SE.getZeroExtendExpr(NewZext, Sext->getType());
     }
     case scAddExpr: {
       const SCEVAddExpr *Add = cast<SCEVAddExpr>(Expr);
-      const SCEV *NewAdd = convertSCEV(Add->getOperand(0));
+      const SCEV *NewAdd = convertSCEV(Add->getOperand(0), AddRuntimeCheck);
       for (int I = 1, E = Add->getNumOperands(); I != E; ++I) {
-        NewAdd = SE.getAddExpr(NewAdd, convertSCEV(Add->getOperand(I)));
+        NewAdd = SE.getAddExpr(NewAdd, convertSCEV(Add->getOperand(I), AddRuntimeCheck));
       }
       return NewAdd;
     }
     case scMulExpr: {
       const SCEVMulExpr *Mul = cast<SCEVMulExpr>(Expr);
-      const SCEV *NewMul = convertSCEV(Mul->getOperand(0));
+      const SCEV *NewMul = convertSCEV(Mul->getOperand(0), AddRuntimeCheck);
       for (int I = 1, E = Mul->getNumOperands(); I != E; ++I) {
-        NewMul = SE.getMulExpr(NewMul, convertSCEV(Mul->getOperand(I)));
+        NewMul = SE.getMulExpr(NewMul, convertSCEV(Mul->getOperand(I), AddRuntimeCheck));
       }
       return NewMul;
     }
     case scUDivExpr: {
       const SCEVUDivExpr *UDiv = cast<SCEVUDivExpr>(Expr);
-      const SCEV *NewLHS = convertSCEV(UDiv->getLHS());
-      const SCEV *NewRHS = convertSCEV(UDiv->getRHS());
+      const SCEV *NewLHS = convertSCEV(UDiv->getLHS(), AddRuntimeCheck);
+      const SCEV *NewRHS = convertSCEV(UDiv->getRHS(), AddRuntimeCheck);
       return SE.getUDivExpr(NewLHS, NewRHS);
     }
     case scAddRecExpr:
       assert(false && "Do not expect AddRec here!");
     case scUMaxExpr: {
       const SCEVUMaxExpr *UMax = cast<SCEVUMaxExpr>(Expr);
-      const SCEV *NewUMax = convertSCEV(UMax->getOperand(0));
+      const SCEV *NewUMax = convertSCEV(UMax->getOperand(0), AddRuntimeCheck);
       for (int I = 1, E = UMax->getNumOperands(); I != E; ++I) {
-        NewUMax = SE.getUMaxExpr(NewUMax, convertSCEV(UMax->getOperand(I)));
+        NewUMax = SE.getUMaxExpr(NewUMax, convertSCEV(UMax->getOperand(I), AddRuntimeCheck));
       }
       return NewUMax;
     }
     case scSMaxExpr: {
+      // Return original SCEV if expression is not guarded by loop with Constant and
+      // dont want to add runtime check. Otherwise we fold constant and add appropriate
+      // runtime check.
       const SCEVSMaxExpr *SMax = cast<SCEVSMaxExpr>(Expr);
       const int NumOfOps = SMax->getNumOperands();
       bool Fold = false;
-      // If an operand is constant zero, it will be the first operand.
+      // If an operand is constant, it will be the first operand.
       const SCEV *SMaxOp0 = SMax->getOperand(0);
-      const SCEVConstant *LHSC = dyn_cast<SCEVConstant>(SMaxOp0);
+      const SCEVConstant *Cst = dyn_cast<SCEVConstant>(SMaxOp0);
 
-      if (LHSC) {
-        // fold the constant with the other operands. there will be
-        // runtime-check to check our assumption for folding the smax is
-        // feasible.
+      if (Cst) {
+        // check if the operand is guarded to the constant
+        // if not, return orignal expression
         Fold = true;
         for (int I = 1, E = NumOfOps; I != E; ++I) {
           auto Ev = SMax->getOperand(I);
-          auto Cst = LHSC->getAPInt().roundToDouble();
-          if (CheckSltMap[Ev] < Cst)
-           CheckSltMap[Ev] = Cst;
+          if (SE.isLoopEntryGuardedByCond(CurLoop, ICmpInst::ICMP_SGE, Ev, Cst) == false) {
+            if (AddRuntimeCheck == false)
+              return SMax;
+            int CstValue = Cst->getAPInt().roundToDouble();
+            if (CheckSltMap[SMax] < CstValue)
+              CheckSltMap[SMax] = CstValue;
+          }
         }
       }
 
       const int StartIdx = Fold ? 1 : 0;
-      const SCEV *NewSMax = convertSCEV(SMax->getOperand(StartIdx));
+      const SCEV *NewSMax = convertSCEV(SMax->getOperand(StartIdx), AddRuntimeCheck);
       for (int I = StartIdx + 1, E = NumOfOps; I != E; ++I) {
-        NewSMax = SE.getSMaxExpr(NewSMax, convertSCEV(SMax->getOperand(I)));
+        NewSMax = SE.getSMaxExpr(NewSMax, convertSCEV(SMax->getOperand(I), AddRuntimeCheck));
       }
       return NewSMax;
     }
     case scUMinExpr: {
       const SCEVUMinExpr *UMin = cast<SCEVUMinExpr>(Expr);
-      const SCEV *NewUMin = convertSCEV(UMin->getOperand(0));
+      const SCEV *NewUMin = convertSCEV(UMin->getOperand(0), AddRuntimeCheck);
       for (int I = 1, E = UMin->getNumOperands(); I != E; ++I) {
-        NewUMin = SE.getUMinExpr(NewUMin, convertSCEV(UMin->getOperand(I)));
+        NewUMin = SE.getUMinExpr(NewUMin, convertSCEV(UMin->getOperand(I), AddRuntimeCheck));
       }
       return NewUMin;
     }
     case scSMinExpr: {
       const SCEVSMinExpr *SMin = cast<SCEVSMinExpr>(Expr);
-      const SCEV *NewSMin = convertSCEV(SMin->getOperand(0));
+      const SCEV *NewSMin = convertSCEV(SMin->getOperand(0), AddRuntimeCheck);
       for (int I = 1, E = SMin->getNumOperands(); I != E; ++I) {
-        NewSMin = SE.getSMinExpr(NewSMin, convertSCEV(SMin->getOperand(I)));
+        NewSMin = SE.getSMinExpr(NewSMin, convertSCEV(SMin->getOperand(I), AddRuntimeCheck));
       }
       return NewSMin;
     }
     default:
       llvm_unreachable("Unexpected SCEV expression!");
   }
 }
 
if (IsConstantSize) {
     NegStride = SizeInBytes == -Stride;
   } else {
     // Memset size is non-constant
     // Check if the stride matches the memset size, by comparing the SCEV
     // expressions of the stride and memset size. The two expressions match
     // if they are equal. If they match, then we know that every byte is
     // touched in the loop. We only handle memset length and stride that
     // are invariant for the top level loop.
+    // To be conservative, in runtime we would not promote pointers that isn't
+    // in address space zero
     LLVM_DEBUG(dbgs() << "  memset size is non-constant\n");
-    if (LN == nullptr) {
-      LLVM_DEBUG(dbgs() << "  need to call LNIR for non-constant memset"
-                        << "optimization\n");
+    if (Pointer->getType()->getPointerAddressSpace() != 0) {
+      LLVM_DEBUG(dbgs() << "  pointer is not in address space zero\n");
       return false;
     }
     if (!SE->isLoopInvariant(MemsetSizeSCEV, TopLoop) ||
         !SE->isLoopInvariant(StrideSCEV, TopLoop)) {
       LLVM_DEBUG(dbgs() << "  memset size or stride is not a loop-invariant, "
                         << "abort\n");
       return false;
     }
 
     // compare positive direction strideSCEV with MemsizeSizeSCEV
     NegStride = StrideSCEV->isNonConstantNegative();
     const SCEV *PositiveStrideSCEV =
         NegStride ? SE->getNegativeSCEV(StrideSCEV) : StrideSCEV;
     LLVM_DEBUG(dbgs() << "  MemsetSizeSCEV: " << *MemsetSizeSCEV << "\n"
                       << "  PositiveStrideSCEV: " << *PositiveStrideSCEV
                       << "\n");
 
     if (PositiveStrideSCEV != MemsetSizeSCEV) {
-      // We will convert the SCEV expressions, and compare again.
-      // required conversion to SCEV will be saved inside Converter.
-      // if this function returns true, which means the optimization does happen,
-      // the <SCEV, APInt> pair will be added when we return to processLoopMemIntrinsic.
+      // If the original StrideSCEV and MemsetSizeSCEV does not match, the pass will
+      // fold expressions that is covered by the loop guard at loop entry.
+      // We will compare again after the folding and proceed if equal
       Converter.CheckSltMap.clear();
-      const SCEV *PositiveStrideSCEVConv =
-          Converter.convertSCEV(PositiveStrideSCEV);
-      const SCEV *MemsetSizeSCEVConv =
-          Converter.convertSCEV(MemsetSizeSCEV);
-      LLVM_DEBUG(dbgs() << "  Try to convert SCEV expression and compare again\n"
-                        << "    MemsetSCEVConv: " << *MemsetSizeSCEVConv << "\n"
-                        << "    PositiveStrideSCEVConv: "
-                        << *PositiveStrideSCEVConv << "\n");
-
-      if (PositiveStrideSCEVConv != MemsetSizeSCEVConv) {
-        LLVM_DEBUG(dbgs() << "  Converted SCEV still inequal, abort\n");
+      Converter.CurLoop = CurLoop;
+      const SCEV *FoldedPositiveStride =
+          Converter.convertSCEV(PositiveStrideSCEV, /*AddRuntimeCheck=*/false);
+      const SCEV *FoldedMemsetSize =
+          Converter.convertSCEV(MemsetSizeSCEV, /*AddRuntimeCheck=*/false);
+      LLVM_DEBUG(dbgs() << "  Try to fold SCEV expression covered by loop guard\n"
+                        << "    FoldedMemsetSCEV: " << *FoldedMemsetSize << "\n"
+                        << "    FoldedPositiveStrideSCEV: "
+                        << *FoldedPositiveStride << "\n");
+
+      if (FoldedPositiveStride != FoldedMemsetSize) {
+        if (LN == nullptr || ForceNoLoopVersion) {
+          LLVM_DEBUG(dbgs() << "  unable to do loop versioning here, abort\n");
+          return false;
+        }
+        const SCEV *ConvertedPositiveStride =
+            Converter.convertSCEV(FoldedPositiveStride, /*AddRuntimeCheck=*/true);
+        const SCEV *ConvertedMemsetSize =
+            Converter.convertSCEV(FoldedMemsetSize, /*AddRuntimeCheck=*/true);
+        LLVM_DEBUG(dbgs() << "  Try to convert SCEV expression and add appropriate runtime check\n"
+                          << "    ConvertedMemsetSCEV: " << *ConvertedMemsetSize << "\n"
+                          << "    ConvertedPositiveStrideSCEV: "
+                          << *ConvertedPositiveStride << "\n");
+        if (ConvertedPositiveStride != ConvertedMemsetSize) {
+          LLVM_DEBUG(dbgs() << "  Converted SCEV inequal, abort\n");
           return false;
         }
       }
     }
+  }
 
   // Verify that the memset value is loop invariant.  If not, we can't promote
   // the memset.
   Value *SplatValue = MSI->getValue();
   if (!SplatValue || !CurLoop->isLoopInvariant(SplatValue))
     return false;
 
   SmallPtrSet<Instruction *, 1> MSIs;
   MSIs.insert(MSI);
   bool Changed = processLoopStridedStore(
       Pointer, MemsetSizeSCEV, MaybeAlign(MSI->getDestAlignment()),
       SplatValue, MSI, MSIs, Ev, BECount, NegStride, /*IsLoopMemset=*/true);
 
   // if we have successfully changed with processLoopStridedStore
   // add the require runtime check information into list.
-  if (Changed) {
+  if (Changed && isTopLoopVersioned()) {
     for (auto Pair : Converter.CheckSltMap) {
       auto Ev = Pair.first;
       auto Cst = Pair.second;
       if (CheckSltMap[Ev] < Cst)
         CheckSltMap[Ev] = Cst;
     }
     Converter.CheckSltMap.clear();
   }
bool LoopIdiomRecognize::processLoopStridedStore(
   if (avoidLIRForMultiBlockLoop(/*IsMemset=*/true, IsLoopMemset))
     return Changed;
 
   // Okay, everything looks good, insert the memset.
 
   // NumBytes = TripCount * StoreSize
   const SCEV *TripCountS = getTripCount(BECount, IntIdxTy, CurLoop, DL, SE);
 
-  // This check is possible only for LoopNestIdiomRecognize, since we are
-  // trying to version on the top-level loop.
-  // Give up if the store size is not constant and the trip count SCEV
-  // expression is variant to the top level loop. In this sense versioning is
-  // needed and compile option enforces not to.
-  if (LN != nullptr && !SE->isLoopInvariant(TripCountS, TopLoop)) {
-    const bool IsConstantSize = isa<SCEVConstant>(StoreSizeSCEV);
-    if (IsLoopMemset && !IsConstantSize && ForceNoLoopVersion) {
-      LLVM_DEBUG(dbgs() << "requires versioning but abort becuase "
-                        << "ForceNoLoopVersion is set to true\n");
+  // If store size is not constant and we need to add runtime checks for the optimization
+  // to proceed, then versioning is required.
+  if (IsLoopMemset && !IsConstantSize && Converter.CheckSltMap.size()) {
+    if (LN == nullptr) {
+      LLVM_DEBUG(dbgs() << "requires versioning but running LoopIdiomRecognizer, "
+                        << "abort (run LoopNestIdiomRecognizer instead support versioning)\n");
+      return Changed;
+    }
+    if (!SE->isLoopInvariant(TripCountS, TopLoop) || ForceNoLoopVersion) {
+      LLVM_DEBUG(dbgs() << "abort becuase TripCount is not TopLoop's invariant "
+                        << "or ForceNoLoopVersion = true\n");
       return Changed;
     }
   }
 
   const SCEVConstant *ConstSize = dyn_cast<SCEVConstant>(StoreSizeSCEV);
   const SCEV *NumBytesS;
 
   if (ConstSize && ConstSize->getAPInt() == 1) {
bool LoopIdiomRecognize::processLoopStridedStore(
 
   // If the memset size is not a constant, we will need to version the top
   // level loop in the current loop nest with runtime checks. We are going
   // to version on only the top level loop once to avoid exponential growth
   // of versioning.
   // Here we check whether the top level clone has beed created yet, and create
   // it if it hasn't. The initial runtime check is set to false and the
   // conditions would be updated after we process all the loops.
-  const bool IsConstantSize = isa<SCEVConstant>(StoreSizeSCEV);
-  if (LN != nullptr && IsLoopMemset && !IsConstantSize && !ForceNoLoopVersion) {
-    if (!isTopLoopVersioned() && Converter.CheckSltMap.size()) {
-      LLVM_DEBUG(dbgs() << "  Create versioning for top loop because SCEV folding is needed\n");
-      versionTopLoop();
+  if (LN != nullptr && IsLoopMemset && !IsConstantSize && !ForceNoLoopVersion &&
+      !isTopLoopVersioned() && Converter.CheckSltMap.size()) {
+    LLVM_DEBUG(dbgs() << "  Create versioning for top loop because runtime check for SCEV is needed\n");
 
-      // If current loop is the top loop, versioning would change the loop's
-      // preheader to RuntimeCheckBB, so we need to reset the insert point.
-      if (CurLoop == TopLoop) {
-        Preheader = CurLoop->getLoopPreheader();
-        Builder.SetInsertPoint(Preheader->getTerminator());
-      }
-    }
-  }
 
   CallInst *NewCall;
   if (SplatValue) {
     NewCall = Builder.CreateMemSet(BasePtr, SplatValue, NumBytes,
                                    MaybeAlign(StoreAlignment));
   } else {
     // Everything is emitted in default address space
     Type *Int8PtrTy = DestInt8PtrTy;

llvm/test/Transforms/LoopIdiom/memset-runtime-lir.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
-; RUN: opt -passes="function(loop(loop-nest-idiom,loop-deletion),simplifycfg)" < %s -S | FileCheck %s
+; RUN: opt -passes="function(loop(loop-idiom,loop-deletion),simplifycfg)" < %s -S | FileCheck %s
 ; The C code to generate this testcase:
 ; void test(int ar[][m], long n, long m)
 ; {
 ;   long i;
 ;   for (i=0; i<n; ++i) {
 ;     int *arr = ar + i * m; // ar[i];
 ;     memset(arr, 0, m * sizeof(int));
 ;   }
 ; }
 ; The optimized IR should be similar to the following:
 ; void test(int ar[][m], long n, long m)
 ; {
-;   if (n < 0 || m < 0 || (n >> 32) != 0 || (4 * m >> 32) != 0)
-;     /* optimization result identical to LoopIdiomRecognize */
-;   else
-;     /* hoists memset to loop-preheader */
+;   memset(ar, 0, m * n * sizeof(int));
 ; }
 define void @test_simple(i32* nocapture %ar, i64 %n, i64 %m) {
 ; CHECK-LABEL: @test_simple(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[AR1:%.*]] = bitcast i32* [[AR:%.*]] to i8*
 ; CHECK-NEXT:    [[TMP0:%.*]] = shl nuw i64 [[M:%.*]], 2
 ; CHECK-NEXT:    [[TMP1:%.*]] = mul i64 [[M]], [[N:%.*]]
 ; CHECK-NEXT:    [[TMP2:%.*]] = shl i64 [[TMP1]], 2

 ;       memset(arr, 0, o * sizeof(int));
 ;       ++j;
 ;     } while (j < m);
 ;     ++i;
 ;   } while (i < n);
 ; }
 define void @test_nested_do_while(i32 %n, i32 %m, i32 %o, i32* nocapture %ar){
 ; CHECK-LABEL: @test_nested_do_while(
-; CHECK-NEXT:  do.body.lver.check:
-; CHECK-NEXT:    [[AR2:%.*]] = bitcast i32* [[AR:%.*]] to i8*
+; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CONV:%.*]] = sext i32 [[M:%.*]] to i64
 ; CHECK-NEXT:    [[CONV2:%.*]] = sext i32 [[O:%.*]] to i64
 ; CHECK-NEXT:    [[MUL:%.*]] = mul nsw i64 [[CONV2]], [[CONV]]
 ; CHECK-NEXT:    [[MUL8:%.*]] = shl nsw i64 [[CONV2]], 2
 ; CHECK-NEXT:    [[SMAX:%.*]] = call i64 @llvm.smax.i64(i64 [[CONV]], i64 1)
 ; CHECK-NEXT:    [[TMP0:%.*]] = call i32 @llvm.smax.i32(i32 [[N:%.*]], i32 1)
 ; CHECK-NEXT:    [[SMAX27:%.*]] = zext i32 [[TMP0]] to i64
 ; CHECK-NEXT:    [[TMP1:%.*]] = mul i64 [[CONV2]], [[CONV]]
 ; CHECK-NEXT:    [[TMP2:%.*]] = mul i64 [[SMAX]], [[CONV2]]
 ; CHECK-NEXT:    [[TMP3:%.*]] = shl i64 [[TMP2]], 2
-; CHECK-NEXT:    [[TMP4:%.*]] = mul i64 [[TMP2]], [[SMAX27]]
-; CHECK-NEXT:    [[TMP5:%.*]] = shl i64 [[TMP4]], 2
-; CHECK-NEXT:    [[TMP6:%.*]] = icmp slt i64 [[CONV]], 1
-; CHECK-NEXT:    [[TMP7:%.*]] = or i1 false, [[TMP6]]
-; CHECK-NEXT:    [[TMP8:%.*]] = icmp slt i64 [[CONV2]], 0
-; CHECK-NEXT:    [[TMP9:%.*]] = or i1 [[TMP7]], [[TMP8]]
-; CHECK-NEXT:    br i1 [[TMP9]], label [[DO_BODY_LVER_ORIG:%.*]], label [[DO_BODY_PH:%.*]]
-; CHECK:       do.body.lver.orig:
-; CHECK-NEXT:    [[I_0_LVER_ORIG:%.*]] = phi i64 [ [[INC11_LVER_ORIG:%.*]], [[DO_END_LVER_ORIG:%.*]] ], [ 0, [[DO_BODY_LVER_CHECK:%.*]] ]
-; CHECK-NEXT:    [[TMP10:%.*]] = mul i64 [[TMP1]], [[I_0_LVER_ORIG]]
-; CHECK-NEXT:    [[SCEVGEP_LVER_ORIG:%.*]] = getelementptr i32, i32* [[AR]], i64 [[TMP10]]
-; CHECK-NEXT:    [[SCEVGEP1_LVER_ORIG:%.*]] = bitcast i32* [[SCEVGEP_LVER_ORIG]] to i8*
-; CHECK-NEXT:    [[MUL3_LVER_ORIG:%.*]] = mul i64 [[MUL]], [[I_0_LVER_ORIG]]
-; CHECK-NEXT:    [[ADD_PTR_LVER_ORIG:%.*]] = getelementptr inbounds i32, i32* [[AR]], i64 [[MUL3_LVER_ORIG]]
-; CHECK-NEXT:    call void @llvm.memset.p0i8.i64(i8* align 4 [[SCEVGEP1_LVER_ORIG]], i8 0, i64 [[TMP3]], i1 false)
-; CHECK-NEXT:    br label [[DO_BODY1_LVER_ORIG:%.*]]
-; CHECK:       do.body1.lver.orig:
-; CHECK-NEXT:    [[J_0_LVER_ORIG:%.*]] = phi i64 [ 0, [[DO_BODY_LVER_ORIG]] ], [ [[INC_LVER_ORIG:%.*]], [[DO_BODY1_LVER_ORIG]] ]
-; CHECK-NEXT:    [[MUL5_LVER_ORIG:%.*]] = mul nsw i64 [[J_0_LVER_ORIG]], [[CONV2]]
-; CHECK-NEXT:    [[ADD_PTR6_LVER_ORIG:%.*]] = getelementptr inbounds i32, i32* [[ADD_PTR_LVER_ORIG]], i64 [[MUL5_LVER_ORIG]]
-; CHECK-NEXT:    [[TMP11:%.*]] = bitcast i32* [[ADD_PTR6_LVER_ORIG]] to i8*
-; CHECK-NEXT:    [[INC_LVER_ORIG]] = add nuw nsw i64 [[J_0_LVER_ORIG]], 1
-; CHECK-NEXT:    [[EXITCOND_NOT_LVER_ORIG:%.*]] = icmp eq i64 [[INC_LVER_ORIG]], [[SMAX]]
-; CHECK-NEXT:    br i1 [[EXITCOND_NOT_LVER_ORIG]], label [[DO_END_LVER_ORIG]], label [[DO_BODY1_LVER_ORIG]]
-; CHECK:       do.end.lver.orig:
-; CHECK-NEXT:    [[INC11_LVER_ORIG]] = add nuw nsw i64 [[I_0_LVER_ORIG]], 1
-; CHECK-NEXT:    [[EXITCOND28_NOT_LVER_ORIG:%.*]] = icmp eq i64 [[INC11_LVER_ORIG]], [[SMAX27]]
-; CHECK-NEXT:    br i1 [[EXITCOND28_NOT_LVER_ORIG]], label [[DO_END16:%.*]], label [[DO_BODY_LVER_ORIG]]
-; CHECK:       do.body.ph:
-; CHECK-NEXT:    call void @llvm.memset.p0i8.i64(i8* align 4 [[AR2]], i8 0, i64 [[TMP5]], i1 false)
-; CHECK-NEXT:    br label [[DO_END16]]
+; CHECK-NEXT:    br label [[DO_BODY:%.*]]
+; CHECK:       do.body:
+; CHECK-NEXT:    [[I_0:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[INC11:%.*]], [[DO_BODY]] ]
+; CHECK-NEXT:    [[TMP4:%.*]] = mul i64 [[TMP1]], [[I_0]]
+; CHECK-NEXT:    [[SCEVGEP:%.*]] = getelementptr i32, i32* [[AR:%.*]], i64 [[TMP4]]
+; CHECK-NEXT:    [[SCEVGEP1:%.*]] = bitcast i32* [[SCEVGEP]] to i8*
+; CHECK-NEXT:    [[MUL3:%.*]] = mul i64 [[MUL]], [[I_0]]
+; CHECK-NEXT:    [[ADD_PTR:%.*]] = getelementptr inbounds i32, i32* [[AR]], i64 [[MUL3]]
+; CHECK-NEXT:    call void @llvm.memset.p0i8.i64(i8* align 4 [[SCEVGEP1]], i8 0, i64 [[TMP3]], i1 false)
+; CHECK-NEXT:    [[INC11]] = add nuw nsw i64 [[I_0]], 1
+; CHECK-NEXT:    [[EXITCOND28_NOT:%.*]] = icmp eq i64 [[INC11]], [[SMAX27]]
+; CHECK-NEXT:    br i1 [[EXITCOND28_NOT]], label [[DO_END16:%.*]], label [[DO_BODY]]
 ; CHECK:       do.end16:
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %conv = sext i32 %m to i64
   %conv2 = sext i32 %o to i64
   %mul = mul nsw i64 %conv2, %conv
   %mul8 = shl nsw i64 %conv2, 2
do.end16:                                         ; preds = %do.end
   ret void
 }
 ; The C code to generate this testcase:
 ; void test(int n, int m, int o, int *ar)
 ; {
 ;   for (int i=0; i<n; ++i) {
 ;     for (int j=0; j<m; ++j) {
 ;       int *arr = ar + i * m * o + j * o;
-;       memset(arr, 0, o * sizeof(int));      
+;       memset(arr, 0, o * sizeof(int));
 ;     }
 ;   }
 ; }
 define void @test_nested_for(i32 %n, i32 %m, i32 %o, i32* %ar) {
 ; CHECK-LABEL: @test_nested_for(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[AR2:%.*]] = bitcast i32* [[AR:%.*]] to i8*
 ; CHECK-NEXT:    [[CMP3:%.*]] = icmp slt i32 0, [[N:%.*]]
 ; CHECK-NEXT:    br i1 [[CMP3]], label [[FOR_BODY_LR_PH:%.*]], label [[FOR_END11:%.*]]
 ; CHECK:       for.body.lr.ph:
 ; CHECK-NEXT:    [[CMP21:%.*]] = icmp slt i32 0, [[M:%.*]]
 ; CHECK-NEXT:    [[CONV:%.*]] = sext i32 [[O:%.*]] to i64
 ; CHECK-NEXT:    [[MUL8:%.*]] = mul i64 [[CONV]], 4
-; CHECK-NEXT:    br i1 [[CMP21]], label [[FOR_BODY_US_LVER_CHECK:%.*]], label [[FOR_END11]]
-; CHECK:       for.body.us.lver.check:
+; CHECK-NEXT:    br i1 [[CMP21]], label [[FOR_BODY_LR_PH_SPLIT_US:%.*]], label [[FOR_END11]]
+; CHECK:       for.body.lr.ph.split.us:
 ; CHECK-NEXT:    [[TMP0:%.*]] = sext i32 [[O]] to i64
 ; CHECK-NEXT:    [[TMP1:%.*]] = sext i32 [[M]] to i64
 ; CHECK-NEXT:    [[TMP2:%.*]] = sext i32 [[O]] to i64
 ; CHECK-NEXT:    [[WIDE_TRIP_COUNT10:%.*]] = zext i32 [[N]] to i64
 ; CHECK-NEXT:    [[TMP3:%.*]] = mul i64 [[TMP0]], [[TMP1]]
 ; CHECK-NEXT:    [[TMP4:%.*]] = zext i32 [[M]] to i64
 ; CHECK-NEXT:    [[TMP5:%.*]] = mul i64 [[TMP0]], [[TMP4]]
 ; CHECK-NEXT:    [[TMP6:%.*]] = shl i64 [[TMP5]], 2
 ; CHECK-NEXT:    [[TMP7:%.*]] = mul i64 [[TMP5]], [[WIDE_TRIP_COUNT10]]
 ; CHECK-NEXT:    [[TMP8:%.*]] = shl i64 [[TMP7]], 2
-; CHECK-NEXT:    [[TMP9:%.*]] = icmp slt i64 [[TMP0]], 0
-; CHECK-NEXT:    [[TMP10:%.*]] = or i1 false, [[TMP9]]
-; CHECK-NEXT:    [[TMP11:%.*]] = icmp slt i64 [[TMP1]], 0
-; CHECK-NEXT:    [[TMP12:%.*]] = or i1 [[TMP10]], [[TMP11]]
-; CHECK-NEXT:    br i1 [[TMP12]], label [[FOR_BODY_US_LVER_ORIG:%.*]], label [[FOR_BODY_US_PH:%.*]]
-; CHECK:       for.body.us.lver.orig:
-; CHECK-NEXT:    [[INDVARS_IV6_LVER_ORIG:%.*]] = phi i64 [ [[INDVARS_IV_NEXT7_LVER_ORIG:%.*]], [[FOR_INC9_US_LVER_ORIG:%.*]] ], [ 0, [[FOR_BODY_US_LVER_CHECK]] ]
-; CHECK-NEXT:    [[TMP13:%.*]] = mul i64 [[TMP3]], [[INDVARS_IV6_LVER_ORIG]]
-; CHECK-NEXT:    [[SCEVGEP_LVER_ORIG:%.*]] = getelementptr i32, i32* [[AR]], i64 [[TMP13]]
-; CHECK-NEXT:    [[SCEVGEP1_LVER_ORIG:%.*]] = bitcast i32* [[SCEVGEP_LVER_ORIG]] to i8*
-; CHECK-NEXT:    [[TMP14:%.*]] = mul nsw i64 [[INDVARS_IV6_LVER_ORIG]], [[TMP1]]
-; CHECK-NEXT:    [[TMP15:%.*]] = mul nsw i64 [[TMP14]], [[TMP2]]
-; CHECK-NEXT:    [[ADD_PTR_US_LVER_ORIG:%.*]] = getelementptr inbounds i32, i32* [[AR]], i64 [[TMP15]]
-; CHECK-NEXT:    [[WIDE_TRIP_COUNT_LVER_ORIG:%.*]] = zext i32 [[M]] to i64
-; CHECK-NEXT:    call void @llvm.memset.p0i8.i64(i8* align 4 [[SCEVGEP1_LVER_ORIG]], i8 0, i64 [[TMP6]], i1 false)
-; CHECK-NEXT:    br label [[FOR_BODY3_US_LVER_ORIG:%.*]]
-; CHECK:       for.body3.us.lver.orig:
-; CHECK-NEXT:    [[INDVARS_IV_LVER_ORIG:%.*]] = phi i64 [ 0, [[FOR_BODY_US_LVER_ORIG]] ], [ [[INDVARS_IV_NEXT_LVER_ORIG:%.*]], [[FOR_BODY3_US_LVER_ORIG]] ]
-; CHECK-NEXT:    [[TMP16:%.*]] = mul nsw i64 [[INDVARS_IV_LVER_ORIG]], [[TMP0]]
-; CHECK-NEXT:    [[ADD_PTR7_US_LVER_ORIG:%.*]] = getelementptr inbounds i32, i32* [[ADD_PTR_US_LVER_ORIG]], i64 [[TMP16]]
-; CHECK-NEXT:    [[TMP17:%.*]] = bitcast i32* [[ADD_PTR7_US_LVER_ORIG]] to i8*
-; CHECK-NEXT:    [[INDVARS_IV_NEXT_LVER_ORIG]] = add nuw nsw i64 [[INDVARS_IV_LVER_ORIG]], 1
-; CHECK-NEXT:    [[EXITCOND_LVER_ORIG:%.*]] = icmp ne i64 [[INDVARS_IV_NEXT_LVER_ORIG]], [[WIDE_TRIP_COUNT_LVER_ORIG]]
-; CHECK-NEXT:    br i1 [[EXITCOND_LVER_ORIG]], label [[FOR_BODY3_US_LVER_ORIG]], label [[FOR_INC9_US_LVER_ORIG]]
-; CHECK:       for.inc9.us.lver.orig:
-; CHECK-NEXT:    [[INDVARS_IV_NEXT7_LVER_ORIG]] = add nuw nsw i64 [[INDVARS_IV6_LVER_ORIG]], 1
-; CHECK-NEXT:    [[EXITCOND11_LVER_ORIG:%.*]] = icmp ne i64 [[INDVARS_IV_NEXT7_LVER_ORIG]], [[WIDE_TRIP_COUNT10]]
-; CHECK-NEXT:    br i1 [[EXITCOND11_LVER_ORIG]], label [[FOR_BODY_US_LVER_ORIG]], label [[FOR_END11]]
-; CHECK:       for.body.us.ph:
 ; CHECK-NEXT:    call void @llvm.memset.p0i8.i64(i8* align 4 [[AR2]], i8 0, i64 [[TMP8]], i1 false)
 ; CHECK-NEXT:    br label [[FOR_END11]]
 ; CHECK:       for.end11:
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %cmp3 = icmp slt i32 0, %n
   br i1 %cmp3, label %for.body.lr.ph, label %for.end11

llvm/test/Transforms/LoopIdiom/memset-runtime-lnir.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -passes="function(loop(loop-nest-idiom,loop-deletion),simplifycfg)" < %s -S | FileCheck %s
 ; The C code to generate this testcase:
 ; void test(int ar[][m], long n, long m)
 ; {
 ;   long i;
 ;   for (i=0; i<n; ++i) {
 ;     int *arr = ar + i * m; // ar[i];
 ;     memset(arr, 0, m * sizeof(int));
 ;   }
 ; }
 ; The optimized IR should be similar to the following:
 ; void test(int ar[][m], long n, long m)
 ; {
-;   if (n < 0 || m < 0 || (n >> 32) != 0 || (4 * m >> 32) != 0)
-;     /* optimization result identical to LoopIdiomRecognize */
-;   else
-;     /* hoists memset to loop-preheader */
+;   memset(ar, 0, m * n * sizeof(int));
 ; }
 define void @test_simple(i32* nocapture %ar, i64 %n, i64 %m) {
 ; CHECK-LABEL: @test_simple(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[AR1:%.*]] = bitcast i32* [[AR:%.*]] to i8*
 ; CHECK-NEXT:    [[TMP0:%.*]] = shl nuw i64 [[M:%.*]], 2
 ; CHECK-NEXT:    [[TMP1:%.*]] = mul i64 [[M]], [[N:%.*]]
 ; CHECK-NEXT:    [[TMP2:%.*]] = shl i64 [[TMP1]], 2
 ; CHECK-NEXT:    call void @llvm.memset.p0i8.i64(i8* align 4 [[AR1]], i8 0, i64 [[TMP2]], i1 false)
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %0 = shl nuw i64 %m, 2
   br label %for.cond1.preheader
 
 for.cond1.preheader:                              ; preds = %for.inc4, %entry
   %i.017 = phi i64 [ 0, %entry ], [ %inc5, %for.inc4 ]
   %1 = mul i64 %m, %i.017
   %scevgep = getelementptr i32, i32* %ar, i64 %1
   %scevgep1 = bitcast i32* %scevgep to i8*
   %mul = mul nsw i64 %i.017, %m
   call void @llvm.memset.p0i8.i64(i8* align 4 %scevgep1, i8 0, i64 %0, i1 false)
   br label %for.inc4
 
 for.inc4:                                         ; preds = %for.cond1.preheader
   %inc5 = add nuw nsw i64 %i.017, 1
   %exitcond18.not = icmp eq i64 %inc5, %n
   br i1 %exitcond18.not, label %for.end6, label %for.cond1.preheader
 

 ; CHECK-NEXT:    [[SMAX:%.*]] = call i64 @llvm.smax.i64(i64 [[CONV]], i64 1)
 ; CHECK-NEXT:    [[TMP0:%.*]] = call i32 @llvm.smax.i32(i32 [[N:%.*]], i32 1)
 ; CHECK-NEXT:    [[SMAX27:%.*]] = zext i32 [[TMP0]] to i64
 ; CHECK-NEXT:    [[TMP1:%.*]] = mul i64 [[CONV2]], [[CONV]]
 ; CHECK-NEXT:    [[TMP2:%.*]] = mul i64 [[SMAX]], [[CONV2]]
 ; CHECK-NEXT:    [[TMP3:%.*]] = shl i64 [[TMP2]], 2
 ; CHECK-NEXT:    [[TMP4:%.*]] = mul i64 [[TMP2]], [[SMAX27]]
 ; CHECK-NEXT:    [[TMP5:%.*]] = shl i64 [[TMP4]], 2
-; CHECK-NEXT:    [[TMP6:%.*]] = icmp slt i64 [[CONV]], 1
+; CHECK-NEXT:    [[TMP6:%.*]] = icmp slt i64 [[CONV]], 0
 ; CHECK-NEXT:    [[TMP7:%.*]] = or i1 false, [[TMP6]]
 ; CHECK-NEXT:    [[TMP8:%.*]] = icmp slt i64 [[CONV2]], 0
 ; CHECK-NEXT:    [[TMP9:%.*]] = or i1 [[TMP7]], [[TMP8]]
-; CHECK-NEXT:    br i1 [[TMP9]], label [[DO_BODY_LVER_ORIG:%.*]], label [[DO_BODY_PH:%.*]]
+; CHECK-NEXT:    [[TMP10:%.*]] = icmp slt i64 [[SMAX]], 1
+; CHECK-NEXT:    [[TMP11:%.*]] = or i1 [[TMP9]], [[TMP10]]
+; CHECK-NEXT:    br i1 [[TMP11]], label [[DO_BODY_LVER_ORIG:%.*]], label [[DO_BODY_PH:%.*]]
 ; CHECK:       do.body.lver.orig:
 ; CHECK-NEXT:    [[I_0_LVER_ORIG:%.*]] = phi i64 [ [[INC11_LVER_ORIG:%.*]], [[DO_END_LVER_ORIG:%.*]] ], [ 0, [[DO_BODY_LVER_CHECK:%.*]] ]
-; CHECK-NEXT:    [[TMP10:%.*]] = mul i64 [[TMP1]], [[I_0_LVER_ORIG]]
-; CHECK-NEXT:    [[SCEVGEP_LVER_ORIG:%.*]] = getelementptr i32, i32* [[AR]], i64 [[TMP10]]
+; CHECK-NEXT:    [[TMP12:%.*]] = mul i64 [[TMP1]], [[I_0_LVER_ORIG]]
+; CHECK-NEXT:    [[SCEVGEP_LVER_ORIG:%.*]] = getelementptr i32, i32* [[AR]], i64 [[TMP12]]
 ; CHECK-NEXT:    [[SCEVGEP1_LVER_ORIG:%.*]] = bitcast i32* [[SCEVGEP_LVER_ORIG]] to i8*
 ; CHECK-NEXT:    [[MUL3_LVER_ORIG:%.*]] = mul i64 [[MUL]], [[I_0_LVER_ORIG]]
 ; CHECK-NEXT:    [[ADD_PTR_LVER_ORIG:%.*]] = getelementptr inbounds i32, i32* [[AR]], i64 [[MUL3_LVER_ORIG]]
 ; CHECK-NEXT:    call void @llvm.memset.p0i8.i64(i8* align 4 [[SCEVGEP1_LVER_ORIG]], i8 0, i64 [[TMP3]], i1 false)
 ; CHECK-NEXT:    br label [[DO_BODY1_LVER_ORIG:%.*]]
 ; CHECK:       do.body1.lver.orig:
 ; CHECK-NEXT:    [[J_0_LVER_ORIG:%.*]] = phi i64 [ 0, [[DO_BODY_LVER_ORIG]] ], [ [[INC_LVER_ORIG:%.*]], [[DO_BODY1_LVER_ORIG]] ]
 ; CHECK-NEXT:    [[MUL5_LVER_ORIG:%.*]] = mul nsw i64 [[J_0_LVER_ORIG]], [[CONV2]]
 ; CHECK-NEXT:    [[ADD_PTR6_LVER_ORIG:%.*]] = getelementptr inbounds i32, i32* [[ADD_PTR_LVER_ORIG]], i64 [[MUL5_LVER_ORIG]]
-; CHECK-NEXT:    [[TMP11:%.*]] = bitcast i32* [[ADD_PTR6_LVER_ORIG]] to i8*
+; CHECK-NEXT:    [[TMP13:%.*]] = bitcast i32* [[ADD_PTR6_LVER_ORIG]] to i8*
 ; CHECK-NEXT:    [[INC_LVER_ORIG]] = add nuw nsw i64 [[J_0_LVER_ORIG]], 1
 ; CHECK-NEXT:    [[EXITCOND_NOT_LVER_ORIG:%.*]] = icmp eq i64 [[INC_LVER_ORIG]], [[SMAX]]
 ; CHECK-NEXT:    br i1 [[EXITCOND_NOT_LVER_ORIG]], label [[DO_END_LVER_ORIG]], label [[DO_BODY1_LVER_ORIG]]
 ; CHECK:       do.end.lver.orig:
 ; CHECK-NEXT:    [[INC11_LVER_ORIG]] = add nuw nsw i64 [[I_0_LVER_ORIG]], 1
 ; CHECK-NEXT:    [[EXITCOND28_NOT_LVER_ORIG:%.*]] = icmp eq i64 [[INC11_LVER_ORIG]], [[SMAX27]]
 ; CHECK-NEXT:    br i1 [[EXITCOND28_NOT_LVER_ORIG]], label [[DO_END16:%.*]], label [[DO_BODY_LVER_ORIG]]
 ; CHECK:       do.body.ph:
do.end16:                                         ; preds = %do.end
   ret void
 }
 ; The C code to generate this testcase:
 ; void test(int n, int m, int o, int *ar)
 ; {
 ;   for (int i=0; i<n; ++i) {
 ;     for (int j=0; j<m; ++j) {
 ;       int *arr = ar + i * m * o + j * o;
-;       memset(arr, 0, o * sizeof(int));      
+;       memset(arr, 0, o * sizeof(int));
 ;     }
 ;   }
 ; }
 define void @test_nested_for(i32 %n, i32 %m, i32 %o, i32* %ar) {
 ; CHECK-LABEL: @test_nested_for(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[AR2:%.*]] = bitcast i32* [[AR:%.*]] to i8*
 ; CHECK-NEXT:    [[CMP3:%.*]] = icmp slt i32 0, [[N:%.*]]
 ; CHECK-NEXT:    br i1 [[CMP3]], label [[FOR_BODY_LR_PH:%.*]], label [[FOR_END11:%.*]]
 ; CHECK:       for.body.lr.ph:
 ; CHECK-NEXT:    [[CMP21:%.*]] = icmp slt i32 0, [[M:%.*]]
 ; CHECK-NEXT:    [[CONV:%.*]] = sext i32 [[O:%.*]] to i64
 ; CHECK-NEXT:    [[MUL8:%.*]] = mul i64 [[CONV]], 4
-; CHECK-NEXT:    br i1 [[CMP21]], label [[FOR_BODY_US_LVER_CHECK:%.*]], label [[FOR_END11]]
-; CHECK:       for.body.us.lver.check:
+; CHECK-NEXT:    br i1 [[CMP21]], label [[FOR_BODY_LR_PH_SPLIT_US:%.*]], label [[FOR_END11]]
+; CHECK:       for.body.lr.ph.split.us:
 ; CHECK-NEXT:    [[TMP0:%.*]] = sext i32 [[O]] to i64
 ; CHECK-NEXT:    [[TMP1:%.*]] = sext i32 [[M]] to i64
 ; CHECK-NEXT:    [[TMP2:%.*]] = sext i32 [[O]] to i64
 ; CHECK-NEXT:    [[WIDE_TRIP_COUNT10:%.*]] = zext i32 [[N]] to i64
 ; CHECK-NEXT:    [[TMP3:%.*]] = mul i64 [[TMP0]], [[TMP1]]
 ; CHECK-NEXT:    [[TMP4:%.*]] = zext i32 [[M]] to i64
 ; CHECK-NEXT:    [[TMP5:%.*]] = mul i64 [[TMP0]], [[TMP4]]
 ; CHECK-NEXT:    [[TMP6:%.*]] = shl i64 [[TMP5]], 2
 ; CHECK-NEXT:    [[TMP7:%.*]] = mul i64 [[TMP5]], [[WIDE_TRIP_COUNT10]]
 ; CHECK-NEXT:    [[TMP8:%.*]] = shl i64 [[TMP7]], 2
-; CHECK-NEXT:    [[TMP9:%.*]] = icmp slt i64 [[TMP0]], 0
-; CHECK-NEXT:    [[TMP10:%.*]] = or i1 false, [[TMP9]]
-; CHECK-NEXT:    [[TMP11:%.*]] = icmp slt i64 [[TMP1]], 0
-; CHECK-NEXT:    [[TMP12:%.*]] = or i1 [[TMP10]], [[TMP11]]
-; CHECK-NEXT:    br i1 [[TMP12]], label [[FOR_BODY_US_LVER_ORIG:%.*]], label [[FOR_BODY_US_PH:%.*]]
-; CHECK:       for.body.us.lver.orig:
-; CHECK-NEXT:    [[INDVARS_IV6_LVER_ORIG:%.*]] = phi i64 [ [[INDVARS_IV_NEXT7_LVER_ORIG:%.*]], [[FOR_INC9_US_LVER_ORIG:%.*]] ], [ 0, [[FOR_BODY_US_LVER_CHECK]] ]
-; CHECK-NEXT:    [[TMP13:%.*]] = mul i64 [[TMP3]], [[INDVARS_IV6_LVER_ORIG]]
-; CHECK-NEXT:    [[SCEVGEP_LVER_ORIG:%.*]] = getelementptr i32, i32* [[AR]], i64 [[TMP13]]
-; CHECK-NEXT:    [[SCEVGEP1_LVER_ORIG:%.*]] = bitcast i32* [[SCEVGEP_LVER_ORIG]] to i8*
-; CHECK-NEXT:    [[TMP14:%.*]] = mul nsw i64 [[INDVARS_IV6_LVER_ORIG]], [[TMP1]]
-; CHECK-NEXT:    [[TMP15:%.*]] = mul nsw i64 [[TMP14]], [[TMP2]]
-; CHECK-NEXT:    [[ADD_PTR_US_LVER_ORIG:%.*]] = getelementptr inbounds i32, i32* [[AR]], i64 [[TMP15]]
-; CHECK-NEXT:    [[WIDE_TRIP_COUNT_LVER_ORIG:%.*]] = zext i32 [[M]] to i64
-; CHECK-NEXT:    call void @llvm.memset.p0i8.i64(i8* align 4 [[SCEVGEP1_LVER_ORIG]], i8 0, i64 [[TMP6]], i1 false)
-; CHECK-NEXT:    br label [[FOR_BODY3_US_LVER_ORIG:%.*]]
-; CHECK:       for.body3.us.lver.orig:
-; CHECK-NEXT:    [[INDVARS_IV_LVER_ORIG:%.*]] = phi i64 [ 0, [[FOR_BODY_US_LVER_ORIG]] ], [ [[INDVARS_IV_NEXT_LVER_ORIG:%.*]], [[FOR_BODY3_US_LVER_ORIG]] ]
-; CHECK-NEXT:    [[TMP16:%.*]] = mul nsw i64 [[INDVARS_IV_LVER_ORIG]], [[TMP0]]
-; CHECK-NEXT:    [[ADD_PTR7_US_LVER_ORIG:%.*]] = getelementptr inbounds i32, i32* [[ADD_PTR_US_LVER_ORIG]], i64 [[TMP16]]
-; CHECK-NEXT:    [[TMP17:%.*]] = bitcast i32* [[ADD_PTR7_US_LVER_ORIG]] to i8*
-; CHECK-NEXT:    [[INDVARS_IV_NEXT_LVER_ORIG]] = add nuw nsw i64 [[INDVARS_IV_LVER_ORIG]], 1
-; CHECK-NEXT:    [[EXITCOND_LVER_ORIG:%.*]] = icmp ne i64 [[INDVARS_IV_NEXT_LVER_ORIG]], [[WIDE_TRIP_COUNT_LVER_ORIG]]
-; CHECK-NEXT:    br i1 [[EXITCOND_LVER_ORIG]], label [[FOR_BODY3_US_LVER_ORIG]], label [[FOR_INC9_US_LVER_ORIG]]
-; CHECK:       for.inc9.us.lver.orig:
-; CHECK-NEXT:    [[INDVARS_IV_NEXT7_LVER_ORIG]] = add nuw nsw i64 [[INDVARS_IV6_LVER_ORIG]], 1
-; CHECK-NEXT:    [[EXITCOND11_LVER_ORIG:%.*]] = icmp ne i64 [[INDVARS_IV_NEXT7_LVER_ORIG]], [[WIDE_TRIP_COUNT10]]
-; CHECK-NEXT:    br i1 [[EXITCOND11_LVER_ORIG]], label [[FOR_BODY_US_LVER_ORIG]], label [[FOR_END11]]
-; CHECK:       for.body.us.ph:
 ; CHECK-NEXT:    call void @llvm.memset.p0i8.i64(i8* align 4 [[AR2]], i8 0, i64 [[TMP8]], i1 false)
 ; CHECK-NEXT:    br label [[FOR_END11]]
 ; CHECK:       for.end11:
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %cmp3 = icmp slt i32 0, %n
   br i1 %cmp3, label %for.body.lr.ph, label %for.end11