109467b48Spatrick //===--- ScheduleDAGSDNodes.cpp - Implement the ScheduleDAGSDNodes class --===//
209467b48Spatrick //
309467b48Spatrick // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
409467b48Spatrick // See https://llvm.org/LICENSE.txt for license information.
509467b48Spatrick // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
609467b48Spatrick //
709467b48Spatrick //===----------------------------------------------------------------------===//
809467b48Spatrick //
909467b48Spatrick // This implements the ScheduleDAG class, which is a base class used by
1009467b48Spatrick // scheduling implementation classes.
1109467b48Spatrick //
1209467b48Spatrick //===----------------------------------------------------------------------===//
1309467b48Spatrick
1409467b48Spatrick #include "ScheduleDAGSDNodes.h"
1509467b48Spatrick #include "InstrEmitter.h"
1609467b48Spatrick #include "SDNodeDbgValue.h"
1709467b48Spatrick #include "llvm/ADT/DenseMap.h"
1809467b48Spatrick #include "llvm/ADT/SmallPtrSet.h"
1909467b48Spatrick #include "llvm/ADT/SmallSet.h"
2009467b48Spatrick #include "llvm/ADT/SmallVector.h"
2109467b48Spatrick #include "llvm/ADT/Statistic.h"
2209467b48Spatrick #include "llvm/CodeGen/MachineInstrBuilder.h"
2309467b48Spatrick #include "llvm/CodeGen/MachineRegisterInfo.h"
2409467b48Spatrick #include "llvm/CodeGen/SelectionDAG.h"
2509467b48Spatrick #include "llvm/CodeGen/TargetInstrInfo.h"
2609467b48Spatrick #include "llvm/CodeGen/TargetLowering.h"
2709467b48Spatrick #include "llvm/CodeGen/TargetRegisterInfo.h"
2809467b48Spatrick #include "llvm/CodeGen/TargetSubtargetInfo.h"
2909467b48Spatrick #include "llvm/Config/llvm-config.h"
3009467b48Spatrick #include "llvm/MC/MCInstrItineraries.h"
3109467b48Spatrick #include "llvm/Support/CommandLine.h"
3209467b48Spatrick #include "llvm/Support/Debug.h"
3309467b48Spatrick #include "llvm/Support/raw_ostream.h"
34097a140dSpatrick #include "llvm/Target/TargetMachine.h"
3509467b48Spatrick using namespace llvm;
3609467b48Spatrick
3709467b48Spatrick #define DEBUG_TYPE "pre-RA-sched"
3809467b48Spatrick
3909467b48Spatrick STATISTIC(LoadsClustered, "Number of loads clustered together");
4009467b48Spatrick
4109467b48Spatrick // This allows the latency-based scheduler to notice high latency instructions
4209467b48Spatrick // without a target itinerary. The choice of number here has more to do with
4309467b48Spatrick // balancing scheduler heuristics than with the actual machine latency.
4409467b48Spatrick static cl::opt<int> HighLatencyCycles(
4509467b48Spatrick "sched-high-latency-cycles", cl::Hidden, cl::init(10),
4609467b48Spatrick cl::desc("Roughly estimate the number of cycles that 'long latency'"
4709467b48Spatrick "instructions take for targets with no itinerary"));
4809467b48Spatrick
ScheduleDAGSDNodes(MachineFunction & mf)4909467b48Spatrick ScheduleDAGSDNodes::ScheduleDAGSDNodes(MachineFunction &mf)
50*d415bd75Srobert : ScheduleDAG(mf), InstrItins(mf.getSubtarget().getInstrItineraryData()) {}
5109467b48Spatrick
5209467b48Spatrick /// Run - perform scheduling.
5309467b48Spatrick ///
Run(SelectionDAG * dag,MachineBasicBlock * bb)5409467b48Spatrick void ScheduleDAGSDNodes::Run(SelectionDAG *dag, MachineBasicBlock *bb) {
5509467b48Spatrick BB = bb;
5609467b48Spatrick DAG = dag;
5709467b48Spatrick
5809467b48Spatrick // Clear the scheduler's SUnit DAG.
5909467b48Spatrick ScheduleDAG::clearDAG();
6009467b48Spatrick Sequence.clear();
6109467b48Spatrick
6209467b48Spatrick // Invoke the target's selection of scheduler.
6309467b48Spatrick Schedule();
6409467b48Spatrick }
6509467b48Spatrick
6609467b48Spatrick /// NewSUnit - Creates a new SUnit and return a ptr to it.
6709467b48Spatrick ///
newSUnit(SDNode * N)6809467b48Spatrick SUnit *ScheduleDAGSDNodes::newSUnit(SDNode *N) {
6909467b48Spatrick #ifndef NDEBUG
7009467b48Spatrick const SUnit *Addr = nullptr;
7109467b48Spatrick if (!SUnits.empty())
7209467b48Spatrick Addr = &SUnits[0];
7309467b48Spatrick #endif
7409467b48Spatrick SUnits.emplace_back(N, (unsigned)SUnits.size());
7509467b48Spatrick assert((Addr == nullptr || Addr == &SUnits[0]) &&
7609467b48Spatrick "SUnits std::vector reallocated on the fly!");
7709467b48Spatrick SUnits.back().OrigNode = &SUnits.back();
7809467b48Spatrick SUnit *SU = &SUnits.back();
7909467b48Spatrick const TargetLowering &TLI = DAG->getTargetLoweringInfo();
8009467b48Spatrick if (!N ||
8109467b48Spatrick (N->isMachineOpcode() &&
8209467b48Spatrick N->getMachineOpcode() == TargetOpcode::IMPLICIT_DEF))
8309467b48Spatrick SU->SchedulingPref = Sched::None;
8409467b48Spatrick else
8509467b48Spatrick SU->SchedulingPref = TLI.getSchedulingPreference(N);
8609467b48Spatrick return SU;
8709467b48Spatrick }
8809467b48Spatrick
Clone(SUnit * Old)8909467b48Spatrick SUnit *ScheduleDAGSDNodes::Clone(SUnit *Old) {
9009467b48Spatrick SUnit *SU = newSUnit(Old->getNode());
9109467b48Spatrick SU->OrigNode = Old->OrigNode;
9209467b48Spatrick SU->Latency = Old->Latency;
9309467b48Spatrick SU->isVRegCycle = Old->isVRegCycle;
9409467b48Spatrick SU->isCall = Old->isCall;
9509467b48Spatrick SU->isCallOp = Old->isCallOp;
9609467b48Spatrick SU->isTwoAddress = Old->isTwoAddress;
9709467b48Spatrick SU->isCommutable = Old->isCommutable;
9809467b48Spatrick SU->hasPhysRegDefs = Old->hasPhysRegDefs;
9909467b48Spatrick SU->hasPhysRegClobbers = Old->hasPhysRegClobbers;
10009467b48Spatrick SU->isScheduleHigh = Old->isScheduleHigh;
10109467b48Spatrick SU->isScheduleLow = Old->isScheduleLow;
10209467b48Spatrick SU->SchedulingPref = Old->SchedulingPref;
10309467b48Spatrick Old->isCloned = true;
10409467b48Spatrick return SU;
10509467b48Spatrick }
10609467b48Spatrick
10709467b48Spatrick /// CheckForPhysRegDependency - Check if the dependency between def and use of
10809467b48Spatrick /// a specified operand is a physical register dependency. If so, returns the
10909467b48Spatrick /// register and the cost of copying the register.
CheckForPhysRegDependency(SDNode * Def,SDNode * User,unsigned Op,const TargetRegisterInfo * TRI,const TargetInstrInfo * TII,const TargetLowering & TLI,unsigned & PhysReg,int & Cost)11009467b48Spatrick static void CheckForPhysRegDependency(SDNode *Def, SDNode *User, unsigned Op,
11109467b48Spatrick const TargetRegisterInfo *TRI,
11209467b48Spatrick const TargetInstrInfo *TII,
113*d415bd75Srobert const TargetLowering &TLI,
11409467b48Spatrick unsigned &PhysReg, int &Cost) {
11509467b48Spatrick if (Op != 2 || User->getOpcode() != ISD::CopyToReg)
11609467b48Spatrick return;
11709467b48Spatrick
11809467b48Spatrick unsigned Reg = cast<RegisterSDNode>(User->getOperand(1))->getReg();
119*d415bd75Srobert if (TLI.checkForPhysRegDependency(Def, User, Op, TRI, TII, PhysReg, Cost))
120*d415bd75Srobert return;
121*d415bd75Srobert
12209467b48Spatrick if (Register::isVirtualRegister(Reg))
12309467b48Spatrick return;
12409467b48Spatrick
12509467b48Spatrick unsigned ResNo = User->getOperand(2).getResNo();
12609467b48Spatrick if (Def->getOpcode() == ISD::CopyFromReg &&
12709467b48Spatrick cast<RegisterSDNode>(Def->getOperand(1))->getReg() == Reg) {
12809467b48Spatrick PhysReg = Reg;
12909467b48Spatrick } else if (Def->isMachineOpcode()) {
13009467b48Spatrick const MCInstrDesc &II = TII->get(Def->getMachineOpcode());
13173471bf0Spatrick if (ResNo >= II.getNumDefs() && II.hasImplicitDefOfPhysReg(Reg))
13209467b48Spatrick PhysReg = Reg;
13309467b48Spatrick }
13409467b48Spatrick
13509467b48Spatrick if (PhysReg != 0) {
13609467b48Spatrick const TargetRegisterClass *RC =
13709467b48Spatrick TRI->getMinimalPhysRegClass(Reg, Def->getSimpleValueType(ResNo));
13809467b48Spatrick Cost = RC->getCopyCost();
13909467b48Spatrick }
14009467b48Spatrick }
14109467b48Spatrick
14209467b48Spatrick // Helper for AddGlue to clone node operands.
CloneNodeWithValues(SDNode * N,SelectionDAG * DAG,ArrayRef<EVT> VTs,SDValue ExtraOper=SDValue ())14309467b48Spatrick static void CloneNodeWithValues(SDNode *N, SelectionDAG *DAG, ArrayRef<EVT> VTs,
14409467b48Spatrick SDValue ExtraOper = SDValue()) {
14509467b48Spatrick SmallVector<SDValue, 8> Ops(N->op_begin(), N->op_end());
14609467b48Spatrick if (ExtraOper.getNode())
14709467b48Spatrick Ops.push_back(ExtraOper);
14809467b48Spatrick
14909467b48Spatrick SDVTList VTList = DAG->getVTList(VTs);
15009467b48Spatrick MachineSDNode *MN = dyn_cast<MachineSDNode>(N);
15109467b48Spatrick
15209467b48Spatrick // Store memory references.
15309467b48Spatrick SmallVector<MachineMemOperand *, 2> MMOs;
15409467b48Spatrick if (MN)
15509467b48Spatrick MMOs.assign(MN->memoperands_begin(), MN->memoperands_end());
15609467b48Spatrick
15709467b48Spatrick DAG->MorphNodeTo(N, N->getOpcode(), VTList, Ops);
15809467b48Spatrick
15909467b48Spatrick // Reset the memory references
16009467b48Spatrick if (MN)
16109467b48Spatrick DAG->setNodeMemRefs(MN, MMOs);
16209467b48Spatrick }
16309467b48Spatrick
AddGlue(SDNode * N,SDValue Glue,bool AddGlue,SelectionDAG * DAG)16409467b48Spatrick static bool AddGlue(SDNode *N, SDValue Glue, bool AddGlue, SelectionDAG *DAG) {
16509467b48Spatrick SDNode *GlueDestNode = Glue.getNode();
16609467b48Spatrick
16709467b48Spatrick // Don't add glue from a node to itself.
16809467b48Spatrick if (GlueDestNode == N) return false;
16909467b48Spatrick
17009467b48Spatrick // Don't add a glue operand to something that already uses glue.
17109467b48Spatrick if (GlueDestNode &&
17209467b48Spatrick N->getOperand(N->getNumOperands()-1).getValueType() == MVT::Glue) {
17309467b48Spatrick return false;
17409467b48Spatrick }
17509467b48Spatrick // Don't add glue to something that already has a glue value.
17609467b48Spatrick if (N->getValueType(N->getNumValues() - 1) == MVT::Glue) return false;
17709467b48Spatrick
17873471bf0Spatrick SmallVector<EVT, 4> VTs(N->values());
17909467b48Spatrick if (AddGlue)
18009467b48Spatrick VTs.push_back(MVT::Glue);
18109467b48Spatrick
18209467b48Spatrick CloneNodeWithValues(N, DAG, VTs, Glue);
18309467b48Spatrick
18409467b48Spatrick return true;
18509467b48Spatrick }
18609467b48Spatrick
18709467b48Spatrick // Cleanup after unsuccessful AddGlue. Use the standard method of morphing the
18809467b48Spatrick // node even though simply shrinking the value list is sufficient.
RemoveUnusedGlue(SDNode * N,SelectionDAG * DAG)18909467b48Spatrick static void RemoveUnusedGlue(SDNode *N, SelectionDAG *DAG) {
19009467b48Spatrick assert((N->getValueType(N->getNumValues() - 1) == MVT::Glue &&
19109467b48Spatrick !N->hasAnyUseOfValue(N->getNumValues() - 1)) &&
19209467b48Spatrick "expected an unused glue value");
19309467b48Spatrick
19409467b48Spatrick CloneNodeWithValues(N, DAG,
195*d415bd75Srobert ArrayRef(N->value_begin(), N->getNumValues() - 1));
19609467b48Spatrick }
19709467b48Spatrick
19809467b48Spatrick /// ClusterNeighboringLoads - Force nearby loads together by "gluing" them.
19909467b48Spatrick /// This function finds loads of the same base and different offsets. If the
20009467b48Spatrick /// offsets are not far apart (target specific), it add MVT::Glue inputs and
20109467b48Spatrick /// outputs to ensure they are scheduled together and in order. This
20209467b48Spatrick /// optimization may benefit some targets by improving cache locality.
ClusterNeighboringLoads(SDNode * Node)20309467b48Spatrick void ScheduleDAGSDNodes::ClusterNeighboringLoads(SDNode *Node) {
204097a140dSpatrick SDValue Chain;
20509467b48Spatrick unsigned NumOps = Node->getNumOperands();
20609467b48Spatrick if (Node->getOperand(NumOps-1).getValueType() == MVT::Other)
207097a140dSpatrick Chain = Node->getOperand(NumOps-1);
20809467b48Spatrick if (!Chain)
20909467b48Spatrick return;
21009467b48Spatrick
21109467b48Spatrick // Skip any load instruction that has a tied input. There may be an additional
21209467b48Spatrick // dependency requiring a different order than by increasing offsets, and the
21309467b48Spatrick // added glue may introduce a cycle.
21409467b48Spatrick auto hasTiedInput = [this](const SDNode *N) {
21509467b48Spatrick const MCInstrDesc &MCID = TII->get(N->getMachineOpcode());
21609467b48Spatrick for (unsigned I = 0; I != MCID.getNumOperands(); ++I) {
21709467b48Spatrick if (MCID.getOperandConstraint(I, MCOI::TIED_TO) != -1)
21809467b48Spatrick return true;
21909467b48Spatrick }
22009467b48Spatrick
22109467b48Spatrick return false;
22209467b48Spatrick };
22309467b48Spatrick
22409467b48Spatrick // Look for other loads of the same chain. Find loads that are loading from
22509467b48Spatrick // the same base pointer and different offsets.
22609467b48Spatrick SmallPtrSet<SDNode*, 16> Visited;
22709467b48Spatrick SmallVector<int64_t, 4> Offsets;
22809467b48Spatrick DenseMap<long long, SDNode*> O2SMap; // Map from offset to SDNode.
22909467b48Spatrick bool Cluster = false;
23009467b48Spatrick SDNode *Base = Node;
23109467b48Spatrick
23209467b48Spatrick if (hasTiedInput(Base))
23309467b48Spatrick return;
23409467b48Spatrick
23509467b48Spatrick // This algorithm requires a reasonably low use count before finding a match
23609467b48Spatrick // to avoid uselessly blowing up compile time in large blocks.
23709467b48Spatrick unsigned UseCount = 0;
23809467b48Spatrick for (SDNode::use_iterator I = Chain->use_begin(), E = Chain->use_end();
23909467b48Spatrick I != E && UseCount < 100; ++I, ++UseCount) {
240097a140dSpatrick if (I.getUse().getResNo() != Chain.getResNo())
241097a140dSpatrick continue;
242097a140dSpatrick
24309467b48Spatrick SDNode *User = *I;
24409467b48Spatrick if (User == Node || !Visited.insert(User).second)
24509467b48Spatrick continue;
24609467b48Spatrick int64_t Offset1, Offset2;
24709467b48Spatrick if (!TII->areLoadsFromSameBasePtr(Base, User, Offset1, Offset2) ||
24809467b48Spatrick Offset1 == Offset2 ||
24909467b48Spatrick hasTiedInput(User)) {
25009467b48Spatrick // FIXME: Should be ok if they addresses are identical. But earlier
25109467b48Spatrick // optimizations really should have eliminated one of the loads.
25209467b48Spatrick continue;
25309467b48Spatrick }
25409467b48Spatrick if (O2SMap.insert(std::make_pair(Offset1, Base)).second)
25509467b48Spatrick Offsets.push_back(Offset1);
25609467b48Spatrick O2SMap.insert(std::make_pair(Offset2, User));
25709467b48Spatrick Offsets.push_back(Offset2);
25809467b48Spatrick if (Offset2 < Offset1)
25909467b48Spatrick Base = User;
26009467b48Spatrick Cluster = true;
26109467b48Spatrick // Reset UseCount to allow more matches.
26209467b48Spatrick UseCount = 0;
26309467b48Spatrick }
26409467b48Spatrick
26509467b48Spatrick if (!Cluster)
26609467b48Spatrick return;
26709467b48Spatrick
26809467b48Spatrick // Sort them in increasing order.
26909467b48Spatrick llvm::sort(Offsets);
27009467b48Spatrick
27109467b48Spatrick // Check if the loads are close enough.
27209467b48Spatrick SmallVector<SDNode*, 4> Loads;
27309467b48Spatrick unsigned NumLoads = 0;
27409467b48Spatrick int64_t BaseOff = Offsets[0];
27509467b48Spatrick SDNode *BaseLoad = O2SMap[BaseOff];
27609467b48Spatrick Loads.push_back(BaseLoad);
27709467b48Spatrick for (unsigned i = 1, e = Offsets.size(); i != e; ++i) {
27809467b48Spatrick int64_t Offset = Offsets[i];
27909467b48Spatrick SDNode *Load = O2SMap[Offset];
28009467b48Spatrick if (!TII->shouldScheduleLoadsNear(BaseLoad, Load, BaseOff, Offset,NumLoads))
28109467b48Spatrick break; // Stop right here. Ignore loads that are further away.
28209467b48Spatrick Loads.push_back(Load);
28309467b48Spatrick ++NumLoads;
28409467b48Spatrick }
28509467b48Spatrick
28609467b48Spatrick if (NumLoads == 0)
28709467b48Spatrick return;
28809467b48Spatrick
28909467b48Spatrick // Cluster loads by adding MVT::Glue outputs and inputs. This also
29009467b48Spatrick // ensure they are scheduled in order of increasing addresses.
29109467b48Spatrick SDNode *Lead = Loads[0];
292*d415bd75Srobert SDValue InGlue;
29309467b48Spatrick if (AddGlue(Lead, InGlue, true, DAG))
29409467b48Spatrick InGlue = SDValue(Lead, Lead->getNumValues() - 1);
29509467b48Spatrick for (unsigned I = 1, E = Loads.size(); I != E; ++I) {
29609467b48Spatrick bool OutGlue = I < E - 1;
29709467b48Spatrick SDNode *Load = Loads[I];
29809467b48Spatrick
29909467b48Spatrick // If AddGlue fails, we could leave an unsused glue value. This should not
30009467b48Spatrick // cause any
30109467b48Spatrick if (AddGlue(Load, InGlue, OutGlue, DAG)) {
30209467b48Spatrick if (OutGlue)
30309467b48Spatrick InGlue = SDValue(Load, Load->getNumValues() - 1);
30409467b48Spatrick
30509467b48Spatrick ++LoadsClustered;
30609467b48Spatrick }
30709467b48Spatrick else if (!OutGlue && InGlue.getNode())
30809467b48Spatrick RemoveUnusedGlue(InGlue.getNode(), DAG);
30909467b48Spatrick }
31009467b48Spatrick }
31109467b48Spatrick
31209467b48Spatrick /// ClusterNodes - Cluster certain nodes which should be scheduled together.
31309467b48Spatrick ///
ClusterNodes()31409467b48Spatrick void ScheduleDAGSDNodes::ClusterNodes() {
31509467b48Spatrick for (SDNode &NI : DAG->allnodes()) {
31609467b48Spatrick SDNode *Node = &NI;
31709467b48Spatrick if (!Node || !Node->isMachineOpcode())
31809467b48Spatrick continue;
31909467b48Spatrick
32009467b48Spatrick unsigned Opc = Node->getMachineOpcode();
32109467b48Spatrick const MCInstrDesc &MCID = TII->get(Opc);
32209467b48Spatrick if (MCID.mayLoad())
32309467b48Spatrick // Cluster loads from "near" addresses into combined SUnits.
32409467b48Spatrick ClusterNeighboringLoads(Node);
32509467b48Spatrick }
32609467b48Spatrick }
32709467b48Spatrick
BuildSchedUnits()32809467b48Spatrick void ScheduleDAGSDNodes::BuildSchedUnits() {
32909467b48Spatrick // During scheduling, the NodeId field of SDNode is used to map SDNodes
33009467b48Spatrick // to their associated SUnits by holding SUnits table indices. A value
33109467b48Spatrick // of -1 means the SDNode does not yet have an associated SUnit.
33209467b48Spatrick unsigned NumNodes = 0;
33309467b48Spatrick for (SDNode &NI : DAG->allnodes()) {
33409467b48Spatrick NI.setNodeId(-1);
33509467b48Spatrick ++NumNodes;
33609467b48Spatrick }
33709467b48Spatrick
33809467b48Spatrick // Reserve entries in the vector for each of the SUnits we are creating. This
33909467b48Spatrick // ensure that reallocation of the vector won't happen, so SUnit*'s won't get
34009467b48Spatrick // invalidated.
34109467b48Spatrick // FIXME: Multiply by 2 because we may clone nodes during scheduling.
34209467b48Spatrick // This is a temporary workaround.
34309467b48Spatrick SUnits.reserve(NumNodes * 2);
34409467b48Spatrick
34509467b48Spatrick // Add all nodes in depth first order.
34609467b48Spatrick SmallVector<SDNode*, 64> Worklist;
34709467b48Spatrick SmallPtrSet<SDNode*, 32> Visited;
34809467b48Spatrick Worklist.push_back(DAG->getRoot().getNode());
34909467b48Spatrick Visited.insert(DAG->getRoot().getNode());
35009467b48Spatrick
35109467b48Spatrick SmallVector<SUnit*, 8> CallSUnits;
35209467b48Spatrick while (!Worklist.empty()) {
35309467b48Spatrick SDNode *NI = Worklist.pop_back_val();
35409467b48Spatrick
35509467b48Spatrick // Add all operands to the worklist unless they've already been added.
35609467b48Spatrick for (const SDValue &Op : NI->op_values())
35709467b48Spatrick if (Visited.insert(Op.getNode()).second)
35809467b48Spatrick Worklist.push_back(Op.getNode());
35909467b48Spatrick
36009467b48Spatrick if (isPassiveNode(NI)) // Leaf node, e.g. a TargetImmediate.
36109467b48Spatrick continue;
36209467b48Spatrick
36309467b48Spatrick // If this node has already been processed, stop now.
36409467b48Spatrick if (NI->getNodeId() != -1) continue;
36509467b48Spatrick
36609467b48Spatrick SUnit *NodeSUnit = newSUnit(NI);
36709467b48Spatrick
36809467b48Spatrick // See if anything is glued to this node, if so, add them to glued
36909467b48Spatrick // nodes. Nodes can have at most one glue input and one glue output. Glue
37009467b48Spatrick // is required to be the last operand and result of a node.
37109467b48Spatrick
37209467b48Spatrick // Scan up to find glued preds.
37309467b48Spatrick SDNode *N = NI;
37409467b48Spatrick while (N->getNumOperands() &&
37509467b48Spatrick N->getOperand(N->getNumOperands()-1).getValueType() == MVT::Glue) {
37609467b48Spatrick N = N->getOperand(N->getNumOperands()-1).getNode();
37709467b48Spatrick assert(N->getNodeId() == -1 && "Node already inserted!");
37809467b48Spatrick N->setNodeId(NodeSUnit->NodeNum);
37909467b48Spatrick if (N->isMachineOpcode() && TII->get(N->getMachineOpcode()).isCall())
38009467b48Spatrick NodeSUnit->isCall = true;
38109467b48Spatrick }
38209467b48Spatrick
38309467b48Spatrick // Scan down to find any glued succs.
38409467b48Spatrick N = NI;
38509467b48Spatrick while (N->getValueType(N->getNumValues()-1) == MVT::Glue) {
38609467b48Spatrick SDValue GlueVal(N, N->getNumValues()-1);
38709467b48Spatrick
38809467b48Spatrick // There are either zero or one users of the Glue result.
38909467b48Spatrick bool HasGlueUse = false;
390*d415bd75Srobert for (SDNode *U : N->uses())
391*d415bd75Srobert if (GlueVal.isOperandOf(U)) {
39209467b48Spatrick HasGlueUse = true;
39309467b48Spatrick assert(N->getNodeId() == -1 && "Node already inserted!");
39409467b48Spatrick N->setNodeId(NodeSUnit->NodeNum);
395*d415bd75Srobert N = U;
39609467b48Spatrick if (N->isMachineOpcode() && TII->get(N->getMachineOpcode()).isCall())
39709467b48Spatrick NodeSUnit->isCall = true;
39809467b48Spatrick break;
39909467b48Spatrick }
40009467b48Spatrick if (!HasGlueUse) break;
40109467b48Spatrick }
40209467b48Spatrick
40309467b48Spatrick if (NodeSUnit->isCall)
40409467b48Spatrick CallSUnits.push_back(NodeSUnit);
40509467b48Spatrick
40609467b48Spatrick // Schedule zero-latency TokenFactor below any nodes that may increase the
40709467b48Spatrick // schedule height. Otherwise, ancestors of the TokenFactor may appear to
40809467b48Spatrick // have false stalls.
40909467b48Spatrick if (NI->getOpcode() == ISD::TokenFactor)
41009467b48Spatrick NodeSUnit->isScheduleLow = true;
41109467b48Spatrick
41209467b48Spatrick // If there are glue operands involved, N is now the bottom-most node
41309467b48Spatrick // of the sequence of nodes that are glued together.
41409467b48Spatrick // Update the SUnit.
41509467b48Spatrick NodeSUnit->setNode(N);
41609467b48Spatrick assert(N->getNodeId() == -1 && "Node already inserted!");
41709467b48Spatrick N->setNodeId(NodeSUnit->NodeNum);
41809467b48Spatrick
41909467b48Spatrick // Compute NumRegDefsLeft. This must be done before AddSchedEdges.
42009467b48Spatrick InitNumRegDefsLeft(NodeSUnit);
42109467b48Spatrick
42209467b48Spatrick // Assign the Latency field of NodeSUnit using target-provided information.
42309467b48Spatrick computeLatency(NodeSUnit);
42409467b48Spatrick }
42509467b48Spatrick
42609467b48Spatrick // Find all call operands.
42709467b48Spatrick while (!CallSUnits.empty()) {
42809467b48Spatrick SUnit *SU = CallSUnits.pop_back_val();
42909467b48Spatrick for (const SDNode *SUNode = SU->getNode(); SUNode;
43009467b48Spatrick SUNode = SUNode->getGluedNode()) {
43109467b48Spatrick if (SUNode->getOpcode() != ISD::CopyToReg)
43209467b48Spatrick continue;
43309467b48Spatrick SDNode *SrcN = SUNode->getOperand(2).getNode();
43409467b48Spatrick if (isPassiveNode(SrcN)) continue; // Not scheduled.
43509467b48Spatrick SUnit *SrcSU = &SUnits[SrcN->getNodeId()];
43609467b48Spatrick SrcSU->isCallOp = true;
43709467b48Spatrick }
43809467b48Spatrick }
43909467b48Spatrick }
44009467b48Spatrick
AddSchedEdges()44109467b48Spatrick void ScheduleDAGSDNodes::AddSchedEdges() {
44209467b48Spatrick const TargetSubtargetInfo &ST = MF.getSubtarget();
44309467b48Spatrick
44409467b48Spatrick // Check to see if the scheduler cares about latencies.
44509467b48Spatrick bool UnitLatencies = forceUnitLatencies();
44609467b48Spatrick
44709467b48Spatrick // Pass 2: add the preds, succs, etc.
448*d415bd75Srobert for (SUnit &SU : SUnits) {
449*d415bd75Srobert SDNode *MainNode = SU.getNode();
45009467b48Spatrick
45109467b48Spatrick if (MainNode->isMachineOpcode()) {
45209467b48Spatrick unsigned Opc = MainNode->getMachineOpcode();
45309467b48Spatrick const MCInstrDesc &MCID = TII->get(Opc);
45409467b48Spatrick for (unsigned i = 0; i != MCID.getNumOperands(); ++i) {
45509467b48Spatrick if (MCID.getOperandConstraint(i, MCOI::TIED_TO) != -1) {
456*d415bd75Srobert SU.isTwoAddress = true;
45709467b48Spatrick break;
45809467b48Spatrick }
45909467b48Spatrick }
46009467b48Spatrick if (MCID.isCommutable())
461*d415bd75Srobert SU.isCommutable = true;
46209467b48Spatrick }
46309467b48Spatrick
46409467b48Spatrick // Find all predecessors and successors of the group.
465*d415bd75Srobert for (SDNode *N = SU.getNode(); N; N = N->getGluedNode()) {
46609467b48Spatrick if (N->isMachineOpcode() &&
467*d415bd75Srobert !TII->get(N->getMachineOpcode()).implicit_defs().empty()) {
468*d415bd75Srobert SU.hasPhysRegClobbers = true;
46909467b48Spatrick unsigned NumUsed = InstrEmitter::CountResults(N);
47009467b48Spatrick while (NumUsed != 0 && !N->hasAnyUseOfValue(NumUsed - 1))
47109467b48Spatrick --NumUsed; // Skip over unused values at the end.
47209467b48Spatrick if (NumUsed > TII->get(N->getMachineOpcode()).getNumDefs())
473*d415bd75Srobert SU.hasPhysRegDefs = true;
47409467b48Spatrick }
47509467b48Spatrick
47609467b48Spatrick for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
47709467b48Spatrick SDNode *OpN = N->getOperand(i).getNode();
478097a140dSpatrick unsigned DefIdx = N->getOperand(i).getResNo();
47909467b48Spatrick if (isPassiveNode(OpN)) continue; // Not scheduled.
48009467b48Spatrick SUnit *OpSU = &SUnits[OpN->getNodeId()];
48109467b48Spatrick assert(OpSU && "Node has no SUnit!");
482*d415bd75Srobert if (OpSU == &SU)
483*d415bd75Srobert continue; // In the same group.
48409467b48Spatrick
48509467b48Spatrick EVT OpVT = N->getOperand(i).getValueType();
48609467b48Spatrick assert(OpVT != MVT::Glue && "Glued nodes should be in same sunit!");
48709467b48Spatrick bool isChain = OpVT == MVT::Other;
48809467b48Spatrick
48909467b48Spatrick unsigned PhysReg = 0;
49009467b48Spatrick int Cost = 1;
49109467b48Spatrick // Determine if this is a physical register dependency.
492*d415bd75Srobert const TargetLowering &TLI = DAG->getTargetLoweringInfo();
493*d415bd75Srobert CheckForPhysRegDependency(OpN, N, i, TRI, TII, TLI, PhysReg, Cost);
49409467b48Spatrick assert((PhysReg == 0 || !isChain) &&
49509467b48Spatrick "Chain dependence via physreg data?");
49609467b48Spatrick // FIXME: See ScheduleDAGSDNodes::EmitCopyFromReg. For now, scheduler
49709467b48Spatrick // emits a copy from the physical register to a virtual register unless
49809467b48Spatrick // it requires a cross class copy (cost < 0). That means we are only
49909467b48Spatrick // treating "expensive to copy" register dependency as physical register
50009467b48Spatrick // dependency. This may change in the future though.
50109467b48Spatrick if (Cost >= 0 && !StressSched)
50209467b48Spatrick PhysReg = 0;
50309467b48Spatrick
50409467b48Spatrick // If this is a ctrl dep, latency is 1.
50509467b48Spatrick unsigned OpLatency = isChain ? 1 : OpSU->Latency;
50609467b48Spatrick // Special-case TokenFactor chains as zero-latency.
50709467b48Spatrick if(isChain && OpN->getOpcode() == ISD::TokenFactor)
50809467b48Spatrick OpLatency = 0;
50909467b48Spatrick
51009467b48Spatrick SDep Dep = isChain ? SDep(OpSU, SDep::Barrier)
51109467b48Spatrick : SDep(OpSU, SDep::Data, PhysReg);
51209467b48Spatrick Dep.setLatency(OpLatency);
51309467b48Spatrick if (!isChain && !UnitLatencies) {
51409467b48Spatrick computeOperandLatency(OpN, N, i, Dep);
515*d415bd75Srobert ST.adjustSchedDependency(OpSU, DefIdx, &SU, i, Dep);
51609467b48Spatrick }
51709467b48Spatrick
518*d415bd75Srobert if (!SU.addPred(Dep) && !Dep.isCtrl() && OpSU->NumRegDefsLeft > 1) {
51909467b48Spatrick // Multiple register uses are combined in the same SUnit. For example,
52009467b48Spatrick // we could have a set of glued nodes with all their defs consumed by
52109467b48Spatrick // another set of glued nodes. Register pressure tracking sees this as
52209467b48Spatrick // a single use, so to keep pressure balanced we reduce the defs.
52309467b48Spatrick //
52409467b48Spatrick // We can't tell (without more book-keeping) if this results from
52509467b48Spatrick // glued nodes or duplicate operands. As long as we don't reduce
52609467b48Spatrick // NumRegDefsLeft to zero, we handle the common cases well.
52709467b48Spatrick --OpSU->NumRegDefsLeft;
52809467b48Spatrick }
52909467b48Spatrick }
53009467b48Spatrick }
53109467b48Spatrick }
53209467b48Spatrick }
53309467b48Spatrick
53409467b48Spatrick /// BuildSchedGraph - Build the SUnit graph from the selection dag that we
53509467b48Spatrick /// are input. This SUnit graph is similar to the SelectionDAG, but
53609467b48Spatrick /// excludes nodes that aren't interesting to scheduling, and represents
53709467b48Spatrick /// glued together nodes with a single SUnit.
BuildSchedGraph(AAResults * AA)53809467b48Spatrick void ScheduleDAGSDNodes::BuildSchedGraph(AAResults *AA) {
53909467b48Spatrick // Cluster certain nodes which should be scheduled together.
54009467b48Spatrick ClusterNodes();
54109467b48Spatrick // Populate the SUnits array.
54209467b48Spatrick BuildSchedUnits();
54309467b48Spatrick // Compute all the scheduling dependencies between nodes.
54409467b48Spatrick AddSchedEdges();
54509467b48Spatrick }
54609467b48Spatrick
54709467b48Spatrick // Initialize NumNodeDefs for the current Node's opcode.
InitNodeNumDefs()54809467b48Spatrick void ScheduleDAGSDNodes::RegDefIter::InitNodeNumDefs() {
54909467b48Spatrick // Check for phys reg copy.
55009467b48Spatrick if (!Node)
55109467b48Spatrick return;
55209467b48Spatrick
55309467b48Spatrick if (!Node->isMachineOpcode()) {
55409467b48Spatrick if (Node->getOpcode() == ISD::CopyFromReg)
55509467b48Spatrick NodeNumDefs = 1;
55609467b48Spatrick else
55709467b48Spatrick NodeNumDefs = 0;
55809467b48Spatrick return;
55909467b48Spatrick }
56009467b48Spatrick unsigned POpc = Node->getMachineOpcode();
56109467b48Spatrick if (POpc == TargetOpcode::IMPLICIT_DEF) {
56209467b48Spatrick // No register need be allocated for this.
56309467b48Spatrick NodeNumDefs = 0;
56409467b48Spatrick return;
56509467b48Spatrick }
56609467b48Spatrick if (POpc == TargetOpcode::PATCHPOINT &&
56709467b48Spatrick Node->getValueType(0) == MVT::Other) {
56809467b48Spatrick // PATCHPOINT is defined to have one result, but it might really have none
56909467b48Spatrick // if we're not using CallingConv::AnyReg. Don't mistake the chain for a
57009467b48Spatrick // real definition.
57109467b48Spatrick NodeNumDefs = 0;
57209467b48Spatrick return;
57309467b48Spatrick }
57409467b48Spatrick unsigned NRegDefs = SchedDAG->TII->get(Node->getMachineOpcode()).getNumDefs();
57509467b48Spatrick // Some instructions define regs that are not represented in the selection DAG
57609467b48Spatrick // (e.g. unused flags). See tMOVi8. Make sure we don't access past NumValues.
57709467b48Spatrick NodeNumDefs = std::min(Node->getNumValues(), NRegDefs);
57809467b48Spatrick DefIdx = 0;
57909467b48Spatrick }
58009467b48Spatrick
58109467b48Spatrick // Construct a RegDefIter for this SUnit and find the first valid value.
RegDefIter(const SUnit * SU,const ScheduleDAGSDNodes * SD)58209467b48Spatrick ScheduleDAGSDNodes::RegDefIter::RegDefIter(const SUnit *SU,
58309467b48Spatrick const ScheduleDAGSDNodes *SD)
584*d415bd75Srobert : SchedDAG(SD), Node(SU->getNode()) {
58509467b48Spatrick InitNodeNumDefs();
58609467b48Spatrick Advance();
58709467b48Spatrick }
58809467b48Spatrick
58909467b48Spatrick // Advance to the next valid value defined by the SUnit.
Advance()59009467b48Spatrick void ScheduleDAGSDNodes::RegDefIter::Advance() {
59109467b48Spatrick for (;Node;) { // Visit all glued nodes.
59209467b48Spatrick for (;DefIdx < NodeNumDefs; ++DefIdx) {
59309467b48Spatrick if (!Node->hasAnyUseOfValue(DefIdx))
59409467b48Spatrick continue;
59509467b48Spatrick ValueType = Node->getSimpleValueType(DefIdx);
59609467b48Spatrick ++DefIdx;
59709467b48Spatrick return; // Found a normal regdef.
59809467b48Spatrick }
59909467b48Spatrick Node = Node->getGluedNode();
60009467b48Spatrick if (!Node) {
60109467b48Spatrick return; // No values left to visit.
60209467b48Spatrick }
60309467b48Spatrick InitNodeNumDefs();
60409467b48Spatrick }
60509467b48Spatrick }
60609467b48Spatrick
InitNumRegDefsLeft(SUnit * SU)60709467b48Spatrick void ScheduleDAGSDNodes::InitNumRegDefsLeft(SUnit *SU) {
60809467b48Spatrick assert(SU->NumRegDefsLeft == 0 && "expect a new node");
60909467b48Spatrick for (RegDefIter I(SU, this); I.IsValid(); I.Advance()) {
61009467b48Spatrick assert(SU->NumRegDefsLeft < USHRT_MAX && "overflow is ok but unexpected");
61109467b48Spatrick ++SU->NumRegDefsLeft;
61209467b48Spatrick }
61309467b48Spatrick }
61409467b48Spatrick
computeLatency(SUnit * SU)61509467b48Spatrick void ScheduleDAGSDNodes::computeLatency(SUnit *SU) {
61609467b48Spatrick SDNode *N = SU->getNode();
61709467b48Spatrick
61809467b48Spatrick // TokenFactor operands are considered zero latency, and some schedulers
61909467b48Spatrick // (e.g. Top-Down list) may rely on the fact that operand latency is nonzero
62009467b48Spatrick // whenever node latency is nonzero.
62109467b48Spatrick if (N && N->getOpcode() == ISD::TokenFactor) {
62209467b48Spatrick SU->Latency = 0;
62309467b48Spatrick return;
62409467b48Spatrick }
62509467b48Spatrick
62609467b48Spatrick // Check to see if the scheduler cares about latencies.
62709467b48Spatrick if (forceUnitLatencies()) {
62809467b48Spatrick SU->Latency = 1;
62909467b48Spatrick return;
63009467b48Spatrick }
63109467b48Spatrick
63209467b48Spatrick if (!InstrItins || InstrItins->isEmpty()) {
63309467b48Spatrick if (N && N->isMachineOpcode() &&
63409467b48Spatrick TII->isHighLatencyDef(N->getMachineOpcode()))
63509467b48Spatrick SU->Latency = HighLatencyCycles;
63609467b48Spatrick else
63709467b48Spatrick SU->Latency = 1;
63809467b48Spatrick return;
63909467b48Spatrick }
64009467b48Spatrick
64109467b48Spatrick // Compute the latency for the node. We use the sum of the latencies for
64209467b48Spatrick // all nodes glued together into this SUnit.
64309467b48Spatrick SU->Latency = 0;
64409467b48Spatrick for (SDNode *N = SU->getNode(); N; N = N->getGluedNode())
64509467b48Spatrick if (N->isMachineOpcode())
64609467b48Spatrick SU->Latency += TII->getInstrLatency(InstrItins, N);
64709467b48Spatrick }
64809467b48Spatrick
computeOperandLatency(SDNode * Def,SDNode * Use,unsigned OpIdx,SDep & dep) const64909467b48Spatrick void ScheduleDAGSDNodes::computeOperandLatency(SDNode *Def, SDNode *Use,
65009467b48Spatrick unsigned OpIdx, SDep& dep) const{
65109467b48Spatrick // Check to see if the scheduler cares about latencies.
65209467b48Spatrick if (forceUnitLatencies())
65309467b48Spatrick return;
65409467b48Spatrick
65509467b48Spatrick if (dep.getKind() != SDep::Data)
65609467b48Spatrick return;
65709467b48Spatrick
65809467b48Spatrick unsigned DefIdx = Use->getOperand(OpIdx).getResNo();
65909467b48Spatrick if (Use->isMachineOpcode())
66009467b48Spatrick // Adjust the use operand index by num of defs.
66109467b48Spatrick OpIdx += TII->get(Use->getMachineOpcode()).getNumDefs();
66209467b48Spatrick int Latency = TII->getOperandLatency(InstrItins, Def, DefIdx, Use, OpIdx);
66309467b48Spatrick if (Latency > 1 && Use->getOpcode() == ISD::CopyToReg &&
66409467b48Spatrick !BB->succ_empty()) {
66509467b48Spatrick unsigned Reg = cast<RegisterSDNode>(Use->getOperand(1))->getReg();
66609467b48Spatrick if (Register::isVirtualRegister(Reg))
66709467b48Spatrick // This copy is a liveout value. It is likely coalesced, so reduce the
66809467b48Spatrick // latency so not to penalize the def.
66909467b48Spatrick // FIXME: need target specific adjustment here?
67009467b48Spatrick Latency = (Latency > 1) ? Latency - 1 : 1;
67109467b48Spatrick }
67209467b48Spatrick if (Latency >= 0)
67309467b48Spatrick dep.setLatency(Latency);
67409467b48Spatrick }
67509467b48Spatrick
dumpNode(const SUnit & SU) const67609467b48Spatrick void ScheduleDAGSDNodes::dumpNode(const SUnit &SU) const {
67709467b48Spatrick #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
67809467b48Spatrick dumpNodeName(SU);
67909467b48Spatrick dbgs() << ": ";
68009467b48Spatrick
68109467b48Spatrick if (!SU.getNode()) {
68209467b48Spatrick dbgs() << "PHYS REG COPY\n";
68309467b48Spatrick return;
68409467b48Spatrick }
68509467b48Spatrick
68609467b48Spatrick SU.getNode()->dump(DAG);
68709467b48Spatrick dbgs() << "\n";
68809467b48Spatrick SmallVector<SDNode *, 4> GluedNodes;
68909467b48Spatrick for (SDNode *N = SU.getNode()->getGluedNode(); N; N = N->getGluedNode())
69009467b48Spatrick GluedNodes.push_back(N);
69109467b48Spatrick while (!GluedNodes.empty()) {
69209467b48Spatrick dbgs() << " ";
69309467b48Spatrick GluedNodes.back()->dump(DAG);
69409467b48Spatrick dbgs() << "\n";
69509467b48Spatrick GluedNodes.pop_back();
69609467b48Spatrick }
69709467b48Spatrick #endif
69809467b48Spatrick }
69909467b48Spatrick
dump() const70009467b48Spatrick void ScheduleDAGSDNodes::dump() const {
70109467b48Spatrick #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
70209467b48Spatrick if (EntrySU.getNode() != nullptr)
70309467b48Spatrick dumpNodeAll(EntrySU);
70409467b48Spatrick for (const SUnit &SU : SUnits)
70509467b48Spatrick dumpNodeAll(SU);
70609467b48Spatrick if (ExitSU.getNode() != nullptr)
70709467b48Spatrick dumpNodeAll(ExitSU);
70809467b48Spatrick #endif
70909467b48Spatrick }
71009467b48Spatrick
71109467b48Spatrick #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
dumpSchedule() const71209467b48Spatrick void ScheduleDAGSDNodes::dumpSchedule() const {
713*d415bd75Srobert for (const SUnit *SU : Sequence) {
714*d415bd75Srobert if (SU)
71509467b48Spatrick dumpNode(*SU);
71609467b48Spatrick else
71709467b48Spatrick dbgs() << "**** NOOP ****\n";
71809467b48Spatrick }
71909467b48Spatrick }
72009467b48Spatrick #endif
72109467b48Spatrick
72209467b48Spatrick #ifndef NDEBUG
72309467b48Spatrick /// VerifyScheduledSequence - Verify that all SUnits were scheduled and that
72409467b48Spatrick /// their state is consistent with the nodes listed in Sequence.
72509467b48Spatrick ///
VerifyScheduledSequence(bool isBottomUp)72609467b48Spatrick void ScheduleDAGSDNodes::VerifyScheduledSequence(bool isBottomUp) {
72709467b48Spatrick unsigned ScheduledNodes = ScheduleDAG::VerifyScheduledDAG(isBottomUp);
728*d415bd75Srobert unsigned Noops = llvm::count(Sequence, nullptr);
72909467b48Spatrick assert(Sequence.size() - Noops == ScheduledNodes &&
73009467b48Spatrick "The number of nodes scheduled doesn't match the expected number!");
73109467b48Spatrick }
73209467b48Spatrick #endif // NDEBUG
73309467b48Spatrick
73409467b48Spatrick /// ProcessSDDbgValues - Process SDDbgValues associated with this node.
73509467b48Spatrick static void
ProcessSDDbgValues(SDNode * N,SelectionDAG * DAG,InstrEmitter & Emitter,SmallVectorImpl<std::pair<unsigned,MachineInstr * >> & Orders,DenseMap<SDValue,Register> & VRBaseMap,unsigned Order)73609467b48Spatrick ProcessSDDbgValues(SDNode *N, SelectionDAG *DAG, InstrEmitter &Emitter,
73709467b48Spatrick SmallVectorImpl<std::pair<unsigned, MachineInstr*> > &Orders,
738097a140dSpatrick DenseMap<SDValue, Register> &VRBaseMap, unsigned Order) {
73909467b48Spatrick if (!N->getHasDebugValue())
74009467b48Spatrick return;
74109467b48Spatrick
74273471bf0Spatrick /// Returns true if \p DV has any VReg operand locations which don't exist in
74373471bf0Spatrick /// VRBaseMap.
74473471bf0Spatrick auto HasUnknownVReg = [&VRBaseMap](SDDbgValue *DV) {
745*d415bd75Srobert for (const SDDbgOperand &L : DV->getLocationOps()) {
74673471bf0Spatrick if (L.getKind() == SDDbgOperand::SDNODE &&
74773471bf0Spatrick VRBaseMap.count({L.getSDNode(), L.getResNo()}) == 0)
74873471bf0Spatrick return true;
74973471bf0Spatrick }
75073471bf0Spatrick return false;
75173471bf0Spatrick };
75273471bf0Spatrick
75309467b48Spatrick // Opportunistically insert immediate dbg_value uses, i.e. those with the same
75409467b48Spatrick // source order number as N.
75509467b48Spatrick MachineBasicBlock *BB = Emitter.getBlock();
75609467b48Spatrick MachineBasicBlock::iterator InsertPos = Emitter.getInsertPos();
757*d415bd75Srobert for (auto *DV : DAG->GetDbgValues(N)) {
75809467b48Spatrick if (DV->isEmitted())
75909467b48Spatrick continue;
76009467b48Spatrick unsigned DVOrder = DV->getOrder();
76173471bf0Spatrick if (Order != 0 && DVOrder != Order)
76273471bf0Spatrick continue;
76373471bf0Spatrick // If DV has any VReg location operands which haven't been mapped then
76473471bf0Spatrick // either that node is no longer available or we just haven't visited the
76573471bf0Spatrick // node yet. In the former case we should emit an undef dbg_value, but we
76673471bf0Spatrick // can do it later. And for the latter we'll want to wait until all
76773471bf0Spatrick // dependent nodes have been visited.
76873471bf0Spatrick if (!DV->isInvalidated() && HasUnknownVReg(DV))
76973471bf0Spatrick continue;
77009467b48Spatrick MachineInstr *DbgMI = Emitter.EmitDbgValue(DV, VRBaseMap);
77173471bf0Spatrick if (!DbgMI)
77273471bf0Spatrick continue;
77309467b48Spatrick Orders.push_back({DVOrder, DbgMI});
77409467b48Spatrick BB->insert(InsertPos, DbgMI);
77509467b48Spatrick }
77609467b48Spatrick }
77709467b48Spatrick
77809467b48Spatrick // ProcessSourceNode - Process nodes with source order numbers. These are added
77909467b48Spatrick // to a vector which EmitSchedule uses to determine how to insert dbg_value
78009467b48Spatrick // instructions in the right order.
78109467b48Spatrick static void
ProcessSourceNode(SDNode * N,SelectionDAG * DAG,InstrEmitter & Emitter,DenseMap<SDValue,Register> & VRBaseMap,SmallVectorImpl<std::pair<unsigned,MachineInstr * >> & Orders,SmallSet<Register,8> & Seen,MachineInstr * NewInsn)78209467b48Spatrick ProcessSourceNode(SDNode *N, SelectionDAG *DAG, InstrEmitter &Emitter,
783097a140dSpatrick DenseMap<SDValue, Register> &VRBaseMap,
78409467b48Spatrick SmallVectorImpl<std::pair<unsigned, MachineInstr *>> &Orders,
785097a140dSpatrick SmallSet<Register, 8> &Seen, MachineInstr *NewInsn) {
78609467b48Spatrick unsigned Order = N->getIROrder();
78709467b48Spatrick if (!Order || Seen.count(Order)) {
78809467b48Spatrick // Process any valid SDDbgValues even if node does not have any order
78909467b48Spatrick // assigned.
79009467b48Spatrick ProcessSDDbgValues(N, DAG, Emitter, Orders, VRBaseMap, 0);
79109467b48Spatrick return;
79209467b48Spatrick }
79309467b48Spatrick
79409467b48Spatrick // If a new instruction was generated for this Order number, record it.
79509467b48Spatrick // Otherwise, leave this order number unseen: we will either find later
79609467b48Spatrick // instructions for it, or leave it unseen if there were no instructions at
79709467b48Spatrick // all.
79809467b48Spatrick if (NewInsn) {
79909467b48Spatrick Seen.insert(Order);
80009467b48Spatrick Orders.push_back({Order, NewInsn});
80109467b48Spatrick }
80209467b48Spatrick
80309467b48Spatrick // Even if no instruction was generated, a Value may have become defined via
80409467b48Spatrick // earlier nodes. Try to process them now.
80509467b48Spatrick ProcessSDDbgValues(N, DAG, Emitter, Orders, VRBaseMap, Order);
80609467b48Spatrick }
80709467b48Spatrick
80809467b48Spatrick void ScheduleDAGSDNodes::
EmitPhysRegCopy(SUnit * SU,DenseMap<SUnit *,Register> & VRBaseMap,MachineBasicBlock::iterator InsertPos)809097a140dSpatrick EmitPhysRegCopy(SUnit *SU, DenseMap<SUnit*, Register> &VRBaseMap,
81009467b48Spatrick MachineBasicBlock::iterator InsertPos) {
81173471bf0Spatrick for (const SDep &Pred : SU->Preds) {
81273471bf0Spatrick if (Pred.isCtrl())
81373471bf0Spatrick continue; // ignore chain preds
81473471bf0Spatrick if (Pred.getSUnit()->CopyDstRC) {
81509467b48Spatrick // Copy to physical register.
81673471bf0Spatrick DenseMap<SUnit *, Register>::iterator VRI =
81773471bf0Spatrick VRBaseMap.find(Pred.getSUnit());
81809467b48Spatrick assert(VRI != VRBaseMap.end() && "Node emitted out of order - late");
81909467b48Spatrick // Find the destination physical register.
820097a140dSpatrick Register Reg;
82173471bf0Spatrick for (const SDep &Succ : SU->Succs) {
82273471bf0Spatrick if (Succ.isCtrl())
82373471bf0Spatrick continue; // ignore chain preds
82473471bf0Spatrick if (Succ.getReg()) {
82573471bf0Spatrick Reg = Succ.getReg();
82609467b48Spatrick break;
82709467b48Spatrick }
82809467b48Spatrick }
82909467b48Spatrick BuildMI(*BB, InsertPos, DebugLoc(), TII->get(TargetOpcode::COPY), Reg)
83009467b48Spatrick .addReg(VRI->second);
83109467b48Spatrick } else {
83209467b48Spatrick // Copy from physical register.
83373471bf0Spatrick assert(Pred.getReg() && "Unknown physical register!");
83409467b48Spatrick Register VRBase = MRI.createVirtualRegister(SU->CopyDstRC);
83509467b48Spatrick bool isNew = VRBaseMap.insert(std::make_pair(SU, VRBase)).second;
83609467b48Spatrick (void)isNew; // Silence compiler warning.
83709467b48Spatrick assert(isNew && "Node emitted out of order - early");
83809467b48Spatrick BuildMI(*BB, InsertPos, DebugLoc(), TII->get(TargetOpcode::COPY), VRBase)
83973471bf0Spatrick .addReg(Pred.getReg());
84009467b48Spatrick }
84109467b48Spatrick break;
84209467b48Spatrick }
84309467b48Spatrick }
84409467b48Spatrick
84509467b48Spatrick /// EmitSchedule - Emit the machine code in scheduled order. Return the new
84609467b48Spatrick /// InsertPos and MachineBasicBlock that contains this insertion
84709467b48Spatrick /// point. ScheduleDAGSDNodes holds a BB pointer for convenience, but this does
84809467b48Spatrick /// not necessarily refer to returned BB. The emitter may split blocks.
84909467b48Spatrick MachineBasicBlock *ScheduleDAGSDNodes::
EmitSchedule(MachineBasicBlock::iterator & InsertPos)85009467b48Spatrick EmitSchedule(MachineBasicBlock::iterator &InsertPos) {
85173471bf0Spatrick InstrEmitter Emitter(DAG->getTarget(), BB, InsertPos);
852097a140dSpatrick DenseMap<SDValue, Register> VRBaseMap;
853097a140dSpatrick DenseMap<SUnit*, Register> CopyVRBaseMap;
85409467b48Spatrick SmallVector<std::pair<unsigned, MachineInstr*>, 32> Orders;
855097a140dSpatrick SmallSet<Register, 8> Seen;
85609467b48Spatrick bool HasDbg = DAG->hasDebugValues();
85709467b48Spatrick
85809467b48Spatrick // Emit a node, and determine where its first instruction is for debuginfo.
85909467b48Spatrick // Zero, one, or multiple instructions can be created when emitting a node.
86009467b48Spatrick auto EmitNode =
86109467b48Spatrick [&](SDNode *Node, bool IsClone, bool IsCloned,
862097a140dSpatrick DenseMap<SDValue, Register> &VRBaseMap) -> MachineInstr * {
86309467b48Spatrick // Fetch instruction prior to this, or end() if nonexistant.
86409467b48Spatrick auto GetPrevInsn = [&](MachineBasicBlock::iterator I) {
86509467b48Spatrick if (I == BB->begin())
86609467b48Spatrick return BB->end();
86709467b48Spatrick else
86809467b48Spatrick return std::prev(Emitter.getInsertPos());
86909467b48Spatrick };
87009467b48Spatrick
87109467b48Spatrick MachineBasicBlock::iterator Before = GetPrevInsn(Emitter.getInsertPos());
87209467b48Spatrick Emitter.EmitNode(Node, IsClone, IsCloned, VRBaseMap);
87309467b48Spatrick MachineBasicBlock::iterator After = GetPrevInsn(Emitter.getInsertPos());
87409467b48Spatrick
87509467b48Spatrick // If the iterator did not change, no instructions were inserted.
87609467b48Spatrick if (Before == After)
87709467b48Spatrick return nullptr;
87809467b48Spatrick
87909467b48Spatrick MachineInstr *MI;
88009467b48Spatrick if (Before == BB->end()) {
88109467b48Spatrick // There were no prior instructions; the new ones must start at the
88209467b48Spatrick // beginning of the block.
88309467b48Spatrick MI = &Emitter.getBlock()->instr_front();
88409467b48Spatrick } else {
88509467b48Spatrick // Return first instruction after the pre-existing instructions.
88609467b48Spatrick MI = &*std::next(Before);
88709467b48Spatrick }
88809467b48Spatrick
889097a140dSpatrick if (MI->isCandidateForCallSiteEntry() &&
890097a140dSpatrick DAG->getTarget().Options.EmitCallSiteInfo)
891*d415bd75Srobert MF.addCallArgsForwardingRegs(MI, DAG->getCallSiteInfo(Node));
89209467b48Spatrick
893097a140dSpatrick if (DAG->getNoMergeSiteInfo(Node)) {
894097a140dSpatrick MI->setFlag(MachineInstr::MIFlag::NoMerge);
895097a140dSpatrick }
896097a140dSpatrick
897*d415bd75Srobert if (MDNode *MD = DAG->getPCSections(Node))
898*d415bd75Srobert MI->setPCSections(MF, MD);
899*d415bd75Srobert
90009467b48Spatrick return MI;
90109467b48Spatrick };
90209467b48Spatrick
90309467b48Spatrick // If this is the first BB, emit byval parameter dbg_value's.
90409467b48Spatrick if (HasDbg && BB->getParent()->begin() == MachineFunction::iterator(BB)) {
90509467b48Spatrick SDDbgInfo::DbgIterator PDI = DAG->ByvalParmDbgBegin();
90609467b48Spatrick SDDbgInfo::DbgIterator PDE = DAG->ByvalParmDbgEnd();
90709467b48Spatrick for (; PDI != PDE; ++PDI) {
90809467b48Spatrick MachineInstr *DbgMI= Emitter.EmitDbgValue(*PDI, VRBaseMap);
90909467b48Spatrick if (DbgMI) {
91009467b48Spatrick BB->insert(InsertPos, DbgMI);
91109467b48Spatrick // We re-emit the dbg_value closer to its use, too, after instructions
91209467b48Spatrick // are emitted to the BB.
91309467b48Spatrick (*PDI)->clearIsEmitted();
91409467b48Spatrick }
91509467b48Spatrick }
91609467b48Spatrick }
91709467b48Spatrick
918*d415bd75Srobert for (SUnit *SU : Sequence) {
91909467b48Spatrick if (!SU) {
92009467b48Spatrick // Null SUnit* is a noop.
92109467b48Spatrick TII->insertNoop(*Emitter.getBlock(), InsertPos);
92209467b48Spatrick continue;
92309467b48Spatrick }
92409467b48Spatrick
92509467b48Spatrick // For pre-regalloc scheduling, create instructions corresponding to the
92609467b48Spatrick // SDNode and any glued SDNodes and append them to the block.
92709467b48Spatrick if (!SU->getNode()) {
92809467b48Spatrick // Emit a copy.
92909467b48Spatrick EmitPhysRegCopy(SU, CopyVRBaseMap, InsertPos);
93009467b48Spatrick continue;
93109467b48Spatrick }
93209467b48Spatrick
93309467b48Spatrick SmallVector<SDNode *, 4> GluedNodes;
93409467b48Spatrick for (SDNode *N = SU->getNode()->getGluedNode(); N; N = N->getGluedNode())
93509467b48Spatrick GluedNodes.push_back(N);
93609467b48Spatrick while (!GluedNodes.empty()) {
93709467b48Spatrick SDNode *N = GluedNodes.back();
93809467b48Spatrick auto NewInsn = EmitNode(N, SU->OrigNode != SU, SU->isCloned, VRBaseMap);
93909467b48Spatrick // Remember the source order of the inserted instruction.
94009467b48Spatrick if (HasDbg)
94109467b48Spatrick ProcessSourceNode(N, DAG, Emitter, VRBaseMap, Orders, Seen, NewInsn);
94209467b48Spatrick
94309467b48Spatrick if (MDNode *MD = DAG->getHeapAllocSite(N))
94409467b48Spatrick if (NewInsn && NewInsn->isCall())
94509467b48Spatrick NewInsn->setHeapAllocMarker(MF, MD);
94609467b48Spatrick
94709467b48Spatrick GluedNodes.pop_back();
94809467b48Spatrick }
94909467b48Spatrick auto NewInsn =
95009467b48Spatrick EmitNode(SU->getNode(), SU->OrigNode != SU, SU->isCloned, VRBaseMap);
95109467b48Spatrick // Remember the source order of the inserted instruction.
95209467b48Spatrick if (HasDbg)
95309467b48Spatrick ProcessSourceNode(SU->getNode(), DAG, Emitter, VRBaseMap, Orders, Seen,
95409467b48Spatrick NewInsn);
95509467b48Spatrick
95609467b48Spatrick if (MDNode *MD = DAG->getHeapAllocSite(SU->getNode())) {
95709467b48Spatrick if (NewInsn && NewInsn->isCall())
95809467b48Spatrick NewInsn->setHeapAllocMarker(MF, MD);
95909467b48Spatrick }
96009467b48Spatrick }
96109467b48Spatrick
96209467b48Spatrick // Insert all the dbg_values which have not already been inserted in source
96309467b48Spatrick // order sequence.
96409467b48Spatrick if (HasDbg) {
96509467b48Spatrick MachineBasicBlock::iterator BBBegin = BB->getFirstNonPHI();
96609467b48Spatrick
96709467b48Spatrick // Sort the source order instructions and use the order to insert debug
96809467b48Spatrick // values. Use stable_sort so that DBG_VALUEs are inserted in the same order
96909467b48Spatrick // regardless of the host's implementation fo std::sort.
97009467b48Spatrick llvm::stable_sort(Orders, less_first());
97109467b48Spatrick std::stable_sort(DAG->DbgBegin(), DAG->DbgEnd(),
97209467b48Spatrick [](const SDDbgValue *LHS, const SDDbgValue *RHS) {
97309467b48Spatrick return LHS->getOrder() < RHS->getOrder();
97409467b48Spatrick });
97509467b48Spatrick
97609467b48Spatrick SDDbgInfo::DbgIterator DI = DAG->DbgBegin();
97709467b48Spatrick SDDbgInfo::DbgIterator DE = DAG->DbgEnd();
97809467b48Spatrick // Now emit the rest according to source order.
97909467b48Spatrick unsigned LastOrder = 0;
98009467b48Spatrick for (unsigned i = 0, e = Orders.size(); i != e && DI != DE; ++i) {
98109467b48Spatrick unsigned Order = Orders[i].first;
98209467b48Spatrick MachineInstr *MI = Orders[i].second;
98309467b48Spatrick // Insert all SDDbgValue's whose order(s) are before "Order".
98409467b48Spatrick assert(MI);
98509467b48Spatrick for (; DI != DE; ++DI) {
98609467b48Spatrick if ((*DI)->getOrder() < LastOrder || (*DI)->getOrder() >= Order)
98709467b48Spatrick break;
98809467b48Spatrick if ((*DI)->isEmitted())
98909467b48Spatrick continue;
99009467b48Spatrick
99109467b48Spatrick MachineInstr *DbgMI = Emitter.EmitDbgValue(*DI, VRBaseMap);
99209467b48Spatrick if (DbgMI) {
99309467b48Spatrick if (!LastOrder)
99409467b48Spatrick // Insert to start of the BB (after PHIs).
99509467b48Spatrick BB->insert(BBBegin, DbgMI);
99609467b48Spatrick else {
99709467b48Spatrick // Insert at the instruction, which may be in a different
99809467b48Spatrick // block, if the block was split by a custom inserter.
99909467b48Spatrick MachineBasicBlock::iterator Pos = MI;
100009467b48Spatrick MI->getParent()->insert(Pos, DbgMI);
100109467b48Spatrick }
100209467b48Spatrick }
100309467b48Spatrick }
100409467b48Spatrick LastOrder = Order;
100509467b48Spatrick }
100609467b48Spatrick // Add trailing DbgValue's before the terminator. FIXME: May want to add
100709467b48Spatrick // some of them before one or more conditional branches?
100809467b48Spatrick SmallVector<MachineInstr*, 8> DbgMIs;
100909467b48Spatrick for (; DI != DE; ++DI) {
101009467b48Spatrick if ((*DI)->isEmitted())
101109467b48Spatrick continue;
101209467b48Spatrick assert((*DI)->getOrder() >= LastOrder &&
101309467b48Spatrick "emitting DBG_VALUE out of order");
101409467b48Spatrick if (MachineInstr *DbgMI = Emitter.EmitDbgValue(*DI, VRBaseMap))
101509467b48Spatrick DbgMIs.push_back(DbgMI);
101609467b48Spatrick }
101709467b48Spatrick
101809467b48Spatrick MachineBasicBlock *InsertBB = Emitter.getBlock();
101909467b48Spatrick MachineBasicBlock::iterator Pos = InsertBB->getFirstTerminator();
102009467b48Spatrick InsertBB->insert(Pos, DbgMIs.begin(), DbgMIs.end());
102109467b48Spatrick
102209467b48Spatrick SDDbgInfo::DbgLabelIterator DLI = DAG->DbgLabelBegin();
102309467b48Spatrick SDDbgInfo::DbgLabelIterator DLE = DAG->DbgLabelEnd();
102409467b48Spatrick // Now emit the rest according to source order.
102509467b48Spatrick LastOrder = 0;
102609467b48Spatrick for (const auto &InstrOrder : Orders) {
102709467b48Spatrick unsigned Order = InstrOrder.first;
102809467b48Spatrick MachineInstr *MI = InstrOrder.second;
102909467b48Spatrick if (!MI)
103009467b48Spatrick continue;
103109467b48Spatrick
103209467b48Spatrick // Insert all SDDbgLabel's whose order(s) are before "Order".
103309467b48Spatrick for (; DLI != DLE &&
103409467b48Spatrick (*DLI)->getOrder() >= LastOrder && (*DLI)->getOrder() < Order;
103509467b48Spatrick ++DLI) {
103609467b48Spatrick MachineInstr *DbgMI = Emitter.EmitDbgLabel(*DLI);
103709467b48Spatrick if (DbgMI) {
103809467b48Spatrick if (!LastOrder)
103909467b48Spatrick // Insert to start of the BB (after PHIs).
104009467b48Spatrick BB->insert(BBBegin, DbgMI);
104109467b48Spatrick else {
104209467b48Spatrick // Insert at the instruction, which may be in a different
104309467b48Spatrick // block, if the block was split by a custom inserter.
104409467b48Spatrick MachineBasicBlock::iterator Pos = MI;
104509467b48Spatrick MI->getParent()->insert(Pos, DbgMI);
104609467b48Spatrick }
104709467b48Spatrick }
104809467b48Spatrick }
104909467b48Spatrick if (DLI == DLE)
105009467b48Spatrick break;
105109467b48Spatrick
105209467b48Spatrick LastOrder = Order;
105309467b48Spatrick }
105409467b48Spatrick }
105509467b48Spatrick
105609467b48Spatrick InsertPos = Emitter.getInsertPos();
105773471bf0Spatrick // In some cases, DBG_VALUEs might be inserted after the first terminator,
105873471bf0Spatrick // which results in an invalid MBB. If that happens, move the DBG_VALUEs
105973471bf0Spatrick // before the first terminator.
106073471bf0Spatrick MachineBasicBlock *InsertBB = Emitter.getBlock();
106173471bf0Spatrick auto FirstTerm = InsertBB->getFirstTerminator();
106273471bf0Spatrick if (FirstTerm != InsertBB->end()) {
106373471bf0Spatrick assert(!FirstTerm->isDebugValue() &&
106473471bf0Spatrick "first terminator cannot be a debug value");
106573471bf0Spatrick for (MachineInstr &MI : make_early_inc_range(
106673471bf0Spatrick make_range(std::next(FirstTerm), InsertBB->end()))) {
1067*d415bd75Srobert // Only scan up to insertion point.
1068*d415bd75Srobert if (&MI == InsertPos)
1069*d415bd75Srobert break;
1070*d415bd75Srobert
107173471bf0Spatrick if (!MI.isDebugValue())
107273471bf0Spatrick continue;
107373471bf0Spatrick
107473471bf0Spatrick // The DBG_VALUE was referencing a value produced by a terminator. By
107573471bf0Spatrick // moving the DBG_VALUE, the referenced value also needs invalidating.
107673471bf0Spatrick MI.getOperand(0).ChangeToRegister(0, false);
107773471bf0Spatrick MI.moveBefore(&*FirstTerm);
107873471bf0Spatrick }
107973471bf0Spatrick }
108073471bf0Spatrick return InsertBB;
108109467b48Spatrick }
108209467b48Spatrick
108309467b48Spatrick /// Return the basic block label.
getDAGName() const108409467b48Spatrick std::string ScheduleDAGSDNodes::getDAGName() const {
108509467b48Spatrick return "sunit-dag." + BB->getFullName();
108609467b48Spatrick }
1087