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/FunctionLoweringInfo.h"
48 #include "llvm/CodeGen/MachineInstrBuilder.h"
49 #include "llvm/CodeGen/MachineModuleInfo.h"
50 #include "llvm/CodeGen/MachineRegisterInfo.h"
51 #include "llvm/Analysis/DebugInfo.h"
52 #include "llvm/Analysis/Loads.h"
53 #include "llvm/Target/TargetData.h"
54 #include "llvm/Target/TargetInstrInfo.h"
55 #include "llvm/Target/TargetLowering.h"
56 #include "llvm/Target/TargetMachine.h"
57 #include "llvm/Support/ErrorHandling.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 = FuncInfo.ValueMap.find(V);
104 if (I != FuncInfo.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))
115 FuncInfo.ValueMap[V] = Reg;
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 = FuncInfo.ValueMap.find(V);
193 if (I != FuncInfo.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 = FuncInfo.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 !FuncInfo.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 FuncInfo.StaticAllocaMap.find(AI);
418 if (SI == FuncInfo.StaticAllocaMap.end()) break; // VLAs.
420 if (!DI->getDebugLoc().isUnknown())
421 FuncInfo.MF->getMMI().setVariableDbgInfo(DI->getVariable(),
422 FI, DI->getDebugLoc());
424 // Building the map above is target independent. Generating DBG_VALUE
425 // inline is target dependent; do this now.
426 (void)TargetSelectInstruction(cast<Instruction>(I));
429 case Intrinsic::dbg_value: {
430 // This form of DBG_VALUE is target-independent.
431 const DbgValueInst *DI = cast<DbgValueInst>(I);
432 const TargetInstrDesc &II = TII.get(TargetOpcode::DBG_VALUE);
433 const Value *V = DI->getValue();
435 // Currently the optimizer can produce this; insert an undef to
436 // help debugging. Probably the optimizer should not do this.
437 BuildMI(MBB, DL, II).addReg(0U).addImm(DI->getOffset()).
438 addMetadata(DI->getVariable());
439 } else if (const ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
440 BuildMI(MBB, DL, II).addImm(CI->getZExtValue()).addImm(DI->getOffset()).
441 addMetadata(DI->getVariable());
442 } else if (const ConstantFP *CF = dyn_cast<ConstantFP>(V)) {
443 BuildMI(MBB, DL, II).addFPImm(CF).addImm(DI->getOffset()).
444 addMetadata(DI->getVariable());
445 } else if (unsigned Reg = lookUpRegForValue(V)) {
446 BuildMI(MBB, DL, II).addReg(Reg, RegState::Debug).addImm(DI->getOffset()).
447 addMetadata(DI->getVariable());
449 // We can't yet handle anything else here because it would require
450 // generating code, thus altering codegen because of debug info.
451 // Insert an undef so we can see what we dropped.
452 BuildMI(MBB, DL, II).addReg(0U).addImm(DI->getOffset()).
453 addMetadata(DI->getVariable());
457 case Intrinsic::eh_exception: {
458 EVT VT = TLI.getValueType(I->getType());
459 switch (TLI.getOperationAction(ISD::EXCEPTIONADDR, VT)) {
461 case TargetLowering::Expand: {
462 assert(MBB->isLandingPad() && "Call to eh.exception not in landing pad!");
463 unsigned Reg = TLI.getExceptionAddressRegister();
464 const TargetRegisterClass *RC = TLI.getRegClassFor(VT);
465 unsigned ResultReg = createResultReg(RC);
466 bool InsertedCopy = TII.copyRegToReg(*MBB, MBB->end(), ResultReg,
468 assert(InsertedCopy && "Can't copy address registers!");
469 InsertedCopy = InsertedCopy;
470 UpdateValueMap(I, ResultReg);
476 case Intrinsic::eh_selector: {
477 EVT VT = TLI.getValueType(I->getType());
478 switch (TLI.getOperationAction(ISD::EHSELECTION, VT)) {
480 case TargetLowering::Expand: {
481 if (MBB->isLandingPad())
482 AddCatchInfo(*cast<CallInst>(I), &FuncInfo.MF->getMMI(), MBB);
485 FuncInfo.CatchInfoLost.insert(cast<CallInst>(I));
487 // FIXME: Mark exception selector register as live in. Hack for PR1508.
488 unsigned Reg = TLI.getExceptionSelectorRegister();
489 if (Reg) MBB->addLiveIn(Reg);
492 unsigned Reg = TLI.getExceptionSelectorRegister();
493 EVT SrcVT = TLI.getPointerTy();
494 const TargetRegisterClass *RC = TLI.getRegClassFor(SrcVT);
495 unsigned ResultReg = createResultReg(RC);
496 bool InsertedCopy = TII.copyRegToReg(*MBB, MBB->end(), ResultReg, Reg,
498 assert(InsertedCopy && "Can't copy address registers!");
499 InsertedCopy = InsertedCopy;
501 bool ResultRegIsKill = hasTrivialKill(I);
503 // Cast the register to the type of the selector.
504 if (SrcVT.bitsGT(MVT::i32))
505 ResultReg = FastEmit_r(SrcVT.getSimpleVT(), MVT::i32, ISD::TRUNCATE,
506 ResultReg, ResultRegIsKill);
507 else if (SrcVT.bitsLT(MVT::i32))
508 ResultReg = FastEmit_r(SrcVT.getSimpleVT(), MVT::i32,
509 ISD::SIGN_EXTEND, ResultReg, ResultRegIsKill);
511 // Unhandled operand. Halt "fast" selection and bail.
514 UpdateValueMap(I, ResultReg);
523 // An arbitrary call. Bail.
527 bool FastISel::SelectCast(const User *I, unsigned Opcode) {
528 EVT SrcVT = TLI.getValueType(I->getOperand(0)->getType());
529 EVT DstVT = TLI.getValueType(I->getType());
531 if (SrcVT == MVT::Other || !SrcVT.isSimple() ||
532 DstVT == MVT::Other || !DstVT.isSimple())
533 // Unhandled type. Halt "fast" selection and bail.
536 // Check if the destination type is legal. Or as a special case,
537 // it may be i1 if we're doing a truncate because that's
538 // easy and somewhat common.
539 if (!TLI.isTypeLegal(DstVT))
540 if (DstVT != MVT::i1 || Opcode != ISD::TRUNCATE)
541 // Unhandled type. Halt "fast" selection and bail.
544 // Check if the source operand is legal. Or as a special case,
545 // it may be i1 if we're doing zero-extension because that's
546 // easy and somewhat common.
547 if (!TLI.isTypeLegal(SrcVT))
548 if (SrcVT != MVT::i1 || Opcode != ISD::ZERO_EXTEND)
549 // Unhandled type. Halt "fast" selection and bail.
552 unsigned InputReg = getRegForValue(I->getOperand(0));
554 // Unhandled operand. Halt "fast" selection and bail.
557 bool InputRegIsKill = hasTrivialKill(I->getOperand(0));
559 // If the operand is i1, arrange for the high bits in the register to be zero.
560 if (SrcVT == MVT::i1) {
561 SrcVT = TLI.getTypeToTransformTo(I->getContext(), SrcVT);
562 InputReg = FastEmitZExtFromI1(SrcVT.getSimpleVT(), InputReg, InputRegIsKill);
565 InputRegIsKill = true;
567 // If the result is i1, truncate to the target's type for i1 first.
568 if (DstVT == MVT::i1)
569 DstVT = TLI.getTypeToTransformTo(I->getContext(), DstVT);
571 unsigned ResultReg = FastEmit_r(SrcVT.getSimpleVT(),
574 InputReg, InputRegIsKill);
578 UpdateValueMap(I, ResultReg);
582 bool FastISel::SelectBitCast(const User *I) {
583 // If the bitcast doesn't change the type, just use the operand value.
584 if (I->getType() == I->getOperand(0)->getType()) {
585 unsigned Reg = getRegForValue(I->getOperand(0));
588 UpdateValueMap(I, Reg);
592 // Bitcasts of other values become reg-reg copies or BIT_CONVERT operators.
593 EVT SrcVT = TLI.getValueType(I->getOperand(0)->getType());
594 EVT DstVT = TLI.getValueType(I->getType());
596 if (SrcVT == MVT::Other || !SrcVT.isSimple() ||
597 DstVT == MVT::Other || !DstVT.isSimple() ||
598 !TLI.isTypeLegal(SrcVT) || !TLI.isTypeLegal(DstVT))
599 // Unhandled type. Halt "fast" selection and bail.
602 unsigned Op0 = getRegForValue(I->getOperand(0));
604 // Unhandled operand. Halt "fast" selection and bail.
607 bool Op0IsKill = hasTrivialKill(I->getOperand(0));
609 // First, try to perform the bitcast by inserting a reg-reg copy.
610 unsigned ResultReg = 0;
611 if (SrcVT.getSimpleVT() == DstVT.getSimpleVT()) {
612 TargetRegisterClass* SrcClass = TLI.getRegClassFor(SrcVT);
613 TargetRegisterClass* DstClass = TLI.getRegClassFor(DstVT);
614 ResultReg = createResultReg(DstClass);
616 bool InsertedCopy = TII.copyRegToReg(*MBB, MBB->end(), ResultReg,
617 Op0, DstClass, SrcClass, DL);
622 // If the reg-reg copy failed, select a BIT_CONVERT opcode.
624 ResultReg = FastEmit_r(SrcVT.getSimpleVT(), DstVT.getSimpleVT(),
625 ISD::BIT_CONVERT, Op0, Op0IsKill);
630 UpdateValueMap(I, ResultReg);
635 FastISel::SelectInstruction(const Instruction *I) {
636 // Just before the terminator instruction, insert instructions to
637 // feed PHI nodes in successor blocks.
638 if (isa<TerminatorInst>(I))
639 if (!HandlePHINodesInSuccessorBlocks(I->getParent()))
642 DL = I->getDebugLoc();
644 // First, try doing target-independent selection.
645 if (SelectOperator(I, I->getOpcode())) {
650 // Next, try calling the target to attempt to handle the instruction.
651 if (TargetSelectInstruction(I)) {
660 /// FastEmitBranch - Emit an unconditional branch to the given block,
661 /// unless it is the immediate (fall-through) successor, and update
664 FastISel::FastEmitBranch(MachineBasicBlock *MSucc, DebugLoc DL) {
665 if (MBB->isLayoutSuccessor(MSucc)) {
666 // The unconditional fall-through case, which needs no instructions.
668 // The unconditional branch case.
669 TII.InsertBranch(*MBB, MSucc, NULL, SmallVector<MachineOperand, 0>(), DL);
671 MBB->addSuccessor(MSucc);
674 /// SelectFNeg - Emit an FNeg operation.
677 FastISel::SelectFNeg(const User *I) {
678 unsigned OpReg = getRegForValue(BinaryOperator::getFNegArgument(I));
679 if (OpReg == 0) return false;
681 bool OpRegIsKill = hasTrivialKill(I);
683 // If the target has ISD::FNEG, use it.
684 EVT VT = TLI.getValueType(I->getType());
685 unsigned ResultReg = FastEmit_r(VT.getSimpleVT(), VT.getSimpleVT(),
686 ISD::FNEG, OpReg, OpRegIsKill);
687 if (ResultReg != 0) {
688 UpdateValueMap(I, ResultReg);
692 // Bitcast the value to integer, twiddle the sign bit with xor,
693 // and then bitcast it back to floating-point.
694 if (VT.getSizeInBits() > 64) return false;
695 EVT IntVT = EVT::getIntegerVT(I->getContext(), VT.getSizeInBits());
696 if (!TLI.isTypeLegal(IntVT))
699 unsigned IntReg = FastEmit_r(VT.getSimpleVT(), IntVT.getSimpleVT(),
700 ISD::BIT_CONVERT, OpReg, OpRegIsKill);
704 unsigned IntResultReg = FastEmit_ri_(IntVT.getSimpleVT(), ISD::XOR,
705 IntReg, /*Kill=*/true,
706 UINT64_C(1) << (VT.getSizeInBits()-1),
707 IntVT.getSimpleVT());
708 if (IntResultReg == 0)
711 ResultReg = FastEmit_r(IntVT.getSimpleVT(), VT.getSimpleVT(),
712 ISD::BIT_CONVERT, IntResultReg, /*Kill=*/true);
716 UpdateValueMap(I, ResultReg);
721 FastISel::SelectLoad(const User *I) {
722 LoadInst *LI = const_cast<LoadInst *>(cast<LoadInst>(I));
724 // For a load from an alloca, make a limited effort to find the value
725 // already available in a register, avoiding redundant loads.
726 if (!LI->isVolatile() && isa<AllocaInst>(LI->getPointerOperand())) {
727 BasicBlock::iterator ScanFrom = LI;
728 if (const Value *V = FindAvailableLoadedValue(LI->getPointerOperand(),
729 LI->getParent(), ScanFrom)) {
730 unsigned ResultReg = getRegForValue(V);
731 if (ResultReg != 0) {
732 UpdateValueMap(I, ResultReg);
742 FastISel::SelectOperator(const User *I, unsigned Opcode) {
744 case Instruction::Load:
745 return SelectLoad(I);
746 case Instruction::Add:
747 return SelectBinaryOp(I, ISD::ADD);
748 case Instruction::FAdd:
749 return SelectBinaryOp(I, ISD::FADD);
750 case Instruction::Sub:
751 return SelectBinaryOp(I, ISD::SUB);
752 case Instruction::FSub:
753 // FNeg is currently represented in LLVM IR as a special case of FSub.
754 if (BinaryOperator::isFNeg(I))
755 return SelectFNeg(I);
756 return SelectBinaryOp(I, ISD::FSUB);
757 case Instruction::Mul:
758 return SelectBinaryOp(I, ISD::MUL);
759 case Instruction::FMul:
760 return SelectBinaryOp(I, ISD::FMUL);
761 case Instruction::SDiv:
762 return SelectBinaryOp(I, ISD::SDIV);
763 case Instruction::UDiv:
764 return SelectBinaryOp(I, ISD::UDIV);
765 case Instruction::FDiv:
766 return SelectBinaryOp(I, ISD::FDIV);
767 case Instruction::SRem:
768 return SelectBinaryOp(I, ISD::SREM);
769 case Instruction::URem:
770 return SelectBinaryOp(I, ISD::UREM);
771 case Instruction::FRem:
772 return SelectBinaryOp(I, ISD::FREM);
773 case Instruction::Shl:
774 return SelectBinaryOp(I, ISD::SHL);
775 case Instruction::LShr:
776 return SelectBinaryOp(I, ISD::SRL);
777 case Instruction::AShr:
778 return SelectBinaryOp(I, ISD::SRA);
779 case Instruction::And:
780 return SelectBinaryOp(I, ISD::AND);
781 case Instruction::Or:
782 return SelectBinaryOp(I, ISD::OR);
783 case Instruction::Xor:
784 return SelectBinaryOp(I, ISD::XOR);
786 case Instruction::GetElementPtr:
787 return SelectGetElementPtr(I);
789 case Instruction::Br: {
790 const BranchInst *BI = cast<BranchInst>(I);
792 if (BI->isUnconditional()) {
793 const BasicBlock *LLVMSucc = BI->getSuccessor(0);
794 MachineBasicBlock *MSucc = FuncInfo.MBBMap[LLVMSucc];
795 FastEmitBranch(MSucc, BI->getDebugLoc());
799 // Conditional branches are not handed yet.
800 // Halt "fast" selection and bail.
804 case Instruction::Unreachable:
808 case Instruction::Alloca:
809 // FunctionLowering has the static-sized case covered.
810 if (FuncInfo.StaticAllocaMap.count(cast<AllocaInst>(I)))
813 // Dynamic-sized alloca is not handled yet.
816 case Instruction::Call:
817 return SelectCall(I);
819 case Instruction::BitCast:
820 return SelectBitCast(I);
822 case Instruction::FPToSI:
823 return SelectCast(I, ISD::FP_TO_SINT);
824 case Instruction::ZExt:
825 return SelectCast(I, ISD::ZERO_EXTEND);
826 case Instruction::SExt:
827 return SelectCast(I, ISD::SIGN_EXTEND);
828 case Instruction::Trunc:
829 return SelectCast(I, ISD::TRUNCATE);
830 case Instruction::SIToFP:
831 return SelectCast(I, ISD::SINT_TO_FP);
833 case Instruction::IntToPtr: // Deliberate fall-through.
834 case Instruction::PtrToInt: {
835 EVT SrcVT = TLI.getValueType(I->getOperand(0)->getType());
836 EVT DstVT = TLI.getValueType(I->getType());
837 if (DstVT.bitsGT(SrcVT))
838 return SelectCast(I, ISD::ZERO_EXTEND);
839 if (DstVT.bitsLT(SrcVT))
840 return SelectCast(I, ISD::TRUNCATE);
841 unsigned Reg = getRegForValue(I->getOperand(0));
842 if (Reg == 0) return false;
843 UpdateValueMap(I, Reg);
847 case Instruction::PHI:
848 llvm_unreachable("FastISel shouldn't visit PHI nodes!");
851 // Unhandled instruction. Halt "fast" selection and bail.
856 FastISel::FastISel(FunctionLoweringInfo &funcInfo)
859 MRI(FuncInfo.MF->getRegInfo()),
860 MFI(*FuncInfo.MF->getFrameInfo()),
861 MCP(*FuncInfo.MF->getConstantPool()),
862 TM(FuncInfo.MF->getTarget()),
863 TD(*TM.getTargetData()),
864 TII(*TM.getInstrInfo()),
865 TLI(*TM.getTargetLowering()),
866 TRI(*TM.getRegisterInfo()),
870 FastISel::~FastISel() {}
872 unsigned FastISel::FastEmit_(MVT, MVT,
877 unsigned FastISel::FastEmit_r(MVT, MVT,
879 unsigned /*Op0*/, bool /*Op0IsKill*/) {
883 unsigned FastISel::FastEmit_rr(MVT, MVT,
885 unsigned /*Op0*/, bool /*Op0IsKill*/,
886 unsigned /*Op1*/, bool /*Op1IsKill*/) {
890 unsigned FastISel::FastEmit_i(MVT, MVT, unsigned, uint64_t /*Imm*/) {
894 unsigned FastISel::FastEmit_f(MVT, MVT,
895 unsigned, const ConstantFP * /*FPImm*/) {
899 unsigned FastISel::FastEmit_ri(MVT, MVT,
901 unsigned /*Op0*/, bool /*Op0IsKill*/,
906 unsigned FastISel::FastEmit_rf(MVT, MVT,
908 unsigned /*Op0*/, bool /*Op0IsKill*/,
909 const ConstantFP * /*FPImm*/) {
913 unsigned FastISel::FastEmit_rri(MVT, MVT,
915 unsigned /*Op0*/, bool /*Op0IsKill*/,
916 unsigned /*Op1*/, bool /*Op1IsKill*/,
921 /// FastEmit_ri_ - This method is a wrapper of FastEmit_ri. It first tries
922 /// to emit an instruction with an immediate operand using FastEmit_ri.
923 /// If that fails, it materializes the immediate into a register and try
924 /// FastEmit_rr instead.
925 unsigned FastISel::FastEmit_ri_(MVT VT, unsigned Opcode,
926 unsigned Op0, bool Op0IsKill,
927 uint64_t Imm, MVT ImmType) {
928 // First check if immediate type is legal. If not, we can't use the ri form.
929 unsigned ResultReg = FastEmit_ri(VT, VT, Opcode, Op0, Op0IsKill, Imm);
932 unsigned MaterialReg = FastEmit_i(ImmType, ImmType, ISD::Constant, Imm);
933 if (MaterialReg == 0)
935 return FastEmit_rr(VT, VT, Opcode,
937 MaterialReg, /*Kill=*/true);
940 /// FastEmit_rf_ - This method is a wrapper of FastEmit_ri. It first tries
941 /// to emit an instruction with a floating-point immediate operand using
942 /// FastEmit_rf. If that fails, it materializes the immediate into a register
943 /// and try FastEmit_rr instead.
944 unsigned FastISel::FastEmit_rf_(MVT VT, unsigned Opcode,
945 unsigned Op0, bool Op0IsKill,
946 const ConstantFP *FPImm, MVT ImmType) {
947 // First check if immediate type is legal. If not, we can't use the rf form.
948 unsigned ResultReg = FastEmit_rf(VT, VT, Opcode, Op0, Op0IsKill, FPImm);
952 // Materialize the constant in a register.
953 unsigned MaterialReg = FastEmit_f(ImmType, ImmType, ISD::ConstantFP, FPImm);
954 if (MaterialReg == 0) {
955 // If the target doesn't have a way to directly enter a floating-point
956 // value into a register, use an alternate approach.
957 // TODO: The current approach only supports floating-point constants
958 // that can be constructed by conversion from integer values. This should
959 // be replaced by code that creates a load from a constant-pool entry,
960 // which will require some target-specific work.
961 const APFloat &Flt = FPImm->getValueAPF();
962 EVT IntVT = TLI.getPointerTy();
965 uint32_t IntBitWidth = IntVT.getSizeInBits();
967 (void) Flt.convertToInteger(x, IntBitWidth, /*isSigned=*/true,
968 APFloat::rmTowardZero, &isExact);
971 APInt IntVal(IntBitWidth, 2, x);
973 unsigned IntegerReg = FastEmit_i(IntVT.getSimpleVT(), IntVT.getSimpleVT(),
974 ISD::Constant, IntVal.getZExtValue());
977 MaterialReg = FastEmit_r(IntVT.getSimpleVT(), VT,
978 ISD::SINT_TO_FP, IntegerReg, /*Kill=*/true);
979 if (MaterialReg == 0)
982 return FastEmit_rr(VT, VT, Opcode,
984 MaterialReg, /*Kill=*/true);
987 unsigned FastISel::createResultReg(const TargetRegisterClass* RC) {
988 return MRI.createVirtualRegister(RC);
991 unsigned FastISel::FastEmitInst_(unsigned MachineInstOpcode,
992 const TargetRegisterClass* RC) {
993 unsigned ResultReg = createResultReg(RC);
994 const TargetInstrDesc &II = TII.get(MachineInstOpcode);
996 BuildMI(MBB, DL, II, ResultReg);
1000 unsigned FastISel::FastEmitInst_r(unsigned MachineInstOpcode,
1001 const TargetRegisterClass *RC,
1002 unsigned Op0, bool Op0IsKill) {
1003 unsigned ResultReg = createResultReg(RC);
1004 const TargetInstrDesc &II = TII.get(MachineInstOpcode);
1006 if (II.getNumDefs() >= 1)
1007 BuildMI(MBB, DL, II, ResultReg).addReg(Op0, Op0IsKill * RegState::Kill);
1009 BuildMI(MBB, DL, II).addReg(Op0, Op0IsKill * RegState::Kill);
1010 bool InsertedCopy = TII.copyRegToReg(*MBB, MBB->end(), ResultReg,
1011 II.ImplicitDefs[0], RC, RC, DL);
1019 unsigned FastISel::FastEmitInst_rr(unsigned MachineInstOpcode,
1020 const TargetRegisterClass *RC,
1021 unsigned Op0, bool Op0IsKill,
1022 unsigned Op1, bool Op1IsKill) {
1023 unsigned ResultReg = createResultReg(RC);
1024 const TargetInstrDesc &II = TII.get(MachineInstOpcode);
1026 if (II.getNumDefs() >= 1)
1027 BuildMI(MBB, DL, II, ResultReg)
1028 .addReg(Op0, Op0IsKill * RegState::Kill)
1029 .addReg(Op1, Op1IsKill * RegState::Kill);
1031 BuildMI(MBB, DL, II)
1032 .addReg(Op0, Op0IsKill * RegState::Kill)
1033 .addReg(Op1, Op1IsKill * RegState::Kill);
1034 bool InsertedCopy = TII.copyRegToReg(*MBB, MBB->end(), ResultReg,
1035 II.ImplicitDefs[0], RC, RC, DL);
1042 unsigned FastISel::FastEmitInst_ri(unsigned MachineInstOpcode,
1043 const TargetRegisterClass *RC,
1044 unsigned Op0, bool Op0IsKill,
1046 unsigned ResultReg = createResultReg(RC);
1047 const TargetInstrDesc &II = TII.get(MachineInstOpcode);
1049 if (II.getNumDefs() >= 1)
1050 BuildMI(MBB, DL, II, ResultReg)
1051 .addReg(Op0, Op0IsKill * RegState::Kill)
1054 BuildMI(MBB, DL, II)
1055 .addReg(Op0, Op0IsKill * RegState::Kill)
1057 bool InsertedCopy = TII.copyRegToReg(*MBB, MBB->end(), ResultReg,
1058 II.ImplicitDefs[0], RC, RC, DL);
1065 unsigned FastISel::FastEmitInst_rf(unsigned MachineInstOpcode,
1066 const TargetRegisterClass *RC,
1067 unsigned Op0, bool Op0IsKill,
1068 const ConstantFP *FPImm) {
1069 unsigned ResultReg = createResultReg(RC);
1070 const TargetInstrDesc &II = TII.get(MachineInstOpcode);
1072 if (II.getNumDefs() >= 1)
1073 BuildMI(MBB, DL, II, ResultReg)
1074 .addReg(Op0, Op0IsKill * RegState::Kill)
1077 BuildMI(MBB, DL, II)
1078 .addReg(Op0, Op0IsKill * RegState::Kill)
1080 bool InsertedCopy = TII.copyRegToReg(*MBB, MBB->end(), ResultReg,
1081 II.ImplicitDefs[0], RC, RC, DL);
1088 unsigned FastISel::FastEmitInst_rri(unsigned MachineInstOpcode,
1089 const TargetRegisterClass *RC,
1090 unsigned Op0, bool Op0IsKill,
1091 unsigned Op1, bool Op1IsKill,
1093 unsigned ResultReg = createResultReg(RC);
1094 const TargetInstrDesc &II = TII.get(MachineInstOpcode);
1096 if (II.getNumDefs() >= 1)
1097 BuildMI(MBB, DL, II, ResultReg)
1098 .addReg(Op0, Op0IsKill * RegState::Kill)
1099 .addReg(Op1, Op1IsKill * RegState::Kill)
1102 BuildMI(MBB, DL, II)
1103 .addReg(Op0, Op0IsKill * RegState::Kill)
1104 .addReg(Op1, Op1IsKill * RegState::Kill)
1106 bool InsertedCopy = TII.copyRegToReg(*MBB, MBB->end(), ResultReg,
1107 II.ImplicitDefs[0], RC, RC, DL);
1114 unsigned FastISel::FastEmitInst_i(unsigned MachineInstOpcode,
1115 const TargetRegisterClass *RC,
1117 unsigned ResultReg = createResultReg(RC);
1118 const TargetInstrDesc &II = TII.get(MachineInstOpcode);
1120 if (II.getNumDefs() >= 1)
1121 BuildMI(MBB, DL, II, ResultReg).addImm(Imm);
1123 BuildMI(MBB, DL, II).addImm(Imm);
1124 bool InsertedCopy = TII.copyRegToReg(*MBB, MBB->end(), ResultReg,
1125 II.ImplicitDefs[0], RC, RC, DL);
1132 unsigned FastISel::FastEmitInst_extractsubreg(MVT RetVT,
1133 unsigned Op0, bool Op0IsKill,
1135 unsigned ResultReg = createResultReg(TLI.getRegClassFor(RetVT));
1136 assert(TargetRegisterInfo::isVirtualRegister(Op0) &&
1137 "Cannot yet extract from physregs");
1138 BuildMI(MBB, DL, TII.get(TargetOpcode::COPY), ResultReg)
1139 .addReg(Op0, getKillRegState(Op0IsKill), Idx);
1143 /// FastEmitZExtFromI1 - Emit MachineInstrs to compute the value of Op
1144 /// with all but the least significant bit set to zero.
1145 unsigned FastISel::FastEmitZExtFromI1(MVT VT, unsigned Op0, bool Op0IsKill) {
1146 return FastEmit_ri(VT, VT, ISD::AND, Op0, Op0IsKill, 1);
1149 /// HandlePHINodesInSuccessorBlocks - Handle PHI nodes in successor blocks.
1150 /// Emit code to ensure constants are copied into registers when needed.
1151 /// Remember the virtual registers that need to be added to the Machine PHI
1152 /// nodes as input. We cannot just directly add them, because expansion
1153 /// might result in multiple MBB's for one BB. As such, the start of the
1154 /// BB might correspond to a different MBB than the end.
1155 bool FastISel::HandlePHINodesInSuccessorBlocks(const BasicBlock *LLVMBB) {
1156 const TerminatorInst *TI = LLVMBB->getTerminator();
1158 SmallPtrSet<MachineBasicBlock *, 4> SuccsHandled;
1159 unsigned OrigNumPHINodesToUpdate = FuncInfo.PHINodesToUpdate.size();
1161 // Check successor nodes' PHI nodes that expect a constant to be available
1163 for (unsigned succ = 0, e = TI->getNumSuccessors(); succ != e; ++succ) {
1164 const BasicBlock *SuccBB = TI->getSuccessor(succ);
1165 if (!isa<PHINode>(SuccBB->begin())) continue;
1166 MachineBasicBlock *SuccMBB = FuncInfo.MBBMap[SuccBB];
1168 // If this terminator has multiple identical successors (common for
1169 // switches), only handle each succ once.
1170 if (!SuccsHandled.insert(SuccMBB)) continue;
1172 MachineBasicBlock::iterator MBBI = SuccMBB->begin();
1174 // At this point we know that there is a 1-1 correspondence between LLVM PHI
1175 // nodes and Machine PHI nodes, but the incoming operands have not been
1177 for (BasicBlock::const_iterator I = SuccBB->begin();
1178 const PHINode *PN = dyn_cast<PHINode>(I); ++I) {
1180 // Ignore dead phi's.
1181 if (PN->use_empty()) continue;
1183 // Only handle legal types. Two interesting things to note here. First,
1184 // by bailing out early, we may leave behind some dead instructions,
1185 // since SelectionDAG's HandlePHINodesInSuccessorBlocks will insert its
1186 // own moves. Second, this check is necessary becuase FastISel doesn't
1187 // use CreateRegs to create registers, so it always creates
1188 // exactly one register for each non-void instruction.
1189 EVT VT = TLI.getValueType(PN->getType(), /*AllowUnknown=*/true);
1190 if (VT == MVT::Other || !TLI.isTypeLegal(VT)) {
1193 VT = TLI.getTypeToTransformTo(LLVMBB->getContext(), VT);
1195 FuncInfo.PHINodesToUpdate.resize(OrigNumPHINodesToUpdate);
1200 const Value *PHIOp = PN->getIncomingValueForBlock(LLVMBB);
1202 // Set the DebugLoc for the copy. Prefer the location of the operand
1203 // if there is one; use the location of the PHI otherwise.
1204 DL = PN->getDebugLoc();
1205 if (const Instruction *Inst = dyn_cast<Instruction>(PHIOp))
1206 DL = Inst->getDebugLoc();
1208 unsigned Reg = getRegForValue(PHIOp);
1210 FuncInfo.PHINodesToUpdate.resize(OrigNumPHINodesToUpdate);
1213 FuncInfo.PHINodesToUpdate.push_back(std::make_pair(MBBI++, Reg));