ScheduleDAGSDNodes.cpp revision 221345
1250003Sadrian//===--- ScheduleDAGSDNodes.cpp - Implement the ScheduleDAGSDNodes class --===// 2250003Sadrian// 3250003Sadrian// The LLVM Compiler Infrastructure 4250003Sadrian// 5250003Sadrian// This file is distributed under the University of Illinois Open Source 6250003Sadrian// License. See LICENSE.TXT for details. 7250003Sadrian// 8250003Sadrian//===----------------------------------------------------------------------===// 9250003Sadrian// 10250003Sadrian// This implements the ScheduleDAG class, which is a base class used by 11250003Sadrian// scheduling implementation classes. 12250003Sadrian// 13250003Sadrian//===----------------------------------------------------------------------===// 14250003Sadrian 15250003Sadrian#define DEBUG_TYPE "pre-RA-sched" 16250003Sadrian#include "SDNodeDbgValue.h" 17250003Sadrian#include "ScheduleDAGSDNodes.h" 18250003Sadrian#include "InstrEmitter.h" 19250003Sadrian#include "llvm/CodeGen/SelectionDAG.h" 20250003Sadrian#include "llvm/Target/TargetMachine.h" 21250003Sadrian#include "llvm/Target/TargetInstrInfo.h" 22250003Sadrian#include "llvm/Target/TargetLowering.h" 23250003Sadrian#include "llvm/Target/TargetRegisterInfo.h" 24250003Sadrian#include "llvm/Target/TargetSubtarget.h" 25250003Sadrian#include "llvm/ADT/DenseMap.h" 26250003Sadrian#include "llvm/ADT/SmallPtrSet.h" 27250003Sadrian#include "llvm/ADT/SmallSet.h" 28250003Sadrian#include "llvm/ADT/SmallVector.h" 29250003Sadrian#include "llvm/ADT/Statistic.h" 30250003Sadrian#include "llvm/Support/CommandLine.h" 31250003Sadrian#include "llvm/Support/Debug.h" 32250003Sadrian#include "llvm/Support/raw_ostream.h" 33250003Sadrianusing namespace llvm; 34250003Sadrian 35250003SadrianSTATISTIC(LoadsClustered, "Number of loads clustered together"); 36250003Sadrian 37250003Sadrian// This allows latency based scheduler to notice high latency instructions 38250003Sadrian// without a target itinerary. The choise if number here has more to do with 39250003Sadrian// balancing scheduler heursitics than with the actual machine latency. 40250003Sadrianstatic cl::opt<int> HighLatencyCycles( 41250003Sadrian "sched-high-latency-cycles", cl::Hidden, cl::init(10), 42250003Sadrian cl::desc("Roughly estimate the number of cycles that 'long latency'" 43250003Sadrian "instructions take for targets with no itinerary")); 44250003Sadrian 45250003SadrianScheduleDAGSDNodes::ScheduleDAGSDNodes(MachineFunction &mf) 46250003Sadrian : ScheduleDAG(mf), 47250003Sadrian InstrItins(mf.getTarget().getInstrItineraryData()) {} 48250003Sadrian 49250003Sadrian/// Run - perform scheduling. 50250003Sadrian/// 51250003Sadrianvoid ScheduleDAGSDNodes::Run(SelectionDAG *dag, MachineBasicBlock *bb, 52250003Sadrian MachineBasicBlock::iterator insertPos) { 53250003Sadrian DAG = dag; 54250003Sadrian ScheduleDAG::Run(bb, insertPos); 55250003Sadrian} 56250003Sadrian 57250003Sadrian/// NewSUnit - Creates a new SUnit and return a ptr to it. 58250003Sadrian/// 59250003SadrianSUnit *ScheduleDAGSDNodes::NewSUnit(SDNode *N) { 60250003Sadrian#ifndef NDEBUG 61250003Sadrian const SUnit *Addr = 0; 62250003Sadrian if (!SUnits.empty()) 63250003Sadrian Addr = &SUnits[0]; 64250003Sadrian#endif 65250003Sadrian SUnits.push_back(SUnit(N, (unsigned)SUnits.size())); 66250003Sadrian assert((Addr == 0 || Addr == &SUnits[0]) && 67250003Sadrian "SUnits std::vector reallocated on the fly!"); 68250003Sadrian SUnits.back().OrigNode = &SUnits.back(); 69250003Sadrian SUnit *SU = &SUnits.back(); 70250003Sadrian const TargetLowering &TLI = DAG->getTargetLoweringInfo(); 71250003Sadrian if (!N || 72250003Sadrian (N->isMachineOpcode() && 73250003Sadrian N->getMachineOpcode() == TargetOpcode::IMPLICIT_DEF)) 74250003Sadrian SU->SchedulingPref = Sched::None; 75250003Sadrian else 76250003Sadrian SU->SchedulingPref = TLI.getSchedulingPreference(N); 77250003Sadrian return SU; 78250003Sadrian} 79250003Sadrian 80250003SadrianSUnit *ScheduleDAGSDNodes::Clone(SUnit *Old) { 81250003Sadrian SUnit *SU = NewSUnit(Old->getNode()); 82250003Sadrian SU->OrigNode = Old->OrigNode; 83250003Sadrian SU->Latency = Old->Latency; 84250003Sadrian SU->isVRegCycle = Old->isVRegCycle; 85250003Sadrian SU->isCall = Old->isCall; 86250003Sadrian SU->isCallOp = Old->isCallOp; 87250003Sadrian SU->isTwoAddress = Old->isTwoAddress; 88250003Sadrian SU->isCommutable = Old->isCommutable; 89250003Sadrian SU->hasPhysRegDefs = Old->hasPhysRegDefs; 90250003Sadrian SU->hasPhysRegClobbers = Old->hasPhysRegClobbers; 91250003Sadrian SU->isScheduleHigh = Old->isScheduleHigh; 92250003Sadrian SU->isScheduleLow = Old->isScheduleLow; 93250003Sadrian SU->SchedulingPref = Old->SchedulingPref; 94250003Sadrian Old->isCloned = true; 95250003Sadrian return SU; 96250003Sadrian} 97250003Sadrian 98250003Sadrian/// CheckForPhysRegDependency - Check if the dependency between def and use of 99250003Sadrian/// a specified operand is a physical register dependency. If so, returns the 100250003Sadrian/// register and the cost of copying the register. 101250003Sadrianstatic void CheckForPhysRegDependency(SDNode *Def, SDNode *User, unsigned Op, 102250003Sadrian const TargetRegisterInfo *TRI, 103250003Sadrian const TargetInstrInfo *TII, 104250003Sadrian unsigned &PhysReg, int &Cost) { 105250003Sadrian if (Op != 2 || User->getOpcode() != ISD::CopyToReg) 106250003Sadrian return; 107250003Sadrian 108250003Sadrian unsigned Reg = cast<RegisterSDNode>(User->getOperand(1))->getReg(); 109250003Sadrian if (TargetRegisterInfo::isVirtualRegister(Reg)) 110250003Sadrian return; 111250003Sadrian 112250003Sadrian unsigned ResNo = User->getOperand(2).getResNo(); 113250003Sadrian if (Def->isMachineOpcode()) { 114250003Sadrian const TargetInstrDesc &II = TII->get(Def->getMachineOpcode()); 115250003Sadrian if (ResNo >= II.getNumDefs() && 116250003Sadrian II.ImplicitDefs[ResNo - II.getNumDefs()] == Reg) { 117250003Sadrian PhysReg = Reg; 118250003Sadrian const TargetRegisterClass *RC = 119250003Sadrian TRI->getMinimalPhysRegClass(Reg, Def->getValueType(ResNo)); 120250003Sadrian Cost = RC->getCopyCost(); 121250003Sadrian } 122250003Sadrian } 123250003Sadrian} 124250003Sadrian 125250003Sadrianstatic void AddGlue(SDNode *N, SDValue Glue, bool AddGlue, SelectionDAG *DAG) { 126250003Sadrian SmallVector<EVT, 4> VTs; 127250003Sadrian SDNode *GlueDestNode = Glue.getNode(); 128250003Sadrian 129250003Sadrian // Don't add glue from a node to itself. 130250003Sadrian if (GlueDestNode == N) return; 131250003Sadrian 132250003Sadrian // Don't add glue to something which already has glue. 133250003Sadrian if (N->getValueType(N->getNumValues() - 1) == MVT::Glue) return; 134250003Sadrian 135250003Sadrian for (unsigned I = 0, E = N->getNumValues(); I != E; ++I) 136250003Sadrian VTs.push_back(N->getValueType(I)); 137250003Sadrian 138250003Sadrian if (AddGlue) 139250003Sadrian VTs.push_back(MVT::Glue); 140250003Sadrian 141250003Sadrian SmallVector<SDValue, 4> Ops; 142250003Sadrian for (unsigned I = 0, E = N->getNumOperands(); I != E; ++I) 143250003Sadrian Ops.push_back(N->getOperand(I)); 144250003Sadrian 145250003Sadrian if (GlueDestNode) 146250003Sadrian Ops.push_back(Glue); 147250003Sadrian 148250003Sadrian SDVTList VTList = DAG->getVTList(&VTs[0], VTs.size()); 149250003Sadrian MachineSDNode::mmo_iterator Begin = 0, End = 0; 150250003Sadrian MachineSDNode *MN = dyn_cast<MachineSDNode>(N); 151250003Sadrian 152250003Sadrian // Store memory references. 153250003Sadrian if (MN) { 154250003Sadrian Begin = MN->memoperands_begin(); 155250003Sadrian End = MN->memoperands_end(); 156250003Sadrian } 157250003Sadrian 158250003Sadrian DAG->MorphNodeTo(N, N->getOpcode(), VTList, &Ops[0], Ops.size()); 159250003Sadrian 160250003Sadrian // Reset the memory references 161250003Sadrian if (MN) 162250003Sadrian MN->setMemRefs(Begin, End); 163250003Sadrian} 164250003Sadrian 165250003Sadrian/// ClusterNeighboringLoads - Force nearby loads together by "gluing" them. 166250003Sadrian/// This function finds loads of the same base and different offsets. If the 167250003Sadrian/// offsets are not far apart (target specific), it add MVT::Glue inputs and 168250003Sadrian/// outputs to ensure they are scheduled together and in order. This 169250003Sadrian/// optimization may benefit some targets by improving cache locality. 170250003Sadrianvoid ScheduleDAGSDNodes::ClusterNeighboringLoads(SDNode *Node) { 171250003Sadrian SDNode *Chain = 0; 172250003Sadrian unsigned NumOps = Node->getNumOperands(); 173250003Sadrian if (Node->getOperand(NumOps-1).getValueType() == MVT::Other) 174250003Sadrian Chain = Node->getOperand(NumOps-1).getNode(); 175250003Sadrian if (!Chain) 176250003Sadrian return; 177250003Sadrian 178250003Sadrian // Look for other loads of the same chain. Find loads that are loading from 179250003Sadrian // the same base pointer and different offsets. 180250003Sadrian SmallPtrSet<SDNode*, 16> Visited; 181250003Sadrian SmallVector<int64_t, 4> Offsets; 182250003Sadrian DenseMap<long long, SDNode*> O2SMap; // Map from offset to SDNode. 183250003Sadrian bool Cluster = false; 184250003Sadrian SDNode *Base = Node; 185250003Sadrian for (SDNode::use_iterator I = Chain->use_begin(), E = Chain->use_end(); 186250003Sadrian I != E; ++I) { 187250003Sadrian SDNode *User = *I; 188250003Sadrian if (User == Node || !Visited.insert(User)) 189250003Sadrian continue; 190250003Sadrian int64_t Offset1, Offset2; 191250003Sadrian if (!TII->areLoadsFromSameBasePtr(Base, User, Offset1, Offset2) || 192250003Sadrian Offset1 == Offset2) 193250003Sadrian // FIXME: Should be ok if they addresses are identical. But earlier 194250003Sadrian // optimizations really should have eliminated one of the loads. 195250003Sadrian continue; 196250003Sadrian if (O2SMap.insert(std::make_pair(Offset1, Base)).second) 197250003Sadrian Offsets.push_back(Offset1); 198250003Sadrian O2SMap.insert(std::make_pair(Offset2, User)); 199250003Sadrian Offsets.push_back(Offset2); 200250003Sadrian if (Offset2 < Offset1) 201250003Sadrian Base = User; 202250003Sadrian Cluster = true; 203250003Sadrian } 204250003Sadrian 205250003Sadrian if (!Cluster) 206250003Sadrian return; 207250003Sadrian 208250003Sadrian // Sort them in increasing order. 209250003Sadrian std::sort(Offsets.begin(), Offsets.end()); 210250003Sadrian 211250003Sadrian // Check if the loads are close enough. 212250003Sadrian SmallVector<SDNode*, 4> Loads; 213250003Sadrian unsigned NumLoads = 0; 214250003Sadrian int64_t BaseOff = Offsets[0]; 215250003Sadrian SDNode *BaseLoad = O2SMap[BaseOff]; 216250003Sadrian Loads.push_back(BaseLoad); 217250003Sadrian for (unsigned i = 1, e = Offsets.size(); i != e; ++i) { 218250003Sadrian int64_t Offset = Offsets[i]; 219250003Sadrian SDNode *Load = O2SMap[Offset]; 220250003Sadrian if (!TII->shouldScheduleLoadsNear(BaseLoad, Load, BaseOff, Offset,NumLoads)) 221250003Sadrian break; // Stop right here. Ignore loads that are further away. 222250003Sadrian Loads.push_back(Load); 223250003Sadrian ++NumLoads; 224250003Sadrian } 225250003Sadrian 226250003Sadrian if (NumLoads == 0) 227250003Sadrian return; 228250003Sadrian 229250003Sadrian // Cluster loads by adding MVT::Glue outputs and inputs. This also 230250003Sadrian // ensure they are scheduled in order of increasing addresses. 231250003Sadrian SDNode *Lead = Loads[0]; 232250003Sadrian AddGlue(Lead, SDValue(0, 0), true, DAG); 233250003Sadrian 234250003Sadrian SDValue InGlue = SDValue(Lead, Lead->getNumValues() - 1); 235250003Sadrian for (unsigned I = 1, E = Loads.size(); I != E; ++I) { 236250003Sadrian bool OutGlue = I < E - 1; 237250003Sadrian SDNode *Load = Loads[I]; 238250003Sadrian 239250003Sadrian AddGlue(Load, InGlue, OutGlue, DAG); 240250003Sadrian 241250003Sadrian if (OutGlue) 242250003Sadrian InGlue = SDValue(Load, Load->getNumValues() - 1); 243250003Sadrian 244250003Sadrian ++LoadsClustered; 245250003Sadrian } 246250003Sadrian} 247250003Sadrian 248250003Sadrian/// ClusterNodes - Cluster certain nodes which should be scheduled together. 249250003Sadrian/// 250250003Sadrianvoid ScheduleDAGSDNodes::ClusterNodes() { 251250003Sadrian for (SelectionDAG::allnodes_iterator NI = DAG->allnodes_begin(), 252250003Sadrian E = DAG->allnodes_end(); NI != E; ++NI) { 253250003Sadrian SDNode *Node = &*NI; 254250003Sadrian if (!Node || !Node->isMachineOpcode()) 255250003Sadrian continue; 256250003Sadrian 257250003Sadrian unsigned Opc = Node->getMachineOpcode(); 258250003Sadrian const TargetInstrDesc &TID = TII->get(Opc); 259250003Sadrian if (TID.mayLoad()) 260250003Sadrian // Cluster loads from "near" addresses into combined SUnits. 261250003Sadrian ClusterNeighboringLoads(Node); 262250003Sadrian } 263250003Sadrian} 264250003Sadrian 265250003Sadrianvoid ScheduleDAGSDNodes::BuildSchedUnits() { 266250003Sadrian // During scheduling, the NodeId field of SDNode is used to map SDNodes 267250003Sadrian // to their associated SUnits by holding SUnits table indices. A value 268250003Sadrian // of -1 means the SDNode does not yet have an associated SUnit. 269250003Sadrian unsigned NumNodes = 0; 270250003Sadrian for (SelectionDAG::allnodes_iterator NI = DAG->allnodes_begin(), 271250003Sadrian E = DAG->allnodes_end(); NI != E; ++NI) { 272250003Sadrian NI->setNodeId(-1); 273250003Sadrian ++NumNodes; 274250003Sadrian } 275250003Sadrian 276250003Sadrian // Reserve entries in the vector for each of the SUnits we are creating. This 277250003Sadrian // ensure that reallocation of the vector won't happen, so SUnit*'s won't get 278250003Sadrian // invalidated. 279250003Sadrian // FIXME: Multiply by 2 because we may clone nodes during scheduling. 280250003Sadrian // This is a temporary workaround. 281250003Sadrian SUnits.reserve(NumNodes * 2); 282250003Sadrian 283250003Sadrian // Add all nodes in depth first order. 284250003Sadrian SmallVector<SDNode*, 64> Worklist; 285250003Sadrian SmallPtrSet<SDNode*, 64> Visited; 286250003Sadrian Worklist.push_back(DAG->getRoot().getNode()); 287250003Sadrian Visited.insert(DAG->getRoot().getNode()); 288250003Sadrian 289250003Sadrian SmallVector<SUnit*, 8> CallSUnits; 290250003Sadrian while (!Worklist.empty()) { 291250003Sadrian SDNode *NI = Worklist.pop_back_val(); 292250003Sadrian 293250003Sadrian // Add all operands to the worklist unless they've already been added. 294250003Sadrian for (unsigned i = 0, e = NI->getNumOperands(); i != e; ++i) 295250003Sadrian if (Visited.insert(NI->getOperand(i).getNode())) 296250003Sadrian Worklist.push_back(NI->getOperand(i).getNode()); 297250003Sadrian 298250003Sadrian if (isPassiveNode(NI)) // Leaf node, e.g. a TargetImmediate. 299250003Sadrian continue; 300250003Sadrian 301250003Sadrian // If this node has already been processed, stop now. 302250003Sadrian if (NI->getNodeId() != -1) continue; 303250003Sadrian 304250003Sadrian SUnit *NodeSUnit = NewSUnit(NI); 305250003Sadrian 306250003Sadrian // See if anything is glued to this node, if so, add them to glued 307250003Sadrian // nodes. Nodes can have at most one glue input and one glue output. Glue 308250003Sadrian // is required to be the last operand and result of a node. 309250003Sadrian 310250003Sadrian // Scan up to find glued preds. 311250003Sadrian SDNode *N = NI; 312250003Sadrian while (N->getNumOperands() && 313250003Sadrian N->getOperand(N->getNumOperands()-1).getValueType() == MVT::Glue) { 314250003Sadrian N = N->getOperand(N->getNumOperands()-1).getNode(); 315250003Sadrian assert(N->getNodeId() == -1 && "Node already inserted!"); 316250003Sadrian N->setNodeId(NodeSUnit->NodeNum); 317250003Sadrian if (N->isMachineOpcode() && TII->get(N->getMachineOpcode()).isCall()) 318250003Sadrian NodeSUnit->isCall = true; 319250003Sadrian } 320250003Sadrian 321250003Sadrian // Scan down to find any glued succs. 322250003Sadrian N = NI; 323250003Sadrian while (N->getValueType(N->getNumValues()-1) == MVT::Glue) { 324250003Sadrian SDValue GlueVal(N, N->getNumValues()-1); 325250003Sadrian 326250003Sadrian // There are either zero or one users of the Glue result. 327250003Sadrian bool HasGlueUse = false; 328250003Sadrian for (SDNode::use_iterator UI = N->use_begin(), E = N->use_end(); 329250003Sadrian UI != E; ++UI) 330250003Sadrian if (GlueVal.isOperandOf(*UI)) { 331250003Sadrian HasGlueUse = true; 332250003Sadrian assert(N->getNodeId() == -1 && "Node already inserted!"); 333250003Sadrian N->setNodeId(NodeSUnit->NodeNum); 334250003Sadrian N = *UI; 335250003Sadrian if (N->isMachineOpcode() && TII->get(N->getMachineOpcode()).isCall()) 336250003Sadrian NodeSUnit->isCall = true; 337250003Sadrian break; 338250003Sadrian } 339250003Sadrian if (!HasGlueUse) break; 340250003Sadrian } 341250003Sadrian 342250003Sadrian if (NodeSUnit->isCall) 343250003Sadrian CallSUnits.push_back(NodeSUnit); 344250003Sadrian 345250003Sadrian // Schedule zero-latency TokenFactor below any nodes that may increase the 346250003Sadrian // schedule height. Otherwise, ancestors of the TokenFactor may appear to 347250003Sadrian // have false stalls. 348250003Sadrian if (NI->getOpcode() == ISD::TokenFactor) 349250003Sadrian NodeSUnit->isScheduleLow = true; 350250003Sadrian 351250003Sadrian // If there are glue operands involved, N is now the bottom-most node 352250003Sadrian // of the sequence of nodes that are glued together. 353250003Sadrian // Update the SUnit. 354250003Sadrian NodeSUnit->setNode(N); 355250003Sadrian assert(N->getNodeId() == -1 && "Node already inserted!"); 356250003Sadrian N->setNodeId(NodeSUnit->NodeNum); 357250003Sadrian 358250003Sadrian // Compute NumRegDefsLeft. This must be done before AddSchedEdges. 359250003Sadrian InitNumRegDefsLeft(NodeSUnit); 360250003Sadrian 361250003Sadrian // Assign the Latency field of NodeSUnit using target-provided information. 362250003Sadrian ComputeLatency(NodeSUnit); 363250003Sadrian } 364250003Sadrian 365250003Sadrian // Find all call operands. 366250003Sadrian while (!CallSUnits.empty()) { 367250003Sadrian SUnit *SU = CallSUnits.pop_back_val(); 368250003Sadrian for (const SDNode *SUNode = SU->getNode(); SUNode; 369250003Sadrian SUNode = SUNode->getGluedNode()) { 370250003Sadrian if (SUNode->getOpcode() != ISD::CopyToReg) 371250003Sadrian continue; 372250003Sadrian SDNode *SrcN = SUNode->getOperand(2).getNode(); 373250003Sadrian if (isPassiveNode(SrcN)) continue; // Not scheduled. 374250003Sadrian SUnit *SrcSU = &SUnits[SrcN->getNodeId()]; 375250003Sadrian SrcSU->isCallOp = true; 376250003Sadrian } 377250003Sadrian } 378250003Sadrian} 379250003Sadrian 380250003Sadrianvoid ScheduleDAGSDNodes::AddSchedEdges() { 381250003Sadrian const TargetSubtarget &ST = TM.getSubtarget<TargetSubtarget>(); 382250003Sadrian 383250003Sadrian // Check to see if the scheduler cares about latencies. 384250003Sadrian bool UnitLatencies = ForceUnitLatencies(); 385250003Sadrian 386250003Sadrian // Pass 2: add the preds, succs, etc. 387250003Sadrian for (unsigned su = 0, e = SUnits.size(); su != e; ++su) { 388250003Sadrian SUnit *SU = &SUnits[su]; 389250003Sadrian SDNode *MainNode = SU->getNode(); 390250003Sadrian 391250003Sadrian if (MainNode->isMachineOpcode()) { 392250003Sadrian unsigned Opc = MainNode->getMachineOpcode(); 393250003Sadrian const TargetInstrDesc &TID = TII->get(Opc); 394250003Sadrian for (unsigned i = 0; i != TID.getNumOperands(); ++i) { 395250003Sadrian if (TID.getOperandConstraint(i, TOI::TIED_TO) != -1) { 396250003Sadrian SU->isTwoAddress = true; 397250003Sadrian break; 398250003Sadrian } 399250003Sadrian } 400250003Sadrian if (TID.isCommutable()) 401250003Sadrian SU->isCommutable = true; 402250003Sadrian } 403250003Sadrian 404250003Sadrian // Find all predecessors and successors of the group. 405250003Sadrian for (SDNode *N = SU->getNode(); N; N = N->getGluedNode()) { 406250003Sadrian if (N->isMachineOpcode() && 407250003Sadrian TII->get(N->getMachineOpcode()).getImplicitDefs()) { 408250003Sadrian SU->hasPhysRegClobbers = true; 409250003Sadrian unsigned NumUsed = InstrEmitter::CountResults(N); 410250003Sadrian while (NumUsed != 0 && !N->hasAnyUseOfValue(NumUsed - 1)) 411250003Sadrian --NumUsed; // Skip over unused values at the end. 412250003Sadrian if (NumUsed > TII->get(N->getMachineOpcode()).getNumDefs()) 413250003Sadrian SU->hasPhysRegDefs = true; 414250003Sadrian } 415250003Sadrian 416250003Sadrian for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) { 417250003Sadrian SDNode *OpN = N->getOperand(i).getNode(); 418250003Sadrian if (isPassiveNode(OpN)) continue; // Not scheduled. 419250003Sadrian SUnit *OpSU = &SUnits[OpN->getNodeId()]; 420250003Sadrian assert(OpSU && "Node has no SUnit!"); 421250003Sadrian if (OpSU == SU) continue; // In the same group. 422250003Sadrian 423250003Sadrian EVT OpVT = N->getOperand(i).getValueType(); 424250003Sadrian assert(OpVT != MVT::Glue && "Glued nodes should be in same sunit!"); 425250003Sadrian bool isChain = OpVT == MVT::Other; 426250003Sadrian 427250003Sadrian unsigned PhysReg = 0; 428250003Sadrian int Cost = 1; 429250003Sadrian // Determine if this is a physical register dependency. 430250003Sadrian CheckForPhysRegDependency(OpN, N, i, TRI, TII, PhysReg, Cost); 431250003Sadrian assert((PhysReg == 0 || !isChain) && 432250003Sadrian "Chain dependence via physreg data?"); 433250003Sadrian // FIXME: See ScheduleDAGSDNodes::EmitCopyFromReg. For now, scheduler 434250003Sadrian // emits a copy from the physical register to a virtual register unless 435250003Sadrian // it requires a cross class copy (cost < 0). That means we are only 436250003Sadrian // treating "expensive to copy" register dependency as physical register 437250003Sadrian // dependency. This may change in the future though. 438250003Sadrian if (Cost >= 0) 439250003Sadrian PhysReg = 0; 440250003Sadrian 441250003Sadrian // If this is a ctrl dep, latency is 1. 442250003Sadrian unsigned OpLatency = isChain ? 1 : OpSU->Latency; 443250003Sadrian // Special-case TokenFactor chains as zero-latency. 444250003Sadrian if(isChain && OpN->getOpcode() == ISD::TokenFactor) 445250003Sadrian OpLatency = 0; 446250003Sadrian 447250003Sadrian const SDep &dep = SDep(OpSU, isChain ? SDep::Order : SDep::Data, 448250003Sadrian OpLatency, PhysReg); 449250003Sadrian if (!isChain && !UnitLatencies) { 450250003Sadrian ComputeOperandLatency(OpN, N, i, const_cast<SDep &>(dep)); 451250003Sadrian ST.adjustSchedDependency(OpSU, SU, const_cast<SDep &>(dep)); 452250003Sadrian } 453250003Sadrian 454250003Sadrian if (!SU->addPred(dep) && !dep.isCtrl() && OpSU->NumRegDefsLeft > 1) { 455250003Sadrian // Multiple register uses are combined in the same SUnit. For example, 456250003Sadrian // we could have a set of glued nodes with all their defs consumed by 457250003Sadrian // another set of glued nodes. Register pressure tracking sees this as 458250003Sadrian // a single use, so to keep pressure balanced we reduce the defs. 459250003Sadrian // 460250003Sadrian // We can't tell (without more book-keeping) if this results from 461250003Sadrian // glued nodes or duplicate operands. As long as we don't reduce 462250003Sadrian // NumRegDefsLeft to zero, we handle the common cases well. 463250003Sadrian --OpSU->NumRegDefsLeft; 464250003Sadrian } 465250003Sadrian } 466250003Sadrian } 467250003Sadrian } 468250003Sadrian} 469250003Sadrian 470250003Sadrian/// BuildSchedGraph - Build the SUnit graph from the selection dag that we 471250003Sadrian/// are input. This SUnit graph is similar to the SelectionDAG, but 472250003Sadrian/// excludes nodes that aren't interesting to scheduling, and represents 473250003Sadrian/// glued together nodes with a single SUnit. 474250003Sadrianvoid ScheduleDAGSDNodes::BuildSchedGraph(AliasAnalysis *AA) { 475250003Sadrian // Cluster certain nodes which should be scheduled together. 476250003Sadrian ClusterNodes(); 477250003Sadrian // Populate the SUnits array. 478250003Sadrian BuildSchedUnits(); 479250003Sadrian // Compute all the scheduling dependencies between nodes. 480250003Sadrian AddSchedEdges(); 481250003Sadrian} 482250003Sadrian 483250003Sadrian// Initialize NumNodeDefs for the current Node's opcode. 484250003Sadrianvoid ScheduleDAGSDNodes::RegDefIter::InitNodeNumDefs() { 485250003Sadrian // Check for phys reg copy. 486250003Sadrian if (!Node) 487250003Sadrian return; 488250003Sadrian 489250003Sadrian if (!Node->isMachineOpcode()) { 490250003Sadrian if (Node->getOpcode() == ISD::CopyFromReg) 491250003Sadrian NodeNumDefs = 1; 492250003Sadrian else 493250003Sadrian NodeNumDefs = 0; 494250003Sadrian return; 495250003Sadrian } 496250003Sadrian unsigned POpc = Node->getMachineOpcode(); 497250003Sadrian if (POpc == TargetOpcode::IMPLICIT_DEF) { 498250003Sadrian // No register need be allocated for this. 499250003Sadrian NodeNumDefs = 0; 500250003Sadrian return; 501250003Sadrian } 502250003Sadrian unsigned NRegDefs = SchedDAG->TII->get(Node->getMachineOpcode()).getNumDefs(); 503250003Sadrian // Some instructions define regs that are not represented in the selection DAG 504250003Sadrian // (e.g. unused flags). See tMOVi8. Make sure we don't access past NumValues. 505250003Sadrian NodeNumDefs = std::min(Node->getNumValues(), NRegDefs); 506250003Sadrian DefIdx = 0; 507250003Sadrian} 508250003Sadrian 509250003Sadrian// Construct a RegDefIter for this SUnit and find the first valid value. 510250003SadrianScheduleDAGSDNodes::RegDefIter::RegDefIter(const SUnit *SU, 511250003Sadrian const ScheduleDAGSDNodes *SD) 512250003Sadrian : SchedDAG(SD), Node(SU->getNode()), DefIdx(0), NodeNumDefs(0) { 513250003Sadrian InitNodeNumDefs(); 514250003Sadrian Advance(); 515250003Sadrian} 516250003Sadrian 517250003Sadrian// Advance to the next valid value defined by the SUnit. 518250003Sadrianvoid ScheduleDAGSDNodes::RegDefIter::Advance() { 519250003Sadrian for (;Node;) { // Visit all glued nodes. 520250003Sadrian for (;DefIdx < NodeNumDefs; ++DefIdx) { 521250003Sadrian if (!Node->hasAnyUseOfValue(DefIdx)) 522250003Sadrian continue; 523250003Sadrian if (Node->isMachineOpcode() && 524250003Sadrian Node->getMachineOpcode() == TargetOpcode::EXTRACT_SUBREG) { 525250003Sadrian // Propagate the incoming (full-register) type. I doubt it's needed. 526250003Sadrian ValueType = Node->getOperand(0).getValueType(); 527250003Sadrian } 528250003Sadrian else { 529250003Sadrian ValueType = Node->getValueType(DefIdx); 530250003Sadrian } 531250003Sadrian ++DefIdx; 532250003Sadrian return; // Found a normal regdef. 533250003Sadrian } 534250003Sadrian Node = Node->getGluedNode(); 535250003Sadrian if (Node == NULL) { 536250003Sadrian return; // No values left to visit. 537250003Sadrian } 538250003Sadrian InitNodeNumDefs(); 539250003Sadrian } 540250003Sadrian} 541250003Sadrian 542250003Sadrianvoid ScheduleDAGSDNodes::InitNumRegDefsLeft(SUnit *SU) { 543250003Sadrian assert(SU->NumRegDefsLeft == 0 && "expect a new node"); 544250003Sadrian for (RegDefIter I(SU, this); I.IsValid(); I.Advance()) { 545250003Sadrian assert(SU->NumRegDefsLeft < USHRT_MAX && "overflow is ok but unexpected"); 546250003Sadrian ++SU->NumRegDefsLeft; 547250003Sadrian } 548250003Sadrian} 549250003Sadrian 550250003Sadrianvoid ScheduleDAGSDNodes::ComputeLatency(SUnit *SU) { 551250003Sadrian SDNode *N = SU->getNode(); 552250003Sadrian 553250003Sadrian // TokenFactor operands are considered zero latency, and some schedulers 554250003Sadrian // (e.g. Top-Down list) may rely on the fact that operand latency is nonzero 555250003Sadrian // whenever node latency is nonzero. 556250003Sadrian if (N && N->getOpcode() == ISD::TokenFactor) { 557250003Sadrian SU->Latency = 0; 558250003Sadrian return; 559250003Sadrian } 560250003Sadrian 561250003Sadrian // Check to see if the scheduler cares about latencies. 562250003Sadrian if (ForceUnitLatencies()) { 563250003Sadrian SU->Latency = 1; 564250003Sadrian return; 565250003Sadrian } 566250003Sadrian 567250003Sadrian if (!InstrItins || InstrItins->isEmpty()) { 568250003Sadrian if (N && N->isMachineOpcode() && 569250003Sadrian TII->isHighLatencyDef(N->getMachineOpcode())) 570250003Sadrian SU->Latency = HighLatencyCycles; 571250003Sadrian else 572250003Sadrian SU->Latency = 1; 573250003Sadrian return; 574250003Sadrian } 575250003Sadrian 576250003Sadrian // Compute the latency for the node. We use the sum of the latencies for 577250003Sadrian // all nodes glued together into this SUnit. 578250003Sadrian SU->Latency = 0; 579250003Sadrian for (SDNode *N = SU->getNode(); N; N = N->getGluedNode()) 580250003Sadrian if (N->isMachineOpcode()) 581250003Sadrian SU->Latency += TII->getInstrLatency(InstrItins, N); 582250003Sadrian} 583250003Sadrian 584250003Sadrianvoid ScheduleDAGSDNodes::ComputeOperandLatency(SDNode *Def, SDNode *Use, 585250003Sadrian unsigned OpIdx, SDep& dep) const{ 586250003Sadrian // Check to see if the scheduler cares about latencies. 587250003Sadrian if (ForceUnitLatencies()) 588250003Sadrian return; 589250003Sadrian 590250003Sadrian if (dep.getKind() != SDep::Data) 591250003Sadrian return; 592250003Sadrian 593250003Sadrian unsigned DefIdx = Use->getOperand(OpIdx).getResNo(); 594250003Sadrian if (Use->isMachineOpcode()) 595250003Sadrian // Adjust the use operand index by num of defs. 596250003Sadrian OpIdx += TII->get(Use->getMachineOpcode()).getNumDefs(); 597250003Sadrian int Latency = TII->getOperandLatency(InstrItins, Def, DefIdx, Use, OpIdx); 598250003Sadrian if (Latency > 1 && Use->getOpcode() == ISD::CopyToReg && 599250003Sadrian !BB->succ_empty()) { 600250003Sadrian unsigned Reg = cast<RegisterSDNode>(Use->getOperand(1))->getReg(); 601250003Sadrian if (TargetRegisterInfo::isVirtualRegister(Reg)) 602250003Sadrian // This copy is a liveout value. It is likely coalesced, so reduce the 603250003Sadrian // latency so not to penalize the def. 604250003Sadrian // FIXME: need target specific adjustment here? 605250003Sadrian Latency = (Latency > 1) ? Latency - 1 : 1; 606250003Sadrian } 607250003Sadrian if (Latency >= 0) 608250003Sadrian dep.setLatency(Latency); 609250003Sadrian} 610250003Sadrian 611250003Sadrianvoid ScheduleDAGSDNodes::dumpNode(const SUnit *SU) const { 612250003Sadrian if (!SU->getNode()) { 613250003Sadrian dbgs() << "PHYS REG COPY\n"; 614250003Sadrian return; 615250003Sadrian } 616250003Sadrian 617250003Sadrian SU->getNode()->dump(DAG); 618250003Sadrian dbgs() << "\n"; 619250003Sadrian SmallVector<SDNode *, 4> GluedNodes; 620250003Sadrian for (SDNode *N = SU->getNode()->getGluedNode(); N; N = N->getGluedNode()) 621250003Sadrian GluedNodes.push_back(N); 622250003Sadrian while (!GluedNodes.empty()) { 623250003Sadrian dbgs() << " "; 624250003Sadrian GluedNodes.back()->dump(DAG); 625250003Sadrian dbgs() << "\n"; 626250003Sadrian GluedNodes.pop_back(); 627250003Sadrian } 628250003Sadrian} 629250003Sadrian 630250003Sadriannamespace { 631250003Sadrian struct OrderSorter { 632250003Sadrian bool operator()(const std::pair<unsigned, MachineInstr*> &A, 633250003Sadrian const std::pair<unsigned, MachineInstr*> &B) { 634250003Sadrian return A.first < B.first; 635250003Sadrian } 636250003Sadrian }; 637250003Sadrian} 638250003Sadrian 639250003Sadrian/// ProcessSDDbgValues - Process SDDbgValues associated with this node. 640250003Sadrianstatic void ProcessSDDbgValues(SDNode *N, SelectionDAG *DAG, 641250003Sadrian InstrEmitter &Emitter, 642250003Sadrian SmallVector<std::pair<unsigned, MachineInstr*>, 32> &Orders, 643250003Sadrian DenseMap<SDValue, unsigned> &VRBaseMap, 644250003Sadrian unsigned Order) { 645250003Sadrian if (!N->getHasDebugValue()) 646250003Sadrian return; 647250003Sadrian 648250003Sadrian // Opportunistically insert immediate dbg_value uses, i.e. those with source 649250003Sadrian // order number right after the N. 650250003Sadrian MachineBasicBlock *BB = Emitter.getBlock(); 651250003Sadrian MachineBasicBlock::iterator InsertPos = Emitter.getInsertPos(); 652250003Sadrian SmallVector<SDDbgValue*,2> &DVs = DAG->GetDbgValues(N); 653250003Sadrian for (unsigned i = 0, e = DVs.size(); i != e; ++i) { 654250003Sadrian if (DVs[i]->isInvalidated()) 655250003Sadrian continue; 656250003Sadrian unsigned DVOrder = DVs[i]->getOrder(); 657250003Sadrian if (!Order || DVOrder == ++Order) { 658250003Sadrian MachineInstr *DbgMI = Emitter.EmitDbgValue(DVs[i], VRBaseMap); 659250003Sadrian if (DbgMI) { 660250003Sadrian Orders.push_back(std::make_pair(DVOrder, DbgMI)); 661250003Sadrian BB->insert(InsertPos, DbgMI); 662250003Sadrian } 663250003Sadrian DVs[i]->setIsInvalidated(); 664250003Sadrian } 665250003Sadrian } 666250003Sadrian} 667250003Sadrian 668250003Sadrian// ProcessSourceNode - Process nodes with source order numbers. These are added 669250003Sadrian// to a vector which EmitSchedule uses to determine how to insert dbg_value 670250003Sadrian// instructions in the right order. 671250003Sadrianstatic void ProcessSourceNode(SDNode *N, SelectionDAG *DAG, 672250003Sadrian InstrEmitter &Emitter, 673250003Sadrian DenseMap<SDValue, unsigned> &VRBaseMap, 674250003Sadrian SmallVector<std::pair<unsigned, MachineInstr*>, 32> &Orders, 675250003Sadrian SmallSet<unsigned, 8> &Seen) { 676250003Sadrian unsigned Order = DAG->GetOrdering(N); 677250003Sadrian if (!Order || !Seen.insert(Order)) { 678250003Sadrian // Process any valid SDDbgValues even if node does not have any order 679250003Sadrian // assigned. 680250003Sadrian ProcessSDDbgValues(N, DAG, Emitter, Orders, VRBaseMap, 0); 681250003Sadrian return; 682250003Sadrian } 683250003Sadrian 684250003Sadrian MachineBasicBlock *BB = Emitter.getBlock(); 685250003Sadrian if (Emitter.getInsertPos() == BB->begin() || BB->back().isPHI()) { 686250003Sadrian // Did not insert any instruction. 687250003Sadrian Orders.push_back(std::make_pair(Order, (MachineInstr*)0)); 688250003Sadrian return; 689250003Sadrian } 690250003Sadrian 691250003Sadrian Orders.push_back(std::make_pair(Order, prior(Emitter.getInsertPos()))); 692250003Sadrian ProcessSDDbgValues(N, DAG, Emitter, Orders, VRBaseMap, Order); 693250003Sadrian} 694250003Sadrian 695250003Sadrian 696250003Sadrian/// EmitSchedule - Emit the machine code in scheduled order. 697250003SadrianMachineBasicBlock *ScheduleDAGSDNodes::EmitSchedule() { 698250003Sadrian InstrEmitter Emitter(BB, InsertPos); 699250003Sadrian DenseMap<SDValue, unsigned> VRBaseMap; 700250003Sadrian DenseMap<SUnit*, unsigned> CopyVRBaseMap; 701250003Sadrian SmallVector<std::pair<unsigned, MachineInstr*>, 32> Orders; 702250003Sadrian SmallSet<unsigned, 8> Seen; 703250003Sadrian bool HasDbg = DAG->hasDebugValues(); 704250003Sadrian 705250003Sadrian // If this is the first BB, emit byval parameter dbg_value's. 706250003Sadrian if (HasDbg && BB->getParent()->begin() == MachineFunction::iterator(BB)) { 707250003Sadrian SDDbgInfo::DbgIterator PDI = DAG->ByvalParmDbgBegin(); 708250003Sadrian SDDbgInfo::DbgIterator PDE = DAG->ByvalParmDbgEnd(); 709250003Sadrian for (; PDI != PDE; ++PDI) { 710250003Sadrian MachineInstr *DbgMI= Emitter.EmitDbgValue(*PDI, VRBaseMap); 711250003Sadrian if (DbgMI) 712250003Sadrian BB->insert(InsertPos, DbgMI); 713250003Sadrian } 714250003Sadrian } 715250003Sadrian 716250003Sadrian for (unsigned i = 0, e = Sequence.size(); i != e; i++) { 717250003Sadrian SUnit *SU = Sequence[i]; 718250003Sadrian if (!SU) { 719250003Sadrian // Null SUnit* is a noop. 720250003Sadrian EmitNoop(); 721250003Sadrian continue; 722250003Sadrian } 723250003Sadrian 724250003Sadrian // For pre-regalloc scheduling, create instructions corresponding to the 725250003Sadrian // SDNode and any glued SDNodes and append them to the block. 726250003Sadrian if (!SU->getNode()) { 727250003Sadrian // Emit a copy. 728250003Sadrian EmitPhysRegCopy(SU, CopyVRBaseMap); 729250003Sadrian continue; 730250003Sadrian } 731250003Sadrian 732250003Sadrian SmallVector<SDNode *, 4> GluedNodes; 733250003Sadrian for (SDNode *N = SU->getNode()->getGluedNode(); N; 734250003Sadrian N = N->getGluedNode()) 735250003Sadrian GluedNodes.push_back(N); 736250003Sadrian while (!GluedNodes.empty()) { 737250003Sadrian SDNode *N = GluedNodes.back(); 738250003Sadrian Emitter.EmitNode(GluedNodes.back(), SU->OrigNode != SU, SU->isCloned, 739250003Sadrian VRBaseMap); 740250003Sadrian // Remember the source order of the inserted instruction. 741250003Sadrian if (HasDbg) 742250003Sadrian ProcessSourceNode(N, DAG, Emitter, VRBaseMap, Orders, Seen); 743250003Sadrian GluedNodes.pop_back(); 744250003Sadrian } 745250003Sadrian Emitter.EmitNode(SU->getNode(), SU->OrigNode != SU, SU->isCloned, 746250003Sadrian VRBaseMap); 747250003Sadrian // Remember the source order of the inserted instruction. 748250003Sadrian if (HasDbg) 749250003Sadrian ProcessSourceNode(SU->getNode(), DAG, Emitter, VRBaseMap, Orders, 750250003Sadrian Seen); 751250003Sadrian } 752250003Sadrian 753250003Sadrian // Insert all the dbg_values which have not already been inserted in source 754250003Sadrian // order sequence. 755250003Sadrian if (HasDbg) { 756250003Sadrian MachineBasicBlock::iterator BBBegin = BB->getFirstNonPHI(); 757250003Sadrian 758250003Sadrian // Sort the source order instructions and use the order to insert debug 759250003Sadrian // values. 760250003Sadrian std::sort(Orders.begin(), Orders.end(), OrderSorter()); 761250003Sadrian 762250003Sadrian SDDbgInfo::DbgIterator DI = DAG->DbgBegin(); 763250003Sadrian SDDbgInfo::DbgIterator DE = DAG->DbgEnd(); 764250003Sadrian // Now emit the rest according to source order. 765250003Sadrian unsigned LastOrder = 0; 766250003Sadrian for (unsigned i = 0, e = Orders.size(); i != e && DI != DE; ++i) { 767250003Sadrian unsigned Order = Orders[i].first; 768250003Sadrian MachineInstr *MI = Orders[i].second; 769250003Sadrian // Insert all SDDbgValue's whose order(s) are before "Order". 770250003Sadrian if (!MI) 771250003Sadrian continue; 772250003Sadrian for (; DI != DE && 773250003Sadrian (*DI)->getOrder() >= LastOrder && (*DI)->getOrder() < Order; ++DI) { 774250003Sadrian if ((*DI)->isInvalidated()) 775250003Sadrian continue; 776250003Sadrian MachineInstr *DbgMI = Emitter.EmitDbgValue(*DI, VRBaseMap); 777250003Sadrian if (DbgMI) { 778250003Sadrian if (!LastOrder) 779250003Sadrian // Insert to start of the BB (after PHIs). 780250003Sadrian BB->insert(BBBegin, DbgMI); 781250003Sadrian else { 782250003Sadrian // Insert at the instruction, which may be in a different 783250003Sadrian // block, if the block was split by a custom inserter. 784250003Sadrian MachineBasicBlock::iterator Pos = MI; 785250003Sadrian MI->getParent()->insert(llvm::next(Pos), DbgMI); 786250003Sadrian } 787250003Sadrian } 788250003Sadrian } 789250003Sadrian LastOrder = Order; 790250003Sadrian } 791250003Sadrian // Add trailing DbgValue's before the terminator. FIXME: May want to add 792250003Sadrian // some of them before one or more conditional branches? 793250003Sadrian while (DI != DE) { 794250003Sadrian MachineBasicBlock *InsertBB = Emitter.getBlock(); 795250003Sadrian MachineBasicBlock::iterator Pos= Emitter.getBlock()->getFirstTerminator(); 796250003Sadrian if (!(*DI)->isInvalidated()) { 797250003Sadrian MachineInstr *DbgMI= Emitter.EmitDbgValue(*DI, VRBaseMap); 798250003Sadrian if (DbgMI) 799250003Sadrian InsertBB->insert(Pos, DbgMI); 800250003Sadrian } 801250003Sadrian ++DI; 802250003Sadrian } 803250003Sadrian } 804250003Sadrian 805250003Sadrian BB = Emitter.getBlock(); 806250003Sadrian InsertPos = Emitter.getInsertPos(); 807250003Sadrian return BB; 808250003Sadrian} 809250003Sadrian