1 //===-- ScheduleDAG.cpp - Implement a trivial DAG scheduler ---------------===//
3 // The LLVM Compiler Infrastructure
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.
8 //===----------------------------------------------------------------------===//
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.
13 //===----------------------------------------------------------------------===//
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"
29 ViewDAGs("view-sched-dags", cl::Hidden,
30 cl::desc("Pop up a window to show sched dags as they are processed"));
32 static const bool ViewDAGS = 0;
38 MachineBasicBlock *BB;
39 const TargetMachine &TM;
40 const TargetInstrInfo &TII;
41 const MRegisterInfo &MRI;
43 MachineConstantPool *ConstPool;
45 std::map<SDNode *, unsigned> EmittedOps;
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?");
55 MachineBasicBlock *Run() {
61 unsigned Emit(SDOperand Op);
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.
70 if (Op.Val->hasOneUse()) {
71 OpSlot = 0; // No reuse possible.
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;
79 unsigned ResultReg = 0;
80 if (Op.isTargetOpcode()) {
81 unsigned Opc = Op.getTargetOpcode();
82 const TargetInstrDescriptor &II = TII.get(Opc);
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)
90 if (NumResults && Op.Val->getValueType(NumResults-1) == MVT::Other)
91 --NumResults; // Skip over chain result.
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)
101 if (NodeOperands && // Ignore chain if it exists.
102 Op.getOperand(NodeOperands-1).getValueType() == MVT::Other)
105 unsigned NumMIOperands = NodeOperands+NumResults;
107 assert((unsigned(II.numOperands) == NumMIOperands || II.numOperands == -1)&&
108 "#operands for dag node doesn't match .td file!");
111 // Create the new machine instruction.
112 MachineInstr *MI = new MachineInstr(Opc, NumMIOperands, true, true);
114 // Add result register values for things that are defined by this
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);
129 // If there is a token chain operand, emit it first, as a hack to get avoid
131 if (Op.getNumOperands() > NodeOperands &&
132 Op.getOperand(NodeOperands).getValueType() == MVT::Other)
133 Emit(Op.getOperand(NodeOperands));
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
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!");
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);
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);
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));
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);
193 // Insert this instruction into the end of the basic block, potentially
194 // taking some custom action.
195 BB = DAG.getTargetLoweringInfo().InsertAtEndOfBasicBlock(MI, BB);
198 switch (Op.getOpcode()) {
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));
207 case ISD::CopyToReg: {
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));
220 case ISD::CopyFromReg: {
221 Emit(Op.getOperand(0)); // Emit the chain.
222 unsigned SrcReg = cast<RegisterSDNode>(Op.getOperand(1))->getReg();
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);
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)) {
237 assert(TRC && "Couldn't find register class for reg copy!");
240 // Create the reg, emit the copy.
241 ResultReg = RegMap->createVirtualRegister(TRC);
242 MRI.copyRegToReg(*BB, BB->end(), ResultReg, SrcReg, TRC);
248 if (OpSlot) *OpSlot = ResultReg;
249 return ResultReg+Op.ResNo;
253 /// Pick a safe ordering and emit instructions for each target node in the
255 void SelectionDAGISel::ScheduleAndEmitDAG(SelectionDAG &SD) {
256 if (ViewDAGs) SD.viewGraph();
257 BB = SimpleSched(SD, BB).Run();