From 6a0dc079efe7acf7e71cc4c0948fe814f35ba091 Mon Sep 17 00:00:00 2001 From: Jakob Stoklund Olesen Date: Tue, 20 Jul 2010 21:46:58 +0000 Subject: Implement loop splitting analysis. Determine which loop exit blocks need a 'pre-exit' block inserted. Recognize when this would be impossible. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@108941 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Analysis/LoopInfo.h | 6 ++ lib/CodeGen/SplitKit.cpp | 166 ++++++++++++++++++++++++++++++++++----- lib/CodeGen/SplitKit.h | 36 ++++++++- 3 files changed, 189 insertions(+), 19 deletions(-) diff --git a/include/llvm/Analysis/LoopInfo.h b/include/llvm/Analysis/LoopInfo.h index b101f32..5dfdc25 100644 --- a/include/llvm/Analysis/LoopInfo.h +++ b/include/llvm/Analysis/LoopInfo.h @@ -509,6 +509,12 @@ protected: } }; +template +raw_ostream& operator<<(raw_ostream &OS, const LoopBase &Loop) { + Loop.print(OS); + return OS; +} + class Loop : public LoopBase { public: Loop() {} diff --git a/lib/CodeGen/SplitKit.cpp b/lib/CodeGen/SplitKit.cpp index b62fabc..897b2a4 100644 --- a/lib/CodeGen/SplitKit.cpp +++ b/lib/CodeGen/SplitKit.cpp @@ -18,11 +18,17 @@ #include "llvm/CodeGen/MachineFunctionPass.h" #include "llvm/CodeGen/MachineLoopInfo.h" #include "llvm/CodeGen/MachineRegisterInfo.h" +#include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" +#include "llvm/Target/TargetInstrInfo.h" +#include "llvm/Target/TargetMachine.h" using namespace llvm; +static cl::opt +AllowSplit("spiller-splits-edges", + cl::desc("Allow critical edge splitting during spilling")); //===----------------------------------------------------------------------===// // Split Analysis @@ -34,6 +40,7 @@ SplitAnalysis::SplitAnalysis(const MachineFunction *mf, : mf_(*mf), lis_(*lis), loops_(*mli), + tii_(*mf->getTarget().getInstrInfo()), curli_(0) {} void SplitAnalysis::clear() { @@ -42,6 +49,12 @@ void SplitAnalysis::clear() { usingLoops_.clear(); } +bool SplitAnalysis::canAnalyzeBranch(const MachineBasicBlock *MBB) { + MachineBasicBlock *T, *F; + SmallVector Cond; + return !tii_.AnalyzeBranch(const_cast(*MBB), T, F, Cond); +} + /// analyzeUses - Count instructions, basic blocks, and loops using curli. void SplitAnalysis::analyzeUses() { const MachineRegisterInfo &MRI = mf_.getRegInfo(); @@ -62,29 +75,49 @@ void SplitAnalysis::analyzeUses() { << *curli_ << "\n"); } -SplitAnalysis::LoopPeripheralUse -SplitAnalysis::analyzeLoopPeripheralUse(const MachineLoop *Loop) { - // Peripheral blocks. - SmallVector Peri; - Loop->getExitBlocks(Peri); - if (MachineBasicBlock *PredBB = Loop->getLoopPredecessor()) - Peri.push_back(PredBB); - array_pod_sort(Peri.begin(), Peri.end()); - Peri.erase(std::unique(Peri.begin(), Peri.end()), Peri.end()); +// Get three sets of basic blocks surrounding a loop: Blocks inside the loop, +// predecessor blocks, and exit blocks. +void SplitAnalysis::getLoopBlocks(const MachineLoop *Loop, LoopBlocks &Blocks) { + Blocks.clear(); + + // Blocks in the loop. + Blocks.Loop.insert(Loop->block_begin(), Loop->block_end()); + + // Predecessor blocks. + const MachineBasicBlock *Header = Loop->getHeader(); + for (MachineBasicBlock::const_pred_iterator I = Header->pred_begin(), + E = Header->pred_end(); I != E; ++I) + if (!Blocks.Loop.count(*I)) + Blocks.Preds.insert(*I); + // Exit blocks. + for (MachineLoop::block_iterator I = Loop->block_begin(), + E = Loop->block_end(); I != E; ++I) { + const MachineBasicBlock *MBB = *I; + for (MachineBasicBlock::const_succ_iterator SI = MBB->succ_begin(), + SE = MBB->succ_end(); SI != SE; ++SI) + if (!Blocks.Loop.count(*SI)) + Blocks.Exits.insert(*SI); + } +} + +/// analyzeLoopPeripheralUse - Return an enum describing how curli_ is used in +/// and around the Loop. +SplitAnalysis::LoopPeripheralUse SplitAnalysis:: +analyzeLoopPeripheralUse(const SplitAnalysis::LoopBlocks &Blocks) { LoopPeripheralUse use = ContainedInLoop; for (BlockCountMap::iterator I = usingBlocks_.begin(), E = usingBlocks_.end(); I != E; ++I) { const MachineBasicBlock *MBB = I->first; // Is this a peripheral block? if (use < MultiPeripheral && - std::binary_search(Peri.begin(), Peri.end(), MBB)) { + (Blocks.Preds.count(MBB) || Blocks.Exits.count(MBB))) { if (I->second > 1) use = MultiPeripheral; else use = SinglePeripheral; continue; } // Is it a loop block? - if (Loop->contains(MBB)) + if (Blocks.Loop.count(MBB)) continue; // It must be an unrelated block. return OutsideLoop; @@ -92,6 +125,80 @@ SplitAnalysis::analyzeLoopPeripheralUse(const MachineLoop *Loop) { return use; } +/// getCriticalExits - It may be necessary to partially break critical edges +/// leaving the loop if an exit block has phi uses of curli. Collect the exit +/// blocks that need special treatment into CriticalExits. +void SplitAnalysis::getCriticalExits(const SplitAnalysis::LoopBlocks &Blocks, + BlockPtrSet &CriticalExits) { + CriticalExits.clear(); + + // A critical exit block contains a phi def of curli, and has a predecessor + // that is not in the loop nor a loop predecessor. + // For such an exit block, the edges carrying the new variable must be moved + // to a new pre-exit block. + for (BlockPtrSet::iterator I = Blocks.Exits.begin(), E = Blocks.Exits.end(); + I != E; ++I) { + const MachineBasicBlock *Succ = *I; + SlotIndex SuccIdx = lis_.getMBBStartIdx(Succ); + VNInfo *SuccVNI = curli_->getVNInfoAt(SuccIdx); + // This exit may not have curli live in at all. No need to split. + if (!SuccVNI) + continue; + // If this is not a PHI def, it is either using a value from before the + // loop, or a value defined inside the loop. Both are safe. + if (!SuccVNI->isPHIDef() || SuccVNI->def.getBaseIndex() != SuccIdx) + continue; + // This exit block does have a PHI. Does it also have a predecessor that is + // not a loop block or loop predecessor? + for (MachineBasicBlock::const_pred_iterator PI = Succ->pred_begin(), + PE = Succ->pred_end(); PI != PE; ++PI) { + const MachineBasicBlock *Pred = *PI; + if (Blocks.Loop.count(Pred) || Blocks.Preds.count(Pred)) + continue; + // This is a critical exit block, and we need to split the exit edge. + CriticalExits.insert(Succ); + break; + } + } +} + +/// canSplitCriticalExits - Return true if it is possible to insert new exit +/// blocks before the blocks in CriticalExits. +bool +SplitAnalysis::canSplitCriticalExits(const SplitAnalysis::LoopBlocks &Blocks, + BlockPtrSet &CriticalExits) { + // If we don't allow critical edge splitting, require no critical exits. + if (!AllowSplit) + return CriticalExits.empty(); + + for (BlockPtrSet::iterator I = CriticalExits.begin(), E = CriticalExits.end(); + I != E; ++I) { + const MachineBasicBlock *Succ = *I; + // We want to insert a new pre-exit MBB before Succ, and change all the + // in-loop blocks to branch to the pre-exit instead of Succ. + // Check that all the in-loop predecessors can be changed. + for (MachineBasicBlock::const_pred_iterator PI = Succ->pred_begin(), + PE = Succ->pred_end(); PI != PE; ++PI) { + const MachineBasicBlock *Pred = *PI; + // The external predecessors won't be altered. + if (!Blocks.Loop.count(Pred) && !Blocks.Preds.count(Pred)) + continue; + if (!canAnalyzeBranch(Pred)) + return false; + } + + // If Succ's layout predecessor falls through, that too must be analyzable. + // We need to insert the pre-exit block in the gap. + MachineFunction::const_iterator MFI = Succ; + if (MFI == mf_.begin()) + continue; + if (!canAnalyzeBranch(--MFI)) + return false; + } + // No problems found. + return true; +} + void SplitAnalysis::analyze(const LiveInterval *li) { clear(); curli_ = li; @@ -99,22 +206,46 @@ void SplitAnalysis::analyze(const LiveInterval *li) { } const MachineLoop *SplitAnalysis::getBestSplitLoop() { + assert(curli_ && "Call analyze() before getBestSplitLoop"); + if (usingLoops_.empty()) + return 0; + LoopPtrSet Loops, SecondLoops; + LoopBlocks Blocks; + BlockPtrSet CriticalExits; // Find first-class and second class candidate loops. // We prefer to split around loops where curli is used outside the periphery. for (LoopPtrSet::const_iterator I = usingLoops_.begin(), - E = usingLoops_.end(); I != E; ++I) - switch(analyzeLoopPeripheralUse(*I)) { + E = usingLoops_.end(); I != E; ++I) { + getLoopBlocks(*I, Blocks); + LoopPtrSet *LPS = 0; + switch(analyzeLoopPeripheralUse(Blocks)) { case OutsideLoop: - Loops.insert(*I); + LPS = &Loops; break; case MultiPeripheral: - SecondLoops.insert(*I); + LPS = &SecondLoops; break; - default: + case ContainedInLoop: + DEBUG(dbgs() << "ContainedInLoop: " << **I); + continue; + case SinglePeripheral: + DEBUG(dbgs() << "SinglePeripheral: " << **I); continue; } + // Will it be possible to split around this loop? + getCriticalExits(Blocks, CriticalExits); + DEBUG(dbgs() << CriticalExits.size() << " critical exits: " << **I); + if (!canSplitCriticalExits(Blocks, CriticalExits)) + continue; + // This is a possible split. + assert(LPS); + LPS->insert(*I); + } + + DEBUG(dbgs() << "Got " << Loops.size() << " + " << SecondLoops.size() + << " candidate loops\n"); // If there are no first class loops available, look at second class loops. if (Loops.empty()) @@ -125,8 +256,6 @@ const MachineLoop *SplitAnalysis::getBestSplitLoop() { // Pick the earliest loop. // FIXME: Are there other heuristics to consider? - // - avoid breaking critical edges. - // - avoid impossible loops. const MachineLoop *Best = 0; SlotIndex BestIdx; for (LoopPtrSet::const_iterator I = Loops.begin(), E = Loops.end(); I != E; @@ -135,6 +264,7 @@ const MachineLoop *SplitAnalysis::getBestSplitLoop() { if (!Best || Idx < BestIdx) Best = *I, BestIdx = Idx; } + DEBUG(dbgs() << "Best: " << *Best); return Best; } diff --git a/lib/CodeGen/SplitKit.h b/lib/CodeGen/SplitKit.h index 3d76772..d567c04 100644 --- a/lib/CodeGen/SplitKit.h +++ b/lib/CodeGen/SplitKit.h @@ -25,11 +25,13 @@ class MachineFunction; class MachineFunctionPass; class MachineLoop; class MachineLoopInfo; +class TargetInstrInfo; class SplitAnalysis { const MachineFunction &mf_; const LiveIntervals &lis_; const MachineLoopInfo &loops_; + const TargetInstrInfo &tii_; // Current live interval. const LiveInterval *curli_; @@ -49,6 +51,10 @@ class SplitAnalysis { // Sumarize statistics by counting instructions using curli_. void analyzeUses(); + /// canAnalyzeBranch - Return true if MBB ends in a branch that can be + /// analyzed. + bool canAnalyzeBranch(const MachineBasicBlock *MBB); + public: SplitAnalysis(const MachineFunction *mf, const LiveIntervals *lis, const MachineLoopInfo *mli); @@ -61,6 +67,24 @@ public: /// new interval. void clear(); + typedef SmallPtrSet BlockPtrSet; + + // Sets of basic blocks surrounding a machine loop. + struct LoopBlocks { + BlockPtrSet Loop; // Blocks in the loop. + BlockPtrSet Preds; // Loop predecessor blocks. + BlockPtrSet Exits; // Loop exit blocks. + + void clear() { + Loop.clear(); + Preds.clear(); + Exits.clear(); + } + }; + + // Calculate the block sets surrounding the loop. + void getLoopBlocks(const MachineLoop *Loop, LoopBlocks &Blocks); + /// LoopPeripheralUse - how is a variable used in and around a loop? /// Peripheral blocks are the loop predecessors and exit blocks. enum LoopPeripheralUse { @@ -72,7 +96,17 @@ public: /// analyzeLoopPeripheralUse - Return an enum describing how curli_ is used in /// and around the Loop. - LoopPeripheralUse analyzeLoopPeripheralUse(const MachineLoop*); + LoopPeripheralUse analyzeLoopPeripheralUse(const LoopBlocks&); + + /// getCriticalExits - It may be necessary to partially break critical edges + /// leaving the loop if an exit block has phi uses of curli. Collect the exit + /// blocks that need special treatment into CriticalExits. + void getCriticalExits(const LoopBlocks &Blocks, BlockPtrSet &CriticalExits); + + /// canSplitCriticalExits - Return true if it is possible to insert new exit + /// blocks before the blocks in CriticalExits. + bool canSplitCriticalExits(const LoopBlocks &Blocks, + BlockPtrSet &CriticalExits); /// getBestSplitLoop - Return the loop where curli may best be split to a /// separate register, or NULL. -- cgit v1.1