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