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 unsigned FastISel::getRegForValue(Value *V) {
25 // Look up the value to see if we already have a register for it. We
26 // cache values defined by Instructions across blocks, and other values
27 // only locally. This is because Instructions already have the SSA
28 // def-dominatess-use requirement enforced.
29 if (ValueMap.count(V))
31 unsigned Reg = LocalValueMap[V];
35 MVT::SimpleValueType VT = TLI.getValueType(V->getType()).getSimpleVT();
36 if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
37 if (CI->getValue().getActiveBits() > 64)
38 return TargetMaterializeConstant(CI,
39 MBB->getParent()->getConstantPool());
40 // Don't cache constant materializations. To do so would require
41 // tracking what uses they dominate.
42 Reg = FastEmit_i(VT, VT, ISD::Constant, CI->getZExtValue());
43 } else if (isa<ConstantPointerNull>(V)) {
44 Reg = FastEmit_i(VT, VT, ISD::Constant, 0);
45 } else if (ConstantFP *CF = dyn_cast<ConstantFP>(V)) {
46 Reg = FastEmit_f(VT, VT, ISD::ConstantFP, CF);
49 const APFloat &Flt = CF->getValueAPF();
50 MVT IntVT = TLI.getPointerTy();
53 uint32_t IntBitWidth = IntVT.getSizeInBits();
54 if (Flt.convertToInteger(x, IntBitWidth, /*isSigned=*/true,
55 APFloat::rmTowardZero) != APFloat::opOK)
56 return TargetMaterializeConstant(CF,
57 MBB->getParent()->getConstantPool());
58 APInt IntVal(IntBitWidth, 2, x);
60 unsigned IntegerReg = FastEmit_i(IntVT.getSimpleVT(), IntVT.getSimpleVT(),
61 ISD::Constant, IntVal.getZExtValue());
63 return TargetMaterializeConstant(CF,
64 MBB->getParent()->getConstantPool());
65 Reg = FastEmit_r(IntVT.getSimpleVT(), VT, ISD::SINT_TO_FP, IntegerReg);
67 return TargetMaterializeConstant(CF,
68 MBB->getParent()->getConstantPool());;
70 } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) {
71 if (!SelectOperator(CE, CE->getOpcode())) return 0;
72 Reg = LocalValueMap[CE];
73 } else if (isa<UndefValue>(V)) {
74 Reg = createResultReg(TLI.getRegClassFor(VT));
75 BuildMI(MBB, TII.get(TargetInstrInfo::IMPLICIT_DEF), Reg);
80 if (!Reg && isa<Constant>(V))
81 return TargetMaterializeConstant(cast<Constant>(V),
82 MBB->getParent()->getConstantPool());
84 LocalValueMap[V] = Reg;
88 /// UpdateValueMap - Update the value map to include the new mapping for this
89 /// instruction, or insert an extra copy to get the result in a previous
90 /// determined register.
91 /// NOTE: This is only necessary because we might select a block that uses
92 /// a value before we select the block that defines the value. It might be
93 /// possible to fix this by selecting blocks in reverse postorder.
94 void FastISel::UpdateValueMap(Value* I, unsigned Reg) {
95 if (!isa<Instruction>(I)) {
96 LocalValueMap[I] = Reg;
99 if (!ValueMap.count(I))
102 TII.copyRegToReg(*MBB, MBB->end(), ValueMap[I],
103 Reg, MRI.getRegClass(Reg), MRI.getRegClass(Reg));
106 /// SelectBinaryOp - Select and emit code for a binary operator instruction,
107 /// which has an opcode which directly corresponds to the given ISD opcode.
109 bool FastISel::SelectBinaryOp(User *I, ISD::NodeType ISDOpcode) {
110 MVT VT = MVT::getMVT(I->getType(), /*HandleUnknown=*/true);
111 if (VT == MVT::Other || !VT.isSimple())
112 // Unhandled type. Halt "fast" selection and bail.
115 // We only handle legal types. For example, on x86-32 the instruction
116 // selector contains all of the 64-bit instructions from x86-64,
117 // under the assumption that i64 won't be used if the target doesn't
119 if (!TLI.isTypeLegal(VT)) {
120 // MVT::i1 is special. Allow AND and OR (but not XOR) because they
121 // don't require additional zeroing, which makes them easy.
123 (ISDOpcode == ISD::AND || ISDOpcode == ISD::OR))
124 VT = TLI.getTypeToTransformTo(VT);
129 unsigned Op0 = getRegForValue(I->getOperand(0));
131 // Unhandled operand. Halt "fast" selection and bail.
134 // Check if the second operand is a constant and handle it appropriately.
135 if (ConstantInt *CI = dyn_cast<ConstantInt>(I->getOperand(1))) {
136 unsigned ResultReg = FastEmit_ri(VT.getSimpleVT(), VT.getSimpleVT(),
137 ISDOpcode, Op0, CI->getZExtValue());
138 if (ResultReg != 0) {
139 // We successfully emitted code for the given LLVM Instruction.
140 UpdateValueMap(I, ResultReg);
145 // Check if the second operand is a constant float.
146 if (ConstantFP *CF = dyn_cast<ConstantFP>(I->getOperand(1))) {
147 unsigned ResultReg = FastEmit_rf(VT.getSimpleVT(), VT.getSimpleVT(),
149 if (ResultReg != 0) {
150 // We successfully emitted code for the given LLVM Instruction.
151 UpdateValueMap(I, ResultReg);
156 unsigned Op1 = getRegForValue(I->getOperand(1));
158 // Unhandled operand. Halt "fast" selection and bail.
161 // Now we have both operands in registers. Emit the instruction.
162 unsigned ResultReg = FastEmit_rr(VT.getSimpleVT(), VT.getSimpleVT(),
163 ISDOpcode, Op0, Op1);
165 // Target-specific code wasn't able to find a machine opcode for
166 // the given ISD opcode and type. Halt "fast" selection and bail.
169 // We successfully emitted code for the given LLVM Instruction.
170 UpdateValueMap(I, ResultReg);
174 bool FastISel::SelectGetElementPtr(User *I) {
175 unsigned N = getRegForValue(I->getOperand(0));
177 // Unhandled operand. Halt "fast" selection and bail.
180 const Type *Ty = I->getOperand(0)->getType();
181 MVT::SimpleValueType VT = TLI.getPointerTy().getSimpleVT();
182 for (GetElementPtrInst::op_iterator OI = I->op_begin()+1, E = I->op_end();
185 if (const StructType *StTy = dyn_cast<StructType>(Ty)) {
186 unsigned Field = cast<ConstantInt>(Idx)->getZExtValue();
189 uint64_t Offs = TD.getStructLayout(StTy)->getElementOffset(Field);
190 // FIXME: This can be optimized by combining the add with a
192 N = FastEmit_ri_(VT, ISD::ADD, N, Offs, VT);
194 // Unhandled operand. Halt "fast" selection and bail.
197 Ty = StTy->getElementType(Field);
199 Ty = cast<SequentialType>(Ty)->getElementType();
201 // If this is a constant subscript, handle it quickly.
202 if (ConstantInt *CI = dyn_cast<ConstantInt>(Idx)) {
203 if (CI->getZExtValue() == 0) continue;
205 TD.getABITypeSize(Ty)*cast<ConstantInt>(CI)->getSExtValue();
206 N = FastEmit_ri_(VT, ISD::ADD, N, Offs, VT);
208 // Unhandled operand. Halt "fast" selection and bail.
213 // N = N + Idx * ElementSize;
214 uint64_t ElementSize = TD.getABITypeSize(Ty);
215 unsigned IdxN = getRegForValue(Idx);
217 // Unhandled operand. Halt "fast" selection and bail.
220 // If the index is smaller or larger than intptr_t, truncate or extend
222 MVT IdxVT = MVT::getMVT(Idx->getType(), /*HandleUnknown=*/false);
223 if (IdxVT.bitsLT(VT))
224 IdxN = FastEmit_r(IdxVT.getSimpleVT(), VT, ISD::SIGN_EXTEND, IdxN);
225 else if (IdxVT.bitsGT(VT))
226 IdxN = FastEmit_r(IdxVT.getSimpleVT(), VT, ISD::TRUNCATE, IdxN);
228 // Unhandled operand. Halt "fast" selection and bail.
231 if (ElementSize != 1) {
232 IdxN = FastEmit_ri_(VT, ISD::MUL, IdxN, ElementSize, VT);
234 // Unhandled operand. Halt "fast" selection and bail.
237 N = FastEmit_rr(VT, VT, ISD::ADD, N, IdxN);
239 // Unhandled operand. Halt "fast" selection and bail.
244 // We successfully emitted code for the given LLVM Instruction.
245 UpdateValueMap(I, N);
249 bool FastISel::SelectCast(User *I, ISD::NodeType Opcode) {
250 MVT SrcVT = TLI.getValueType(I->getOperand(0)->getType());
251 MVT DstVT = TLI.getValueType(I->getType());
253 if (SrcVT == MVT::Other || !SrcVT.isSimple() ||
254 DstVT == MVT::Other || !DstVT.isSimple() ||
255 !TLI.isTypeLegal(SrcVT) || !TLI.isTypeLegal(DstVT))
256 // Unhandled type. Halt "fast" selection and bail.
259 unsigned InputReg = getRegForValue(I->getOperand(0));
261 // Unhandled operand. Halt "fast" selection and bail.
264 unsigned ResultReg = FastEmit_r(SrcVT.getSimpleVT(),
271 UpdateValueMap(I, ResultReg);
275 bool FastISel::SelectBitCast(User *I) {
276 // If the bitcast doesn't change the type, just use the operand value.
277 if (I->getType() == I->getOperand(0)->getType()) {
278 unsigned Reg = getRegForValue(I->getOperand(0));
281 UpdateValueMap(I, Reg);
285 // Bitcasts of other values become reg-reg copies or BIT_CONVERT operators.
286 MVT SrcVT = TLI.getValueType(I->getOperand(0)->getType());
287 MVT DstVT = TLI.getValueType(I->getType());
289 if (SrcVT == MVT::Other || !SrcVT.isSimple() ||
290 DstVT == MVT::Other || !DstVT.isSimple() ||
291 !TLI.isTypeLegal(SrcVT) || !TLI.isTypeLegal(DstVT))
292 // Unhandled type. Halt "fast" selection and bail.
295 unsigned Op0 = getRegForValue(I->getOperand(0));
297 // Unhandled operand. Halt "fast" selection and bail.
300 // First, try to perform the bitcast by inserting a reg-reg copy.
301 unsigned ResultReg = 0;
302 if (SrcVT.getSimpleVT() == DstVT.getSimpleVT()) {
303 TargetRegisterClass* SrcClass = TLI.getRegClassFor(SrcVT);
304 TargetRegisterClass* DstClass = TLI.getRegClassFor(DstVT);
305 ResultReg = createResultReg(DstClass);
307 bool InsertedCopy = TII.copyRegToReg(*MBB, MBB->end(), ResultReg,
308 Op0, DstClass, SrcClass);
313 // If the reg-reg copy failed, select a BIT_CONVERT opcode.
315 ResultReg = FastEmit_r(SrcVT.getSimpleVT(), DstVT.getSimpleVT(),
316 ISD::BIT_CONVERT, Op0);
321 UpdateValueMap(I, ResultReg);
326 FastISel::SelectInstruction(Instruction *I) {
327 return SelectOperator(I, I->getOpcode());
331 FastISel::SelectOperator(User *I, unsigned Opcode) {
333 case Instruction::Add: {
334 ISD::NodeType Opc = I->getType()->isFPOrFPVector() ? ISD::FADD : ISD::ADD;
335 return SelectBinaryOp(I, Opc);
337 case Instruction::Sub: {
338 ISD::NodeType Opc = I->getType()->isFPOrFPVector() ? ISD::FSUB : ISD::SUB;
339 return SelectBinaryOp(I, Opc);
341 case Instruction::Mul: {
342 ISD::NodeType Opc = I->getType()->isFPOrFPVector() ? ISD::FMUL : ISD::MUL;
343 return SelectBinaryOp(I, Opc);
345 case Instruction::SDiv:
346 return SelectBinaryOp(I, ISD::SDIV);
347 case Instruction::UDiv:
348 return SelectBinaryOp(I, ISD::UDIV);
349 case Instruction::FDiv:
350 return SelectBinaryOp(I, ISD::FDIV);
351 case Instruction::SRem:
352 return SelectBinaryOp(I, ISD::SREM);
353 case Instruction::URem:
354 return SelectBinaryOp(I, ISD::UREM);
355 case Instruction::FRem:
356 return SelectBinaryOp(I, ISD::FREM);
357 case Instruction::Shl:
358 return SelectBinaryOp(I, ISD::SHL);
359 case Instruction::LShr:
360 return SelectBinaryOp(I, ISD::SRL);
361 case Instruction::AShr:
362 return SelectBinaryOp(I, ISD::SRA);
363 case Instruction::And:
364 return SelectBinaryOp(I, ISD::AND);
365 case Instruction::Or:
366 return SelectBinaryOp(I, ISD::OR);
367 case Instruction::Xor:
368 return SelectBinaryOp(I, ISD::XOR);
370 case Instruction::GetElementPtr:
371 return SelectGetElementPtr(I);
373 case Instruction::Br: {
374 BranchInst *BI = cast<BranchInst>(I);
376 if (BI->isUnconditional()) {
377 MachineFunction::iterator NextMBB =
378 next(MachineFunction::iterator(MBB));
379 BasicBlock *LLVMSucc = BI->getSuccessor(0);
380 MachineBasicBlock *MSucc = MBBMap[LLVMSucc];
382 if (NextMBB != MF.end() && MSucc == NextMBB) {
383 // The unconditional fall-through case, which needs no instructions.
385 // The unconditional branch case.
386 TII.InsertBranch(*MBB, MSucc, NULL, SmallVector<MachineOperand, 0>());
388 MBB->addSuccessor(MSucc);
392 // Conditional branches are not handed yet.
393 // Halt "fast" selection and bail.
397 case Instruction::Unreachable:
401 case Instruction::PHI:
402 // PHI nodes are already emitted.
405 case Instruction::BitCast:
406 return SelectBitCast(I);
408 case Instruction::FPToSI:
409 return SelectCast(I, ISD::FP_TO_SINT);
410 case Instruction::ZExt:
411 return SelectCast(I, ISD::ZERO_EXTEND);
412 case Instruction::SExt:
413 return SelectCast(I, ISD::SIGN_EXTEND);
414 case Instruction::Trunc:
415 return SelectCast(I, ISD::TRUNCATE);
416 case Instruction::SIToFP:
417 return SelectCast(I, ISD::SINT_TO_FP);
419 case Instruction::IntToPtr: // Deliberate fall-through.
420 case Instruction::PtrToInt: {
421 MVT SrcVT = TLI.getValueType(I->getOperand(0)->getType());
422 MVT DstVT = TLI.getValueType(I->getType());
423 if (DstVT.bitsGT(SrcVT))
424 return SelectCast(I, ISD::ZERO_EXTEND);
425 if (DstVT.bitsLT(SrcVT))
426 return SelectCast(I, ISD::TRUNCATE);
427 unsigned Reg = getRegForValue(I->getOperand(0));
428 if (Reg == 0) return false;
429 UpdateValueMap(I, Reg);
434 // Unhandled instruction. Halt "fast" selection and bail.
439 FastISel::FastISel(MachineFunction &mf,
440 DenseMap<const Value *, unsigned> &vm,
441 DenseMap<const BasicBlock *, MachineBasicBlock *> &bm)
446 MRI(MF.getRegInfo()),
448 TD(*TM.getTargetData()),
449 TII(*TM.getInstrInfo()),
450 TLI(*TM.getTargetLowering()) {
453 FastISel::~FastISel() {}
455 unsigned FastISel::FastEmit_(MVT::SimpleValueType, MVT::SimpleValueType,
460 unsigned FastISel::FastEmit_r(MVT::SimpleValueType, MVT::SimpleValueType,
461 ISD::NodeType, unsigned /*Op0*/) {
465 unsigned FastISel::FastEmit_rr(MVT::SimpleValueType, MVT::SimpleValueType,
466 ISD::NodeType, unsigned /*Op0*/,
471 unsigned FastISel::FastEmit_i(MVT::SimpleValueType, MVT::SimpleValueType,
472 ISD::NodeType, uint64_t /*Imm*/) {
476 unsigned FastISel::FastEmit_f(MVT::SimpleValueType, MVT::SimpleValueType,
477 ISD::NodeType, ConstantFP * /*FPImm*/) {
481 unsigned FastISel::FastEmit_ri(MVT::SimpleValueType, MVT::SimpleValueType,
482 ISD::NodeType, unsigned /*Op0*/,
487 unsigned FastISel::FastEmit_rf(MVT::SimpleValueType, MVT::SimpleValueType,
488 ISD::NodeType, unsigned /*Op0*/,
489 ConstantFP * /*FPImm*/) {
493 unsigned FastISel::FastEmit_rri(MVT::SimpleValueType, MVT::SimpleValueType,
495 unsigned /*Op0*/, unsigned /*Op1*/,
500 /// FastEmit_ri_ - This method is a wrapper of FastEmit_ri. It first tries
501 /// to emit an instruction with an immediate operand using FastEmit_ri.
502 /// If that fails, it materializes the immediate into a register and try
503 /// FastEmit_rr instead.
504 unsigned FastISel::FastEmit_ri_(MVT::SimpleValueType VT, ISD::NodeType Opcode,
505 unsigned Op0, uint64_t Imm,
506 MVT::SimpleValueType ImmType) {
507 // First check if immediate type is legal. If not, we can't use the ri form.
508 unsigned ResultReg = FastEmit_ri(VT, VT, Opcode, Op0, Imm);
511 unsigned MaterialReg = FastEmit_i(ImmType, ImmType, ISD::Constant, Imm);
512 if (MaterialReg == 0)
514 return FastEmit_rr(VT, VT, Opcode, Op0, MaterialReg);
517 /// FastEmit_rf_ - This method is a wrapper of FastEmit_ri. It first tries
518 /// to emit an instruction with a floating-point immediate operand using
519 /// FastEmit_rf. If that fails, it materializes the immediate into a register
520 /// and try FastEmit_rr instead.
521 unsigned FastISel::FastEmit_rf_(MVT::SimpleValueType VT, ISD::NodeType Opcode,
522 unsigned Op0, ConstantFP *FPImm,
523 MVT::SimpleValueType ImmType) {
524 // First check if immediate type is legal. If not, we can't use the rf form.
525 unsigned ResultReg = FastEmit_rf(VT, VT, Opcode, Op0, FPImm);
529 // Materialize the constant in a register.
530 unsigned MaterialReg = FastEmit_f(ImmType, ImmType, ISD::ConstantFP, FPImm);
531 if (MaterialReg == 0) {
532 // If the target doesn't have a way to directly enter a floating-point
533 // value into a register, use an alternate approach.
534 // TODO: The current approach only supports floating-point constants
535 // that can be constructed by conversion from integer values. This should
536 // be replaced by code that creates a load from a constant-pool entry,
537 // which will require some target-specific work.
538 const APFloat &Flt = FPImm->getValueAPF();
539 MVT IntVT = TLI.getPointerTy();
542 uint32_t IntBitWidth = IntVT.getSizeInBits();
543 if (Flt.convertToInteger(x, IntBitWidth, /*isSigned=*/true,
544 APFloat::rmTowardZero) != APFloat::opOK)
546 APInt IntVal(IntBitWidth, 2, x);
548 unsigned IntegerReg = FastEmit_i(IntVT.getSimpleVT(), IntVT.getSimpleVT(),
549 ISD::Constant, IntVal.getZExtValue());
552 MaterialReg = FastEmit_r(IntVT.getSimpleVT(), VT,
553 ISD::SINT_TO_FP, IntegerReg);
554 if (MaterialReg == 0)
557 return FastEmit_rr(VT, VT, Opcode, Op0, MaterialReg);
560 unsigned FastISel::createResultReg(const TargetRegisterClass* RC) {
561 return MRI.createVirtualRegister(RC);
564 unsigned FastISel::FastEmitInst_(unsigned MachineInstOpcode,
565 const TargetRegisterClass* RC) {
566 unsigned ResultReg = createResultReg(RC);
567 const TargetInstrDesc &II = TII.get(MachineInstOpcode);
569 BuildMI(MBB, II, ResultReg);
573 unsigned FastISel::FastEmitInst_r(unsigned MachineInstOpcode,
574 const TargetRegisterClass *RC,
576 unsigned ResultReg = createResultReg(RC);
577 const TargetInstrDesc &II = TII.get(MachineInstOpcode);
579 BuildMI(MBB, II, ResultReg).addReg(Op0);
583 unsigned FastISel::FastEmitInst_rr(unsigned MachineInstOpcode,
584 const TargetRegisterClass *RC,
585 unsigned Op0, unsigned Op1) {
586 unsigned ResultReg = createResultReg(RC);
587 const TargetInstrDesc &II = TII.get(MachineInstOpcode);
589 BuildMI(MBB, II, ResultReg).addReg(Op0).addReg(Op1);
593 unsigned FastISel::FastEmitInst_ri(unsigned MachineInstOpcode,
594 const TargetRegisterClass *RC,
595 unsigned Op0, uint64_t Imm) {
596 unsigned ResultReg = createResultReg(RC);
597 const TargetInstrDesc &II = TII.get(MachineInstOpcode);
599 BuildMI(MBB, II, ResultReg).addReg(Op0).addImm(Imm);
603 unsigned FastISel::FastEmitInst_rf(unsigned MachineInstOpcode,
604 const TargetRegisterClass *RC,
605 unsigned Op0, ConstantFP *FPImm) {
606 unsigned ResultReg = createResultReg(RC);
607 const TargetInstrDesc &II = TII.get(MachineInstOpcode);
609 BuildMI(MBB, II, ResultReg).addReg(Op0).addFPImm(FPImm);
613 unsigned FastISel::FastEmitInst_rri(unsigned MachineInstOpcode,
614 const TargetRegisterClass *RC,
615 unsigned Op0, unsigned Op1, uint64_t Imm) {
616 unsigned ResultReg = createResultReg(RC);
617 const TargetInstrDesc &II = TII.get(MachineInstOpcode);
619 BuildMI(MBB, II, ResultReg).addReg(Op0).addReg(Op1).addImm(Imm);
623 unsigned FastISel::FastEmitInst_i(unsigned MachineInstOpcode,
624 const TargetRegisterClass *RC,
626 unsigned ResultReg = createResultReg(RC);
627 const TargetInstrDesc &II = TII.get(MachineInstOpcode);
629 BuildMI(MBB, II, ResultReg).addImm(Imm);
633 unsigned FastISel::FastEmitInst_extractsubreg(unsigned Op0, uint32_t Idx) {
634 const TargetRegisterClass* RC = MRI.getRegClass(Op0);
635 const TargetRegisterClass* SRC = *(RC->subregclasses_begin()+Idx-1);
637 unsigned ResultReg = createResultReg(SRC);
638 const TargetInstrDesc &II = TII.get(TargetInstrInfo::EXTRACT_SUBREG);
640 BuildMI(MBB, II, ResultReg).addReg(Op0).addImm(Idx);