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 // "Fast" instruction selection is designed to emit very poor code quickly.
13 // Also, it is not designed to be able to do much lowering, so most illegal
14 // types (e.g. i64 on 32-bit targets) and operations are not supported. It is
15 // also not intended to be able to do much optimization, except in a few cases
16 // where doing optimizations reduces overall compile time. For example, folding
17 // constants into immediate fields is often done, because it's cheap and it
18 // reduces the number of instructions later phases have to examine.
20 // "Fast" instruction selection is able to fail gracefully and transfer
21 // control to the SelectionDAG selector for operations that it doesn't
22 // support. In many cases, this allows us to avoid duplicating a lot of
23 // the complicated lowering logic that SelectionDAG currently has.
25 // The intended use for "fast" instruction selection is "-O0" mode
26 // compilation, where the quality of the generated code is irrelevant when
27 // weighed against the speed at which the code can be generated. Also,
28 // at -O0, the LLVM optimizers are not running, and this makes the
29 // compile time of codegen a much higher portion of the overall compile
30 // time. Despite its limitations, "fast" instruction selection is able to
31 // handle enough code on its own to provide noticeable overall speedups
34 // Basic operations are supported in a target-independent way, by reading
35 // the same instruction descriptions that the SelectionDAG selector reads,
36 // and identifying simple arithmetic operations that can be directly selected
37 // from simple operators. More complicated operations currently require
38 // target-specific code.
40 //===----------------------------------------------------------------------===//
42 #include "llvm/Function.h"
43 #include "llvm/GlobalVariable.h"
44 #include "llvm/Instructions.h"
45 #include "llvm/IntrinsicInst.h"
46 #include "llvm/CodeGen/FastISel.h"
47 #include "llvm/CodeGen/MachineInstrBuilder.h"
48 #include "llvm/CodeGen/MachineModuleInfo.h"
49 #include "llvm/CodeGen/MachineRegisterInfo.h"
50 #include "llvm/Analysis/DebugInfo.h"
51 #include "llvm/Target/TargetData.h"
52 #include "llvm/Target/TargetInstrInfo.h"
53 #include "llvm/Target/TargetLowering.h"
54 #include "llvm/Target/TargetMachine.h"
55 #include "llvm/Support/ErrorHandling.h"
56 #include "FunctionLoweringInfo.h"
59 unsigned FastISel::getRegForValue(const Value *V) {
60 EVT RealVT = TLI.getValueType(V->getType(), /*AllowUnknown=*/true);
61 // Don't handle non-simple values in FastISel.
62 if (!RealVT.isSimple())
65 // Ignore illegal types. We must do this before looking up the value
66 // in ValueMap because Arguments are given virtual registers regardless
67 // of whether FastISel can handle them.
68 MVT VT = RealVT.getSimpleVT();
69 if (!TLI.isTypeLegal(VT)) {
70 // Promote MVT::i1 to a legal type though, because it's common and easy.
72 VT = TLI.getTypeToTransformTo(V->getContext(), VT).getSimpleVT();
77 // Look up the value to see if we already have a register for it. We
78 // cache values defined by Instructions across blocks, and other values
79 // only locally. This is because Instructions already have the SSA
80 // def-dominates-use requirement enforced.
81 if (ValueMap.count(V))
83 unsigned Reg = LocalValueMap[V];
87 // In bottom-up mode, just create the virtual register which will be used
88 // to hold the value. It will be materialized later.
90 Reg = createResultReg(TLI.getRegClassFor(VT));
91 if (isa<Instruction>(V))
94 LocalValueMap[V] = Reg;
98 return materializeRegForValue(V, VT);
101 /// materializeRegForValue - Helper for getRegForVale. This function is
102 /// called when the value isn't already available in a register and must
103 /// be materialized with new instructions.
104 unsigned FastISel::materializeRegForValue(const Value *V, MVT VT) {
107 if (const ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
108 if (CI->getValue().getActiveBits() <= 64)
109 Reg = FastEmit_i(VT, VT, ISD::Constant, CI->getZExtValue());
110 } else if (isa<AllocaInst>(V)) {
111 Reg = TargetMaterializeAlloca(cast<AllocaInst>(V));
112 } else if (isa<ConstantPointerNull>(V)) {
113 // Translate this as an integer zero so that it can be
114 // local-CSE'd with actual integer zeros.
116 getRegForValue(Constant::getNullValue(TD.getIntPtrType(V->getContext())));
117 } else if (const ConstantFP *CF = dyn_cast<ConstantFP>(V)) {
118 // Try to emit the constant directly.
119 Reg = FastEmit_f(VT, VT, ISD::ConstantFP, CF);
122 // Try to emit the constant by using an integer constant with a cast.
123 const APFloat &Flt = CF->getValueAPF();
124 EVT IntVT = TLI.getPointerTy();
127 uint32_t IntBitWidth = IntVT.getSizeInBits();
129 (void) Flt.convertToInteger(x, IntBitWidth, /*isSigned=*/true,
130 APFloat::rmTowardZero, &isExact);
132 APInt IntVal(IntBitWidth, 2, x);
134 unsigned IntegerReg =
135 getRegForValue(ConstantInt::get(V->getContext(), IntVal));
137 Reg = FastEmit_r(IntVT.getSimpleVT(), VT, ISD::SINT_TO_FP, IntegerReg);
140 } else if (const Operator *Op = dyn_cast<Operator>(V)) {
141 if (!SelectOperator(Op, Op->getOpcode())) return 0;
142 Reg = LocalValueMap[Op];
143 } else if (isa<UndefValue>(V)) {
144 Reg = createResultReg(TLI.getRegClassFor(VT));
145 BuildMI(MBB, DL, TII.get(TargetOpcode::IMPLICIT_DEF), Reg);
148 // If target-independent code couldn't handle the value, give target-specific
150 if (!Reg && isa<Constant>(V))
151 Reg = TargetMaterializeConstant(cast<Constant>(V));
153 // Don't cache constant materializations in the general ValueMap.
154 // To do so would require tracking what uses they dominate.
156 LocalValueMap[V] = Reg;
160 unsigned FastISel::lookUpRegForValue(const Value *V) {
161 // Look up the value to see if we already have a register for it. We
162 // cache values defined by Instructions across blocks, and other values
163 // only locally. This is because Instructions already have the SSA
164 // def-dominates-use requirement enforced.
165 if (ValueMap.count(V))
167 return LocalValueMap[V];
170 /// UpdateValueMap - Update the value map to include the new mapping for this
171 /// instruction, or insert an extra copy to get the result in a previous
172 /// determined register.
173 /// NOTE: This is only necessary because we might select a block that uses
174 /// a value before we select the block that defines the value. It might be
175 /// possible to fix this by selecting blocks in reverse postorder.
176 unsigned FastISel::UpdateValueMap(const Value *I, unsigned Reg) {
177 if (!isa<Instruction>(I)) {
178 LocalValueMap[I] = Reg;
182 unsigned &AssignedReg = ValueMap[I];
183 if (AssignedReg == 0)
185 else if (Reg != AssignedReg) {
186 const TargetRegisterClass *RegClass = MRI.getRegClass(Reg);
187 TII.copyRegToReg(*MBB, MBB->end(), AssignedReg,
188 Reg, RegClass, RegClass, DL);
193 unsigned FastISel::getRegForGEPIndex(const Value *Idx) {
194 unsigned IdxN = getRegForValue(Idx);
196 // Unhandled operand. Halt "fast" selection and bail.
199 // If the index is smaller or larger than intptr_t, truncate or extend it.
200 MVT PtrVT = TLI.getPointerTy();
201 EVT IdxVT = EVT::getEVT(Idx->getType(), /*HandleUnknown=*/false);
202 if (IdxVT.bitsLT(PtrVT))
203 IdxN = FastEmit_r(IdxVT.getSimpleVT(), PtrVT, ISD::SIGN_EXTEND, IdxN);
204 else if (IdxVT.bitsGT(PtrVT))
205 IdxN = FastEmit_r(IdxVT.getSimpleVT(), PtrVT, ISD::TRUNCATE, IdxN);
209 /// SelectBinaryOp - Select and emit code for a binary operator instruction,
210 /// which has an opcode which directly corresponds to the given ISD opcode.
212 bool FastISel::SelectBinaryOp(const User *I, unsigned ISDOpcode) {
213 EVT VT = EVT::getEVT(I->getType(), /*HandleUnknown=*/true);
214 if (VT == MVT::Other || !VT.isSimple())
215 // Unhandled type. Halt "fast" selection and bail.
218 // We only handle legal types. For example, on x86-32 the instruction
219 // selector contains all of the 64-bit instructions from x86-64,
220 // under the assumption that i64 won't be used if the target doesn't
222 if (!TLI.isTypeLegal(VT)) {
223 // MVT::i1 is special. Allow AND, OR, or XOR because they
224 // don't require additional zeroing, which makes them easy.
226 (ISDOpcode == ISD::AND || ISDOpcode == ISD::OR ||
227 ISDOpcode == ISD::XOR))
228 VT = TLI.getTypeToTransformTo(I->getContext(), VT);
233 unsigned Op0 = getRegForValue(I->getOperand(0));
235 // Unhandled operand. Halt "fast" selection and bail.
238 // Check if the second operand is a constant and handle it appropriately.
239 if (ConstantInt *CI = dyn_cast<ConstantInt>(I->getOperand(1))) {
240 unsigned ResultReg = FastEmit_ri(VT.getSimpleVT(), VT.getSimpleVT(),
241 ISDOpcode, Op0, CI->getZExtValue());
242 if (ResultReg != 0) {
243 // We successfully emitted code for the given LLVM Instruction.
244 UpdateValueMap(I, ResultReg);
249 // Check if the second operand is a constant float.
250 if (ConstantFP *CF = dyn_cast<ConstantFP>(I->getOperand(1))) {
251 unsigned ResultReg = FastEmit_rf(VT.getSimpleVT(), VT.getSimpleVT(),
253 if (ResultReg != 0) {
254 // We successfully emitted code for the given LLVM Instruction.
255 UpdateValueMap(I, ResultReg);
260 unsigned Op1 = getRegForValue(I->getOperand(1));
262 // Unhandled operand. Halt "fast" selection and bail.
265 // Now we have both operands in registers. Emit the instruction.
266 unsigned ResultReg = FastEmit_rr(VT.getSimpleVT(), VT.getSimpleVT(),
267 ISDOpcode, Op0, Op1);
269 // Target-specific code wasn't able to find a machine opcode for
270 // the given ISD opcode and type. Halt "fast" selection and bail.
273 // We successfully emitted code for the given LLVM Instruction.
274 UpdateValueMap(I, ResultReg);
278 bool FastISel::SelectGetElementPtr(const User *I) {
279 unsigned N = getRegForValue(I->getOperand(0));
281 // Unhandled operand. Halt "fast" selection and bail.
284 const Type *Ty = I->getOperand(0)->getType();
285 MVT VT = TLI.getPointerTy();
286 for (GetElementPtrInst::const_op_iterator OI = I->op_begin()+1,
287 E = I->op_end(); OI != E; ++OI) {
288 const Value *Idx = *OI;
289 if (const StructType *StTy = dyn_cast<StructType>(Ty)) {
290 unsigned Field = cast<ConstantInt>(Idx)->getZExtValue();
293 uint64_t Offs = TD.getStructLayout(StTy)->getElementOffset(Field);
294 // FIXME: This can be optimized by combining the add with a
296 N = FastEmit_ri_(VT, ISD::ADD, N, Offs, VT);
298 // Unhandled operand. Halt "fast" selection and bail.
301 Ty = StTy->getElementType(Field);
303 Ty = cast<SequentialType>(Ty)->getElementType();
305 // If this is a constant subscript, handle it quickly.
306 if (const ConstantInt *CI = dyn_cast<ConstantInt>(Idx)) {
307 if (CI->getZExtValue() == 0) continue;
309 TD.getTypeAllocSize(Ty)*cast<ConstantInt>(CI)->getSExtValue();
310 N = FastEmit_ri_(VT, ISD::ADD, N, Offs, VT);
312 // Unhandled operand. Halt "fast" selection and bail.
317 // N = N + Idx * ElementSize;
318 uint64_t ElementSize = TD.getTypeAllocSize(Ty);
319 unsigned IdxN = getRegForGEPIndex(Idx);
321 // Unhandled operand. Halt "fast" selection and bail.
324 if (ElementSize != 1) {
325 IdxN = FastEmit_ri_(VT, ISD::MUL, IdxN, ElementSize, VT);
327 // Unhandled operand. Halt "fast" selection and bail.
330 N = FastEmit_rr(VT, VT, ISD::ADD, N, IdxN);
332 // Unhandled operand. Halt "fast" selection and bail.
337 // We successfully emitted code for the given LLVM Instruction.
338 UpdateValueMap(I, N);
342 bool FastISel::SelectCall(const User *I) {
343 const Function *F = cast<CallInst>(I)->getCalledFunction();
344 if (!F) return false;
346 // Handle selected intrinsic function calls.
347 unsigned IID = F->getIntrinsicID();
350 case Intrinsic::dbg_declare: {
351 const DbgDeclareInst *DI = cast<DbgDeclareInst>(I);
352 if (!DIVariable(DI->getVariable()).Verify() ||
353 !MF.getMMI().hasDebugInfo())
356 const Value *Address = DI->getAddress();
359 if (isa<UndefValue>(Address))
361 const AllocaInst *AI = dyn_cast<AllocaInst>(Address);
362 // Don't handle byval struct arguments or VLAs, for example.
363 // Note that if we have a byval struct argument, fast ISel is turned off;
364 // those are handled in SelectionDAGBuilder.
366 DenseMap<const AllocaInst*, int>::iterator SI =
367 StaticAllocaMap.find(AI);
368 if (SI == StaticAllocaMap.end()) break; // VLAs.
370 if (!DI->getDebugLoc().isUnknown())
371 MF.getMMI().setVariableDbgInfo(DI->getVariable(), FI, DI->getDebugLoc());
373 // Building the map above is target independent. Generating DBG_VALUE
374 // inline is target dependent; do this now.
375 (void)TargetSelectInstruction(cast<Instruction>(I));
378 case Intrinsic::dbg_value: {
379 // This form of DBG_VALUE is target-independent.
380 const DbgValueInst *DI = cast<DbgValueInst>(I);
381 const TargetInstrDesc &II = TII.get(TargetOpcode::DBG_VALUE);
382 const Value *V = DI->getValue();
384 // Currently the optimizer can produce this; insert an undef to
385 // help debugging. Probably the optimizer should not do this.
386 BuildMI(MBB, DL, II).addReg(0U).addImm(DI->getOffset()).
387 addMetadata(DI->getVariable());
388 } else if (const ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
389 BuildMI(MBB, DL, II).addImm(CI->getZExtValue()).addImm(DI->getOffset()).
390 addMetadata(DI->getVariable());
391 } else if (const ConstantFP *CF = dyn_cast<ConstantFP>(V)) {
392 BuildMI(MBB, DL, II).addFPImm(CF).addImm(DI->getOffset()).
393 addMetadata(DI->getVariable());
394 } else if (unsigned Reg = lookUpRegForValue(V)) {
395 BuildMI(MBB, DL, II).addReg(Reg, RegState::Debug).addImm(DI->getOffset()).
396 addMetadata(DI->getVariable());
398 // We can't yet handle anything else here because it would require
399 // generating code, thus altering codegen because of debug info.
400 // Insert an undef so we can see what we dropped.
401 BuildMI(MBB, DL, II).addReg(0U).addImm(DI->getOffset()).
402 addMetadata(DI->getVariable());
406 case Intrinsic::eh_exception: {
407 EVT VT = TLI.getValueType(I->getType());
408 switch (TLI.getOperationAction(ISD::EXCEPTIONADDR, VT)) {
410 case TargetLowering::Expand: {
411 assert(MBB->isLandingPad() && "Call to eh.exception not in landing pad!");
412 unsigned Reg = TLI.getExceptionAddressRegister();
413 const TargetRegisterClass *RC = TLI.getRegClassFor(VT);
414 unsigned ResultReg = createResultReg(RC);
415 bool InsertedCopy = TII.copyRegToReg(*MBB, MBB->end(), ResultReg,
417 assert(InsertedCopy && "Can't copy address registers!");
418 InsertedCopy = InsertedCopy;
419 UpdateValueMap(I, ResultReg);
425 case Intrinsic::eh_selector: {
426 EVT VT = TLI.getValueType(I->getType());
427 switch (TLI.getOperationAction(ISD::EHSELECTION, VT)) {
429 case TargetLowering::Expand: {
430 if (MBB->isLandingPad())
431 AddCatchInfo(*cast<CallInst>(I), &MF.getMMI(), MBB);
434 CatchInfoLost.insert(cast<CallInst>(I));
436 // FIXME: Mark exception selector register as live in. Hack for PR1508.
437 unsigned Reg = TLI.getExceptionSelectorRegister();
438 if (Reg) MBB->addLiveIn(Reg);
441 unsigned Reg = TLI.getExceptionSelectorRegister();
442 EVT SrcVT = TLI.getPointerTy();
443 const TargetRegisterClass *RC = TLI.getRegClassFor(SrcVT);
444 unsigned ResultReg = createResultReg(RC);
445 bool InsertedCopy = TII.copyRegToReg(*MBB, MBB->end(), ResultReg, Reg,
447 assert(InsertedCopy && "Can't copy address registers!");
448 InsertedCopy = InsertedCopy;
450 // Cast the register to the type of the selector.
451 if (SrcVT.bitsGT(MVT::i32))
452 ResultReg = FastEmit_r(SrcVT.getSimpleVT(), MVT::i32, ISD::TRUNCATE,
454 else if (SrcVT.bitsLT(MVT::i32))
455 ResultReg = FastEmit_r(SrcVT.getSimpleVT(), MVT::i32,
456 ISD::SIGN_EXTEND, ResultReg);
458 // Unhandled operand. Halt "fast" selection and bail.
461 UpdateValueMap(I, ResultReg);
470 // An arbitrary call. Bail.
474 bool FastISel::SelectCast(const User *I, unsigned Opcode) {
475 EVT SrcVT = TLI.getValueType(I->getOperand(0)->getType());
476 EVT DstVT = TLI.getValueType(I->getType());
478 if (SrcVT == MVT::Other || !SrcVT.isSimple() ||
479 DstVT == MVT::Other || !DstVT.isSimple())
480 // Unhandled type. Halt "fast" selection and bail.
483 // Check if the destination type is legal. Or as a special case,
484 // it may be i1 if we're doing a truncate because that's
485 // easy and somewhat common.
486 if (!TLI.isTypeLegal(DstVT))
487 if (DstVT != MVT::i1 || Opcode != ISD::TRUNCATE)
488 // Unhandled type. Halt "fast" selection and bail.
491 // Check if the source operand is legal. Or as a special case,
492 // it may be i1 if we're doing zero-extension because that's
493 // easy and somewhat common.
494 if (!TLI.isTypeLegal(SrcVT))
495 if (SrcVT != MVT::i1 || Opcode != ISD::ZERO_EXTEND)
496 // Unhandled type. Halt "fast" selection and bail.
499 unsigned InputReg = getRegForValue(I->getOperand(0));
501 // Unhandled operand. Halt "fast" selection and bail.
504 // If the operand is i1, arrange for the high bits in the register to be zero.
505 if (SrcVT == MVT::i1) {
506 SrcVT = TLI.getTypeToTransformTo(I->getContext(), SrcVT);
507 InputReg = FastEmitZExtFromI1(SrcVT.getSimpleVT(), InputReg);
511 // If the result is i1, truncate to the target's type for i1 first.
512 if (DstVT == MVT::i1)
513 DstVT = TLI.getTypeToTransformTo(I->getContext(), DstVT);
515 unsigned ResultReg = FastEmit_r(SrcVT.getSimpleVT(),
522 UpdateValueMap(I, ResultReg);
526 bool FastISel::SelectBitCast(const User *I) {
527 // If the bitcast doesn't change the type, just use the operand value.
528 if (I->getType() == I->getOperand(0)->getType()) {
529 unsigned Reg = getRegForValue(I->getOperand(0));
532 UpdateValueMap(I, Reg);
536 // Bitcasts of other values become reg-reg copies or BIT_CONVERT operators.
537 EVT SrcVT = TLI.getValueType(I->getOperand(0)->getType());
538 EVT DstVT = TLI.getValueType(I->getType());
540 if (SrcVT == MVT::Other || !SrcVT.isSimple() ||
541 DstVT == MVT::Other || !DstVT.isSimple() ||
542 !TLI.isTypeLegal(SrcVT) || !TLI.isTypeLegal(DstVT))
543 // Unhandled type. Halt "fast" selection and bail.
546 unsigned Op0 = getRegForValue(I->getOperand(0));
548 // Unhandled operand. Halt "fast" selection and bail.
551 // First, try to perform the bitcast by inserting a reg-reg copy.
552 unsigned ResultReg = 0;
553 if (SrcVT.getSimpleVT() == DstVT.getSimpleVT()) {
554 TargetRegisterClass* SrcClass = TLI.getRegClassFor(SrcVT);
555 TargetRegisterClass* DstClass = TLI.getRegClassFor(DstVT);
556 ResultReg = createResultReg(DstClass);
558 bool InsertedCopy = TII.copyRegToReg(*MBB, MBB->end(), ResultReg,
559 Op0, DstClass, SrcClass, DL);
564 // If the reg-reg copy failed, select a BIT_CONVERT opcode.
566 ResultReg = FastEmit_r(SrcVT.getSimpleVT(), DstVT.getSimpleVT(),
567 ISD::BIT_CONVERT, Op0);
572 UpdateValueMap(I, ResultReg);
577 FastISel::SelectInstruction(const Instruction *I) {
578 // Just before the terminator instruction, insert instructions to
579 // feed PHI nodes in successor blocks.
580 if (isa<TerminatorInst>(I))
581 if (!HandlePHINodesInSuccessorBlocks(I->getParent()))
584 DL = I->getDebugLoc();
586 // First, try doing target-independent selection.
587 if (SelectOperator(I, I->getOpcode())) {
592 // Next, try calling the target to attempt to handle the instruction.
593 if (TargetSelectInstruction(I)) {
602 /// FastEmitBranch - Emit an unconditional branch to the given block,
603 /// unless it is the immediate (fall-through) successor, and update
606 FastISel::FastEmitBranch(MachineBasicBlock *MSucc) {
607 if (MBB->isLayoutSuccessor(MSucc)) {
608 // The unconditional fall-through case, which needs no instructions.
610 // The unconditional branch case.
611 TII.InsertBranch(*MBB, MSucc, NULL, SmallVector<MachineOperand, 0>());
613 MBB->addSuccessor(MSucc);
616 /// SelectFNeg - Emit an FNeg operation.
619 FastISel::SelectFNeg(const User *I) {
620 unsigned OpReg = getRegForValue(BinaryOperator::getFNegArgument(I));
621 if (OpReg == 0) return false;
623 // If the target has ISD::FNEG, use it.
624 EVT VT = TLI.getValueType(I->getType());
625 unsigned ResultReg = FastEmit_r(VT.getSimpleVT(), VT.getSimpleVT(),
627 if (ResultReg != 0) {
628 UpdateValueMap(I, ResultReg);
632 // Bitcast the value to integer, twiddle the sign bit with xor,
633 // and then bitcast it back to floating-point.
634 if (VT.getSizeInBits() > 64) return false;
635 EVT IntVT = EVT::getIntegerVT(I->getContext(), VT.getSizeInBits());
636 if (!TLI.isTypeLegal(IntVT))
639 unsigned IntReg = FastEmit_r(VT.getSimpleVT(), IntVT.getSimpleVT(),
640 ISD::BIT_CONVERT, OpReg);
644 unsigned IntResultReg = FastEmit_ri_(IntVT.getSimpleVT(), ISD::XOR, IntReg,
645 UINT64_C(1) << (VT.getSizeInBits()-1),
646 IntVT.getSimpleVT());
647 if (IntResultReg == 0)
650 ResultReg = FastEmit_r(IntVT.getSimpleVT(), VT.getSimpleVT(),
651 ISD::BIT_CONVERT, IntResultReg);
655 UpdateValueMap(I, ResultReg);
660 FastISel::SelectOperator(const User *I, unsigned Opcode) {
662 case Instruction::Add:
663 return SelectBinaryOp(I, ISD::ADD);
664 case Instruction::FAdd:
665 return SelectBinaryOp(I, ISD::FADD);
666 case Instruction::Sub:
667 return SelectBinaryOp(I, ISD::SUB);
668 case Instruction::FSub:
669 // FNeg is currently represented in LLVM IR as a special case of FSub.
670 if (BinaryOperator::isFNeg(I))
671 return SelectFNeg(I);
672 return SelectBinaryOp(I, ISD::FSUB);
673 case Instruction::Mul:
674 return SelectBinaryOp(I, ISD::MUL);
675 case Instruction::FMul:
676 return SelectBinaryOp(I, ISD::FMUL);
677 case Instruction::SDiv:
678 return SelectBinaryOp(I, ISD::SDIV);
679 case Instruction::UDiv:
680 return SelectBinaryOp(I, ISD::UDIV);
681 case Instruction::FDiv:
682 return SelectBinaryOp(I, ISD::FDIV);
683 case Instruction::SRem:
684 return SelectBinaryOp(I, ISD::SREM);
685 case Instruction::URem:
686 return SelectBinaryOp(I, ISD::UREM);
687 case Instruction::FRem:
688 return SelectBinaryOp(I, ISD::FREM);
689 case Instruction::Shl:
690 return SelectBinaryOp(I, ISD::SHL);
691 case Instruction::LShr:
692 return SelectBinaryOp(I, ISD::SRL);
693 case Instruction::AShr:
694 return SelectBinaryOp(I, ISD::SRA);
695 case Instruction::And:
696 return SelectBinaryOp(I, ISD::AND);
697 case Instruction::Or:
698 return SelectBinaryOp(I, ISD::OR);
699 case Instruction::Xor:
700 return SelectBinaryOp(I, ISD::XOR);
702 case Instruction::GetElementPtr:
703 return SelectGetElementPtr(I);
705 case Instruction::Br: {
706 const BranchInst *BI = cast<BranchInst>(I);
708 if (BI->isUnconditional()) {
709 const BasicBlock *LLVMSucc = BI->getSuccessor(0);
710 MachineBasicBlock *MSucc = MBBMap[LLVMSucc];
711 FastEmitBranch(MSucc);
715 // Conditional branches are not handed yet.
716 // Halt "fast" selection and bail.
720 case Instruction::Unreachable:
724 case Instruction::Alloca:
725 // FunctionLowering has the static-sized case covered.
726 if (StaticAllocaMap.count(cast<AllocaInst>(I)))
729 // Dynamic-sized alloca is not handled yet.
732 case Instruction::Call:
733 return SelectCall(I);
735 case Instruction::BitCast:
736 return SelectBitCast(I);
738 case Instruction::FPToSI:
739 return SelectCast(I, ISD::FP_TO_SINT);
740 case Instruction::ZExt:
741 return SelectCast(I, ISD::ZERO_EXTEND);
742 case Instruction::SExt:
743 return SelectCast(I, ISD::SIGN_EXTEND);
744 case Instruction::Trunc:
745 return SelectCast(I, ISD::TRUNCATE);
746 case Instruction::SIToFP:
747 return SelectCast(I, ISD::SINT_TO_FP);
749 case Instruction::IntToPtr: // Deliberate fall-through.
750 case Instruction::PtrToInt: {
751 EVT SrcVT = TLI.getValueType(I->getOperand(0)->getType());
752 EVT DstVT = TLI.getValueType(I->getType());
753 if (DstVT.bitsGT(SrcVT))
754 return SelectCast(I, ISD::ZERO_EXTEND);
755 if (DstVT.bitsLT(SrcVT))
756 return SelectCast(I, ISD::TRUNCATE);
757 unsigned Reg = getRegForValue(I->getOperand(0));
758 if (Reg == 0) return false;
759 UpdateValueMap(I, Reg);
763 case Instruction::PHI:
764 llvm_unreachable("FastISel shouldn't visit PHI nodes!");
767 // Unhandled instruction. Halt "fast" selection and bail.
772 FastISel::FastISel(MachineFunction &mf,
773 DenseMap<const Value *, unsigned> &vm,
774 DenseMap<const BasicBlock *, MachineBasicBlock *> &bm,
775 DenseMap<const AllocaInst *, int> &am,
776 std::vector<std::pair<MachineInstr*, unsigned> > &pn
778 , SmallSet<const Instruction *, 8> &cil
785 PHINodesToUpdate(pn),
790 MRI(MF.getRegInfo()),
791 MFI(*MF.getFrameInfo()),
792 MCP(*MF.getConstantPool()),
794 TD(*TM.getTargetData()),
795 TII(*TM.getInstrInfo()),
796 TLI(*TM.getTargetLowering()),
800 FastISel::~FastISel() {}
802 unsigned FastISel::FastEmit_(MVT, MVT,
807 unsigned FastISel::FastEmit_r(MVT, MVT,
808 unsigned, unsigned /*Op0*/) {
812 unsigned FastISel::FastEmit_rr(MVT, MVT,
813 unsigned, unsigned /*Op0*/,
818 unsigned FastISel::FastEmit_i(MVT, MVT, unsigned, uint64_t /*Imm*/) {
822 unsigned FastISel::FastEmit_f(MVT, MVT,
823 unsigned, const ConstantFP * /*FPImm*/) {
827 unsigned FastISel::FastEmit_ri(MVT, MVT,
828 unsigned, unsigned /*Op0*/,
833 unsigned FastISel::FastEmit_rf(MVT, MVT,
834 unsigned, unsigned /*Op0*/,
835 const ConstantFP * /*FPImm*/) {
839 unsigned FastISel::FastEmit_rri(MVT, MVT,
841 unsigned /*Op0*/, unsigned /*Op1*/,
846 /// FastEmit_ri_ - This method is a wrapper of FastEmit_ri. It first tries
847 /// to emit an instruction with an immediate operand using FastEmit_ri.
848 /// If that fails, it materializes the immediate into a register and try
849 /// FastEmit_rr instead.
850 unsigned FastISel::FastEmit_ri_(MVT VT, unsigned Opcode,
851 unsigned Op0, uint64_t Imm,
853 // First check if immediate type is legal. If not, we can't use the ri form.
854 unsigned ResultReg = FastEmit_ri(VT, VT, Opcode, Op0, Imm);
857 unsigned MaterialReg = FastEmit_i(ImmType, ImmType, ISD::Constant, Imm);
858 if (MaterialReg == 0)
860 return FastEmit_rr(VT, VT, Opcode, Op0, MaterialReg);
863 /// FastEmit_rf_ - This method is a wrapper of FastEmit_ri. It first tries
864 /// to emit an instruction with a floating-point immediate operand using
865 /// FastEmit_rf. If that fails, it materializes the immediate into a register
866 /// and try FastEmit_rr instead.
867 unsigned FastISel::FastEmit_rf_(MVT VT, unsigned Opcode,
868 unsigned Op0, const ConstantFP *FPImm,
870 // First check if immediate type is legal. If not, we can't use the rf form.
871 unsigned ResultReg = FastEmit_rf(VT, VT, Opcode, Op0, FPImm);
875 // Materialize the constant in a register.
876 unsigned MaterialReg = FastEmit_f(ImmType, ImmType, ISD::ConstantFP, FPImm);
877 if (MaterialReg == 0) {
878 // If the target doesn't have a way to directly enter a floating-point
879 // value into a register, use an alternate approach.
880 // TODO: The current approach only supports floating-point constants
881 // that can be constructed by conversion from integer values. This should
882 // be replaced by code that creates a load from a constant-pool entry,
883 // which will require some target-specific work.
884 const APFloat &Flt = FPImm->getValueAPF();
885 EVT IntVT = TLI.getPointerTy();
888 uint32_t IntBitWidth = IntVT.getSizeInBits();
890 (void) Flt.convertToInteger(x, IntBitWidth, /*isSigned=*/true,
891 APFloat::rmTowardZero, &isExact);
894 APInt IntVal(IntBitWidth, 2, x);
896 unsigned IntegerReg = FastEmit_i(IntVT.getSimpleVT(), IntVT.getSimpleVT(),
897 ISD::Constant, IntVal.getZExtValue());
900 MaterialReg = FastEmit_r(IntVT.getSimpleVT(), VT,
901 ISD::SINT_TO_FP, IntegerReg);
902 if (MaterialReg == 0)
905 return FastEmit_rr(VT, VT, Opcode, Op0, MaterialReg);
908 unsigned FastISel::createResultReg(const TargetRegisterClass* RC) {
909 return MRI.createVirtualRegister(RC);
912 unsigned FastISel::FastEmitInst_(unsigned MachineInstOpcode,
913 const TargetRegisterClass* RC) {
914 unsigned ResultReg = createResultReg(RC);
915 const TargetInstrDesc &II = TII.get(MachineInstOpcode);
917 BuildMI(MBB, DL, II, ResultReg);
921 unsigned FastISel::FastEmitInst_r(unsigned MachineInstOpcode,
922 const TargetRegisterClass *RC,
924 unsigned ResultReg = createResultReg(RC);
925 const TargetInstrDesc &II = TII.get(MachineInstOpcode);
927 if (II.getNumDefs() >= 1)
928 BuildMI(MBB, DL, II, ResultReg).addReg(Op0);
930 BuildMI(MBB, DL, II).addReg(Op0);
931 bool InsertedCopy = TII.copyRegToReg(*MBB, MBB->end(), ResultReg,
932 II.ImplicitDefs[0], RC, RC, DL);
940 unsigned FastISel::FastEmitInst_rr(unsigned MachineInstOpcode,
941 const TargetRegisterClass *RC,
942 unsigned Op0, unsigned Op1) {
943 unsigned ResultReg = createResultReg(RC);
944 const TargetInstrDesc &II = TII.get(MachineInstOpcode);
946 if (II.getNumDefs() >= 1)
947 BuildMI(MBB, DL, II, ResultReg).addReg(Op0).addReg(Op1);
949 BuildMI(MBB, DL, II).addReg(Op0).addReg(Op1);
950 bool InsertedCopy = TII.copyRegToReg(*MBB, MBB->end(), ResultReg,
951 II.ImplicitDefs[0], RC, RC, DL);
958 unsigned FastISel::FastEmitInst_ri(unsigned MachineInstOpcode,
959 const TargetRegisterClass *RC,
960 unsigned Op0, uint64_t Imm) {
961 unsigned ResultReg = createResultReg(RC);
962 const TargetInstrDesc &II = TII.get(MachineInstOpcode);
964 if (II.getNumDefs() >= 1)
965 BuildMI(MBB, DL, II, ResultReg).addReg(Op0).addImm(Imm);
967 BuildMI(MBB, DL, II).addReg(Op0).addImm(Imm);
968 bool InsertedCopy = TII.copyRegToReg(*MBB, MBB->end(), ResultReg,
969 II.ImplicitDefs[0], RC, RC, DL);
976 unsigned FastISel::FastEmitInst_rf(unsigned MachineInstOpcode,
977 const TargetRegisterClass *RC,
978 unsigned Op0, const ConstantFP *FPImm) {
979 unsigned ResultReg = createResultReg(RC);
980 const TargetInstrDesc &II = TII.get(MachineInstOpcode);
982 if (II.getNumDefs() >= 1)
983 BuildMI(MBB, DL, II, ResultReg).addReg(Op0).addFPImm(FPImm);
985 BuildMI(MBB, DL, II).addReg(Op0).addFPImm(FPImm);
986 bool InsertedCopy = TII.copyRegToReg(*MBB, MBB->end(), ResultReg,
987 II.ImplicitDefs[0], RC, RC, DL);
994 unsigned FastISel::FastEmitInst_rri(unsigned MachineInstOpcode,
995 const TargetRegisterClass *RC,
996 unsigned Op0, unsigned Op1, uint64_t Imm) {
997 unsigned ResultReg = createResultReg(RC);
998 const TargetInstrDesc &II = TII.get(MachineInstOpcode);
1000 if (II.getNumDefs() >= 1)
1001 BuildMI(MBB, DL, II, ResultReg).addReg(Op0).addReg(Op1).addImm(Imm);
1003 BuildMI(MBB, DL, II).addReg(Op0).addReg(Op1).addImm(Imm);
1004 bool InsertedCopy = TII.copyRegToReg(*MBB, MBB->end(), ResultReg,
1005 II.ImplicitDefs[0], RC, RC, DL);
1012 unsigned FastISel::FastEmitInst_i(unsigned MachineInstOpcode,
1013 const TargetRegisterClass *RC,
1015 unsigned ResultReg = createResultReg(RC);
1016 const TargetInstrDesc &II = TII.get(MachineInstOpcode);
1018 if (II.getNumDefs() >= 1)
1019 BuildMI(MBB, DL, II, ResultReg).addImm(Imm);
1021 BuildMI(MBB, DL, II).addImm(Imm);
1022 bool InsertedCopy = TII.copyRegToReg(*MBB, MBB->end(), ResultReg,
1023 II.ImplicitDefs[0], RC, RC, DL);
1030 unsigned FastISel::FastEmitInst_extractsubreg(MVT RetVT,
1031 unsigned Op0, uint32_t Idx) {
1032 const TargetRegisterClass* RC = MRI.getRegClass(Op0);
1034 unsigned ResultReg = createResultReg(TLI.getRegClassFor(RetVT));
1035 const TargetInstrDesc &II = TII.get(TargetOpcode::EXTRACT_SUBREG);
1037 if (II.getNumDefs() >= 1)
1038 BuildMI(MBB, DL, II, ResultReg).addReg(Op0).addImm(Idx);
1040 BuildMI(MBB, DL, II).addReg(Op0).addImm(Idx);
1041 bool InsertedCopy = TII.copyRegToReg(*MBB, MBB->end(), ResultReg,
1042 II.ImplicitDefs[0], RC, RC, DL);
1049 /// FastEmitZExtFromI1 - Emit MachineInstrs to compute the value of Op
1050 /// with all but the least significant bit set to zero.
1051 unsigned FastISel::FastEmitZExtFromI1(MVT VT, unsigned Op) {
1052 return FastEmit_ri(VT, VT, ISD::AND, Op, 1);
1055 /// HandlePHINodesInSuccessorBlocks - Handle PHI nodes in successor blocks.
1056 /// Emit code to ensure constants are copied into registers when needed.
1057 /// Remember the virtual registers that need to be added to the Machine PHI
1058 /// nodes as input. We cannot just directly add them, because expansion
1059 /// might result in multiple MBB's for one BB. As such, the start of the
1060 /// BB might correspond to a different MBB than the end.
1061 bool FastISel::HandlePHINodesInSuccessorBlocks(const BasicBlock *LLVMBB) {
1062 const TerminatorInst *TI = LLVMBB->getTerminator();
1064 SmallPtrSet<MachineBasicBlock *, 4> SuccsHandled;
1065 unsigned OrigNumPHINodesToUpdate = PHINodesToUpdate.size();
1067 // Check successor nodes' PHI nodes that expect a constant to be available
1069 for (unsigned succ = 0, e = TI->getNumSuccessors(); succ != e; ++succ) {
1070 const BasicBlock *SuccBB = TI->getSuccessor(succ);
1071 if (!isa<PHINode>(SuccBB->begin())) continue;
1072 MachineBasicBlock *SuccMBB = MBBMap[SuccBB];
1074 // If this terminator has multiple identical successors (common for
1075 // switches), only handle each succ once.
1076 if (!SuccsHandled.insert(SuccMBB)) continue;
1078 MachineBasicBlock::iterator MBBI = SuccMBB->begin();
1080 // At this point we know that there is a 1-1 correspondence between LLVM PHI
1081 // nodes and Machine PHI nodes, but the incoming operands have not been
1083 for (BasicBlock::const_iterator I = SuccBB->begin();
1084 const PHINode *PN = dyn_cast<PHINode>(I); ++I) {
1086 // Ignore dead phi's.
1087 if (PN->use_empty()) continue;
1089 // Only handle legal types. Two interesting things to note here. First,
1090 // by bailing out early, we may leave behind some dead instructions,
1091 // since SelectionDAG's HandlePHINodesInSuccessorBlocks will insert its
1092 // own moves. Second, this check is necessary becuase FastISel doesn't
1093 // use CreateRegForValue to create registers, so it always creates
1094 // exactly one register for each non-void instruction.
1095 EVT VT = TLI.getValueType(PN->getType(), /*AllowUnknown=*/true);
1096 if (VT == MVT::Other || !TLI.isTypeLegal(VT)) {
1099 VT = TLI.getTypeToTransformTo(LLVMBB->getContext(), VT);
1101 PHINodesToUpdate.resize(OrigNumPHINodesToUpdate);
1106 const Value *PHIOp = PN->getIncomingValueForBlock(LLVMBB);
1108 // Set the DebugLoc for the copy. Prefer the location of the operand
1109 // if there is one; use the location of the PHI otherwise.
1110 DL = PN->getDebugLoc();
1111 if (const Instruction *Inst = dyn_cast<Instruction>(PHIOp))
1112 DL = Inst->getDebugLoc();
1114 unsigned Reg = getRegForValue(PHIOp);
1116 PHINodesToUpdate.resize(OrigNumPHINodesToUpdate);
1119 PHINodesToUpdate.push_back(std::make_pair(MBBI++, Reg));