1 ///===-- FastISel.cpp - Implementation of the FastISel class --------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file contains the implementation of the FastISel class.
12 //===----------------------------------------------------------------------===//
14 #include "llvm/Instructions.h"
15 #include "llvm/CodeGen/FastISel.h"
16 #include "llvm/CodeGen/MachineInstrBuilder.h"
17 #include "llvm/CodeGen/MachineRegisterInfo.h"
18 #include "llvm/Target/TargetData.h"
19 #include "llvm/Target/TargetInstrInfo.h"
20 #include "llvm/Target/TargetLowering.h"
21 #include "llvm/Target/TargetMachine.h"
24 /// SelectBinaryOp - Select and emit code for a binary operator instruction,
25 /// which has an opcode which directly corresponds to the given ISD opcode.
27 bool FastISel::SelectBinaryOp(Instruction *I, ISD::NodeType ISDOpcode,
28 DenseMap<const Value*, unsigned> &ValueMap) {
29 MVT VT = MVT::getMVT(I->getType(), /*HandleUnknown=*/true);
30 if (VT == MVT::Other || !VT.isSimple())
31 // Unhandled type. Halt "fast" selection and bail.
34 unsigned Op0 = ValueMap[I->getOperand(0)];
36 // Unhandled operand. Halt "fast" selection and bail.
39 // Check if the second operand is a constant and handle it appropriately.
40 if (ConstantInt *CI = dyn_cast<ConstantInt>(I->getOperand(1))) {
41 unsigned ResultReg = FastEmit_ri_(VT.getSimpleVT(), ISDOpcode, Op0,
42 CI->getZExtValue(), VT.getSimpleVT());
44 // Target-specific code wasn't able to find a machine opcode for
45 // the given ISD opcode and type. Halt "fast" selection and bail.
48 // We successfully emitted code for the given LLVM Instruction.
49 ValueMap[I] = ResultReg;
53 unsigned Op1 = ValueMap[I->getOperand(1)];
55 // Unhandled operand. Halt "fast" selection and bail.
58 unsigned ResultReg = FastEmit_rr(VT.getSimpleVT(), VT.getSimpleVT(),
61 // Target-specific code wasn't able to find a machine opcode for
62 // the given ISD opcode and type. Halt "fast" selection and bail.
65 // We successfully emitted code for the given LLVM Instruction.
66 ValueMap[I] = ResultReg;
70 bool FastISel::SelectGetElementPtr(Instruction *I,
71 DenseMap<const Value*, unsigned> &ValueMap) {
72 unsigned N = ValueMap[I->getOperand(0)];
74 // Unhandled operand. Halt "fast" selection and bail.
77 const Type *Ty = I->getOperand(0)->getType();
78 MVT::SimpleValueType VT = TLI.getPointerTy().getSimpleVT();
79 for (GetElementPtrInst::op_iterator OI = I->op_begin()+1, E = I->op_end();
82 if (const StructType *StTy = dyn_cast<StructType>(Ty)) {
83 unsigned Field = cast<ConstantInt>(Idx)->getZExtValue();
86 uint64_t Offs = TD.getStructLayout(StTy)->getElementOffset(Field);
87 // FIXME: This can be optimized by combining the add with a
89 N = FastEmit_ri_(VT, ISD::ADD, N, Offs, VT);
91 // Unhandled operand. Halt "fast" selection and bail.
94 Ty = StTy->getElementType(Field);
96 Ty = cast<SequentialType>(Ty)->getElementType();
98 // If this is a constant subscript, handle it quickly.
99 if (ConstantInt *CI = dyn_cast<ConstantInt>(Idx)) {
100 if (CI->getZExtValue() == 0) continue;
102 TD.getABITypeSize(Ty)*cast<ConstantInt>(CI)->getSExtValue();
103 N = FastEmit_ri_(VT, ISD::ADD, N, Offs, VT);
105 // Unhandled operand. Halt "fast" selection and bail.
110 // N = N + Idx * ElementSize;
111 uint64_t ElementSize = TD.getABITypeSize(Ty);
112 unsigned IdxN = ValueMap[Idx];
114 // Unhandled operand. Halt "fast" selection and bail.
117 // If the index is smaller or larger than intptr_t, truncate or extend
119 MVT IdxVT = MVT::getMVT(Idx->getType(), /*HandleUnknown=*/false);
120 if (IdxVT.bitsLT(VT))
121 IdxN = FastEmit_r(VT, VT, ISD::SIGN_EXTEND, IdxN);
122 else if (IdxVT.bitsGT(VT))
123 IdxN = FastEmit_r(VT, VT, ISD::TRUNCATE, IdxN);
125 // Unhandled operand. Halt "fast" selection and bail.
128 if (ElementSize != 1)
129 IdxN = FastEmit_ri_(VT, ISD::MUL, IdxN, ElementSize, VT);
131 // Unhandled operand. Halt "fast" selection and bail.
133 N = FastEmit_rr(VT, VT, ISD::ADD, N, IdxN);
135 // Unhandled operand. Halt "fast" selection and bail.
140 // We successfully emitted code for the given LLVM Instruction.
146 FastISel::SelectInstructions(BasicBlock::iterator Begin,
147 BasicBlock::iterator End,
148 DenseMap<const Value*, unsigned> &ValueMap,
149 DenseMap<const BasicBlock*,
150 MachineBasicBlock *> &MBBMap,
151 MachineBasicBlock *mbb) {
153 BasicBlock::iterator I = Begin;
155 for (; I != End; ++I) {
156 switch (I->getOpcode()) {
157 case Instruction::Add: {
158 ISD::NodeType Opc = I->getType()->isFPOrFPVector() ? ISD::FADD : ISD::ADD;
159 if (!SelectBinaryOp(I, Opc, ValueMap)) return I; break;
161 case Instruction::Sub: {
162 ISD::NodeType Opc = I->getType()->isFPOrFPVector() ? ISD::FSUB : ISD::SUB;
163 if (!SelectBinaryOp(I, Opc, ValueMap)) return I; break;
165 case Instruction::Mul: {
166 ISD::NodeType Opc = I->getType()->isFPOrFPVector() ? ISD::FMUL : ISD::MUL;
167 if (!SelectBinaryOp(I, Opc, ValueMap)) return I; break;
169 case Instruction::SDiv:
170 if (!SelectBinaryOp(I, ISD::SDIV, ValueMap)) return I; break;
171 case Instruction::UDiv:
172 if (!SelectBinaryOp(I, ISD::UDIV, ValueMap)) return I; break;
173 case Instruction::FDiv:
174 if (!SelectBinaryOp(I, ISD::FDIV, ValueMap)) return I; break;
175 case Instruction::SRem:
176 if (!SelectBinaryOp(I, ISD::SREM, ValueMap)) return I; break;
177 case Instruction::URem:
178 if (!SelectBinaryOp(I, ISD::UREM, ValueMap)) return I; break;
179 case Instruction::FRem:
180 if (!SelectBinaryOp(I, ISD::FREM, ValueMap)) return I; break;
181 case Instruction::Shl:
182 if (!SelectBinaryOp(I, ISD::SHL, ValueMap)) return I; break;
183 case Instruction::LShr:
184 if (!SelectBinaryOp(I, ISD::SRL, ValueMap)) return I; break;
185 case Instruction::AShr:
186 if (!SelectBinaryOp(I, ISD::SRA, ValueMap)) return I; break;
187 case Instruction::And:
188 if (!SelectBinaryOp(I, ISD::AND, ValueMap)) return I; break;
189 case Instruction::Or:
190 if (!SelectBinaryOp(I, ISD::OR, ValueMap)) return I; break;
191 case Instruction::Xor:
192 if (!SelectBinaryOp(I, ISD::XOR, ValueMap)) return I; break;
194 case Instruction::GetElementPtr:
195 if (!SelectGetElementPtr(I, ValueMap)) return I;
198 case Instruction::Br: {
199 BranchInst *BI = cast<BranchInst>(I);
201 if (BI->isUnconditional()) {
202 MachineFunction::iterator NextMBB =
203 next(MachineFunction::iterator(MBB));
204 BasicBlock *LLVMSucc = BI->getSuccessor(0);
205 MachineBasicBlock *MSucc = MBBMap[LLVMSucc];
207 if (NextMBB != MF.end() && MSucc == NextMBB) {
208 // The unconditional fall-through case, which needs no instructions.
210 // The unconditional branch case.
211 TII.InsertBranch(*MBB, MSucc, NULL, SmallVector<MachineOperand, 0>());
213 MBB->addSuccessor(MSucc);
217 // Conditional branches are not handed yet.
218 // Halt "fast" selection and bail.
222 case Instruction::PHI:
223 // PHI nodes are already emitted.
226 case Instruction::BitCast:
227 // BitCast consists of either an immediate to register move
228 // or a register to register move.
229 if (ConstantInt* CI = dyn_cast<ConstantInt>(I->getOperand(0))) {
230 if (I->getType()->isInteger()) {
231 MVT VT = MVT::getMVT(I->getType(), /*HandleUnknown=*/false);
232 unsigned result = FastEmit_i(VT.getSimpleVT(), VT.getSimpleVT(),
238 ValueMap[I] = result;
241 // TODO: Support vector and fp constants.
243 } else if (!isa<Constant>(I->getOperand(0))) {
244 // Bitcasts of non-constant values become reg-reg copies.
245 MVT SrcVT = MVT::getMVT(I->getOperand(0)->getType());
246 MVT DstVT = MVT::getMVT(I->getType());
248 if (SrcVT == MVT::Other || !SrcVT.isSimple() ||
249 DstVT == MVT::Other || !DstVT.isSimple() ||
250 !TLI.isTypeLegal(SrcVT) || !TLI.isTypeLegal(DstVT))
251 // Unhandled type. Halt "fast" selection and bail.
254 unsigned Op0 = ValueMap[I->getOperand(0)];
256 // Unhandled operand. Halt "fast" selection and bail.
259 // First, try to perform the bitcast by inserting a reg-reg copy.
260 unsigned ResultReg = 0;
261 if (SrcVT.getSimpleVT() == DstVT.getSimpleVT()) {
262 TargetRegisterClass* SrcClass = TLI.getRegClassFor(SrcVT);
263 TargetRegisterClass* DstClass = TLI.getRegClassFor(DstVT);
264 ResultReg = createResultReg(DstClass);
266 bool InsertedCopy = TII.copyRegToReg(*MBB, MBB->end(), ResultReg,
267 Op0, DstClass, SrcClass);
272 // If the reg-reg copy failed, select a BIT_CONVERT opcode.
274 ResultReg = FastEmit_r(SrcVT.getSimpleVT(), DstVT.getSimpleVT(),
275 ISD::BIT_CONVERT, Op0);
280 ValueMap[I] = ResultReg;
283 // TODO: Casting a non-integral constant?
286 case Instruction::FPToSI:
287 if (!isa<ConstantFP>(I->getOperand(0))) {
288 MVT SrcVT = MVT::getMVT(I->getOperand(0)->getType());
289 MVT DstVT = MVT::getMVT(I->getType());
291 if (SrcVT == MVT::Other || !SrcVT.isSimple() ||
292 DstVT == MVT::Other || !DstVT.isSimple() ||
293 !TLI.isTypeLegal(SrcVT) || !TLI.isTypeLegal(DstVT))
294 // Unhandled type. Halt "fast" selection and bail.
296 if (TLI.getOperationAction(ISD::FP_TO_SINT, SrcVT) !=
297 TargetLowering::Legal)
298 // Unhandled opcode on this type. Halt "fast" seleciton and bail.
301 unsigned InputReg = ValueMap[I->getOperand(0)];
303 // Unhandled operand. Halt "fast" selection and bail.
306 unsigned ResultReg = FastEmit_r(SrcVT.getSimpleVT(),
313 ValueMap[I] = ResultReg;
316 // TODO: Materialize the FP constant and then convert,
317 // or attempt constant folding.
321 // Unhandled instruction. Halt "fast" selection and bail.
329 FastISel::FastISel(MachineFunction &mf)
331 MRI(mf.getRegInfo()),
333 TD(*TM.getTargetData()),
334 TII(*TM.getInstrInfo()),
335 TLI(*TM.getTargetLowering()) {
338 FastISel::~FastISel() {}
340 unsigned FastISel::FastEmit_(MVT::SimpleValueType, MVT::SimpleValueType, ISD::NodeType) {
344 unsigned FastISel::FastEmit_r(MVT::SimpleValueType, MVT::SimpleValueType,
345 ISD::NodeType, unsigned /*Op0*/) {
349 unsigned FastISel::FastEmit_rr(MVT::SimpleValueType, MVT::SimpleValueType,
350 ISD::NodeType, unsigned /*Op0*/,
355 unsigned FastISel::FastEmit_i(MVT::SimpleValueType, MVT::SimpleValueType,
356 ISD::NodeType, uint64_t /*Imm*/) {
360 unsigned FastISel::FastEmit_ri(MVT::SimpleValueType, MVT::SimpleValueType,
361 ISD::NodeType, unsigned /*Op0*/,
366 unsigned FastISel::FastEmit_rri(MVT::SimpleValueType, MVT::SimpleValueType,
368 unsigned /*Op0*/, unsigned /*Op1*/,
373 /// FastEmit_ri_ - This method is a wrapper of FastEmit_ri. It first tries
374 /// to emit an instruction with an immediate operand using FastEmit_ri.
375 /// If that fails, it materializes the immediate into a register and try
376 /// FastEmit_rr instead.
377 unsigned FastISel::FastEmit_ri_(MVT::SimpleValueType VT, ISD::NodeType Opcode,
378 unsigned Op0, uint64_t Imm,
379 MVT::SimpleValueType ImmType) {
380 unsigned ResultReg = 0;
381 // First check if immediate type is legal. If not, we can't use the ri form.
382 if (TLI.getOperationAction(ISD::Constant, ImmType) == TargetLowering::Legal)
383 ResultReg = FastEmit_ri(VT, VT, Opcode, Op0, Imm);
386 unsigned MaterialReg = FastEmit_i(ImmType, ImmType, ISD::Constant, Imm);
387 if (MaterialReg == 0)
389 return FastEmit_rr(VT, VT, Opcode, Op0, MaterialReg);
392 unsigned FastISel::createResultReg(const TargetRegisterClass* RC) {
393 return MRI.createVirtualRegister(RC);
396 unsigned FastISel::FastEmitInst_(unsigned MachineInstOpcode,
397 const TargetRegisterClass* RC) {
398 unsigned ResultReg = createResultReg(RC);
399 const TargetInstrDesc &II = TII.get(MachineInstOpcode);
401 BuildMI(MBB, II, ResultReg);
405 unsigned FastISel::FastEmitInst_r(unsigned MachineInstOpcode,
406 const TargetRegisterClass *RC,
408 unsigned ResultReg = createResultReg(RC);
409 const TargetInstrDesc &II = TII.get(MachineInstOpcode);
411 BuildMI(MBB, II, ResultReg).addReg(Op0);
415 unsigned FastISel::FastEmitInst_rr(unsigned MachineInstOpcode,
416 const TargetRegisterClass *RC,
417 unsigned Op0, unsigned Op1) {
418 unsigned ResultReg = createResultReg(RC);
419 const TargetInstrDesc &II = TII.get(MachineInstOpcode);
421 BuildMI(MBB, II, ResultReg).addReg(Op0).addReg(Op1);
425 unsigned FastISel::FastEmitInst_ri(unsigned MachineInstOpcode,
426 const TargetRegisterClass *RC,
427 unsigned Op0, uint64_t Imm) {
428 unsigned ResultReg = createResultReg(RC);
429 const TargetInstrDesc &II = TII.get(MachineInstOpcode);
431 BuildMI(MBB, II, ResultReg).addReg(Op0).addImm(Imm);
435 unsigned FastISel::FastEmitInst_rri(unsigned MachineInstOpcode,
436 const TargetRegisterClass *RC,
437 unsigned Op0, unsigned Op1, uint64_t Imm) {
438 unsigned ResultReg = createResultReg(RC);
439 const TargetInstrDesc &II = TII.get(MachineInstOpcode);
441 BuildMI(MBB, II, ResultReg).addReg(Op0).addReg(Op1).addImm(Imm);
445 unsigned FastISel::FastEmitInst_i(unsigned MachineInstOpcode,
446 const TargetRegisterClass *RC,
448 unsigned ResultReg = createResultReg(RC);
449 const TargetInstrDesc &II = TII.get(MachineInstOpcode);
451 BuildMI(MBB, II, ResultReg).addImm(Imm);