119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman//===-- llvm/CodeGen/Splitter.cpp - Splitter -----------------------------===// 219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// The LLVM Compiler Infrastructure 419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// This file is distributed under the University of Illinois Open Source 619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// License. See LICENSE.TXT for details. 719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman//===----------------------------------------------------------------------===// 919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 1019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#define DEBUG_TYPE "loopsplitter" 1119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 1219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "Splitter.h" 1319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 1419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/Module.h" 1519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/CodeGen/CalcSpillWeights.h" 1619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/CodeGen/LiveIntervalAnalysis.h" 1719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/CodeGen/LiveStackAnalysis.h" 1819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/CodeGen/MachineDominators.h" 1919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/CodeGen/MachineInstrBuilder.h" 2019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/CodeGen/MachineFunction.h" 2119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/CodeGen/MachineRegisterInfo.h" 2219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/CodeGen/Passes.h" 2319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/CodeGen/SlotIndexes.h" 2419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/Support/Debug.h" 2519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/Support/raw_ostream.h" 2619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/Target/TargetMachine.h" 2719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/Target/TargetInstrInfo.h" 2819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 2919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanusing namespace llvm; 3019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 3119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanchar LoopSplitter::ID = 0; 3219bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanINITIALIZE_PASS_BEGIN(LoopSplitter, "loop-splitting", 3319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman "Split virtual regists across loop boundaries.", false, false) 3419bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanINITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) 3519bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanINITIALIZE_PASS_DEPENDENCY(MachineLoopInfo) 3619bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanINITIALIZE_PASS_DEPENDENCY(SlotIndexes) 3719bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanINITIALIZE_PASS_DEPENDENCY(LiveIntervals) 3819bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanINITIALIZE_PASS_END(LoopSplitter, "loop-splitting", 3919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman "Split virtual regists across loop boundaries.", false, false) 4019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 4119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumannamespace llvm { 4219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 4319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman class StartSlotComparator { 4419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman public: 4519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman StartSlotComparator(LiveIntervals &lis) : lis(lis) {} 4619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool operator()(const MachineBasicBlock *mbb1, 4719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const MachineBasicBlock *mbb2) const { 4819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return lis.getMBBStartIdx(mbb1) < lis.getMBBStartIdx(mbb2); 4919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 5019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman private: 5119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LiveIntervals &lis; 5219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman }; 5319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 5419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman class LoopSplit { 5519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman public: 5619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LoopSplit(LoopSplitter &ls, LiveInterval &li, MachineLoop &loop) 5719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman : ls(ls), li(li), loop(loop), valid(true), inSplit(false), newLI(0) { 5819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(TargetRegisterInfo::isVirtualRegister(li.reg) && 5919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman "Cannot split physical registers."); 6019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 6119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 6219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LiveInterval& getLI() const { return li; } 6319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 6419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineLoop& getLoop() const { return loop; } 6519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 6619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool isValid() const { return valid; } 6719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 6819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool isWorthwhile() const { return valid && (inSplit || !outSplits.empty()); } 6919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 7019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void invalidate() { valid = false; } 7119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 7219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void splitIncoming() { inSplit = true; } 7319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 7419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void splitOutgoing(MachineLoop::Edge &edge) { outSplits.insert(edge); } 7519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 7619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void addLoopInstr(MachineInstr *i) { loopInstrs.push_back(i); } 7719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 7819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void apply() { 7919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(valid && "Attempt to apply invalid split."); 8019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman applyIncoming(); 8119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman applyOutgoing(); 8219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman copyRanges(); 8319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman renameInside(); 8419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 8519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 8619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman private: 8719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LoopSplitter &ls; 8819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LiveInterval &li; 8919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineLoop &loop; 9019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool valid, inSplit; 9119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman std::set<MachineLoop::Edge> outSplits; 9219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman std::vector<MachineInstr*> loopInstrs; 9319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 9419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LiveInterval *newLI; 9519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman std::map<VNInfo*, VNInfo*> vniMap; 9619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 9719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LiveInterval* getNewLI() { 9819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (newLI == 0) { 9919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const TargetRegisterClass *trc = ls.mri->getRegClass(li.reg); 10019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned vreg = ls.mri->createVirtualRegister(trc); 10119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman newLI = &ls.lis->getOrCreateInterval(vreg); 10219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 10319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return newLI; 10419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 10519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 10619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman VNInfo* getNewVNI(VNInfo *oldVNI) { 10719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman VNInfo *newVNI = vniMap[oldVNI]; 10819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 10919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (newVNI == 0) { 11019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman newVNI = getNewLI()->createValueCopy(oldVNI, 11119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ls.lis->getVNInfoAllocator()); 11219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman vniMap[oldVNI] = newVNI; 11319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 11419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 11519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return newVNI; 11619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 11719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 11819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void applyIncoming() { 11919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!inSplit) { 12019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return; 12119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 12219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 12319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineBasicBlock *preHeader = loop.getLoopPreheader(); 12419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (preHeader == 0) { 12519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(ls.canInsertPreHeader(loop) && 12619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman "Can't insert required preheader."); 12719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman preHeader = &ls.insertPreHeader(loop); 12819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 12919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 13019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LiveRange *preHeaderRange = 13119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ls.lis->findExitingRange(li, preHeader); 13219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(preHeaderRange != 0 && "Range not live into preheader."); 13319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 13419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Insert the new copy. 13519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineInstr *copy = BuildMI(*preHeader, 13619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman preHeader->getFirstTerminator(), 13719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DebugLoc(), 13819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ls.tii->get(TargetOpcode::COPY)) 13919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman .addReg(getNewLI()->reg, RegState::Define) 14019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman .addReg(li.reg, RegState::Kill); 14119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 14219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ls.lis->InsertMachineInstrInMaps(copy); 14319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 14419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SlotIndex copyDefIdx = ls.lis->getInstructionIndex(copy).getDefIndex(); 14519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 14619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman VNInfo *newVal = getNewVNI(preHeaderRange->valno); 14719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman newVal->def = copyDefIdx; 14819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman newVal->setCopy(copy); 14919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman li.removeRange(copyDefIdx, ls.lis->getMBBEndIdx(preHeader), true); 15019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 15119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman getNewLI()->addRange(LiveRange(copyDefIdx, 15219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ls.lis->getMBBEndIdx(preHeader), 15319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman newVal)); 15419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 15519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 15619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void applyOutgoing() { 15719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 15819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (std::set<MachineLoop::Edge>::iterator osItr = outSplits.begin(), 15919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman osEnd = outSplits.end(); 16019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman osItr != osEnd; ++osItr) { 16119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineLoop::Edge edge = *osItr; 16219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineBasicBlock *outBlock = edge.second; 16319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (ls.isCriticalEdge(edge)) { 16419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(ls.canSplitEdge(edge) && "Unsplitable critical edge."); 16519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman outBlock = &ls.splitEdge(edge, loop); 16619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 16719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LiveRange *outRange = ls.lis->findEnteringRange(li, outBlock); 16819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(outRange != 0 && "No exiting range?"); 16919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 17019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineInstr *copy = BuildMI(*outBlock, outBlock->begin(), 17119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DebugLoc(), 17219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ls.tii->get(TargetOpcode::COPY)) 17319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman .addReg(li.reg, RegState::Define) 17419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman .addReg(getNewLI()->reg, RegState::Kill); 17519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 17619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ls.lis->InsertMachineInstrInMaps(copy); 17719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 17819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SlotIndex copyDefIdx = ls.lis->getInstructionIndex(copy).getDefIndex(); 17919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 18019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Blow away output range definition. 18119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman outRange->valno->def = ls.lis->getInvalidIndex(); 18219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman li.removeRange(ls.lis->getMBBStartIdx(outBlock), copyDefIdx); 18319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 18419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SlotIndex newDefIdx = ls.lis->getMBBStartIdx(outBlock); 18519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(ls.lis->getInstructionFromIndex(newDefIdx) == 0 && 18619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman "PHI def index points at actual instruction."); 18719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman VNInfo *newVal = 18819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman getNewLI()->getNextValue(newDefIdx, 0, ls.lis->getVNInfoAllocator()); 18919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 19019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman getNewLI()->addRange(LiveRange(ls.lis->getMBBStartIdx(outBlock), 19119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman copyDefIdx, newVal)); 19219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 19319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 19419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 19519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 19619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void copyRange(LiveRange &lr) { 19719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman std::pair<bool, LoopSplitter::SlotPair> lsr = 19819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ls.getLoopSubRange(lr, loop); 19919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 20019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!lsr.first) 20119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return; 20219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 20319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LiveRange loopRange(lsr.second.first, lsr.second.second, 20419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman getNewVNI(lr.valno)); 20519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 20619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman li.removeRange(loopRange.start, loopRange.end, true); 20719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 20819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman getNewLI()->addRange(loopRange); 20919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 21019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 21119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void copyRanges() { 21219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (std::vector<MachineInstr*>::iterator iItr = loopInstrs.begin(), 21319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman iEnd = loopInstrs.end(); 21419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman iItr != iEnd; ++iItr) { 21519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineInstr &instr = **iItr; 21619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SlotIndex instrIdx = ls.lis->getInstructionIndex(&instr); 21719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (instr.modifiesRegister(li.reg, 0)) { 21819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LiveRange *defRange = 21919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman li.getLiveRangeContaining(instrIdx.getDefIndex()); 22019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (defRange != 0) // May have caught this already. 22119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman copyRange(*defRange); 22219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 22319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (instr.readsRegister(li.reg, 0)) { 22419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LiveRange *useRange = 22519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman li.getLiveRangeContaining(instrIdx.getUseIndex()); 22619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (useRange != 0) { // May have caught this already. 22719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman copyRange(*useRange); 22819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 22919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 23019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 23119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 23219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (MachineLoop::block_iterator bbItr = loop.block_begin(), 23319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bbEnd = loop.block_end(); 23419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bbItr != bbEnd; ++bbItr) { 23519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineBasicBlock &loopBlock = **bbItr; 23619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LiveRange *enteringRange = 23719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ls.lis->findEnteringRange(li, &loopBlock); 23819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (enteringRange != 0) { 23919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman copyRange(*enteringRange); 24019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 24119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 24219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 24319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 24419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void renameInside() { 24519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (std::vector<MachineInstr*>::iterator iItr = loopInstrs.begin(), 24619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman iEnd = loopInstrs.end(); 24719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman iItr != iEnd; ++iItr) { 24819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineInstr &instr = **iItr; 24919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (unsigned i = 0; i < instr.getNumOperands(); ++i) { 25019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineOperand &mop = instr.getOperand(i); 25119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (mop.isReg() && mop.getReg() == li.reg) { 25219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman mop.setReg(getNewLI()->reg); 25319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 25419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 25519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 25619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 25719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 25819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman }; 25919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 26019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void LoopSplitter::getAnalysisUsage(AnalysisUsage &au) const { 26119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman au.addRequired<MachineDominatorTree>(); 26219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman au.addPreserved<MachineDominatorTree>(); 26319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman au.addRequired<MachineLoopInfo>(); 26419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman au.addPreserved<MachineLoopInfo>(); 26519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman au.addPreservedID(RegisterCoalescerPassID); 26619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman au.addPreserved<CalculateSpillWeights>(); 26719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman au.addPreserved<LiveStacks>(); 26819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman au.addRequired<SlotIndexes>(); 26919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman au.addPreserved<SlotIndexes>(); 27019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman au.addRequired<LiveIntervals>(); 27119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman au.addPreserved<LiveIntervals>(); 27219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineFunctionPass::getAnalysisUsage(au); 27319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 27419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 27519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool LoopSplitter::runOnMachineFunction(MachineFunction &fn) { 27619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 27719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman mf = &fn; 27819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman mri = &mf->getRegInfo(); 27919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman tii = mf->getTarget().getInstrInfo(); 28019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman tri = mf->getTarget().getRegisterInfo(); 28119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman sis = &getAnalysis<SlotIndexes>(); 28219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman lis = &getAnalysis<LiveIntervals>(); 28319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman mli = &getAnalysis<MachineLoopInfo>(); 28419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman mdt = &getAnalysis<MachineDominatorTree>(); 28519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 28619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman fqn = mf->getFunction()->getParent()->getModuleIdentifier() + "." + 28719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman mf->getFunction()->getName().str(); 28819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 28919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman dbgs() << "Splitting " << mf->getFunction()->getName() << "."; 29019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 29119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman dumpOddTerminators(); 29219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 29319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// dbgs() << "----------------------------------------\n"; 29419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// lis->dump(); 29519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// dbgs() << "----------------------------------------\n"; 29619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 29719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// std::deque<MachineLoop*> loops; 29819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// std::copy(mli->begin(), mli->end(), std::back_inserter(loops)); 29919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// dbgs() << "Loops:\n"; 30019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// while (!loops.empty()) { 30119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// MachineLoop &loop = *loops.front(); 30219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// loops.pop_front(); 30319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// std::copy(loop.begin(), loop.end(), std::back_inserter(loops)); 30419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 30519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// dumpLoopInfo(loop); 30619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// } 30719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 30819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman //lis->dump(); 30919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman //exit(0); 31019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 31119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Setup initial intervals. 31219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (LiveIntervals::iterator liItr = lis->begin(), liEnd = lis->end(); 31319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman liItr != liEnd; ++liItr) { 31419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LiveInterval *li = liItr->second; 31519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 31619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (TargetRegisterInfo::isVirtualRegister(li->reg) && 31719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman !lis->intervalIsInOneMBB(*li)) { 31819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman intervals.push_back(li); 31919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 32019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 32119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 32219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman processIntervals(); 32319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 32419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman intervals.clear(); 32519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 32619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// dbgs() << "----------------------------------------\n"; 32719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// lis->dump(); 32819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// dbgs() << "----------------------------------------\n"; 32919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 33019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman dumpOddTerminators(); 33119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 33219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman //exit(1); 33319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 33419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 33519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 33619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 33719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void LoopSplitter::releaseMemory() { 33819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman fqn.clear(); 33919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman intervals.clear(); 34019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman loopRangeMap.clear(); 34119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 34219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 34319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void LoopSplitter::dumpOddTerminators() { 34419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (MachineFunction::iterator bbItr = mf->begin(), bbEnd = mf->end(); 34519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bbItr != bbEnd; ++bbItr) { 34619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineBasicBlock *mbb = &*bbItr; 34719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineBasicBlock *a = 0, *b = 0; 34819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SmallVector<MachineOperand, 4> c; 34919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (tii->AnalyzeBranch(*mbb, a, b, c)) { 35019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman dbgs() << "MBB#" << mbb->getNumber() << " has multiway terminator.\n"; 35119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman dbgs() << " Terminators:\n"; 35219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (MachineBasicBlock::iterator iItr = mbb->begin(), iEnd = mbb->end(); 35319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman iItr != iEnd; ++iItr) { 35419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineInstr *instr= &*iItr; 35519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman dbgs() << " " << *instr << ""; 35619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 35719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman dbgs() << "\n Listed successors: [ "; 35819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (MachineBasicBlock::succ_iterator sItr = mbb->succ_begin(), sEnd = mbb->succ_end(); 35919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman sItr != sEnd; ++sItr) { 36019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineBasicBlock *succMBB = *sItr; 36119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman dbgs() << succMBB->getNumber() << " "; 36219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 36319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman dbgs() << "]\n\n"; 36419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 36519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 36619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 36719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 36819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void LoopSplitter::dumpLoopInfo(MachineLoop &loop) { 36919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineBasicBlock &headerBlock = *loop.getHeader(); 37019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman typedef SmallVector<MachineLoop::Edge, 8> ExitEdgesList; 37119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ExitEdgesList exitEdges; 37219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman loop.getExitEdges(exitEdges); 37319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 37419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman dbgs() << " Header: BB#" << headerBlock.getNumber() << ", Contains: [ "; 37519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (std::vector<MachineBasicBlock*>::const_iterator 37619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman subBlockItr = loop.getBlocks().begin(), 37719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman subBlockEnd = loop.getBlocks().end(); 37819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman subBlockItr != subBlockEnd; ++subBlockItr) { 37919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineBasicBlock &subBlock = **subBlockItr; 38019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman dbgs() << "BB#" << subBlock.getNumber() << " "; 38119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 38219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman dbgs() << "], Exit edges: [ "; 38319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (ExitEdgesList::iterator exitEdgeItr = exitEdges.begin(), 38419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman exitEdgeEnd = exitEdges.end(); 38519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman exitEdgeItr != exitEdgeEnd; ++exitEdgeItr) { 38619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineLoop::Edge &exitEdge = *exitEdgeItr; 38719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman dbgs() << "(MBB#" << exitEdge.first->getNumber() 38819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman << ", MBB#" << exitEdge.second->getNumber() << ") "; 38919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 39019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman dbgs() << "], Sub-Loop Headers: [ "; 39119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (MachineLoop::iterator subLoopItr = loop.begin(), 39219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman subLoopEnd = loop.end(); 39319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman subLoopItr != subLoopEnd; ++subLoopItr) { 39419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineLoop &subLoop = **subLoopItr; 39519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineBasicBlock &subLoopBlock = *subLoop.getHeader(); 39619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman dbgs() << "BB#" << subLoopBlock.getNumber() << " "; 39719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 39819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman dbgs() << "]\n"; 39919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 40019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 40119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void LoopSplitter::updateTerminators(MachineBasicBlock &mbb) { 40219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman mbb.updateTerminator(); 40319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 40419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (MachineBasicBlock::iterator miItr = mbb.begin(), miEnd = mbb.end(); 40519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman miItr != miEnd; ++miItr) { 40619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (lis->isNotInMIMap(miItr)) { 40719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman lis->InsertMachineInstrInMaps(miItr); 40819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 40919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 41019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 41119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 41219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool LoopSplitter::canInsertPreHeader(MachineLoop &loop) { 41319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineBasicBlock *header = loop.getHeader(); 41419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineBasicBlock *a = 0, *b = 0; 41519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SmallVector<MachineOperand, 4> c; 41619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 41719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (MachineBasicBlock::pred_iterator pbItr = header->pred_begin(), 41819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman pbEnd = header->pred_end(); 41919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman pbItr != pbEnd; ++pbItr) { 42019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineBasicBlock *predBlock = *pbItr; 42119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!!tii->AnalyzeBranch(*predBlock, a, b, c)) { 42219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 42319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 42419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 42519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 42619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineFunction::iterator headerItr(header); 42719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (headerItr == mf->begin()) 42819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return true; 42919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineBasicBlock *headerLayoutPred = llvm::prior(headerItr); 43019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(headerLayoutPred != 0 && "Header should have layout pred."); 43119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 43219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return (!tii->AnalyzeBranch(*headerLayoutPred, a, b, c)); 43319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 43419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 43519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineBasicBlock& LoopSplitter::insertPreHeader(MachineLoop &loop) { 43619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(loop.getLoopPreheader() == 0 && "Loop already has preheader."); 43719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 43819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineBasicBlock &header = *loop.getHeader(); 43919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 44019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Save the preds - we'll need to update them once we insert the preheader. 44119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman typedef std::set<MachineBasicBlock*> HeaderPreds; 44219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman HeaderPreds headerPreds; 44319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 44419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (MachineBasicBlock::pred_iterator predItr = header.pred_begin(), 44519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman predEnd = header.pred_end(); 44619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman predItr != predEnd; ++predItr) { 44719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!loop.contains(*predItr)) 44819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman headerPreds.insert(*predItr); 44919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 45019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 45119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(!headerPreds.empty() && "No predecessors for header?"); 45219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 45319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman //dbgs() << fqn << " MBB#" << header.getNumber() << " inserting preheader..."; 45419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 45519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineBasicBlock *preHeader = 45619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman mf->CreateMachineBasicBlock(header.getBasicBlock()); 45719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 45819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(preHeader != 0 && "Failed to create pre-header."); 45919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 46019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman mf->insert(header, preHeader); 46119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 46219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (HeaderPreds::iterator hpItr = headerPreds.begin(), 46319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman hpEnd = headerPreds.end(); 46419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman hpItr != hpEnd; ++hpItr) { 46519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(*hpItr != 0 && "How'd a null predecessor get into this set?"); 46619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineBasicBlock &hp = **hpItr; 46719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman hp.ReplaceUsesOfBlockWith(&header, preHeader); 46819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 46919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman preHeader->addSuccessor(&header); 47019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 47119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineBasicBlock *oldLayoutPred = 47219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman llvm::prior(MachineFunction::iterator(preHeader)); 47319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (oldLayoutPred != 0) { 47419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman updateTerminators(*oldLayoutPred); 47519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 47619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 47719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman lis->InsertMBBInMaps(preHeader); 47819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 47919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (MachineLoop *parentLoop = loop.getParentLoop()) { 48019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(parentLoop->getHeader() != loop.getHeader() && 48119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman "Parent loop has same header?"); 48219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman parentLoop->addBasicBlockToLoop(preHeader, mli->getBase()); 48319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 48419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Invalidate all parent loop ranges. 48519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman while (parentLoop != 0) { 48619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman loopRangeMap.erase(parentLoop); 48719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman parentLoop = parentLoop->getParentLoop(); 48819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 48919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 49019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 49119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (LiveIntervals::iterator liItr = lis->begin(), 49219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman liEnd = lis->end(); 49319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman liItr != liEnd; ++liItr) { 49419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LiveInterval &li = *liItr->second; 49519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 49619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Is this safe for physregs? 49719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // TargetRegisterInfo::isPhysicalRegister(li.reg) || 49819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!lis->isLiveInToMBB(li, &header)) 49919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman continue; 50019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 50119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (lis->isLiveInToMBB(li, preHeader)) { 50219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(lis->isLiveOutOfMBB(li, preHeader) && 50319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman "Range terminates in newly added preheader?"); 50419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman continue; 50519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 50619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 50719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool insertRange = false; 50819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 50919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (MachineBasicBlock::pred_iterator predItr = preHeader->pred_begin(), 51019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman predEnd = preHeader->pred_end(); 51119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman predItr != predEnd; ++predItr) { 51219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineBasicBlock *predMBB = *predItr; 51319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (lis->isLiveOutOfMBB(li, predMBB)) { 51419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman insertRange = true; 51519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman break; 51619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 51719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 51819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 51919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!insertRange) 52019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman continue; 52119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 52219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SlotIndex newDefIdx = lis->getMBBStartIdx(preHeader); 52319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(lis->getInstructionFromIndex(newDefIdx) == 0 && 52419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman "PHI def index points at actual instruction."); 52519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman VNInfo *newVal = li.getNextValue(newDefIdx, 0, lis->getVNInfoAllocator()); 52619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman li.addRange(LiveRange(lis->getMBBStartIdx(preHeader), 52719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman lis->getMBBEndIdx(preHeader), 52819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman newVal)); 52919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 53019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 53119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 53219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman //dbgs() << "Dumping SlotIndexes:\n"; 53319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman //sis->dump(); 53419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 53519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman //dbgs() << "done. (Added MBB#" << preHeader->getNumber() << ")\n"; 53619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 53719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return *preHeader; 53819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 53919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 54019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool LoopSplitter::isCriticalEdge(MachineLoop::Edge &edge) { 54119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(edge.first->succ_size() > 1 && "Non-sensical edge."); 54219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (edge.second->pred_size() > 1) 54319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return true; 54419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 54519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 54619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 54719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool LoopSplitter::canSplitEdge(MachineLoop::Edge &edge) { 54819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineFunction::iterator outBlockItr(edge.second); 54919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (outBlockItr == mf->begin()) 55019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return true; 55119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineBasicBlock *outBlockLayoutPred = llvm::prior(outBlockItr); 55219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(outBlockLayoutPred != 0 && "Should have a layout pred if out!=begin."); 55319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineBasicBlock *a = 0, *b = 0; 55419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SmallVector<MachineOperand, 4> c; 55519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return (!tii->AnalyzeBranch(*outBlockLayoutPred, a, b, c) && 55619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman !tii->AnalyzeBranch(*edge.first, a, b, c)); 55719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 55819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 55919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineBasicBlock& LoopSplitter::splitEdge(MachineLoop::Edge &edge, 56019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineLoop &loop) { 56119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 56219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineBasicBlock &inBlock = *edge.first; 56319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineBasicBlock &outBlock = *edge.second; 56419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 56519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert((inBlock.succ_size() > 1) && (outBlock.pred_size() > 1) && 56619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman "Splitting non-critical edge?"); 56719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 56819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman //dbgs() << fqn << " Splitting edge (MBB#" << inBlock.getNumber() 56919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // << " -> MBB#" << outBlock.getNumber() << ")..."; 57019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 57119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineBasicBlock *splitBlock = 57219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman mf->CreateMachineBasicBlock(); 57319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 57419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(splitBlock != 0 && "Failed to create split block."); 57519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 57619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman mf->insert(&outBlock, splitBlock); 57719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 57819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman inBlock.ReplaceUsesOfBlockWith(&outBlock, splitBlock); 57919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman splitBlock->addSuccessor(&outBlock); 58019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 58119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineBasicBlock *oldLayoutPred = 58219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman llvm::prior(MachineFunction::iterator(splitBlock)); 58319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (oldLayoutPred != 0) { 58419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman updateTerminators(*oldLayoutPred); 58519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 58619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 58719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman lis->InsertMBBInMaps(splitBlock); 58819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 58919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman loopRangeMap.erase(&loop); 59019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 59119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineLoop *splitParentLoop = loop.getParentLoop(); 59219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman while (splitParentLoop != 0 && 59319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman !splitParentLoop->contains(&outBlock)) { 59419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman splitParentLoop = splitParentLoop->getParentLoop(); 59519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 59619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 59719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (splitParentLoop != 0) { 59819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(splitParentLoop->contains(&loop) && 59919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman "Split-block parent doesn't contain original loop?"); 60019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman splitParentLoop->addBasicBlockToLoop(splitBlock, mli->getBase()); 60119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 60219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Invalidate all parent loop ranges. 60319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman while (splitParentLoop != 0) { 60419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman loopRangeMap.erase(splitParentLoop); 60519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman splitParentLoop = splitParentLoop->getParentLoop(); 60619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 60719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 60819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 60919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 61019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (LiveIntervals::iterator liItr = lis->begin(), 61119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman liEnd = lis->end(); 61219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman liItr != liEnd; ++liItr) { 61319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LiveInterval &li = *liItr->second; 61419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool intersects = lis->isLiveOutOfMBB(li, &inBlock) && 61519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman lis->isLiveInToMBB(li, &outBlock); 61619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (lis->isLiveInToMBB(li, splitBlock)) { 61719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!intersects) { 61819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman li.removeRange(lis->getMBBStartIdx(splitBlock), 61919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman lis->getMBBEndIdx(splitBlock), true); 62019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 62119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } else if (intersects) { 62219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SlotIndex newDefIdx = lis->getMBBStartIdx(splitBlock); 62319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(lis->getInstructionFromIndex(newDefIdx) == 0 && 62419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman "PHI def index points at actual instruction."); 62519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman VNInfo *newVal = li.getNextValue(newDefIdx, 0, 62619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman lis->getVNInfoAllocator()); 62719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman li.addRange(LiveRange(lis->getMBBStartIdx(splitBlock), 62819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman lis->getMBBEndIdx(splitBlock), 62919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman newVal)); 63019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 63119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 63219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 63319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman //dbgs() << "done. (Added MBB#" << splitBlock->getNumber() << ")\n"; 63419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 63519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return *splitBlock; 63619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 63719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 63819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LoopSplitter::LoopRanges& LoopSplitter::getLoopRanges(MachineLoop &loop) { 63919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman typedef std::set<MachineBasicBlock*, StartSlotComparator> LoopMBBSet; 64019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LoopRangeMap::iterator lrItr = loopRangeMap.find(&loop); 64119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (lrItr == loopRangeMap.end()) { 64219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LoopMBBSet loopMBBs((StartSlotComparator(*lis))); 64319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman std::copy(loop.block_begin(), loop.block_end(), 64419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman std::inserter(loopMBBs, loopMBBs.begin())); 64519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 64619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(!loopMBBs.empty() && "No blocks in loop?"); 64719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 64819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LoopRanges &loopRanges = loopRangeMap[&loop]; 64919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(loopRanges.empty() && "Loop encountered but not processed?"); 65019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SlotIndex oldEnd = lis->getMBBEndIdx(*loopMBBs.begin()); 65119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman loopRanges.push_back( 65219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman std::make_pair(lis->getMBBStartIdx(*loopMBBs.begin()), 65319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman lis->getInvalidIndex())); 65419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (LoopMBBSet::iterator curBlockItr = llvm::next(loopMBBs.begin()), 65519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman curBlockEnd = loopMBBs.end(); 65619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman curBlockItr != curBlockEnd; ++curBlockItr) { 65719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SlotIndex newStart = lis->getMBBStartIdx(*curBlockItr); 65819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (newStart != oldEnd) { 65919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman loopRanges.back().second = oldEnd; 66019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman loopRanges.push_back(std::make_pair(newStart, 66119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman lis->getInvalidIndex())); 66219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 66319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman oldEnd = lis->getMBBEndIdx(*curBlockItr); 66419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 66519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 66619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman loopRanges.back().second = 66719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman lis->getMBBEndIdx(*llvm::prior(loopMBBs.end())); 66819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 66919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return loopRanges; 67019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 67119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return lrItr->second; 67219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 67319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 67419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman std::pair<bool, LoopSplitter::SlotPair> LoopSplitter::getLoopSubRange( 67519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const LiveRange &lr, 67619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineLoop &loop) { 67719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LoopRanges &loopRanges = getLoopRanges(loop); 67819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LoopRanges::iterator lrItr = loopRanges.begin(), 67919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman lrEnd = loopRanges.end(); 68019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman while (lrItr != lrEnd && lr.start >= lrItr->second) { 68119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ++lrItr; 68219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 68319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 68419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (lrItr == lrEnd) { 68519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SlotIndex invalid = lis->getInvalidIndex(); 68619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return std::make_pair(false, SlotPair(invalid, invalid)); 68719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 68819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 68919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SlotIndex srStart(lr.start < lrItr->first ? lrItr->first : lr.start); 69019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SlotIndex srEnd(lr.end > lrItr->second ? lrItr->second : lr.end); 69119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 69219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return std::make_pair(true, SlotPair(srStart, srEnd)); 69319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 69419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 69519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void LoopSplitter::dumpLoopRanges(MachineLoop &loop) { 69619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LoopRanges &loopRanges = getLoopRanges(loop); 69719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman dbgs() << "For loop MBB#" << loop.getHeader()->getNumber() << ", subranges are: [ "; 69819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (LoopRanges::iterator lrItr = loopRanges.begin(), lrEnd = loopRanges.end(); 69919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman lrItr != lrEnd; ++lrItr) { 70019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman dbgs() << "[" << lrItr->first << ", " << lrItr->second << ") "; 70119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 70219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman dbgs() << "]\n"; 70319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 70419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 70519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void LoopSplitter::processHeader(LoopSplit &split) { 70619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineBasicBlock &header = *split.getLoop().getHeader(); 70719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman //dbgs() << " Processing loop header BB#" << header.getNumber() << "\n"; 70819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 70919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!lis->isLiveInToMBB(split.getLI(), &header)) 71019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return; // Not live in, but nothing wrong so far. 71119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 71219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineBasicBlock *preHeader = split.getLoop().getLoopPreheader(); 71319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!preHeader) { 71419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 71519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!canInsertPreHeader(split.getLoop())) { 71619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman split.invalidate(); 71719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return; // Couldn't insert a pre-header. Bail on this interval. 71819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 71919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 72019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (MachineBasicBlock::pred_iterator predItr = header.pred_begin(), 72119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman predEnd = header.pred_end(); 72219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman predItr != predEnd; ++predItr) { 72319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (lis->isLiveOutOfMBB(split.getLI(), *predItr)) { 72419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman split.splitIncoming(); 72519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman break; 72619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 72719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 72819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } else if (lis->isLiveOutOfMBB(split.getLI(), preHeader)) { 72919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman split.splitIncoming(); 73019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 73119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 73219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 73319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void LoopSplitter::processLoopExits(LoopSplit &split) { 73419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman typedef SmallVector<MachineLoop::Edge, 8> ExitEdgesList; 73519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ExitEdgesList exitEdges; 73619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman split.getLoop().getExitEdges(exitEdges); 73719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 73819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman //dbgs() << " Processing loop exits:\n"; 73919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 74019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (ExitEdgesList::iterator exitEdgeItr = exitEdges.begin(), 74119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman exitEdgeEnd = exitEdges.end(); 74219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman exitEdgeItr != exitEdgeEnd; ++exitEdgeItr) { 74319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineLoop::Edge exitEdge = *exitEdgeItr; 74419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 74519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LiveRange *outRange = 74619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman split.getLI().getLiveRangeContaining(lis->getMBBStartIdx(exitEdge.second)); 74719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 74819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (outRange != 0) { 74919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (isCriticalEdge(exitEdge) && !canSplitEdge(exitEdge)) { 75019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman split.invalidate(); 75119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return; 75219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 75319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 75419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman split.splitOutgoing(exitEdge); 75519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 75619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 75719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 75819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 75919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void LoopSplitter::processLoopUses(LoopSplit &split) { 76019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman std::set<MachineInstr*> processed; 76119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 76219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (MachineRegisterInfo::reg_iterator 76319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman rItr = mri->reg_begin(split.getLI().reg), 76419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman rEnd = mri->reg_end(); 76519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman rItr != rEnd; ++rItr) { 76619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineInstr &instr = *rItr; 76719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (split.getLoop().contains(&instr) && processed.count(&instr) == 0) { 76819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman split.addLoopInstr(&instr); 76919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman processed.insert(&instr); 77019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 77119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 77219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 77319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman //dbgs() << " Rewriting reg" << li.reg << " to reg" << newLI->reg 77419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // << " in blocks [ "; 77519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman //dbgs() << "]\n"; 77619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 77719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 77819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool LoopSplitter::splitOverLoop(LiveInterval &li, MachineLoop &loop) { 77919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(TargetRegisterInfo::isVirtualRegister(li.reg) && 78019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman "Attempt to split physical register."); 78119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 78219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LoopSplit split(*this, li, loop); 78319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman processHeader(split); 78419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (split.isValid()) 78519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman processLoopExits(split); 78619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (split.isValid()) 78719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman processLoopUses(split); 78819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (split.isValid() /* && split.isWorthwhile() */) { 78919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman split.apply(); 79019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DEBUG(dbgs() << "Success.\n"); 79119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return true; 79219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 79319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DEBUG(dbgs() << "Failed.\n"); 79419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 79519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 79619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 79719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void LoopSplitter::processInterval(LiveInterval &li) { 79819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman std::deque<MachineLoop*> loops; 79919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman std::copy(mli->begin(), mli->end(), std::back_inserter(loops)); 80019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 80119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman while (!loops.empty()) { 80219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineLoop &loop = *loops.front(); 80319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman loops.pop_front(); 80419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DEBUG( 80519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman dbgs() << fqn << " reg" << li.reg << " " << li.weight << " BB#" 80619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman << loop.getHeader()->getNumber() << " "; 80719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ); 80819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!splitOverLoop(li, loop)) { 80919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Couldn't split over outer loop, schedule sub-loops to be checked. 81019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman std::copy(loop.begin(), loop.end(), std::back_inserter(loops)); 81119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 81219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 81319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 81419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 81519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void LoopSplitter::processIntervals() { 81619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman while (!intervals.empty()) { 81719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LiveInterval &li = *intervals.front(); 81819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman intervals.pop_front(); 81919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 82019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(!lis->intervalIsInOneMBB(li) && 82119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman "Single interval in process worklist."); 82219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 82319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman processInterval(li); 82419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 82519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 82619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 82719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 828