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/MachineFunction.h"
  17 #include "llvm/CodeGen/SelectionDAGISel.h"
  18 #include "llvm/CodeGen/SelectionDAG.h"
  19 #include "llvm/CodeGen/SSARegMap.h"
  20 #include "llvm/Target/TargetMachine.h"
  21 #include "llvm/Target/TargetInstrInfo.h"
  22 #include "llvm/Support/CommandLine.h"
  23 using namespace llvm;
  24
  25 #ifndef _NDEBUG
  26 static cl::opt<bool>
  27 ViewDAGs("view-sched-dags", cl::Hidden,
  28          cl::desc("Pop up a window to show sched dags as they are processed"));
  29 #else
  30 static const bool ViewDAGS = 0;
  31 #endif
  32
  33 namespace {
  34   class SimpleSched {
  35     SelectionDAG &DAG;
  36     MachineBasicBlock *BB;
  37     const TargetMachine &TM;
  38     const TargetInstrInfo &TII;
  39     SSARegMap *RegMap;
  40
  41     std::map<SDNode *, unsigned> EmittedOps;
  42   public:
  43     SimpleSched(SelectionDAG &D, MachineBasicBlock *bb)
  44       : DAG(D), BB(bb), TM(D.getTarget()), TII(*TM.getInstrInfo()),
  45         RegMap(BB->getParent()->getSSARegMap()) {
  46       assert(&TII && "Target doesn't provide instr info?");
  47     }
  48
  49     void Run() {
  50       Emit(DAG.getRoot());
  51     }
  52
  53   private:
  54     unsigned Emit(SDOperand Op);
  55   };
  56 }
  57
  58 unsigned SimpleSched::Emit(SDOperand Op) {
  59   // Check to see if we have already emitted this.  If so, return the value
  60   // already emitted.  Note that if a node has a single use it cannot be
  61   // revisited, so don't bother putting it in the map.
  62   unsigned *OpSlot;
  63   if (Op.Val->hasOneUse()) {
  64     OpSlot = 0;  // No reuse possible.
  65   } else {
  66     std::map<SDNode *, unsigned>::iterator OpI = EmittedOps.lower_bound(Op.Val);
  67     if (OpI != EmittedOps.end() && OpI->first == Op.Val)
  68       return OpI->second + Op.ResNo;
  69     OpSlot = &EmittedOps.insert(OpI, std::make_pair(Op.Val, 0))->second;
  70   }
  71
  72   unsigned ResultReg = 0;
  73   if (Op.isTargetOpcode()) {
  74     unsigned Opc = Op.getTargetOpcode();
  75     const TargetInstrDescriptor &II = TII.get(Opc);
  76
  77     // Target nodes have any register or immediate operands before any chain
  78     // nodes.  Check that the DAG matches the TD files's expectation of #
  79     // operands.
  80     unsigned NumResults = Op.Val->getNumValues();
  81     if (NumResults && Op.getOperand(NumResults-1).getValueType() == MVT::Other)
  82       --NumResults;
  83 #ifndef _NDEBUG
  84     unsigned Operands = Op.getNumOperands();
  85     if (Operands && Op.getOperand(Operands-1).getValueType() == MVT::Other)
  86       --Operands;
  87     assert(unsigned(II.numOperands) == Operands+NumResults &&
  88            "#operands for dag node doesn't match .td file!");
  89 #endif
  90
  91     // Create the new machine instruction.
  92     MachineInstr *MI = new MachineInstr(Opc, II.numOperands, true, true);
  93
  94     // Add result register values for things that are defined by this
  95     // instruction.
  96     if (NumResults) {
  97       // Create the result registers for this node and add the result regs to
  98       // the machine instruction.
  99       const TargetOperandInfo *OpInfo = II.OpInfo;
 100       ResultReg = RegMap->createVirtualRegister(OpInfo[0].RegClass);
 101       MI->addRegOperand(ResultReg, MachineOperand::Def);
 102       for (unsigned i = 1; i != NumResults; ++i) {
 103         assert(OpInfo[i].RegClass && "Isn't a register operand!");
 104         MI->addRegOperand(RegMap->createVirtualRegister(OpInfo[0].RegClass),
 105                           MachineOperand::Def);
 106       }
 107     }
 108
 109     // Emit all of the operands of this instruction, adding them to the
 110     // instruction as appropriate.
 111     for (unsigned i = 0, e = Op.getNumOperands(); i != e; ++i) {
 112       if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(i))) {
 113         MI->addZeroExtImm64Operand(C->getValue());
 114       } else if (RegisterSDNode*R =dyn_cast<RegisterSDNode>(Op.getOperand(i))) {
 115         MI->addRegOperand(R->getReg(), MachineOperand::Use);
 116       } else {
 117         unsigned R = Emit(Op.getOperand(i));
 118         // Add an operand, unless this corresponds to a chain node.
 119         if (Op.getOperand(i).getValueType() != MVT::Other)
 120           MI->addRegOperand(R, MachineOperand::Use);
 121       }
 122     }
 123
 124     // Now that we have emitted all operands, emit this instruction itself.
 125     BB->insert(BB->end(), MI);
 126   } else {
 127     switch (Op.getOpcode()) {
 128     default:
 129       Op.Val->dump();
 130       assert(0 && "This target-independent node should have been selected!");
 131     case ISD::EntryToken: break;
 132     case ISD::CopyToReg: {
 133       unsigned Val = Emit(Op.getOperand(2));
 134       // FIXME: DO THE COPY NOW.
 135       break;
 136     }
 137     }
 138   }
 139
 140   if (OpSlot) *OpSlot = ResultReg;
 141   return ResultReg+Op.ResNo;
 142 }
 143
 144
 145 /// Pick a safe ordering and emit instructions for each target node in the
 146 /// graph.
 147 void SelectionDAGISel::ScheduleAndEmitDAG(SelectionDAG &SD) {
 148   if (ViewDAGs) SD.viewGraph();
 149   SimpleSched(SD, BB).Run();
 150 }