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/MachineConstantPool.h"
  17 #include "llvm/CodeGen/MachineFunction.h"
  18 #include "llvm/CodeGen/SelectionDAGISel.h"
  19 #include "llvm/CodeGen/SelectionDAG.h"
  20 #include "llvm/CodeGen/SSARegMap.h"
  21 #include "llvm/Target/TargetMachine.h"
  22 #include "llvm/Target/TargetInstrInfo.h"
  23 #include "llvm/Target/TargetLowering.h"
  24 #include "llvm/Support/CommandLine.h"
  25 using namespace llvm;
  26
  27 #ifndef _NDEBUG
  28 static cl::opt<bool>
  29 ViewDAGs("view-sched-dags", cl::Hidden,
  30          cl::desc("Pop up a window to show sched dags as they are processed"));
  31 #else
  32 static const bool ViewDAGS = 0;
  33 #endif
  34
  35 namespace {
  36   class SimpleSched {
  37     SelectionDAG &DAG;
  38     MachineBasicBlock *BB;
  39     const TargetMachine &TM;
  40     const TargetInstrInfo &TII;
  41     const MRegisterInfo &MRI;
  42     SSARegMap *RegMap;
  43     MachineConstantPool *ConstPool;
  44
  45     std::map<SDNode *, unsigned> EmittedOps;
  46   public:
  47     SimpleSched(SelectionDAG &D, MachineBasicBlock *bb)
  48       : DAG(D), BB(bb), TM(D.getTarget()), TII(*TM.getInstrInfo()),
  49         MRI(*TM.getRegisterInfo()), RegMap(BB->getParent()->getSSARegMap()),
  50         ConstPool(BB->getParent()->getConstantPool()) {
  51       assert(&TII && "Target doesn't provide instr info?");
  52       assert(&MRI && "Target doesn't provide register info?");
  53     }
  54
  55     MachineBasicBlock *Run() {
  56       Emit(DAG.getRoot());
  57       return BB;
  58     }
  59
  60   private:
  61     unsigned Emit(SDOperand Op);
  62   };
  63 }
  64
  65 unsigned SimpleSched::Emit(SDOperand Op) {
  66   // Check to see if we have already emitted this.  If so, return the value
  67   // already emitted.  Note that if a node has a single use it cannot be
  68   // revisited, so don't bother putting it in the map.
  69   unsigned *OpSlot;
  70   if (Op.Val->hasOneUse()) {
  71     OpSlot = 0;  // No reuse possible.
  72   } else {
  73     std::map<SDNode *, unsigned>::iterator OpI = EmittedOps.lower_bound(Op.Val);
  74     if (OpI != EmittedOps.end() && OpI->first == Op.Val)
  75       return OpI->second + Op.ResNo;
  76     OpSlot = &EmittedOps.insert(OpI, std::make_pair(Op.Val, 0))->second;
  77   }
  78
  79   unsigned ResultReg = 0;
  80   if (Op.isTargetOpcode()) {
  81     unsigned Opc = Op.getTargetOpcode();
  82     const TargetInstrDescriptor &II = TII.get(Opc);
  83
  84     // The results of target nodes have register or immediate operands first,
  85     // then an optional chain, and optional flag operands (which do not go into
  86     // the machine instrs).
  87     unsigned NumResults = Op.Val->getNumValues();
  88     while (NumResults && Op.Val->getValueType(NumResults-1) == MVT::Flag)
  89       --NumResults;
  90     if (NumResults && Op.Val->getValueType(NumResults-1) == MVT::Other)
  91       --NumResults;    // Skip over chain result.
  92
  93     // The inputs to target nodes have any actual inputs first, followed by an
  94     // optional chain operand, then flag operands.  Compute the number of actual
  95     // operands that  will go into the machine instr.
  96     unsigned NodeOperands = Op.getNumOperands();
  97     while (NodeOperands &&
  98            Op.getOperand(NodeOperands-1).getValueType() == MVT::Flag)
  99       --NodeOperands;
 100
 101     if (NodeOperands &&    // Ignore chain if it exists.
 102         Op.getOperand(NodeOperands-1).getValueType() == MVT::Other)
 103       --NodeOperands;
 104
 105     unsigned NumMIOperands = NodeOperands+NumResults;
 106 #ifndef _NDEBUG
 107     assert((unsigned(II.numOperands) == NumMIOperands || II.numOperands == -1)&&
 108            "#operands for dag node doesn't match .td file!");
 109 #endif
 110
 111     // Create the new machine instruction.
 112     MachineInstr *MI = new MachineInstr(Opc, NumMIOperands, true, true);
 113
 114     // Add result register values for things that are defined by this
 115     // instruction.
 116     if (NumResults) {
 117       // Create the result registers for this node and add the result regs to
 118       // the machine instruction.
 119       const TargetOperandInfo *OpInfo = II.OpInfo;
 120       ResultReg = RegMap->createVirtualRegister(OpInfo[0].RegClass);
 121       MI->addRegOperand(ResultReg, MachineOperand::Def);
 122       for (unsigned i = 1; i != NumResults; ++i) {
 123         assert(OpInfo[i].RegClass && "Isn't a register operand!");
 124         MI->addRegOperand(RegMap->createVirtualRegister(OpInfo[0].RegClass),
 125                           MachineOperand::Def);
 126       }
 127     }
 128
 129     // If there is a token chain operand, emit it first, as a hack to get avoid
 130     // really bad cases.
 131     if (Op.getNumOperands() > NodeOperands &&
 132         Op.getOperand(NodeOperands).getValueType() == MVT::Other)
 133       Emit(Op.getOperand(NodeOperands));
 134
 135     // Emit all of the actual operands of this instruction, adding them to the
 136     // instruction as appropriate.
 137     for (unsigned i = 0; i != NodeOperands; ++i) {
 138       if (Op.getOperand(i).isTargetOpcode()) {
 139         // Note that this case is redundant with the final else block, but we
 140         // include it because it is the most common and it makes the logic
 141         // simpler here.
 142         assert(Op.getOperand(i).getValueType() != MVT::Other &&
 143                Op.getOperand(i).getValueType() != MVT::Flag &&
 144                "Chain and flag operands should occur at end of operand list!");
 145
 146         MI->addRegOperand(Emit(Op.getOperand(i)), MachineOperand::Use);
 147       } else if (ConstantSDNode *C =
 148                                    dyn_cast<ConstantSDNode>(Op.getOperand(i))) {
 149         MI->addZeroExtImm64Operand(C->getValue());
 150       } else if (RegisterSDNode*R =dyn_cast<RegisterSDNode>(Op.getOperand(i))) {
 151         MI->addRegOperand(R->getReg(), MachineOperand::Use);
 152       } else if (GlobalAddressSDNode *TGA =
 153                        dyn_cast<GlobalAddressSDNode>(Op.getOperand(i))) {
 154         MI->addGlobalAddressOperand(TGA->getGlobal(), false, 0);
 155       } else if (BasicBlockSDNode *BB =
 156                        dyn_cast<BasicBlockSDNode>(Op.getOperand(i))) {
 157         MI->addMachineBasicBlockOperand(BB->getBasicBlock());
 158       } else if (FrameIndexSDNode *FI =
 159                        dyn_cast<FrameIndexSDNode>(Op.getOperand(i))) {
 160         MI->addFrameIndexOperand(FI->getIndex());
 161       } else if (ConstantPoolSDNode *CP =
 162                     dyn_cast<ConstantPoolSDNode>(Op.getOperand(i))) {
 163         unsigned Idx = ConstPool->getConstantPoolIndex(CP->get());
 164         MI->addConstantPoolIndexOperand(Idx);
 165       } else if (ExternalSymbolSDNode *ES =
 166                  dyn_cast<ExternalSymbolSDNode>(Op.getOperand(i))) {
 167         MI->addExternalSymbolOperand(ES->getSymbol(), false);
 168       } else {
 169         assert(Op.getOperand(i).getValueType() != MVT::Other &&
 170                Op.getOperand(i).getValueType() != MVT::Flag &&
 171                "Chain and flag operands should occur at end of operand list!");
 172         MI->addRegOperand(Emit(Op.getOperand(i)), MachineOperand::Use);
 173       }
 174     }
 175
 176     // Finally, if this node has any flag operands, we *must* emit them last, to
 177     // avoid emitting operations that might clobber the flags.
 178     if (Op.getNumOperands() > NodeOperands) {
 179       unsigned i = NodeOperands;
 180       if (Op.getOperand(i).getValueType() == MVT::Other)
 181         ++i;  // the chain is already selected.
 182       for (; i != Op.getNumOperands(); ++i) {
 183         assert(Op.getOperand(i).getValueType() == MVT::Flag &&
 184                "Must be flag operands!");
 185         Emit(Op.getOperand(i));
 186       }
 187     }
 188
 189     // Now that we have emitted all operands, emit this instruction itself.
 190     if ((II.Flags & M_USES_CUSTOM_DAG_SCHED_INSERTION) == 0) {
 191       BB->insert(BB->end(), MI);
 192     } else {
 193       // Insert this instruction into the end of the basic block, potentially
 194       // taking some custom action.
 195       BB = DAG.getTargetLoweringInfo().InsertAtEndOfBasicBlock(MI, BB);
 196     }
 197   } else {
 198     switch (Op.getOpcode()) {
 199     default:
 200       Op.Val->dump();
 201       assert(0 && "This target-independent node should have been selected!");
 202     case ISD::EntryToken: break;
 203     case ISD::TokenFactor:
 204       for (unsigned i = 0, e = Op.getNumOperands(); i != e; ++i)
 205         Emit(Op.getOperand(i));
 206       break;
 207     case ISD::CopyToReg: {
 208       SDOperand FlagOp;
 209       if (Op.getNumOperands() == 4)
 210         FlagOp = Op.getOperand(3);
 211       if (Op.getOperand(0).Val != FlagOp.Val)
 212         Emit(Op.getOperand(0));   // Emit the chain.
 213       unsigned Val = Emit(Op.getOperand(2));
 214       if (FlagOp.Val) Emit(FlagOp);
 215       MRI.copyRegToReg(*BB, BB->end(),
 216                        cast<RegisterSDNode>(Op.getOperand(1))->getReg(), Val,
 217                        RegMap->getRegClass(Val));
 218       break;
 219     }
 220     case ISD::CopyFromReg: {
 221       Emit(Op.getOperand(0));   // Emit the chain.
 222       unsigned SrcReg = cast<RegisterSDNode>(Op.getOperand(1))->getReg();
 223
 224       // Figure out the register class to create for the destreg.
 225       const TargetRegisterClass *TRC = 0;
 226       if (MRegisterInfo::isVirtualRegister(SrcReg)) {
 227         TRC = RegMap->getRegClass(SrcReg);
 228       } else {
 229         // FIXME: we don't know what register class to generate this for.  Do
 230         // a brute force search and pick the first match. :(
 231         for (MRegisterInfo::regclass_iterator I = MRI.regclass_begin(),
 232                E = MRI.regclass_end(); I != E; ++I)
 233           if ((*I)->contains(SrcReg)) {
 234             TRC = *I;
 235             break;
 236           }
 237         assert(TRC && "Couldn't find register class for reg copy!");
 238       }
 239
 240       // Create the reg, emit the copy.
 241       ResultReg = RegMap->createVirtualRegister(TRC);
 242       MRI.copyRegToReg(*BB, BB->end(), ResultReg, SrcReg, TRC);
 243       break;
 244     }
 245     }
 246   }
 247
 248   if (OpSlot) *OpSlot = ResultReg;
 249   return ResultReg+Op.ResNo;
 250 }
 251
 252
 253 /// Pick a safe ordering and emit instructions for each target node in the
 254 /// graph.
 255 void SelectionDAGISel::ScheduleAndEmitDAG(SelectionDAG &SD) {
 256   if (ViewDAGs) SD.viewGraph();
 257   BB = SimpleSched(SD, BB).Run();
 258 }