[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

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

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/include/llvm/Transforms/Utils/LoopVersioning.h

public:
   /// loop don't alias (i.e. all memchecks passed).  (This loop is actually the
   /// same as the original loop that we got constructed with.)
   Loop *getVersionedLoop() { return VersionedLoop; }
 
   /// Returns the fall-back loop.  Control flows here if pointers in the
   /// loop may alias (i.e. one of the memchecks failed).
   Loop *getNonVersionedLoop() { return NonVersionedLoop; }
 
+  /// Returns the basic block that contains the runtime check BranchInst
+  BasicBlock *getRuntimeCheckBB() { return RuntimeCheckBB; }
+
+  /// Returns the runtime check BranchInst
+  BranchInst *getRuntimeCheckBI() { return RuntimeCheckBI; }
+
   /// Annotate memory instructions in the versioned loop with no-alias
   /// metadata based on the memchecks issued.
   ///
   /// This is just wrapper that calls prepareNoAliasMetadata and
   /// annotateInstWithNoAlias on the instructions of the versioned loop.
   void annotateLoopWithNoAlias();
 
   /// Set up the aliasing scopes based on the memchecks.  This needs to
private:
 
   /// The original loop.  This becomes the "versioned" one.  I.e.,
   /// control flows here if pointers in the loop don't alias.
   Loop *VersionedLoop;
   /// The fall-back loop.  I.e. control flows here if pointers in the
   /// loop may alias (memchecks failed).
   Loop *NonVersionedLoop;
 
+  /// The basic Block that stores the BranchInst to Versioned / NonVersioned
+  BasicBlock *RuntimeCheckBB;
+
+  /// The branch instruction to Versioned / NonVersioned
+  BranchInst *RuntimeCheckBI;
+
   /// This maps the instructions from VersionedLoop to their counterpart
   /// in NonVersionedLoop.
   ValueToValueMapTy VMap;
 
   /// The set of alias checks that we are versioning for.
   SmallVector<RuntimePointerCheck, 4> AliasChecks;
 
   /// The set of SCEV checks that we are versioning for.

llvm/lib/Transforms/Utils/LoopVersioning.cpp

 #include "llvm/InitializePasses.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
 #include "llvm/Transforms/Utils/Cloning.h"
 #include "llvm/Transforms/Utils/ScalarEvolutionExpander.h"
 
 using namespace llvm;
 
+#define LVER_OPTION "loop-versioning"
+#define DEBUG_TYPE LVER_OPTION
+
 static cl::opt<bool>
     AnnotateNoAlias("loop-version-annotate-no-alias", cl::init(true),
                     cl::Hidden,
                     cl::desc("Add no-alias annotation for instructions that "
                              "are disambiguated by memchecks"));
 
 LoopVersioning::LoopVersioning(const LoopAccessInfo &LAI,
                                ArrayRef<RuntimePointerCheck> Checks, Loop *L,
void LoopVersioning::versionLoop(
   if (MemRuntimeCheck && SCEVRuntimeCheck) {
     RuntimeCheck = BinaryOperator::Create(Instruction::Or, MemRuntimeCheck,
                                           SCEVRuntimeCheck, "lver.safe");
     if (auto *I = dyn_cast<Instruction>(RuntimeCheck))
       I->insertBefore(RuntimeCheckBB->getTerminator());
   } else
     RuntimeCheck = MemRuntimeCheck ? MemRuntimeCheck : SCEVRuntimeCheck;
 
-  assert(RuntimeCheck && "called even though we don't need "
-                         "any runtime checks");
+  if (!RuntimeCheck) {
+    LLVM_DEBUG(dbgs() << DEBUG_TYPE " No MemRuntimeCheck or SCEVRuntimeCheck found"
+                      << ", set RuntimeCheck to False\n");
+    RuntimeCheck = ConstantInt::getFalse(RuntimeCheckBB->getContext());
+  }
 
   // Rename the block to make the IR more readable.
   RuntimeCheckBB->setName(VersionedLoop->getHeader()->getName() +
                           ".lver.check");
 
   // Create empty preheader for the loop (and after cloning for the
   // non-versioned loop).
   BasicBlock *PH =
       SplitBlock(RuntimeCheckBB, RuntimeCheckBB->getTerminator(), DT, LI,
                  nullptr, VersionedLoop->getHeader()->getName() + ".ph");
 
   // Clone the loop including the preheader.
   //
   // FIXME: This does not currently preserve SimplifyLoop because the exit
   // block is a join between the two loops.
   SmallVector<BasicBlock *, 8> NonVersionedLoopBlocks;
   NonVersionedLoop =
       cloneLoopWithPreheader(PH, RuntimeCheckBB, VersionedLoop, VMap,
                              ".lver.orig", LI, DT, NonVersionedLoopBlocks);
   remapInstructionsInBlocks(NonVersionedLoopBlocks, VMap);
 
   // Insert the conditional branch based on the result of the memchecks.
   Instruction *OrigTerm = RuntimeCheckBB->getTerminator();
-  BranchInst::Create(NonVersionedLoop->getLoopPreheader(),
+  RuntimeCheckBI = BranchInst::Create(NonVersionedLoop->getLoopPreheader(),
                            VersionedLoop->getLoopPreheader(), RuntimeCheck, OrigTerm);
   OrigTerm->eraseFromParent();
 
   // The loops merge in the original exit block.  This is now dominated by the
   // memchecking block.
   DT->changeImmediateDominator(VersionedLoop->getExitBlock(), RuntimeCheckBB);
 
   // Adds the necessary PHI nodes for the versioned loops based on the
   // loop-defined values used outside of the loop.
   addPHINodes(DefsUsedOutside);
   formDedicatedExitBlocks(NonVersionedLoop, DT, LI, nullptr, true);
   formDedicatedExitBlocks(VersionedLoop, DT, LI, nullptr, true);
   assert(NonVersionedLoop->isLoopSimplifyForm() &&
          VersionedLoop->isLoopSimplifyForm() &&
          "The versioned loops should be in simplify form.");
+
+  // RuntimeCheckBB and RuntimeCheckBI is recorded
+  assert(RuntimeCheckBB && RuntimeCheckBI);
 }
 
 void LoopVersioning::addPHINodes(
     const SmallVectorImpl<Instruction *> &DefsUsedOutside) {
   BasicBlock *PHIBlock = VersionedLoop->getExitBlock();
   assert(PHIBlock && "No single successor to loop exit block");
   PHINode *PN;
 
void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.addPreserved<DominatorTreeWrapperPass>();
     AU.addRequired<ScalarEvolutionWrapperPass>();
   }
 
   static char ID;
 };
 }
 
-#define LVER_OPTION "loop-versioning"
-#define DEBUG_TYPE LVER_OPTION
-
 char LoopVersioningLegacyPass::ID;
 static const char LVer_name[] = "Loop Versioning";
 
 INITIALIZE_PASS_BEGIN(LoopVersioningLegacyPass, LVER_OPTION, LVer_name, false,
                       false)
 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(LoopAccessLegacyAnalysis)
 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)