ScheduleDAGSDNodes.cpp 37 KB

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