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 "SDNodeDbgValue.h" 19#include "llvm/ADT/DenseMap.h" 20#include "llvm/ADT/SmallPtrSet.h" 21#include "llvm/ADT/SmallSet.h" 22#include "llvm/ADT/SmallVector.h" 23#include "llvm/ADT/Statistic.h" 24#include "llvm/CodeGen/MachineInstrBuilder.h" 25#include "llvm/CodeGen/MachineRegisterInfo.h" 26#include "llvm/CodeGen/SelectionDAG.h" 27#include "llvm/MC/MCInstrItineraries.h" 28#include "llvm/Support/CommandLine.h" 29#include "llvm/Support/Debug.h" 30#include "llvm/Support/raw_ostream.h" 31#include "llvm/Target/TargetInstrInfo.h" 32#include "llvm/Target/TargetLowering.h" 33#include "llvm/Target/TargetMachine.h" 34#include "llvm/Target/TargetRegisterInfo.h" 35#include "llvm/Target/TargetSubtargetInfo.h" 36using namespace llvm; 37 38STATISTIC(LoadsClustered, "Number of loads clustered together"); 39 40// This allows latency based scheduler to notice high latency instructions 41// without a target itinerary. The choise if number here has more to do with 42// balancing scheduler heursitics than with the actual machine latency. 43static cl::opt<int> HighLatencyCycles( 44 "sched-high-latency-cycles", cl::Hidden, cl::init(10), 45 cl::desc("Roughly estimate the number of cycles that 'long latency'" 46 "instructions take for targets with no itinerary")); 47 48ScheduleDAGSDNodes::ScheduleDAGSDNodes(MachineFunction &mf) 49 : ScheduleDAG(mf), BB(0), DAG(0), 50 InstrItins(mf.getTarget().getInstrItineraryData()) {} 51 52/// Run - perform scheduling. 53/// 54void ScheduleDAGSDNodes::Run(SelectionDAG *dag, MachineBasicBlock *bb) { 55 BB = bb; 56 DAG = dag; 57 58 // Clear the scheduler's SUnit DAG. 59 ScheduleDAG::clearDAG(); 60 Sequence.clear(); 61 62 // Invoke the target's selection of scheduler. 63 Schedule(); 64} 65 66/// NewSUnit - Creates a new SUnit and return a ptr to it. 67/// 68SUnit *ScheduleDAGSDNodes::newSUnit(SDNode *N) { 69#ifndef NDEBUG 70 const SUnit *Addr = 0; 71 if (!SUnits.empty()) 72 Addr = &SUnits[0]; 73#endif 74 SUnits.push_back(SUnit(N, (unsigned)SUnits.size())); 75 assert((Addr == 0 || Addr == &SUnits[0]) && 76 "SUnits std::vector reallocated on the fly!"); 77 SUnits.back().OrigNode = &SUnits.back(); 78 SUnit *SU = &SUnits.back(); 79 const TargetLowering &TLI = DAG->getTargetLoweringInfo(); 80 if (!N || 81 (N->isMachineOpcode() && 82 N->getMachineOpcode() == TargetOpcode::IMPLICIT_DEF)) 83 SU->SchedulingPref = Sched::None; 84 else 85 SU->SchedulingPref = TLI.getSchedulingPreference(N); 86 return SU; 87} 88 89SUnit *ScheduleDAGSDNodes::Clone(SUnit *Old) { 90 SUnit *SU = newSUnit(Old->getNode()); 91 SU->OrigNode = Old->OrigNode; 92 SU->Latency = Old->Latency; 93 SU->isVRegCycle = Old->isVRegCycle; 94 SU->isCall = Old->isCall; 95 SU->isCallOp = Old->isCallOp; 96 SU->isTwoAddress = Old->isTwoAddress; 97 SU->isCommutable = Old->isCommutable; 98 SU->hasPhysRegDefs = Old->hasPhysRegDefs; 99 SU->hasPhysRegClobbers = Old->hasPhysRegClobbers; 100 SU->isScheduleHigh = Old->isScheduleHigh; 101 SU->isScheduleLow = Old->isScheduleLow; 102 SU->SchedulingPref = Old->SchedulingPref; 103 Old->isCloned = true; 104 return SU; 105} 106 107/// CheckForPhysRegDependency - Check if the dependency between def and use of 108/// a specified operand is a physical register dependency. If so, returns the 109/// register and the cost of copying the register. 110static void CheckForPhysRegDependency(SDNode *Def, SDNode *User, unsigned Op, 111 const TargetRegisterInfo *TRI, 112 const TargetInstrInfo *TII, 113 unsigned &PhysReg, int &Cost) { 114 if (Op != 2 || User->getOpcode() != ISD::CopyToReg) 115 return; 116 117 unsigned Reg = cast<RegisterSDNode>(User->getOperand(1))->getReg(); 118 if (TargetRegisterInfo::isVirtualRegister(Reg)) 119 return; 120 121 unsigned ResNo = User->getOperand(2).getResNo(); 122 if (Def->isMachineOpcode()) { 123 const MCInstrDesc &II = TII->get(Def->getMachineOpcode()); 124 if (ResNo >= II.getNumDefs() && 125 II.ImplicitDefs[ResNo - II.getNumDefs()] == Reg) { 126 PhysReg = Reg; 127 const TargetRegisterClass *RC = 128 TRI->getMinimalPhysRegClass(Reg, Def->getValueType(ResNo)); 129 Cost = RC->getCopyCost(); 130 } 131 } 132} 133 134// Helper for AddGlue to clone node operands. 135static void CloneNodeWithValues(SDNode *N, SelectionDAG *DAG, 136 SmallVectorImpl<EVT> &VTs, 137 SDValue ExtraOper = SDValue()) { 138 SmallVector<SDValue, 4> Ops; 139 for (unsigned I = 0, E = N->getNumOperands(); I != E; ++I) 140 Ops.push_back(N->getOperand(I)); 141 142 if (ExtraOper.getNode()) 143 Ops.push_back(ExtraOper); 144 145 SDVTList VTList = DAG->getVTList(&VTs[0], VTs.size()); 146 MachineSDNode::mmo_iterator Begin = 0, End = 0; 147 MachineSDNode *MN = dyn_cast<MachineSDNode>(N); 148 149 // Store memory references. 150 if (MN) { 151 Begin = MN->memoperands_begin(); 152 End = MN->memoperands_end(); 153 } 154 155 DAG->MorphNodeTo(N, N->getOpcode(), VTList, &Ops[0], Ops.size()); 156 157 // Reset the memory references 158 if (MN) 159 MN->setMemRefs(Begin, End); 160} 161 162static bool AddGlue(SDNode *N, SDValue Glue, bool AddGlue, SelectionDAG *DAG) { 163 SmallVector<EVT, 4> VTs; 164 SDNode *GlueDestNode = Glue.getNode(); 165 166 // Don't add glue from a node to itself. 167 if (GlueDestNode == N) return false; 168 169 // Don't add a glue operand to something that already uses glue. 170 if (GlueDestNode && 171 N->getOperand(N->getNumOperands()-1).getValueType() == MVT::Glue) { 172 return false; 173 } 174 // Don't add glue to something that already has a glue value. 175 if (N->getValueType(N->getNumValues() - 1) == MVT::Glue) return false; 176 177 for (unsigned I = 0, E = N->getNumValues(); I != E; ++I) 178 VTs.push_back(N->getValueType(I)); 179 180 if (AddGlue) 181 VTs.push_back(MVT::Glue); 182 183 CloneNodeWithValues(N, DAG, VTs, Glue); 184 185 return true; 186} 187 188// Cleanup after unsuccessful AddGlue. Use the standard method of morphing the 189// node even though simply shrinking the value list is sufficient. 190static void RemoveUnusedGlue(SDNode *N, SelectionDAG *DAG) { 191 assert((N->getValueType(N->getNumValues() - 1) == MVT::Glue && 192 !N->hasAnyUseOfValue(N->getNumValues() - 1)) && 193 "expected an unused glue value"); 194 195 SmallVector<EVT, 4> VTs; 196 for (unsigned I = 0, E = N->getNumValues()-1; I != E; ++I) 197 VTs.push_back(N->getValueType(I)); 198 199 CloneNodeWithValues(N, DAG, VTs); 200} 201 202/// ClusterNeighboringLoads - Force nearby loads together by "gluing" them. 203/// This function finds loads of the same base and different offsets. If the 204/// offsets are not far apart (target specific), it add MVT::Glue inputs and 205/// outputs to ensure they are scheduled together and in order. This 206/// optimization may benefit some targets by improving cache locality. 207void ScheduleDAGSDNodes::ClusterNeighboringLoads(SDNode *Node) { 208 SDNode *Chain = 0; 209 unsigned NumOps = Node->getNumOperands(); 210 if (Node->getOperand(NumOps-1).getValueType() == MVT::Other) 211 Chain = Node->getOperand(NumOps-1).getNode(); 212 if (!Chain) 213 return; 214 215 // Look for other loads of the same chain. Find loads that are loading from 216 // the same base pointer and different offsets. 217 SmallPtrSet<SDNode*, 16> Visited; 218 SmallVector<int64_t, 4> Offsets; 219 DenseMap<long long, SDNode*> O2SMap; // Map from offset to SDNode. 220 bool Cluster = false; 221 SDNode *Base = Node;
| 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 "SDNodeDbgValue.h" 19#include "llvm/ADT/DenseMap.h" 20#include "llvm/ADT/SmallPtrSet.h" 21#include "llvm/ADT/SmallSet.h" 22#include "llvm/ADT/SmallVector.h" 23#include "llvm/ADT/Statistic.h" 24#include "llvm/CodeGen/MachineInstrBuilder.h" 25#include "llvm/CodeGen/MachineRegisterInfo.h" 26#include "llvm/CodeGen/SelectionDAG.h" 27#include "llvm/MC/MCInstrItineraries.h" 28#include "llvm/Support/CommandLine.h" 29#include "llvm/Support/Debug.h" 30#include "llvm/Support/raw_ostream.h" 31#include "llvm/Target/TargetInstrInfo.h" 32#include "llvm/Target/TargetLowering.h" 33#include "llvm/Target/TargetMachine.h" 34#include "llvm/Target/TargetRegisterInfo.h" 35#include "llvm/Target/TargetSubtargetInfo.h" 36using namespace llvm; 37 38STATISTIC(LoadsClustered, "Number of loads clustered together"); 39 40// This allows latency based scheduler to notice high latency instructions 41// without a target itinerary. The choise if number here has more to do with 42// balancing scheduler heursitics than with the actual machine latency. 43static cl::opt<int> HighLatencyCycles( 44 "sched-high-latency-cycles", cl::Hidden, cl::init(10), 45 cl::desc("Roughly estimate the number of cycles that 'long latency'" 46 "instructions take for targets with no itinerary")); 47 48ScheduleDAGSDNodes::ScheduleDAGSDNodes(MachineFunction &mf) 49 : ScheduleDAG(mf), BB(0), DAG(0), 50 InstrItins(mf.getTarget().getInstrItineraryData()) {} 51 52/// Run - perform scheduling. 53/// 54void ScheduleDAGSDNodes::Run(SelectionDAG *dag, MachineBasicBlock *bb) { 55 BB = bb; 56 DAG = dag; 57 58 // Clear the scheduler's SUnit DAG. 59 ScheduleDAG::clearDAG(); 60 Sequence.clear(); 61 62 // Invoke the target's selection of scheduler. 63 Schedule(); 64} 65 66/// NewSUnit - Creates a new SUnit and return a ptr to it. 67/// 68SUnit *ScheduleDAGSDNodes::newSUnit(SDNode *N) { 69#ifndef NDEBUG 70 const SUnit *Addr = 0; 71 if (!SUnits.empty()) 72 Addr = &SUnits[0]; 73#endif 74 SUnits.push_back(SUnit(N, (unsigned)SUnits.size())); 75 assert((Addr == 0 || Addr == &SUnits[0]) && 76 "SUnits std::vector reallocated on the fly!"); 77 SUnits.back().OrigNode = &SUnits.back(); 78 SUnit *SU = &SUnits.back(); 79 const TargetLowering &TLI = DAG->getTargetLoweringInfo(); 80 if (!N || 81 (N->isMachineOpcode() && 82 N->getMachineOpcode() == TargetOpcode::IMPLICIT_DEF)) 83 SU->SchedulingPref = Sched::None; 84 else 85 SU->SchedulingPref = TLI.getSchedulingPreference(N); 86 return SU; 87} 88 89SUnit *ScheduleDAGSDNodes::Clone(SUnit *Old) { 90 SUnit *SU = newSUnit(Old->getNode()); 91 SU->OrigNode = Old->OrigNode; 92 SU->Latency = Old->Latency; 93 SU->isVRegCycle = Old->isVRegCycle; 94 SU->isCall = Old->isCall; 95 SU->isCallOp = Old->isCallOp; 96 SU->isTwoAddress = Old->isTwoAddress; 97 SU->isCommutable = Old->isCommutable; 98 SU->hasPhysRegDefs = Old->hasPhysRegDefs; 99 SU->hasPhysRegClobbers = Old->hasPhysRegClobbers; 100 SU->isScheduleHigh = Old->isScheduleHigh; 101 SU->isScheduleLow = Old->isScheduleLow; 102 SU->SchedulingPref = Old->SchedulingPref; 103 Old->isCloned = true; 104 return SU; 105} 106 107/// CheckForPhysRegDependency - Check if the dependency between def and use of 108/// a specified operand is a physical register dependency. If so, returns the 109/// register and the cost of copying the register. 110static void CheckForPhysRegDependency(SDNode *Def, SDNode *User, unsigned Op, 111 const TargetRegisterInfo *TRI, 112 const TargetInstrInfo *TII, 113 unsigned &PhysReg, int &Cost) { 114 if (Op != 2 || User->getOpcode() != ISD::CopyToReg) 115 return; 116 117 unsigned Reg = cast<RegisterSDNode>(User->getOperand(1))->getReg(); 118 if (TargetRegisterInfo::isVirtualRegister(Reg)) 119 return; 120 121 unsigned ResNo = User->getOperand(2).getResNo(); 122 if (Def->isMachineOpcode()) { 123 const MCInstrDesc &II = TII->get(Def->getMachineOpcode()); 124 if (ResNo >= II.getNumDefs() && 125 II.ImplicitDefs[ResNo - II.getNumDefs()] == Reg) { 126 PhysReg = Reg; 127 const TargetRegisterClass *RC = 128 TRI->getMinimalPhysRegClass(Reg, Def->getValueType(ResNo)); 129 Cost = RC->getCopyCost(); 130 } 131 } 132} 133 134// Helper for AddGlue to clone node operands. 135static void CloneNodeWithValues(SDNode *N, SelectionDAG *DAG, 136 SmallVectorImpl<EVT> &VTs, 137 SDValue ExtraOper = SDValue()) { 138 SmallVector<SDValue, 4> Ops; 139 for (unsigned I = 0, E = N->getNumOperands(); I != E; ++I) 140 Ops.push_back(N->getOperand(I)); 141 142 if (ExtraOper.getNode()) 143 Ops.push_back(ExtraOper); 144 145 SDVTList VTList = DAG->getVTList(&VTs[0], VTs.size()); 146 MachineSDNode::mmo_iterator Begin = 0, End = 0; 147 MachineSDNode *MN = dyn_cast<MachineSDNode>(N); 148 149 // Store memory references. 150 if (MN) { 151 Begin = MN->memoperands_begin(); 152 End = MN->memoperands_end(); 153 } 154 155 DAG->MorphNodeTo(N, N->getOpcode(), VTList, &Ops[0], Ops.size()); 156 157 // Reset the memory references 158 if (MN) 159 MN->setMemRefs(Begin, End); 160} 161 162static bool AddGlue(SDNode *N, SDValue Glue, bool AddGlue, SelectionDAG *DAG) { 163 SmallVector<EVT, 4> VTs; 164 SDNode *GlueDestNode = Glue.getNode(); 165 166 // Don't add glue from a node to itself. 167 if (GlueDestNode == N) return false; 168 169 // Don't add a glue operand to something that already uses glue. 170 if (GlueDestNode && 171 N->getOperand(N->getNumOperands()-1).getValueType() == MVT::Glue) { 172 return false; 173 } 174 // Don't add glue to something that already has a glue value. 175 if (N->getValueType(N->getNumValues() - 1) == MVT::Glue) return false; 176 177 for (unsigned I = 0, E = N->getNumValues(); I != E; ++I) 178 VTs.push_back(N->getValueType(I)); 179 180 if (AddGlue) 181 VTs.push_back(MVT::Glue); 182 183 CloneNodeWithValues(N, DAG, VTs, Glue); 184 185 return true; 186} 187 188// Cleanup after unsuccessful AddGlue. Use the standard method of morphing the 189// node even though simply shrinking the value list is sufficient. 190static void RemoveUnusedGlue(SDNode *N, SelectionDAG *DAG) { 191 assert((N->getValueType(N->getNumValues() - 1) == MVT::Glue && 192 !N->hasAnyUseOfValue(N->getNumValues() - 1)) && 193 "expected an unused glue value"); 194 195 SmallVector<EVT, 4> VTs; 196 for (unsigned I = 0, E = N->getNumValues()-1; I != E; ++I) 197 VTs.push_back(N->getValueType(I)); 198 199 CloneNodeWithValues(N, DAG, VTs); 200} 201 202/// ClusterNeighboringLoads - Force nearby loads together by "gluing" them. 203/// This function finds loads of the same base and different offsets. If the 204/// offsets are not far apart (target specific), it add MVT::Glue inputs and 205/// outputs to ensure they are scheduled together and in order. This 206/// optimization may benefit some targets by improving cache locality. 207void ScheduleDAGSDNodes::ClusterNeighboringLoads(SDNode *Node) { 208 SDNode *Chain = 0; 209 unsigned NumOps = Node->getNumOperands(); 210 if (Node->getOperand(NumOps-1).getValueType() == MVT::Other) 211 Chain = Node->getOperand(NumOps-1).getNode(); 212 if (!Chain) 213 return; 214 215 // Look for other loads of the same chain. Find loads that are loading from 216 // the same base pointer and different offsets. 217 SmallPtrSet<SDNode*, 16> Visited; 218 SmallVector<int64_t, 4> Offsets; 219 DenseMap<long long, SDNode*> O2SMap; // Map from offset to SDNode. 220 bool Cluster = false; 221 SDNode *Base = Node;
|
240 } 241 242 if (!Cluster) 243 return; 244 245 // Sort them in increasing order. 246 std::sort(Offsets.begin(), Offsets.end()); 247 248 // Check if the loads are close enough. 249 SmallVector<SDNode*, 4> Loads; 250 unsigned NumLoads = 0; 251 int64_t BaseOff = Offsets[0]; 252 SDNode *BaseLoad = O2SMap[BaseOff]; 253 Loads.push_back(BaseLoad); 254 for (unsigned i = 1, e = Offsets.size(); i != e; ++i) { 255 int64_t Offset = Offsets[i]; 256 SDNode *Load = O2SMap[Offset]; 257 if (!TII->shouldScheduleLoadsNear(BaseLoad, Load, BaseOff, Offset,NumLoads)) 258 break; // Stop right here. Ignore loads that are further away. 259 Loads.push_back(Load); 260 ++NumLoads; 261 } 262 263 if (NumLoads == 0) 264 return; 265 266 // Cluster loads by adding MVT::Glue outputs and inputs. This also 267 // ensure they are scheduled in order of increasing addresses. 268 SDNode *Lead = Loads[0]; 269 SDValue InGlue = SDValue(0, 0); 270 if (AddGlue(Lead, InGlue, true, DAG)) 271 InGlue = SDValue(Lead, Lead->getNumValues() - 1); 272 for (unsigned I = 1, E = Loads.size(); I != E; ++I) { 273 bool OutGlue = I < E - 1; 274 SDNode *Load = Loads[I]; 275 276 // If AddGlue fails, we could leave an unsused glue value. This should not 277 // cause any 278 if (AddGlue(Load, InGlue, OutGlue, DAG)) { 279 if (OutGlue) 280 InGlue = SDValue(Load, Load->getNumValues() - 1); 281 282 ++LoadsClustered; 283 } 284 else if (!OutGlue && InGlue.getNode()) 285 RemoveUnusedGlue(InGlue.getNode(), DAG); 286 } 287} 288 289/// ClusterNodes - Cluster certain nodes which should be scheduled together. 290/// 291void ScheduleDAGSDNodes::ClusterNodes() { 292 for (SelectionDAG::allnodes_iterator NI = DAG->allnodes_begin(), 293 E = DAG->allnodes_end(); NI != E; ++NI) { 294 SDNode *Node = &*NI; 295 if (!Node || !Node->isMachineOpcode()) 296 continue; 297 298 unsigned Opc = Node->getMachineOpcode(); 299 const MCInstrDesc &MCID = TII->get(Opc); 300 if (MCID.mayLoad()) 301 // Cluster loads from "near" addresses into combined SUnits. 302 ClusterNeighboringLoads(Node); 303 } 304} 305 306void ScheduleDAGSDNodes::BuildSchedUnits() { 307 // During scheduling, the NodeId field of SDNode is used to map SDNodes 308 // to their associated SUnits by holding SUnits table indices. A value 309 // of -1 means the SDNode does not yet have an associated SUnit. 310 unsigned NumNodes = 0; 311 for (SelectionDAG::allnodes_iterator NI = DAG->allnodes_begin(), 312 E = DAG->allnodes_end(); NI != E; ++NI) { 313 NI->setNodeId(-1); 314 ++NumNodes; 315 } 316 317 // Reserve entries in the vector for each of the SUnits we are creating. This 318 // ensure that reallocation of the vector won't happen, so SUnit*'s won't get 319 // invalidated. 320 // FIXME: Multiply by 2 because we may clone nodes during scheduling. 321 // This is a temporary workaround. 322 SUnits.reserve(NumNodes * 2); 323 324 // Add all nodes in depth first order. 325 SmallVector<SDNode*, 64> Worklist; 326 SmallPtrSet<SDNode*, 64> Visited; 327 Worklist.push_back(DAG->getRoot().getNode()); 328 Visited.insert(DAG->getRoot().getNode()); 329 330 SmallVector<SUnit*, 8> CallSUnits; 331 while (!Worklist.empty()) { 332 SDNode *NI = Worklist.pop_back_val(); 333 334 // Add all operands to the worklist unless they've already been added. 335 for (unsigned i = 0, e = NI->getNumOperands(); i != e; ++i) 336 if (Visited.insert(NI->getOperand(i).getNode())) 337 Worklist.push_back(NI->getOperand(i).getNode()); 338 339 if (isPassiveNode(NI)) // Leaf node, e.g. a TargetImmediate. 340 continue; 341 342 // If this node has already been processed, stop now. 343 if (NI->getNodeId() != -1) continue; 344 345 SUnit *NodeSUnit = newSUnit(NI); 346 347 // See if anything is glued to this node, if so, add them to glued 348 // nodes. Nodes can have at most one glue input and one glue output. Glue 349 // is required to be the last operand and result of a node. 350 351 // Scan up to find glued preds. 352 SDNode *N = NI; 353 while (N->getNumOperands() && 354 N->getOperand(N->getNumOperands()-1).getValueType() == MVT::Glue) { 355 N = N->getOperand(N->getNumOperands()-1).getNode(); 356 assert(N->getNodeId() == -1 && "Node already inserted!"); 357 N->setNodeId(NodeSUnit->NodeNum); 358 if (N->isMachineOpcode() && TII->get(N->getMachineOpcode()).isCall()) 359 NodeSUnit->isCall = true; 360 } 361 362 // Scan down to find any glued succs. 363 N = NI; 364 while (N->getValueType(N->getNumValues()-1) == MVT::Glue) { 365 SDValue GlueVal(N, N->getNumValues()-1); 366 367 // There are either zero or one users of the Glue result. 368 bool HasGlueUse = false; 369 for (SDNode::use_iterator UI = N->use_begin(), E = N->use_end(); 370 UI != E; ++UI) 371 if (GlueVal.isOperandOf(*UI)) { 372 HasGlueUse = true; 373 assert(N->getNodeId() == -1 && "Node already inserted!"); 374 N->setNodeId(NodeSUnit->NodeNum); 375 N = *UI; 376 if (N->isMachineOpcode() && TII->get(N->getMachineOpcode()).isCall()) 377 NodeSUnit->isCall = true; 378 break; 379 } 380 if (!HasGlueUse) break; 381 } 382 383 if (NodeSUnit->isCall) 384 CallSUnits.push_back(NodeSUnit); 385 386 // Schedule zero-latency TokenFactor below any nodes that may increase the 387 // schedule height. Otherwise, ancestors of the TokenFactor may appear to 388 // have false stalls. 389 if (NI->getOpcode() == ISD::TokenFactor) 390 NodeSUnit->isScheduleLow = true; 391 392 // If there are glue operands involved, N is now the bottom-most node 393 // of the sequence of nodes that are glued together. 394 // Update the SUnit. 395 NodeSUnit->setNode(N); 396 assert(N->getNodeId() == -1 && "Node already inserted!"); 397 N->setNodeId(NodeSUnit->NodeNum); 398 399 // Compute NumRegDefsLeft. This must be done before AddSchedEdges. 400 InitNumRegDefsLeft(NodeSUnit); 401 402 // Assign the Latency field of NodeSUnit using target-provided information. 403 computeLatency(NodeSUnit); 404 } 405 406 // Find all call operands. 407 while (!CallSUnits.empty()) { 408 SUnit *SU = CallSUnits.pop_back_val(); 409 for (const SDNode *SUNode = SU->getNode(); SUNode; 410 SUNode = SUNode->getGluedNode()) { 411 if (SUNode->getOpcode() != ISD::CopyToReg) 412 continue; 413 SDNode *SrcN = SUNode->getOperand(2).getNode(); 414 if (isPassiveNode(SrcN)) continue; // Not scheduled. 415 SUnit *SrcSU = &SUnits[SrcN->getNodeId()]; 416 SrcSU->isCallOp = true; 417 } 418 } 419} 420 421void ScheduleDAGSDNodes::AddSchedEdges() { 422 const TargetSubtargetInfo &ST = TM.getSubtarget<TargetSubtargetInfo>(); 423 424 // Check to see if the scheduler cares about latencies. 425 bool UnitLatencies = forceUnitLatencies(); 426 427 // Pass 2: add the preds, succs, etc. 428 for (unsigned su = 0, e = SUnits.size(); su != e; ++su) { 429 SUnit *SU = &SUnits[su]; 430 SDNode *MainNode = SU->getNode(); 431 432 if (MainNode->isMachineOpcode()) { 433 unsigned Opc = MainNode->getMachineOpcode(); 434 const MCInstrDesc &MCID = TII->get(Opc); 435 for (unsigned i = 0; i != MCID.getNumOperands(); ++i) { 436 if (MCID.getOperandConstraint(i, MCOI::TIED_TO) != -1) { 437 SU->isTwoAddress = true; 438 break; 439 } 440 } 441 if (MCID.isCommutable()) 442 SU->isCommutable = true; 443 } 444 445 // Find all predecessors and successors of the group. 446 for (SDNode *N = SU->getNode(); N; N = N->getGluedNode()) { 447 if (N->isMachineOpcode() && 448 TII->get(N->getMachineOpcode()).getImplicitDefs()) { 449 SU->hasPhysRegClobbers = true; 450 unsigned NumUsed = InstrEmitter::CountResults(N); 451 while (NumUsed != 0 && !N->hasAnyUseOfValue(NumUsed - 1)) 452 --NumUsed; // Skip over unused values at the end. 453 if (NumUsed > TII->get(N->getMachineOpcode()).getNumDefs()) 454 SU->hasPhysRegDefs = true; 455 } 456 457 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) { 458 SDNode *OpN = N->getOperand(i).getNode(); 459 if (isPassiveNode(OpN)) continue; // Not scheduled. 460 SUnit *OpSU = &SUnits[OpN->getNodeId()]; 461 assert(OpSU && "Node has no SUnit!"); 462 if (OpSU == SU) continue; // In the same group. 463 464 EVT OpVT = N->getOperand(i).getValueType(); 465 assert(OpVT != MVT::Glue && "Glued nodes should be in same sunit!"); 466 bool isChain = OpVT == MVT::Other; 467 468 unsigned PhysReg = 0; 469 int Cost = 1; 470 // Determine if this is a physical register dependency. 471 CheckForPhysRegDependency(OpN, N, i, TRI, TII, PhysReg, Cost); 472 assert((PhysReg == 0 || !isChain) && 473 "Chain dependence via physreg data?"); 474 // FIXME: See ScheduleDAGSDNodes::EmitCopyFromReg. For now, scheduler 475 // emits a copy from the physical register to a virtual register unless 476 // it requires a cross class copy (cost < 0). That means we are only 477 // treating "expensive to copy" register dependency as physical register 478 // dependency. This may change in the future though. 479 if (Cost >= 0 && !StressSched) 480 PhysReg = 0; 481 482 // If this is a ctrl dep, latency is 1. 483 unsigned OpLatency = isChain ? 1 : OpSU->Latency; 484 // Special-case TokenFactor chains as zero-latency. 485 if(isChain && OpN->getOpcode() == ISD::TokenFactor) 486 OpLatency = 0; 487 488 SDep Dep = isChain ? SDep(OpSU, SDep::Barrier) 489 : SDep(OpSU, SDep::Data, PhysReg); 490 Dep.setLatency(OpLatency); 491 if (!isChain && !UnitLatencies) { 492 computeOperandLatency(OpN, N, i, Dep); 493 ST.adjustSchedDependency(OpSU, SU, Dep); 494 } 495 496 if (!SU->addPred(Dep) && !Dep.isCtrl() && OpSU->NumRegDefsLeft > 1) { 497 // Multiple register uses are combined in the same SUnit. For example, 498 // we could have a set of glued nodes with all their defs consumed by 499 // another set of glued nodes. Register pressure tracking sees this as 500 // a single use, so to keep pressure balanced we reduce the defs. 501 // 502 // We can't tell (without more book-keeping) if this results from 503 // glued nodes or duplicate operands. As long as we don't reduce 504 // NumRegDefsLeft to zero, we handle the common cases well. 505 --OpSU->NumRegDefsLeft; 506 } 507 } 508 } 509 } 510} 511 512/// BuildSchedGraph - Build the SUnit graph from the selection dag that we 513/// are input. This SUnit graph is similar to the SelectionDAG, but 514/// excludes nodes that aren't interesting to scheduling, and represents 515/// glued together nodes with a single SUnit. 516void ScheduleDAGSDNodes::BuildSchedGraph(AliasAnalysis *AA) { 517 // Cluster certain nodes which should be scheduled together. 518 ClusterNodes(); 519 // Populate the SUnits array. 520 BuildSchedUnits(); 521 // Compute all the scheduling dependencies between nodes. 522 AddSchedEdges(); 523} 524 525// Initialize NumNodeDefs for the current Node's opcode. 526void ScheduleDAGSDNodes::RegDefIter::InitNodeNumDefs() { 527 // Check for phys reg copy. 528 if (!Node) 529 return; 530 531 if (!Node->isMachineOpcode()) { 532 if (Node->getOpcode() == ISD::CopyFromReg) 533 NodeNumDefs = 1; 534 else 535 NodeNumDefs = 0; 536 return; 537 } 538 unsigned POpc = Node->getMachineOpcode(); 539 if (POpc == TargetOpcode::IMPLICIT_DEF) { 540 // No register need be allocated for this. 541 NodeNumDefs = 0; 542 return; 543 } 544 unsigned NRegDefs = SchedDAG->TII->get(Node->getMachineOpcode()).getNumDefs(); 545 // Some instructions define regs that are not represented in the selection DAG 546 // (e.g. unused flags). See tMOVi8. Make sure we don't access past NumValues. 547 NodeNumDefs = std::min(Node->getNumValues(), NRegDefs); 548 DefIdx = 0; 549} 550 551// Construct a RegDefIter for this SUnit and find the first valid value. 552ScheduleDAGSDNodes::RegDefIter::RegDefIter(const SUnit *SU, 553 const ScheduleDAGSDNodes *SD) 554 : SchedDAG(SD), Node(SU->getNode()), DefIdx(0), NodeNumDefs(0) { 555 InitNodeNumDefs(); 556 Advance(); 557} 558 559// Advance to the next valid value defined by the SUnit. 560void ScheduleDAGSDNodes::RegDefIter::Advance() { 561 for (;Node;) { // Visit all glued nodes. 562 for (;DefIdx < NodeNumDefs; ++DefIdx) { 563 if (!Node->hasAnyUseOfValue(DefIdx)) 564 continue; 565 ValueType = Node->getSimpleValueType(DefIdx); 566 ++DefIdx; 567 return; // Found a normal regdef. 568 } 569 Node = Node->getGluedNode(); 570 if (Node == NULL) { 571 return; // No values left to visit. 572 } 573 InitNodeNumDefs(); 574 } 575} 576 577void ScheduleDAGSDNodes::InitNumRegDefsLeft(SUnit *SU) { 578 assert(SU->NumRegDefsLeft == 0 && "expect a new node"); 579 for (RegDefIter I(SU, this); I.IsValid(); I.Advance()) { 580 assert(SU->NumRegDefsLeft < USHRT_MAX && "overflow is ok but unexpected"); 581 ++SU->NumRegDefsLeft; 582 } 583} 584 585void ScheduleDAGSDNodes::computeLatency(SUnit *SU) { 586 SDNode *N = SU->getNode(); 587 588 // TokenFactor operands are considered zero latency, and some schedulers 589 // (e.g. Top-Down list) may rely on the fact that operand latency is nonzero 590 // whenever node latency is nonzero. 591 if (N && N->getOpcode() == ISD::TokenFactor) { 592 SU->Latency = 0; 593 return; 594 } 595 596 // Check to see if the scheduler cares about latencies. 597 if (forceUnitLatencies()) { 598 SU->Latency = 1; 599 return; 600 } 601 602 if (!InstrItins || InstrItins->isEmpty()) { 603 if (N && N->isMachineOpcode() && 604 TII->isHighLatencyDef(N->getMachineOpcode())) 605 SU->Latency = HighLatencyCycles; 606 else 607 SU->Latency = 1; 608 return; 609 } 610 611 // Compute the latency for the node. We use the sum of the latencies for 612 // all nodes glued together into this SUnit. 613 SU->Latency = 0; 614 for (SDNode *N = SU->getNode(); N; N = N->getGluedNode()) 615 if (N->isMachineOpcode()) 616 SU->Latency += TII->getInstrLatency(InstrItins, N); 617} 618 619void ScheduleDAGSDNodes::computeOperandLatency(SDNode *Def, SDNode *Use, 620 unsigned OpIdx, SDep& dep) const{ 621 // Check to see if the scheduler cares about latencies. 622 if (forceUnitLatencies()) 623 return; 624 625 if (dep.getKind() != SDep::Data) 626 return; 627 628 unsigned DefIdx = Use->getOperand(OpIdx).getResNo(); 629 if (Use->isMachineOpcode()) 630 // Adjust the use operand index by num of defs. 631 OpIdx += TII->get(Use->getMachineOpcode()).getNumDefs(); 632 int Latency = TII->getOperandLatency(InstrItins, Def, DefIdx, Use, OpIdx); 633 if (Latency > 1 && Use->getOpcode() == ISD::CopyToReg && 634 !BB->succ_empty()) { 635 unsigned Reg = cast<RegisterSDNode>(Use->getOperand(1))->getReg(); 636 if (TargetRegisterInfo::isVirtualRegister(Reg)) 637 // This copy is a liveout value. It is likely coalesced, so reduce the 638 // latency so not to penalize the def. 639 // FIXME: need target specific adjustment here? 640 Latency = (Latency > 1) ? Latency - 1 : 1; 641 } 642 if (Latency >= 0) 643 dep.setLatency(Latency); 644} 645 646void ScheduleDAGSDNodes::dumpNode(const SUnit *SU) const { 647#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 648 if (!SU->getNode()) { 649 dbgs() << "PHYS REG COPY\n"; 650 return; 651 } 652 653 SU->getNode()->dump(DAG); 654 dbgs() << "\n"; 655 SmallVector<SDNode *, 4> GluedNodes; 656 for (SDNode *N = SU->getNode()->getGluedNode(); N; N = N->getGluedNode()) 657 GluedNodes.push_back(N); 658 while (!GluedNodes.empty()) { 659 dbgs() << " "; 660 GluedNodes.back()->dump(DAG); 661 dbgs() << "\n"; 662 GluedNodes.pop_back(); 663 } 664#endif 665} 666 667#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 668void ScheduleDAGSDNodes::dumpSchedule() const { 669 for (unsigned i = 0, e = Sequence.size(); i != e; i++) { 670 if (SUnit *SU = Sequence[i]) 671 SU->dump(this); 672 else 673 dbgs() << "**** NOOP ****\n"; 674 } 675} 676#endif 677 678#ifndef NDEBUG 679/// VerifyScheduledSequence - Verify that all SUnits were scheduled and that 680/// their state is consistent with the nodes listed in Sequence. 681/// 682void ScheduleDAGSDNodes::VerifyScheduledSequence(bool isBottomUp) { 683 unsigned ScheduledNodes = ScheduleDAG::VerifyScheduledDAG(isBottomUp); 684 unsigned Noops = 0; 685 for (unsigned i = 0, e = Sequence.size(); i != e; ++i) 686 if (!Sequence[i]) 687 ++Noops; 688 assert(Sequence.size() - Noops == ScheduledNodes && 689 "The number of nodes scheduled doesn't match the expected number!"); 690} 691#endif // NDEBUG 692 693/// ProcessSDDbgValues - Process SDDbgValues associated with this node. 694static void 695ProcessSDDbgValues(SDNode *N, SelectionDAG *DAG, InstrEmitter &Emitter, 696 SmallVectorImpl<std::pair<unsigned, MachineInstr*> > &Orders, 697 DenseMap<SDValue, unsigned> &VRBaseMap, unsigned Order) { 698 if (!N->getHasDebugValue()) 699 return; 700 701 // Opportunistically insert immediate dbg_value uses, i.e. those with source 702 // order number right after the N. 703 MachineBasicBlock *BB = Emitter.getBlock(); 704 MachineBasicBlock::iterator InsertPos = Emitter.getInsertPos(); 705 ArrayRef<SDDbgValue*> DVs = DAG->GetDbgValues(N); 706 for (unsigned i = 0, e = DVs.size(); i != e; ++i) { 707 if (DVs[i]->isInvalidated()) 708 continue; 709 unsigned DVOrder = DVs[i]->getOrder(); 710 if (!Order || DVOrder == ++Order) { 711 MachineInstr *DbgMI = Emitter.EmitDbgValue(DVs[i], VRBaseMap); 712 if (DbgMI) { 713 Orders.push_back(std::make_pair(DVOrder, DbgMI)); 714 BB->insert(InsertPos, DbgMI); 715 } 716 DVs[i]->setIsInvalidated(); 717 } 718 } 719} 720 721// ProcessSourceNode - Process nodes with source order numbers. These are added 722// to a vector which EmitSchedule uses to determine how to insert dbg_value 723// instructions in the right order. 724static void 725ProcessSourceNode(SDNode *N, SelectionDAG *DAG, InstrEmitter &Emitter, 726 DenseMap<SDValue, unsigned> &VRBaseMap, 727 SmallVectorImpl<std::pair<unsigned, MachineInstr*> > &Orders, 728 SmallSet<unsigned, 8> &Seen) { 729 unsigned Order = N->getIROrder(); 730 if (!Order || !Seen.insert(Order)) { 731 // Process any valid SDDbgValues even if node does not have any order 732 // assigned. 733 ProcessSDDbgValues(N, DAG, Emitter, Orders, VRBaseMap, 0); 734 return; 735 } 736 737 MachineBasicBlock *BB = Emitter.getBlock(); 738 if (Emitter.getInsertPos() == BB->begin() || BB->back().isPHI() || 739 // Fast-isel may have inserted some instructions, in which case the 740 // BB->back().isPHI() test will not fire when we want it to. 741 prior(Emitter.getInsertPos())->isPHI()) { 742 // Did not insert any instruction. 743 Orders.push_back(std::make_pair(Order, (MachineInstr*)0)); 744 return; 745 } 746 747 Orders.push_back(std::make_pair(Order, prior(Emitter.getInsertPos()))); 748 ProcessSDDbgValues(N, DAG, Emitter, Orders, VRBaseMap, Order); 749} 750 751void ScheduleDAGSDNodes:: 752EmitPhysRegCopy(SUnit *SU, DenseMap<SUnit*, unsigned> &VRBaseMap, 753 MachineBasicBlock::iterator InsertPos) { 754 for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 755 I != E; ++I) { 756 if (I->isCtrl()) continue; // ignore chain preds 757 if (I->getSUnit()->CopyDstRC) { 758 // Copy to physical register. 759 DenseMap<SUnit*, unsigned>::iterator VRI = VRBaseMap.find(I->getSUnit()); 760 assert(VRI != VRBaseMap.end() && "Node emitted out of order - late"); 761 // Find the destination physical register. 762 unsigned Reg = 0; 763 for (SUnit::const_succ_iterator II = SU->Succs.begin(), 764 EE = SU->Succs.end(); II != EE; ++II) { 765 if (II->isCtrl()) continue; // ignore chain preds 766 if (II->getReg()) { 767 Reg = II->getReg(); 768 break; 769 } 770 } 771 BuildMI(*BB, InsertPos, DebugLoc(), TII->get(TargetOpcode::COPY), Reg) 772 .addReg(VRI->second); 773 } else { 774 // Copy from physical register. 775 assert(I->getReg() && "Unknown physical register!"); 776 unsigned VRBase = MRI.createVirtualRegister(SU->CopyDstRC); 777 bool isNew = VRBaseMap.insert(std::make_pair(SU, VRBase)).second; 778 (void)isNew; // Silence compiler warning. 779 assert(isNew && "Node emitted out of order - early"); 780 BuildMI(*BB, InsertPos, DebugLoc(), TII->get(TargetOpcode::COPY), VRBase) 781 .addReg(I->getReg()); 782 } 783 break; 784 } 785} 786 787/// EmitSchedule - Emit the machine code in scheduled order. Return the new 788/// InsertPos and MachineBasicBlock that contains this insertion 789/// point. ScheduleDAGSDNodes holds a BB pointer for convenience, but this does 790/// not necessarily refer to returned BB. The emitter may split blocks. 791MachineBasicBlock *ScheduleDAGSDNodes:: 792EmitSchedule(MachineBasicBlock::iterator &InsertPos) { 793 InstrEmitter Emitter(BB, InsertPos); 794 DenseMap<SDValue, unsigned> VRBaseMap; 795 DenseMap<SUnit*, unsigned> CopyVRBaseMap; 796 SmallVector<std::pair<unsigned, MachineInstr*>, 32> Orders; 797 SmallSet<unsigned, 8> Seen; 798 bool HasDbg = DAG->hasDebugValues(); 799 800 // If this is the first BB, emit byval parameter dbg_value's. 801 if (HasDbg && BB->getParent()->begin() == MachineFunction::iterator(BB)) { 802 SDDbgInfo::DbgIterator PDI = DAG->ByvalParmDbgBegin(); 803 SDDbgInfo::DbgIterator PDE = DAG->ByvalParmDbgEnd(); 804 for (; PDI != PDE; ++PDI) { 805 MachineInstr *DbgMI= Emitter.EmitDbgValue(*PDI, VRBaseMap); 806 if (DbgMI) 807 BB->insert(InsertPos, DbgMI); 808 } 809 } 810 811 for (unsigned i = 0, e = Sequence.size(); i != e; i++) { 812 SUnit *SU = Sequence[i]; 813 if (!SU) { 814 // Null SUnit* is a noop. 815 TII->insertNoop(*Emitter.getBlock(), InsertPos); 816 continue; 817 } 818 819 // For pre-regalloc scheduling, create instructions corresponding to the 820 // SDNode and any glued SDNodes and append them to the block. 821 if (!SU->getNode()) { 822 // Emit a copy. 823 EmitPhysRegCopy(SU, CopyVRBaseMap, InsertPos); 824 continue; 825 } 826 827 SmallVector<SDNode *, 4> GluedNodes; 828 for (SDNode *N = SU->getNode()->getGluedNode(); N; N = N->getGluedNode()) 829 GluedNodes.push_back(N); 830 while (!GluedNodes.empty()) { 831 SDNode *N = GluedNodes.back(); 832 Emitter.EmitNode(GluedNodes.back(), SU->OrigNode != SU, SU->isCloned, 833 VRBaseMap); 834 // Remember the source order of the inserted instruction. 835 if (HasDbg) 836 ProcessSourceNode(N, DAG, Emitter, VRBaseMap, Orders, Seen); 837 GluedNodes.pop_back(); 838 } 839 Emitter.EmitNode(SU->getNode(), SU->OrigNode != SU, SU->isCloned, 840 VRBaseMap); 841 // Remember the source order of the inserted instruction. 842 if (HasDbg) 843 ProcessSourceNode(SU->getNode(), DAG, Emitter, VRBaseMap, Orders, 844 Seen); 845 } 846 847 // Insert all the dbg_values which have not already been inserted in source 848 // order sequence. 849 if (HasDbg) { 850 MachineBasicBlock::iterator BBBegin = BB->getFirstNonPHI(); 851 852 // Sort the source order instructions and use the order to insert debug 853 // values. 854 std::sort(Orders.begin(), Orders.end(), less_first()); 855 856 SDDbgInfo::DbgIterator DI = DAG->DbgBegin(); 857 SDDbgInfo::DbgIterator DE = DAG->DbgEnd(); 858 // Now emit the rest according to source order. 859 unsigned LastOrder = 0; 860 for (unsigned i = 0, e = Orders.size(); i != e && DI != DE; ++i) { 861 unsigned Order = Orders[i].first; 862 MachineInstr *MI = Orders[i].second; 863 // Insert all SDDbgValue's whose order(s) are before "Order". 864 if (!MI) 865 continue; 866 for (; DI != DE && 867 (*DI)->getOrder() >= LastOrder && (*DI)->getOrder() < Order; ++DI) { 868 if ((*DI)->isInvalidated()) 869 continue; 870 MachineInstr *DbgMI = Emitter.EmitDbgValue(*DI, VRBaseMap); 871 if (DbgMI) { 872 if (!LastOrder) 873 // Insert to start of the BB (after PHIs). 874 BB->insert(BBBegin, DbgMI); 875 else { 876 // Insert at the instruction, which may be in a different 877 // block, if the block was split by a custom inserter. 878 MachineBasicBlock::iterator Pos = MI; 879 MI->getParent()->insert(Pos, DbgMI); 880 } 881 } 882 } 883 LastOrder = Order; 884 } 885 // Add trailing DbgValue's before the terminator. FIXME: May want to add 886 // some of them before one or more conditional branches? 887 SmallVector<MachineInstr*, 8> DbgMIs; 888 while (DI != DE) { 889 if (!(*DI)->isInvalidated()) 890 if (MachineInstr *DbgMI = Emitter.EmitDbgValue(*DI, VRBaseMap)) 891 DbgMIs.push_back(DbgMI); 892 ++DI; 893 } 894 895 MachineBasicBlock *InsertBB = Emitter.getBlock(); 896 MachineBasicBlock::iterator Pos = InsertBB->getFirstTerminator(); 897 InsertBB->insert(Pos, DbgMIs.begin(), DbgMIs.end()); 898 } 899 900 InsertPos = Emitter.getInsertPos(); 901 return Emitter.getBlock(); 902} 903 904/// Return the basic block label. 905std::string ScheduleDAGSDNodes::getDAGName() const { 906 return "sunit-dag." + BB->getFullName(); 907}
| 245 } 246 247 if (!Cluster) 248 return; 249 250 // Sort them in increasing order. 251 std::sort(Offsets.begin(), Offsets.end()); 252 253 // Check if the loads are close enough. 254 SmallVector<SDNode*, 4> Loads; 255 unsigned NumLoads = 0; 256 int64_t BaseOff = Offsets[0]; 257 SDNode *BaseLoad = O2SMap[BaseOff]; 258 Loads.push_back(BaseLoad); 259 for (unsigned i = 1, e = Offsets.size(); i != e; ++i) { 260 int64_t Offset = Offsets[i]; 261 SDNode *Load = O2SMap[Offset]; 262 if (!TII->shouldScheduleLoadsNear(BaseLoad, Load, BaseOff, Offset,NumLoads)) 263 break; // Stop right here. Ignore loads that are further away. 264 Loads.push_back(Load); 265 ++NumLoads; 266 } 267 268 if (NumLoads == 0) 269 return; 270 271 // Cluster loads by adding MVT::Glue outputs and inputs. This also 272 // ensure they are scheduled in order of increasing addresses. 273 SDNode *Lead = Loads[0]; 274 SDValue InGlue = SDValue(0, 0); 275 if (AddGlue(Lead, InGlue, true, DAG)) 276 InGlue = SDValue(Lead, Lead->getNumValues() - 1); 277 for (unsigned I = 1, E = Loads.size(); I != E; ++I) { 278 bool OutGlue = I < E - 1; 279 SDNode *Load = Loads[I]; 280 281 // If AddGlue fails, we could leave an unsused glue value. This should not 282 // cause any 283 if (AddGlue(Load, InGlue, OutGlue, DAG)) { 284 if (OutGlue) 285 InGlue = SDValue(Load, Load->getNumValues() - 1); 286 287 ++LoadsClustered; 288 } 289 else if (!OutGlue && InGlue.getNode()) 290 RemoveUnusedGlue(InGlue.getNode(), DAG); 291 } 292} 293 294/// ClusterNodes - Cluster certain nodes which should be scheduled together. 295/// 296void ScheduleDAGSDNodes::ClusterNodes() { 297 for (SelectionDAG::allnodes_iterator NI = DAG->allnodes_begin(), 298 E = DAG->allnodes_end(); NI != E; ++NI) { 299 SDNode *Node = &*NI; 300 if (!Node || !Node->isMachineOpcode()) 301 continue; 302 303 unsigned Opc = Node->getMachineOpcode(); 304 const MCInstrDesc &MCID = TII->get(Opc); 305 if (MCID.mayLoad()) 306 // Cluster loads from "near" addresses into combined SUnits. 307 ClusterNeighboringLoads(Node); 308 } 309} 310 311void ScheduleDAGSDNodes::BuildSchedUnits() { 312 // During scheduling, the NodeId field of SDNode is used to map SDNodes 313 // to their associated SUnits by holding SUnits table indices. A value 314 // of -1 means the SDNode does not yet have an associated SUnit. 315 unsigned NumNodes = 0; 316 for (SelectionDAG::allnodes_iterator NI = DAG->allnodes_begin(), 317 E = DAG->allnodes_end(); NI != E; ++NI) { 318 NI->setNodeId(-1); 319 ++NumNodes; 320 } 321 322 // Reserve entries in the vector for each of the SUnits we are creating. This 323 // ensure that reallocation of the vector won't happen, so SUnit*'s won't get 324 // invalidated. 325 // FIXME: Multiply by 2 because we may clone nodes during scheduling. 326 // This is a temporary workaround. 327 SUnits.reserve(NumNodes * 2); 328 329 // Add all nodes in depth first order. 330 SmallVector<SDNode*, 64> Worklist; 331 SmallPtrSet<SDNode*, 64> Visited; 332 Worklist.push_back(DAG->getRoot().getNode()); 333 Visited.insert(DAG->getRoot().getNode()); 334 335 SmallVector<SUnit*, 8> CallSUnits; 336 while (!Worklist.empty()) { 337 SDNode *NI = Worklist.pop_back_val(); 338 339 // Add all operands to the worklist unless they've already been added. 340 for (unsigned i = 0, e = NI->getNumOperands(); i != e; ++i) 341 if (Visited.insert(NI->getOperand(i).getNode())) 342 Worklist.push_back(NI->getOperand(i).getNode()); 343 344 if (isPassiveNode(NI)) // Leaf node, e.g. a TargetImmediate. 345 continue; 346 347 // If this node has already been processed, stop now. 348 if (NI->getNodeId() != -1) continue; 349 350 SUnit *NodeSUnit = newSUnit(NI); 351 352 // See if anything is glued to this node, if so, add them to glued 353 // nodes. Nodes can have at most one glue input and one glue output. Glue 354 // is required to be the last operand and result of a node. 355 356 // Scan up to find glued preds. 357 SDNode *N = NI; 358 while (N->getNumOperands() && 359 N->getOperand(N->getNumOperands()-1).getValueType() == MVT::Glue) { 360 N = N->getOperand(N->getNumOperands()-1).getNode(); 361 assert(N->getNodeId() == -1 && "Node already inserted!"); 362 N->setNodeId(NodeSUnit->NodeNum); 363 if (N->isMachineOpcode() && TII->get(N->getMachineOpcode()).isCall()) 364 NodeSUnit->isCall = true; 365 } 366 367 // Scan down to find any glued succs. 368 N = NI; 369 while (N->getValueType(N->getNumValues()-1) == MVT::Glue) { 370 SDValue GlueVal(N, N->getNumValues()-1); 371 372 // There are either zero or one users of the Glue result. 373 bool HasGlueUse = false; 374 for (SDNode::use_iterator UI = N->use_begin(), E = N->use_end(); 375 UI != E; ++UI) 376 if (GlueVal.isOperandOf(*UI)) { 377 HasGlueUse = true; 378 assert(N->getNodeId() == -1 && "Node already inserted!"); 379 N->setNodeId(NodeSUnit->NodeNum); 380 N = *UI; 381 if (N->isMachineOpcode() && TII->get(N->getMachineOpcode()).isCall()) 382 NodeSUnit->isCall = true; 383 break; 384 } 385 if (!HasGlueUse) break; 386 } 387 388 if (NodeSUnit->isCall) 389 CallSUnits.push_back(NodeSUnit); 390 391 // Schedule zero-latency TokenFactor below any nodes that may increase the 392 // schedule height. Otherwise, ancestors of the TokenFactor may appear to 393 // have false stalls. 394 if (NI->getOpcode() == ISD::TokenFactor) 395 NodeSUnit->isScheduleLow = true; 396 397 // If there are glue operands involved, N is now the bottom-most node 398 // of the sequence of nodes that are glued together. 399 // Update the SUnit. 400 NodeSUnit->setNode(N); 401 assert(N->getNodeId() == -1 && "Node already inserted!"); 402 N->setNodeId(NodeSUnit->NodeNum); 403 404 // Compute NumRegDefsLeft. This must be done before AddSchedEdges. 405 InitNumRegDefsLeft(NodeSUnit); 406 407 // Assign the Latency field of NodeSUnit using target-provided information. 408 computeLatency(NodeSUnit); 409 } 410 411 // Find all call operands. 412 while (!CallSUnits.empty()) { 413 SUnit *SU = CallSUnits.pop_back_val(); 414 for (const SDNode *SUNode = SU->getNode(); SUNode; 415 SUNode = SUNode->getGluedNode()) { 416 if (SUNode->getOpcode() != ISD::CopyToReg) 417 continue; 418 SDNode *SrcN = SUNode->getOperand(2).getNode(); 419 if (isPassiveNode(SrcN)) continue; // Not scheduled. 420 SUnit *SrcSU = &SUnits[SrcN->getNodeId()]; 421 SrcSU->isCallOp = true; 422 } 423 } 424} 425 426void ScheduleDAGSDNodes::AddSchedEdges() { 427 const TargetSubtargetInfo &ST = TM.getSubtarget<TargetSubtargetInfo>(); 428 429 // Check to see if the scheduler cares about latencies. 430 bool UnitLatencies = forceUnitLatencies(); 431 432 // Pass 2: add the preds, succs, etc. 433 for (unsigned su = 0, e = SUnits.size(); su != e; ++su) { 434 SUnit *SU = &SUnits[su]; 435 SDNode *MainNode = SU->getNode(); 436 437 if (MainNode->isMachineOpcode()) { 438 unsigned Opc = MainNode->getMachineOpcode(); 439 const MCInstrDesc &MCID = TII->get(Opc); 440 for (unsigned i = 0; i != MCID.getNumOperands(); ++i) { 441 if (MCID.getOperandConstraint(i, MCOI::TIED_TO) != -1) { 442 SU->isTwoAddress = true; 443 break; 444 } 445 } 446 if (MCID.isCommutable()) 447 SU->isCommutable = true; 448 } 449 450 // Find all predecessors and successors of the group. 451 for (SDNode *N = SU->getNode(); N; N = N->getGluedNode()) { 452 if (N->isMachineOpcode() && 453 TII->get(N->getMachineOpcode()).getImplicitDefs()) { 454 SU->hasPhysRegClobbers = true; 455 unsigned NumUsed = InstrEmitter::CountResults(N); 456 while (NumUsed != 0 && !N->hasAnyUseOfValue(NumUsed - 1)) 457 --NumUsed; // Skip over unused values at the end. 458 if (NumUsed > TII->get(N->getMachineOpcode()).getNumDefs()) 459 SU->hasPhysRegDefs = true; 460 } 461 462 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) { 463 SDNode *OpN = N->getOperand(i).getNode(); 464 if (isPassiveNode(OpN)) continue; // Not scheduled. 465 SUnit *OpSU = &SUnits[OpN->getNodeId()]; 466 assert(OpSU && "Node has no SUnit!"); 467 if (OpSU == SU) continue; // In the same group. 468 469 EVT OpVT = N->getOperand(i).getValueType(); 470 assert(OpVT != MVT::Glue && "Glued nodes should be in same sunit!"); 471 bool isChain = OpVT == MVT::Other; 472 473 unsigned PhysReg = 0; 474 int Cost = 1; 475 // Determine if this is a physical register dependency. 476 CheckForPhysRegDependency(OpN, N, i, TRI, TII, PhysReg, Cost); 477 assert((PhysReg == 0 || !isChain) && 478 "Chain dependence via physreg data?"); 479 // FIXME: See ScheduleDAGSDNodes::EmitCopyFromReg. For now, scheduler 480 // emits a copy from the physical register to a virtual register unless 481 // it requires a cross class copy (cost < 0). That means we are only 482 // treating "expensive to copy" register dependency as physical register 483 // dependency. This may change in the future though. 484 if (Cost >= 0 && !StressSched) 485 PhysReg = 0; 486 487 // If this is a ctrl dep, latency is 1. 488 unsigned OpLatency = isChain ? 1 : OpSU->Latency; 489 // Special-case TokenFactor chains as zero-latency. 490 if(isChain && OpN->getOpcode() == ISD::TokenFactor) 491 OpLatency = 0; 492 493 SDep Dep = isChain ? SDep(OpSU, SDep::Barrier) 494 : SDep(OpSU, SDep::Data, PhysReg); 495 Dep.setLatency(OpLatency); 496 if (!isChain && !UnitLatencies) { 497 computeOperandLatency(OpN, N, i, Dep); 498 ST.adjustSchedDependency(OpSU, SU, Dep); 499 } 500 501 if (!SU->addPred(Dep) && !Dep.isCtrl() && OpSU->NumRegDefsLeft > 1) { 502 // Multiple register uses are combined in the same SUnit. For example, 503 // we could have a set of glued nodes with all their defs consumed by 504 // another set of glued nodes. Register pressure tracking sees this as 505 // a single use, so to keep pressure balanced we reduce the defs. 506 // 507 // We can't tell (without more book-keeping) if this results from 508 // glued nodes or duplicate operands. As long as we don't reduce 509 // NumRegDefsLeft to zero, we handle the common cases well. 510 --OpSU->NumRegDefsLeft; 511 } 512 } 513 } 514 } 515} 516 517/// BuildSchedGraph - Build the SUnit graph from the selection dag that we 518/// are input. This SUnit graph is similar to the SelectionDAG, but 519/// excludes nodes that aren't interesting to scheduling, and represents 520/// glued together nodes with a single SUnit. 521void ScheduleDAGSDNodes::BuildSchedGraph(AliasAnalysis *AA) { 522 // Cluster certain nodes which should be scheduled together. 523 ClusterNodes(); 524 // Populate the SUnits array. 525 BuildSchedUnits(); 526 // Compute all the scheduling dependencies between nodes. 527 AddSchedEdges(); 528} 529 530// Initialize NumNodeDefs for the current Node's opcode. 531void ScheduleDAGSDNodes::RegDefIter::InitNodeNumDefs() { 532 // Check for phys reg copy. 533 if (!Node) 534 return; 535 536 if (!Node->isMachineOpcode()) { 537 if (Node->getOpcode() == ISD::CopyFromReg) 538 NodeNumDefs = 1; 539 else 540 NodeNumDefs = 0; 541 return; 542 } 543 unsigned POpc = Node->getMachineOpcode(); 544 if (POpc == TargetOpcode::IMPLICIT_DEF) { 545 // No register need be allocated for this. 546 NodeNumDefs = 0; 547 return; 548 } 549 unsigned NRegDefs = SchedDAG->TII->get(Node->getMachineOpcode()).getNumDefs(); 550 // Some instructions define regs that are not represented in the selection DAG 551 // (e.g. unused flags). See tMOVi8. Make sure we don't access past NumValues. 552 NodeNumDefs = std::min(Node->getNumValues(), NRegDefs); 553 DefIdx = 0; 554} 555 556// Construct a RegDefIter for this SUnit and find the first valid value. 557ScheduleDAGSDNodes::RegDefIter::RegDefIter(const SUnit *SU, 558 const ScheduleDAGSDNodes *SD) 559 : SchedDAG(SD), Node(SU->getNode()), DefIdx(0), NodeNumDefs(0) { 560 InitNodeNumDefs(); 561 Advance(); 562} 563 564// Advance to the next valid value defined by the SUnit. 565void ScheduleDAGSDNodes::RegDefIter::Advance() { 566 for (;Node;) { // Visit all glued nodes. 567 for (;DefIdx < NodeNumDefs; ++DefIdx) { 568 if (!Node->hasAnyUseOfValue(DefIdx)) 569 continue; 570 ValueType = Node->getSimpleValueType(DefIdx); 571 ++DefIdx; 572 return; // Found a normal regdef. 573 } 574 Node = Node->getGluedNode(); 575 if (Node == NULL) { 576 return; // No values left to visit. 577 } 578 InitNodeNumDefs(); 579 } 580} 581 582void ScheduleDAGSDNodes::InitNumRegDefsLeft(SUnit *SU) { 583 assert(SU->NumRegDefsLeft == 0 && "expect a new node"); 584 for (RegDefIter I(SU, this); I.IsValid(); I.Advance()) { 585 assert(SU->NumRegDefsLeft < USHRT_MAX && "overflow is ok but unexpected"); 586 ++SU->NumRegDefsLeft; 587 } 588} 589 590void ScheduleDAGSDNodes::computeLatency(SUnit *SU) { 591 SDNode *N = SU->getNode(); 592 593 // TokenFactor operands are considered zero latency, and some schedulers 594 // (e.g. Top-Down list) may rely on the fact that operand latency is nonzero 595 // whenever node latency is nonzero. 596 if (N && N->getOpcode() == ISD::TokenFactor) { 597 SU->Latency = 0; 598 return; 599 } 600 601 // Check to see if the scheduler cares about latencies. 602 if (forceUnitLatencies()) { 603 SU->Latency = 1; 604 return; 605 } 606 607 if (!InstrItins || InstrItins->isEmpty()) { 608 if (N && N->isMachineOpcode() && 609 TII->isHighLatencyDef(N->getMachineOpcode())) 610 SU->Latency = HighLatencyCycles; 611 else 612 SU->Latency = 1; 613 return; 614 } 615 616 // Compute the latency for the node. We use the sum of the latencies for 617 // all nodes glued together into this SUnit. 618 SU->Latency = 0; 619 for (SDNode *N = SU->getNode(); N; N = N->getGluedNode()) 620 if (N->isMachineOpcode()) 621 SU->Latency += TII->getInstrLatency(InstrItins, N); 622} 623 624void ScheduleDAGSDNodes::computeOperandLatency(SDNode *Def, SDNode *Use, 625 unsigned OpIdx, SDep& dep) const{ 626 // Check to see if the scheduler cares about latencies. 627 if (forceUnitLatencies()) 628 return; 629 630 if (dep.getKind() != SDep::Data) 631 return; 632 633 unsigned DefIdx = Use->getOperand(OpIdx).getResNo(); 634 if (Use->isMachineOpcode()) 635 // Adjust the use operand index by num of defs. 636 OpIdx += TII->get(Use->getMachineOpcode()).getNumDefs(); 637 int Latency = TII->getOperandLatency(InstrItins, Def, DefIdx, Use, OpIdx); 638 if (Latency > 1 && Use->getOpcode() == ISD::CopyToReg && 639 !BB->succ_empty()) { 640 unsigned Reg = cast<RegisterSDNode>(Use->getOperand(1))->getReg(); 641 if (TargetRegisterInfo::isVirtualRegister(Reg)) 642 // This copy is a liveout value. It is likely coalesced, so reduce the 643 // latency so not to penalize the def. 644 // FIXME: need target specific adjustment here? 645 Latency = (Latency > 1) ? Latency - 1 : 1; 646 } 647 if (Latency >= 0) 648 dep.setLatency(Latency); 649} 650 651void ScheduleDAGSDNodes::dumpNode(const SUnit *SU) const { 652#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 653 if (!SU->getNode()) { 654 dbgs() << "PHYS REG COPY\n"; 655 return; 656 } 657 658 SU->getNode()->dump(DAG); 659 dbgs() << "\n"; 660 SmallVector<SDNode *, 4> GluedNodes; 661 for (SDNode *N = SU->getNode()->getGluedNode(); N; N = N->getGluedNode()) 662 GluedNodes.push_back(N); 663 while (!GluedNodes.empty()) { 664 dbgs() << " "; 665 GluedNodes.back()->dump(DAG); 666 dbgs() << "\n"; 667 GluedNodes.pop_back(); 668 } 669#endif 670} 671 672#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 673void ScheduleDAGSDNodes::dumpSchedule() const { 674 for (unsigned i = 0, e = Sequence.size(); i != e; i++) { 675 if (SUnit *SU = Sequence[i]) 676 SU->dump(this); 677 else 678 dbgs() << "**** NOOP ****\n"; 679 } 680} 681#endif 682 683#ifndef NDEBUG 684/// VerifyScheduledSequence - Verify that all SUnits were scheduled and that 685/// their state is consistent with the nodes listed in Sequence. 686/// 687void ScheduleDAGSDNodes::VerifyScheduledSequence(bool isBottomUp) { 688 unsigned ScheduledNodes = ScheduleDAG::VerifyScheduledDAG(isBottomUp); 689 unsigned Noops = 0; 690 for (unsigned i = 0, e = Sequence.size(); i != e; ++i) 691 if (!Sequence[i]) 692 ++Noops; 693 assert(Sequence.size() - Noops == ScheduledNodes && 694 "The number of nodes scheduled doesn't match the expected number!"); 695} 696#endif // NDEBUG 697 698/// ProcessSDDbgValues - Process SDDbgValues associated with this node. 699static void 700ProcessSDDbgValues(SDNode *N, SelectionDAG *DAG, InstrEmitter &Emitter, 701 SmallVectorImpl<std::pair<unsigned, MachineInstr*> > &Orders, 702 DenseMap<SDValue, unsigned> &VRBaseMap, unsigned Order) { 703 if (!N->getHasDebugValue()) 704 return; 705 706 // Opportunistically insert immediate dbg_value uses, i.e. those with source 707 // order number right after the N. 708 MachineBasicBlock *BB = Emitter.getBlock(); 709 MachineBasicBlock::iterator InsertPos = Emitter.getInsertPos(); 710 ArrayRef<SDDbgValue*> DVs = DAG->GetDbgValues(N); 711 for (unsigned i = 0, e = DVs.size(); i != e; ++i) { 712 if (DVs[i]->isInvalidated()) 713 continue; 714 unsigned DVOrder = DVs[i]->getOrder(); 715 if (!Order || DVOrder == ++Order) { 716 MachineInstr *DbgMI = Emitter.EmitDbgValue(DVs[i], VRBaseMap); 717 if (DbgMI) { 718 Orders.push_back(std::make_pair(DVOrder, DbgMI)); 719 BB->insert(InsertPos, DbgMI); 720 } 721 DVs[i]->setIsInvalidated(); 722 } 723 } 724} 725 726// ProcessSourceNode - Process nodes with source order numbers. These are added 727// to a vector which EmitSchedule uses to determine how to insert dbg_value 728// instructions in the right order. 729static void 730ProcessSourceNode(SDNode *N, SelectionDAG *DAG, InstrEmitter &Emitter, 731 DenseMap<SDValue, unsigned> &VRBaseMap, 732 SmallVectorImpl<std::pair<unsigned, MachineInstr*> > &Orders, 733 SmallSet<unsigned, 8> &Seen) { 734 unsigned Order = N->getIROrder(); 735 if (!Order || !Seen.insert(Order)) { 736 // Process any valid SDDbgValues even if node does not have any order 737 // assigned. 738 ProcessSDDbgValues(N, DAG, Emitter, Orders, VRBaseMap, 0); 739 return; 740 } 741 742 MachineBasicBlock *BB = Emitter.getBlock(); 743 if (Emitter.getInsertPos() == BB->begin() || BB->back().isPHI() || 744 // Fast-isel may have inserted some instructions, in which case the 745 // BB->back().isPHI() test will not fire when we want it to. 746 prior(Emitter.getInsertPos())->isPHI()) { 747 // Did not insert any instruction. 748 Orders.push_back(std::make_pair(Order, (MachineInstr*)0)); 749 return; 750 } 751 752 Orders.push_back(std::make_pair(Order, prior(Emitter.getInsertPos()))); 753 ProcessSDDbgValues(N, DAG, Emitter, Orders, VRBaseMap, Order); 754} 755 756void ScheduleDAGSDNodes:: 757EmitPhysRegCopy(SUnit *SU, DenseMap<SUnit*, unsigned> &VRBaseMap, 758 MachineBasicBlock::iterator InsertPos) { 759 for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 760 I != E; ++I) { 761 if (I->isCtrl()) continue; // ignore chain preds 762 if (I->getSUnit()->CopyDstRC) { 763 // Copy to physical register. 764 DenseMap<SUnit*, unsigned>::iterator VRI = VRBaseMap.find(I->getSUnit()); 765 assert(VRI != VRBaseMap.end() && "Node emitted out of order - late"); 766 // Find the destination physical register. 767 unsigned Reg = 0; 768 for (SUnit::const_succ_iterator II = SU->Succs.begin(), 769 EE = SU->Succs.end(); II != EE; ++II) { 770 if (II->isCtrl()) continue; // ignore chain preds 771 if (II->getReg()) { 772 Reg = II->getReg(); 773 break; 774 } 775 } 776 BuildMI(*BB, InsertPos, DebugLoc(), TII->get(TargetOpcode::COPY), Reg) 777 .addReg(VRI->second); 778 } else { 779 // Copy from physical register. 780 assert(I->getReg() && "Unknown physical register!"); 781 unsigned VRBase = MRI.createVirtualRegister(SU->CopyDstRC); 782 bool isNew = VRBaseMap.insert(std::make_pair(SU, VRBase)).second; 783 (void)isNew; // Silence compiler warning. 784 assert(isNew && "Node emitted out of order - early"); 785 BuildMI(*BB, InsertPos, DebugLoc(), TII->get(TargetOpcode::COPY), VRBase) 786 .addReg(I->getReg()); 787 } 788 break; 789 } 790} 791 792/// EmitSchedule - Emit the machine code in scheduled order. Return the new 793/// InsertPos and MachineBasicBlock that contains this insertion 794/// point. ScheduleDAGSDNodes holds a BB pointer for convenience, but this does 795/// not necessarily refer to returned BB. The emitter may split blocks. 796MachineBasicBlock *ScheduleDAGSDNodes:: 797EmitSchedule(MachineBasicBlock::iterator &InsertPos) { 798 InstrEmitter Emitter(BB, InsertPos); 799 DenseMap<SDValue, unsigned> VRBaseMap; 800 DenseMap<SUnit*, unsigned> CopyVRBaseMap; 801 SmallVector<std::pair<unsigned, MachineInstr*>, 32> Orders; 802 SmallSet<unsigned, 8> Seen; 803 bool HasDbg = DAG->hasDebugValues(); 804 805 // If this is the first BB, emit byval parameter dbg_value's. 806 if (HasDbg && BB->getParent()->begin() == MachineFunction::iterator(BB)) { 807 SDDbgInfo::DbgIterator PDI = DAG->ByvalParmDbgBegin(); 808 SDDbgInfo::DbgIterator PDE = DAG->ByvalParmDbgEnd(); 809 for (; PDI != PDE; ++PDI) { 810 MachineInstr *DbgMI= Emitter.EmitDbgValue(*PDI, VRBaseMap); 811 if (DbgMI) 812 BB->insert(InsertPos, DbgMI); 813 } 814 } 815 816 for (unsigned i = 0, e = Sequence.size(); i != e; i++) { 817 SUnit *SU = Sequence[i]; 818 if (!SU) { 819 // Null SUnit* is a noop. 820 TII->insertNoop(*Emitter.getBlock(), InsertPos); 821 continue; 822 } 823 824 // For pre-regalloc scheduling, create instructions corresponding to the 825 // SDNode and any glued SDNodes and append them to the block. 826 if (!SU->getNode()) { 827 // Emit a copy. 828 EmitPhysRegCopy(SU, CopyVRBaseMap, InsertPos); 829 continue; 830 } 831 832 SmallVector<SDNode *, 4> GluedNodes; 833 for (SDNode *N = SU->getNode()->getGluedNode(); N; N = N->getGluedNode()) 834 GluedNodes.push_back(N); 835 while (!GluedNodes.empty()) { 836 SDNode *N = GluedNodes.back(); 837 Emitter.EmitNode(GluedNodes.back(), SU->OrigNode != SU, SU->isCloned, 838 VRBaseMap); 839 // Remember the source order of the inserted instruction. 840 if (HasDbg) 841 ProcessSourceNode(N, DAG, Emitter, VRBaseMap, Orders, Seen); 842 GluedNodes.pop_back(); 843 } 844 Emitter.EmitNode(SU->getNode(), SU->OrigNode != SU, SU->isCloned, 845 VRBaseMap); 846 // Remember the source order of the inserted instruction. 847 if (HasDbg) 848 ProcessSourceNode(SU->getNode(), DAG, Emitter, VRBaseMap, Orders, 849 Seen); 850 } 851 852 // Insert all the dbg_values which have not already been inserted in source 853 // order sequence. 854 if (HasDbg) { 855 MachineBasicBlock::iterator BBBegin = BB->getFirstNonPHI(); 856 857 // Sort the source order instructions and use the order to insert debug 858 // values. 859 std::sort(Orders.begin(), Orders.end(), less_first()); 860 861 SDDbgInfo::DbgIterator DI = DAG->DbgBegin(); 862 SDDbgInfo::DbgIterator DE = DAG->DbgEnd(); 863 // Now emit the rest according to source order. 864 unsigned LastOrder = 0; 865 for (unsigned i = 0, e = Orders.size(); i != e && DI != DE; ++i) { 866 unsigned Order = Orders[i].first; 867 MachineInstr *MI = Orders[i].second; 868 // Insert all SDDbgValue's whose order(s) are before "Order". 869 if (!MI) 870 continue; 871 for (; DI != DE && 872 (*DI)->getOrder() >= LastOrder && (*DI)->getOrder() < Order; ++DI) { 873 if ((*DI)->isInvalidated()) 874 continue; 875 MachineInstr *DbgMI = Emitter.EmitDbgValue(*DI, VRBaseMap); 876 if (DbgMI) { 877 if (!LastOrder) 878 // Insert to start of the BB (after PHIs). 879 BB->insert(BBBegin, DbgMI); 880 else { 881 // Insert at the instruction, which may be in a different 882 // block, if the block was split by a custom inserter. 883 MachineBasicBlock::iterator Pos = MI; 884 MI->getParent()->insert(Pos, DbgMI); 885 } 886 } 887 } 888 LastOrder = Order; 889 } 890 // Add trailing DbgValue's before the terminator. FIXME: May want to add 891 // some of them before one or more conditional branches? 892 SmallVector<MachineInstr*, 8> DbgMIs; 893 while (DI != DE) { 894 if (!(*DI)->isInvalidated()) 895 if (MachineInstr *DbgMI = Emitter.EmitDbgValue(*DI, VRBaseMap)) 896 DbgMIs.push_back(DbgMI); 897 ++DI; 898 } 899 900 MachineBasicBlock *InsertBB = Emitter.getBlock(); 901 MachineBasicBlock::iterator Pos = InsertBB->getFirstTerminator(); 902 InsertBB->insert(Pos, DbgMIs.begin(), DbgMIs.end()); 903 } 904 905 InsertPos = Emitter.getInsertPos(); 906 return Emitter.getBlock(); 907} 908 909/// Return the basic block label. 910std::string ScheduleDAGSDNodes::getDAGName() const { 911 return "sunit-dag." + BB->getFullName(); 912}
|