SplitKit.h revision e1b43c3b4000ee7201fcac8d1c8e75bb9fb547e3
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 15db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen#include "llvm/ADT/ArrayRef.h" 1613ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen#include "llvm/ADT/BitVector.h" 178ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen#include "llvm/ADT/DenseMap.h" 1813ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen#include "llvm/ADT/IndexedMap.h" 190f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher#include "llvm/ADT/IntervalMap.h" 208d0963f72c8922bafffb36ff49b18064098a3cabJakob Stoklund Olesen#include "llvm/ADT/SmallPtrSet.h" 21f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen#include "llvm/CodeGen/SlotIndexes.h" 228ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 238ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesennamespace llvm { 248ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 250f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopherclass ConnectedVNInfoEqClasses; 268ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesenclass LiveInterval; 278ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesenclass LiveIntervals; 28a17768f5822ab62bc18608e5ba473187bf726b84Jakob Stoklund Olesenclass LiveRangeEdit; 298ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesenclass MachineInstr; 308ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesenclass MachineLoopInfo; 31f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesenclass MachineRegisterInfo; 326a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesenclass TargetInstrInfo; 33cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesenclass TargetRegisterInfo; 34f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesenclass VirtRegMap; 35f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesenclass VNInfo; 36532de3dc6ea98387368954c0ac0e07b0adca8b62Jakob Stoklund Olesenclass raw_ostream; 378ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 38e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen/// At some point we should just include MachineDominators.h: 39e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesenclass MachineDominatorTree; 40e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesentemplate <class NodeT> class DomTreeNodeBase; 41e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesentypedef DomTreeNodeBase<MachineBasicBlock> MachineDomTreeNode; 42e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen 438d0963f72c8922bafffb36ff49b18064098a3cabJakob Stoklund Olesen 44f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen/// SplitAnalysis - Analyze a LiveInterval, looking for live range splitting 45f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen/// opportunities. 468ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesenclass SplitAnalysis { 4708e93b14c37277ab40b835de340f89ba357d3332Jakob Stoklund Olesenpublic: 48078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen const MachineFunction &MF; 491b847deb26b52051de39f4cbecd224c9fbd0d1c2Jakob Stoklund Olesen const VirtRegMap &VRM; 50078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen const LiveIntervals &LIS; 51078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen const MachineLoopInfo &Loops; 52078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen const TargetInstrInfo &TII; 538ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 54b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen // Sorted slot indexes of using instructions. 55b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen SmallVector<SlotIndex, 8> UseSlots; 56b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 57f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen /// Additional information about basic blocks where the current variable is 58f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen /// live. Such a block will look like one of these templates: 59f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen /// 60f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen /// 1. | o---x | Internal to block. Variable is only live in this block. 61f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen /// 2. |---x | Live-in, kill. 62f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen /// 3. | o---| Def, live-out. 63f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen /// 4. |---x o---| Live-in, kill, def, live-out. 64f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen /// 5. |---o---o---| Live-through with uses or defs. 65f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen /// 6. |-----------| Live-through without uses. Transparent. 66f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen /// 67f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen struct BlockInfo { 68f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen MachineBasicBlock *MBB; 69f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen SlotIndex FirstUse; ///< First instr using current reg. 70f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen SlotIndex LastUse; ///< Last instr using current reg. 71f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen SlotIndex Kill; ///< Interval end point inside block. 72f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen SlotIndex Def; ///< Interval start point inside block. 73f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen bool LiveThrough; ///< Live in whole block (Templ 5. or 6. above). 74f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen bool LiveIn; ///< Current reg is live in. 75f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen bool LiveOut; ///< Current reg is live out. 76f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen }; 77f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 78f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesenprivate: 79f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen // Current live interval. 80078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen const LiveInterval *CurLI; 81f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen 821a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen /// LastSplitPoint - Last legal split point in each basic block in the current 831a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen /// function. The first entry is the first terminator, the second entry is the 841a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen /// last valid split point for a variable that is live in to a landing pad 851a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen /// successor. 861a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen SmallVector<std::pair<SlotIndex, SlotIndex>, 8> LastSplitPoint; 871a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen 88db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen /// UseBlocks - Blocks where CurLI has uses. 89db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen SmallVector<BlockInfo, 8> UseBlocks; 90db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen 91db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen /// ThroughBlocks - Block numbers where CurLI is live through without uses. 92f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen BitVector ThroughBlocks; 93f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen 94f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen /// NumThroughBlocks - Number of live-through blocks. 95f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen unsigned NumThroughBlocks; 96db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen 971a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen SlotIndex computeLastSplitPoint(unsigned Num); 981a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen 99078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen // Sumarize statistics by counting instructions using CurLI. 100abff28087fd6be8150ff0e69def7de7312b2f76bJakob Stoklund Olesen void analyzeUses(); 1018ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 102f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen /// calcLiveBlockInfo - Compute per-block information about CurLI. 1032b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen bool calcLiveBlockInfo(); 104f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 1058ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesenpublic: 1061b847deb26b52051de39f4cbecd224c9fbd0d1c2Jakob Stoklund Olesen SplitAnalysis(const VirtRegMap &vrm, const LiveIntervals &lis, 107f2c6e367c1c0d8797e62e58a3ccdb8cceee27987Jakob Stoklund Olesen const MachineLoopInfo &mli); 1088ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 109078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen /// analyze - set CurLI to the specified interval, and analyze how it may be 1108ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen /// split. 1118ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen void analyze(const LiveInterval *li); 1128ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 1138ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen /// clear - clear all data structures so SplitAnalysis is ready to analyze a 1148ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen /// new interval. 1158ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen void clear(); 1168ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 117034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen /// getParent - Return the last analyzed interval. 118034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen const LiveInterval &getParent() const { return *CurLI; } 119034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1201a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen /// getLastSplitPoint - Return that base index of the last valid split point 1211a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen /// in the basic block numbered Num. 1221a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen SlotIndex getLastSplitPoint(unsigned Num) { 1231a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen // Inline the common simple case. 1241a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen if (LastSplitPoint[Num].first.isValid() && 1251a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen !LastSplitPoint[Num].second.isValid()) 1261a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen return LastSplitPoint[Num].first; 1271a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen return computeLastSplitPoint(Num); 1281a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen } 1291a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen 13006c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen /// isOriginalEndpoint - Return true if the original live range was killed or 13106c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen /// (re-)defined at Idx. Idx should be the 'def' slot for a normal kill/def, 13206c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen /// and 'use' for an early-clobber def. 13306c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen /// This can be used to recognize code inserted by earlier live range 13406c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen /// splitting. 13506c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen bool isOriginalEndpoint(SlotIndex Idx) const; 13606c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen 137db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen /// getUseBlocks - Return an array of BlockInfo objects for the basic blocks 138db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen /// where CurLI has uses. 139db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen ArrayRef<BlockInfo> getUseBlocks() { return UseBlocks; } 140db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen 141f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen /// getNumThroughBlocks - Return the number of through blocks. 142f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen unsigned getNumThroughBlocks() const { return NumThroughBlocks; } 143f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen 144f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen /// isThroughBlock - Return true if CurLI is live through MBB without uses. 145f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen bool isThroughBlock(unsigned MBB) const { return ThroughBlocks.test(MBB); } 146db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen 1476a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen typedef SmallPtrSet<const MachineBasicBlock*, 16> BlockPtrSet; 1486a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen 149f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen /// getMultiUseBlocks - Add basic blocks to Blocks that may benefit from 150078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen /// having CurLI split to a new live interval. Return true if Blocks can be 151f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen /// passed to SplitEditor::splitSingleBlocks. 152f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen bool getMultiUseBlocks(BlockPtrSet &Blocks); 1538ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen}; 1548ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 1551407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen 156f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen/// SplitEditor - Edit machine code and LiveIntervals for live range 157f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen/// splitting. 158f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen/// 1595eb308b9448ee5b14fac26c0533eac481bc28471Jakob Stoklund Olesen/// - Create a SplitEditor from a SplitAnalysis. 1607536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen/// - Start a new live interval with openIntv. 1617536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen/// - Mark the places where the new interval is entered using enterIntv* 1627536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen/// - Mark the ranges where the new interval is used with useIntv* 1637536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen/// - Mark the places where the interval is exited with exitIntv*. 1647536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen/// - Finish the current interval with closeIntv and repeat from 2. 1657466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen/// - Rewrite instructions with finish(). 166f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen/// 167f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesenclass SplitEditor { 1680eeca440469e23f2db2bea3d7b136f0f95f6ff1dJakob Stoklund Olesen SplitAnalysis &SA; 169078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen LiveIntervals &LIS; 170078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen VirtRegMap &VRM; 171078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen MachineRegisterInfo &MRI; 1720f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher MachineDominatorTree &MDT; 173078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen const TargetInstrInfo &TII; 174078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen const TargetRegisterInfo &TRI; 175f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 176078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen /// Edit - The current parent register and new intervals created. 177a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen LiveRangeEdit *Edit; 178a17768f5822ab62bc18608e5ba473187bf726b84Jakob Stoklund Olesen 1790f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher /// Index into Edit of the currently open interval. 1800f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher /// The index 0 is used for the complement, so the first interval started by 1810f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher /// openIntv will be 1. 1820f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher unsigned OpenIdx; 1830f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher 1840f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher typedef IntervalMap<SlotIndex, unsigned> RegAssignMap; 1850f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher 1860f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher /// Allocator for the interval map. This will eventually be shared with 1870f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher /// SlotIndexes and LiveIntervals. 1880f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher RegAssignMap::Allocator Allocator; 1890f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher 1900f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher /// RegAssign - Map of the assigned register indexes. 1910f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher /// Edit.get(RegAssign.lookup(Idx)) is the register that should be live at 1920f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher /// Idx. 1930f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher RegAssignMap RegAssign; 194f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 195670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen typedef DenseMap<std::pair<unsigned, unsigned>, VNInfo*> ValueMap; 196670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen 197670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen /// Values - keep track of the mapping from parent values to values in the new 198670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen /// intervals. Given a pair (RegIdx, ParentVNI->id), Values contains: 199670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen /// 200670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen /// 1. No entry - the value is not mapped to Edit.get(RegIdx). 201670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen /// 2. Null - the value is mapped to multiple values in Edit.get(RegIdx). 202670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen /// Each value is represented by a minimal live range at its def. 203670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen /// 3. A non-null VNInfo - the value is mapped to a single new value. 204670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen /// The new value has no live ranges anywhere. 205670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen ValueMap Values; 206670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen 2071c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen typedef std::pair<VNInfo*, MachineDomTreeNode*> LiveOutPair; 20813ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen typedef IndexedMap<LiveOutPair, MBB2NumberFunctor> LiveOutMap; 2091c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 2101c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // LiveOutCache - Map each basic block where a new register is live out to the 2111c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // live-out value and its defining block. 2121c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // One of these conditions shall be true: 2131c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // 2141c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // 1. !LiveOutCache.count(MBB) 2151c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // 2. LiveOutCache[MBB].second.getNode() == MBB 2161c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // 3. forall P in preds(MBB): LiveOutCache[P] == LiveOutCache[MBB] 2171c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // 2181c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // This is only a cache, the values can be computed as: 2191c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // 2201c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // VNI = Edit.get(RegIdx)->getVNInfoAt(LIS.getMBBEndIdx(MBB)) 2211c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // Node = mbt_[LIS.getMBBFromIndex(VNI->def)] 2221c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // 2231c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // The cache is also used as a visited set by extendRange(). It can be shared 2241c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // by all the new registers because at most one is live out of each block. 2251c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen LiveOutMap LiveOutCache; 2261c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 22713ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen // LiveOutSeen - Indexed by MBB->getNumber(), a bit is set for each valid 22813ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen // entry in LiveOutCache. 22913ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen BitVector LiveOutSeen; 23013ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen 231670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen /// defValue - define a value in RegIdx from ParentVNI at Idx. 232670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen /// Idx does not have to be ParentVNI->def, but it must be contained within 233670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen /// ParentVNI's live range in ParentLI. The new value is added to the value 234670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen /// map. 235670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen /// Return the new LI value. 236670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen VNInfo *defValue(unsigned RegIdx, const VNInfo *ParentVNI, SlotIndex Idx); 237670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen 238670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen /// markComplexMapped - Mark ParentVNI as complex mapped in RegIdx regardless 239670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen /// of the number of defs. 240670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen void markComplexMapped(unsigned RegIdx, const VNInfo *ParentVNI); 241670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen 242cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen /// defFromParent - Define Reg from ParentVNI at UseIdx using either 243cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen /// rematerialization or a COPY from parent. Return the new value. 2440f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher VNInfo *defFromParent(unsigned RegIdx, 245cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen VNInfo *ParentVNI, 246cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen SlotIndex UseIdx, 247cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen MachineBasicBlock &MBB, 248cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen MachineBasicBlock::iterator I); 249cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen 2501c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen /// extendRange - Extend the live range of Edit.get(RegIdx) so it reaches Idx. 2511c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen /// Insert PHIDefs as needed to preserve SSA form. 2521c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen void extendRange(unsigned RegIdx, SlotIndex Idx); 2531c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 2541c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen /// updateSSA - Insert PHIDefs as necessary and update LiveOutCache such that 2551c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen /// Edit.get(RegIdx) is live-in to all the blocks in LiveIn. 2561c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen /// Return the value that is eventually live-in to IdxMBB. 2571c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen VNInfo *updateSSA(unsigned RegIdx, 2581c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen SmallVectorImpl<MachineDomTreeNode*> &LiveIn, 2591c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen SlotIndex Idx, 2601c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen const MachineBasicBlock *IdxMBB); 2611c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 2624670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen /// transferSimpleValues - Transfer simply defined values to the new ranges. 2634670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen /// Return true if any complex ranges were skipped. 2644670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen bool transferSimpleValues(); 2654670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen 266e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen /// extendPHIKillRanges - Extend the ranges of all values killed by original 267e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen /// parent PHIDefs. 268e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen void extendPHIKillRanges(); 269e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen 2700f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher /// rewriteAssigned - Rewrite all uses of Edit.getReg() to assigned registers. 2714670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen void rewriteAssigned(bool ExtendRanges); 2725fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen 2735881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen /// deleteRematVictims - Delete defs that are dead after rematerializing. 2745881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen void deleteRematVictims(); 2755881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen 276f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesenpublic: 277f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen /// Create a new SplitEditor for editing the LiveInterval analyzed by SA. 2787536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen /// Newly created intervals will be appended to newIntervals. 279d68f458244b9d9a6644a9550dd5cee60331c9e7dJakob Stoklund Olesen SplitEditor(SplitAnalysis &SA, LiveIntervals&, VirtRegMap&, 280bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen MachineDominatorTree&); 281f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 282bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen /// reset - Prepare for a new split. 283bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen void reset(LiveRangeEdit&); 284f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 2857536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen /// Create a new virtual register and live interval. 286e1b43c3b4000ee7201fcac8d1c8e75bb9fb547e3Jakob Stoklund Olesen /// Return the interval index, starting from 1. Interval index 0 is the 287e1b43c3b4000ee7201fcac8d1c8e75bb9fb547e3Jakob Stoklund Olesen /// implicit complement interval. 288e1b43c3b4000ee7201fcac8d1c8e75bb9fb547e3Jakob Stoklund Olesen unsigned openIntv(); 289e1b43c3b4000ee7201fcac8d1c8e75bb9fb547e3Jakob Stoklund Olesen 290e1b43c3b4000ee7201fcac8d1c8e75bb9fb547e3Jakob Stoklund Olesen /// currentIntv - Return the current interval index. 291e1b43c3b4000ee7201fcac8d1c8e75bb9fb547e3Jakob Stoklund Olesen unsigned currentIntv() const { return OpenIdx; } 292e1b43c3b4000ee7201fcac8d1c8e75bb9fb547e3Jakob Stoklund Olesen 293e1b43c3b4000ee7201fcac8d1c8e75bb9fb547e3Jakob Stoklund Olesen /// selectIntv - Select a previously opened interval index. 294e1b43c3b4000ee7201fcac8d1c8e75bb9fb547e3Jakob Stoklund Olesen void selectIntv(unsigned Idx); 295f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 296207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen /// enterIntvBefore - Enter the open interval before the instruction at Idx. 297207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen /// If the parent interval is not live before Idx, a COPY is not inserted. 298207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen /// Return the beginning of the new live range. 299207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen SlotIndex enterIntvBefore(SlotIndex Idx); 300f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen 301207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen /// enterIntvAtEnd - Enter the open interval at the end of MBB. 302207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen /// Use the open interval from he inserted copy to the MBB end. 303207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen /// Return the beginning of the new live range. 304207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen SlotIndex enterIntvAtEnd(MachineBasicBlock &MBB); 305f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 306078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen /// useIntv - indicate that all instructions in MBB should use OpenLI. 3077536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen void useIntv(const MachineBasicBlock &MBB); 308f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 309078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen /// useIntv - indicate that all instructions in range should use OpenLI. 3107536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen void useIntv(SlotIndex Start, SlotIndex End); 311f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 312207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen /// leaveIntvAfter - Leave the open interval after the instruction at Idx. 313207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen /// Return the end of the live range. 314207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen SlotIndex leaveIntvAfter(SlotIndex Idx); 315f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen 3169b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen /// leaveIntvBefore - Leave the open interval before the instruction at Idx. 3179b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen /// Return the end of the live range. 3189b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen SlotIndex leaveIntvBefore(SlotIndex Idx); 3199b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen 3207536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen /// leaveIntvAtTop - Leave the interval at the top of MBB. 321207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen /// Add liveness from the MBB top to the copy. 322207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen /// Return the end of the live range. 323207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen SlotIndex leaveIntvAtTop(MachineBasicBlock &MBB); 324f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 3255c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen /// overlapIntv - Indicate that all instructions in range should use the open 3265c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen /// interval, but also let the complement interval be live. 3275c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen /// 3285c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen /// This doubles the register pressure, but is sometimes required to deal with 3295c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen /// register uses after the last valid split point. 3305c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen /// 3315c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen /// The Start index should be a return value from a leaveIntv* call, and End 3325c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen /// should be in the same basic block. The parent interval must have the same 3335c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen /// value across the range. 3345c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen /// 3355c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen void overlapIntv(SlotIndex Start, SlotIndex End); 3365c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen 3377536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen /// closeIntv - Indicate that we are done editing the currently open 338f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen /// LiveInterval, and ranges can be trimmed. 3397536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen void closeIntv(); 340f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 3417466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen /// finish - after all the new live ranges have been created, compute the 3427466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen /// remaining live range, and rewrite instructions to use the new registers. 3437466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen void finish(); 344f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 3450f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher /// dump - print the current interval maping to dbgs(). 3460f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher void dump() const; 3470f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher 348f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen // ===--- High level methods ---=== 349f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 350078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen /// splitSingleBlocks - Split CurLI into a separate live interval inside each 35157d0f2deb0afefe69770a28937a4363e7b1f9753Jakob Stoklund Olesen /// basic block in Blocks. 35257d0f2deb0afefe69770a28937a4363e7b1f9753Jakob Stoklund Olesen void splitSingleBlocks(const SplitAnalysis::BlockPtrSet &Blocks); 353fc412d85c46a8656361fe1e9197ea85922e2cd61Jakob Stoklund Olesen}; 3548ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 3558ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen} 356