ScheduleDAGInstrs.cpp revision fc626b62b877beec1cc3c0289eb794f28614e23f 
1//===---- ScheduleDAG.cpp - Implement the ScheduleDAG 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 "sched-instrs"
16#include "llvm/CodeGen/ScheduleDAGInstrs.h"
17#include "llvm/Target/TargetMachine.h"
18#include "llvm/Target/TargetInstrInfo.h"
19#include "llvm/Target/TargetRegisterInfo.h"
20#include "llvm/Support/Debug.h"
21#include "llvm/Support/raw_ostream.h"
22using namespace llvm;
23
24ScheduleDAGInstrs::ScheduleDAGInstrs(MachineBasicBlock *bb,
25                                     const TargetMachine &tm)
26  : ScheduleDAG(0, bb, tm) {}
27
28void ScheduleDAGInstrs::BuildSchedUnits() {
29  SUnits.clear();
30  SUnits.reserve(BB->size());
31
32  std::vector<SUnit *> PendingLoads;
33  SUnit *Terminator = 0;
34  SUnit *Chain = 0;
35  SUnit *Defs[TargetRegisterInfo::FirstVirtualRegister] = {};
36  std::vector<SUnit *> Uses[TargetRegisterInfo::FirstVirtualRegister] = {};
37  int Cost = 1; // FIXME
38
39  for (MachineBasicBlock::iterator MII = BB->end(), MIE = BB->begin();
40       MII != MIE; --MII) {
41    MachineInstr *MI = prior(MII);
42    SUnit *SU = NewSUnit(MI);
43
44    for (unsigned j = 0, n = MI->getNumOperands(); j != n; ++j) {
45      const MachineOperand &MO = MI->getOperand(j);
46      if (!MO.isReg()) continue;
47      unsigned Reg = MO.getReg();
48      if (Reg == 0) continue;
49
50      assert(TRI->isPhysicalRegister(Reg) && "Virtual register encountered!");
51      std::vector<SUnit *> &UseList = Uses[Reg];
52      SUnit *&Def = Defs[Reg];
53      // Optionally add output and anti dependencies.
54      if (Def && Def != SU)
55        Def->addPred(SU, /*isCtrl=*/true, /*isArtificial=*/false,
56                     /*PhyReg=*/Reg, Cost, /*isAntiDep=*/MO.isUse());
57      for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) {
58        SUnit *&Def = Defs[*Alias];
59        if (Def && Def != SU)
60          Def->addPred(SU, /*isCtrl=*/true, /*isArtificial=*/false,
61                       /*PhyReg=*/*Alias, Cost);
62      }
63
64      if (MO.isDef()) {
65        // Add any data dependencies.
66        for (unsigned i = 0, e = UseList.size(); i != e; ++i)
67          if (UseList[i] != SU)
68            UseList[i]->addPred(SU, /*isCtrl=*/false, /*isArtificial=*/false,
69                                /*PhysReg=*/Reg, Cost);
70        for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) {
71          std::vector<SUnit *> &UseList = Uses[*Alias];
72          for (unsigned i = 0, e = UseList.size(); i != e; ++i)
73            if (UseList[i] != SU)
74              UseList[i]->addPred(SU, /*isCtrl=*/false, /*isArtificial=*/false,
75                                  /*PhysReg=*/*Alias, Cost);
76        }
77
78        UseList.clear();
79        Def = SU;
80      } else {
81        UseList.push_back(SU);
82      }
83    }
84    bool False = false;
85    bool True = true;
86    if (!MI->isSafeToMove(TII, False)) {
87      if (Chain)
88        Chain->addPred(SU, /*isCtrl=*/false, /*isArtificial=*/false);
89      for (unsigned k = 0, m = PendingLoads.size(); k != m; ++k)
90        PendingLoads[k]->addPred(SU, /*isCtrl=*/false, /*isArtificial=*/false);
91      PendingLoads.clear();
92      Chain = SU;
93    } else if (!MI->isSafeToMove(TII, True)) {
94      if (Chain)
95        Chain->addPred(SU, /*isCtrl=*/false, /*isArtificial=*/false);
96      PendingLoads.push_back(SU);
97    }
98    if (Terminator && SU->Succs.empty())
99      Terminator->addPred(SU, /*isCtrl=*/false, /*isArtificial=*/false);
100    if (MI->getDesc().isTerminator() || MI->isLabel())
101      Terminator = SU;
102
103    // Assign the Latency field of SU using target-provided information.
104    ComputeLatency(SU);
105  }
106}
107
108void ScheduleDAGInstrs::ComputeLatency(SUnit *SU) {
109  const InstrItineraryData &InstrItins = TM.getInstrItineraryData();
110
111  // Compute the latency for the node.  We use the sum of the latencies for
112  // all nodes flagged together into this SUnit.
113  SU->Latency =
114    InstrItins.getLatency(SU->getInstr()->getDesc().getSchedClass());
115}
116
117void ScheduleDAGInstrs::dumpNode(const SUnit *SU) const {
118  SU->getInstr()->dump();
119}
120
121std::string ScheduleDAGInstrs::getGraphNodeLabel(const SUnit *SU) const {
122  std::string s;
123  raw_string_ostream oss(s);
124  SU->getInstr()->print(oss);
125  return oss.str();
126}
127
128// EmitSchedule - Emit the machine code in scheduled order.
129MachineBasicBlock *ScheduleDAGInstrs::EmitSchedule() {
130  // For MachineInstr-based scheduling, we're rescheduling the instructions in
131  // the block, so start by removing them from the block.
132  while (!BB->empty())
133    BB->remove(BB->begin());
134
135  for (unsigned i = 0, e = Sequence.size(); i != e; i++) {
136    SUnit *SU = Sequence[i];
137    if (!SU) {
138      // Null SUnit* is a noop.
139      EmitNoop();
140      continue;
141    }
142
143    BB->push_back(SU->getInstr());
144  }
145
146  return BB;
147}
148