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 #ifndef _NDEBUG
  77     unsigned Operands = Op.getNumOperands();
  78     if (Operands && Op.getOperand(Operands-1).getValueType() == MVT::Other)
  79       --Operands;
  80     unsigned Results = Op.Val->getNumValues();
  81     if (Results && Op.getOperand(Results-1).getValueType() == MVT::Other)
  82       --Results;
  83     assert(unsigned(II.numOperands) == Operands+Results &&
  84            "#operands for dag node doesn't match .td file!");
  85 #endif
  86
  87     // Create the new machine instruction.
  88     MachineInstr *MI = new MachineInstr(Opc, II.numOperands, true, true);
  89
  90     // Add result register values for things that are defined by this
  91     // instruction.
  92     assert(Op.Val->getNumValues() == 1 &&
  93            Op.getValue(0).getValueType() == MVT::Other &&
  94            "Return values not implemented yet");
  95
  96     // Emit all of the operands of this instruction, adding them to the
  97     // instruction as appropriate.
  98     for (unsigned i = 0, e = Op.getNumOperands(); i != e; ++i) {
  99       if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(i))) {
 100         MI->addZeroExtImm64Operand(C->getValue());
 101       } else if (RegisterSDNode*R =dyn_cast<RegisterSDNode>(Op.getOperand(i))) {
 102         MI->addRegOperand(R->getReg(), MachineOperand::Use);
 103       } else {
 104         unsigned R = Emit(Op.getOperand(i));
 105         // Add an operand, unless this corresponds to a chain node.
 106         if (Op.getOperand(i).getValueType() != MVT::Other)
 107           MI->addRegOperand(R, MachineOperand::Use);
 108       }
 109     }
 110
 111     // Now that we have emitted all operands, emit this instruction itself.
 112     BB->insert(BB->end(), MI);
 113   } else {
 114     switch (Op.getOpcode()) {
 115     default:
 116       Op.Val->dump();
 117       assert(0 && "This target-independent node should have been selected!");
 118     case ISD::EntryToken: break;
 119     case ISD::CopyToReg: {
 120       unsigned Val = Emit(Op.getOperand(2));
 121       // FIXME: DO THE COPY NOW.
 122       break;
 123     }
 124     }
 125   }
 126
 127   if (OpSlot) *OpSlot = ResultReg;
 128   return ResultReg+Op.ResNo;
 129 }
 130
 131
 132 /// Pick a safe ordering and emit instructions for each target node in the
 133 /// graph.
 134 void SelectionDAGISel::ScheduleAndEmitDAG(SelectionDAG &SD) {
 135   if (ViewDAGs) SD.viewGraph();
 136   SimpleSched(SD, BB).Run();
 137 }