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/Analysis/Loads.h"
52 #include "llvm/Target/TargetData.h"
53 #include "llvm/Target/TargetInstrInfo.h"
54 #include "llvm/Target/TargetLowering.h"
55 #include "llvm/Target/TargetMachine.h"
56 #include "llvm/Support/ErrorHandling.h"
57 #include "FunctionLoweringInfo.h"
60 bool FastISel::hasTrivialKill(const Value *V) const {
61 // Don't consider constants or arguments to have trivial kills.
62 const Instruction *I = dyn_cast<Instruction>(V);
66 // No-op casts are trivially coalesced by fast-isel.
67 if (const CastInst *Cast = dyn_cast<CastInst>(I))
68 if (Cast->isNoopCast(TD.getIntPtrType(Cast->getContext())) &&
69 !hasTrivialKill(Cast->getOperand(0)))
72 // Only instructions with a single use in the same basic block are considered
73 // to have trivial kills.
74 return I->hasOneUse() &&
75 !(I->getOpcode() == Instruction::BitCast ||
76 I->getOpcode() == Instruction::PtrToInt ||
77 I->getOpcode() == Instruction::IntToPtr) &&
78 cast<Instruction>(I->use_begin())->getParent() == I->getParent();
81 unsigned FastISel::getRegForValue(const Value *V) {
82 EVT RealVT = TLI.getValueType(V->getType(), /*AllowUnknown=*/true);
83 // Don't handle non-simple values in FastISel.
84 if (!RealVT.isSimple())
87 // Ignore illegal types. We must do this before looking up the value
88 // in ValueMap because Arguments are given virtual registers regardless
89 // of whether FastISel can handle them.
90 MVT VT = RealVT.getSimpleVT();
91 if (!TLI.isTypeLegal(VT)) {
92 // Promote MVT::i1 to a legal type though, because it's common and easy.
94 VT = TLI.getTypeToTransformTo(V->getContext(), VT).getSimpleVT();
99 // Look up the value to see if we already have a register for it. We
100 // cache values defined by Instructions across blocks, and other values
101 // only locally. This is because Instructions already have the SSA
102 // def-dominates-use requirement enforced.
103 DenseMap<const Value *, unsigned>::iterator I = ValueMap.find(V);
104 if (I != ValueMap.end())
106 unsigned Reg = LocalValueMap[V];
110 // In bottom-up mode, just create the virtual register which will be used
111 // to hold the value. It will be materialized later.
113 Reg = createResultReg(TLI.getRegClassFor(VT));
114 if (isa<Instruction>(V))
117 LocalValueMap[V] = Reg;
121 return materializeRegForValue(V, VT);
124 /// materializeRegForValue - Helper for getRegForVale. This function is
125 /// called when the value isn't already available in a register and must
126 /// be materialized with new instructions.
127 unsigned FastISel::materializeRegForValue(const Value *V, MVT VT) {
130 if (const ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
131 if (CI->getValue().getActiveBits() <= 64)
132 Reg = FastEmit_i(VT, VT, ISD::Constant, CI->getZExtValue());
133 } else if (isa<AllocaInst>(V)) {
134 Reg = TargetMaterializeAlloca(cast<AllocaInst>(V));
135 } else if (isa<ConstantPointerNull>(V)) {
136 // Translate this as an integer zero so that it can be
137 // local-CSE'd with actual integer zeros.
139 getRegForValue(Constant::getNullValue(TD.getIntPtrType(V->getContext())));
140 } else if (const ConstantFP *CF = dyn_cast<ConstantFP>(V)) {
141 // Try to emit the constant directly.
142 Reg = FastEmit_f(VT, VT, ISD::ConstantFP, CF);
145 // Try to emit the constant by using an integer constant with a cast.
146 const APFloat &Flt = CF->getValueAPF();
147 EVT IntVT = TLI.getPointerTy();
150 uint32_t IntBitWidth = IntVT.getSizeInBits();
152 (void) Flt.convertToInteger(x, IntBitWidth, /*isSigned=*/true,
153 APFloat::rmTowardZero, &isExact);
155 APInt IntVal(IntBitWidth, 2, x);
157 unsigned IntegerReg =
158 getRegForValue(ConstantInt::get(V->getContext(), IntVal));
160 Reg = FastEmit_r(IntVT.getSimpleVT(), VT, ISD::SINT_TO_FP,
161 IntegerReg, /*Kill=*/false);
164 } else if (const Operator *Op = dyn_cast<Operator>(V)) {
165 if (!SelectOperator(Op, Op->getOpcode()))
166 if (!isa<Instruction>(Op) ||
167 !TargetSelectInstruction(cast<Instruction>(Op)))
169 Reg = lookUpRegForValue(Op);
170 } else if (isa<UndefValue>(V)) {
171 Reg = createResultReg(TLI.getRegClassFor(VT));
172 BuildMI(MBB, DL, TII.get(TargetOpcode::IMPLICIT_DEF), Reg);
175 // If target-independent code couldn't handle the value, give target-specific
177 if (!Reg && isa<Constant>(V))
178 Reg = TargetMaterializeConstant(cast<Constant>(V));
180 // Don't cache constant materializations in the general ValueMap.
181 // To do so would require tracking what uses they dominate.
183 LocalValueMap[V] = Reg;
187 unsigned FastISel::lookUpRegForValue(const Value *V) {
188 // Look up the value to see if we already have a register for it. We
189 // cache values defined by Instructions across blocks, and other values
190 // only locally. This is because Instructions already have the SSA
191 // def-dominates-use requirement enforced.
192 DenseMap<const Value *, unsigned>::iterator I = ValueMap.find(V);
193 if (I != ValueMap.end())
195 return LocalValueMap[V];
198 /// UpdateValueMap - Update the value map to include the new mapping for this
199 /// instruction, or insert an extra copy to get the result in a previous
200 /// determined register.
201 /// NOTE: This is only necessary because we might select a block that uses
202 /// a value before we select the block that defines the value. It might be
203 /// possible to fix this by selecting blocks in reverse postorder.
204 unsigned FastISel::UpdateValueMap(const Value *I, unsigned Reg) {
205 if (!isa<Instruction>(I)) {
206 LocalValueMap[I] = Reg;
210 unsigned &AssignedReg = ValueMap[I];
211 if (AssignedReg == 0)
213 else if (Reg != AssignedReg) {
214 const TargetRegisterClass *RegClass = MRI.getRegClass(Reg);
215 TII.copyRegToReg(*MBB, MBB->end(), AssignedReg,
216 Reg, RegClass, RegClass, DL);
221 std::pair<unsigned, bool> FastISel::getRegForGEPIndex(const Value *Idx) {
222 unsigned IdxN = getRegForValue(Idx);
224 // Unhandled operand. Halt "fast" selection and bail.
225 return std::pair<unsigned, bool>(0, false);
227 bool IdxNIsKill = hasTrivialKill(Idx);
229 // If the index is smaller or larger than intptr_t, truncate or extend it.
230 MVT PtrVT = TLI.getPointerTy();
231 EVT IdxVT = EVT::getEVT(Idx->getType(), /*HandleUnknown=*/false);
232 if (IdxVT.bitsLT(PtrVT)) {
233 IdxN = FastEmit_r(IdxVT.getSimpleVT(), PtrVT, ISD::SIGN_EXTEND,
237 else if (IdxVT.bitsGT(PtrVT)) {
238 IdxN = FastEmit_r(IdxVT.getSimpleVT(), PtrVT, ISD::TRUNCATE,
242 return std::pair<unsigned, bool>(IdxN, IdxNIsKill);
245 /// SelectBinaryOp - Select and emit code for a binary operator instruction,
246 /// which has an opcode which directly corresponds to the given ISD opcode.
248 bool FastISel::SelectBinaryOp(const User *I, unsigned ISDOpcode) {
249 EVT VT = EVT::getEVT(I->getType(), /*HandleUnknown=*/true);
250 if (VT == MVT::Other || !VT.isSimple())
251 // Unhandled type. Halt "fast" selection and bail.
254 // We only handle legal types. For example, on x86-32 the instruction
255 // selector contains all of the 64-bit instructions from x86-64,
256 // under the assumption that i64 won't be used if the target doesn't
258 if (!TLI.isTypeLegal(VT)) {
259 // MVT::i1 is special. Allow AND, OR, or XOR because they
260 // don't require additional zeroing, which makes them easy.
262 (ISDOpcode == ISD::AND || ISDOpcode == ISD::OR ||
263 ISDOpcode == ISD::XOR))
264 VT = TLI.getTypeToTransformTo(I->getContext(), VT);
269 unsigned Op0 = getRegForValue(I->getOperand(0));
271 // Unhandled operand. Halt "fast" selection and bail.
274 bool Op0IsKill = hasTrivialKill(I->getOperand(0));
276 // Check if the second operand is a constant and handle it appropriately.
277 if (ConstantInt *CI = dyn_cast<ConstantInt>(I->getOperand(1))) {
278 unsigned ResultReg = FastEmit_ri(VT.getSimpleVT(), VT.getSimpleVT(),
279 ISDOpcode, Op0, Op0IsKill,
281 if (ResultReg != 0) {
282 // We successfully emitted code for the given LLVM Instruction.
283 UpdateValueMap(I, ResultReg);
288 // Check if the second operand is a constant float.
289 if (ConstantFP *CF = dyn_cast<ConstantFP>(I->getOperand(1))) {
290 unsigned ResultReg = FastEmit_rf(VT.getSimpleVT(), VT.getSimpleVT(),
291 ISDOpcode, Op0, Op0IsKill, CF);
292 if (ResultReg != 0) {
293 // We successfully emitted code for the given LLVM Instruction.
294 UpdateValueMap(I, ResultReg);
299 unsigned Op1 = getRegForValue(I->getOperand(1));
301 // Unhandled operand. Halt "fast" selection and bail.
304 bool Op1IsKill = hasTrivialKill(I->getOperand(1));
306 // Now we have both operands in registers. Emit the instruction.
307 unsigned ResultReg = FastEmit_rr(VT.getSimpleVT(), VT.getSimpleVT(),
312 // Target-specific code wasn't able to find a machine opcode for
313 // the given ISD opcode and type. Halt "fast" selection and bail.
316 // We successfully emitted code for the given LLVM Instruction.
317 UpdateValueMap(I, ResultReg);
321 bool FastISel::SelectGetElementPtr(const User *I) {
322 unsigned N = getRegForValue(I->getOperand(0));
324 // Unhandled operand. Halt "fast" selection and bail.
327 bool NIsKill = hasTrivialKill(I->getOperand(0));
329 const Type *Ty = I->getOperand(0)->getType();
330 MVT VT = TLI.getPointerTy();
331 for (GetElementPtrInst::const_op_iterator OI = I->op_begin()+1,
332 E = I->op_end(); OI != E; ++OI) {
333 const Value *Idx = *OI;
334 if (const StructType *StTy = dyn_cast<StructType>(Ty)) {
335 unsigned Field = cast<ConstantInt>(Idx)->getZExtValue();
338 uint64_t Offs = TD.getStructLayout(StTy)->getElementOffset(Field);
339 // FIXME: This can be optimized by combining the add with a
341 N = FastEmit_ri_(VT, ISD::ADD, N, NIsKill, Offs, VT);
343 // Unhandled operand. Halt "fast" selection and bail.
347 Ty = StTy->getElementType(Field);
349 Ty = cast<SequentialType>(Ty)->getElementType();
351 // If this is a constant subscript, handle it quickly.
352 if (const ConstantInt *CI = dyn_cast<ConstantInt>(Idx)) {
353 if (CI->isZero()) continue;
355 TD.getTypeAllocSize(Ty)*cast<ConstantInt>(CI)->getSExtValue();
356 N = FastEmit_ri_(VT, ISD::ADD, N, NIsKill, Offs, VT);
358 // Unhandled operand. Halt "fast" selection and bail.
364 // N = N + Idx * ElementSize;
365 uint64_t ElementSize = TD.getTypeAllocSize(Ty);
366 std::pair<unsigned, bool> Pair = getRegForGEPIndex(Idx);
367 unsigned IdxN = Pair.first;
368 bool IdxNIsKill = Pair.second;
370 // Unhandled operand. Halt "fast" selection and bail.
373 if (ElementSize != 1) {
374 IdxN = FastEmit_ri_(VT, ISD::MUL, IdxN, IdxNIsKill, ElementSize, VT);
376 // Unhandled operand. Halt "fast" selection and bail.
380 N = FastEmit_rr(VT, VT, ISD::ADD, N, NIsKill, IdxN, IdxNIsKill);
382 // Unhandled operand. Halt "fast" selection and bail.
387 // We successfully emitted code for the given LLVM Instruction.
388 UpdateValueMap(I, N);
392 bool FastISel::SelectCall(const User *I) {
393 const Function *F = cast<CallInst>(I)->getCalledFunction();
394 if (!F) return false;
396 // Handle selected intrinsic function calls.
397 unsigned IID = F->getIntrinsicID();
400 case Intrinsic::dbg_declare: {
401 const DbgDeclareInst *DI = cast<DbgDeclareInst>(I);
402 if (!DIVariable(DI->getVariable()).Verify() ||
403 !MF.getMMI().hasDebugInfo())
406 const Value *Address = DI->getAddress();
409 if (isa<UndefValue>(Address))
411 const AllocaInst *AI = dyn_cast<AllocaInst>(Address);
412 // Don't handle byval struct arguments or VLAs, for example.
413 // Note that if we have a byval struct argument, fast ISel is turned off;
414 // those are handled in SelectionDAGBuilder.
416 DenseMap<const AllocaInst*, int>::iterator SI =
417 StaticAllocaMap.find(AI);
418 if (SI == StaticAllocaMap.end()) break; // VLAs.
420 if (!DI->getDebugLoc().isUnknown())
421 MF.getMMI().setVariableDbgInfo(DI->getVariable(), FI, DI->getDebugLoc());
423 // Building the map above is target independent. Generating DBG_VALUE
424 // inline is target dependent; do this now.
425 (void)TargetSelectInstruction(cast<Instruction>(I));
428 case Intrinsic::dbg_value: {
429 // This form of DBG_VALUE is target-independent.
430 const DbgValueInst *DI = cast<DbgValueInst>(I);
431 const TargetInstrDesc &II = TII.get(TargetOpcode::DBG_VALUE);
432 const Value *V = DI->getValue();
434 // Currently the optimizer can produce this; insert an undef to
435 // help debugging. Probably the optimizer should not do this.
436 BuildMI(MBB, DL, II).addReg(0U).addImm(DI->getOffset()).
437 addMetadata(DI->getVariable());
438 } else if (const ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
439 BuildMI(MBB, DL, II).addImm(CI->getZExtValue()).addImm(DI->getOffset()).
440 addMetadata(DI->getVariable());
441 } else if (const ConstantFP *CF = dyn_cast<ConstantFP>(V)) {
442 BuildMI(MBB, DL, II).addFPImm(CF).addImm(DI->getOffset()).
443 addMetadata(DI->getVariable());
444 } else if (unsigned Reg = lookUpRegForValue(V)) {
445 BuildMI(MBB, DL, II).addReg(Reg, RegState::Debug).addImm(DI->getOffset()).
446 addMetadata(DI->getVariable());
448 // We can't yet handle anything else here because it would require
449 // generating code, thus altering codegen because of debug info.
450 // Insert an undef so we can see what we dropped.
451 BuildMI(MBB, DL, II).addReg(0U).addImm(DI->getOffset()).
452 addMetadata(DI->getVariable());
456 case Intrinsic::eh_exception: {
457 EVT VT = TLI.getValueType(I->getType());
458 switch (TLI.getOperationAction(ISD::EXCEPTIONADDR, VT)) {
460 case TargetLowering::Expand: {
461 assert(MBB->isLandingPad() && "Call to eh.exception not in landing pad!");
462 unsigned Reg = TLI.getExceptionAddressRegister();
463 const TargetRegisterClass *RC = TLI.getRegClassFor(VT);
464 unsigned ResultReg = createResultReg(RC);
465 bool InsertedCopy = TII.copyRegToReg(*MBB, MBB->end(), ResultReg,
467 assert(InsertedCopy && "Can't copy address registers!");
468 InsertedCopy = InsertedCopy;
469 UpdateValueMap(I, ResultReg);
475 case Intrinsic::eh_selector: {
476 EVT VT = TLI.getValueType(I->getType());
477 switch (TLI.getOperationAction(ISD::EHSELECTION, VT)) {
479 case TargetLowering::Expand: {
480 if (MBB->isLandingPad())
481 AddCatchInfo(*cast<CallInst>(I), &MF.getMMI(), MBB);
484 CatchInfoLost.insert(cast<CallInst>(I));
486 // FIXME: Mark exception selector register as live in. Hack for PR1508.
487 unsigned Reg = TLI.getExceptionSelectorRegister();
488 if (Reg) MBB->addLiveIn(Reg);
491 unsigned Reg = TLI.getExceptionSelectorRegister();
492 EVT SrcVT = TLI.getPointerTy();
493 const TargetRegisterClass *RC = TLI.getRegClassFor(SrcVT);
494 unsigned ResultReg = createResultReg(RC);
495 bool InsertedCopy = TII.copyRegToReg(*MBB, MBB->end(), ResultReg, Reg,
497 assert(InsertedCopy && "Can't copy address registers!");
498 InsertedCopy = InsertedCopy;
500 bool ResultRegIsKill = hasTrivialKill(I);
502 // Cast the register to the type of the selector.
503 if (SrcVT.bitsGT(MVT::i32))
504 ResultReg = FastEmit_r(SrcVT.getSimpleVT(), MVT::i32, ISD::TRUNCATE,
505 ResultReg, ResultRegIsKill);
506 else if (SrcVT.bitsLT(MVT::i32))
507 ResultReg = FastEmit_r(SrcVT.getSimpleVT(), MVT::i32,
508 ISD::SIGN_EXTEND, ResultReg, ResultRegIsKill);
510 // Unhandled operand. Halt "fast" selection and bail.
513 UpdateValueMap(I, ResultReg);
522 // An arbitrary call. Bail.
526 bool FastISel::SelectCast(const User *I, unsigned Opcode) {
527 EVT SrcVT = TLI.getValueType(I->getOperand(0)->getType());
528 EVT DstVT = TLI.getValueType(I->getType());
530 if (SrcVT == MVT::Other || !SrcVT.isSimple() ||
531 DstVT == MVT::Other || !DstVT.isSimple())
532 // Unhandled type. Halt "fast" selection and bail.
535 // Check if the destination type is legal. Or as a special case,
536 // it may be i1 if we're doing a truncate because that's
537 // easy and somewhat common.
538 if (!TLI.isTypeLegal(DstVT))
539 if (DstVT != MVT::i1 || Opcode != ISD::TRUNCATE)
540 // Unhandled type. Halt "fast" selection and bail.
543 // Check if the source operand is legal. Or as a special case,
544 // it may be i1 if we're doing zero-extension because that's
545 // easy and somewhat common.
546 if (!TLI.isTypeLegal(SrcVT))
547 if (SrcVT != MVT::i1 || Opcode != ISD::ZERO_EXTEND)
548 // Unhandled type. Halt "fast" selection and bail.
551 unsigned InputReg = getRegForValue(I->getOperand(0));
553 // Unhandled operand. Halt "fast" selection and bail.
556 bool InputRegIsKill = hasTrivialKill(I->getOperand(0));
558 // If the operand is i1, arrange for the high bits in the register to be zero.
559 if (SrcVT == MVT::i1) {
560 SrcVT = TLI.getTypeToTransformTo(I->getContext(), SrcVT);
561 InputReg = FastEmitZExtFromI1(SrcVT.getSimpleVT(), InputReg, InputRegIsKill);
564 InputRegIsKill = true;
566 // If the result is i1, truncate to the target's type for i1 first.
567 if (DstVT == MVT::i1)
568 DstVT = TLI.getTypeToTransformTo(I->getContext(), DstVT);
570 unsigned ResultReg = FastEmit_r(SrcVT.getSimpleVT(),
573 InputReg, InputRegIsKill);
577 UpdateValueMap(I, ResultReg);
581 bool FastISel::SelectBitCast(const User *I) {
582 // If the bitcast doesn't change the type, just use the operand value.
583 if (I->getType() == I->getOperand(0)->getType()) {
584 unsigned Reg = getRegForValue(I->getOperand(0));
587 UpdateValueMap(I, Reg);
591 // Bitcasts of other values become reg-reg copies or BIT_CONVERT operators.
592 EVT SrcVT = TLI.getValueType(I->getOperand(0)->getType());
593 EVT DstVT = TLI.getValueType(I->getType());
595 if (SrcVT == MVT::Other || !SrcVT.isSimple() ||
596 DstVT == MVT::Other || !DstVT.isSimple() ||
597 !TLI.isTypeLegal(SrcVT) || !TLI.isTypeLegal(DstVT))
598 // Unhandled type. Halt "fast" selection and bail.
601 unsigned Op0 = getRegForValue(I->getOperand(0));
603 // Unhandled operand. Halt "fast" selection and bail.
606 bool Op0IsKill = hasTrivialKill(I->getOperand(0));
608 // First, try to perform the bitcast by inserting a reg-reg copy.
609 unsigned ResultReg = 0;
610 if (SrcVT.getSimpleVT() == DstVT.getSimpleVT()) {
611 TargetRegisterClass* SrcClass = TLI.getRegClassFor(SrcVT);
612 TargetRegisterClass* DstClass = TLI.getRegClassFor(DstVT);
613 ResultReg = createResultReg(DstClass);
615 bool InsertedCopy = TII.copyRegToReg(*MBB, MBB->end(), ResultReg,
616 Op0, DstClass, SrcClass, DL);
621 // If the reg-reg copy failed, select a BIT_CONVERT opcode.
623 ResultReg = FastEmit_r(SrcVT.getSimpleVT(), DstVT.getSimpleVT(),
624 ISD::BIT_CONVERT, Op0, Op0IsKill);
629 UpdateValueMap(I, ResultReg);
634 FastISel::SelectInstruction(const Instruction *I) {
635 // Just before the terminator instruction, insert instructions to
636 // feed PHI nodes in successor blocks.
637 if (isa<TerminatorInst>(I))
638 if (!HandlePHINodesInSuccessorBlocks(I->getParent()))
641 DL = I->getDebugLoc();
643 // First, try doing target-independent selection.
644 if (SelectOperator(I, I->getOpcode())) {
649 // Next, try calling the target to attempt to handle the instruction.
650 if (TargetSelectInstruction(I)) {
659 /// FastEmitBranch - Emit an unconditional branch to the given block,
660 /// unless it is the immediate (fall-through) successor, and update
663 FastISel::FastEmitBranch(MachineBasicBlock *MSucc, DebugLoc DL) {
664 if (MBB->isLayoutSuccessor(MSucc)) {
665 // The unconditional fall-through case, which needs no instructions.
667 // The unconditional branch case.
668 TII.InsertBranch(*MBB, MSucc, NULL, SmallVector<MachineOperand, 0>(), DL);
670 MBB->addSuccessor(MSucc);
673 /// SelectFNeg - Emit an FNeg operation.
676 FastISel::SelectFNeg(const User *I) {
677 unsigned OpReg = getRegForValue(BinaryOperator::getFNegArgument(I));
678 if (OpReg == 0) return false;
680 bool OpRegIsKill = hasTrivialKill(I);
682 // If the target has ISD::FNEG, use it.
683 EVT VT = TLI.getValueType(I->getType());
684 unsigned ResultReg = FastEmit_r(VT.getSimpleVT(), VT.getSimpleVT(),
685 ISD::FNEG, OpReg, OpRegIsKill);
686 if (ResultReg != 0) {
687 UpdateValueMap(I, ResultReg);
691 // Bitcast the value to integer, twiddle the sign bit with xor,
692 // and then bitcast it back to floating-point.
693 if (VT.getSizeInBits() > 64) return false;
694 EVT IntVT = EVT::getIntegerVT(I->getContext(), VT.getSizeInBits());
695 if (!TLI.isTypeLegal(IntVT))
698 unsigned IntReg = FastEmit_r(VT.getSimpleVT(), IntVT.getSimpleVT(),
699 ISD::BIT_CONVERT, OpReg, OpRegIsKill);
703 unsigned IntResultReg = FastEmit_ri_(IntVT.getSimpleVT(), ISD::XOR,
704 IntReg, /*Kill=*/true,
705 UINT64_C(1) << (VT.getSizeInBits()-1),
706 IntVT.getSimpleVT());
707 if (IntResultReg == 0)
710 ResultReg = FastEmit_r(IntVT.getSimpleVT(), VT.getSimpleVT(),
711 ISD::BIT_CONVERT, IntResultReg, /*Kill=*/true);
715 UpdateValueMap(I, ResultReg);
720 FastISel::SelectLoad(const User *I) {
721 LoadInst *LI = const_cast<LoadInst *>(cast<LoadInst>(I));
723 // For a load from an alloca, make a limited effort to find the value
724 // already available in a register, avoiding redundant loads.
725 if (!LI->isVolatile() && isa<AllocaInst>(LI->getPointerOperand())) {
726 BasicBlock::iterator ScanFrom = LI;
727 if (const Value *V = FindAvailableLoadedValue(LI->getPointerOperand(),
728 LI->getParent(), ScanFrom)) {
729 unsigned ResultReg = getRegForValue(V);
730 if (ResultReg != 0) {
731 UpdateValueMap(I, ResultReg);
741 FastISel::SelectOperator(const User *I, unsigned Opcode) {
743 case Instruction::Load:
744 return SelectLoad(I);
745 case Instruction::Add:
746 return SelectBinaryOp(I, ISD::ADD);
747 case Instruction::FAdd:
748 return SelectBinaryOp(I, ISD::FADD);
749 case Instruction::Sub:
750 return SelectBinaryOp(I, ISD::SUB);
751 case Instruction::FSub:
752 // FNeg is currently represented in LLVM IR as a special case of FSub.
753 if (BinaryOperator::isFNeg(I))
754 return SelectFNeg(I);
755 return SelectBinaryOp(I, ISD::FSUB);
756 case Instruction::Mul:
757 return SelectBinaryOp(I, ISD::MUL);
758 case Instruction::FMul:
759 return SelectBinaryOp(I, ISD::FMUL);
760 case Instruction::SDiv:
761 return SelectBinaryOp(I, ISD::SDIV);
762 case Instruction::UDiv:
763 return SelectBinaryOp(I, ISD::UDIV);
764 case Instruction::FDiv:
765 return SelectBinaryOp(I, ISD::FDIV);
766 case Instruction::SRem:
767 return SelectBinaryOp(I, ISD::SREM);
768 case Instruction::URem:
769 return SelectBinaryOp(I, ISD::UREM);
770 case Instruction::FRem:
771 return SelectBinaryOp(I, ISD::FREM);
772 case Instruction::Shl:
773 return SelectBinaryOp(I, ISD::SHL);
774 case Instruction::LShr:
775 return SelectBinaryOp(I, ISD::SRL);
776 case Instruction::AShr:
777 return SelectBinaryOp(I, ISD::SRA);
778 case Instruction::And:
779 return SelectBinaryOp(I, ISD::AND);
780 case Instruction::Or:
781 return SelectBinaryOp(I, ISD::OR);
782 case Instruction::Xor:
783 return SelectBinaryOp(I, ISD::XOR);
785 case Instruction::GetElementPtr:
786 return SelectGetElementPtr(I);
788 case Instruction::Br: {
789 const BranchInst *BI = cast<BranchInst>(I);
791 if (BI->isUnconditional()) {
792 const BasicBlock *LLVMSucc = BI->getSuccessor(0);
793 MachineBasicBlock *MSucc = MBBMap[LLVMSucc];
794 FastEmitBranch(MSucc, BI->getDebugLoc());
798 // Conditional branches are not handed yet.
799 // Halt "fast" selection and bail.
803 case Instruction::Unreachable:
807 case Instruction::Alloca:
808 // FunctionLowering has the static-sized case covered.
809 if (StaticAllocaMap.count(cast<AllocaInst>(I)))
812 // Dynamic-sized alloca is not handled yet.
815 case Instruction::Call:
816 return SelectCall(I);
818 case Instruction::BitCast:
819 return SelectBitCast(I);
821 case Instruction::FPToSI:
822 return SelectCast(I, ISD::FP_TO_SINT);
823 case Instruction::ZExt:
824 return SelectCast(I, ISD::ZERO_EXTEND);
825 case Instruction::SExt:
826 return SelectCast(I, ISD::SIGN_EXTEND);
827 case Instruction::Trunc:
828 return SelectCast(I, ISD::TRUNCATE);
829 case Instruction::SIToFP:
830 return SelectCast(I, ISD::SINT_TO_FP);
832 case Instruction::IntToPtr: // Deliberate fall-through.
833 case Instruction::PtrToInt: {
834 EVT SrcVT = TLI.getValueType(I->getOperand(0)->getType());
835 EVT DstVT = TLI.getValueType(I->getType());
836 if (DstVT.bitsGT(SrcVT))
837 return SelectCast(I, ISD::ZERO_EXTEND);
838 if (DstVT.bitsLT(SrcVT))
839 return SelectCast(I, ISD::TRUNCATE);
840 unsigned Reg = getRegForValue(I->getOperand(0));
841 if (Reg == 0) return false;
842 UpdateValueMap(I, Reg);
846 case Instruction::PHI:
847 llvm_unreachable("FastISel shouldn't visit PHI nodes!");
850 // Unhandled instruction. Halt "fast" selection and bail.
855 FastISel::FastISel(MachineFunction &mf,
856 DenseMap<const Value *, unsigned> &vm,
857 DenseMap<const BasicBlock *, MachineBasicBlock *> &bm,
858 DenseMap<const AllocaInst *, int> &am,
859 std::vector<std::pair<MachineInstr*, unsigned> > &pn
861 , SmallSet<const Instruction *, 8> &cil
868 PHINodesToUpdate(pn),
873 MRI(MF.getRegInfo()),
874 MFI(*MF.getFrameInfo()),
875 MCP(*MF.getConstantPool()),
877 TD(*TM.getTargetData()),
878 TII(*TM.getInstrInfo()),
879 TLI(*TM.getTargetLowering()),
880 TRI(*TM.getRegisterInfo()),
884 FastISel::~FastISel() {}
886 unsigned FastISel::FastEmit_(MVT, MVT,
891 unsigned FastISel::FastEmit_r(MVT, MVT,
893 unsigned /*Op0*/, bool /*Op0IsKill*/) {
897 unsigned FastISel::FastEmit_rr(MVT, MVT,
899 unsigned /*Op0*/, bool /*Op0IsKill*/,
900 unsigned /*Op1*/, bool /*Op1IsKill*/) {
904 unsigned FastISel::FastEmit_i(MVT, MVT, unsigned, uint64_t /*Imm*/) {
908 unsigned FastISel::FastEmit_f(MVT, MVT,
909 unsigned, const ConstantFP * /*FPImm*/) {
913 unsigned FastISel::FastEmit_ri(MVT, MVT,
915 unsigned /*Op0*/, bool /*Op0IsKill*/,
920 unsigned FastISel::FastEmit_rf(MVT, MVT,
922 unsigned /*Op0*/, bool /*Op0IsKill*/,
923 const ConstantFP * /*FPImm*/) {
927 unsigned FastISel::FastEmit_rri(MVT, MVT,
929 unsigned /*Op0*/, bool /*Op0IsKill*/,
930 unsigned /*Op1*/, bool /*Op1IsKill*/,
935 /// FastEmit_ri_ - This method is a wrapper of FastEmit_ri. It first tries
936 /// to emit an instruction with an immediate operand using FastEmit_ri.
937 /// If that fails, it materializes the immediate into a register and try
938 /// FastEmit_rr instead.
939 unsigned FastISel::FastEmit_ri_(MVT VT, unsigned Opcode,
940 unsigned Op0, bool Op0IsKill,
941 uint64_t Imm, MVT ImmType) {
942 // First check if immediate type is legal. If not, we can't use the ri form.
943 unsigned ResultReg = FastEmit_ri(VT, VT, Opcode, Op0, Op0IsKill, Imm);
946 unsigned MaterialReg = FastEmit_i(ImmType, ImmType, ISD::Constant, Imm);
947 if (MaterialReg == 0)
949 return FastEmit_rr(VT, VT, Opcode,
951 MaterialReg, /*Kill=*/true);
954 /// FastEmit_rf_ - This method is a wrapper of FastEmit_ri. It first tries
955 /// to emit an instruction with a floating-point immediate operand using
956 /// FastEmit_rf. If that fails, it materializes the immediate into a register
957 /// and try FastEmit_rr instead.
958 unsigned FastISel::FastEmit_rf_(MVT VT, unsigned Opcode,
959 unsigned Op0, bool Op0IsKill,
960 const ConstantFP *FPImm, MVT ImmType) {
961 // First check if immediate type is legal. If not, we can't use the rf form.
962 unsigned ResultReg = FastEmit_rf(VT, VT, Opcode, Op0, Op0IsKill, FPImm);
966 // Materialize the constant in a register.
967 unsigned MaterialReg = FastEmit_f(ImmType, ImmType, ISD::ConstantFP, FPImm);
968 if (MaterialReg == 0) {
969 // If the target doesn't have a way to directly enter a floating-point
970 // value into a register, use an alternate approach.
971 // TODO: The current approach only supports floating-point constants
972 // that can be constructed by conversion from integer values. This should
973 // be replaced by code that creates a load from a constant-pool entry,
974 // which will require some target-specific work.
975 const APFloat &Flt = FPImm->getValueAPF();
976 EVT IntVT = TLI.getPointerTy();
979 uint32_t IntBitWidth = IntVT.getSizeInBits();
981 (void) Flt.convertToInteger(x, IntBitWidth, /*isSigned=*/true,
982 APFloat::rmTowardZero, &isExact);
985 APInt IntVal(IntBitWidth, 2, x);
987 unsigned IntegerReg = FastEmit_i(IntVT.getSimpleVT(), IntVT.getSimpleVT(),
988 ISD::Constant, IntVal.getZExtValue());
991 MaterialReg = FastEmit_r(IntVT.getSimpleVT(), VT,
992 ISD::SINT_TO_FP, IntegerReg, /*Kill=*/true);
993 if (MaterialReg == 0)
996 return FastEmit_rr(VT, VT, Opcode,
998 MaterialReg, /*Kill=*/true);
1001 unsigned FastISel::createResultReg(const TargetRegisterClass* RC) {
1002 return MRI.createVirtualRegister(RC);
1005 unsigned FastISel::FastEmitInst_(unsigned MachineInstOpcode,
1006 const TargetRegisterClass* RC) {
1007 unsigned ResultReg = createResultReg(RC);
1008 const TargetInstrDesc &II = TII.get(MachineInstOpcode);
1010 BuildMI(MBB, DL, II, ResultReg);
1014 unsigned FastISel::FastEmitInst_r(unsigned MachineInstOpcode,
1015 const TargetRegisterClass *RC,
1016 unsigned Op0, bool Op0IsKill) {
1017 unsigned ResultReg = createResultReg(RC);
1018 const TargetInstrDesc &II = TII.get(MachineInstOpcode);
1020 if (II.getNumDefs() >= 1)
1021 BuildMI(MBB, DL, II, ResultReg).addReg(Op0, Op0IsKill * RegState::Kill);
1023 BuildMI(MBB, DL, II).addReg(Op0, Op0IsKill * RegState::Kill);
1024 bool InsertedCopy = TII.copyRegToReg(*MBB, MBB->end(), ResultReg,
1025 II.ImplicitDefs[0], RC, RC, DL);
1033 unsigned FastISel::FastEmitInst_rr(unsigned MachineInstOpcode,
1034 const TargetRegisterClass *RC,
1035 unsigned Op0, bool Op0IsKill,
1036 unsigned Op1, bool Op1IsKill) {
1037 unsigned ResultReg = createResultReg(RC);
1038 const TargetInstrDesc &II = TII.get(MachineInstOpcode);
1040 if (II.getNumDefs() >= 1)
1041 BuildMI(MBB, DL, II, ResultReg)
1042 .addReg(Op0, Op0IsKill * RegState::Kill)
1043 .addReg(Op1, Op1IsKill * RegState::Kill);
1045 BuildMI(MBB, DL, II)
1046 .addReg(Op0, Op0IsKill * RegState::Kill)
1047 .addReg(Op1, Op1IsKill * RegState::Kill);
1048 bool InsertedCopy = TII.copyRegToReg(*MBB, MBB->end(), ResultReg,
1049 II.ImplicitDefs[0], RC, RC, DL);
1056 unsigned FastISel::FastEmitInst_ri(unsigned MachineInstOpcode,
1057 const TargetRegisterClass *RC,
1058 unsigned Op0, bool Op0IsKill,
1060 unsigned ResultReg = createResultReg(RC);
1061 const TargetInstrDesc &II = TII.get(MachineInstOpcode);
1063 if (II.getNumDefs() >= 1)
1064 BuildMI(MBB, DL, II, ResultReg)
1065 .addReg(Op0, Op0IsKill * RegState::Kill)
1068 BuildMI(MBB, DL, II)
1069 .addReg(Op0, Op0IsKill * RegState::Kill)
1071 bool InsertedCopy = TII.copyRegToReg(*MBB, MBB->end(), ResultReg,
1072 II.ImplicitDefs[0], RC, RC, DL);
1079 unsigned FastISel::FastEmitInst_rf(unsigned MachineInstOpcode,
1080 const TargetRegisterClass *RC,
1081 unsigned Op0, bool Op0IsKill,
1082 const ConstantFP *FPImm) {
1083 unsigned ResultReg = createResultReg(RC);
1084 const TargetInstrDesc &II = TII.get(MachineInstOpcode);
1086 if (II.getNumDefs() >= 1)
1087 BuildMI(MBB, DL, II, ResultReg)
1088 .addReg(Op0, Op0IsKill * RegState::Kill)
1091 BuildMI(MBB, DL, II)
1092 .addReg(Op0, Op0IsKill * RegState::Kill)
1094 bool InsertedCopy = TII.copyRegToReg(*MBB, MBB->end(), ResultReg,
1095 II.ImplicitDefs[0], RC, RC, DL);
1102 unsigned FastISel::FastEmitInst_rri(unsigned MachineInstOpcode,
1103 const TargetRegisterClass *RC,
1104 unsigned Op0, bool Op0IsKill,
1105 unsigned Op1, bool Op1IsKill,
1107 unsigned ResultReg = createResultReg(RC);
1108 const TargetInstrDesc &II = TII.get(MachineInstOpcode);
1110 if (II.getNumDefs() >= 1)
1111 BuildMI(MBB, DL, II, ResultReg)
1112 .addReg(Op0, Op0IsKill * RegState::Kill)
1113 .addReg(Op1, Op1IsKill * RegState::Kill)
1116 BuildMI(MBB, DL, II)
1117 .addReg(Op0, Op0IsKill * RegState::Kill)
1118 .addReg(Op1, Op1IsKill * RegState::Kill)
1120 bool InsertedCopy = TII.copyRegToReg(*MBB, MBB->end(), ResultReg,
1121 II.ImplicitDefs[0], RC, RC, DL);
1128 unsigned FastISel::FastEmitInst_i(unsigned MachineInstOpcode,
1129 const TargetRegisterClass *RC,
1131 unsigned ResultReg = createResultReg(RC);
1132 const TargetInstrDesc &II = TII.get(MachineInstOpcode);
1134 if (II.getNumDefs() >= 1)
1135 BuildMI(MBB, DL, II, ResultReg).addImm(Imm);
1137 BuildMI(MBB, DL, II).addImm(Imm);
1138 bool InsertedCopy = TII.copyRegToReg(*MBB, MBB->end(), ResultReg,
1139 II.ImplicitDefs[0], RC, RC, DL);
1146 unsigned FastISel::FastEmitInst_extractsubreg(MVT RetVT,
1147 unsigned Op0, bool Op0IsKill,
1149 const TargetRegisterClass* RC = MRI.getRegClass(Op0);
1151 unsigned ResultReg = createResultReg(TLI.getRegClassFor(RetVT));
1152 const TargetInstrDesc &II = TII.get(TargetOpcode::EXTRACT_SUBREG);
1154 if (II.getNumDefs() >= 1)
1155 BuildMI(MBB, DL, II, ResultReg)
1156 .addReg(Op0, Op0IsKill * RegState::Kill)
1159 BuildMI(MBB, DL, II)
1160 .addReg(Op0, Op0IsKill * RegState::Kill)
1162 bool InsertedCopy = TII.copyRegToReg(*MBB, MBB->end(), ResultReg,
1163 II.ImplicitDefs[0], RC, RC, DL);
1170 /// FastEmitZExtFromI1 - Emit MachineInstrs to compute the value of Op
1171 /// with all but the least significant bit set to zero.
1172 unsigned FastISel::FastEmitZExtFromI1(MVT VT, unsigned Op0, bool Op0IsKill) {
1173 return FastEmit_ri(VT, VT, ISD::AND, Op0, Op0IsKill, 1);
1176 /// HandlePHINodesInSuccessorBlocks - Handle PHI nodes in successor blocks.
1177 /// Emit code to ensure constants are copied into registers when needed.
1178 /// Remember the virtual registers that need to be added to the Machine PHI
1179 /// nodes as input. We cannot just directly add them, because expansion
1180 /// might result in multiple MBB's for one BB. As such, the start of the
1181 /// BB might correspond to a different MBB than the end.
1182 bool FastISel::HandlePHINodesInSuccessorBlocks(const BasicBlock *LLVMBB) {
1183 const TerminatorInst *TI = LLVMBB->getTerminator();
1185 SmallPtrSet<MachineBasicBlock *, 4> SuccsHandled;
1186 unsigned OrigNumPHINodesToUpdate = PHINodesToUpdate.size();
1188 // Check successor nodes' PHI nodes that expect a constant to be available
1190 for (unsigned succ = 0, e = TI->getNumSuccessors(); succ != e; ++succ) {
1191 const BasicBlock *SuccBB = TI->getSuccessor(succ);
1192 if (!isa<PHINode>(SuccBB->begin())) continue;
1193 MachineBasicBlock *SuccMBB = MBBMap[SuccBB];
1195 // If this terminator has multiple identical successors (common for
1196 // switches), only handle each succ once.
1197 if (!SuccsHandled.insert(SuccMBB)) continue;
1199 MachineBasicBlock::iterator MBBI = SuccMBB->begin();
1201 // At this point we know that there is a 1-1 correspondence between LLVM PHI
1202 // nodes and Machine PHI nodes, but the incoming operands have not been
1204 for (BasicBlock::const_iterator I = SuccBB->begin();
1205 const PHINode *PN = dyn_cast<PHINode>(I); ++I) {
1207 // Ignore dead phi's.
1208 if (PN->use_empty()) continue;
1210 // Only handle legal types. Two interesting things to note here. First,
1211 // by bailing out early, we may leave behind some dead instructions,
1212 // since SelectionDAG's HandlePHINodesInSuccessorBlocks will insert its
1213 // own moves. Second, this check is necessary becuase FastISel doesn't
1214 // use CreateReg to create registers, so it always creates
1215 // exactly one register for each non-void instruction.
1216 EVT VT = TLI.getValueType(PN->getType(), /*AllowUnknown=*/true);
1217 if (VT == MVT::Other || !TLI.isTypeLegal(VT)) {
1220 VT = TLI.getTypeToTransformTo(LLVMBB->getContext(), VT);
1222 PHINodesToUpdate.resize(OrigNumPHINodesToUpdate);
1227 const Value *PHIOp = PN->getIncomingValueForBlock(LLVMBB);
1229 // Set the DebugLoc for the copy. Prefer the location of the operand
1230 // if there is one; use the location of the PHI otherwise.
1231 DL = PN->getDebugLoc();
1232 if (const Instruction *Inst = dyn_cast<Instruction>(PHIOp))
1233 DL = Inst->getDebugLoc();
1235 unsigned Reg = getRegForValue(PHIOp);
1237 PHINodesToUpdate.resize(OrigNumPHINodesToUpdate);
1240 PHINodesToUpdate.push_back(std::make_pair(MBBI++, Reg));