From 60f422f894ae9aff2f508f34733be36f5a0ed20a Mon Sep 17 00:00:00 2001 From: Lang Hames Date: Sat, 17 Jul 2010 07:34:01 +0000 Subject: [PATCH] LoopSplitter - intended to split live intervals over loop boundaries. Still very much under development. Comments and fixes will be forthcoming. (This commit includes some small tweaks to LiveIntervals & LoopInfo to support the splitter) git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@108615 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Analysis/LoopInfo.h | 9 +- include/llvm/CodeGen/LiveIntervalAnalysis.h | 24 + lib/CodeGen/Splitter.cpp | 819 ++++++++++++++++++++++++++++ lib/CodeGen/Splitter.h | 99 ++++ 4 files changed, 948 insertions(+), 3 deletions(-) create mode 100644 lib/CodeGen/Splitter.cpp create mode 100644 lib/CodeGen/Splitter.h diff --git a/include/llvm/Analysis/LoopInfo.h b/include/llvm/Analysis/LoopInfo.h index 9455fd84032..2d93909d19b 100644 --- a/include/llvm/Analysis/LoopInfo.h +++ b/include/llvm/Analysis/LoopInfo.h @@ -229,9 +229,12 @@ public: return 0; } + /// Edge type. + typedef std::pair Edge; + /// getExitEdges - Return all pairs of (_inside_block_,_outside_block_). - typedef std::pair Edge; - void getExitEdges(SmallVectorImpl &ExitEdges) const { + template + void getExitEdges(SmallVectorImpl &ExitEdges) const { // Sort the blocks vector so that we can use binary search to do quick // lookups. SmallVector LoopBBs(block_begin(), block_end()); @@ -244,7 +247,7 @@ public: I != E; ++I) if (!std::binary_search(LoopBBs.begin(), LoopBBs.end(), *I)) // Not in current loop? It must be an exit block. - ExitEdges.push_back(std::make_pair(*BI, *I)); + ExitEdges.push_back(EdgeT(*BI, *I)); } /// getLoopPreheader - If there is a preheader for this loop, return it. A diff --git a/include/llvm/CodeGen/LiveIntervalAnalysis.h b/include/llvm/CodeGen/LiveIntervalAnalysis.h index c136048c9c7..8a59bf1428a 100644 --- a/include/llvm/CodeGen/LiveIntervalAnalysis.h +++ b/include/llvm/CodeGen/LiveIntervalAnalysis.h @@ -197,6 +197,26 @@ namespace llvm { return indexes_->getMBBEndIdx(mbb); } + bool isLiveInToMBB(const LiveInterval &li, + const MachineBasicBlock *mbb) const { + return li.liveAt(getMBBStartIdx(mbb)); + } + + LiveRange* findEnteringRange(LiveInterval &li, + const MachineBasicBlock *mbb) { + return li.getLiveRangeContaining(getMBBStartIdx(mbb)); + } + + bool isLiveOutOfMBB(const LiveInterval &li, + const MachineBasicBlock *mbb) const { + return li.liveAt(getMBBEndIdx(mbb).getPrevSlot()); + } + + LiveRange* findExitingRange(LiveInterval &li, + const MachineBasicBlock *mbb) { + return li.getLiveRangeContaining(getMBBEndIdx(mbb).getPrevSlot()); + } + MachineBasicBlock* getMBBFromIndex(SlotIndex index) const { return indexes_->getMBBFromIndex(index); } @@ -217,6 +237,10 @@ namespace llvm { indexes_->replaceMachineInstrInMaps(MI, NewMI); } + void InsertMBBInMaps(MachineBasicBlock *MBB) { + indexes_->insertMBBInMaps(MBB); + } + bool findLiveInMBBs(SlotIndex Start, SlotIndex End, SmallVectorImpl &MBBs) const { return indexes_->findLiveInMBBs(Start, End, MBBs); diff --git a/lib/CodeGen/Splitter.cpp b/lib/CodeGen/Splitter.cpp new file mode 100644 index 00000000000..c2f2591fa64 --- /dev/null +++ b/lib/CodeGen/Splitter.cpp @@ -0,0 +1,819 @@ +//===-- llvm/CodeGen/Splitter.cpp - Splitter -----------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#define DEBUG_TYPE "loopsplitter" + +#include "Splitter.h" + +#include "SimpleRegisterCoalescing.h" +#include "llvm/Module.h" +#include "llvm/CodeGen/CalcSpillWeights.h" +#include "llvm/CodeGen/LiveIntervalAnalysis.h" +#include "llvm/CodeGen/LiveStackAnalysis.h" +#include "llvm/CodeGen/MachineDominators.h" +#include "llvm/CodeGen/MachineInstrBuilder.h" +#include "llvm/CodeGen/MachineFunction.h" +#include "llvm/CodeGen/MachineRegisterInfo.h" +#include "llvm/CodeGen/SlotIndexes.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/raw_ostream.h" +#include "llvm/Target/TargetMachine.h" +#include "llvm/Target/TargetInstrInfo.h" + +using namespace llvm; + +char LoopSplitter::ID = 0; +static RegisterPass +X("loop-splitting", "Split virtual regists across loop boundaries."); + +namespace llvm { + + class StartSlotComparator { + public: + StartSlotComparator(LiveIntervals &lis) : lis(lis) {} + bool operator()(const MachineBasicBlock *mbb1, + const MachineBasicBlock *mbb2) const { + return lis.getMBBStartIdx(mbb1) < lis.getMBBStartIdx(mbb2); + } + private: + LiveIntervals &lis; + }; + + class LoopSplit { + public: + LoopSplit(LoopSplitter &ls, LiveInterval &li, MachineLoop &loop) + : ls(ls), li(li), loop(loop), valid(true), inSplit(false), newLI(0) { + assert(TargetRegisterInfo::isVirtualRegister(li.reg) && + "Cannot split physical registers."); + } + + LiveInterval& getLI() const { return li; } + + MachineLoop& getLoop() const { return loop; } + + bool isValid() const { return valid; } + + bool isWorthwhile() const { return valid && (inSplit || !outSplits.empty()); } + + void invalidate() { valid = false; } + + void splitIncoming() { inSplit = true; } + + void splitOutgoing(MachineLoop::Edge &edge) { outSplits.insert(edge); } + + void addLoopInstr(MachineInstr *i) { loopInstrs.push_back(i); } + + void apply() { + assert(valid && "Attempt to apply invalid split."); + applyIncoming(); + applyOutgoing(); + copyRanges(); + renameInside(); + } + + private: + LoopSplitter &ls; + LiveInterval &li; + MachineLoop &loop; + bool valid, inSplit; + std::set outSplits; + std::vector loopInstrs; + + LiveInterval *newLI; + std::map vniMap; + + LiveInterval* getNewLI() { + if (newLI == 0) { + const TargetRegisterClass *trc = ls.mri->getRegClass(li.reg); + unsigned vreg = ls.mri->createVirtualRegister(trc); + newLI = &ls.lis->getOrCreateInterval(vreg); + } + return newLI; + } + + VNInfo* getNewVNI(VNInfo *oldVNI) { + VNInfo *newVNI = vniMap[oldVNI]; + + if (newVNI == 0) { + newVNI = getNewLI()->createValueCopy(oldVNI, + ls.lis->getVNInfoAllocator()); + vniMap[oldVNI] = newVNI; + } + + return newVNI; + } + + void applyIncoming() { + if (!inSplit) { + return; + } + + MachineBasicBlock *preHeader = loop.getLoopPreheader(); + if (preHeader == 0) { + assert(ls.canInsertPreHeader(loop) && + "Can't insert required preheader."); + preHeader = &ls.insertPreHeader(loop); + } + + LiveRange *preHeaderRange = + ls.lis->findExitingRange(li, preHeader); + assert(preHeaderRange != 0 && "Range not live into preheader."); + + // Insert the new copy. + MachineInstr *copy = BuildMI(*preHeader, + preHeader->getFirstTerminator(), + DebugLoc(), + ls.tii->get(TargetOpcode::COPY)) + .addReg(getNewLI()->reg, RegState::Define) + .addReg(li.reg, RegState::Kill); + + ls.lis->InsertMachineInstrInMaps(copy); + + SlotIndex copyDefIdx = ls.lis->getInstructionIndex(copy).getDefIndex(); + + VNInfo *newVal = getNewVNI(preHeaderRange->valno); + newVal->def = copyDefIdx; + newVal->setCopy(copy); + newVal->setIsDefAccurate(true); + li.removeRange(copyDefIdx, ls.lis->getMBBEndIdx(preHeader), true); + + getNewLI()->addRange(LiveRange(copyDefIdx, + ls.lis->getMBBEndIdx(preHeader), + newVal)); + } + + void applyOutgoing() { + + for (std::set::iterator osItr = outSplits.begin(), + osEnd = outSplits.end(); + osItr != osEnd; ++osItr) { + MachineLoop::Edge edge = *osItr; + MachineBasicBlock *outBlock = edge.second; + if (ls.isCriticalEdge(edge)) { + assert(ls.canSplitEdge(edge) && "Unsplitable critical edge."); + outBlock = &ls.splitEdge(edge, loop); + } + LiveRange *outRange = ls.lis->findEnteringRange(li, outBlock); + assert(outRange != 0 && "No exiting range?"); + + MachineInstr *copy = BuildMI(*outBlock, outBlock->begin(), + DebugLoc(), + ls.tii->get(TargetOpcode::COPY)) + .addReg(li.reg, RegState::Define) + .addReg(getNewLI()->reg, RegState::Kill); + + ls.lis->InsertMachineInstrInMaps(copy); + + SlotIndex copyDefIdx = ls.lis->getInstructionIndex(copy).getDefIndex(); + + // Blow away output range definition. + outRange->valno->def = ls.lis->getInvalidIndex(); + outRange->valno->setIsDefAccurate(false); + li.removeRange(ls.lis->getMBBStartIdx(outBlock), copyDefIdx); + + VNInfo *newVal = + getNewLI()->getNextValue(SlotIndex(ls.lis->getMBBStartIdx(outBlock), + true), + 0, false, ls.lis->getVNInfoAllocator()); + + getNewLI()->addRange(LiveRange(ls.lis->getMBBStartIdx(outBlock), + copyDefIdx, newVal)); + + } + } + + void copyRange(LiveRange &lr) { + std::pair lsr = + ls.getLoopSubRange(lr, loop); + + if (!lsr.first) + return; + + LiveRange loopRange(lsr.second.first, lsr.second.second, + getNewVNI(lr.valno)); + + li.removeRange(loopRange.start, loopRange.end, true); + + getNewLI()->addRange(loopRange); + } + + void copyRanges() { + for (std::vector::iterator iItr = loopInstrs.begin(), + iEnd = loopInstrs.end(); + iItr != iEnd; ++iItr) { + MachineInstr &instr = **iItr; + SlotIndex instrIdx = ls.lis->getInstructionIndex(&instr); + if (instr.modifiesRegister(li.reg, 0)) { + LiveRange *defRange = + li.getLiveRangeContaining(instrIdx.getDefIndex()); + if (defRange != 0) // May have caught this already. + copyRange(*defRange); + } + if (instr.readsRegister(li.reg, 0)) { + LiveRange *useRange = + li.getLiveRangeContaining(instrIdx.getUseIndex()); + if (useRange != 0) { // May have caught this already. + copyRange(*useRange); + } + } + } + + for (MachineLoop::block_iterator bbItr = loop.block_begin(), + bbEnd = loop.block_end(); + bbItr != bbEnd; ++bbItr) { + MachineBasicBlock &loopBlock = **bbItr; + LiveRange *enteringRange = + ls.lis->findEnteringRange(li, &loopBlock); + if (enteringRange != 0) { + copyRange(*enteringRange); + } + } + } + + void renameInside() { + for (std::vector::iterator iItr = loopInstrs.begin(), + iEnd = loopInstrs.end(); + iItr != iEnd; ++iItr) { + MachineInstr &instr = **iItr; + for (unsigned i = 0; i < instr.getNumOperands(); ++i) { + MachineOperand &mop = instr.getOperand(i); + if (mop.isReg() && mop.getReg() == li.reg) { + mop.setReg(getNewLI()->reg); + } + } + } + } + + }; + + void LoopSplitter::getAnalysisUsage(AnalysisUsage &au) const { + au.addRequired(); + au.addPreserved(); + au.addRequired(); + au.addPreserved(); + au.addPreserved(); + au.addPreserved(); + au.addPreserved(); + au.addRequired(); + au.addPreserved(); + au.addRequired(); + au.addPreserved(); + MachineFunctionPass::getAnalysisUsage(au); + } + + bool LoopSplitter::runOnMachineFunction(MachineFunction &fn) { + + mf = &fn; + mri = &mf->getRegInfo(); + tii = mf->getTarget().getInstrInfo(); + tri = mf->getTarget().getRegisterInfo(); + sis = &getAnalysis(); + lis = &getAnalysis(); + mli = &getAnalysis(); + mdt = &getAnalysis(); + + fqn = mf->getFunction()->getParent()->getModuleIdentifier() + "." + + mf->getFunction()->getName().str(); + + dbgs() << "Splitting " << mf->getFunction()->getName() << "."; + + dumpOddTerminators(); + +// dbgs() << "----------------------------------------\n"; +// lis->dump(); +// dbgs() << "----------------------------------------\n"; + +// std::deque loops; +// std::copy(mli->begin(), mli->end(), std::back_inserter(loops)); +// dbgs() << "Loops:\n"; +// while (!loops.empty()) { +// MachineLoop &loop = *loops.front(); +// loops.pop_front(); +// std::copy(loop.begin(), loop.end(), std::back_inserter(loops)); + +// dumpLoopInfo(loop); +// } + + //lis->dump(); + //exit(0); + + // Setup initial intervals. + for (LiveIntervals::iterator liItr = lis->begin(), liEnd = lis->end(); + liItr != liEnd; ++liItr) { + LiveInterval *li = liItr->second; + + if (TargetRegisterInfo::isVirtualRegister(li->reg) && + !lis->intervalIsInOneMBB(*li)) { + intervals.push_back(li); + } + } + + processIntervals(); + + intervals.clear(); + +// dbgs() << "----------------------------------------\n"; +// lis->dump(); +// dbgs() << "----------------------------------------\n"; + + dumpOddTerminators(); + + //exit(1); + + return false; + } + + void LoopSplitter::releaseMemory() { + fqn.clear(); + intervals.clear(); + loopRangeMap.clear(); + } + + void LoopSplitter::dumpOddTerminators() { + for (MachineFunction::iterator bbItr = mf->begin(), bbEnd = mf->end(); + bbItr != bbEnd; ++bbItr) { + MachineBasicBlock *mbb = &*bbItr; + MachineBasicBlock *a = 0, *b = 0; + SmallVector c; + if (tii->AnalyzeBranch(*mbb, a, b, c)) { + dbgs() << "MBB#" << mbb->getNumber() << " has multiway terminator.\n"; + dbgs() << " Terminators:\n"; + for (MachineBasicBlock::iterator iItr = mbb->begin(), iEnd = mbb->end(); + iItr != iEnd; ++iItr) { + MachineInstr *instr= &*iItr; + dbgs() << " " << *instr << ""; + } + dbgs() << "\n Listed successors: [ "; + for (MachineBasicBlock::succ_iterator sItr = mbb->succ_begin(), sEnd = mbb->succ_end(); + sItr != sEnd; ++sItr) { + MachineBasicBlock *succMBB = *sItr; + dbgs() << succMBB->getNumber() << " "; + } + dbgs() << "]\n\n"; + } + } + } + + void LoopSplitter::dumpLoopInfo(MachineLoop &loop) { + MachineBasicBlock &headerBlock = *loop.getHeader(); + typedef SmallVector ExitEdgesList; + ExitEdgesList exitEdges; + loop.getExitEdges(exitEdges); + + dbgs() << " Header: BB#" << headerBlock.getNumber() << ", Contains: [ "; + for (std::vector::const_iterator + subBlockItr = loop.getBlocks().begin(), + subBlockEnd = loop.getBlocks().end(); + subBlockItr != subBlockEnd; ++subBlockItr) { + MachineBasicBlock &subBlock = **subBlockItr; + dbgs() << "BB#" << subBlock.getNumber() << " "; + } + dbgs() << "], Exit edges: [ "; + for (ExitEdgesList::iterator exitEdgeItr = exitEdges.begin(), + exitEdgeEnd = exitEdges.end(); + exitEdgeItr != exitEdgeEnd; ++exitEdgeItr) { + MachineLoop::Edge &exitEdge = *exitEdgeItr; + dbgs() << "(MBB#" << exitEdge.first->getNumber() + << ", MBB#" << exitEdge.second->getNumber() << ") "; + } + dbgs() << "], Sub-Loop Headers: [ "; + for (MachineLoop::iterator subLoopItr = loop.begin(), + subLoopEnd = loop.end(); + subLoopItr != subLoopEnd; ++subLoopItr) { + MachineLoop &subLoop = **subLoopItr; + MachineBasicBlock &subLoopBlock = *subLoop.getHeader(); + dbgs() << "BB#" << subLoopBlock.getNumber() << " "; + } + dbgs() << "]\n"; + } + + void LoopSplitter::updateTerminators(MachineBasicBlock &mbb) { + mbb.updateTerminator(); + + for (MachineBasicBlock::iterator miItr = mbb.begin(), miEnd = mbb.end(); + miItr != miEnd; ++miItr) { + if (lis->isNotInMIMap(miItr)) { + lis->InsertMachineInstrInMaps(miItr); + } + } + } + + bool LoopSplitter::canInsertPreHeader(MachineLoop &loop) { + MachineBasicBlock *header = loop.getHeader(); + MachineBasicBlock *a = 0, *b = 0; + SmallVector c; + + for (MachineBasicBlock::pred_iterator pbItr = header->pred_begin(), + pbEnd = header->pred_end(); + pbItr != pbEnd; ++pbItr) { + MachineBasicBlock *predBlock = *pbItr; + if (!!tii->AnalyzeBranch(*predBlock, a, b, c)) { + return false; + } + } + + MachineFunction::iterator headerItr(header); + if (headerItr == mf->begin()) + return true; + MachineBasicBlock *headerLayoutPred = llvm::prior(headerItr); + assert(headerLayoutPred != 0 && "Header should have layout pred."); + + return (!tii->AnalyzeBranch(*headerLayoutPred, a, b, c)); + } + + MachineBasicBlock& LoopSplitter::insertPreHeader(MachineLoop &loop) { + assert(loop.getLoopPreheader() == 0 && "Loop already has preheader."); + + MachineBasicBlock &header = *loop.getHeader(); + + // Save the preds - we'll need to update them once we insert the preheader. + typedef std::set HeaderPreds; + HeaderPreds headerPreds; + + for (MachineBasicBlock::pred_iterator predItr = header.pred_begin(), + predEnd = header.pred_end(); + predItr != predEnd; ++predItr) { + if (!loop.contains(*predItr)) + headerPreds.insert(*predItr); + } + + assert(!headerPreds.empty() && "No predecessors for header?"); + + //dbgs() << fqn << " MBB#" << header.getNumber() << " inserting preheader..."; + + MachineBasicBlock *preHeader = + mf->CreateMachineBasicBlock(header.getBasicBlock()); + + assert(preHeader != 0 && "Failed to create pre-header."); + + mf->insert(header, preHeader); + + for (HeaderPreds::iterator hpItr = headerPreds.begin(), + hpEnd = headerPreds.end(); + hpItr != hpEnd; ++hpItr) { + assert(*hpItr != 0 && "How'd a null predecessor get into this set?"); + MachineBasicBlock &hp = **hpItr; + hp.ReplaceUsesOfBlockWith(&header, preHeader); + } + preHeader->addSuccessor(&header); + + MachineBasicBlock *oldLayoutPred = + llvm::prior(MachineFunction::iterator(preHeader)); + if (oldLayoutPred != 0) { + updateTerminators(*oldLayoutPred); + } + + lis->InsertMBBInMaps(preHeader); + + if (MachineLoop *parentLoop = loop.getParentLoop()) { + assert(parentLoop->getHeader() != loop.getHeader() && + "Parent loop has same header?"); + parentLoop->addBasicBlockToLoop(preHeader, mli->getBase()); + + // Invalidate all parent loop ranges. + while (parentLoop != 0) { + loopRangeMap.erase(parentLoop); + parentLoop = parentLoop->getParentLoop(); + } + } + + for (LiveIntervals::iterator liItr = lis->begin(), + liEnd = lis->end(); + liItr != liEnd; ++liItr) { + LiveInterval &li = *liItr->second; + + // Is this safe for physregs? + // TargetRegisterInfo::isPhysicalRegister(li.reg) || + if (!lis->isLiveInToMBB(li, &header)) + continue; + + if (lis->isLiveInToMBB(li, preHeader)) { + assert(lis->isLiveOutOfMBB(li, preHeader) && + "Range terminates in newly added preheader?"); + continue; + } + + bool insertRange = false; + + for (MachineBasicBlock::pred_iterator predItr = preHeader->pred_begin(), + predEnd = preHeader->pred_end(); + predItr != predEnd; ++predItr) { + MachineBasicBlock *predMBB = *predItr; + if (lis->isLiveOutOfMBB(li, predMBB)) { + insertRange = true; + break; + } + } + + if (!insertRange) + continue; + + VNInfo *newVal = li.getNextValue(lis->getMBBStartIdx(preHeader), + 0, false, lis->getVNInfoAllocator()); + li.addRange(LiveRange(lis->getMBBStartIdx(preHeader), + lis->getMBBEndIdx(preHeader), + newVal)); + } + + + //dbgs() << "Dumping SlotIndexes:\n"; + //sis->dump(); + + //dbgs() << "done. (Added MBB#" << preHeader->getNumber() << ")\n"; + + return *preHeader; + } + + bool LoopSplitter::isCriticalEdge(MachineLoop::Edge &edge) { + assert(edge.first->succ_size() > 1 && "Non-sensical edge."); + if (edge.second->pred_size() > 1) + return true; + return false; + } + + bool LoopSplitter::canSplitEdge(MachineLoop::Edge &edge) { + MachineFunction::iterator outBlockItr(edge.second); + if (outBlockItr == mf->begin()) + return true; + MachineBasicBlock *outBlockLayoutPred = llvm::prior(outBlockItr); + assert(outBlockLayoutPred != 0 && "Should have a layout pred if out!=begin."); + MachineBasicBlock *a = 0, *b = 0; + SmallVector c; + return (!tii->AnalyzeBranch(*outBlockLayoutPred, a, b, c) && + !tii->AnalyzeBranch(*edge.first, a, b, c)); + } + + MachineBasicBlock& LoopSplitter::splitEdge(MachineLoop::Edge &edge, + MachineLoop &loop) { + + MachineBasicBlock &inBlock = *edge.first; + MachineBasicBlock &outBlock = *edge.second; + + assert((inBlock.succ_size() > 1) && (outBlock.pred_size() > 1) && + "Splitting non-critical edge?"); + + //dbgs() << fqn << " Splitting edge (MBB#" << inBlock.getNumber() + // << " -> MBB#" << outBlock.getNumber() << ")..."; + + MachineBasicBlock *splitBlock = + mf->CreateMachineBasicBlock(); + + assert(splitBlock != 0 && "Failed to create split block."); + + mf->insert(&outBlock, splitBlock); + + inBlock.ReplaceUsesOfBlockWith(&outBlock, splitBlock); + splitBlock->addSuccessor(&outBlock); + + MachineBasicBlock *oldLayoutPred = + llvm::prior(MachineFunction::iterator(splitBlock)); + if (oldLayoutPred != 0) { + updateTerminators(*oldLayoutPred); + } + + lis->InsertMBBInMaps(splitBlock); + + loopRangeMap.erase(&loop); + + MachineLoop *splitParentLoop = loop.getParentLoop(); + while (splitParentLoop != 0 && + !splitParentLoop->contains(&outBlock)) { + splitParentLoop = splitParentLoop->getParentLoop(); + } + + if (splitParentLoop != 0) { + assert(splitParentLoop->contains(&loop) && + "Split-block parent doesn't contain original loop?"); + splitParentLoop->addBasicBlockToLoop(splitBlock, mli->getBase()); + + // Invalidate all parent loop ranges. + while (splitParentLoop != 0) { + loopRangeMap.erase(splitParentLoop); + splitParentLoop = splitParentLoop->getParentLoop(); + } + } + + + for (LiveIntervals::iterator liItr = lis->begin(), + liEnd = lis->end(); + liItr != liEnd; ++liItr) { + LiveInterval &li = *liItr->second; + bool intersects = lis->isLiveOutOfMBB(li, &inBlock) && + lis->isLiveInToMBB(li, &outBlock); + if (lis->isLiveInToMBB(li, splitBlock)) { + if (!intersects) { + li.removeRange(lis->getMBBStartIdx(splitBlock), + lis->getMBBEndIdx(splitBlock), true); + } + } else if (intersects) { + VNInfo *newVal = li.getNextValue(lis->getMBBStartIdx(splitBlock), + 0, false, lis->getVNInfoAllocator()); + li.addRange(LiveRange(lis->getMBBStartIdx(splitBlock), + lis->getMBBEndIdx(splitBlock), + newVal)); + } + } + + //dbgs() << "done. (Added MBB#" << splitBlock->getNumber() << ")\n"; + + return *splitBlock; + } + + LoopSplitter::LoopRanges& LoopSplitter::getLoopRanges(MachineLoop &loop) { + typedef std::set LoopMBBSet; + LoopRangeMap::iterator lrItr = loopRangeMap.find(&loop); + if (lrItr == loopRangeMap.end()) { + LoopMBBSet loopMBBs((StartSlotComparator(*lis))); + std::copy(loop.block_begin(), loop.block_end(), + std::inserter(loopMBBs, loopMBBs.begin())); + + assert(!loopMBBs.empty() && "No blocks in loop?"); + + LoopRanges &loopRanges = loopRangeMap[&loop]; + assert(loopRanges.empty() && "Loop encountered but not processed?"); + SlotIndex oldEnd = lis->getMBBEndIdx(*loopMBBs.begin()); + loopRanges.push_back( + std::make_pair(lis->getMBBStartIdx(*loopMBBs.begin()), + lis->getInvalidIndex())); + for (LoopMBBSet::iterator curBlockItr = llvm::next(loopMBBs.begin()), + curBlockEnd = loopMBBs.end(); + curBlockItr != curBlockEnd; ++curBlockItr) { + SlotIndex newStart = lis->getMBBStartIdx(*curBlockItr); + if (newStart != oldEnd) { + loopRanges.back().second = oldEnd; + loopRanges.push_back(std::make_pair(newStart, + lis->getInvalidIndex())); + } + oldEnd = lis->getMBBEndIdx(*curBlockItr); + } + + loopRanges.back().second = + lis->getMBBEndIdx(*llvm::prior(loopMBBs.end())); + + return loopRanges; + } + return lrItr->second; + } + + std::pair LoopSplitter::getLoopSubRange( + const LiveRange &lr, + MachineLoop &loop) { + LoopRanges &loopRanges = getLoopRanges(loop); + LoopRanges::iterator lrItr = loopRanges.begin(), + lrEnd = loopRanges.end(); + while (lrItr != lrEnd && lr.start >= lrItr->second) { + ++lrItr; + } + + if (lrItr == lrEnd) { + SlotIndex invalid = lis->getInvalidIndex(); + return std::make_pair(false, SlotPair(invalid, invalid)); + } + + SlotIndex srStart(lr.start < lrItr->first ? lrItr->first : lr.start); + SlotIndex srEnd(lr.end > lrItr->second ? lrItr->second : lr.end); + + return std::make_pair(true, SlotPair(srStart, srEnd)); + } + + void LoopSplitter::dumpLoopRanges(MachineLoop &loop) { + LoopRanges &loopRanges = getLoopRanges(loop); + dbgs() << "For loop MBB#" << loop.getHeader()->getNumber() << ", subranges are: [ "; + for (LoopRanges::iterator lrItr = loopRanges.begin(), lrEnd = loopRanges.end(); + lrItr != lrEnd; ++lrItr) { + dbgs() << "[" << lrItr->first << ", " << lrItr->second << ") "; + } + dbgs() << "]\n"; + } + + void LoopSplitter::processHeader(LoopSplit &split) { + MachineBasicBlock &header = *split.getLoop().getHeader(); + //dbgs() << " Processing loop header BB#" << header.getNumber() << "\n"; + + if (!lis->isLiveInToMBB(split.getLI(), &header)) + return; // Not live in, but nothing wrong so far. + + MachineBasicBlock *preHeader = split.getLoop().getLoopPreheader(); + if (!preHeader) { + + if (!canInsertPreHeader(split.getLoop())) { + split.invalidate(); + return; // Couldn't insert a pre-header. Bail on this interval. + } + + for (MachineBasicBlock::pred_iterator predItr = header.pred_begin(), + predEnd = header.pred_end(); + predItr != predEnd; ++predItr) { + if (lis->isLiveOutOfMBB(split.getLI(), *predItr)) { + split.splitIncoming(); + break; + } + } + } else if (lis->isLiveOutOfMBB(split.getLI(), preHeader)) { + split.splitIncoming(); + } + } + + void LoopSplitter::processLoopExits(LoopSplit &split) { + typedef SmallVector ExitEdgesList; + ExitEdgesList exitEdges; + split.getLoop().getExitEdges(exitEdges); + + //dbgs() << " Processing loop exits:\n"; + + for (ExitEdgesList::iterator exitEdgeItr = exitEdges.begin(), + exitEdgeEnd = exitEdges.end(); + exitEdgeItr != exitEdgeEnd; ++exitEdgeItr) { + MachineLoop::Edge exitEdge = *exitEdgeItr; + + LiveRange *inRange = + split.getLI().getLiveRangeContaining(lis->getMBBEndIdx(exitEdge.first).getPrevSlot()); + LiveRange *outRange = + split.getLI().getLiveRangeContaining(lis->getMBBStartIdx(exitEdge.second)); + + if (outRange != 0) { + if (isCriticalEdge(exitEdge) && !canSplitEdge(exitEdge)) { + split.invalidate(); + return; + } + + split.splitOutgoing(exitEdge); + } + } + } + + void LoopSplitter::processLoopUses(LoopSplit &split) { + std::set processed; + + for (MachineRegisterInfo::reg_iterator + rItr = mri->reg_begin(split.getLI().reg), + rEnd = mri->reg_end(); + rItr != rEnd; ++rItr) { + MachineInstr &instr = *rItr; + if (split.getLoop().contains(&instr) && processed.count(&instr) == 0) { + split.addLoopInstr(&instr); + processed.insert(&instr); + } + } + + //dbgs() << " Rewriting reg" << li.reg << " to reg" << newLI->reg + // << " in blocks [ "; + //dbgs() << "]\n"; + } + + bool LoopSplitter::splitOverLoop(LiveInterval &li, MachineLoop &loop) { + assert(TargetRegisterInfo::isVirtualRegister(li.reg) && + "Attempt to split physical register."); + + LoopSplit split(*this, li, loop); + processHeader(split); + if (split.isValid()) + processLoopExits(split); + if (split.isValid()) + processLoopUses(split); + if (split.isValid() /* && split.isWorthwhile() */) { + split.apply(); + DEBUG(dbgs() << "Success.\n"); + return true; + } + DEBUG(dbgs() << "Failed.\n"); + return false; + } + + void LoopSplitter::processInterval(LiveInterval &li) { + std::deque loops; + std::copy(mli->begin(), mli->end(), std::back_inserter(loops)); + + while (!loops.empty()) { + MachineLoop &loop = *loops.front(); + loops.pop_front(); + DEBUG( + dbgs() << fqn << " reg" << li.reg << " " << li.weight << " BB#" + << loop.getHeader()->getNumber() << " "; + ); + if (!splitOverLoop(li, loop)) { + // Couldn't split over outer loop, schedule sub-loops to be checked. + std::copy(loop.begin(), loop.end(), std::back_inserter(loops)); + } + } + } + + void LoopSplitter::processIntervals() { + while (!intervals.empty()) { + LiveInterval &li = *intervals.front(); + intervals.pop_front(); + + assert(!lis->intervalIsInOneMBB(li) && + "Single interval in process worklist."); + + processInterval(li); + } + } + +} diff --git a/lib/CodeGen/Splitter.h b/lib/CodeGen/Splitter.h new file mode 100644 index 00000000000..f253ee77bf8 --- /dev/null +++ b/lib/CodeGen/Splitter.h @@ -0,0 +1,99 @@ +//===-- llvm/CodeGen/Splitter.h - Splitter -*- C++ -*----------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CODEGEN_SPLITTER_H +#define LLVM_CODEGEN_SPLITTER_H + +#include "llvm/CodeGen/MachineFunctionPass.h" +#include "llvm/CodeGen/MachineLoopInfo.h" +#include "llvm/CodeGen/SlotIndexes.h" + +#include +#include +#include +#include + +namespace llvm { + + class LiveInterval; + class LiveIntervals; + class LiveRange; + class LoopSplit; + class MachineDominatorTree; + class MachineRegisterInfo; + class SlotIndexes; + class TargetInstrInfo; + class VNInfo; + + class LoopSplitter : public MachineFunctionPass { + friend class LoopSplit; + public: + static char ID; + + LoopSplitter() : MachineFunctionPass(&ID) {} + + virtual void getAnalysisUsage(AnalysisUsage &au) const; + + virtual bool runOnMachineFunction(MachineFunction &fn); + + virtual void releaseMemory(); + + + private: + + MachineFunction *mf; + LiveIntervals *lis; + MachineLoopInfo *mli; + MachineRegisterInfo *mri; + MachineDominatorTree *mdt; + SlotIndexes *sis; + const TargetInstrInfo *tii; + const TargetRegisterInfo *tri; + + std::string fqn; + std::deque intervals; + + typedef std::pair SlotPair; + typedef std::vector LoopRanges; + typedef std::map LoopRangeMap; + LoopRangeMap loopRangeMap; + + void dumpLoopInfo(MachineLoop &loop); + + void dumpOddTerminators(); + + void updateTerminators(MachineBasicBlock &mbb); + + bool canInsertPreHeader(MachineLoop &loop); + MachineBasicBlock& insertPreHeader(MachineLoop &loop); + + bool isCriticalEdge(MachineLoop::Edge &edge); + bool canSplitEdge(MachineLoop::Edge &edge); + MachineBasicBlock& splitEdge(MachineLoop::Edge &edge, MachineLoop &loop); + + LoopRanges& getLoopRanges(MachineLoop &loop); + std::pair getLoopSubRange(const LiveRange &lr, + MachineLoop &loop); + + void dumpLoopRanges(MachineLoop &loop); + + void processHeader(LoopSplit &split); + void processLoopExits(LoopSplit &split); + void processLoopUses(LoopSplit &split); + + bool splitOverLoop(LiveInterval &li, MachineLoop &loop); + + void processInterval(LiveInterval &li); + + void processIntervals(); + }; + +} + +#endif -- 2.11.0