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 #define DEBUG_TYPE "isel"
43 #include "llvm/CodeGen/FastISel.h"
44 #include "llvm/ADT/Optional.h"
45 #include "llvm/ADT/Statistic.h"
46 #include "llvm/Analysis/Loads.h"
47 #include "llvm/CodeGen/Analysis.h"
48 #include "llvm/CodeGen/FunctionLoweringInfo.h"
49 #include "llvm/CodeGen/MachineInstrBuilder.h"
50 #include "llvm/CodeGen/MachineModuleInfo.h"
51 #include "llvm/CodeGen/MachineRegisterInfo.h"
52 #include "llvm/DebugInfo.h"
53 #include "llvm/IR/DataLayout.h"
54 #include "llvm/IR/Function.h"
55 #include "llvm/IR/GlobalVariable.h"
56 #include "llvm/IR/Instructions.h"
57 #include "llvm/IR/IntrinsicInst.h"
58 #include "llvm/IR/Operator.h"
59 #include "llvm/Support/Debug.h"
60 #include "llvm/Support/ErrorHandling.h"
61 #include "llvm/Target/TargetInstrInfo.h"
62 #include "llvm/Target/TargetLibraryInfo.h"
63 #include "llvm/Target/TargetLowering.h"
64 #include "llvm/Target/TargetMachine.h"
67 STATISTIC(NumFastIselSuccessIndependent, "Number of insts selected by "
68 "target-independent selector");
69 STATISTIC(NumFastIselSuccessTarget, "Number of insts selected by "
70 "target-specific selector");
71 STATISTIC(NumFastIselDead, "Number of dead insts removed on failure");
73 /// startNewBlock - Set the current block to which generated machine
74 /// instructions will be appended, and clear the local CSE map.
76 void FastISel::startNewBlock() {
77 LocalValueMap.clear();
81 // Advance the emit start point past any EH_LABEL instructions.
82 MachineBasicBlock::iterator
83 I = FuncInfo.MBB->begin(), E = FuncInfo.MBB->end();
84 while (I != E && I->getOpcode() == TargetOpcode::EH_LABEL) {
88 LastLocalValue = EmitStartPt;
91 bool FastISel::LowerArguments() {
92 if (!FuncInfo.CanLowerReturn)
93 // Fallback to SDISel argument lowering code to deal with sret pointer
97 if (!FastLowerArguments())
100 // Enter arguments into ValueMap for uses in non-entry BBs.
101 for (Function::const_arg_iterator I = FuncInfo.Fn->arg_begin(),
102 E = FuncInfo.Fn->arg_end(); I != E; ++I) {
103 DenseMap<const Value *, unsigned>::iterator VI = LocalValueMap.find(I);
104 assert(VI != LocalValueMap.end() && "Missed an argument?");
105 FuncInfo.ValueMap[I] = VI->second;
110 void FastISel::flushLocalValueMap() {
111 LocalValueMap.clear();
112 LastLocalValue = EmitStartPt;
116 bool FastISel::hasTrivialKill(const Value *V) const {
117 // Don't consider constants or arguments to have trivial kills.
118 const Instruction *I = dyn_cast<Instruction>(V);
122 // No-op casts are trivially coalesced by fast-isel.
123 if (const CastInst *Cast = dyn_cast<CastInst>(I))
124 if (Cast->isNoopCast(TD.getIntPtrType(Cast->getContext())) &&
125 !hasTrivialKill(Cast->getOperand(0)))
128 // GEPs with all zero indices are trivially coalesced by fast-isel.
129 if (const GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(I))
130 if (GEP->hasAllZeroIndices() && !hasTrivialKill(GEP->getOperand(0)))
133 // Only instructions with a single use in the same basic block are considered
134 // to have trivial kills.
135 return I->hasOneUse() &&
136 !(I->getOpcode() == Instruction::BitCast ||
137 I->getOpcode() == Instruction::PtrToInt ||
138 I->getOpcode() == Instruction::IntToPtr) &&
139 cast<Instruction>(*I->use_begin())->getParent() == I->getParent();
142 unsigned FastISel::getRegForValue(const Value *V) {
143 EVT RealVT = TLI.getValueType(V->getType(), /*AllowUnknown=*/true);
144 // Don't handle non-simple values in FastISel.
145 if (!RealVT.isSimple())
148 // Ignore illegal types. We must do this before looking up the value
149 // in ValueMap because Arguments are given virtual registers regardless
150 // of whether FastISel can handle them.
151 MVT VT = RealVT.getSimpleVT();
152 if (!TLI.isTypeLegal(VT)) {
153 // Handle integer promotions, though, because they're common and easy.
154 if (VT == MVT::i1 || VT == MVT::i8 || VT == MVT::i16)
155 VT = TLI.getTypeToTransformTo(V->getContext(), VT).getSimpleVT();
160 // Look up the value to see if we already have a register for it.
161 unsigned Reg = lookUpRegForValue(V);
165 // In bottom-up mode, just create the virtual register which will be used
166 // to hold the value. It will be materialized later.
167 if (isa<Instruction>(V) &&
168 (!isa<AllocaInst>(V) ||
169 !FuncInfo.StaticAllocaMap.count(cast<AllocaInst>(V))))
170 return FuncInfo.InitializeRegForValue(V);
172 SavePoint SaveInsertPt = enterLocalValueArea();
174 // Materialize the value in a register. Emit any instructions in the
176 Reg = materializeRegForValue(V, VT);
178 leaveLocalValueArea(SaveInsertPt);
183 /// materializeRegForValue - Helper for getRegForValue. This function is
184 /// called when the value isn't already available in a register and must
185 /// be materialized with new instructions.
186 unsigned FastISel::materializeRegForValue(const Value *V, MVT VT) {
189 if (const ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
190 if (CI->getValue().getActiveBits() <= 64)
191 Reg = FastEmit_i(VT, VT, ISD::Constant, CI->getZExtValue());
192 } else if (isa<AllocaInst>(V)) {
193 Reg = TargetMaterializeAlloca(cast<AllocaInst>(V));
194 } else if (isa<ConstantPointerNull>(V)) {
195 // Translate this as an integer zero so that it can be
196 // local-CSE'd with actual integer zeros.
198 getRegForValue(Constant::getNullValue(TD.getIntPtrType(V->getContext())));
199 } else if (const ConstantFP *CF = dyn_cast<ConstantFP>(V)) {
200 if (CF->isNullValue()) {
201 Reg = TargetMaterializeFloatZero(CF);
203 // Try to emit the constant directly.
204 Reg = FastEmit_f(VT, VT, ISD::ConstantFP, CF);
208 // Try to emit the constant by using an integer constant with a cast.
209 const APFloat &Flt = CF->getValueAPF();
210 EVT IntVT = TLI.getPointerTy();
213 uint32_t IntBitWidth = IntVT.getSizeInBits();
215 (void) Flt.convertToInteger(x, IntBitWidth, /*isSigned=*/true,
216 APFloat::rmTowardZero, &isExact);
218 APInt IntVal(IntBitWidth, x);
220 unsigned IntegerReg =
221 getRegForValue(ConstantInt::get(V->getContext(), IntVal));
223 Reg = FastEmit_r(IntVT.getSimpleVT(), VT, ISD::SINT_TO_FP,
224 IntegerReg, /*Kill=*/false);
227 } else if (const Operator *Op = dyn_cast<Operator>(V)) {
228 if (!SelectOperator(Op, Op->getOpcode()))
229 if (!isa<Instruction>(Op) ||
230 !TargetSelectInstruction(cast<Instruction>(Op)))
232 Reg = lookUpRegForValue(Op);
233 } else if (isa<UndefValue>(V)) {
234 Reg = createResultReg(TLI.getRegClassFor(VT));
235 BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL,
236 TII.get(TargetOpcode::IMPLICIT_DEF), Reg);
239 // If target-independent code couldn't handle the value, give target-specific
241 if (!Reg && isa<Constant>(V))
242 Reg = TargetMaterializeConstant(cast<Constant>(V));
244 // Don't cache constant materializations in the general ValueMap.
245 // To do so would require tracking what uses they dominate.
247 LocalValueMap[V] = Reg;
248 LastLocalValue = MRI.getVRegDef(Reg);
253 unsigned FastISel::lookUpRegForValue(const Value *V) {
254 // Look up the value to see if we already have a register for it. We
255 // cache values defined by Instructions across blocks, and other values
256 // only locally. This is because Instructions already have the SSA
257 // def-dominates-use requirement enforced.
258 DenseMap<const Value *, unsigned>::iterator I = FuncInfo.ValueMap.find(V);
259 if (I != FuncInfo.ValueMap.end())
261 return LocalValueMap[V];
264 /// UpdateValueMap - Update the value map to include the new mapping for this
265 /// instruction, or insert an extra copy to get the result in a previous
266 /// determined register.
267 /// NOTE: This is only necessary because we might select a block that uses
268 /// a value before we select the block that defines the value. It might be
269 /// possible to fix this by selecting blocks in reverse postorder.
270 void FastISel::UpdateValueMap(const Value *I, unsigned Reg, unsigned NumRegs) {
271 if (!isa<Instruction>(I)) {
272 LocalValueMap[I] = Reg;
276 unsigned &AssignedReg = FuncInfo.ValueMap[I];
277 if (AssignedReg == 0)
278 // Use the new register.
280 else if (Reg != AssignedReg) {
281 // Arrange for uses of AssignedReg to be replaced by uses of Reg.
282 for (unsigned i = 0; i < NumRegs; i++)
283 FuncInfo.RegFixups[AssignedReg+i] = Reg+i;
289 std::pair<unsigned, bool> FastISel::getRegForGEPIndex(const Value *Idx) {
290 unsigned IdxN = getRegForValue(Idx);
292 // Unhandled operand. Halt "fast" selection and bail.
293 return std::pair<unsigned, bool>(0, false);
295 bool IdxNIsKill = hasTrivialKill(Idx);
297 // If the index is smaller or larger than intptr_t, truncate or extend it.
298 MVT PtrVT = TLI.getPointerTy();
299 EVT IdxVT = EVT::getEVT(Idx->getType(), /*HandleUnknown=*/false);
300 if (IdxVT.bitsLT(PtrVT)) {
301 IdxN = FastEmit_r(IdxVT.getSimpleVT(), PtrVT, ISD::SIGN_EXTEND,
305 else if (IdxVT.bitsGT(PtrVT)) {
306 IdxN = FastEmit_r(IdxVT.getSimpleVT(), PtrVT, ISD::TRUNCATE,
310 return std::pair<unsigned, bool>(IdxN, IdxNIsKill);
313 void FastISel::recomputeInsertPt() {
314 if (getLastLocalValue()) {
315 FuncInfo.InsertPt = getLastLocalValue();
316 FuncInfo.MBB = FuncInfo.InsertPt->getParent();
319 FuncInfo.InsertPt = FuncInfo.MBB->getFirstNonPHI();
321 // Now skip past any EH_LABELs, which must remain at the beginning.
322 while (FuncInfo.InsertPt != FuncInfo.MBB->end() &&
323 FuncInfo.InsertPt->getOpcode() == TargetOpcode::EH_LABEL)
327 void FastISel::removeDeadCode(MachineBasicBlock::iterator I,
328 MachineBasicBlock::iterator E) {
329 assert (I && E && std::distance(I, E) > 0 && "Invalid iterator!");
331 MachineInstr *Dead = &*I;
333 Dead->eraseFromParent();
339 FastISel::SavePoint FastISel::enterLocalValueArea() {
340 MachineBasicBlock::iterator OldInsertPt = FuncInfo.InsertPt;
344 SavePoint SP = { OldInsertPt, OldDL };
348 void FastISel::leaveLocalValueArea(SavePoint OldInsertPt) {
349 if (FuncInfo.InsertPt != FuncInfo.MBB->begin())
350 LastLocalValue = llvm::prior(FuncInfo.InsertPt);
352 // Restore the previous insert position.
353 FuncInfo.InsertPt = OldInsertPt.InsertPt;
357 /// SelectBinaryOp - Select and emit code for a binary operator instruction,
358 /// which has an opcode which directly corresponds to the given ISD opcode.
360 bool FastISel::SelectBinaryOp(const User *I, unsigned ISDOpcode) {
361 EVT VT = EVT::getEVT(I->getType(), /*HandleUnknown=*/true);
362 if (VT == MVT::Other || !VT.isSimple())
363 // Unhandled type. Halt "fast" selection and bail.
366 // We only handle legal types. For example, on x86-32 the instruction
367 // selector contains all of the 64-bit instructions from x86-64,
368 // under the assumption that i64 won't be used if the target doesn't
370 if (!TLI.isTypeLegal(VT)) {
371 // MVT::i1 is special. Allow AND, OR, or XOR because they
372 // don't require additional zeroing, which makes them easy.
374 (ISDOpcode == ISD::AND || ISDOpcode == ISD::OR ||
375 ISDOpcode == ISD::XOR))
376 VT = TLI.getTypeToTransformTo(I->getContext(), VT);
381 // Check if the first operand is a constant, and handle it as "ri". At -O0,
382 // we don't have anything that canonicalizes operand order.
383 if (ConstantInt *CI = dyn_cast<ConstantInt>(I->getOperand(0)))
384 if (isa<Instruction>(I) && cast<Instruction>(I)->isCommutative()) {
385 unsigned Op1 = getRegForValue(I->getOperand(1));
386 if (Op1 == 0) return false;
388 bool Op1IsKill = hasTrivialKill(I->getOperand(1));
390 unsigned ResultReg = FastEmit_ri_(VT.getSimpleVT(), ISDOpcode, Op1,
391 Op1IsKill, CI->getZExtValue(),
393 if (ResultReg == 0) return false;
395 // We successfully emitted code for the given LLVM Instruction.
396 UpdateValueMap(I, ResultReg);
401 unsigned Op0 = getRegForValue(I->getOperand(0));
402 if (Op0 == 0) // Unhandled operand. Halt "fast" selection and bail.
405 bool Op0IsKill = hasTrivialKill(I->getOperand(0));
407 // Check if the second operand is a constant and handle it appropriately.
408 if (ConstantInt *CI = dyn_cast<ConstantInt>(I->getOperand(1))) {
409 uint64_t Imm = CI->getZExtValue();
411 // Transform "sdiv exact X, 8" -> "sra X, 3".
412 if (ISDOpcode == ISD::SDIV && isa<BinaryOperator>(I) &&
413 cast<BinaryOperator>(I)->isExact() &&
414 isPowerOf2_64(Imm)) {
416 ISDOpcode = ISD::SRA;
419 // Transform "urem x, pow2" -> "and x, pow2-1".
420 if (ISDOpcode == ISD::UREM && isa<BinaryOperator>(I) &&
421 isPowerOf2_64(Imm)) {
423 ISDOpcode = ISD::AND;
426 unsigned ResultReg = FastEmit_ri_(VT.getSimpleVT(), ISDOpcode, Op0,
427 Op0IsKill, Imm, VT.getSimpleVT());
428 if (ResultReg == 0) return false;
430 // We successfully emitted code for the given LLVM Instruction.
431 UpdateValueMap(I, ResultReg);
435 // Check if the second operand is a constant float.
436 if (ConstantFP *CF = dyn_cast<ConstantFP>(I->getOperand(1))) {
437 unsigned ResultReg = FastEmit_rf(VT.getSimpleVT(), VT.getSimpleVT(),
438 ISDOpcode, Op0, Op0IsKill, CF);
439 if (ResultReg != 0) {
440 // We successfully emitted code for the given LLVM Instruction.
441 UpdateValueMap(I, ResultReg);
446 unsigned Op1 = getRegForValue(I->getOperand(1));
448 // Unhandled operand. Halt "fast" selection and bail.
451 bool Op1IsKill = hasTrivialKill(I->getOperand(1));
453 // Now we have both operands in registers. Emit the instruction.
454 unsigned ResultReg = FastEmit_rr(VT.getSimpleVT(), VT.getSimpleVT(),
459 // Target-specific code wasn't able to find a machine opcode for
460 // the given ISD opcode and type. Halt "fast" selection and bail.
463 // We successfully emitted code for the given LLVM Instruction.
464 UpdateValueMap(I, ResultReg);
468 bool FastISel::SelectGetElementPtr(const User *I) {
469 unsigned N = getRegForValue(I->getOperand(0));
471 // Unhandled operand. Halt "fast" selection and bail.
474 bool NIsKill = hasTrivialKill(I->getOperand(0));
476 // Keep a running tab of the total offset to coalesce multiple N = N + Offset
477 // into a single N = N + TotalOffset.
478 uint64_t TotalOffs = 0;
479 // FIXME: What's a good SWAG number for MaxOffs?
480 uint64_t MaxOffs = 2048;
481 Type *Ty = I->getOperand(0)->getType();
482 MVT VT = TLI.getPointerTy();
483 for (GetElementPtrInst::const_op_iterator OI = I->op_begin()+1,
484 E = I->op_end(); OI != E; ++OI) {
485 const Value *Idx = *OI;
486 if (StructType *StTy = dyn_cast<StructType>(Ty)) {
487 unsigned Field = cast<ConstantInt>(Idx)->getZExtValue();
490 TotalOffs += TD.getStructLayout(StTy)->getElementOffset(Field);
491 if (TotalOffs >= MaxOffs) {
492 N = FastEmit_ri_(VT, ISD::ADD, N, NIsKill, TotalOffs, VT);
494 // Unhandled operand. Halt "fast" selection and bail.
500 Ty = StTy->getElementType(Field);
502 Ty = cast<SequentialType>(Ty)->getElementType();
504 // If this is a constant subscript, handle it quickly.
505 if (const ConstantInt *CI = dyn_cast<ConstantInt>(Idx)) {
506 if (CI->isZero()) continue;
509 TD.getTypeAllocSize(Ty)*cast<ConstantInt>(CI)->getSExtValue();
510 if (TotalOffs >= MaxOffs) {
511 N = FastEmit_ri_(VT, ISD::ADD, N, NIsKill, TotalOffs, VT);
513 // Unhandled operand. Halt "fast" selection and bail.
521 N = FastEmit_ri_(VT, ISD::ADD, N, NIsKill, TotalOffs, VT);
523 // Unhandled operand. Halt "fast" selection and bail.
529 // N = N + Idx * ElementSize;
530 uint64_t ElementSize = TD.getTypeAllocSize(Ty);
531 std::pair<unsigned, bool> Pair = getRegForGEPIndex(Idx);
532 unsigned IdxN = Pair.first;
533 bool IdxNIsKill = Pair.second;
535 // Unhandled operand. Halt "fast" selection and bail.
538 if (ElementSize != 1) {
539 IdxN = FastEmit_ri_(VT, ISD::MUL, IdxN, IdxNIsKill, ElementSize, VT);
541 // Unhandled operand. Halt "fast" selection and bail.
545 N = FastEmit_rr(VT, VT, ISD::ADD, N, NIsKill, IdxN, IdxNIsKill);
547 // Unhandled operand. Halt "fast" selection and bail.
552 N = FastEmit_ri_(VT, ISD::ADD, N, NIsKill, TotalOffs, VT);
554 // Unhandled operand. Halt "fast" selection and bail.
558 // We successfully emitted code for the given LLVM Instruction.
559 UpdateValueMap(I, N);
563 bool FastISel::SelectCall(const User *I) {
564 const CallInst *Call = cast<CallInst>(I);
566 // Handle simple inline asms.
567 if (const InlineAsm *IA = dyn_cast<InlineAsm>(Call->getCalledValue())) {
568 // Don't attempt to handle constraints.
569 if (!IA->getConstraintString().empty())
572 unsigned ExtraInfo = 0;
573 if (IA->hasSideEffects())
574 ExtraInfo |= InlineAsm::Extra_HasSideEffects;
575 if (IA->isAlignStack())
576 ExtraInfo |= InlineAsm::Extra_IsAlignStack;
578 BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL,
579 TII.get(TargetOpcode::INLINEASM))
580 .addExternalSymbol(IA->getAsmString().c_str())
585 MachineModuleInfo &MMI = FuncInfo.MF->getMMI();
586 ComputeUsesVAFloatArgument(*Call, &MMI);
588 const Function *F = Call->getCalledFunction();
589 if (!F) return false;
591 // Handle selected intrinsic function calls.
592 switch (F->getIntrinsicID()) {
594 // At -O0 we don't care about the lifetime intrinsics.
595 case Intrinsic::lifetime_start:
596 case Intrinsic::lifetime_end:
597 // The donothing intrinsic does, well, nothing.
598 case Intrinsic::donothing:
601 case Intrinsic::dbg_declare: {
602 const DbgDeclareInst *DI = cast<DbgDeclareInst>(Call);
603 DIVariable DIVar(DI->getVariable());
604 assert((!DIVar || DIVar.isVariable()) &&
605 "Variable in DbgDeclareInst should be either null or a DIVariable.");
607 !FuncInfo.MF->getMMI().hasDebugInfo()) {
608 DEBUG(dbgs() << "Dropping debug info for " << *DI << "\n");
612 const Value *Address = DI->getAddress();
613 if (!Address || isa<UndefValue>(Address)) {
614 DEBUG(dbgs() << "Dropping debug info for " << *DI << "\n");
618 Optional<MachineOperand> Op;
619 if (const Argument *Arg = dyn_cast<Argument>(Address))
620 // Some arguments' frame index is recorded during argument lowering.
621 if (int FI = FuncInfo.getArgumentFrameIndex(Arg))
622 Op = MachineOperand::CreateFI(FI);
624 if (unsigned Reg = lookUpRegForValue(Address))
625 Op = MachineOperand::CreateReg(Reg, false);
627 // If we have a VLA that has a "use" in a metadata node that's then used
628 // here but it has no other uses, then we have a problem. E.g.,
630 // int foo (const int *x) {
635 // If we assign 'a' a vreg and fast isel later on has to use the selection
636 // DAG isel, it will want to copy the value to the vreg. However, there are
637 // no uses, which goes counter to what selection DAG isel expects.
638 if (!Op && !Address->use_empty() && isa<Instruction>(Address) &&
639 (!isa<AllocaInst>(Address) ||
640 !FuncInfo.StaticAllocaMap.count(cast<AllocaInst>(Address))))
641 Op = MachineOperand::CreateReg(FuncInfo.InitializeRegForValue(Address),
644 if (Op && Op->isReg())
645 Op->setIsDebug(true);
648 BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL,
649 TII.get(TargetOpcode::DBG_VALUE)).addOperand(*Op).addImm(0)
650 .addMetadata(DI->getVariable());
652 // We can't yet handle anything else here because it would require
653 // generating code, thus altering codegen because of debug info.
654 DEBUG(dbgs() << "Dropping debug info for " << *DI << "\n");
657 case Intrinsic::dbg_value: {
658 // This form of DBG_VALUE is target-independent.
659 const DbgValueInst *DI = cast<DbgValueInst>(Call);
660 const MCInstrDesc &II = TII.get(TargetOpcode::DBG_VALUE);
661 const Value *V = DI->getValue();
663 // Currently the optimizer can produce this; insert an undef to
664 // help debugging. Probably the optimizer should not do this.
665 BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, II)
666 .addReg(0U).addImm(DI->getOffset())
667 .addMetadata(DI->getVariable());
668 } else if (const ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
669 if (CI->getBitWidth() > 64)
670 BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, II)
671 .addCImm(CI).addImm(DI->getOffset())
672 .addMetadata(DI->getVariable());
674 BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, II)
675 .addImm(CI->getZExtValue()).addImm(DI->getOffset())
676 .addMetadata(DI->getVariable());
677 } else if (const ConstantFP *CF = dyn_cast<ConstantFP>(V)) {
678 BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, II)
679 .addFPImm(CF).addImm(DI->getOffset())
680 .addMetadata(DI->getVariable());
681 } else if (unsigned Reg = lookUpRegForValue(V)) {
682 BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, II)
683 .addReg(Reg, RegState::Debug).addImm(DI->getOffset())
684 .addMetadata(DI->getVariable());
686 // We can't yet handle anything else here because it would require
687 // generating code, thus altering codegen because of debug info.
688 DEBUG(dbgs() << "Dropping debug info for " << *DI << "\n");
692 case Intrinsic::objectsize: {
693 ConstantInt *CI = cast<ConstantInt>(Call->getArgOperand(1));
694 unsigned long long Res = CI->isZero() ? -1ULL : 0;
695 Constant *ResCI = ConstantInt::get(Call->getType(), Res);
696 unsigned ResultReg = getRegForValue(ResCI);
699 UpdateValueMap(Call, ResultReg);
702 case Intrinsic::expect: {
703 unsigned ResultReg = getRegForValue(Call->getArgOperand(0));
706 UpdateValueMap(Call, ResultReg);
711 // Usually, it does not make sense to initialize a value,
712 // make an unrelated function call and use the value, because
713 // it tends to be spilled on the stack. So, we move the pointer
714 // to the last local value to the beginning of the block, so that
715 // all the values which have already been materialized,
716 // appear after the call. It also makes sense to skip intrinsics
717 // since they tend to be inlined.
718 if (!isa<IntrinsicInst>(Call))
719 flushLocalValueMap();
721 // An arbitrary call. Bail.
725 bool FastISel::SelectCast(const User *I, unsigned Opcode) {
726 EVT SrcVT = TLI.getValueType(I->getOperand(0)->getType());
727 EVT DstVT = TLI.getValueType(I->getType());
729 if (SrcVT == MVT::Other || !SrcVT.isSimple() ||
730 DstVT == MVT::Other || !DstVT.isSimple())
731 // Unhandled type. Halt "fast" selection and bail.
734 // Check if the destination type is legal.
735 if (!TLI.isTypeLegal(DstVT))
738 // Check if the source operand is legal.
739 if (!TLI.isTypeLegal(SrcVT))
742 unsigned InputReg = getRegForValue(I->getOperand(0));
744 // Unhandled operand. Halt "fast" selection and bail.
747 bool InputRegIsKill = hasTrivialKill(I->getOperand(0));
749 unsigned ResultReg = FastEmit_r(SrcVT.getSimpleVT(),
752 InputReg, InputRegIsKill);
756 UpdateValueMap(I, ResultReg);
760 bool FastISel::SelectBitCast(const User *I) {
761 // If the bitcast doesn't change the type, just use the operand value.
762 if (I->getType() == I->getOperand(0)->getType()) {
763 unsigned Reg = getRegForValue(I->getOperand(0));
766 UpdateValueMap(I, Reg);
770 // Bitcasts of other values become reg-reg copies or BITCAST operators.
771 EVT SrcEVT = TLI.getValueType(I->getOperand(0)->getType());
772 EVT DstEVT = TLI.getValueType(I->getType());
773 if (SrcEVT == MVT::Other || DstEVT == MVT::Other ||
774 !TLI.isTypeLegal(SrcEVT) || !TLI.isTypeLegal(DstEVT))
775 // Unhandled type. Halt "fast" selection and bail.
778 MVT SrcVT = SrcEVT.getSimpleVT();
779 MVT DstVT = DstEVT.getSimpleVT();
780 unsigned Op0 = getRegForValue(I->getOperand(0));
782 // Unhandled operand. Halt "fast" selection and bail.
785 bool Op0IsKill = hasTrivialKill(I->getOperand(0));
787 // First, try to perform the bitcast by inserting a reg-reg copy.
788 unsigned ResultReg = 0;
789 if (SrcVT == DstVT) {
790 const TargetRegisterClass* SrcClass = TLI.getRegClassFor(SrcVT);
791 const TargetRegisterClass* DstClass = TLI.getRegClassFor(DstVT);
792 // Don't attempt a cross-class copy. It will likely fail.
793 if (SrcClass == DstClass) {
794 ResultReg = createResultReg(DstClass);
795 BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, TII.get(TargetOpcode::COPY),
796 ResultReg).addReg(Op0);
800 // If the reg-reg copy failed, select a BITCAST opcode.
802 ResultReg = FastEmit_r(SrcVT, DstVT, ISD::BITCAST, Op0, Op0IsKill);
807 UpdateValueMap(I, ResultReg);
812 FastISel::SelectInstruction(const Instruction *I) {
813 // Just before the terminator instruction, insert instructions to
814 // feed PHI nodes in successor blocks.
815 if (isa<TerminatorInst>(I))
816 if (!HandlePHINodesInSuccessorBlocks(I->getParent()))
819 DL = I->getDebugLoc();
821 MachineBasicBlock::iterator SavedInsertPt = FuncInfo.InsertPt;
823 // As a special case, don't handle calls to builtin library functions that
824 // may be translated directly to target instructions.
825 if (const CallInst *Call = dyn_cast<CallInst>(I)) {
826 const Function *F = Call->getCalledFunction();
828 if (F && !F->hasLocalLinkage() && F->hasName() &&
829 LibInfo->getLibFunc(F->getName(), Func) &&
830 LibInfo->hasOptimizedCodeGen(Func))
834 // First, try doing target-independent selection.
835 if (SelectOperator(I, I->getOpcode())) {
836 ++NumFastIselSuccessIndependent;
840 // Remove dead code. However, ignore call instructions since we've flushed
841 // the local value map and recomputed the insert point.
842 if (!isa<CallInst>(I)) {
844 if (SavedInsertPt != FuncInfo.InsertPt)
845 removeDeadCode(FuncInfo.InsertPt, SavedInsertPt);
848 // Next, try calling the target to attempt to handle the instruction.
849 SavedInsertPt = FuncInfo.InsertPt;
850 if (TargetSelectInstruction(I)) {
851 ++NumFastIselSuccessTarget;
855 // Check for dead code and remove as necessary.
857 if (SavedInsertPt != FuncInfo.InsertPt)
858 removeDeadCode(FuncInfo.InsertPt, SavedInsertPt);
864 /// FastEmitBranch - Emit an unconditional branch to the given block,
865 /// unless it is the immediate (fall-through) successor, and update
868 FastISel::FastEmitBranch(MachineBasicBlock *MSucc, DebugLoc DL) {
870 if (FuncInfo.MBB->getBasicBlock()->size() > 1 &&
871 FuncInfo.MBB->isLayoutSuccessor(MSucc)) {
872 // For more accurate line information if this is the only instruction
873 // in the block then emit it, otherwise we have the unconditional
874 // fall-through case, which needs no instructions.
876 // The unconditional branch case.
877 TII.InsertBranch(*FuncInfo.MBB, MSucc, NULL,
878 SmallVector<MachineOperand, 0>(), DL);
880 FuncInfo.MBB->addSuccessor(MSucc);
883 /// SelectFNeg - Emit an FNeg operation.
886 FastISel::SelectFNeg(const User *I) {
887 unsigned OpReg = getRegForValue(BinaryOperator::getFNegArgument(I));
888 if (OpReg == 0) return false;
890 bool OpRegIsKill = hasTrivialKill(I);
892 // If the target has ISD::FNEG, use it.
893 EVT VT = TLI.getValueType(I->getType());
894 unsigned ResultReg = FastEmit_r(VT.getSimpleVT(), VT.getSimpleVT(),
895 ISD::FNEG, OpReg, OpRegIsKill);
896 if (ResultReg != 0) {
897 UpdateValueMap(I, ResultReg);
901 // Bitcast the value to integer, twiddle the sign bit with xor,
902 // and then bitcast it back to floating-point.
903 if (VT.getSizeInBits() > 64) return false;
904 EVT IntVT = EVT::getIntegerVT(I->getContext(), VT.getSizeInBits());
905 if (!TLI.isTypeLegal(IntVT))
908 unsigned IntReg = FastEmit_r(VT.getSimpleVT(), IntVT.getSimpleVT(),
909 ISD::BITCAST, OpReg, OpRegIsKill);
913 unsigned IntResultReg = FastEmit_ri_(IntVT.getSimpleVT(), ISD::XOR,
914 IntReg, /*Kill=*/true,
915 UINT64_C(1) << (VT.getSizeInBits()-1),
916 IntVT.getSimpleVT());
917 if (IntResultReg == 0)
920 ResultReg = FastEmit_r(IntVT.getSimpleVT(), VT.getSimpleVT(),
921 ISD::BITCAST, IntResultReg, /*Kill=*/true);
925 UpdateValueMap(I, ResultReg);
930 FastISel::SelectExtractValue(const User *U) {
931 const ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(U);
935 // Make sure we only try to handle extracts with a legal result. But also
936 // allow i1 because it's easy.
937 EVT RealVT = TLI.getValueType(EVI->getType(), /*AllowUnknown=*/true);
938 if (!RealVT.isSimple())
940 MVT VT = RealVT.getSimpleVT();
941 if (!TLI.isTypeLegal(VT) && VT != MVT::i1)
944 const Value *Op0 = EVI->getOperand(0);
945 Type *AggTy = Op0->getType();
947 // Get the base result register.
949 DenseMap<const Value *, unsigned>::iterator I = FuncInfo.ValueMap.find(Op0);
950 if (I != FuncInfo.ValueMap.end())
951 ResultReg = I->second;
952 else if (isa<Instruction>(Op0))
953 ResultReg = FuncInfo.InitializeRegForValue(Op0);
955 return false; // fast-isel can't handle aggregate constants at the moment
957 // Get the actual result register, which is an offset from the base register.
958 unsigned VTIndex = ComputeLinearIndex(AggTy, EVI->getIndices());
960 SmallVector<EVT, 4> AggValueVTs;
961 ComputeValueVTs(TLI, AggTy, AggValueVTs);
963 for (unsigned i = 0; i < VTIndex; i++)
964 ResultReg += TLI.getNumRegisters(FuncInfo.Fn->getContext(), AggValueVTs[i]);
966 UpdateValueMap(EVI, ResultReg);
971 FastISel::SelectOperator(const User *I, unsigned Opcode) {
973 case Instruction::Add:
974 return SelectBinaryOp(I, ISD::ADD);
975 case Instruction::FAdd:
976 return SelectBinaryOp(I, ISD::FADD);
977 case Instruction::Sub:
978 return SelectBinaryOp(I, ISD::SUB);
979 case Instruction::FSub:
980 // FNeg is currently represented in LLVM IR as a special case of FSub.
981 if (BinaryOperator::isFNeg(I))
982 return SelectFNeg(I);
983 return SelectBinaryOp(I, ISD::FSUB);
984 case Instruction::Mul:
985 return SelectBinaryOp(I, ISD::MUL);
986 case Instruction::FMul:
987 return SelectBinaryOp(I, ISD::FMUL);
988 case Instruction::SDiv:
989 return SelectBinaryOp(I, ISD::SDIV);
990 case Instruction::UDiv:
991 return SelectBinaryOp(I, ISD::UDIV);
992 case Instruction::FDiv:
993 return SelectBinaryOp(I, ISD::FDIV);
994 case Instruction::SRem:
995 return SelectBinaryOp(I, ISD::SREM);
996 case Instruction::URem:
997 return SelectBinaryOp(I, ISD::UREM);
998 case Instruction::FRem:
999 return SelectBinaryOp(I, ISD::FREM);
1000 case Instruction::Shl:
1001 return SelectBinaryOp(I, ISD::SHL);
1002 case Instruction::LShr:
1003 return SelectBinaryOp(I, ISD::SRL);
1004 case Instruction::AShr:
1005 return SelectBinaryOp(I, ISD::SRA);
1006 case Instruction::And:
1007 return SelectBinaryOp(I, ISD::AND);
1008 case Instruction::Or:
1009 return SelectBinaryOp(I, ISD::OR);
1010 case Instruction::Xor:
1011 return SelectBinaryOp(I, ISD::XOR);
1013 case Instruction::GetElementPtr:
1014 return SelectGetElementPtr(I);
1016 case Instruction::Br: {
1017 const BranchInst *BI = cast<BranchInst>(I);
1019 if (BI->isUnconditional()) {
1020 const BasicBlock *LLVMSucc = BI->getSuccessor(0);
1021 MachineBasicBlock *MSucc = FuncInfo.MBBMap[LLVMSucc];
1022 FastEmitBranch(MSucc, BI->getDebugLoc());
1026 // Conditional branches are not handed yet.
1027 // Halt "fast" selection and bail.
1031 case Instruction::Unreachable:
1035 case Instruction::Alloca:
1036 // FunctionLowering has the static-sized case covered.
1037 if (FuncInfo.StaticAllocaMap.count(cast<AllocaInst>(I)))
1040 // Dynamic-sized alloca is not handled yet.
1043 case Instruction::Call:
1044 return SelectCall(I);
1046 case Instruction::BitCast:
1047 return SelectBitCast(I);
1049 case Instruction::FPToSI:
1050 return SelectCast(I, ISD::FP_TO_SINT);
1051 case Instruction::ZExt:
1052 return SelectCast(I, ISD::ZERO_EXTEND);
1053 case Instruction::SExt:
1054 return SelectCast(I, ISD::SIGN_EXTEND);
1055 case Instruction::Trunc:
1056 return SelectCast(I, ISD::TRUNCATE);
1057 case Instruction::SIToFP:
1058 return SelectCast(I, ISD::SINT_TO_FP);
1060 case Instruction::IntToPtr: // Deliberate fall-through.
1061 case Instruction::PtrToInt: {
1062 EVT SrcVT = TLI.getValueType(I->getOperand(0)->getType());
1063 EVT DstVT = TLI.getValueType(I->getType());
1064 if (DstVT.bitsGT(SrcVT))
1065 return SelectCast(I, ISD::ZERO_EXTEND);
1066 if (DstVT.bitsLT(SrcVT))
1067 return SelectCast(I, ISD::TRUNCATE);
1068 unsigned Reg = getRegForValue(I->getOperand(0));
1069 if (Reg == 0) return false;
1070 UpdateValueMap(I, Reg);
1074 case Instruction::ExtractValue:
1075 return SelectExtractValue(I);
1077 case Instruction::PHI:
1078 llvm_unreachable("FastISel shouldn't visit PHI nodes!");
1081 // Unhandled instruction. Halt "fast" selection and bail.
1086 FastISel::FastISel(FunctionLoweringInfo &funcInfo,
1087 const TargetLibraryInfo *libInfo)
1088 : FuncInfo(funcInfo),
1089 MRI(FuncInfo.MF->getRegInfo()),
1090 MFI(*FuncInfo.MF->getFrameInfo()),
1091 MCP(*FuncInfo.MF->getConstantPool()),
1092 TM(FuncInfo.MF->getTarget()),
1093 TD(*TM.getDataLayout()),
1094 TII(*TM.getInstrInfo()),
1095 TLI(*TM.getTargetLowering()),
1096 TRI(*TM.getRegisterInfo()),
1100 FastISel::~FastISel() {}
1102 bool FastISel::FastLowerArguments() {
1106 unsigned FastISel::FastEmit_(MVT, MVT,
1111 unsigned FastISel::FastEmit_r(MVT, MVT,
1113 unsigned /*Op0*/, bool /*Op0IsKill*/) {
1117 unsigned FastISel::FastEmit_rr(MVT, MVT,
1119 unsigned /*Op0*/, bool /*Op0IsKill*/,
1120 unsigned /*Op1*/, bool /*Op1IsKill*/) {
1124 unsigned FastISel::FastEmit_i(MVT, MVT, unsigned, uint64_t /*Imm*/) {
1128 unsigned FastISel::FastEmit_f(MVT, MVT,
1129 unsigned, const ConstantFP * /*FPImm*/) {
1133 unsigned FastISel::FastEmit_ri(MVT, MVT,
1135 unsigned /*Op0*/, bool /*Op0IsKill*/,
1140 unsigned FastISel::FastEmit_rf(MVT, MVT,
1142 unsigned /*Op0*/, bool /*Op0IsKill*/,
1143 const ConstantFP * /*FPImm*/) {
1147 unsigned FastISel::FastEmit_rri(MVT, MVT,
1149 unsigned /*Op0*/, bool /*Op0IsKill*/,
1150 unsigned /*Op1*/, bool /*Op1IsKill*/,
1155 /// FastEmit_ri_ - This method is a wrapper of FastEmit_ri. It first tries
1156 /// to emit an instruction with an immediate operand using FastEmit_ri.
1157 /// If that fails, it materializes the immediate into a register and try
1158 /// FastEmit_rr instead.
1159 unsigned FastISel::FastEmit_ri_(MVT VT, unsigned Opcode,
1160 unsigned Op0, bool Op0IsKill,
1161 uint64_t Imm, MVT ImmType) {
1162 // If this is a multiply by a power of two, emit this as a shift left.
1163 if (Opcode == ISD::MUL && isPowerOf2_64(Imm)) {
1166 } else if (Opcode == ISD::UDIV && isPowerOf2_64(Imm)) {
1167 // div x, 8 -> srl x, 3
1172 // Horrible hack (to be removed), check to make sure shift amounts are
1174 if ((Opcode == ISD::SHL || Opcode == ISD::SRA || Opcode == ISD::SRL) &&
1175 Imm >= VT.getSizeInBits())
1178 // First check if immediate type is legal. If not, we can't use the ri form.
1179 unsigned ResultReg = FastEmit_ri(VT, VT, Opcode, Op0, Op0IsKill, Imm);
1182 unsigned MaterialReg = FastEmit_i(ImmType, ImmType, ISD::Constant, Imm);
1183 if (MaterialReg == 0) {
1184 // This is a bit ugly/slow, but failing here means falling out of
1185 // fast-isel, which would be very slow.
1186 IntegerType *ITy = IntegerType::get(FuncInfo.Fn->getContext(),
1187 VT.getSizeInBits());
1188 MaterialReg = getRegForValue(ConstantInt::get(ITy, Imm));
1189 assert (MaterialReg != 0 && "Unable to materialize imm.");
1190 if (MaterialReg == 0) return 0;
1192 return FastEmit_rr(VT, VT, Opcode,
1194 MaterialReg, /*Kill=*/true);
1197 unsigned FastISel::createResultReg(const TargetRegisterClass* RC) {
1198 return MRI.createVirtualRegister(RC);
1201 unsigned FastISel::FastEmitInst_(unsigned MachineInstOpcode,
1202 const TargetRegisterClass* RC) {
1203 unsigned ResultReg = createResultReg(RC);
1204 const MCInstrDesc &II = TII.get(MachineInstOpcode);
1206 BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, II, ResultReg);
1210 unsigned FastISel::FastEmitInst_r(unsigned MachineInstOpcode,
1211 const TargetRegisterClass *RC,
1212 unsigned Op0, bool Op0IsKill) {
1213 unsigned ResultReg = createResultReg(RC);
1214 const MCInstrDesc &II = TII.get(MachineInstOpcode);
1216 if (II.getNumDefs() >= 1)
1217 BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, II, ResultReg)
1218 .addReg(Op0, Op0IsKill * RegState::Kill);
1220 BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, II)
1221 .addReg(Op0, Op0IsKill * RegState::Kill);
1222 BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, TII.get(TargetOpcode::COPY),
1223 ResultReg).addReg(II.ImplicitDefs[0]);
1229 unsigned FastISel::FastEmitInst_rr(unsigned MachineInstOpcode,
1230 const TargetRegisterClass *RC,
1231 unsigned Op0, bool Op0IsKill,
1232 unsigned Op1, bool Op1IsKill) {
1233 unsigned ResultReg = createResultReg(RC);
1234 const MCInstrDesc &II = TII.get(MachineInstOpcode);
1236 if (II.getNumDefs() >= 1)
1237 BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, II, ResultReg)
1238 .addReg(Op0, Op0IsKill * RegState::Kill)
1239 .addReg(Op1, Op1IsKill * RegState::Kill);
1241 BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, II)
1242 .addReg(Op0, Op0IsKill * RegState::Kill)
1243 .addReg(Op1, Op1IsKill * RegState::Kill);
1244 BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, TII.get(TargetOpcode::COPY),
1245 ResultReg).addReg(II.ImplicitDefs[0]);
1250 unsigned FastISel::FastEmitInst_rrr(unsigned MachineInstOpcode,
1251 const TargetRegisterClass *RC,
1252 unsigned Op0, bool Op0IsKill,
1253 unsigned Op1, bool Op1IsKill,
1254 unsigned Op2, bool Op2IsKill) {
1255 unsigned ResultReg = createResultReg(RC);
1256 const MCInstrDesc &II = TII.get(MachineInstOpcode);
1258 if (II.getNumDefs() >= 1)
1259 BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, II, ResultReg)
1260 .addReg(Op0, Op0IsKill * RegState::Kill)
1261 .addReg(Op1, Op1IsKill * RegState::Kill)
1262 .addReg(Op2, Op2IsKill * RegState::Kill);
1264 BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, II)
1265 .addReg(Op0, Op0IsKill * RegState::Kill)
1266 .addReg(Op1, Op1IsKill * RegState::Kill)
1267 .addReg(Op2, Op2IsKill * RegState::Kill);
1268 BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, TII.get(TargetOpcode::COPY),
1269 ResultReg).addReg(II.ImplicitDefs[0]);
1274 unsigned FastISel::FastEmitInst_ri(unsigned MachineInstOpcode,
1275 const TargetRegisterClass *RC,
1276 unsigned Op0, bool Op0IsKill,
1278 unsigned ResultReg = createResultReg(RC);
1279 const MCInstrDesc &II = TII.get(MachineInstOpcode);
1281 if (II.getNumDefs() >= 1)
1282 BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, II, ResultReg)
1283 .addReg(Op0, Op0IsKill * RegState::Kill)
1286 BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, II)
1287 .addReg(Op0, Op0IsKill * RegState::Kill)
1289 BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, TII.get(TargetOpcode::COPY),
1290 ResultReg).addReg(II.ImplicitDefs[0]);
1295 unsigned FastISel::FastEmitInst_rii(unsigned MachineInstOpcode,
1296 const TargetRegisterClass *RC,
1297 unsigned Op0, bool Op0IsKill,
1298 uint64_t Imm1, uint64_t Imm2) {
1299 unsigned ResultReg = createResultReg(RC);
1300 const MCInstrDesc &II = TII.get(MachineInstOpcode);
1302 if (II.getNumDefs() >= 1)
1303 BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, II, ResultReg)
1304 .addReg(Op0, Op0IsKill * RegState::Kill)
1308 BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, II)
1309 .addReg(Op0, Op0IsKill * RegState::Kill)
1312 BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, TII.get(TargetOpcode::COPY),
1313 ResultReg).addReg(II.ImplicitDefs[0]);
1318 unsigned FastISel::FastEmitInst_rf(unsigned MachineInstOpcode,
1319 const TargetRegisterClass *RC,
1320 unsigned Op0, bool Op0IsKill,
1321 const ConstantFP *FPImm) {
1322 unsigned ResultReg = createResultReg(RC);
1323 const MCInstrDesc &II = TII.get(MachineInstOpcode);
1325 if (II.getNumDefs() >= 1)
1326 BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, II, ResultReg)
1327 .addReg(Op0, Op0IsKill * RegState::Kill)
1330 BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, II)
1331 .addReg(Op0, Op0IsKill * RegState::Kill)
1333 BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, TII.get(TargetOpcode::COPY),
1334 ResultReg).addReg(II.ImplicitDefs[0]);
1339 unsigned FastISel::FastEmitInst_rri(unsigned MachineInstOpcode,
1340 const TargetRegisterClass *RC,
1341 unsigned Op0, bool Op0IsKill,
1342 unsigned Op1, bool Op1IsKill,
1344 unsigned ResultReg = createResultReg(RC);
1345 const MCInstrDesc &II = TII.get(MachineInstOpcode);
1347 if (II.getNumDefs() >= 1)
1348 BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, II, ResultReg)
1349 .addReg(Op0, Op0IsKill * RegState::Kill)
1350 .addReg(Op1, Op1IsKill * RegState::Kill)
1353 BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, II)
1354 .addReg(Op0, Op0IsKill * RegState::Kill)
1355 .addReg(Op1, Op1IsKill * RegState::Kill)
1357 BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, TII.get(TargetOpcode::COPY),
1358 ResultReg).addReg(II.ImplicitDefs[0]);
1363 unsigned FastISel::FastEmitInst_rrii(unsigned MachineInstOpcode,
1364 const TargetRegisterClass *RC,
1365 unsigned Op0, bool Op0IsKill,
1366 unsigned Op1, bool Op1IsKill,
1367 uint64_t Imm1, uint64_t Imm2) {
1368 unsigned ResultReg = createResultReg(RC);
1369 const MCInstrDesc &II = TII.get(MachineInstOpcode);
1371 if (II.getNumDefs() >= 1)
1372 BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, II, ResultReg)
1373 .addReg(Op0, Op0IsKill * RegState::Kill)
1374 .addReg(Op1, Op1IsKill * RegState::Kill)
1375 .addImm(Imm1).addImm(Imm2);
1377 BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, II)
1378 .addReg(Op0, Op0IsKill * RegState::Kill)
1379 .addReg(Op1, Op1IsKill * RegState::Kill)
1380 .addImm(Imm1).addImm(Imm2);
1381 BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, TII.get(TargetOpcode::COPY),
1382 ResultReg).addReg(II.ImplicitDefs[0]);
1387 unsigned FastISel::FastEmitInst_i(unsigned MachineInstOpcode,
1388 const TargetRegisterClass *RC,
1390 unsigned ResultReg = createResultReg(RC);
1391 const MCInstrDesc &II = TII.get(MachineInstOpcode);
1393 if (II.getNumDefs() >= 1)
1394 BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, II, ResultReg).addImm(Imm);
1396 BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, II).addImm(Imm);
1397 BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, TII.get(TargetOpcode::COPY),
1398 ResultReg).addReg(II.ImplicitDefs[0]);
1403 unsigned FastISel::FastEmitInst_ii(unsigned MachineInstOpcode,
1404 const TargetRegisterClass *RC,
1405 uint64_t Imm1, uint64_t Imm2) {
1406 unsigned ResultReg = createResultReg(RC);
1407 const MCInstrDesc &II = TII.get(MachineInstOpcode);
1409 if (II.getNumDefs() >= 1)
1410 BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, II, ResultReg)
1411 .addImm(Imm1).addImm(Imm2);
1413 BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, II).addImm(Imm1).addImm(Imm2);
1414 BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, TII.get(TargetOpcode::COPY),
1415 ResultReg).addReg(II.ImplicitDefs[0]);
1420 unsigned FastISel::FastEmitInst_extractsubreg(MVT RetVT,
1421 unsigned Op0, bool Op0IsKill,
1423 unsigned ResultReg = createResultReg(TLI.getRegClassFor(RetVT));
1424 assert(TargetRegisterInfo::isVirtualRegister(Op0) &&
1425 "Cannot yet extract from physregs");
1426 const TargetRegisterClass *RC = MRI.getRegClass(Op0);
1427 MRI.constrainRegClass(Op0, TRI.getSubClassWithSubReg(RC, Idx));
1428 BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt,
1429 DL, TII.get(TargetOpcode::COPY), ResultReg)
1430 .addReg(Op0, getKillRegState(Op0IsKill), Idx);
1434 /// FastEmitZExtFromI1 - Emit MachineInstrs to compute the value of Op
1435 /// with all but the least significant bit set to zero.
1436 unsigned FastISel::FastEmitZExtFromI1(MVT VT, unsigned Op0, bool Op0IsKill) {
1437 return FastEmit_ri(VT, VT, ISD::AND, Op0, Op0IsKill, 1);
1440 /// HandlePHINodesInSuccessorBlocks - Handle PHI nodes in successor blocks.
1441 /// Emit code to ensure constants are copied into registers when needed.
1442 /// Remember the virtual registers that need to be added to the Machine PHI
1443 /// nodes as input. We cannot just directly add them, because expansion
1444 /// might result in multiple MBB's for one BB. As such, the start of the
1445 /// BB might correspond to a different MBB than the end.
1446 bool FastISel::HandlePHINodesInSuccessorBlocks(const BasicBlock *LLVMBB) {
1447 const TerminatorInst *TI = LLVMBB->getTerminator();
1449 SmallPtrSet<MachineBasicBlock *, 4> SuccsHandled;
1450 unsigned OrigNumPHINodesToUpdate = FuncInfo.PHINodesToUpdate.size();
1452 // Check successor nodes' PHI nodes that expect a constant to be available
1454 for (unsigned succ = 0, e = TI->getNumSuccessors(); succ != e; ++succ) {
1455 const BasicBlock *SuccBB = TI->getSuccessor(succ);
1456 if (!isa<PHINode>(SuccBB->begin())) continue;
1457 MachineBasicBlock *SuccMBB = FuncInfo.MBBMap[SuccBB];
1459 // If this terminator has multiple identical successors (common for
1460 // switches), only handle each succ once.
1461 if (!SuccsHandled.insert(SuccMBB)) continue;
1463 MachineBasicBlock::iterator MBBI = SuccMBB->begin();
1465 // At this point we know that there is a 1-1 correspondence between LLVM PHI
1466 // nodes and Machine PHI nodes, but the incoming operands have not been
1468 for (BasicBlock::const_iterator I = SuccBB->begin();
1469 const PHINode *PN = dyn_cast<PHINode>(I); ++I) {
1471 // Ignore dead phi's.
1472 if (PN->use_empty()) continue;
1474 // Only handle legal types. Two interesting things to note here. First,
1475 // by bailing out early, we may leave behind some dead instructions,
1476 // since SelectionDAG's HandlePHINodesInSuccessorBlocks will insert its
1477 // own moves. Second, this check is necessary because FastISel doesn't
1478 // use CreateRegs to create registers, so it always creates
1479 // exactly one register for each non-void instruction.
1480 EVT VT = TLI.getValueType(PN->getType(), /*AllowUnknown=*/true);
1481 if (VT == MVT::Other || !TLI.isTypeLegal(VT)) {
1482 // Handle integer promotions, though, because they're common and easy.
1483 if (VT == MVT::i1 || VT == MVT::i8 || VT == MVT::i16)
1484 VT = TLI.getTypeToTransformTo(LLVMBB->getContext(), VT);
1486 FuncInfo.PHINodesToUpdate.resize(OrigNumPHINodesToUpdate);
1491 const Value *PHIOp = PN->getIncomingValueForBlock(LLVMBB);
1493 // Set the DebugLoc for the copy. Prefer the location of the operand
1494 // if there is one; use the location of the PHI otherwise.
1495 DL = PN->getDebugLoc();
1496 if (const Instruction *Inst = dyn_cast<Instruction>(PHIOp))
1497 DL = Inst->getDebugLoc();
1499 unsigned Reg = getRegForValue(PHIOp);
1501 FuncInfo.PHINodesToUpdate.resize(OrigNumPHINodesToUpdate);
1504 FuncInfo.PHINodesToUpdate.push_back(std::make_pair(MBBI++, Reg));
1512 bool FastISel::tryToFoldLoad(const LoadInst *LI, const Instruction *FoldInst) {
1513 assert(LI->hasOneUse() &&
1514 "tryToFoldLoad expected a LoadInst with a single use");
1515 // We know that the load has a single use, but don't know what it is. If it
1516 // isn't one of the folded instructions, then we can't succeed here. Handle
1517 // this by scanning the single-use users of the load until we get to FoldInst.
1518 unsigned MaxUsers = 6; // Don't scan down huge single-use chains of instrs.
1520 const Instruction *TheUser = LI->use_back();
1521 while (TheUser != FoldInst && // Scan up until we find FoldInst.
1522 // Stay in the right block.
1523 TheUser->getParent() == FoldInst->getParent() &&
1524 --MaxUsers) { // Don't scan too far.
1525 // If there are multiple or no uses of this instruction, then bail out.
1526 if (!TheUser->hasOneUse())
1529 TheUser = TheUser->use_back();
1532 // If we didn't find the fold instruction, then we failed to collapse the
1534 if (TheUser != FoldInst)
1537 // Don't try to fold volatile loads. Target has to deal with alignment
1539 if (LI->isVolatile())
1542 // Figure out which vreg this is going into. If there is no assigned vreg yet
1543 // then there actually was no reference to it. Perhaps the load is referenced
1544 // by a dead instruction.
1545 unsigned LoadReg = getRegForValue(LI);
1549 // We can't fold if this vreg has no uses or more than one use. Multiple uses
1550 // may mean that the instruction got lowered to multiple MIs, or the use of
1551 // the loaded value ended up being multiple operands of the result.
1552 if (!MRI.hasOneUse(LoadReg))
1555 MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(LoadReg);
1556 MachineInstr *User = &*RI;
1558 // Set the insertion point properly. Folding the load can cause generation of
1559 // other random instructions (like sign extends) for addressing modes; make
1560 // sure they get inserted in a logical place before the new instruction.
1561 FuncInfo.InsertPt = User;
1562 FuncInfo.MBB = User->getParent();
1564 // Ask the target to try folding the load.
1565 return tryToFoldLoadIntoMI(User, RI.getOperandNo(), LI);