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