lib/CodeGen/SelectionDAG/ScheduleDAG.cpp

   1 //===-- ScheduleDAG.cpp - Implement a trivial DAG scheduler ---------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by Chris Lattner and is distributed under the
   6 // University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This implements a simple code linearizer for DAGs.  This is not a very good
  11 // way to emit code, but gets working code quickly.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #define DEBUG_TYPE "sched"
  16 #include "llvm/CodeGen/SelectionDAGISel.h"
  17 #include "llvm/CodeGen/SelectionDAG.h"
  18 #include "llvm/Target/TargetMachine.h"
  19 #include "llvm/Target/TargetInstrInfo.h"
  20 #include "llvm/Support/CommandLine.h"
  21 using namespace llvm;
  22
  23 #ifndef _NDEBUG
  24 static cl::opt<bool>
  25 ViewDAGs("view-sched-dags", cl::Hidden,
  26          cl::desc("Pop up a window to show sched dags as they are processed"));
  27 #else
  28 static const bool ViewDAGS = 0;
  29 #endif
  30
  31 namespace {
  32   class SimpleSched {
  33     SelectionDAG &DAG;
  34     MachineBasicBlock *BB;
  35     const TargetMachine &TM;
  36     const TargetInstrInfo &TII;
  37
  38     std::map<SDNode *, unsigned> EmittedOps;
  39   public:
  40     SimpleSched(SelectionDAG &D, MachineBasicBlock *bb)
  41       : DAG(D), BB(bb), TM(D.getTarget()), TII(*TM.getInstrInfo()) {
  42       assert(&TII && "Target doesn't provide instr info?");
  43     }
  44
  45     void Run() {
  46       Emit(DAG.getRoot());
  47     }
  48
  49   private:
  50     unsigned Emit(SDOperand Op);
  51   };
  52 }
  53
  54 unsigned SimpleSched::Emit(SDOperand Op) {
  55   // Check to see if we have already emitted this.  If so, return the value
  56   // already emitted.  Note that if a node has a single use it cannot be
  57   // revisited, so don't bother putting it in the map.
  58   unsigned *OpSlot;
  59   if (Op.Val->hasOneUse()) {
  60     OpSlot = 0;  // No reuse possible.
  61   } else {
  62     std::map<SDNode *, unsigned>::iterator OpI = EmittedOps.lower_bound(Op.Val);
  63     if (OpI != EmittedOps.end() && OpI->first == Op.Val)
  64       return OpI->second + Op.ResNo;
  65     OpSlot = &EmittedOps.insert(OpI, std::make_pair(Op.Val, 0))->second;
  66   }
  67
  68   unsigned ResultReg = 0;
  69   if (Op.isTargetOpcode()) {
  70     unsigned Opc = Op.getTargetOpcode();
  71     const TargetInstrDescriptor &II = TII.get(Opc);
  72
  73     // Target nodes have any register or immediate operands before any chain
  74     // nodes.  Check that the DAG matches the TD files's expectation of #
  75     // operands.
  76     assert((unsigned(II.numOperands) == Op.getNumOperands() ||
  77             // It could be some number of operands followed by a token chain.
  78            (unsigned(II.numOperands)+1 == Op.getNumOperands() &&
  79             Op.getOperand(II.numOperands).getValueType() == MVT::Other)) &&
  80            "#operands for dag node doesn't match .td file!");
  81
  82     // Create the new machine instruction.
  83     MachineInstr *MI = new MachineInstr(Opc, II.numOperands, true, true);
  84
  85     // Add result register values for things that are defined by this
  86     // instruction.
  87     assert(Op.Val->getNumValues() == 1 &&
  88            Op.getValue(0).getValueType() == MVT::Other &&
  89            "Return values not implemented yet");
  90
  91     // Emit all of the operands of this instruction, adding them to the
  92     // instruction as appropriate.
  93     for (unsigned i = 0, e = Op.getNumOperands(); i != e; ++i) {
  94       if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(i))) {
  95         MI->addZeroExtImm64Operand(C->getValue());
  96       } else if (RegisterSDNode*R =dyn_cast<RegisterSDNode>(Op.getOperand(i))) {
  97         MI->addRegOperand(R->getReg(), MachineOperand::Use);
  98       } else {
  99         unsigned R = Emit(Op.getOperand(i));
 100         // Add an operand, unless this corresponds to a chain node.
 101         if (Op.getOperand(i).getValueType() != MVT::Other)
 102           MI->addRegOperand(R, MachineOperand::Use);
 103       }
 104     }
 105
 106     // Now that we have emitted all operands, emit this instruction itself.
 107     BB->insert(BB->end(), MI);
 108   } else {
 109     switch (Op.getOpcode()) {
 110     default: assert(0 &&
 111                     "This target-independent node should have been selected!");
 112     case ISD::EntryToken: break;
 113     }
 114   }
 115
 116   if (OpSlot) *OpSlot = ResultReg;
 117   return ResultReg+Op.ResNo;
 118 }
 119
 120
 121 /// Pick a safe ordering and emit instructions for each target node in the
 122 /// graph.
 123 void SelectionDAGISel::ScheduleAndEmitDAG(SelectionDAG &SD) {
 124   if (ViewDAGs) SD.viewGraph();
 125   SimpleSched(SD, BB).Run();
 126 }