FastISel.cpp revision 3193a689db3de8640d412ccd9482301647359a4e
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/Target/TargetData.h" 52#include "llvm/Target/TargetInstrInfo.h" 53#include "llvm/Target/TargetLowering.h" 54#include "llvm/Target/TargetMachine.h" 55#include "llvm/Support/ErrorHandling.h" 56#include "FunctionLoweringInfo.h" 57using namespace llvm; 58 59bool FastISel::hasTrivialKill(const Value *V) const { 60 // Don't consider constants or arguments to have trivial kills. 61 const Instruction *I = dyn_cast<Instruction>(V); 62 if (!I) 63 return false; 64 65 // No-op casts are trivially coalesced by fast-isel. 66 if (const CastInst *Cast = dyn_cast<CastInst>(I)) 67 if (Cast->isNoopCast(TD.getIntPtrType(Cast->getContext())) && 68 !hasTrivialKill(Cast->getOperand(0))) 69 return false; 70 71 // Only instructions with a single use in the same basic block are considered 72 // to have trivial kills. 73 return I->hasOneUse() && 74 !(I->getOpcode() == Instruction::BitCast || 75 I->getOpcode() == Instruction::PtrToInt || 76 I->getOpcode() == Instruction::IntToPtr) && 77 cast<Instruction>(I->use_begin())->getParent() == I->getParent(); 78} 79 80unsigned FastISel::getRegForValue(const Value *V) { 81 EVT RealVT = TLI.getValueType(V->getType(), /*AllowUnknown=*/true); 82 // Don't handle non-simple values in FastISel. 83 if (!RealVT.isSimple()) 84 return 0; 85 86 // Ignore illegal types. We must do this before looking up the value 87 // in ValueMap because Arguments are given virtual registers regardless 88 // of whether FastISel can handle them. 89 MVT VT = RealVT.getSimpleVT(); 90 if (!TLI.isTypeLegal(VT)) { 91 // Promote MVT::i1 to a legal type though, because it's common and easy. 92 if (VT == MVT::i1) 93 VT = TLI.getTypeToTransformTo(V->getContext(), VT).getSimpleVT(); 94 else 95 return 0; 96 } 97 98 // Look up the value to see if we already have a register for it. We 99 // cache values defined by Instructions across blocks, and other values 100 // only locally. This is because Instructions already have the SSA 101 // def-dominates-use requirement enforced. 102 DenseMap<const Value *, unsigned>::iterator I = ValueMap.find(V); 103 if (I != ValueMap.end()) 104 return I->second; 105 unsigned Reg = LocalValueMap[V]; 106 if (Reg != 0) 107 return Reg; 108 109 // In bottom-up mode, just create the virtual register which will be used 110 // to hold the value. It will be materialized later. 111 if (IsBottomUp) { 112 Reg = createResultReg(TLI.getRegClassFor(VT)); 113 if (isa<Instruction>(V)) 114 ValueMap[V] = Reg; 115 else 116 LocalValueMap[V] = Reg; 117 return Reg; 118 } 119 120 return materializeRegForValue(V, VT); 121} 122 123/// materializeRegForValue - Helper for getRegForVale. This function is 124/// called when the value isn't already available in a register and must 125/// be materialized with new instructions. 126unsigned FastISel::materializeRegForValue(const Value *V, MVT VT) { 127 unsigned Reg = 0; 128 129 if (const ConstantInt *CI = dyn_cast<ConstantInt>(V)) { 130 if (CI->getValue().getActiveBits() <= 64) 131 Reg = FastEmit_i(VT, VT, ISD::Constant, CI->getZExtValue()); 132 } else if (isa<AllocaInst>(V)) { 133 Reg = TargetMaterializeAlloca(cast<AllocaInst>(V)); 134 } else if (isa<ConstantPointerNull>(V)) { 135 // Translate this as an integer zero so that it can be 136 // local-CSE'd with actual integer zeros. 137 Reg = 138 getRegForValue(Constant::getNullValue(TD.getIntPtrType(V->getContext()))); 139 } else if (const ConstantFP *CF = dyn_cast<ConstantFP>(V)) { 140 // Try to emit the constant directly. 141 Reg = FastEmit_f(VT, VT, ISD::ConstantFP, CF); 142 143 if (!Reg) { 144 // Try to emit the constant by using an integer constant with a cast. 145 const APFloat &Flt = CF->getValueAPF(); 146 EVT IntVT = TLI.getPointerTy(); 147 148 uint64_t x[2]; 149 uint32_t IntBitWidth = IntVT.getSizeInBits(); 150 bool isExact; 151 (void) Flt.convertToInteger(x, IntBitWidth, /*isSigned=*/true, 152 APFloat::rmTowardZero, &isExact); 153 if (isExact) { 154 APInt IntVal(IntBitWidth, 2, x); 155 156 unsigned IntegerReg = 157 getRegForValue(ConstantInt::get(V->getContext(), IntVal)); 158 if (IntegerReg != 0) 159 Reg = FastEmit_r(IntVT.getSimpleVT(), VT, ISD::SINT_TO_FP, 160 IntegerReg, /*Kill=*/false); 161 } 162 } 163 } else if (const Operator *Op = dyn_cast<Operator>(V)) { 164 if (!SelectOperator(Op, Op->getOpcode())) return 0; 165 Reg = lookUpRegForValue(Op); 166 } else if (isa<UndefValue>(V)) { 167 Reg = createResultReg(TLI.getRegClassFor(VT)); 168 BuildMI(MBB, DL, TII.get(TargetOpcode::IMPLICIT_DEF), Reg); 169 } 170 171 // If target-independent code couldn't handle the value, give target-specific 172 // code a try. 173 if (!Reg && isa<Constant>(V)) 174 Reg = TargetMaterializeConstant(cast<Constant>(V)); 175 176 // Don't cache constant materializations in the general ValueMap. 177 // To do so would require tracking what uses they dominate. 178 if (Reg != 0) 179 LocalValueMap[V] = Reg; 180 return Reg; 181} 182 183unsigned FastISel::lookUpRegForValue(const Value *V) { 184 // Look up the value to see if we already have a register for it. We 185 // cache values defined by Instructions across blocks, and other values 186 // only locally. This is because Instructions already have the SSA 187 // def-dominates-use requirement enforced. 188 DenseMap<const Value *, unsigned>::iterator I = ValueMap.find(V); 189 if (I != ValueMap.end()) 190 return I->second; 191 return LocalValueMap[V]; 192} 193 194/// UpdateValueMap - Update the value map to include the new mapping for this 195/// instruction, or insert an extra copy to get the result in a previous 196/// determined register. 197/// NOTE: This is only necessary because we might select a block that uses 198/// a value before we select the block that defines the value. It might be 199/// possible to fix this by selecting blocks in reverse postorder. 200unsigned FastISel::UpdateValueMap(const Value *I, unsigned Reg) { 201 if (!isa<Instruction>(I)) { 202 LocalValueMap[I] = Reg; 203 return Reg; 204 } 205 206 unsigned &AssignedReg = ValueMap[I]; 207 if (AssignedReg == 0) 208 AssignedReg = Reg; 209 else if (Reg != AssignedReg) { 210 const TargetRegisterClass *RegClass = MRI.getRegClass(Reg); 211 TII.copyRegToReg(*MBB, MBB->end(), AssignedReg, 212 Reg, RegClass, RegClass, DL); 213 } 214 return AssignedReg; 215} 216 217std::pair<unsigned, bool> FastISel::getRegForGEPIndex(const Value *Idx) { 218 unsigned IdxN = getRegForValue(Idx); 219 if (IdxN == 0) 220 // Unhandled operand. Halt "fast" selection and bail. 221 return std::pair<unsigned, bool>(0, false); 222 223 bool IdxNIsKill = hasTrivialKill(Idx); 224 225 // If the index is smaller or larger than intptr_t, truncate or extend it. 226 MVT PtrVT = TLI.getPointerTy(); 227 EVT IdxVT = EVT::getEVT(Idx->getType(), /*HandleUnknown=*/false); 228 if (IdxVT.bitsLT(PtrVT)) { 229 IdxN = FastEmit_r(IdxVT.getSimpleVT(), PtrVT, ISD::SIGN_EXTEND, 230 IdxN, IdxNIsKill); 231 IdxNIsKill = true; 232 } 233 else if (IdxVT.bitsGT(PtrVT)) { 234 IdxN = FastEmit_r(IdxVT.getSimpleVT(), PtrVT, ISD::TRUNCATE, 235 IdxN, IdxNIsKill); 236 IdxNIsKill = true; 237 } 238 return std::pair<unsigned, bool>(IdxN, IdxNIsKill); 239} 240 241/// SelectBinaryOp - Select and emit code for a binary operator instruction, 242/// which has an opcode which directly corresponds to the given ISD opcode. 243/// 244bool FastISel::SelectBinaryOp(const User *I, unsigned ISDOpcode) { 245 EVT VT = EVT::getEVT(I->getType(), /*HandleUnknown=*/true); 246 if (VT == MVT::Other || !VT.isSimple()) 247 // Unhandled type. Halt "fast" selection and bail. 248 return false; 249 250 // We only handle legal types. For example, on x86-32 the instruction 251 // selector contains all of the 64-bit instructions from x86-64, 252 // under the assumption that i64 won't be used if the target doesn't 253 // support it. 254 if (!TLI.isTypeLegal(VT)) { 255 // MVT::i1 is special. Allow AND, OR, or XOR because they 256 // don't require additional zeroing, which makes them easy. 257 if (VT == MVT::i1 && 258 (ISDOpcode == ISD::AND || ISDOpcode == ISD::OR || 259 ISDOpcode == ISD::XOR)) 260 VT = TLI.getTypeToTransformTo(I->getContext(), VT); 261 else 262 return false; 263 } 264 265 unsigned Op0 = getRegForValue(I->getOperand(0)); 266 if (Op0 == 0) 267 // Unhandled operand. Halt "fast" selection and bail. 268 return false; 269 270 bool Op0IsKill = hasTrivialKill(I->getOperand(0)); 271 272 // Check if the second operand is a constant and handle it appropriately. 273 if (ConstantInt *CI = dyn_cast<ConstantInt>(I->getOperand(1))) { 274 unsigned ResultReg = FastEmit_ri(VT.getSimpleVT(), VT.getSimpleVT(), 275 ISDOpcode, Op0, Op0IsKill, 276 CI->getZExtValue()); 277 if (ResultReg != 0) { 278 // We successfully emitted code for the given LLVM Instruction. 279 UpdateValueMap(I, ResultReg); 280 return true; 281 } 282 } 283 284 // Check if the second operand is a constant float. 285 if (ConstantFP *CF = dyn_cast<ConstantFP>(I->getOperand(1))) { 286 unsigned ResultReg = FastEmit_rf(VT.getSimpleVT(), VT.getSimpleVT(), 287 ISDOpcode, Op0, Op0IsKill, CF); 288 if (ResultReg != 0) { 289 // We successfully emitted code for the given LLVM Instruction. 290 UpdateValueMap(I, ResultReg); 291 return true; 292 } 293 } 294 295 unsigned Op1 = getRegForValue(I->getOperand(1)); 296 if (Op1 == 0) 297 // Unhandled operand. Halt "fast" selection and bail. 298 return false; 299 300 bool Op1IsKill = hasTrivialKill(I->getOperand(1)); 301 302 // Now we have both operands in registers. Emit the instruction. 303 unsigned ResultReg = FastEmit_rr(VT.getSimpleVT(), VT.getSimpleVT(), 304 ISDOpcode, 305 Op0, Op0IsKill, 306 Op1, Op1IsKill); 307 if (ResultReg == 0) 308 // Target-specific code wasn't able to find a machine opcode for 309 // the given ISD opcode and type. Halt "fast" selection and bail. 310 return false; 311 312 // We successfully emitted code for the given LLVM Instruction. 313 UpdateValueMap(I, ResultReg); 314 return true; 315} 316 317bool FastISel::SelectGetElementPtr(const User *I) { 318 unsigned N = getRegForValue(I->getOperand(0)); 319 if (N == 0) 320 // Unhandled operand. Halt "fast" selection and bail. 321 return false; 322 323 bool NIsKill = hasTrivialKill(I->getOperand(0)); 324 325 const Type *Ty = I->getOperand(0)->getType(); 326 MVT VT = TLI.getPointerTy(); 327 for (GetElementPtrInst::const_op_iterator OI = I->op_begin()+1, 328 E = I->op_end(); OI != E; ++OI) { 329 const Value *Idx = *OI; 330 if (const StructType *StTy = dyn_cast<StructType>(Ty)) { 331 unsigned Field = cast<ConstantInt>(Idx)->getZExtValue(); 332 if (Field) { 333 // N = N + Offset 334 uint64_t Offs = TD.getStructLayout(StTy)->getElementOffset(Field); 335 // FIXME: This can be optimized by combining the add with a 336 // subsequent one. 337 N = FastEmit_ri_(VT, ISD::ADD, N, NIsKill, Offs, VT); 338 if (N == 0) 339 // Unhandled operand. Halt "fast" selection and bail. 340 return false; 341 NIsKill = true; 342 } 343 Ty = StTy->getElementType(Field); 344 } else { 345 Ty = cast<SequentialType>(Ty)->getElementType(); 346 347 // If this is a constant subscript, handle it quickly. 348 if (const ConstantInt *CI = dyn_cast<ConstantInt>(Idx)) { 349 if (CI->isZero()) continue; 350 uint64_t Offs = 351 TD.getTypeAllocSize(Ty)*cast<ConstantInt>(CI)->getSExtValue(); 352 N = FastEmit_ri_(VT, ISD::ADD, N, NIsKill, Offs, VT); 353 if (N == 0) 354 // Unhandled operand. Halt "fast" selection and bail. 355 return false; 356 NIsKill = true; 357 continue; 358 } 359 360 // N = N + Idx * ElementSize; 361 uint64_t ElementSize = TD.getTypeAllocSize(Ty); 362 std::pair<unsigned, bool> Pair = getRegForGEPIndex(Idx); 363 unsigned IdxN = Pair.first; 364 bool IdxNIsKill = Pair.second; 365 if (IdxN == 0) 366 // Unhandled operand. Halt "fast" selection and bail. 367 return false; 368 369 if (ElementSize != 1) { 370 IdxN = FastEmit_ri_(VT, ISD::MUL, IdxN, IdxNIsKill, ElementSize, VT); 371 if (IdxN == 0) 372 // Unhandled operand. Halt "fast" selection and bail. 373 return false; 374 IdxNIsKill = true; 375 } 376 N = FastEmit_rr(VT, VT, ISD::ADD, N, NIsKill, IdxN, IdxNIsKill); 377 if (N == 0) 378 // Unhandled operand. Halt "fast" selection and bail. 379 return false; 380 } 381 } 382 383 // We successfully emitted code for the given LLVM Instruction. 384 UpdateValueMap(I, N); 385 return true; 386} 387 388bool FastISel::SelectCall(const User *I) { 389 const Function *F = cast<CallInst>(I)->getCalledFunction(); 390 if (!F) return false; 391 392 // Handle selected intrinsic function calls. 393 unsigned IID = F->getIntrinsicID(); 394 switch (IID) { 395 default: break; 396 case Intrinsic::dbg_declare: { 397 const DbgDeclareInst *DI = cast<DbgDeclareInst>(I); 398 if (!DIVariable(DI->getVariable()).Verify() || 399 !MF.getMMI().hasDebugInfo()) 400 return true; 401 402 const Value *Address = DI->getAddress(); 403 if (!Address) 404 return true; 405 if (isa<UndefValue>(Address)) 406 return true; 407 const AllocaInst *AI = dyn_cast<AllocaInst>(Address); 408 // Don't handle byval struct arguments or VLAs, for example. 409 // Note that if we have a byval struct argument, fast ISel is turned off; 410 // those are handled in SelectionDAGBuilder. 411 if (AI) { 412 DenseMap<const AllocaInst*, int>::iterator SI = 413 StaticAllocaMap.find(AI); 414 if (SI == StaticAllocaMap.end()) break; // VLAs. 415 int FI = SI->second; 416 if (!DI->getDebugLoc().isUnknown()) 417 MF.getMMI().setVariableDbgInfo(DI->getVariable(), FI, DI->getDebugLoc()); 418 } else 419 // Building the map above is target independent. Generating DBG_VALUE 420 // inline is target dependent; do this now. 421 (void)TargetSelectInstruction(cast<Instruction>(I)); 422 return true; 423 } 424 case Intrinsic::dbg_value: { 425 // This form of DBG_VALUE is target-independent. 426 const DbgValueInst *DI = cast<DbgValueInst>(I); 427 const TargetInstrDesc &II = TII.get(TargetOpcode::DBG_VALUE); 428 const Value *V = DI->getValue(); 429 if (!V) { 430 // Currently the optimizer can produce this; insert an undef to 431 // help debugging. Probably the optimizer should not do this. 432 BuildMI(MBB, DL, II).addReg(0U).addImm(DI->getOffset()). 433 addMetadata(DI->getVariable()); 434 } else if (const ConstantInt *CI = dyn_cast<ConstantInt>(V)) { 435 BuildMI(MBB, DL, II).addImm(CI->getZExtValue()).addImm(DI->getOffset()). 436 addMetadata(DI->getVariable()); 437 } else if (const ConstantFP *CF = dyn_cast<ConstantFP>(V)) { 438 BuildMI(MBB, DL, II).addFPImm(CF).addImm(DI->getOffset()). 439 addMetadata(DI->getVariable()); 440 } else if (unsigned Reg = lookUpRegForValue(V)) { 441 BuildMI(MBB, DL, II).addReg(Reg, RegState::Debug).addImm(DI->getOffset()). 442 addMetadata(DI->getVariable()); 443 } else { 444 // We can't yet handle anything else here because it would require 445 // generating code, thus altering codegen because of debug info. 446 // Insert an undef so we can see what we dropped. 447 BuildMI(MBB, DL, II).addReg(0U).addImm(DI->getOffset()). 448 addMetadata(DI->getVariable()); 449 } 450 return true; 451 } 452 case Intrinsic::eh_exception: { 453 EVT VT = TLI.getValueType(I->getType()); 454 switch (TLI.getOperationAction(ISD::EXCEPTIONADDR, VT)) { 455 default: break; 456 case TargetLowering::Expand: { 457 assert(MBB->isLandingPad() && "Call to eh.exception not in landing pad!"); 458 unsigned Reg = TLI.getExceptionAddressRegister(); 459 const TargetRegisterClass *RC = TLI.getRegClassFor(VT); 460 unsigned ResultReg = createResultReg(RC); 461 bool InsertedCopy = TII.copyRegToReg(*MBB, MBB->end(), ResultReg, 462 Reg, RC, RC, DL); 463 assert(InsertedCopy && "Can't copy address registers!"); 464 InsertedCopy = InsertedCopy; 465 UpdateValueMap(I, ResultReg); 466 return true; 467 } 468 } 469 break; 470 } 471 case Intrinsic::eh_selector: { 472 EVT VT = TLI.getValueType(I->getType()); 473 switch (TLI.getOperationAction(ISD::EHSELECTION, VT)) { 474 default: break; 475 case TargetLowering::Expand: { 476 if (MBB->isLandingPad()) 477 AddCatchInfo(*cast<CallInst>(I), &MF.getMMI(), MBB); 478 else { 479#ifndef NDEBUG 480 CatchInfoLost.insert(cast<CallInst>(I)); 481#endif 482 // FIXME: Mark exception selector register as live in. Hack for PR1508. 483 unsigned Reg = TLI.getExceptionSelectorRegister(); 484 if (Reg) MBB->addLiveIn(Reg); 485 } 486 487 unsigned Reg = TLI.getExceptionSelectorRegister(); 488 EVT SrcVT = TLI.getPointerTy(); 489 const TargetRegisterClass *RC = TLI.getRegClassFor(SrcVT); 490 unsigned ResultReg = createResultReg(RC); 491 bool InsertedCopy = TII.copyRegToReg(*MBB, MBB->end(), ResultReg, Reg, 492 RC, RC, DL); 493 assert(InsertedCopy && "Can't copy address registers!"); 494 InsertedCopy = InsertedCopy; 495 496 bool ResultRegIsKill = hasTrivialKill(I); 497 498 // Cast the register to the type of the selector. 499 if (SrcVT.bitsGT(MVT::i32)) 500 ResultReg = FastEmit_r(SrcVT.getSimpleVT(), MVT::i32, ISD::TRUNCATE, 501 ResultReg, ResultRegIsKill); 502 else if (SrcVT.bitsLT(MVT::i32)) 503 ResultReg = FastEmit_r(SrcVT.getSimpleVT(), MVT::i32, 504 ISD::SIGN_EXTEND, ResultReg, ResultRegIsKill); 505 if (ResultReg == 0) 506 // Unhandled operand. Halt "fast" selection and bail. 507 return false; 508 509 UpdateValueMap(I, ResultReg); 510 511 return true; 512 } 513 } 514 break; 515 } 516 } 517 518 // An arbitrary call. Bail. 519 return false; 520} 521 522bool FastISel::SelectCast(const User *I, unsigned Opcode) { 523 EVT SrcVT = TLI.getValueType(I->getOperand(0)->getType()); 524 EVT DstVT = TLI.getValueType(I->getType()); 525 526 if (SrcVT == MVT::Other || !SrcVT.isSimple() || 527 DstVT == MVT::Other || !DstVT.isSimple()) 528 // Unhandled type. Halt "fast" selection and bail. 529 return false; 530 531 // Check if the destination type is legal. Or as a special case, 532 // it may be i1 if we're doing a truncate because that's 533 // easy and somewhat common. 534 if (!TLI.isTypeLegal(DstVT)) 535 if (DstVT != MVT::i1 || Opcode != ISD::TRUNCATE) 536 // Unhandled type. Halt "fast" selection and bail. 537 return false; 538 539 // Check if the source operand is legal. Or as a special case, 540 // it may be i1 if we're doing zero-extension because that's 541 // easy and somewhat common. 542 if (!TLI.isTypeLegal(SrcVT)) 543 if (SrcVT != MVT::i1 || Opcode != ISD::ZERO_EXTEND) 544 // Unhandled type. Halt "fast" selection and bail. 545 return false; 546 547 unsigned InputReg = getRegForValue(I->getOperand(0)); 548 if (!InputReg) 549 // Unhandled operand. Halt "fast" selection and bail. 550 return false; 551 552 bool InputRegIsKill = hasTrivialKill(I->getOperand(0)); 553 554 // If the operand is i1, arrange for the high bits in the register to be zero. 555 if (SrcVT == MVT::i1) { 556 SrcVT = TLI.getTypeToTransformTo(I->getContext(), SrcVT); 557 InputReg = FastEmitZExtFromI1(SrcVT.getSimpleVT(), InputReg, InputRegIsKill); 558 if (!InputReg) 559 return false; 560 InputRegIsKill = true; 561 } 562 // If the result is i1, truncate to the target's type for i1 first. 563 if (DstVT == MVT::i1) 564 DstVT = TLI.getTypeToTransformTo(I->getContext(), DstVT); 565 566 unsigned ResultReg = FastEmit_r(SrcVT.getSimpleVT(), 567 DstVT.getSimpleVT(), 568 Opcode, 569 InputReg, InputRegIsKill); 570 if (!ResultReg) 571 return false; 572 573 UpdateValueMap(I, ResultReg); 574 return true; 575} 576 577bool FastISel::SelectBitCast(const User *I) { 578 // If the bitcast doesn't change the type, just use the operand value. 579 if (I->getType() == I->getOperand(0)->getType()) { 580 unsigned Reg = getRegForValue(I->getOperand(0)); 581 if (Reg == 0) 582 return false; 583 UpdateValueMap(I, Reg); 584 return true; 585 } 586 587 // Bitcasts of other values become reg-reg copies or BIT_CONVERT operators. 588 EVT SrcVT = TLI.getValueType(I->getOperand(0)->getType()); 589 EVT DstVT = TLI.getValueType(I->getType()); 590 591 if (SrcVT == MVT::Other || !SrcVT.isSimple() || 592 DstVT == MVT::Other || !DstVT.isSimple() || 593 !TLI.isTypeLegal(SrcVT) || !TLI.isTypeLegal(DstVT)) 594 // Unhandled type. Halt "fast" selection and bail. 595 return false; 596 597 unsigned Op0 = getRegForValue(I->getOperand(0)); 598 if (Op0 == 0) 599 // Unhandled operand. Halt "fast" selection and bail. 600 return false; 601 602 bool Op0IsKill = hasTrivialKill(I->getOperand(0)); 603 604 // First, try to perform the bitcast by inserting a reg-reg copy. 605 unsigned ResultReg = 0; 606 if (SrcVT.getSimpleVT() == DstVT.getSimpleVT()) { 607 TargetRegisterClass* SrcClass = TLI.getRegClassFor(SrcVT); 608 TargetRegisterClass* DstClass = TLI.getRegClassFor(DstVT); 609 ResultReg = createResultReg(DstClass); 610 611 bool InsertedCopy = TII.copyRegToReg(*MBB, MBB->end(), ResultReg, 612 Op0, DstClass, SrcClass, DL); 613 if (!InsertedCopy) 614 ResultReg = 0; 615 } 616 617 // If the reg-reg copy failed, select a BIT_CONVERT opcode. 618 if (!ResultReg) 619 ResultReg = FastEmit_r(SrcVT.getSimpleVT(), DstVT.getSimpleVT(), 620 ISD::BIT_CONVERT, Op0, Op0IsKill); 621 622 if (!ResultReg) 623 return false; 624 625 UpdateValueMap(I, ResultReg); 626 return true; 627} 628 629bool 630FastISel::SelectInstruction(const Instruction *I) { 631 // Just before the terminator instruction, insert instructions to 632 // feed PHI nodes in successor blocks. 633 if (isa<TerminatorInst>(I)) 634 if (!HandlePHINodesInSuccessorBlocks(I->getParent())) 635 return false; 636 637 DL = I->getDebugLoc(); 638 639 // First, try doing target-independent selection. 640 if (SelectOperator(I, I->getOpcode())) { 641 DL = DebugLoc(); 642 return true; 643 } 644 645 // Next, try calling the target to attempt to handle the instruction. 646 if (TargetSelectInstruction(I)) { 647 DL = DebugLoc(); 648 return true; 649 } 650 651 DL = DebugLoc(); 652 return false; 653} 654 655/// FastEmitBranch - Emit an unconditional branch to the given block, 656/// unless it is the immediate (fall-through) successor, and update 657/// the CFG. 658void 659FastISel::FastEmitBranch(MachineBasicBlock *MSucc, DebugLoc DL) { 660 if (MBB->isLayoutSuccessor(MSucc)) { 661 // The unconditional fall-through case, which needs no instructions. 662 } else { 663 // The unconditional branch case. 664 TII.InsertBranch(*MBB, MSucc, NULL, SmallVector<MachineOperand, 0>(), DL); 665 } 666 MBB->addSuccessor(MSucc); 667} 668 669/// SelectFNeg - Emit an FNeg operation. 670/// 671bool 672FastISel::SelectFNeg(const User *I) { 673 unsigned OpReg = getRegForValue(BinaryOperator::getFNegArgument(I)); 674 if (OpReg == 0) return false; 675 676 bool OpRegIsKill = hasTrivialKill(I); 677 678 // If the target has ISD::FNEG, use it. 679 EVT VT = TLI.getValueType(I->getType()); 680 unsigned ResultReg = FastEmit_r(VT.getSimpleVT(), VT.getSimpleVT(), 681 ISD::FNEG, OpReg, OpRegIsKill); 682 if (ResultReg != 0) { 683 UpdateValueMap(I, ResultReg); 684 return true; 685 } 686 687 // Bitcast the value to integer, twiddle the sign bit with xor, 688 // and then bitcast it back to floating-point. 689 if (VT.getSizeInBits() > 64) return false; 690 EVT IntVT = EVT::getIntegerVT(I->getContext(), VT.getSizeInBits()); 691 if (!TLI.isTypeLegal(IntVT)) 692 return false; 693 694 unsigned IntReg = FastEmit_r(VT.getSimpleVT(), IntVT.getSimpleVT(), 695 ISD::BIT_CONVERT, OpReg, OpRegIsKill); 696 if (IntReg == 0) 697 return false; 698 699 unsigned IntResultReg = FastEmit_ri_(IntVT.getSimpleVT(), ISD::XOR, 700 IntReg, /*Kill=*/true, 701 UINT64_C(1) << (VT.getSizeInBits()-1), 702 IntVT.getSimpleVT()); 703 if (IntResultReg == 0) 704 return false; 705 706 ResultReg = FastEmit_r(IntVT.getSimpleVT(), VT.getSimpleVT(), 707 ISD::BIT_CONVERT, IntResultReg, /*Kill=*/true); 708 if (ResultReg == 0) 709 return false; 710 711 UpdateValueMap(I, ResultReg); 712 return true; 713} 714 715bool 716FastISel::SelectOperator(const User *I, unsigned Opcode) { 717 switch (Opcode) { 718 case Instruction::Add: 719 return SelectBinaryOp(I, ISD::ADD); 720 case Instruction::FAdd: 721 return SelectBinaryOp(I, ISD::FADD); 722 case Instruction::Sub: 723 return SelectBinaryOp(I, ISD::SUB); 724 case Instruction::FSub: 725 // FNeg is currently represented in LLVM IR as a special case of FSub. 726 if (BinaryOperator::isFNeg(I)) 727 return SelectFNeg(I); 728 return SelectBinaryOp(I, ISD::FSUB); 729 case Instruction::Mul: 730 return SelectBinaryOp(I, ISD::MUL); 731 case Instruction::FMul: 732 return SelectBinaryOp(I, ISD::FMUL); 733 case Instruction::SDiv: 734 return SelectBinaryOp(I, ISD::SDIV); 735 case Instruction::UDiv: 736 return SelectBinaryOp(I, ISD::UDIV); 737 case Instruction::FDiv: 738 return SelectBinaryOp(I, ISD::FDIV); 739 case Instruction::SRem: 740 return SelectBinaryOp(I, ISD::SREM); 741 case Instruction::URem: 742 return SelectBinaryOp(I, ISD::UREM); 743 case Instruction::FRem: 744 return SelectBinaryOp(I, ISD::FREM); 745 case Instruction::Shl: 746 return SelectBinaryOp(I, ISD::SHL); 747 case Instruction::LShr: 748 return SelectBinaryOp(I, ISD::SRL); 749 case Instruction::AShr: 750 return SelectBinaryOp(I, ISD::SRA); 751 case Instruction::And: 752 return SelectBinaryOp(I, ISD::AND); 753 case Instruction::Or: 754 return SelectBinaryOp(I, ISD::OR); 755 case Instruction::Xor: 756 return SelectBinaryOp(I, ISD::XOR); 757 758 case Instruction::GetElementPtr: 759 return SelectGetElementPtr(I); 760 761 case Instruction::Br: { 762 const BranchInst *BI = cast<BranchInst>(I); 763 764 if (BI->isUnconditional()) { 765 const BasicBlock *LLVMSucc = BI->getSuccessor(0); 766 MachineBasicBlock *MSucc = MBBMap[LLVMSucc]; 767 FastEmitBranch(MSucc, BI->getDebugLoc()); 768 return true; 769 } 770 771 // Conditional branches are not handed yet. 772 // Halt "fast" selection and bail. 773 return false; 774 } 775 776 case Instruction::Unreachable: 777 // Nothing to emit. 778 return true; 779 780 case Instruction::Alloca: 781 // FunctionLowering has the static-sized case covered. 782 if (StaticAllocaMap.count(cast<AllocaInst>(I))) 783 return true; 784 785 // Dynamic-sized alloca is not handled yet. 786 return false; 787 788 case Instruction::Call: 789 return SelectCall(I); 790 791 case Instruction::BitCast: 792 return SelectBitCast(I); 793 794 case Instruction::FPToSI: 795 return SelectCast(I, ISD::FP_TO_SINT); 796 case Instruction::ZExt: 797 return SelectCast(I, ISD::ZERO_EXTEND); 798 case Instruction::SExt: 799 return SelectCast(I, ISD::SIGN_EXTEND); 800 case Instruction::Trunc: 801 return SelectCast(I, ISD::TRUNCATE); 802 case Instruction::SIToFP: 803 return SelectCast(I, ISD::SINT_TO_FP); 804 805 case Instruction::IntToPtr: // Deliberate fall-through. 806 case Instruction::PtrToInt: { 807 EVT SrcVT = TLI.getValueType(I->getOperand(0)->getType()); 808 EVT DstVT = TLI.getValueType(I->getType()); 809 if (DstVT.bitsGT(SrcVT)) 810 return SelectCast(I, ISD::ZERO_EXTEND); 811 if (DstVT.bitsLT(SrcVT)) 812 return SelectCast(I, ISD::TRUNCATE); 813 unsigned Reg = getRegForValue(I->getOperand(0)); 814 if (Reg == 0) return false; 815 UpdateValueMap(I, Reg); 816 return true; 817 } 818 819 case Instruction::PHI: 820 llvm_unreachable("FastISel shouldn't visit PHI nodes!"); 821 822 default: 823 // Unhandled instruction. Halt "fast" selection and bail. 824 return false; 825 } 826} 827 828FastISel::FastISel(MachineFunction &mf, 829 DenseMap<const Value *, unsigned> &vm, 830 DenseMap<const BasicBlock *, MachineBasicBlock *> &bm, 831 DenseMap<const AllocaInst *, int> &am, 832 std::vector<std::pair<MachineInstr*, unsigned> > &pn 833#ifndef NDEBUG 834 , SmallSet<const Instruction *, 8> &cil 835#endif 836 ) 837 : MBB(0), 838 ValueMap(vm), 839 MBBMap(bm), 840 StaticAllocaMap(am), 841 PHINodesToUpdate(pn), 842#ifndef NDEBUG 843 CatchInfoLost(cil), 844#endif 845 MF(mf), 846 MRI(MF.getRegInfo()), 847 MFI(*MF.getFrameInfo()), 848 MCP(*MF.getConstantPool()), 849 TM(MF.getTarget()), 850 TD(*TM.getTargetData()), 851 TII(*TM.getInstrInfo()), 852 TLI(*TM.getTargetLowering()), 853 TRI(*TM.getRegisterInfo()), 854 IsBottomUp(false) { 855} 856 857FastISel::~FastISel() {} 858 859unsigned FastISel::FastEmit_(MVT, MVT, 860 unsigned) { 861 return 0; 862} 863 864unsigned FastISel::FastEmit_r(MVT, MVT, 865 unsigned, 866 unsigned /*Op0*/, bool /*Op0IsKill*/) { 867 return 0; 868} 869 870unsigned FastISel::FastEmit_rr(MVT, MVT, 871 unsigned, 872 unsigned /*Op0*/, bool /*Op0IsKill*/, 873 unsigned /*Op1*/, bool /*Op1IsKill*/) { 874 return 0; 875} 876 877unsigned FastISel::FastEmit_i(MVT, MVT, unsigned, uint64_t /*Imm*/) { 878 return 0; 879} 880 881unsigned FastISel::FastEmit_f(MVT, MVT, 882 unsigned, const ConstantFP * /*FPImm*/) { 883 return 0; 884} 885 886unsigned FastISel::FastEmit_ri(MVT, MVT, 887 unsigned, 888 unsigned /*Op0*/, bool /*Op0IsKill*/, 889 uint64_t /*Imm*/) { 890 return 0; 891} 892 893unsigned FastISel::FastEmit_rf(MVT, MVT, 894 unsigned, 895 unsigned /*Op0*/, bool /*Op0IsKill*/, 896 const ConstantFP * /*FPImm*/) { 897 return 0; 898} 899 900unsigned FastISel::FastEmit_rri(MVT, MVT, 901 unsigned, 902 unsigned /*Op0*/, bool /*Op0IsKill*/, 903 unsigned /*Op1*/, bool /*Op1IsKill*/, 904 uint64_t /*Imm*/) { 905 return 0; 906} 907 908/// FastEmit_ri_ - This method is a wrapper of FastEmit_ri. It first tries 909/// to emit an instruction with an immediate operand using FastEmit_ri. 910/// If that fails, it materializes the immediate into a register and try 911/// FastEmit_rr instead. 912unsigned FastISel::FastEmit_ri_(MVT VT, unsigned Opcode, 913 unsigned Op0, bool Op0IsKill, 914 uint64_t Imm, MVT ImmType) { 915 // First check if immediate type is legal. If not, we can't use the ri form. 916 unsigned ResultReg = FastEmit_ri(VT, VT, Opcode, Op0, Op0IsKill, Imm); 917 if (ResultReg != 0) 918 return ResultReg; 919 unsigned MaterialReg = FastEmit_i(ImmType, ImmType, ISD::Constant, Imm); 920 if (MaterialReg == 0) 921 return 0; 922 return FastEmit_rr(VT, VT, Opcode, 923 Op0, Op0IsKill, 924 MaterialReg, /*Kill=*/true); 925} 926 927/// FastEmit_rf_ - This method is a wrapper of FastEmit_ri. It first tries 928/// to emit an instruction with a floating-point immediate operand using 929/// FastEmit_rf. If that fails, it materializes the immediate into a register 930/// and try FastEmit_rr instead. 931unsigned FastISel::FastEmit_rf_(MVT VT, unsigned Opcode, 932 unsigned Op0, bool Op0IsKill, 933 const ConstantFP *FPImm, MVT ImmType) { 934 // First check if immediate type is legal. If not, we can't use the rf form. 935 unsigned ResultReg = FastEmit_rf(VT, VT, Opcode, Op0, Op0IsKill, FPImm); 936 if (ResultReg != 0) 937 return ResultReg; 938 939 // Materialize the constant in a register. 940 unsigned MaterialReg = FastEmit_f(ImmType, ImmType, ISD::ConstantFP, FPImm); 941 if (MaterialReg == 0) { 942 // If the target doesn't have a way to directly enter a floating-point 943 // value into a register, use an alternate approach. 944 // TODO: The current approach only supports floating-point constants 945 // that can be constructed by conversion from integer values. This should 946 // be replaced by code that creates a load from a constant-pool entry, 947 // which will require some target-specific work. 948 const APFloat &Flt = FPImm->getValueAPF(); 949 EVT IntVT = TLI.getPointerTy(); 950 951 uint64_t x[2]; 952 uint32_t IntBitWidth = IntVT.getSizeInBits(); 953 bool isExact; 954 (void) Flt.convertToInteger(x, IntBitWidth, /*isSigned=*/true, 955 APFloat::rmTowardZero, &isExact); 956 if (!isExact) 957 return 0; 958 APInt IntVal(IntBitWidth, 2, x); 959 960 unsigned IntegerReg = FastEmit_i(IntVT.getSimpleVT(), IntVT.getSimpleVT(), 961 ISD::Constant, IntVal.getZExtValue()); 962 if (IntegerReg == 0) 963 return 0; 964 MaterialReg = FastEmit_r(IntVT.getSimpleVT(), VT, 965 ISD::SINT_TO_FP, IntegerReg, /*Kill=*/true); 966 if (MaterialReg == 0) 967 return 0; 968 } 969 return FastEmit_rr(VT, VT, Opcode, 970 Op0, Op0IsKill, 971 MaterialReg, /*Kill=*/true); 972} 973 974unsigned FastISel::createResultReg(const TargetRegisterClass* RC) { 975 return MRI.createVirtualRegister(RC); 976} 977 978unsigned FastISel::FastEmitInst_(unsigned MachineInstOpcode, 979 const TargetRegisterClass* RC) { 980 unsigned ResultReg = createResultReg(RC); 981 const TargetInstrDesc &II = TII.get(MachineInstOpcode); 982 983 BuildMI(MBB, DL, II, ResultReg); 984 return ResultReg; 985} 986 987unsigned FastISel::FastEmitInst_r(unsigned MachineInstOpcode, 988 const TargetRegisterClass *RC, 989 unsigned Op0, bool Op0IsKill) { 990 unsigned ResultReg = createResultReg(RC); 991 const TargetInstrDesc &II = TII.get(MachineInstOpcode); 992 993 if (II.getNumDefs() >= 1) 994 BuildMI(MBB, DL, II, ResultReg).addReg(Op0, Op0IsKill * RegState::Kill); 995 else { 996 BuildMI(MBB, DL, II).addReg(Op0, Op0IsKill * RegState::Kill); 997 bool InsertedCopy = TII.copyRegToReg(*MBB, MBB->end(), ResultReg, 998 II.ImplicitDefs[0], RC, RC, DL); 999 if (!InsertedCopy) 1000 ResultReg = 0; 1001 } 1002 1003 return ResultReg; 1004} 1005 1006unsigned FastISel::FastEmitInst_rr(unsigned MachineInstOpcode, 1007 const TargetRegisterClass *RC, 1008 unsigned Op0, bool Op0IsKill, 1009 unsigned Op1, bool Op1IsKill) { 1010 unsigned ResultReg = createResultReg(RC); 1011 const TargetInstrDesc &II = TII.get(MachineInstOpcode); 1012 1013 if (II.getNumDefs() >= 1) 1014 BuildMI(MBB, DL, II, ResultReg) 1015 .addReg(Op0, Op0IsKill * RegState::Kill) 1016 .addReg(Op1, Op1IsKill * RegState::Kill); 1017 else { 1018 BuildMI(MBB, DL, II) 1019 .addReg(Op0, Op0IsKill * RegState::Kill) 1020 .addReg(Op1, Op1IsKill * RegState::Kill); 1021 bool InsertedCopy = TII.copyRegToReg(*MBB, MBB->end(), ResultReg, 1022 II.ImplicitDefs[0], RC, RC, DL); 1023 if (!InsertedCopy) 1024 ResultReg = 0; 1025 } 1026 return ResultReg; 1027} 1028 1029unsigned FastISel::FastEmitInst_ri(unsigned MachineInstOpcode, 1030 const TargetRegisterClass *RC, 1031 unsigned Op0, bool Op0IsKill, 1032 uint64_t Imm) { 1033 unsigned ResultReg = createResultReg(RC); 1034 const TargetInstrDesc &II = TII.get(MachineInstOpcode); 1035 1036 if (II.getNumDefs() >= 1) 1037 BuildMI(MBB, DL, II, ResultReg) 1038 .addReg(Op0, Op0IsKill * RegState::Kill) 1039 .addImm(Imm); 1040 else { 1041 BuildMI(MBB, DL, II) 1042 .addReg(Op0, Op0IsKill * RegState::Kill) 1043 .addImm(Imm); 1044 bool InsertedCopy = TII.copyRegToReg(*MBB, MBB->end(), ResultReg, 1045 II.ImplicitDefs[0], RC, RC, DL); 1046 if (!InsertedCopy) 1047 ResultReg = 0; 1048 } 1049 return ResultReg; 1050} 1051 1052unsigned FastISel::FastEmitInst_rf(unsigned MachineInstOpcode, 1053 const TargetRegisterClass *RC, 1054 unsigned Op0, bool Op0IsKill, 1055 const ConstantFP *FPImm) { 1056 unsigned ResultReg = createResultReg(RC); 1057 const TargetInstrDesc &II = TII.get(MachineInstOpcode); 1058 1059 if (II.getNumDefs() >= 1) 1060 BuildMI(MBB, DL, II, ResultReg) 1061 .addReg(Op0, Op0IsKill * RegState::Kill) 1062 .addFPImm(FPImm); 1063 else { 1064 BuildMI(MBB, DL, II) 1065 .addReg(Op0, Op0IsKill * RegState::Kill) 1066 .addFPImm(FPImm); 1067 bool InsertedCopy = TII.copyRegToReg(*MBB, MBB->end(), ResultReg, 1068 II.ImplicitDefs[0], RC, RC, DL); 1069 if (!InsertedCopy) 1070 ResultReg = 0; 1071 } 1072 return ResultReg; 1073} 1074 1075unsigned FastISel::FastEmitInst_rri(unsigned MachineInstOpcode, 1076 const TargetRegisterClass *RC, 1077 unsigned Op0, bool Op0IsKill, 1078 unsigned Op1, bool Op1IsKill, 1079 uint64_t Imm) { 1080 unsigned ResultReg = createResultReg(RC); 1081 const TargetInstrDesc &II = TII.get(MachineInstOpcode); 1082 1083 if (II.getNumDefs() >= 1) 1084 BuildMI(MBB, DL, II, ResultReg) 1085 .addReg(Op0, Op0IsKill * RegState::Kill) 1086 .addReg(Op1, Op1IsKill * RegState::Kill) 1087 .addImm(Imm); 1088 else { 1089 BuildMI(MBB, DL, II) 1090 .addReg(Op0, Op0IsKill * RegState::Kill) 1091 .addReg(Op1, Op1IsKill * RegState::Kill) 1092 .addImm(Imm); 1093 bool InsertedCopy = TII.copyRegToReg(*MBB, MBB->end(), ResultReg, 1094 II.ImplicitDefs[0], RC, RC, DL); 1095 if (!InsertedCopy) 1096 ResultReg = 0; 1097 } 1098 return ResultReg; 1099} 1100 1101unsigned FastISel::FastEmitInst_i(unsigned MachineInstOpcode, 1102 const TargetRegisterClass *RC, 1103 uint64_t Imm) { 1104 unsigned ResultReg = createResultReg(RC); 1105 const TargetInstrDesc &II = TII.get(MachineInstOpcode); 1106 1107 if (II.getNumDefs() >= 1) 1108 BuildMI(MBB, DL, II, ResultReg).addImm(Imm); 1109 else { 1110 BuildMI(MBB, DL, II).addImm(Imm); 1111 bool InsertedCopy = TII.copyRegToReg(*MBB, MBB->end(), ResultReg, 1112 II.ImplicitDefs[0], RC, RC, DL); 1113 if (!InsertedCopy) 1114 ResultReg = 0; 1115 } 1116 return ResultReg; 1117} 1118 1119unsigned FastISel::FastEmitInst_extractsubreg(MVT RetVT, 1120 unsigned Op0, bool Op0IsKill, 1121 uint32_t Idx) { 1122 const TargetRegisterClass* RC = MRI.getRegClass(Op0); 1123 1124 unsigned ResultReg = createResultReg(TLI.getRegClassFor(RetVT)); 1125 const TargetInstrDesc &II = TII.get(TargetOpcode::EXTRACT_SUBREG); 1126 1127 if (II.getNumDefs() >= 1) 1128 BuildMI(MBB, DL, II, ResultReg) 1129 .addReg(Op0, Op0IsKill * RegState::Kill) 1130 .addImm(Idx); 1131 else { 1132 BuildMI(MBB, DL, II) 1133 .addReg(Op0, Op0IsKill * RegState::Kill) 1134 .addImm(Idx); 1135 bool InsertedCopy = TII.copyRegToReg(*MBB, MBB->end(), ResultReg, 1136 II.ImplicitDefs[0], RC, RC, DL); 1137 if (!InsertedCopy) 1138 ResultReg = 0; 1139 } 1140 return ResultReg; 1141} 1142 1143/// FastEmitZExtFromI1 - Emit MachineInstrs to compute the value of Op 1144/// with all but the least significant bit set to zero. 1145unsigned FastISel::FastEmitZExtFromI1(MVT VT, unsigned Op0, bool Op0IsKill) { 1146 return FastEmit_ri(VT, VT, ISD::AND, Op0, Op0IsKill, 1); 1147} 1148 1149/// HandlePHINodesInSuccessorBlocks - Handle PHI nodes in successor blocks. 1150/// Emit code to ensure constants are copied into registers when needed. 1151/// Remember the virtual registers that need to be added to the Machine PHI 1152/// nodes as input. We cannot just directly add them, because expansion 1153/// might result in multiple MBB's for one BB. As such, the start of the 1154/// BB might correspond to a different MBB than the end. 1155bool FastISel::HandlePHINodesInSuccessorBlocks(const BasicBlock *LLVMBB) { 1156 const TerminatorInst *TI = LLVMBB->getTerminator(); 1157 1158 SmallPtrSet<MachineBasicBlock *, 4> SuccsHandled; 1159 unsigned OrigNumPHINodesToUpdate = PHINodesToUpdate.size(); 1160 1161 // Check successor nodes' PHI nodes that expect a constant to be available 1162 // from this block. 1163 for (unsigned succ = 0, e = TI->getNumSuccessors(); succ != e; ++succ) { 1164 const BasicBlock *SuccBB = TI->getSuccessor(succ); 1165 if (!isa<PHINode>(SuccBB->begin())) continue; 1166 MachineBasicBlock *SuccMBB = MBBMap[SuccBB]; 1167 1168 // If this terminator has multiple identical successors (common for 1169 // switches), only handle each succ once. 1170 if (!SuccsHandled.insert(SuccMBB)) continue; 1171 1172 MachineBasicBlock::iterator MBBI = SuccMBB->begin(); 1173 1174 // At this point we know that there is a 1-1 correspondence between LLVM PHI 1175 // nodes and Machine PHI nodes, but the incoming operands have not been 1176 // emitted yet. 1177 for (BasicBlock::const_iterator I = SuccBB->begin(); 1178 const PHINode *PN = dyn_cast<PHINode>(I); ++I) { 1179 1180 // Ignore dead phi's. 1181 if (PN->use_empty()) continue; 1182 1183 // Only handle legal types. Two interesting things to note here. First, 1184 // by bailing out early, we may leave behind some dead instructions, 1185 // since SelectionDAG's HandlePHINodesInSuccessorBlocks will insert its 1186 // own moves. Second, this check is necessary becuase FastISel doesn't 1187 // use CreateRegForValue to create registers, so it always creates 1188 // exactly one register for each non-void instruction. 1189 EVT VT = TLI.getValueType(PN->getType(), /*AllowUnknown=*/true); 1190 if (VT == MVT::Other || !TLI.isTypeLegal(VT)) { 1191 // Promote MVT::i1. 1192 if (VT == MVT::i1) 1193 VT = TLI.getTypeToTransformTo(LLVMBB->getContext(), VT); 1194 else { 1195 PHINodesToUpdate.resize(OrigNumPHINodesToUpdate); 1196 return false; 1197 } 1198 } 1199 1200 const Value *PHIOp = PN->getIncomingValueForBlock(LLVMBB); 1201 1202 // Set the DebugLoc for the copy. Prefer the location of the operand 1203 // if there is one; use the location of the PHI otherwise. 1204 DL = PN->getDebugLoc(); 1205 if (const Instruction *Inst = dyn_cast<Instruction>(PHIOp)) 1206 DL = Inst->getDebugLoc(); 1207 1208 unsigned Reg = getRegForValue(PHIOp); 1209 if (Reg == 0) { 1210 PHINodesToUpdate.resize(OrigNumPHINodesToUpdate); 1211 return false; 1212 } 1213 PHINodesToUpdate.push_back(std::make_pair(MBBI++, Reg)); 1214 DL = DebugLoc(); 1215 } 1216 } 1217 1218 return true; 1219} 1220