SplitKit.h revision 2dee7a527b083e259f9e826c57c1e5dab9540798
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#include "llvm/ADT/SmallPtrSet.h" 168ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen#include "llvm/ADT/DenseMap.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; 238ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesenclass MachineInstr; 248ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesenclass MachineLoop; 258ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesenclass MachineLoopInfo; 26f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesenclass MachineRegisterInfo; 276a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesenclass TargetInstrInfo; 28f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesenclass VirtRegMap; 29f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesenclass VNInfo; 308ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 31f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen/// SplitAnalysis - Analyze a LiveInterval, looking for live range splitting 32f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen/// opportunities. 338ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesenclass SplitAnalysis { 3408e93b14c37277ab40b835de340f89ba357d3332Jakob Stoklund Olesenpublic: 358ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen const MachineFunction &mf_; 368ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen const LiveIntervals &lis_; 378ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen const MachineLoopInfo &loops_; 386a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen const TargetInstrInfo &tii_; 398ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 408ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen // Instructions using the the current register. 418ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen typedef SmallPtrSet<const MachineInstr*, 16> InstrPtrSet; 428ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen InstrPtrSet usingInstrs_; 438ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 448ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen // The number of instructions using curli in each basic block. 458ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen typedef DenseMap<const MachineBasicBlock*, unsigned> BlockCountMap; 468ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen BlockCountMap usingBlocks_; 478ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 482dee7a527b083e259f9e826c57c1e5dab9540798Jakob Stoklund Olesen // The number of basic block using curli in each loop. 492dee7a527b083e259f9e826c57c1e5dab9540798Jakob Stoklund Olesen typedef DenseMap<const MachineLoop*, unsigned> LoopCountMap; 502dee7a527b083e259f9e826c57c1e5dab9540798Jakob Stoklund Olesen LoopCountMap usingLoops_; 518ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 52f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesenprivate: 53f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen // Current live interval. 54f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen const LiveInterval *curli_; 55f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen 568ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen // Sumarize statistics by counting instructions using curli_. 57abff28087fd6be8150ff0e69def7de7312b2f76bJakob Stoklund Olesen void analyzeUses(); 588ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 596a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen /// canAnalyzeBranch - Return true if MBB ends in a branch that can be 606a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen /// analyzed. 616a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen bool canAnalyzeBranch(const MachineBasicBlock *MBB); 626a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen 638ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesenpublic: 64f2c6e367c1c0d8797e62e58a3ccdb8cceee27987Jakob Stoklund Olesen SplitAnalysis(const MachineFunction &mf, const LiveIntervals &lis, 65f2c6e367c1c0d8797e62e58a3ccdb8cceee27987Jakob Stoklund Olesen const MachineLoopInfo &mli); 668ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 678ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen /// analyze - set curli to the specified interval, and analyze how it may be 688ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen /// split. 698ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen void analyze(const LiveInterval *li); 708ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 712dee7a527b083e259f9e826c57c1e5dab9540798Jakob Stoklund Olesen /// removeUse - Update statistics by noting that mi no longer uses curli. 722dee7a527b083e259f9e826c57c1e5dab9540798Jakob Stoklund Olesen void removeUse(const MachineInstr *mi); 732dee7a527b083e259f9e826c57c1e5dab9540798Jakob Stoklund Olesen 74f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen const LiveInterval *getCurLI() { return curli_; } 75f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 768ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen /// clear - clear all data structures so SplitAnalysis is ready to analyze a 778ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen /// new interval. 788ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen void clear(); 798ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 806a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen typedef SmallPtrSet<const MachineBasicBlock*, 16> BlockPtrSet; 812dee7a527b083e259f9e826c57c1e5dab9540798Jakob Stoklund Olesen typedef SmallPtrSet<const MachineLoop*, 16> LoopPtrSet; 826a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen 836a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen // Sets of basic blocks surrounding a machine loop. 846a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen struct LoopBlocks { 856a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen BlockPtrSet Loop; // Blocks in the loop. 866a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen BlockPtrSet Preds; // Loop predecessor blocks. 876a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen BlockPtrSet Exits; // Loop exit blocks. 886a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen 896a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen void clear() { 906a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen Loop.clear(); 916a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen Preds.clear(); 926a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen Exits.clear(); 936a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen } 946a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen }; 956a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen 966a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen // Calculate the block sets surrounding the loop. 976a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen void getLoopBlocks(const MachineLoop *Loop, LoopBlocks &Blocks); 986a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen 998ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen /// LoopPeripheralUse - how is a variable used in and around a loop? 1008ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen /// Peripheral blocks are the loop predecessors and exit blocks. 1018ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen enum LoopPeripheralUse { 1028ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen ContainedInLoop, // All uses are inside the loop. 1038ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen SinglePeripheral, // At most one instruction per peripheral block. 1048ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen MultiPeripheral, // Multiple instructions in some peripheral blocks. 1058ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen OutsideLoop // Uses outside loop periphery. 1068ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen }; 1078ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 1088ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen /// analyzeLoopPeripheralUse - Return an enum describing how curli_ is used in 1098ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen /// and around the Loop. 1106a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen LoopPeripheralUse analyzeLoopPeripheralUse(const LoopBlocks&); 1116a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen 1126a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen /// getCriticalExits - It may be necessary to partially break critical edges 1136a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen /// leaving the loop if an exit block has phi uses of curli. Collect the exit 1146a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen /// blocks that need special treatment into CriticalExits. 1156a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen void getCriticalExits(const LoopBlocks &Blocks, BlockPtrSet &CriticalExits); 1166a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen 1176a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen /// canSplitCriticalExits - Return true if it is possible to insert new exit 1186a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen /// blocks before the blocks in CriticalExits. 1196a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen bool canSplitCriticalExits(const LoopBlocks &Blocks, 1206a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen BlockPtrSet &CriticalExits); 1218ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 1228ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen /// getBestSplitLoop - Return the loop where curli may best be split to a 1238ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen /// separate register, or NULL. 1248ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen const MachineLoop *getBestSplitLoop(); 125f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen 126f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen /// getMultiUseBlocks - Add basic blocks to Blocks that may benefit from 127f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen /// having curli split to a new live interval. Return true if Blocks can be 128f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen /// passed to SplitEditor::splitSingleBlocks. 129f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen bool getMultiUseBlocks(BlockPtrSet &Blocks); 1308ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen}; 1318ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 132f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen/// SplitEditor - Edit machine code and LiveIntervals for live range 133f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen/// splitting. 134f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen/// 1355eb308b9448ee5b14fac26c0533eac481bc28471Jakob Stoklund Olesen/// - Create a SplitEditor from a SplitAnalysis. 1367536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen/// - Start a new live interval with openIntv. 1377536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen/// - Mark the places where the new interval is entered using enterIntv* 1387536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen/// - Mark the ranges where the new interval is used with useIntv* 1397536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen/// - Mark the places where the interval is exited with exitIntv*. 1407536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen/// - Finish the current interval with closeIntv and repeat from 2. 1417536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen/// - Rewrite instructions with rewrite(). 142f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen/// 143f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesenclass SplitEditor { 144f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen SplitAnalysis &sa_; 145f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen LiveIntervals &lis_; 146f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen VirtRegMap &vrm_; 147f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen MachineRegisterInfo &mri_; 148f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen const TargetInstrInfo &tii_; 149f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 1505eb308b9448ee5b14fac26c0533eac481bc28471Jakob Stoklund Olesen /// curli_ - The immutable interval we are currently splitting. 1515eb308b9448ee5b14fac26c0533eac481bc28471Jakob Stoklund Olesen const LiveInterval *const curli_; 1525eb308b9448ee5b14fac26c0533eac481bc28471Jakob Stoklund Olesen 1535eb308b9448ee5b14fac26c0533eac481bc28471Jakob Stoklund Olesen /// dupli_ - Created as a copy of curli_, ranges are carved out as new 1545eb308b9448ee5b14fac26c0533eac481bc28471Jakob Stoklund Olesen /// intervals get added through openIntv / closeIntv. This is used to avoid 1555eb308b9448ee5b14fac26c0533eac481bc28471Jakob Stoklund Olesen /// editing curli_. 156f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen LiveInterval *dupli_; 157f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 158f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen /// Currently open LiveInterval. 159f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen LiveInterval *openli_; 160f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 161f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen /// createInterval - Create a new virtual register and LiveInterval with same 162f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen /// register class and spill slot as curli. 163f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen LiveInterval *createInterval(); 164f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 1655eb308b9448ee5b14fac26c0533eac481bc28471Jakob Stoklund Olesen /// getDupLI - Ensure dupli is created and return it. 1665eb308b9448ee5b14fac26c0533eac481bc28471Jakob Stoklund Olesen LiveInterval *getDupLI(); 1675eb308b9448ee5b14fac26c0533eac481bc28471Jakob Stoklund Olesen 168f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen /// valueMap_ - Map values in cupli to values in openli. These are direct 1-1 1695eb308b9448ee5b14fac26c0533eac481bc28471Jakob Stoklund Olesen /// mappings, and do not include values created by inserted copies. 1705eb308b9448ee5b14fac26c0533eac481bc28471Jakob Stoklund Olesen DenseMap<const VNInfo*, VNInfo*> valueMap_; 171f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 1725eb308b9448ee5b14fac26c0533eac481bc28471Jakob Stoklund Olesen /// mapValue - Return the openIntv value that corresponds to the given curli 1735eb308b9448ee5b14fac26c0533eac481bc28471Jakob Stoklund Olesen /// value. 1745eb308b9448ee5b14fac26c0533eac481bc28471Jakob Stoklund Olesen VNInfo *mapValue(const VNInfo *curliVNI); 1757536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen 1767536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen /// A dupli value is live through openIntv. 1777536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen bool liveThrough_; 1787536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen 1797536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen /// All the new intervals created for this split are added to intervals_. 1807536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen std::vector<LiveInterval*> &intervals_; 1817536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen 1827536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen /// The index into intervals_ of the first interval we added. There may be 1837536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen /// others from before we got it. 1847536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen unsigned firstInterval; 1857536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen 1867536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen /// Insert a COPY instruction curli -> li. Allocate a new value from li 1877536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen /// defined by the COPY 1887536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen VNInfo *insertCopy(LiveInterval &LI, 1897536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen MachineBasicBlock &MBB, 1907536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen MachineBasicBlock::iterator I); 191f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 192f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesenpublic: 193f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen /// Create a new SplitEditor for editing the LiveInterval analyzed by SA. 1947536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen /// Newly created intervals will be appended to newIntervals. 1957536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen SplitEditor(SplitAnalysis &SA, LiveIntervals&, VirtRegMap&, 1967536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen std::vector<LiveInterval*> &newIntervals); 197f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 1985eb308b9448ee5b14fac26c0533eac481bc28471Jakob Stoklund Olesen /// getAnalysis - Get the corresponding analysis. 1995eb308b9448ee5b14fac26c0533eac481bc28471Jakob Stoklund Olesen SplitAnalysis &getAnalysis() { return sa_; } 200f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 2017536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen /// Create a new virtual register and live interval. 2027536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen void openIntv(); 203f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 204f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen /// enterIntvBefore - Enter openli before the instruction at Idx. If curli is 205f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen /// not live before Idx, a COPY is not inserted. 206f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen void enterIntvBefore(SlotIndex Idx); 207f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen 2087536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen /// enterIntvAtEnd - Enter openli at the end of MBB. 2097536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen /// PhiMBB is a successor inside openli where a PHI value is created. 2107536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen /// Currently, all entries must share the same PhiMBB. 2117536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen void enterIntvAtEnd(MachineBasicBlock &MBB, MachineBasicBlock &PhiMBB); 212f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 2137536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen /// useIntv - indicate that all instructions in MBB should use openli. 2147536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen void useIntv(const MachineBasicBlock &MBB); 215f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 2167536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen /// useIntv - indicate that all instructions in range should use openli. 2177536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen void useIntv(SlotIndex Start, SlotIndex End); 218f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 219f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen /// leaveIntvAfter - Leave openli after the instruction at Idx. 220f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen void leaveIntvAfter(SlotIndex Idx); 221f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen 2227536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen /// leaveIntvAtTop - Leave the interval at the top of MBB. 2237536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen /// Currently, only one value can leave the interval. 2247536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen void leaveIntvAtTop(MachineBasicBlock &MBB); 225f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 2267536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen /// closeIntv - Indicate that we are done editing the currently open 227f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen /// LiveInterval, and ranges can be trimmed. 2287536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen void closeIntv(); 229f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 230f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen /// rewrite - after all the new live ranges have been created, rewrite 231f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen /// instructions using curli to use the new intervals. 232f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen void rewrite(); 233f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 234f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen // ===--- High level methods ---=== 235f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 236f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen /// splitAroundLoop - Split curli into a separate live interval inside 2375eb308b9448ee5b14fac26c0533eac481bc28471Jakob Stoklund Olesen /// the loop. Return true if curli has been completely replaced, false if 2385eb308b9448ee5b14fac26c0533eac481bc28471Jakob Stoklund Olesen /// curli is still intact, and needs to be spilled or split further. 2395eb308b9448ee5b14fac26c0533eac481bc28471Jakob Stoklund Olesen bool splitAroundLoop(const MachineLoop*); 240f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 241f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen /// splitSingleBlocks - Split curli into a separate live interval inside each 242f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen /// basic block in Blocks. Return true if curli has been completely replaced, 243f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen /// false if curli is still intact, and needs to be spilled or split further. 244f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen bool splitSingleBlocks(const SplitAnalysis::BlockPtrSet &Blocks); 245f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen}; 246f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 2478ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 2488ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen} 249