lib/CodeGen/ScheduleDAGInstrs.cpp

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