SplitKit.h revision 7d6b6a05b549da70b4473f015c97954c2a422724
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 156796e4fc889d99c4ad97ec5ad86e4c8cf75e52a4Sebastian Redl#ifndef LLVM_CODEGEN_SPLITKIT_H 166796e4fc889d99c4ad97ec5ad86e4c8cf75e52a4Sebastian Redl#define LLVM_CODEGEN_SPLITKIT_H 176796e4fc889d99c4ad97ec5ad86e4c8cf75e52a4Sebastian Redl 18db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen#include "llvm/ADT/ArrayRef.h" 1913ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen#include "llvm/ADT/BitVector.h" 208ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen#include "llvm/ADT/DenseMap.h" 2113ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen#include "llvm/ADT/IndexedMap.h" 220f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher#include "llvm/ADT/IntervalMap.h" 238d0963f72c8922bafffb36ff49b18064098a3cabJakob Stoklund Olesen#include "llvm/ADT/SmallPtrSet.h" 24f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen#include "llvm/CodeGen/SlotIndexes.h" 258ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 268ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesennamespace llvm { 278ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 280f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopherclass ConnectedVNInfoEqClasses; 298ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesenclass LiveInterval; 308ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesenclass LiveIntervals; 31a17768f5822ab62bc18608e5ba473187bf726b84Jakob Stoklund Olesenclass LiveRangeEdit; 328ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesenclass MachineInstr; 338ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesenclass MachineLoopInfo; 34f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesenclass MachineRegisterInfo; 356a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesenclass TargetInstrInfo; 36cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesenclass TargetRegisterInfo; 37f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesenclass VirtRegMap; 38f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesenclass VNInfo; 39532de3dc6ea98387368954c0ac0e07b0adca8b62Jakob Stoklund Olesenclass raw_ostream; 408ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 41e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen/// At some point we should just include MachineDominators.h: 42e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesenclass MachineDominatorTree; 43e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesentemplate <class NodeT> class DomTreeNodeBase; 44e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesentypedef DomTreeNodeBase<MachineBasicBlock> MachineDomTreeNode; 45e1dde7b05a83438eeba4bd83f8cf080f56d22c5bJakob Stoklund Olesen 468d0963f72c8922bafffb36ff49b18064098a3cabJakob Stoklund Olesen 47f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen/// SplitAnalysis - Analyze a LiveInterval, looking for live range splitting 48f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen/// opportunities. 498ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesenclass SplitAnalysis { 5008e93b14c37277ab40b835de340f89ba357d3332Jakob Stoklund Olesenpublic: 51078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen const MachineFunction &MF; 521b847deb26b52051de39f4cbecd224c9fbd0d1c2Jakob Stoklund Olesen const VirtRegMap &VRM; 53078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen const LiveIntervals &LIS; 54078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen const MachineLoopInfo &Loops; 55078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen const TargetInstrInfo &TII; 568ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 57b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen // Sorted slot indexes of using instructions. 58b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen SmallVector<SlotIndex, 8> UseSlots; 59b5fa9333431673aac2ced8dea80152349a85cf6fJakob Stoklund Olesen 60f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen /// Additional information about basic blocks where the current variable is 61f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen /// live. Such a block will look like one of these templates: 62f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen /// 63f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen /// 1. | o---x | Internal to block. Variable is only live in this block. 64f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen /// 2. |---x | Live-in, kill. 65f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen /// 3. | o---| Def, live-out. 66f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen /// 4. |---x o---| Live-in, kill, def, live-out. 67f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen /// 5. |---o---o---| Live-through with uses or defs. 68f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen /// 6. |-----------| Live-through without uses. Transparent. 69f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen /// 70f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen struct BlockInfo { 71f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen MachineBasicBlock *MBB; 72f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen SlotIndex FirstUse; ///< First instr using current reg. 73f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen SlotIndex LastUse; ///< Last instr using current reg. 74f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen SlotIndex Kill; ///< Interval end point inside block. 75f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen SlotIndex Def; ///< Interval start point inside block. 76f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen bool LiveThrough; ///< Live in whole block (Templ 5. or 6. above). 77f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen bool LiveIn; ///< Current reg is live in. 78f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen bool LiveOut; ///< Current reg is live out. 79f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen }; 80f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 81f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesenprivate: 82f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen // Current live interval. 83078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen const LiveInterval *CurLI; 84f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen 851a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen /// LastSplitPoint - Last legal split point in each basic block in the current 861a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen /// function. The first entry is the first terminator, the second entry is the 871a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen /// last valid split point for a variable that is live in to a landing pad 881a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen /// successor. 891a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen SmallVector<std::pair<SlotIndex, SlotIndex>, 8> LastSplitPoint; 901a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen 91db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen /// UseBlocks - Blocks where CurLI has uses. 92db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen SmallVector<BlockInfo, 8> UseBlocks; 93db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen 94db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen /// ThroughBlocks - Block numbers where CurLI is live through without uses. 95f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen BitVector ThroughBlocks; 96f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen 97f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen /// NumThroughBlocks - Number of live-through blocks. 98f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen unsigned NumThroughBlocks; 99db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen 1007d6b6a05b549da70b4473f015c97954c2a422724Jakob Stoklund Olesen /// DidRepairRange - analyze was forced to shrinkToUses(). 1017d6b6a05b549da70b4473f015c97954c2a422724Jakob Stoklund Olesen bool DidRepairRange; 1027d6b6a05b549da70b4473f015c97954c2a422724Jakob Stoklund Olesen 1031a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen SlotIndex computeLastSplitPoint(unsigned Num); 1041a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen 105078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen // Sumarize statistics by counting instructions using CurLI. 106abff28087fd6be8150ff0e69def7de7312b2f76bJakob Stoklund Olesen void analyzeUses(); 1078ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 108f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen /// calcLiveBlockInfo - Compute per-block information about CurLI. 1092b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen bool calcLiveBlockInfo(); 110f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 1118ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesenpublic: 1121b847deb26b52051de39f4cbecd224c9fbd0d1c2Jakob Stoklund Olesen SplitAnalysis(const VirtRegMap &vrm, const LiveIntervals &lis, 113f2c6e367c1c0d8797e62e58a3ccdb8cceee27987Jakob Stoklund Olesen const MachineLoopInfo &mli); 1148ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 115078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen /// analyze - set CurLI to the specified interval, and analyze how it may be 1168ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen /// split. 1178ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen void analyze(const LiveInterval *li); 1188ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 1197d6b6a05b549da70b4473f015c97954c2a422724Jakob Stoklund Olesen /// didRepairRange() - Returns true if CurLI was invalid and has been repaired 1207d6b6a05b549da70b4473f015c97954c2a422724Jakob Stoklund Olesen /// by analyze(). This really shouldn't happen, but sometimes the coalescer 1217d6b6a05b549da70b4473f015c97954c2a422724Jakob Stoklund Olesen /// can create live ranges that end in mid-air. 1227d6b6a05b549da70b4473f015c97954c2a422724Jakob Stoklund Olesen bool didRepairRange() const { return DidRepairRange; } 1237d6b6a05b549da70b4473f015c97954c2a422724Jakob Stoklund Olesen 1248ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen /// clear - clear all data structures so SplitAnalysis is ready to analyze a 1258ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen /// new interval. 1268ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen void clear(); 1278ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 128034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen /// getParent - Return the last analyzed interval. 129034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen const LiveInterval &getParent() const { return *CurLI; } 130034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 1311a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen /// getLastSplitPoint - Return that base index of the last valid split point 1321a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen /// in the basic block numbered Num. 1331a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen SlotIndex getLastSplitPoint(unsigned Num) { 1341a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen // Inline the common simple case. 1351a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen if (LastSplitPoint[Num].first.isValid() && 1361a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen !LastSplitPoint[Num].second.isValid()) 1371a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen return LastSplitPoint[Num].first; 1381a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen return computeLastSplitPoint(Num); 1391a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen } 1401a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen 14106c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen /// isOriginalEndpoint - Return true if the original live range was killed or 14206c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen /// (re-)defined at Idx. Idx should be the 'def' slot for a normal kill/def, 14306c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen /// and 'use' for an early-clobber def. 14406c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen /// This can be used to recognize code inserted by earlier live range 14506c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen /// splitting. 14606c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen bool isOriginalEndpoint(SlotIndex Idx) const; 14706c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen 148db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen /// getUseBlocks - Return an array of BlockInfo objects for the basic blocks 149db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen /// where CurLI has uses. 150db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen ArrayRef<BlockInfo> getUseBlocks() { return UseBlocks; } 151db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen 152f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen /// getNumThroughBlocks - Return the number of through blocks. 153f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen unsigned getNumThroughBlocks() const { return NumThroughBlocks; } 154f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen 155f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen /// isThroughBlock - Return true if CurLI is live through MBB without uses. 156f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen bool isThroughBlock(unsigned MBB) const { return ThroughBlocks.test(MBB); } 157db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen 1585db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen /// getThroughBlocks - Return the set of through blocks. 1595db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen const BitVector &getThroughBlocks() const { return ThroughBlocks; } 1605db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen 1619f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen /// countLiveBlocks - Return the number of blocks where li is live. 1629f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen /// This is guaranteed to return the same number as getNumThroughBlocks() + 1639f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen /// getUseBlocks().size() after calling analyze(li). 1649f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen unsigned countLiveBlocks(const LiveInterval *li) const; 1659f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen 1666a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen typedef SmallPtrSet<const MachineBasicBlock*, 16> BlockPtrSet; 1676a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen 168f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen /// getMultiUseBlocks - Add basic blocks to Blocks that may benefit from 169078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen /// having CurLI split to a new live interval. Return true if Blocks can be 170f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen /// passed to SplitEditor::splitSingleBlocks. 171f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen bool getMultiUseBlocks(BlockPtrSet &Blocks); 1728ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen}; 1738ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 1741407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen 175f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen/// SplitEditor - Edit machine code and LiveIntervals for live range 176f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen/// splitting. 177f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen/// 1785eb308b9448ee5b14fac26c0533eac481bc28471Jakob Stoklund Olesen/// - Create a SplitEditor from a SplitAnalysis. 1797536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen/// - Start a new live interval with openIntv. 1807536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen/// - Mark the places where the new interval is entered using enterIntv* 1817536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen/// - Mark the ranges where the new interval is used with useIntv* 1827536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen/// - Mark the places where the interval is exited with exitIntv*. 1837536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen/// - Finish the current interval with closeIntv and repeat from 2. 1847466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen/// - Rewrite instructions with finish(). 185f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen/// 186f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesenclass SplitEditor { 1870eeca440469e23f2db2bea3d7b136f0f95f6ff1dJakob Stoklund Olesen SplitAnalysis &SA; 188078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen LiveIntervals &LIS; 189078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen VirtRegMap &VRM; 190078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen MachineRegisterInfo &MRI; 1910f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher MachineDominatorTree &MDT; 192078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen const TargetInstrInfo &TII; 193078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen const TargetRegisterInfo &TRI; 194f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 195078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen /// Edit - The current parent register and new intervals created. 196a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen LiveRangeEdit *Edit; 197a17768f5822ab62bc18608e5ba473187bf726b84Jakob Stoklund Olesen 1980f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher /// Index into Edit of the currently open interval. 1990f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher /// The index 0 is used for the complement, so the first interval started by 2000f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher /// openIntv will be 1. 2010f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher unsigned OpenIdx; 2020f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher 2030f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher typedef IntervalMap<SlotIndex, unsigned> RegAssignMap; 2040f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher 2050f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher /// Allocator for the interval map. This will eventually be shared with 2060f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher /// SlotIndexes and LiveIntervals. 2070f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher RegAssignMap::Allocator Allocator; 2080f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher 2090f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher /// RegAssign - Map of the assigned register indexes. 2100f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher /// Edit.get(RegAssign.lookup(Idx)) is the register that should be live at 2110f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher /// Idx. 2120f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher RegAssignMap RegAssign; 213f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 214670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen typedef DenseMap<std::pair<unsigned, unsigned>, VNInfo*> ValueMap; 215670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen 216670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen /// Values - keep track of the mapping from parent values to values in the new 217670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen /// intervals. Given a pair (RegIdx, ParentVNI->id), Values contains: 218670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen /// 219670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen /// 1. No entry - the value is not mapped to Edit.get(RegIdx). 220670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen /// 2. Null - the value is mapped to multiple values in Edit.get(RegIdx). 221670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen /// Each value is represented by a minimal live range at its def. 222670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen /// 3. A non-null VNInfo - the value is mapped to a single new value. 223670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen /// The new value has no live ranges anywhere. 224670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen ValueMap Values; 225670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen 2261c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen typedef std::pair<VNInfo*, MachineDomTreeNode*> LiveOutPair; 22713ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen typedef IndexedMap<LiveOutPair, MBB2NumberFunctor> LiveOutMap; 2281c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 2291c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // LiveOutCache - Map each basic block where a new register is live out to the 2301c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // live-out value and its defining block. 2311c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // One of these conditions shall be true: 2321c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // 2331c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // 1. !LiveOutCache.count(MBB) 2341c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // 2. LiveOutCache[MBB].second.getNode() == MBB 2351c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // 3. forall P in preds(MBB): LiveOutCache[P] == LiveOutCache[MBB] 2361c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // 2371c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // This is only a cache, the values can be computed as: 2381c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // 2391c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // VNI = Edit.get(RegIdx)->getVNInfoAt(LIS.getMBBEndIdx(MBB)) 2401c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // Node = mbt_[LIS.getMBBFromIndex(VNI->def)] 2411c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // 2421c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // The cache is also used as a visited set by extendRange(). It can be shared 2431c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen // by all the new registers because at most one is live out of each block. 2441c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen LiveOutMap LiveOutCache; 2451c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 24613ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen // LiveOutSeen - Indexed by MBB->getNumber(), a bit is set for each valid 24713ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen // entry in LiveOutCache. 24813ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen BitVector LiveOutSeen; 24913ba2dab631636e525a44bb259aaea56a860d1c7Jakob Stoklund Olesen 25044b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen /// LiveInBlock - Info for updateSSA() about a block where a register is 25144b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen /// live-in. 25244b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen /// The updateSSA caller provides DomNode and Kill inside MBB, updateSSA() 25344b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen /// adds the computed live-in value. 25444b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen struct LiveInBlock { 25544b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen // Dominator tree node for the block. 25644b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen // Cleared by updateSSA when the final value has been determined. 25744b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen MachineDomTreeNode *DomNode; 25844b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen 25944b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen // Live-in value filled in by updateSSA once it is known. 26044b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen VNInfo *Value; 26144b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen 26244b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen // Position in block where the live-in range ends, or SlotIndex() if the 26344b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen // range passes through the block. 26444b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen SlotIndex Kill; 26544b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen 26644b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen LiveInBlock(MachineDomTreeNode *node) : DomNode(node), Value(0) {} 26744b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen }; 26844b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen 26944b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen /// LiveInBlocks - List of live-in blocks used by findReachingDefs() and 27044b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen /// updateSSA(). This list is usually empty, it exists here to avoid frequent 27144b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen /// reallocations. 27244b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen SmallVector<LiveInBlock, 16> LiveInBlocks; 27344b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen 274670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen /// defValue - define a value in RegIdx from ParentVNI at Idx. 275670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen /// Idx does not have to be ParentVNI->def, but it must be contained within 276670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen /// ParentVNI's live range in ParentLI. The new value is added to the value 277670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen /// map. 278670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen /// Return the new LI value. 279670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen VNInfo *defValue(unsigned RegIdx, const VNInfo *ParentVNI, SlotIndex Idx); 280670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen 281670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen /// markComplexMapped - Mark ParentVNI as complex mapped in RegIdx regardless 282670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen /// of the number of defs. 283670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen void markComplexMapped(unsigned RegIdx, const VNInfo *ParentVNI); 284670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen 285cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen /// defFromParent - Define Reg from ParentVNI at UseIdx using either 286cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen /// rematerialization or a COPY from parent. Return the new value. 2870f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher VNInfo *defFromParent(unsigned RegIdx, 288cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen VNInfo *ParentVNI, 289cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen SlotIndex UseIdx, 290cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen MachineBasicBlock &MBB, 291cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen MachineBasicBlock::iterator I); 292cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen 2931c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen /// extendRange - Extend the live range of Edit.get(RegIdx) so it reaches Idx. 2941c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen /// Insert PHIDefs as needed to preserve SSA form. 2951c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen void extendRange(unsigned RegIdx, SlotIndex Idx); 2961c38ba6355a019b7fc3baa0d0ab31e8ba11f7db1Jakob Stoklund Olesen 29744b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen /// findReachingDefs - Starting from MBB, add blocks to LiveInBlocks until all 29844b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen /// reaching defs for LI are found. 29944b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen /// @param LI Live interval whose value is needed. 30044b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen /// @param MBB Block where LI should be live-in. 30144b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen /// @param Kill Kill point in MBB. 30244b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen /// @return Unique value seen, or NULL. 30344b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen VNInfo *findReachingDefs(LiveInterval *LI, MachineBasicBlock *MBB, 30444b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen SlotIndex Kill); 30544b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen 30644b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen /// updateSSA - Compute and insert PHIDefs such that all blocks in 30744b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen // LiveInBlocks get a known live-in value. Add live ranges to the blocks. 30844b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen void updateSSA(); 30944b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen 31044b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen /// transferValues - Transfer values to the new ranges. 31144b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen /// Return true if any ranges were skipped. 31244b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen bool transferValues(); 3134670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen 314e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen /// extendPHIKillRanges - Extend the ranges of all values killed by original 315e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen /// parent PHIDefs. 316e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen void extendPHIKillRanges(); 317e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen 3180f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher /// rewriteAssigned - Rewrite all uses of Edit.getReg() to assigned registers. 3194670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen void rewriteAssigned(bool ExtendRanges); 3205fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen 3215881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen /// deleteRematVictims - Delete defs that are dead after rematerializing. 3225881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen void deleteRematVictims(); 3235881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen 324f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesenpublic: 325f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen /// Create a new SplitEditor for editing the LiveInterval analyzed by SA. 3267536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen /// Newly created intervals will be appended to newIntervals. 327d68f458244b9d9a6644a9550dd5cee60331c9e7dJakob Stoklund Olesen SplitEditor(SplitAnalysis &SA, LiveIntervals&, VirtRegMap&, 328bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen MachineDominatorTree&); 329f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 330bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen /// reset - Prepare for a new split. 331bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen void reset(LiveRangeEdit&); 332f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 3337536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen /// Create a new virtual register and live interval. 334e1b43c3b4000ee7201fcac8d1c8e75bb9fb547e3Jakob Stoklund Olesen /// Return the interval index, starting from 1. Interval index 0 is the 335e1b43c3b4000ee7201fcac8d1c8e75bb9fb547e3Jakob Stoklund Olesen /// implicit complement interval. 336e1b43c3b4000ee7201fcac8d1c8e75bb9fb547e3Jakob Stoklund Olesen unsigned openIntv(); 337e1b43c3b4000ee7201fcac8d1c8e75bb9fb547e3Jakob Stoklund Olesen 338e1b43c3b4000ee7201fcac8d1c8e75bb9fb547e3Jakob Stoklund Olesen /// currentIntv - Return the current interval index. 339e1b43c3b4000ee7201fcac8d1c8e75bb9fb547e3Jakob Stoklund Olesen unsigned currentIntv() const { return OpenIdx; } 340e1b43c3b4000ee7201fcac8d1c8e75bb9fb547e3Jakob Stoklund Olesen 341e1b43c3b4000ee7201fcac8d1c8e75bb9fb547e3Jakob Stoklund Olesen /// selectIntv - Select a previously opened interval index. 342e1b43c3b4000ee7201fcac8d1c8e75bb9fb547e3Jakob Stoklund Olesen void selectIntv(unsigned Idx); 343f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 344207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen /// enterIntvBefore - Enter the open interval before the instruction at Idx. 345207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen /// If the parent interval is not live before Idx, a COPY is not inserted. 346207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen /// Return the beginning of the new live range. 347207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen SlotIndex enterIntvBefore(SlotIndex Idx); 348f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen 349207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen /// enterIntvAtEnd - Enter the open interval at the end of MBB. 350207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen /// Use the open interval from he inserted copy to the MBB end. 351207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen /// Return the beginning of the new live range. 352207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen SlotIndex enterIntvAtEnd(MachineBasicBlock &MBB); 353f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 354078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen /// useIntv - indicate that all instructions in MBB should use OpenLI. 3557536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen void useIntv(const MachineBasicBlock &MBB); 356f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 357078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen /// useIntv - indicate that all instructions in range should use OpenLI. 3587536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen void useIntv(SlotIndex Start, SlotIndex End); 359f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 360207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen /// leaveIntvAfter - Leave the open interval after the instruction at Idx. 361207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen /// Return the end of the live range. 362207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen SlotIndex leaveIntvAfter(SlotIndex Idx); 363f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen 3649b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen /// leaveIntvBefore - Leave the open interval before the instruction at Idx. 3659b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen /// Return the end of the live range. 3669b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen SlotIndex leaveIntvBefore(SlotIndex Idx); 3679b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen 3687536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen /// leaveIntvAtTop - Leave the interval at the top of MBB. 369207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen /// Add liveness from the MBB top to the copy. 370207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen /// Return the end of the live range. 371207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen SlotIndex leaveIntvAtTop(MachineBasicBlock &MBB); 372f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 3735c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen /// overlapIntv - Indicate that all instructions in range should use the open 3745c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen /// interval, but also let the complement interval be live. 3755c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen /// 3765c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen /// This doubles the register pressure, but is sometimes required to deal with 3775c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen /// register uses after the last valid split point. 3785c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen /// 3795c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen /// The Start index should be a return value from a leaveIntv* call, and End 3805c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen /// should be in the same basic block. The parent interval must have the same 3815c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen /// value across the range. 3825c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen /// 3835c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen void overlapIntv(SlotIndex Start, SlotIndex End); 3845c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen 3857466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen /// finish - after all the new live ranges have been created, compute the 3867466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen /// remaining live range, and rewrite instructions to use the new registers. 3875928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen /// @param LRMap When not null, this vector will map each live range in Edit 3885928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen /// back to the indices returned by openIntv. 3895928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen /// There may be extra indices created by dead code elimination. 3905928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen void finish(SmallVectorImpl<unsigned> *LRMap = 0); 391f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 3920f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher /// dump - print the current interval maping to dbgs(). 3930f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher void dump() const; 3940f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher 395f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen // ===--- High level methods ---=== 396f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 397fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen /// splitSingleBlock - Split CurLI into a separate live interval around the 398fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen /// uses in a single block. This is intended to be used as part of a larger 399fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen /// split, and doesn't call finish(). 400fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen void splitSingleBlock(const SplitAnalysis::BlockInfo &BI); 401fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen 402078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen /// splitSingleBlocks - Split CurLI into a separate live interval inside each 40357d0f2deb0afefe69770a28937a4363e7b1f9753Jakob Stoklund Olesen /// basic block in Blocks. 40457d0f2deb0afefe69770a28937a4363e7b1f9753Jakob Stoklund Olesen void splitSingleBlocks(const SplitAnalysis::BlockPtrSet &Blocks); 405fc412d85c46a8656361fe1e9197ea85922e2cd61Jakob Stoklund Olesen}; 4068ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 4078ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen} 4086796e4fc889d99c4ad97ec5ad86e4c8cf75e52a4Sebastian Redl 4096796e4fc889d99c4ad97ec5ad86e4c8cf75e52a4Sebastian Redl#endif 410