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/Transforms/Scalar/LoopDistribute.h"
26 #include "llvm/ADT/DepthFirstIterator.h"
27 #include "llvm/ADT/EquivalenceClasses.h"
28 #include "llvm/ADT/STLExtras.h"
29 #include "llvm/ADT/Statistic.h"
30 #include "llvm/Analysis/BlockFrequencyInfo.h"
31 #include "llvm/Analysis/LoopAccessAnalysis.h"
32 #include "llvm/Analysis/LoopInfo.h"
33 #include "llvm/Analysis/LoopPassManager.h"
34 #include "llvm/Analysis/OptimizationDiagnosticInfo.h"
35 #include "llvm/IR/DiagnosticInfo.h"
36 #include "llvm/IR/Dominators.h"
37 #include "llvm/Pass.h"
38 #include "llvm/Support/CommandLine.h"
39 #include "llvm/Support/Debug.h"
40 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
41 #include "llvm/Transforms/Utils/Cloning.h"
42 #include "llvm/Transforms/Utils/LoopUtils.h"
43 #include "llvm/Transforms/Utils/LoopVersioning.h"
46 #define LDIST_NAME "loop-distribute"
47 #define DEBUG_TYPE LDIST_NAME
52 LDistVerify("loop-distribute-verify", cl::Hidden,
53 cl::desc("Turn on DominatorTree and LoopInfo verification "
54 "after Loop Distribution"),
57 static cl::opt<bool> DistributeNonIfConvertible(
58 "loop-distribute-non-if-convertible", cl::Hidden,
59 cl::desc("Whether to distribute into a loop that may not be "
60 "if-convertible by the loop vectorizer"),
63 static cl::opt<unsigned> DistributeSCEVCheckThreshold(
64 "loop-distribute-scev-check-threshold", cl::init(8), cl::Hidden,
65 cl::desc("The maximum number of SCEV checks allowed for Loop "
68 static cl::opt<unsigned> PragmaDistributeSCEVCheckThreshold(
69 "loop-distribute-scev-check-threshold-with-pragma", cl::init(128),
72 "The maximum number of SCEV checks allowed for Loop "
73 "Distribution for loop marked with #pragma loop distribute(enable)"));
75 // Note that the initial value for this depends on whether the pass is invoked
76 // directly or from the optimization pipeline.
77 static cl::opt<bool> EnableLoopDistribute(
78 "enable-loop-distribute", cl::Hidden,
79 cl::desc("Enable the new, experimental LoopDistribution Pass"));
81 STATISTIC(NumLoopsDistributed, "Number of loops distributed");
84 /// \brief Maintains the set of instructions of the loop for a partition before
85 /// cloning. After cloning, it hosts the new loop.
87 typedef SmallPtrSet<Instruction *, 8> InstructionSet;
90 InstPartition(Instruction *I, Loop *L, bool DepCycle = false)
91 : DepCycle(DepCycle), OrigLoop(L), ClonedLoop(nullptr) {
95 /// \brief Returns whether this partition contains a dependence cycle.
96 bool hasDepCycle() const { return DepCycle; }
98 /// \brief Adds an instruction to this partition.
99 void add(Instruction *I) { Set.insert(I); }
101 /// \brief Collection accessors.
102 InstructionSet::iterator begin() { return Set.begin(); }
103 InstructionSet::iterator end() { return Set.end(); }
104 InstructionSet::const_iterator begin() const { return Set.begin(); }
105 InstructionSet::const_iterator end() const { return Set.end(); }
106 bool empty() const { return Set.empty(); }
108 /// \brief Moves this partition into \p Other. This partition becomes empty
110 void moveTo(InstPartition &Other) {
111 Other.Set.insert(Set.begin(), Set.end());
113 Other.DepCycle |= DepCycle;
116 /// \brief Populates the partition with a transitive closure of all the
117 /// instructions that the seeded instructions dependent on.
118 void populateUsedSet() {
119 // FIXME: We currently don't use control-dependence but simply include all
120 // blocks (possibly empty at the end) and let simplifycfg mostly clean this
122 for (auto *B : OrigLoop->getBlocks())
123 Set.insert(B->getTerminator());
125 // Follow the use-def chains to form a transitive closure of all the
126 // instructions that the originally seeded instructions depend on.
127 SmallVector<Instruction *, 8> Worklist(Set.begin(), Set.end());
128 while (!Worklist.empty()) {
129 Instruction *I = Worklist.pop_back_val();
130 // Insert instructions from the loop that we depend on.
131 for (Value *V : I->operand_values()) {
132 auto *I = dyn_cast<Instruction>(V);
133 if (I && OrigLoop->contains(I->getParent()) && Set.insert(I).second)
134 Worklist.push_back(I);
139 /// \brief Clones the original loop.
141 /// Updates LoopInfo and DominatorTree using the information that block \p
142 /// LoopDomBB dominates the loop.
143 Loop *cloneLoopWithPreheader(BasicBlock *InsertBefore, BasicBlock *LoopDomBB,
144 unsigned Index, LoopInfo *LI,
146 ClonedLoop = ::cloneLoopWithPreheader(InsertBefore, LoopDomBB, OrigLoop,
147 VMap, Twine(".ldist") + Twine(Index),
148 LI, DT, ClonedLoopBlocks);
152 /// \brief The cloned loop. If this partition is mapped to the original loop,
154 const Loop *getClonedLoop() const { return ClonedLoop; }
156 /// \brief Returns the loop where this partition ends up after distribution.
157 /// If this partition is mapped to the original loop then use the block from
159 const Loop *getDistributedLoop() const {
160 return ClonedLoop ? ClonedLoop : OrigLoop;
163 /// \brief The VMap that is populated by cloning and then used in
164 /// remapinstruction to remap the cloned instructions.
165 ValueToValueMapTy &getVMap() { return VMap; }
167 /// \brief Remaps the cloned instructions using VMap.
168 void remapInstructions() {
169 remapInstructionsInBlocks(ClonedLoopBlocks, VMap);
172 /// \brief Based on the set of instructions selected for this partition,
173 /// removes the unnecessary ones.
174 void removeUnusedInsts() {
175 SmallVector<Instruction *, 8> Unused;
177 for (auto *Block : OrigLoop->getBlocks())
178 for (auto &Inst : *Block)
179 if (!Set.count(&Inst)) {
180 Instruction *NewInst = &Inst;
182 NewInst = cast<Instruction>(VMap[NewInst]);
184 assert(!isa<BranchInst>(NewInst) &&
185 "Branches are marked used early on");
186 Unused.push_back(NewInst);
189 // Delete the instructions backwards, as it has a reduced likelihood of
190 // having to update as many def-use and use-def chains.
191 for (auto *Inst : reverse(Unused)) {
192 if (!Inst->use_empty())
193 Inst->replaceAllUsesWith(UndefValue::get(Inst->getType()));
194 Inst->eraseFromParent();
200 dbgs() << " (cycle)\n";
202 // Prefix with the block name.
203 dbgs() << " " << I->getParent()->getName() << ":" << *I << "\n";
206 void printBlocks() const {
207 for (auto *BB : getDistributedLoop()->getBlocks())
212 /// \brief Instructions from OrigLoop selected for this partition.
215 /// \brief Whether this partition contains a dependence cycle.
218 /// \brief The original loop.
221 /// \brief The cloned loop. If this partition is mapped to the original loop,
225 /// \brief The blocks of ClonedLoop including the preheader. If this
226 /// partition is mapped to the original loop, this is empty.
227 SmallVector<BasicBlock *, 8> ClonedLoopBlocks;
229 /// \brief These gets populated once the set of instructions have been
230 /// finalized. If this partition is mapped to the original loop, these are not
232 ValueToValueMapTy VMap;
235 /// \brief Holds the set of Partitions. It populates them, merges them and then
236 /// clones the loops.
237 class InstPartitionContainer {
238 typedef DenseMap<Instruction *, int> InstToPartitionIdT;
241 InstPartitionContainer(Loop *L, LoopInfo *LI, DominatorTree *DT)
242 : L(L), LI(LI), DT(DT) {}
244 /// \brief Returns the number of partitions.
245 unsigned getSize() const { return PartitionContainer.size(); }
247 /// \brief Adds \p Inst into the current partition if that is marked to
248 /// contain cycles. Otherwise start a new partition for it.
249 void addToCyclicPartition(Instruction *Inst) {
250 // If the current partition is non-cyclic. Start a new one.
251 if (PartitionContainer.empty() || !PartitionContainer.back().hasDepCycle())
252 PartitionContainer.emplace_back(Inst, L, /*DepCycle=*/true);
254 PartitionContainer.back().add(Inst);
257 /// \brief Adds \p Inst into a partition that is not marked to contain
258 /// dependence cycles.
260 // Initially we isolate memory instructions into as many partitions as
261 // possible, then later we may merge them back together.
262 void addToNewNonCyclicPartition(Instruction *Inst) {
263 PartitionContainer.emplace_back(Inst, L);
266 /// \brief Merges adjacent non-cyclic partitions.
268 /// The idea is that we currently only want to isolate the non-vectorizable
269 /// partition. We could later allow more distribution among these partition
271 void mergeAdjacentNonCyclic() {
272 mergeAdjacentPartitionsIf(
273 [](const InstPartition *P) { return !P->hasDepCycle(); });
276 /// \brief If a partition contains only conditional stores, we won't vectorize
277 /// it. Try to merge it with a previous cyclic partition.
278 void mergeNonIfConvertible() {
279 mergeAdjacentPartitionsIf([&](const InstPartition *Partition) {
280 if (Partition->hasDepCycle())
283 // Now, check if all stores are conditional in this partition.
284 bool seenStore = false;
286 for (auto *Inst : *Partition)
287 if (isa<StoreInst>(Inst)) {
289 if (!LoopAccessInfo::blockNeedsPredication(Inst->getParent(), L, DT))
296 /// \brief Merges the partitions according to various heuristics.
297 void mergeBeforePopulating() {
298 mergeAdjacentNonCyclic();
299 if (!DistributeNonIfConvertible)
300 mergeNonIfConvertible();
303 /// \brief Merges partitions in order to ensure that no loads are duplicated.
305 /// We can't duplicate loads because that could potentially reorder them.
306 /// LoopAccessAnalysis provides dependency information with the context that
307 /// the order of memory operation is preserved.
309 /// Return if any partitions were merged.
310 bool mergeToAvoidDuplicatedLoads() {
311 typedef DenseMap<Instruction *, InstPartition *> LoadToPartitionT;
312 typedef EquivalenceClasses<InstPartition *> ToBeMergedT;
314 LoadToPartitionT LoadToPartition;
315 ToBeMergedT ToBeMerged;
317 // Step through the partitions and create equivalence between partitions
318 // that contain the same load. Also put partitions in between them in the
319 // same equivalence class to avoid reordering of memory operations.
320 for (PartitionContainerT::iterator I = PartitionContainer.begin(),
321 E = PartitionContainer.end();
325 // If a load occurs in two partitions PartI and PartJ, merge all
326 // partitions (PartI, PartJ] into PartI.
327 for (Instruction *Inst : *PartI)
328 if (isa<LoadInst>(Inst)) {
330 LoadToPartitionT::iterator LoadToPart;
332 std::tie(LoadToPart, NewElt) =
333 LoadToPartition.insert(std::make_pair(Inst, PartI));
335 DEBUG(dbgs() << "Merging partitions due to this load in multiple "
336 << "partitions: " << PartI << ", "
337 << LoadToPart->second << "\n" << *Inst << "\n");
342 ToBeMerged.unionSets(PartI, &*PartJ);
343 } while (&*PartJ != LoadToPart->second);
347 if (ToBeMerged.empty())
350 // Merge the member of an equivalence class into its class leader. This
351 // makes the members empty.
352 for (ToBeMergedT::iterator I = ToBeMerged.begin(), E = ToBeMerged.end();
357 auto PartI = I->getData();
358 for (auto PartJ : make_range(std::next(ToBeMerged.member_begin(I)),
359 ToBeMerged.member_end())) {
360 PartJ->moveTo(*PartI);
364 // Remove the empty partitions.
365 PartitionContainer.remove_if(
366 [](const InstPartition &P) { return P.empty(); });
371 /// \brief Sets up the mapping between instructions to partitions. If the
372 /// instruction is duplicated across multiple partitions, set the entry to -1.
373 void setupPartitionIdOnInstructions() {
375 for (const auto &Partition : PartitionContainer) {
376 for (Instruction *Inst : Partition) {
378 InstToPartitionIdT::iterator Iter;
380 std::tie(Iter, NewElt) =
381 InstToPartitionId.insert(std::make_pair(Inst, PartitionID));
389 /// \brief Populates the partition with everything that the seeding
390 /// instructions require.
391 void populateUsedSet() {
392 for (auto &P : PartitionContainer)
396 /// \brief This performs the main chunk of the work of cloning the loops for
399 BasicBlock *OrigPH = L->getLoopPreheader();
400 // At this point the predecessor of the preheader is either the memcheck
401 // block or the top part of the original preheader.
402 BasicBlock *Pred = OrigPH->getSinglePredecessor();
403 assert(Pred && "Preheader does not have a single predecessor");
404 BasicBlock *ExitBlock = L->getExitBlock();
405 assert(ExitBlock && "No single exit block");
408 assert(!PartitionContainer.empty() && "at least two partitions expected");
409 // We're cloning the preheader along with the loop so we already made sure
411 assert(&*OrigPH->begin() == OrigPH->getTerminator() &&
412 "preheader not empty");
414 // Create a loop for each partition except the last. Clone the original
415 // loop before PH along with adding a preheader for the cloned loop. Then
416 // update PH to point to the newly added preheader.
417 BasicBlock *TopPH = OrigPH;
418 unsigned Index = getSize() - 1;
419 for (auto I = std::next(PartitionContainer.rbegin()),
420 E = PartitionContainer.rend();
421 I != E; ++I, --Index, TopPH = NewLoop->getLoopPreheader()) {
424 NewLoop = Part->cloneLoopWithPreheader(TopPH, Pred, Index, LI, DT);
426 Part->getVMap()[ExitBlock] = TopPH;
427 Part->remapInstructions();
429 Pred->getTerminator()->replaceUsesOfWith(OrigPH, TopPH);
431 // Now go in forward order and update the immediate dominator for the
432 // preheaders with the exiting block of the previous loop. Dominance
433 // within the loop is updated in cloneLoopWithPreheader.
434 for (auto Curr = PartitionContainer.cbegin(),
435 Next = std::next(PartitionContainer.cbegin()),
436 E = PartitionContainer.cend();
437 Next != E; ++Curr, ++Next)
438 DT->changeImmediateDominator(
439 Next->getDistributedLoop()->getLoopPreheader(),
440 Curr->getDistributedLoop()->getExitingBlock());
443 /// \brief Removes the dead instructions from the cloned loops.
444 void removeUnusedInsts() {
445 for (auto &Partition : PartitionContainer)
446 Partition.removeUnusedInsts();
449 /// \brief For each memory pointer, it computes the partitionId the pointer is
452 /// This returns an array of int where the I-th entry corresponds to I-th
453 /// entry in LAI.getRuntimePointerCheck(). If the pointer is used in multiple
454 /// partitions its entry is set to -1.
456 computePartitionSetForPointers(const LoopAccessInfo &LAI) {
457 const RuntimePointerChecking *RtPtrCheck = LAI.getRuntimePointerChecking();
459 unsigned N = RtPtrCheck->Pointers.size();
460 SmallVector<int, 8> PtrToPartitions(N);
461 for (unsigned I = 0; I < N; ++I) {
462 Value *Ptr = RtPtrCheck->Pointers[I].PointerValue;
464 LAI.getInstructionsForAccess(Ptr, RtPtrCheck->Pointers[I].IsWritePtr);
466 int &Partition = PtrToPartitions[I];
467 // First set it to uninitialized.
469 for (Instruction *Inst : Instructions) {
470 // Note that this could be -1 if Inst is duplicated across multiple
472 int ThisPartition = this->InstToPartitionId[Inst];
474 Partition = ThisPartition;
475 // -1 means belonging to multiple partitions.
476 else if (Partition == -1)
478 else if (Partition != (int)ThisPartition)
481 assert(Partition != -2 && "Pointer not belonging to any partition");
484 return PtrToPartitions;
487 void print(raw_ostream &OS) const {
489 for (const auto &P : PartitionContainer) {
490 OS << "Partition " << Index++ << " (" << &P << "):\n";
495 void dump() const { print(dbgs()); }
498 friend raw_ostream &operator<<(raw_ostream &OS,
499 const InstPartitionContainer &Partitions) {
500 Partitions.print(OS);
505 void printBlocks() const {
507 for (const auto &P : PartitionContainer) {
508 dbgs() << "\nPartition " << Index++ << " (" << &P << "):\n";
514 typedef std::list<InstPartition> PartitionContainerT;
516 /// \brief List of partitions.
517 PartitionContainerT PartitionContainer;
519 /// \brief Mapping from Instruction to partition Id. If the instruction
520 /// belongs to multiple partitions the entry contains -1.
521 InstToPartitionIdT InstToPartitionId;
527 /// \brief The control structure to merge adjacent partitions if both satisfy
528 /// the \p Predicate.
529 template <class UnaryPredicate>
530 void mergeAdjacentPartitionsIf(UnaryPredicate Predicate) {
531 InstPartition *PrevMatch = nullptr;
532 for (auto I = PartitionContainer.begin(); I != PartitionContainer.end();) {
533 auto DoesMatch = Predicate(&*I);
534 if (PrevMatch == nullptr && DoesMatch) {
537 } else if (PrevMatch != nullptr && DoesMatch) {
538 I->moveTo(*PrevMatch);
539 I = PartitionContainer.erase(I);
548 /// \brief For each memory instruction, this class maintains difference of the
549 /// number of unsafe dependences that start out from this instruction minus
550 /// those that end here.
552 /// By traversing the memory instructions in program order and accumulating this
553 /// number, we know whether any unsafe dependence crosses over a program point.
554 class MemoryInstructionDependences {
555 typedef MemoryDepChecker::Dependence Dependence;
560 unsigned NumUnsafeDependencesStartOrEnd;
562 Entry(Instruction *Inst) : Inst(Inst), NumUnsafeDependencesStartOrEnd(0) {}
565 typedef SmallVector<Entry, 8> AccessesType;
567 AccessesType::const_iterator begin() const { return Accesses.begin(); }
568 AccessesType::const_iterator end() const { return Accesses.end(); }
570 MemoryInstructionDependences(
571 const SmallVectorImpl<Instruction *> &Instructions,
572 const SmallVectorImpl<Dependence> &Dependences) {
573 Accesses.append(Instructions.begin(), Instructions.end());
575 DEBUG(dbgs() << "Backward dependences:\n");
576 for (auto &Dep : Dependences)
577 if (Dep.isPossiblyBackward()) {
578 // Note that the designations source and destination follow the program
579 // order, i.e. source is always first. (The direction is given by the
581 ++Accesses[Dep.Source].NumUnsafeDependencesStartOrEnd;
582 --Accesses[Dep.Destination].NumUnsafeDependencesStartOrEnd;
584 DEBUG(Dep.print(dbgs(), 2, Instructions));
589 AccessesType Accesses;
592 /// \brief The actual class performing the per-loop work.
593 class LoopDistributeForLoop {
595 LoopDistributeForLoop(Loop *L, Function *F, LoopInfo *LI, DominatorTree *DT,
596 ScalarEvolution *SE, OptimizationRemarkEmitter *ORE)
597 : L(L), F(F), LI(LI), LAI(nullptr), DT(DT), SE(SE), ORE(ORE) {
601 /// \brief Try to distribute an inner-most loop.
602 bool processLoop(std::function<const LoopAccessInfo &(Loop &)> &GetLAA) {
603 assert(L->empty() && "Only process inner loops.");
605 DEBUG(dbgs() << "\nLDist: In \"" << L->getHeader()->getParent()->getName()
606 << "\" checking " << *L << "\n");
608 BasicBlock *PH = L->getLoopPreheader();
610 return fail("no preheader");
611 if (!L->getExitBlock())
612 return fail("multiple exit blocks");
614 // LAA will check that we only have a single exiting block.
617 // Currently, we only distribute to isolate the part of the loop with
618 // dependence cycles to enable partial vectorization.
619 if (LAI->canVectorizeMemory())
620 return fail("memory operations are safe for vectorization");
622 auto *Dependences = LAI->getDepChecker().getDependences();
623 if (!Dependences || Dependences->empty())
624 return fail("no unsafe dependences to isolate");
626 InstPartitionContainer Partitions(L, LI, DT);
628 // First, go through each memory operation and assign them to consecutive
629 // partitions (the order of partitions follows program order). Put those
630 // with unsafe dependences into "cyclic" partition otherwise put each store
631 // in its own "non-cyclic" partition (we'll merge these later).
633 // Note that a memory operation (e.g. Load2 below) at a program point that
634 // has an unsafe dependence (Store3->Load1) spanning over it must be
635 // included in the same cyclic partition as the dependent operations. This
636 // is to preserve the original program order after distribution. E.g.:
638 // NumUnsafeDependencesStartOrEnd NumUnsafeDependencesActive
640 // Load2 | /Unsafe/ 0 1
644 // NumUnsafeDependencesActive > 0 indicates this situation and in this case
645 // we just keep assigning to the same cyclic partition until
646 // NumUnsafeDependencesActive reaches 0.
647 const MemoryDepChecker &DepChecker = LAI->getDepChecker();
648 MemoryInstructionDependences MID(DepChecker.getMemoryInstructions(),
651 int NumUnsafeDependencesActive = 0;
652 for (auto &InstDep : MID) {
653 Instruction *I = InstDep.Inst;
654 // We update NumUnsafeDependencesActive post-instruction, catch the
655 // start of a dependence directly via NumUnsafeDependencesStartOrEnd.
656 if (NumUnsafeDependencesActive ||
657 InstDep.NumUnsafeDependencesStartOrEnd > 0)
658 Partitions.addToCyclicPartition(I);
660 Partitions.addToNewNonCyclicPartition(I);
661 NumUnsafeDependencesActive += InstDep.NumUnsafeDependencesStartOrEnd;
662 assert(NumUnsafeDependencesActive >= 0 &&
663 "Negative number of dependences active");
666 // Add partitions for values used outside. These partitions can be out of
667 // order from the original program order. This is OK because if the
668 // partition uses a load we will merge this partition with the original
669 // partition of the load that we set up in the previous loop (see
670 // mergeToAvoidDuplicatedLoads).
671 auto DefsUsedOutside = findDefsUsedOutsideOfLoop(L);
672 for (auto *Inst : DefsUsedOutside)
673 Partitions.addToNewNonCyclicPartition(Inst);
675 DEBUG(dbgs() << "Seeded partitions:\n" << Partitions);
676 if (Partitions.getSize() < 2)
677 return fail("cannot isolate unsafe dependencies");
679 // Run the merge heuristics: Merge non-cyclic adjacent partitions since we
680 // should be able to vectorize these together.
681 Partitions.mergeBeforePopulating();
682 DEBUG(dbgs() << "\nMerged partitions:\n" << Partitions);
683 if (Partitions.getSize() < 2)
684 return fail("cannot isolate unsafe dependencies");
686 // Now, populate the partitions with non-memory operations.
687 Partitions.populateUsedSet();
688 DEBUG(dbgs() << "\nPopulated partitions:\n" << Partitions);
690 // In order to preserve original lexical order for loads, keep them in the
691 // partition that we set up in the MemoryInstructionDependences loop.
692 if (Partitions.mergeToAvoidDuplicatedLoads()) {
693 DEBUG(dbgs() << "\nPartitions merged to ensure unique loads:\n"
695 if (Partitions.getSize() < 2)
696 return fail("cannot isolate unsafe dependencies");
699 // Don't distribute the loop if we need too many SCEV run-time checks.
700 const SCEVUnionPredicate &Pred = LAI->getPSE().getUnionPredicate();
701 if (Pred.getComplexity() > (IsForced.getValueOr(false)
702 ? PragmaDistributeSCEVCheckThreshold
703 : DistributeSCEVCheckThreshold))
704 return fail("too many SCEV run-time checks needed.\n");
706 DEBUG(dbgs() << "\nDistributing loop: " << *L << "\n");
707 // We're done forming the partitions set up the reverse mapping from
708 // instructions to partitions.
709 Partitions.setupPartitionIdOnInstructions();
711 // To keep things simple have an empty preheader before we version or clone
712 // the loop. (Also split if this has no predecessor, i.e. entry, because we
713 // rely on PH having a predecessor.)
714 if (!PH->getSinglePredecessor() || &*PH->begin() != PH->getTerminator())
715 SplitBlock(PH, PH->getTerminator(), DT, LI);
717 // If we need run-time checks, version the loop now.
718 auto PtrToPartition = Partitions.computePartitionSetForPointers(*LAI);
719 const auto *RtPtrChecking = LAI->getRuntimePointerChecking();
720 const auto &AllChecks = RtPtrChecking->getChecks();
721 auto Checks = includeOnlyCrossPartitionChecks(AllChecks, PtrToPartition,
724 if (!Pred.isAlwaysTrue() || !Checks.empty()) {
725 DEBUG(dbgs() << "\nPointers:\n");
726 DEBUG(LAI->getRuntimePointerChecking()->printChecks(dbgs(), Checks));
727 LoopVersioning LVer(*LAI, L, LI, DT, SE, false);
728 LVer.setAliasChecks(std::move(Checks));
729 LVer.setSCEVChecks(LAI->getPSE().getUnionPredicate());
730 LVer.versionLoop(DefsUsedOutside);
731 LVer.annotateLoopWithNoAlias();
734 // Create identical copies of the original loop for each partition and hook
735 // them up sequentially.
736 Partitions.cloneLoops();
738 // Now, we remove the instruction from each loop that don't belong to that
740 Partitions.removeUnusedInsts();
741 DEBUG(dbgs() << "\nAfter removing unused Instrs:\n");
742 DEBUG(Partitions.printBlocks());
749 ++NumLoopsDistributed;
750 // Report the success.
751 emitOptimizationRemark(F->getContext(), LDIST_NAME, *F, L->getStartLoc(),
756 /// \brief Provide diagnostics then \return with false.
757 bool fail(llvm::StringRef Message) {
758 LLVMContext &Ctx = F->getContext();
759 bool Forced = isForced().getValueOr(false);
761 DEBUG(dbgs() << "Skipping; " << Message << "\n");
763 // With Rpass-missed report that distribution failed.
764 ORE->emitOptimizationRemarkMissed(
766 "loop not distributed: use -Rpass-analysis=loop-distribute for more "
769 // With Rpass-analysis report why. This is on by default if distribution
770 // was requested explicitly.
771 emitOptimizationRemarkAnalysis(
772 Ctx, Forced ? DiagnosticInfoOptimizationRemarkAnalysis::AlwaysPrint
774 *F, L->getStartLoc(), Twine("loop not distributed: ") + Message);
776 // Also issue a warning if distribution was requested explicitly but it
779 Ctx.diagnose(DiagnosticInfoOptimizationFailure(
780 *F, L->getStartLoc(), "loop not distributed: failed "
781 "explicitly specified loop distribution"));
786 /// \brief Return if distribution forced to be enabled/disabled for the loop.
788 /// If the optional has a value, it indicates whether distribution was forced
789 /// to be enabled (true) or disabled (false). If the optional has no value
790 /// distribution was not forced either way.
791 const Optional<bool> &isForced() const { return IsForced; }
794 /// \brief Filter out checks between pointers from the same partition.
796 /// \p PtrToPartition contains the partition number for pointers. Partition
797 /// number -1 means that the pointer is used in multiple partitions. In this
798 /// case we can't safely omit the check.
799 SmallVector<RuntimePointerChecking::PointerCheck, 4>
800 includeOnlyCrossPartitionChecks(
801 const SmallVectorImpl<RuntimePointerChecking::PointerCheck> &AllChecks,
802 const SmallVectorImpl<int> &PtrToPartition,
803 const RuntimePointerChecking *RtPtrChecking) {
804 SmallVector<RuntimePointerChecking::PointerCheck, 4> Checks;
806 std::copy_if(AllChecks.begin(), AllChecks.end(), std::back_inserter(Checks),
807 [&](const RuntimePointerChecking::PointerCheck &Check) {
808 for (unsigned PtrIdx1 : Check.first->Members)
809 for (unsigned PtrIdx2 : Check.second->Members)
810 // Only include this check if there is a pair of pointers
811 // that require checking and the pointers fall into
812 // separate partitions.
814 // (Note that we already know at this point that the two
815 // pointer groups need checking but it doesn't follow
816 // that each pair of pointers within the two groups need
819 // In other words we don't want to include a check just
820 // because there is a pair of pointers between the two
821 // pointer groups that require checks and a different
822 // pair whose pointers fall into different partitions.)
823 if (RtPtrChecking->needsChecking(PtrIdx1, PtrIdx2) &&
824 !RuntimePointerChecking::arePointersInSamePartition(
825 PtrToPartition, PtrIdx1, PtrIdx2))
833 /// \brief Check whether the loop metadata is forcing distribution to be
834 /// enabled/disabled.
836 Optional<const MDOperand *> Value =
837 findStringMetadataForLoop(L, "llvm.loop.distribute.enable");
841 const MDOperand *Op = *Value;
842 assert(Op && mdconst::hasa<ConstantInt>(*Op) && "invalid metadata");
843 IsForced = mdconst::extract<ConstantInt>(*Op)->getZExtValue();
851 const LoopAccessInfo *LAI;
854 OptimizationRemarkEmitter *ORE;
856 /// \brief Indicates whether distribution is forced to be enabled/disabled for
859 /// If the optional has a value, it indicates whether distribution was forced
860 /// to be enabled (true) or disabled (false). If the optional has no value
861 /// distribution was not forced either way.
862 Optional<bool> IsForced;
865 /// Shared implementation between new and old PMs.
866 static bool runImpl(Function &F, LoopInfo *LI, DominatorTree *DT,
867 ScalarEvolution *SE, OptimizationRemarkEmitter *ORE,
868 std::function<const LoopAccessInfo &(Loop &)> &GetLAA,
869 bool ProcessAllLoops) {
870 // Build up a worklist of inner-loops to vectorize. This is necessary as the
871 // act of distributing a loop creates new loops and can invalidate iterators
873 SmallVector<Loop *, 8> Worklist;
875 for (Loop *TopLevelLoop : *LI)
876 for (Loop *L : depth_first(TopLevelLoop))
877 // We only handle inner-most loops.
879 Worklist.push_back(L);
881 // Now walk the identified inner loops.
882 bool Changed = false;
883 for (Loop *L : Worklist) {
884 LoopDistributeForLoop LDL(L, &F, LI, DT, SE, ORE);
886 // If distribution was forced for the specific loop to be
887 // enabled/disabled, follow that. Otherwise use the global flag.
888 if (LDL.isForced().getValueOr(ProcessAllLoops))
889 Changed |= LDL.processLoop(GetLAA);
892 // Process each loop nest in the function.
896 /// \brief The pass class.
897 class LoopDistributeLegacy : public FunctionPass {
899 /// \p ProcessAllLoopsByDefault specifies whether loop distribution should be
900 /// performed by default. Pass -enable-loop-distribute={0,1} overrides this
901 /// default. We use this to keep LoopDistribution off by default when invoked
902 /// from the optimization pipeline but on when invoked explicitly from opt.
903 LoopDistributeLegacy(bool ProcessAllLoopsByDefault = true)
904 : FunctionPass(ID), ProcessAllLoops(ProcessAllLoopsByDefault) {
905 // The default is set by the caller.
906 if (EnableLoopDistribute.getNumOccurrences() > 0)
907 ProcessAllLoops = EnableLoopDistribute;
908 initializeLoopDistributeLegacyPass(*PassRegistry::getPassRegistry());
911 bool runOnFunction(Function &F) override {
915 auto *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
916 auto *LAA = &getAnalysis<LoopAccessLegacyAnalysis>();
917 auto *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
918 auto *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
919 auto *ORE = &getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE();
920 std::function<const LoopAccessInfo &(Loop &)> GetLAA =
921 [&](Loop &L) -> const LoopAccessInfo & { return LAA->getInfo(&L); };
923 return runImpl(F, LI, DT, SE, ORE, GetLAA, ProcessAllLoops);
926 void getAnalysisUsage(AnalysisUsage &AU) const override {
927 AU.addRequired<ScalarEvolutionWrapperPass>();
928 AU.addRequired<LoopInfoWrapperPass>();
929 AU.addPreserved<LoopInfoWrapperPass>();
930 AU.addRequired<LoopAccessLegacyAnalysis>();
931 AU.addRequired<DominatorTreeWrapperPass>();
932 AU.addPreserved<DominatorTreeWrapperPass>();
933 AU.addRequired<OptimizationRemarkEmitterWrapperPass>();
939 /// \brief Whether distribution should be on in this function. The per-loop
940 /// pragma can override this.
941 bool ProcessAllLoops;
943 } // anonymous namespace
945 PreservedAnalyses LoopDistributePass::run(Function &F,
946 FunctionAnalysisManager &AM) {
947 // FIXME: This does not currently match the behavior from the old PM.
948 // ProcessAllLoops with the old PM defaults to true when invoked from opt and
949 // false when invoked from the optimization pipeline.
950 bool ProcessAllLoops = false;
951 if (EnableLoopDistribute.getNumOccurrences() > 0)
952 ProcessAllLoops = EnableLoopDistribute;
954 auto &LI = AM.getResult<LoopAnalysis>(F);
955 auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
956 auto &SE = AM.getResult<ScalarEvolutionAnalysis>(F);
957 auto &ORE = AM.getResult<OptimizationRemarkEmitterAnalysis>(F);
959 auto &LAM = AM.getResult<LoopAnalysisManagerFunctionProxy>(F).getManager();
960 std::function<const LoopAccessInfo &(Loop &)> GetLAA =
961 [&](Loop &L) -> const LoopAccessInfo & {
962 return LAM.getResult<LoopAccessAnalysis>(L);
965 bool Changed = runImpl(F, &LI, &DT, &SE, &ORE, GetLAA, ProcessAllLoops);
967 return PreservedAnalyses::all();
968 PreservedAnalyses PA;
969 PA.preserve<LoopAnalysis>();
970 PA.preserve<DominatorTreeAnalysis>();
974 char LoopDistributeLegacy::ID;
975 static const char ldist_name[] = "Loop Distribition";
977 INITIALIZE_PASS_BEGIN(LoopDistributeLegacy, LDIST_NAME, ldist_name, false,
979 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
980 INITIALIZE_PASS_DEPENDENCY(LoopAccessLegacyAnalysis)
981 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
982 INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
983 INITIALIZE_PASS_DEPENDENCY(OptimizationRemarkEmitterWrapperPass)
984 INITIALIZE_PASS_END(LoopDistributeLegacy, LDIST_NAME, ldist_name, false, false)
987 FunctionPass *createLoopDistributePass(bool ProcessAllLoopsByDefault) {
988 return new LoopDistributeLegacy(ProcessAllLoopsByDefault);