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/CodeGen/PseudoSourceValue.h"
  18 #include "llvm/Target/TargetMachine.h"
  19 #include "llvm/Target/TargetInstrInfo.h"
  20 #include "llvm/Target/TargetRegisterInfo.h"
  21 #include "llvm/Support/Debug.h"
  22 #include "llvm/Support/raw_ostream.h"
  23 #include <map>
  24 using namespace llvm;
  25
  26 ScheduleDAGInstrs::ScheduleDAGInstrs(MachineBasicBlock *bb,
  27                                      const TargetMachine &tm)
  28   : ScheduleDAG(0, bb, tm) {}
  29
  30 void ScheduleDAGInstrs::BuildSchedUnits() {
  31   SUnits.clear();
  32   SUnits.reserve(BB->size());
  33   int Cost = 1; // FIXME
  34
  35   // We build scheduling units by walking a block's instruction list from bottom
  36   // to top.
  37
  38   // Remember where defs and uses of each physical register are as we procede.
  39   SUnit *Defs[TargetRegisterInfo::FirstVirtualRegister] = {};
  40   std::vector<SUnit *> Uses[TargetRegisterInfo::FirstVirtualRegister] = {};
  41
  42   // Remember where unknown loads are after the most recent unknown store
  43   // as we procede.
  44   std::vector<SUnit *> PendingLoads;
  45
  46   // Remember where a generic side-effecting instruction is as we procede. If
  47   // ChainMMO is null, this is assumed to have arbitrary side-effects. If
  48   // ChainMMO is non-null, then Chain makes only a single memory reference.
  49   SUnit *Chain = 0;
  50   MachineMemOperand *ChainMMO = 0;
  51
  52   // Memory references to specific known memory locations are tracked so that
  53   // they can be given more precise dependencies.
  54   std::map<const Value *, SUnit *> MemDefs;
  55   std::map<const Value *, std::vector<SUnit *> > MemUses;
  56
  57   // Terminators can perform control transfers, we we need to make sure that
  58   // all the work of the block is done before the terminator.
  59   SUnit *Terminator = 0;
  60
  61   for (MachineBasicBlock::iterator MII = BB->end(), MIE = BB->begin();
  62        MII != MIE; --MII) {
  63     MachineInstr *MI = prior(MII);
  64     SUnit *SU = NewSUnit(MI);
  65
  66     // Add register-based dependencies (data, anti, and output).
  67     for (unsigned j = 0, n = MI->getNumOperands(); j != n; ++j) {
  68       const MachineOperand &MO = MI->getOperand(j);
  69       if (!MO.isReg()) continue;
  70       unsigned Reg = MO.getReg();
  71       if (Reg == 0) continue;
  72
  73       assert(TRI->isPhysicalRegister(Reg) && "Virtual register encountered!");
  74       std::vector<SUnit *> &UseList = Uses[Reg];
  75       SUnit *&Def = Defs[Reg];
  76       // Optionally add output and anti dependencies.
  77       if (Def && Def != SU)
  78         Def->addPred(SU, /*isCtrl=*/true, /*isArtificial=*/false,
  79                      /*PhyReg=*/Reg, Cost, /*isAntiDep=*/MO.isUse());
  80       for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) {
  81         SUnit *&Def = Defs[*Alias];
  82         if (Def && Def != SU)
  83           Def->addPred(SU, /*isCtrl=*/true, /*isArtificial=*/false,
  84                        /*PhyReg=*/*Alias, Cost, /*isAntiDep=*/MO.isUse());
  85       }
  86
  87       if (MO.isDef()) {
  88         // Add any data dependencies.
  89         for (unsigned i = 0, e = UseList.size(); i != e; ++i)
  90           if (UseList[i] != SU)
  91             UseList[i]->addPred(SU, /*isCtrl=*/false, /*isArtificial=*/false,
  92                                 /*PhysReg=*/Reg, Cost);
  93         for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) {
  94           std::vector<SUnit *> &UseList = Uses[*Alias];
  95           for (unsigned i = 0, e = UseList.size(); i != e; ++i)
  96             if (UseList[i] != SU)
  97               UseList[i]->addPred(SU, /*isCtrl=*/false, /*isArtificial=*/false,
  98                                   /*PhysReg=*/*Alias, Cost);
  99         }
 100
 101         UseList.clear();
 102         Def = SU;
 103       } else {
 104         UseList.push_back(SU);
 105       }
 106     }
 107
 108     // Add chain dependencies.
 109     // Note that isStoreToStackSlot and isLoadFromStackSLot are not usable
 110     // after stack slots are lowered to actual addresses.
 111     // TODO: Use an AliasAnalysis and do real alias-analysis queries, and
 112     // produce more precise dependence information.
 113     const TargetInstrDesc &TID = MI->getDesc();
 114     if (TID.isCall() || TID.isReturn() || TID.isBranch() ||
 115         TID.hasUnmodeledSideEffects()) {
 116     new_chain:
 117       // This is the conservative case. Add dependencies on all memory references.
 118       if (Chain)
 119         Chain->addPred(SU, /*isCtrl=*/true, /*isArtificial=*/false);
 120       Chain = SU;
 121       for (unsigned k = 0, m = PendingLoads.size(); k != m; ++k)
 122         PendingLoads[k]->addPred(SU, /*isCtrl=*/true, /*isArtificial=*/false);
 123       PendingLoads.clear();
 124       for (std::map<const Value *, SUnit *>::iterator I = MemDefs.begin(),
 125            E = MemDefs.end(); I != E; ++I) {
 126         I->second->addPred(SU, /*isCtrl=*/true, /*isArtificial=*/false);
 127         I->second = SU;
 128       }
 129       for (std::map<const Value *, std::vector<SUnit *> >::iterator I =
 130            MemUses.begin(), E = MemUses.end(); I != E; ++I) {
 131         for (unsigned i = 0, e = I->second.size(); i != e; ++i)
 132           I->second[i]->addPred(SU, /*isCtrl=*/true, /*isArtificial=*/false);
 133         I->second.clear();
 134       }
 135       // See if it is known to just have a single memory reference.
 136       MachineInstr *ChainMI = Chain->getInstr();
 137       const TargetInstrDesc &ChainTID = ChainMI->getDesc();
 138       if (!ChainTID.isCall() && !ChainTID.isReturn() && !ChainTID.isBranch() &&
 139           !ChainTID.hasUnmodeledSideEffects() &&
 140           ChainMI->hasOneMemOperand() &&
 141           !ChainMI->memoperands_begin()->isVolatile() &&
 142           ChainMI->memoperands_begin()->getValue())
 143         // We know that the Chain accesses one specific memory location.
 144         ChainMMO = &*ChainMI->memoperands_begin();
 145       else
 146         // Unknown memory accesses. Assume the worst.
 147         ChainMMO = 0;
 148     } else if (TID.mayStore()) {
 149       if (MI->hasOneMemOperand() &&
 150           MI->memoperands_begin()->getValue() &&
 151           !MI->memoperands_begin()->isVolatile() &&
 152           isa<PseudoSourceValue>(MI->memoperands_begin()->getValue())) {
 153         // A store to a specific PseudoSourceValue. Add precise dependencies.
 154         const Value *V = MI->memoperands_begin()->getValue();
 155         // Handle the def in MemDefs, if there is one.
 156         std::map<const Value *, SUnit *>::iterator I = MemDefs.find(V);
 157         if (I != MemDefs.end()) {
 158           I->second->addPred(SU, /*isCtrl=*/true, /*isArtificial=*/false);
 159           I->second = SU;
 160         } else {
 161           MemDefs[V] = SU;
 162         }
 163         // Handle the uses in MemUses, if there are any.
 164         std::map<const Value *, std::vector<SUnit *> >::iterator J = MemUses.find(V);
 165         if (J != MemUses.end()) {
 166           for (unsigned i = 0, e = J->second.size(); i != e; ++i)
 167             J->second[i]->addPred(SU, /*isCtrl=*/true, /*isArtificial=*/false);
 168           J->second.clear();
 169         }
 170         // Add a general dependence too, if needed.
 171         if (Chain)
 172           Chain->addPred(SU, /*isCtrl=*/true, /*isArtificial=*/false);
 173       } else
 174         // Treat all other stores conservatively.
 175         goto new_chain;
 176     } else if (TID.mayLoad()) {
 177       if (TII->isInvariantLoad(MI)) {
 178         // Invariant load, no chain dependencies needed!
 179       } else if (MI->hasOneMemOperand() &&
 180                  MI->memoperands_begin()->getValue() &&
 181                  !MI->memoperands_begin()->isVolatile() &&
 182                  isa<PseudoSourceValue>(MI->memoperands_begin()->getValue())) {
 183         // A load from a specific PseudoSourceValue. Add precise dependencies.
 184         const Value *V = MI->memoperands_begin()->getValue();
 185         std::map<const Value *, SUnit *>::iterator I = MemDefs.find(V);
 186         if (I != MemDefs.end())
 187           I->second->addPred(SU, /*isCtrl=*/true, /*isArtificial=*/false);
 188         MemUses[V].push_back(SU);
 189
 190         // Add a general dependence too, if needed.
 191         if (Chain && (!ChainMMO ||
 192                       (ChainMMO->isStore() || ChainMMO->isVolatile())))
 193           Chain->addPred(SU, /*isCtrl=*/true, /*isArtificial=*/false);
 194       } else if (MI->hasVolatileMemoryRef()) {
 195         // Treat volatile loads conservatively. Note that this includes
 196         // cases where memoperand information is unavailable.
 197         goto new_chain;
 198       } else {
 199         // A normal load. Just depend on the general chain.
 200         if (Chain)
 201           Chain->addPred(SU, /*isCtrl=*/true, /*isArtificial=*/false);
 202         PendingLoads.push_back(SU);
 203       }
 204     }
 205
 206     // Add chain edges from the terminator to ensure that all the work of the block is
 207     // completed before any control transfers.
 208     if (Terminator && SU->Succs.empty())
 209       Terminator->addPred(SU, /*isCtrl=*/true, /*isArtificial=*/false);
 210     if (TID.isTerminator() || MI->isLabel())
 211       Terminator = SU;
 212
 213     // Assign the Latency field of SU using target-provided information.
 214     ComputeLatency(SU);
 215   }
 216 }
 217
 218 void ScheduleDAGInstrs::ComputeLatency(SUnit *SU) {
 219   const InstrItineraryData &InstrItins = TM.getInstrItineraryData();
 220
 221   // Compute the latency for the node.  We use the sum of the latencies for
 222   // all nodes flagged together into this SUnit.
 223   SU->Latency =
 224     InstrItins.getLatency(SU->getInstr()->getDesc().getSchedClass());
 225 }
 226
 227 void ScheduleDAGInstrs::dumpNode(const SUnit *SU) const {
 228   SU->getInstr()->dump();
 229 }
 230
 231 std::string ScheduleDAGInstrs::getGraphNodeLabel(const SUnit *SU) const {
 232   std::string s;
 233   raw_string_ostream oss(s);
 234   SU->getInstr()->print(oss);
 235   return oss.str();
 236 }
 237
 238 // EmitSchedule - Emit the machine code in scheduled order.
 239 MachineBasicBlock *ScheduleDAGInstrs::EmitSchedule() {
 240   // For MachineInstr-based scheduling, we're rescheduling the instructions in
 241   // the block, so start by removing them from the block.
 242   while (!BB->empty())
 243     BB->remove(BB->begin());
 244
 245   for (unsigned i = 0, e = Sequence.size(); i != e; i++) {
 246     SUnit *SU = Sequence[i];
 247     if (!SU) {
 248       // Null SUnit* is a noop.
 249       EmitNoop();
 250       continue;
 251     }
 252
 253     BB->push_back(SU->getInstr());
 254   }
 255
 256   return BB;
 257 }