ScheduleDAGSDNodes.cpp revision 3974667c1a6d48686e92f85bc4463bb239af7442
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 2947ac0f0c7c39289f5970688154e385be22b7f293Dan Gohman/// Run - perform scheduling. 3047ac0f0c7c39289f5970688154e385be22b7f293Dan Gohman/// 3147ac0f0c7c39289f5970688154e385be22b7f293Dan Gohmanvoid ScheduleDAGSDNodes::Run(SelectionDAG *dag, MachineBasicBlock *bb, 3247ac0f0c7c39289f5970688154e385be22b7f293Dan Gohman MachineBasicBlock::iterator insertPos) { 3347ac0f0c7c39289f5970688154e385be22b7f293Dan Gohman DAG = dag; 3447ac0f0c7c39289f5970688154e385be22b7f293Dan Gohman ScheduleDAG::Run(bb, insertPos); 3547ac0f0c7c39289f5970688154e385be22b7f293Dan Gohman} 3647ac0f0c7c39289f5970688154e385be22b7f293Dan Gohman 37343f0c046702831a4a6aec951b6a297a23241a55Dan GohmanSUnit *ScheduleDAGSDNodes::Clone(SUnit *Old) { 38343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SUnit *SU = NewSUnit(Old->getNode()); 39343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SU->OrigNode = Old->OrigNode; 40343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SU->Latency = Old->Latency; 41343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SU->isTwoAddress = Old->isTwoAddress; 42343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SU->isCommutable = Old->isCommutable; 43343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SU->hasPhysRegDefs = Old->hasPhysRegDefs; 443974667c1a6d48686e92f85bc4463bb239af7442Dan Gohman SU->hasPhysRegClobbers = Old->hasPhysRegClobbers; 45e57187cbe321a286f6a7f409a7badd1ae4e4642cEvan Cheng Old->isCloned = true; 46343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman return SU; 47343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman} 48343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 49343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman/// CheckForPhysRegDependency - Check if the dependency between def and use of 50343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman/// a specified operand is a physical register dependency. If so, returns the 51c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng/// register and the cost of copying the register. 52343f0c046702831a4a6aec951b6a297a23241a55Dan Gohmanstatic void CheckForPhysRegDependency(SDNode *Def, SDNode *User, unsigned Op, 53343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman const TargetRegisterInfo *TRI, 54343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman const TargetInstrInfo *TII, 55c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng unsigned &PhysReg, int &Cost) { 56343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (Op != 2 || User->getOpcode() != ISD::CopyToReg) 57343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman return; 58343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 59343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman unsigned Reg = cast<RegisterSDNode>(User->getOperand(1))->getReg(); 60343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (TargetRegisterInfo::isVirtualRegister(Reg)) 61343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman return; 62343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 63343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman unsigned ResNo = User->getOperand(2).getResNo(); 64343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (Def->isMachineOpcode()) { 65343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman const TargetInstrDesc &II = TII->get(Def->getMachineOpcode()); 66343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (ResNo >= II.getNumDefs() && 67c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng II.ImplicitDefs[ResNo - II.getNumDefs()] == Reg) { 68343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman PhysReg = Reg; 69c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng const TargetRegisterClass *RC = 70c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng TRI->getPhysicalRegisterRegClass(Reg, Def->getValueType(ResNo)); 71c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng Cost = RC->getCopyCost(); 72c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng } 73343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 74343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman} 75343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 76343f0c046702831a4a6aec951b6a297a23241a55Dan Gohmanvoid ScheduleDAGSDNodes::BuildSchedUnits() { 77343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // During scheduling, the NodeId field of SDNode is used to map SDNodes 78343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // to their associated SUnits by holding SUnits table indices. A value 79343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // of -1 means the SDNode does not yet have an associated SUnit. 80e1dfc7da8991270db5094aa736fde273bfab6061Dan Gohman unsigned NumNodes = 0; 81343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman for (SelectionDAG::allnodes_iterator NI = DAG->allnodes_begin(), 82e1dfc7da8991270db5094aa736fde273bfab6061Dan Gohman E = DAG->allnodes_end(); NI != E; ++NI) { 83343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman NI->setNodeId(-1); 84e1dfc7da8991270db5094aa736fde273bfab6061Dan Gohman ++NumNodes; 85e1dfc7da8991270db5094aa736fde273bfab6061Dan Gohman } 86343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 87e1dfc7da8991270db5094aa736fde273bfab6061Dan Gohman // Reserve entries in the vector for each of the SUnits we are creating. This 88e1dfc7da8991270db5094aa736fde273bfab6061Dan Gohman // ensure that reallocation of the vector won't happen, so SUnit*'s won't get 89e1dfc7da8991270db5094aa736fde273bfab6061Dan Gohman // invalidated. 90e1dfc7da8991270db5094aa736fde273bfab6061Dan Gohman // FIXME: Multiply by 2 because we may clone nodes during scheduling. 91e1dfc7da8991270db5094aa736fde273bfab6061Dan Gohman // This is a temporary workaround. 92e1dfc7da8991270db5094aa736fde273bfab6061Dan Gohman SUnits.reserve(NumNodes * 2); 93e1dfc7da8991270db5094aa736fde273bfab6061Dan Gohman 943f23744df4809eba94284e601e81489212c974d4Dan Gohman // Check to see if the scheduler cares about latencies. 953f23744df4809eba94284e601e81489212c974d4Dan Gohman bool UnitLatencies = ForceUnitLatencies(); 963f23744df4809eba94284e601e81489212c974d4Dan Gohman 97343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman for (SelectionDAG::allnodes_iterator NI = DAG->allnodes_begin(), 98343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman E = DAG->allnodes_end(); NI != E; ++NI) { 99343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (isPassiveNode(NI)) // Leaf node, e.g. a TargetImmediate. 100343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman continue; 101343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 102343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // If this node has already been processed, stop now. 103343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (NI->getNodeId() != -1) continue; 104343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 105343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SUnit *NodeSUnit = NewSUnit(NI); 106343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 107343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // See if anything is flagged to this node, if so, add them to flagged 108343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // nodes. Nodes can have at most one flag input and one flag output. Flags 109db95fa131a229652f925794ca7a5b84e9490050bDan Gohman // are required to be the last operand and result of a node. 110343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 111343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // Scan up to find flagged preds. 112343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SDNode *N = NI; 113db95fa131a229652f925794ca7a5b84e9490050bDan Gohman while (N->getNumOperands() && 114db95fa131a229652f925794ca7a5b84e9490050bDan Gohman N->getOperand(N->getNumOperands()-1).getValueType() == MVT::Flag) { 115db95fa131a229652f925794ca7a5b84e9490050bDan Gohman N = N->getOperand(N->getNumOperands()-1).getNode(); 116db95fa131a229652f925794ca7a5b84e9490050bDan Gohman assert(N->getNodeId() == -1 && "Node already inserted!"); 117db95fa131a229652f925794ca7a5b84e9490050bDan Gohman N->setNodeId(NodeSUnit->NodeNum); 118343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 119343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 120343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // Scan down to find any flagged succs. 121343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman N = NI; 122343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman while (N->getValueType(N->getNumValues()-1) == MVT::Flag) { 123343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SDValue FlagVal(N, N->getNumValues()-1); 124343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 125343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // There are either zero or one users of the Flag result. 126343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman bool HasFlagUse = false; 127343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman for (SDNode::use_iterator UI = N->use_begin(), E = N->use_end(); 128343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman UI != E; ++UI) 129343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (FlagVal.isOperandOf(*UI)) { 130343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman HasFlagUse = true; 131343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman assert(N->getNodeId() == -1 && "Node already inserted!"); 132343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman N->setNodeId(NodeSUnit->NodeNum); 133343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman N = *UI; 134343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman break; 135343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 136343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (!HasFlagUse) break; 137343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 138343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 139343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // If there are flag operands involved, N is now the bottom-most node 140343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // of the sequence of nodes that are flagged together. 141343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // Update the SUnit. 142343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman NodeSUnit->setNode(N); 143343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman assert(N->getNodeId() == -1 && "Node already inserted!"); 144343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman N->setNodeId(NodeSUnit->NodeNum); 145343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 146787782f4ca0cca2523825131c24a6f78535a3eb8Dan Gohman // Assign the Latency field of NodeSUnit using target-provided information. 1473f23744df4809eba94284e601e81489212c974d4Dan Gohman if (UnitLatencies) 1483f23744df4809eba94284e601e81489212c974d4Dan Gohman NodeSUnit->Latency = 1; 1493f23744df4809eba94284e601e81489212c974d4Dan Gohman else 1503f23744df4809eba94284e601e81489212c974d4Dan Gohman ComputeLatency(NodeSUnit); 151343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 152c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman} 153c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman 154c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohmanvoid ScheduleDAGSDNodes::AddSchedEdges() { 155343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // Pass 2: add the preds, succs, etc. 156343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman for (unsigned su = 0, e = SUnits.size(); su != e; ++su) { 157343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SUnit *SU = &SUnits[su]; 158343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SDNode *MainNode = SU->getNode(); 159343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 160343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (MainNode->isMachineOpcode()) { 161343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman unsigned Opc = MainNode->getMachineOpcode(); 162343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman const TargetInstrDesc &TID = TII->get(Opc); 163343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman for (unsigned i = 0; i != TID.getNumOperands(); ++i) { 164343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (TID.getOperandConstraint(i, TOI::TIED_TO) != -1) { 165343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SU->isTwoAddress = true; 166343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman break; 167343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 168343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 169343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (TID.isCommutable()) 170343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SU->isCommutable = true; 171343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 172343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 173343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // Find all predecessors and successors of the group. 174343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman for (SDNode *N = SU->getNode(); N; N = N->getFlaggedNode()) { 175343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (N->isMachineOpcode() && 1763974667c1a6d48686e92f85bc4463bb239af7442Dan Gohman TII->get(N->getMachineOpcode()).getImplicitDefs()) { 1773974667c1a6d48686e92f85bc4463bb239af7442Dan Gohman SU->hasPhysRegClobbers = true; 1783974667c1a6d48686e92f85bc4463bb239af7442Dan Gohman if (CountResults(N) > TII->get(N->getMachineOpcode()).getNumDefs()) 1793974667c1a6d48686e92f85bc4463bb239af7442Dan Gohman SU->hasPhysRegDefs = true; 1803974667c1a6d48686e92f85bc4463bb239af7442Dan Gohman } 181343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 182343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) { 183343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SDNode *OpN = N->getOperand(i).getNode(); 184343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (isPassiveNode(OpN)) continue; // Not scheduled. 185343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SUnit *OpSU = &SUnits[OpN->getNodeId()]; 186343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman assert(OpSU && "Node has no SUnit!"); 187343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (OpSU == SU) continue; // In the same group. 188343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 189343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman MVT OpVT = N->getOperand(i).getValueType(); 190343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman assert(OpVT != MVT::Flag && "Flagged nodes should be in same sunit!"); 191343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman bool isChain = OpVT == MVT::Other; 192343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 193343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman unsigned PhysReg = 0; 194c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng int Cost = 1; 195343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // Determine if this is a physical register dependency. 196c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng CheckForPhysRegDependency(OpN, N, i, TRI, TII, PhysReg, Cost); 19754e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman assert((PhysReg == 0 || !isChain) && 19854e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman "Chain dependence via physreg data?"); 199c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng // FIXME: See ScheduleDAGSDNodes::EmitCopyFromReg. For now, scheduler 200c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng // emits a copy from the physical register to a virtual register unless 201c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng // it requires a cross class copy (cost < 0). That means we are only 202c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng // treating "expensive to copy" register dependency as physical register 203c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng // dependency. This may change in the future though. 204c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng if (Cost >= 0) 205c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng PhysReg = 0; 20654e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman SU->addPred(SDep(OpSU, isChain ? SDep::Order : SDep::Data, 20754e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman OpSU->Latency, PhysReg)); 208343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 209343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 210343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 211343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman} 212343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 213c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman/// BuildSchedGraph - Build the SUnit graph from the selection dag that we 214c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman/// are input. This SUnit graph is similar to the SelectionDAG, but 215c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman/// excludes nodes that aren't interesting to scheduling, and represents 216c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman/// flagged together nodes with a single SUnit. 217c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohmanvoid ScheduleDAGSDNodes::BuildSchedGraph() { 218c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman // Populate the SUnits array. 219c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman BuildSchedUnits(); 220c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman // Compute all the scheduling dependencies between nodes. 221c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman AddSchedEdges(); 222c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman} 223c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman 224343f0c046702831a4a6aec951b6a297a23241a55Dan Gohmanvoid ScheduleDAGSDNodes::ComputeLatency(SUnit *SU) { 225343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman const InstrItineraryData &InstrItins = TM.getInstrItineraryData(); 226343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 227343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // Compute the latency for the node. We use the sum of the latencies for 228343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // all nodes flagged together into this SUnit. 229343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SU->Latency = 0; 230c8c2827993204207ca70a93f62f233fbe81b97efDan Gohman bool SawMachineOpcode = false; 231c8c2827993204207ca70a93f62f233fbe81b97efDan Gohman for (SDNode *N = SU->getNode(); N; N = N->getFlaggedNode()) 232343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (N->isMachineOpcode()) { 233c8c2827993204207ca70a93f62f233fbe81b97efDan Gohman SawMachineOpcode = true; 234c8c2827993204207ca70a93f62f233fbe81b97efDan Gohman SU->Latency += 235c8c2827993204207ca70a93f62f233fbe81b97efDan Gohman InstrItins.getLatency(TII->get(N->getMachineOpcode()).getSchedClass()); 236343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 237343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman} 238343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 239343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman/// CountResults - The results of target nodes have register or immediate 240343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman/// operands first, then an optional chain, and optional flag operands (which do 241343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman/// not go into the resulting MachineInstr). 242343f0c046702831a4a6aec951b6a297a23241a55Dan Gohmanunsigned ScheduleDAGSDNodes::CountResults(SDNode *Node) { 243343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman unsigned N = Node->getNumValues(); 244343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman while (N && Node->getValueType(N - 1) == MVT::Flag) 245343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman --N; 246343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (N && Node->getValueType(N - 1) == MVT::Other) 247343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman --N; // Skip over chain result. 248343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman return N; 249343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman} 250343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 251343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman/// CountOperands - The inputs to target nodes have any actual inputs first, 252343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman/// followed by special operands that describe memory references, then an 253343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman/// optional chain operand, then an optional flag operand. Compute the number 254343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman/// of actual operands that will go into the resulting MachineInstr. 255343f0c046702831a4a6aec951b6a297a23241a55Dan Gohmanunsigned ScheduleDAGSDNodes::CountOperands(SDNode *Node) { 256343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman unsigned N = ComputeMemOperandsEnd(Node); 257343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman while (N && isa<MemOperandSDNode>(Node->getOperand(N - 1).getNode())) 258343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman --N; // Ignore MEMOPERAND nodes 259343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman return N; 260343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman} 261343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 262343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman/// ComputeMemOperandsEnd - Find the index one past the last MemOperandSDNode 263343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman/// operand 264343f0c046702831a4a6aec951b6a297a23241a55Dan Gohmanunsigned ScheduleDAGSDNodes::ComputeMemOperandsEnd(SDNode *Node) { 265343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman unsigned N = Node->getNumOperands(); 266343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman while (N && Node->getOperand(N - 1).getValueType() == MVT::Flag) 267343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman --N; 268343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (N && Node->getOperand(N - 1).getValueType() == MVT::Other) 269343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman --N; // Ignore chain if it exists. 270343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman return N; 271343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman} 272343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 273343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 274343f0c046702831a4a6aec951b6a297a23241a55Dan Gohmanvoid ScheduleDAGSDNodes::dumpNode(const SUnit *SU) const { 275c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng if (!SU->getNode()) { 276c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng cerr << "PHYS REG COPY\n"; 277c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng return; 278c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng } 279c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng 280c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng SU->getNode()->dump(DAG); 281343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman cerr << "\n"; 282343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SmallVector<SDNode *, 4> FlaggedNodes; 283343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman for (SDNode *N = SU->getNode()->getFlaggedNode(); N; N = N->getFlaggedNode()) 284343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman FlaggedNodes.push_back(N); 285343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman while (!FlaggedNodes.empty()) { 286343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman cerr << " "; 287343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman FlaggedNodes.back()->dump(DAG); 288343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman cerr << "\n"; 289343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman FlaggedNodes.pop_back(); 290343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 291343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman} 292