FastISel.cpp revision ece06e65c9d40925651216845e0d731d5365d2e3
1//===-- FastISel.cpp - Implementation of the FastISel class ---------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file contains the implementation of the FastISel class. 11// 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. 19// 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. 24// 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 32// in -O0 compiles. 33// 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. 39// 40//===----------------------------------------------------------------------===// 41 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" 58using namespace llvm; 59 60bool 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); 63 if (!I) 64 return false; 65 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))) 70 return false; 71 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(); 79} 80 81unsigned 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()) 85 return 0; 86 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. 93 if (VT == MVT::i1) 94 VT = TLI.getTypeToTransformTo(V->getContext(), VT).getSimpleVT(); 95 else 96 return 0; 97 } 98 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()) 105 return I->second; 106 unsigned Reg = LocalValueMap[V]; 107 if (Reg != 0) 108 return Reg; 109 110 // In bottom-up mode, just create the virtual register which will be used 111 // to hold the value. It will be materialized later. 112 if (IsBottomUp) { 113 Reg = createResultReg(TLI.getRegClassFor(VT)); 114 if (isa<Instruction>(V)) 115 ValueMap[V] = Reg; 116 else 117 LocalValueMap[V] = Reg; 118 return Reg; 119 } 120 121 return materializeRegForValue(V, VT); 122} 123 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. 127unsigned FastISel::materializeRegForValue(const Value *V, MVT VT) { 128 unsigned Reg = 0; 129 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. 138 Reg = 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); 143 144 if (!Reg) { 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(); 148 149 uint64_t x[2]; 150 uint32_t IntBitWidth = IntVT.getSizeInBits(); 151 bool isExact; 152 (void) Flt.convertToInteger(x, IntBitWidth, /*isSigned=*/true, 153 APFloat::rmTowardZero, &isExact); 154 if (isExact) { 155 APInt IntVal(IntBitWidth, 2, x); 156 157 unsigned IntegerReg = 158 getRegForValue(ConstantInt::get(V->getContext(), IntVal)); 159 if (IntegerReg != 0) 160 Reg = FastEmit_r(IntVT.getSimpleVT(), VT, ISD::SINT_TO_FP, 161 IntegerReg, /*Kill=*/false); 162 } 163 } 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))) 168 return 0; 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); 173 } 174 175 // If target-independent code couldn't handle the value, give target-specific 176 // code a try. 177 if (!Reg && isa<Constant>(V)) 178 Reg = TargetMaterializeConstant(cast<Constant>(V)); 179 180 // Don't cache constant materializations in the general ValueMap. 181 // To do so would require tracking what uses they dominate. 182 if (Reg != 0) 183 LocalValueMap[V] = Reg; 184 return Reg; 185} 186 187unsigned 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()) 194 return I->second; 195 return LocalValueMap[V]; 196} 197 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. 204unsigned FastISel::UpdateValueMap(const Value *I, unsigned Reg) { 205 if (!isa<Instruction>(I)) { 206 LocalValueMap[I] = Reg; 207 return Reg; 208 } 209 210 unsigned &AssignedReg = ValueMap[I]; 211 if (AssignedReg == 0) 212 AssignedReg = Reg; 213 else if (Reg != AssignedReg) { 214 const TargetRegisterClass *RegClass = MRI.getRegClass(Reg); 215 TII.copyRegToReg(*MBB, MBB->end(), AssignedReg, 216 Reg, RegClass, RegClass, DL); 217 } 218 return AssignedReg; 219} 220 221std::pair<unsigned, bool> FastISel::getRegForGEPIndex(const Value *Idx) { 222 unsigned IdxN = getRegForValue(Idx); 223 if (IdxN == 0) 224 // Unhandled operand. Halt "fast" selection and bail. 225 return std::pair<unsigned, bool>(0, false); 226 227 bool IdxNIsKill = hasTrivialKill(Idx); 228 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, 234 IdxN, IdxNIsKill); 235 IdxNIsKill = true; 236 } 237 else if (IdxVT.bitsGT(PtrVT)) { 238 IdxN = FastEmit_r(IdxVT.getSimpleVT(), PtrVT, ISD::TRUNCATE, 239 IdxN, IdxNIsKill); 240 IdxNIsKill = true; 241 } 242 return std::pair<unsigned, bool>(IdxN, IdxNIsKill); 243} 244 245/// SelectBinaryOp - Select and emit code for a binary operator instruction, 246/// which has an opcode which directly corresponds to the given ISD opcode. 247/// 248bool 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. 252 return false; 253 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 257 // support it. 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. 261 if (VT == MVT::i1 && 262 (ISDOpcode == ISD::AND || ISDOpcode == ISD::OR || 263 ISDOpcode == ISD::XOR)) 264 VT = TLI.getTypeToTransformTo(I->getContext(), VT); 265 else 266 return false; 267 } 268 269 unsigned Op0 = getRegForValue(I->getOperand(0)); 270 if (Op0 == 0) 271 // Unhandled operand. Halt "fast" selection and bail. 272 return false; 273 274 bool Op0IsKill = hasTrivialKill(I->getOperand(0)); 275 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, 280 CI->getZExtValue()); 281 if (ResultReg != 0) { 282 // We successfully emitted code for the given LLVM Instruction. 283 UpdateValueMap(I, ResultReg); 284 return true; 285 } 286 } 287 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); 295 return true; 296 } 297 } 298 299 unsigned Op1 = getRegForValue(I->getOperand(1)); 300 if (Op1 == 0) 301 // Unhandled operand. Halt "fast" selection and bail. 302 return false; 303 304 bool Op1IsKill = hasTrivialKill(I->getOperand(1)); 305 306 // Now we have both operands in registers. Emit the instruction. 307 unsigned ResultReg = FastEmit_rr(VT.getSimpleVT(), VT.getSimpleVT(), 308 ISDOpcode, 309 Op0, Op0IsKill, 310 Op1, Op1IsKill); 311 if (ResultReg == 0) 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. 314 return false; 315 316 // We successfully emitted code for the given LLVM Instruction. 317 UpdateValueMap(I, ResultReg); 318 return true; 319} 320 321bool FastISel::SelectGetElementPtr(const User *I) { 322 unsigned N = getRegForValue(I->getOperand(0)); 323 if (N == 0) 324 // Unhandled operand. Halt "fast" selection and bail. 325 return false; 326 327 bool NIsKill = hasTrivialKill(I->getOperand(0)); 328 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(); 336 if (Field) { 337 // N = N + Offset 338 uint64_t Offs = TD.getStructLayout(StTy)->getElementOffset(Field); 339 // FIXME: This can be optimized by combining the add with a 340 // subsequent one. 341 N = FastEmit_ri_(VT, ISD::ADD, N, NIsKill, Offs, VT); 342 if (N == 0) 343 // Unhandled operand. Halt "fast" selection and bail. 344 return false; 345 NIsKill = true; 346 } 347 Ty = StTy->getElementType(Field); 348 } else { 349 Ty = cast<SequentialType>(Ty)->getElementType(); 350 351 // If this is a constant subscript, handle it quickly. 352 if (const ConstantInt *CI = dyn_cast<ConstantInt>(Idx)) { 353 if (CI->isZero()) continue; 354 uint64_t Offs = 355 TD.getTypeAllocSize(Ty)*cast<ConstantInt>(CI)->getSExtValue(); 356 N = FastEmit_ri_(VT, ISD::ADD, N, NIsKill, Offs, VT); 357 if (N == 0) 358 // Unhandled operand. Halt "fast" selection and bail. 359 return false; 360 NIsKill = true; 361 continue; 362 } 363 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; 369 if (IdxN == 0) 370 // Unhandled operand. Halt "fast" selection and bail. 371 return false; 372 373 if (ElementSize != 1) { 374 IdxN = FastEmit_ri_(VT, ISD::MUL, IdxN, IdxNIsKill, ElementSize, VT); 375 if (IdxN == 0) 376 // Unhandled operand. Halt "fast" selection and bail. 377 return false; 378 IdxNIsKill = true; 379 } 380 N = FastEmit_rr(VT, VT, ISD::ADD, N, NIsKill, IdxN, IdxNIsKill); 381 if (N == 0) 382 // Unhandled operand. Halt "fast" selection and bail. 383 return false; 384 } 385 } 386 387 // We successfully emitted code for the given LLVM Instruction. 388 UpdateValueMap(I, N); 389 return true; 390} 391 392bool FastISel::SelectCall(const User *I) { 393 const Function *F = cast<CallInst>(I)->getCalledFunction(); 394 if (!F) return false; 395 396 // Handle selected intrinsic function calls. 397 unsigned IID = F->getIntrinsicID(); 398 switch (IID) { 399 default: break; 400 case Intrinsic::dbg_declare: { 401 const DbgDeclareInst *DI = cast<DbgDeclareInst>(I); 402 if (!DIVariable(DI->getVariable()).Verify() || 403 !MF.getMMI().hasDebugInfo()) 404 return true; 405 406 const Value *Address = DI->getAddress(); 407 if (!Address) 408 return true; 409 if (isa<UndefValue>(Address)) 410 return true; 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. 415 if (AI) { 416 DenseMap<const AllocaInst*, int>::iterator SI = 417 StaticAllocaMap.find(AI); 418 if (SI == StaticAllocaMap.end()) break; // VLAs. 419 int FI = SI->second; 420 if (!DI->getDebugLoc().isUnknown()) 421 MF.getMMI().setVariableDbgInfo(DI->getVariable(), FI, DI->getDebugLoc()); 422 } else 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)); 426 return true; 427 } 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(); 433 if (!V) { 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()); 447 } else { 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()); 453 } 454 return true; 455 } 456 case Intrinsic::eh_exception: { 457 EVT VT = TLI.getValueType(I->getType()); 458 switch (TLI.getOperationAction(ISD::EXCEPTIONADDR, VT)) { 459 default: break; 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, 466 Reg, RC, RC, DL); 467 assert(InsertedCopy && "Can't copy address registers!"); 468 InsertedCopy = InsertedCopy; 469 UpdateValueMap(I, ResultReg); 470 return true; 471 } 472 } 473 break; 474 } 475 case Intrinsic::eh_selector: { 476 EVT VT = TLI.getValueType(I->getType()); 477 switch (TLI.getOperationAction(ISD::EHSELECTION, VT)) { 478 default: break; 479 case TargetLowering::Expand: { 480 if (MBB->isLandingPad()) 481 AddCatchInfo(*cast<CallInst>(I), &MF.getMMI(), MBB); 482 else { 483#ifndef NDEBUG 484 CatchInfoLost.insert(cast<CallInst>(I)); 485#endif 486 // FIXME: Mark exception selector register as live in. Hack for PR1508. 487 unsigned Reg = TLI.getExceptionSelectorRegister(); 488 if (Reg) MBB->addLiveIn(Reg); 489 } 490 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, 496 RC, RC, DL); 497 assert(InsertedCopy && "Can't copy address registers!"); 498 InsertedCopy = InsertedCopy; 499 500 bool ResultRegIsKill = hasTrivialKill(I); 501 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); 509 if (ResultReg == 0) 510 // Unhandled operand. Halt "fast" selection and bail. 511 return false; 512 513 UpdateValueMap(I, ResultReg); 514 515 return true; 516 } 517 } 518 break; 519 } 520 } 521 522 // An arbitrary call. Bail. 523 return false; 524} 525 526bool FastISel::SelectCast(const User *I, unsigned Opcode) { 527 EVT SrcVT = TLI.getValueType(I->getOperand(0)->getType()); 528 EVT DstVT = TLI.getValueType(I->getType()); 529 530 if (SrcVT == MVT::Other || !SrcVT.isSimple() || 531 DstVT == MVT::Other || !DstVT.isSimple()) 532 // Unhandled type. Halt "fast" selection and bail. 533 return false; 534 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. 541 return false; 542 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. 549 return false; 550 551 unsigned InputReg = getRegForValue(I->getOperand(0)); 552 if (!InputReg) 553 // Unhandled operand. Halt "fast" selection and bail. 554 return false; 555 556 bool InputRegIsKill = hasTrivialKill(I->getOperand(0)); 557 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); 562 if (!InputReg) 563 return false; 564 InputRegIsKill = true; 565 } 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); 569 570 unsigned ResultReg = FastEmit_r(SrcVT.getSimpleVT(), 571 DstVT.getSimpleVT(), 572 Opcode, 573 InputReg, InputRegIsKill); 574 if (!ResultReg) 575 return false; 576 577 UpdateValueMap(I, ResultReg); 578 return true; 579} 580 581bool 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)); 585 if (Reg == 0) 586 return false; 587 UpdateValueMap(I, Reg); 588 return true; 589 } 590 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()); 594 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. 599 return false; 600 601 unsigned Op0 = getRegForValue(I->getOperand(0)); 602 if (Op0 == 0) 603 // Unhandled operand. Halt "fast" selection and bail. 604 return false; 605 606 bool Op0IsKill = hasTrivialKill(I->getOperand(0)); 607 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); 614 615 bool InsertedCopy = TII.copyRegToReg(*MBB, MBB->end(), ResultReg, 616 Op0, DstClass, SrcClass, DL); 617 if (!InsertedCopy) 618 ResultReg = 0; 619 } 620 621 // If the reg-reg copy failed, select a BIT_CONVERT opcode. 622 if (!ResultReg) 623 ResultReg = FastEmit_r(SrcVT.getSimpleVT(), DstVT.getSimpleVT(), 624 ISD::BIT_CONVERT, Op0, Op0IsKill); 625 626 if (!ResultReg) 627 return false; 628 629 UpdateValueMap(I, ResultReg); 630 return true; 631} 632 633bool 634FastISel::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())) 639 return false; 640 641 DL = I->getDebugLoc(); 642 643 // First, try doing target-independent selection. 644 if (SelectOperator(I, I->getOpcode())) { 645 DL = DebugLoc(); 646 return true; 647 } 648 649 // Next, try calling the target to attempt to handle the instruction. 650 if (TargetSelectInstruction(I)) { 651 DL = DebugLoc(); 652 return true; 653 } 654 655 DL = DebugLoc(); 656 return false; 657} 658 659/// FastEmitBranch - Emit an unconditional branch to the given block, 660/// unless it is the immediate (fall-through) successor, and update 661/// the CFG. 662void 663FastISel::FastEmitBranch(MachineBasicBlock *MSucc, DebugLoc DL) { 664 if (MBB->isLayoutSuccessor(MSucc)) { 665 // The unconditional fall-through case, which needs no instructions. 666 } else { 667 // The unconditional branch case. 668 TII.InsertBranch(*MBB, MSucc, NULL, SmallVector<MachineOperand, 0>(), DL); 669 } 670 MBB->addSuccessor(MSucc); 671} 672 673/// SelectFNeg - Emit an FNeg operation. 674/// 675bool 676FastISel::SelectFNeg(const User *I) { 677 unsigned OpReg = getRegForValue(BinaryOperator::getFNegArgument(I)); 678 if (OpReg == 0) return false; 679 680 bool OpRegIsKill = hasTrivialKill(I); 681 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); 688 return true; 689 } 690 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)) 696 return false; 697 698 unsigned IntReg = FastEmit_r(VT.getSimpleVT(), IntVT.getSimpleVT(), 699 ISD::BIT_CONVERT, OpReg, OpRegIsKill); 700 if (IntReg == 0) 701 return false; 702 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) 708 return false; 709 710 ResultReg = FastEmit_r(IntVT.getSimpleVT(), VT.getSimpleVT(), 711 ISD::BIT_CONVERT, IntResultReg, /*Kill=*/true); 712 if (ResultReg == 0) 713 return false; 714 715 UpdateValueMap(I, ResultReg); 716 return true; 717} 718 719bool 720FastISel::SelectLoad(const User *I) { 721 LoadInst *LI = const_cast<LoadInst *>(cast<LoadInst>(I)); 722 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); 732 return true; 733 } 734 } 735 } 736 737 return false; 738} 739 740bool 741FastISel::SelectOperator(const User *I, unsigned Opcode) { 742 switch (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); 784 785 case Instruction::GetElementPtr: 786 return SelectGetElementPtr(I); 787 788 case Instruction::Br: { 789 const BranchInst *BI = cast<BranchInst>(I); 790 791 if (BI->isUnconditional()) { 792 const BasicBlock *LLVMSucc = BI->getSuccessor(0); 793 MachineBasicBlock *MSucc = MBBMap[LLVMSucc]; 794 FastEmitBranch(MSucc, BI->getDebugLoc()); 795 return true; 796 } 797 798 // Conditional branches are not handed yet. 799 // Halt "fast" selection and bail. 800 return false; 801 } 802 803 case Instruction::Unreachable: 804 // Nothing to emit. 805 return true; 806 807 case Instruction::Alloca: 808 // FunctionLowering has the static-sized case covered. 809 if (StaticAllocaMap.count(cast<AllocaInst>(I))) 810 return true; 811 812 // Dynamic-sized alloca is not handled yet. 813 return false; 814 815 case Instruction::Call: 816 return SelectCall(I); 817 818 case Instruction::BitCast: 819 return SelectBitCast(I); 820 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); 831 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); 843 return true; 844 } 845 846 case Instruction::PHI: 847 llvm_unreachable("FastISel shouldn't visit PHI nodes!"); 848 849 default: 850 // Unhandled instruction. Halt "fast" selection and bail. 851 return false; 852 } 853} 854 855FastISel::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 860#ifndef NDEBUG 861 , SmallSet<const Instruction *, 8> &cil 862#endif 863 ) 864 : MBB(0), 865 ValueMap(vm), 866 MBBMap(bm), 867 StaticAllocaMap(am), 868 PHINodesToUpdate(pn), 869#ifndef NDEBUG 870 CatchInfoLost(cil), 871#endif 872 MF(mf), 873 MRI(MF.getRegInfo()), 874 MFI(*MF.getFrameInfo()), 875 MCP(*MF.getConstantPool()), 876 TM(MF.getTarget()), 877 TD(*TM.getTargetData()), 878 TII(*TM.getInstrInfo()), 879 TLI(*TM.getTargetLowering()), 880 TRI(*TM.getRegisterInfo()), 881 IsBottomUp(false) { 882} 883 884FastISel::~FastISel() {} 885 886unsigned FastISel::FastEmit_(MVT, MVT, 887 unsigned) { 888 return 0; 889} 890 891unsigned FastISel::FastEmit_r(MVT, MVT, 892 unsigned, 893 unsigned /*Op0*/, bool /*Op0IsKill*/) { 894 return 0; 895} 896 897unsigned FastISel::FastEmit_rr(MVT, MVT, 898 unsigned, 899 unsigned /*Op0*/, bool /*Op0IsKill*/, 900 unsigned /*Op1*/, bool /*Op1IsKill*/) { 901 return 0; 902} 903 904unsigned FastISel::FastEmit_i(MVT, MVT, unsigned, uint64_t /*Imm*/) { 905 return 0; 906} 907 908unsigned FastISel::FastEmit_f(MVT, MVT, 909 unsigned, const ConstantFP * /*FPImm*/) { 910 return 0; 911} 912 913unsigned FastISel::FastEmit_ri(MVT, MVT, 914 unsigned, 915 unsigned /*Op0*/, bool /*Op0IsKill*/, 916 uint64_t /*Imm*/) { 917 return 0; 918} 919 920unsigned FastISel::FastEmit_rf(MVT, MVT, 921 unsigned, 922 unsigned /*Op0*/, bool /*Op0IsKill*/, 923 const ConstantFP * /*FPImm*/) { 924 return 0; 925} 926 927unsigned FastISel::FastEmit_rri(MVT, MVT, 928 unsigned, 929 unsigned /*Op0*/, bool /*Op0IsKill*/, 930 unsigned /*Op1*/, bool /*Op1IsKill*/, 931 uint64_t /*Imm*/) { 932 return 0; 933} 934 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. 939unsigned 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); 944 if (ResultReg != 0) 945 return ResultReg; 946 unsigned MaterialReg = FastEmit_i(ImmType, ImmType, ISD::Constant, Imm); 947 if (MaterialReg == 0) 948 return 0; 949 return FastEmit_rr(VT, VT, Opcode, 950 Op0, Op0IsKill, 951 MaterialReg, /*Kill=*/true); 952} 953 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. 958unsigned 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); 963 if (ResultReg != 0) 964 return ResultReg; 965 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(); 977 978 uint64_t x[2]; 979 uint32_t IntBitWidth = IntVT.getSizeInBits(); 980 bool isExact; 981 (void) Flt.convertToInteger(x, IntBitWidth, /*isSigned=*/true, 982 APFloat::rmTowardZero, &isExact); 983 if (!isExact) 984 return 0; 985 APInt IntVal(IntBitWidth, 2, x); 986 987 unsigned IntegerReg = FastEmit_i(IntVT.getSimpleVT(), IntVT.getSimpleVT(), 988 ISD::Constant, IntVal.getZExtValue()); 989 if (IntegerReg == 0) 990 return 0; 991 MaterialReg = FastEmit_r(IntVT.getSimpleVT(), VT, 992 ISD::SINT_TO_FP, IntegerReg, /*Kill=*/true); 993 if (MaterialReg == 0) 994 return 0; 995 } 996 return FastEmit_rr(VT, VT, Opcode, 997 Op0, Op0IsKill, 998 MaterialReg, /*Kill=*/true); 999} 1000 1001unsigned FastISel::createResultReg(const TargetRegisterClass* RC) { 1002 return MRI.createVirtualRegister(RC); 1003} 1004 1005unsigned FastISel::FastEmitInst_(unsigned MachineInstOpcode, 1006 const TargetRegisterClass* RC) { 1007 unsigned ResultReg = createResultReg(RC); 1008 const TargetInstrDesc &II = TII.get(MachineInstOpcode); 1009 1010 BuildMI(MBB, DL, II, ResultReg); 1011 return ResultReg; 1012} 1013 1014unsigned 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); 1019 1020 if (II.getNumDefs() >= 1) 1021 BuildMI(MBB, DL, II, ResultReg).addReg(Op0, Op0IsKill * RegState::Kill); 1022 else { 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); 1026 if (!InsertedCopy) 1027 ResultReg = 0; 1028 } 1029 1030 return ResultReg; 1031} 1032 1033unsigned 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); 1039 1040 if (II.getNumDefs() >= 1) 1041 BuildMI(MBB, DL, II, ResultReg) 1042 .addReg(Op0, Op0IsKill * RegState::Kill) 1043 .addReg(Op1, Op1IsKill * RegState::Kill); 1044 else { 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); 1050 if (!InsertedCopy) 1051 ResultReg = 0; 1052 } 1053 return ResultReg; 1054} 1055 1056unsigned FastISel::FastEmitInst_ri(unsigned MachineInstOpcode, 1057 const TargetRegisterClass *RC, 1058 unsigned Op0, bool Op0IsKill, 1059 uint64_t Imm) { 1060 unsigned ResultReg = createResultReg(RC); 1061 const TargetInstrDesc &II = TII.get(MachineInstOpcode); 1062 1063 if (II.getNumDefs() >= 1) 1064 BuildMI(MBB, DL, II, ResultReg) 1065 .addReg(Op0, Op0IsKill * RegState::Kill) 1066 .addImm(Imm); 1067 else { 1068 BuildMI(MBB, DL, II) 1069 .addReg(Op0, Op0IsKill * RegState::Kill) 1070 .addImm(Imm); 1071 bool InsertedCopy = TII.copyRegToReg(*MBB, MBB->end(), ResultReg, 1072 II.ImplicitDefs[0], RC, RC, DL); 1073 if (!InsertedCopy) 1074 ResultReg = 0; 1075 } 1076 return ResultReg; 1077} 1078 1079unsigned 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); 1085 1086 if (II.getNumDefs() >= 1) 1087 BuildMI(MBB, DL, II, ResultReg) 1088 .addReg(Op0, Op0IsKill * RegState::Kill) 1089 .addFPImm(FPImm); 1090 else { 1091 BuildMI(MBB, DL, II) 1092 .addReg(Op0, Op0IsKill * RegState::Kill) 1093 .addFPImm(FPImm); 1094 bool InsertedCopy = TII.copyRegToReg(*MBB, MBB->end(), ResultReg, 1095 II.ImplicitDefs[0], RC, RC, DL); 1096 if (!InsertedCopy) 1097 ResultReg = 0; 1098 } 1099 return ResultReg; 1100} 1101 1102unsigned FastISel::FastEmitInst_rri(unsigned MachineInstOpcode, 1103 const TargetRegisterClass *RC, 1104 unsigned Op0, bool Op0IsKill, 1105 unsigned Op1, bool Op1IsKill, 1106 uint64_t Imm) { 1107 unsigned ResultReg = createResultReg(RC); 1108 const TargetInstrDesc &II = TII.get(MachineInstOpcode); 1109 1110 if (II.getNumDefs() >= 1) 1111 BuildMI(MBB, DL, II, ResultReg) 1112 .addReg(Op0, Op0IsKill * RegState::Kill) 1113 .addReg(Op1, Op1IsKill * RegState::Kill) 1114 .addImm(Imm); 1115 else { 1116 BuildMI(MBB, DL, II) 1117 .addReg(Op0, Op0IsKill * RegState::Kill) 1118 .addReg(Op1, Op1IsKill * RegState::Kill) 1119 .addImm(Imm); 1120 bool InsertedCopy = TII.copyRegToReg(*MBB, MBB->end(), ResultReg, 1121 II.ImplicitDefs[0], RC, RC, DL); 1122 if (!InsertedCopy) 1123 ResultReg = 0; 1124 } 1125 return ResultReg; 1126} 1127 1128unsigned FastISel::FastEmitInst_i(unsigned MachineInstOpcode, 1129 const TargetRegisterClass *RC, 1130 uint64_t Imm) { 1131 unsigned ResultReg = createResultReg(RC); 1132 const TargetInstrDesc &II = TII.get(MachineInstOpcode); 1133 1134 if (II.getNumDefs() >= 1) 1135 BuildMI(MBB, DL, II, ResultReg).addImm(Imm); 1136 else { 1137 BuildMI(MBB, DL, II).addImm(Imm); 1138 bool InsertedCopy = TII.copyRegToReg(*MBB, MBB->end(), ResultReg, 1139 II.ImplicitDefs[0], RC, RC, DL); 1140 if (!InsertedCopy) 1141 ResultReg = 0; 1142 } 1143 return ResultReg; 1144} 1145 1146unsigned FastISel::FastEmitInst_extractsubreg(MVT RetVT, 1147 unsigned Op0, bool Op0IsKill, 1148 uint32_t Idx) { 1149 const TargetRegisterClass* RC = MRI.getRegClass(Op0); 1150 1151 unsigned ResultReg = createResultReg(TLI.getRegClassFor(RetVT)); 1152 const TargetInstrDesc &II = TII.get(TargetOpcode::EXTRACT_SUBREG); 1153 1154 if (II.getNumDefs() >= 1) 1155 BuildMI(MBB, DL, II, ResultReg) 1156 .addReg(Op0, Op0IsKill * RegState::Kill) 1157 .addImm(Idx); 1158 else { 1159 BuildMI(MBB, DL, II) 1160 .addReg(Op0, Op0IsKill * RegState::Kill) 1161 .addImm(Idx); 1162 bool InsertedCopy = TII.copyRegToReg(*MBB, MBB->end(), ResultReg, 1163 II.ImplicitDefs[0], RC, RC, DL); 1164 if (!InsertedCopy) 1165 ResultReg = 0; 1166 } 1167 return ResultReg; 1168} 1169 1170/// FastEmitZExtFromI1 - Emit MachineInstrs to compute the value of Op 1171/// with all but the least significant bit set to zero. 1172unsigned FastISel::FastEmitZExtFromI1(MVT VT, unsigned Op0, bool Op0IsKill) { 1173 return FastEmit_ri(VT, VT, ISD::AND, Op0, Op0IsKill, 1); 1174} 1175 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. 1182bool FastISel::HandlePHINodesInSuccessorBlocks(const BasicBlock *LLVMBB) { 1183 const TerminatorInst *TI = LLVMBB->getTerminator(); 1184 1185 SmallPtrSet<MachineBasicBlock *, 4> SuccsHandled; 1186 unsigned OrigNumPHINodesToUpdate = PHINodesToUpdate.size(); 1187 1188 // Check successor nodes' PHI nodes that expect a constant to be available 1189 // from this block. 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]; 1194 1195 // If this terminator has multiple identical successors (common for 1196 // switches), only handle each succ once. 1197 if (!SuccsHandled.insert(SuccMBB)) continue; 1198 1199 MachineBasicBlock::iterator MBBI = SuccMBB->begin(); 1200 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 1203 // emitted yet. 1204 for (BasicBlock::const_iterator I = SuccBB->begin(); 1205 const PHINode *PN = dyn_cast<PHINode>(I); ++I) { 1206 1207 // Ignore dead phi's. 1208 if (PN->use_empty()) continue; 1209 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 CreateRegForValue 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)) { 1218 // Promote MVT::i1. 1219 if (VT == MVT::i1) 1220 VT = TLI.getTypeToTransformTo(LLVMBB->getContext(), VT); 1221 else { 1222 PHINodesToUpdate.resize(OrigNumPHINodesToUpdate); 1223 return false; 1224 } 1225 } 1226 1227 const Value *PHIOp = PN->getIncomingValueForBlock(LLVMBB); 1228 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(); 1234 1235 unsigned Reg = getRegForValue(PHIOp); 1236 if (Reg == 0) { 1237 PHINodesToUpdate.resize(OrigNumPHINodesToUpdate); 1238 return false; 1239 } 1240 PHINodesToUpdate.push_back(std::make_pair(MBBI++, Reg)); 1241 DL = DebugLoc(); 1242 } 1243 } 1244 1245 return true; 1246} 1247