[LoopDist/LoopVer] Move LoopVersioning to a new module, NFC

[anemet]

Summary

This is a verbatim move except for expanded comment before the class,
the new assert in the constructor and some clang-format fixes due to the
changed indentation level in the function defs.

The class will obviously need improvement down the road. For one, there
is no reason that addPHINodes would have to be exposed like that. I
will make this and other improvements in follow-up patches.

The main goal is to be able to share this functionality. The
LoopLoadElimination pass I am working on needs it too. Later we can
move other clients as well (LV and Ashutosh's LICMVer).

[anemet]

Rebase after r240352 ([LoopDist] Improve variable names and comments in LoopVersioning class, NFC)

[anemet]

OK, let's try this again without merging the two pending patches...

[hfinkel]

include/llvm/Transforms/Utils/LoopVersioning.h

10 ↗

(On Diff #28171)

This is a stale comment?

44 ↗

(On Diff #28171)

From this interface, I find it very unclear how you get out the new versioned loop after the CFG mutation is complete.

lib/Transforms/Utils/LoopVersioning.cpp

10 ↗

(On Diff #28171)

Stale comment?

[anemet]

include/llvm/Transforms/Utils/LoopVersioning.h

10 ↗

(On Diff #28171)

Yes, sorry.

44 ↗

(On Diff #28171)

The loop that was used to construct the class will be the "versioned" loop i.e. the loop that will get control if all the memchecks pass.

This is the loop that typically, the client transform will be interested in modifying. E.g. this is what LoopDistribute does.

This is sort of implicit because the versioning is optional. I think this is a typical algorithm:

for each loop L:
  analyze L
  if versioning is necessary version L
  transform L

The versioning itself is an optional step and you don't change the loop underlying the transformation if versioning was necessary.

Both loops (versioned, unversioned) are attributes of the class, so we can add APIs to query them as we need them.

Let me know if you'd be OK just commenting the above or you're requesting an actual API change.

Thanks very much for the review!

Adam

[hfinkel]

include/llvm/Transforms/Utils/LoopVersioning.h

44 ↗

(On Diff #28171)

In that case, I think the current API is okay, but needs comments.

49 ↗

(On Diff #28171)

This function too needs comments on when/how it should be used.

[anemet]

include/llvm/Transforms/Utils/LoopVersioning.h

44 ↗

(On Diff #28171)

OK, will add.

49 ↗

(On Diff #28171)

Sure, I'll explain it.

Just FYI, as I was mentioning in the summary, I'd like to make this a private member function in a follow-on patch, so clients would not have to worry about when/where to call it. This can be called at the end of versionLoop, internally.

Where I'd like to end up is something like this:

• move findDefsUsedOutside to LoopUtils.h or something like that
• have LoopVersioning take an optional DefsUsedOutside vector in the ctor. Optional, because like in the case of LoopDistribution the pass itself needs this piece of information so it's readily available
• compute DefsUsedOutside using findDefsUsedOutside if it wasn't passed
• call addPHINodes if there are DefsUsedOutside

[ashutosh.nema]

Thanks Adam for working on this, it looks useful.

General comment:
Please add more comments to functions.

lib/Transforms/Utils/LoopVersioning.cpp

41 ↗

(On Diff #28171)

Loop pre header may be null, probably you need to check that.
If you are assuming a preheader then you can put a assert here.

60 ↗

(On Diff #28171)

This function does not care about exit blocks, you don't want to clone exit blocks ?

75 ↗

(On Diff #28171)

Add some comments what this function does

[anemet]

lib/Transforms/Utils/LoopVersioning.cpp

41 ↗

(On Diff #28171)

Sounds good. I'll put it in the constructor next to the other assert.

60 ↗

(On Diff #28171)

It does not, hence the name ;). Here we may want to create exist blocks and then clone them to preserve SimplifyLoop.

cloneLoopWithPreheader is used in the LoopDistribution as well and in LoopDistribution there is no point of cloning the exit blocks because the preheader of the next distributed loop becomes the current loop's exit block (satisfying SimplifyLoop).

75 ↗

(On Diff #28171)

There is some before the decl but Hal also requested more comments there, so more to follow.

Thanks for your review.

Adam

[anemet]

Address review comments

[ashutosh.nema]

memcheck no-alias resulting branch is original loop(VersionedLoop).
& memcheck alias resulting branch is newly created loop(NonVersionedLoop).

Any specific reason you kept memcheck branch target like this ?

Why can't memcheck no-alias resulting branch targets to NonVersionedLoop
and alias resulting branch targets to VersionedLoop ?

In current implementation if loopVersioningLICM attempts to set no-alias attribute to the VersionedLoop
that is actually it will set no-alias attribute to the original loop.

I'm doubtful here because the variables of the original loop might be used out of loop in that function.
after setting no-alias it might change the intent of program.

My understanding might be wrong here, please clarify.

include/llvm/Transforms/Utils/LoopVersioning.h

67 ↗

(On Diff #28309)

Its more clear if we expand meaning of memcheck pass & fail.
i.e. memory/pointers [non]aliased in loop.

71 ↗

(On Diff #28309)

Can we expose NonVersionedLoop & VersionedLoop, or provide getter functions for these.
Loop versioning need these to set meta data.

[ashutosh.nema]

Typo:

• Loop versioning need these to set meta data.

Its
+ Loop versioning LICM need these to set meta data.

[anemet]

Hi Ashutosh,

In D10577#198383, @ashutosh.nema wrote:

memcheck no-alias resulting branch is original loop(VersionedLoop).
& memcheck alias resulting branch is newly created loop(NonVersionedLoop).

Any specific reason you kept memcheck branch target like this ?

Why can't memcheck no-alias resulting branch targets to NonVersionedLoop
and alias resulting branch targets to VersionedLoop ?

In current implementation if loopVersioningLICM attempts to set no-alias attribute to the VersionedLoop
that is actually it will set no-alias attribute to the original loop.

I'm doubtful here because the variables of the original loop might be used out of loop in that function.
after setting no-alias it might change the intent of program.

My understanding might be wrong here, please clarify.

The loops flow into a join where the values used outside are merge with phis. So outside users will see the value from whichever way we arrived. If we had an alias the value will come from the non-versioned loop and vice-versa.

Let me know if this helps.

Adam

[anemet]

Address Ashutosh's latest comments

[anemet]

In D10577#198636, @anemet wrote:

Address Ashutosh's latest comments

Ashutosh,

Does this and the other patch look OK to you now?

Thanks,
Adam

[ashutosh.nema]

Thanks Adam, This looks OK to me.

You can check with Hal, if he is OK you can proceed.

Regards,
Ashutosh

[hfinkel]

In D10577#200129, @ashutosh.nema wrote:

Thanks Adam, This looks OK to me.

You can check with Hal, if he is OK you can proceed.

Yes, LGTM.

Regards,
Ashutosh

include/llvm/Transforms/Utils/LoopVersioning.h

67 ↗

(On Diff #28965)

got constructed with -> passed to the constructor

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

+//===- LoopVersioning.h - Utility to version a loop -------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines a utility class to perform loop versioning.  The versioned
+// loop speculates that otherwise may-aliasing memory accesses don't overlap and
+// emits checks to prove this.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TRANSFORMS_UTILS_LOOPVERSIONING_H
+#define LLVM_TRANSFORMS_UTILS_LOOPVERSIONING_H
+
+#include "llvm/Transforms/Utils/ValueMapper.h"
+
+namespace llvm {
+
+class Loop;
+class LoopAccessInfo;
+class LoopInfo;
+
+/// \brief This class emits a version of the loop where run-time checks ensure
+/// that may-alias pointers can't overlap.
+///
+/// It currently only supports single-exit loops and assumes that the loop
+/// already has a preheader.
+class LoopVersioning {
+public:
+  LoopVersioning(const LoopAccessInfo &LAI, Loop *L, LoopInfo *LI,
+                 DominatorTree *DT,
+                 const SmallVector<int, 8> *PtrToPartition = nullptr);
+
+  /// \brief Returns true if we need memchecks to disambiguate may-aliasing
+  /// accesses.
+  bool needsRuntimeChecks() const;
+
+  /// \brief Performs the CFG manipulation part of versioning the loop including
+  /// the DominatorTree and LoopInfo updates.
+  ///
+  /// The loop that was used to construct the class will be the "versioned" loop
+  /// i.e. the loop that will receive control if all the memchecks pass.
+  ///
+  /// This allows the loop transform pass to operate on the same loop regardless
+  /// of whether versioning was necessary or not:
+  ///
+  ///    for each loop L:
+  ///        analyze L
+  ///        if versioning is necessary version L
+  ///        transform L
+  void versionLoop(Pass *P);
+
+  /// \brief Adds the necessary PHI nodes for the versioned loops based on the
+  /// loop-defined values used outside of the loop.
+  ///
+  /// This needs to be called after versionLoop if there are defs in the loop
+  /// that are used outside the loop.  FIXME: this should be invoked internally
+  /// by versionLoop and made private.
+  void addPHINodes(const SmallVectorImpl<Instruction *> &DefsUsedOutside);
+
+  /// \brief Returns the versioned loop.  Control flows here if pointers in the
+  /// 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; }
+
+  /// \brief 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; }
+
+private:
+  /// \brief The original loop.  This becomes the "versioned" one.  I.e.,
+  /// control flows here if pointers in the loop don't alias.
+  Loop *VersionedLoop;
+  /// \brief The fall-back loop.  I.e. control flows here if pointers in the
+  /// loop may alias (memchecks failed).
+  Loop *NonVersionedLoop;
+
+  /// \brief For each memory pointer it contains the partitionId it is used in.
+  /// If nullptr, no partitioning is used.
+  ///
+  /// The I-th entry corresponds to I-th entry in LAI.getRuntimePointerCheck().
+  /// If the pointer is used in multiple partitions the entry is set to -1.
+  const SmallVector<int, 8> *PtrToPartition;
+
+  /// \brief This maps the instructions from VersionedLoop to their counterpart
+  /// in NonVersionedLoop.
+  ValueToValueMapTy VMap;
+
+  /// \brief Analyses used.
+  const LoopAccessInfo &LAI;
+  LoopInfo *LI;
+  DominatorTree *DT;
+};
+}
+
+#endif

llvm/trunk/lib/Transforms/Scalar/LoopDistribute.cpp

 #include "llvm/Analysis/LoopAccessAnalysis.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
 #include "llvm/Transforms/Utils/Cloning.h"
+#include "llvm/Transforms/Utils/LoopVersioning.h"
 #include <list>
 
 #define LDIST_NAME "loop-distribute"
 #define DEBUG_TYPE LDIST_NAME
 
 using namespace llvm;
 
 static cl::opt<bool>
for (auto &Dep : InterestingDependences)
         DEBUG(Dep.print(dbgs(), 2, Instructions));
       }
   }
 
 private:
   AccessesType Accesses;
 };
 
-/// \brief Handles the loop versioning based on memchecks.
-class LoopVersioning {
-public:
-  LoopVersioning(const LoopAccessInfo &LAI, Loop *L, LoopInfo *LI,
-                 DominatorTree *DT,
-                 const SmallVector<int, 8> *PtrToPartition = nullptr)
-      : VersionedLoop(L), NonVersionedLoop(nullptr),
-        PtrToPartition(PtrToPartition), LAI(LAI), LI(LI), DT(DT) {}
-
-  /// \brief Returns true if we need memchecks to disambiguate may-aliasing
-  /// accesses.
-  bool needsRuntimeChecks() const {
-    return LAI.getRuntimePointerCheck()->needsAnyChecking(PtrToPartition);
-  }
-
-  /// \brief Performs the CFG manipulation part of versioning the loop including
-  /// the DominatorTree and LoopInfo updates.
-  void versionLoop(Pass *P) {
-    Instruction *FirstCheckInst;
-    Instruction *MemRuntimeCheck;
-    // Add the memcheck in the original preheader (this is empty initially).
-    BasicBlock *MemCheckBB = VersionedLoop->getLoopPreheader();
-    std::tie(FirstCheckInst, MemRuntimeCheck) =
-        LAI.addRuntimeCheck(MemCheckBB->getTerminator(), PtrToPartition);
-    assert(MemRuntimeCheck && "called even though needsAnyChecking = false");
-
-    // Rename the block to make the IR more readable.
-    MemCheckBB->setName(VersionedLoop->getHeader()->getName() +
-                        ".lver.memcheck");
-
-    // Create empty preheader for the loop (and after cloning for the
-    // non-versioned loop).
-    BasicBlock *PH =
-        SplitBlock(MemCheckBB, MemCheckBB->getTerminator(), DT, LI);
-    PH->setName(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, MemCheckBB, VersionedLoop, VMap,
-                               ".lver.orig", LI, DT, NonVersionedLoopBlocks);
-    remapInstructionsInBlocks(NonVersionedLoopBlocks, VMap);
-
-    // Insert the conditional branch based on the result of the memchecks.
-    Instruction *OrigTerm = MemCheckBB->getTerminator();
-    BranchInst::Create(NonVersionedLoop->getLoopPreheader(),
-                       VersionedLoop->getLoopPreheader(), MemRuntimeCheck,
-                       OrigTerm);
-    OrigTerm->eraseFromParent();
-
-    // The loops merge in the original exit block.  This is now dominated by the
-    // memchecking block.
-    DT->changeImmediateDominator(VersionedLoop->getExitBlock(), MemCheckBB);
-  }
-
-  /// \brief Adds the necessary PHI nodes for the versioned loops based on the
-  /// loop-defined values used outside of the loop.
-  void addPHINodes(const SmallVectorImpl<Instruction *> &DefsUsedOutside) {
-    BasicBlock *PHIBlock = VersionedLoop->getExitBlock();
-    assert(PHIBlock && "No single successor to loop exit block");
-
-    for (auto *Inst : DefsUsedOutside) {
-      auto *NonVersionedLoopInst = cast<Instruction>(VMap[Inst]);
-      PHINode *PN;
-
-      // First see if we have a single-operand PHI with the value defined by the
-      // original loop.
-      for (auto I = PHIBlock->begin(); (PN = dyn_cast<PHINode>(I)); ++I) {
-        assert(PN->getNumOperands() == 1 &&
-               "Exit block should only have on predecessor");
-        if (PN->getIncomingValue(0) == Inst)
-          break;
-      }
-      // If not create it.
-      if (!PN) {
-        PN = PHINode::Create(Inst->getType(), 2, Inst->getName() + ".lver",
-                             PHIBlock->begin());
-        for (auto *User : Inst->users())
-          if (!VersionedLoop->contains(cast<Instruction>(User)->getParent()))
-            User->replaceUsesOfWith(Inst, PN);
-        PN->addIncoming(Inst, VersionedLoop->getExitingBlock());
-      }
-      // Add the new incoming value from the non-versioned loop.
-      PN->addIncoming(NonVersionedLoopInst,
-                      NonVersionedLoop->getExitingBlock());
-    }
-  }
-
-private:
-  /// \brief The original loop.  This becomes the "versioned" one, i.e. control
-  /// goes if the memchecks all pass.
-  Loop *VersionedLoop;
-  /// \brief The fall-back loop, i.e. if any of the memchecks fail.
-  Loop *NonVersionedLoop;
-
-  /// \brief For each memory pointer it contains the partitionId it is used in.
-  /// If nullptr, no partitioning is used.
-  ///
-  /// The I-th entry corresponds to I-th entry in LAI.getRuntimePointerCheck().
-  /// If the pointer is used in multiple partitions the entry is set to -1.
-  const SmallVector<int, 8> *PtrToPartition;
-
-  /// \brief This maps the instructions from VersionedLoop to their counterpart
-  /// in NonVersionedLoop.
-  ValueToValueMapTy VMap;
-
-  /// \brief Analyses used.
-  const LoopAccessInfo &LAI;
-  LoopInfo *LI;
-  DominatorTree *DT;
-};
-
 /// \brief Returns the instructions that use values defined in the loop.
 static SmallVector<Instruction *, 8> findDefsUsedOutsideOfLoop(Loop *L) {
   SmallVector<Instruction *, 8> UsedOutside;
 
   for (auto *Block : L->getBlocks())
     // FIXME: I believe that this could use copy_if if the Inst reference could
     // be adapted into a pointer.
     for (auto &Inst : *Block) {

llvm/trunk/lib/Transforms/Utils/CMakeLists.txt

add_llvm_library(LLVMTransformUtils
   InstructionNamer.cpp
   IntegerDivision.cpp
   LCSSA.cpp
   Local.cpp
   LoopSimplify.cpp
   LoopUnroll.cpp
   LoopUnrollRuntime.cpp
   LoopUtils.cpp
+  LoopVersioning.cpp
   LowerInvoke.cpp
   LowerSwitch.cpp
   Mem2Reg.cpp
   MetaRenamer.cpp
   ModuleUtils.cpp
   PromoteMemoryToRegister.cpp
   SSAUpdater.cpp
   SimplifyCFG.cpp

llvm/trunk/lib/Transforms/Utils/LoopVersioning.cpp

+//===- LoopVersioning.cpp - Utility to version a loop ---------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines a utility class to perform loop versioning.  The versioned
+// loop speculates that otherwise may-aliasing memory accesses don't overlap and
+// emits checks to prove this.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Analysis/LoopAccessAnalysis.h"
+#include "llvm/Analysis/LoopInfo.h"
+#include "llvm/IR/Dominators.h"
+#include "llvm/Transforms/Utils/BasicBlockUtils.h"
+#include "llvm/Transforms/Utils/Cloning.h"
+#include "llvm/Transforms/Utils/LoopVersioning.h"
+
+using namespace llvm;
+
+LoopVersioning::LoopVersioning(const LoopAccessInfo &LAI, Loop *L, LoopInfo *LI,
+                               DominatorTree *DT,
+                               const SmallVector<int, 8> *PtrToPartition)
+    : VersionedLoop(L), NonVersionedLoop(nullptr),
+      PtrToPartition(PtrToPartition), LAI(LAI), LI(LI), DT(DT) {
+  assert(L->getExitBlock() && "No single exit block");
+  assert(L->getLoopPreheader() && "No preheader");
+}
+
+bool LoopVersioning::needsRuntimeChecks() const {
+  return LAI.getRuntimePointerCheck()->needsAnyChecking(PtrToPartition);
+}
+
+void LoopVersioning::versionLoop(Pass *P) {
+  Instruction *FirstCheckInst;
+  Instruction *MemRuntimeCheck;
+  // Add the memcheck in the original preheader (this is empty initially).
+  BasicBlock *MemCheckBB = VersionedLoop->getLoopPreheader();
+  std::tie(FirstCheckInst, MemRuntimeCheck) =
+      LAI.addRuntimeCheck(MemCheckBB->getTerminator(), PtrToPartition);
+  assert(MemRuntimeCheck && "called even though needsAnyChecking = false");
+
+  // Rename the block to make the IR more readable.
+  MemCheckBB->setName(VersionedLoop->getHeader()->getName() + ".lver.memcheck");
+
+  // Create empty preheader for the loop (and after cloning for the
+  // non-versioned loop).
+  BasicBlock *PH = SplitBlock(MemCheckBB, MemCheckBB->getTerminator(), DT, LI);
+  PH->setName(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, MemCheckBB, VersionedLoop, VMap, ".lver.orig",
+                             LI, DT, NonVersionedLoopBlocks);
+  remapInstructionsInBlocks(NonVersionedLoopBlocks, VMap);
+
+  // Insert the conditional branch based on the result of the memchecks.
+  Instruction *OrigTerm = MemCheckBB->getTerminator();
+  BranchInst::Create(NonVersionedLoop->getLoopPreheader(),
+                     VersionedLoop->getLoopPreheader(), MemRuntimeCheck,
+                     OrigTerm);
+  OrigTerm->eraseFromParent();
+
+  // The loops merge in the original exit block.  This is now dominated by the
+  // memchecking block.
+  DT->changeImmediateDominator(VersionedLoop->getExitBlock(), MemCheckBB);
+}
+
+void LoopVersioning::addPHINodes(
+    const SmallVectorImpl<Instruction *> &DefsUsedOutside) {
+  BasicBlock *PHIBlock = VersionedLoop->getExitBlock();
+  assert(PHIBlock && "No single successor to loop exit block");
+
+  for (auto *Inst : DefsUsedOutside) {
+    auto *NonVersionedLoopInst = cast<Instruction>(VMap[Inst]);
+    PHINode *PN;
+
+    // First see if we have a single-operand PHI with the value defined by the
+    // original loop.
+    for (auto I = PHIBlock->begin(); (PN = dyn_cast<PHINode>(I)); ++I) {
+      assert(PN->getNumOperands() == 1 &&
+             "Exit block should only have on predecessor");
+      if (PN->getIncomingValue(0) == Inst)
+        break;
+    }
+    // If not create it.
+    if (!PN) {
+      PN = PHINode::Create(Inst->getType(), 2, Inst->getName() + ".lver",
+                           PHIBlock->begin());
+      for (auto *User : Inst->users())
+        if (!VersionedLoop->contains(cast<Instruction>(User)->getParent()))
+          User->replaceUsesOfWith(Inst, PN);
+      PN->addIncoming(Inst, VersionedLoop->getExitingBlock());
+    }
+    // Add the new incoming value from the non-versioned loop.
+    PN->addIncoming(NonVersionedLoopInst, NonVersionedLoop->getExitingBlock());
+  }
+}