X-Git-Url: http://plrg.eecs.uci.edu/git/?p=oota-llvm.git;a=blobdiff_plain;f=lib%2FTransforms%2FScalar%2FLoopDistribute.cpp;h=6c211458100ca9bf88ad45772655679db467b3b4;hp=0325d268c3256fb9e3f861a6ce6121b5692561e6;hb=8452a3f46e1636321765e2022b14b789f2b99ec4;hpb=08056a49f10d411c010fa450f86732ff87f5cf49 diff --git a/lib/Transforms/Scalar/LoopDistribute.cpp b/lib/Transforms/Scalar/LoopDistribute.cpp index 0325d268c32..6c211458100 100644 --- a/lib/Transforms/Scalar/LoopDistribute.cpp +++ b/lib/Transforms/Scalar/LoopDistribute.cpp @@ -34,6 +34,7 @@ #include "llvm/Support/Debug.h" #include "llvm/Transforms/Utils/BasicBlockUtils.h" #include "llvm/Transforms/Utils/Cloning.h" +#include "llvm/Transforms/Utils/LoopVersioning.h" #include #define LDIST_NAME "loop-distribute" @@ -55,70 +56,6 @@ static cl::opt DistributeNonIfConvertible( STATISTIC(NumLoopsDistributed, "Number of loops distributed"); -/// \brief Remaps instructions in a loop including the preheader. -static void remapInstructionsInLoop(const SmallVectorImpl &Blocks, - ValueToValueMapTy &VMap) { - // Rewrite the code to refer to itself. - for (auto *BB : Blocks) - for (auto &Inst : *BB) - RemapInstruction(&Inst, VMap, - RF_NoModuleLevelChanges | RF_IgnoreMissingEntries); -} - -/// \brief Clones a loop \p OrigLoop. Returns the loop and the blocks in \p -/// Blocks. -/// -/// Updates LoopInfo and DominatorTree assuming the loop is dominated by block -/// \p LoopDomBB. Insert the new blocks before block specified in \p Before. -static Loop *cloneLoopWithPreheader(BasicBlock *Before, BasicBlock *LoopDomBB, - Loop *OrigLoop, ValueToValueMapTy &VMap, - const Twine &NameSuffix, LoopInfo *LI, - DominatorTree *DT, - SmallVectorImpl &Blocks) { - Function *F = OrigLoop->getHeader()->getParent(); - Loop *ParentLoop = OrigLoop->getParentLoop(); - - Loop *NewLoop = new Loop(); - if (ParentLoop) - ParentLoop->addChildLoop(NewLoop); - else - LI->addTopLevelLoop(NewLoop); - - BasicBlock *OrigPH = OrigLoop->getLoopPreheader(); - BasicBlock *NewPH = CloneBasicBlock(OrigPH, VMap, NameSuffix, F); - // To rename the loop PHIs. - VMap[OrigPH] = NewPH; - Blocks.push_back(NewPH); - - // Update LoopInfo. - if (ParentLoop) - ParentLoop->addBasicBlockToLoop(NewPH, *LI); - - // Update DominatorTree. - DT->addNewBlock(NewPH, LoopDomBB); - - for (BasicBlock *BB : OrigLoop->getBlocks()) { - BasicBlock *NewBB = CloneBasicBlock(BB, VMap, NameSuffix, F); - VMap[BB] = NewBB; - - // Update LoopInfo. - NewLoop->addBasicBlockToLoop(NewBB, *LI); - - // Update DominatorTree. - BasicBlock *IDomBB = DT->getNode(BB)->getIDom()->getBlock(); - DT->addNewBlock(NewBB, cast(VMap[IDomBB])); - - Blocks.push_back(NewBB); - } - - // Move them physically from the end of the block list. - F->getBasicBlockList().splice(Before, F->getBasicBlockList(), NewPH); - F->getBasicBlockList().splice(Before, F->getBasicBlockList(), - NewLoop->getHeader(), F->end()); - - return NewLoop; -} - namespace { /// \brief Maintains the set of instructions of the loop for a partition before /// cloning. After cloning, it hosts the new loop. @@ -204,7 +141,9 @@ public: ValueToValueMapTy &getVMap() { return VMap; } /// \brief Remaps the cloned instructions using VMap. - void remapInstructions() { remapInstructionsInLoop(ClonedLoopBlocks, VMap); } + void remapInstructions() { + remapInstructionsInBlocks(ClonedLoopBlocks, VMap); + } /// \brief Based on the set of instructions selected for this partition, /// removes the unnecessary ones. @@ -225,9 +164,7 @@ public: // Delete the instructions backwards, as it has a reduced likelihood of // having to update as many def-use and use-def chains. - for (auto I = Unused.rbegin(), E = Unused.rend(); I != E; ++I) { - auto *Inst = *I; - + for (auto *Inst : make_range(Unused.rbegin(), Unused.rend())) { if (!Inst->use_empty()) Inst->replaceAllUsesWith(UndefValue::get(Inst->getType())); Inst->eraseFromParent(); @@ -493,15 +430,14 @@ public: /// partitions its entry is set to -1. SmallVector computePartitionSetForPointers(const LoopAccessInfo &LAI) { - const LoopAccessInfo::RuntimePointerCheck *RtPtrCheck = - LAI.getRuntimePointerCheck(); + const RuntimePointerChecking *RtPtrCheck = LAI.getRuntimePointerChecking(); unsigned N = RtPtrCheck->Pointers.size(); SmallVector PtrToPartitions(N); for (unsigned I = 0; I < N; ++I) { - Value *Ptr = RtPtrCheck->Pointers[I]; + Value *Ptr = RtPtrCheck->Pointers[I].PointerValue; auto Instructions = - LAI.getInstructionsForAccess(Ptr, RtPtrCheck->IsWritePtr[I]); + LAI.getInstructionsForAccess(Ptr, RtPtrCheck->Pointers[I].IsWritePtr); int &Partition = PtrToPartitions[I]; // First set it to uninitialized. @@ -629,121 +565,6 @@ private: AccessesType Accesses; }; -/// \brief Handles the loop versioning based on memchecks. -class LoopVersioning { -public: - LoopVersioning(const LoopAccessInfo &LAI, Loop *L, LoopInfo *LI, - DominatorTree *DT, - const SmallVector *PtrToPartition = nullptr) - : VersionedLoop(L), NonVersionedLoop(nullptr), - PtrToPartition(PtrToPartition), LAI(LAI), LI(LI), DT(DT) {} - - /// \brief Returns true if we need memchecks to disambiguate may-aliasing - /// accesses. - bool needsRuntimeChecks() const { - return LAI.getRuntimePointerCheck()->needsAnyChecking(PtrToPartition); - } - - /// \brief Performs the CFG manipulation part of versioning the loop including - /// the DominatorTree and LoopInfo updates. - void versionLoop(Pass *P) { - Instruction *FirstCheckInst; - Instruction *MemRuntimeCheck; - // Add the memcheck in the original preheader (this is empty initially). - BasicBlock *MemCheckBB = VersionedLoop->getLoopPreheader(); - std::tie(FirstCheckInst, MemRuntimeCheck) = - LAI.addRuntimeCheck(MemCheckBB->getTerminator(), PtrToPartition); - assert(MemRuntimeCheck && "called even though needsAnyChecking = false"); - - // Rename the block to make the IR more readable. - MemCheckBB->setName(VersionedLoop->getHeader()->getName() + - ".lver.memcheck"); - - // Create empty preheader for the loop (and after cloning for the - // non-versioned loop). - BasicBlock *PH = - SplitBlock(MemCheckBB, MemCheckBB->getTerminator(), DT, LI); - PH->setName(VersionedLoop->getHeader()->getName() + ".ph"); - - // Clone the loop including the preheader. - // - // FIXME: This does not currently preserve SimplifyLoop because the exit - // block is a join between the two loops. - SmallVector NonVersionedLoopBlocks; - NonVersionedLoop = - cloneLoopWithPreheader(PH, MemCheckBB, VersionedLoop, VMap, - ".lver.orig", LI, DT, NonVersionedLoopBlocks); - remapInstructionsInLoop(NonVersionedLoopBlocks, VMap); - - // Insert the conditional branch based on the result of the memchecks. - Instruction *OrigTerm = MemCheckBB->getTerminator(); - BranchInst::Create(NonVersionedLoop->getLoopPreheader(), - VersionedLoop->getLoopPreheader(), MemRuntimeCheck, - OrigTerm); - OrigTerm->eraseFromParent(); - - // The loops merge in the original exit block. This is now dominated by the - // memchecking block. - DT->changeImmediateDominator(VersionedLoop->getExitBlock(), MemCheckBB); - } - - /// \brief Adds the necessary PHI nodes for the versioned loops based on the - /// loop-defined values used outside of the loop. - void addPHINodes(const SmallVectorImpl &DefsUsedOutside) { - BasicBlock *PHIBlock = VersionedLoop->getExitBlock(); - assert(PHIBlock && "No single successor to loop exit block"); - - for (auto *Inst : DefsUsedOutside) { - auto *NonVersionedLoopInst = cast(VMap[Inst]); - PHINode *PN; - - // First see if we have a single-operand PHI with the value defined by the - // original loop. - for (auto I = PHIBlock->begin(); (PN = dyn_cast(I)); ++I) { - assert(PN->getNumOperands() == 1 && - "Exit block should only have on predecessor"); - if (PN->getIncomingValue(0) == Inst) - break; - } - // If not create it. - if (!PN) { - PN = PHINode::Create(Inst->getType(), 2, Inst->getName() + ".lver", - PHIBlock->begin()); - for (auto *User : Inst->users()) - if (!VersionedLoop->contains(cast(User)->getParent())) - User->replaceUsesOfWith(Inst, PN); - PN->addIncoming(Inst, VersionedLoop->getExitingBlock()); - } - // Add the new incoming value from the non-versioned loop. - PN->addIncoming(NonVersionedLoopInst, - NonVersionedLoop->getExitingBlock()); - } - } - -private: - /// \brief The original loop. This becomes the "versioned" one, i.e. control - /// goes if the memchecks all pass. - Loop *VersionedLoop; - /// \brief The fall-back loop, i.e. if any of the memchecks fail. - Loop *NonVersionedLoop; - - /// \brief For each memory pointer it contains the partitionId it is used in. - /// If nullptr, no partitioning is used. - /// - /// The I-th entry corresponds to I-th entry in LAI.getRuntimePointerCheck(). - /// If the pointer is used in multiple partitions the entry is set to -1. - const SmallVector *PtrToPartition; - - /// \brief This maps the instructions from VersionedLoop to their counterpart - /// in NonVersionedLoop. - ValueToValueMapTy VMap; - - /// \brief Analyses used. - const LoopAccessInfo &LAI; - LoopInfo *LI; - DominatorTree *DT; -}; - /// \brief Returns the instructions that use values defined in the loop. static SmallVector findDefsUsedOutsideOfLoop(Loop *L) { SmallVector UsedOutside; @@ -806,6 +627,45 @@ public: static char ID; private: + /// \brief Filter out checks between pointers from the same partition. + /// + /// \p PtrToPartition contains the partition number for pointers. Partition + /// number -1 means that the pointer is used in multiple partitions. In this + /// case we can't safely omit the check. + SmallVector + includeOnlyCrossPartitionChecks( + const SmallVectorImpl &AllChecks, + const SmallVectorImpl &PtrToPartition, + const RuntimePointerChecking *RtPtrChecking) { + SmallVector Checks; + + std::copy_if(AllChecks.begin(), AllChecks.end(), std::back_inserter(Checks), + [&](const RuntimePointerChecking::PointerCheck &Check) { + for (unsigned PtrIdx1 : Check.first->Members) + for (unsigned PtrIdx2 : Check.second->Members) + // Only include this check if there is a pair of pointers + // that require checking and the pointers fall into + // separate partitions. + // + // (Note that we already know at this point that the two + // pointer groups need checking but it doesn't follow + // that each pair of pointers within the two groups need + // checking as well. + // + // In other words we don't want to include a check just + // because there is a pair of pointers between the two + // pointer groups that require checks and a different + // pair whose pointers fall into different partitions.) + if (RtPtrChecking->needsChecking(PtrIdx1, PtrIdx2) && + !RuntimePointerChecking::arePointersInSamePartition( + PtrToPartition, PtrIdx1, PtrIdx2)) + return true; + return false; + }); + + return Checks; + } + /// \brief Try to distribute an inner-most loop. bool processLoop(Loop *L) { assert(L->empty() && "Only process inner loops."); @@ -926,11 +786,15 @@ private: // If we need run-time checks to disambiguate pointers are run-time, version // the loop now. auto PtrToPartition = Partitions.computePartitionSetForPointers(LAI); - LoopVersioning LVer(LAI, L, LI, DT, &PtrToPartition); - if (LVer.needsRuntimeChecks()) { + const auto *RtPtrChecking = LAI.getRuntimePointerChecking(); + const auto &AllChecks = RtPtrChecking->getChecks(); + auto Checks = includeOnlyCrossPartitionChecks(AllChecks, PtrToPartition, + RtPtrChecking); + if (!Checks.empty()) { DEBUG(dbgs() << "\nPointers:\n"); - DEBUG(LAI.getRuntimePointerCheck()->print(dbgs(), 0, &PtrToPartition)); - LVer.versionLoop(this); + DEBUG(LAI.getRuntimePointerChecking()->printChecks(dbgs(), Checks)); + LoopVersioning LVer(std::move(Checks), LAI, L, LI, DT); + LVer.versionLoop(); LVer.addPHINodes(DefsUsedOutside); }