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