1025 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8//9// This file implements the Loop Distribution Pass. Its main focus is to10// distribute loops that cannot be vectorized due to dependence cycles. It11// tries to isolate the offending dependences into a new loop allowing12// vectorization of the remaining parts.13//14// For dependence analysis, the pass uses the LoopVectorizer's15// LoopAccessAnalysis. Because this analysis presumes no change in the order of16// memory operations, special care is taken to preserve the lexical order of17// these operations.18//19// Similarly to the Vectorizer, the pass also supports loop versioning to20// 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_NAME73 74/// @{75/// Metadata attribute names76static 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(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(false));97 98static cl::opt<unsigned> DistributeSCEVCheckThreshold(99 "loop-distribute-scev-check-threshold", cl::init(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(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(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 before122/// 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(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(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 empty146 /// after this.147 void moveTo(InstPartition &Other) {148 Other.Set.insert_range(Set);149 Set.clear();150 Other.DepCycle |= DepCycle;151 }152 153 /// Populates the partition with a transitive closure of all the154 /// instructions that the seeded instructions dependent on.155 void populateUsedSet() {156 // FIXME: We currently don't use control-dependence but simply include all157 // blocks (possibly empty at the end) and let simplifycfg mostly clean this158 // up.159 for (auto *B : OrigLoop->getBlocks())160 Set.insert(B->getTerminator());161 162 // Follow the use-def chains to form a transitive closure of all the163 // 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>(V);170 if (I && OrigLoop->contains(I->getParent()) && Set.insert(I))171 Worklist.push_back(I);172 }173 }174 }175 176 /// Clones the original loop.177 ///178 /// Updates LoopInfo and DominatorTree using the information that block \p179 /// LoopDomBB dominates the loop.180 Loop *cloneLoopWithPreheader(BasicBlock *InsertBefore, BasicBlock *LoopDomBB,181 unsigned Index, LoopInfo *LI,182 DominatorTree *DT) {183 ClonedLoop = ::cloneLoopWithPreheader(InsertBefore, LoopDomBB, OrigLoop,184 VMap, Twine(".ldist") + Twine(Index),185 LI, DT, 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 from195 /// the loop.196 Loop *getDistributedLoop() const {197 return ClonedLoop ? ClonedLoop : OrigLoop;198 }199 200 /// The VMap that is populated by cloning and then used in201 /// remapinstruction to remap the cloned instructions.202 ValueToValueMapTy &getVMap() { return VMap; }203 204 /// Remaps the cloned instructions using VMap.205 void remapInstructions() {206 remapInstructionsInBlocks(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(&Inst)) {217 Instruction *NewInst = &Inst;218 if (!VMap.empty())219 NewInst = cast<Instruction>(VMap[NewInst]);220 221 assert(!isa<BranchInst>(NewInst) &&222 "Branches are marked used early on");223 Unused.push_back(NewInst);224 }225 226 // Delete the instructions backwards, as it has a reduced likelihood of227 // having to update as many def-use and use-def chains.228 for (auto *Inst : reverse(Unused)) {229 salvageDebugInfo(*Inst);230 if (!Inst->use_empty())231 Inst->replaceAllUsesWith(PoisonValue::get(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 this263 /// 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 been267 /// finalized. If this partition is mapped to the original loop, these are not268 /// set.269 ValueToValueMapTy VMap;270};271 272/// Holds the set of Partitions. It populates them, merges them and then273/// 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 to285 /// 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(Inst, L, /*DepCycle=*/true);290 else291 PartitionContainer.back().add(Inst);292 }293 294 /// Adds \p Inst into a partition that is not marked to contain295 /// dependence cycles.296 ///297 // Initially we isolate memory instructions into as many partitions as298 // possible, then later we may merge them back together.299 void addToNewNonCyclicPartition(Instruction *Inst) {300 PartitionContainer.emplace_back(Inst, L);301 }302 303 /// Merges adjacent non-cyclic partitions.304 ///305 /// The idea is that we currently only want to isolate the non-vectorizable306 /// partition. We could later allow more distribution among these partition307 /// too.308 void mergeAdjacentNonCyclic() {309 mergeAdjacentPartitionsIf(310 [](const InstPartition *P) { return !P->hasDepCycle(); });311 }312 313 /// If a partition contains only conditional stores, we won't vectorize314 /// it. Try to merge it with a previous cyclic partition.315 void mergeNonIfConvertible() {316 mergeAdjacentPartitionsIf([&](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>(Inst)) {325 seenStore = true;326 if (!LoopAccessInfo::blockNeedsPredication(Inst->getParent(), 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 that344 /// 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 partitions355 // that contain the same load. Also put partitions in between them in the356 // 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 all363 // partitions (PartI, PartJ] into PartI.364 for (Instruction *Inst : *PartI)365 if (isa<LoadInst>(Inst)) {366 bool NewElt;367 LoadToPartitionT::iterator LoadToPart;368 369 std::tie(LoadToPart, NewElt) =370 LoadToPartition.insert(std::make_pair(Inst, 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(PartI, &*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. This390 // 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(std::next(ToBeMerged.member_begin(*C)),397 ToBeMerged.member_end())) {398 PartJ->moveTo(*PartI);399 }400 }401 402 // Remove the empty partitions.403 PartitionContainer.remove_if(404 [](const InstPartition &P) { return P.empty(); });405 406 return true;407 }408 409 /// Sets up the mapping between instructions to partitions. If the410 /// 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(Iter, NewElt) =419 InstToPartitionId.insert(std::make_pair(Inst, PartitionID));420 if (!NewElt)421 Iter->second = -1;422 }423 ++PartitionID;424 }425 }426 427 /// Populates the partition with everything that the seeding428 /// 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 for435 /// the partitions.436 void cloneLoops() {437 BasicBlock *OrigPH = L->getLoopPreheader();438 // At this point the predecessor of the preheader is either the memcheck439 // 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 sure448 // 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 original456 // loop before PH along with adding a preheader for the cloned loop. Then457 // 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(llvm::reverse(PartitionContainer))) {461 NewLoop = Part.cloneLoopWithPreheader(TopPH, Pred, Index, LI, DT);462 463 Part.getVMap()[ExitBlock] = TopPH;464 Part.remapInstructions();465 setNewLoopID(OrigLoopID, &Part);466 --Index;467 TopPH = NewLoop->getLoopPreheader();468 }469 Pred->getTerminator()->replaceUsesOfWith(OrigPH, TopPH);470 471 // Also set a new loop ID for the last loop.472 setNewLoopID(OrigLoopID, &PartitionContainer.back());473 474 // Now go in forward order and update the immediate dominator for the475 // preheaders with the exiting block of the previous loop. Dominance476 // within the loop is updated in cloneLoopWithPreheader.477 for (auto Curr = PartitionContainer.cbegin(),478 Next = std::next(PartitionContainer.cbegin()),479 E = PartitionContainer.cend();480 Next != E; ++Curr, ++Next)481 DT->changeImmediateDominator(482 Next->getDistributedLoop()->getLoopPreheader(),483 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 is493 /// used in.494 ///495 /// This returns an array of int where the I-th entry corresponds to I-th496 /// entry in LAI.getRuntimePointerCheck(). If the pointer is used in multiple497 /// 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 */ true);507 auto ReadInstructions =508 LAI.getInstructionsForAccess(Ptr, /* IsWrite */ false);509 Instructions.append(ReadInstructions.begin(), 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 multiple516 // 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(dbgs()); }541 542#ifndef NDEBUG543 friend raw_ostream &operator<<(raw_ostream &OS,544 const InstPartitionContainer &Partitions) {545 Partitions.print(OS);546 return OS;547 }548#endif549 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 instruction565 /// 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 satisfy573 /// 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(*PrevMatch);584 I = PartitionContainer.erase(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 {LLVMLoopDistributeFollowupAll,597 Part->hasDepCycle() ? LLVMLoopDistributeFollowupSequential598 : 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 the607/// number of unsafe dependences that start out from this instruction minus608/// those that end here.609///610/// By traversing the memory instructions in program order and accumulating this611/// 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(Instructions.begin(), 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 program637 // order, i.e. source is always first. (The direction is given by the638 // 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("MultipleExitBlocks", "multiple exit blocks");671 if (!L->isLoopSimplifyForm())672 return fail("NotLoopSimplifyForm",673 "loop is not in loop-simplify form");674 if (!L->isRotatedForm())675 return fail("NotBottomTested", "loop is not bottom tested");676 677 BasicBlock *PH = L->getLoopPreheader();678 679 LAI = &LAIs.getInfo(*L);680 681 // Currently, we only distribute to isolate the part of the loop with682 // dependence cycles to enable partial vectorization.683 if (LAI->canVectorizeMemory())684 return fail("MemOpsCanBeVectorized",685 "memory operations are safe for vectorization");686 687 auto *Dependences = LAI->getDepChecker().getDependences();688 if (!Dependences || Dependences->empty())689 return fail("NoUnsafeDeps", "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 consecutive697 // partitions (the order of partitions follows program order). Put those698 // with unsafe dependences into "cyclic" partition otherwise put each store699 // 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 that702 // has an unsafe dependence (Store3->Load1) spanning over it must be703 // included in the same cyclic partition as the dependent operations. This704 // is to preserve the original program order after distribution. E.g.:705 //706 // NumUnsafeDependencesStartOrEnd NumUnsafeDependencesActive707 // Load1 -. 1 0->1708 // Load2 | /Unsafe/ 0 1709 // Store3 -' -1 1->0710 // Load4 0 0711 //712 // NumUnsafeDependencesActive > 0 indicates this situation and in this case713 // we just keep assigning to the same cyclic partition until714 // 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 the723 // start of a dependence directly via NumUnsafeDependencesStartOrEnd.724 if (NumUnsafeDependencesActive ||725 InstDep.NumUnsafeDependencesStartOrEnd > 0)726 Partitions.addToCyclicPartition(I);727 else728 Partitions.addToNewNonCyclicPartition(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 of735 // order from the original program order. This is OK because if the736 // partition uses a load we will merge this partition with the original737 // partition of the load that we set up in the previous loop (see738 // 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("CantIsolateUnsafeDeps",746 "cannot isolate unsafe dependencies");747 748 // Run the merge heuristics: Merge non-cyclic adjacent partitions since we749 // 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("CantIsolateUnsafeDeps",754 "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 the761 // 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("CantIsolateUnsafeDeps",767 "cannot isolate unsafe dependencies");768 }769 770 // Don't distribute the loop if we need too many SCEV run-time checks, or771 // any if it's illegal.772 const SCEVPredicate &Pred = LAI->getPSE().getPredicate();773 if (LAI->hasConvergentOp() && !Pred.isAlwaysTrue()) {774 return fail("RuntimeCheckWithConvergent",775 "may not insert runtime check with convergent operation");776 }777 778 if (Pred.getComplexity() > (IsForced.value_or(false)779 ? PragmaDistributeSCEVCheckThreshold780 : DistributeSCEVCheckThreshold))781 return fail("TooManySCEVRuntimeChecks",782 "too many SCEV run-time checks needed.\n");783 784 if (!IsForced.value_or(false) && hasDisableAllTransformsHint(L))785 return fail("HeuristicDisabled", "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 from790 // instructions to partitions.791 Partitions.setupPartitionIdOnInstructions();792 793 // If we need run-time checks, version the loop now.794 auto PtrToPartition = Partitions.computePartitionSetForPointers(*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("RuntimeCheckWithConvergent",802 "may not insert runtime check with convergent operation");803 }804 805 // To keep things simple have an empty preheader before we version or clone806 // the loop. (Also split if this has no predecessor, i.e. entry, because we807 // rely on PH having a predecessor.)808 if (!PH->getSinglePredecessor() || &*PH->begin() != PH->getTerminator())809 SplitBlock(PH, 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 attributes823 // from the original loop, but remove the loop distribution metadata to824 // avoid to distribute it again.825 MDNode *UnversionedLoopID = *makeFollowupLoopID(826 OrigLoopID,827 {LLVMLoopDistributeFollowupAll, LLVMLoopDistributeFollowupFallback},828 "llvm.loop.distribute.", true);829 LVer.getNonVersionedLoop()->setLoopID(UnversionedLoopID);830 addStringMetadataToLoop(LVer.getNonVersionedLoop(), DistributedMetaData,831 true);832 }833 834 // Create identical copies of the original loop for each partition and hook835 // them up sequentially.836 Partitions.cloneLoops();837 838 // Now, we remove the instruction from each loop that don't belong to that839 // 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(*DT);846 assert(DT->verify(DominatorTree::VerificationLevel::Fast));847 }848 849 ++NumLoopsDistributed;850 // Report the success.851 ORE->emit([&]() {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(false);863 864 LLVM_DEBUG(dbgs() << "LDist: Skipping; " << Message << "\n");865 866 // With Rpass-missed report that distribution failed.867 ORE->emit([&]() {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 distribution876 // was requested explicitly.877 ORE->emit(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 it883 // failed.884 if (Forced)885 Ctx.diagnose(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 forced895 /// to be enabled (true) or disabled (false). If the optional has no value896 /// 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. Partition903 /// number -1 means that the pointer is used in multiple partitions. In this904 /// 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(AllChecks, std::back_inserter(Checks),912 [&](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 pointers916 // that require checking and the pointers fall into917 // separate partitions.918 //919 // (Note that we already know at this point that the two920 // pointer groups need checking but it doesn't follow921 // that each pair of pointers within the two groups need922 // checking as well.923 //924 // In other words we don't want to include a check just925 // because there is a pair of pointers between the two926 // pointer groups that require checks and a different927 // pair whose pointers fall into different partitions.)928 if (RtPtrChecking->needsChecking(PtrIdx1, 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 be939 /// enabled/disabled.940 void setForced() {941 std::optional<const MDOperand *> Value =942 findStringMetadataForLoop(L, "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>(*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 for963 /// the loop.964 ///965 /// If the optional has a value, it indicates whether distribution was forced966 /// to be enabled (true) or disabled (false). If the optional has no value967 /// distribution was not forced either way.968 std::optional<bool> IsForced;969};970 971} // end anonymous namespace972 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 the977 // act of distributing a loop creates new loops and can invalidate iterators978 // across the loops.979 SmallVector<Loop *, 8> Worklist;980 981 for (Loop *TopLevelLoop : *LI)982 for (Loop *L : depth_first(TopLevelLoop))983 // We only handle inner-most loops.984 if (L->isInnermost())985 Worklist.push_back(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 distributed993 if (getOptionalBoolLoopAttribute(L, DistributedMetaData).value_or(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 be1000 // enabled/disabled, follow that. Otherwise use the global flag.1001 if (LDL.isForced().value_or(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>(F);1012 auto &DT = AM.getResult<DominatorTreeAnalysis>(F);1013 auto &SE = AM.getResult<ScalarEvolutionAnalysis>(F);1014 auto &ORE = AM.getResult<OptimizationRemarkEmitterAnalysis>(F);1015 1016 LoopAccessInfoManager &LAIs = AM.getResult<LoopAccessAnalysis>(F);1017 bool Changed = runImpl(F, &LI, &DT, &SE, &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