SplitKit.h revision 13ba2dab631636e525a44bb259aaea56a860d1c7
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 1513ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen#include "llvm/ADT/BitVector.h" 168ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen#include "llvm/ADT/DenseMap.h" 1713ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen#include "llvm/ADT/IndexedMap.h" 180f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher#include "llvm/ADT/IntervalMap.h" 198d0963f72c8922bafffb36ff49b18064098a3cabJakob Stoklund Olesen#include "llvm/ADT/SmallPtrSet.h" 20f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen#include "llvm/CodeGen/SlotIndexes.h" 218ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 228ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesennamespace llvm { 238ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 240f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopherclass ConnectedVNInfoEqClasses; 258ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesenclass LiveInterval; 268ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesenclass LiveIntervals; 27a17768f5822ab62bc18608e5ba473187bf726b84Jakob Stoklund Olesenclass LiveRangeEdit; 288ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesenclass MachineInstr; 298ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesenclass MachineLoopInfo; 30f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesenclass MachineRegisterInfo; 316a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesenclass TargetInstrInfo; 32cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesenclass TargetRegisterInfo; 33f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesenclass VirtRegMap; 34f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesenclass VNInfo; 35532de3dc6ea98387368954c0ac0e07b0adca8b62Jakob Stoklund Olesenclass raw_ostream; 368ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 37e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen/// At some point we should just include MachineDominators.h: 38e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesenclass MachineDominatorTree; 39e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesentemplate <class NodeT> class DomTreeNodeBase; 40e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesentypedef DomTreeNodeBase<MachineBasicBlock> MachineDomTreeNode; 41e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen 428d0963f72c8922bafffb36ff49b18064098a3cabJakob Stoklund Olesen 43f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen/// SplitAnalysis - Analyze a LiveInterval, looking for live range splitting 44f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen/// opportunities. 458ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesenclass SplitAnalysis { 4608e93b14c37277ab40b835de340f89ba357d3332Jakob Stoklund Olesenpublic: 47078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen const MachineFunction &MF; 481b847deb26b52051de39f4cbecd224c9fbd0d1c2Jakob Stoklund Olesen const VirtRegMap &VRM; 49078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen const LiveIntervals &LIS; 50078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen const MachineLoopInfo &Loops; 51078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen const TargetInstrInfo &TII; 528ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 538ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen // Instructions using the the current register. 548ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen typedef SmallPtrSet<const MachineInstr*, 16> InstrPtrSet; 55078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen InstrPtrSet UsingInstrs; 568ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 57b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen // Sorted slot indexes of using instructions. 58b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen SmallVector<SlotIndex, 8> UseSlots; 59b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 60078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen // The number of instructions using CurLI in each basic block. 618ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen typedef DenseMap<const MachineBasicBlock*, unsigned> BlockCountMap; 62078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen BlockCountMap UsingBlocks; 638ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 64f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen /// Additional information about basic blocks where the current variable is 65f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen /// live. Such a block will look like one of these templates: 66f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen /// 67f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen /// 1. | o---x | Internal to block. Variable is only live in this block. 68f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen /// 2. |---x | Live-in, kill. 69f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen /// 3. | o---| Def, live-out. 70f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen /// 4. |---x o---| Live-in, kill, def, live-out. 71f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen /// 5. |---o---o---| Live-through with uses or defs. 72f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen /// 6. |-----------| Live-through without uses. Transparent. 73f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen /// 74f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen struct BlockInfo { 75f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen MachineBasicBlock *MBB; 7636d61863bc83bd2301e0224adc560098b35ec0dcJakob Stoklund Olesen SlotIndex Start; ///< Beginining of block. 7736d61863bc83bd2301e0224adc560098b35ec0dcJakob Stoklund Olesen SlotIndex Stop; ///< End of block. 78f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen SlotIndex FirstUse; ///< First instr using current reg. 79f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen SlotIndex LastUse; ///< Last instr using current reg. 80f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen SlotIndex Kill; ///< Interval end point inside block. 81f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen SlotIndex Def; ///< Interval start point inside block. 82f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen /// Last possible point for splitting live ranges. 83f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen SlotIndex LastSplitPoint; 84f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen bool Uses; ///< Current reg has uses or defs in block. 85f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen bool LiveThrough; ///< Live in whole block (Templ 5. or 6. above). 86f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen bool LiveIn; ///< Current reg is live in. 87f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen bool LiveOut; ///< Current reg is live out. 88f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 89f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen // Per-interference pattern scratch data. 90f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen bool OverlapEntry; ///< Interference overlaps entering interval. 91f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen bool OverlapExit; ///< Interference overlaps exiting interval. 92f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen }; 93f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 94f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen /// Basic blocks where var is live. This array is parallel to 95f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen /// SpillConstraints. 96f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen SmallVector<BlockInfo, 8> LiveBlocks; 97f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 98f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesenprivate: 99f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen // Current live interval. 100078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen const LiveInterval *CurLI; 101f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen 102078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen // Sumarize statistics by counting instructions using CurLI. 103abff28087fd6be8150ff0e69def7de7312b2f76bJakob Stoklund Olesen void analyzeUses(); 1048ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 105f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen /// calcLiveBlockInfo - Compute per-block information about CurLI. 106f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen void calcLiveBlockInfo(); 107f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 1086a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen /// canAnalyzeBranch - Return true if MBB ends in a branch that can be 1096a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen /// analyzed. 1106a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen bool canAnalyzeBranch(const MachineBasicBlock *MBB); 1116a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen 1128ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesenpublic: 1131b847deb26b52051de39f4cbecd224c9fbd0d1c2Jakob Stoklund Olesen SplitAnalysis(const VirtRegMap &vrm, const LiveIntervals &lis, 114f2c6e367c1c0d8797e62e58a3ccdb8cceee27987Jakob Stoklund Olesen const MachineLoopInfo &mli); 1158ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 116078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen /// analyze - set CurLI to the specified interval, and analyze how it may be 1178ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen /// split. 1188ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen void analyze(const LiveInterval *li); 1198ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 1208ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen /// clear - clear all data structures so SplitAnalysis is ready to analyze a 1218ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen /// new interval. 1228ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen void clear(); 1238ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 124034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen /// getParent - Return the last analyzed interval. 125034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen const LiveInterval &getParent() const { return *CurLI; } 126034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 127078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen /// hasUses - Return true if MBB has any uses of CurLI. 128b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen bool hasUses(const MachineBasicBlock *MBB) const { 129078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen return UsingBlocks.lookup(MBB); 130b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen } 131b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 13206c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen /// isOriginalEndpoint - Return true if the original live range was killed or 13306c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen /// (re-)defined at Idx. Idx should be the 'def' slot for a normal kill/def, 13406c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen /// and 'use' for an early-clobber def. 13506c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen /// This can be used to recognize code inserted by earlier live range 13606c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen /// splitting. 13706c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen bool isOriginalEndpoint(SlotIndex Idx) const; 13806c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen 1396a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen typedef SmallPtrSet<const MachineBasicBlock*, 16> BlockPtrSet; 1406a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen 141532de3dc6ea98387368954c0ac0e07b0adca8b62Jakob Stoklund Olesen // Print a set of blocks with use counts. 142532de3dc6ea98387368954c0ac0e07b0adca8b62Jakob Stoklund Olesen void print(const BlockPtrSet&, raw_ostream&) const; 143532de3dc6ea98387368954c0ac0e07b0adca8b62Jakob Stoklund Olesen 144f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen /// getMultiUseBlocks - Add basic blocks to Blocks that may benefit from 145078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen /// having CurLI split to a new live interval. Return true if Blocks can be 146f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen /// passed to SplitEditor::splitSingleBlocks. 147f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen bool getMultiUseBlocks(BlockPtrSet &Blocks); 1488ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen}; 1498ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 1501407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen 151f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen/// SplitEditor - Edit machine code and LiveIntervals for live range 152f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen/// splitting. 153f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen/// 1545eb308b9448ee5b14fac26c0533eac481bc28471Jakob Stoklund Olesen/// - Create a SplitEditor from a SplitAnalysis. 1557536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen/// - Start a new live interval with openIntv. 1567536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen/// - Mark the places where the new interval is entered using enterIntv* 1577536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen/// - Mark the ranges where the new interval is used with useIntv* 1587536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen/// - Mark the places where the interval is exited with exitIntv*. 1597536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen/// - Finish the current interval with closeIntv and repeat from 2. 1607466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen/// - Rewrite instructions with finish(). 161f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen/// 162f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesenclass SplitEditor { 1630eeca440469e23f2db2bea3d7b136f0f95f6ff1dJakob Stoklund Olesen SplitAnalysis &SA; 164078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen LiveIntervals &LIS; 165078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen VirtRegMap &VRM; 166078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen MachineRegisterInfo &MRI; 1670f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher MachineDominatorTree &MDT; 168078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen const TargetInstrInfo &TII; 169078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen const TargetRegisterInfo &TRI; 170f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 171078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen /// Edit - The current parent register and new intervals created. 172a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen LiveRangeEdit *Edit; 173a17768f5822ab62bc18608e5ba473187bf726b84Jakob Stoklund Olesen 1740f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher /// Index into Edit of the currently open interval. 1750f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher /// The index 0 is used for the complement, so the first interval started by 1760f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher /// openIntv will be 1. 1770f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher unsigned OpenIdx; 1780f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher 1790f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher typedef IntervalMap<SlotIndex, unsigned> RegAssignMap; 1800f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher 1810f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher /// Allocator for the interval map. This will eventually be shared with 1820f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher /// SlotIndexes and LiveIntervals. 1830f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher RegAssignMap::Allocator Allocator; 1840f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher 1850f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher /// RegAssign - Map of the assigned register indexes. 1860f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher /// Edit.get(RegAssign.lookup(Idx)) is the register that should be live at 1870f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher /// Idx. 1880f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher RegAssignMap RegAssign; 189f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 190670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen typedef DenseMap<std::pair<unsigned, unsigned>, VNInfo*> ValueMap; 191670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen 192670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen /// Values - keep track of the mapping from parent values to values in the new 193670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen /// intervals. Given a pair (RegIdx, ParentVNI->id), Values contains: 194670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen /// 195670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen /// 1. No entry - the value is not mapped to Edit.get(RegIdx). 196670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen /// 2. Null - the value is mapped to multiple values in Edit.get(RegIdx). 197670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen /// Each value is represented by a minimal live range at its def. 198670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen /// 3. A non-null VNInfo - the value is mapped to a single new value. 199670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen /// The new value has no live ranges anywhere. 200670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen ValueMap Values; 201670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen 2021c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen typedef std::pair<VNInfo*, MachineDomTreeNode*> LiveOutPair; 20313ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen typedef IndexedMap<LiveOutPair, MBB2NumberFunctor> LiveOutMap; 2041c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 2051c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // LiveOutCache - Map each basic block where a new register is live out to the 2061c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // live-out value and its defining block. 2071c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // One of these conditions shall be true: 2081c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // 2091c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // 1. !LiveOutCache.count(MBB) 2101c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // 2. LiveOutCache[MBB].second.getNode() == MBB 2111c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // 3. forall P in preds(MBB): LiveOutCache[P] == LiveOutCache[MBB] 2121c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // 2131c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // This is only a cache, the values can be computed as: 2141c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // 2151c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // VNI = Edit.get(RegIdx)->getVNInfoAt(LIS.getMBBEndIdx(MBB)) 2161c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // Node = mbt_[LIS.getMBBFromIndex(VNI->def)] 2171c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // 2181c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // The cache is also used as a visited set by extendRange(). It can be shared 2191c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // by all the new registers because at most one is live out of each block. 2201c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen LiveOutMap LiveOutCache; 2211c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 22213ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen // LiveOutSeen - Indexed by MBB->getNumber(), a bit is set for each valid 22313ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen // entry in LiveOutCache. 22413ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen BitVector LiveOutSeen; 22513ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen 226670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen /// defValue - define a value in RegIdx from ParentVNI at Idx. 227670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen /// Idx does not have to be ParentVNI->def, but it must be contained within 228670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen /// ParentVNI's live range in ParentLI. The new value is added to the value 229670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen /// map. 230670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen /// Return the new LI value. 231670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen VNInfo *defValue(unsigned RegIdx, const VNInfo *ParentVNI, SlotIndex Idx); 232670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen 233670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen /// markComplexMapped - Mark ParentVNI as complex mapped in RegIdx regardless 234670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen /// of the number of defs. 235670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen void markComplexMapped(unsigned RegIdx, const VNInfo *ParentVNI); 236670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen 237cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen /// defFromParent - Define Reg from ParentVNI at UseIdx using either 238cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen /// rematerialization or a COPY from parent. Return the new value. 2390f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher VNInfo *defFromParent(unsigned RegIdx, 240cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen VNInfo *ParentVNI, 241cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen SlotIndex UseIdx, 242cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen MachineBasicBlock &MBB, 243cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen MachineBasicBlock::iterator I); 244cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen 2451c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen /// extendRange - Extend the live range of Edit.get(RegIdx) so it reaches Idx. 2461c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen /// Insert PHIDefs as needed to preserve SSA form. 2471c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen void extendRange(unsigned RegIdx, SlotIndex Idx); 2481c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 2491c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen /// updateSSA - Insert PHIDefs as necessary and update LiveOutCache such that 2501c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen /// Edit.get(RegIdx) is live-in to all the blocks in LiveIn. 2511c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen /// Return the value that is eventually live-in to IdxMBB. 2521c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen VNInfo *updateSSA(unsigned RegIdx, 2531c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen SmallVectorImpl<MachineDomTreeNode*> &LiveIn, 2541c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen SlotIndex Idx, 2551c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen const MachineBasicBlock *IdxMBB); 2561c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 2574670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen /// transferSimpleValues - Transfer simply defined values to the new ranges. 2584670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen /// Return true if any complex ranges were skipped. 2594670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen bool transferSimpleValues(); 2604670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen 261e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen /// extendPHIKillRanges - Extend the ranges of all values killed by original 262e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen /// parent PHIDefs. 263e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen void extendPHIKillRanges(); 264e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen 2650f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher /// rewriteAssigned - Rewrite all uses of Edit.getReg() to assigned registers. 2664670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen void rewriteAssigned(bool ExtendRanges); 2675fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen 2680f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher /// rewriteComponents - Rewrite all uses of Intv[0] according to the eq 2690f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher /// classes in ConEQ. 2700f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher /// This must be done when Intvs[0] is styill live at all uses, before calling 2710f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher /// ConEq.Distribute(). 2720f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher void rewriteComponents(const SmallVectorImpl<LiveInterval*> &Intvs, 2730f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher const ConnectedVNInfoEqClasses &ConEq); 2747466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen 275f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesenpublic: 276f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen /// Create a new SplitEditor for editing the LiveInterval analyzed by SA. 2777536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen /// Newly created intervals will be appended to newIntervals. 278d68f458244b9d9a6644a9550dd5cee60331c9e7dJakob Stoklund Olesen SplitEditor(SplitAnalysis &SA, LiveIntervals&, VirtRegMap&, 279bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen MachineDominatorTree&); 280f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 281bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen /// reset - Prepare for a new split. 282bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen void reset(LiveRangeEdit&); 283f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 2847536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen /// Create a new virtual register and live interval. 2857536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen void openIntv(); 286f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 287207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen /// enterIntvBefore - Enter the open interval before the instruction at Idx. 288207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen /// If the parent interval is not live before Idx, a COPY is not inserted. 289207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen /// Return the beginning of the new live range. 290207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen SlotIndex enterIntvBefore(SlotIndex Idx); 291f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen 292207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen /// enterIntvAtEnd - Enter the open interval at the end of MBB. 293207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen /// Use the open interval from he inserted copy to the MBB end. 294207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen /// Return the beginning of the new live range. 295207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen SlotIndex enterIntvAtEnd(MachineBasicBlock &MBB); 296f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 297078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen /// useIntv - indicate that all instructions in MBB should use OpenLI. 2987536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen void useIntv(const MachineBasicBlock &MBB); 299f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 300078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen /// useIntv - indicate that all instructions in range should use OpenLI. 3017536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen void useIntv(SlotIndex Start, SlotIndex End); 302f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 303207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen /// leaveIntvAfter - Leave the open interval after the instruction at Idx. 304207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen /// Return the end of the live range. 305207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen SlotIndex leaveIntvAfter(SlotIndex Idx); 306f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen 3079b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen /// leaveIntvBefore - Leave the open interval before the instruction at Idx. 3089b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen /// Return the end of the live range. 3099b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen SlotIndex leaveIntvBefore(SlotIndex Idx); 3109b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen 3117536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen /// leaveIntvAtTop - Leave the interval at the top of MBB. 312207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen /// Add liveness from the MBB top to the copy. 313207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen /// Return the end of the live range. 314207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen SlotIndex leaveIntvAtTop(MachineBasicBlock &MBB); 315f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 3165c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen /// overlapIntv - Indicate that all instructions in range should use the open 3175c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen /// interval, but also let the complement interval be live. 3185c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen /// 3195c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen /// This doubles the register pressure, but is sometimes required to deal with 3205c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen /// register uses after the last valid split point. 3215c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen /// 3225c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen /// The Start index should be a return value from a leaveIntv* call, and End 3235c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen /// should be in the same basic block. The parent interval must have the same 3245c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen /// value across the range. 3255c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen /// 3265c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen void overlapIntv(SlotIndex Start, SlotIndex End); 3275c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen 3287536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen /// closeIntv - Indicate that we are done editing the currently open 329f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen /// LiveInterval, and ranges can be trimmed. 3307536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen void closeIntv(); 331f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 3327466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen /// finish - after all the new live ranges have been created, compute the 3337466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen /// remaining live range, and rewrite instructions to use the new registers. 3347466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen void finish(); 335f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 3360f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher /// dump - print the current interval maping to dbgs(). 3370f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher void dump() const; 3380f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher 339f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen // ===--- High level methods ---=== 340f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 341078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen /// splitSingleBlocks - Split CurLI into a separate live interval inside each 34257d0f2deb0afefe69770a28937a4363e7b1f9753Jakob Stoklund Olesen /// basic block in Blocks. 34357d0f2deb0afefe69770a28937a4363e7b1f9753Jakob Stoklund Olesen void splitSingleBlocks(const SplitAnalysis::BlockPtrSet &Blocks); 344fc412d85c46a8656361fe1e9197ea85922e2cd61Jakob Stoklund Olesen}; 3458ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 3468ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen} 347