[LoopVersioning] Allow versionLoop to create plain branch inst when no runtime check is specified

[eopXD]

Summary

After this function call, the LLVM IR would look like the following:

if (true)
  /* NonVersionedLoop */
else
  /* VersionedLoop */

[eopXD]

User may need to create versioned loops of such structure to append more runtime checks conditions to the branch instruction.

[fhahn]

In D104631#2830110, @eopXD wrote:

User may need to create versioned loops of such structure to append more runtime checks conditions to the branch instruction.

Are you planning on sharing a follow-up that makes use of the new functionality? That would be helpful to review this and the earlier patch, to make sure the new API is a good fit. Also, it would be good to have a way to test this.

[lebedev.ri]

The design seems weird here.
I think it would be best to first see the intended use case.

[fhahn]

In terms of structuring of LoopVersioning, I think it would be great if the existing functionality could be refactored so that there is a set of helper functions that expose the functionality for re-use, rather than growing the existing LoopVersioning class.

[eopXD]

Preserve information inside versionLoop and add helper functions to get them.

[eopXD]

Preserve information inside versionLoop and add helper functions to get them.

[eopXD]

Hi @fhahn ,

Aside from adding helper functions, I think removing the assertion that "ensures RuntimeCheck is not a nullptr is necessary,
since in my use-case, the loop provided to LoopVersioning doesn't require any MemRuntimeCheck and SCEVRuntimeCheck but wants to clone the loop and setup a branch instruction for them.
Other than that I kept the interface and logic of versionLoop the same.

Thank you for reviewing this patch.

[eopXD]

Address comments.

[eopXD]

pushed to the wrong patch. revert.

[Whitney]

LGTM.

[fhahn]

In D104631#2842314, @eopXD wrote:

Hi @fhahn ,

Aside from adding helper functions, I think removing the assertion that "ensures RuntimeCheck is not a nullptr is necessary,
since in my use-case, the loop provided to LoopVersioning doesn't require any MemRuntimeCheck and SCEVRuntimeCheck but wants to clone the loop and setup a branch instruction for them.
Other than that I kept the interface and logic of versionLoop the same.

Right, currently versionLoop roughly does the following things: 1) create memory runtime checks (if requested), 2) generate SCEV predicate checks (if requested) and 3) clone the loop and 4) branch to the right version depending on the generated runtime checks.

IIUC you only need 3). Personally it seems like extending versionLoop to only do 3) makes the interface more complicated than it needs to be. Instead, would it be possible to extract the code to do 3) into a utility function that returns the conditional branch to select the loop? Then you could use that in LoopIdiomRecognize directly.

llvm/include/llvm/Transforms/Utils/LoopVersioning.h

79 ↗

(On Diff #354659)

dead code? (same for the other changes here)

[eopXD]

IIUC you only need 3). Personally it seems like extending versionLoop to only do 3) makes the interface more complicated than it needs to be. Instead, would it be possible to extract the code to do 3) into a utility function that returns the conditional branch to select the loop? Then you could use that in LoopIdiomRecognize directly.

Hi @fhahn,

Sorry for the late reply.
I think I have made minimum change for versionLoop and only exposed utility functions (getRuntimeCheckBB and getRuntimeCheckBI) for use.
The usage of these two functions are inside D104636.
Since @Whitney have accepted it I think we can land this and proceed to the child patches and give LoopNestIdiomRecognize a try?

/// versionTopLoop - Create a fallback version the TopLoop
void LoopIdiomRecognize::versionTopLoop() {
  const LoopAccessInfo LAI(TopLoop, SE, TLI, AA, DT, LI);
  LoopVersioning LV(LAI, LAI.getRuntimePointerChecking()->getChecks(), TopLoop,
                    LI, DT, SE);

  LV.versionLoopWithPlainRuntimeCheck();

  RuntimeCheckBB = LV.getRuntimeCheckBB();
  FallBackLoop = LV.getNonVersionedLoop();
}

llvm/include/llvm/Transforms/Utils/LoopVersioning.h

79 ↗

(On Diff #354659)

It is dead code right now but will be used in D104636.

[eopXD]

Rebase.

[eopXD]

Rebase.

[eopXD]

I am landing this utility to give it a try on D104636.

[eopXD]

Rebase.

[eopXD]

Rebase.

[fhahn]

In D104631#3185655, @eopXD wrote:

IIUC you only need 3). Personally it seems like extending versionLoop to only do 3) makes the interface more complicated than it needs to be. Instead, would it be possible to extract the code to do 3) into a utility function that returns the conditional branch to select the loop? Then you could use that in LoopIdiomRecognize directly.

Hi @fhahn,

Sorry for the late reply.
I think I have made minimum change for versionLoop and only exposed utility functions (getRuntimeCheckBB and getRuntimeCheckBI) for use.
The usage of these two functions are inside D104636.

FWIW I still think the interface should be adopted to make this more useable, rather than just adding on additional state that makes it even harder to make further changes. While the changes here are indeed a bit smaller than improving the interface, the additional state that needs maintained increases the complexity of the class even further, which has a cost down the road.

I *think* the patch should only be committed once D104636 has also been accepted; at the moment there's nothing to test the new functionality.

[eopXD]

You are right. Patch reverted.

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::init(false), cl::Hidden);
 
 namespace {
 
 typedef SmallVector<std::pair<const SCEV *, unsigned>, 4> SCEVExprPairList;
 
 class LoopIdiomRecognize {
   Loop *CurLoop = nullptr;
-  LoopNest *LN;
+  LoopNest *LN = nullptr;
   Loop *TopLoop = nullptr;
   Loop *FallBackLoop = nullptr;
   BasicBlock *RuntimeCheckBB = nullptr;
+  BranchInst *RuntimeCheckBI = nullptr;
   AliasAnalysis *AA;
   DominatorTree *DT;
   LoopInfo *LI;
   ScalarEvolution *SE;
   TargetLibraryInfo *TLI;
   const TargetTransformInfo *TTI;
   const DataLayout *DL;
   OptimizationRemarkEmitter &ORE;
bool LoopIdiomRecognize::runOnLoopNest() {
   for (Loop *L : WorkList) {
     Changed |= runOnLoop(L);
   }
 
   // After processing all the loops, we now add the stored conditions into
   // the RuntimeCheckBB. Conditions are stored when:
   //   - detect runtime store size in StridedStore (SizeAddrSpacePairList)
   if (Changed && isTopLoopVersioned()) {
-    // Get the branch instruction in the runtime check basic block.
-    BranchInst *BI = dyn_cast<BranchInst>(RuntimeCheckBB->getTerminator());
-    assert(BI && "Expects a BranchInst");
+    assert(RuntimeCheckBI && "should be fetched when calling versionTopLoop()");
 
     // Create conditional branch instructions with conditions:
     //   - Store size overflow half of the width of the pointer
     // If any of the condition above is true, the fallback loop is taken.
     // Otherwise, the optimized loop is taken.
     LLVMContext &Context = TopLoop->getHeader()->getContext();
     Value *Cond = ConstantInt::getFalse(Context);
 
-    IRBuilder<> Builder(BI);
+    IRBuilder<> Builder(RuntimeCheckBI);
     for (auto Pair : *SizeAddrSpacePairList) {
       const SCEV *Ev = Pair.first;
       unsigned AddrSpace = Pair.second;
       Value *NewCond0 =
-          generateOverflowPredicate(Ev, AddrSpace, BI, DL, SE, Builder);
-      Value *NewCond1 = generateSltZeroPredicate(Ev, BI, DL, SE, Builder);
+          generateOverflowPredicate(Ev, AddrSpace, RuntimeCheckBI, DL, SE, Builder);
+      Value *NewCond1 = generateSltZeroPredicate(Ev, RuntimeCheckBI, DL, SE, Builder);
       Cond = Builder.CreateOr(Cond, NewCond0);
       Cond = Builder.CreateOr(Cond, NewCond1);
     }
 
-    BranchInst::Create(FallBackLoop->getLoopPreheader(),
-                       LN->getOutermostLoop().getLoopPreheader(), Cond, BI);
-    deleteDeadInstruction(BI);
+    RuntimeCheckBI->setCondition(Cond);
   }
 
   return Changed;
 }
 
 bool LoopIdiomRecognize::runOnLoop(Loop *L) {
   CurLoop = L;
   // If the loop could not be converted to canonical form, it must have an

 }
 
 /// versionTopLoop - Create a fallback version the TopLoop
 void LoopIdiomRecognize::versionTopLoop() {
   const LoopAccessInfo LAI(TopLoop, SE, TLI, AA, DT, LI);
   LoopVersioning LV(LAI, LAI.getRuntimePointerChecking()->getChecks(), TopLoop,
                     LI, DT, SE);
 
-  LV.versionLoopWithPlainRuntimeCheck();
+  LV.versionLoop();
 
   RuntimeCheckBB = LV.getRuntimeCheckBB();
+  RuntimeCheckBI = LV.getRuntimeCheckBI();
   FallBackLoop = LV.getNonVersionedLoop();
 }
 
 bool LoopIdiomRecognize::runOnNoncountableLoop() {
   LLVM_DEBUG(dbgs() << DEBUG_TYPE " Scanning: F["
                     << CurLoop->getHeader()->getParent()->getName()
                     << "] Noncountable Loop %"
                     << CurLoop->getHeader()->getName() << "\n");