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 18b5a457c4cbc71db6ae313ef1bf8eadac65767ab0Jakob Stoklund Olesen#include "LiveRangeCalc.h" 19db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen#include "llvm/ADT/ArrayRef.h" 208ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen#include "llvm/ADT/DenseMap.h" 210f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher#include "llvm/ADT/IntervalMap.h" 228d0963f72c8922bafffb36ff49b18064098a3cabJakob Stoklund Olesen#include "llvm/ADT/SmallPtrSet.h" 238ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 248ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesennamespace llvm { 258ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 260f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopherclass ConnectedVNInfoEqClasses; 278ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesenclass LiveInterval; 288ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesenclass LiveIntervals; 29a17768f5822ab62bc18608e5ba473187bf726b84Jakob Stoklund Olesenclass LiveRangeEdit; 304eed756153b84c211114a3e9186bf0cb55d4b394Benjamin Kramerclass MachineBlockFrequencyInfo; 318ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesenclass MachineInstr; 328ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesenclass MachineLoopInfo; 33f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesenclass MachineRegisterInfo; 346a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesenclass TargetInstrInfo; 35cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesenclass TargetRegisterInfo; 36f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesenclass VirtRegMap; 37f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesenclass VNInfo; 38532de3dc6ea98387368954c0ac0e07b0adca8b62Jakob Stoklund Olesenclass raw_ostream; 398ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 40f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen/// SplitAnalysis - Analyze a LiveInterval, looking for live range splitting 41f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen/// opportunities. 428ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesenclass SplitAnalysis { 4308e93b14c37277ab40b835de340f89ba357d3332Jakob Stoklund Olesenpublic: 44078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen const MachineFunction &MF; 451b847deb26b52051de39f4cbecd224c9fbd0d1c2Jakob Stoklund Olesen const VirtRegMap &VRM; 46078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen const LiveIntervals &LIS; 47078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen const MachineLoopInfo &Loops; 48078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen const TargetInstrInfo &TII; 498ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 50f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen /// Additional information about basic blocks where the current variable is 51f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen /// live. Such a block will look like one of these templates: 52f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen /// 53f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen /// 1. | o---x | Internal to block. Variable is only live in this block. 54f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen /// 2. |---x | Live-in, kill. 55f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen /// 3. | o---| Def, live-out. 56a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen /// 4. |---x o---| Live-in, kill, def, live-out. Counted by NumGapBlocks. 57f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen /// 5. |---o---o---| Live-through with uses or defs. 58a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen /// 6. |-----------| Live-through without uses. Counted by NumThroughBlocks. 59a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen /// 60a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen /// Two BlockInfo entries are created for template 4. One for the live-in 61a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen /// segment, and one for the live-out segment. These entries look as if the 62a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen /// block were split in the middle where the live range isn't live. 63a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen /// 64a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen /// Live-through blocks without any uses don't get BlockInfo entries. They 65a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen /// are simply listed in ThroughBlocks instead. 66f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen /// 67f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen struct BlockInfo { 68f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen MachineBasicBlock *MBB; 69fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen SlotIndex FirstInstr; ///< First instr accessing current reg. 70fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen SlotIndex LastInstr; ///< Last instr accessing current reg. 7177ee1140a3297e6fbd6cb7cf586872af6d00d07eJakob Stoklund Olesen SlotIndex FirstDef; ///< First non-phi valno->def, or SlotIndex(). 72f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen bool LiveIn; ///< Current reg is live in. 73f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen bool LiveOut; ///< Current reg is live out. 7487360f73ae205854f100ba5fb7eef7b90ac3bc27Jakob Stoklund Olesen 7587360f73ae205854f100ba5fb7eef7b90ac3bc27Jakob Stoklund Olesen /// isOneInstr - Returns true when this BlockInfo describes a single 7687360f73ae205854f100ba5fb7eef7b90ac3bc27Jakob Stoklund Olesen /// instruction. 7787360f73ae205854f100ba5fb7eef7b90ac3bc27Jakob Stoklund Olesen bool isOneInstr() const { 78fe62d92b7bbaf73e576bec0c0b11cfa6c191aa87Jakob Stoklund Olesen return SlotIndex::isSameInstr(FirstInstr, LastInstr); 7987360f73ae205854f100ba5fb7eef7b90ac3bc27Jakob Stoklund Olesen } 80f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen }; 81f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 82f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesenprivate: 83f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen // Current live interval. 84078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen const LiveInterval *CurLI; 85f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen 86b20b518f800293ea6b2bed04134c71293ac52403Jakob Stoklund Olesen // Sorted slot indexes of using instructions. 87b20b518f800293ea6b2bed04134c71293ac52403Jakob Stoklund Olesen SmallVector<SlotIndex, 8> UseSlots; 88b20b518f800293ea6b2bed04134c71293ac52403Jakob Stoklund Olesen 891a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen /// LastSplitPoint - Last legal split point in each basic block in the current 901a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen /// function. The first entry is the first terminator, the second entry is the 911a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen /// last valid split point for a variable that is live in to a landing pad 921a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen /// successor. 931a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen SmallVector<std::pair<SlotIndex, SlotIndex>, 8> LastSplitPoint; 941a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen 95db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen /// UseBlocks - Blocks where CurLI has uses. 96db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen SmallVector<BlockInfo, 8> UseBlocks; 97db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen 98a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen /// NumGapBlocks - Number of duplicate entries in UseBlocks for blocks where 99a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen /// the live range has a gap. 100a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen unsigned NumGapBlocks; 101a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen 102db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen /// ThroughBlocks - Block numbers where CurLI is live through without uses. 103f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen BitVector ThroughBlocks; 104f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen 105f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen /// NumThroughBlocks - Number of live-through blocks. 106f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen unsigned NumThroughBlocks; 107db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen 1087d6b6a05b549da70b4473f015c97954c2a422724Jakob Stoklund Olesen /// DidRepairRange - analyze was forced to shrinkToUses(). 1097d6b6a05b549da70b4473f015c97954c2a422724Jakob Stoklund Olesen bool DidRepairRange; 1107d6b6a05b549da70b4473f015c97954c2a422724Jakob Stoklund Olesen 1111a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen SlotIndex computeLastSplitPoint(unsigned Num); 1121a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen 113078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen // Sumarize statistics by counting instructions using CurLI. 114abff28087fd6be8150ff0e69def7de7312b2f76bJakob Stoklund Olesen void analyzeUses(); 1158ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 116f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen /// calcLiveBlockInfo - Compute per-block information about CurLI. 1172b0f9e73d8623b21fc14335ef6208deab2629cdfJakob Stoklund Olesen bool calcLiveBlockInfo(); 118f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen 1198ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesenpublic: 1201b847deb26b52051de39f4cbecd224c9fbd0d1c2Jakob Stoklund Olesen SplitAnalysis(const VirtRegMap &vrm, const LiveIntervals &lis, 121f2c6e367c1c0d8797e62e58a3ccdb8cceee27987Jakob Stoklund Olesen const MachineLoopInfo &mli); 1228ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 123078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen /// analyze - set CurLI to the specified interval, and analyze how it may be 1248ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen /// split. 1258ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen void analyze(const LiveInterval *li); 1268ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 1277d6b6a05b549da70b4473f015c97954c2a422724Jakob Stoklund Olesen /// didRepairRange() - Returns true if CurLI was invalid and has been repaired 1287d6b6a05b549da70b4473f015c97954c2a422724Jakob Stoklund Olesen /// by analyze(). This really shouldn't happen, but sometimes the coalescer 1297d6b6a05b549da70b4473f015c97954c2a422724Jakob Stoklund Olesen /// can create live ranges that end in mid-air. 1307d6b6a05b549da70b4473f015c97954c2a422724Jakob Stoklund Olesen bool didRepairRange() const { return DidRepairRange; } 1317d6b6a05b549da70b4473f015c97954c2a422724Jakob Stoklund Olesen 1328ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen /// clear - clear all data structures so SplitAnalysis is ready to analyze a 1338ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen /// new interval. 1348ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen void clear(); 1358ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 136034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen /// getParent - Return the last analyzed interval. 137034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen const LiveInterval &getParent() const { return *CurLI; } 138034a80d065358b412cdd270e08fb6f1986e65e50Jakob Stoklund Olesen 13974c4f97a466513e45e66e04469973fdcd5865300Jakob Stoklund Olesen /// getLastSplitPoint - Return the base index of the last valid split point 1401a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen /// in the basic block numbered Num. 1411a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen SlotIndex getLastSplitPoint(unsigned Num) { 1421a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen // Inline the common simple case. 1431a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen if (LastSplitPoint[Num].first.isValid() && 1441a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen !LastSplitPoint[Num].second.isValid()) 1451a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen return LastSplitPoint[Num].first; 1461a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen return computeLastSplitPoint(Num); 1471a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen } 1481a7744501a80351ce31fcecad42c8e35823bc081Jakob Stoklund Olesen 14974c4f97a466513e45e66e04469973fdcd5865300Jakob Stoklund Olesen /// getLastSplitPointIter - Returns the last split point as an iterator. 15074c4f97a466513e45e66e04469973fdcd5865300Jakob Stoklund Olesen MachineBasicBlock::iterator getLastSplitPointIter(MachineBasicBlock*); 15174c4f97a466513e45e66e04469973fdcd5865300Jakob Stoklund Olesen 15206c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen /// isOriginalEndpoint - Return true if the original live range was killed or 15306c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen /// (re-)defined at Idx. Idx should be the 'def' slot for a normal kill/def, 15406c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen /// and 'use' for an early-clobber def. 15506c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen /// This can be used to recognize code inserted by earlier live range 15606c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen /// splitting. 15706c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen bool isOriginalEndpoint(SlotIndex Idx) const; 15806c0f25499fd502668ca720b0fea4a4dfe6eb44aJakob Stoklund Olesen 159b20b518f800293ea6b2bed04134c71293ac52403Jakob Stoklund Olesen /// getUseSlots - Return an array of SlotIndexes of instructions using CurLI. 160b20b518f800293ea6b2bed04134c71293ac52403Jakob Stoklund Olesen /// This include both use and def operands, at most one entry per instruction. 161b20b518f800293ea6b2bed04134c71293ac52403Jakob Stoklund Olesen ArrayRef<SlotIndex> getUseSlots() const { return UseSlots; } 162b20b518f800293ea6b2bed04134c71293ac52403Jakob Stoklund Olesen 163db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen /// getUseBlocks - Return an array of BlockInfo objects for the basic blocks 164db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen /// where CurLI has uses. 165b2abfa0bf30edf292a27a06e091d03983e644c9bJakob Stoklund Olesen ArrayRef<BlockInfo> getUseBlocks() const { return UseBlocks; } 166db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen 167f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen /// getNumThroughBlocks - Return the number of through blocks. 168f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen unsigned getNumThroughBlocks() const { return NumThroughBlocks; } 169f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen 170f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen /// isThroughBlock - Return true if CurLI is live through MBB without uses. 171f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen bool isThroughBlock(unsigned MBB) const { return ThroughBlocks.test(MBB); } 172db529a8a5d071610f3a8b467693bc40b073e68efJakob Stoklund Olesen 1735db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen /// getThroughBlocks - Return the set of through blocks. 1745db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen const BitVector &getThroughBlocks() const { return ThroughBlocks; } 1755db4289e404d76664f8aabe2675a4cc2d7b0e98eJakob Stoklund Olesen 176b2abfa0bf30edf292a27a06e091d03983e644c9bJakob Stoklund Olesen /// getNumLiveBlocks - Return the number of blocks where CurLI is live. 177b2abfa0bf30edf292a27a06e091d03983e644c9bJakob Stoklund Olesen unsigned getNumLiveBlocks() const { 178a2e79ef908e0f4179cda9e85e2f75057181bf321Jakob Stoklund Olesen return getUseBlocks().size() - NumGapBlocks + getNumThroughBlocks(); 179b2abfa0bf30edf292a27a06e091d03983e644c9bJakob Stoklund Olesen } 180b2abfa0bf30edf292a27a06e091d03983e644c9bJakob Stoklund Olesen 181b2abfa0bf30edf292a27a06e091d03983e644c9bJakob Stoklund Olesen /// countLiveBlocks - Return the number of blocks where li is live. This is 182b2abfa0bf30edf292a27a06e091d03983e644c9bJakob Stoklund Olesen /// guaranteed to return the same number as getNumLiveBlocks() after calling 183b2abfa0bf30edf292a27a06e091d03983e644c9bJakob Stoklund Olesen /// analyze(li). 1849f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen unsigned countLiveBlocks(const LiveInterval *li) const; 1859f4b893b84d9c2b56aa2abc3c96ce1e5ccc465e5Jakob Stoklund Olesen 1866a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen typedef SmallPtrSet<const MachineBasicBlock*, 16> BlockPtrSet; 1876a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen 1882d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen /// shouldSplitSingleBlock - Returns true if it would help to create a local 1892d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen /// live range for the instructions in BI. There is normally no benefit to 1902d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen /// creating a live range for a single instruction, but it does enable 1912d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen /// register class inflation if the instruction has a restricted register 1922d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen /// class. 1932d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen /// 1942d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen /// @param BI The block to be isolated. 1952d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen /// @param SingleInstrs True when single instructions should be isolated. 1962d6d86be84ee355223ccd20b7f87a0c9971c50c9Jakob Stoklund Olesen bool shouldSplitSingleBlock(const BlockInfo &BI, bool SingleInstrs) const; 1978ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen}; 1988ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 1991407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen 200f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen/// SplitEditor - Edit machine code and LiveIntervals for live range 201f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen/// splitting. 202f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen/// 2035eb308b9448ee5b14fac26c0533eac481bc28471Jakob Stoklund Olesen/// - Create a SplitEditor from a SplitAnalysis. 2047536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen/// - Start a new live interval with openIntv. 2057536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen/// - Mark the places where the new interval is entered using enterIntv* 2067536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen/// - Mark the ranges where the new interval is used with useIntv* 2077536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen/// - Mark the places where the interval is exited with exitIntv*. 2087536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen/// - Finish the current interval with closeIntv and repeat from 2. 2097466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen/// - Rewrite instructions with finish(). 210f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen/// 211f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesenclass SplitEditor { 2120eeca440469e23f2db2bea3d7b136f0f95f6ff1dJakob Stoklund Olesen SplitAnalysis &SA; 213078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen LiveIntervals &LIS; 214078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen VirtRegMap &VRM; 215078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen MachineRegisterInfo &MRI; 2160f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher MachineDominatorTree &MDT; 217078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen const TargetInstrInfo &TII; 218078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen const TargetRegisterInfo &TRI; 2194eed756153b84c211114a3e9186bf0cb55d4b394Benjamin Kramer const MachineBlockFrequencyInfo &MBFI; 220f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 221708d06f7fb5dfd9c8559aea07b042a88c65645f8Jakob Stoklund Olesenpublic: 222708d06f7fb5dfd9c8559aea07b042a88c65645f8Jakob Stoklund Olesen 223708d06f7fb5dfd9c8559aea07b042a88c65645f8Jakob Stoklund Olesen /// ComplementSpillMode - Select how the complement live range should be 224708d06f7fb5dfd9c8559aea07b042a88c65645f8Jakob Stoklund Olesen /// created. SplitEditor automatically creates interval 0 to contain 225708d06f7fb5dfd9c8559aea07b042a88c65645f8Jakob Stoklund Olesen /// anything that isn't added to another interval. This complement interval 226708d06f7fb5dfd9c8559aea07b042a88c65645f8Jakob Stoklund Olesen /// can get quite complicated, and it can sometimes be an advantage to allow 227708d06f7fb5dfd9c8559aea07b042a88c65645f8Jakob Stoklund Olesen /// it to overlap the other intervals. If it is going to spill anyway, no 228708d06f7fb5dfd9c8559aea07b042a88c65645f8Jakob Stoklund Olesen /// registers are wasted by keeping a value in two places at the same time. 229708d06f7fb5dfd9c8559aea07b042a88c65645f8Jakob Stoklund Olesen enum ComplementSpillMode { 230708d06f7fb5dfd9c8559aea07b042a88c65645f8Jakob Stoklund Olesen /// SM_Partition(Default) - Try to create the complement interval so it 231708d06f7fb5dfd9c8559aea07b042a88c65645f8Jakob Stoklund Olesen /// doesn't overlap any other intervals, and the original interval is 232708d06f7fb5dfd9c8559aea07b042a88c65645f8Jakob Stoklund Olesen /// partitioned. This may require a large number of back copies and extra 233708d06f7fb5dfd9c8559aea07b042a88c65645f8Jakob Stoklund Olesen /// PHI-defs. Only segments marked with overlapIntv will be overlapping. 234708d06f7fb5dfd9c8559aea07b042a88c65645f8Jakob Stoklund Olesen SM_Partition, 235708d06f7fb5dfd9c8559aea07b042a88c65645f8Jakob Stoklund Olesen 236708d06f7fb5dfd9c8559aea07b042a88c65645f8Jakob Stoklund Olesen /// SM_Size - Overlap intervals to minimize the number of inserted COPY 237708d06f7fb5dfd9c8559aea07b042a88c65645f8Jakob Stoklund Olesen /// instructions. Copies to the complement interval are hoisted to their 238708d06f7fb5dfd9c8559aea07b042a88c65645f8Jakob Stoklund Olesen /// common dominator, so only one COPY is required per value in the 239708d06f7fb5dfd9c8559aea07b042a88c65645f8Jakob Stoklund Olesen /// complement interval. This also means that no extra PHI-defs need to be 240708d06f7fb5dfd9c8559aea07b042a88c65645f8Jakob Stoklund Olesen /// inserted in the complement interval. 241708d06f7fb5dfd9c8559aea07b042a88c65645f8Jakob Stoklund Olesen SM_Size, 242708d06f7fb5dfd9c8559aea07b042a88c65645f8Jakob Stoklund Olesen 243708d06f7fb5dfd9c8559aea07b042a88c65645f8Jakob Stoklund Olesen /// SM_Speed - Overlap intervals to minimize the expected execution 244708d06f7fb5dfd9c8559aea07b042a88c65645f8Jakob Stoklund Olesen /// frequency of the inserted copies. This is very similar to SM_Size, but 245708d06f7fb5dfd9c8559aea07b042a88c65645f8Jakob Stoklund Olesen /// the complement interval may get some extra PHI-defs. 246708d06f7fb5dfd9c8559aea07b042a88c65645f8Jakob Stoklund Olesen SM_Speed 247708d06f7fb5dfd9c8559aea07b042a88c65645f8Jakob Stoklund Olesen }; 248708d06f7fb5dfd9c8559aea07b042a88c65645f8Jakob Stoklund Olesen 249708d06f7fb5dfd9c8559aea07b042a88c65645f8Jakob Stoklund Olesenprivate: 250708d06f7fb5dfd9c8559aea07b042a88c65645f8Jakob Stoklund Olesen 251078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen /// Edit - The current parent register and new intervals created. 252a2cae58411b36a58f658f9402e8d039add31ae4dJakob Stoklund Olesen LiveRangeEdit *Edit; 253a17768f5822ab62bc18608e5ba473187bf726b84Jakob Stoklund Olesen 2540f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher /// Index into Edit of the currently open interval. 2550f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher /// The index 0 is used for the complement, so the first interval started by 2560f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher /// openIntv will be 1. 2570f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher unsigned OpenIdx; 2580f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher 259708d06f7fb5dfd9c8559aea07b042a88c65645f8Jakob Stoklund Olesen /// The current spill mode, selected by reset(). 260708d06f7fb5dfd9c8559aea07b042a88c65645f8Jakob Stoklund Olesen ComplementSpillMode SpillMode; 261708d06f7fb5dfd9c8559aea07b042a88c65645f8Jakob Stoklund Olesen 2620f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher typedef IntervalMap<SlotIndex, unsigned> RegAssignMap; 2630f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher 2640f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher /// Allocator for the interval map. This will eventually be shared with 2650f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher /// SlotIndexes and LiveIntervals. 2660f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher RegAssignMap::Allocator Allocator; 2670f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher 2680f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher /// RegAssign - Map of the assigned register indexes. 2690f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher /// Edit.get(RegAssign.lookup(Idx)) is the register that should be live at 2700f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher /// Idx. 2710f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher RegAssignMap RegAssign; 272f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 273393bfcb263fa46e4badc73c6aa56306986f94dcfJakob Stoklund Olesen typedef PointerIntPair<VNInfo*, 1> ValueForcePair; 274393bfcb263fa46e4badc73c6aa56306986f94dcfJakob Stoklund Olesen typedef DenseMap<std::pair<unsigned, unsigned>, ValueForcePair> ValueMap; 275670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen 276670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen /// Values - keep track of the mapping from parent values to values in the new 277670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen /// intervals. Given a pair (RegIdx, ParentVNI->id), Values contains: 278670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen /// 279670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen /// 1. No entry - the value is not mapped to Edit.get(RegIdx). 280393bfcb263fa46e4badc73c6aa56306986f94dcfJakob Stoklund Olesen /// 2. (Null, false) - the value is mapped to multiple values in 281393bfcb263fa46e4badc73c6aa56306986f94dcfJakob Stoklund Olesen /// Edit.get(RegIdx). Each value is represented by a minimal live range at 282393bfcb263fa46e4badc73c6aa56306986f94dcfJakob Stoklund Olesen /// its def. The full live range can be inferred exactly from the range 283393bfcb263fa46e4badc73c6aa56306986f94dcfJakob Stoklund Olesen /// of RegIdx in RegAssign. 284393bfcb263fa46e4badc73c6aa56306986f94dcfJakob Stoklund Olesen /// 3. (Null, true). As above, but the ranges in RegAssign are too large, and 285393bfcb263fa46e4badc73c6aa56306986f94dcfJakob Stoklund Olesen /// the live range must be recomputed using LiveRangeCalc::extend(). 286393bfcb263fa46e4badc73c6aa56306986f94dcfJakob Stoklund Olesen /// 4. (VNI, false) The value is mapped to a single new value. 287670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen /// The new value has no live ranges anywhere. 288670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen ValueMap Values; 289670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen 290c1c622ef0dd29d1bafd580790aec5231af50abf2Jakob Stoklund Olesen /// LRCalc - Cache for computing live ranges and SSA update. Each instance 291c1c622ef0dd29d1bafd580790aec5231af50abf2Jakob Stoklund Olesen /// can only handle non-overlapping live ranges, so use a separate 292c1c622ef0dd29d1bafd580790aec5231af50abf2Jakob Stoklund Olesen /// LiveRangeCalc instance for the complement interval when in spill mode. 293c1c622ef0dd29d1bafd580790aec5231af50abf2Jakob Stoklund Olesen LiveRangeCalc LRCalc[2]; 294c1c622ef0dd29d1bafd580790aec5231af50abf2Jakob Stoklund Olesen 295c1c622ef0dd29d1bafd580790aec5231af50abf2Jakob Stoklund Olesen /// getLRCalc - Return the LRCalc to use for RegIdx. In spill mode, the 296c1c622ef0dd29d1bafd580790aec5231af50abf2Jakob Stoklund Olesen /// complement interval can overlap the other intervals, so it gets its own 297c1c622ef0dd29d1bafd580790aec5231af50abf2Jakob Stoklund Olesen /// LRCalc instance. When not in spill mode, all intervals can share one. 298c1c622ef0dd29d1bafd580790aec5231af50abf2Jakob Stoklund Olesen LiveRangeCalc &getLRCalc(unsigned RegIdx) { 299c1c622ef0dd29d1bafd580790aec5231af50abf2Jakob Stoklund Olesen return LRCalc[SpillMode != SM_Partition && RegIdx != 0]; 300c1c622ef0dd29d1bafd580790aec5231af50abf2Jakob Stoklund Olesen } 30144b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen 302670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen /// defValue - define a value in RegIdx from ParentVNI at Idx. 303670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen /// Idx does not have to be ParentVNI->def, but it must be contained within 304670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen /// ParentVNI's live range in ParentLI. The new value is added to the value 305670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen /// map. 306670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen /// Return the new LI value. 307670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen VNInfo *defValue(unsigned RegIdx, const VNInfo *ParentVNI, SlotIndex Idx); 308670ccd18ae1ecec3b3c92885d5b64b21859001c4Jakob Stoklund Olesen 309393bfcb263fa46e4badc73c6aa56306986f94dcfJakob Stoklund Olesen /// forceRecompute - Force the live range of ParentVNI in RegIdx to be 310393bfcb263fa46e4badc73c6aa56306986f94dcfJakob Stoklund Olesen /// recomputed by LiveRangeCalc::extend regardless of the number of defs. 311393bfcb263fa46e4badc73c6aa56306986f94dcfJakob Stoklund Olesen /// This is used for values whose live range doesn't match RegAssign exactly. 312393bfcb263fa46e4badc73c6aa56306986f94dcfJakob Stoklund Olesen /// They could have rematerialized, or back-copies may have been moved. 313393bfcb263fa46e4badc73c6aa56306986f94dcfJakob Stoklund Olesen void forceRecompute(unsigned RegIdx, const VNInfo *ParentVNI); 314e5a2e366322ef5f0d597b1fb8dbf55f2cf36cf15Jakob Stoklund Olesen 315cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen /// defFromParent - Define Reg from ParentVNI at UseIdx using either 316cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen /// rematerialization or a COPY from parent. Return the new value. 3170f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher VNInfo *defFromParent(unsigned RegIdx, 318cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen VNInfo *ParentVNI, 319cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen SlotIndex UseIdx, 320cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen MachineBasicBlock &MBB, 321cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen MachineBasicBlock::iterator I); 322cfa7134a9c33c0c7f8dda359c89dc6763a258e07Jakob Stoklund Olesen 323b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen /// removeBackCopies - Remove the copy instructions that defines the values 324b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen /// in the vector in the complement interval. 325b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen void removeBackCopies(SmallVectorImpl<VNInfo*> &Copies); 326b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen 327c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen /// getShallowDominator - Returns the least busy dominator of MBB that is 328c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen /// also dominated by DefMBB. Busy is measured by loop depth. 329c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen MachineBasicBlock *findShallowDominator(MachineBasicBlock *MBB, 330c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen MachineBasicBlock *DefMBB); 331c4c633852fbb8ab9ef2679b679d2862746d2fa3eJakob Stoklund Olesen 332b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen /// hoistCopiesForSize - Hoist back-copies to the complement interval in a 333b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen /// way that minimizes code size. This implements the SM_Size spill mode. 334b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen void hoistCopiesForSize(); 335b21abfed813fa46976f896439ca2f9fbd2eba9baJakob Stoklund Olesen 33644b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen /// transferValues - Transfer values to the new ranges. 33744b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen /// Return true if any ranges were skipped. 33844b7ae2355a32035ea286555736d173755a1c5e2Jakob Stoklund Olesen bool transferValues(); 3394670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen 340e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen /// extendPHIKillRanges - Extend the ranges of all values killed by original 341e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen /// parent PHIDefs. 342e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen void extendPHIKillRanges(); 343e2dc0c978e2435dbbb55cb7fca7750034c3e292aJakob Stoklund Olesen 3440f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher /// rewriteAssigned - Rewrite all uses of Edit.getReg() to assigned registers. 3454670353a21fbc6e8159a129cda965f256e73a451Jakob Stoklund Olesen void rewriteAssigned(bool ExtendRanges); 3465fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen 3475881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen /// deleteRematVictims - Delete defs that are dead after rematerializing. 3485881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen void deleteRematVictims(); 3495881799d0cccbd814ec1b0f0509df9be1f63c6cbJakob Stoklund Olesen 350f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesenpublic: 351f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen /// Create a new SplitEditor for editing the LiveInterval analyzed by SA. 3527536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen /// Newly created intervals will be appended to newIntervals. 353d68f458244b9d9a6644a9550dd5cee60331c9e7dJakob Stoklund Olesen SplitEditor(SplitAnalysis &SA, LiveIntervals&, VirtRegMap&, 3544eed756153b84c211114a3e9186bf0cb55d4b394Benjamin Kramer MachineDominatorTree&, MachineBlockFrequencyInfo &); 355f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 356bece06f0c6936527e2b1c72d09f7d3a949af9a47Jakob Stoklund Olesen /// reset - Prepare for a new split. 357708d06f7fb5dfd9c8559aea07b042a88c65645f8Jakob Stoklund Olesen void reset(LiveRangeEdit&, ComplementSpillMode = SM_Partition); 358f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 3597536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen /// Create a new virtual register and live interval. 360e1b43c3b4000ee7201fcac8d1c8e75bb9fb547e3Jakob Stoklund Olesen /// Return the interval index, starting from 1. Interval index 0 is the 361e1b43c3b4000ee7201fcac8d1c8e75bb9fb547e3Jakob Stoklund Olesen /// implicit complement interval. 362e1b43c3b4000ee7201fcac8d1c8e75bb9fb547e3Jakob Stoklund Olesen unsigned openIntv(); 363e1b43c3b4000ee7201fcac8d1c8e75bb9fb547e3Jakob Stoklund Olesen 364e1b43c3b4000ee7201fcac8d1c8e75bb9fb547e3Jakob Stoklund Olesen /// currentIntv - Return the current interval index. 365e1b43c3b4000ee7201fcac8d1c8e75bb9fb547e3Jakob Stoklund Olesen unsigned currentIntv() const { return OpenIdx; } 366e1b43c3b4000ee7201fcac8d1c8e75bb9fb547e3Jakob Stoklund Olesen 367e1b43c3b4000ee7201fcac8d1c8e75bb9fb547e3Jakob Stoklund Olesen /// selectIntv - Select a previously opened interval index. 368e1b43c3b4000ee7201fcac8d1c8e75bb9fb547e3Jakob Stoklund Olesen void selectIntv(unsigned Idx); 369f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 370207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen /// enterIntvBefore - Enter the open interval before the instruction at Idx. 371207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen /// If the parent interval is not live before Idx, a COPY is not inserted. 372207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen /// Return the beginning of the new live range. 373207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen SlotIndex enterIntvBefore(SlotIndex Idx); 374f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen 37587360f73ae205854f100ba5fb7eef7b90ac3bc27Jakob Stoklund Olesen /// enterIntvAfter - Enter the open interval after the instruction at Idx. 37687360f73ae205854f100ba5fb7eef7b90ac3bc27Jakob Stoklund Olesen /// Return the beginning of the new live range. 37787360f73ae205854f100ba5fb7eef7b90ac3bc27Jakob Stoklund Olesen SlotIndex enterIntvAfter(SlotIndex Idx); 37887360f73ae205854f100ba5fb7eef7b90ac3bc27Jakob Stoklund Olesen 379207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen /// enterIntvAtEnd - Enter the open interval at the end of MBB. 380dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines /// Use the open interval from the inserted copy to the MBB end. 381207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen /// Return the beginning of the new live range. 382207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen SlotIndex enterIntvAtEnd(MachineBasicBlock &MBB); 383f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 384078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen /// useIntv - indicate that all instructions in MBB should use OpenLI. 3857536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen void useIntv(const MachineBasicBlock &MBB); 386f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 387078628465b73348b5608ec6aa2d7181679543903Jakob Stoklund Olesen /// useIntv - indicate that all instructions in range should use OpenLI. 3887536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen void useIntv(SlotIndex Start, SlotIndex End); 389f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 390207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen /// leaveIntvAfter - Leave the open interval after the instruction at Idx. 391207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen /// Return the end of the live range. 392207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen SlotIndex leaveIntvAfter(SlotIndex Idx); 393f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen 3949b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen /// leaveIntvBefore - Leave the open interval before the instruction at Idx. 3959b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen /// Return the end of the live range. 3969b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen SlotIndex leaveIntvBefore(SlotIndex Idx); 3979b057771ba22441b8d312404204433477b4be657Jakob Stoklund Olesen 3987536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen /// leaveIntvAtTop - Leave the interval at the top of MBB. 399207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen /// Add liveness from the MBB top to the copy. 400207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen /// Return the end of the live range. 401207c868c9210663d401b7f5ce5cae7c3e0943849Jakob Stoklund Olesen SlotIndex leaveIntvAtTop(MachineBasicBlock &MBB); 402f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 4035c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen /// overlapIntv - Indicate that all instructions in range should use the open 4045c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen /// interval, but also let the complement interval be live. 4055c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen /// 4065c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen /// This doubles the register pressure, but is sometimes required to deal with 4075c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen /// register uses after the last valid split point. 4085c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen /// 4095c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen /// The Start index should be a return value from a leaveIntv* call, and End 4105c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen /// should be in the same basic block. The parent interval must have the same 4115c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen /// value across the range. 4125c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen /// 4135c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen void overlapIntv(SlotIndex Start, SlotIndex End); 4145c716bdccce2fa504e1aa0b67226165d181d2459Jakob Stoklund Olesen 4157466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen /// finish - after all the new live ranges have been created, compute the 4167466927b1af264b359c860cb9f7d1f3b275cc5cdJakob Stoklund Olesen /// remaining live range, and rewrite instructions to use the new registers. 4175928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen /// @param LRMap When not null, this vector will map each live range in Edit 4185928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen /// back to the indices returned by openIntv. 4195928046306d8bbe7db35707c294689f515f90e56Jakob Stoklund Olesen /// There may be extra indices created by dead code elimination. 420dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines void finish(SmallVectorImpl<unsigned> *LRMap = nullptr); 421f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 4220f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher /// dump - print the current interval maping to dbgs(). 4230f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher void dump() const; 4240f43811903f10394f7088f4634c0b4f9668cbac0Eric Christopher 425f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen // ===--- High level methods ---=== 426f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 427fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen /// splitSingleBlock - Split CurLI into a separate live interval around the 428fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen /// uses in a single block. This is intended to be used as part of a larger 429fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen /// split, and doesn't call finish(). 430fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen void splitSingleBlock(const SplitAnalysis::BlockInfo &BI); 431fd5c51342a429ecab86a645282d0b36b216c0256Jakob Stoklund Olesen 432b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen /// splitLiveThroughBlock - Split CurLI in the given block such that it 433b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen /// enters the block in IntvIn and leaves it in IntvOut. There may be uses in 434b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen /// the block, but they will be ignored when placing split points. 435b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen /// 436b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen /// @param MBBNum Block number. 437b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen /// @param IntvIn Interval index entering the block. 438b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen /// @param LeaveBefore When set, leave IntvIn before this point. 439b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen /// @param IntvOut Interval index leaving the block. 440b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen /// @param EnterAfter When set, enter IntvOut after this point. 441b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen void splitLiveThroughBlock(unsigned MBBNum, 442b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen unsigned IntvIn, SlotIndex LeaveBefore, 443b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen unsigned IntvOut, SlotIndex EnterAfter); 444b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 445b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen /// splitRegInBlock - Split CurLI in the given block such that it enters the 446b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen /// block in IntvIn and leaves it on the stack (or not at all). Split points 447b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen /// are placed in a way that avoids putting uses in the stack interval. This 448b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen /// may require creating a local interval when there is interference. 449b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen /// 450b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen /// @param BI Block descriptor. 451b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen /// @param IntvIn Interval index entering the block. Not 0. 452b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen /// @param LeaveBefore When set, leave IntvIn before this point. 453b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen void splitRegInBlock(const SplitAnalysis::BlockInfo &BI, 454b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen unsigned IntvIn, SlotIndex LeaveBefore); 455b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen 456b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen /// splitRegOutBlock - Split CurLI in the given block such that it enters the 457b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen /// block on the stack (or isn't live-in at all) and leaves it in IntvOut. 458b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen /// Split points are placed to avoid interference and such that the uses are 459b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen /// not in the stack interval. This may require creating a local interval 460b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen /// when there is interference. 461b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen /// 462b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen /// @param BI Block descriptor. 463b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen /// @param IntvOut Interval index leaving the block. 464b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen /// @param EnterAfter When set, enter IntvOut after this point. 465b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen void splitRegOutBlock(const SplitAnalysis::BlockInfo &BI, 466b4ddedce599183362b0f0333922c2fe0e163a129Jakob Stoklund Olesen unsigned IntvOut, SlotIndex EnterAfter); 467fc412d85c46a8656361fe1e9197ea85922e2cd61Jakob Stoklund Olesen}; 4688ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 4698ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen} 4706796e4fc889d99c4ad97ec5ad86e4c8cf75e52a4Sebastian Redl 4716796e4fc889d99c4ad97ec5ad86e4c8cf75e52a4Sebastian Redl#endif 472