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 using namespace llvm;
  21
  22 namespace {
  23   class SimpleSched {
  24     SelectionDAG &DAG;
  25     MachineBasicBlock *BB;
  26     const TargetMachine &TM;
  27     const TargetInstrInfo &TII;
  28
  29     std::map<SDNode *, unsigned> EmittedOps;
  30   public:
  31     SimpleSched(SelectionDAG &D, MachineBasicBlock *bb)
  32       : DAG(D), BB(bb), TM(D.getTarget()), TII(*TM.getInstrInfo()) {
  33       assert(&TII && "Target doesn't provide instr info?");
  34     }
  35
  36     void Run() {
  37       Emit(DAG.getRoot());
  38     }
  39
  40   private:
  41     unsigned Emit(SDOperand Op);
  42   };
  43 }
  44
  45 unsigned SimpleSched::Emit(SDOperand Op) {
  46   // Check to see if we have already emitted this.  If so, return the value
  47   // already emitted.  Note that if a node has a single use it cannot be
  48   // revisited, so don't bother putting it in the map.
  49   unsigned *OpSlot;
  50   if (Op.Val->hasOneUse()) {
  51     OpSlot = 0;  // No reuse possible.
  52   } else {
  53     std::map<SDNode *, unsigned>::iterator OpI = EmittedOps.lower_bound(Op.Val);
  54     if (OpI != EmittedOps.end() && OpI->first == Op.Val)
  55       return OpI->second + Op.ResNo;
  56     OpSlot = &EmittedOps.insert(OpI, std::make_pair(Op.Val, 0))->second;
  57   }
  58
  59   unsigned ResultReg = 0;
  60   if (Op.isTargetOpcode()) {
  61     unsigned Opc = Op.getTargetOpcode();
  62     const TargetInstrDescriptor &II = TII.get(Opc);
  63
  64     // Target nodes have any register or immediate operands before any chain
  65     // nodes.  Check that the DAG matches the TD files's expectation of #
  66     // operands.
  67     assert((unsigned(II.numOperands) == Op.getNumOperands() ||
  68             // It could be some number of operands followed by a token chain.
  69            (unsigned(II.numOperands)+1 == Op.getNumOperands() &&
  70             Op.getOperand(II.numOperands).getValueType() == MVT::Other)) &&
  71            "#operands for dag node doesn't match .td file!");
  72
  73     // Create the new machine instruction.
  74     MachineInstr *MI = new MachineInstr(Opc, II.numOperands, true, true);
  75
  76     // Add result register values for things that are defined by this
  77     // instruction.
  78     assert(Op.Val->getNumValues() == 1 &&
  79            Op.getValue(0).getValueType() == MVT::Other &&
  80            "Return values not implemented yet");
  81
  82     // Emit all of the operands of this instruction, adding them to the
  83     // instruction as appropriate.
  84     for (unsigned i = 0, e = Op.getNumOperands(); i != e; ++i) {
  85       if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(i))) {
  86         MI->addZeroExtImm64Operand(C->getValue());
  87       } else if (RegisterSDNode*R =dyn_cast<RegisterSDNode>(Op.getOperand(i))) {
  88         MI->addRegOperand(R->getReg(), MachineOperand::Use);
  89       } else {
  90         unsigned R = Emit(Op.getOperand(i));
  91         // Add an operand, unless this corresponds to a chain node.
  92         if (Op.getOperand(i).getValueType() != MVT::Other)
  93           MI->addRegOperand(R, MachineOperand::Use);
  94       }
  95     }
  96
  97     // Now that we have emitted all operands, emit this instruction itself.
  98     BB->insert(BB->end(), MI);
  99   } else {
 100     switch (Op.getOpcode()) {
 101     default: assert(0 &&
 102                     "This target-independent node should have been selected!");
 103     case ISD::EntryToken: break;
 104     }
 105   }
 106
 107   if (OpSlot) *OpSlot = ResultReg;
 108   return ResultReg+Op.ResNo;
 109 }
 110
 111
 112 /// Pick a safe ordering and emit instructions for each target node in the
 113 /// graph.
 114 void SelectionDAGISel::ScheduleAndEmitDAG(SelectionDAG &SD) {
 115   SimpleSched(SD, BB).Run();
 116 }