1ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick//===- ResourcePriorityQueue.cpp - A DFA-oriented priority queue -*- C++ -*-==// 2ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick// 3ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick// The LLVM Compiler Infrastructure 4ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick// 5ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick// This file is distributed under the University of Illinois Open Source 6ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick// License. See LICENSE.TXT for details. 7ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick// 8ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick//===----------------------------------------------------------------------===// 9ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick// 10ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick// This file implements the ResourcePriorityQueue class, which is a 11ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick// SchedulingPriorityQueue that prioritizes instructions using DFA state to 12ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick// reduce the length of the critical path through the basic block 13ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick// on VLIW platforms. 14ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick// The scheduler is basically a top-down adaptable list scheduler with DFA 15ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick// resource tracking added to the cost function. 16ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick// DFA is queried as a state machine to model "packets/bundles" during 17ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick// schedule. Currently packets/bundles are discarded at the end of 18ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick// scheduling, affecting only order of instructions. 19ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick// 20ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick//===----------------------------------------------------------------------===// 21ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 22ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick#define DEBUG_TYPE "scheduler" 23ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick#include "llvm/CodeGen/ResourcePriorityQueue.h" 24d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/CodeGen/MachineInstr.h" 25d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/CodeGen/SelectionDAGNodes.h" 26ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick#include "llvm/Support/CommandLine.h" 27ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick#include "llvm/Support/Debug.h" 28ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick#include "llvm/Support/raw_ostream.h" 29ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick#include "llvm/Target/TargetLowering.h" 30d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Target/TargetMachine.h" 31ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 32ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trickusing namespace llvm; 33ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 34ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trickstatic cl::opt<bool> DisableDFASched("disable-dfa-sched", cl::Hidden, 35ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick cl::ZeroOrMore, cl::init(false), 36ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick cl::desc("Disable use of DFA during scheduling")); 37ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 38ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trickstatic cl::opt<signed> RegPressureThreshold( 39ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick "dfa-sched-reg-pressure-threshold", cl::Hidden, cl::ZeroOrMore, cl::init(5), 40ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick cl::desc("Track reg pressure and switch priority to in-depth")); 41ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 42ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 43ee498d3254b86bceb4f441741e9f442990647ce6Andrew TrickResourcePriorityQueue::ResourcePriorityQueue(SelectionDAGISel *IS) : 44ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick Picker(this), 456a2e7ac0b6647a409394e58b385e579ea62b5cbaBill Wendling InstrItins(IS->getTargetLowering()->getTargetMachine().getInstrItineraryData()) 46ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick{ 476a2e7ac0b6647a409394e58b385e579ea62b5cbaBill Wendling TII = IS->getTargetLowering()->getTargetMachine().getInstrInfo(); 486a2e7ac0b6647a409394e58b385e579ea62b5cbaBill Wendling TRI = IS->getTargetLowering()->getTargetMachine().getRegisterInfo(); 496a2e7ac0b6647a409394e58b385e579ea62b5cbaBill Wendling TLI = IS->getTargetLowering(); 50ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 51ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick const TargetMachine &tm = (*IS->MF).getTarget(); 52ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick ResourcesModel = tm.getInstrInfo()->CreateTargetScheduleState(&tm,NULL); 53d9b0b025612992a0b724eeca8bdf10b1d7a5c355Benjamin Kramer // This hard requirement could be relaxed, but for now 54ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick // do not let it procede. 55ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick assert (ResourcesModel && "Unimplemented CreateTargetScheduleState."); 56ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 57ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick unsigned NumRC = TRI->getNumRegClasses(); 58ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick RegLimit.resize(NumRC); 59ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick RegPressure.resize(NumRC); 60ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick std::fill(RegLimit.begin(), RegLimit.end(), 0); 61ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick std::fill(RegPressure.begin(), RegPressure.end(), 0); 62ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick for (TargetRegisterInfo::regclass_iterator I = TRI->regclass_begin(), 63ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick E = TRI->regclass_end(); I != E; ++I) 64ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick RegLimit[(*I)->getID()] = TRI->getRegPressureLimit(*I, *IS->MF); 65ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 66ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick ParallelLiveRanges = 0; 67ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick HorizontalVerticalBalance = 0; 68ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick} 69ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 70ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trickunsigned 71ee498d3254b86bceb4f441741e9f442990647ce6Andrew TrickResourcePriorityQueue::numberRCValPredInSU(SUnit *SU, unsigned RCId) { 72ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick unsigned NumberDeps = 0; 73ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 74ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick I != E; ++I) { 75ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick if (I->isCtrl()) 76ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick continue; 77ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 78ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick SUnit *PredSU = I->getSUnit(); 79ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick const SDNode *ScegN = PredSU->getNode(); 80ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 81ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick if (!ScegN) 82ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick continue; 83ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 84ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick // If value is passed to CopyToReg, it is probably 85ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick // live outside BB. 86ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick switch (ScegN->getOpcode()) { 87ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick default: break; 88ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick case ISD::TokenFactor: break; 89ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick case ISD::CopyFromReg: NumberDeps++; break; 90ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick case ISD::CopyToReg: break; 91ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick case ISD::INLINEASM: break; 92ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick } 93ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick if (!ScegN->isMachineOpcode()) 94ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick continue; 95ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 96ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick for (unsigned i = 0, e = ScegN->getNumValues(); i != e; ++i) { 97a61b17c18a67f1b3faef2f2108379c4337ce9bb7Patrik Hagglund MVT VT = ScegN->getSimpleValueType(i); 98ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick if (TLI->isTypeLegal(VT) 99a61b17c18a67f1b3faef2f2108379c4337ce9bb7Patrik Hagglund && (TLI->getRegClassFor(VT)->getID() == RCId)) { 100ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick NumberDeps++; 101ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick break; 102ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick } 103ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick } 104ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick } 105ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick return NumberDeps; 106ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick} 107ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 108ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trickunsigned ResourcePriorityQueue::numberRCValSuccInSU(SUnit *SU, 109ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick unsigned RCId) { 110ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick unsigned NumberDeps = 0; 111ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 112ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick I != E; ++I) { 113ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick if (I->isCtrl()) 114ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick continue; 115ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 116ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick SUnit *SuccSU = I->getSUnit(); 117ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick const SDNode *ScegN = SuccSU->getNode(); 118ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick if (!ScegN) 119ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick continue; 120ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 121ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick // If value is passed to CopyToReg, it is probably 122ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick // live outside BB. 123ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick switch (ScegN->getOpcode()) { 124ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick default: break; 125ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick case ISD::TokenFactor: break; 126ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick case ISD::CopyFromReg: break; 127ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick case ISD::CopyToReg: NumberDeps++; break; 128ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick case ISD::INLINEASM: break; 129ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick } 130ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick if (!ScegN->isMachineOpcode()) 131ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick continue; 132ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 133ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick for (unsigned i = 0, e = ScegN->getNumOperands(); i != e; ++i) { 134ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick const SDValue &Op = ScegN->getOperand(i); 135a61b17c18a67f1b3faef2f2108379c4337ce9bb7Patrik Hagglund MVT VT = Op.getNode()->getSimpleValueType(Op.getResNo()); 136ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick if (TLI->isTypeLegal(VT) 137a61b17c18a67f1b3faef2f2108379c4337ce9bb7Patrik Hagglund && (TLI->getRegClassFor(VT)->getID() == RCId)) { 138ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick NumberDeps++; 139ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick break; 140ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick } 141ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick } 142ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick } 143ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick return NumberDeps; 144ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick} 145ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 146ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trickstatic unsigned numberCtrlDepsInSU(SUnit *SU) { 147ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick unsigned NumberDeps = 0; 148ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 149ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick I != E; ++I) 150ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick if (I->isCtrl()) 151ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick NumberDeps++; 152ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 153ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick return NumberDeps; 154ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick} 155ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 156ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trickstatic unsigned numberCtrlPredInSU(SUnit *SU) { 157ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick unsigned NumberDeps = 0; 158ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 159ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick I != E; ++I) 160ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick if (I->isCtrl()) 161ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick NumberDeps++; 162ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 163ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick return NumberDeps; 164ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick} 165ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 166ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick/// 167ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick/// Initialize nodes. 168ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick/// 169ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trickvoid ResourcePriorityQueue::initNodes(std::vector<SUnit> &sunits) { 170ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick SUnits = &sunits; 171ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick NumNodesSolelyBlocking.resize(SUnits->size(), 0); 172ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 173ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick for (unsigned i = 0, e = SUnits->size(); i != e; ++i) { 174ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick SUnit *SU = &(*SUnits)[i]; 175ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick initNumRegDefsLeft(SU); 176ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick SU->NodeQueueId = 0; 177ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick } 178ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick} 179ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 180ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick/// This heuristic is used if DFA scheduling is not desired 181ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick/// for some VLIW platform. 182ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trickbool resource_sort::operator()(const SUnit *LHS, const SUnit *RHS) const { 183ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick // The isScheduleHigh flag allows nodes with wraparound dependencies that 184ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick // cannot easily be modeled as edges with latencies to be scheduled as 185ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick // soon as possible in a top-down schedule. 186ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick if (LHS->isScheduleHigh && !RHS->isScheduleHigh) 187ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick return false; 188ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 189ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick if (!LHS->isScheduleHigh && RHS->isScheduleHigh) 190ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick return true; 191ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 192ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick unsigned LHSNum = LHS->NodeNum; 193ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick unsigned RHSNum = RHS->NodeNum; 194ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 195ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick // The most important heuristic is scheduling the critical path. 196ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick unsigned LHSLatency = PQ->getLatency(LHSNum); 197ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick unsigned RHSLatency = PQ->getLatency(RHSNum); 198ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick if (LHSLatency < RHSLatency) return true; 199ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick if (LHSLatency > RHSLatency) return false; 200ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 201ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick // After that, if two nodes have identical latencies, look to see if one will 202ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick // unblock more other nodes than the other. 203ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick unsigned LHSBlocked = PQ->getNumSolelyBlockNodes(LHSNum); 204ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick unsigned RHSBlocked = PQ->getNumSolelyBlockNodes(RHSNum); 205ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick if (LHSBlocked < RHSBlocked) return true; 206ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick if (LHSBlocked > RHSBlocked) return false; 207ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 208ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick // Finally, just to provide a stable ordering, use the node number as a 209ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick // deciding factor. 210ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick return LHSNum < RHSNum; 211ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick} 212ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 213ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 214ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick/// getSingleUnscheduledPred - If there is exactly one unscheduled predecessor 215ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick/// of SU, return it, otherwise return null. 216ee498d3254b86bceb4f441741e9f442990647ce6Andrew TrickSUnit *ResourcePriorityQueue::getSingleUnscheduledPred(SUnit *SU) { 217ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick SUnit *OnlyAvailablePred = 0; 218ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 219ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick I != E; ++I) { 220ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick SUnit &Pred = *I->getSUnit(); 221ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick if (!Pred.isScheduled) { 222ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick // We found an available, but not scheduled, predecessor. If it's the 223ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick // only one we have found, keep track of it... otherwise give up. 224ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick if (OnlyAvailablePred && OnlyAvailablePred != &Pred) 225ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick return 0; 226ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick OnlyAvailablePred = &Pred; 227ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick } 228ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick } 229ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick return OnlyAvailablePred; 230ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick} 231ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 232ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trickvoid ResourcePriorityQueue::push(SUnit *SU) { 233ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick // Look at all of the successors of this node. Count the number of nodes that 234ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick // this node is the sole unscheduled node for. 235ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick unsigned NumNodesBlocking = 0; 236ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 237ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick I != E; ++I) 238ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick if (getSingleUnscheduledPred(I->getSUnit()) == SU) 239ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick ++NumNodesBlocking; 240ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 241ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick NumNodesSolelyBlocking[SU->NodeNum] = NumNodesBlocking; 242ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick Queue.push_back(SU); 243ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick} 244ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 245ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick/// Check if scheduling of this SU is possible 246ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick/// in the current packet. 247ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trickbool ResourcePriorityQueue::isResourceAvailable(SUnit *SU) { 248ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick if (!SU || !SU->getNode()) 249ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick return false; 250ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 251ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick // If this is a compound instruction, 252ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick // it is likely to be a call. Do not delay it. 253ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick if (SU->getNode()->getGluedNode()) 254ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick return true; 255ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 256ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick // First see if the pipeline could receive this instruction 257ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick // in the current cycle. 258ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick if (SU->getNode()->isMachineOpcode()) 259ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick switch (SU->getNode()->getMachineOpcode()) { 260ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick default: 261ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick if (!ResourcesModel->canReserveResources(&TII->get( 262ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick SU->getNode()->getMachineOpcode()))) 263ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick return false; 264ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick case TargetOpcode::EXTRACT_SUBREG: 265ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick case TargetOpcode::INSERT_SUBREG: 266ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick case TargetOpcode::SUBREG_TO_REG: 267ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick case TargetOpcode::REG_SEQUENCE: 268ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick case TargetOpcode::IMPLICIT_DEF: 269ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick break; 270ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick } 271ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 272ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick // Now see if there are no other dependencies 273ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick // to instructions alredy in the packet. 274ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick for (unsigned i = 0, e = Packet.size(); i != e; ++i) 275ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick for (SUnit::const_succ_iterator I = Packet[i]->Succs.begin(), 276ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick E = Packet[i]->Succs.end(); I != E; ++I) { 277ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick // Since we do not add pseudos to packets, might as well 278ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick // ignor order deps. 279ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick if (I->isCtrl()) 280ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick continue; 281ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 282ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick if (I->getSUnit() == SU) 283ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick return false; 284ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick } 285ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 286ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick return true; 287ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick} 288ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 289ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick/// Keep track of available resources. 290ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trickvoid ResourcePriorityQueue::reserveResources(SUnit *SU) { 291ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick // If this SU does not fit in the packet 292ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick // start a new one. 293ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick if (!isResourceAvailable(SU) || SU->getNode()->getGluedNode()) { 294ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick ResourcesModel->clearResources(); 295ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick Packet.clear(); 296ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick } 297ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 298ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick if (SU->getNode() && SU->getNode()->isMachineOpcode()) { 299ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick switch (SU->getNode()->getMachineOpcode()) { 300ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick default: 301ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick ResourcesModel->reserveResources(&TII->get( 302ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick SU->getNode()->getMachineOpcode())); 303ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick break; 304ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick case TargetOpcode::EXTRACT_SUBREG: 305ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick case TargetOpcode::INSERT_SUBREG: 306ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick case TargetOpcode::SUBREG_TO_REG: 307ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick case TargetOpcode::REG_SEQUENCE: 308ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick case TargetOpcode::IMPLICIT_DEF: 309ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick break; 310ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick } 311ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick Packet.push_back(SU); 312ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick } 313ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick // Forcefully end packet for PseudoOps. 314ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick else { 315ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick ResourcesModel->clearResources(); 316ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick Packet.clear(); 317ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick } 318ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 319ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick // If packet is now full, reset the state so in the next cycle 320ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick // we start fresh. 3212661b411ccc81b1fe19194d3f43b2630cbef3f28Andrew Trick if (Packet.size() >= InstrItins->SchedModel->IssueWidth) { 322ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick ResourcesModel->clearResources(); 323ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick Packet.clear(); 324ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick } 325ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick} 326ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 327ee498d3254b86bceb4f441741e9f442990647ce6Andrew Tricksigned ResourcePriorityQueue::rawRegPressureDelta(SUnit *SU, unsigned RCId) { 328ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick signed RegBalance = 0; 329ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 330ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick if (!SU || !SU->getNode() || !SU->getNode()->isMachineOpcode()) 331ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick return RegBalance; 332ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 333ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick // Gen estimate. 334ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick for (unsigned i = 0, e = SU->getNode()->getNumValues(); i != e; ++i) { 335a61b17c18a67f1b3faef2f2108379c4337ce9bb7Patrik Hagglund MVT VT = SU->getNode()->getSimpleValueType(i); 336ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick if (TLI->isTypeLegal(VT) 337ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick && TLI->getRegClassFor(VT) 338ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick && TLI->getRegClassFor(VT)->getID() == RCId) 339ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick RegBalance += numberRCValSuccInSU(SU, RCId); 340ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick } 341ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick // Kill estimate. 342ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick for (unsigned i = 0, e = SU->getNode()->getNumOperands(); i != e; ++i) { 343ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick const SDValue &Op = SU->getNode()->getOperand(i); 344a61b17c18a67f1b3faef2f2108379c4337ce9bb7Patrik Hagglund MVT VT = Op.getNode()->getSimpleValueType(Op.getResNo()); 345ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick if (isa<ConstantSDNode>(Op.getNode())) 346ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick continue; 347ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 348ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick if (TLI->isTypeLegal(VT) && TLI->getRegClassFor(VT) 349ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick && TLI->getRegClassFor(VT)->getID() == RCId) 350ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick RegBalance -= numberRCValPredInSU(SU, RCId); 351ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick } 352ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick return RegBalance; 353ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick} 354ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 355ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick/// Estimates change in reg pressure from this SU. 356d9b0b025612992a0b724eeca8bdf10b1d7a5c355Benjamin Kramer/// It is achieved by trivial tracking of defined 357ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick/// and used vregs in dependent instructions. 358ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick/// The RawPressure flag makes this function to ignore 359ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick/// existing reg file sizes, and report raw def/use 360ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick/// balance. 361ee498d3254b86bceb4f441741e9f442990647ce6Andrew Tricksigned ResourcePriorityQueue::regPressureDelta(SUnit *SU, bool RawPressure) { 362ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick signed RegBalance = 0; 363ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 364ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick if (!SU || !SU->getNode() || !SU->getNode()->isMachineOpcode()) 365ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick return RegBalance; 366ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 367ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick if (RawPressure) { 368ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick for (TargetRegisterInfo::regclass_iterator I = TRI->regclass_begin(), 369ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick E = TRI->regclass_end(); I != E; ++I) { 370ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick const TargetRegisterClass *RC = *I; 371ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick RegBalance += rawRegPressureDelta(SU, RC->getID()); 372ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick } 373ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick } 374ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick else { 375ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick for (TargetRegisterInfo::regclass_iterator I = TRI->regclass_begin(), 376ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick E = TRI->regclass_end(); I != E; ++I) { 377ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick const TargetRegisterClass *RC = *I; 378ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick if ((RegPressure[RC->getID()] + 379ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick rawRegPressureDelta(SU, RC->getID()) > 0) && 380ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick (RegPressure[RC->getID()] + 381ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick rawRegPressureDelta(SU, RC->getID()) >= RegLimit[RC->getID()])) 382ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick RegBalance += rawRegPressureDelta(SU, RC->getID()); 383ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick } 384ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick } 385ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 386ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick return RegBalance; 387ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick} 388ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 389ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick// Constants used to denote relative importance of 390ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick// heuristic components for cost computation. 391ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trickstatic const unsigned PriorityOne = 200; 392ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trickstatic const unsigned PriorityTwo = 100; 393ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trickstatic const unsigned PriorityThree = 50; 394ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trickstatic const unsigned PriorityFour = 15; 395ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trickstatic const unsigned PriorityFive = 5; 396ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trickstatic const unsigned ScaleOne = 20; 397ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trickstatic const unsigned ScaleTwo = 10; 398ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trickstatic const unsigned ScaleThree = 5; 399ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trickstatic const unsigned FactorOne = 2; 400ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 401ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick/// Returns single number reflecting benefit of scheduling SU 402ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick/// in the current cycle. 403ee498d3254b86bceb4f441741e9f442990647ce6Andrew Tricksigned ResourcePriorityQueue::SUSchedulingCost(SUnit *SU) { 404ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick // Initial trivial priority. 405ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick signed ResCount = 1; 406ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 407ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick // Do not waste time on a node that is already scheduled. 408ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick if (SU->isScheduled) 409ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick return ResCount; 410ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 411ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick // Forced priority is high. 412ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick if (SU->isScheduleHigh) 413ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick ResCount += PriorityOne; 414ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 415ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick // Adaptable scheduling 416ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick // A small, but very parallel 417ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick // region, where reg pressure is an issue. 418ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick if (HorizontalVerticalBalance > RegPressureThreshold) { 419ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick // Critical path first 420ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick ResCount += (SU->getHeight() * ScaleTwo); 421ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick // If resources are available for it, multiply the 422ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick // chance of scheduling. 423ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick if (isResourceAvailable(SU)) 424ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick ResCount <<= FactorOne; 425ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 426ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick // Consider change to reg pressure from scheduling 427ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick // this SU. 428ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick ResCount -= (regPressureDelta(SU,true) * ScaleOne); 429ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick } 430ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick // Default heuristic, greeady and 431ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick // critical path driven. 432ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick else { 433ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick // Critical path first. 434ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick ResCount += (SU->getHeight() * ScaleTwo); 435ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick // Now see how many instructions is blocked by this SU. 436ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick ResCount += (NumNodesSolelyBlocking[SU->NodeNum] * ScaleTwo); 437ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick // If resources are available for it, multiply the 438ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick // chance of scheduling. 439ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick if (isResourceAvailable(SU)) 440ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick ResCount <<= FactorOne; 441ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 442ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick ResCount -= (regPressureDelta(SU) * ScaleTwo); 443ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick } 444ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 445ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick // These are platform specific things. 446ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick // Will need to go into the back end 447ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick // and accessed from here via a hook. 448ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick for (SDNode *N = SU->getNode(); N; N = N->getGluedNode()) { 449ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick if (N->isMachineOpcode()) { 450ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick const MCInstrDesc &TID = TII->get(N->getMachineOpcode()); 451ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick if (TID.isCall()) 452ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick ResCount += (PriorityThree + (ScaleThree*N->getNumValues())); 453ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick } 454ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick else 455ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick switch (N->getOpcode()) { 456ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick default: break; 457ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick case ISD::TokenFactor: 458ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick case ISD::CopyFromReg: 459ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick case ISD::CopyToReg: 460ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick ResCount += PriorityFive; 461ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick break; 462ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 463ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick case ISD::INLINEASM: 464ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick ResCount += PriorityFour; 465ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick break; 466ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick } 467ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick } 468ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick return ResCount; 469ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick} 470ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 471ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 472ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick/// Main resource tracking point. 473953be893e8cffa0ef9bf410036cd96aeb526e98aAndrew Trickvoid ResourcePriorityQueue::scheduledNode(SUnit *SU) { 474ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick // Use NULL entry as an event marker to reset 475ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick // the DFA state. 476ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick if (!SU) { 477ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick ResourcesModel->clearResources(); 478ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick Packet.clear(); 479ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick return; 480ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick } 481ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 482ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick const SDNode *ScegN = SU->getNode(); 483ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick // Update reg pressure tracking. 484ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick // First update current node. 485ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick if (ScegN->isMachineOpcode()) { 486ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick // Estimate generated regs. 487ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick for (unsigned i = 0, e = ScegN->getNumValues(); i != e; ++i) { 488a61b17c18a67f1b3faef2f2108379c4337ce9bb7Patrik Hagglund MVT VT = ScegN->getSimpleValueType(i); 489ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 490ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick if (TLI->isTypeLegal(VT)) { 491ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick const TargetRegisterClass *RC = TLI->getRegClassFor(VT); 492ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick if (RC) 493ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick RegPressure[RC->getID()] += numberRCValSuccInSU(SU, RC->getID()); 494ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick } 495ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick } 496ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick // Estimate killed regs. 497ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick for (unsigned i = 0, e = ScegN->getNumOperands(); i != e; ++i) { 498ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick const SDValue &Op = ScegN->getOperand(i); 499a61b17c18a67f1b3faef2f2108379c4337ce9bb7Patrik Hagglund MVT VT = Op.getNode()->getSimpleValueType(Op.getResNo()); 500ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 501ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick if (TLI->isTypeLegal(VT)) { 502ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick const TargetRegisterClass *RC = TLI->getRegClassFor(VT); 503ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick if (RC) { 504ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick if (RegPressure[RC->getID()] > 505ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick (numberRCValPredInSU(SU, RC->getID()))) 506ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick RegPressure[RC->getID()] -= numberRCValPredInSU(SU, RC->getID()); 507ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick else RegPressure[RC->getID()] = 0; 508ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick } 509ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick } 510ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick } 511ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 512ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick I != E; ++I) { 513ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick if (I->isCtrl() || (I->getSUnit()->NumRegDefsLeft == 0)) 514ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick continue; 515ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick --I->getSUnit()->NumRegDefsLeft; 516ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick } 517ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick } 518ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 519ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick // Reserve resources for this SU. 520ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick reserveResources(SU); 521ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 522ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick // Adjust number of parallel live ranges. 523ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick // Heuristic is simple - node with no data successors reduces 524ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick // number of live ranges. All others, increase it. 525ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick unsigned NumberNonControlDeps = 0; 526ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 527ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 528ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick I != E; ++I) { 529ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick adjustPriorityOfUnscheduledPreds(I->getSUnit()); 530ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick if (!I->isCtrl()) 531ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick NumberNonControlDeps++; 532ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick } 533ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 534ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick if (!NumberNonControlDeps) { 535ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick if (ParallelLiveRanges >= SU->NumPreds) 536ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick ParallelLiveRanges -= SU->NumPreds; 537ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick else 538ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick ParallelLiveRanges = 0; 539ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 540ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick } 541ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick else 542ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick ParallelLiveRanges += SU->NumRegDefsLeft; 543ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 544ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick // Track parallel live chains. 545ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick HorizontalVerticalBalance += (SU->Succs.size() - numberCtrlDepsInSU(SU)); 546ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick HorizontalVerticalBalance -= (SU->Preds.size() - numberCtrlPredInSU(SU)); 547ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick} 548ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 549ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trickvoid ResourcePriorityQueue::initNumRegDefsLeft(SUnit *SU) { 550ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick unsigned NodeNumDefs = 0; 551ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick for (SDNode *N = SU->getNode(); N; N = N->getGluedNode()) 552ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick if (N->isMachineOpcode()) { 553ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick const MCInstrDesc &TID = TII->get(N->getMachineOpcode()); 554ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick // No register need be allocated for this. 555ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick if (N->getMachineOpcode() == TargetOpcode::IMPLICIT_DEF) { 556ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick NodeNumDefs = 0; 557ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick break; 558ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick } 559ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick NodeNumDefs = std::min(N->getNumValues(), TID.getNumDefs()); 560ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick } 561ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick else 562ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick switch(N->getOpcode()) { 563ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick default: break; 564ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick case ISD::CopyFromReg: 565ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick NodeNumDefs++; 566ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick break; 567ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick case ISD::INLINEASM: 568ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick NodeNumDefs++; 569ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick break; 570ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick } 571ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 572ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick SU->NumRegDefsLeft = NodeNumDefs; 573ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick} 574ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 575ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick/// adjustPriorityOfUnscheduledPreds - One of the predecessors of SU was just 576ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick/// scheduled. If SU is not itself available, then there is at least one 577ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick/// predecessor node that has not been scheduled yet. If SU has exactly ONE 578ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick/// unscheduled predecessor, we want to increase its priority: it getting 579ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick/// scheduled will make this node available, so it is better than some other 580ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick/// node of the same priority that will not make a node available. 581ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trickvoid ResourcePriorityQueue::adjustPriorityOfUnscheduledPreds(SUnit *SU) { 582ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick if (SU->isAvailable) return; // All preds scheduled. 583ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 584ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick SUnit *OnlyAvailablePred = getSingleUnscheduledPred(SU); 585ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick if (OnlyAvailablePred == 0 || !OnlyAvailablePred->isAvailable) 586ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick return; 587ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 588ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick // Okay, we found a single predecessor that is available, but not scheduled. 589ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick // Since it is available, it must be in the priority queue. First remove it. 590ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick remove(OnlyAvailablePred); 591ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 592ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick // Reinsert the node into the priority queue, which recomputes its 593ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick // NumNodesSolelyBlocking value. 594ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick push(OnlyAvailablePred); 595ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick} 596ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 597ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 598ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick/// Main access point - returns next instructions 599ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick/// to be placed in scheduling sequence. 600ee498d3254b86bceb4f441741e9f442990647ce6Andrew TrickSUnit *ResourcePriorityQueue::pop() { 601ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick if (empty()) 602ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick return 0; 603ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 604ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick std::vector<SUnit *>::iterator Best = Queue.begin(); 605ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick if (!DisableDFASched) { 606ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick signed BestCost = SUSchedulingCost(*Best); 607f94e8c4cafc6a2ce7ff5c0c46084d3c38c2921f6Jakub Staszak for (std::vector<SUnit *>::iterator I = llvm::next(Queue.begin()), 608ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick E = Queue.end(); I != E; ++I) { 609ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 610ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick if (SUSchedulingCost(*I) > BestCost) { 611ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick BestCost = SUSchedulingCost(*I); 612ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick Best = I; 613ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick } 614ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick } 615ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick } 616ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick // Use default TD scheduling mechanism. 617ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick else { 618ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick for (std::vector<SUnit *>::iterator I = llvm::next(Queue.begin()), 619ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick E = Queue.end(); I != E; ++I) 620ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick if (Picker(*Best, *I)) 621ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick Best = I; 622ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick } 623ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 624ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick SUnit *V = *Best; 625ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick if (Best != prior(Queue.end())) 626ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick std::swap(*Best, Queue.back()); 627ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 628ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick Queue.pop_back(); 629ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 630ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick return V; 631ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick} 632ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 633ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 634ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trickvoid ResourcePriorityQueue::remove(SUnit *SU) { 635ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick assert(!Queue.empty() && "Queue is empty!"); 636ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick std::vector<SUnit *>::iterator I = std::find(Queue.begin(), Queue.end(), SU); 637ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick if (I != prior(Queue.end())) 638ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick std::swap(*I, Queue.back()); 639ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 640ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick Queue.pop_back(); 641ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick} 642ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 643ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 644ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick#ifdef NDEBUG 645ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trickvoid ResourcePriorityQueue::dump(ScheduleDAG *DAG) const {} 646ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick#else 647ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trickvoid ResourcePriorityQueue::dump(ScheduleDAG *DAG) const { 648ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick ResourcePriorityQueue q = *this; 649ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick while (!q.empty()) { 650ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick SUnit *su = q.pop(); 651ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick dbgs() << "Height " << su->getHeight() << ": "; 652ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick su->dump(DAG); 653ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick } 654ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick} 655ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick#endif 656