lib/Transforms/Scalar/LoopDistribute.cpp

   1 //===- LoopDistribute.cpp - Loop Distribution Pass ------------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements the Loop Distribution Pass.  Its main focus is to
  11 // distribute loops that cannot be vectorized due to dependence cycles.  It
  12 // tries to isolate the offending dependences into a new loop allowing
  13 // vectorization of the remaining parts.
  14 //
  15 // For dependence analysis, the pass uses the LoopVectorizer's
  16 // LoopAccessAnalysis.  Because this analysis presumes no change in the order of
  17 // memory operations, special care is taken to preserve the lexical order of
  18 // these operations.
  19 //
  20 // Similarly to the Vectorizer, the pass also supports loop versioning to
  21 // run-time disambiguate potentially overlapping arrays.
  22 //
  23 //===----------------------------------------------------------------------===//
  24
  25 #include "llvm/ADT/DepthFirstIterator.h"
  26 #include "llvm/ADT/EquivalenceClasses.h"
  27 #include "llvm/ADT/STLExtras.h"
  28 #include "llvm/ADT/Statistic.h"
  29 #include "llvm/Analysis/LoopAccessAnalysis.h"
  30 #include "llvm/Analysis/LoopInfo.h"
  31 #include "llvm/IR/Dominators.h"
  32 #include "llvm/Pass.h"
  33 #include "llvm/Support/CommandLine.h"
  34 #include "llvm/Support/Debug.h"
  35 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
  36 #include "llvm/Transforms/Utils/Cloning.h"
  37 #include <list>
  38
  39 #define LDIST_NAME "loop-distribute"
  40 #define DEBUG_TYPE LDIST_NAME
  41
  42 using namespace llvm;
  43
  44 static cl::opt<bool>
  45     LDistVerify("loop-distribute-verify", cl::Hidden,
  46                 cl::desc("Turn on DominatorTree and LoopInfo verification "
  47                          "after Loop Distribution"),
  48                 cl::init(false));
  49
  50 static cl::opt<bool> DistributeNonIfConvertible(
  51     "loop-distribute-non-if-convertible", cl::Hidden,
  52     cl::desc("Whether to distribute into a loop that may not be "
  53              "if-convertible by the loop vectorizer"),
  54     cl::init(false));
  55
  56 STATISTIC(NumLoopsDistributed, "Number of loops distributed");
  57
  58 namespace {
  59 /// \brief Maintains the set of instructions of the loop for a partition before
  60 /// cloning.  After cloning, it hosts the new loop.
  61 class InstPartition {
  62   typedef SmallPtrSet<Instruction *, 8> InstructionSet;
  63
  64 public:
  65   InstPartition(Instruction *I, Loop *L, bool DepCycle = false)
  66       : DepCycle(DepCycle), OrigLoop(L), ClonedLoop(nullptr) {
  67     Set.insert(I);
  68   }
  69
  70   /// \brief Returns whether this partition contains a dependence cycle.
  71   bool hasDepCycle() const { return DepCycle; }
  72
  73   /// \brief Adds an instruction to this partition.
  74   void add(Instruction *I) { Set.insert(I); }
  75
  76   /// \brief Collection accessors.
  77   InstructionSet::iterator begin() { return Set.begin(); }
  78   InstructionSet::iterator end() { return Set.end(); }
  79   InstructionSet::const_iterator begin() const { return Set.begin(); }
  80   InstructionSet::const_iterator end() const { return Set.end(); }
  81   bool empty() const { return Set.empty(); }
  82
  83   /// \brief Moves this partition into \p Other.  This partition becomes empty
  84   /// after this.
  85   void moveTo(InstPartition &Other) {
  86     Other.Set.insert(Set.begin(), Set.end());
  87     Set.clear();
  88     Other.DepCycle |= DepCycle;
  89   }
  90
  91   /// \brief Populates the partition with a transitive closure of all the
  92   /// instructions that the seeded instructions dependent on.
  93   void populateUsedSet() {
  94     // FIXME: We currently don't use control-dependence but simply include all
  95     // blocks (possibly empty at the end) and let simplifycfg mostly clean this
  96     // up.
  97     for (auto *B : OrigLoop->getBlocks())
  98       Set.insert(B->getTerminator());
  99
 100     // Follow the use-def chains to form a transitive closure of all the
 101     // instructions that the originally seeded instructions depend on.
 102     SmallVector<Instruction *, 8> Worklist(Set.begin(), Set.end());
 103     while (!Worklist.empty()) {
 104       Instruction *I = Worklist.pop_back_val();
 105       // Insert instructions from the loop that we depend on.
 106       for (Value *V : I->operand_values()) {
 107         auto *I = dyn_cast<Instruction>(V);
 108         if (I && OrigLoop->contains(I->getParent()) && Set.insert(I).second)
 109           Worklist.push_back(I);
 110       }
 111     }
 112   }
 113
 114   /// \brief Clones the original loop.
 115   ///
 116   /// Updates LoopInfo and DominatorTree using the information that block \p
 117   /// LoopDomBB dominates the loop.
 118   Loop *cloneLoopWithPreheader(BasicBlock *InsertBefore, BasicBlock *LoopDomBB,
 119                                unsigned Index, LoopInfo *LI,
 120                                DominatorTree *DT) {
 121     ClonedLoop = ::cloneLoopWithPreheader(InsertBefore, LoopDomBB, OrigLoop,
 122                                           VMap, Twine(".ldist") + Twine(Index),
 123                                           LI, DT, ClonedLoopBlocks);
 124     return ClonedLoop;
 125   }
 126
 127   /// \brief The cloned loop.  If this partition is mapped to the original loop,
 128   /// this is null.
 129   const Loop *getClonedLoop() const { return ClonedLoop; }
 130
 131   /// \brief Returns the loop where this partition ends up after distribution.
 132   /// If this partition is mapped to the original loop then use the block from
 133   /// the loop.
 134   const Loop *getDistributedLoop() const {
 135     return ClonedLoop ? ClonedLoop : OrigLoop;
 136   }
 137
 138   /// \brief The VMap that is populated by cloning and then used in
 139   /// remapinstruction to remap the cloned instructions.
 140   ValueToValueMapTy &getVMap() { return VMap; }
 141
 142   /// \brief Remaps the cloned instructions using VMap.
 143   void remapInstructions() {
 144     remapInstructionsInBlocks(ClonedLoopBlocks, VMap);
 145   }
 146
 147   /// \brief Based on the set of instructions selected for this partition,
 148   /// removes the unnecessary ones.
 149   void removeUnusedInsts() {
 150     SmallVector<Instruction *, 8> Unused;
 151
 152     for (auto *Block : OrigLoop->getBlocks())
 153       for (auto &Inst : *Block)
 154         if (!Set.count(&Inst)) {
 155           Instruction *NewInst = &Inst;
 156           if (!VMap.empty())
 157             NewInst = cast<Instruction>(VMap[NewInst]);
 158
 159           assert(!isa<BranchInst>(NewInst) &&
 160                  "Branches are marked used early on");
 161           Unused.push_back(NewInst);
 162         }
 163
 164     // Delete the instructions backwards, as it has a reduced likelihood of
 165     // having to update as many def-use and use-def chains.
 166     for (auto I = Unused.rbegin(), E = Unused.rend(); I != E; ++I) {
 167       auto *Inst = *I;
 168
 169       if (!Inst->use_empty())
 170         Inst->replaceAllUsesWith(UndefValue::get(Inst->getType()));
 171       Inst->eraseFromParent();
 172     }
 173   }
 174
 175   void print() const {
 176     if (DepCycle)
 177       dbgs() << "  (cycle)\n";
 178     for (auto *I : Set)
 179       // Prefix with the block name.
 180       dbgs() << "  " << I->getParent()->getName() << ":" << *I << "\n";
 181   }
 182
 183   void printBlocks() const {
 184     for (auto *BB : getDistributedLoop()->getBlocks())
 185       dbgs() << *BB;
 186   }
 187
 188 private:
 189   /// \brief Instructions from OrigLoop selected for this partition.
 190   InstructionSet Set;
 191
 192   /// \brief Whether this partition contains a dependence cycle.
 193   bool DepCycle;
 194
 195   /// \brief The original loop.
 196   Loop *OrigLoop;
 197
 198   /// \brief The cloned loop.  If this partition is mapped to the original loop,
 199   /// this is null.
 200   Loop *ClonedLoop;
 201
 202   /// \brief The blocks of ClonedLoop including the preheader.  If this
 203   /// partition is mapped to the original loop, this is empty.
 204   SmallVector<BasicBlock *, 8> ClonedLoopBlocks;
 205
 206   /// \brief These gets populated once the set of instructions have been
 207   /// finalized. If this partition is mapped to the original loop, these are not
 208   /// set.
 209   ValueToValueMapTy VMap;
 210 };
 211
 212 /// \brief Holds the set of Partitions.  It populates them, merges them and then
 213 /// clones the loops.
 214 class InstPartitionContainer {
 215   typedef DenseMap<Instruction *, int> InstToPartitionIdT;
 216
 217 public:
 218   InstPartitionContainer(Loop *L, LoopInfo *LI, DominatorTree *DT)
 219       : L(L), LI(LI), DT(DT) {}
 220
 221   /// \brief Returns the number of partitions.
 222   unsigned getSize() const { return PartitionContainer.size(); }
 223
 224   /// \brief Adds \p Inst into the current partition if that is marked to
 225   /// contain cycles.  Otherwise start a new partition for it.
 226   void addToCyclicPartition(Instruction *Inst) {
 227     // If the current partition is non-cyclic.  Start a new one.
 228     if (PartitionContainer.empty() || !PartitionContainer.back().hasDepCycle())
 229       PartitionContainer.emplace_back(Inst, L, /*DepCycle=*/true);
 230     else
 231       PartitionContainer.back().add(Inst);
 232   }
 233
 234   /// \brief Adds \p Inst into a partition that is not marked to contain
 235   /// dependence cycles.
 236   ///
 237   //  Initially we isolate memory instructions into as many partitions as
 238   //  possible, then later we may merge them back together.
 239   void addToNewNonCyclicPartition(Instruction *Inst) {
 240     PartitionContainer.emplace_back(Inst, L);
 241   }
 242
 243   /// \brief Merges adjacent non-cyclic partitions.
 244   ///
 245   /// The idea is that we currently only want to isolate the non-vectorizable
 246   /// partition.  We could later allow more distribution among these partition
 247   /// too.
 248   void mergeAdjacentNonCyclic() {
 249     mergeAdjacentPartitionsIf(
 250         [](const InstPartition *P) { return !P->hasDepCycle(); });
 251   }
 252
 253   /// \brief If a partition contains only conditional stores, we won't vectorize
 254   /// it.  Try to merge it with a previous cyclic partition.
 255   void mergeNonIfConvertible() {
 256     mergeAdjacentPartitionsIf([&](const InstPartition *Partition) {
 257       if (Partition->hasDepCycle())
 258         return true;
 259
 260       // Now, check if all stores are conditional in this partition.
 261       bool seenStore = false;
 262
 263       for (auto *Inst : *Partition)
 264         if (isa<StoreInst>(Inst)) {
 265           seenStore = true;
 266           if (!LoopAccessInfo::blockNeedsPredication(Inst->getParent(), L, DT))
 267             return false;
 268         }
 269       return seenStore;
 270     });
 271   }
 272
 273   /// \brief Merges the partitions according to various heuristics.
 274   void mergeBeforePopulating() {
 275     mergeAdjacentNonCyclic();
 276     if (!DistributeNonIfConvertible)
 277       mergeNonIfConvertible();
 278   }
 279
 280   /// \brief Merges partitions in order to ensure that no loads are duplicated.
 281   ///
 282   /// We can't duplicate loads because that could potentially reorder them.
 283   /// LoopAccessAnalysis provides dependency information with the context that
 284   /// the order of memory operation is preserved.
 285   ///
 286   /// Return if any partitions were merged.
 287   bool mergeToAvoidDuplicatedLoads() {
 288     typedef DenseMap<Instruction *, InstPartition *> LoadToPartitionT;
 289     typedef EquivalenceClasses<InstPartition *> ToBeMergedT;
 290
 291     LoadToPartitionT LoadToPartition;
 292     ToBeMergedT ToBeMerged;
 293
 294     // Step through the partitions and create equivalence between partitions
 295     // that contain the same load.  Also put partitions in between them in the
 296     // same equivalence class to avoid reordering of memory operations.
 297     for (PartitionContainerT::iterator I = PartitionContainer.begin(),
 298                                        E = PartitionContainer.end();
 299          I != E; ++I) {
 300       auto *PartI = &*I;
 301
 302       // If a load occurs in two partitions PartI and PartJ, merge all
 303       // partitions (PartI, PartJ] into PartI.
 304       for (Instruction *Inst : *PartI)
 305         if (isa<LoadInst>(Inst)) {
 306           bool NewElt;
 307           LoadToPartitionT::iterator LoadToPart;
 308
 309           std::tie(LoadToPart, NewElt) =
 310               LoadToPartition.insert(std::make_pair(Inst, PartI));
 311           if (!NewElt) {
 312             DEBUG(dbgs() << "Merging partitions due to this load in multiple "
 313                          << "partitions: " << PartI << ", "
 314                          << LoadToPart->second << "\n" << *Inst << "\n");
 315
 316             auto PartJ = I;
 317             do {
 318               --PartJ;
 319               ToBeMerged.unionSets(PartI, &*PartJ);
 320             } while (&*PartJ != LoadToPart->second);
 321           }
 322         }
 323     }
 324     if (ToBeMerged.empty())
 325       return false;
 326
 327     // Merge the member of an equivalence class into its class leader.  This
 328     // makes the members empty.
 329     for (ToBeMergedT::iterator I = ToBeMerged.begin(), E = ToBeMerged.end();
 330          I != E; ++I) {
 331       if (!I->isLeader())
 332         continue;
 333
 334       auto PartI = I->getData();
 335       for (auto PartJ : make_range(std::next(ToBeMerged.member_begin(I)),
 336                                    ToBeMerged.member_end())) {
 337         PartJ->moveTo(*PartI);
 338       }
 339     }
 340
 341     // Remove the empty partitions.
 342     PartitionContainer.remove_if(
 343         [](const InstPartition &P) { return P.empty(); });
 344
 345     return true;
 346   }
 347
 348   /// \brief Sets up the mapping between instructions to partitions.  If the
 349   /// instruction is duplicated across multiple partitions, set the entry to -1.
 350   void setupPartitionIdOnInstructions() {
 351     int PartitionID = 0;
 352     for (const auto &Partition : PartitionContainer) {
 353       for (Instruction *Inst : Partition) {
 354         bool NewElt;
 355         InstToPartitionIdT::iterator Iter;
 356
 357         std::tie(Iter, NewElt) =
 358             InstToPartitionId.insert(std::make_pair(Inst, PartitionID));
 359         if (!NewElt)
 360           Iter->second = -1;
 361       }
 362       ++PartitionID;
 363     }
 364   }
 365
 366   /// \brief Populates the partition with everything that the seeding
 367   /// instructions require.
 368   void populateUsedSet() {
 369     for (auto &P : PartitionContainer)
 370       P.populateUsedSet();
 371   }
 372
 373   /// \brief This performs the main chunk of the work of cloning the loops for
 374   /// the partitions.
 375   void cloneLoops(Pass *P) {
 376     BasicBlock *OrigPH = L->getLoopPreheader();
 377     // At this point the predecessor of the preheader is either the memcheck
 378     // block or the top part of the original preheader.
 379     BasicBlock *Pred = OrigPH->getSinglePredecessor();
 380     assert(Pred && "Preheader does not have a single predecessor");
 381     BasicBlock *ExitBlock = L->getExitBlock();
 382     assert(ExitBlock && "No single exit block");
 383     Loop *NewLoop;
 384
 385     assert(!PartitionContainer.empty() && "at least two partitions expected");
 386     // We're cloning the preheader along with the loop so we already made sure
 387     // it was empty.
 388     assert(&*OrigPH->begin() == OrigPH->getTerminator() &&
 389            "preheader not empty");
 390
 391     // Create a loop for each partition except the last.  Clone the original
 392     // loop before PH along with adding a preheader for the cloned loop.  Then
 393     // update PH to point to the newly added preheader.
 394     BasicBlock *TopPH = OrigPH;
 395     unsigned Index = getSize() - 1;
 396     for (auto I = std::next(PartitionContainer.rbegin()),
 397               E = PartitionContainer.rend();
 398          I != E; ++I, --Index, TopPH = NewLoop->getLoopPreheader()) {
 399       auto *Part = &*I;
 400
 401       NewLoop = Part->cloneLoopWithPreheader(TopPH, Pred, Index, LI, DT);
 402
 403       Part->getVMap()[ExitBlock] = TopPH;
 404       Part->remapInstructions();
 405     }
 406     Pred->getTerminator()->replaceUsesOfWith(OrigPH, TopPH);
 407
 408     // Now go in forward order and update the immediate dominator for the
 409     // preheaders with the exiting block of the previous loop.  Dominance
 410     // within the loop is updated in cloneLoopWithPreheader.
 411     for (auto Curr = PartitionContainer.cbegin(),
 412               Next = std::next(PartitionContainer.cbegin()),
 413               E = PartitionContainer.cend();
 414          Next != E; ++Curr, ++Next)
 415       DT->changeImmediateDominator(
 416           Next->getDistributedLoop()->getLoopPreheader(),
 417           Curr->getDistributedLoop()->getExitingBlock());
 418   }
 419
 420   /// \brief Removes the dead instructions from the cloned loops.
 421   void removeUnusedInsts() {
 422     for (auto &Partition : PartitionContainer)
 423       Partition.removeUnusedInsts();
 424   }
 425
 426   /// \brief For each memory pointer, it computes the partitionId the pointer is
 427   /// used in.
 428   ///
 429   /// This returns an array of int where the I-th entry corresponds to I-th
 430   /// entry in LAI.getRuntimePointerCheck().  If the pointer is used in multiple
 431   /// partitions its entry is set to -1.
 432   SmallVector<int, 8>
 433   computePartitionSetForPointers(const LoopAccessInfo &LAI) {
 434     const LoopAccessInfo::RuntimePointerCheck *RtPtrCheck =
 435         LAI.getRuntimePointerCheck();
 436
 437     unsigned N = RtPtrCheck->Pointers.size();
 438     SmallVector<int, 8> PtrToPartitions(N);
 439     for (unsigned I = 0; I < N; ++I) {
 440       Value *Ptr = RtPtrCheck->Pointers[I];
 441       auto Instructions =
 442           LAI.getInstructionsForAccess(Ptr, RtPtrCheck->IsWritePtr[I]);
 443
 444       int &Partition = PtrToPartitions[I];
 445       // First set it to uninitialized.
 446       Partition = -2;
 447       for (Instruction *Inst : Instructions) {
 448         // Note that this could be -1 if Inst is duplicated across multiple
 449         // partitions.
 450         int ThisPartition = this->InstToPartitionId[Inst];
 451         if (Partition == -2)
 452           Partition = ThisPartition;
 453         // -1 means belonging to multiple partitions.
 454         else if (Partition == -1)
 455           break;
 456         else if (Partition != (int)ThisPartition)
 457           Partition = -1;
 458       }
 459       assert(Partition != -2 && "Pointer not belonging to any partition");
 460     }
 461
 462     return PtrToPartitions;
 463   }
 464
 465   void print(raw_ostream &OS) const {
 466     unsigned Index = 0;
 467     for (const auto &P : PartitionContainer) {
 468       OS << "Partition " << Index++ << " (" << &P << "):\n";
 469       P.print();
 470     }
 471   }
 472
 473   void dump() const { print(dbgs()); }
 474
 475 #ifndef NDEBUG
 476   friend raw_ostream &operator<<(raw_ostream &OS,
 477                                  const InstPartitionContainer &Partitions) {
 478     Partitions.print(OS);
 479     return OS;
 480   }
 481 #endif
 482
 483   void printBlocks() const {
 484     unsigned Index = 0;
 485     for (const auto &P : PartitionContainer) {
 486       dbgs() << "\nPartition " << Index++ << " (" << &P << "):\n";
 487       P.printBlocks();
 488     }
 489   }
 490
 491 private:
 492   typedef std::list<InstPartition> PartitionContainerT;
 493
 494   /// \brief List of partitions.
 495   PartitionContainerT PartitionContainer;
 496
 497   /// \brief Mapping from Instruction to partition Id.  If the instruction
 498   /// belongs to multiple partitions the entry contains -1.
 499   InstToPartitionIdT InstToPartitionId;
 500
 501   Loop *L;
 502   LoopInfo *LI;
 503   DominatorTree *DT;
 504
 505   /// \brief The control structure to merge adjacent partitions if both satisfy
 506   /// the \p Predicate.
 507   template <class UnaryPredicate>
 508   void mergeAdjacentPartitionsIf(UnaryPredicate Predicate) {
 509     InstPartition *PrevMatch = nullptr;
 510     for (auto I = PartitionContainer.begin(); I != PartitionContainer.end();) {
 511       auto DoesMatch = Predicate(&*I);
 512       if (PrevMatch == nullptr && DoesMatch) {
 513         PrevMatch = &*I;
 514         ++I;
 515       } else if (PrevMatch != nullptr && DoesMatch) {
 516         I->moveTo(*PrevMatch);
 517         I = PartitionContainer.erase(I);
 518       } else {
 519         PrevMatch = nullptr;
 520         ++I;
 521       }
 522     }
 523   }
 524 };
 525
 526 /// \brief For each memory instruction, this class maintains difference of the
 527 /// number of unsafe dependences that start out from this instruction minus
 528 /// those that end here.
 529 ///
 530 /// By traversing the memory instructions in program order and accumulating this
 531 /// number, we know whether any unsafe dependence crosses over a program point.
 532 class MemoryInstructionDependences {
 533   typedef MemoryDepChecker::Dependence Dependence;
 534
 535 public:
 536   struct Entry {
 537     Instruction *Inst;
 538     unsigned NumUnsafeDependencesStartOrEnd;
 539
 540     Entry(Instruction *Inst) : Inst(Inst), NumUnsafeDependencesStartOrEnd(0) {}
 541   };
 542
 543   typedef SmallVector<Entry, 8> AccessesType;
 544
 545   AccessesType::const_iterator begin() const { return Accesses.begin(); }
 546   AccessesType::const_iterator end() const { return Accesses.end(); }
 547
 548   MemoryInstructionDependences(
 549       const SmallVectorImpl<Instruction *> &Instructions,
 550       const SmallVectorImpl<Dependence> &InterestingDependences) {
 551     Accesses.append(Instructions.begin(), Instructions.end());
 552
 553     DEBUG(dbgs() << "Backward dependences:\n");
 554     for (auto &Dep : InterestingDependences)
 555       if (Dep.isPossiblyBackward()) {
 556         // Note that the designations source and destination follow the program
 557         // order, i.e. source is always first.  (The direction is given by the
 558         // DepType.)
 559         ++Accesses[Dep.Source].NumUnsafeDependencesStartOrEnd;
 560         --Accesses[Dep.Destination].NumUnsafeDependencesStartOrEnd;
 561
 562         DEBUG(Dep.print(dbgs(), 2, Instructions));
 563       }
 564   }
 565
 566 private:
 567   AccessesType Accesses;
 568 };
 569
 570 /// \brief Handles the loop versioning based on memchecks.
 571 class LoopVersioning {
 572 public:
 573   LoopVersioning(const LoopAccessInfo &LAI, Loop *L, LoopInfo *LI,
 574                  DominatorTree *DT,
 575                  const SmallVector<int, 8> *PtrToPartition = nullptr)
 576       : VersionedLoop(L), NonVersionedLoop(nullptr),
 577         PtrToPartition(PtrToPartition), LAI(LAI), LI(LI), DT(DT) {}
 578
 579   /// \brief Returns true if we need memchecks to disambiguate may-aliasing
 580   /// accesses.
 581   bool needsRuntimeChecks() const {
 582     return LAI.getRuntimePointerCheck()->needsAnyChecking(PtrToPartition);
 583   }
 584
 585   /// \brief Performs the CFG manipulation part of versioning the loop including
 586   /// the DominatorTree and LoopInfo updates.
 587   void versionLoop(Pass *P) {
 588     Instruction *FirstCheckInst;
 589     Instruction *MemRuntimeCheck;
 590     // Add the memcheck in the original preheader (this is empty initially).
 591     BasicBlock *MemCheckBB = VersionedLoop->getLoopPreheader();
 592     std::tie(FirstCheckInst, MemRuntimeCheck) =
 593         LAI.addRuntimeCheck(MemCheckBB->getTerminator(), PtrToPartition);
 594     assert(MemRuntimeCheck && "called even though needsAnyChecking = false");
 595
 596     // Rename the block to make the IR more readable.
 597     MemCheckBB->setName(VersionedLoop->getHeader()->getName() +
 598                         ".lver.memcheck");
 599
 600     // Create empty preheader for the loop (and after cloning for the
 601     // non-versioned loop).
 602     BasicBlock *PH =
 603         SplitBlock(MemCheckBB, MemCheckBB->getTerminator(), DT, LI);
 604     PH->setName(VersionedLoop->getHeader()->getName() + ".ph");
 605
 606     // Clone the loop including the preheader.
 607     //
 608     // FIXME: This does not currently preserve SimplifyLoop because the exit
 609     // block is a join between the two loops.
 610     SmallVector<BasicBlock *, 8> NonVersionedLoopBlocks;
 611     NonVersionedLoop =
 612         cloneLoopWithPreheader(PH, MemCheckBB, VersionedLoop, VMap,
 613                                ".lver.orig", LI, DT, NonVersionedLoopBlocks);
 614     remapInstructionsInBlocks(NonVersionedLoopBlocks, VMap);
 615
 616     // Insert the conditional branch based on the result of the memchecks.
 617     Instruction *OrigTerm = MemCheckBB->getTerminator();
 618     BranchInst::Create(NonVersionedLoop->getLoopPreheader(),
 619                        VersionedLoop->getLoopPreheader(), MemRuntimeCheck,
 620                        OrigTerm);
 621     OrigTerm->eraseFromParent();
 622
 623     // The loops merge in the original exit block.  This is now dominated by the
 624     // memchecking block.
 625     DT->changeImmediateDominator(VersionedLoop->getExitBlock(), MemCheckBB);
 626   }
 627
 628   /// \brief Adds the necessary PHI nodes for the versioned loops based on the
 629   /// loop-defined values used outside of the loop.
 630   void addPHINodes(const SmallVectorImpl<Instruction *> &DefsUsedOutside) {
 631     BasicBlock *PHIBlock = VersionedLoop->getExitBlock();
 632     assert(PHIBlock && "No single successor to loop exit block");
 633
 634     for (auto *Inst : DefsUsedOutside) {
 635       auto *NonVersionedLoopInst = cast<Instruction>(VMap[Inst]);
 636       PHINode *PN;
 637
 638       // First see if we have a single-operand PHI with the value defined by the
 639       // original loop.
 640       for (auto I = PHIBlock->begin(); (PN = dyn_cast<PHINode>(I)); ++I) {
 641         assert(PN->getNumOperands() == 1 &&
 642                "Exit block should only have on predecessor");
 643         if (PN->getIncomingValue(0) == Inst)
 644           break;
 645       }
 646       // If not create it.
 647       if (!PN) {
 648         PN = PHINode::Create(Inst->getType(), 2, Inst->getName() + ".lver",
 649                              PHIBlock->begin());
 650         for (auto *User : Inst->users())
 651           if (!VersionedLoop->contains(cast<Instruction>(User)->getParent()))
 652             User->replaceUsesOfWith(Inst, PN);
 653         PN->addIncoming(Inst, VersionedLoop->getExitingBlock());
 654       }
 655       // Add the new incoming value from the non-versioned loop.
 656       PN->addIncoming(NonVersionedLoopInst,
 657                       NonVersionedLoop->getExitingBlock());
 658     }
 659   }
 660
 661 private:
 662   /// \brief The original loop.  This becomes the "versioned" one, i.e. control
 663   /// goes if the memchecks all pass.
 664   Loop *VersionedLoop;
 665   /// \brief The fall-back loop, i.e. if any of the memchecks fail.
 666   Loop *NonVersionedLoop;
 667
 668   /// \brief For each memory pointer it contains the partitionId it is used in.
 669   /// If nullptr, no partitioning is used.
 670   ///
 671   /// The I-th entry corresponds to I-th entry in LAI.getRuntimePointerCheck().
 672   /// If the pointer is used in multiple partitions the entry is set to -1.
 673   const SmallVector<int, 8> *PtrToPartition;
 674
 675   /// \brief This maps the instructions from VersionedLoop to their counterpart
 676   /// in NonVersionedLoop.
 677   ValueToValueMapTy VMap;
 678
 679   /// \brief Analyses used.
 680   const LoopAccessInfo &LAI;
 681   LoopInfo *LI;
 682   DominatorTree *DT;
 683 };
 684
 685 /// \brief Returns the instructions that use values defined in the loop.
 686 static SmallVector<Instruction *, 8> findDefsUsedOutsideOfLoop(Loop *L) {
 687   SmallVector<Instruction *, 8> UsedOutside;
 688
 689   for (auto *Block : L->getBlocks())
 690     // FIXME: I believe that this could use copy_if if the Inst reference could
 691     // be adapted into a pointer.
 692     for (auto &Inst : *Block) {
 693       auto Users = Inst.users();
 694       if (std::any_of(Users.begin(), Users.end(), [&](User *U) {
 695             auto *Use = cast<Instruction>(U);
 696             return !L->contains(Use->getParent());
 697           }))
 698         UsedOutside.push_back(&Inst);
 699     }
 700
 701   return UsedOutside;
 702 }
 703
 704 /// \brief The pass class.
 705 class LoopDistribute : public FunctionPass {
 706 public:
 707   LoopDistribute() : FunctionPass(ID) {
 708     initializeLoopDistributePass(*PassRegistry::getPassRegistry());
 709   }
 710
 711   bool runOnFunction(Function &F) override {
 712     LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
 713     LAA = &getAnalysis<LoopAccessAnalysis>();
 714     DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
 715
 716     // Build up a worklist of inner-loops to vectorize. This is necessary as the
 717     // act of distributing a loop creates new loops and can invalidate iterators
 718     // across the loops.
 719     SmallVector<Loop *, 8> Worklist;
 720
 721     for (Loop *TopLevelLoop : *LI)
 722       for (Loop *L : depth_first(TopLevelLoop))
 723         // We only handle inner-most loops.
 724         if (L->empty())
 725           Worklist.push_back(L);
 726
 727     // Now walk the identified inner loops.
 728     bool Changed = false;
 729     for (Loop *L : Worklist)
 730       Changed |= processLoop(L);
 731
 732     // Process each loop nest in the function.
 733     return Changed;
 734   }
 735
 736   void getAnalysisUsage(AnalysisUsage &AU) const override {
 737     AU.addRequired<LoopInfoWrapperPass>();
 738     AU.addPreserved<LoopInfoWrapperPass>();
 739     AU.addRequired<LoopAccessAnalysis>();
 740     AU.addRequired<DominatorTreeWrapperPass>();
 741     AU.addPreserved<DominatorTreeWrapperPass>();
 742   }
 743
 744   static char ID;
 745
 746 private:
 747   /// \brief Try to distribute an inner-most loop.
 748   bool processLoop(Loop *L) {
 749     assert(L->empty() && "Only process inner loops.");
 750
 751     DEBUG(dbgs() << "\nLDist: In \"" << L->getHeader()->getParent()->getName()
 752                  << "\" checking " << *L << "\n");
 753
 754     BasicBlock *PH = L->getLoopPreheader();
 755     if (!PH) {
 756       DEBUG(dbgs() << "Skipping; no preheader");
 757       return false;
 758     }
 759     if (!L->getExitBlock()) {
 760       DEBUG(dbgs() << "Skipping; multiple exit blocks");
 761       return false;
 762     }
 763     // LAA will check that we only have a single exiting block.
 764
 765     const LoopAccessInfo &LAI = LAA->getInfo(L, ValueToValueMap());
 766
 767     // Currently, we only distribute to isolate the part of the loop with
 768     // dependence cycles to enable partial vectorization.
 769     if (LAI.canVectorizeMemory()) {
 770       DEBUG(dbgs() << "Skipping; memory operations are safe for vectorization");
 771       return false;
 772     }
 773     auto *InterestingDependences =
 774         LAI.getDepChecker().getInterestingDependences();
 775     if (!InterestingDependences || InterestingDependences->empty()) {
 776       DEBUG(dbgs() << "Skipping; No unsafe dependences to isolate");
 777       return false;
 778     }
 779
 780     InstPartitionContainer Partitions(L, LI, DT);
 781
 782     // First, go through each memory operation and assign them to consecutive
 783     // partitions (the order of partitions follows program order).  Put those
 784     // with unsafe dependences into "cyclic" partition otherwise put each store
 785     // in its own "non-cyclic" partition (we'll merge these later).
 786     //
 787     // Note that a memory operation (e.g. Load2 below) at a program point that
 788     // has an unsafe dependence (Store3->Load1) spanning over it must be
 789     // included in the same cyclic partition as the dependent operations.  This
 790     // is to preserve the original program order after distribution.  E.g.:
 791     //
 792     //                NumUnsafeDependencesStartOrEnd  NumUnsafeDependencesActive
 793     //  Load1   -.                     1                       0->1
 794     //  Load2    | /Unsafe/            0                       1
 795     //  Store3  -'                    -1                       1->0
 796     //  Load4                          0                       0
 797     //
 798     // NumUnsafeDependencesActive > 0 indicates this situation and in this case
 799     // we just keep assigning to the same cyclic partition until
 800     // NumUnsafeDependencesActive reaches 0.
 801     const MemoryDepChecker &DepChecker = LAI.getDepChecker();
 802     MemoryInstructionDependences MID(DepChecker.getMemoryInstructions(),
 803                                      *InterestingDependences);
 804
 805     int NumUnsafeDependencesActive = 0;
 806     for (auto &InstDep : MID) {
 807       Instruction *I = InstDep.Inst;
 808       // We update NumUnsafeDependencesActive post-instruction, catch the
 809       // start of a dependence directly via NumUnsafeDependencesStartOrEnd.
 810       if (NumUnsafeDependencesActive ||
 811           InstDep.NumUnsafeDependencesStartOrEnd > 0)
 812         Partitions.addToCyclicPartition(I);
 813       else
 814         Partitions.addToNewNonCyclicPartition(I);
 815       NumUnsafeDependencesActive += InstDep.NumUnsafeDependencesStartOrEnd;
 816       assert(NumUnsafeDependencesActive >= 0 &&
 817              "Negative number of dependences active");
 818     }
 819
 820     // Add partitions for values used outside.  These partitions can be out of
 821     // order from the original program order.  This is OK because if the
 822     // partition uses a load we will merge this partition with the original
 823     // partition of the load that we set up in the previous loop (see
 824     // mergeToAvoidDuplicatedLoads).
 825     auto DefsUsedOutside = findDefsUsedOutsideOfLoop(L);
 826     for (auto *Inst : DefsUsedOutside)
 827       Partitions.addToNewNonCyclicPartition(Inst);
 828
 829     DEBUG(dbgs() << "Seeded partitions:\n" << Partitions);
 830     if (Partitions.getSize() < 2)
 831       return false;
 832
 833     // Run the merge heuristics: Merge non-cyclic adjacent partitions since we
 834     // should be able to vectorize these together.
 835     Partitions.mergeBeforePopulating();
 836     DEBUG(dbgs() << "\nMerged partitions:\n" << Partitions);
 837     if (Partitions.getSize() < 2)
 838       return false;
 839
 840     // Now, populate the partitions with non-memory operations.
 841     Partitions.populateUsedSet();
 842     DEBUG(dbgs() << "\nPopulated partitions:\n" << Partitions);
 843
 844     // In order to preserve original lexical order for loads, keep them in the
 845     // partition that we set up in the MemoryInstructionDependences loop.
 846     if (Partitions.mergeToAvoidDuplicatedLoads()) {
 847       DEBUG(dbgs() << "\nPartitions merged to ensure unique loads:\n"
 848                    << Partitions);
 849       if (Partitions.getSize() < 2)
 850         return false;
 851     }
 852
 853     DEBUG(dbgs() << "\nDistributing loop: " << *L << "\n");
 854     // We're done forming the partitions set up the reverse mapping from
 855     // instructions to partitions.
 856     Partitions.setupPartitionIdOnInstructions();
 857
 858     // To keep things simple have an empty preheader before we version or clone
 859     // the loop.  (Also split if this has no predecessor, i.e. entry, because we
 860     // rely on PH having a predecessor.)
 861     if (!PH->getSinglePredecessor() || &*PH->begin() != PH->getTerminator())
 862       SplitBlock(PH, PH->getTerminator(), DT, LI);
 863
 864     // If we need run-time checks to disambiguate pointers are run-time, version
 865     // the loop now.
 866     auto PtrToPartition = Partitions.computePartitionSetForPointers(LAI);
 867     LoopVersioning LVer(LAI, L, LI, DT, &PtrToPartition);
 868     if (LVer.needsRuntimeChecks()) {
 869       DEBUG(dbgs() << "\nPointers:\n");
 870       DEBUG(LAI.getRuntimePointerCheck()->print(dbgs(), 0, &PtrToPartition));
 871       LVer.versionLoop(this);
 872       LVer.addPHINodes(DefsUsedOutside);
 873     }
 874
 875     // Create identical copies of the original loop for each partition and hook
 876     // them up sequentially.
 877     Partitions.cloneLoops(this);
 878
 879     // Now, we remove the instruction from each loop that don't belong to that
 880     // partition.
 881     Partitions.removeUnusedInsts();
 882     DEBUG(dbgs() << "\nAfter removing unused Instrs:\n");
 883     DEBUG(Partitions.printBlocks());
 884
 885     if (LDistVerify) {
 886       LI->verify();
 887       DT->verifyDomTree();
 888     }
 889
 890     ++NumLoopsDistributed;
 891     return true;
 892   }
 893
 894   // Analyses used.
 895   LoopInfo *LI;
 896   LoopAccessAnalysis *LAA;
 897   DominatorTree *DT;
 898 };
 899 } // anonymous namespace
 900
 901 char LoopDistribute::ID;
 902 static const char ldist_name[] = "Loop Distribition";
 903
 904 INITIALIZE_PASS_BEGIN(LoopDistribute, LDIST_NAME, ldist_name, false, false)
 905 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
 906 INITIALIZE_PASS_DEPENDENCY(LoopAccessAnalysis)
 907 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 908 INITIALIZE_PASS_END(LoopDistribute, LDIST_NAME, ldist_name, false, false)
 909
 910 namespace llvm {
 911 FunctionPass *createLoopDistributePass() { return new LoopDistribute(); }
 912 }