1 //===- LoopDistribute.cpp - Loop Distribution Pass ------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
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.
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
20 // Similarly to the Vectorizer, the pass also supports loop versioning to
21 // run-time disambiguate potentially overlapping arrays.
23 //===----------------------------------------------------------------------===//
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"
40 #define LDIST_NAME "loop-distribute"
41 #define DEBUG_TYPE LDIST_NAME
46 LDistVerify("loop-distribute-verify", cl::Hidden,
47 cl::desc("Turn on DominatorTree and LoopInfo verification "
48 "after Loop Distribution"),
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"),
57 STATISTIC(NumLoopsDistributed, "Number of loops distributed");
60 /// \brief Maintains the set of instructions of the loop for a partition before
61 /// cloning. After cloning, it hosts the new loop.
63 typedef SmallPtrSet<Instruction *, 8> InstructionSet;
66 InstPartition(Instruction *I, Loop *L, bool DepCycle = false)
67 : DepCycle(DepCycle), OrigLoop(L), ClonedLoop(nullptr) {
71 /// \brief Returns whether this partition contains a dependence cycle.
72 bool hasDepCycle() const { return DepCycle; }
74 /// \brief Adds an instruction to this partition.
75 void add(Instruction *I) { Set.insert(I); }
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(); }
84 /// \brief Moves this partition into \p Other. This partition becomes empty
86 void moveTo(InstPartition &Other) {
87 Other.Set.insert(Set.begin(), Set.end());
89 Other.DepCycle |= DepCycle;
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
98 for (auto *B : OrigLoop->getBlocks())
99 Set.insert(B->getTerminator());
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);
115 /// \brief Clones the original loop.
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,
122 ClonedLoop = ::cloneLoopWithPreheader(InsertBefore, LoopDomBB, OrigLoop,
123 VMap, Twine(".ldist") + Twine(Index),
124 LI, DT, ClonedLoopBlocks);
128 /// \brief The cloned loop. If this partition is mapped to the original loop,
130 const Loop *getClonedLoop() const { return ClonedLoop; }
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
135 const Loop *getDistributedLoop() const {
136 return ClonedLoop ? ClonedLoop : OrigLoop;
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; }
143 /// \brief Remaps the cloned instructions using VMap.
144 void remapInstructions() {
145 remapInstructionsInBlocks(ClonedLoopBlocks, VMap);
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;
153 for (auto *Block : OrigLoop->getBlocks())
154 for (auto &Inst : *Block)
155 if (!Set.count(&Inst)) {
156 Instruction *NewInst = &Inst;
158 NewInst = cast<Instruction>(VMap[NewInst]);
160 assert(!isa<BranchInst>(NewInst) &&
161 "Branches are marked used early on");
162 Unused.push_back(NewInst);
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();
176 dbgs() << " (cycle)\n";
178 // Prefix with the block name.
179 dbgs() << " " << I->getParent()->getName() << ":" << *I << "\n";
182 void printBlocks() const {
183 for (auto *BB : getDistributedLoop()->getBlocks())
188 /// \brief Instructions from OrigLoop selected for this partition.
191 /// \brief Whether this partition contains a dependence cycle.
194 /// \brief The original loop.
197 /// \brief The cloned loop. If this partition is mapped to the original loop,
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;
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
208 ValueToValueMapTy VMap;
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;
217 InstPartitionContainer(Loop *L, LoopInfo *LI, DominatorTree *DT)
218 : L(L), LI(LI), DT(DT) {}
220 /// \brief Returns the number of partitions.
221 unsigned getSize() const { return PartitionContainer.size(); }
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);
230 PartitionContainer.back().add(Inst);
233 /// \brief Adds \p Inst into a partition that is not marked to contain
234 /// dependence cycles.
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);
242 /// \brief Merges adjacent non-cyclic partitions.
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
247 void mergeAdjacentNonCyclic() {
248 mergeAdjacentPartitionsIf(
249 [](const InstPartition *P) { return !P->hasDepCycle(); });
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())
259 // Now, check if all stores are conditional in this partition.
260 bool seenStore = false;
262 for (auto *Inst : *Partition)
263 if (isa<StoreInst>(Inst)) {
265 if (!LoopAccessInfo::blockNeedsPredication(Inst->getParent(), L, DT))
272 /// \brief Merges the partitions according to various heuristics.
273 void mergeBeforePopulating() {
274 mergeAdjacentNonCyclic();
275 if (!DistributeNonIfConvertible)
276 mergeNonIfConvertible();
279 /// \brief Merges partitions in order to ensure that no loads are duplicated.
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.
285 /// Return if any partitions were merged.
286 bool mergeToAvoidDuplicatedLoads() {
287 typedef DenseMap<Instruction *, InstPartition *> LoadToPartitionT;
288 typedef EquivalenceClasses<InstPartition *> ToBeMergedT;
290 LoadToPartitionT LoadToPartition;
291 ToBeMergedT ToBeMerged;
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();
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)) {
306 LoadToPartitionT::iterator LoadToPart;
308 std::tie(LoadToPart, NewElt) =
309 LoadToPartition.insert(std::make_pair(Inst, PartI));
311 DEBUG(dbgs() << "Merging partitions due to this load in multiple "
312 << "partitions: " << PartI << ", "
313 << LoadToPart->second << "\n" << *Inst << "\n");
318 ToBeMerged.unionSets(PartI, &*PartJ);
319 } while (&*PartJ != LoadToPart->second);
323 if (ToBeMerged.empty())
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();
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);
340 // Remove the empty partitions.
341 PartitionContainer.remove_if(
342 [](const InstPartition &P) { return P.empty(); });
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() {
351 for (const auto &Partition : PartitionContainer) {
352 for (Instruction *Inst : Partition) {
354 InstToPartitionIdT::iterator Iter;
356 std::tie(Iter, NewElt) =
357 InstToPartitionId.insert(std::make_pair(Inst, PartitionID));
365 /// \brief Populates the partition with everything that the seeding
366 /// instructions require.
367 void populateUsedSet() {
368 for (auto &P : PartitionContainer)
372 /// \brief This performs the main chunk of the work of cloning the loops for
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");
384 assert(!PartitionContainer.empty() && "at least two partitions expected");
385 // We're cloning the preheader along with the loop so we already made sure
387 assert(&*OrigPH->begin() == OrigPH->getTerminator() &&
388 "preheader not empty");
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()) {
400 NewLoop = Part->cloneLoopWithPreheader(TopPH, Pred, Index, LI, DT);
402 Part->getVMap()[ExitBlock] = TopPH;
403 Part->remapInstructions();
405 Pred->getTerminator()->replaceUsesOfWith(OrigPH, TopPH);
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());
419 /// \brief Removes the dead instructions from the cloned loops.
420 void removeUnusedInsts() {
421 for (auto &Partition : PartitionContainer)
422 Partition.removeUnusedInsts();
425 /// \brief For each memory pointer, it computes the partitionId the pointer is
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.
432 computePartitionSetForPointers(const LoopAccessInfo &LAI) {
433 const RuntimePointerChecking *RtPtrCheck = LAI.getRuntimePointerChecking();
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;
440 LAI.getInstructionsForAccess(Ptr, RtPtrCheck->Pointers[I].IsWritePtr);
442 int &Partition = PtrToPartitions[I];
443 // First set it to uninitialized.
445 for (Instruction *Inst : Instructions) {
446 // Note that this could be -1 if Inst is duplicated across multiple
448 int ThisPartition = this->InstToPartitionId[Inst];
450 Partition = ThisPartition;
451 // -1 means belonging to multiple partitions.
452 else if (Partition == -1)
454 else if (Partition != (int)ThisPartition)
457 assert(Partition != -2 && "Pointer not belonging to any partition");
460 return PtrToPartitions;
463 void print(raw_ostream &OS) const {
465 for (const auto &P : PartitionContainer) {
466 OS << "Partition " << Index++ << " (" << &P << "):\n";
471 void dump() const { print(dbgs()); }
474 friend raw_ostream &operator<<(raw_ostream &OS,
475 const InstPartitionContainer &Partitions) {
476 Partitions.print(OS);
481 void printBlocks() const {
483 for (const auto &P : PartitionContainer) {
484 dbgs() << "\nPartition " << Index++ << " (" << &P << "):\n";
490 typedef std::list<InstPartition> PartitionContainerT;
492 /// \brief List of partitions.
493 PartitionContainerT PartitionContainer;
495 /// \brief Mapping from Instruction to partition Id. If the instruction
496 /// belongs to multiple partitions the entry contains -1.
497 InstToPartitionIdT InstToPartitionId;
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) {
513 } else if (PrevMatch != nullptr && DoesMatch) {
514 I->moveTo(*PrevMatch);
515 I = PartitionContainer.erase(I);
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.
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;
536 unsigned NumUnsafeDependencesStartOrEnd;
538 Entry(Instruction *Inst) : Inst(Inst), NumUnsafeDependencesStartOrEnd(0) {}
541 typedef SmallVector<Entry, 8> AccessesType;
543 AccessesType::const_iterator begin() const { return Accesses.begin(); }
544 AccessesType::const_iterator end() const { return Accesses.end(); }
546 MemoryInstructionDependences(
547 const SmallVectorImpl<Instruction *> &Instructions,
548 const SmallVectorImpl<Dependence> &InterestingDependences) {
549 Accesses.append(Instructions.begin(), Instructions.end());
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
557 ++Accesses[Dep.Source].NumUnsafeDependencesStartOrEnd;
558 --Accesses[Dep.Destination].NumUnsafeDependencesStartOrEnd;
560 DEBUG(Dep.print(dbgs(), 2, Instructions));
565 AccessesType Accesses;
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;
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());
581 UsedOutside.push_back(&Inst);
587 /// \brief The pass class.
588 class LoopDistribute : public FunctionPass {
590 LoopDistribute() : FunctionPass(ID) {
591 initializeLoopDistributePass(*PassRegistry::getPassRegistry());
594 bool runOnFunction(Function &F) override {
595 LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
596 LAA = &getAnalysis<LoopAccessAnalysis>();
597 DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
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
602 SmallVector<Loop *, 8> Worklist;
604 for (Loop *TopLevelLoop : *LI)
605 for (Loop *L : depth_first(TopLevelLoop))
606 // We only handle inner-most loops.
608 Worklist.push_back(L);
610 // Now walk the identified inner loops.
611 bool Changed = false;
612 for (Loop *L : Worklist)
613 Changed |= processLoop(L);
615 // Process each loop nest in the function.
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>();
630 /// \brief Filter out checks between pointers from the same partition.
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;
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.
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
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))
669 /// \brief Try to distribute an inner-most loop.
670 bool processLoop(Loop *L) {
671 assert(L->empty() && "Only process inner loops.");
673 DEBUG(dbgs() << "\nLDist: In \"" << L->getHeader()->getParent()->getName()
674 << "\" checking " << *L << "\n");
676 BasicBlock *PH = L->getLoopPreheader();
678 DEBUG(dbgs() << "Skipping; no preheader");
681 if (!L->getExitBlock()) {
682 DEBUG(dbgs() << "Skipping; multiple exit blocks");
685 // LAA will check that we only have a single exiting block.
687 const LoopAccessInfo &LAI = LAA->getInfo(L, ValueToValueMap());
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");
695 auto *InterestingDependences =
696 LAI.getDepChecker().getInterestingDependences();
697 if (!InterestingDependences || InterestingDependences->empty()) {
698 DEBUG(dbgs() << "Skipping; No unsafe dependences to isolate");
702 InstPartitionContainer Partitions(L, LI, DT);
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).
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.:
714 // NumUnsafeDependencesStartOrEnd NumUnsafeDependencesActive
716 // Load2 | /Unsafe/ 0 1
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);
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);
736 Partitions.addToNewNonCyclicPartition(I);
737 NumUnsafeDependencesActive += InstDep.NumUnsafeDependencesStartOrEnd;
738 assert(NumUnsafeDependencesActive >= 0 &&
739 "Negative number of dependences active");
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);
751 DEBUG(dbgs() << "Seeded partitions:\n" << Partitions);
752 if (Partitions.getSize() < 2)
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)
762 // Now, populate the partitions with non-memory operations.
763 Partitions.populateUsedSet();
764 DEBUG(dbgs() << "\nPopulated partitions:\n" << Partitions);
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"
771 if (Partitions.getSize() < 2)
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();
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);
786 // If we need run-time checks to disambiguate pointers are run-time, version
788 auto PtrToPartition = Partitions.computePartitionSetForPointers(LAI);
789 const auto *RtPtrChecking = LAI.getRuntimePointerChecking();
790 auto AllChecks = RtPtrChecking->generateChecks();
791 auto Checks = includeOnlyCrossPartitionChecks(AllChecks, PtrToPartition,
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);
801 // Create identical copies of the original loop for each partition and hook
802 // them up sequentially.
803 Partitions.cloneLoops(this);
805 // Now, we remove the instruction from each loop that don't belong to that
807 Partitions.removeUnusedInsts();
808 DEBUG(dbgs() << "\nAfter removing unused Instrs:\n");
809 DEBUG(Partitions.printBlocks());
816 ++NumLoopsDistributed;
822 LoopAccessAnalysis *LAA;
825 } // anonymous namespace
827 char LoopDistribute::ID;
828 static const char ldist_name[] = "Loop Distribition";
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)
837 FunctionPass *createLoopDistributePass() { return new LoopDistribute(); }