summaryrefslogtreecommitdiffstats
path: root/contrib/llvm/lib/Transforms/Scalar/LoopDistribute.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'contrib/llvm/lib/Transforms/Scalar/LoopDistribute.cpp')
-rw-r--r--contrib/llvm/lib/Transforms/Scalar/LoopDistribute.cpp193
1 files changed, 8 insertions, 185 deletions
diff --git a/contrib/llvm/lib/Transforms/Scalar/LoopDistribute.cpp b/contrib/llvm/lib/Transforms/Scalar/LoopDistribute.cpp
index 0325d26..1b9859b 100644
--- a/contrib/llvm/lib/Transforms/Scalar/LoopDistribute.cpp
+++ b/contrib/llvm/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 <list>
#define LDIST_NAME "loop-distribute"
@@ -55,70 +56,6 @@ static cl::opt<bool> DistributeNonIfConvertible(
STATISTIC(NumLoopsDistributed, "Number of loops distributed");
-/// \brief Remaps instructions in a loop including the preheader.
-static void remapInstructionsInLoop(const SmallVectorImpl<BasicBlock *> &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<BasicBlock *> &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<BasicBlock>(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.
@@ -493,15 +432,14 @@ public:
/// partitions its entry is set to -1.
SmallVector<int, 8>
computePartitionSetForPointers(const LoopAccessInfo &LAI) {
- const LoopAccessInfo::RuntimePointerCheck *RtPtrCheck =
- LAI.getRuntimePointerCheck();
+ const RuntimePointerChecking *RtPtrCheck = LAI.getRuntimePointerChecking();
unsigned N = RtPtrCheck->Pointers.size();
SmallVector<int, 8> 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 +567,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<int, 8> *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<BasicBlock *, 8> 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<Instruction *> &DefsUsedOutside) {
- BasicBlock *PHIBlock = VersionedLoop->getExitBlock();
- assert(PHIBlock && "No single successor to loop exit block");
-
- for (auto *Inst : DefsUsedOutside) {
- auto *NonVersionedLoopInst = cast<Instruction>(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<PHINode>(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<Instruction>(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<int, 8> *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<Instruction *, 8> findDefsUsedOutsideOfLoop(Loop *L) {
SmallVector<Instruction *, 8> UsedOutside;
@@ -929,7 +752,7 @@ private:
LoopVersioning LVer(LAI, L, LI, DT, &PtrToPartition);
if (LVer.needsRuntimeChecks()) {
DEBUG(dbgs() << "\nPointers:\n");
- DEBUG(LAI.getRuntimePointerCheck()->print(dbgs(), 0, &PtrToPartition));
+ DEBUG(LAI.getRuntimePointerChecking()->print(dbgs(), 0, &PtrToPartition));
LVer.versionLoop(this);
LVer.addPHINodes(DefsUsedOutside);
}
OpenPOWER on IntegriCloud