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 #define DEBUG_TYPE "isel" 43 #include "llvm/Function.h" 44 #include "llvm/GlobalVariable.h" 45 #include "llvm/Instructions.h" 46 #include "llvm/IntrinsicInst.h" 47 #include "llvm/Operator.h" 48 #include "llvm/CodeGen/Analysis.h" 49 #include "llvm/CodeGen/FastISel.h" 50 #include "llvm/CodeGen/FunctionLoweringInfo.h" 51 #include "llvm/CodeGen/MachineInstrBuilder.h" 52 #include "llvm/CodeGen/MachineModuleInfo.h" 53 #include "llvm/CodeGen/MachineRegisterInfo.h" 54 #include "llvm/Analysis/DebugInfo.h" 55 #include "llvm/Analysis/Loads.h" 56 #include "llvm/Target/TargetData.h" 57 #include "llvm/Target/TargetInstrInfo.h" 58 #include "llvm/Target/TargetLowering.h" 59 #include "llvm/Target/TargetMachine.h" 60 #include "llvm/Support/ErrorHandling.h" 61 #include "llvm/Support/Debug.h" 62 #include "llvm/ADT/Statistic.h" 63 using namespace llvm; 64 65 STATISTIC(NumFastIselSuccessIndependent, "Number of insts selected by " 66 "target-independent selector"); 67 STATISTIC(NumFastIselSuccessTarget, "Number of insts selected by " 68 "target-specific selector"); 69 STATISTIC(NumFastIselDead, "Number of dead insts removed on failure"); 70 71 /// startNewBlock - Set the current block to which generated machine 72 /// instructions will be appended, and clear the local CSE map. 73 /// 74 void FastISel::startNewBlock() { 75 LocalValueMap.clear(); 76 77 EmitStartPt = 0; 78 79 // Advance the emit start point past any EH_LABEL instructions. 80 MachineBasicBlock::iterator 81 I = FuncInfo.MBB->begin(), E = FuncInfo.MBB->end(); 82 while (I != E && I->getOpcode() == TargetOpcode::EH_LABEL) { 83 EmitStartPt = I; 84 ++I; 85 } 86 LastLocalValue = EmitStartPt; 87 } 88 89 void FastISel::flushLocalValueMap() { 90 LocalValueMap.clear(); 91 LastLocalValue = EmitStartPt; 92 recomputeInsertPt(); 93 } 94 95 bool FastISel::hasTrivialKill(const Value *V) const { 96 // Don't consider constants or arguments to have trivial kills. 97 const Instruction *I = dyn_cast<Instruction>(V); 98 if (!I) 99 return false; 100 101 // No-op casts are trivially coalesced by fast-isel. 102 if (const CastInst *Cast = dyn_cast<CastInst>(I)) 103 if (Cast->isNoopCast(TD.getIntPtrType(Cast->getContext())) && 104 !hasTrivialKill(Cast->getOperand(0))) 105 return false; 106 107 // GEPs with all zero indices are trivially coalesced by fast-isel. 108 if (const GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(I)) 109 if (GEP->hasAllZeroIndices() && !hasTrivialKill(GEP->getOperand(0))) 110 return false; 111 112 // Only instructions with a single use in the same basic block are considered 113 // to have trivial kills. 114 return I->hasOneUse() && 115 !(I->getOpcode() == Instruction::BitCast || 116 I->getOpcode() == Instruction::PtrToInt || 117 I->getOpcode() == Instruction::IntToPtr) && 118 cast<Instruction>(*I->use_begin())->getParent() == I->getParent(); 119 } 120 121 unsigned FastISel::getRegForValue(const Value *V) { 122 EVT RealVT = TLI.getValueType(V->getType(), /*AllowUnknown=*/true); 123 // Don't handle non-simple values in FastISel. 124 if (!RealVT.isSimple()) 125 return 0; 126 127 // Ignore illegal types. We must do this before looking up the value 128 // in ValueMap because Arguments are given virtual registers regardless 129 // of whether FastISel can handle them. 130 MVT VT = RealVT.getSimpleVT(); 131 if (!TLI.isTypeLegal(VT)) { 132 // Handle integer promotions, though, because they're common and easy. 133 if (VT == MVT::i1 || VT == MVT::i8 || VT == MVT::i16) 134 VT = TLI.getTypeToTransformTo(V->getContext(), VT).getSimpleVT(); 135 else 136 return 0; 137 } 138 139 // Look up the value to see if we already have a register for it. 140 unsigned Reg = lookUpRegForValue(V); 141 if (Reg != 0) 142 return Reg; 143 144 // In bottom-up mode, just create the virtual register which will be used 145 // to hold the value. It will be materialized later. 146 if (isa<Instruction>(V) && 147 (!isa<AllocaInst>(V) || 148 !FuncInfo.StaticAllocaMap.count(cast<AllocaInst>(V)))) 149 return FuncInfo.InitializeRegForValue(V); 150 151 SavePoint SaveInsertPt = enterLocalValueArea(); 152 153 // Materialize the value in a register. Emit any instructions in the 154 // local value area. 155 Reg = materializeRegForValue(V, VT); 156 157 leaveLocalValueArea(SaveInsertPt); 158 159 return Reg; 160 } 161 162 /// materializeRegForValue - Helper for getRegForValue. This function is 163 /// called when the value isn't already available in a register and must 164 /// be materialized with new instructions. 165 unsigned FastISel::materializeRegForValue(const Value *V, MVT VT) { 166 unsigned Reg = 0; 167 168 if (const ConstantInt *CI = dyn_cast<ConstantInt>(V)) { 169 if (CI->getValue().getActiveBits() <= 64) 170 Reg = FastEmit_i(VT, VT, ISD::Constant, CI->getZExtValue()); 171 } else if (isa<AllocaInst>(V)) { 172 Reg = TargetMaterializeAlloca(cast<AllocaInst>(V)); 173 } else if (isa<ConstantPointerNull>(V)) { 174 // Translate this as an integer zero so that it can be 175 // local-CSE'd with actual integer zeros. 176 Reg = 177 getRegForValue(Constant::getNullValue(TD.getIntPtrType(V->getContext()))); 178 } else if (const ConstantFP *CF = dyn_cast<ConstantFP>(V)) { 179 if (CF->isNullValue()) { 180 Reg = TargetMaterializeFloatZero(CF); 181 } else { 182 // Try to emit the constant directly. 183 Reg = FastEmit_f(VT, VT, ISD::ConstantFP, CF); 184 } 185 186 if (!Reg) { 187 // Try to emit the constant by using an integer constant with a cast. 188 const APFloat &Flt = CF->getValueAPF(); 189 EVT IntVT = TLI.getPointerTy(); 190 191 uint64_t x[2]; 192 uint32_t IntBitWidth = IntVT.getSizeInBits(); 193 bool isExact; 194 (void) Flt.convertToInteger(x, IntBitWidth, /*isSigned=*/true, 195 APFloat::rmTowardZero, &isExact); 196 if (isExact) { 197 APInt IntVal(IntBitWidth, x); 198 199 unsigned IntegerReg = 200 getRegForValue(ConstantInt::get(V->getContext(), IntVal)); 201 if (IntegerReg != 0) 202 Reg = FastEmit_r(IntVT.getSimpleVT(), VT, ISD::SINT_TO_FP, 203 IntegerReg, /*Kill=*/false); 204 } 205 } 206 } else if (const Operator *Op = dyn_cast<Operator>(V)) { 207 if (!SelectOperator(Op, Op->getOpcode())) 208 if (!isa<Instruction>(Op) || 209 !TargetSelectInstruction(cast<Instruction>(Op))) 210 return 0; 211 Reg = lookUpRegForValue(Op); 212 } else if (isa<UndefValue>(V)) { 213 Reg = createResultReg(TLI.getRegClassFor(VT)); 214 BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, 215 TII.get(TargetOpcode::IMPLICIT_DEF), Reg); 216 } 217 218 // If target-independent code couldn't handle the value, give target-specific 219 // code a try. 220 if (!Reg && isa<Constant>(V)) 221 Reg = TargetMaterializeConstant(cast<Constant>(V)); 222 223 // Don't cache constant materializations in the general ValueMap. 224 // To do so would require tracking what uses they dominate. 225 if (Reg != 0) { 226 LocalValueMap[V] = Reg; 227 LastLocalValue = MRI.getVRegDef(Reg); 228 } 229 return Reg; 230 } 231 232 unsigned FastISel::lookUpRegForValue(const Value *V) { 233 // Look up the value to see if we already have a register for it. We 234 // cache values defined by Instructions across blocks, and other values 235 // only locally. This is because Instructions already have the SSA 236 // def-dominates-use requirement enforced. 237 DenseMap<const Value *, unsigned>::iterator I = FuncInfo.ValueMap.find(V); 238 if (I != FuncInfo.ValueMap.end()) 239 return I->second; 240 return LocalValueMap[V]; 241 } 242 243 /// UpdateValueMap - Update the value map to include the new mapping for this 244 /// instruction, or insert an extra copy to get the result in a previous 245 /// determined register. 246 /// NOTE: This is only necessary because we might select a block that uses 247 /// a value before we select the block that defines the value. It might be 248 /// possible to fix this by selecting blocks in reverse postorder. 249 void FastISel::UpdateValueMap(const Value *I, unsigned Reg, unsigned NumRegs) { 250 if (!isa<Instruction>(I)) { 251 LocalValueMap[I] = Reg; 252 return; 253 } 254 255 unsigned &AssignedReg = FuncInfo.ValueMap[I]; 256 if (AssignedReg == 0) 257 // Use the new register. 258 AssignedReg = Reg; 259 else if (Reg != AssignedReg) { 260 // Arrange for uses of AssignedReg to be replaced by uses of Reg. 261 for (unsigned i = 0; i < NumRegs; i++) 262 FuncInfo.RegFixups[AssignedReg+i] = Reg+i; 263 264 AssignedReg = Reg; 265 } 266 } 267 268 std::pair<unsigned, bool> FastISel::getRegForGEPIndex(const Value *Idx) { 269 unsigned IdxN = getRegForValue(Idx); 270 if (IdxN == 0) 271 // Unhandled operand. Halt "fast" selection and bail. 272 return std::pair<unsigned, bool>(0, false); 273 274 bool IdxNIsKill = hasTrivialKill(Idx); 275 276 // If the index is smaller or larger than intptr_t, truncate or extend it. 277 MVT PtrVT = TLI.getPointerTy(); 278 EVT IdxVT = EVT::getEVT(Idx->getType(), /*HandleUnknown=*/false); 279 if (IdxVT.bitsLT(PtrVT)) { 280 IdxN = FastEmit_r(IdxVT.getSimpleVT(), PtrVT, ISD::SIGN_EXTEND, 281 IdxN, IdxNIsKill); 282 IdxNIsKill = true; 283 } 284 else if (IdxVT.bitsGT(PtrVT)) { 285 IdxN = FastEmit_r(IdxVT.getSimpleVT(), PtrVT, ISD::TRUNCATE, 286 IdxN, IdxNIsKill); 287 IdxNIsKill = true; 288 } 289 return std::pair<unsigned, bool>(IdxN, IdxNIsKill); 290 } 291 292 void FastISel::recomputeInsertPt() { 293 if (getLastLocalValue()) { 294 FuncInfo.InsertPt = getLastLocalValue(); 295 FuncInfo.MBB = FuncInfo.InsertPt->getParent(); 296 ++FuncInfo.InsertPt; 297 } else 298 FuncInfo.InsertPt = FuncInfo.MBB->getFirstNonPHI(); 299 300 // Now skip past any EH_LABELs, which must remain at the beginning. 301 while (FuncInfo.InsertPt != FuncInfo.MBB->end() && 302 FuncInfo.InsertPt->getOpcode() == TargetOpcode::EH_LABEL) 303 ++FuncInfo.InsertPt; 304 } 305 306 void FastISel::removeDeadCode(MachineBasicBlock::iterator I, 307 MachineBasicBlock::iterator E) { 308 assert (I && E && std::distance(I, E) > 0 && "Invalid iterator!"); 309 while (I != E) { 310 MachineInstr *Dead = &*I; 311 ++I; 312 Dead->eraseFromParent(); 313 ++NumFastIselDead; 314 } 315 recomputeInsertPt(); 316 } 317 318 FastISel::SavePoint FastISel::enterLocalValueArea() { 319 MachineBasicBlock::iterator OldInsertPt = FuncInfo.InsertPt; 320 DebugLoc OldDL = DL; 321 recomputeInsertPt(); 322 DL = DebugLoc(); 323 SavePoint SP = { OldInsertPt, OldDL }; 324 return SP; 325 } 326 327 void FastISel::leaveLocalValueArea(SavePoint OldInsertPt) { 328 if (FuncInfo.InsertPt != FuncInfo.MBB->begin()) 329 LastLocalValue = llvm::prior(FuncInfo.InsertPt); 330 331 // Restore the previous insert position. 332 FuncInfo.InsertPt = OldInsertPt.InsertPt; 333 DL = OldInsertPt.DL; 334 } 335 336 /// SelectBinaryOp - Select and emit code for a binary operator instruction, 337 /// which has an opcode which directly corresponds to the given ISD opcode. 338 /// 339 bool FastISel::SelectBinaryOp(const User *I, unsigned ISDOpcode) { 340 EVT VT = EVT::getEVT(I->getType(), /*HandleUnknown=*/true); 341 if (VT == MVT::Other || !VT.isSimple()) 342 // Unhandled type. Halt "fast" selection and bail. 343 return false; 344 345 // We only handle legal types. For example, on x86-32 the instruction 346 // selector contains all of the 64-bit instructions from x86-64, 347 // under the assumption that i64 won't be used if the target doesn't 348 // support it. 349 if (!TLI.isTypeLegal(VT)) { 350 // MVT::i1 is special. Allow AND, OR, or XOR because they 351 // don't require additional zeroing, which makes them easy. 352 if (VT == MVT::i1 && 353 (ISDOpcode == ISD::AND || ISDOpcode == ISD::OR || 354 ISDOpcode == ISD::XOR)) 355 VT = TLI.getTypeToTransformTo(I->getContext(), VT); 356 else 357 return false; 358 } 359 360 // Check if the first operand is a constant, and handle it as "ri". At -O0, 361 // we don't have anything that canonicalizes operand order. 362 if (ConstantInt *CI = dyn_cast<ConstantInt>(I->getOperand(0))) 363 if (isa<Instruction>(I) && cast<Instruction>(I)->isCommutative()) { 364 unsigned Op1 = getRegForValue(I->getOperand(1)); 365 if (Op1 == 0) return false; 366 367 bool Op1IsKill = hasTrivialKill(I->getOperand(1)); 368 369 unsigned ResultReg = FastEmit_ri_(VT.getSimpleVT(), ISDOpcode, Op1, 370 Op1IsKill, CI->getZExtValue(), 371 VT.getSimpleVT()); 372 if (ResultReg == 0) return false; 373 374 // We successfully emitted code for the given LLVM Instruction. 375 UpdateValueMap(I, ResultReg); 376 return true; 377 } 378 379 380 unsigned Op0 = getRegForValue(I->getOperand(0)); 381 if (Op0 == 0) // Unhandled operand. Halt "fast" selection and bail. 382 return false; 383 384 bool Op0IsKill = hasTrivialKill(I->getOperand(0)); 385 386 // Check if the second operand is a constant and handle it appropriately. 387 if (ConstantInt *CI = dyn_cast<ConstantInt>(I->getOperand(1))) { 388 uint64_t Imm = CI->getZExtValue(); 389 390 // Transform "sdiv exact X, 8" -> "sra X, 3". 391 if (ISDOpcode == ISD::SDIV && isa<BinaryOperator>(I) && 392 cast<BinaryOperator>(I)->isExact() && 393 isPowerOf2_64(Imm)) { 394 Imm = Log2_64(Imm); 395 ISDOpcode = ISD::SRA; 396 } 397 398 // Transform "urem x, pow2" -> "and x, pow2-1". 399 if (ISDOpcode == ISD::UREM && isa<BinaryOperator>(I) && 400 isPowerOf2_64(Imm)) { 401 --Imm; 402 ISDOpcode = ISD::AND; 403 } 404 405 unsigned ResultReg = FastEmit_ri_(VT.getSimpleVT(), ISDOpcode, Op0, 406 Op0IsKill, Imm, VT.getSimpleVT()); 407 if (ResultReg == 0) return false; 408 409 // We successfully emitted code for the given LLVM Instruction. 410 UpdateValueMap(I, ResultReg); 411 return true; 412 } 413 414 // Check if the second operand is a constant float. 415 if (ConstantFP *CF = dyn_cast<ConstantFP>(I->getOperand(1))) { 416 unsigned ResultReg = FastEmit_rf(VT.getSimpleVT(), VT.getSimpleVT(), 417 ISDOpcode, Op0, Op0IsKill, CF); 418 if (ResultReg != 0) { 419 // We successfully emitted code for the given LLVM Instruction. 420 UpdateValueMap(I, ResultReg); 421 return true; 422 } 423 } 424 425 unsigned Op1 = getRegForValue(I->getOperand(1)); 426 if (Op1 == 0) 427 // Unhandled operand. Halt "fast" selection and bail. 428 return false; 429 430 bool Op1IsKill = hasTrivialKill(I->getOperand(1)); 431 432 // Now we have both operands in registers. Emit the instruction. 433 unsigned ResultReg = FastEmit_rr(VT.getSimpleVT(), VT.getSimpleVT(), 434 ISDOpcode, 435 Op0, Op0IsKill, 436 Op1, Op1IsKill); 437 if (ResultReg == 0) 438 // Target-specific code wasn't able to find a machine opcode for 439 // the given ISD opcode and type. Halt "fast" selection and bail. 440 return false; 441 442 // We successfully emitted code for the given LLVM Instruction. 443 UpdateValueMap(I, ResultReg); 444 return true; 445 } 446 447 bool FastISel::SelectGetElementPtr(const User *I) { 448 unsigned N = getRegForValue(I->getOperand(0)); 449 if (N == 0) 450 // Unhandled operand. Halt "fast" selection and bail. 451 return false; 452 453 bool NIsKill = hasTrivialKill(I->getOperand(0)); 454 455 // Keep a running tab of the total offset to coalesce multiple N = N + Offset 456 // into a single N = N + TotalOffset. 457 uint64_t TotalOffs = 0; 458 // FIXME: What's a good SWAG number for MaxOffs? 459 uint64_t MaxOffs = 2048; 460 Type *Ty = I->getOperand(0)->getType(); 461 MVT VT = TLI.getPointerTy(); 462 for (GetElementPtrInst::const_op_iterator OI = I->op_begin()+1, 463 E = I->op_end(); OI != E; ++OI) { 464 const Value *Idx = *OI; 465 if (StructType *StTy = dyn_cast<StructType>(Ty)) { 466 unsigned Field = cast<ConstantInt>(Idx)->getZExtValue(); 467 if (Field) { 468 // N = N + Offset 469 TotalOffs += TD.getStructLayout(StTy)->getElementOffset(Field); 470 if (TotalOffs >= MaxOffs) { 471 N = FastEmit_ri_(VT, ISD::ADD, N, NIsKill, TotalOffs, VT); 472 if (N == 0) 473 // Unhandled operand. Halt "fast" selection and bail. 474 return false; 475 NIsKill = true; 476 TotalOffs = 0; 477 } 478 } 479 Ty = StTy->getElementType(Field); 480 } else { 481 Ty = cast<SequentialType>(Ty)->getElementType(); 482 483 // If this is a constant subscript, handle it quickly. 484 if (const ConstantInt *CI = dyn_cast<ConstantInt>(Idx)) { 485 if (CI->isZero()) continue; 486 // N = N + Offset 487 TotalOffs += 488 TD.getTypeAllocSize(Ty)*cast<ConstantInt>(CI)->getSExtValue(); 489 if (TotalOffs >= MaxOffs) { 490 N = FastEmit_ri_(VT, ISD::ADD, N, NIsKill, TotalOffs, VT); 491 if (N == 0) 492 // Unhandled operand. Halt "fast" selection and bail. 493 return false; 494 NIsKill = true; 495 TotalOffs = 0; 496 } 497 continue; 498 } 499 if (TotalOffs) { 500 N = FastEmit_ri_(VT, ISD::ADD, N, NIsKill, TotalOffs, VT); 501 if (N == 0) 502 // Unhandled operand. Halt "fast" selection and bail. 503 return false; 504 NIsKill = true; 505 TotalOffs = 0; 506 } 507 508 // N = N + Idx * ElementSize; 509 uint64_t ElementSize = TD.getTypeAllocSize(Ty); 510 std::pair<unsigned, bool> Pair = getRegForGEPIndex(Idx); 511 unsigned IdxN = Pair.first; 512 bool IdxNIsKill = Pair.second; 513 if (IdxN == 0) 514 // Unhandled operand. Halt "fast" selection and bail. 515 return false; 516 517 if (ElementSize != 1) { 518 IdxN = FastEmit_ri_(VT, ISD::MUL, IdxN, IdxNIsKill, ElementSize, VT); 519 if (IdxN == 0) 520 // Unhandled operand. Halt "fast" selection and bail. 521 return false; 522 IdxNIsKill = true; 523 } 524 N = FastEmit_rr(VT, VT, ISD::ADD, N, NIsKill, IdxN, IdxNIsKill); 525 if (N == 0) 526 // Unhandled operand. Halt "fast" selection and bail. 527 return false; 528 } 529 } 530 if (TotalOffs) { 531 N = FastEmit_ri_(VT, ISD::ADD, N, NIsKill, TotalOffs, VT); 532 if (N == 0) 533 // Unhandled operand. Halt "fast" selection and bail. 534 return false; 535 } 536 537 // We successfully emitted code for the given LLVM Instruction. 538 UpdateValueMap(I, N); 539 return true; 540 } 541 542 bool FastISel::SelectCall(const User *I) { 543 const CallInst *Call = cast<CallInst>(I); 544 545 // Handle simple inline asms. 546 if (const InlineAsm *IA = dyn_cast<InlineAsm>(Call->getCalledValue())) { 547 // Don't attempt to handle constraints. 548 if (!IA->getConstraintString().empty()) 549 return false; 550 551 unsigned ExtraInfo = 0; 552 if (IA->hasSideEffects()) 553 ExtraInfo |= InlineAsm::Extra_HasSideEffects; 554 if (IA->isAlignStack()) 555 ExtraInfo |= InlineAsm::Extra_IsAlignStack; 556 557 BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, 558 TII.get(TargetOpcode::INLINEASM)) 559 .addExternalSymbol(IA->getAsmString().c_str()) 560 .addImm(ExtraInfo); 561 return true; 562 } 563 564 MachineModuleInfo &MMI = FuncInfo.MF->getMMI(); 565 ComputeUsesVAFloatArgument(*Call, &MMI); 566 567 const Function *F = Call->getCalledFunction(); 568 if (!F) return false; 569 570 // Handle selected intrinsic function calls. 571 switch (F->getIntrinsicID()) { 572 default: break; 573 // At -O0 we don't care about the lifetime intrinsics. 574 case Intrinsic::lifetime_start: 575 case Intrinsic::lifetime_end: 576 return true; 577 case Intrinsic::dbg_declare: { 578 const DbgDeclareInst *DI = cast<DbgDeclareInst>(Call); 579 if (!DIVariable(DI->getVariable()).Verify() || 580 !FuncInfo.MF->getMMI().hasDebugInfo()) { 581 DEBUG(dbgs() << "Dropping debug info for " << *DI << "\n"); 582 return true; 583 } 584 585 const Value *Address = DI->getAddress(); 586 if (!Address || isa<UndefValue>(Address)) { 587 DEBUG(dbgs() << "Dropping debug info for " << *DI << "\n"); 588 return true; 589 } 590 591 unsigned Reg = 0; 592 unsigned Offset = 0; 593 if (const Argument *Arg = dyn_cast<Argument>(Address)) { 594 // Some arguments' frame index is recorded during argument lowering. 595 Offset = FuncInfo.getArgumentFrameIndex(Arg); 596 if (Offset) 597 Reg = TRI.getFrameRegister(*FuncInfo.MF); 598 } 599 if (!Reg) 600 Reg = lookUpRegForValue(Address); 601 602 // If we have a VLA that has a "use" in a metadata node that's then used 603 // here but it has no other uses, then we have a problem. E.g., 604 // 605 // int foo (const int *x) { 606 // char a[*x]; 607 // return 0; 608 // } 609 // 610 // If we assign 'a' a vreg and fast isel later on has to use the selection 611 // DAG isel, it will want to copy the value to the vreg. However, there are 612 // no uses, which goes counter to what selection DAG isel expects. 613 if (!Reg && !Address->use_empty() && isa<Instruction>(Address) && 614 (!isa<AllocaInst>(Address) || 615 !FuncInfo.StaticAllocaMap.count(cast<AllocaInst>(Address)))) 616 Reg = FuncInfo.InitializeRegForValue(Address); 617 618 if (Reg) 619 BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, 620 TII.get(TargetOpcode::DBG_VALUE)) 621 .addReg(Reg, RegState::Debug).addImm(Offset) 622 .addMetadata(DI->getVariable()); 623 else 624 // We can't yet handle anything else here because it would require 625 // generating code, thus altering codegen because of debug info. 626 DEBUG(dbgs() << "Dropping debug info for " << DI); 627 return true; 628 } 629 case Intrinsic::dbg_value: { 630 // This form of DBG_VALUE is target-independent. 631 const DbgValueInst *DI = cast<DbgValueInst>(Call); 632 const MCInstrDesc &II = TII.get(TargetOpcode::DBG_VALUE); 633 const Value *V = DI->getValue(); 634 if (!V) { 635 // Currently the optimizer can produce this; insert an undef to 636 // help debugging. Probably the optimizer should not do this. 637 BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, II) 638 .addReg(0U).addImm(DI->getOffset()) 639 .addMetadata(DI->getVariable()); 640 } else if (const ConstantInt *CI = dyn_cast<ConstantInt>(V)) { 641 if (CI->getBitWidth() > 64) 642 BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, II) 643 .addCImm(CI).addImm(DI->getOffset()) 644 .addMetadata(DI->getVariable()); 645 else 646 BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, II) 647 .addImm(CI->getZExtValue()).addImm(DI->getOffset()) 648 .addMetadata(DI->getVariable()); 649 } else if (const ConstantFP *CF = dyn_cast<ConstantFP>(V)) { 650 BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, II) 651 .addFPImm(CF).addImm(DI->getOffset()) 652 .addMetadata(DI->getVariable()); 653 } else if (unsigned Reg = lookUpRegForValue(V)) { 654 BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, II) 655 .addReg(Reg, RegState::Debug).addImm(DI->getOffset()) 656 .addMetadata(DI->getVariable()); 657 } else { 658 // We can't yet handle anything else here because it would require 659 // generating code, thus altering codegen because of debug info. 660 DEBUG(dbgs() << "Dropping debug info for " << DI); 661 } 662 return true; 663 } 664 case Intrinsic::objectsize: { 665 ConstantInt *CI = cast<ConstantInt>(Call->getArgOperand(1)); 666 unsigned long long Res = CI->isZero() ? -1ULL : 0; 667 Constant *ResCI = ConstantInt::get(Call->getType(), Res); 668 unsigned ResultReg = getRegForValue(ResCI); 669 if (ResultReg == 0) 670 return false; 671 UpdateValueMap(Call, ResultReg); 672 return true; 673 } 674 } 675 676 // Usually, it does not make sense to initialize a value, 677 // make an unrelated function call and use the value, because 678 // it tends to be spilled on the stack. So, we move the pointer 679 // to the last local value to the beginning of the block, so that 680 // all the values which have already been materialized, 681 // appear after the call. It also makes sense to skip intrinsics 682 // since they tend to be inlined. 683 if (!isa<IntrinsicInst>(F)) 684 flushLocalValueMap(); 685 686 // An arbitrary call. Bail. 687 return false; 688 } 689 690 bool FastISel::SelectCast(const User *I, unsigned Opcode) { 691 EVT SrcVT = TLI.getValueType(I->getOperand(0)->getType()); 692 EVT DstVT = TLI.getValueType(I->getType()); 693 694 if (SrcVT == MVT::Other || !SrcVT.isSimple() || 695 DstVT == MVT::Other || !DstVT.isSimple()) 696 // Unhandled type. Halt "fast" selection and bail. 697 return false; 698 699 // Check if the destination type is legal. 700 if (!TLI.isTypeLegal(DstVT)) 701 return false; 702 703 // Check if the source operand is legal. 704 if (!TLI.isTypeLegal(SrcVT)) 705 return false; 706 707 unsigned InputReg = getRegForValue(I->getOperand(0)); 708 if (!InputReg) 709 // Unhandled operand. Halt "fast" selection and bail. 710 return false; 711 712 bool InputRegIsKill = hasTrivialKill(I->getOperand(0)); 713 714 unsigned ResultReg = FastEmit_r(SrcVT.getSimpleVT(), 715 DstVT.getSimpleVT(), 716 Opcode, 717 InputReg, InputRegIsKill); 718 if (!ResultReg) 719 return false; 720 721 UpdateValueMap(I, ResultReg); 722 return true; 723 } 724 725 bool FastISel::SelectBitCast(const User *I) { 726 // If the bitcast doesn't change the type, just use the operand value. 727 if (I->getType() == I->getOperand(0)->getType()) { 728 unsigned Reg = getRegForValue(I->getOperand(0)); 729 if (Reg == 0) 730 return false; 731 UpdateValueMap(I, Reg); 732 return true; 733 } 734 735 // Bitcasts of other values become reg-reg copies or BITCAST operators. 736 EVT SrcVT = TLI.getValueType(I->getOperand(0)->getType()); 737 EVT DstVT = TLI.getValueType(I->getType()); 738 739 if (SrcVT == MVT::Other || !SrcVT.isSimple() || 740 DstVT == MVT::Other || !DstVT.isSimple() || 741 !TLI.isTypeLegal(SrcVT) || !TLI.isTypeLegal(DstVT)) 742 // Unhandled type. Halt "fast" selection and bail. 743 return false; 744 745 unsigned Op0 = getRegForValue(I->getOperand(0)); 746 if (Op0 == 0) 747 // Unhandled operand. Halt "fast" selection and bail. 748 return false; 749 750 bool Op0IsKill = hasTrivialKill(I->getOperand(0)); 751 752 // First, try to perform the bitcast by inserting a reg-reg copy. 753 unsigned ResultReg = 0; 754 if (SrcVT.getSimpleVT() == DstVT.getSimpleVT()) { 755 const TargetRegisterClass* SrcClass = TLI.getRegClassFor(SrcVT); 756 const TargetRegisterClass* DstClass = TLI.getRegClassFor(DstVT); 757 // Don't attempt a cross-class copy. It will likely fail. 758 if (SrcClass == DstClass) { 759 ResultReg = createResultReg(DstClass); 760 BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, TII.get(TargetOpcode::COPY), 761 ResultReg).addReg(Op0); 762 } 763 } 764 765 // If the reg-reg copy failed, select a BITCAST opcode. 766 if (!ResultReg) 767 ResultReg = FastEmit_r(SrcVT.getSimpleVT(), DstVT.getSimpleVT(), 768 ISD::BITCAST, Op0, Op0IsKill); 769 770 if (!ResultReg) 771 return false; 772 773 UpdateValueMap(I, ResultReg); 774 return true; 775 } 776 777 bool 778 FastISel::SelectInstruction(const Instruction *I) { 779 // Just before the terminator instruction, insert instructions to 780 // feed PHI nodes in successor blocks. 781 if (isa<TerminatorInst>(I)) 782 if (!HandlePHINodesInSuccessorBlocks(I->getParent())) 783 return false; 784 785 DL = I->getDebugLoc(); 786 787 MachineBasicBlock::iterator SavedInsertPt = FuncInfo.InsertPt; 788 789 // First, try doing target-independent selection. 790 if (SelectOperator(I, I->getOpcode())) { 791 ++NumFastIselSuccessIndependent; 792 DL = DebugLoc(); 793 return true; 794 } 795 // Remove dead code. However, ignore call instructions since we've flushed 796 // the local value map and recomputed the insert point. 797 if (!isa<CallInst>(I)) { 798 recomputeInsertPt(); 799 if (SavedInsertPt != FuncInfo.InsertPt) 800 removeDeadCode(FuncInfo.InsertPt, SavedInsertPt); 801 } 802 803 // Next, try calling the target to attempt to handle the instruction. 804 SavedInsertPt = FuncInfo.InsertPt; 805 if (TargetSelectInstruction(I)) { 806 ++NumFastIselSuccessTarget; 807 DL = DebugLoc(); 808 return true; 809 } 810 // Check for dead code and remove as necessary. 811 recomputeInsertPt(); 812 if (SavedInsertPt != FuncInfo.InsertPt) 813 removeDeadCode(FuncInfo.InsertPt, SavedInsertPt); 814 815 DL = DebugLoc(); 816 return false; 817 } 818 819 /// FastEmitBranch - Emit an unconditional branch to the given block, 820 /// unless it is the immediate (fall-through) successor, and update 821 /// the CFG. 822 void 823 FastISel::FastEmitBranch(MachineBasicBlock *MSucc, DebugLoc DL) { 824 825 if (FuncInfo.MBB->getBasicBlock()->size() > 1 && FuncInfo.MBB->isLayoutSuccessor(MSucc)) { 826 // For more accurate line information if this is the only instruction 827 // in the block then emit it, otherwise we have the unconditional 828 // fall-through case, which needs no instructions. 829 } else { 830 // The unconditional branch case. 831 TII.InsertBranch(*FuncInfo.MBB, MSucc, NULL, 832 SmallVector<MachineOperand, 0>(), DL); 833 } 834 FuncInfo.MBB->addSuccessor(MSucc); 835 } 836 837 /// SelectFNeg - Emit an FNeg operation. 838 /// 839 bool 840 FastISel::SelectFNeg(const User *I) { 841 unsigned OpReg = getRegForValue(BinaryOperator::getFNegArgument(I)); 842 if (OpReg == 0) return false; 843 844 bool OpRegIsKill = hasTrivialKill(I); 845 846 // If the target has ISD::FNEG, use it. 847 EVT VT = TLI.getValueType(I->getType()); 848 unsigned ResultReg = FastEmit_r(VT.getSimpleVT(), VT.getSimpleVT(), 849 ISD::FNEG, OpReg, OpRegIsKill); 850 if (ResultReg != 0) { 851 UpdateValueMap(I, ResultReg); 852 return true; 853 } 854 855 // Bitcast the value to integer, twiddle the sign bit with xor, 856 // and then bitcast it back to floating-point. 857 if (VT.getSizeInBits() > 64) return false; 858 EVT IntVT = EVT::getIntegerVT(I->getContext(), VT.getSizeInBits()); 859 if (!TLI.isTypeLegal(IntVT)) 860 return false; 861 862 unsigned IntReg = FastEmit_r(VT.getSimpleVT(), IntVT.getSimpleVT(), 863 ISD::BITCAST, OpReg, OpRegIsKill); 864 if (IntReg == 0) 865 return false; 866 867 unsigned IntResultReg = FastEmit_ri_(IntVT.getSimpleVT(), ISD::XOR, 868 IntReg, /*Kill=*/true, 869 UINT64_C(1) << (VT.getSizeInBits()-1), 870 IntVT.getSimpleVT()); 871 if (IntResultReg == 0) 872 return false; 873 874 ResultReg = FastEmit_r(IntVT.getSimpleVT(), VT.getSimpleVT(), 875 ISD::BITCAST, IntResultReg, /*Kill=*/true); 876 if (ResultReg == 0) 877 return false; 878 879 UpdateValueMap(I, ResultReg); 880 return true; 881 } 882 883 bool 884 FastISel::SelectExtractValue(const User *U) { 885 const ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(U); 886 if (!EVI) 887 return false; 888 889 // Make sure we only try to handle extracts with a legal result. But also 890 // allow i1 because it's easy. 891 EVT RealVT = TLI.getValueType(EVI->getType(), /*AllowUnknown=*/true); 892 if (!RealVT.isSimple()) 893 return false; 894 MVT VT = RealVT.getSimpleVT(); 895 if (!TLI.isTypeLegal(VT) && VT != MVT::i1) 896 return false; 897 898 const Value *Op0 = EVI->getOperand(0); 899 Type *AggTy = Op0->getType(); 900 901 // Get the base result register. 902 unsigned ResultReg; 903 DenseMap<const Value *, unsigned>::iterator I = FuncInfo.ValueMap.find(Op0); 904 if (I != FuncInfo.ValueMap.end()) 905 ResultReg = I->second; 906 else if (isa<Instruction>(Op0)) 907 ResultReg = FuncInfo.InitializeRegForValue(Op0); 908 else 909 return false; // fast-isel can't handle aggregate constants at the moment 910 911 // Get the actual result register, which is an offset from the base register. 912 unsigned VTIndex = ComputeLinearIndex(AggTy, EVI->getIndices()); 913 914 SmallVector<EVT, 4> AggValueVTs; 915 ComputeValueVTs(TLI, AggTy, AggValueVTs); 916 917 for (unsigned i = 0; i < VTIndex; i++) 918 ResultReg += TLI.getNumRegisters(FuncInfo.Fn->getContext(), AggValueVTs[i]); 919 920 UpdateValueMap(EVI, ResultReg); 921 return true; 922 } 923 924 bool 925 FastISel::SelectOperator(const User *I, unsigned Opcode) { 926 switch (Opcode) { 927 case Instruction::Add: 928 return SelectBinaryOp(I, ISD::ADD); 929 case Instruction::FAdd: 930 return SelectBinaryOp(I, ISD::FADD); 931 case Instruction::Sub: 932 return SelectBinaryOp(I, ISD::SUB); 933 case Instruction::FSub: 934 // FNeg is currently represented in LLVM IR as a special case of FSub. 935 if (BinaryOperator::isFNeg(I)) 936 return SelectFNeg(I); 937 return SelectBinaryOp(I, ISD::FSUB); 938 case Instruction::Mul: 939 return SelectBinaryOp(I, ISD::MUL); 940 case Instruction::FMul: 941 return SelectBinaryOp(I, ISD::FMUL); 942 case Instruction::SDiv: 943 return SelectBinaryOp(I, ISD::SDIV); 944 case Instruction::UDiv: 945 return SelectBinaryOp(I, ISD::UDIV); 946 case Instruction::FDiv: 947 return SelectBinaryOp(I, ISD::FDIV); 948 case Instruction::SRem: 949 return SelectBinaryOp(I, ISD::SREM); 950 case Instruction::URem: 951 return SelectBinaryOp(I, ISD::UREM); 952 case Instruction::FRem: 953 return SelectBinaryOp(I, ISD::FREM); 954 case Instruction::Shl: 955 return SelectBinaryOp(I, ISD::SHL); 956 case Instruction::LShr: 957 return SelectBinaryOp(I, ISD::SRL); 958 case Instruction::AShr: 959 return SelectBinaryOp(I, ISD::SRA); 960 case Instruction::And: 961 return SelectBinaryOp(I, ISD::AND); 962 case Instruction::Or: 963 return SelectBinaryOp(I, ISD::OR); 964 case Instruction::Xor: 965 return SelectBinaryOp(I, ISD::XOR); 966 967 case Instruction::GetElementPtr: 968 return SelectGetElementPtr(I); 969 970 case Instruction::Br: { 971 const BranchInst *BI = cast<BranchInst>(I); 972 973 if (BI->isUnconditional()) { 974 const BasicBlock *LLVMSucc = BI->getSuccessor(0); 975 MachineBasicBlock *MSucc = FuncInfo.MBBMap[LLVMSucc]; 976 FastEmitBranch(MSucc, BI->getDebugLoc()); 977 return true; 978 } 979 980 // Conditional branches are not handed yet. 981 // Halt "fast" selection and bail. 982 return false; 983 } 984 985 case Instruction::Unreachable: 986 // Nothing to emit. 987 return true; 988 989 case Instruction::Alloca: 990 // FunctionLowering has the static-sized case covered. 991 if (FuncInfo.StaticAllocaMap.count(cast<AllocaInst>(I))) 992 return true; 993 994 // Dynamic-sized alloca is not handled yet. 995 return false; 996 997 case Instruction::Call: 998 return SelectCall(I); 999 1000 case Instruction::BitCast: 1001 return SelectBitCast(I); 1002 1003 case Instruction::FPToSI: 1004 return SelectCast(I, ISD::FP_TO_SINT); 1005 case Instruction::ZExt: 1006 return SelectCast(I, ISD::ZERO_EXTEND); 1007 case Instruction::SExt: 1008 return SelectCast(I, ISD::SIGN_EXTEND); 1009 case Instruction::Trunc: 1010 return SelectCast(I, ISD::TRUNCATE); 1011 case Instruction::SIToFP: 1012 return SelectCast(I, ISD::SINT_TO_FP); 1013 1014 case Instruction::IntToPtr: // Deliberate fall-through. 1015 case Instruction::PtrToInt: { 1016 EVT SrcVT = TLI.getValueType(I->getOperand(0)->getType()); 1017 EVT DstVT = TLI.getValueType(I->getType()); 1018 if (DstVT.bitsGT(SrcVT)) 1019 return SelectCast(I, ISD::ZERO_EXTEND); 1020 if (DstVT.bitsLT(SrcVT)) 1021 return SelectCast(I, ISD::TRUNCATE); 1022 unsigned Reg = getRegForValue(I->getOperand(0)); 1023 if (Reg == 0) return false; 1024 UpdateValueMap(I, Reg); 1025 return true; 1026 } 1027 1028 case Instruction::ExtractValue: 1029 return SelectExtractValue(I); 1030 1031 case Instruction::PHI: 1032 llvm_unreachable("FastISel shouldn't visit PHI nodes!"); 1033 1034 default: 1035 // Unhandled instruction. Halt "fast" selection and bail. 1036 return false; 1037 } 1038 } 1039 1040 FastISel::FastISel(FunctionLoweringInfo &funcInfo) 1041 : FuncInfo(funcInfo), 1042 MRI(FuncInfo.MF->getRegInfo()), 1043 MFI(*FuncInfo.MF->getFrameInfo()), 1044 MCP(*FuncInfo.MF->getConstantPool()), 1045 TM(FuncInfo.MF->getTarget()), 1046 TD(*TM.getTargetData()), 1047 TII(*TM.getInstrInfo()), 1048 TLI(*TM.getTargetLowering()), 1049 TRI(*TM.getRegisterInfo()) { 1050 } 1051 1052 FastISel::~FastISel() {} 1053 1054 unsigned FastISel::FastEmit_(MVT, MVT, 1055 unsigned) { 1056 return 0; 1057 } 1058 1059 unsigned FastISel::FastEmit_r(MVT, MVT, 1060 unsigned, 1061 unsigned /*Op0*/, bool /*Op0IsKill*/) { 1062 return 0; 1063 } 1064 1065 unsigned FastISel::FastEmit_rr(MVT, MVT, 1066 unsigned, 1067 unsigned /*Op0*/, bool /*Op0IsKill*/, 1068 unsigned /*Op1*/, bool /*Op1IsKill*/) { 1069 return 0; 1070 } 1071 1072 unsigned FastISel::FastEmit_i(MVT, MVT, unsigned, uint64_t /*Imm*/) { 1073 return 0; 1074 } 1075 1076 unsigned FastISel::FastEmit_f(MVT, MVT, 1077 unsigned, const ConstantFP * /*FPImm*/) { 1078 return 0; 1079 } 1080 1081 unsigned FastISel::FastEmit_ri(MVT, MVT, 1082 unsigned, 1083 unsigned /*Op0*/, bool /*Op0IsKill*/, 1084 uint64_t /*Imm*/) { 1085 return 0; 1086 } 1087 1088 unsigned FastISel::FastEmit_rf(MVT, MVT, 1089 unsigned, 1090 unsigned /*Op0*/, bool /*Op0IsKill*/, 1091 const ConstantFP * /*FPImm*/) { 1092 return 0; 1093 } 1094 1095 unsigned FastISel::FastEmit_rri(MVT, MVT, 1096 unsigned, 1097 unsigned /*Op0*/, bool /*Op0IsKill*/, 1098 unsigned /*Op1*/, bool /*Op1IsKill*/, 1099 uint64_t /*Imm*/) { 1100 return 0; 1101 } 1102 1103 /// FastEmit_ri_ - This method is a wrapper of FastEmit_ri. It first tries 1104 /// to emit an instruction with an immediate operand using FastEmit_ri. 1105 /// If that fails, it materializes the immediate into a register and try 1106 /// FastEmit_rr instead. 1107 unsigned FastISel::FastEmit_ri_(MVT VT, unsigned Opcode, 1108 unsigned Op0, bool Op0IsKill, 1109 uint64_t Imm, MVT ImmType) { 1110 // If this is a multiply by a power of two, emit this as a shift left. 1111 if (Opcode == ISD::MUL && isPowerOf2_64(Imm)) { 1112 Opcode = ISD::SHL; 1113 Imm = Log2_64(Imm); 1114 } else if (Opcode == ISD::UDIV && isPowerOf2_64(Imm)) { 1115 // div x, 8 -> srl x, 3 1116 Opcode = ISD::SRL; 1117 Imm = Log2_64(Imm); 1118 } 1119 1120 // Horrible hack (to be removed), check to make sure shift amounts are 1121 // in-range. 1122 if ((Opcode == ISD::SHL || Opcode == ISD::SRA || Opcode == ISD::SRL) && 1123 Imm >= VT.getSizeInBits()) 1124 return 0; 1125 1126 // First check if immediate type is legal. If not, we can't use the ri form. 1127 unsigned ResultReg = FastEmit_ri(VT, VT, Opcode, Op0, Op0IsKill, Imm); 1128 if (ResultReg != 0) 1129 return ResultReg; 1130 unsigned MaterialReg = FastEmit_i(ImmType, ImmType, ISD::Constant, Imm); 1131 if (MaterialReg == 0) { 1132 // This is a bit ugly/slow, but failing here means falling out of 1133 // fast-isel, which would be very slow. 1134 IntegerType *ITy = IntegerType::get(FuncInfo.Fn->getContext(), 1135 VT.getSizeInBits()); 1136 MaterialReg = getRegForValue(ConstantInt::get(ITy, Imm)); 1137 } 1138 return FastEmit_rr(VT, VT, Opcode, 1139 Op0, Op0IsKill, 1140 MaterialReg, /*Kill=*/true); 1141 } 1142 1143 unsigned FastISel::createResultReg(const TargetRegisterClass* RC) { 1144 return MRI.createVirtualRegister(RC); 1145 } 1146 1147 unsigned FastISel::FastEmitInst_(unsigned MachineInstOpcode, 1148 const TargetRegisterClass* RC) { 1149 unsigned ResultReg = createResultReg(RC); 1150 const MCInstrDesc &II = TII.get(MachineInstOpcode); 1151 1152 BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, II, ResultReg); 1153 return ResultReg; 1154 } 1155 1156 unsigned FastISel::FastEmitInst_r(unsigned MachineInstOpcode, 1157 const TargetRegisterClass *RC, 1158 unsigned Op0, bool Op0IsKill) { 1159 unsigned ResultReg = createResultReg(RC); 1160 const MCInstrDesc &II = TII.get(MachineInstOpcode); 1161 1162 if (II.getNumDefs() >= 1) 1163 BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, II, ResultReg) 1164 .addReg(Op0, Op0IsKill * RegState::Kill); 1165 else { 1166 BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, II) 1167 .addReg(Op0, Op0IsKill * RegState::Kill); 1168 BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, TII.get(TargetOpcode::COPY), 1169 ResultReg).addReg(II.ImplicitDefs[0]); 1170 } 1171 1172 return ResultReg; 1173 } 1174 1175 unsigned FastISel::FastEmitInst_rr(unsigned MachineInstOpcode, 1176 const TargetRegisterClass *RC, 1177 unsigned Op0, bool Op0IsKill, 1178 unsigned Op1, bool Op1IsKill) { 1179 unsigned ResultReg = createResultReg(RC); 1180 const MCInstrDesc &II = TII.get(MachineInstOpcode); 1181 1182 if (II.getNumDefs() >= 1) 1183 BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, II, ResultReg) 1184 .addReg(Op0, Op0IsKill * RegState::Kill) 1185 .addReg(Op1, Op1IsKill * RegState::Kill); 1186 else { 1187 BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, II) 1188 .addReg(Op0, Op0IsKill * RegState::Kill) 1189 .addReg(Op1, Op1IsKill * RegState::Kill); 1190 BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, TII.get(TargetOpcode::COPY), 1191 ResultReg).addReg(II.ImplicitDefs[0]); 1192 } 1193 return ResultReg; 1194 } 1195 1196 unsigned FastISel::FastEmitInst_rrr(unsigned MachineInstOpcode, 1197 const TargetRegisterClass *RC, 1198 unsigned Op0, bool Op0IsKill, 1199 unsigned Op1, bool Op1IsKill, 1200 unsigned Op2, bool Op2IsKill) { 1201 unsigned ResultReg = createResultReg(RC); 1202 const MCInstrDesc &II = TII.get(MachineInstOpcode); 1203 1204 if (II.getNumDefs() >= 1) 1205 BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, II, ResultReg) 1206 .addReg(Op0, Op0IsKill * RegState::Kill) 1207 .addReg(Op1, Op1IsKill * RegState::Kill) 1208 .addReg(Op2, Op2IsKill * RegState::Kill); 1209 else { 1210 BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, II) 1211 .addReg(Op0, Op0IsKill * RegState::Kill) 1212 .addReg(Op1, Op1IsKill * RegState::Kill) 1213 .addReg(Op2, Op2IsKill * RegState::Kill); 1214 BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, TII.get(TargetOpcode::COPY), 1215 ResultReg).addReg(II.ImplicitDefs[0]); 1216 } 1217 return ResultReg; 1218 } 1219 1220 unsigned FastISel::FastEmitInst_ri(unsigned MachineInstOpcode, 1221 const TargetRegisterClass *RC, 1222 unsigned Op0, bool Op0IsKill, 1223 uint64_t Imm) { 1224 unsigned ResultReg = createResultReg(RC); 1225 const MCInstrDesc &II = TII.get(MachineInstOpcode); 1226 1227 if (II.getNumDefs() >= 1) 1228 BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, II, ResultReg) 1229 .addReg(Op0, Op0IsKill * RegState::Kill) 1230 .addImm(Imm); 1231 else { 1232 BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, II) 1233 .addReg(Op0, Op0IsKill * RegState::Kill) 1234 .addImm(Imm); 1235 BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, TII.get(TargetOpcode::COPY), 1236 ResultReg).addReg(II.ImplicitDefs[0]); 1237 } 1238 return ResultReg; 1239 } 1240 1241 unsigned FastISel::FastEmitInst_rii(unsigned MachineInstOpcode, 1242 const TargetRegisterClass *RC, 1243 unsigned Op0, bool Op0IsKill, 1244 uint64_t Imm1, uint64_t Imm2) { 1245 unsigned ResultReg = createResultReg(RC); 1246 const MCInstrDesc &II = TII.get(MachineInstOpcode); 1247 1248 if (II.getNumDefs() >= 1) 1249 BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, II, ResultReg) 1250 .addReg(Op0, Op0IsKill * RegState::Kill) 1251 .addImm(Imm1) 1252 .addImm(Imm2); 1253 else { 1254 BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, II) 1255 .addReg(Op0, Op0IsKill * RegState::Kill) 1256 .addImm(Imm1) 1257 .addImm(Imm2); 1258 BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, TII.get(TargetOpcode::COPY), 1259 ResultReg).addReg(II.ImplicitDefs[0]); 1260 } 1261 return ResultReg; 1262 } 1263 1264 unsigned FastISel::FastEmitInst_rf(unsigned MachineInstOpcode, 1265 const TargetRegisterClass *RC, 1266 unsigned Op0, bool Op0IsKill, 1267 const ConstantFP *FPImm) { 1268 unsigned ResultReg = createResultReg(RC); 1269 const MCInstrDesc &II = TII.get(MachineInstOpcode); 1270 1271 if (II.getNumDefs() >= 1) 1272 BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, II, ResultReg) 1273 .addReg(Op0, Op0IsKill * RegState::Kill) 1274 .addFPImm(FPImm); 1275 else { 1276 BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, II) 1277 .addReg(Op0, Op0IsKill * RegState::Kill) 1278 .addFPImm(FPImm); 1279 BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, TII.get(TargetOpcode::COPY), 1280 ResultReg).addReg(II.ImplicitDefs[0]); 1281 } 1282 return ResultReg; 1283 } 1284 1285 unsigned FastISel::FastEmitInst_rri(unsigned MachineInstOpcode, 1286 const TargetRegisterClass *RC, 1287 unsigned Op0, bool Op0IsKill, 1288 unsigned Op1, bool Op1IsKill, 1289 uint64_t Imm) { 1290 unsigned ResultReg = createResultReg(RC); 1291 const MCInstrDesc &II = TII.get(MachineInstOpcode); 1292 1293 if (II.getNumDefs() >= 1) 1294 BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, II, ResultReg) 1295 .addReg(Op0, Op0IsKill * RegState::Kill) 1296 .addReg(Op1, Op1IsKill * RegState::Kill) 1297 .addImm(Imm); 1298 else { 1299 BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, II) 1300 .addReg(Op0, Op0IsKill * RegState::Kill) 1301 .addReg(Op1, Op1IsKill * RegState::Kill) 1302 .addImm(Imm); 1303 BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, TII.get(TargetOpcode::COPY), 1304 ResultReg).addReg(II.ImplicitDefs[0]); 1305 } 1306 return ResultReg; 1307 } 1308 1309 unsigned FastISel::FastEmitInst_i(unsigned MachineInstOpcode, 1310 const TargetRegisterClass *RC, 1311 uint64_t Imm) { 1312 unsigned ResultReg = createResultReg(RC); 1313 const MCInstrDesc &II = TII.get(MachineInstOpcode); 1314 1315 if (II.getNumDefs() >= 1) 1316 BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, II, ResultReg).addImm(Imm); 1317 else { 1318 BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, II).addImm(Imm); 1319 BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, TII.get(TargetOpcode::COPY), 1320 ResultReg).addReg(II.ImplicitDefs[0]); 1321 } 1322 return ResultReg; 1323 } 1324 1325 unsigned FastISel::FastEmitInst_ii(unsigned MachineInstOpcode, 1326 const TargetRegisterClass *RC, 1327 uint64_t Imm1, uint64_t Imm2) { 1328 unsigned ResultReg = createResultReg(RC); 1329 const MCInstrDesc &II = TII.get(MachineInstOpcode); 1330 1331 if (II.getNumDefs() >= 1) 1332 BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, II, ResultReg) 1333 .addImm(Imm1).addImm(Imm2); 1334 else { 1335 BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, II).addImm(Imm1).addImm(Imm2); 1336 BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, TII.get(TargetOpcode::COPY), 1337 ResultReg).addReg(II.ImplicitDefs[0]); 1338 } 1339 return ResultReg; 1340 } 1341 1342 unsigned FastISel::FastEmitInst_extractsubreg(MVT RetVT, 1343 unsigned Op0, bool Op0IsKill, 1344 uint32_t Idx) { 1345 unsigned ResultReg = createResultReg(TLI.getRegClassFor(RetVT)); 1346 assert(TargetRegisterInfo::isVirtualRegister(Op0) && 1347 "Cannot yet extract from physregs"); 1348 BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, 1349 DL, TII.get(TargetOpcode::COPY), ResultReg) 1350 .addReg(Op0, getKillRegState(Op0IsKill), Idx); 1351 return ResultReg; 1352 } 1353 1354 /// FastEmitZExtFromI1 - Emit MachineInstrs to compute the value of Op 1355 /// with all but the least significant bit set to zero. 1356 unsigned FastISel::FastEmitZExtFromI1(MVT VT, unsigned Op0, bool Op0IsKill) { 1357 return FastEmit_ri(VT, VT, ISD::AND, Op0, Op0IsKill, 1); 1358 } 1359 1360 /// HandlePHINodesInSuccessorBlocks - Handle PHI nodes in successor blocks. 1361 /// Emit code to ensure constants are copied into registers when needed. 1362 /// Remember the virtual registers that need to be added to the Machine PHI 1363 /// nodes as input. We cannot just directly add them, because expansion 1364 /// might result in multiple MBB's for one BB. As such, the start of the 1365 /// BB might correspond to a different MBB than the end. 1366 bool FastISel::HandlePHINodesInSuccessorBlocks(const BasicBlock *LLVMBB) { 1367 const TerminatorInst *TI = LLVMBB->getTerminator(); 1368 1369 SmallPtrSet<MachineBasicBlock *, 4> SuccsHandled; 1370 unsigned OrigNumPHINodesToUpdate = FuncInfo.PHINodesToUpdate.size(); 1371 1372 // Check successor nodes' PHI nodes that expect a constant to be available 1373 // from this block. 1374 for (unsigned succ = 0, e = TI->getNumSuccessors(); succ != e; ++succ) { 1375 const BasicBlock *SuccBB = TI->getSuccessor(succ); 1376 if (!isa<PHINode>(SuccBB->begin())) continue; 1377 MachineBasicBlock *SuccMBB = FuncInfo.MBBMap[SuccBB]; 1378 1379 // If this terminator has multiple identical successors (common for 1380 // switches), only handle each succ once. 1381 if (!SuccsHandled.insert(SuccMBB)) continue; 1382 1383 MachineBasicBlock::iterator MBBI = SuccMBB->begin(); 1384 1385 // At this point we know that there is a 1-1 correspondence between LLVM PHI 1386 // nodes and Machine PHI nodes, but the incoming operands have not been 1387 // emitted yet. 1388 for (BasicBlock::const_iterator I = SuccBB->begin(); 1389 const PHINode *PN = dyn_cast<PHINode>(I); ++I) { 1390 1391 // Ignore dead phi's. 1392 if (PN->use_empty()) continue; 1393 1394 // Only handle legal types. Two interesting things to note here. First, 1395 // by bailing out early, we may leave behind some dead instructions, 1396 // since SelectionDAG's HandlePHINodesInSuccessorBlocks will insert its 1397 // own moves. Second, this check is necessary because FastISel doesn't 1398 // use CreateRegs to create registers, so it always creates 1399 // exactly one register for each non-void instruction. 1400 EVT VT = TLI.getValueType(PN->getType(), /*AllowUnknown=*/true); 1401 if (VT == MVT::Other || !TLI.isTypeLegal(VT)) { 1402 // Handle integer promotions, though, because they're common and easy. 1403 if (VT == MVT::i1 || VT == MVT::i8 || VT == MVT::i16) 1404 VT = TLI.getTypeToTransformTo(LLVMBB->getContext(), VT); 1405 else { 1406 FuncInfo.PHINodesToUpdate.resize(OrigNumPHINodesToUpdate); 1407 return false; 1408 } 1409 } 1410 1411 const Value *PHIOp = PN->getIncomingValueForBlock(LLVMBB); 1412 1413 // Set the DebugLoc for the copy. Prefer the location of the operand 1414 // if there is one; use the location of the PHI otherwise. 1415 DL = PN->getDebugLoc(); 1416 if (const Instruction *Inst = dyn_cast<Instruction>(PHIOp)) 1417 DL = Inst->getDebugLoc(); 1418 1419 unsigned Reg = getRegForValue(PHIOp); 1420 if (Reg == 0) { 1421 FuncInfo.PHINodesToUpdate.resize(OrigNumPHINodesToUpdate); 1422 return false; 1423 } 1424 FuncInfo.PHINodesToUpdate.push_back(std::make_pair(MBBI++, Reg)); 1425 DL = DebugLoc(); 1426 } 1427 } 1428 1429 return true; 1430 } 1431