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     const MRegisterInfo &MRI;
  40     SSARegMap *RegMap;
  41
  42     std::map<SDNode *, unsigned> EmittedOps;
  43   public:
  44     SimpleSched(SelectionDAG &D, MachineBasicBlock *bb)
  45       : DAG(D), BB(bb), TM(D.getTarget()), TII(*TM.getInstrInfo()),
  46         MRI(*TM.getRegisterInfo()), RegMap(BB->getParent()->getSSARegMap()) {
  47       assert(&TII && "Target doesn't provide instr info?");
  48       assert(&MRI && "Target doesn't provide register info?");
  49     }
  50
  51     void Run() {
  52       Emit(DAG.getRoot());
  53     }
  54
  55   private:
  56     unsigned Emit(SDOperand Op);
  57   };
  58 }
  59
  60 unsigned SimpleSched::Emit(SDOperand Op) {
  61   // Check to see if we have already emitted this.  If so, return the value
  62   // already emitted.  Note that if a node has a single use it cannot be
  63   // revisited, so don't bother putting it in the map.
  64   unsigned *OpSlot;
  65   if (Op.Val->hasOneUse()) {
  66     OpSlot = 0;  // No reuse possible.
  67   } else {
  68     std::map<SDNode *, unsigned>::iterator OpI = EmittedOps.lower_bound(Op.Val);
  69     if (OpI != EmittedOps.end() && OpI->first == Op.Val)
  70       return OpI->second + Op.ResNo;
  71     OpSlot = &EmittedOps.insert(OpI, std::make_pair(Op.Val, 0))->second;
  72   }
  73
  74   unsigned ResultReg = 0;
  75   if (Op.isTargetOpcode()) {
  76     unsigned Opc = Op.getTargetOpcode();
  77     const TargetInstrDescriptor &II = TII.get(Opc);
  78
  79     // Target nodes have any register or immediate operands before any chain
  80     // nodes.  Check that the DAG matches the TD files's expectation of #
  81     // operands.
  82     unsigned NumResults = Op.Val->getNumValues();
  83     if (NumResults && Op.Val->getValueType(NumResults-1) == MVT::Other)
  84       --NumResults;
  85 #ifndef _NDEBUG
  86     unsigned Operands = Op.getNumOperands();
  87     if (Operands && Op.getOperand(Operands-1).getValueType() == MVT::Other)
  88       --Operands;
  89     assert(unsigned(II.numOperands) == Operands+NumResults &&
  90            "#operands for dag node doesn't match .td file!");
  91 #endif
  92
  93     // Create the new machine instruction.
  94     MachineInstr *MI = new MachineInstr(Opc, II.numOperands, true, true);
  95
  96     // Add result register values for things that are defined by this
  97     // instruction.
  98     if (NumResults) {
  99       // Create the result registers for this node and add the result regs to
 100       // the machine instruction.
 101       const TargetOperandInfo *OpInfo = II.OpInfo;
 102       ResultReg = RegMap->createVirtualRegister(OpInfo[0].RegClass);
 103       MI->addRegOperand(ResultReg, MachineOperand::Def);
 104       for (unsigned i = 1; i != NumResults; ++i) {
 105         assert(OpInfo[i].RegClass && "Isn't a register operand!");
 106         MI->addRegOperand(RegMap->createVirtualRegister(OpInfo[0].RegClass),
 107                           MachineOperand::Def);
 108       }
 109     }
 110
 111     // Emit all of the operands of this instruction, adding them to the
 112     // instruction as appropriate.
 113     for (unsigned i = 0, e = Op.getNumOperands(); i != e; ++i) {
 114       if (Op.getOperand(i).isTargetOpcode()) {
 115         // Note that this case is redundant with the final else block, but we
 116         // include it because it is the most common and it makes the logic
 117         // simpler here.
 118         unsigned R = Emit(Op.getOperand(i));
 119         // Add an operand, unless this corresponds to a chain node.
 120         if (Op.getOperand(i).getValueType() != MVT::Other)
 121           MI->addRegOperand(R, MachineOperand::Use);
 122       } else if (ConstantSDNode *C =
 123                                    dyn_cast<ConstantSDNode>(Op.getOperand(i))) {
 124         MI->addZeroExtImm64Operand(C->getValue());
 125       } else if (RegisterSDNode*R =dyn_cast<RegisterSDNode>(Op.getOperand(i))) {
 126         MI->addRegOperand(R->getReg(), MachineOperand::Use);
 127       } else if (GlobalAddressSDNode *TGA =
 128                        dyn_cast<GlobalAddressSDNode>(Op.getOperand(i))) {
 129         MI->addGlobalAddressOperand(TGA->getGlobal(), false, 0);
 130       } else if (BasicBlockSDNode *BB =
 131                        dyn_cast<BasicBlockSDNode>(Op.getOperand(i))) {
 132         MI->addMachineBasicBlockOperand(BB->getBasicBlock());
 133       } else if (FrameIndexSDNode *FI =
 134                        dyn_cast<FrameIndexSDNode>(Op.getOperand(i))) {
 135         MI->addFrameIndexOperand(FI->getIndex());
 136       } else if (ConstantPoolSDNode *CP =
 137                     dyn_cast<ConstantPoolSDNode>(Op.getOperand(i))) {
 138         MI->addConstantPoolIndexOperand(CP->getIndex());
 139       } else {
 140         unsigned R = Emit(Op.getOperand(i));
 141         // Add an operand, unless this corresponds to a chain node.
 142         if (Op.getOperand(i).getValueType() != MVT::Other)
 143           MI->addRegOperand(R, MachineOperand::Use);
 144       }
 145     }
 146
 147     // Now that we have emitted all operands, emit this instruction itself.
 148     BB->insert(BB->end(), MI);
 149   } else {
 150     switch (Op.getOpcode()) {
 151     default:
 152       Op.Val->dump();
 153       assert(0 && "This target-independent node should have been selected!");
 154     case ISD::EntryToken: break;
 155     case ISD::TokenFactor:
 156       for (unsigned i = 0, e = Op.getNumOperands(); i != e; ++i)
 157         Emit(Op.getOperand(i));
 158       break;
 159     case ISD::CopyToReg: {
 160       Emit(Op.getOperand(0));   // Emit the chain.
 161       unsigned Val = Emit(Op.getOperand(2));
 162       MRI.copyRegToReg(*BB, BB->end(),
 163                        cast<RegisterSDNode>(Op.getOperand(1))->getReg(), Val,
 164                        RegMap->getRegClass(Val));
 165       break;
 166     }
 167     case ISD::CopyFromReg: {
 168       Emit(Op.getOperand(0));   // Emit the chain.
 169       unsigned SrcReg = cast<RegisterSDNode>(Op.getOperand(1))->getReg();
 170
 171       // Figure out the register class to create for the destreg.
 172       const TargetRegisterClass *TRC = 0;
 173       if (MRegisterInfo::isVirtualRegister(SrcReg)) {
 174         TRC = RegMap->getRegClass(SrcReg);
 175       } else {
 176         // FIXME: we don't know what register class to generate this for.  Do
 177         // a brute force search and pick the first match. :(
 178         for (MRegisterInfo::regclass_iterator I = MRI.regclass_begin(),
 179                E = MRI.regclass_end(); I != E; ++I)
 180           if ((*I)->contains(SrcReg)) {
 181             TRC = *I;
 182             break;
 183           }
 184         assert(TRC && "Couldn't find register class for reg copy!");
 185       }
 186
 187       // Create the reg, emit the copy.
 188       ResultReg = RegMap->createVirtualRegister(TRC);
 189       MRI.copyRegToReg(*BB, BB->end(), ResultReg, SrcReg, TRC);
 190       break;
 191     }
 192     }
 193   }
 194
 195   if (OpSlot) *OpSlot = ResultReg;
 196   return ResultReg+Op.ResNo;
 197 }
 198
 199
 200 /// Pick a safe ordering and emit instructions for each target node in the
 201 /// graph.
 202 void SelectionDAGISel::ScheduleAndEmitDAG(SelectionDAG &SD) {
 203   if (ViewDAGs) SD.viewGraph();
 204   SimpleSched(SD, BB).Run();
 205 }