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