SplitKit.h revision 57d0f2deb0afefe69770a28937a4363e7b1f9753
18ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen//===---------- SplitKit.cpp - Toolkit for splitting live ranges ----------===// 28ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen// 38ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen// The LLVM Compiler Infrastructure 48ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen// 58ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen// This file is distributed under the University of Illinois Open Source 68ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen// License. See LICENSE.TXT for details. 78ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen// 88ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen//===----------------------------------------------------------------------===// 98ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen// 108ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen// This file contains the SplitAnalysis class as well as mutator functions for 118ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen// live range splitting. 128ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen// 138ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen//===----------------------------------------------------------------------===// 148ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 158ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen#include "llvm/ADT/SmallPtrSet.h" 168ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen#include "llvm/ADT/DenseMap.h" 17f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen#include "llvm/CodeGen/SlotIndexes.h" 188ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 198ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesennamespace llvm { 208ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 218ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesenclass LiveInterval; 228ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesenclass LiveIntervals; 238ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesenclass MachineInstr; 248ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesenclass MachineLoop; 258ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesenclass MachineLoopInfo; 26f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesenclass MachineRegisterInfo; 276a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesenclass TargetInstrInfo; 28f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesenclass VirtRegMap; 29f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesenclass VNInfo; 308ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 31f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen/// SplitAnalysis - Analyze a LiveInterval, looking for live range splitting 32f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen/// opportunities. 338ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesenclass SplitAnalysis { 3408e93b14c37277ab40b835de340f89ba357d3332Jakob Stoklund Olesenpublic: 358ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen const MachineFunction &mf_; 368ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen const LiveIntervals &lis_; 378ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen const MachineLoopInfo &loops_; 386a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen const TargetInstrInfo &tii_; 398ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 408ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen // Instructions using the the current register. 418ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen typedef SmallPtrSet<const MachineInstr*, 16> InstrPtrSet; 428ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen InstrPtrSet usingInstrs_; 438ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 448ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen // The number of instructions using curli in each basic block. 458ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen typedef DenseMap<const MachineBasicBlock*, unsigned> BlockCountMap; 468ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen BlockCountMap usingBlocks_; 478ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 482dee7a527b083e259f9e826c57c1e5dab9540798Jakob Stoklund Olesen // The number of basic block using curli in each loop. 492dee7a527b083e259f9e826c57c1e5dab9540798Jakob Stoklund Olesen typedef DenseMap<const MachineLoop*, unsigned> LoopCountMap; 502dee7a527b083e259f9e826c57c1e5dab9540798Jakob Stoklund Olesen LoopCountMap usingLoops_; 518ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 52f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesenprivate: 53f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen // Current live interval. 54f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen const LiveInterval *curli_; 55f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen 568ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen // Sumarize statistics by counting instructions using curli_. 57abff28087fd6be8150ff0e69def7de7312b2f76bJakob Stoklund Olesen void analyzeUses(); 588ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 596a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen /// canAnalyzeBranch - Return true if MBB ends in a branch that can be 606a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen /// analyzed. 616a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen bool canAnalyzeBranch(const MachineBasicBlock *MBB); 626a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen 638ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesenpublic: 64f2c6e367c1c0d8797e62e58a3ccdb8cceee27987Jakob Stoklund Olesen SplitAnalysis(const MachineFunction &mf, const LiveIntervals &lis, 65f2c6e367c1c0d8797e62e58a3ccdb8cceee27987Jakob Stoklund Olesen const MachineLoopInfo &mli); 668ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 678ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen /// analyze - set curli to the specified interval, and analyze how it may be 688ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen /// split. 698ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen void analyze(const LiveInterval *li); 708ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 712dee7a527b083e259f9e826c57c1e5dab9540798Jakob Stoklund Olesen /// removeUse - Update statistics by noting that mi no longer uses curli. 722dee7a527b083e259f9e826c57c1e5dab9540798Jakob Stoklund Olesen void removeUse(const MachineInstr *mi); 732dee7a527b083e259f9e826c57c1e5dab9540798Jakob Stoklund Olesen 74f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen const LiveInterval *getCurLI() { return curli_; } 75f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 768ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen /// clear - clear all data structures so SplitAnalysis is ready to analyze a 778ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen /// new interval. 788ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen void clear(); 798ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 806a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen typedef SmallPtrSet<const MachineBasicBlock*, 16> BlockPtrSet; 812dee7a527b083e259f9e826c57c1e5dab9540798Jakob Stoklund Olesen typedef SmallPtrSet<const MachineLoop*, 16> LoopPtrSet; 826a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen 836a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen // Sets of basic blocks surrounding a machine loop. 846a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen struct LoopBlocks { 856a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen BlockPtrSet Loop; // Blocks in the loop. 866a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen BlockPtrSet Preds; // Loop predecessor blocks. 876a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen BlockPtrSet Exits; // Loop exit blocks. 886a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen 896a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen void clear() { 906a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen Loop.clear(); 916a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen Preds.clear(); 926a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen Exits.clear(); 936a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen } 946a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen }; 956a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen 966a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen // Calculate the block sets surrounding the loop. 976a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen void getLoopBlocks(const MachineLoop *Loop, LoopBlocks &Blocks); 986a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen 998ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen /// LoopPeripheralUse - how is a variable used in and around a loop? 1008ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen /// Peripheral blocks are the loop predecessors and exit blocks. 1018ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen enum LoopPeripheralUse { 1028ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen ContainedInLoop, // All uses are inside the loop. 1038ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen SinglePeripheral, // At most one instruction per peripheral block. 1048ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen MultiPeripheral, // Multiple instructions in some peripheral blocks. 1058ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen OutsideLoop // Uses outside loop periphery. 1068ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen }; 1078ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 1088ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen /// analyzeLoopPeripheralUse - Return an enum describing how curli_ is used in 1098ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen /// and around the Loop. 1106a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen LoopPeripheralUse analyzeLoopPeripheralUse(const LoopBlocks&); 1116a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen 1126a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen /// getCriticalExits - It may be necessary to partially break critical edges 1136a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen /// leaving the loop if an exit block has phi uses of curli. Collect the exit 1146a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen /// blocks that need special treatment into CriticalExits. 1156a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen void getCriticalExits(const LoopBlocks &Blocks, BlockPtrSet &CriticalExits); 1166a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen 1176a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen /// canSplitCriticalExits - Return true if it is possible to insert new exit 1186a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen /// blocks before the blocks in CriticalExits. 1196a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen bool canSplitCriticalExits(const LoopBlocks &Blocks, 1206a0dc079efe7acf7e71cc4c0948fe814f35ba091Jakob Stoklund Olesen BlockPtrSet &CriticalExits); 1218ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 1228ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen /// getBestSplitLoop - Return the loop where curli may best be split to a 1238ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen /// separate register, or NULL. 1248ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen const MachineLoop *getBestSplitLoop(); 125f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen 126f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen /// getMultiUseBlocks - Add basic blocks to Blocks that may benefit from 127f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen /// having curli split to a new live interval. Return true if Blocks can be 128f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen /// passed to SplitEditor::splitSingleBlocks. 129f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen bool getMultiUseBlocks(BlockPtrSet &Blocks); 130fc412d85c46a8656361fe1e9197ea85922e2cd61Jakob Stoklund Olesen 131fc412d85c46a8656361fe1e9197ea85922e2cd61Jakob Stoklund Olesen /// getBlockForInsideSplit - If curli is contained inside a single basic block, 132fc412d85c46a8656361fe1e9197ea85922e2cd61Jakob Stoklund Olesen /// and it wou pay to subdivide the interval inside that block, return it. 133fc412d85c46a8656361fe1e9197ea85922e2cd61Jakob Stoklund Olesen /// Otherwise return NULL. The returned block can be passed to 134fc412d85c46a8656361fe1e9197ea85922e2cd61Jakob Stoklund Olesen /// SplitEditor::splitInsideBlock. 135fc412d85c46a8656361fe1e9197ea85922e2cd61Jakob Stoklund Olesen const MachineBasicBlock *getBlockForInsideSplit(); 1368ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen}; 1378ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 1381407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen 1391407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen/// LiveIntervalMap - Map values from a large LiveInterval into a small 1401407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen/// interval that is a subset. Insert phi-def values as needed. This class is 1411407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen/// used by SplitEditor to create new smaller LiveIntervals. 1421407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen/// 1431407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen/// parentli_ is the larger interval, li_ is the subset interval. Every value 1441407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen/// in li_ corresponds to exactly one value in parentli_, and the live range 1451407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen/// of the value is contained within the live range of the parentli_ value. 1461407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen/// Values in parentli_ may map to any number of openli_ values, including 0. 1471407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesenclass LiveIntervalMap { 1481407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen LiveIntervals &lis_; 1491407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen 1501407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen // The parent interval is never changed. 1511407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen const LiveInterval &parentli_; 1521407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen 1531407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen // The child interval's values are fully contained inside parentli_ values. 1549ca2aeb2d223d11fd01b0bb8f13fe7f3a969714dJakob Stoklund Olesen LiveInterval *li_; 1551407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen 1561407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen typedef DenseMap<const VNInfo*, VNInfo*> ValueMap; 1571407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen 1581407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen // Map parentli_ values to simple values in li_ that are defined at the same 1591407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen // SlotIndex, or NULL for parentli_ values that have complex li_ defs. 1601407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen // Note there is a difference between values mapping to NULL (complex), and 1611407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen // values not present (unknown/unmapped). 1621407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen ValueMap valueMap_; 1631407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen 1641407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesenpublic: 1651407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen LiveIntervalMap(LiveIntervals &lis, 1669ca2aeb2d223d11fd01b0bb8f13fe7f3a969714dJakob Stoklund Olesen const LiveInterval &parentli) 1679ca2aeb2d223d11fd01b0bb8f13fe7f3a969714dJakob Stoklund Olesen : lis_(lis), parentli_(parentli), li_(0) {} 1689ca2aeb2d223d11fd01b0bb8f13fe7f3a969714dJakob Stoklund Olesen 1699ca2aeb2d223d11fd01b0bb8f13fe7f3a969714dJakob Stoklund Olesen /// reset - clear all data structures and start a new live interval. 1709ca2aeb2d223d11fd01b0bb8f13fe7f3a969714dJakob Stoklund Olesen void reset(LiveInterval *); 1719ca2aeb2d223d11fd01b0bb8f13fe7f3a969714dJakob Stoklund Olesen 1729ca2aeb2d223d11fd01b0bb8f13fe7f3a969714dJakob Stoklund Olesen /// getLI - return the current live interval. 1739ca2aeb2d223d11fd01b0bb8f13fe7f3a969714dJakob Stoklund Olesen LiveInterval *getLI() const { return li_; } 1741407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen 1751407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen /// defValue - define a value in li_ from the parentli_ value VNI and Idx. 1761407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen /// Idx does not have to be ParentVNI->def, but it must be contained within 1771407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen /// ParentVNI's live range in parentli_. 1781407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen /// Return the new li_ value. 1791407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen VNInfo *defValue(const VNInfo *ParentVNI, SlotIndex Idx); 1801407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen 1811407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen /// mapValue - map ParentVNI to the corresponding li_ value at Idx. It is 1821407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen /// assumed that ParentVNI is live at Idx. 1831407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen /// If ParentVNI has not been defined by defValue, it is assumed that 1841407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen /// ParentVNI->def dominates Idx. 1851407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen /// If ParentVNI has been defined by defValue one or more times, a value that 1861407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen /// dominates Idx will be returned. This may require creating extra phi-def 1871407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen /// values and adding live ranges to li_. 1885fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen /// If simple is not NULL, *simple will indicate if ParentVNI is a simply 1895fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen /// mapped value. 1905fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen VNInfo *mapValue(const VNInfo *ParentVNI, SlotIndex Idx, bool *simple = 0); 1915fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen 192fc60d7729bb5b63b7d61e370e51bd05e9a18b8bcJakob Stoklund Olesen // extendTo - Find the last li_ value defined in MBB at or before Idx. The 193fc60d7729bb5b63b7d61e370e51bd05e9a18b8bcJakob Stoklund Olesen // parentli is assumed to be live at Idx. Extend the live range to include 194fc60d7729bb5b63b7d61e370e51bd05e9a18b8bcJakob Stoklund Olesen // Idx. Return the found VNInfo, or NULL. 195fc60d7729bb5b63b7d61e370e51bd05e9a18b8bcJakob Stoklund Olesen VNInfo *extendTo(MachineBasicBlock *MBB, SlotIndex Idx); 196fc60d7729bb5b63b7d61e370e51bd05e9a18b8bcJakob Stoklund Olesen 1975fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen /// isMapped - Return true is ParentVNI is a known mapped value. It may be a 1985fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen /// simple 1-1 mapping or a complex mapping to later defs. 1995fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen bool isMapped(const VNInfo *ParentVNI) const { 2005fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen return valueMap_.count(ParentVNI); 2015fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen } 2025fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen 2035fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen /// isComplexMapped - Return true if ParentVNI has received new definitions 2045fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen /// with defValue. 2055fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen bool isComplexMapped(const VNInfo *ParentVNI) const; 2065fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen 2075fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen // addSimpleRange - Add a simple range from parentli_ to li_. 2085fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen // ParentVNI must be live in the [Start;End) interval. 2095fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen void addSimpleRange(SlotIndex Start, SlotIndex End, const VNInfo *ParentVNI); 2101407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen 2111407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen /// addRange - Add live ranges to li_ where [Start;End) intersects parentli_. 2121407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen /// All needed values whose def is not inside [Start;End) must be defined 2131407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen /// beforehand so mapValue will work. 2141407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen void addRange(SlotIndex Start, SlotIndex End); 215f6a129a24b866635c3c51edf08749755f952b5f2Jakob Stoklund Olesen 216f6a129a24b866635c3c51edf08749755f952b5f2Jakob Stoklund Olesen /// defByCopyFrom - Insert a copy from Reg to li, assuming that Reg carries 217f6a129a24b866635c3c51edf08749755f952b5f2Jakob Stoklund Olesen /// ParentVNI. Add a minimal live range for the new value and return it. 218f6a129a24b866635c3c51edf08749755f952b5f2Jakob Stoklund Olesen VNInfo *defByCopyFrom(unsigned Reg, 219f6a129a24b866635c3c51edf08749755f952b5f2Jakob Stoklund Olesen const VNInfo *ParentVNI, 220f6a129a24b866635c3c51edf08749755f952b5f2Jakob Stoklund Olesen MachineBasicBlock &MBB, 221f6a129a24b866635c3c51edf08749755f952b5f2Jakob Stoklund Olesen MachineBasicBlock::iterator I); 222f6a129a24b866635c3c51edf08749755f952b5f2Jakob Stoklund Olesen 2231407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen}; 2241407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen 2251407c84242688dbcdbaa5b0296c18f46d102f25aJakob Stoklund Olesen 226f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen/// SplitEditor - Edit machine code and LiveIntervals for live range 227f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen/// splitting. 228f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen/// 2295eb308b9448ee5b14fac26c0533eac481bc28471Jakob Stoklund Olesen/// - Create a SplitEditor from a SplitAnalysis. 2307536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen/// - Start a new live interval with openIntv. 2317536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen/// - Mark the places where the new interval is entered using enterIntv* 2327536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen/// - Mark the ranges where the new interval is used with useIntv* 2337536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen/// - Mark the places where the interval is exited with exitIntv*. 2347536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen/// - Finish the current interval with closeIntv and repeat from 2. 2357536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen/// - Rewrite instructions with rewrite(). 236f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen/// 237f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesenclass SplitEditor { 238f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen SplitAnalysis &sa_; 239f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen LiveIntervals &lis_; 240f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen VirtRegMap &vrm_; 241f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen MachineRegisterInfo &mri_; 242f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen const TargetInstrInfo &tii_; 243f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 2445eb308b9448ee5b14fac26c0533eac481bc28471Jakob Stoklund Olesen /// curli_ - The immutable interval we are currently splitting. 2455eb308b9448ee5b14fac26c0533eac481bc28471Jakob Stoklund Olesen const LiveInterval *const curli_; 2465eb308b9448ee5b14fac26c0533eac481bc28471Jakob Stoklund Olesen 2475eb308b9448ee5b14fac26c0533eac481bc28471Jakob Stoklund Olesen /// dupli_ - Created as a copy of curli_, ranges are carved out as new 2485eb308b9448ee5b14fac26c0533eac481bc28471Jakob Stoklund Olesen /// intervals get added through openIntv / closeIntv. This is used to avoid 2495eb308b9448ee5b14fac26c0533eac481bc28471Jakob Stoklund Olesen /// editing curli_. 250dd9f3fdc77b77b10710c27050d508d7c7fb40c25Jakob Stoklund Olesen LiveIntervalMap dupli_; 251f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 252f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen /// Currently open LiveInterval. 253dd9f3fdc77b77b10710c27050d508d7c7fb40c25Jakob Stoklund Olesen LiveIntervalMap openli_; 254f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 255f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen /// createInterval - Create a new virtual register and LiveInterval with same 256f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen /// register class and spill slot as curli. 257f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen LiveInterval *createInterval(); 258f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 2597536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen /// All the new intervals created for this split are added to intervals_. 2600a2b2a1497a77f1db281d4dc9f21d01fe48f6ec6Jakob Stoklund Olesen SmallVectorImpl<LiveInterval*> &intervals_; 2617536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen 2627536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen /// The index into intervals_ of the first interval we added. There may be 2637536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen /// others from before we got it. 2647536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen unsigned firstInterval; 2657536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen 2665fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen /// intervalsLiveAt - Return true if any member of intervals_ is live at Idx. 2675fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen bool intervalsLiveAt(SlotIndex Idx) const; 2685fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen 2695fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen /// Values in curli whose live range has been truncated when entering an open 2705fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen /// li. 2715fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen SmallPtrSet<const VNInfo*, 8> truncatedValues; 2725fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen 2735fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen /// addTruncSimpleRange - Add the given simple range to dupli_ after 2745fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen /// truncating any overlap with intervals_. 2755fa42a45a1845046dde84089fb4d8e1e1b329b65Jakob Stoklund Olesen void addTruncSimpleRange(SlotIndex Start, SlotIndex End, VNInfo *VNI); 276f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 277f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesenpublic: 278f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen /// Create a new SplitEditor for editing the LiveInterval analyzed by SA. 2797536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen /// Newly created intervals will be appended to newIntervals. 2807536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen SplitEditor(SplitAnalysis &SA, LiveIntervals&, VirtRegMap&, 2810a2b2a1497a77f1db281d4dc9f21d01fe48f6ec6Jakob Stoklund Olesen SmallVectorImpl<LiveInterval*> &newIntervals); 282f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 2835eb308b9448ee5b14fac26c0533eac481bc28471Jakob Stoklund Olesen /// getAnalysis - Get the corresponding analysis. 2845eb308b9448ee5b14fac26c0533eac481bc28471Jakob Stoklund Olesen SplitAnalysis &getAnalysis() { return sa_; } 285f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 2867536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen /// Create a new virtual register and live interval. 2877536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen void openIntv(); 288f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 289f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen /// enterIntvBefore - Enter openli before the instruction at Idx. If curli is 290f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen /// not live before Idx, a COPY is not inserted. 291f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen void enterIntvBefore(SlotIndex Idx); 292f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen 2937536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen /// enterIntvAtEnd - Enter openli at the end of MBB. 294f6a129a24b866635c3c51edf08749755f952b5f2Jakob Stoklund Olesen void enterIntvAtEnd(MachineBasicBlock &MBB); 295f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 2967536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen /// useIntv - indicate that all instructions in MBB should use openli. 2977536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen void useIntv(const MachineBasicBlock &MBB); 298f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 2997536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen /// useIntv - indicate that all instructions in range should use openli. 3007536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen void useIntv(SlotIndex Start, SlotIndex End); 301f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 302f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen /// leaveIntvAfter - Leave openli after the instruction at Idx. 303f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen void leaveIntvAfter(SlotIndex Idx); 304f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen 3057536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen /// leaveIntvAtTop - Leave the interval at the top of MBB. 3067536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen /// Currently, only one value can leave the interval. 3077536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen void leaveIntvAtTop(MachineBasicBlock &MBB); 308f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 3097536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen /// closeIntv - Indicate that we are done editing the currently open 310f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen /// LiveInterval, and ranges can be trimmed. 3117536f72a97ad25c3652fdfe26d392fd78b6ea7b9Jakob Stoklund Olesen void closeIntv(); 312f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 313f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen /// rewrite - after all the new live ranges have been created, rewrite 314f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen /// instructions using curli to use the new intervals. 31557d0f2deb0afefe69770a28937a4363e7b1f9753Jakob Stoklund Olesen void rewrite(); 316f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 317f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen // ===--- High level methods ---=== 318f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 319f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen /// splitAroundLoop - Split curli into a separate live interval inside 32057d0f2deb0afefe69770a28937a4363e7b1f9753Jakob Stoklund Olesen /// the loop. 32157d0f2deb0afefe69770a28937a4363e7b1f9753Jakob Stoklund Olesen void splitAroundLoop(const MachineLoop*); 322f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 323f1b05f2b0ef48cb80b064e2f792b38c626822fc0Jakob Stoklund Olesen /// splitSingleBlocks - Split curli into a separate live interval inside each 32457d0f2deb0afefe69770a28937a4363e7b1f9753Jakob Stoklund Olesen /// basic block in Blocks. 32557d0f2deb0afefe69770a28937a4363e7b1f9753Jakob Stoklund Olesen void splitSingleBlocks(const SplitAnalysis::BlockPtrSet &Blocks); 32657d0f2deb0afefe69770a28937a4363e7b1f9753Jakob Stoklund Olesen 32757d0f2deb0afefe69770a28937a4363e7b1f9753Jakob Stoklund Olesen /// splitInsideBlock - Split curli into multiple intervals inside MBB. 32857d0f2deb0afefe69770a28937a4363e7b1f9753Jakob Stoklund Olesen void splitInsideBlock(const MachineBasicBlock *); 329fc412d85c46a8656361fe1e9197ea85922e2cd61Jakob Stoklund Olesen}; 3308ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen 3318ae0263471cc29c5f8278ee1ea5b678042ec6dceJakob Stoklund Olesen} 332