LLVM API Documentation
00001 //===--- ScheduleDAGSDNodes.cpp - Implement the ScheduleDAGSDNodes class --===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This implements the ScheduleDAG class, which is a base class used by 00011 // scheduling implementation classes. 00012 // 00013 //===----------------------------------------------------------------------===// 00014 00015 #define DEBUG_TYPE "pre-RA-sched" 00016 #include "ScheduleDAGSDNodes.h" 00017 #include "llvm/CodeGen/SelectionDAG.h" 00018 #include "llvm/Target/TargetMachine.h" 00019 #include "llvm/Target/TargetInstrInfo.h" 00020 #include "llvm/Target/TargetRegisterInfo.h" 00021 #include "llvm/Target/TargetSubtarget.h" 00022 #include "llvm/Support/Debug.h" 00023 #include "llvm/Support/raw_ostream.h" 00024 using namespace llvm; 00025 00026 ScheduleDAGSDNodes::ScheduleDAGSDNodes(MachineFunction &mf) 00027 : ScheduleDAG(mf) { 00028 } 00029 00030 /// Run - perform scheduling. 00031 /// 00032 void ScheduleDAGSDNodes::Run(SelectionDAG *dag, MachineBasicBlock *bb, 00033 MachineBasicBlock::iterator insertPos) { 00034 DAG = dag; 00035 ScheduleDAG::Run(bb, insertPos); 00036 } 00037 00038 SUnit *ScheduleDAGSDNodes::Clone(SUnit *Old) { 00039 SUnit *SU = NewSUnit(Old->getNode()); 00040 SU->OrigNode = Old->OrigNode; 00041 SU->Latency = Old->Latency; 00042 SU->isTwoAddress = Old->isTwoAddress; 00043 SU->isCommutable = Old->isCommutable; 00044 SU->hasPhysRegDefs = Old->hasPhysRegDefs; 00045 SU->hasPhysRegClobbers = Old->hasPhysRegClobbers; 00046 Old->isCloned = true; 00047 return SU; 00048 } 00049 00050 /// CheckForPhysRegDependency - Check if the dependency between def and use of 00051 /// a specified operand is a physical register dependency. If so, returns the 00052 /// register and the cost of copying the register. 00053 static void CheckForPhysRegDependency(SDNode *Def, SDNode *User, unsigned Op, 00054 const TargetRegisterInfo *TRI, 00055 const TargetInstrInfo *TII, 00056 unsigned &PhysReg, int &Cost) { 00057 if (Op != 2 || User->getOpcode() != ISD::CopyToReg) 00058 return; 00059 00060 unsigned Reg = cast<RegisterSDNode>(User->getOperand(1))->getReg(); 00061 if (TargetRegisterInfo::isVirtualRegister(Reg)) 00062 return; 00063 00064 unsigned ResNo = User->getOperand(2).getResNo(); 00065 if (Def->isMachineOpcode()) { 00066 const TargetInstrDesc &II = TII->get(Def->getMachineOpcode()); 00067 if (ResNo >= II.getNumDefs() && 00068 II.ImplicitDefs[ResNo - II.getNumDefs()] == Reg) { 00069 PhysReg = Reg; 00070 const TargetRegisterClass *RC = 00071 TRI->getPhysicalRegisterRegClass(Reg, Def->getValueType(ResNo)); 00072 Cost = RC->getCopyCost(); 00073 } 00074 } 00075 } 00076 00077 void ScheduleDAGSDNodes::BuildSchedUnits() { 00078 // During scheduling, the NodeId field of SDNode is used to map SDNodes 00079 // to their associated SUnits by holding SUnits table indices. A value 00080 // of -1 means the SDNode does not yet have an associated SUnit. 00081 unsigned NumNodes = 0; 00082 for (SelectionDAG::allnodes_iterator NI = DAG->allnodes_begin(), 00083 E = DAG->allnodes_end(); NI != E; ++NI) { 00084 NI->setNodeId(-1); 00085 ++NumNodes; 00086 } 00087 00088 // Reserve entries in the vector for each of the SUnits we are creating. This 00089 // ensure that reallocation of the vector won't happen, so SUnit*'s won't get 00090 // invalidated. 00091 // FIXME: Multiply by 2 because we may clone nodes during scheduling. 00092 // This is a temporary workaround. 00093 SUnits.reserve(NumNodes * 2); 00094 00095 // Check to see if the scheduler cares about latencies. 00096 bool UnitLatencies = ForceUnitLatencies(); 00097 00098 for (SelectionDAG::allnodes_iterator NI = DAG->allnodes_begin(), 00099 E = DAG->allnodes_end(); NI != E; ++NI) { 00100 if (isPassiveNode(NI)) // Leaf node, e.g. a TargetImmediate. 00101 continue; 00102 00103 // If this node has already been processed, stop now. 00104 if (NI->getNodeId() != -1) continue; 00105 00106 SUnit *NodeSUnit = NewSUnit(NI); 00107 00108 // See if anything is flagged to this node, if so, add them to flagged 00109 // nodes. Nodes can have at most one flag input and one flag output. Flags 00110 // are required to be the last operand and result of a node. 00111 00112 // Scan up to find flagged preds. 00113 SDNode *N = NI; 00114 while (N->getNumOperands() && 00115 N->getOperand(N->getNumOperands()-1).getValueType() == MVT::Flag) { 00116 N = N->getOperand(N->getNumOperands()-1).getNode(); 00117 assert(N->getNodeId() == -1 && "Node already inserted!"); 00118 N->setNodeId(NodeSUnit->NodeNum); 00119 } 00120 00121 // Scan down to find any flagged succs. 00122 N = NI; 00123 while (N->getValueType(N->getNumValues()-1) == MVT::Flag) { 00124 SDValue FlagVal(N, N->getNumValues()-1); 00125 00126 // There are either zero or one users of the Flag result. 00127 bool HasFlagUse = false; 00128 for (SDNode::use_iterator UI = N->use_begin(), E = N->use_end(); 00129 UI != E; ++UI) 00130 if (FlagVal.isOperandOf(*UI)) { 00131 HasFlagUse = true; 00132 assert(N->getNodeId() == -1 && "Node already inserted!"); 00133 N->setNodeId(NodeSUnit->NodeNum); 00134 N = *UI; 00135 break; 00136 } 00137 if (!HasFlagUse) break; 00138 } 00139 00140 // If there are flag operands involved, N is now the bottom-most node 00141 // of the sequence of nodes that are flagged together. 00142 // Update the SUnit. 00143 NodeSUnit->setNode(N); 00144 assert(N->getNodeId() == -1 && "Node already inserted!"); 00145 N->setNodeId(NodeSUnit->NodeNum); 00146 00147 // Assign the Latency field of NodeSUnit using target-provided information. 00148 if (UnitLatencies) 00149 NodeSUnit->Latency = 1; 00150 else 00151 ComputeLatency(NodeSUnit); 00152 } 00153 } 00154 00155 void ScheduleDAGSDNodes::AddSchedEdges() { 00156 const TargetSubtarget &ST = TM.getSubtarget<TargetSubtarget>(); 00157 00158 // Check to see if the scheduler cares about latencies. 00159 bool UnitLatencies = ForceUnitLatencies(); 00160 00161 // Pass 2: add the preds, succs, etc. 00162 for (unsigned su = 0, e = SUnits.size(); su != e; ++su) { 00163 SUnit *SU = &SUnits[su]; 00164 SDNode *MainNode = SU->getNode(); 00165 00166 if (MainNode->isMachineOpcode()) { 00167 unsigned Opc = MainNode->getMachineOpcode(); 00168 const TargetInstrDesc &TID = TII->get(Opc); 00169 for (unsigned i = 0; i != TID.getNumOperands(); ++i) { 00170 if (TID.getOperandConstraint(i, TOI::TIED_TO) != -1) { 00171 SU->isTwoAddress = true; 00172 break; 00173 } 00174 } 00175 if (TID.isCommutable()) 00176 SU->isCommutable = true; 00177 } 00178 00179 // Find all predecessors and successors of the group. 00180 for (SDNode *N = SU->getNode(); N; N = N->getFlaggedNode()) { 00181 if (N->isMachineOpcode() && 00182 TII->get(N->getMachineOpcode()).getImplicitDefs()) { 00183 SU->hasPhysRegClobbers = true; 00184 unsigned NumUsed = CountResults(N); 00185 while (NumUsed != 0 && !N->hasAnyUseOfValue(NumUsed - 1)) 00186 --NumUsed; // Skip over unused values at the end. 00187 if (NumUsed > TII->get(N->getMachineOpcode()).getNumDefs()) 00188 SU->hasPhysRegDefs = true; 00189 } 00190 00191 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) { 00192 SDNode *OpN = N->getOperand(i).getNode(); 00193 if (isPassiveNode(OpN)) continue; // Not scheduled. 00194 SUnit *OpSU = &SUnits[OpN->getNodeId()]; 00195 assert(OpSU && "Node has no SUnit!"); 00196 if (OpSU == SU) continue; // In the same group. 00197 00198 EVT OpVT = N->getOperand(i).getValueType(); 00199 assert(OpVT != MVT::Flag && "Flagged nodes should be in same sunit!"); 00200 bool isChain = OpVT == MVT::Other; 00201 00202 unsigned PhysReg = 0; 00203 int Cost = 1; 00204 // Determine if this is a physical register dependency. 00205 CheckForPhysRegDependency(OpN, N, i, TRI, TII, PhysReg, Cost); 00206 assert((PhysReg == 0 || !isChain) && 00207 "Chain dependence via physreg data?"); 00208 // FIXME: See ScheduleDAGSDNodes::EmitCopyFromReg. For now, scheduler 00209 // emits a copy from the physical register to a virtual register unless 00210 // it requires a cross class copy (cost < 0). That means we are only 00211 // treating "expensive to copy" register dependency as physical register 00212 // dependency. This may change in the future though. 00213 if (Cost >= 0) 00214 PhysReg = 0; 00215 00216 const SDep& dep = SDep(OpSU, isChain ? SDep::Order : SDep::Data, 00217 OpSU->Latency, PhysReg); 00218 if (!isChain && !UnitLatencies) { 00219 ComputeOperandLatency(OpSU, SU, (SDep &)dep); 00220 ST.adjustSchedDependency(OpSU, SU, (SDep &)dep); 00221 } 00222 00223 SU->addPred(dep); 00224 } 00225 } 00226 } 00227 } 00228 00229 /// BuildSchedGraph - Build the SUnit graph from the selection dag that we 00230 /// are input. This SUnit graph is similar to the SelectionDAG, but 00231 /// excludes nodes that aren't interesting to scheduling, and represents 00232 /// flagged together nodes with a single SUnit. 00233 void ScheduleDAGSDNodes::BuildSchedGraph() { 00234 // Populate the SUnits array. 00235 BuildSchedUnits(); 00236 // Compute all the scheduling dependencies between nodes. 00237 AddSchedEdges(); 00238 } 00239 00240 void ScheduleDAGSDNodes::ComputeLatency(SUnit *SU) { 00241 const InstrItineraryData &InstrItins = TM.getInstrItineraryData(); 00242 00243 // Compute the latency for the node. We use the sum of the latencies for 00244 // all nodes flagged together into this SUnit. 00245 SU->Latency = 0; 00246 bool SawMachineOpcode = false; 00247 for (SDNode *N = SU->getNode(); N; N = N->getFlaggedNode()) 00248 if (N->isMachineOpcode()) { 00249 SawMachineOpcode = true; 00250 SU->Latency += InstrItins. 00251 getStageLatency(TII->get(N->getMachineOpcode()).getSchedClass()); 00252 } 00253 } 00254 00255 /// CountResults - The results of target nodes have register or immediate 00256 /// operands first, then an optional chain, and optional flag operands (which do 00257 /// not go into the resulting MachineInstr). 00258 unsigned ScheduleDAGSDNodes::CountResults(SDNode *Node) { 00259 unsigned N = Node->getNumValues(); 00260 while (N && Node->getValueType(N - 1) == MVT::Flag) 00261 --N; 00262 if (N && Node->getValueType(N - 1) == MVT::Other) 00263 --N; // Skip over chain result. 00264 return N; 00265 } 00266 00267 /// CountOperands - The inputs to target nodes have any actual inputs first, 00268 /// followed by special operands that describe memory references, then an 00269 /// optional chain operand, then an optional flag operand. Compute the number 00270 /// of actual operands that will go into the resulting MachineInstr. 00271 unsigned ScheduleDAGSDNodes::CountOperands(SDNode *Node) { 00272 unsigned N = ComputeMemOperandsEnd(Node); 00273 while (N && isa<MemOperandSDNode>(Node->getOperand(N - 1).getNode())) 00274 --N; // Ignore MEMOPERAND nodes 00275 return N; 00276 } 00277 00278 /// ComputeMemOperandsEnd - Find the index one past the last MemOperandSDNode 00279 /// operand 00280 unsigned ScheduleDAGSDNodes::ComputeMemOperandsEnd(SDNode *Node) { 00281 unsigned N = Node->getNumOperands(); 00282 while (N && Node->getOperand(N - 1).getValueType() == MVT::Flag) 00283 --N; 00284 if (N && Node->getOperand(N - 1).getValueType() == MVT::Other) 00285 --N; // Ignore chain if it exists. 00286 return N; 00287 } 00288 00289 00290 void ScheduleDAGSDNodes::dumpNode(const SUnit *SU) const { 00291 if (!SU->getNode()) { 00292 errs() << "PHYS REG COPY\n"; 00293 return; 00294 } 00295 00296 SU->getNode()->dump(DAG); 00297 errs() << "\n"; 00298 SmallVector<SDNode *, 4> FlaggedNodes; 00299 for (SDNode *N = SU->getNode()->getFlaggedNode(); N; N = N->getFlaggedNode()) 00300 FlaggedNodes.push_back(N); 00301 while (!FlaggedNodes.empty()) { 00302 errs() << " "; 00303 FlaggedNodes.back()->dump(DAG); 00304 errs() << "\n"; 00305 FlaggedNodes.pop_back(); 00306 } 00307 }