14dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick//===-- RegisterPressure.cpp - Dynamic Register Pressure ------------------===// 24dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick// 34dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick// The LLVM Compiler Infrastructure 44dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick// 54dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick// This file is distributed under the University of Illinois Open Source 64dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick// License. See LICENSE.TXT for details. 74dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick// 84dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick//===----------------------------------------------------------------------===// 94dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick// 104dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick// This file implements the RegisterPressure class which can be used to track 114dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick// MachineInstr level register pressure. 124dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick// 134dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick//===----------------------------------------------------------------------===// 144dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick 15d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/CodeGen/RegisterPressure.h" 164dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick#include "llvm/CodeGen/LiveInterval.h" 174dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick#include "llvm/CodeGen/LiveIntervalAnalysis.h" 184dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick#include "llvm/CodeGen/MachineRegisterInfo.h" 191525260b3e50cc578939ef41b60609689eecfdd2Andrew Trick#include "llvm/CodeGen/RegisterClassInfo.h" 205f887fab35cd71a1e6fcbfa64ae5cbbf43b39807Andrew Trick#include "llvm/Support/Debug.h" 215f887fab35cd71a1e6fcbfa64ae5cbbf43b39807Andrew Trick#include "llvm/Support/raw_ostream.h" 22d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Target/TargetMachine.h" 234dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick 244dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trickusing namespace llvm; 254dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick 26553c42cefc9abe1f10ee33d34a12498b8ac12fe6Andrew Trick/// Increase pressure for each pressure set provided by TargetRegisterInfo. 274dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trickstatic void increaseSetPressure(std::vector<unsigned> &CurrSetPressure, 28238bf5ada19ee411c1decff68e140966f7baf479Andrew Trick PSetIterator PSetI) { 29238bf5ada19ee411c1decff68e140966f7baf479Andrew Trick unsigned Weight = PSetI.getWeight(); 306abb4ab8127e270477f1028cb089c0d0fe4be927Andrew Trick for (; PSetI.isValid(); ++PSetI) 31238bf5ada19ee411c1decff68e140966f7baf479Andrew Trick CurrSetPressure[*PSetI] += Weight; 324dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick} 334dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick 34553c42cefc9abe1f10ee33d34a12498b8ac12fe6Andrew Trick/// Decrease pressure for each pressure set provided by TargetRegisterInfo. 354dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trickstatic void decreaseSetPressure(std::vector<unsigned> &CurrSetPressure, 36238bf5ada19ee411c1decff68e140966f7baf479Andrew Trick PSetIterator PSetI) { 37238bf5ada19ee411c1decff68e140966f7baf479Andrew Trick unsigned Weight = PSetI.getWeight(); 38238bf5ada19ee411c1decff68e140966f7baf479Andrew Trick for (; PSetI.isValid(); ++PSetI) { 39238bf5ada19ee411c1decff68e140966f7baf479Andrew Trick assert(CurrSetPressure[*PSetI] >= Weight && "register pressure underflow"); 40238bf5ada19ee411c1decff68e140966f7baf479Andrew Trick CurrSetPressure[*PSetI] -= Weight; 41f54f61538688eff25f392c2062b3a654394333aaAndrew Trick } 424dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick} 434dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick 44cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen HinesLLVM_DUMP_METHOD 45d71efffdcffc4204e75238f940df41fb24979a7dAndrew Trickvoid llvm::dumpRegSetPressure(ArrayRef<unsigned> SetPressure, 46d71efffdcffc4204e75238f940df41fb24979a7dAndrew Trick const TargetRegisterInfo *TRI) { 47d71efffdcffc4204e75238f940df41fb24979a7dAndrew Trick bool Empty = true; 4817cf53519905acb69c567173bedd2df1c8e45523Andrew Trick for (unsigned i = 0, e = SetPressure.size(); i < e; ++i) { 49d71efffdcffc4204e75238f940df41fb24979a7dAndrew Trick if (SetPressure[i] != 0) { 5017cf53519905acb69c567173bedd2df1c8e45523Andrew Trick dbgs() << TRI->getRegPressureSetName(i) << "=" << SetPressure[i] << '\n'; 51d71efffdcffc4204e75238f940df41fb24979a7dAndrew Trick Empty = false; 52d71efffdcffc4204e75238f940df41fb24979a7dAndrew Trick } 5317cf53519905acb69c567173bedd2df1c8e45523Andrew Trick } 54d71efffdcffc4204e75238f940df41fb24979a7dAndrew Trick if (Empty) 55d71efffdcffc4204e75238f940df41fb24979a7dAndrew Trick dbgs() << "\n"; 5617cf53519905acb69c567173bedd2df1c8e45523Andrew Trick} 5717cf53519905acb69c567173bedd2df1c8e45523Andrew Trick 58cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen HinesLLVM_DUMP_METHOD 59881a05b46c28299046bd0dc3d0b8c6677e68a4d7Andrew Trickvoid RegisterPressure::dump(const TargetRegisterInfo *TRI) const { 6017cf53519905acb69c567173bedd2df1c8e45523Andrew Trick dbgs() << "Max Pressure: "; 61d71efffdcffc4204e75238f940df41fb24979a7dAndrew Trick dumpRegSetPressure(MaxSetPressure, TRI); 625f887fab35cd71a1e6fcbfa64ae5cbbf43b39807Andrew Trick dbgs() << "Live In: "; 635f887fab35cd71a1e6fcbfa64ae5cbbf43b39807Andrew Trick for (unsigned i = 0, e = LiveInRegs.size(); i < e; ++i) 645f887fab35cd71a1e6fcbfa64ae5cbbf43b39807Andrew Trick dbgs() << PrintReg(LiveInRegs[i], TRI) << " "; 655f887fab35cd71a1e6fcbfa64ae5cbbf43b39807Andrew Trick dbgs() << '\n'; 665f887fab35cd71a1e6fcbfa64ae5cbbf43b39807Andrew Trick dbgs() << "Live Out: "; 675f887fab35cd71a1e6fcbfa64ae5cbbf43b39807Andrew Trick for (unsigned i = 0, e = LiveOutRegs.size(); i < e; ++i) 685f887fab35cd71a1e6fcbfa64ae5cbbf43b39807Andrew Trick dbgs() << PrintReg(LiveOutRegs[i], TRI) << " "; 695f887fab35cd71a1e6fcbfa64ae5cbbf43b39807Andrew Trick dbgs() << '\n'; 7017cf53519905acb69c567173bedd2df1c8e45523Andrew Trick} 7117cf53519905acb69c567173bedd2df1c8e45523Andrew Trick 72cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen HinesLLVM_DUMP_METHOD 7322af4bc07bb81c22b15d7a63fb566efcab913bd9Andrew Trickvoid RegPressureTracker::dump() const { 74d71efffdcffc4204e75238f940df41fb24979a7dAndrew Trick if (!isTopClosed() || !isBottomClosed()) { 75d71efffdcffc4204e75238f940df41fb24979a7dAndrew Trick dbgs() << "Curr Pressure: "; 76d71efffdcffc4204e75238f940df41fb24979a7dAndrew Trick dumpRegSetPressure(CurrSetPressure, TRI); 77d71efffdcffc4204e75238f940df41fb24979a7dAndrew Trick } 7817cf53519905acb69c567173bedd2df1c8e45523Andrew Trick P.dump(TRI); 795f887fab35cd71a1e6fcbfa64ae5cbbf43b39807Andrew Trick} 805f887fab35cd71a1e6fcbfa64ae5cbbf43b39807Andrew Trick 81f54f61538688eff25f392c2062b3a654394333aaAndrew Trick/// Increase the current pressure as impacted by these registers and bump 82553c42cefc9abe1f10ee33d34a12498b8ac12fe6Andrew Trick/// the high water mark if needed. 83751c6d28780e9e852f71aff63de608cff6a146ecAndrew Trickvoid RegPressureTracker::increaseRegPressure(ArrayRef<unsigned> RegUnits) { 84751c6d28780e9e852f71aff63de608cff6a146ecAndrew Trick for (unsigned i = 0, e = RegUnits.size(); i != e; ++i) { 85751c6d28780e9e852f71aff63de608cff6a146ecAndrew Trick PSetIterator PSetI = MRI->getPressureSets(RegUnits[i]); 866abb4ab8127e270477f1028cb089c0d0fe4be927Andrew Trick unsigned Weight = PSetI.getWeight(); 876abb4ab8127e270477f1028cb089c0d0fe4be927Andrew Trick for (; PSetI.isValid(); ++PSetI) { 886abb4ab8127e270477f1028cb089c0d0fe4be927Andrew Trick CurrSetPressure[*PSetI] += Weight; 896abb4ab8127e270477f1028cb089c0d0fe4be927Andrew Trick if (CurrSetPressure[*PSetI] > P.MaxSetPressure[*PSetI]) { 906abb4ab8127e270477f1028cb089c0d0fe4be927Andrew Trick P.MaxSetPressure[*PSetI] = CurrSetPressure[*PSetI]; 916abb4ab8127e270477f1028cb089c0d0fe4be927Andrew Trick } 926abb4ab8127e270477f1028cb089c0d0fe4be927Andrew Trick } 93553c42cefc9abe1f10ee33d34a12498b8ac12fe6Andrew Trick } 944dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick} 954dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick 96f54f61538688eff25f392c2062b3a654394333aaAndrew Trick/// Simply decrease the current pressure as impacted by these registers. 97751c6d28780e9e852f71aff63de608cff6a146ecAndrew Trickvoid RegPressureTracker::decreaseRegPressure(ArrayRef<unsigned> RegUnits) { 98751c6d28780e9e852f71aff63de608cff6a146ecAndrew Trick for (unsigned I = 0, E = RegUnits.size(); I != E; ++I) 99751c6d28780e9e852f71aff63de608cff6a146ecAndrew Trick decreaseSetPressure(CurrSetPressure, MRI->getPressureSets(RegUnits[I])); 1004dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick} 1014dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick 1024dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick/// Clear the result so it can be used for another round of pressure tracking. 1034dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trickvoid IntervalPressure::reset() { 1044dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick TopIdx = BottomIdx = SlotIndex(); 1054dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick MaxSetPressure.clear(); 1064dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick LiveInRegs.clear(); 1074dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick LiveOutRegs.clear(); 1084dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick} 1094dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick 1104dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick/// Clear the result so it can be used for another round of pressure tracking. 1114dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trickvoid RegionPressure::reset() { 1124dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick TopPos = BottomPos = MachineBasicBlock::const_iterator(); 1134dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick MaxSetPressure.clear(); 1144dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick LiveInRegs.clear(); 1154dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick LiveOutRegs.clear(); 1164dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick} 1174dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick 1184dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick/// If the current top is not less than or equal to the next index, open it. 1194dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick/// We happen to need the SlotIndex for the next top for pressure update. 1204dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trickvoid IntervalPressure::openTop(SlotIndex NextTop) { 1214dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick if (TopIdx <= NextTop) 1224dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick return; 1234dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick TopIdx = SlotIndex(); 1244dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick LiveInRegs.clear(); 1254dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick} 1264dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick 1274dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick/// If the current top is the previous instruction (before receding), open it. 1284dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trickvoid RegionPressure::openTop(MachineBasicBlock::const_iterator PrevTop) { 1294dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick if (TopPos != PrevTop) 1304dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick return; 1314dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick TopPos = MachineBasicBlock::const_iterator(); 1324dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick LiveInRegs.clear(); 1334dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick} 1344dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick 1354dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick/// If the current bottom is not greater than the previous index, open it. 1364dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trickvoid IntervalPressure::openBottom(SlotIndex PrevBottom) { 1374dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick if (BottomIdx > PrevBottom) 1384dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick return; 1394dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick BottomIdx = SlotIndex(); 1404dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick LiveInRegs.clear(); 1414dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick} 1424dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick 1434dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick/// If the current bottom is the previous instr (before advancing), open it. 1444dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trickvoid RegionPressure::openBottom(MachineBasicBlock::const_iterator PrevBottom) { 1454dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick if (BottomPos != PrevBottom) 1464dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick return; 1474dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick BottomPos = MachineBasicBlock::const_iterator(); 1484dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick LiveInRegs.clear(); 1494dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick} 1504dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick 1514f3b5e8c9232e43d1291aab8db5f5698d7ee0ea4Matthias Braunconst LiveRange *RegPressureTracker::getLiveRange(unsigned Reg) const { 152f54f61538688eff25f392c2062b3a654394333aaAndrew Trick if (TargetRegisterInfo::isVirtualRegister(Reg)) 153f54f61538688eff25f392c2062b3a654394333aaAndrew Trick return &LIS->getInterval(Reg); 154f54f61538688eff25f392c2062b3a654394333aaAndrew Trick return LIS->getCachedRegUnit(Reg); 155f54f61538688eff25f392c2062b3a654394333aaAndrew Trick} 156f54f61538688eff25f392c2062b3a654394333aaAndrew Trick 15742ebb3ad41813af292cfa681c1fe2aadd1008721Andrew Trickvoid RegPressureTracker::reset() { 158dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines MBB = nullptr; 159dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LIS = nullptr; 16042ebb3ad41813af292cfa681c1fe2aadd1008721Andrew Trick 16142ebb3ad41813af292cfa681c1fe2aadd1008721Andrew Trick CurrSetPressure.clear(); 16242ebb3ad41813af292cfa681c1fe2aadd1008721Andrew Trick LiveThruPressure.clear(); 16342ebb3ad41813af292cfa681c1fe2aadd1008721Andrew Trick P.MaxSetPressure.clear(); 16442ebb3ad41813af292cfa681c1fe2aadd1008721Andrew Trick 16542ebb3ad41813af292cfa681c1fe2aadd1008721Andrew Trick if (RequireIntervals) 16642ebb3ad41813af292cfa681c1fe2aadd1008721Andrew Trick static_cast<IntervalPressure&>(P).reset(); 16742ebb3ad41813af292cfa681c1fe2aadd1008721Andrew Trick else 16842ebb3ad41813af292cfa681c1fe2aadd1008721Andrew Trick static_cast<RegionPressure&>(P).reset(); 16942ebb3ad41813af292cfa681c1fe2aadd1008721Andrew Trick 17042ebb3ad41813af292cfa681c1fe2aadd1008721Andrew Trick LiveRegs.PhysRegs.clear(); 17142ebb3ad41813af292cfa681c1fe2aadd1008721Andrew Trick LiveRegs.VirtRegs.clear(); 17242ebb3ad41813af292cfa681c1fe2aadd1008721Andrew Trick UntiedDefs.clear(); 17342ebb3ad41813af292cfa681c1fe2aadd1008721Andrew Trick} 17442ebb3ad41813af292cfa681c1fe2aadd1008721Andrew Trick 1754dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick/// Setup the RegPressureTracker. 1764dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick/// 1774dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick/// TODO: Add support for pressure without LiveIntervals. 1784dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trickvoid RegPressureTracker::init(const MachineFunction *mf, 1794dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick const RegisterClassInfo *rci, 1804dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick const LiveIntervals *lis, 1814dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick const MachineBasicBlock *mbb, 182d71efffdcffc4204e75238f940df41fb24979a7dAndrew Trick MachineBasicBlock::const_iterator pos, 183d71efffdcffc4204e75238f940df41fb24979a7dAndrew Trick bool ShouldTrackUntiedDefs) 1844dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick{ 18542ebb3ad41813af292cfa681c1fe2aadd1008721Andrew Trick reset(); 18642ebb3ad41813af292cfa681c1fe2aadd1008721Andrew Trick 1874dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick MF = mf; 1884dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick TRI = MF->getTarget().getRegisterInfo(); 1894dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick RCI = rci; 1904dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick MRI = &MF->getRegInfo(); 1914dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick MBB = mbb; 192d71efffdcffc4204e75238f940df41fb24979a7dAndrew Trick TrackUntiedDefs = ShouldTrackUntiedDefs; 1934dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick 1944dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick if (RequireIntervals) { 1954dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick assert(lis && "IntervalPressure requires LiveIntervals"); 1964dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick LIS = lis; 1974dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick } 1984dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick 1994dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick CurrPos = pos; 2004dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick CurrSetPressure.assign(TRI->getNumRegPressureSets(), 0); 2014dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick 2024dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick P.MaxSetPressure = CurrSetPressure; 2034dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick 204f54f61538688eff25f392c2062b3a654394333aaAndrew Trick LiveRegs.PhysRegs.setUniverse(TRI->getNumRegs()); 205f54f61538688eff25f392c2062b3a654394333aaAndrew Trick LiveRegs.VirtRegs.setUniverse(MRI->getNumVirtRegs()); 206d71efffdcffc4204e75238f940df41fb24979a7dAndrew Trick if (TrackUntiedDefs) 207d71efffdcffc4204e75238f940df41fb24979a7dAndrew Trick UntiedDefs.setUniverse(MRI->getNumVirtRegs()); 2084dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick} 2094dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick 2104dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick/// Does this pressure result have a valid top position and live ins. 2114dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trickbool RegPressureTracker::isTopClosed() const { 2124dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick if (RequireIntervals) 2134dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick return static_cast<IntervalPressure&>(P).TopIdx.isValid(); 2144dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick return (static_cast<RegionPressure&>(P).TopPos == 2154dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick MachineBasicBlock::const_iterator()); 2164dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick} 2174dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick 2184dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick/// Does this pressure result have a valid bottom position and live outs. 2194dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trickbool RegPressureTracker::isBottomClosed() const { 2204dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick if (RequireIntervals) 2214dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick return static_cast<IntervalPressure&>(P).BottomIdx.isValid(); 2224dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick return (static_cast<RegionPressure&>(P).BottomPos == 2234dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick MachineBasicBlock::const_iterator()); 2244dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick} 2254dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick 226657b75b9946eae763725b413841dfd01ed12a051Andrew Trick 227657b75b9946eae763725b413841dfd01ed12a051Andrew TrickSlotIndex RegPressureTracker::getCurrSlot() const { 228657b75b9946eae763725b413841dfd01ed12a051Andrew Trick MachineBasicBlock::const_iterator IdxPos = CurrPos; 229657b75b9946eae763725b413841dfd01ed12a051Andrew Trick while (IdxPos != MBB->end() && IdxPos->isDebugValue()) 230657b75b9946eae763725b413841dfd01ed12a051Andrew Trick ++IdxPos; 231657b75b9946eae763725b413841dfd01ed12a051Andrew Trick if (IdxPos == MBB->end()) 232657b75b9946eae763725b413841dfd01ed12a051Andrew Trick return LIS->getMBBEndIdx(MBB); 233657b75b9946eae763725b413841dfd01ed12a051Andrew Trick return LIS->getInstructionIndex(IdxPos).getRegSlot(); 234657b75b9946eae763725b413841dfd01ed12a051Andrew Trick} 235657b75b9946eae763725b413841dfd01ed12a051Andrew Trick 2364dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick/// Set the boundary for the top of the region and summarize live ins. 2374dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trickvoid RegPressureTracker::closeTop() { 2384dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick if (RequireIntervals) 239657b75b9946eae763725b413841dfd01ed12a051Andrew Trick static_cast<IntervalPressure&>(P).TopIdx = getCurrSlot(); 2404dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick else 2414dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick static_cast<RegionPressure&>(P).TopPos = CurrPos; 2424dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick 2434dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick assert(P.LiveInRegs.empty() && "inconsistent max pressure result"); 244f54f61538688eff25f392c2062b3a654394333aaAndrew Trick P.LiveInRegs.reserve(LiveRegs.PhysRegs.size() + LiveRegs.VirtRegs.size()); 245f54f61538688eff25f392c2062b3a654394333aaAndrew Trick P.LiveInRegs.append(LiveRegs.PhysRegs.begin(), LiveRegs.PhysRegs.end()); 2464dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick for (SparseSet<unsigned>::const_iterator I = 247f54f61538688eff25f392c2062b3a654394333aaAndrew Trick LiveRegs.VirtRegs.begin(), E = LiveRegs.VirtRegs.end(); I != E; ++I) 2484dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick P.LiveInRegs.push_back(*I); 2494dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick std::sort(P.LiveInRegs.begin(), P.LiveInRegs.end()); 2504dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick P.LiveInRegs.erase(std::unique(P.LiveInRegs.begin(), P.LiveInRegs.end()), 2514dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick P.LiveInRegs.end()); 2524dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick} 2534dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick 2544dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick/// Set the boundary for the bottom of the region and summarize live outs. 2554dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trickvoid RegPressureTracker::closeBottom() { 2564dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick if (RequireIntervals) 257657b75b9946eae763725b413841dfd01ed12a051Andrew Trick static_cast<IntervalPressure&>(P).BottomIdx = getCurrSlot(); 2584dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick else 2594dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick static_cast<RegionPressure&>(P).BottomPos = CurrPos; 2604dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick 2614dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick assert(P.LiveOutRegs.empty() && "inconsistent max pressure result"); 262f54f61538688eff25f392c2062b3a654394333aaAndrew Trick P.LiveOutRegs.reserve(LiveRegs.PhysRegs.size() + LiveRegs.VirtRegs.size()); 263f54f61538688eff25f392c2062b3a654394333aaAndrew Trick P.LiveOutRegs.append(LiveRegs.PhysRegs.begin(), LiveRegs.PhysRegs.end()); 2644dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick for (SparseSet<unsigned>::const_iterator I = 265f54f61538688eff25f392c2062b3a654394333aaAndrew Trick LiveRegs.VirtRegs.begin(), E = LiveRegs.VirtRegs.end(); I != E; ++I) 2664dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick P.LiveOutRegs.push_back(*I); 2674dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick std::sort(P.LiveOutRegs.begin(), P.LiveOutRegs.end()); 2684dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick P.LiveOutRegs.erase(std::unique(P.LiveOutRegs.begin(), P.LiveOutRegs.end()), 2694dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick P.LiveOutRegs.end()); 2704dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick} 2714dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick 2724dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick/// Finalize the region boundaries and record live ins and live outs. 2734dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trickvoid RegPressureTracker::closeRegion() { 2744dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick if (!isTopClosed() && !isBottomClosed()) { 275f54f61538688eff25f392c2062b3a654394333aaAndrew Trick assert(LiveRegs.PhysRegs.empty() && LiveRegs.VirtRegs.empty() && 2764dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick "no region boundary"); 2774dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick return; 2784dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick } 2794dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick if (!isBottomClosed()) 2804dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick closeBottom(); 2814dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick else if (!isTopClosed()) 2824dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick closeTop(); 2834dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick // If both top and bottom are closed, do nothing. 2844dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick} 2854dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick 286d71efffdcffc4204e75238f940df41fb24979a7dAndrew Trick/// The register tracker is unaware of global liveness so ignores normal 287d71efffdcffc4204e75238f940df41fb24979a7dAndrew Trick/// live-thru ranges. However, two-address or coalesced chains can also lead 288d71efffdcffc4204e75238f940df41fb24979a7dAndrew Trick/// to live ranges with no holes. Count these to inform heuristics that we 289d71efffdcffc4204e75238f940df41fb24979a7dAndrew Trick/// can never drop below this pressure. 290d71efffdcffc4204e75238f940df41fb24979a7dAndrew Trickvoid RegPressureTracker::initLiveThru(const RegPressureTracker &RPTracker) { 291d71efffdcffc4204e75238f940df41fb24979a7dAndrew Trick LiveThruPressure.assign(TRI->getNumRegPressureSets(), 0); 292d71efffdcffc4204e75238f940df41fb24979a7dAndrew Trick assert(isBottomClosed() && "need bottom-up tracking to intialize."); 293d71efffdcffc4204e75238f940df41fb24979a7dAndrew Trick for (unsigned i = 0, e = P.LiveOutRegs.size(); i < e; ++i) { 294d71efffdcffc4204e75238f940df41fb24979a7dAndrew Trick unsigned Reg = P.LiveOutRegs[i]; 295d71efffdcffc4204e75238f940df41fb24979a7dAndrew Trick if (TargetRegisterInfo::isVirtualRegister(Reg) 296d71efffdcffc4204e75238f940df41fb24979a7dAndrew Trick && !RPTracker.hasUntiedDef(Reg)) { 2976abb4ab8127e270477f1028cb089c0d0fe4be927Andrew Trick increaseSetPressure(LiveThruPressure, MRI->getPressureSets(Reg)); 298d71efffdcffc4204e75238f940df41fb24979a7dAndrew Trick } 299d71efffdcffc4204e75238f940df41fb24979a7dAndrew Trick } 300d71efffdcffc4204e75238f940df41fb24979a7dAndrew Trick} 301d71efffdcffc4204e75238f940df41fb24979a7dAndrew Trick 302553c42cefc9abe1f10ee33d34a12498b8ac12fe6Andrew Trick/// \brief Convenient wrapper for checking membership in RegisterOperands. 303751c6d28780e9e852f71aff63de608cff6a146ecAndrew Trick/// (std::count() doesn't have an early exit). 304751c6d28780e9e852f71aff63de608cff6a146ecAndrew Trickstatic bool containsReg(ArrayRef<unsigned> RegUnits, unsigned RegUnit) { 305751c6d28780e9e852f71aff63de608cff6a146ecAndrew Trick return std::find(RegUnits.begin(), RegUnits.end(), RegUnit) != RegUnits.end(); 3064dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick} 3074dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick 3084dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick/// Collect this instruction's unique uses and defs into SmallVectors for 3094dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick/// processing defs and uses in order. 3104c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick/// 3114c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick/// FIXME: always ignore tied opers 312553c42cefc9abe1f10ee33d34a12498b8ac12fe6Andrew Trickclass RegisterOperands { 313f54f61538688eff25f392c2062b3a654394333aaAndrew Trick const TargetRegisterInfo *TRI; 314f54f61538688eff25f392c2062b3a654394333aaAndrew Trick const MachineRegisterInfo *MRI; 3154c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick bool IgnoreDead; 316f54f61538688eff25f392c2062b3a654394333aaAndrew Trick 317553c42cefc9abe1f10ee33d34a12498b8ac12fe6Andrew Trickpublic: 3184dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick SmallVector<unsigned, 8> Uses; 3194dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick SmallVector<unsigned, 8> Defs; 3204dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick SmallVector<unsigned, 8> DeadDefs; 3214dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick 322f54f61538688eff25f392c2062b3a654394333aaAndrew Trick RegisterOperands(const TargetRegisterInfo *tri, 3234c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick const MachineRegisterInfo *mri, bool ID = false): 3244c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick TRI(tri), MRI(mri), IgnoreDead(ID) {} 325f54f61538688eff25f392c2062b3a654394333aaAndrew Trick 3264dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick /// Push this operand's register onto the correct vector. 327f54f61538688eff25f392c2062b3a654394333aaAndrew Trick void collect(const MachineOperand &MO) { 328f54f61538688eff25f392c2062b3a654394333aaAndrew Trick if (!MO.isReg() || !MO.getReg()) 329f54f61538688eff25f392c2062b3a654394333aaAndrew Trick return; 330553c42cefc9abe1f10ee33d34a12498b8ac12fe6Andrew Trick if (MO.readsReg()) 331f54f61538688eff25f392c2062b3a654394333aaAndrew Trick pushRegUnits(MO.getReg(), Uses); 3324dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick if (MO.isDef()) { 3334c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick if (MO.isDead()) { 3344c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick if (!IgnoreDead) 3354c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick pushRegUnits(MO.getReg(), DeadDefs); 3364c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick } 337553c42cefc9abe1f10ee33d34a12498b8ac12fe6Andrew Trick else 338f54f61538688eff25f392c2062b3a654394333aaAndrew Trick pushRegUnits(MO.getReg(), Defs); 339553c42cefc9abe1f10ee33d34a12498b8ac12fe6Andrew Trick } 340553c42cefc9abe1f10ee33d34a12498b8ac12fe6Andrew Trick } 341553c42cefc9abe1f10ee33d34a12498b8ac12fe6Andrew Trick 342553c42cefc9abe1f10ee33d34a12498b8ac12fe6Andrew Trickprotected: 343751c6d28780e9e852f71aff63de608cff6a146ecAndrew Trick void pushRegUnits(unsigned Reg, SmallVectorImpl<unsigned> &RegUnits) { 344f54f61538688eff25f392c2062b3a654394333aaAndrew Trick if (TargetRegisterInfo::isVirtualRegister(Reg)) { 345751c6d28780e9e852f71aff63de608cff6a146ecAndrew Trick if (containsReg(RegUnits, Reg)) 346553c42cefc9abe1f10ee33d34a12498b8ac12fe6Andrew Trick return; 347751c6d28780e9e852f71aff63de608cff6a146ecAndrew Trick RegUnits.push_back(Reg); 348553c42cefc9abe1f10ee33d34a12498b8ac12fe6Andrew Trick } 349f54f61538688eff25f392c2062b3a654394333aaAndrew Trick else if (MRI->isAllocatable(Reg)) { 350553c42cefc9abe1f10ee33d34a12498b8ac12fe6Andrew Trick for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units) { 351751c6d28780e9e852f71aff63de608cff6a146ecAndrew Trick if (containsReg(RegUnits, *Units)) 352553c42cefc9abe1f10ee33d34a12498b8ac12fe6Andrew Trick continue; 353751c6d28780e9e852f71aff63de608cff6a146ecAndrew Trick RegUnits.push_back(*Units); 3544dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick } 3554dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick } 3564dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick } 3574dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick}; 3584dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick 3594dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick/// Collect physical and virtual register operands. 3604dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trickstatic void collectOperands(const MachineInstr *MI, 361f54f61538688eff25f392c2062b3a654394333aaAndrew Trick RegisterOperands &RegOpers) { 362eb4774a972af4bdd36d8795625c8c5d96ca507d1Benjamin Kramer for (ConstMIBundleOperands OperI(MI); OperI.isValid(); ++OperI) 363f54f61538688eff25f392c2062b3a654394333aaAndrew Trick RegOpers.collect(*OperI); 3644dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick 3654dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick // Remove redundant physreg dead defs. 366eb4774a972af4bdd36d8795625c8c5d96ca507d1Benjamin Kramer SmallVectorImpl<unsigned>::iterator I = 367eb4774a972af4bdd36d8795625c8c5d96ca507d1Benjamin Kramer std::remove_if(RegOpers.DeadDefs.begin(), RegOpers.DeadDefs.end(), 368eb4774a972af4bdd36d8795625c8c5d96ca507d1Benjamin Kramer std::bind1st(std::ptr_fun(containsReg), RegOpers.Defs)); 369eb4774a972af4bdd36d8795625c8c5d96ca507d1Benjamin Kramer RegOpers.DeadDefs.erase(I, RegOpers.DeadDefs.end()); 3704dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick} 3714dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick 3724c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick/// Initialize an array of N PressureDiffs. 3734c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trickvoid PressureDiffs::init(unsigned N) { 3744c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick Size = N; 3754c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick if (N <= Max) { 3764c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick memset(PDiffArray, 0, N * sizeof(PressureDiff)); 3774c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick return; 3784c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick } 3794c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick Max = Size; 3804c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick free(PDiffArray); 3814c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick PDiffArray = reinterpret_cast<PressureDiff*>(calloc(N, sizeof(PressureDiff))); 3824c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick} 3834c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick 3844c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick/// Add a change in pressure to the pressure diff of a given instruction. 3854c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trickvoid PressureDiff::addPressureChange(unsigned RegUnit, bool IsDec, 3864c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick const MachineRegisterInfo *MRI) { 3874c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick PSetIterator PSetI = MRI->getPressureSets(RegUnit); 3884c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick int Weight = IsDec ? -PSetI.getWeight() : PSetI.getWeight(); 3894c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick for (; PSetI.isValid(); ++PSetI) { 3904c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick // Find an existing entry in the pressure diff for this PSet. 3914c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick PressureDiff::iterator I = begin(), E = end(); 3924c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick for (; I != E && I->isValid(); ++I) { 3934c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick if (I->getPSet() >= *PSetI) 3944c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick break; 3954c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick } 3964c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick // If all pressure sets are more constrained, skip the remaining PSets. 3974c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick if (I == E) 3984c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick break; 3994c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick // Insert this PressureChange. 4004c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick if (!I->isValid() || I->getPSet() != *PSetI) { 4014c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick PressureChange PTmp = PressureChange(*PSetI); 4024c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick for (PressureDiff::iterator J = I; J != E && PTmp.isValid(); ++J) 4034c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick std::swap(*J,PTmp); 4044c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick } 4054c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick // Update the units for this pressure set. 4064c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick I->setUnitInc(I->getUnitInc() + Weight); 4074c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick } 4084c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick} 4094c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick 4104c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick/// Record the pressure difference induced by the given operand list. 4114c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trickstatic void collectPDiff(PressureDiff &PDiff, RegisterOperands &RegOpers, 4124c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick const MachineRegisterInfo *MRI) { 4134c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick assert(!PDiff.begin()->isValid() && "stale PDiff"); 4144c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick 415663bd9922776e5f7bc17dfc574efe3fe05ceb12cAndrew Trick for (unsigned i = 0, e = RegOpers.Defs.size(); i != e; ++i) 416663bd9922776e5f7bc17dfc574efe3fe05ceb12cAndrew Trick PDiff.addPressureChange(RegOpers.Defs[i], true, MRI); 417663bd9922776e5f7bc17dfc574efe3fe05ceb12cAndrew Trick 4184c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick for (unsigned i = 0, e = RegOpers.Uses.size(); i != e; ++i) 4194c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick PDiff.addPressureChange(RegOpers.Uses[i], false, MRI); 4204c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick} 4214c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick 4227f8ab785af09e4d6e4db07157a5b5aa449b5c3aeAndrew Trick/// Force liveness of registers. 4237f8ab785af09e4d6e4db07157a5b5aa449b5c3aeAndrew Trickvoid RegPressureTracker::addLiveRegs(ArrayRef<unsigned> Regs) { 4247f8ab785af09e4d6e4db07157a5b5aa449b5c3aeAndrew Trick for (unsigned i = 0, e = Regs.size(); i != e; ++i) { 425f54f61538688eff25f392c2062b3a654394333aaAndrew Trick if (LiveRegs.insert(Regs[i])) 426f54f61538688eff25f392c2062b3a654394333aaAndrew Trick increaseRegPressure(Regs[i]); 4277f8ab785af09e4d6e4db07157a5b5aa449b5c3aeAndrew Trick } 4287f8ab785af09e4d6e4db07157a5b5aa449b5c3aeAndrew Trick} 4297f8ab785af09e4d6e4db07157a5b5aa449b5c3aeAndrew Trick 430f54f61538688eff25f392c2062b3a654394333aaAndrew Trick/// Add Reg to the live in set and increase max pressure. 431f54f61538688eff25f392c2062b3a654394333aaAndrew Trickvoid RegPressureTracker::discoverLiveIn(unsigned Reg) { 432f54f61538688eff25f392c2062b3a654394333aaAndrew Trick assert(!LiveRegs.contains(Reg) && "avoid bumping max pressure twice"); 433553c42cefc9abe1f10ee33d34a12498b8ac12fe6Andrew Trick if (containsReg(P.LiveInRegs, Reg)) 4344dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick return; 4354dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick 4364dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick // At live in discovery, unconditionally increase the high water mark. 4374dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick P.LiveInRegs.push_back(Reg); 4386abb4ab8127e270477f1028cb089c0d0fe4be927Andrew Trick increaseSetPressure(P.MaxSetPressure, MRI->getPressureSets(Reg)); 4394dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick} 4404dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick 441f54f61538688eff25f392c2062b3a654394333aaAndrew Trick/// Add Reg to the live out set and increase max pressure. 442f54f61538688eff25f392c2062b3a654394333aaAndrew Trickvoid RegPressureTracker::discoverLiveOut(unsigned Reg) { 443f54f61538688eff25f392c2062b3a654394333aaAndrew Trick assert(!LiveRegs.contains(Reg) && "avoid bumping max pressure twice"); 444553c42cefc9abe1f10ee33d34a12498b8ac12fe6Andrew Trick if (containsReg(P.LiveOutRegs, Reg)) 4454dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick return; 4464dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick 4474dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick // At live out discovery, unconditionally increase the high water mark. 4484dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick P.LiveOutRegs.push_back(Reg); 4496abb4ab8127e270477f1028cb089c0d0fe4be927Andrew Trick increaseSetPressure(P.MaxSetPressure, MRI->getPressureSets(Reg)); 4504dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick} 4514dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick 452663bd9922776e5f7bc17dfc574efe3fe05ceb12cAndrew Trick/// Recede across the previous instruction. If LiveUses is provided, record any 453663bd9922776e5f7bc17dfc574efe3fe05ceb12cAndrew Trick/// RegUnits that are made live by the current instruction's uses. This includes 454663bd9922776e5f7bc17dfc574efe3fe05ceb12cAndrew Trick/// registers that are both defined and used by the instruction. If a pressure 455663bd9922776e5f7bc17dfc574efe3fe05ceb12cAndrew Trick/// difference pointer is provided record the changes is pressure caused by this 456663bd9922776e5f7bc17dfc574efe3fe05ceb12cAndrew Trick/// instruction independent of liveness. 457663bd9922776e5f7bc17dfc574efe3fe05ceb12cAndrew Trickbool RegPressureTracker::recede(SmallVectorImpl<unsigned> *LiveUses, 458663bd9922776e5f7bc17dfc574efe3fe05ceb12cAndrew Trick PressureDiff *PDiff) { 4594dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick // Check for the top of the analyzable region. 4604dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick if (CurrPos == MBB->begin()) { 4614dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick closeRegion(); 4624dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick return false; 4634dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick } 4644dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick if (!isBottomClosed()) 4654dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick closeBottom(); 4664dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick 4674dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick // Open the top of the region using block iterators. 4684dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick if (!RequireIntervals && isTopClosed()) 4694dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick static_cast<RegionPressure&>(P).openTop(CurrPos); 4704dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick 4714dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick // Find the previous instruction. 4722b8d0501b169c3ee81a9af1cb715e1be4d6a079eBenjamin Kramer do 4732b8d0501b169c3ee81a9af1cb715e1be4d6a079eBenjamin Kramer --CurrPos; 4742b8d0501b169c3ee81a9af1cb715e1be4d6a079eBenjamin Kramer while (CurrPos != MBB->begin() && CurrPos->isDebugValue()); 4754dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick 4764dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick if (CurrPos->isDebugValue()) { 4774dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick closeRegion(); 4784dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick return false; 4794dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick } 4804dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick SlotIndex SlotIdx; 4814dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick if (RequireIntervals) 4824dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick SlotIdx = LIS->getInstructionIndex(CurrPos).getRegSlot(); 4834dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick 4844dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick // Open the top of the region using slot indexes. 4854dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick if (RequireIntervals && isTopClosed()) 4864dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick static_cast<IntervalPressure&>(P).openTop(SlotIdx); 4874dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick 488f54f61538688eff25f392c2062b3a654394333aaAndrew Trick RegisterOperands RegOpers(TRI, MRI); 489f54f61538688eff25f392c2062b3a654394333aaAndrew Trick collectOperands(CurrPos, RegOpers); 4904dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick 4914c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick if (PDiff) 4924c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick collectPDiff(*PDiff, RegOpers, MRI); 4934c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick 4944dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick // Boost pressure for all dead defs together. 495f54f61538688eff25f392c2062b3a654394333aaAndrew Trick increaseRegPressure(RegOpers.DeadDefs); 496f54f61538688eff25f392c2062b3a654394333aaAndrew Trick decreaseRegPressure(RegOpers.DeadDefs); 4974dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick 4984dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick // Kill liveness at live defs. 4994dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick // TODO: consider earlyclobbers? 500f54f61538688eff25f392c2062b3a654394333aaAndrew Trick for (unsigned i = 0, e = RegOpers.Defs.size(); i < e; ++i) { 501f54f61538688eff25f392c2062b3a654394333aaAndrew Trick unsigned Reg = RegOpers.Defs[i]; 502d900b1179535298510490030a5d2ecce93f79eb0Pedro Artigas bool DeadDef = false; 503d900b1179535298510490030a5d2ecce93f79eb0Pedro Artigas if (RequireIntervals) { 504d900b1179535298510490030a5d2ecce93f79eb0Pedro Artigas const LiveRange *LR = getLiveRange(Reg); 505d900b1179535298510490030a5d2ecce93f79eb0Pedro Artigas if (LR) { 506d900b1179535298510490030a5d2ecce93f79eb0Pedro Artigas LiveQueryResult LRQ = LR->Query(SlotIdx); 507d900b1179535298510490030a5d2ecce93f79eb0Pedro Artigas DeadDef = LRQ.isDeadDef(); 508d900b1179535298510490030a5d2ecce93f79eb0Pedro Artigas } 509d900b1179535298510490030a5d2ecce93f79eb0Pedro Artigas } 51036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (DeadDef) { 51136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // LiveIntervals knows this is a dead even though it's MachineOperand is 51236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // not flagged as such. Since this register will not be recorded as 51336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // live-out, increase its PDiff value to avoid underflowing pressure. 51436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (PDiff) 51536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines PDiff->addPressureChange(Reg, false, MRI); 51636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } else { 517d900b1179535298510490030a5d2ecce93f79eb0Pedro Artigas if (LiveRegs.erase(Reg)) 518d900b1179535298510490030a5d2ecce93f79eb0Pedro Artigas decreaseRegPressure(Reg); 519d900b1179535298510490030a5d2ecce93f79eb0Pedro Artigas else 520d900b1179535298510490030a5d2ecce93f79eb0Pedro Artigas discoverLiveOut(Reg); 521d900b1179535298510490030a5d2ecce93f79eb0Pedro Artigas } 5224dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick } 5234dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick 5244dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick // Generate liveness for uses. 525f54f61538688eff25f392c2062b3a654394333aaAndrew Trick for (unsigned i = 0, e = RegOpers.Uses.size(); i < e; ++i) { 526f54f61538688eff25f392c2062b3a654394333aaAndrew Trick unsigned Reg = RegOpers.Uses[i]; 527f54f61538688eff25f392c2062b3a654394333aaAndrew Trick if (!LiveRegs.contains(Reg)) { 5284dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick // Adjust liveouts if LiveIntervals are available. 5294dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick if (RequireIntervals) { 5304f3b5e8c9232e43d1291aab8db5f5698d7ee0ea4Matthias Braun const LiveRange *LR = getLiveRange(Reg); 5314f3b5e8c9232e43d1291aab8db5f5698d7ee0ea4Matthias Braun if (LR) { 5324f3b5e8c9232e43d1291aab8db5f5698d7ee0ea4Matthias Braun LiveQueryResult LRQ = LR->Query(SlotIdx); 533846b31d74aa673a178f57f9d47f366d8ddb756d3Andrew Trick if (!LRQ.isKill() && !LRQ.valueDefined()) 534663bd9922776e5f7bc17dfc574efe3fe05ceb12cAndrew Trick discoverLiveOut(Reg); 535663bd9922776e5f7bc17dfc574efe3fe05ceb12cAndrew Trick } 5364dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick } 537f54f61538688eff25f392c2062b3a654394333aaAndrew Trick increaseRegPressure(Reg); 538f54f61538688eff25f392c2062b3a654394333aaAndrew Trick LiveRegs.insert(Reg); 539663bd9922776e5f7bc17dfc574efe3fe05ceb12cAndrew Trick if (LiveUses && !containsReg(*LiveUses, Reg)) 540663bd9922776e5f7bc17dfc574efe3fe05ceb12cAndrew Trick LiveUses->push_back(Reg); 5414dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick } 5424dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick } 543d71efffdcffc4204e75238f940df41fb24979a7dAndrew Trick if (TrackUntiedDefs) { 544d71efffdcffc4204e75238f940df41fb24979a7dAndrew Trick for (unsigned i = 0, e = RegOpers.Defs.size(); i < e; ++i) { 545d71efffdcffc4204e75238f940df41fb24979a7dAndrew Trick unsigned Reg = RegOpers.Defs[i]; 546d71efffdcffc4204e75238f940df41fb24979a7dAndrew Trick if (TargetRegisterInfo::isVirtualRegister(Reg) && !LiveRegs.contains(Reg)) 547d71efffdcffc4204e75238f940df41fb24979a7dAndrew Trick UntiedDefs.insert(Reg); 548d71efffdcffc4204e75238f940df41fb24979a7dAndrew Trick } 549d71efffdcffc4204e75238f940df41fb24979a7dAndrew Trick } 5504dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick return true; 5514dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick} 5524dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick 5534dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick/// Advance across the current instruction. 5544dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trickbool RegPressureTracker::advance() { 555d71efffdcffc4204e75238f940df41fb24979a7dAndrew Trick assert(!TrackUntiedDefs && "unsupported mode"); 556d71efffdcffc4204e75238f940df41fb24979a7dAndrew Trick 5574dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick // Check for the bottom of the analyzable region. 5584dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick if (CurrPos == MBB->end()) { 5594dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick closeRegion(); 5604dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick return false; 5614dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick } 5624dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick if (!isTopClosed()) 5634dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick closeTop(); 5644dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick 5654dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick SlotIndex SlotIdx; 5664dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick if (RequireIntervals) 567657b75b9946eae763725b413841dfd01ed12a051Andrew Trick SlotIdx = getCurrSlot(); 5684dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick 5694dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick // Open the bottom of the region using slot indexes. 5704dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick if (isBottomClosed()) { 5714dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick if (RequireIntervals) 5724dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick static_cast<IntervalPressure&>(P).openBottom(SlotIdx); 5734dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick else 5744dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick static_cast<RegionPressure&>(P).openBottom(CurrPos); 5754dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick } 5764dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick 577f54f61538688eff25f392c2062b3a654394333aaAndrew Trick RegisterOperands RegOpers(TRI, MRI); 578f54f61538688eff25f392c2062b3a654394333aaAndrew Trick collectOperands(CurrPos, RegOpers); 5794dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick 580f54f61538688eff25f392c2062b3a654394333aaAndrew Trick for (unsigned i = 0, e = RegOpers.Uses.size(); i < e; ++i) { 581f54f61538688eff25f392c2062b3a654394333aaAndrew Trick unsigned Reg = RegOpers.Uses[i]; 582f54f61538688eff25f392c2062b3a654394333aaAndrew Trick // Discover live-ins. 583f54f61538688eff25f392c2062b3a654394333aaAndrew Trick bool isLive = LiveRegs.contains(Reg); 584f54f61538688eff25f392c2062b3a654394333aaAndrew Trick if (!isLive) 585f54f61538688eff25f392c2062b3a654394333aaAndrew Trick discoverLiveIn(Reg); 586f54f61538688eff25f392c2062b3a654394333aaAndrew Trick // Kill liveness at last uses. 587f54f61538688eff25f392c2062b3a654394333aaAndrew Trick bool lastUse = false; 5884dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick if (RequireIntervals) { 5894f3b5e8c9232e43d1291aab8db5f5698d7ee0ea4Matthias Braun const LiveRange *LR = getLiveRange(Reg); 5904f3b5e8c9232e43d1291aab8db5f5698d7ee0ea4Matthias Braun lastUse = LR && LR->Query(SlotIdx).isKill(); 5914dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick } 592f54f61538688eff25f392c2062b3a654394333aaAndrew Trick else { 593f54f61538688eff25f392c2062b3a654394333aaAndrew Trick // Allocatable physregs are always single-use before register rewriting. 594f54f61538688eff25f392c2062b3a654394333aaAndrew Trick lastUse = !TargetRegisterInfo::isVirtualRegister(Reg); 5954dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick } 596f54f61538688eff25f392c2062b3a654394333aaAndrew Trick if (lastUse && isLive) { 597f54f61538688eff25f392c2062b3a654394333aaAndrew Trick LiveRegs.erase(Reg); 598f54f61538688eff25f392c2062b3a654394333aaAndrew Trick decreaseRegPressure(Reg); 599f54f61538688eff25f392c2062b3a654394333aaAndrew Trick } 600f54f61538688eff25f392c2062b3a654394333aaAndrew Trick else if (!lastUse && !isLive) 601f54f61538688eff25f392c2062b3a654394333aaAndrew Trick increaseRegPressure(Reg); 6024dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick } 6034dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick 6044dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick // Generate liveness for defs. 605f54f61538688eff25f392c2062b3a654394333aaAndrew Trick for (unsigned i = 0, e = RegOpers.Defs.size(); i < e; ++i) { 606f54f61538688eff25f392c2062b3a654394333aaAndrew Trick unsigned Reg = RegOpers.Defs[i]; 607f54f61538688eff25f392c2062b3a654394333aaAndrew Trick if (LiveRegs.insert(Reg)) 608f54f61538688eff25f392c2062b3a654394333aaAndrew Trick increaseRegPressure(Reg); 6094dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick } 6104dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick 6114dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick // Boost pressure for all dead defs together. 612f54f61538688eff25f392c2062b3a654394333aaAndrew Trick increaseRegPressure(RegOpers.DeadDefs); 613f54f61538688eff25f392c2062b3a654394333aaAndrew Trick decreaseRegPressure(RegOpers.DeadDefs); 6144dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick 6154dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick // Find the next instruction. 6162b8d0501b169c3ee81a9af1cb715e1be4d6a079eBenjamin Kramer do 6172b8d0501b169c3ee81a9af1cb715e1be4d6a079eBenjamin Kramer ++CurrPos; 6182b8d0501b169c3ee81a9af1cb715e1be4d6a079eBenjamin Kramer while (CurrPos != MBB->end() && CurrPos->isDebugValue()); 6194dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick return true; 6204dfeef100d940a0c1ca22055dcb29b02a4848f65Andrew Trick} 62155ba5dff3c1a723adf302f1124aafde797dbf31aAndrew Trick 62273a0d8ecf838a9b333c9865d2a4b72c5768fb49fAndrew Trick/// Find the max change in excess pressure across all sets. 62373a0d8ecf838a9b333c9865d2a4b72c5768fb49fAndrew Trickstatic void computeExcessPressureDelta(ArrayRef<unsigned> OldPressureVec, 62473a0d8ecf838a9b333c9865d2a4b72c5768fb49fAndrew Trick ArrayRef<unsigned> NewPressureVec, 62573a0d8ecf838a9b333c9865d2a4b72c5768fb49fAndrew Trick RegPressureDelta &Delta, 626d71efffdcffc4204e75238f940df41fb24979a7dAndrew Trick const RegisterClassInfo *RCI, 627d71efffdcffc4204e75238f940df41fb24979a7dAndrew Trick ArrayRef<unsigned> LiveThruPressureVec) { 6284c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick Delta.Excess = PressureChange(); 62955ba5dff3c1a723adf302f1124aafde797dbf31aAndrew Trick for (unsigned i = 0, e = OldPressureVec.size(); i < e; ++i) { 63055ba5dff3c1a723adf302f1124aafde797dbf31aAndrew Trick unsigned POld = OldPressureVec[i]; 63155ba5dff3c1a723adf302f1124aafde797dbf31aAndrew Trick unsigned PNew = NewPressureVec[i]; 63255ba5dff3c1a723adf302f1124aafde797dbf31aAndrew Trick int PDiff = (int)PNew - (int)POld; 63355ba5dff3c1a723adf302f1124aafde797dbf31aAndrew Trick if (!PDiff) // No change in this set in the common case. 63455ba5dff3c1a723adf302f1124aafde797dbf31aAndrew Trick continue; 63555ba5dff3c1a723adf302f1124aafde797dbf31aAndrew Trick // Only consider change beyond the limit. 6361f8b48ab3262bd5623ecbda7b0c024884e8169d3Andrew Trick unsigned Limit = RCI->getRegPressureSetLimit(i); 637d71efffdcffc4204e75238f940df41fb24979a7dAndrew Trick if (!LiveThruPressureVec.empty()) 638d71efffdcffc4204e75238f940df41fb24979a7dAndrew Trick Limit += LiveThruPressureVec[i]; 639d71efffdcffc4204e75238f940df41fb24979a7dAndrew Trick 64055ba5dff3c1a723adf302f1124aafde797dbf31aAndrew Trick if (Limit > POld) { 64155ba5dff3c1a723adf302f1124aafde797dbf31aAndrew Trick if (Limit > PNew) 64224617213ba8e9d1e0f10af33d88285a92304ab95Andrew Trick PDiff = 0; // Under the limit 64355ba5dff3c1a723adf302f1124aafde797dbf31aAndrew Trick else 64455ba5dff3c1a723adf302f1124aafde797dbf31aAndrew Trick PDiff = PNew - Limit; // Just exceeded limit. 64555ba5dff3c1a723adf302f1124aafde797dbf31aAndrew Trick } 64655ba5dff3c1a723adf302f1124aafde797dbf31aAndrew Trick else if (Limit > PNew) 64724617213ba8e9d1e0f10af33d88285a92304ab95Andrew Trick PDiff = Limit - POld; // Just obeyed limit. 64855ba5dff3c1a723adf302f1124aafde797dbf31aAndrew Trick 6494b43ed53b6b4aec95d7c7003e70cb74ac58886e7Andrew Trick if (PDiff) { 6504c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick Delta.Excess = PressureChange(i); 6514c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick Delta.Excess.setUnitInc(PDiff); 6524b43ed53b6b4aec95d7c7003e70cb74ac58886e7Andrew Trick break; 65355ba5dff3c1a723adf302f1124aafde797dbf31aAndrew Trick } 65455ba5dff3c1a723adf302f1124aafde797dbf31aAndrew Trick } 65573a0d8ecf838a9b333c9865d2a4b72c5768fb49fAndrew Trick} 65673a0d8ecf838a9b333c9865d2a4b72c5768fb49fAndrew Trick 65773a0d8ecf838a9b333c9865d2a4b72c5768fb49fAndrew Trick/// Find the max change in max pressure that either surpasses a critical PSet 65873a0d8ecf838a9b333c9865d2a4b72c5768fb49fAndrew Trick/// limit or exceeds the current MaxPressureLimit. 65973a0d8ecf838a9b333c9865d2a4b72c5768fb49fAndrew Trick/// 66073a0d8ecf838a9b333c9865d2a4b72c5768fb49fAndrew Trick/// FIXME: comparing each element of the old and new MaxPressure vectors here is 66173a0d8ecf838a9b333c9865d2a4b72c5768fb49fAndrew Trick/// silly. It's done now to demonstrate the concept but will go away with a 66273a0d8ecf838a9b333c9865d2a4b72c5768fb49fAndrew Trick/// RegPressureTracker API change to work with pressure differences. 66373a0d8ecf838a9b333c9865d2a4b72c5768fb49fAndrew Trickstatic void computeMaxPressureDelta(ArrayRef<unsigned> OldMaxPressureVec, 66473a0d8ecf838a9b333c9865d2a4b72c5768fb49fAndrew Trick ArrayRef<unsigned> NewMaxPressureVec, 6654c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick ArrayRef<PressureChange> CriticalPSets, 66673a0d8ecf838a9b333c9865d2a4b72c5768fb49fAndrew Trick ArrayRef<unsigned> MaxPressureLimit, 66773a0d8ecf838a9b333c9865d2a4b72c5768fb49fAndrew Trick RegPressureDelta &Delta) { 6684c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick Delta.CriticalMax = PressureChange(); 6694c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick Delta.CurrentMax = PressureChange(); 67073a0d8ecf838a9b333c9865d2a4b72c5768fb49fAndrew Trick 67173a0d8ecf838a9b333c9865d2a4b72c5768fb49fAndrew Trick unsigned CritIdx = 0, CritEnd = CriticalPSets.size(); 67273a0d8ecf838a9b333c9865d2a4b72c5768fb49fAndrew Trick for (unsigned i = 0, e = OldMaxPressureVec.size(); i < e; ++i) { 67373a0d8ecf838a9b333c9865d2a4b72c5768fb49fAndrew Trick unsigned POld = OldMaxPressureVec[i]; 67473a0d8ecf838a9b333c9865d2a4b72c5768fb49fAndrew Trick unsigned PNew = NewMaxPressureVec[i]; 67573a0d8ecf838a9b333c9865d2a4b72c5768fb49fAndrew Trick if (PNew == POld) // No change in this set in the common case. 67673a0d8ecf838a9b333c9865d2a4b72c5768fb49fAndrew Trick continue; 67773a0d8ecf838a9b333c9865d2a4b72c5768fb49fAndrew Trick 6784b43ed53b6b4aec95d7c7003e70cb74ac58886e7Andrew Trick if (!Delta.CriticalMax.isValid()) { 6794c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick while (CritIdx != CritEnd && CriticalPSets[CritIdx].getPSet() < i) 6804b43ed53b6b4aec95d7c7003e70cb74ac58886e7Andrew Trick ++CritIdx; 68173a0d8ecf838a9b333c9865d2a4b72c5768fb49fAndrew Trick 6824c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick if (CritIdx != CritEnd && CriticalPSets[CritIdx].getPSet() == i) { 6834c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick int PDiff = (int)PNew - (int)CriticalPSets[CritIdx].getUnitInc(); 6844b43ed53b6b4aec95d7c7003e70cb74ac58886e7Andrew Trick if (PDiff > 0) { 6854c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick Delta.CriticalMax = PressureChange(i); 6864c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick Delta.CriticalMax.setUnitInc(PDiff); 6874b43ed53b6b4aec95d7c7003e70cb74ac58886e7Andrew Trick } 68873a0d8ecf838a9b333c9865d2a4b72c5768fb49fAndrew Trick } 68973a0d8ecf838a9b333c9865d2a4b72c5768fb49fAndrew Trick } 6904b43ed53b6b4aec95d7c7003e70cb74ac58886e7Andrew Trick // Find the first increase above MaxPressureLimit. 69173a0d8ecf838a9b333c9865d2a4b72c5768fb49fAndrew Trick // (Ignores negative MDiff). 6924c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick if (!Delta.CurrentMax.isValid() && PNew > MaxPressureLimit[i]) { 6934c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick Delta.CurrentMax = PressureChange(i); 6944c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick Delta.CurrentMax.setUnitInc(PNew - POld); 6954c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick if (CritIdx == CritEnd || Delta.CriticalMax.isValid()) 6964c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick break; 69773a0d8ecf838a9b333c9865d2a4b72c5768fb49fAndrew Trick } 69873a0d8ecf838a9b333c9865d2a4b72c5768fb49fAndrew Trick } 69955ba5dff3c1a723adf302f1124aafde797dbf31aAndrew Trick} 70055ba5dff3c1a723adf302f1124aafde797dbf31aAndrew Trick 701ba17293a8827a7e0e390b0a1d6075148a58d9eddAndrew Trick/// Record the upward impact of a single instruction on current register 702ba17293a8827a7e0e390b0a1d6075148a58d9eddAndrew Trick/// pressure. Unlike the advance/recede pressure tracking interface, this does 703ba17293a8827a7e0e390b0a1d6075148a58d9eddAndrew Trick/// not discover live in/outs. 70455ba5dff3c1a723adf302f1124aafde797dbf31aAndrew Trick/// 705ba17293a8827a7e0e390b0a1d6075148a58d9eddAndrew Trick/// This is intended for speculative queries. It leaves pressure inconsistent 706ba17293a8827a7e0e390b0a1d6075148a58d9eddAndrew Trick/// with the current position, so must be restored by the caller. 707ba17293a8827a7e0e390b0a1d6075148a58d9eddAndrew Trickvoid RegPressureTracker::bumpUpwardPressure(const MachineInstr *MI) { 708f54f61538688eff25f392c2062b3a654394333aaAndrew Trick assert(!MI->isDebugValue() && "Expect a nondebug instruction."); 709f54f61538688eff25f392c2062b3a654394333aaAndrew Trick 71055ba5dff3c1a723adf302f1124aafde797dbf31aAndrew Trick // Account for register pressure similar to RegPressureTracker::recede(). 7114c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick RegisterOperands RegOpers(TRI, MRI, /*IgnoreDead=*/true); 712f54f61538688eff25f392c2062b3a654394333aaAndrew Trick collectOperands(MI, RegOpers); 71355ba5dff3c1a723adf302f1124aafde797dbf31aAndrew Trick 71455ba5dff3c1a723adf302f1124aafde797dbf31aAndrew Trick // Boost max pressure for all dead defs together. 71555ba5dff3c1a723adf302f1124aafde797dbf31aAndrew Trick // Since CurrSetPressure and MaxSetPressure 716f54f61538688eff25f392c2062b3a654394333aaAndrew Trick increaseRegPressure(RegOpers.DeadDefs); 717f54f61538688eff25f392c2062b3a654394333aaAndrew Trick decreaseRegPressure(RegOpers.DeadDefs); 71855ba5dff3c1a723adf302f1124aafde797dbf31aAndrew Trick 71955ba5dff3c1a723adf302f1124aafde797dbf31aAndrew Trick // Kill liveness at live defs. 720f54f61538688eff25f392c2062b3a654394333aaAndrew Trick for (unsigned i = 0, e = RegOpers.Defs.size(); i < e; ++i) { 721f54f61538688eff25f392c2062b3a654394333aaAndrew Trick unsigned Reg = RegOpers.Defs[i]; 722d900b1179535298510490030a5d2ecce93f79eb0Pedro Artigas bool DeadDef = false; 723d900b1179535298510490030a5d2ecce93f79eb0Pedro Artigas if (RequireIntervals) { 724d900b1179535298510490030a5d2ecce93f79eb0Pedro Artigas const LiveRange *LR = getLiveRange(Reg); 725d900b1179535298510490030a5d2ecce93f79eb0Pedro Artigas if (LR) { 726d900b1179535298510490030a5d2ecce93f79eb0Pedro Artigas SlotIndex SlotIdx = LIS->getInstructionIndex(MI); 727d900b1179535298510490030a5d2ecce93f79eb0Pedro Artigas LiveQueryResult LRQ = LR->Query(SlotIdx); 728d900b1179535298510490030a5d2ecce93f79eb0Pedro Artigas DeadDef = LRQ.isDeadDef(); 729d900b1179535298510490030a5d2ecce93f79eb0Pedro Artigas } 730d900b1179535298510490030a5d2ecce93f79eb0Pedro Artigas } 731d900b1179535298510490030a5d2ecce93f79eb0Pedro Artigas if (!DeadDef) { 732d900b1179535298510490030a5d2ecce93f79eb0Pedro Artigas if (!containsReg(RegOpers.Uses, Reg)) 733d900b1179535298510490030a5d2ecce93f79eb0Pedro Artigas decreaseRegPressure(Reg); 734d900b1179535298510490030a5d2ecce93f79eb0Pedro Artigas } 735881a05b46c28299046bd0dc3d0b8c6677e68a4d7Andrew Trick } 73655ba5dff3c1a723adf302f1124aafde797dbf31aAndrew Trick // Generate liveness for uses. 737f54f61538688eff25f392c2062b3a654394333aaAndrew Trick for (unsigned i = 0, e = RegOpers.Uses.size(); i < e; ++i) { 738f54f61538688eff25f392c2062b3a654394333aaAndrew Trick unsigned Reg = RegOpers.Uses[i]; 739f54f61538688eff25f392c2062b3a654394333aaAndrew Trick if (!LiveRegs.contains(Reg)) 740f54f61538688eff25f392c2062b3a654394333aaAndrew Trick increaseRegPressure(Reg); 74155ba5dff3c1a723adf302f1124aafde797dbf31aAndrew Trick } 742ba17293a8827a7e0e390b0a1d6075148a58d9eddAndrew Trick} 743ba17293a8827a7e0e390b0a1d6075148a58d9eddAndrew Trick 744ba17293a8827a7e0e390b0a1d6075148a58d9eddAndrew Trick/// Consider the pressure increase caused by traversing this instruction 745ba17293a8827a7e0e390b0a1d6075148a58d9eddAndrew Trick/// bottom-up. Find the pressure set with the most change beyond its pressure 746ba17293a8827a7e0e390b0a1d6075148a58d9eddAndrew Trick/// limit based on the tracker's current pressure, and return the change in 747ba17293a8827a7e0e390b0a1d6075148a58d9eddAndrew Trick/// number of register units of that pressure set introduced by this 748ba17293a8827a7e0e390b0a1d6075148a58d9eddAndrew Trick/// instruction. 749ba17293a8827a7e0e390b0a1d6075148a58d9eddAndrew Trick/// 750ba17293a8827a7e0e390b0a1d6075148a58d9eddAndrew Trick/// This assumes that the current LiveOut set is sufficient. 751ba17293a8827a7e0e390b0a1d6075148a58d9eddAndrew Trick/// 752ba17293a8827a7e0e390b0a1d6075148a58d9eddAndrew Trick/// FIXME: This is expensive for an on-the-fly query. We need to cache the 753ba17293a8827a7e0e390b0a1d6075148a58d9eddAndrew Trick/// result per-SUnit with enough information to adjust for the current 754ba17293a8827a7e0e390b0a1d6075148a58d9eddAndrew Trick/// scheduling position. But this works as a proof of concept. 755ba17293a8827a7e0e390b0a1d6075148a58d9eddAndrew Trickvoid RegPressureTracker:: 7564c60b8a78d811a5b16ae45f6957933fb479bab58Andrew TrickgetMaxUpwardPressureDelta(const MachineInstr *MI, PressureDiff *PDiff, 7574c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick RegPressureDelta &Delta, 7584c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick ArrayRef<PressureChange> CriticalPSets, 759ba17293a8827a7e0e390b0a1d6075148a58d9eddAndrew Trick ArrayRef<unsigned> MaxPressureLimit) { 760ba17293a8827a7e0e390b0a1d6075148a58d9eddAndrew Trick // Snapshot Pressure. 761ba17293a8827a7e0e390b0a1d6075148a58d9eddAndrew Trick // FIXME: The snapshot heap space should persist. But I'm planning to 762ba17293a8827a7e0e390b0a1d6075148a58d9eddAndrew Trick // summarize the pressure effect so we don't need to snapshot at all. 763ba17293a8827a7e0e390b0a1d6075148a58d9eddAndrew Trick std::vector<unsigned> SavedPressure = CurrSetPressure; 764ba17293a8827a7e0e390b0a1d6075148a58d9eddAndrew Trick std::vector<unsigned> SavedMaxPressure = P.MaxSetPressure; 765ba17293a8827a7e0e390b0a1d6075148a58d9eddAndrew Trick 766ba17293a8827a7e0e390b0a1d6075148a58d9eddAndrew Trick bumpUpwardPressure(MI); 767ba17293a8827a7e0e390b0a1d6075148a58d9eddAndrew Trick 768d71efffdcffc4204e75238f940df41fb24979a7dAndrew Trick computeExcessPressureDelta(SavedPressure, CurrSetPressure, Delta, RCI, 769d71efffdcffc4204e75238f940df41fb24979a7dAndrew Trick LiveThruPressure); 77073a0d8ecf838a9b333c9865d2a4b72c5768fb49fAndrew Trick computeMaxPressureDelta(SavedMaxPressure, P.MaxSetPressure, CriticalPSets, 77173a0d8ecf838a9b333c9865d2a4b72c5768fb49fAndrew Trick MaxPressureLimit, Delta); 7724c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick assert(Delta.CriticalMax.getUnitInc() >= 0 && 7734c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick Delta.CurrentMax.getUnitInc() >= 0 && "cannot decrease max pressure"); 77455ba5dff3c1a723adf302f1124aafde797dbf31aAndrew Trick 77555ba5dff3c1a723adf302f1124aafde797dbf31aAndrew Trick // Restore the tracker's state. 77655ba5dff3c1a723adf302f1124aafde797dbf31aAndrew Trick P.MaxSetPressure.swap(SavedMaxPressure); 77755ba5dff3c1a723adf302f1124aafde797dbf31aAndrew Trick CurrSetPressure.swap(SavedPressure); 7784c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick 7794c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick#ifndef NDEBUG 7804c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick if (!PDiff) 7814c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick return; 7824c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick 7834c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick // Check if the alternate algorithm yields the same result. 7844c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick RegPressureDelta Delta2; 7854c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick getUpwardPressureDelta(MI, *PDiff, Delta2, CriticalPSets, MaxPressureLimit); 7864c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick if (Delta != Delta2) { 7874c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick dbgs() << "DELTA: " << *MI; 7884c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick if (Delta.Excess.isValid()) 7894c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick dbgs() << "Excess1 " << TRI->getRegPressureSetName(Delta.Excess.getPSet()) 7904c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick << " " << Delta.Excess.getUnitInc() << "\n"; 7914c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick if (Delta.CriticalMax.isValid()) 7924c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick dbgs() << "Critic1 " << TRI->getRegPressureSetName(Delta.CriticalMax.getPSet()) 7934c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick << " " << Delta.CriticalMax.getUnitInc() << "\n"; 7944c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick if (Delta.CurrentMax.isValid()) 7954c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick dbgs() << "CurrMx1 " << TRI->getRegPressureSetName(Delta.CurrentMax.getPSet()) 7964c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick << " " << Delta.CurrentMax.getUnitInc() << "\n"; 7974c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick if (Delta2.Excess.isValid()) 7984c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick dbgs() << "Excess2 " << TRI->getRegPressureSetName(Delta2.Excess.getPSet()) 7994c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick << " " << Delta2.Excess.getUnitInc() << "\n"; 8004c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick if (Delta2.CriticalMax.isValid()) 8014c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick dbgs() << "Critic2 " << TRI->getRegPressureSetName(Delta2.CriticalMax.getPSet()) 8024c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick << " " << Delta2.CriticalMax.getUnitInc() << "\n"; 8034c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick if (Delta2.CurrentMax.isValid()) 8044c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick dbgs() << "CurrMx2 " << TRI->getRegPressureSetName(Delta2.CurrentMax.getPSet()) 8054c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick << " " << Delta2.CurrentMax.getUnitInc() << "\n"; 8064c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick llvm_unreachable("RegP Delta Mismatch"); 8074c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick } 8084c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick#endif 8094c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick} 8104c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick 8114c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick/// This is a prototype of the fast version of querying register pressure that 8124c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick/// does not directly depend on current liveness. It's still slow because we 8134c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick/// recompute pressure change on-the-fly. This implementation only exists to 8144c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick/// prove correctness. 8154c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick/// 8164c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick/// @param Delta captures information needed for heuristics. 8174c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick/// 8184c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick/// @param CriticalPSets Are the pressure sets that are known to exceed some 8194c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick/// limit within the region, not necessarily at the current position. 8204c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick/// 8214c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick/// @param MaxPressureLimit Is the max pressure within the region, not 8224c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick/// necessarily at the current position. 8234c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trickvoid RegPressureTracker:: 824663bd9922776e5f7bc17dfc574efe3fe05ceb12cAndrew TrickgetUpwardPressureDelta(const MachineInstr *MI, /*const*/ PressureDiff &PDiff, 8254c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick RegPressureDelta &Delta, 8264c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick ArrayRef<PressureChange> CriticalPSets, 8274c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick ArrayRef<unsigned> MaxPressureLimit) const { 8284c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick unsigned CritIdx = 0, CritEnd = CriticalPSets.size(); 8294c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick for (PressureDiff::const_iterator 8304c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick PDiffI = PDiff.begin(), PDiffE = PDiff.end(); 8314c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick PDiffI != PDiffE && PDiffI->isValid(); ++PDiffI) { 8324c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick 8334c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick unsigned PSetID = PDiffI->getPSet(); 8344c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick unsigned Limit = RCI->getRegPressureSetLimit(PSetID); 8354c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick if (!LiveThruPressure.empty()) 8364c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick Limit += LiveThruPressure[PSetID]; 8374c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick 8384c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick unsigned POld = CurrSetPressure[PSetID]; 8394c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick unsigned MOld = P.MaxSetPressure[PSetID]; 8404c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick unsigned MNew = MOld; 8414c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick // Ignore DeadDefs here because they aren't captured by PressureChange. 8424c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick unsigned PNew = POld + PDiffI->getUnitInc(); 8434c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick assert((PDiffI->getUnitInc() >= 0) == (PNew >= POld) && "PSet overflow"); 8444c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick if (PNew > MOld) 8454c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick MNew = PNew; 8464c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick // Check if current pressure has exceeded the limit. 8474c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick if (!Delta.Excess.isValid()) { 8484c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick unsigned ExcessInc = 0; 8494c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick if (PNew > Limit) 8504c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick ExcessInc = POld > Limit ? PNew - POld : PNew - Limit; 8514c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick else if (POld > Limit) 8524c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick ExcessInc = Limit - POld; 8534c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick if (ExcessInc) { 8544c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick Delta.Excess = PressureChange(PSetID); 8554c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick Delta.Excess.setUnitInc(ExcessInc); 8564c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick } 8574c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick } 8584c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick // Check if max pressure has exceeded a critical pressure set max. 8594c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick if (MNew == MOld) 8604c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick continue; 8614c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick if (!Delta.CriticalMax.isValid()) { 8624c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick while (CritIdx != CritEnd && CriticalPSets[CritIdx].getPSet() < PSetID) 8634c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick ++CritIdx; 8644c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick 8654c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick if (CritIdx != CritEnd && CriticalPSets[CritIdx].getPSet() == PSetID) { 8664c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick int CritInc = (int)MNew - (int)CriticalPSets[CritIdx].getUnitInc(); 8674c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick if (CritInc > 0 && CritInc <= INT16_MAX) { 8684c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick Delta.CriticalMax = PressureChange(PSetID); 8694c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick Delta.CriticalMax.setUnitInc(CritInc); 8704c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick } 8714c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick } 8724c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick } 8734c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick // Check if max pressure has exceeded the current max. 8744c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick if (!Delta.CurrentMax.isValid() && MNew > MaxPressureLimit[PSetID]) { 8754c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick Delta.CurrentMax = PressureChange(PSetID); 8764c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick Delta.CurrentMax.setUnitInc(MNew - MOld); 8774c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick } 8784c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick } 87955ba5dff3c1a723adf302f1124aafde797dbf31aAndrew Trick} 88055ba5dff3c1a723adf302f1124aafde797dbf31aAndrew Trick 88155ba5dff3c1a723adf302f1124aafde797dbf31aAndrew Trick/// Helper to find a vreg use between two indices [PriorUseIdx, NextUseIdx). 88255ba5dff3c1a723adf302f1124aafde797dbf31aAndrew Trickstatic bool findUseBetween(unsigned Reg, 88355ba5dff3c1a723adf302f1124aafde797dbf31aAndrew Trick SlotIndex PriorUseIdx, SlotIndex NextUseIdx, 88455ba5dff3c1a723adf302f1124aafde797dbf31aAndrew Trick const MachineRegisterInfo *MRI, 88555ba5dff3c1a723adf302f1124aafde797dbf31aAndrew Trick const LiveIntervals *LIS) { 88636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (MachineRegisterInfo::use_instr_nodbg_iterator 88736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines UI = MRI->use_instr_nodbg_begin(Reg), 88836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines UE = MRI->use_instr_nodbg_end(); UI != UE; ++UI) { 88955ba5dff3c1a723adf302f1124aafde797dbf31aAndrew Trick const MachineInstr* MI = &*UI; 890f3329c419b1010089e8aaf3d43b811ba12d94c8aAndrew Trick if (MI->isDebugValue()) 891f3329c419b1010089e8aaf3d43b811ba12d94c8aAndrew Trick continue; 89255ba5dff3c1a723adf302f1124aafde797dbf31aAndrew Trick SlotIndex InstSlot = LIS->getInstructionIndex(MI).getRegSlot(); 89355ba5dff3c1a723adf302f1124aafde797dbf31aAndrew Trick if (InstSlot >= PriorUseIdx && InstSlot < NextUseIdx) 89455ba5dff3c1a723adf302f1124aafde797dbf31aAndrew Trick return true; 89555ba5dff3c1a723adf302f1124aafde797dbf31aAndrew Trick } 89655ba5dff3c1a723adf302f1124aafde797dbf31aAndrew Trick return false; 89755ba5dff3c1a723adf302f1124aafde797dbf31aAndrew Trick} 89855ba5dff3c1a723adf302f1124aafde797dbf31aAndrew Trick 899ba17293a8827a7e0e390b0a1d6075148a58d9eddAndrew Trick/// Record the downward impact of a single instruction on current register 900ba17293a8827a7e0e390b0a1d6075148a58d9eddAndrew Trick/// pressure. Unlike the advance/recede pressure tracking interface, this does 901ba17293a8827a7e0e390b0a1d6075148a58d9eddAndrew Trick/// not discover live in/outs. 90255ba5dff3c1a723adf302f1124aafde797dbf31aAndrew Trick/// 903ba17293a8827a7e0e390b0a1d6075148a58d9eddAndrew Trick/// This is intended for speculative queries. It leaves pressure inconsistent 904ba17293a8827a7e0e390b0a1d6075148a58d9eddAndrew Trick/// with the current position, so must be restored by the caller. 905ba17293a8827a7e0e390b0a1d6075148a58d9eddAndrew Trickvoid RegPressureTracker::bumpDownwardPressure(const MachineInstr *MI) { 906f54f61538688eff25f392c2062b3a654394333aaAndrew Trick assert(!MI->isDebugValue() && "Expect a nondebug instruction."); 907f54f61538688eff25f392c2062b3a654394333aaAndrew Trick 90855ba5dff3c1a723adf302f1124aafde797dbf31aAndrew Trick // Account for register pressure similar to RegPressureTracker::recede(). 909f54f61538688eff25f392c2062b3a654394333aaAndrew Trick RegisterOperands RegOpers(TRI, MRI); 910f54f61538688eff25f392c2062b3a654394333aaAndrew Trick collectOperands(MI, RegOpers); 91155ba5dff3c1a723adf302f1124aafde797dbf31aAndrew Trick 91255ba5dff3c1a723adf302f1124aafde797dbf31aAndrew Trick // Kill liveness at last uses. Assume allocatable physregs are single-use 91355ba5dff3c1a723adf302f1124aafde797dbf31aAndrew Trick // rather than checking LiveIntervals. 914f54f61538688eff25f392c2062b3a654394333aaAndrew Trick SlotIndex SlotIdx; 915f54f61538688eff25f392c2062b3a654394333aaAndrew Trick if (RequireIntervals) 916f54f61538688eff25f392c2062b3a654394333aaAndrew Trick SlotIdx = LIS->getInstructionIndex(MI).getRegSlot(); 917f54f61538688eff25f392c2062b3a654394333aaAndrew Trick 918f54f61538688eff25f392c2062b3a654394333aaAndrew Trick for (unsigned i = 0, e = RegOpers.Uses.size(); i < e; ++i) { 919f54f61538688eff25f392c2062b3a654394333aaAndrew Trick unsigned Reg = RegOpers.Uses[i]; 920f54f61538688eff25f392c2062b3a654394333aaAndrew Trick if (RequireIntervals) { 921f54f61538688eff25f392c2062b3a654394333aaAndrew Trick // FIXME: allow the caller to pass in the list of vreg uses that remain 922f54f61538688eff25f392c2062b3a654394333aaAndrew Trick // to be bottom-scheduled to avoid searching uses at each query. 923657b75b9946eae763725b413841dfd01ed12a051Andrew Trick SlotIndex CurrIdx = getCurrSlot(); 9244f3b5e8c9232e43d1291aab8db5f5698d7ee0ea4Matthias Braun const LiveRange *LR = getLiveRange(Reg); 9254f3b5e8c9232e43d1291aab8db5f5698d7ee0ea4Matthias Braun if (LR) { 9264f3b5e8c9232e43d1291aab8db5f5698d7ee0ea4Matthias Braun LiveQueryResult LRQ = LR->Query(SlotIdx); 9274f3b5e8c9232e43d1291aab8db5f5698d7ee0ea4Matthias Braun if (LRQ.isKill() && !findUseBetween(Reg, CurrIdx, SlotIdx, MRI, LIS)) { 928846b31d74aa673a178f57f9d47f366d8ddb756d3Andrew Trick decreaseRegPressure(Reg); 9294f3b5e8c9232e43d1291aab8db5f5698d7ee0ea4Matthias Braun } 93055ba5dff3c1a723adf302f1124aafde797dbf31aAndrew Trick } 93155ba5dff3c1a723adf302f1124aafde797dbf31aAndrew Trick } 932f54f61538688eff25f392c2062b3a654394333aaAndrew Trick else if (!TargetRegisterInfo::isVirtualRegister(Reg)) { 933f54f61538688eff25f392c2062b3a654394333aaAndrew Trick // Allocatable physregs are always single-use before register rewriting. 934f54f61538688eff25f392c2062b3a654394333aaAndrew Trick decreaseRegPressure(Reg); 935f54f61538688eff25f392c2062b3a654394333aaAndrew Trick } 93655ba5dff3c1a723adf302f1124aafde797dbf31aAndrew Trick } 93755ba5dff3c1a723adf302f1124aafde797dbf31aAndrew Trick 93855ba5dff3c1a723adf302f1124aafde797dbf31aAndrew Trick // Generate liveness for defs. 939f54f61538688eff25f392c2062b3a654394333aaAndrew Trick increaseRegPressure(RegOpers.Defs); 94055ba5dff3c1a723adf302f1124aafde797dbf31aAndrew Trick 94155ba5dff3c1a723adf302f1124aafde797dbf31aAndrew Trick // Boost pressure for all dead defs together. 942f54f61538688eff25f392c2062b3a654394333aaAndrew Trick increaseRegPressure(RegOpers.DeadDefs); 943f54f61538688eff25f392c2062b3a654394333aaAndrew Trick decreaseRegPressure(RegOpers.DeadDefs); 944ba17293a8827a7e0e390b0a1d6075148a58d9eddAndrew Trick} 945ba17293a8827a7e0e390b0a1d6075148a58d9eddAndrew Trick 946ba17293a8827a7e0e390b0a1d6075148a58d9eddAndrew Trick/// Consider the pressure increase caused by traversing this instruction 947ba17293a8827a7e0e390b0a1d6075148a58d9eddAndrew Trick/// top-down. Find the register class with the most change in its pressure limit 948ba17293a8827a7e0e390b0a1d6075148a58d9eddAndrew Trick/// based on the tracker's current pressure, and return the number of excess 949ba17293a8827a7e0e390b0a1d6075148a58d9eddAndrew Trick/// register units of that pressure set introduced by this instruction. 950ba17293a8827a7e0e390b0a1d6075148a58d9eddAndrew Trick/// 951ba17293a8827a7e0e390b0a1d6075148a58d9eddAndrew Trick/// This assumes that the current LiveIn set is sufficient. 952ba17293a8827a7e0e390b0a1d6075148a58d9eddAndrew Trickvoid RegPressureTracker:: 953ba17293a8827a7e0e390b0a1d6075148a58d9eddAndrew TrickgetMaxDownwardPressureDelta(const MachineInstr *MI, RegPressureDelta &Delta, 9544c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick ArrayRef<PressureChange> CriticalPSets, 955ba17293a8827a7e0e390b0a1d6075148a58d9eddAndrew Trick ArrayRef<unsigned> MaxPressureLimit) { 956ba17293a8827a7e0e390b0a1d6075148a58d9eddAndrew Trick // Snapshot Pressure. 957ba17293a8827a7e0e390b0a1d6075148a58d9eddAndrew Trick std::vector<unsigned> SavedPressure = CurrSetPressure; 958ba17293a8827a7e0e390b0a1d6075148a58d9eddAndrew Trick std::vector<unsigned> SavedMaxPressure = P.MaxSetPressure; 959ba17293a8827a7e0e390b0a1d6075148a58d9eddAndrew Trick 960ba17293a8827a7e0e390b0a1d6075148a58d9eddAndrew Trick bumpDownwardPressure(MI); 96155ba5dff3c1a723adf302f1124aafde797dbf31aAndrew Trick 962d71efffdcffc4204e75238f940df41fb24979a7dAndrew Trick computeExcessPressureDelta(SavedPressure, CurrSetPressure, Delta, RCI, 963d71efffdcffc4204e75238f940df41fb24979a7dAndrew Trick LiveThruPressure); 96473a0d8ecf838a9b333c9865d2a4b72c5768fb49fAndrew Trick computeMaxPressureDelta(SavedMaxPressure, P.MaxSetPressure, CriticalPSets, 96573a0d8ecf838a9b333c9865d2a4b72c5768fb49fAndrew Trick MaxPressureLimit, Delta); 9664c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick assert(Delta.CriticalMax.getUnitInc() >= 0 && 9674c60b8a78d811a5b16ae45f6957933fb479bab58Andrew Trick Delta.CurrentMax.getUnitInc() >= 0 && "cannot decrease max pressure"); 96855ba5dff3c1a723adf302f1124aafde797dbf31aAndrew Trick 96955ba5dff3c1a723adf302f1124aafde797dbf31aAndrew Trick // Restore the tracker's state. 97055ba5dff3c1a723adf302f1124aafde797dbf31aAndrew Trick P.MaxSetPressure.swap(SavedMaxPressure); 97155ba5dff3c1a723adf302f1124aafde797dbf31aAndrew Trick CurrSetPressure.swap(SavedPressure); 97255ba5dff3c1a723adf302f1124aafde797dbf31aAndrew Trick} 973ba17293a8827a7e0e390b0a1d6075148a58d9eddAndrew Trick 974ba17293a8827a7e0e390b0a1d6075148a58d9eddAndrew Trick/// Get the pressure of each PSet after traversing this instruction bottom-up. 975ba17293a8827a7e0e390b0a1d6075148a58d9eddAndrew Trickvoid RegPressureTracker:: 976ba17293a8827a7e0e390b0a1d6075148a58d9eddAndrew TrickgetUpwardPressure(const MachineInstr *MI, 9770eb3a3524e9d68642e574780d19c781386ed4469Andrew Trick std::vector<unsigned> &PressureResult, 9780eb3a3524e9d68642e574780d19c781386ed4469Andrew Trick std::vector<unsigned> &MaxPressureResult) { 979ba17293a8827a7e0e390b0a1d6075148a58d9eddAndrew Trick // Snapshot pressure. 980ba17293a8827a7e0e390b0a1d6075148a58d9eddAndrew Trick PressureResult = CurrSetPressure; 9810eb3a3524e9d68642e574780d19c781386ed4469Andrew Trick MaxPressureResult = P.MaxSetPressure; 982ba17293a8827a7e0e390b0a1d6075148a58d9eddAndrew Trick 983ba17293a8827a7e0e390b0a1d6075148a58d9eddAndrew Trick bumpUpwardPressure(MI); 984ba17293a8827a7e0e390b0a1d6075148a58d9eddAndrew Trick 985ba17293a8827a7e0e390b0a1d6075148a58d9eddAndrew Trick // Current pressure becomes the result. Restore current pressure. 9860eb3a3524e9d68642e574780d19c781386ed4469Andrew Trick P.MaxSetPressure.swap(MaxPressureResult); 987ba17293a8827a7e0e390b0a1d6075148a58d9eddAndrew Trick CurrSetPressure.swap(PressureResult); 988ba17293a8827a7e0e390b0a1d6075148a58d9eddAndrew Trick} 989ba17293a8827a7e0e390b0a1d6075148a58d9eddAndrew Trick 990ba17293a8827a7e0e390b0a1d6075148a58d9eddAndrew Trick/// Get the pressure of each PSet after traversing this instruction top-down. 991ba17293a8827a7e0e390b0a1d6075148a58d9eddAndrew Trickvoid RegPressureTracker:: 992ba17293a8827a7e0e390b0a1d6075148a58d9eddAndrew TrickgetDownwardPressure(const MachineInstr *MI, 9930eb3a3524e9d68642e574780d19c781386ed4469Andrew Trick std::vector<unsigned> &PressureResult, 9940eb3a3524e9d68642e574780d19c781386ed4469Andrew Trick std::vector<unsigned> &MaxPressureResult) { 995ba17293a8827a7e0e390b0a1d6075148a58d9eddAndrew Trick // Snapshot pressure. 996ba17293a8827a7e0e390b0a1d6075148a58d9eddAndrew Trick PressureResult = CurrSetPressure; 9970eb3a3524e9d68642e574780d19c781386ed4469Andrew Trick MaxPressureResult = P.MaxSetPressure; 998ba17293a8827a7e0e390b0a1d6075148a58d9eddAndrew Trick 999ba17293a8827a7e0e390b0a1d6075148a58d9eddAndrew Trick bumpDownwardPressure(MI); 1000ba17293a8827a7e0e390b0a1d6075148a58d9eddAndrew Trick 1001ba17293a8827a7e0e390b0a1d6075148a58d9eddAndrew Trick // Current pressure becomes the result. Restore current pressure. 10020eb3a3524e9d68642e574780d19c781386ed4469Andrew Trick P.MaxSetPressure.swap(MaxPressureResult); 1003ba17293a8827a7e0e390b0a1d6075148a58d9eddAndrew Trick CurrSetPressure.swap(PressureResult); 1004ba17293a8827a7e0e390b0a1d6075148a58d9eddAndrew Trick} 1005