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