SplitKit.h revision bece06f0c6936527e2b1c72d09f7d3a949af9a47
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" 160f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher#include "llvm/ADT/IntervalMap.h" 178d0963f72c8922bafffb36ff49b18064098a3cabJakob Stoklund Olesen#include "llvm/ADT/SmallPtrSet.h" 18f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen#include "llvm/CodeGen/SlotIndexes.h" 198ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 208ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesennamespace llvm { 218ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 220f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopherclass ConnectedVNInfoEqClasses; 238ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesenclass LiveInterval; 248ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesenclass LiveIntervals; 25a17768f5822ab62bc18608e5ba473187bf726b84Jakob Stoklund Olesenclass LiveRangeEdit; 268ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesenclass MachineInstr; 278ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesenclass MachineLoopInfo; 28f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesenclass MachineRegisterInfo; 296a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesenclass TargetInstrInfo; 30cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesenclass TargetRegisterInfo; 31f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesenclass VirtRegMap; 32f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesenclass VNInfo; 33532de3dc6ea98387368954c0ac0e07b0adca8b62Jakob Stoklund Olesenclass raw_ostream; 348ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 35e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen/// At some point we should just include MachineDominators.h: 36e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesenclass MachineDominatorTree; 37e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesentemplate <class NodeT> class DomTreeNodeBase; 38e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesentypedef DomTreeNodeBase<MachineBasicBlock> MachineDomTreeNode; 39e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen 408d0963f72c8922bafffb36ff49b18064098a3cabJakob Stoklund Olesen 41f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen/// SplitAnalysis - Analyze a LiveInterval, looking for live range splitting 42f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen/// opportunities. 438ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesenclass SplitAnalysis { 4408e93b14c37277ab40b835de340f89ba357d3332Jakob Stoklund Olesenpublic: 45078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen const MachineFunction &MF; 461b847deb26b52051de39f4cbecd224c9fbd0d1c2Jakob Stoklund Olesen const VirtRegMap &VRM; 47078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen const LiveIntervals &LIS; 48078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen const MachineLoopInfo &Loops; 49078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen const TargetInstrInfo &TII; 508ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 518ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen // Instructions using the the current register. 528ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen typedef SmallPtrSet<const MachineInstr*, 16> InstrPtrSet; 53078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen InstrPtrSet UsingInstrs; 548ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 55b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen // Sorted slot indexes of using instructions. 56b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen SmallVector<SlotIndex, 8> UseSlots; 57b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 58078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen // The number of instructions using CurLI in each basic block. 598ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen typedef DenseMap<const MachineBasicBlock*, unsigned> BlockCountMap; 60078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen BlockCountMap UsingBlocks; 618ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 62f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen /// Additional information about basic blocks where the current variable is 63f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen /// live. Such a block will look like one of these templates: 64f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen /// 65f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen /// 1. | o---x | Internal to block. Variable is only live in this block. 66f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen /// 2. |---x | Live-in, kill. 67f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen /// 3. | o---| Def, live-out. 68f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen /// 4. |---x o---| Live-in, kill, def, live-out. 69f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen /// 5. |---o---o---| Live-through with uses or defs. 70f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen /// 6. |-----------| Live-through without uses. Transparent. 71f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen /// 72f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen struct BlockInfo { 73f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen MachineBasicBlock *MBB; 74f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen SlotIndex FirstUse; ///< First instr using current reg. 75f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen SlotIndex LastUse; ///< Last instr using current reg. 76f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen SlotIndex Kill; ///< Interval end point inside block. 77f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen SlotIndex Def; ///< Interval start point inside block. 78f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen /// Last possible point for splitting live ranges. 79f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen SlotIndex LastSplitPoint; 80f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen bool Uses; ///< Current reg has uses or defs in block. 81f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen bool LiveThrough; ///< Live in whole block (Templ 5. or 6. above). 82f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen bool LiveIn; ///< Current reg is live in. 83f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen bool LiveOut; ///< Current reg is live out. 84f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 85f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen // Per-interference pattern scratch data. 86f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen bool OverlapEntry; ///< Interference overlaps entering interval. 87f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen bool OverlapExit; ///< Interference overlaps exiting interval. 88f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen }; 89f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 90f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen /// Basic blocks where var is live. This array is parallel to 91f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen /// SpillConstraints. 92f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen SmallVector<BlockInfo, 8> LiveBlocks; 93f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 94f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesenprivate: 95f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen // Current live interval. 96078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen const LiveInterval *CurLI; 97f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen 98078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen // Sumarize statistics by counting instructions using CurLI. 99abff28087fd6be8150ff0e69def7de7312b2f76bJakob Stoklund Olesen void analyzeUses(); 1008ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 101f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen /// calcLiveBlockInfo - Compute per-block information about CurLI. 102f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen void calcLiveBlockInfo(); 103f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 1046a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen /// canAnalyzeBranch - Return true if MBB ends in a branch that can be 1056a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen /// analyzed. 1066a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen bool canAnalyzeBranch(const MachineBasicBlock *MBB); 1076a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen 1088ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesenpublic: 1091b847deb26b52051de39f4cbecd224c9fbd0d1c2Jakob Stoklund Olesen SplitAnalysis(const VirtRegMap &vrm, const LiveIntervals &lis, 110f2c6e367c1c0d8797e62e58a3ccdb8cceee27987Jakob Stoklund Olesen const MachineLoopInfo &mli); 1118ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 112078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen /// analyze - set CurLI to the specified interval, and analyze how it may be 1138ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen /// split. 1148ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen void analyze(const LiveInterval *li); 1158ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 1168ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen /// clear - clear all data structures so SplitAnalysis is ready to analyze a 1178ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen /// new interval. 1188ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen void clear(); 1198ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 120034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen /// getParent - Return the last analyzed interval. 121034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen const LiveInterval &getParent() const { return *CurLI; } 122034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 123078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen /// hasUses - Return true if MBB has any uses of CurLI. 124b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen bool hasUses(const MachineBasicBlock *MBB) const { 125078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen return UsingBlocks.lookup(MBB); 126b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen } 127b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 12806c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen /// isOriginalEndpoint - Return true if the original live range was killed or 12906c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen /// (re-)defined at Idx. Idx should be the 'def' slot for a normal kill/def, 13006c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen /// and 'use' for an early-clobber def. 13106c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen /// This can be used to recognize code inserted by earlier live range 13206c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen /// splitting. 13306c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen bool isOriginalEndpoint(SlotIndex Idx) const; 13406c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen 1356a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen typedef SmallPtrSet<const MachineBasicBlock*, 16> BlockPtrSet; 1366a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen 137532de3dc6ea98387368954c0ac0e07b0adca8b62Jakob Stoklund Olesen // Print a set of blocks with use counts. 138532de3dc6ea98387368954c0ac0e07b0adca8b62Jakob Stoklund Olesen void print(const BlockPtrSet&, raw_ostream&) const; 139532de3dc6ea98387368954c0ac0e07b0adca8b62Jakob Stoklund Olesen 140f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen /// getMultiUseBlocks - Add basic blocks to Blocks that may benefit from 141078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen /// having CurLI split to a new live interval. Return true if Blocks can be 142f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen /// passed to SplitEditor::splitSingleBlocks. 143f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen bool getMultiUseBlocks(BlockPtrSet &Blocks); 1448ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen}; 1458ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 1461407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen 147f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen/// SplitEditor - Edit machine code and LiveIntervals for live range 148f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen/// splitting. 149f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen/// 1505eb308b9448ee5b14fac26c0533eac481bc28471Jakob Stoklund Olesen/// - Create a SplitEditor from a SplitAnalysis. 1517536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen/// - Start a new live interval with openIntv. 1527536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen/// - Mark the places where the new interval is entered using enterIntv* 1537536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen/// - Mark the ranges where the new interval is used with useIntv* 1547536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen/// - Mark the places where the interval is exited with exitIntv*. 1557536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen/// - Finish the current interval with closeIntv and repeat from 2. 1567466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen/// - Rewrite instructions with finish(). 157f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen/// 158f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesenclass SplitEditor { 1590eeca440469e23f2db2bea3d7b136f0f95f6ff1dJakob Stoklund Olesen SplitAnalysis &SA; 160078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen LiveIntervals &LIS; 161078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen VirtRegMap &VRM; 162078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen MachineRegisterInfo &MRI; 1630f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher MachineDominatorTree &MDT; 164078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen const TargetInstrInfo &TII; 165078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen const TargetRegisterInfo &TRI; 166f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 167078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen /// Edit - The current parent register and new intervals created. 168a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen LiveRangeEdit *Edit; 169a17768f5822ab62bc18608e5ba473187bf726b84Jakob Stoklund Olesen 1700f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher /// Index into Edit of the currently open interval. 1710f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher /// The index 0 is used for the complement, so the first interval started by 1720f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher /// openIntv will be 1. 1730f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher unsigned OpenIdx; 1740f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher 1750f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher typedef IntervalMap<SlotIndex, unsigned> RegAssignMap; 1760f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher 1770f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher /// Allocator for the interval map. This will eventually be shared with 1780f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher /// SlotIndexes and LiveIntervals. 1790f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher RegAssignMap::Allocator Allocator; 1800f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher 1810f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher /// RegAssign - Map of the assigned register indexes. 1820f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher /// Edit.get(RegAssign.lookup(Idx)) is the register that should be live at 1830f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher /// Idx. 1840f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher RegAssignMap RegAssign; 185f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 186670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen typedef DenseMap<std::pair<unsigned, unsigned>, VNInfo*> ValueMap; 187670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen 188670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen /// Values - keep track of the mapping from parent values to values in the new 189670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen /// intervals. Given a pair (RegIdx, ParentVNI->id), Values contains: 190670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen /// 191670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen /// 1. No entry - the value is not mapped to Edit.get(RegIdx). 192670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen /// 2. Null - the value is mapped to multiple values in Edit.get(RegIdx). 193670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen /// Each value is represented by a minimal live range at its def. 194670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen /// 3. A non-null VNInfo - the value is mapped to a single new value. 195670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen /// The new value has no live ranges anywhere. 196670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen ValueMap Values; 197670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen 1981c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen typedef std::pair<VNInfo*, MachineDomTreeNode*> LiveOutPair; 1991c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen typedef DenseMap<MachineBasicBlock*,LiveOutPair> LiveOutMap; 2001c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 2011c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // LiveOutCache - Map each basic block where a new register is live out to the 2021c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // live-out value and its defining block. 2031c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // One of these conditions shall be true: 2041c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // 2051c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // 1. !LiveOutCache.count(MBB) 2061c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // 2. LiveOutCache[MBB].second.getNode() == MBB 2071c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // 3. forall P in preds(MBB): LiveOutCache[P] == LiveOutCache[MBB] 2081c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // 2091c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // This is only a cache, the values can be computed as: 2101c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // 2111c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // VNI = Edit.get(RegIdx)->getVNInfoAt(LIS.getMBBEndIdx(MBB)) 2121c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // Node = mbt_[LIS.getMBBFromIndex(VNI->def)] 2131c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // 2141c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // The cache is also used as a visited set by extendRange(). It can be shared 2151c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // by all the new registers because at most one is live out of each block. 2161c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen LiveOutMap LiveOutCache; 2171c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 218670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen /// defValue - define a value in RegIdx from ParentVNI at Idx. 219670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen /// Idx does not have to be ParentVNI->def, but it must be contained within 220670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen /// ParentVNI's live range in ParentLI. The new value is added to the value 221670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen /// map. 222670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen /// Return the new LI value. 223670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen VNInfo *defValue(unsigned RegIdx, const VNInfo *ParentVNI, SlotIndex Idx); 224670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen 225670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen /// markComplexMapped - Mark ParentVNI as complex mapped in RegIdx regardless 226670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen /// of the number of defs. 227670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen void markComplexMapped(unsigned RegIdx, const VNInfo *ParentVNI); 228670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen 229cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen /// defFromParent - Define Reg from ParentVNI at UseIdx using either 230cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen /// rematerialization or a COPY from parent. Return the new value. 2310f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher VNInfo *defFromParent(unsigned RegIdx, 232cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen VNInfo *ParentVNI, 233cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen SlotIndex UseIdx, 234cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen MachineBasicBlock &MBB, 235cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen MachineBasicBlock::iterator I); 236cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen 2371c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen /// extendRange - Extend the live range of Edit.get(RegIdx) so it reaches Idx. 2381c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen /// Insert PHIDefs as needed to preserve SSA form. 2391c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen void extendRange(unsigned RegIdx, SlotIndex Idx); 2401c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 2411c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen /// updateSSA - Insert PHIDefs as necessary and update LiveOutCache such that 2421c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen /// Edit.get(RegIdx) is live-in to all the blocks in LiveIn. 2431c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen /// Return the value that is eventually live-in to IdxMBB. 2441c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen VNInfo *updateSSA(unsigned RegIdx, 2451c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen SmallVectorImpl<MachineDomTreeNode*> &LiveIn, 2461c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen SlotIndex Idx, 2471c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen const MachineBasicBlock *IdxMBB); 2481c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 2494670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen /// transferSimpleValues - Transfer simply defined values to the new ranges. 2504670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen /// Return true if any complex ranges were skipped. 2514670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen bool transferSimpleValues(); 2524670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen 253e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen /// extendPHIKillRanges - Extend the ranges of all values killed by original 254e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen /// parent PHIDefs. 255e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen void extendPHIKillRanges(); 256e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen 2570f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher /// rewriteAssigned - Rewrite all uses of Edit.getReg() to assigned registers. 2584670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen void rewriteAssigned(bool ExtendRanges); 2595fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen 2600f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher /// rewriteComponents - Rewrite all uses of Intv[0] according to the eq 2610f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher /// classes in ConEQ. 2620f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher /// This must be done when Intvs[0] is styill live at all uses, before calling 2630f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher /// ConEq.Distribute(). 2640f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher void rewriteComponents(const SmallVectorImpl<LiveInterval*> &Intvs, 2650f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher const ConnectedVNInfoEqClasses &ConEq); 2667466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen 267f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesenpublic: 268f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen /// Create a new SplitEditor for editing the LiveInterval analyzed by SA. 2697536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen /// Newly created intervals will be appended to newIntervals. 270d68f458244b9d9a6644a9550dd5cee60331c9e7dJakob Stoklund Olesen SplitEditor(SplitAnalysis &SA, LiveIntervals&, VirtRegMap&, 271bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen MachineDominatorTree&); 272f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 273bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen /// reset - Prepare for a new split. 274bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen void reset(LiveRangeEdit&); 275f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 2767536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen /// Create a new virtual register and live interval. 2777536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen void openIntv(); 278f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 279207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen /// enterIntvBefore - Enter the open interval before the instruction at Idx. 280207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen /// If the parent interval is not live before Idx, a COPY is not inserted. 281207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen /// Return the beginning of the new live range. 282207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen SlotIndex enterIntvBefore(SlotIndex Idx); 283f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen 284207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen /// enterIntvAtEnd - Enter the open interval at the end of MBB. 285207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen /// Use the open interval from he inserted copy to the MBB end. 286207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen /// Return the beginning of the new live range. 287207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen SlotIndex enterIntvAtEnd(MachineBasicBlock &MBB); 288f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 289078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen /// useIntv - indicate that all instructions in MBB should use OpenLI. 2907536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen void useIntv(const MachineBasicBlock &MBB); 291f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 292078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen /// useIntv - indicate that all instructions in range should use OpenLI. 2937536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen void useIntv(SlotIndex Start, SlotIndex End); 294f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 295207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen /// leaveIntvAfter - Leave the open interval after the instruction at Idx. 296207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen /// Return the end of the live range. 297207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen SlotIndex leaveIntvAfter(SlotIndex Idx); 298f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen 2999b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen /// leaveIntvBefore - Leave the open interval before the instruction at Idx. 3009b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen /// Return the end of the live range. 3019b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen SlotIndex leaveIntvBefore(SlotIndex Idx); 3029b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen 3037536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen /// leaveIntvAtTop - Leave the interval at the top of MBB. 304207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen /// Add liveness from the MBB top to the copy. 305207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen /// Return the end of the live range. 306207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen SlotIndex leaveIntvAtTop(MachineBasicBlock &MBB); 307f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 3085c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen /// overlapIntv - Indicate that all instructions in range should use the open 3095c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen /// interval, but also let the complement interval be live. 3105c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen /// 3115c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen /// This doubles the register pressure, but is sometimes required to deal with 3125c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen /// register uses after the last valid split point. 3135c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen /// 3145c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen /// The Start index should be a return value from a leaveIntv* call, and End 3155c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen /// should be in the same basic block. The parent interval must have the same 3165c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen /// value across the range. 3175c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen /// 3185c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen void overlapIntv(SlotIndex Start, SlotIndex End); 3195c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen 3207536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen /// closeIntv - Indicate that we are done editing the currently open 321f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen /// LiveInterval, and ranges can be trimmed. 3227536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen void closeIntv(); 323f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 3247466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen /// finish - after all the new live ranges have been created, compute the 3257466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen /// remaining live range, and rewrite instructions to use the new registers. 3267466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen void finish(); 327f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 3280f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher /// dump - print the current interval maping to dbgs(). 3290f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher void dump() const; 3300f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher 331f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen // ===--- High level methods ---=== 332f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 333078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen /// splitSingleBlocks - Split CurLI into a separate live interval inside each 33457d0f2deb0afefe69770a28937a4363e7b1f9753Jakob Stoklund Olesen /// basic block in Blocks. 33557d0f2deb0afefe69770a28937a4363e7b1f9753Jakob Stoklund Olesen void splitSingleBlocks(const SplitAnalysis::BlockPtrSet &Blocks); 336fc412d85c46a8656361fe1e9197ea85922e2cd61Jakob Stoklund Olesen}; 3378ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 3388ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen} 339