ScheduleDAGSDNodes.cpp revision 84fbac580941548a6ab1121ed3b0ffdc4e2bc080
1343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman//===--- ScheduleDAGSDNodes.cpp - Implement the ScheduleDAGSDNodes class --===// 2343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman// 3343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman// The LLVM Compiler Infrastructure 4343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman// 5343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman// This file is distributed under the University of Illinois Open Source 6343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman// License. See LICENSE.TXT for details. 7343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman// 8343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman//===----------------------------------------------------------------------===// 9343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman// 10343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman// This implements the ScheduleDAG class, which is a base class used by 11343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman// scheduling implementation classes. 12343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman// 13343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman//===----------------------------------------------------------------------===// 14343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 15343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman#define DEBUG_TYPE "pre-RA-sched" 1684fbac580941548a6ab1121ed3b0ffdc4e2bc080Dan Gohman#include "ScheduleDAGSDNodes.h" 17343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman#include "llvm/CodeGen/SelectionDAG.h" 18343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman#include "llvm/Target/TargetMachine.h" 19343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman#include "llvm/Target/TargetInstrInfo.h" 20343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman#include "llvm/Target/TargetRegisterInfo.h" 21343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman#include "llvm/Support/Debug.h" 22343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman#include "llvm/Support/raw_ostream.h" 23343f0c046702831a4a6aec951b6a297a23241a55Dan Gohmanusing namespace llvm; 24343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 2579ce276083ced01256a0eb7d80731e4948ca6e87Dan GohmanScheduleDAGSDNodes::ScheduleDAGSDNodes(MachineFunction &mf) 2679ce276083ced01256a0eb7d80731e4948ca6e87Dan Gohman : ScheduleDAG(mf) { 27343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman} 28343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 29343f0c046702831a4a6aec951b6a297a23241a55Dan GohmanSUnit *ScheduleDAGSDNodes::Clone(SUnit *Old) { 30343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SUnit *SU = NewSUnit(Old->getNode()); 31343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SU->OrigNode = Old->OrigNode; 32343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SU->Latency = Old->Latency; 33343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SU->isTwoAddress = Old->isTwoAddress; 34343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SU->isCommutable = Old->isCommutable; 35343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SU->hasPhysRegDefs = Old->hasPhysRegDefs; 36e57187cbe321a286f6a7f409a7badd1ae4e4642cEvan Cheng Old->isCloned = true; 37343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman return SU; 38343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman} 39343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 40343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman/// CheckForPhysRegDependency - Check if the dependency between def and use of 41343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman/// a specified operand is a physical register dependency. If so, returns the 42c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng/// register and the cost of copying the register. 43343f0c046702831a4a6aec951b6a297a23241a55Dan Gohmanstatic void CheckForPhysRegDependency(SDNode *Def, SDNode *User, unsigned Op, 44343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman const TargetRegisterInfo *TRI, 45343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman const TargetInstrInfo *TII, 46c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng unsigned &PhysReg, int &Cost) { 47343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (Op != 2 || User->getOpcode() != ISD::CopyToReg) 48343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman return; 49343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 50343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman unsigned Reg = cast<RegisterSDNode>(User->getOperand(1))->getReg(); 51343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (TargetRegisterInfo::isVirtualRegister(Reg)) 52343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman return; 53343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 54343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman unsigned ResNo = User->getOperand(2).getResNo(); 55343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (Def->isMachineOpcode()) { 56343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman const TargetInstrDesc &II = TII->get(Def->getMachineOpcode()); 57343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (ResNo >= II.getNumDefs() && 58c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng II.ImplicitDefs[ResNo - II.getNumDefs()] == Reg) { 59343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman PhysReg = Reg; 60c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng const TargetRegisterClass *RC = 61c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng TRI->getPhysicalRegisterRegClass(Reg, Def->getValueType(ResNo)); 62c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng Cost = RC->getCopyCost(); 63c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng } 64343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 65343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman} 66343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 67343f0c046702831a4a6aec951b6a297a23241a55Dan Gohmanvoid ScheduleDAGSDNodes::BuildSchedUnits() { 68343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // During scheduling, the NodeId field of SDNode is used to map SDNodes 69343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // to their associated SUnits by holding SUnits table indices. A value 70343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // of -1 means the SDNode does not yet have an associated SUnit. 71e1dfc7da8991270db5094aa736fde273bfab6061Dan Gohman unsigned NumNodes = 0; 72343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman for (SelectionDAG::allnodes_iterator NI = DAG->allnodes_begin(), 73e1dfc7da8991270db5094aa736fde273bfab6061Dan Gohman E = DAG->allnodes_end(); NI != E; ++NI) { 74343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman NI->setNodeId(-1); 75e1dfc7da8991270db5094aa736fde273bfab6061Dan Gohman ++NumNodes; 76e1dfc7da8991270db5094aa736fde273bfab6061Dan Gohman } 77343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 78e1dfc7da8991270db5094aa736fde273bfab6061Dan Gohman // Reserve entries in the vector for each of the SUnits we are creating. This 79e1dfc7da8991270db5094aa736fde273bfab6061Dan Gohman // ensure that reallocation of the vector won't happen, so SUnit*'s won't get 80e1dfc7da8991270db5094aa736fde273bfab6061Dan Gohman // invalidated. 81e1dfc7da8991270db5094aa736fde273bfab6061Dan Gohman // FIXME: Multiply by 2 because we may clone nodes during scheduling. 82e1dfc7da8991270db5094aa736fde273bfab6061Dan Gohman // This is a temporary workaround. 83e1dfc7da8991270db5094aa736fde273bfab6061Dan Gohman SUnits.reserve(NumNodes * 2); 84e1dfc7da8991270db5094aa736fde273bfab6061Dan Gohman 853f23744df4809eba94284e601e81489212c974d4Dan Gohman // Check to see if the scheduler cares about latencies. 863f23744df4809eba94284e601e81489212c974d4Dan Gohman bool UnitLatencies = ForceUnitLatencies(); 873f23744df4809eba94284e601e81489212c974d4Dan Gohman 88343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman for (SelectionDAG::allnodes_iterator NI = DAG->allnodes_begin(), 89343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman E = DAG->allnodes_end(); NI != E; ++NI) { 90343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (isPassiveNode(NI)) // Leaf node, e.g. a TargetImmediate. 91343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman continue; 92343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 93343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // If this node has already been processed, stop now. 94343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (NI->getNodeId() != -1) continue; 95343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 96343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SUnit *NodeSUnit = NewSUnit(NI); 97343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 98343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // See if anything is flagged to this node, if so, add them to flagged 99343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // nodes. Nodes can have at most one flag input and one flag output. Flags 100343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // are required the be the last operand and result of a node. 101343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 102343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // Scan up to find flagged preds. 103343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SDNode *N = NI; 104343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (N->getNumOperands() && 105343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman N->getOperand(N->getNumOperands()-1).getValueType() == MVT::Flag) { 106343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman do { 107343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman N = N->getOperand(N->getNumOperands()-1).getNode(); 108343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman assert(N->getNodeId() == -1 && "Node already inserted!"); 109343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman N->setNodeId(NodeSUnit->NodeNum); 110343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } while (N->getNumOperands() && 111343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman N->getOperand(N->getNumOperands()-1).getValueType()== MVT::Flag); 112343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 113343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 114343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // Scan down to find any flagged succs. 115343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman N = NI; 116343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman while (N->getValueType(N->getNumValues()-1) == MVT::Flag) { 117343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SDValue FlagVal(N, N->getNumValues()-1); 118343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 119343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // There are either zero or one users of the Flag result. 120343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman bool HasFlagUse = false; 121343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman for (SDNode::use_iterator UI = N->use_begin(), E = N->use_end(); 122343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman UI != E; ++UI) 123343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (FlagVal.isOperandOf(*UI)) { 124343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman HasFlagUse = true; 125343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman assert(N->getNodeId() == -1 && "Node already inserted!"); 126343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman N->setNodeId(NodeSUnit->NodeNum); 127343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman N = *UI; 128343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman break; 129343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 130343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (!HasFlagUse) break; 131343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 132343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 133343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // If there are flag operands involved, N is now the bottom-most node 134343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // of the sequence of nodes that are flagged together. 135343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // Update the SUnit. 136343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman NodeSUnit->setNode(N); 137343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman assert(N->getNodeId() == -1 && "Node already inserted!"); 138343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman N->setNodeId(NodeSUnit->NodeNum); 139343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 140787782f4ca0cca2523825131c24a6f78535a3eb8Dan Gohman // Assign the Latency field of NodeSUnit using target-provided information. 1413f23744df4809eba94284e601e81489212c974d4Dan Gohman if (UnitLatencies) 1423f23744df4809eba94284e601e81489212c974d4Dan Gohman NodeSUnit->Latency = 1; 1433f23744df4809eba94284e601e81489212c974d4Dan Gohman else 1443f23744df4809eba94284e601e81489212c974d4Dan Gohman ComputeLatency(NodeSUnit); 145343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 146c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman} 147c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman 148c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohmanvoid ScheduleDAGSDNodes::AddSchedEdges() { 149343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // Pass 2: add the preds, succs, etc. 150343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman for (unsigned su = 0, e = SUnits.size(); su != e; ++su) { 151343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SUnit *SU = &SUnits[su]; 152343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SDNode *MainNode = SU->getNode(); 153343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 154343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (MainNode->isMachineOpcode()) { 155343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman unsigned Opc = MainNode->getMachineOpcode(); 156343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman const TargetInstrDesc &TID = TII->get(Opc); 157343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman for (unsigned i = 0; i != TID.getNumOperands(); ++i) { 158343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (TID.getOperandConstraint(i, TOI::TIED_TO) != -1) { 159343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SU->isTwoAddress = true; 160343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman break; 161343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 162343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 163343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (TID.isCommutable()) 164343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SU->isCommutable = true; 165343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 166343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 167343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // Find all predecessors and successors of the group. 168343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman for (SDNode *N = SU->getNode(); N; N = N->getFlaggedNode()) { 169343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (N->isMachineOpcode() && 170343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman TII->get(N->getMachineOpcode()).getImplicitDefs() && 171343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman CountResults(N) > TII->get(N->getMachineOpcode()).getNumDefs()) 172343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SU->hasPhysRegDefs = true; 173343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 174343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) { 175343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SDNode *OpN = N->getOperand(i).getNode(); 176343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (isPassiveNode(OpN)) continue; // Not scheduled. 177343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SUnit *OpSU = &SUnits[OpN->getNodeId()]; 178343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman assert(OpSU && "Node has no SUnit!"); 179343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (OpSU == SU) continue; // In the same group. 180343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 181343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman MVT OpVT = N->getOperand(i).getValueType(); 182343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman assert(OpVT != MVT::Flag && "Flagged nodes should be in same sunit!"); 183343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman bool isChain = OpVT == MVT::Other; 184343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 185343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman unsigned PhysReg = 0; 186c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng int Cost = 1; 187343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // Determine if this is a physical register dependency. 188c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng CheckForPhysRegDependency(OpN, N, i, TRI, TII, PhysReg, Cost); 18954e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman assert((PhysReg == 0 || !isChain) && 19054e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman "Chain dependence via physreg data?"); 191c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng // FIXME: See ScheduleDAGSDNodes::EmitCopyFromReg. For now, scheduler 192c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng // emits a copy from the physical register to a virtual register unless 193c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng // it requires a cross class copy (cost < 0). That means we are only 194c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng // treating "expensive to copy" register dependency as physical register 195c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng // dependency. This may change in the future though. 196c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng if (Cost >= 0) 197c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng PhysReg = 0; 19854e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman SU->addPred(SDep(OpSU, isChain ? SDep::Order : SDep::Data, 19954e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman OpSU->Latency, PhysReg)); 200343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 201343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 202343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 203343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman} 204343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 205c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman/// BuildSchedGraph - Build the SUnit graph from the selection dag that we 206c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman/// are input. This SUnit graph is similar to the SelectionDAG, but 207c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman/// excludes nodes that aren't interesting to scheduling, and represents 208c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman/// flagged together nodes with a single SUnit. 209c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohmanvoid ScheduleDAGSDNodes::BuildSchedGraph() { 210c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman // Populate the SUnits array. 211c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman BuildSchedUnits(); 212c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman // Compute all the scheduling dependencies between nodes. 213c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman AddSchedEdges(); 214c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman} 215c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman 216343f0c046702831a4a6aec951b6a297a23241a55Dan Gohmanvoid ScheduleDAGSDNodes::ComputeLatency(SUnit *SU) { 217343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman const InstrItineraryData &InstrItins = TM.getInstrItineraryData(); 218343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 219343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // Compute the latency for the node. We use the sum of the latencies for 220343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // all nodes flagged together into this SUnit. 221343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SU->Latency = 0; 222c8c2827993204207ca70a93f62f233fbe81b97efDan Gohman bool SawMachineOpcode = false; 223c8c2827993204207ca70a93f62f233fbe81b97efDan Gohman for (SDNode *N = SU->getNode(); N; N = N->getFlaggedNode()) 224343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (N->isMachineOpcode()) { 225c8c2827993204207ca70a93f62f233fbe81b97efDan Gohman SawMachineOpcode = true; 226c8c2827993204207ca70a93f62f233fbe81b97efDan Gohman SU->Latency += 227c8c2827993204207ca70a93f62f233fbe81b97efDan Gohman InstrItins.getLatency(TII->get(N->getMachineOpcode()).getSchedClass()); 228343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 229343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman} 230343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 231343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman/// CountResults - The results of target nodes have register or immediate 232343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman/// operands first, then an optional chain, and optional flag operands (which do 233343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman/// not go into the resulting MachineInstr). 234343f0c046702831a4a6aec951b6a297a23241a55Dan Gohmanunsigned ScheduleDAGSDNodes::CountResults(SDNode *Node) { 235343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman unsigned N = Node->getNumValues(); 236343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman while (N && Node->getValueType(N - 1) == MVT::Flag) 237343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman --N; 238343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (N && Node->getValueType(N - 1) == MVT::Other) 239343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman --N; // Skip over chain result. 240343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman return N; 241343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman} 242343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 243343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman/// CountOperands - The inputs to target nodes have any actual inputs first, 244343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman/// followed by special operands that describe memory references, then an 245343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman/// optional chain operand, then an optional flag operand. Compute the number 246343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman/// of actual operands that will go into the resulting MachineInstr. 247343f0c046702831a4a6aec951b6a297a23241a55Dan Gohmanunsigned ScheduleDAGSDNodes::CountOperands(SDNode *Node) { 248343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman unsigned N = ComputeMemOperandsEnd(Node); 249343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman while (N && isa<MemOperandSDNode>(Node->getOperand(N - 1).getNode())) 250343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman --N; // Ignore MEMOPERAND nodes 251343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman return N; 252343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman} 253343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 254343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman/// ComputeMemOperandsEnd - Find the index one past the last MemOperandSDNode 255343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman/// operand 256343f0c046702831a4a6aec951b6a297a23241a55Dan Gohmanunsigned ScheduleDAGSDNodes::ComputeMemOperandsEnd(SDNode *Node) { 257343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman unsigned N = Node->getNumOperands(); 258343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman while (N && Node->getOperand(N - 1).getValueType() == MVT::Flag) 259343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman --N; 260343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (N && Node->getOperand(N - 1).getValueType() == MVT::Other) 261343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman --N; // Ignore chain if it exists. 262343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman return N; 263343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman} 264343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 265343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 266343f0c046702831a4a6aec951b6a297a23241a55Dan Gohmanvoid ScheduleDAGSDNodes::dumpNode(const SUnit *SU) const { 267c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng if (!SU->getNode()) { 268c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng cerr << "PHYS REG COPY\n"; 269c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng return; 270c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng } 271c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng 272c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng SU->getNode()->dump(DAG); 273343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman cerr << "\n"; 274343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SmallVector<SDNode *, 4> FlaggedNodes; 275343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman for (SDNode *N = SU->getNode()->getFlaggedNode(); N; N = N->getFlaggedNode()) 276343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman FlaggedNodes.push_back(N); 277343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman while (!FlaggedNodes.empty()) { 278343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman cerr << " "; 279343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman FlaggedNodes.back()->dump(DAG); 280343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman cerr << "\n"; 281343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman FlaggedNodes.pop_back(); 282343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 283343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman} 284