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