lib/CodeGen/ScheduleDAGInstrs.cpp

   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"
  22 using namespace llvm;
  23
  24 ScheduleDAGInstrs::ScheduleDAGInstrs(MachineBasicBlock *bb,
  25                                      const TargetMachine &tm)
  26   : ScheduleDAG(0, bb, tm) {}
  27
  28 void 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 dependences.
  54       if (Def && Def != SU)
  55         Def->addPred(SU, /*isCtrl=*/true, /*isSpecial=*/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, /*isSpecial=*/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, /*isSpecial=*/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, /*isSpecial=*/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, /*isSpecial=*/false);
  89       for (unsigned k = 0, m = PendingLoads.size(); k != m; ++k)
  90         PendingLoads[k]->addPred(SU, /*isCtrl=*/false, /*isSpecial=*/false);
  91       PendingLoads.clear();
  92       Chain = SU;
  93     } else if (!MI->isSafeToMove(TII, True)) {
  94       if (Chain)
  95         Chain->addPred(SU, /*isCtrl=*/false, /*isSpecial=*/false);
  96       PendingLoads.push_back(SU);
  97     }
  98     if (Terminator && SU->Succs.empty())
  99       Terminator->addPred(SU, /*isCtrl=*/false, /*isSpecial=*/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
 108 void 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
 117 void ScheduleDAGInstrs::dumpNode(const SUnit *SU) const {
 118   SU->getInstr()->dump();
 119 }
 120
 121 std::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.
 129 MachineBasicBlock *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 }