1//===-- MipsISelDAGToDAG.cpp - A dag to dag inst selector for Mips --------===//
2//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This file defines an instruction selector for the MIPS target.
11//
12//===----------------------------------------------------------------------===//
13
14#define DEBUG_TYPE "mips-isel"
15#include "Mips.h"
16#include "MipsISelLowering.h"
17#include "MipsMachineFunction.h"
18#include "MipsRegisterInfo.h"
19#include "MipsSubtarget.h"
20#include "MipsTargetMachine.h"
21#include "llvm/GlobalValue.h"
22#include "llvm/Instructions.h"
23#include "llvm/Intrinsics.h"
24#include "llvm/Support/CFG.h"
25#include "llvm/Type.h"
26#include "llvm/CodeGen/MachineConstantPool.h"
27#include "llvm/CodeGen/MachineFunction.h"
28#include "llvm/CodeGen/MachineFrameInfo.h"
29#include "llvm/CodeGen/MachineInstrBuilder.h"
30#include "llvm/CodeGen/MachineRegisterInfo.h"
31#include "llvm/CodeGen/SelectionDAGISel.h"
32#include "llvm/Target/TargetMachine.h"
33#include "llvm/Support/Debug.h"
34#include "llvm/Support/ErrorHandling.h"
35#include "llvm/Support/raw_ostream.h"
36using namespace llvm;
37
38//===----------------------------------------------------------------------===//
39// Instruction Selector Implementation
40//===----------------------------------------------------------------------===//
41
42//===----------------------------------------------------------------------===//
43// MipsDAGToDAGISel - MIPS specific code to select MIPS machine
44// instructions for SelectionDAG operations.
45//===----------------------------------------------------------------------===//
46namespace {
47
48class MipsDAGToDAGISel : public SelectionDAGISel {
49
50 /// TM - Keep a reference to MipsTargetMachine.
51 MipsTargetMachine &TM;
52
53 /// Subtarget - Keep a pointer to the MipsSubtarget around so that we can
54 /// make the right decision when generating code for different targets.
55 const MipsSubtarget &Subtarget;
56
57public:
58 explicit MipsDAGToDAGISel(MipsTargetMachine &tm) :
59 SelectionDAGISel(tm),
60 TM(tm), Subtarget(tm.getSubtarget<MipsSubtarget>()) {}
61
62 virtual void InstructionSelect();
63
64 // Pass Name
65 virtual const char *getPassName() const {
66 return "MIPS DAG->DAG Pattern Instruction Selection";
67 }
68
69
70private:
71 // Include the pieces autogenerated from the target description.
72 #include "MipsGenDAGISel.inc"
73
74 /// getTargetMachine - Return a reference to the TargetMachine, casted
75 /// to the target-specific type.
76 const MipsTargetMachine &getTargetMachine() {
77 return static_cast<const MipsTargetMachine &>(TM);
78 }
79
80 /// getInstrInfo - Return a reference to the TargetInstrInfo, casted
81 /// to the target-specific type.
82 const MipsInstrInfo *getInstrInfo() {
83 return getTargetMachine().getInstrInfo();
84 }
85
86 SDNode *getGlobalBaseReg();
87 SDNode *Select(SDValue N);
88
89 // Complex Pattern.
90 bool SelectAddr(SDValue Op, SDValue N,
91 SDValue &Base, SDValue &Offset);
92
93
94 // getI32Imm - Return a target constant with the specified
95 // value, of type i32.
96 inline SDValue getI32Imm(unsigned Imm) {
97 return CurDAG->getTargetConstant(Imm, MVT::i32);
98 }
99
100
101 #ifndef NDEBUG
102 unsigned Indent;
103 #endif
104};
105
106}
107
108/// InstructionSelect - This callback is invoked by
109/// SelectionDAGISel when it has created a SelectionDAG for us to codegen.
110void MipsDAGToDAGISel::InstructionSelect() {
111 // Codegen the basic block.
112 DEBUG(errs() << "===== Instruction selection begins:\n");
113 DEBUG(Indent = 0);
114
115 // Select target instructions for the DAG.
116 SelectRoot(*CurDAG);
117
118 DEBUG(errs() << "===== Instruction selection ends:\n");
119
120 CurDAG->RemoveDeadNodes();
121}
122
123/// getGlobalBaseReg - Output the instructions required to put the
124/// GOT address into a register.
125SDNode *MipsDAGToDAGISel::getGlobalBaseReg() {
126 unsigned GlobalBaseReg = getInstrInfo()->getGlobalBaseReg(MF);
127 return CurDAG->getRegister(GlobalBaseReg, TLI.getPointerTy()).getNode();
128}
129
130/// ComplexPattern used on MipsInstrInfo
131/// Used on Mips Load/Store instructions
132bool MipsDAGToDAGISel::
133SelectAddr(SDValue Op, SDValue Addr, SDValue &Offset, SDValue &Base)
134{
135 // if Address is FI, get the TargetFrameIndex.
136 if (FrameIndexSDNode *FIN = dyn_cast<FrameIndexSDNode>(Addr)) {
137 Base = CurDAG->getTargetFrameIndex(FIN->getIndex(), MVT::i32);
138 Offset = CurDAG->getTargetConstant(0, MVT::i32);
139 return true;
140 }
141
142 // on PIC code Load GA
143 if (TM.getRelocationModel() == Reloc::PIC_) {
144 if ((Addr.getOpcode() == ISD::TargetGlobalAddress) ||
145 (Addr.getOpcode() == ISD::TargetJumpTable)){
146 Base = CurDAG->getRegister(Mips::GP, MVT::i32);
147 Offset = Addr;
148 return true;
149 }
150 } else {
151 if ((Addr.getOpcode() == ISD::TargetExternalSymbol ||
152 Addr.getOpcode() == ISD::TargetGlobalAddress))
153 return false;
154 }
155
156 // Operand is a result from an ADD.
157 if (Addr.getOpcode() == ISD::ADD) {
158 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(Addr.getOperand(1))) {
159 if (Predicate_immSExt16(CN)) {
160
161 // If the first operand is a FI, get the TargetFI Node
162 if (FrameIndexSDNode *FIN = dyn_cast<FrameIndexSDNode>
163 (Addr.getOperand(0))) {
164 Base = CurDAG->getTargetFrameIndex(FIN->getIndex(), MVT::i32);
165 } else {
166 Base = Addr.getOperand(0);
167 }
168
169 Offset = CurDAG->getTargetConstant(CN->getZExtValue(), MVT::i32);
170 return true;
171 }
172 }
173
174 // When loading from constant pools, load the lower address part in
175 // the instruction itself. Instead of:
176 // lui $2, %hi($CPI1_0)
177 // addiu $2, $2, %lo($CPI1_0)
178 // lwc1 $f0, 0($2)
179 // Generate:
180 // lui $2, %hi($CPI1_0)
181 // lwc1 $f0, %lo($CPI1_0)($2)
182 if (Addr.getOperand(0).getOpcode() == MipsISD::Hi &&
183 Addr.getOperand(1).getOpcode() == MipsISD::Lo) {
184 SDValue LoVal = Addr.getOperand(1);
185 if (ConstantPoolSDNode *CP = dyn_cast<ConstantPoolSDNode>(
186 LoVal.getOperand(0))) {
187 if (!CP->getOffset()) {
188 Base = Addr.getOperand(0);
189 Offset = LoVal.getOperand(0);
190 return true;
191 }
192 }
193 }
194 }
195
196 Base = Addr;
197 Offset = CurDAG->getTargetConstant(0, MVT::i32);
198 return true;
199}
200
201/// Select instructions not customized! Used for
202/// expanded, promoted and normal instructions
203SDNode* MipsDAGToDAGISel::Select(SDValue N) {
204 SDNode *Node = N.getNode();
205 unsigned Opcode = Node->getOpcode();
206 DebugLoc dl = Node->getDebugLoc();
207
208 // Dump information about the Node being selected
209 DEBUG(errs().indent(Indent) << "Selecting: ";
210 Node->dump(CurDAG);
211 errs() << "\n");
212 DEBUG(Indent += 2);
213
214 // If we have a custom node, we already have selected!
215 if (Node->isMachineOpcode()) {
216 DEBUG(errs().indent(Indent-2) << "== ";
217 Node->dump(CurDAG);
218 errs() << "\n");
219 DEBUG(Indent -= 2);
220 return NULL;
221 }
222
223 ///
224 // Instruction Selection not handled by the auto-generated
225 // tablegen selection should be handled here.
226 ///
227 switch(Opcode) {
228
229 default: break;
230
231 case ISD::SUBE:
232 case ISD::ADDE: {
233 SDValue InFlag = Node->getOperand(2), CmpLHS;
234 unsigned Opc = InFlag.getOpcode(); Opc=Opc;
235 assert(((Opc == ISD::ADDC || Opc == ISD::ADDE) ||
236 (Opc == ISD::SUBC || Opc == ISD::SUBE)) &&
237 "(ADD|SUB)E flag operand must come from (ADD|SUB)C/E insn");
238
239 unsigned MOp;
240 if (Opcode == ISD::ADDE) {
241 CmpLHS = InFlag.getValue(0);
242 MOp = Mips::ADDu;
243 } else {
244 CmpLHS = InFlag.getOperand(0);
245 MOp = Mips::SUBu;
246 }
247
248 SDValue Ops[] = { CmpLHS, InFlag.getOperand(1) };
249
250 SDValue LHS = Node->getOperand(0);
251 SDValue RHS = Node->getOperand(1);
252
253 EVT VT = LHS.getValueType();
254 SDNode *Carry = CurDAG->getMachineNode(Mips::SLTu, dl, VT, Ops, 2);
255 SDNode *AddCarry = CurDAG->getMachineNode(Mips::ADDu, dl, VT,
256 SDValue(Carry,0), RHS);
257
258 return CurDAG->SelectNodeTo(N.getNode(), MOp, VT, MVT::Flag,
259 LHS, SDValue(AddCarry,0));
260 }
261
262 /// Mul/Div with two results
263 case ISD::SDIVREM:
264 case ISD::UDIVREM:
265 case ISD::SMUL_LOHI:
266 case ISD::UMUL_LOHI: {
267 SDValue Op1 = Node->getOperand(0);
268 SDValue Op2 = Node->getOperand(1);
269
270 unsigned Op;
271 if (Opcode == ISD::UMUL_LOHI || Opcode == ISD::SMUL_LOHI)
272 Op = (Opcode == ISD::UMUL_LOHI ? Mips::MULTu : Mips::MULT);
273 else
274 Op = (Opcode == ISD::UDIVREM ? Mips::DIVu : Mips::DIV);
275
276 SDNode *Node = CurDAG->getMachineNode(Op, dl, MVT::Flag, Op1, Op2);
277
278 SDValue InFlag = SDValue(Node, 0);
279 SDNode *Lo = CurDAG->getMachineNode(Mips::MFLO, dl, MVT::i32,
280 MVT::Flag, InFlag);
281 InFlag = SDValue(Lo,1);
282 SDNode *Hi = CurDAG->getMachineNode(Mips::MFHI, dl, MVT::i32, InFlag);
283
284 if (!N.getValue(0).use_empty())
285 ReplaceUses(N.getValue(0), SDValue(Lo,0));
286
287 if (!N.getValue(1).use_empty())
288 ReplaceUses(N.getValue(1), SDValue(Hi,0));
289
290 return NULL;
291 }
292
293 /// Special Muls
294 case ISD::MUL:
295 case ISD::MULHS:
296 case ISD::MULHU: {
297 SDValue MulOp1 = Node->getOperand(0);
298 SDValue MulOp2 = Node->getOperand(1);
299
300 unsigned MulOp = (Opcode == ISD::MULHU ? Mips::MULTu : Mips::MULT);
301 SDNode *MulNode = CurDAG->getMachineNode(MulOp, dl,
302 MVT::Flag, MulOp1, MulOp2);
303
304 SDValue InFlag = SDValue(MulNode, 0);
305
306 if (MulOp == ISD::MUL)
307 return CurDAG->getMachineNode(Mips::MFLO, dl, MVT::i32, InFlag);
308 else
309 return CurDAG->getMachineNode(Mips::MFHI, dl, MVT::i32, InFlag);
310 }
311
312 /// Div/Rem operations
313 case ISD::SREM:
314 case ISD::UREM:
315 case ISD::SDIV:
316 case ISD::UDIV: {
317 SDValue Op1 = Node->getOperand(0);
318 SDValue Op2 = Node->getOperand(1);
319
320 unsigned Op, MOp;
321 if (Opcode == ISD::SDIV || Opcode == ISD::UDIV) {
322 Op = (Opcode == ISD::SDIV ? Mips::DIV : Mips::DIVu);
323 MOp = Mips::MFLO;
324 } else {
325 Op = (Opcode == ISD::SREM ? Mips::DIV : Mips::DIVu);
326 MOp = Mips::MFHI;
327 }
328 SDNode *Node = CurDAG->getMachineNode(Op, dl, MVT::Flag, Op1, Op2);
329
330 SDValue InFlag = SDValue(Node, 0);
331 return CurDAG->getMachineNode(MOp, dl, MVT::i32, InFlag);
332 }
333
334 // Get target GOT address.
335 case ISD::GLOBAL_OFFSET_TABLE:
336 return getGlobalBaseReg();
337
338 case ISD::ConstantFP: {
339 ConstantFPSDNode *CN = dyn_cast<ConstantFPSDNode>(N);
340 if (N.getValueType() == MVT::f64 && CN->isExactlyValue(+0.0)) {
341 SDValue Zero = CurDAG->getRegister(Mips::ZERO, MVT::i32);
342 ReplaceUses(N, Zero);
343 return Zero.getNode();
344 }
345 break;
346 }
347
348 /// Handle direct and indirect calls when using PIC. On PIC, when
349 /// GOT is smaller than about 64k (small code) the GA target is
350 /// loaded with only one instruction. Otherwise GA's target must
351 /// be loaded with 3 instructions.
352 case MipsISD::JmpLink: {
353 if (TM.getRelocationModel() == Reloc::PIC_) {
354 SDValue Chain = Node->getOperand(0);
355 SDValue Callee = Node->getOperand(1);
356 SDValue T9Reg = CurDAG->getRegister(Mips::T9, MVT::i32);
357 SDValue InFlag(0, 0);
358
359 if ( (isa<GlobalAddressSDNode>(Callee)) ||
360 (isa<ExternalSymbolSDNode>(Callee)) )
361 {
362 /// Direct call for global addresses and external symbols
363 SDValue GPReg = CurDAG->getRegister(Mips::GP, MVT::i32);
364
365 // Use load to get GOT target
366 SDValue Ops[] = { Callee, GPReg, Chain };
367 SDValue Load = SDValue(CurDAG->getMachineNode(Mips::LW, dl, MVT::i32,
368 MVT::Other, Ops, 3), 0);
369 Chain = Load.getValue(1);
370
371 // Call target must be on T9
372 Chain = CurDAG->getCopyToReg(Chain, dl, T9Reg, Load, InFlag);
373 } else
374 /// Indirect call
375 Chain = CurDAG->getCopyToReg(Chain, dl, T9Reg, Callee, InFlag);
376
377 // Emit Jump and Link Register
378 SDNode *ResNode = CurDAG->getMachineNode(Mips::JALR, dl, MVT::Other,
379 MVT::Flag, T9Reg, Chain);
380 Chain = SDValue(ResNode, 0);
381 InFlag = SDValue(ResNode, 1);
382 ReplaceUses(SDValue(Node, 0), Chain);
383 ReplaceUses(SDValue(Node, 1), InFlag);
384 return ResNode;
385 }
386 }
387 }
388
389 // Select the default instruction
390 SDNode *ResNode = SelectCode(N);
391
392 DEBUG(errs().indent(Indent-2) << "=> ");
393 if (ResNode == NULL || ResNode == N.getNode())
394 DEBUG(N.getNode()->dump(CurDAG));
395 else
396 DEBUG(ResNode->dump(CurDAG));
397 DEBUG(errs() << "\n");
398 DEBUG(Indent -= 2);
399
400 return ResNode;
401}
402
403/// createMipsISelDag - This pass converts a legalized DAG into a
404/// MIPS-specific DAG, ready for instruction scheduling.
405FunctionPass *llvm::createMipsISelDag(MipsTargetMachine &TM) {
406 return new MipsDAGToDAGISel(TM);
407}