SplitKit.cpp revision 8ae0263471cc29c5f8278ee1ea5b678042ec6dce
18ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen//===---------- SplitKit.cpp - Toolkit for splitting live ranges ----------===// 28ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen// 38ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen// The LLVM Compiler Infrastructure 48ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen// 58ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen// This file is distributed under the University of Illinois Open Source 68ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen// License. See LICENSE.TXT for details. 78ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen// 88ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen//===----------------------------------------------------------------------===// 98ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen// 108ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen// This file contains the SplitAnalysis class as well as mutator functions for 118ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen// live range splitting. 128ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen// 138ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen//===----------------------------------------------------------------------===// 148ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 158ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen#define DEBUG_TYPE "splitter" 168ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen#include "SplitKit.h" 178ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen#include "llvm/CodeGen/LiveIntervalAnalysis.h" 188ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen#include "llvm/CodeGen/MachineFunctionPass.h" 198ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen#include "llvm/CodeGen/MachineLoopInfo.h" 208ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen#include "llvm/CodeGen/MachineRegisterInfo.h" 218ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen#include "llvm/Support/Debug.h" 228ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen#include "llvm/Support/raw_ostream.h" 238ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 248ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesenusing namespace llvm; 258ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 268ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 278ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen//===----------------------------------------------------------------------===// 288ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen// Split Analysis 298ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen//===----------------------------------------------------------------------===// 308ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 318ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund OlesenSplitAnalysis::SplitAnalysis(const MachineFunction *mf, 328ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen const LiveIntervals *lis, 338ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen const MachineLoopInfo *mli) 348ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen : mf_(*mf), 358ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen lis_(*lis), 368ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen loops_(*mli), 378ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen curli_(0) {} 388ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 398ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesenvoid SplitAnalysis::clear() { 408ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen usingInstrs_.clear(); 418ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen usingBlocks_.clear(); 428ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen usingLoops_.clear(); 438ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen} 448ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 458ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen/// analyseUses - Count instructions, basic blocks, and loops using curli. 468ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesenvoid SplitAnalysis::analyseUses() { 478ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen const MachineRegisterInfo &MRI = mf_.getRegInfo(); 488ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen for (MachineRegisterInfo::reg_iterator I = MRI.reg_begin(curli_->reg); 498ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen MachineInstr *MI = I.skipInstruction();) { 508ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen if (MI->isDebugValue() || !usingInstrs_.insert(MI)) 518ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen continue; 528ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen MachineBasicBlock *MBB = MI->getParent(); 538ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen if (usingBlocks_[MBB]++) 548ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen continue; 558ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen if (MachineLoop *Loop = loops_.getLoopFor(MBB)) 568ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen usingLoops_.insert(Loop); 578ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen } 588ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen DEBUG(dbgs() << "Counted " 598ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen << usingInstrs_.size() << " instrs, " 608ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen << usingBlocks_.size() << " blocks, " 618ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen << usingLoops_.size() << " loops in " 628ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen << *curli_ << "\n"); 638ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen} 648ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 658ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund OlesenSplitAnalysis::LoopPeripheralUse 668ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund OlesenSplitAnalysis::analyzeLoopPeripheralUse(const MachineLoop *Loop) { 678ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen // Peripheral blocks. 688ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen SmallVector<MachineBasicBlock*, 16> Peri; 698ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen Loop->getExitBlocks(Peri); 708ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen if (MachineBasicBlock *PredBB = Loop->getLoopPredecessor()) 718ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen Peri.push_back(PredBB); 728ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen array_pod_sort(Peri.begin(), Peri.end()); 738ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen Peri.erase(std::unique(Peri.begin(), Peri.end()), Peri.end()); 748ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 758ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen LoopPeripheralUse use = ContainedInLoop; 768ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen for (BlockCountMap::iterator I = usingBlocks_.begin(), E = usingBlocks_.end(); 778ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen I != E; ++I) { 788ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen const MachineBasicBlock *MBB = I->first; 798ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen // Is this a peripheral block? 808ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen if (use < MultiPeripheral && 818ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen std::binary_search(Peri.begin(), Peri.end(), MBB)) { 828ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen if (I->second > 1) use = MultiPeripheral; 838ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen else use = SinglePeripheral; 848ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen continue; 858ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen } 868ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen // Is it a loop block? 878ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen if (Loop->contains(MBB)) 888ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen continue; 898ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen // It must be an unrelated block. 908ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen return OutsideLoop; 918ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen } 928ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen return use; 938ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen} 948ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 958ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesenvoid SplitAnalysis::analyze(const LiveInterval *li) { 968ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen clear(); 978ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen curli_ = li; 988ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen analyseUses(); 998ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen} 1008ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 1018ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesenconst MachineLoop *SplitAnalysis::getBestSplitLoop() { 1028ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen LoopPtrSet Loops, SecondLoops; 1038ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 1048ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen // Find first-class and second class candidate loops. 1058ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen // We prefer to split around loops where curli is used outside the periphery. 1068ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen for (LoopPtrSet::const_iterator I = usingLoops_.begin(), 1078ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen E = usingLoops_.end(); I != E; ++I) 1088ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen switch(analyzeLoopPeripheralUse(*I)) { 1098ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen case OutsideLoop: 1108ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen Loops.insert(*I); 1118ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen break; 1128ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen case MultiPeripheral: 1138ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen SecondLoops.insert(*I); 1148ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen break; 1158ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen default: 1168ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen continue; 1178ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen } 1188ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 1198ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen // If there are no first class loops available, look at second class loops. 1208ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen if (Loops.empty()) 1218ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen Loops = SecondLoops; 1228ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 1238ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen if (Loops.empty()) 1248ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen return 0; 1258ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 1268ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen // Pick the earliest loop. 1278ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen // FIXME: Are there other heuristics to consider? 1288ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen // - avoid breaking critical edges. 1298ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen // - avoid impossible loops. 1308ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen const MachineLoop *Best = 0; 1318ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen SlotIndex BestIdx; 1328ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen for (LoopPtrSet::const_iterator I = Loops.begin(), E = Loops.end(); I != E; 1338ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen ++I) { 1348ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen SlotIndex Idx = lis_.getMBBStartIdx((*I)->getHeader()); 1358ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen if (!Best || Idx < BestIdx) 1368ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen Best = *I, BestIdx = Idx; 1378ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen } 1388ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen return Best; 1398ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen} 1408ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 1418ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen//===----------------------------------------------------------------------===// 1428ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen// Loop Splitting 1438ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen//===----------------------------------------------------------------------===// 1448ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 1458ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesenbool llvm::splitAroundLoop(SplitAnalysis &sa, const MachineLoop *loop) { 1468ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen return false; 1478ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen} 1488ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 149