SplitKit.h revision b5fa9333431673aac2ced8dea80152349a85cf6f
18dd070edc2209ecfdae49780ec1596b349e2cbd1Jakob Stoklund Olesen//===-------- SplitKit.h - Toolkit for splitting live ranges ----*- C++ -*-===// 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#include "llvm/ADT/DenseMap.h" 168d0963f72c8922bafffb36ff49b18064098a3cabJakob Stoklund Olesen#include "llvm/ADT/SmallPtrSet.h" 17f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen#include "llvm/CodeGen/SlotIndexes.h" 188ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 198ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesennamespace llvm { 208ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 218ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesenclass LiveInterval; 228ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesenclass LiveIntervals; 23a17768f5822ab62bc18608e5ba473187bf726b84Jakob Stoklund Olesenclass LiveRangeEdit; 248ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesenclass MachineInstr; 258ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesenclass MachineLoop; 268ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesenclass MachineLoopInfo; 27f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesenclass MachineRegisterInfo; 286a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesenclass TargetInstrInfo; 29cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesenclass TargetRegisterInfo; 30f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesenclass VirtRegMap; 31f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesenclass VNInfo; 32532de3dc6ea98387368954c0ac0e07b0adca8b62Jakob Stoklund Olesenclass raw_ostream; 338ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 34e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen/// At some point we should just include MachineDominators.h: 35e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesenclass MachineDominatorTree; 36e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesentemplate <class NodeT> class DomTreeNodeBase; 37e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesentypedef DomTreeNodeBase<MachineBasicBlock> MachineDomTreeNode; 38e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen 398d0963f72c8922bafffb36ff49b18064098a3cabJakob Stoklund Olesen 40f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen/// SplitAnalysis - Analyze a LiveInterval, looking for live range splitting 41f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen/// opportunities. 428ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesenclass SplitAnalysis { 4308e93b14c37277ab40b835de340f89ba357d3332Jakob Stoklund Olesenpublic: 448ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen const MachineFunction &mf_; 458ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen const LiveIntervals &lis_; 468ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen const MachineLoopInfo &loops_; 476a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen const TargetInstrInfo &tii_; 488ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 498ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen // Instructions using the the current register. 508ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen typedef SmallPtrSet<const MachineInstr*, 16> InstrPtrSet; 518ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen InstrPtrSet usingInstrs_; 528ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 53b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen // Sorted slot indexes of using instructions. 54b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen SmallVector<SlotIndex, 8> UseSlots; 55b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 568ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen // The number of instructions using curli in each basic block. 578ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen typedef DenseMap<const MachineBasicBlock*, unsigned> BlockCountMap; 588ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen BlockCountMap usingBlocks_; 598ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 602dee7a527b083e259f9e826c57c1e5dab9540798Jakob Stoklund Olesen // The number of basic block using curli in each loop. 612dee7a527b083e259f9e826c57c1e5dab9540798Jakob Stoklund Olesen typedef DenseMap<const MachineLoop*, unsigned> LoopCountMap; 622dee7a527b083e259f9e826c57c1e5dab9540798Jakob Stoklund Olesen LoopCountMap usingLoops_; 638ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 64f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesenprivate: 65f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen // Current live interval. 66f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen const LiveInterval *curli_; 67f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen 688ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen // Sumarize statistics by counting instructions using curli_. 69abff28087fd6be8150ff0e69def7de7312b2f76bJakob Stoklund Olesen void analyzeUses(); 708ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 716a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen /// canAnalyzeBranch - Return true if MBB ends in a branch that can be 726a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen /// analyzed. 736a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen bool canAnalyzeBranch(const MachineBasicBlock *MBB); 746a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen 758ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesenpublic: 76f2c6e367c1c0d8797e62e58a3ccdb8cceee27987Jakob Stoklund Olesen SplitAnalysis(const MachineFunction &mf, const LiveIntervals &lis, 77f2c6e367c1c0d8797e62e58a3ccdb8cceee27987Jakob Stoklund Olesen const MachineLoopInfo &mli); 788ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 798ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen /// analyze - set curli to the specified interval, and analyze how it may be 808ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen /// split. 818ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen void analyze(const LiveInterval *li); 828ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 838ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen /// clear - clear all data structures so SplitAnalysis is ready to analyze a 848ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen /// new interval. 858ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen void clear(); 868ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 87b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen /// hasUses - Return true if MBB has any uses of curli. 88b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen bool hasUses(const MachineBasicBlock *MBB) const { 89b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen return usingBlocks_.lookup(MBB); 90b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen } 91b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 926a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen typedef SmallPtrSet<const MachineBasicBlock*, 16> BlockPtrSet; 932dee7a527b083e259f9e826c57c1e5dab9540798Jakob Stoklund Olesen typedef SmallPtrSet<const MachineLoop*, 16> LoopPtrSet; 946a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen 95532de3dc6ea98387368954c0ac0e07b0adca8b62Jakob Stoklund Olesen // Print a set of blocks with use counts. 96532de3dc6ea98387368954c0ac0e07b0adca8b62Jakob Stoklund Olesen void print(const BlockPtrSet&, raw_ostream&) const; 97532de3dc6ea98387368954c0ac0e07b0adca8b62Jakob Stoklund Olesen 986a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen // Sets of basic blocks surrounding a machine loop. 996a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen struct LoopBlocks { 1006a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen BlockPtrSet Loop; // Blocks in the loop. 1016a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen BlockPtrSet Preds; // Loop predecessor blocks. 1026a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen BlockPtrSet Exits; // Loop exit blocks. 1036a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen 1046a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen void clear() { 1056a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen Loop.clear(); 1066a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen Preds.clear(); 1076a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen Exits.clear(); 1086a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen } 1096a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen }; 1106a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen 111532de3dc6ea98387368954c0ac0e07b0adca8b62Jakob Stoklund Olesen // Print loop blocks with use counts. 112532de3dc6ea98387368954c0ac0e07b0adca8b62Jakob Stoklund Olesen void print(const LoopBlocks&, raw_ostream&) const; 113532de3dc6ea98387368954c0ac0e07b0adca8b62Jakob Stoklund Olesen 1146a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen // Calculate the block sets surrounding the loop. 1156a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen void getLoopBlocks(const MachineLoop *Loop, LoopBlocks &Blocks); 1166a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen 1178ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen /// LoopPeripheralUse - how is a variable used in and around a loop? 1188ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen /// Peripheral blocks are the loop predecessors and exit blocks. 1198ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen enum LoopPeripheralUse { 1208ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen ContainedInLoop, // All uses are inside the loop. 1218ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen SinglePeripheral, // At most one instruction per peripheral block. 1228ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen MultiPeripheral, // Multiple instructions in some peripheral blocks. 1238ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen OutsideLoop // Uses outside loop periphery. 1248ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen }; 1258ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 1268ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen /// analyzeLoopPeripheralUse - Return an enum describing how curli_ is used in 1278ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen /// and around the Loop. 1286a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen LoopPeripheralUse analyzeLoopPeripheralUse(const LoopBlocks&); 1296a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen 1306a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen /// getCriticalExits - It may be necessary to partially break critical edges 1316a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen /// leaving the loop if an exit block has phi uses of curli. Collect the exit 1326a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen /// blocks that need special treatment into CriticalExits. 1336a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen void getCriticalExits(const LoopBlocks &Blocks, BlockPtrSet &CriticalExits); 1346a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen 1356a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen /// canSplitCriticalExits - Return true if it is possible to insert new exit 1366a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen /// blocks before the blocks in CriticalExits. 1376a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen bool canSplitCriticalExits(const LoopBlocks &Blocks, 1386a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen BlockPtrSet &CriticalExits); 1398ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 1400960a650b7047373da25bee6ec2eb73889c3b7bbJakob Stoklund Olesen /// getCriticalPreds - Get the set of loop predecessors with critical edges to 1410960a650b7047373da25bee6ec2eb73889c3b7bbJakob Stoklund Olesen /// blocks outside the loop that have curli live in. We don't have to break 1420960a650b7047373da25bee6ec2eb73889c3b7bbJakob Stoklund Olesen /// these edges, but they do require special treatment. 1430960a650b7047373da25bee6ec2eb73889c3b7bbJakob Stoklund Olesen void getCriticalPreds(const LoopBlocks &Blocks, BlockPtrSet &CriticalPreds); 1440960a650b7047373da25bee6ec2eb73889c3b7bbJakob Stoklund Olesen 145521a453721aeefbb6783b6acc8ea36b3c18b4931Jakob Stoklund Olesen /// getSplitLoops - Get the set of loops that have curli uses and would be 146521a453721aeefbb6783b6acc8ea36b3c18b4931Jakob Stoklund Olesen /// profitable to split. 147521a453721aeefbb6783b6acc8ea36b3c18b4931Jakob Stoklund Olesen void getSplitLoops(LoopPtrSet&); 148521a453721aeefbb6783b6acc8ea36b3c18b4931Jakob Stoklund Olesen 1498ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen /// getBestSplitLoop - Return the loop where curli may best be split to a 1508ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen /// separate register, or NULL. 1518ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen const MachineLoop *getBestSplitLoop(); 152f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen 153697483addf056595c997302f1316cc59244eefaaJakob Stoklund Olesen /// isBypassLoop - Return true if curli is live through Loop and has no uses 154697483addf056595c997302f1316cc59244eefaaJakob Stoklund Olesen /// inside the loop. Bypass loops are candidates for splitting because it can 155697483addf056595c997302f1316cc59244eefaaJakob Stoklund Olesen /// prevent interference inside the loop. 156697483addf056595c997302f1316cc59244eefaaJakob Stoklund Olesen bool isBypassLoop(const MachineLoop *Loop); 157697483addf056595c997302f1316cc59244eefaaJakob Stoklund Olesen 158697483addf056595c997302f1316cc59244eefaaJakob Stoklund Olesen /// getBypassLoops - Get all the maximal bypass loops. These are the bypass 159697483addf056595c997302f1316cc59244eefaaJakob Stoklund Olesen /// loops whose parent is not a bypass loop. 160697483addf056595c997302f1316cc59244eefaaJakob Stoklund Olesen void getBypassLoops(LoopPtrSet&); 161697483addf056595c997302f1316cc59244eefaaJakob Stoklund Olesen 162f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen /// getMultiUseBlocks - Add basic blocks to Blocks that may benefit from 163f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen /// having curli split to a new live interval. Return true if Blocks can be 164f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen /// passed to SplitEditor::splitSingleBlocks. 165f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen bool getMultiUseBlocks(BlockPtrSet &Blocks); 166fc412d85c46a8656361fe1e9197ea85922e2cd61Jakob Stoklund Olesen 167fc412d85c46a8656361fe1e9197ea85922e2cd61Jakob Stoklund Olesen /// getBlockForInsideSplit - If curli is contained inside a single basic block, 168fc412d85c46a8656361fe1e9197ea85922e2cd61Jakob Stoklund Olesen /// and it wou pay to subdivide the interval inside that block, return it. 169fc412d85c46a8656361fe1e9197ea85922e2cd61Jakob Stoklund Olesen /// Otherwise return NULL. The returned block can be passed to 170fc412d85c46a8656361fe1e9197ea85922e2cd61Jakob Stoklund Olesen /// SplitEditor::splitInsideBlock. 171fc412d85c46a8656361fe1e9197ea85922e2cd61Jakob Stoklund Olesen const MachineBasicBlock *getBlockForInsideSplit(); 1728ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen}; 1738ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 1741407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen 1751407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen/// LiveIntervalMap - Map values from a large LiveInterval into a small 1761407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen/// interval that is a subset. Insert phi-def values as needed. This class is 1771407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen/// used by SplitEditor to create new smaller LiveIntervals. 1781407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen/// 1791407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen/// parentli_ is the larger interval, li_ is the subset interval. Every value 1801407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen/// in li_ corresponds to exactly one value in parentli_, and the live range 1811407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen/// of the value is contained within the live range of the parentli_ value. 1821407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen/// Values in parentli_ may map to any number of openli_ values, including 0. 1831407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesenclass LiveIntervalMap { 1841407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen LiveIntervals &lis_; 185d68f458244b9d9a6644a9550dd5cee60331c9e7dJakob Stoklund Olesen MachineDominatorTree &mdt_; 1861407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen 1871407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen // The parent interval is never changed. 1881407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen const LiveInterval &parentli_; 1891407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen 1901407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen // The child interval's values are fully contained inside parentli_ values. 1919ca2aeb2d223d11fd01b0bb8f13fe7f3a969714dJakob Stoklund Olesen LiveInterval *li_; 1921407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen 1931407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen typedef DenseMap<const VNInfo*, VNInfo*> ValueMap; 1941407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen 1951407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen // Map parentli_ values to simple values in li_ that are defined at the same 1961407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen // SlotIndex, or NULL for parentli_ values that have complex li_ defs. 1971407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen // Note there is a difference between values mapping to NULL (complex), and 1981407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen // values not present (unknown/unmapped). 1991407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen ValueMap valueMap_; 2001407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen 201e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen typedef std::pair<VNInfo*, MachineDomTreeNode*> LiveOutPair; 202e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen typedef DenseMap<MachineBasicBlock*,LiveOutPair> LiveOutMap; 203e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen 204e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // liveOutCache_ - Map each basic block where li_ is live out to the live-out 205e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // value and its defining block. One of these conditions shall be true: 206e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // 207e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // 1. !liveOutCache_.count(MBB) 208e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // 2. liveOutCache_[MBB].second.getNode() == MBB 209e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // 3. forall P in preds(MBB): liveOutCache_[P] == liveOutCache_[MBB] 210e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // 211e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // This is only a cache, the values can be computed as: 212e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // 213e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // VNI = li_->getVNInfoAt(lis_.getMBBEndIdx(MBB)) 214e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // Node = mbt_[lis_.getMBBFromIndex(VNI->def)] 215e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // 216e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen // The cache is also used as a visiteed set by mapValue(). 217e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen LiveOutMap liveOutCache_; 218e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen 2191407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesenpublic: 2201407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen LiveIntervalMap(LiveIntervals &lis, 221d68f458244b9d9a6644a9550dd5cee60331c9e7dJakob Stoklund Olesen MachineDominatorTree &mdt, 2229ca2aeb2d223d11fd01b0bb8f13fe7f3a969714dJakob Stoklund Olesen const LiveInterval &parentli) 223d68f458244b9d9a6644a9550dd5cee60331c9e7dJakob Stoklund Olesen : lis_(lis), mdt_(mdt), parentli_(parentli), li_(0) {} 2249ca2aeb2d223d11fd01b0bb8f13fe7f3a969714dJakob Stoklund Olesen 2259ca2aeb2d223d11fd01b0bb8f13fe7f3a969714dJakob Stoklund Olesen /// reset - clear all data structures and start a new live interval. 2269ca2aeb2d223d11fd01b0bb8f13fe7f3a969714dJakob Stoklund Olesen void reset(LiveInterval *); 2279ca2aeb2d223d11fd01b0bb8f13fe7f3a969714dJakob Stoklund Olesen 2289ca2aeb2d223d11fd01b0bb8f13fe7f3a969714dJakob Stoklund Olesen /// getLI - return the current live interval. 2299ca2aeb2d223d11fd01b0bb8f13fe7f3a969714dJakob Stoklund Olesen LiveInterval *getLI() const { return li_; } 2301407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen 2311407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen /// defValue - define a value in li_ from the parentli_ value VNI and Idx. 2321407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen /// Idx does not have to be ParentVNI->def, but it must be contained within 2331407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen /// ParentVNI's live range in parentli_. 2341407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen /// Return the new li_ value. 2351407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen VNInfo *defValue(const VNInfo *ParentVNI, SlotIndex Idx); 2361407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen 2371407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen /// mapValue - map ParentVNI to the corresponding li_ value at Idx. It is 2381407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen /// assumed that ParentVNI is live at Idx. 2391407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen /// If ParentVNI has not been defined by defValue, it is assumed that 2401407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen /// ParentVNI->def dominates Idx. 2411407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen /// If ParentVNI has been defined by defValue one or more times, a value that 2421407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen /// dominates Idx will be returned. This may require creating extra phi-def 2431407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen /// values and adding live ranges to li_. 2445fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen /// If simple is not NULL, *simple will indicate if ParentVNI is a simply 2455fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen /// mapped value. 2465fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen VNInfo *mapValue(const VNInfo *ParentVNI, SlotIndex Idx, bool *simple = 0); 2475fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen 248fc60d7729bb5b63b7d61e370e51bd05e9a18b8bcJakob Stoklund Olesen // extendTo - Find the last li_ value defined in MBB at or before Idx. The 249fc60d7729bb5b63b7d61e370e51bd05e9a18b8bcJakob Stoklund Olesen // parentli is assumed to be live at Idx. Extend the live range to include 250fc60d7729bb5b63b7d61e370e51bd05e9a18b8bcJakob Stoklund Olesen // Idx. Return the found VNInfo, or NULL. 251c95c1465fdba059f6cbf24d1d9fd84f442c60fe4Jakob Stoklund Olesen VNInfo *extendTo(const MachineBasicBlock *MBB, SlotIndex Idx); 252fc60d7729bb5b63b7d61e370e51bd05e9a18b8bcJakob Stoklund Olesen 2535fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen /// isMapped - Return true is ParentVNI is a known mapped value. It may be a 2545fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen /// simple 1-1 mapping or a complex mapping to later defs. 2555fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen bool isMapped(const VNInfo *ParentVNI) const { 2565fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen return valueMap_.count(ParentVNI); 2575fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen } 2585fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen 2595fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen /// isComplexMapped - Return true if ParentVNI has received new definitions 2605fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen /// with defValue. 2615fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen bool isComplexMapped(const VNInfo *ParentVNI) const; 2625fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen 2635fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen // addSimpleRange - Add a simple range from parentli_ to li_. 2645fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen // ParentVNI must be live in the [Start;End) interval. 2655fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen void addSimpleRange(SlotIndex Start, SlotIndex End, const VNInfo *ParentVNI); 2661407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen 2671407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen /// addRange - Add live ranges to li_ where [Start;End) intersects parentli_. 2681407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen /// All needed values whose def is not inside [Start;End) must be defined 2691407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen /// beforehand so mapValue will work. 2701407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen void addRange(SlotIndex Start, SlotIndex End); 2711407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen}; 2721407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen 2731407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen 274f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen/// SplitEditor - Edit machine code and LiveIntervals for live range 275f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen/// splitting. 276f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen/// 2775eb308b9448ee5b14fac26c0533eac481bc28471Jakob Stoklund Olesen/// - Create a SplitEditor from a SplitAnalysis. 2787536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen/// - Start a new live interval with openIntv. 2797536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen/// - Mark the places where the new interval is entered using enterIntv* 2807536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen/// - Mark the ranges where the new interval is used with useIntv* 2817536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen/// - Mark the places where the interval is exited with exitIntv*. 2827536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen/// - Finish the current interval with closeIntv and repeat from 2. 2837466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen/// - Rewrite instructions with finish(). 284f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen/// 285f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesenclass SplitEditor { 286f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen SplitAnalysis &sa_; 287f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen LiveIntervals &lis_; 288f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen VirtRegMap &vrm_; 289f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen MachineRegisterInfo &mri_; 290f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen const TargetInstrInfo &tii_; 291cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen const TargetRegisterInfo &tri_; 292f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 293a17768f5822ab62bc18608e5ba473187bf726b84Jakob Stoklund Olesen /// edit_ - The current parent register and new intervals created. 294a17768f5822ab62bc18608e5ba473187bf726b84Jakob Stoklund Olesen LiveRangeEdit &edit_; 295a17768f5822ab62bc18608e5ba473187bf726b84Jakob Stoklund Olesen 2965eb308b9448ee5b14fac26c0533eac481bc28471Jakob Stoklund Olesen /// dupli_ - Created as a copy of curli_, ranges are carved out as new 2975eb308b9448ee5b14fac26c0533eac481bc28471Jakob Stoklund Olesen /// intervals get added through openIntv / closeIntv. This is used to avoid 2985eb308b9448ee5b14fac26c0533eac481bc28471Jakob Stoklund Olesen /// editing curli_. 299dd9f3fdc77b77b10710c27050d508d7c7fb40c25Jakob Stoklund Olesen LiveIntervalMap dupli_; 300f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 301f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen /// Currently open LiveInterval. 302dd9f3fdc77b77b10710c27050d508d7c7fb40c25Jakob Stoklund Olesen LiveIntervalMap openli_; 303f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 304cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen /// defFromParent - Define Reg from ParentVNI at UseIdx using either 305cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen /// rematerialization or a COPY from parent. Return the new value. 306cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen VNInfo *defFromParent(LiveIntervalMap &Reg, 307cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen VNInfo *ParentVNI, 308cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen SlotIndex UseIdx, 309cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen MachineBasicBlock &MBB, 310cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen MachineBasicBlock::iterator I); 311cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen 3125fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen /// intervalsLiveAt - Return true if any member of intervals_ is live at Idx. 3135fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen bool intervalsLiveAt(SlotIndex Idx) const; 3145fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen 3155fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen /// Values in curli whose live range has been truncated when entering an open 3165fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen /// li. 3175fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen SmallPtrSet<const VNInfo*, 8> truncatedValues; 3185fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen 3195fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen /// addTruncSimpleRange - Add the given simple range to dupli_ after 3205fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen /// truncating any overlap with intervals_. 3215fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen void addTruncSimpleRange(SlotIndex Start, SlotIndex End, VNInfo *VNI); 322f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 323c95c1465fdba059f6cbf24d1d9fd84f442c60fe4Jakob Stoklund Olesen /// criticalPreds_ - Set of basic blocks where both dupli and openli should be 324c95c1465fdba059f6cbf24d1d9fd84f442c60fe4Jakob Stoklund Olesen /// live out because of a critical edge. 325c95c1465fdba059f6cbf24d1d9fd84f442c60fe4Jakob Stoklund Olesen SplitAnalysis::BlockPtrSet criticalPreds_; 326c95c1465fdba059f6cbf24d1d9fd84f442c60fe4Jakob Stoklund Olesen 3277466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen /// computeRemainder - Compute the dupli liveness as the complement of all the 3287466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen /// new intervals. 3297466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen void computeRemainder(); 3307466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen 3317466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen /// rewrite - Rewrite all uses of reg to use the new registers. 3327466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen void rewrite(unsigned reg); 3337466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen 334f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesenpublic: 335f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen /// Create a new SplitEditor for editing the LiveInterval analyzed by SA. 3367536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen /// Newly created intervals will be appended to newIntervals. 337d68f458244b9d9a6644a9550dd5cee60331c9e7dJakob Stoklund Olesen SplitEditor(SplitAnalysis &SA, LiveIntervals&, VirtRegMap&, 338d68f458244b9d9a6644a9550dd5cee60331c9e7dJakob Stoklund Olesen MachineDominatorTree&, LiveRangeEdit&); 339f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 3405eb308b9448ee5b14fac26c0533eac481bc28471Jakob Stoklund Olesen /// getAnalysis - Get the corresponding analysis. 3415eb308b9448ee5b14fac26c0533eac481bc28471Jakob Stoklund Olesen SplitAnalysis &getAnalysis() { return sa_; } 342f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 3437536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen /// Create a new virtual register and live interval. 3447536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen void openIntv(); 345f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 346f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen /// enterIntvBefore - Enter openli before the instruction at Idx. If curli is 347f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen /// not live before Idx, a COPY is not inserted. 348f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen void enterIntvBefore(SlotIndex Idx); 349f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen 3507536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen /// enterIntvAtEnd - Enter openli at the end of MBB. 351f6a129a24b866635c3c51edf08749755f952b5f2Jakob Stoklund Olesen void enterIntvAtEnd(MachineBasicBlock &MBB); 352f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 3537536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen /// useIntv - indicate that all instructions in MBB should use openli. 3547536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen void useIntv(const MachineBasicBlock &MBB); 355f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 3567536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen /// useIntv - indicate that all instructions in range should use openli. 3577536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen void useIntv(SlotIndex Start, SlotIndex End); 358f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 359f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen /// leaveIntvAfter - Leave openli after the instruction at Idx. 360f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen void leaveIntvAfter(SlotIndex Idx); 361f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen 3627536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen /// leaveIntvAtTop - Leave the interval at the top of MBB. 3637536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen /// Currently, only one value can leave the interval. 3647536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen void leaveIntvAtTop(MachineBasicBlock &MBB); 365f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 3667536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen /// closeIntv - Indicate that we are done editing the currently open 367f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen /// LiveInterval, and ranges can be trimmed. 3687536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen void closeIntv(); 369f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 3707466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen /// finish - after all the new live ranges have been created, compute the 3717466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen /// remaining live range, and rewrite instructions to use the new registers. 3727466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen void finish(); 373f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 374f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen // ===--- High level methods ---=== 375f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 376f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen /// splitAroundLoop - Split curli into a separate live interval inside 37757d0f2deb0afefe69770a28937a4363e7b1f9753Jakob Stoklund Olesen /// the loop. 37857d0f2deb0afefe69770a28937a4363e7b1f9753Jakob Stoklund Olesen void splitAroundLoop(const MachineLoop*); 379f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 380f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen /// splitSingleBlocks - Split curli into a separate live interval inside each 38157d0f2deb0afefe69770a28937a4363e7b1f9753Jakob Stoklund Olesen /// basic block in Blocks. 38257d0f2deb0afefe69770a28937a4363e7b1f9753Jakob Stoklund Olesen void splitSingleBlocks(const SplitAnalysis::BlockPtrSet &Blocks); 38357d0f2deb0afefe69770a28937a4363e7b1f9753Jakob Stoklund Olesen 38457d0f2deb0afefe69770a28937a4363e7b1f9753Jakob Stoklund Olesen /// splitInsideBlock - Split curli into multiple intervals inside MBB. 38557d0f2deb0afefe69770a28937a4363e7b1f9753Jakob Stoklund Olesen void splitInsideBlock(const MachineBasicBlock *); 386fc412d85c46a8656361fe1e9197ea85922e2cd61Jakob Stoklund Olesen}; 3878ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 3888ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen} 389