lib/CodeGen/SelectionDAG/ScheduleDAGSDNodes.cpp

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