ScheduleDAGSDNodes.cpp revision 819309efec6f11ba752bd7cbfe186495745f020b
1//===--- ScheduleDAGSDNodes.cpp - Implement the ScheduleDAGSDNodes class --===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This implements the ScheduleDAG class, which is a base class used by 11// scheduling implementation classes. 12// 13//===----------------------------------------------------------------------===// 14 15#define DEBUG_TYPE "pre-RA-sched" 16#include "ScheduleDAGSDNodes.h" 17#include "InstrEmitter.h" 18#include "llvm/CodeGen/SelectionDAG.h" 19#include "llvm/Target/TargetMachine.h" 20#include "llvm/Target/TargetInstrInfo.h" 21#include "llvm/Target/TargetRegisterInfo.h" 22#include "llvm/Target/TargetSubtarget.h" 23#include "llvm/Support/CommandLine.h" 24#include "llvm/Support/Debug.h" 25#include "llvm/Support/raw_ostream.h" 26using namespace llvm; 27 28cl::opt<bool> 29DisableInstScheduling("disable-inst-scheduling", 30 cl::init(false), 31 cl::desc("Disable instruction scheduling")); 32 33ScheduleDAGSDNodes::ScheduleDAGSDNodes(MachineFunction &mf) 34 : ScheduleDAG(mf) { 35} 36 37/// Run - perform scheduling. 38/// 39void ScheduleDAGSDNodes::Run(SelectionDAG *dag, MachineBasicBlock *bb, 40 MachineBasicBlock::iterator insertPos) { 41 DAG = dag; 42 ScheduleDAG::Run(bb, insertPos); 43} 44 45SUnit *ScheduleDAGSDNodes::Clone(SUnit *Old) { 46 SUnit *SU = NewSUnit(Old->getNode()); 47 SU->OrigNode = Old->OrigNode; 48 SU->Latency = Old->Latency; 49 SU->isTwoAddress = Old->isTwoAddress; 50 SU->isCommutable = Old->isCommutable; 51 SU->hasPhysRegDefs = Old->hasPhysRegDefs; 52 SU->hasPhysRegClobbers = Old->hasPhysRegClobbers; 53 Old->isCloned = true; 54 return SU; 55} 56 57/// CheckForPhysRegDependency - Check if the dependency between def and use of 58/// a specified operand is a physical register dependency. If so, returns the 59/// register and the cost of copying the register. 60static void CheckForPhysRegDependency(SDNode *Def, SDNode *User, unsigned Op, 61 const TargetRegisterInfo *TRI, 62 const TargetInstrInfo *TII, 63 unsigned &PhysReg, int &Cost) { 64 if (Op != 2 || User->getOpcode() != ISD::CopyToReg) 65 return; 66 67 unsigned Reg = cast<RegisterSDNode>(User->getOperand(1))->getReg(); 68 if (TargetRegisterInfo::isVirtualRegister(Reg)) 69 return; 70 71 unsigned ResNo = User->getOperand(2).getResNo(); 72 if (Def->isMachineOpcode()) { 73 const TargetInstrDesc &II = TII->get(Def->getMachineOpcode()); 74 if (ResNo >= II.getNumDefs() && 75 II.ImplicitDefs[ResNo - II.getNumDefs()] == Reg) { 76 PhysReg = Reg; 77 const TargetRegisterClass *RC = 78 TRI->getPhysicalRegisterRegClass(Reg, Def->getValueType(ResNo)); 79 Cost = RC->getCopyCost(); 80 } 81 } 82} 83 84void ScheduleDAGSDNodes::BuildSchedUnits() { 85 // During scheduling, the NodeId field of SDNode is used to map SDNodes 86 // to their associated SUnits by holding SUnits table indices. A value 87 // of -1 means the SDNode does not yet have an associated SUnit. 88 unsigned NumNodes = 0; 89 for (SelectionDAG::allnodes_iterator NI = DAG->allnodes_begin(), 90 E = DAG->allnodes_end(); NI != E; ++NI) { 91 NI->setNodeId(-1); 92 ++NumNodes; 93 } 94 95 // Reserve entries in the vector for each of the SUnits we are creating. This 96 // ensure that reallocation of the vector won't happen, so SUnit*'s won't get 97 // invalidated. 98 // FIXME: Multiply by 2 because we may clone nodes during scheduling. 99 // This is a temporary workaround. 100 SUnits.reserve(NumNodes * 2); 101 102 // Check to see if the scheduler cares about latencies. 103 bool UnitLatencies = ForceUnitLatencies(); 104 105 for (SelectionDAG::allnodes_iterator NI = DAG->allnodes_begin(), 106 E = DAG->allnodes_end(); NI != E; ++NI) { 107 if (isPassiveNode(NI)) // Leaf node, e.g. a TargetImmediate. 108 continue; 109 110 // If this node has already been processed, stop now. 111 if (NI->getNodeId() != -1) continue; 112 113 SUnit *NodeSUnit = NewSUnit(NI); 114 115 // See if anything is flagged to this node, if so, add them to flagged 116 // nodes. Nodes can have at most one flag input and one flag output. Flags 117 // are required to be the last operand and result of a node. 118 119 // Scan up to find flagged preds. 120 SDNode *N = NI; 121 while (N->getNumOperands() && 122 N->getOperand(N->getNumOperands()-1).getValueType() == MVT::Flag) { 123 N = N->getOperand(N->getNumOperands()-1).getNode(); 124 assert(N->getNodeId() == -1 && "Node already inserted!"); 125 N->setNodeId(NodeSUnit->NodeNum); 126 } 127 128 // Scan down to find any flagged succs. 129 N = NI; 130 while (N->getValueType(N->getNumValues()-1) == MVT::Flag) { 131 SDValue FlagVal(N, N->getNumValues()-1); 132 133 // There are either zero or one users of the Flag result. 134 bool HasFlagUse = false; 135 for (SDNode::use_iterator UI = N->use_begin(), E = N->use_end(); 136 UI != E; ++UI) 137 if (FlagVal.isOperandOf(*UI)) { 138 HasFlagUse = true; 139 assert(N->getNodeId() == -1 && "Node already inserted!"); 140 N->setNodeId(NodeSUnit->NodeNum); 141 N = *UI; 142 break; 143 } 144 if (!HasFlagUse) break; 145 } 146 147 // If there are flag operands involved, N is now the bottom-most node 148 // of the sequence of nodes that are flagged together. 149 // Update the SUnit. 150 NodeSUnit->setNode(N); 151 assert(N->getNodeId() == -1 && "Node already inserted!"); 152 N->setNodeId(NodeSUnit->NodeNum); 153 154 // Assign the Latency field of NodeSUnit using target-provided information. 155 if (UnitLatencies) 156 NodeSUnit->Latency = 1; 157 else 158 ComputeLatency(NodeSUnit); 159 } 160} 161 162void ScheduleDAGSDNodes::AddSchedEdges() { 163 const TargetSubtarget &ST = TM.getSubtarget<TargetSubtarget>(); 164 165 // Check to see if the scheduler cares about latencies. 166 bool UnitLatencies = ForceUnitLatencies(); 167 168 // Pass 2: add the preds, succs, etc. 169 for (unsigned su = 0, e = SUnits.size(); su != e; ++su) { 170 SUnit *SU = &SUnits[su]; 171 SDNode *MainNode = SU->getNode(); 172 173 if (MainNode->isMachineOpcode()) { 174 unsigned Opc = MainNode->getMachineOpcode(); 175 const TargetInstrDesc &TID = TII->get(Opc); 176 for (unsigned i = 0; i != TID.getNumOperands(); ++i) { 177 if (TID.getOperandConstraint(i, TOI::TIED_TO) != -1) { 178 SU->isTwoAddress = true; 179 break; 180 } 181 } 182 if (TID.isCommutable()) 183 SU->isCommutable = true; 184 } 185 186 // Find all predecessors and successors of the group. 187 for (SDNode *N = SU->getNode(); N; N = N->getFlaggedNode()) { 188 if (N->isMachineOpcode() && 189 TII->get(N->getMachineOpcode()).getImplicitDefs()) { 190 SU->hasPhysRegClobbers = true; 191 unsigned NumUsed = InstrEmitter::CountResults(N); 192 while (NumUsed != 0 && !N->hasAnyUseOfValue(NumUsed - 1)) 193 --NumUsed; // Skip over unused values at the end. 194 if (NumUsed > TII->get(N->getMachineOpcode()).getNumDefs()) 195 SU->hasPhysRegDefs = true; 196 } 197 198 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) { 199 SDNode *OpN = N->getOperand(i).getNode(); 200 if (isPassiveNode(OpN)) continue; // Not scheduled. 201 SUnit *OpSU = &SUnits[OpN->getNodeId()]; 202 assert(OpSU && "Node has no SUnit!"); 203 if (OpSU == SU) continue; // In the same group. 204 205 EVT OpVT = N->getOperand(i).getValueType(); 206 assert(OpVT != MVT::Flag && "Flagged nodes should be in same sunit!"); 207 bool isChain = OpVT == MVT::Other; 208 209 unsigned PhysReg = 0; 210 int Cost = 1; 211 // Determine if this is a physical register dependency. 212 CheckForPhysRegDependency(OpN, N, i, TRI, TII, PhysReg, Cost); 213 assert((PhysReg == 0 || !isChain) && 214 "Chain dependence via physreg data?"); 215 // FIXME: See ScheduleDAGSDNodes::EmitCopyFromReg. For now, scheduler 216 // emits a copy from the physical register to a virtual register unless 217 // it requires a cross class copy (cost < 0). That means we are only 218 // treating "expensive to copy" register dependency as physical register 219 // dependency. This may change in the future though. 220 if (Cost >= 0) 221 PhysReg = 0; 222 223 const SDep& dep = SDep(OpSU, isChain ? SDep::Order : SDep::Data, 224 OpSU->Latency, PhysReg); 225 if (!isChain && !UnitLatencies) { 226 ComputeOperandLatency(OpSU, SU, (SDep &)dep); 227 ST.adjustSchedDependency(OpSU, SU, (SDep &)dep); 228 } 229 230 SU->addPred(dep); 231 } 232 } 233 } 234} 235 236/// BuildSchedGraph - Build the SUnit graph from the selection dag that we 237/// are input. This SUnit graph is similar to the SelectionDAG, but 238/// excludes nodes that aren't interesting to scheduling, and represents 239/// flagged together nodes with a single SUnit. 240void ScheduleDAGSDNodes::BuildSchedGraph(AliasAnalysis *AA) { 241 // Populate the SUnits array. 242 BuildSchedUnits(); 243 // Compute all the scheduling dependencies between nodes. 244 AddSchedEdges(); 245} 246 247void ScheduleDAGSDNodes::ComputeLatency(SUnit *SU) { 248 const InstrItineraryData &InstrItins = TM.getInstrItineraryData(); 249 250 // Compute the latency for the node. We use the sum of the latencies for 251 // all nodes flagged together into this SUnit. 252 SU->Latency = 0; 253 for (SDNode *N = SU->getNode(); N; N = N->getFlaggedNode()) 254 if (N->isMachineOpcode()) { 255 SU->Latency += InstrItins. 256 getStageLatency(TII->get(N->getMachineOpcode()).getSchedClass()); 257 } 258} 259 260void ScheduleDAGSDNodes::dumpNode(const SUnit *SU) const { 261 if (!SU->getNode()) { 262 errs() << "PHYS REG COPY\n"; 263 return; 264 } 265 266 SU->getNode()->dump(DAG); 267 errs() << "\n"; 268 SmallVector<SDNode *, 4> FlaggedNodes; 269 for (SDNode *N = SU->getNode()->getFlaggedNode(); N; N = N->getFlaggedNode()) 270 FlaggedNodes.push_back(N); 271 while (!FlaggedNodes.empty()) { 272 errs() << " "; 273 FlaggedNodes.back()->dump(DAG); 274 errs() << "\n"; 275 FlaggedNodes.pop_back(); 276 } 277} 278 279/// EmitSchedule - Emit the machine code in scheduled order. 280MachineBasicBlock *ScheduleDAGSDNodes:: 281EmitSchedule(DenseMap<MachineBasicBlock*, MachineBasicBlock*> *EM) { 282 InstrEmitter Emitter(BB, InsertPos); 283 DenseMap<SDValue, unsigned> VRBaseMap; 284 DenseMap<SUnit*, unsigned> CopyVRBaseMap; 285 for (unsigned i = 0, e = Sequence.size(); i != e; i++) { 286 SUnit *SU = Sequence[i]; 287 if (!SU) { 288 // Null SUnit* is a noop. 289 EmitNoop(); 290 continue; 291 } 292 293 // For pre-regalloc scheduling, create instructions corresponding to the 294 // SDNode and any flagged SDNodes and append them to the block. 295 if (!SU->getNode()) { 296 // Emit a copy. 297 EmitPhysRegCopy(SU, CopyVRBaseMap); 298 continue; 299 } 300 301 SmallVector<SDNode *, 4> FlaggedNodes; 302 for (SDNode *N = SU->getNode()->getFlaggedNode(); N; 303 N = N->getFlaggedNode()) 304 FlaggedNodes.push_back(N); 305 while (!FlaggedNodes.empty()) { 306 Emitter.EmitNode(FlaggedNodes.back(), SU->OrigNode != SU, SU->isCloned, 307 VRBaseMap, EM); 308 FlaggedNodes.pop_back(); 309 } 310 Emitter.EmitNode(SU->getNode(), SU->OrigNode != SU, SU->isCloned, 311 VRBaseMap, EM); 312 } 313 314 BB = Emitter.getBlock(); 315 InsertPos = Emitter.getInsertPos(); 316 return BB; 317} 318