119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman//===-------- SplitKit.h - Toolkit for splitting live ranges ----*- C++ -*-===// 2894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 3894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// The LLVM Compiler Infrastructure 4894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 5894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// This file is distributed under the University of Illinois Open Source 6894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// License. See LICENSE.TXT for details. 7894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 8894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 9894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 10894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// This file contains the SplitAnalysis class as well as mutator functions for 11894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// live range splitting. 12894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 13894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 14894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 1519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#ifndef LLVM_CODEGEN_SPLITKIT_H 1619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#define LLVM_CODEGEN_SPLITKIT_H 1719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 1819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "LiveRangeCalc.h" 1919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/ADT/ArrayRef.h" 20894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/ADT/DenseMap.h" 2119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/ADT/IntervalMap.h" 2219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/ADT/SmallPtrSet.h" 23894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 24894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumannamespace llvm { 25894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 2619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanclass ConnectedVNInfoEqClasses; 27894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanclass LiveInterval; 28894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanclass LiveIntervals; 2919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanclass LiveRangeEdit; 30894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanclass MachineInstr; 31894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanclass MachineLoopInfo; 32894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanclass MachineRegisterInfo; 33894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanclass TargetInstrInfo; 3419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanclass TargetRegisterInfo; 35894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanclass VirtRegMap; 36894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanclass VNInfo; 3719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanclass raw_ostream; 38894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 39894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// SplitAnalysis - Analyze a LiveInterval, looking for live range splitting 40894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// opportunities. 41894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanclass SplitAnalysis { 42894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanpublic: 4319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const MachineFunction &MF; 4419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const VirtRegMap &VRM; 4519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const LiveIntervals &LIS; 4619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const MachineLoopInfo &Loops; 4719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const TargetInstrInfo &TII; 4819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 4919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Sorted slot indexes of using instructions. 5019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SmallVector<SlotIndex, 8> UseSlots; 5119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 5219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// Additional information about basic blocks where the current variable is 5319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// live. Such a block will look like one of these templates: 5419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// 5519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// 1. | o---x | Internal to block. Variable is only live in this block. 5619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// 2. |---x | Live-in, kill. 5719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// 3. | o---| Def, live-out. 5819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// 4. |---x o---| Live-in, kill, def, live-out. Counted by NumGapBlocks. 5919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// 5. |---o---o---| Live-through with uses or defs. 6019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// 6. |-----------| Live-through without uses. Counted by NumThroughBlocks. 6119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// 6219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// Two BlockInfo entries are created for template 4. One for the live-in 6319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// segment, and one for the live-out segment. These entries look as if the 6419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// block were split in the middle where the live range isn't live. 6519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// 6619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// Live-through blocks without any uses don't get BlockInfo entries. They 6719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// are simply listed in ThroughBlocks instead. 6819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// 6919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman struct BlockInfo { 7019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineBasicBlock *MBB; 7119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SlotIndex FirstInstr; ///< First instr accessing current reg. 7219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SlotIndex LastInstr; ///< Last instr accessing current reg. 7319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SlotIndex FirstDef; ///< First non-phi valno->def, or SlotIndex(). 7419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool LiveIn; ///< Current reg is live in. 7519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool LiveOut; ///< Current reg is live out. 7619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 7719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// isOneInstr - Returns true when this BlockInfo describes a single 7819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// instruction. 7919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool isOneInstr() const { 8019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return SlotIndex::isSameInstr(FirstInstr, LastInstr); 8119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 8219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman }; 83894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 84894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanprivate: 85894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Current live interval. 8619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const LiveInterval *CurLI; 87894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 8819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// LastSplitPoint - Last legal split point in each basic block in the current 8919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// function. The first entry is the first terminator, the second entry is the 9019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// last valid split point for a variable that is live in to a landing pad 9119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// successor. 9219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SmallVector<std::pair<SlotIndex, SlotIndex>, 8> LastSplitPoint; 93894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 9419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// UseBlocks - Blocks where CurLI has uses. 9519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SmallVector<BlockInfo, 8> UseBlocks; 96894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 9719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// NumGapBlocks - Number of duplicate entries in UseBlocks for blocks where 9819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// the live range has a gap. 9919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned NumGapBlocks; 100894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 10119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// ThroughBlocks - Block numbers where CurLI is live through without uses. 10219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BitVector ThroughBlocks; 10319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 10419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// NumThroughBlocks - Number of live-through blocks. 10519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned NumThroughBlocks; 10619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 10719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// DidRepairRange - analyze was forced to shrinkToUses(). 10819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool DidRepairRange; 10919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 11019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SlotIndex computeLastSplitPoint(unsigned Num); 11119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 11219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Sumarize statistics by counting instructions using CurLI. 113894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void analyzeUses(); 114894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 11519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// calcLiveBlockInfo - Compute per-block information about CurLI. 11619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool calcLiveBlockInfo(); 117894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 118894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanpublic: 11919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SplitAnalysis(const VirtRegMap &vrm, const LiveIntervals &lis, 120894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const MachineLoopInfo &mli); 121894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 12219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// analyze - set CurLI to the specified interval, and analyze how it may be 123894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// split. 124894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void analyze(const LiveInterval *li); 125894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 12619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// didRepairRange() - Returns true if CurLI was invalid and has been repaired 12719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// by analyze(). This really shouldn't happen, but sometimes the coalescer 12819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// can create live ranges that end in mid-air. 12919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool didRepairRange() const { return DidRepairRange; } 130894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 131894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// clear - clear all data structures so SplitAnalysis is ready to analyze a 132894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// new interval. 133894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void clear(); 134894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 13519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// getParent - Return the last analyzed interval. 13619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const LiveInterval &getParent() const { return *CurLI; } 13719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 13819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// getLastSplitPoint - Return that base index of the last valid split point 13919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// in the basic block numbered Num. 14019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SlotIndex getLastSplitPoint(unsigned Num) { 14119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Inline the common simple case. 14219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (LastSplitPoint[Num].first.isValid() && 14319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman !LastSplitPoint[Num].second.isValid()) 14419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return LastSplitPoint[Num].first; 14519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return computeLastSplitPoint(Num); 14619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 14719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 14819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// isOriginalEndpoint - Return true if the original live range was killed or 14919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// (re-)defined at Idx. Idx should be the 'def' slot for a normal kill/def, 15019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// and 'use' for an early-clobber def. 15119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// This can be used to recognize code inserted by earlier live range 15219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// splitting. 15319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool isOriginalEndpoint(SlotIndex Idx) const; 15419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 15519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// getUseBlocks - Return an array of BlockInfo objects for the basic blocks 15619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// where CurLI has uses. 15719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ArrayRef<BlockInfo> getUseBlocks() const { return UseBlocks; } 15819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 15919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// getNumThroughBlocks - Return the number of through blocks. 16019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned getNumThroughBlocks() const { return NumThroughBlocks; } 16119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 16219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// isThroughBlock - Return true if CurLI is live through MBB without uses. 16319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool isThroughBlock(unsigned MBB) const { return ThroughBlocks.test(MBB); } 16419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 16519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// getThroughBlocks - Return the set of through blocks. 16619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const BitVector &getThroughBlocks() const { return ThroughBlocks; } 16719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 16819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// getNumLiveBlocks - Return the number of blocks where CurLI is live. 16919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned getNumLiveBlocks() const { 17019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return getUseBlocks().size() - NumGapBlocks + getNumThroughBlocks(); 17119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 17219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 17319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// countLiveBlocks - Return the number of blocks where li is live. This is 17419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// guaranteed to return the same number as getNumLiveBlocks() after calling 17519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// analyze(li). 17619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned countLiveBlocks(const LiveInterval *li) const; 177894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 17819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman typedef SmallPtrSet<const MachineBasicBlock*, 16> BlockPtrSet; 179894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 18019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// shouldSplitSingleBlock - Returns true if it would help to create a local 18119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// live range for the instructions in BI. There is normally no benefit to 18219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// creating a live range for a single instruction, but it does enable 18319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// register class inflation if the instruction has a restricted register 18419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// class. 18519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// 18619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param BI The block to be isolated. 18719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param SingleInstrs True when single instructions should be isolated. 18819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool shouldSplitSingleBlock(const BlockInfo &BI, bool SingleInstrs) const; 189894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman}; 190894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 19119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 192894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// SplitEditor - Edit machine code and LiveIntervals for live range 193894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// splitting. 194894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// 195894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// - Create a SplitEditor from a SplitAnalysis. 196894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// - Start a new live interval with openIntv. 197894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// - Mark the places where the new interval is entered using enterIntv* 198894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// - Mark the ranges where the new interval is used with useIntv* 199894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// - Mark the places where the interval is exited with exitIntv*. 200894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// - Finish the current interval with closeIntv and repeat from 2. 20119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// - Rewrite instructions with finish(). 202894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// 203894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanclass SplitEditor { 20419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SplitAnalysis &SA; 20519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LiveIntervals &LIS; 20619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman VirtRegMap &VRM; 20719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineRegisterInfo &MRI; 20819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineDominatorTree &MDT; 20919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const TargetInstrInfo &TII; 21019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const TargetRegisterInfo &TRI; 211894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 21219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanpublic: 213894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 21419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// ComplementSpillMode - Select how the complement live range should be 21519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// created. SplitEditor automatically creates interval 0 to contain 21619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// anything that isn't added to another interval. This complement interval 21719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// can get quite complicated, and it can sometimes be an advantage to allow 21819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// it to overlap the other intervals. If it is going to spill anyway, no 21919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// registers are wasted by keeping a value in two places at the same time. 22019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman enum ComplementSpillMode { 22119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// SM_Partition(Default) - Try to create the complement interval so it 22219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// doesn't overlap any other intervals, and the original interval is 22319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// partitioned. This may require a large number of back copies and extra 22419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// PHI-defs. Only segments marked with overlapIntv will be overlapping. 22519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SM_Partition, 22619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 22719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// SM_Size - Overlap intervals to minimize the number of inserted COPY 22819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// instructions. Copies to the complement interval are hoisted to their 22919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// common dominator, so only one COPY is required per value in the 23019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// complement interval. This also means that no extra PHI-defs need to be 23119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// inserted in the complement interval. 23219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SM_Size, 23319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 23419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// SM_Speed - Overlap intervals to minimize the expected execution 23519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// frequency of the inserted copies. This is very similar to SM_Size, but 23619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// the complement interval may get some extra PHI-defs. 23719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SM_Speed 23819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman }; 239894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 24019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanprivate: 241894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 24219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// Edit - The current parent register and new intervals created. 24319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LiveRangeEdit *Edit; 24419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 24519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// Index into Edit of the currently open interval. 24619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// The index 0 is used for the complement, so the first interval started by 24719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// openIntv will be 1. 24819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned OpenIdx; 24919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 25019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// The current spill mode, selected by reset(). 25119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ComplementSpillMode SpillMode; 25219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 25319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman typedef IntervalMap<SlotIndex, unsigned> RegAssignMap; 25419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 25519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// Allocator for the interval map. This will eventually be shared with 25619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// SlotIndexes and LiveIntervals. 25719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman RegAssignMap::Allocator Allocator; 25819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 25919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// RegAssign - Map of the assigned register indexes. 26019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// Edit.get(RegAssign.lookup(Idx)) is the register that should be live at 26119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// Idx. 26219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman RegAssignMap RegAssign; 26319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 26419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman typedef PointerIntPair<VNInfo*, 1> ValueForcePair; 26519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman typedef DenseMap<std::pair<unsigned, unsigned>, ValueForcePair> ValueMap; 26619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 26719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// Values - keep track of the mapping from parent values to values in the new 26819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// intervals. Given a pair (RegIdx, ParentVNI->id), Values contains: 26919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// 27019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// 1. No entry - the value is not mapped to Edit.get(RegIdx). 27119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// 2. (Null, false) - the value is mapped to multiple values in 27219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// Edit.get(RegIdx). Each value is represented by a minimal live range at 27319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// its def. The full live range can be inferred exactly from the range 27419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// of RegIdx in RegAssign. 27519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// 3. (Null, true). As above, but the ranges in RegAssign are too large, and 27619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// the live range must be recomputed using LiveRangeCalc::extend(). 27719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// 4. (VNI, false) The value is mapped to a single new value. 27819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// The new value has no live ranges anywhere. 27919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ValueMap Values; 28019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 28119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// LRCalc - Cache for computing live ranges and SSA update. Each instance 28219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// can only handle non-overlapping live ranges, so use a separate 28319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// LiveRangeCalc instance for the complement interval when in spill mode. 28419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LiveRangeCalc LRCalc[2]; 28519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 28619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// getLRCalc - Return the LRCalc to use for RegIdx. In spill mode, the 28719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// complement interval can overlap the other intervals, so it gets its own 28819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// LRCalc instance. When not in spill mode, all intervals can share one. 28919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LiveRangeCalc &getLRCalc(unsigned RegIdx) { 29019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return LRCalc[SpillMode != SM_Partition && RegIdx != 0]; 29119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 29219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 29319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// defValue - define a value in RegIdx from ParentVNI at Idx. 29419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// Idx does not have to be ParentVNI->def, but it must be contained within 29519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// ParentVNI's live range in ParentLI. The new value is added to the value 29619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// map. 29719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// Return the new LI value. 29819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman VNInfo *defValue(unsigned RegIdx, const VNInfo *ParentVNI, SlotIndex Idx); 29919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 30019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// forceRecompute - Force the live range of ParentVNI in RegIdx to be 30119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// recomputed by LiveRangeCalc::extend regardless of the number of defs. 30219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// This is used for values whose live range doesn't match RegAssign exactly. 30319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// They could have rematerialized, or back-copies may have been moved. 30419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void forceRecompute(unsigned RegIdx, const VNInfo *ParentVNI); 30519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 30619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// defFromParent - Define Reg from ParentVNI at UseIdx using either 30719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// rematerialization or a COPY from parent. Return the new value. 30819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman VNInfo *defFromParent(unsigned RegIdx, 30919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman VNInfo *ParentVNI, 31019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SlotIndex UseIdx, 31119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineBasicBlock &MBB, 31219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineBasicBlock::iterator I); 31319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 31419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// removeBackCopies - Remove the copy instructions that defines the values 31519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// in the vector in the complement interval. 31619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void removeBackCopies(SmallVectorImpl<VNInfo*> &Copies); 31719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 31819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// getShallowDominator - Returns the least busy dominator of MBB that is 31919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// also dominated by DefMBB. Busy is measured by loop depth. 32019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineBasicBlock *findShallowDominator(MachineBasicBlock *MBB, 32119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineBasicBlock *DefMBB); 32219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 32319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// hoistCopiesForSize - Hoist back-copies to the complement interval in a 32419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// way that minimizes code size. This implements the SM_Size spill mode. 32519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void hoistCopiesForSize(); 32619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 32719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// transferValues - Transfer values to the new ranges. 32819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// Return true if any ranges were skipped. 32919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool transferValues(); 33019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 33119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// extendPHIKillRanges - Extend the ranges of all values killed by original 33219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// parent PHIDefs. 33319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void extendPHIKillRanges(); 33419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 33519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// rewriteAssigned - Rewrite all uses of Edit.getReg() to assigned registers. 33619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void rewriteAssigned(bool ExtendRanges); 33719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 33819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// deleteRematVictims - Delete defs that are dead after rematerializing. 33919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void deleteRematVictims(); 340894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 341894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanpublic: 342894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// Create a new SplitEditor for editing the LiveInterval analyzed by SA. 343894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// Newly created intervals will be appended to newIntervals. 344894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SplitEditor(SplitAnalysis &SA, LiveIntervals&, VirtRegMap&, 34519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineDominatorTree&); 346894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 34719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// reset - Prepare for a new split. 34819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void reset(LiveRangeEdit&, ComplementSpillMode = SM_Partition); 349894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 350894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// Create a new virtual register and live interval. 35119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// Return the interval index, starting from 1. Interval index 0 is the 35219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// implicit complement interval. 35319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned openIntv(); 35419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 35519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// currentIntv - Return the current interval index. 35619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned currentIntv() const { return OpenIdx; } 35719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 35819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// selectIntv - Select a previously opened interval index. 35919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void selectIntv(unsigned Idx); 36019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 36119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// enterIntvBefore - Enter the open interval before the instruction at Idx. 36219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// If the parent interval is not live before Idx, a COPY is not inserted. 36319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// Return the beginning of the new live range. 36419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SlotIndex enterIntvBefore(SlotIndex Idx); 36519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 36619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// enterIntvAfter - Enter the open interval after the instruction at Idx. 36719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// Return the beginning of the new live range. 36819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SlotIndex enterIntvAfter(SlotIndex Idx); 369894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 37019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// enterIntvAtEnd - Enter the open interval at the end of MBB. 37119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// Use the open interval from he inserted copy to the MBB end. 37219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// Return the beginning of the new live range. 37319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SlotIndex enterIntvAtEnd(MachineBasicBlock &MBB); 374894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 37519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// useIntv - indicate that all instructions in MBB should use OpenLI. 376894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void useIntv(const MachineBasicBlock &MBB); 377894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 37819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// useIntv - indicate that all instructions in range should use OpenLI. 379894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void useIntv(SlotIndex Start, SlotIndex End); 380894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 38119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// leaveIntvAfter - Leave the open interval after the instruction at Idx. 38219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// Return the end of the live range. 38319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SlotIndex leaveIntvAfter(SlotIndex Idx); 384894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 38519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// leaveIntvBefore - Leave the open interval before the instruction at Idx. 38619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// Return the end of the live range. 38719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SlotIndex leaveIntvBefore(SlotIndex Idx); 388894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 38919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// leaveIntvAtTop - Leave the interval at the top of MBB. 39019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// Add liveness from the MBB top to the copy. 39119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// Return the end of the live range. 39219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SlotIndex leaveIntvAtTop(MachineBasicBlock &MBB); 39319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 39419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// overlapIntv - Indicate that all instructions in range should use the open 39519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// interval, but also let the complement interval be live. 39619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// 39719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// This doubles the register pressure, but is sometimes required to deal with 39819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// register uses after the last valid split point. 39919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// 40019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// The Start index should be a return value from a leaveIntv* call, and End 40119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// should be in the same basic block. The parent interval must have the same 40219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// value across the range. 40319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// 40419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void overlapIntv(SlotIndex Start, SlotIndex End); 40519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 40619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// finish - after all the new live ranges have been created, compute the 40719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// remaining live range, and rewrite instructions to use the new registers. 40819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param LRMap When not null, this vector will map each live range in Edit 40919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// back to the indices returned by openIntv. 41019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// There may be extra indices created by dead code elimination. 41119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void finish(SmallVectorImpl<unsigned> *LRMap = 0); 41219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 41319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// dump - print the current interval maping to dbgs(). 41419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void dump() const; 415894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 416894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // ===--- High level methods ---=== 417894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 41819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// splitSingleBlock - Split CurLI into a separate live interval around the 41919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// uses in a single block. This is intended to be used as part of a larger 42019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// split, and doesn't call finish(). 42119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void splitSingleBlock(const SplitAnalysis::BlockInfo &BI); 42219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 42319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// splitLiveThroughBlock - Split CurLI in the given block such that it 42419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// enters the block in IntvIn and leaves it in IntvOut. There may be uses in 42519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// the block, but they will be ignored when placing split points. 42619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// 42719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param MBBNum Block number. 42819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param IntvIn Interval index entering the block. 42919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param LeaveBefore When set, leave IntvIn before this point. 43019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param IntvOut Interval index leaving the block. 43119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param EnterAfter When set, enter IntvOut after this point. 43219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void splitLiveThroughBlock(unsigned MBBNum, 43319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned IntvIn, SlotIndex LeaveBefore, 43419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned IntvOut, SlotIndex EnterAfter); 43519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 43619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// splitRegInBlock - Split CurLI in the given block such that it enters the 43719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// block in IntvIn and leaves it on the stack (or not at all). Split points 43819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// are placed in a way that avoids putting uses in the stack interval. This 43919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// may require creating a local interval when there is interference. 44019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// 44119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param BI Block descriptor. 44219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param IntvIn Interval index entering the block. Not 0. 44319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param LeaveBefore When set, leave IntvIn before this point. 44419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void splitRegInBlock(const SplitAnalysis::BlockInfo &BI, 44519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned IntvIn, SlotIndex LeaveBefore); 44619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 44719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// splitRegOutBlock - Split CurLI in the given block such that it enters the 44819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// block on the stack (or isn't live-in at all) and leaves it in IntvOut. 44919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// Split points are placed to avoid interference and such that the uses are 45019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// not in the stack interval. This may require creating a local interval 45119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// when there is interference. 45219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// 45319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param BI Block descriptor. 45419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param IntvOut Interval index leaving the block. 45519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param EnterAfter When set, enter IntvOut after this point. 45619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void splitRegOutBlock(const SplitAnalysis::BlockInfo &BI, 45719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned IntvOut, SlotIndex EnterAfter); 458894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman}; 459894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 460894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 46119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 46219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#endif 463