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