ScheduleDAGSDNodes.cpp revision 98976e4dcd18adbbe676048c0069e67346eb4ade
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" 21710461688bba935f0ad5c75da7fec2ad0f225c00David Goodwin#include "llvm/Target/TargetSubtarget.h" 22343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman#include "llvm/Support/Debug.h" 23343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman#include "llvm/Support/raw_ostream.h" 24343f0c046702831a4a6aec951b6a297a23241a55Dan Gohmanusing namespace llvm; 25343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 2679ce276083ced01256a0eb7d80731e4948ca6e87Dan GohmanScheduleDAGSDNodes::ScheduleDAGSDNodes(MachineFunction &mf) 2779ce276083ced01256a0eb7d80731e4948ca6e87Dan Gohman : ScheduleDAG(mf) { 28343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman} 29343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 3047ac0f0c7c39289f5970688154e385be22b7f293Dan Gohman/// Run - perform scheduling. 3147ac0f0c7c39289f5970688154e385be22b7f293Dan Gohman/// 3247ac0f0c7c39289f5970688154e385be22b7f293Dan Gohmanvoid ScheduleDAGSDNodes::Run(SelectionDAG *dag, MachineBasicBlock *bb, 3347ac0f0c7c39289f5970688154e385be22b7f293Dan Gohman MachineBasicBlock::iterator insertPos) { 3447ac0f0c7c39289f5970688154e385be22b7f293Dan Gohman DAG = dag; 3547ac0f0c7c39289f5970688154e385be22b7f293Dan Gohman ScheduleDAG::Run(bb, insertPos); 3647ac0f0c7c39289f5970688154e385be22b7f293Dan Gohman} 3747ac0f0c7c39289f5970688154e385be22b7f293Dan Gohman 38343f0c046702831a4a6aec951b6a297a23241a55Dan GohmanSUnit *ScheduleDAGSDNodes::Clone(SUnit *Old) { 39343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SUnit *SU = NewSUnit(Old->getNode()); 40343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SU->OrigNode = Old->OrigNode; 41343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SU->Latency = Old->Latency; 42343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SU->isTwoAddress = Old->isTwoAddress; 43343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SU->isCommutable = Old->isCommutable; 44343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SU->hasPhysRegDefs = Old->hasPhysRegDefs; 453974667c1a6d48686e92f85bc4463bb239af7442Dan Gohman SU->hasPhysRegClobbers = Old->hasPhysRegClobbers; 46e57187cbe321a286f6a7f409a7badd1ae4e4642cEvan Cheng Old->isCloned = true; 47343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman return SU; 48343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman} 49343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 50343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman/// CheckForPhysRegDependency - Check if the dependency between def and use of 51343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman/// a specified operand is a physical register dependency. If so, returns the 52c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng/// register and the cost of copying the register. 53343f0c046702831a4a6aec951b6a297a23241a55Dan Gohmanstatic void CheckForPhysRegDependency(SDNode *Def, SDNode *User, unsigned Op, 54343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman const TargetRegisterInfo *TRI, 55343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman const TargetInstrInfo *TII, 56c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng unsigned &PhysReg, int &Cost) { 57343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (Op != 2 || User->getOpcode() != ISD::CopyToReg) 58343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman return; 59343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 60343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman unsigned Reg = cast<RegisterSDNode>(User->getOperand(1))->getReg(); 61343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (TargetRegisterInfo::isVirtualRegister(Reg)) 62343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman return; 63343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 64343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman unsigned ResNo = User->getOperand(2).getResNo(); 65343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (Def->isMachineOpcode()) { 66343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman const TargetInstrDesc &II = TII->get(Def->getMachineOpcode()); 67343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (ResNo >= II.getNumDefs() && 68c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng II.ImplicitDefs[ResNo - II.getNumDefs()] == Reg) { 69343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman PhysReg = Reg; 70c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng const TargetRegisterClass *RC = 71c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng TRI->getPhysicalRegisterRegClass(Reg, Def->getValueType(ResNo)); 72c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng Cost = RC->getCopyCost(); 73c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng } 74343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 75343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman} 76343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 77343f0c046702831a4a6aec951b6a297a23241a55Dan Gohmanvoid ScheduleDAGSDNodes::BuildSchedUnits() { 78343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // During scheduling, the NodeId field of SDNode is used to map SDNodes 79343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // to their associated SUnits by holding SUnits table indices. A value 80343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // of -1 means the SDNode does not yet have an associated SUnit. 81e1dfc7da8991270db5094aa736fde273bfab6061Dan Gohman unsigned NumNodes = 0; 82343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman for (SelectionDAG::allnodes_iterator NI = DAG->allnodes_begin(), 83e1dfc7da8991270db5094aa736fde273bfab6061Dan Gohman E = DAG->allnodes_end(); NI != E; ++NI) { 84343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman NI->setNodeId(-1); 85e1dfc7da8991270db5094aa736fde273bfab6061Dan Gohman ++NumNodes; 86e1dfc7da8991270db5094aa736fde273bfab6061Dan Gohman } 87343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 88e1dfc7da8991270db5094aa736fde273bfab6061Dan Gohman // Reserve entries in the vector for each of the SUnits we are creating. This 89e1dfc7da8991270db5094aa736fde273bfab6061Dan Gohman // ensure that reallocation of the vector won't happen, so SUnit*'s won't get 90e1dfc7da8991270db5094aa736fde273bfab6061Dan Gohman // invalidated. 91e1dfc7da8991270db5094aa736fde273bfab6061Dan Gohman // FIXME: Multiply by 2 because we may clone nodes during scheduling. 92e1dfc7da8991270db5094aa736fde273bfab6061Dan Gohman // This is a temporary workaround. 93e1dfc7da8991270db5094aa736fde273bfab6061Dan Gohman SUnits.reserve(NumNodes * 2); 94e1dfc7da8991270db5094aa736fde273bfab6061Dan Gohman 953f23744df4809eba94284e601e81489212c974d4Dan Gohman // Check to see if the scheduler cares about latencies. 963f23744df4809eba94284e601e81489212c974d4Dan Gohman bool UnitLatencies = ForceUnitLatencies(); 973f23744df4809eba94284e601e81489212c974d4Dan Gohman 98343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman for (SelectionDAG::allnodes_iterator NI = DAG->allnodes_begin(), 99343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman E = DAG->allnodes_end(); NI != E; ++NI) { 100343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (isPassiveNode(NI)) // Leaf node, e.g. a TargetImmediate. 101343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman continue; 102343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 103343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // If this node has already been processed, stop now. 104343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (NI->getNodeId() != -1) continue; 105343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 106343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SUnit *NodeSUnit = NewSUnit(NI); 107343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 108343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // See if anything is flagged to this node, if so, add them to flagged 109343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // nodes. Nodes can have at most one flag input and one flag output. Flags 110db95fa131a229652f925794ca7a5b84e9490050bDan Gohman // are required to be the last operand and result of a node. 111343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 112343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // Scan up to find flagged preds. 113343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SDNode *N = NI; 114db95fa131a229652f925794ca7a5b84e9490050bDan Gohman while (N->getNumOperands() && 115825b72b0571821bf2d378749f69d6c4cfb52d2f9Owen Anderson N->getOperand(N->getNumOperands()-1).getValueType() == MVT::Flag) { 116db95fa131a229652f925794ca7a5b84e9490050bDan Gohman N = N->getOperand(N->getNumOperands()-1).getNode(); 117db95fa131a229652f925794ca7a5b84e9490050bDan Gohman assert(N->getNodeId() == -1 && "Node already inserted!"); 118db95fa131a229652f925794ca7a5b84e9490050bDan Gohman N->setNodeId(NodeSUnit->NodeNum); 119343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 120343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 121343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // Scan down to find any flagged succs. 122343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman N = NI; 123825b72b0571821bf2d378749f69d6c4cfb52d2f9Owen Anderson while (N->getValueType(N->getNumValues()-1) == MVT::Flag) { 124343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SDValue FlagVal(N, N->getNumValues()-1); 125343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 126343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // There are either zero or one users of the Flag result. 127343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman bool HasFlagUse = false; 128343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman for (SDNode::use_iterator UI = N->use_begin(), E = N->use_end(); 129343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman UI != E; ++UI) 130343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (FlagVal.isOperandOf(*UI)) { 131343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman HasFlagUse = true; 132343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman assert(N->getNodeId() == -1 && "Node already inserted!"); 133343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman N->setNodeId(NodeSUnit->NodeNum); 134343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman N = *UI; 135343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman break; 136343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 137343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (!HasFlagUse) break; 138343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 139343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 140343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // If there are flag operands involved, N is now the bottom-most node 141343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // of the sequence of nodes that are flagged together. 142343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // Update the SUnit. 143343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman NodeSUnit->setNode(N); 144343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman assert(N->getNodeId() == -1 && "Node already inserted!"); 145343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman N->setNodeId(NodeSUnit->NodeNum); 146343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 147787782f4ca0cca2523825131c24a6f78535a3eb8Dan Gohman // Assign the Latency field of NodeSUnit using target-provided information. 1483f23744df4809eba94284e601e81489212c974d4Dan Gohman if (UnitLatencies) 1493f23744df4809eba94284e601e81489212c974d4Dan Gohman NodeSUnit->Latency = 1; 1503f23744df4809eba94284e601e81489212c974d4Dan Gohman else 1513f23744df4809eba94284e601e81489212c974d4Dan Gohman ComputeLatency(NodeSUnit); 152343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 153c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman} 154c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman 155c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohmanvoid ScheduleDAGSDNodes::AddSchedEdges() { 156710461688bba935f0ad5c75da7fec2ad0f225c00David Goodwin const TargetSubtarget &ST = TM.getSubtarget<TargetSubtarget>(); 157710461688bba935f0ad5c75da7fec2ad0f225c00David Goodwin 158dc4bdcdef1c8dd1a28b82deb08df039e5c0ffc5aDavid Goodwin // Check to see if the scheduler cares about latencies. 159dc4bdcdef1c8dd1a28b82deb08df039e5c0ffc5aDavid Goodwin bool UnitLatencies = ForceUnitLatencies(); 160dc4bdcdef1c8dd1a28b82deb08df039e5c0ffc5aDavid Goodwin 161343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // Pass 2: add the preds, succs, etc. 162343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman for (unsigned su = 0, e = SUnits.size(); su != e; ++su) { 163343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SUnit *SU = &SUnits[su]; 164343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SDNode *MainNode = SU->getNode(); 165343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 166343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (MainNode->isMachineOpcode()) { 167343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman unsigned Opc = MainNode->getMachineOpcode(); 168343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman const TargetInstrDesc &TID = TII->get(Opc); 169343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman for (unsigned i = 0; i != TID.getNumOperands(); ++i) { 170343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (TID.getOperandConstraint(i, TOI::TIED_TO) != -1) { 171343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SU->isTwoAddress = true; 172343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman break; 173343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 174343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 175343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (TID.isCommutable()) 176343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SU->isCommutable = true; 177343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 178343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 179343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // Find all predecessors and successors of the group. 180343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman for (SDNode *N = SU->getNode(); N; N = N->getFlaggedNode()) { 181343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (N->isMachineOpcode() && 1823974667c1a6d48686e92f85bc4463bb239af7442Dan Gohman TII->get(N->getMachineOpcode()).getImplicitDefs()) { 1833974667c1a6d48686e92f85bc4463bb239af7442Dan Gohman SU->hasPhysRegClobbers = true; 1848cccf0ef0ced7f4d75ca574b596036a9b6cd4315Dan Gohman unsigned NumUsed = CountResults(N); 1858cccf0ef0ced7f4d75ca574b596036a9b6cd4315Dan Gohman while (NumUsed != 0 && !N->hasAnyUseOfValue(NumUsed - 1)) 1868cccf0ef0ced7f4d75ca574b596036a9b6cd4315Dan Gohman --NumUsed; // Skip over unused values at the end. 1878cccf0ef0ced7f4d75ca574b596036a9b6cd4315Dan Gohman if (NumUsed > TII->get(N->getMachineOpcode()).getNumDefs()) 1883974667c1a6d48686e92f85bc4463bb239af7442Dan Gohman SU->hasPhysRegDefs = true; 1893974667c1a6d48686e92f85bc4463bb239af7442Dan Gohman } 190343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 191343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) { 192343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SDNode *OpN = N->getOperand(i).getNode(); 193343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (isPassiveNode(OpN)) continue; // Not scheduled. 194343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SUnit *OpSU = &SUnits[OpN->getNodeId()]; 195343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman assert(OpSU && "Node has no SUnit!"); 196343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (OpSU == SU) continue; // In the same group. 197343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 198e50ed30282bb5b4a9ed952580523f2dda16215acOwen Anderson EVT OpVT = N->getOperand(i).getValueType(); 199825b72b0571821bf2d378749f69d6c4cfb52d2f9Owen Anderson assert(OpVT != MVT::Flag && "Flagged nodes should be in same sunit!"); 200825b72b0571821bf2d378749f69d6c4cfb52d2f9Owen Anderson bool isChain = OpVT == MVT::Other; 201343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 202343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman unsigned PhysReg = 0; 203c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng int Cost = 1; 204343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // Determine if this is a physical register dependency. 205c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng CheckForPhysRegDependency(OpN, N, i, TRI, TII, PhysReg, Cost); 20654e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman assert((PhysReg == 0 || !isChain) && 20754e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman "Chain dependence via physreg data?"); 208c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng // FIXME: See ScheduleDAGSDNodes::EmitCopyFromReg. For now, scheduler 209c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng // emits a copy from the physical register to a virtual register unless 210c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng // it requires a cross class copy (cost < 0). That means we are only 211c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng // treating "expensive to copy" register dependency as physical register 212c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng // dependency. This may change in the future though. 213c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng if (Cost >= 0) 214c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng PhysReg = 0; 215710461688bba935f0ad5c75da7fec2ad0f225c00David Goodwin 216710461688bba935f0ad5c75da7fec2ad0f225c00David Goodwin const SDep& dep = SDep(OpSU, isChain ? SDep::Order : SDep::Data, 217710461688bba935f0ad5c75da7fec2ad0f225c00David Goodwin OpSU->Latency, PhysReg); 218dc4bdcdef1c8dd1a28b82deb08df039e5c0ffc5aDavid Goodwin if (!isChain && !UnitLatencies) { 219dc4bdcdef1c8dd1a28b82deb08df039e5c0ffc5aDavid Goodwin ComputeOperandLatency(OpSU, SU, (SDep &)dep); 220dc4bdcdef1c8dd1a28b82deb08df039e5c0ffc5aDavid Goodwin ST.adjustSchedDependency(OpSU, SU, (SDep &)dep); 221dc4bdcdef1c8dd1a28b82deb08df039e5c0ffc5aDavid Goodwin } 222710461688bba935f0ad5c75da7fec2ad0f225c00David Goodwin 223710461688bba935f0ad5c75da7fec2ad0f225c00David Goodwin SU->addPred(dep); 224343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 225343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 226343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 227343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman} 228343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 229c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman/// BuildSchedGraph - Build the SUnit graph from the selection dag that we 230c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman/// are input. This SUnit graph is similar to the SelectionDAG, but 231c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman/// excludes nodes that aren't interesting to scheduling, and represents 232c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman/// flagged together nodes with a single SUnit. 23398976e4dcd18adbbe676048c0069e67346eb4adeDan Gohmanvoid ScheduleDAGSDNodes::BuildSchedGraph(AliasAnalysis *AA) { 234c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman // Populate the SUnits array. 235c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman BuildSchedUnits(); 236c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman // Compute all the scheduling dependencies between nodes. 237c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman AddSchedEdges(); 238c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman} 239c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman 240343f0c046702831a4a6aec951b6a297a23241a55Dan Gohmanvoid ScheduleDAGSDNodes::ComputeLatency(SUnit *SU) { 241343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman const InstrItineraryData &InstrItins = TM.getInstrItineraryData(); 242343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 243343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // Compute the latency for the node. We use the sum of the latencies for 244343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // all nodes flagged together into this SUnit. 245343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SU->Latency = 0; 246c8c2827993204207ca70a93f62f233fbe81b97efDan Gohman for (SDNode *N = SU->getNode(); N; N = N->getFlaggedNode()) 247343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (N->isMachineOpcode()) { 248dc4bdcdef1c8dd1a28b82deb08df039e5c0ffc5aDavid Goodwin SU->Latency += InstrItins. 249dc4bdcdef1c8dd1a28b82deb08df039e5c0ffc5aDavid Goodwin getStageLatency(TII->get(N->getMachineOpcode()).getSchedClass()); 250343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 251343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman} 252343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 253343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman/// CountResults - The results of target nodes have register or immediate 254343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman/// operands first, then an optional chain, and optional flag operands (which do 255343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman/// not go into the resulting MachineInstr). 256343f0c046702831a4a6aec951b6a297a23241a55Dan Gohmanunsigned ScheduleDAGSDNodes::CountResults(SDNode *Node) { 257343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman unsigned N = Node->getNumValues(); 258825b72b0571821bf2d378749f69d6c4cfb52d2f9Owen Anderson while (N && Node->getValueType(N - 1) == MVT::Flag) 259343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman --N; 260825b72b0571821bf2d378749f69d6c4cfb52d2f9Owen Anderson if (N && Node->getValueType(N - 1) == MVT::Other) 261343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman --N; // Skip over chain result. 262343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman return N; 263343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman} 264343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 265343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman/// CountOperands - The inputs to target nodes have any actual inputs first, 266c76909abfec876c6b751d693ebd3df07df686aa0Dan Gohman/// followed by an optional chain operand, then an optional flag operand. 267c76909abfec876c6b751d693ebd3df07df686aa0Dan Gohman/// Compute the number of actual operands that will go into the resulting 268c76909abfec876c6b751d693ebd3df07df686aa0Dan Gohman/// MachineInstr. 269343f0c046702831a4a6aec951b6a297a23241a55Dan Gohmanunsigned ScheduleDAGSDNodes::CountOperands(SDNode *Node) { 270343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman unsigned N = Node->getNumOperands(); 271825b72b0571821bf2d378749f69d6c4cfb52d2f9Owen Anderson while (N && Node->getOperand(N - 1).getValueType() == MVT::Flag) 272343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman --N; 273825b72b0571821bf2d378749f69d6c4cfb52d2f9Owen Anderson if (N && Node->getOperand(N - 1).getValueType() == MVT::Other) 274343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman --N; // Ignore chain if it exists. 275343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman return N; 276343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman} 277343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 278343f0c046702831a4a6aec951b6a297a23241a55Dan Gohmanvoid ScheduleDAGSDNodes::dumpNode(const SUnit *SU) const { 279c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng if (!SU->getNode()) { 2801cd1d98232c3c3a0bd3810c3bf6c2572ea02f208Daniel Dunbar errs() << "PHYS REG COPY\n"; 281c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng return; 282c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng } 283c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng 284c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng SU->getNode()->dump(DAG); 2851cd1d98232c3c3a0bd3810c3bf6c2572ea02f208Daniel Dunbar errs() << "\n"; 286343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SmallVector<SDNode *, 4> FlaggedNodes; 287343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman for (SDNode *N = SU->getNode()->getFlaggedNode(); N; N = N->getFlaggedNode()) 288343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman FlaggedNodes.push_back(N); 289343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman while (!FlaggedNodes.empty()) { 2901cd1d98232c3c3a0bd3810c3bf6c2572ea02f208Daniel Dunbar errs() << " "; 291343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman FlaggedNodes.back()->dump(DAG); 2921cd1d98232c3c3a0bd3810c3bf6c2572ea02f208Daniel Dunbar errs() << "\n"; 293343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman FlaggedNodes.pop_back(); 294343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 295343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman} 296