1//===- LoopDistribute.cpp - Loop Distribution Pass ------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file implements the Loop Distribution Pass. Its main focus is to
10// distribute loops that cannot be vectorized due to dependence cycles. It
11// tries to isolate the offending dependences into a new loop allowing
12// vectorization of the remaining parts.
13//
14// For dependence analysis, the pass uses the LoopVectorizer's
15// LoopAccessAnalysis. Because this analysis presumes no change in the order of
16// memory operations, special care is taken to preserve the lexical order of
17// these operations.
18//
19// Similarly to the Vectorizer, the pass also supports loop versioning to
20// run-time disambiguate potentially overlapping arrays.
21//
22//===----------------------------------------------------------------------===//
23
24#include "llvm/Transforms/Scalar/LoopDistribute.h"
25#include "ScalarOptions.h"
26#include "llvm/ADT/DenseMap.h"
27#include "llvm/ADT/DepthFirstIterator.h"
28#include "llvm/ADT/EquivalenceClasses.h"
29#include "llvm/ADT/STLExtras.h"
30#include "llvm/ADT/SetVector.h"
31#include "llvm/ADT/SmallVector.h"
32#include "llvm/ADT/Statistic.h"
33#include "llvm/ADT/StringRef.h"
34#include "llvm/ADT/Twine.h"
35#include "llvm/ADT/iterator_range.h"
36#include "llvm/Analysis/AssumptionCache.h"
37#include "llvm/Analysis/GlobalsModRef.h"
38#include "llvm/Analysis/LoopAccessAnalysis.h"
39#include "llvm/Analysis/LoopAnalysisManager.h"
40#include "llvm/Analysis/LoopInfo.h"
41#include "llvm/Analysis/OptimizationRemarkEmitter.h"
42#include "llvm/Analysis/ScalarEvolution.h"
43#include "llvm/Analysis/TargetLibraryInfo.h"
44#include "llvm/Analysis/TargetTransformInfo.h"
45#include "llvm/IR/BasicBlock.h"
46#include "llvm/IR/Constants.h"
47#include "llvm/IR/DiagnosticInfo.h"
48#include "llvm/IR/Dominators.h"
49#include "llvm/IR/Function.h"
50#include "llvm/IR/Instruction.h"
51#include "llvm/IR/Instructions.h"
52#include "llvm/IR/LLVMContext.h"
53#include "llvm/IR/Metadata.h"
54#include "llvm/IR/PassManager.h"
55#include "llvm/IR/Value.h"
56#include "llvm/Support/Casting.h"
57#include "llvm/Support/Debug.h"
58#include "llvm/Support/raw_ostream.h"
59#include "llvm/Transforms/Utils/BasicBlockUtils.h"
60#include "llvm/Transforms/Utils/Cloning.h"
61#include "llvm/Transforms/Utils/Local.h"
62#include "llvm/Transforms/Utils/LoopUtils.h"
63#include "llvm/Transforms/Utils/LoopVersioning.h"
64#include "llvm/Transforms/Utils/ValueMapper.h"
65#include <cassert>
66#include <list>
67#include <tuple>
68
69using namespace llvm;
70
71#define LDIST_NAME "loop-distribute"
72#define DEBUG_TYPE LDIST_NAME
73
74/// @{
75/// Metadata attribute names
76static const char *const LLVMLoopDistributeFollowupAll =
77 "llvm.loop.distribute.followup_all";
78static const char *const LLVMLoopDistributeFollowupCoincident =
79 "llvm.loop.distribute.followup_coincident";
80static const char *const LLVMLoopDistributeFollowupSequential =
81 "llvm.loop.distribute.followup_sequential";
82static const char *const LLVMLoopDistributeFollowupFallback =
83 "llvm.loop.distribute.followup_fallback";
84/// @}
85
86static const char *DistributedMetaData = "llvm.loop.isdistributed";
87
88STATISTIC(NumLoopsDistributed, "Number of loops distributed");
89
90namespace {
91
92/// Maintains the set of instructions of the loop for a partition before
93/// cloning. After cloning, it hosts the new loop.
94class InstPartition {
95 using InstructionSet = SmallSetVector<Instruction *, 8>;
96
97public:
98 InstPartition(Instruction *I, Loop *L, bool DepCycle = false)
99 : DepCycle(DepCycle), OrigLoop(L) {
100 Set.insert(X: I);
101 }
102
103 /// Returns whether this partition contains a dependence cycle.
104 bool hasDepCycle() const { return DepCycle; }
105
106 /// Adds an instruction to this partition.
107 void add(Instruction *I) { Set.insert(X: I); }
108
109 /// Collection accessors.
110 InstructionSet::iterator begin() { return Set.begin(); }
111 InstructionSet::iterator end() { return Set.end(); }
112 InstructionSet::const_iterator begin() const { return Set.begin(); }
113 InstructionSet::const_iterator end() const { return Set.end(); }
114 bool empty() const { return Set.empty(); }
115
116 /// Moves this partition into \p Other. This partition becomes empty
117 /// after this.
118 void moveTo(InstPartition &Other) {
119 Other.Set.insert_range(R&: Set);
120 Set.clear();
121 Other.DepCycle |= DepCycle;
122 }
123
124 /// Populates the partition with a transitive closure of all the
125 /// instructions that the seeded instructions dependent on.
126 void populateUsedSet() {
127 // FIXME: We currently don't use control-dependence but simply include all
128 // blocks (possibly empty at the end) and let simplifycfg mostly clean this
129 // up.
130 for (auto *B : OrigLoop->getBlocks())
131 Set.insert(X: B->getTerminator());
132
133 // Follow the use-def chains to form a transitive closure of all the
134 // instructions that the originally seeded instructions depend on.
135 SmallVector<Instruction *, 8> Worklist(Set.begin(), Set.end());
136 while (!Worklist.empty()) {
137 Instruction *I = Worklist.pop_back_val();
138 // Insert instructions from the loop that we depend on.
139 for (Value *V : I->operand_values()) {
140 auto *I = dyn_cast<Instruction>(Val: V);
141 if (I && OrigLoop->contains(BB: I->getParent()) && Set.insert(X: I))
142 Worklist.push_back(Elt: I);
143 }
144 }
145 }
146
147 /// Clones the original loop.
148 ///
149 /// Updates LoopInfo and DominatorTree using the information that block \p
150 /// LoopDomBB dominates the loop.
151 Loop *cloneLoopWithPreheader(BasicBlock *InsertBefore, BasicBlock *LoopDomBB,
152 unsigned Index, LoopInfo *LI,
153 DominatorTree *DT) {
154 ClonedLoop = ::cloneLoopWithPreheader(Before: InsertBefore, LoopDomBB, OrigLoop,
155 VMap, NameSuffix: Twine(".ldist") + Twine(Index),
156 LI, DT, Blocks&: ClonedLoopBlocks);
157 return ClonedLoop;
158 }
159
160 /// The cloned loop. If this partition is mapped to the original loop,
161 /// this is null.
162 const Loop *getClonedLoop() const { return ClonedLoop; }
163
164 /// Returns the loop where this partition ends up after distribution.
165 /// If this partition is mapped to the original loop then use the block from
166 /// the loop.
167 Loop *getDistributedLoop() const {
168 return ClonedLoop ? ClonedLoop : OrigLoop;
169 }
170
171 /// The VMap that is populated by cloning and then used in
172 /// remapinstruction to remap the cloned instructions.
173 ValueToValueMapTy &getVMap() { return VMap; }
174
175 /// Remaps the cloned instructions using VMap.
176 void remapInstructions() {
177 remapInstructionsInBlocks(Blocks: ClonedLoopBlocks, VMap);
178 }
179
180 /// Based on the set of instructions selected for this partition,
181 /// removes the unnecessary ones.
182 void removeUnusedInsts() {
183 SmallVector<Instruction *, 8> Unused;
184
185 for (auto *Block : OrigLoop->getBlocks())
186 for (auto &Inst : *Block)
187 if (!Set.count(key: &Inst)) {
188 Instruction *NewInst = &Inst;
189 if (!VMap.empty())
190 NewInst = cast<Instruction>(Val&: VMap[NewInst]);
191
192 assert((!isa<UncondBrInst, CondBrInst>(NewInst)) &&
193 "Branches are marked used early on");
194 Unused.push_back(Elt: NewInst);
195 }
196
197 // Delete the instructions backwards, as it has a reduced likelihood of
198 // having to update as many def-use and use-def chains.
199 for (auto *Inst : reverse(C&: Unused)) {
200 salvageDebugInfo(I&: *Inst);
201 if (!Inst->use_empty())
202 Inst->replaceAllUsesWith(V: PoisonValue::get(T: Inst->getType()));
203 Inst->eraseFromParent();
204 }
205 }
206
207 void print(raw_ostream &OS) const {
208 OS << (DepCycle ? " (cycle)\n" : "\n");
209 for (auto *I : Set)
210 // Prefix with the block name.
211 OS << " " << I->getParent()->getName() << ":" << *I << "\n";
212 }
213
214 void printBlocks(raw_ostream &OS) const {
215 for (auto *BB : getDistributedLoop()->getBlocks())
216 OS << *BB;
217 }
218
219private:
220 /// Instructions from OrigLoop selected for this partition.
221 InstructionSet Set;
222
223 /// Whether this partition contains a dependence cycle.
224 bool DepCycle;
225
226 /// The original loop.
227 Loop *OrigLoop;
228
229 /// The cloned loop. If this partition is mapped to the original loop,
230 /// this is null.
231 Loop *ClonedLoop = nullptr;
232
233 /// The blocks of ClonedLoop including the preheader. If this
234 /// partition is mapped to the original loop, this is empty.
235 SmallVector<BasicBlock *, 8> ClonedLoopBlocks;
236
237 /// These gets populated once the set of instructions have been
238 /// finalized. If this partition is mapped to the original loop, these are not
239 /// set.
240 ValueToValueMapTy VMap;
241};
242
243/// Holds the set of Partitions. It populates them, merges them and then
244/// clones the loops.
245class InstPartitionContainer {
246 using InstToPartitionIdT = DenseMap<Instruction *, int>;
247
248public:
249 InstPartitionContainer(Loop *L, LoopInfo *LI, DominatorTree *DT)
250 : L(L), LI(LI), DT(DT) {}
251
252 /// Returns the number of partitions.
253 unsigned getSize() const { return PartitionContainer.size(); }
254
255 /// Adds \p Inst into the current partition if that is marked to
256 /// contain cycles. Otherwise start a new partition for it.
257 void addToCyclicPartition(Instruction *Inst) {
258 // If the current partition is non-cyclic. Start a new one.
259 if (PartitionContainer.empty() || !PartitionContainer.back().hasDepCycle())
260 PartitionContainer.emplace_back(args&: Inst, args&: L, /*DepCycle=*/args: true);
261 else
262 PartitionContainer.back().add(I: Inst);
263 }
264
265 /// Adds \p Inst into a partition that is not marked to contain
266 /// dependence cycles.
267 ///
268 // Initially we isolate memory instructions into as many partitions as
269 // possible, then later we may merge them back together.
270 void addToNewNonCyclicPartition(Instruction *Inst) {
271 PartitionContainer.emplace_back(args&: Inst, args&: L);
272 }
273
274 /// Merges adjacent non-cyclic partitions.
275 ///
276 /// The idea is that we currently only want to isolate the non-vectorizable
277 /// partition. We could later allow more distribution among these partition
278 /// too.
279 void mergeAdjacentNonCyclic() {
280 mergeAdjacentPartitionsIf(
281 Predicate: [](const InstPartition *P) { return !P->hasDepCycle(); });
282 }
283
284 /// If a partition contains only conditional stores, we won't vectorize
285 /// it. Try to merge it with a previous cyclic partition.
286 void mergeNonIfConvertible() {
287 mergeAdjacentPartitionsIf(Predicate: [&](const InstPartition *Partition) {
288 if (Partition->hasDepCycle())
289 return true;
290
291 // Now, check if all stores are conditional in this partition.
292 bool seenStore = false;
293
294 for (auto *Inst : *Partition)
295 if (isa<StoreInst>(Val: Inst)) {
296 seenStore = true;
297 if (!LoopAccessInfo::blockNeedsPredication(BB: Inst->getParent(), TheLoop: L, DT))
298 return false;
299 }
300 return seenStore;
301 });
302 }
303
304 /// Merges the partitions according to various heuristics.
305 void mergeBeforePopulating(const ScalarOptions &Opts) {
306 mergeAdjacentNonCyclic();
307 if (!Opts.loop_distribute_non_if_convertible)
308 mergeNonIfConvertible();
309 }
310
311 /// Merges partitions in order to ensure that no loads are duplicated.
312 ///
313 /// We can't duplicate loads because that could potentially reorder them.
314 /// LoopAccessAnalysis provides dependency information with the context that
315 /// the order of memory operation is preserved.
316 ///
317 /// Return if any partitions were merged.
318 bool mergeToAvoidDuplicatedLoads() {
319 using LoadToPartitionT = DenseMap<Instruction *, InstPartition *>;
320 using ToBeMergedT = EquivalenceClasses<InstPartition *>;
321
322 LoadToPartitionT LoadToPartition;
323 ToBeMergedT ToBeMerged;
324
325 // Step through the partitions and create equivalence between partitions
326 // that contain the same load. Also put partitions in between them in the
327 // same equivalence class to avoid reordering of memory operations.
328 for (PartitionContainerT::iterator I = PartitionContainer.begin(),
329 E = PartitionContainer.end();
330 I != E; ++I) {
331 auto *PartI = &*I;
332
333 // If a load occurs in two partitions PartI and PartJ, merge all
334 // partitions (PartI, PartJ] into PartI.
335 for (Instruction *Inst : *PartI)
336 if (isa<LoadInst>(Val: Inst)) {
337 bool NewElt;
338 LoadToPartitionT::iterator LoadToPart;
339
340 std::tie(args&: LoadToPart, args&: NewElt) =
341 LoadToPartition.insert(KV: std::make_pair(x&: Inst, y&: PartI));
342 if (!NewElt) {
343 LLVM_DEBUG(
344 dbgs()
345 << "LDist: Merging partitions due to this load in multiple "
346 << "partitions: " << PartI << ", " << LoadToPart->second << "\n"
347 << *Inst << "\n");
348
349 auto PartJ = I;
350 do {
351 --PartJ;
352 ToBeMerged.unionSets(V1: PartI, V2: &*PartJ);
353 } while (&*PartJ != LoadToPart->second);
354 }
355 }
356 }
357 if (ToBeMerged.empty())
358 return false;
359
360 // Merge the member of an equivalence class into its class leader. This
361 // makes the members empty.
362 for (const auto &C : ToBeMerged) {
363 if (!C->isLeader())
364 continue;
365
366 auto PartI = C->getData();
367 for (auto *PartJ : make_range(x: std::next(x: ToBeMerged.member_begin(ECV: *C)),
368 y: ToBeMerged.member_end())) {
369 PartJ->moveTo(Other&: *PartI);
370 }
371 }
372
373 // Remove the empty partitions.
374 PartitionContainer.remove_if(
375 pred: [](const InstPartition &P) { return P.empty(); });
376
377 return true;
378 }
379
380 /// Sets up the mapping between instructions to partitions. If the
381 /// instruction is duplicated across multiple partitions, set the entry to -1.
382 void setupPartitionIdOnInstructions() {
383 int PartitionID = 0;
384 for (const auto &Partition : PartitionContainer) {
385 for (Instruction *Inst : Partition) {
386 bool NewElt;
387 InstToPartitionIdT::iterator Iter;
388
389 std::tie(args&: Iter, args&: NewElt) =
390 InstToPartitionId.insert(KV: std::make_pair(x&: Inst, y&: PartitionID));
391 if (!NewElt)
392 Iter->second = -1;
393 }
394 ++PartitionID;
395 }
396 }
397
398 /// Populates the partition with everything that the seeding
399 /// instructions require.
400 void populateUsedSet() {
401 for (auto &P : PartitionContainer)
402 P.populateUsedSet();
403 }
404
405 /// This performs the main chunk of the work of cloning the loops for
406 /// the partitions.
407 void cloneLoops() {
408 BasicBlock *OrigPH = L->getLoopPreheader();
409 // At this point the predecessor of the preheader is either the memcheck
410 // block or the top part of the original preheader.
411 BasicBlock *Pred = OrigPH->getSinglePredecessor();
412 assert(Pred && "Preheader does not have a single predecessor");
413 BasicBlock *ExitBlock = L->getExitBlock();
414 assert(ExitBlock && "No single exit block");
415 Loop *NewLoop;
416
417 assert(!PartitionContainer.empty() && "at least two partitions expected");
418 // We're cloning the preheader along with the loop so we already made sure
419 // it was empty.
420 assert(&*OrigPH->begin() == OrigPH->getTerminator() &&
421 "preheader not empty");
422
423 // Preserve the original loop ID for use after the transformation.
424 MDNode *OrigLoopID = L->getLoopID();
425
426 // Create a loop for each partition except the last. Clone the original
427 // loop before PH along with adding a preheader for the cloned loop. Then
428 // update PH to point to the newly added preheader.
429 BasicBlock *TopPH = OrigPH;
430 unsigned Index = getSize() - 1;
431 for (auto &Part : llvm::drop_begin(RangeOrContainer: llvm::reverse(C&: PartitionContainer))) {
432 NewLoop = Part.cloneLoopWithPreheader(InsertBefore: TopPH, LoopDomBB: Pred, Index, LI, DT);
433
434 Part.getVMap()[ExitBlock] = TopPH;
435 Part.remapInstructions();
436 setNewLoopID(OrigLoopID, Part: &Part);
437 --Index;
438 TopPH = NewLoop->getLoopPreheader();
439 }
440 Pred->getTerminator()->replaceUsesOfWith(From: OrigPH, To: TopPH);
441
442 // Also set a new loop ID for the last loop.
443 setNewLoopID(OrigLoopID, Part: &PartitionContainer.back());
444
445 // Now go in forward order and update the immediate dominator for the
446 // preheaders with the exiting block of the previous loop. Dominance
447 // within the loop is updated in cloneLoopWithPreheader.
448 for (auto Curr = PartitionContainer.cbegin(),
449 Next = std::next(x: PartitionContainer.cbegin()),
450 E = PartitionContainer.cend();
451 Next != E; ++Curr, ++Next)
452 DT->changeImmediateDominator(
453 BB: Next->getDistributedLoop()->getLoopPreheader(),
454 NewBB: Curr->getDistributedLoop()->getExitingBlock());
455 }
456
457 /// Removes the dead instructions from the cloned loops.
458 void removeUnusedInsts() {
459 for (auto &Partition : PartitionContainer)
460 Partition.removeUnusedInsts();
461 }
462
463 /// For each memory pointer, it computes the partitionId the pointer is
464 /// used in.
465 ///
466 /// This returns an array of int where the I-th entry corresponds to I-th
467 /// entry in LAI.getRuntimePointerCheck(). If the pointer is used in multiple
468 /// partitions its entry is set to -1.
469 SmallVector<int, 8>
470 computePartitionSetForPointers(const LoopAccessInfo &LAI) {
471 const RuntimePointerChecking *RtPtrCheck = LAI.getRuntimePointerChecking();
472
473 unsigned N = RtPtrCheck->Pointers.size();
474 SmallVector<int, 8> PtrToPartitions(N);
475 for (unsigned I = 0; I < N; ++I) {
476 Value *Ptr = RtPtrCheck->Pointers[I].PointerValue;
477 auto Instructions = LAI.getInstructionsForAccess(Ptr, /* IsWrite */ isWrite: true);
478 auto ReadInstructions =
479 LAI.getInstructionsForAccess(Ptr, /* IsWrite */ isWrite: false);
480 Instructions.append(in_start: ReadInstructions.begin(), in_end: ReadInstructions.end());
481
482 int &Partition = PtrToPartitions[I];
483 // First set it to uninitialized.
484 Partition = -2;
485 for (Instruction *Inst : Instructions) {
486 // Note that this could be -1 if Inst is duplicated across multiple
487 // partitions.
488 int ThisPartition = this->InstToPartitionId[Inst];
489 if (Partition == -2)
490 Partition = ThisPartition;
491 // -1 means belonging to multiple partitions.
492 else if (Partition == -1)
493 break;
494 else if (Partition != ThisPartition)
495 Partition = -1;
496 }
497 assert(Partition != -2 && "Pointer not belonging to any partition");
498 }
499
500 return PtrToPartitions;
501 }
502
503 void print(raw_ostream &OS) const {
504 unsigned Index = 0;
505 for (const auto &P : PartitionContainer) {
506 OS << "LDist: Partition " << Index++ << ":";
507 P.print(OS);
508 }
509 }
510
511 void dump() const { print(OS&: dbgs()); }
512
513#ifndef NDEBUG
514 friend raw_ostream &operator<<(raw_ostream &OS,
515 const InstPartitionContainer &Partitions) {
516 Partitions.print(OS);
517 return OS;
518 }
519#endif
520
521 void printBlocks(raw_ostream &OS) const {
522 unsigned Index = 0;
523 for (const auto &P : PartitionContainer) {
524 OS << "LDist: Partition " << Index++ << ":";
525 P.printBlocks(OS);
526 }
527 }
528
529private:
530 using PartitionContainerT = std::list<InstPartition>;
531
532 /// List of partitions.
533 PartitionContainerT PartitionContainer;
534
535 /// Mapping from Instruction to partition Id. If the instruction
536 /// belongs to multiple partitions the entry contains -1.
537 InstToPartitionIdT InstToPartitionId;
538
539 Loop *L;
540 LoopInfo *LI;
541 DominatorTree *DT;
542
543 /// The control structure to merge adjacent partitions if both satisfy
544 /// the \p Predicate.
545 template <class UnaryPredicate>
546 void mergeAdjacentPartitionsIf(UnaryPredicate Predicate) {
547 InstPartition *PrevMatch = nullptr;
548 for (auto I = PartitionContainer.begin(); I != PartitionContainer.end();) {
549 auto DoesMatch = Predicate(&*I);
550 if (PrevMatch == nullptr && DoesMatch) {
551 PrevMatch = &*I;
552 ++I;
553 } else if (PrevMatch != nullptr && DoesMatch) {
554 I->moveTo(Other&: *PrevMatch);
555 I = PartitionContainer.erase(position: I);
556 } else {
557 PrevMatch = nullptr;
558 ++I;
559 }
560 }
561 }
562
563 /// Assign new LoopIDs for the partition's cloned loop.
564 void setNewLoopID(MDNode *OrigLoopID, InstPartition *Part) {
565 std::optional<MDNode *> PartitionID = makeFollowupLoopID(
566 OrigLoopID,
567 FollowupAttrs: {LLVMLoopDistributeFollowupAll,
568 Part->hasDepCycle() ? LLVMLoopDistributeFollowupSequential
569 : LLVMLoopDistributeFollowupCoincident});
570 if (PartitionID) {
571 Loop *NewLoop = Part->getDistributedLoop();
572 NewLoop->setLoopID(*PartitionID);
573 }
574 }
575};
576
577/// For each memory instruction, this class maintains difference of the
578/// number of unsafe dependences that start out from this instruction minus
579/// those that end here.
580///
581/// By traversing the memory instructions in program order and accumulating this
582/// number, we know whether any unsafe dependence crosses over a program point.
583class MemoryInstructionDependences {
584 using Dependence = MemoryDepChecker::Dependence;
585
586public:
587 struct Entry {
588 Instruction *Inst;
589 unsigned NumUnsafeDependencesStartOrEnd = 0;
590
591 Entry(Instruction *Inst) : Inst(Inst) {}
592 };
593
594 using AccessesType = SmallVector<Entry, 8>;
595
596 AccessesType::const_iterator begin() const { return Accesses.begin(); }
597 AccessesType::const_iterator end() const { return Accesses.end(); }
598
599 MemoryInstructionDependences(
600 const SmallVectorImpl<Instruction *> &Instructions,
601 const SmallVectorImpl<Dependence> &Dependences) {
602 Accesses.append(in_start: Instructions.begin(), in_end: Instructions.end());
603
604 LLVM_DEBUG(dbgs() << "LDist: Backward dependences:\n");
605 for (const auto &Dep : Dependences)
606 if (Dep.isPossiblyBackward()) {
607 // Note that the designations source and destination follow the program
608 // order, i.e. source is always first. (The direction is given by the
609 // DepType.)
610 ++Accesses[Dep.Source].NumUnsafeDependencesStartOrEnd;
611 --Accesses[Dep.Destination].NumUnsafeDependencesStartOrEnd;
612
613 LLVM_DEBUG(Dep.print(dbgs(), 2, Instructions));
614 }
615 }
616
617private:
618 AccessesType Accesses;
619};
620
621/// The actual class performing the per-loop work.
622class LoopDistributeForLoop {
623public:
624 LoopDistributeForLoop(const ScalarOptions &Opts, Loop *L, Function *F,
625 LoopInfo *LI, DominatorTree *DT, ScalarEvolution *SE,
626 LoopAccessInfoManager &LAIs,
627 OptimizationRemarkEmitter *ORE)
628 : Opts(Opts), L(L), F(F), LI(LI), DT(DT), SE(SE), LAIs(LAIs), ORE(ORE) {
629 setForced();
630 }
631
632 /// Try to distribute an inner-most loop.
633 bool processLoop() {
634 assert(L->isInnermost() && "Only process inner loops.");
635
636 LLVM_DEBUG(dbgs() << "\nLDist: Checking a loop in '"
637 << L->getHeader()->getParent()->getName() << "' from "
638 << L->getLocStr() << "\n");
639
640 // Having a single exit block implies there's also one exiting block.
641 if (!L->getExitBlock())
642 return fail(RemarkName: "MultipleExitBlocks", Message: "multiple exit blocks");
643 if (!L->isLoopSimplifyForm())
644 return fail(RemarkName: "NotLoopSimplifyForm",
645 Message: "loop is not in loop-simplify form");
646 if (!L->isRotatedForm())
647 return fail(RemarkName: "NotBottomTested", Message: "loop is not bottom tested");
648
649 BasicBlock *PH = L->getLoopPreheader();
650
651 LAI = &LAIs.getInfo(L&: *L);
652
653 // Currently, we only distribute to isolate the part of the loop with
654 // dependence cycles to enable partial vectorization.
655 if (LAI->canVectorizeMemory())
656 return fail(RemarkName: "MemOpsCanBeVectorized",
657 Message: "memory operations are safe for vectorization");
658
659 auto *Dependences = LAI->getDepChecker().getDependences();
660 if (!Dependences || Dependences->empty())
661 return fail(RemarkName: "NoUnsafeDeps", Message: "no unsafe dependences to isolate");
662
663 LLVM_DEBUG(dbgs() << "LDist: Found a candidate loop: "
664 << L->getHeader()->getName() << "\n");
665
666 InstPartitionContainer Partitions(L, LI, DT);
667
668 // First, go through each memory operation and assign them to consecutive
669 // partitions (the order of partitions follows program order). Put those
670 // with unsafe dependences into "cyclic" partition otherwise put each store
671 // in its own "non-cyclic" partition (we'll merge these later).
672 //
673 // Note that a memory operation (e.g. Load2 below) at a program point that
674 // has an unsafe dependence (Store3->Load1) spanning over it must be
675 // included in the same cyclic partition as the dependent operations. This
676 // is to preserve the original program order after distribution. E.g.:
677 //
678 // NumUnsafeDependencesStartOrEnd NumUnsafeDependencesActive
679 // Load1 -. 1 0->1
680 // Load2 | /Unsafe/ 0 1
681 // Store3 -' -1 1->0
682 // Load4 0 0
683 //
684 // NumUnsafeDependencesActive > 0 indicates this situation and in this case
685 // we just keep assigning to the same cyclic partition until
686 // NumUnsafeDependencesActive reaches 0.
687 const MemoryDepChecker &DepChecker = LAI->getDepChecker();
688 MemoryInstructionDependences MID(DepChecker.getMemoryInstructions(),
689 *Dependences);
690
691 int NumUnsafeDependencesActive = 0;
692 for (const auto &InstDep : MID) {
693 Instruction *I = InstDep.Inst;
694 // We update NumUnsafeDependencesActive post-instruction, catch the
695 // start of a dependence directly via NumUnsafeDependencesStartOrEnd.
696 if (NumUnsafeDependencesActive ||
697 InstDep.NumUnsafeDependencesStartOrEnd > 0)
698 Partitions.addToCyclicPartition(Inst: I);
699 else
700 Partitions.addToNewNonCyclicPartition(Inst: I);
701 NumUnsafeDependencesActive += InstDep.NumUnsafeDependencesStartOrEnd;
702 assert(NumUnsafeDependencesActive >= 0 &&
703 "Negative number of dependences active");
704 }
705
706 // Add partitions for values used outside. These partitions can be out of
707 // order from the original program order. This is OK because if the
708 // partition uses a load we will merge this partition with the original
709 // partition of the load that we set up in the previous loop (see
710 // mergeToAvoidDuplicatedLoads).
711 auto DefsUsedOutside = findDefsUsedOutsideOfLoop(L);
712 for (auto *Inst : DefsUsedOutside)
713 Partitions.addToNewNonCyclicPartition(Inst);
714
715 LLVM_DEBUG(dbgs() << "LDist: Seeded partitions:\n" << Partitions);
716 if (Partitions.getSize() < 2)
717 return fail(RemarkName: "CantIsolateUnsafeDeps",
718 Message: "cannot isolate unsafe dependencies");
719
720 // Run the merge heuristics: Merge non-cyclic adjacent partitions since we
721 // should be able to vectorize these together.
722 Partitions.mergeBeforePopulating(Opts);
723 LLVM_DEBUG(dbgs() << "LDist: Merged partitions:\n" << Partitions);
724 if (Partitions.getSize() < 2)
725 return fail(RemarkName: "CantIsolateUnsafeDeps",
726 Message: "cannot isolate unsafe dependencies");
727
728 // Now, populate the partitions with non-memory operations.
729 Partitions.populateUsedSet();
730 LLVM_DEBUG(dbgs() << "LDist: Populated partitions:\n" << Partitions);
731
732 // In order to preserve original lexical order for loads, keep them in the
733 // partition that we set up in the MemoryInstructionDependences loop.
734 if (Partitions.mergeToAvoidDuplicatedLoads()) {
735 LLVM_DEBUG(dbgs() << "LDist: Partitions merged to ensure unique loads:\n"
736 << Partitions);
737 if (Partitions.getSize() < 2)
738 return fail(RemarkName: "CantIsolateUnsafeDeps",
739 Message: "cannot isolate unsafe dependencies");
740 }
741
742 // Don't distribute the loop if we need too many SCEV run-time checks, or
743 // any if it's illegal.
744 const SCEVPredicate &Pred = LAI->getPSE().getPredicate();
745 if (LAI->hasConvergentOp() && !Pred.isAlwaysTrue()) {
746 return fail(RemarkName: "RuntimeCheckWithConvergent",
747 Message: "may not insert runtime check with convergent operation");
748 }
749
750 if (Pred.getComplexity() >
751 (IsForced.value_or(u: false)
752 ? Opts.loop_distribute_scev_check_threshold_with_pragma
753 : Opts.loop_distribute_scev_check_threshold))
754 return fail(RemarkName: "TooManySCEVRuntimeChecks",
755 Message: "too many SCEV run-time checks needed.\n");
756
757 if (!IsForced.value_or(u: false) && hasDisableAllTransformsHint(L))
758 return fail(RemarkName: "HeuristicDisabled", Message: "distribution heuristic disabled");
759
760 LLVM_DEBUG(dbgs() << "LDist: Distributing loop: "
761 << L->getHeader()->getName() << "\n");
762 // We're done forming the partitions set up the reverse mapping from
763 // instructions to partitions.
764 Partitions.setupPartitionIdOnInstructions();
765
766 // If we need run-time checks, version the loop now.
767 auto PtrToPartition = Partitions.computePartitionSetForPointers(LAI: *LAI);
768 const auto *RtPtrChecking = LAI->getRuntimePointerChecking();
769 const auto &AllChecks = RtPtrChecking->getChecks();
770 auto Checks = includeOnlyCrossPartitionChecks(AllChecks, PtrToPartition,
771 RtPtrChecking);
772
773 if (LAI->hasConvergentOp() && !Checks.empty()) {
774 return fail(RemarkName: "RuntimeCheckWithConvergent",
775 Message: "may not insert runtime check with convergent operation");
776 }
777
778 // To keep things simple have an empty preheader before we version or clone
779 // the loop. (Also split if this has no predecessor, i.e. entry, because we
780 // rely on PH having a predecessor.)
781 if (!PH->getSinglePredecessor() || &*PH->begin() != PH->getTerminator())
782 SplitBlock(Old: PH, SplitPt: PH->getTerminator(), DT, LI);
783
784 if (!Pred.isAlwaysTrue() || !Checks.empty()) {
785 assert(!LAI->hasConvergentOp() && "inserting illegal loop versioning");
786
787 MDNode *OrigLoopID = L->getLoopID();
788
789 LLVM_DEBUG(dbgs() << "LDist: Pointers:\n");
790 LLVM_DEBUG(LAI->getRuntimePointerChecking()->printChecks(dbgs(), Checks));
791 // Forming LCSSA is a precondition of versioning.
792 if (!L->isRecursivelyLCSSAForm(DT: *DT, LI: *LI))
793 formLCSSARecursively(L&: *L, DT: *DT, LI, SE);
794 LoopVersioning LVer(*LAI, Checks, L, LI, DT, SE);
795 LVer.versionLoop(DefsUsedOutside);
796 LVer.annotateLoopWithNoAlias();
797
798 // The unversioned loop will not be changed, so we inherit all attributes
799 // from the original loop, but remove the loop distribution metadata to
800 // avoid to distribute it again.
801 MDNode *UnversionedLoopID = *makeFollowupLoopID(
802 OrigLoopID,
803 FollowupAttrs: {LLVMLoopDistributeFollowupAll, LLVMLoopDistributeFollowupFallback},
804 InheritOptionsAttrsPrefix: "llvm.loop.distribute.", AlwaysNew: true);
805 LVer.getNonVersionedLoop()->setLoopID(UnversionedLoopID);
806 addStringMetadataToLoop(TheLoop: LVer.getNonVersionedLoop(), MDString: DistributedMetaData,
807 V: true);
808 }
809
810 // Create identical copies of the original loop for each partition and hook
811 // them up sequentially.
812 Partitions.cloneLoops();
813
814 // Now, we remove the instruction from each loop that don't belong to that
815 // partition.
816 Partitions.removeUnusedInsts();
817 LLVM_DEBUG(dbgs() << "LDist: After removing unused Instrs:\n");
818 LLVM_DEBUG(Partitions.printBlocks(dbgs()));
819
820 if (Opts.loop_distribute_verify) {
821 LI->verify();
822 assert(DT->verify(DominatorTree::VerificationLevel::Fast));
823 }
824
825 ++NumLoopsDistributed;
826 // Report the success.
827 ORE->emit(RemarkBuilder: [&]() {
828 return OptimizationRemark(LDIST_NAME, "Distribute", L->getStartLoc(),
829 L->getHeader())
830 << "distributed loop";
831 });
832 return true;
833 }
834
835 /// Provide diagnostics then \return with false.
836 bool fail(StringRef RemarkName, StringRef Message) {
837 LLVMContext &Ctx = F->getContext();
838 bool Forced = isForced().value_or(u: false);
839
840 LLVM_DEBUG(dbgs() << "LDist: Skipping; " << Message << "\n");
841
842 // With Rpass-missed report that distribution failed.
843 ORE->emit(RemarkBuilder: [&]() {
844 return OptimizationRemarkMissed(LDIST_NAME, "NotDistributed",
845 L->getStartLoc(), L->getHeader())
846 << "loop not distributed: use -Rpass-analysis=loop-distribute for "
847 "more "
848 "info";
849 });
850
851 // With Rpass-analysis report why. This is on by default if distribution
852 // was requested explicitly.
853 ORE->emit(OptDiag: OptimizationRemarkAnalysis(
854 Forced ? OptimizationRemarkAnalysis::AlwaysPrint : LDIST_NAME,
855 RemarkName, L->getStartLoc(), L->getHeader())
856 << "loop not distributed: " << Message);
857
858 // Also issue a warning if distribution was requested explicitly but it
859 // failed.
860 if (Forced)
861 Ctx.diagnose(DI: DiagnosticInfoOptimizationFailure(
862 *F, L->getStartLoc(), "loop not distributed: failed "
863 "explicitly specified loop distribution"));
864
865 return false;
866 }
867
868 /// Return if distribution forced to be enabled/disabled for the loop.
869 ///
870 /// If the optional has a value, it indicates whether distribution was forced
871 /// to be enabled (true) or disabled (false). If the optional has no value
872 /// distribution was not forced either way.
873 const std::optional<bool> &isForced() const { return IsForced; }
874
875private:
876 /// Filter out checks between pointers from the same partition.
877 ///
878 /// \p PtrToPartition contains the partition number for pointers. Partition
879 /// number -1 means that the pointer is used in multiple partitions. In this
880 /// case we can't safely omit the check.
881 SmallVector<RuntimePointerCheck, 4> includeOnlyCrossPartitionChecks(
882 const SmallVectorImpl<RuntimePointerCheck> &AllChecks,
883 const SmallVectorImpl<int> &PtrToPartition,
884 const RuntimePointerChecking *RtPtrChecking) {
885 SmallVector<RuntimePointerCheck, 4> Checks;
886
887 copy_if(Range: AllChecks, Out: std::back_inserter(x&: Checks),
888 P: [&](const RuntimePointerCheck &Check) {
889 for (unsigned PtrIdx1 : Check.first->Members)
890 for (unsigned PtrIdx2 : Check.second->Members)
891 // Only include this check if there is a pair of pointers
892 // that require checking and the pointers fall into
893 // separate partitions.
894 //
895 // (Note that we already know at this point that the two
896 // pointer groups need checking but it doesn't follow
897 // that each pair of pointers within the two groups need
898 // checking as well.
899 //
900 // In other words we don't want to include a check just
901 // because there is a pair of pointers between the two
902 // pointer groups that require checks and a different
903 // pair whose pointers fall into different partitions.)
904 if (RtPtrChecking->needsChecking(I: PtrIdx1, J: PtrIdx2) &&
905 !RuntimePointerChecking::arePointersInSamePartition(
906 PtrToPartition, PtrIdx1, PtrIdx2))
907 return true;
908 return false;
909 });
910
911 return Checks;
912 }
913
914 /// Check whether the loop metadata is forcing distribution to be
915 /// enabled/disabled.
916 void setForced() {
917 if (getBooleanLoopAttribute(TheLoop: L, Name: "llvm.loop.distribute.enable"))
918 IsForced = true;
919 else if (getBooleanLoopAttribute(TheLoop: L, Name: "llvm.loop.distribute.disable"))
920 IsForced = false;
921 }
922
923 const ScalarOptions &Opts;
924 Loop *L;
925 Function *F;
926
927 // Analyses used.
928 LoopInfo *LI;
929 const LoopAccessInfo *LAI = nullptr;
930 DominatorTree *DT;
931 ScalarEvolution *SE;
932 LoopAccessInfoManager &LAIs;
933 OptimizationRemarkEmitter *ORE;
934
935 /// Indicates whether distribution is forced to be enabled/disabled for
936 /// the loop.
937 ///
938 /// If the optional has a value, it indicates whether distribution was forced
939 /// to be enabled (true) or disabled (false). If the optional has no value
940 /// distribution was not forced either way.
941 std::optional<bool> IsForced;
942};
943
944} // end anonymous namespace
945
946static bool runImpl(Function &F, LoopInfo *LI, DominatorTree *DT,
947 ScalarEvolution *SE, OptimizationRemarkEmitter *ORE,
948 LoopAccessInfoManager &LAIs) {
949 // Build up a worklist of inner-loops to distribute. This is necessary as the
950 // act of distributing a loop creates new loops and can invalidate iterators
951 // across the loops.
952 SmallVector<Loop *, 8> Worklist;
953
954 for (Loop *TopLevelLoop : *LI)
955 for (Loop *L : depth_first(G: TopLevelLoop))
956 // We only handle inner-most loops.
957 if (L->isInnermost())
958 Worklist.push_back(Elt: L);
959
960 // Now walk the identified inner loops.
961 const ScalarOptions &Opts = ScalarOptions::Global;
962 bool Changed = false;
963 for (Loop *L : Worklist) {
964 LoopDistributeForLoop LDL(Opts, L, &F, LI, DT, SE, LAIs, ORE);
965
966 // Do not reprocess loops we already distributed
967 if (getOptionalBoolLoopAttribute(TheLoop: L, Name: DistributedMetaData).value_or(u: false)) {
968 LLVM_DEBUG(
969 dbgs() << "LDist: Distributed loop guarded for reprocessing\n");
970 continue;
971 }
972
973 // If distribution was forced for the specific loop to be
974 // enabled/disabled, follow that. Otherwise use the global flag.
975 if (LDL.isForced().value_or(u: Opts.enable_loop_distribute))
976 Changed |= LDL.processLoop();
977 }
978
979 // Process each loop nest in the function.
980 return Changed;
981}
982
983PreservedAnalyses LoopDistributePass::run(Function &F,
984 FunctionAnalysisManager &AM) {
985 auto &LI = AM.getResult<LoopAnalysis>(IR&: F);
986 auto &DT = AM.getResult<DominatorTreeAnalysis>(IR&: F);
987 auto &SE = AM.getResult<ScalarEvolutionAnalysis>(IR&: F);
988 auto &ORE = AM.getResult<OptimizationRemarkEmitterAnalysis>(IR&: F);
989
990 LoopAccessInfoManager &LAIs = AM.getResult<LoopAccessAnalysis>(IR&: F);
991 bool Changed = runImpl(F, LI: &LI, DT: &DT, SE: &SE, ORE: &ORE, LAIs);
992 if (!Changed)
993 return PreservedAnalyses::all();
994 PreservedAnalyses PA;
995 PA.preserve<LoopAnalysis>();
996 PA.preserve<DominatorTreeAnalysis>();
997 return PA;
998}
999