Allow LLE/LD and the loop versioning infrastructure to use SCEV predicates

[sbaranga]

Summary

LAA currently generates a set of SCEV predicates that must be checked by users.
In the case of Loop Distribute/Loop Load Elimination, no such predicates could have
been emitted, since we don't allow stride versioning. However, in the future there
could be SCEV predicates that will need to be checked.

This change adds support for SCEV predicate versioning in the Loop Distribute, Loop
Load Eliminate and the loop versioning infrastructure.

[anemet]

I have a high-level question. How should LoopDist work with SCEVAssumptions? If you look at alias checks we filter those in includeOnlyCrossPartitionChecks to get rid of unnecessary checks.

Could something like this be implemented with SCEVAssumptions? E.g. if you have a may-wrapping pointer that can't alias with anything in the other partition, we don't need to issue the non-wrapping check in order to make distribution correct.

lib/Transforms/Scalar/LoopDistribute.cpp

770–771

This comment needs updating now since we don't only version to disambiguate pointers anymore.

779

Extra () in the first term.

lib/Transforms/Utils/LoopVersioning.cpp

27–35

Now that we will feed LVers with two sets of checks optionally, we should probably move away from taking these in the ctor.

I think that we should have two members like addAliasChecks and addSCEVChecks or something.

I also don't think that we should take LAI but SCEVPredUnion instead.

The second ctor below is fine because the idea there is to take everything from LAI without filtering it.

55

s/MemCheckBB/RuntimeCheckBB

[sbaranga]

Hi Adam.

In D14240#282030, @anemet wrote:

I have a high-level question. How should LoopDist work with SCEVAssumptions? If you look at alias checks we filter those in includeOnlyCrossPartitionChecks to get rid of unnecessary checks.

That's an interesting problem. Currently we're only making enough assumptions to return true for LAI.canVectorizeMemory() (and LD checks that anyway).
Since it does that, I think it should add all predicates - for the current behaviour.

However if we wouldn't be interested in the answer for canVectorizeMemory() it should be possible to change MemoryDepChecker::areDepsSafe in LAA such that we have a per-dependence predicate. Then we can ignore the predicates dependences we don't care about. Do you think this approach makes sense?

Thanks,
Silviu

[sbaranga]

In D14240#282137, @sbaranga wrote:

Hi Adam.

In D14240#282030, @anemet wrote:

I have a high-level question. How should LoopDist work with SCEVAssumptions? If you look at alias checks we filter those in includeOnlyCrossPartitionChecks to get rid of unnecessary checks.

That's an interesting problem. Currently we're only making enough assumptions to return true for LAI.canVectorizeMemory() (and LD checks that anyway).
Since it does that, I think it should add all predicates - for the current behaviour.

However if we wouldn't be interested in the answer for canVectorizeMemory() it should be possible to change MemoryDepChecker::areDepsSafe in LAA such that we have a per-dependence predicate. Then we can ignore the predicates dependences we don't care about. Do you think this approach makes sense?

Thanks,
Silviu

I thought about this some more and besides dependences we would also need to figure out for each MemCheck what predicate needs to be true in order for us to be able to emit it.

[sbaranga]

Applied review comments.

[sbaranga]

lib/Transforms/Utils/LoopVersioning.cpp

26–35

Removing the Checks parameter made the two constructors have identical arguments. Since we want to be able to construct with all the changes from the LAI, I've added a bool parameter to enable this.

[anemet]

In D14240#282137, @sbaranga wrote:

However if we wouldn't be interested in the answer for canVectorizeMemory() it should be possible to change MemoryDepChecker::areDepsSafe in LAA such that we have a per-dependence predicate. Then we can ignore the predicates dependences we don't care about. Do you think this approach makes sense?

I am not saying we should implement this but I'd like to think about this now before committing to a design where we'd have no way of dropping unnecessary predicates.

I am not sure that we need per-dependence predicates though. I think it needs to be per alias set. If you have a pointer that may wrap that can now have a dependence to any of the pointers in the same alias set. It is still OK to drop this predicate for loop distribution if all members of this alias set fall into the same partition.

Where are we going to use SCEVPreds with alias checks? Is it to try to shape a SCEV into an AddRec?

include/llvm/Transforms/Utils/LoopVersioning.h

76–78

Sorry I didn't realize that by suggesting "add" in the name you would make this "additive". The problem is now we lost the nice "move constructibility" of Checks.

How about making this setAliasChecks which would still take a value and then restoring the std::move's.

Would a set* interface work for SCEVUnionPredicate?

95–96

Rename to AliasChecks?

[sbaranga]

In D14240#283209, @anemet wrote:

In D14240#282137, @sbaranga wrote:

However if we wouldn't be interested in the answer for canVectorizeMemory() it should be possible to change MemoryDepChecker::areDepsSafe in LAA such that we have a per-dependence predicate. Then we can ignore the predicates dependences we don't care about. Do you think this approach makes sense?

I am not saying we should implement this but I'd like to think about this now before committing to a design where we'd have no way of dropping unnecessary predicates.

I am not sure that we need per-dependence predicates though. I think it needs to be per alias set. If you have a pointer that may wrap that can now have a dependence to any of the pointers in the same alias set. It is still OK to drop this predicate for loop distribution if all members of this alias set fall into the same partition.

Where are we going to use SCEVPreds with alias checks? Is it to try to shape a SCEV into an AddRec?

Yes, we would use these to get AddRec expressions. I've also found one additional use case where it's already an AddRec and we want to check for nuw or nsw (see isStridedPtr).

include/llvm/Transforms/Utils/LoopVersioning.h

76–78

Ok, I understand. It wouldn't work at the moment for SCEVUnionPredicate. We need to define copy and move constructors for it. I'll create another review for that.

[sbaranga]

Added versioning to LLE as well. The same outstanding issues remain as with Loop Distribute.
Now using move/copy constructors to pass both alias checks and SCEV predicates to Loop Versioning.

[sbaranga]

Hi Adam,

I've uploaded a new patch, and had to make LLE use this as well.

Thanks,
Silviu

include/llvm/Transforms/Utils/LoopVersioning.h

76–78

I was confused about the ability of DenseMap to use copy/move constructors, sorry. It turns out we can actually do the same thing as for alias checks.

[anemet]

LGTM. We will have to add thresholds for the SCEV checks as well but right now these are only placeholders since these passes don't use stride checks.

[sbaranga]

Add thresholds for LD and LLE when versioning with SCEV predicates.
These passes won't actually use the predicates (they don't use stride versioning), so the actual value doesn't matter right now.

[sbaranga]

Committed in r252467, thanks!

[sbaranga]

Hi Adam,

In D14240#283209, @anemet wrote:

I am not saying we should implement this but I'd like to think about this now before committing to a design where we'd have no way of dropping unnecessary predicates.

I am not sure that we need per-dependence predicates though. I think it needs to be per alias set. If you have a pointer that may wrap that can now have a dependence to any of the pointers in the same alias set. It is still OK to drop this predicate for loop distribution if all members of this alias set fall into the same partition.

Where are we going to use SCEVPreds with alias checks? Is it to try to shape a SCEV into an AddRec?

Did you get a chance to think about this? Should we start a thread on llvm-dev?

I guess this would block the addition of new SCEV predicate types..

Thanks,
Silviu

[anemet]

Hi Silviu,

In D14240#288784, @sbaranga wrote:

Hi Adam,

In D14240#283209, @anemet wrote:

I am not saying we should implement this but I'd like to think about this now before committing to a design where we'd have no way of dropping unnecessary predicates.

I am not sure that we need per-dependence predicates though. I think it needs to be per alias set. If you have a pointer that may wrap that can now have a dependence to any of the pointers in the same alias set. It is still OK to drop this predicate for loop distribution if all members of this alias set fall into the same partition.

Where are we going to use SCEVPreds with alias checks? Is it to try to shape a SCEV into an AddRec?

Did you get a chance to think about this? Should we start a thread on llvm-dev?

I guess this would block the addition of new SCEV predicate types..

Sorry about the delay. No, I don't think this should hold up further work.

If we want to tag predicates with either the affected dependences or use some other mechanism is an additional improvement to try to reduce the number of predicates. As long as we keep the threshold for the number predicates low for distribution we should be good.

[sbaranga]

In D14240#300560, @anemet wrote:

Sorry about the delay. No, I don't think this should hold up further work.

If we want to tag predicates with either the affected dependences or use some other mechanism is an additional improvement to try to reduce the number of predicates. As long as we keep the threshold for the number predicates low for distribution we should be good.

Thanks, that makes sense to me. FWIW this means that after http://reviews.llvm.org/D14296 and a small update to LLE we should be ready to add the no overflow predicates, so we're not that far away.

-Silviu

include/llvm/Transforms/Utils/LoopVersioning.h

 #include "llvm/Transforms/Utils/ValueMapper.h"
 #include "llvm/Transforms/Utils/LoopUtils.h"
 
 namespace llvm {
 
 class Loop;
 class LoopAccessInfo;
 class LoopInfo;
+class ScalarEvolution;
 
 /// \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:
   /// \brief Expects MemCheck, LoopAccessInfo, Loop, LoopInfo, DominatorTree
   /// as input. It uses runtime check provided by user.
   LoopVersioning(SmallVector<RuntimePointerChecking::PointerCheck, 4> Checks,
                  const LoopAccessInfo &LAI, Loop *L, LoopInfo *LI,
-                 DominatorTree *DT);
+                 DominatorTree *DT, ScalarEvolution *SE);
 
   /// \brief Expects LoopAccessInfo, Loop, LoopInfo, DominatorTree as input.
   /// It uses default runtime check provided by LoopAccessInfo.
   LoopVersioning(const LoopAccessInfo &LAInfo, Loop *L, LoopInfo *LI,
-                 DominatorTree *DT);
+                 DominatorTree *DT, ScalarEvolution *SE);
 
   /// \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
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; }
 
   /// \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 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.
   void addPHINodes(const SmallVectorImpl<Instruction *> &DefsUsedOutside);
 
   /// \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 This maps the instructions from VersionedLoop to their counterpart
   /// in NonVersionedLoop.
   ValueToValueMapTy VMap;
 
   /// \brief The set of checks that we are versioning for.
   SmallVector<RuntimePointerChecking::PointerCheck, 4> Checks;
 
   /// \brief Analyses used.
   const LoopAccessInfo &LAI;
   LoopInfo *LI;
   DominatorTree *DT;
+  ScalarEvolution *SE;
 };
 }
 
 #endif

lib/Transforms/Scalar/LoopDistribute.cpp

public:
   LoopDistribute() : FunctionPass(ID) {
     initializeLoopDistributePass(*PassRegistry::getPassRegistry());
   }
 
   bool runOnFunction(Function &F) override {
     LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
     LAA = &getAnalysis<LoopAccessAnalysis>();
     DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
+    SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
 
     // Build up a worklist of inner-loops to vectorize. This is necessary as the
     // act of distributing a loop creates new loops and can invalidate iterators
     // across the loops.
     SmallVector<Loop *, 8> Worklist;
 
     for (Loop *TopLevelLoop : *LI)
       for (Loop *L : depth_first(TopLevelLoop))
         // We only handle inner-most loops.
         if (L->empty())
           Worklist.push_back(L);
 
     // Now walk the identified inner loops.
     bool Changed = false;
     for (Loop *L : Worklist)
       Changed |= processLoop(L);
 
     // Process each loop nest in the function.
     return Changed;
   }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
+    AU.addRequired<ScalarEvolutionWrapperPass>();
     AU.addRequired<LoopInfoWrapperPass>();
     AU.addPreserved<LoopInfoWrapperPass>();
     AU.addRequired<LoopAccessAnalysis>();
     AU.addRequired<DominatorTreeWrapperPass>();
     AU.addPreserved<DominatorTreeWrapperPass>();
   }
 
   static char ID;
bool processLoop(Loop *L) {
     Partitions.setupPartitionIdOnInstructions();
 
     // To keep things simple have an empty preheader before we version or clone
     // the loop.  (Also split if this has no predecessor, i.e. entry, because we
     // rely on PH having a predecessor.)
     if (!PH->getSinglePredecessor() || &*PH->begin() != PH->getTerminator())
       SplitBlock(PH, PH->getTerminator(), DT, LI);
 
     // If we need run-time checks to disambiguate pointers are run-time, version
     // the loop now.
     auto PtrToPartition = Partitions.computePartitionSetForPointers(LAI);
     const auto *RtPtrChecking = LAI.getRuntimePointerChecking();
     const auto &AllChecks = RtPtrChecking->getChecks();
     auto Checks = includeOnlyCrossPartitionChecks(AllChecks, PtrToPartition,
                                                   RtPtrChecking);
-    if (!Checks.empty()) {
+
+    const SCEVUnionPredicate &Pred = LAI.Preds;
+    if ((!Pred.isAlwaysTrue()) || !Checks.empty()) {
       DEBUG(dbgs() << "\nPointers:\n");
       DEBUG(LAI.getRuntimePointerChecking()->printChecks(dbgs(), Checks));
-      LoopVersioning LVer(std::move(Checks), LAI, L, LI, DT);
+      LoopVersioning LVer(std::move(Checks), LAI, L, LI, DT, SE);
       LVer.versionLoop(DefsUsedOutside);
     }
 
     // Create identical copies of the original loop for each partition and hook
     // them up sequentially.
     Partitions.cloneLoops(this);
 
     // Now, we remove the instruction from each loop that don't belong to that
bool processLoop(Loop *L) {
     ++NumLoopsDistributed;
     return true;
   }
 
   // Analyses used.
   LoopInfo *LI;
   LoopAccessAnalysis *LAA;
   DominatorTree *DT;
+  ScalarEvolution *SE;
 };
 } // anonymous namespace
 
 char LoopDistribute::ID;
 static const char ldist_name[] = "Loop Distribition";
 
 INITIALIZE_PASS_BEGIN(LoopDistribute, LDIST_NAME, ldist_name, false, false)
 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(LoopAccessAnalysis)
 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
 INITIALIZE_PASS_END(LoopDistribute, LDIST_NAME, ldist_name, false, false)
 
 namespace llvm {
 FunctionPass *createLoopDistributePass() { return new LoopDistribute(); }
 }

lib/Transforms/Utils/LoopVersioning.cpp

 // emits checks to prove this.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/Utils/LoopVersioning.h"
 
 #include "llvm/Analysis/LoopAccessAnalysis.h"
 #include "llvm/Analysis/LoopInfo.h"
+#include "llvm/Analysis/ScalarEvolutionExpander.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
 #include "llvm/Transforms/Utils/Cloning.h"
 
 using namespace llvm;
 
 LoopVersioning::LoopVersioning(
     SmallVector<RuntimePointerChecking::PointerCheck, 4> Checks,
-    const LoopAccessInfo &LAI, Loop *L, LoopInfo *LI, DominatorTree *DT)
+    const LoopAccessInfo &LAI, Loop *L, LoopInfo *LI, DominatorTree *DT,
+    ScalarEvolution *SE)
     : VersionedLoop(L), NonVersionedLoop(nullptr), Checks(std::move(Checks)),
-      LAI(LAI), LI(LI), DT(DT) {
+      LAI(LAI), LI(LI), DT(DT), SE(SE) {
   assert(L->getExitBlock() && "No single exit block");
   assert(L->getLoopPreheader() && "No preheader");
 }
 
 LoopVersioning::LoopVersioning(const LoopAccessInfo &LAInfo, Loop *L,
-                               LoopInfo *LI, DominatorTree *DT)
+                               LoopInfo *LI, DominatorTree *DT,
+                               ScalarEvolution *SE)
     : VersionedLoop(L), NonVersionedLoop(nullptr),
       Checks(LAInfo.getRuntimePointerChecking()->getChecks()), LAI(LAInfo),
-      LI(LI), DT(DT) {
+      LI(LI), DT(DT), SE(SE) {
   assert(L->getExitBlock() && "No single exit block");
   assert(L->getLoopPreheader() && "No preheader");
 }
 
 void LoopVersioning::versionLoop(
     const SmallVectorImpl<Instruction *> &DefsUsedOutside) {
   Instruction *FirstCheckInst;
   Instruction *MemRuntimeCheck;
+  Value *SCEVRuntimeCheck;
+  Value *RuntimeCheck = nullptr;
+
   // Add the memcheck in the original preheader (this is empty initially).
   BasicBlock *MemCheckBB = VersionedLoop->getLoopPreheader();
   std::tie(FirstCheckInst, MemRuntimeCheck) =
       LAI.addRuntimeChecks(MemCheckBB->getTerminator(), Checks);
   assert(MemRuntimeCheck && "called even though needsAnyChecking = false");
 
+  const SCEVUnionPredicate &Pred = LAI.Preds;
+  SCEVExpander Exp(*SE, MemCheckBB->getModule()->getDataLayout(), "scev.check");
+  SCEVRuntimeCheck = Exp.expandCodeForPredicate(&Pred,
+                                                MemCheckBB->getTerminator());
+  auto *CI = dyn_cast<ConstantInt>(SCEVRuntimeCheck);
+
+  // Discard the SCEV runtime check if it is always true.
+  if (CI && CI->isZero())
+    SCEVRuntimeCheck = nullptr;
+
+  if (MemRuntimeCheck && SCEVRuntimeCheck) {
+    RuntimeCheck = BinaryOperator::Create(Instruction::Or, MemRuntimeCheck,
+                                          SCEVRuntimeCheck, "ldist.safe");
+    if (auto *I = dyn_cast<Instruction>(RuntimeCheck))
+      I->insertBefore(MemCheckBB->getTerminator());
+  } else
+    RuntimeCheck = MemRuntimeCheck ? MemRuntimeCheck : SCEVRuntimeCheck;
+
+  assert(RuntimeCheck && "called even though we don't need "
+                         "any runtime checks");
+
   // 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);
+                     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(), MemCheckBB);
 
   // Adds the necessary PHI nodes for the versioned loops based on the
   // loop-defined values used outside of the loop.