1207618Srdivacky//===-- FastISel.cpp - Implementation of the FastISel class ---------------===// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed// 10193323Sed// This file contains the implementation of the FastISel class. 11193323Sed// 12193323Sed// "Fast" instruction selection is designed to emit very poor code quickly. 13193323Sed// Also, it is not designed to be able to do much lowering, so most illegal 14193323Sed// types (e.g. i64 on 32-bit targets) and operations are not supported. It is 15193323Sed// also not intended to be able to do much optimization, except in a few cases 16193323Sed// where doing optimizations reduces overall compile time. For example, folding 17193323Sed// constants into immediate fields is often done, because it's cheap and it 18193323Sed// reduces the number of instructions later phases have to examine. 19193323Sed// 20193323Sed// "Fast" instruction selection is able to fail gracefully and transfer 21193323Sed// control to the SelectionDAG selector for operations that it doesn't 22193323Sed// support. In many cases, this allows us to avoid duplicating a lot of 23193323Sed// the complicated lowering logic that SelectionDAG currently has. 24193323Sed// 25193323Sed// The intended use for "fast" instruction selection is "-O0" mode 26193323Sed// compilation, where the quality of the generated code is irrelevant when 27193323Sed// weighed against the speed at which the code can be generated. Also, 28193323Sed// at -O0, the LLVM optimizers are not running, and this makes the 29193323Sed// compile time of codegen a much higher portion of the overall compile 30193323Sed// time. Despite its limitations, "fast" instruction selection is able to 31193323Sed// handle enough code on its own to provide noticeable overall speedups 32193323Sed// in -O0 compiles. 33193323Sed// 34193323Sed// Basic operations are supported in a target-independent way, by reading 35193323Sed// the same instruction descriptions that the SelectionDAG selector reads, 36193323Sed// and identifying simple arithmetic operations that can be directly selected 37193323Sed// from simple operators. More complicated operations currently require 38193323Sed// target-specific code. 39193323Sed// 40193323Sed//===----------------------------------------------------------------------===// 41193323Sed 42235633Sdim#define DEBUG_TYPE "isel" 43252723Sdim#include "llvm/CodeGen/FastISel.h" 44263509Sdim#include "llvm/ADT/Optional.h" 45252723Sdim#include "llvm/ADT/Statistic.h" 46252723Sdim#include "llvm/Analysis/Loads.h" 47223017Sdim#include "llvm/CodeGen/Analysis.h" 48210299Sed#include "llvm/CodeGen/FunctionLoweringInfo.h" 49193323Sed#include "llvm/CodeGen/MachineInstrBuilder.h" 50193323Sed#include "llvm/CodeGen/MachineModuleInfo.h" 51193323Sed#include "llvm/CodeGen/MachineRegisterInfo.h" 52252723Sdim#include "llvm/DebugInfo.h" 53252723Sdim#include "llvm/IR/DataLayout.h" 54252723Sdim#include "llvm/IR/Function.h" 55252723Sdim#include "llvm/IR/GlobalVariable.h" 56252723Sdim#include "llvm/IR/Instructions.h" 57252723Sdim#include "llvm/IR/IntrinsicInst.h" 58252723Sdim#include "llvm/IR/Operator.h" 59252723Sdim#include "llvm/Support/Debug.h" 60252723Sdim#include "llvm/Support/ErrorHandling.h" 61193323Sed#include "llvm/Target/TargetInstrInfo.h" 62245431Sdim#include "llvm/Target/TargetLibraryInfo.h" 63193323Sed#include "llvm/Target/TargetLowering.h" 64193323Sed#include "llvm/Target/TargetMachine.h" 65193323Sedusing namespace llvm; 66193323Sed 67235633SdimSTATISTIC(NumFastIselSuccessIndependent, "Number of insts selected by " 68235633Sdim "target-independent selector"); 69235633SdimSTATISTIC(NumFastIselSuccessTarget, "Number of insts selected by " 70235633Sdim "target-specific selector"); 71235633SdimSTATISTIC(NumFastIselDead, "Number of dead insts removed on failure"); 72235633Sdim 73210299Sed/// startNewBlock - Set the current block to which generated machine 74210299Sed/// instructions will be appended, and clear the local CSE map. 75210299Sed/// 76210299Sedvoid FastISel::startNewBlock() { 77210299Sed LocalValueMap.clear(); 78210299Sed 79253192Sdim // Instructions are appended to FuncInfo.MBB. If the basic block already 80253192Sdim // contains labels or copies, use the last instruction as the last local 81253192Sdim // value. 82226890Sdim EmitStartPt = 0; 83253192Sdim if (!FuncInfo.MBB->empty()) 84253192Sdim EmitStartPt = &FuncInfo.MBB->back(); 85226890Sdim LastLocalValue = EmitStartPt; 86210299Sed} 87210299Sed 88252723Sdimbool FastISel::LowerArguments() { 89252723Sdim if (!FuncInfo.CanLowerReturn) 90252723Sdim // Fallback to SDISel argument lowering code to deal with sret pointer 91252723Sdim // parameter. 92252723Sdim return false; 93263509Sdim 94252723Sdim if (!FastLowerArguments()) 95252723Sdim return false; 96252723Sdim 97263509Sdim // Enter arguments into ValueMap for uses in non-entry BBs. 98252723Sdim for (Function::const_arg_iterator I = FuncInfo.Fn->arg_begin(), 99252723Sdim E = FuncInfo.Fn->arg_end(); I != E; ++I) { 100263509Sdim DenseMap<const Value *, unsigned>::iterator VI = LocalValueMap.find(I); 101263509Sdim assert(VI != LocalValueMap.end() && "Missed an argument?"); 102263509Sdim FuncInfo.ValueMap[I] = VI->second; 103252723Sdim } 104252723Sdim return true; 105252723Sdim} 106252723Sdim 107226890Sdimvoid FastISel::flushLocalValueMap() { 108226890Sdim LocalValueMap.clear(); 109226890Sdim LastLocalValue = EmitStartPt; 110226890Sdim recomputeInsertPt(); 111226890Sdim} 112226890Sdim 113208599Srdivackybool FastISel::hasTrivialKill(const Value *V) const { 114208599Srdivacky // Don't consider constants or arguments to have trivial kills. 115208599Srdivacky const Instruction *I = dyn_cast<Instruction>(V); 116208599Srdivacky if (!I) 117208599Srdivacky return false; 118208599Srdivacky 119208599Srdivacky // No-op casts are trivially coalesced by fast-isel. 120208599Srdivacky if (const CastInst *Cast = dyn_cast<CastInst>(I)) 121208599Srdivacky if (Cast->isNoopCast(TD.getIntPtrType(Cast->getContext())) && 122208599Srdivacky !hasTrivialKill(Cast->getOperand(0))) 123208599Srdivacky return false; 124208599Srdivacky 125235633Sdim // GEPs with all zero indices are trivially coalesced by fast-isel. 126235633Sdim if (const GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(I)) 127235633Sdim if (GEP->hasAllZeroIndices() && !hasTrivialKill(GEP->getOperand(0))) 128235633Sdim return false; 129235633Sdim 130208599Srdivacky // Only instructions with a single use in the same basic block are considered 131208599Srdivacky // to have trivial kills. 132208599Srdivacky return I->hasOneUse() && 133208599Srdivacky !(I->getOpcode() == Instruction::BitCast || 134208599Srdivacky I->getOpcode() == Instruction::PtrToInt || 135208599Srdivacky I->getOpcode() == Instruction::IntToPtr) && 136212904Sdim cast<Instruction>(*I->use_begin())->getParent() == I->getParent(); 137208599Srdivacky} 138208599Srdivacky 139207618Srdivackyunsigned FastISel::getRegForValue(const Value *V) { 140198090Srdivacky EVT RealVT = TLI.getValueType(V->getType(), /*AllowUnknown=*/true); 141193323Sed // Don't handle non-simple values in FastISel. 142193323Sed if (!RealVT.isSimple()) 143193323Sed return 0; 144193323Sed 145193323Sed // Ignore illegal types. We must do this before looking up the value 146193323Sed // in ValueMap because Arguments are given virtual registers regardless 147193323Sed // of whether FastISel can handle them. 148198090Srdivacky MVT VT = RealVT.getSimpleVT(); 149193323Sed if (!TLI.isTypeLegal(VT)) { 150223017Sdim // Handle integer promotions, though, because they're common and easy. 151223017Sdim if (VT == MVT::i1 || VT == MVT::i8 || VT == MVT::i16) 152198090Srdivacky VT = TLI.getTypeToTransformTo(V->getContext(), VT).getSimpleVT(); 153193323Sed else 154193323Sed return 0; 155193323Sed } 156193323Sed 157235633Sdim // Look up the value to see if we already have a register for it. 158235633Sdim unsigned Reg = lookUpRegForValue(V); 159193323Sed if (Reg != 0) 160193323Sed return Reg; 161193323Sed 162208599Srdivacky // In bottom-up mode, just create the virtual register which will be used 163208599Srdivacky // to hold the value. It will be materialized later. 164210299Sed if (isa<Instruction>(V) && 165210299Sed (!isa<AllocaInst>(V) || 166210299Sed !FuncInfo.StaticAllocaMap.count(cast<AllocaInst>(V)))) 167210299Sed return FuncInfo.InitializeRegForValue(V); 168208599Srdivacky 169210299Sed SavePoint SaveInsertPt = enterLocalValueArea(); 170210299Sed 171210299Sed // Materialize the value in a register. Emit any instructions in the 172210299Sed // local value area. 173210299Sed Reg = materializeRegForValue(V, VT); 174210299Sed 175210299Sed leaveLocalValueArea(SaveInsertPt); 176210299Sed 177210299Sed return Reg; 178207618Srdivacky} 179207618Srdivacky 180212904Sdim/// materializeRegForValue - Helper for getRegForValue. This function is 181207618Srdivacky/// called when the value isn't already available in a register and must 182207618Srdivacky/// be materialized with new instructions. 183207618Srdivackyunsigned FastISel::materializeRegForValue(const Value *V, MVT VT) { 184207618Srdivacky unsigned Reg = 0; 185207618Srdivacky 186207618Srdivacky if (const ConstantInt *CI = dyn_cast<ConstantInt>(V)) { 187193323Sed if (CI->getValue().getActiveBits() <= 64) 188193323Sed Reg = FastEmit_i(VT, VT, ISD::Constant, CI->getZExtValue()); 189193323Sed } else if (isa<AllocaInst>(V)) { 190193323Sed Reg = TargetMaterializeAlloca(cast<AllocaInst>(V)); 191193323Sed } else if (isa<ConstantPointerNull>(V)) { 192193323Sed // Translate this as an integer zero so that it can be 193193323Sed // local-CSE'd with actual integer zeros. 194198090Srdivacky Reg = 195198090Srdivacky getRegForValue(Constant::getNullValue(TD.getIntPtrType(V->getContext()))); 196207618Srdivacky } else if (const ConstantFP *CF = dyn_cast<ConstantFP>(V)) { 197221345Sdim if (CF->isNullValue()) { 198221345Sdim Reg = TargetMaterializeFloatZero(CF); 199221345Sdim } else { 200221345Sdim // Try to emit the constant directly. 201221345Sdim Reg = FastEmit_f(VT, VT, ISD::ConstantFP, CF); 202221345Sdim } 203193323Sed 204193323Sed if (!Reg) { 205207618Srdivacky // Try to emit the constant by using an integer constant with a cast. 206193323Sed const APFloat &Flt = CF->getValueAPF(); 207198090Srdivacky EVT IntVT = TLI.getPointerTy(); 208193323Sed 209193323Sed uint64_t x[2]; 210193323Sed uint32_t IntBitWidth = IntVT.getSizeInBits(); 211193323Sed bool isExact; 212193323Sed (void) Flt.convertToInteger(x, IntBitWidth, /*isSigned=*/true, 213235633Sdim APFloat::rmTowardZero, &isExact); 214193323Sed if (isExact) { 215226890Sdim APInt IntVal(IntBitWidth, x); 216193323Sed 217198090Srdivacky unsigned IntegerReg = 218198090Srdivacky getRegForValue(ConstantInt::get(V->getContext(), IntVal)); 219193323Sed if (IntegerReg != 0) 220208599Srdivacky Reg = FastEmit_r(IntVT.getSimpleVT(), VT, ISD::SINT_TO_FP, 221208599Srdivacky IntegerReg, /*Kill=*/false); 222193323Sed } 223193323Sed } 224207618Srdivacky } else if (const Operator *Op = dyn_cast<Operator>(V)) { 225210299Sed if (!SelectOperator(Op, Op->getOpcode())) 226210299Sed if (!isa<Instruction>(Op) || 227210299Sed !TargetSelectInstruction(cast<Instruction>(Op))) 228210299Sed return 0; 229210299Sed Reg = lookUpRegForValue(Op); 230193323Sed } else if (isa<UndefValue>(V)) { 231193323Sed Reg = createResultReg(TLI.getRegClassFor(VT)); 232210299Sed BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, 233210299Sed TII.get(TargetOpcode::IMPLICIT_DEF), Reg); 234193323Sed } 235218893Sdim 236193323Sed // If target-independent code couldn't handle the value, give target-specific 237193323Sed // code a try. 238193323Sed if (!Reg && isa<Constant>(V)) 239193323Sed Reg = TargetMaterializeConstant(cast<Constant>(V)); 240218893Sdim 241193323Sed // Don't cache constant materializations in the general ValueMap. 242193323Sed // To do so would require tracking what uses they dominate. 243210299Sed if (Reg != 0) { 244193323Sed LocalValueMap[V] = Reg; 245210299Sed LastLocalValue = MRI.getVRegDef(Reg); 246210299Sed } 247193323Sed return Reg; 248193323Sed} 249193323Sed 250207618Srdivackyunsigned FastISel::lookUpRegForValue(const Value *V) { 251193323Sed // Look up the value to see if we already have a register for it. We 252193323Sed // cache values defined by Instructions across blocks, and other values 253193323Sed // only locally. This is because Instructions already have the SSA 254207618Srdivacky // def-dominates-use requirement enforced. 255210299Sed DenseMap<const Value *, unsigned>::iterator I = FuncInfo.ValueMap.find(V); 256210299Sed if (I != FuncInfo.ValueMap.end()) 257210299Sed return I->second; 258193323Sed return LocalValueMap[V]; 259193323Sed} 260193323Sed 261193323Sed/// UpdateValueMap - Update the value map to include the new mapping for this 262193323Sed/// instruction, or insert an extra copy to get the result in a previous 263193323Sed/// determined register. 264193323Sed/// NOTE: This is only necessary because we might select a block that uses 265193323Sed/// a value before we select the block that defines the value. It might be 266193323Sed/// possible to fix this by selecting blocks in reverse postorder. 267223017Sdimvoid FastISel::UpdateValueMap(const Value *I, unsigned Reg, unsigned NumRegs) { 268193323Sed if (!isa<Instruction>(I)) { 269193323Sed LocalValueMap[I] = Reg; 270223017Sdim return; 271193323Sed } 272218893Sdim 273210299Sed unsigned &AssignedReg = FuncInfo.ValueMap[I]; 274193323Sed if (AssignedReg == 0) 275210299Sed // Use the new register. 276193323Sed AssignedReg = Reg; 277193323Sed else if (Reg != AssignedReg) { 278210299Sed // Arrange for uses of AssignedReg to be replaced by uses of Reg. 279223017Sdim for (unsigned i = 0; i < NumRegs; i++) 280223017Sdim FuncInfo.RegFixups[AssignedReg+i] = Reg+i; 281210299Sed 282210299Sed AssignedReg = Reg; 283193323Sed } 284193323Sed} 285193323Sed 286208599Srdivackystd::pair<unsigned, bool> FastISel::getRegForGEPIndex(const Value *Idx) { 287193323Sed unsigned IdxN = getRegForValue(Idx); 288193323Sed if (IdxN == 0) 289193323Sed // Unhandled operand. Halt "fast" selection and bail. 290208599Srdivacky return std::pair<unsigned, bool>(0, false); 291193323Sed 292208599Srdivacky bool IdxNIsKill = hasTrivialKill(Idx); 293208599Srdivacky 294193323Sed // If the index is smaller or larger than intptr_t, truncate or extend it. 295193323Sed MVT PtrVT = TLI.getPointerTy(); 296198090Srdivacky EVT IdxVT = EVT::getEVT(Idx->getType(), /*HandleUnknown=*/false); 297208599Srdivacky if (IdxVT.bitsLT(PtrVT)) { 298208599Srdivacky IdxN = FastEmit_r(IdxVT.getSimpleVT(), PtrVT, ISD::SIGN_EXTEND, 299208599Srdivacky IdxN, IdxNIsKill); 300208599Srdivacky IdxNIsKill = true; 301208599Srdivacky } 302208599Srdivacky else if (IdxVT.bitsGT(PtrVT)) { 303208599Srdivacky IdxN = FastEmit_r(IdxVT.getSimpleVT(), PtrVT, ISD::TRUNCATE, 304208599Srdivacky IdxN, IdxNIsKill); 305208599Srdivacky IdxNIsKill = true; 306208599Srdivacky } 307208599Srdivacky return std::pair<unsigned, bool>(IdxN, IdxNIsKill); 308193323Sed} 309193323Sed 310210299Sedvoid FastISel::recomputeInsertPt() { 311210299Sed if (getLastLocalValue()) { 312210299Sed FuncInfo.InsertPt = getLastLocalValue(); 313212904Sdim FuncInfo.MBB = FuncInfo.InsertPt->getParent(); 314210299Sed ++FuncInfo.InsertPt; 315210299Sed } else 316210299Sed FuncInfo.InsertPt = FuncInfo.MBB->getFirstNonPHI(); 317210299Sed 318210299Sed // Now skip past any EH_LABELs, which must remain at the beginning. 319210299Sed while (FuncInfo.InsertPt != FuncInfo.MBB->end() && 320210299Sed FuncInfo.InsertPt->getOpcode() == TargetOpcode::EH_LABEL) 321210299Sed ++FuncInfo.InsertPt; 322210299Sed} 323210299Sed 324235633Sdimvoid FastISel::removeDeadCode(MachineBasicBlock::iterator I, 325235633Sdim MachineBasicBlock::iterator E) { 326235633Sdim assert (I && E && std::distance(I, E) > 0 && "Invalid iterator!"); 327235633Sdim while (I != E) { 328235633Sdim MachineInstr *Dead = &*I; 329235633Sdim ++I; 330235633Sdim Dead->eraseFromParent(); 331235633Sdim ++NumFastIselDead; 332235633Sdim } 333235633Sdim recomputeInsertPt(); 334235633Sdim} 335235633Sdim 336210299SedFastISel::SavePoint FastISel::enterLocalValueArea() { 337210299Sed MachineBasicBlock::iterator OldInsertPt = FuncInfo.InsertPt; 338210299Sed DebugLoc OldDL = DL; 339210299Sed recomputeInsertPt(); 340210299Sed DL = DebugLoc(); 341210299Sed SavePoint SP = { OldInsertPt, OldDL }; 342210299Sed return SP; 343210299Sed} 344210299Sed 345210299Sedvoid FastISel::leaveLocalValueArea(SavePoint OldInsertPt) { 346210299Sed if (FuncInfo.InsertPt != FuncInfo.MBB->begin()) 347210299Sed LastLocalValue = llvm::prior(FuncInfo.InsertPt); 348210299Sed 349210299Sed // Restore the previous insert position. 350210299Sed FuncInfo.InsertPt = OldInsertPt.InsertPt; 351210299Sed DL = OldInsertPt.DL; 352210299Sed} 353210299Sed 354193323Sed/// SelectBinaryOp - Select and emit code for a binary operator instruction, 355193323Sed/// which has an opcode which directly corresponds to the given ISD opcode. 356193323Sed/// 357207618Srdivackybool FastISel::SelectBinaryOp(const User *I, unsigned ISDOpcode) { 358198090Srdivacky EVT VT = EVT::getEVT(I->getType(), /*HandleUnknown=*/true); 359193323Sed if (VT == MVT::Other || !VT.isSimple()) 360193323Sed // Unhandled type. Halt "fast" selection and bail. 361193323Sed return false; 362193323Sed 363193323Sed // We only handle legal types. For example, on x86-32 the instruction 364193323Sed // selector contains all of the 64-bit instructions from x86-64, 365193323Sed // under the assumption that i64 won't be used if the target doesn't 366193323Sed // support it. 367193323Sed if (!TLI.isTypeLegal(VT)) { 368193323Sed // MVT::i1 is special. Allow AND, OR, or XOR because they 369193323Sed // don't require additional zeroing, which makes them easy. 370193323Sed if (VT == MVT::i1 && 371193323Sed (ISDOpcode == ISD::AND || ISDOpcode == ISD::OR || 372193323Sed ISDOpcode == ISD::XOR)) 373198090Srdivacky VT = TLI.getTypeToTransformTo(I->getContext(), VT); 374193323Sed else 375193323Sed return false; 376193323Sed } 377193323Sed 378221345Sdim // Check if the first operand is a constant, and handle it as "ri". At -O0, 379221345Sdim // we don't have anything that canonicalizes operand order. 380221345Sdim if (ConstantInt *CI = dyn_cast<ConstantInt>(I->getOperand(0))) 381221345Sdim if (isa<Instruction>(I) && cast<Instruction>(I)->isCommutative()) { 382221345Sdim unsigned Op1 = getRegForValue(I->getOperand(1)); 383221345Sdim if (Op1 == 0) return false; 384221345Sdim 385221345Sdim bool Op1IsKill = hasTrivialKill(I->getOperand(1)); 386221345Sdim 387221345Sdim unsigned ResultReg = FastEmit_ri_(VT.getSimpleVT(), ISDOpcode, Op1, 388221345Sdim Op1IsKill, CI->getZExtValue(), 389221345Sdim VT.getSimpleVT()); 390221345Sdim if (ResultReg == 0) return false; 391221345Sdim 392221345Sdim // We successfully emitted code for the given LLVM Instruction. 393221345Sdim UpdateValueMap(I, ResultReg); 394221345Sdim return true; 395221345Sdim } 396221345Sdim 397221345Sdim 398193323Sed unsigned Op0 = getRegForValue(I->getOperand(0)); 399221345Sdim if (Op0 == 0) // Unhandled operand. Halt "fast" selection and bail. 400193323Sed return false; 401193323Sed 402208599Srdivacky bool Op0IsKill = hasTrivialKill(I->getOperand(0)); 403208599Srdivacky 404193323Sed // Check if the second operand is a constant and handle it appropriately. 405193323Sed if (ConstantInt *CI = dyn_cast<ConstantInt>(I->getOperand(1))) { 406221345Sdim uint64_t Imm = CI->getZExtValue(); 407221345Sdim 408221345Sdim // Transform "sdiv exact X, 8" -> "sra X, 3". 409221345Sdim if (ISDOpcode == ISD::SDIV && isa<BinaryOperator>(I) && 410221345Sdim cast<BinaryOperator>(I)->isExact() && 411221345Sdim isPowerOf2_64(Imm)) { 412221345Sdim Imm = Log2_64(Imm); 413221345Sdim ISDOpcode = ISD::SRA; 414193323Sed } 415221345Sdim 416235633Sdim // Transform "urem x, pow2" -> "and x, pow2-1". 417235633Sdim if (ISDOpcode == ISD::UREM && isa<BinaryOperator>(I) && 418235633Sdim isPowerOf2_64(Imm)) { 419235633Sdim --Imm; 420235633Sdim ISDOpcode = ISD::AND; 421235633Sdim } 422235633Sdim 423221345Sdim unsigned ResultReg = FastEmit_ri_(VT.getSimpleVT(), ISDOpcode, Op0, 424221345Sdim Op0IsKill, Imm, VT.getSimpleVT()); 425221345Sdim if (ResultReg == 0) return false; 426221345Sdim 427221345Sdim // We successfully emitted code for the given LLVM Instruction. 428221345Sdim UpdateValueMap(I, ResultReg); 429221345Sdim return true; 430193323Sed } 431193323Sed 432193323Sed // Check if the second operand is a constant float. 433193323Sed if (ConstantFP *CF = dyn_cast<ConstantFP>(I->getOperand(1))) { 434193323Sed unsigned ResultReg = FastEmit_rf(VT.getSimpleVT(), VT.getSimpleVT(), 435208599Srdivacky ISDOpcode, Op0, Op0IsKill, CF); 436193323Sed if (ResultReg != 0) { 437193323Sed // We successfully emitted code for the given LLVM Instruction. 438193323Sed UpdateValueMap(I, ResultReg); 439193323Sed return true; 440193323Sed } 441193323Sed } 442193323Sed 443193323Sed unsigned Op1 = getRegForValue(I->getOperand(1)); 444193323Sed if (Op1 == 0) 445193323Sed // Unhandled operand. Halt "fast" selection and bail. 446193323Sed return false; 447193323Sed 448208599Srdivacky bool Op1IsKill = hasTrivialKill(I->getOperand(1)); 449208599Srdivacky 450193323Sed // Now we have both operands in registers. Emit the instruction. 451193323Sed unsigned ResultReg = FastEmit_rr(VT.getSimpleVT(), VT.getSimpleVT(), 452208599Srdivacky ISDOpcode, 453208599Srdivacky Op0, Op0IsKill, 454208599Srdivacky Op1, Op1IsKill); 455193323Sed if (ResultReg == 0) 456193323Sed // Target-specific code wasn't able to find a machine opcode for 457193323Sed // the given ISD opcode and type. Halt "fast" selection and bail. 458193323Sed return false; 459193323Sed 460193323Sed // We successfully emitted code for the given LLVM Instruction. 461193323Sed UpdateValueMap(I, ResultReg); 462193323Sed return true; 463193323Sed} 464193323Sed 465207618Srdivackybool FastISel::SelectGetElementPtr(const User *I) { 466193323Sed unsigned N = getRegForValue(I->getOperand(0)); 467193323Sed if (N == 0) 468193323Sed // Unhandled operand. Halt "fast" selection and bail. 469193323Sed return false; 470193323Sed 471208599Srdivacky bool NIsKill = hasTrivialKill(I->getOperand(0)); 472208599Srdivacky 473235633Sdim // Keep a running tab of the total offset to coalesce multiple N = N + Offset 474235633Sdim // into a single N = N + TotalOffset. 475235633Sdim uint64_t TotalOffs = 0; 476235633Sdim // FIXME: What's a good SWAG number for MaxOffs? 477235633Sdim uint64_t MaxOffs = 2048; 478226890Sdim Type *Ty = I->getOperand(0)->getType(); 479198090Srdivacky MVT VT = TLI.getPointerTy(); 480207618Srdivacky for (GetElementPtrInst::const_op_iterator OI = I->op_begin()+1, 481207618Srdivacky E = I->op_end(); OI != E; ++OI) { 482207618Srdivacky const Value *Idx = *OI; 483226890Sdim if (StructType *StTy = dyn_cast<StructType>(Ty)) { 484193323Sed unsigned Field = cast<ConstantInt>(Idx)->getZExtValue(); 485193323Sed if (Field) { 486193323Sed // N = N + Offset 487235633Sdim TotalOffs += TD.getStructLayout(StTy)->getElementOffset(Field); 488235633Sdim if (TotalOffs >= MaxOffs) { 489235633Sdim N = FastEmit_ri_(VT, ISD::ADD, N, NIsKill, TotalOffs, VT); 490235633Sdim if (N == 0) 491235633Sdim // Unhandled operand. Halt "fast" selection and bail. 492235633Sdim return false; 493235633Sdim NIsKill = true; 494235633Sdim TotalOffs = 0; 495235633Sdim } 496193323Sed } 497193323Sed Ty = StTy->getElementType(Field); 498193323Sed } else { 499193323Sed Ty = cast<SequentialType>(Ty)->getElementType(); 500193323Sed 501193323Sed // If this is a constant subscript, handle it quickly. 502207618Srdivacky if (const ConstantInt *CI = dyn_cast<ConstantInt>(Idx)) { 503210299Sed if (CI->isZero()) continue; 504235633Sdim // N = N + Offset 505245431Sdim TotalOffs += 506193323Sed TD.getTypeAllocSize(Ty)*cast<ConstantInt>(CI)->getSExtValue(); 507235633Sdim if (TotalOffs >= MaxOffs) { 508235633Sdim N = FastEmit_ri_(VT, ISD::ADD, N, NIsKill, TotalOffs, VT); 509235633Sdim if (N == 0) 510235633Sdim // Unhandled operand. Halt "fast" selection and bail. 511235633Sdim return false; 512235633Sdim NIsKill = true; 513235633Sdim TotalOffs = 0; 514235633Sdim } 515235633Sdim continue; 516235633Sdim } 517235633Sdim if (TotalOffs) { 518235633Sdim N = FastEmit_ri_(VT, ISD::ADD, N, NIsKill, TotalOffs, VT); 519193323Sed if (N == 0) 520193323Sed // Unhandled operand. Halt "fast" selection and bail. 521193323Sed return false; 522208599Srdivacky NIsKill = true; 523235633Sdim TotalOffs = 0; 524193323Sed } 525218893Sdim 526193323Sed // N = N + Idx * ElementSize; 527193323Sed uint64_t ElementSize = TD.getTypeAllocSize(Ty); 528208599Srdivacky std::pair<unsigned, bool> Pair = getRegForGEPIndex(Idx); 529208599Srdivacky unsigned IdxN = Pair.first; 530208599Srdivacky bool IdxNIsKill = Pair.second; 531193323Sed if (IdxN == 0) 532193323Sed // Unhandled operand. Halt "fast" selection and bail. 533193323Sed return false; 534193323Sed 535193323Sed if (ElementSize != 1) { 536208599Srdivacky IdxN = FastEmit_ri_(VT, ISD::MUL, IdxN, IdxNIsKill, ElementSize, VT); 537193323Sed if (IdxN == 0) 538193323Sed // Unhandled operand. Halt "fast" selection and bail. 539193323Sed return false; 540208599Srdivacky IdxNIsKill = true; 541193323Sed } 542208599Srdivacky N = FastEmit_rr(VT, VT, ISD::ADD, N, NIsKill, IdxN, IdxNIsKill); 543193323Sed if (N == 0) 544193323Sed // Unhandled operand. Halt "fast" selection and bail. 545193323Sed return false; 546193323Sed } 547193323Sed } 548235633Sdim if (TotalOffs) { 549235633Sdim N = FastEmit_ri_(VT, ISD::ADD, N, NIsKill, TotalOffs, VT); 550235633Sdim if (N == 0) 551235633Sdim // Unhandled operand. Halt "fast" selection and bail. 552235633Sdim return false; 553235633Sdim } 554193323Sed 555193323Sed // We successfully emitted code for the given LLVM Instruction. 556193323Sed UpdateValueMap(I, N); 557193323Sed return true; 558193323Sed} 559193323Sed 560207618Srdivackybool FastISel::SelectCall(const User *I) { 561221345Sdim const CallInst *Call = cast<CallInst>(I); 562221345Sdim 563221345Sdim // Handle simple inline asms. 564226890Sdim if (const InlineAsm *IA = dyn_cast<InlineAsm>(Call->getCalledValue())) { 565221345Sdim // Don't attempt to handle constraints. 566221345Sdim if (!IA->getConstraintString().empty()) 567221345Sdim return false; 568221345Sdim 569221345Sdim unsigned ExtraInfo = 0; 570221345Sdim if (IA->hasSideEffects()) 571221345Sdim ExtraInfo |= InlineAsm::Extra_HasSideEffects; 572221345Sdim if (IA->isAlignStack()) 573221345Sdim ExtraInfo |= InlineAsm::Extra_IsAlignStack; 574221345Sdim 575221345Sdim BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, 576221345Sdim TII.get(TargetOpcode::INLINEASM)) 577221345Sdim .addExternalSymbol(IA->getAsmString().c_str()) 578221345Sdim .addImm(ExtraInfo); 579221345Sdim return true; 580221345Sdim } 581221345Sdim 582235633Sdim MachineModuleInfo &MMI = FuncInfo.MF->getMMI(); 583235633Sdim ComputeUsesVAFloatArgument(*Call, &MMI); 584235633Sdim 585221345Sdim const Function *F = Call->getCalledFunction(); 586193323Sed if (!F) return false; 587193323Sed 588207618Srdivacky // Handle selected intrinsic function calls. 589221345Sdim switch (F->getIntrinsicID()) { 590193323Sed default: break; 591235633Sdim // At -O0 we don't care about the lifetime intrinsics. 592235633Sdim case Intrinsic::lifetime_start: 593235633Sdim case Intrinsic::lifetime_end: 594245431Sdim // The donothing intrinsic does, well, nothing. 595245431Sdim case Intrinsic::donothing: 596235633Sdim return true; 597245431Sdim 598193323Sed case Intrinsic::dbg_declare: { 599221345Sdim const DbgDeclareInst *DI = cast<DbgDeclareInst>(Call); 600263509Sdim DIVariable DIVar(DI->getVariable()); 601263509Sdim assert((!DIVar || DIVar.isVariable()) && 602263509Sdim "Variable in DbgDeclareInst should be either null or a DIVariable."); 603263509Sdim if (!DIVar || 604235633Sdim !FuncInfo.MF->getMMI().hasDebugInfo()) { 605235633Sdim DEBUG(dbgs() << "Dropping debug info for " << *DI << "\n"); 606195340Sed return true; 607235633Sdim } 608195340Sed 609207618Srdivacky const Value *Address = DI->getAddress(); 610235633Sdim if (!Address || isa<UndefValue>(Address)) { 611235633Sdim DEBUG(dbgs() << "Dropping debug info for " << *DI << "\n"); 612203954Srdivacky return true; 613235633Sdim } 614218893Sdim 615218893Sdim unsigned Offset = 0; 616263509Sdim Optional<MachineOperand> Op; 617263509Sdim if (const Argument *Arg = dyn_cast<Argument>(Address)) 618226890Sdim // Some arguments' frame index is recorded during argument lowering. 619226890Sdim Offset = FuncInfo.getArgumentFrameIndex(Arg); 620263509Sdim if (Offset) 621263509Sdim Op = MachineOperand::CreateFI(Offset); 622263509Sdim if (!Op) 623263509Sdim if (unsigned Reg = lookUpRegForValue(Address)) 624263509Sdim Op = MachineOperand::CreateReg(Reg, false); 625218893Sdim 626235633Sdim // If we have a VLA that has a "use" in a metadata node that's then used 627235633Sdim // here but it has no other uses, then we have a problem. E.g., 628235633Sdim // 629235633Sdim // int foo (const int *x) { 630235633Sdim // char a[*x]; 631235633Sdim // return 0; 632235633Sdim // } 633235633Sdim // 634235633Sdim // If we assign 'a' a vreg and fast isel later on has to use the selection 635235633Sdim // DAG isel, it will want to copy the value to the vreg. However, there are 636235633Sdim // no uses, which goes counter to what selection DAG isel expects. 637263509Sdim if (!Op && !Address->use_empty() && isa<Instruction>(Address) && 638235633Sdim (!isa<AllocaInst>(Address) || 639235633Sdim !FuncInfo.StaticAllocaMap.count(cast<AllocaInst>(Address)))) 640263509Sdim Op = MachineOperand::CreateReg(FuncInfo.InitializeRegForValue(Address), 641263509Sdim false); 642235633Sdim 643263509Sdim if (Op) { 644263509Sdim if (Op->isReg()) { 645263509Sdim Op->setIsDebug(true); 646263509Sdim BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, 647263509Sdim TII.get(TargetOpcode::DBG_VALUE), false, Op->getReg(), 0, 648263509Sdim DI->getVariable()); 649263509Sdim } else 650263509Sdim BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, 651263509Sdim TII.get(TargetOpcode::DBG_VALUE)) 652263509Sdim .addOperand(*Op) 653263509Sdim .addImm(0) 654263509Sdim .addMetadata(DI->getVariable()); 655263509Sdim } else { 656235633Sdim // We can't yet handle anything else here because it would require 657235633Sdim // generating code, thus altering codegen because of debug info. 658263509Sdim DEBUG(dbgs() << "Dropping debug info for " << *DI << "\n"); 659263509Sdim } 660193323Sed return true; 661193323Sed } 662204642Srdivacky case Intrinsic::dbg_value: { 663207618Srdivacky // This form of DBG_VALUE is target-independent. 664221345Sdim const DbgValueInst *DI = cast<DbgValueInst>(Call); 665224145Sdim const MCInstrDesc &II = TII.get(TargetOpcode::DBG_VALUE); 666207618Srdivacky const Value *V = DI->getValue(); 667204642Srdivacky if (!V) { 668204642Srdivacky // Currently the optimizer can produce this; insert an undef to 669204642Srdivacky // help debugging. Probably the optimizer should not do this. 670210299Sed BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, II) 671210299Sed .addReg(0U).addImm(DI->getOffset()) 672210299Sed .addMetadata(DI->getVariable()); 673207618Srdivacky } else if (const ConstantInt *CI = dyn_cast<ConstantInt>(V)) { 674224145Sdim if (CI->getBitWidth() > 64) 675224145Sdim BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, II) 676224145Sdim .addCImm(CI).addImm(DI->getOffset()) 677224145Sdim .addMetadata(DI->getVariable()); 678245431Sdim else 679224145Sdim BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, II) 680224145Sdim .addImm(CI->getZExtValue()).addImm(DI->getOffset()) 681224145Sdim .addMetadata(DI->getVariable()); 682207618Srdivacky } else if (const ConstantFP *CF = dyn_cast<ConstantFP>(V)) { 683210299Sed BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, II) 684210299Sed .addFPImm(CF).addImm(DI->getOffset()) 685210299Sed .addMetadata(DI->getVariable()); 686204642Srdivacky } else if (unsigned Reg = lookUpRegForValue(V)) { 687263509Sdim // FIXME: This does not handle register-indirect values at offset 0. 688263509Sdim bool IsIndirect = DI->getOffset() != 0; 689263509Sdim BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, II, IsIndirect, 690263509Sdim Reg, DI->getOffset(), DI->getVariable()); 691204642Srdivacky } else { 692204642Srdivacky // We can't yet handle anything else here because it would require 693204642Srdivacky // generating code, thus altering codegen because of debug info. 694263509Sdim DEBUG(dbgs() << "Dropping debug info for " << *DI << "\n"); 695218893Sdim } 696204642Srdivacky return true; 697204642Srdivacky } 698223017Sdim case Intrinsic::objectsize: { 699223017Sdim ConstantInt *CI = cast<ConstantInt>(Call->getArgOperand(1)); 700223017Sdim unsigned long long Res = CI->isZero() ? -1ULL : 0; 701223017Sdim Constant *ResCI = ConstantInt::get(Call->getType(), Res); 702223017Sdim unsigned ResultReg = getRegForValue(ResCI); 703223017Sdim if (ResultReg == 0) 704223017Sdim return false; 705223017Sdim UpdateValueMap(Call, ResultReg); 706223017Sdim return true; 707193323Sed } 708252723Sdim case Intrinsic::expect: { 709252723Sdim unsigned ResultReg = getRegForValue(Call->getArgOperand(0)); 710252723Sdim if (ResultReg == 0) 711252723Sdim return false; 712252723Sdim UpdateValueMap(Call, ResultReg); 713252723Sdim return true; 714223017Sdim } 715252723Sdim } 716207618Srdivacky 717226890Sdim // Usually, it does not make sense to initialize a value, 718226890Sdim // make an unrelated function call and use the value, because 719226890Sdim // it tends to be spilled on the stack. So, we move the pointer 720226890Sdim // to the last local value to the beginning of the block, so that 721226890Sdim // all the values which have already been materialized, 722226890Sdim // appear after the call. It also makes sense to skip intrinsics 723226890Sdim // since they tend to be inlined. 724252723Sdim if (!isa<IntrinsicInst>(Call)) 725226890Sdim flushLocalValueMap(); 726226890Sdim 727207618Srdivacky // An arbitrary call. Bail. 728193323Sed return false; 729193323Sed} 730193323Sed 731207618Srdivackybool FastISel::SelectCast(const User *I, unsigned Opcode) { 732198090Srdivacky EVT SrcVT = TLI.getValueType(I->getOperand(0)->getType()); 733198090Srdivacky EVT DstVT = TLI.getValueType(I->getType()); 734218893Sdim 735193323Sed if (SrcVT == MVT::Other || !SrcVT.isSimple() || 736193323Sed DstVT == MVT::Other || !DstVT.isSimple()) 737193323Sed // Unhandled type. Halt "fast" selection and bail. 738193323Sed return false; 739218893Sdim 740223017Sdim // Check if the destination type is legal. 741193323Sed if (!TLI.isTypeLegal(DstVT)) 742223017Sdim return false; 743193323Sed 744223017Sdim // Check if the source operand is legal. 745193323Sed if (!TLI.isTypeLegal(SrcVT)) 746223017Sdim return false; 747193323Sed 748193323Sed unsigned InputReg = getRegForValue(I->getOperand(0)); 749193323Sed if (!InputReg) 750193323Sed // Unhandled operand. Halt "fast" selection and bail. 751193323Sed return false; 752193323Sed 753208599Srdivacky bool InputRegIsKill = hasTrivialKill(I->getOperand(0)); 754208599Srdivacky 755193323Sed unsigned ResultReg = FastEmit_r(SrcVT.getSimpleVT(), 756193323Sed DstVT.getSimpleVT(), 757193323Sed Opcode, 758208599Srdivacky InputReg, InputRegIsKill); 759193323Sed if (!ResultReg) 760193323Sed return false; 761218893Sdim 762193323Sed UpdateValueMap(I, ResultReg); 763193323Sed return true; 764193323Sed} 765193323Sed 766207618Srdivackybool FastISel::SelectBitCast(const User *I) { 767193323Sed // If the bitcast doesn't change the type, just use the operand value. 768193323Sed if (I->getType() == I->getOperand(0)->getType()) { 769193323Sed unsigned Reg = getRegForValue(I->getOperand(0)); 770193323Sed if (Reg == 0) 771193323Sed return false; 772193323Sed UpdateValueMap(I, Reg); 773193323Sed return true; 774193323Sed } 775193323Sed 776218893Sdim // Bitcasts of other values become reg-reg copies or BITCAST operators. 777252723Sdim EVT SrcEVT = TLI.getValueType(I->getOperand(0)->getType()); 778252723Sdim EVT DstEVT = TLI.getValueType(I->getType()); 779252723Sdim if (SrcEVT == MVT::Other || DstEVT == MVT::Other || 780252723Sdim !TLI.isTypeLegal(SrcEVT) || !TLI.isTypeLegal(DstEVT)) 781193323Sed // Unhandled type. Halt "fast" selection and bail. 782193323Sed return false; 783218893Sdim 784252723Sdim MVT SrcVT = SrcEVT.getSimpleVT(); 785252723Sdim MVT DstVT = DstEVT.getSimpleVT(); 786193323Sed unsigned Op0 = getRegForValue(I->getOperand(0)); 787193323Sed if (Op0 == 0) 788193323Sed // Unhandled operand. Halt "fast" selection and bail. 789193323Sed return false; 790208599Srdivacky 791208599Srdivacky bool Op0IsKill = hasTrivialKill(I->getOperand(0)); 792218893Sdim 793193323Sed // First, try to perform the bitcast by inserting a reg-reg copy. 794193323Sed unsigned ResultReg = 0; 795252723Sdim if (SrcVT == DstVT) { 796235633Sdim const TargetRegisterClass* SrcClass = TLI.getRegClassFor(SrcVT); 797235633Sdim const TargetRegisterClass* DstClass = TLI.getRegClassFor(DstVT); 798210299Sed // Don't attempt a cross-class copy. It will likely fail. 799210299Sed if (SrcClass == DstClass) { 800210299Sed ResultReg = createResultReg(DstClass); 801210299Sed BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, TII.get(TargetOpcode::COPY), 802210299Sed ResultReg).addReg(Op0); 803210299Sed } 804193323Sed } 805218893Sdim 806218893Sdim // If the reg-reg copy failed, select a BITCAST opcode. 807193323Sed if (!ResultReg) 808252723Sdim ResultReg = FastEmit_r(SrcVT, DstVT, ISD::BITCAST, Op0, Op0IsKill); 809218893Sdim 810193323Sed if (!ResultReg) 811193323Sed return false; 812218893Sdim 813193323Sed UpdateValueMap(I, ResultReg); 814193323Sed return true; 815193323Sed} 816193323Sed 817193323Sedbool 818207618SrdivackyFastISel::SelectInstruction(const Instruction *I) { 819207618Srdivacky // Just before the terminator instruction, insert instructions to 820207618Srdivacky // feed PHI nodes in successor blocks. 821207618Srdivacky if (isa<TerminatorInst>(I)) 822207618Srdivacky if (!HandlePHINodesInSuccessorBlocks(I->getParent())) 823207618Srdivacky return false; 824207618Srdivacky 825207618Srdivacky DL = I->getDebugLoc(); 826207618Srdivacky 827235633Sdim MachineBasicBlock::iterator SavedInsertPt = FuncInfo.InsertPt; 828235633Sdim 829245431Sdim // As a special case, don't handle calls to builtin library functions that 830245431Sdim // may be translated directly to target instructions. 831245431Sdim if (const CallInst *Call = dyn_cast<CallInst>(I)) { 832245431Sdim const Function *F = Call->getCalledFunction(); 833245431Sdim LibFunc::Func Func; 834245431Sdim if (F && !F->hasLocalLinkage() && F->hasName() && 835245431Sdim LibInfo->getLibFunc(F->getName(), Func) && 836245431Sdim LibInfo->hasOptimizedCodeGen(Func)) 837245431Sdim return false; 838245431Sdim } 839245431Sdim 840200581Srdivacky // First, try doing target-independent selection. 841207618Srdivacky if (SelectOperator(I, I->getOpcode())) { 842235633Sdim ++NumFastIselSuccessIndependent; 843207618Srdivacky DL = DebugLoc(); 844200581Srdivacky return true; 845207618Srdivacky } 846245431Sdim // Remove dead code. However, ignore call instructions since we've flushed 847235633Sdim // the local value map and recomputed the insert point. 848235633Sdim if (!isa<CallInst>(I)) { 849235633Sdim recomputeInsertPt(); 850235633Sdim if (SavedInsertPt != FuncInfo.InsertPt) 851235633Sdim removeDeadCode(FuncInfo.InsertPt, SavedInsertPt); 852235633Sdim } 853200581Srdivacky 854200581Srdivacky // Next, try calling the target to attempt to handle the instruction. 855235633Sdim SavedInsertPt = FuncInfo.InsertPt; 856207618Srdivacky if (TargetSelectInstruction(I)) { 857235633Sdim ++NumFastIselSuccessTarget; 858207618Srdivacky DL = DebugLoc(); 859200581Srdivacky return true; 860207618Srdivacky } 861235633Sdim // Check for dead code and remove as necessary. 862235633Sdim recomputeInsertPt(); 863235633Sdim if (SavedInsertPt != FuncInfo.InsertPt) 864235633Sdim removeDeadCode(FuncInfo.InsertPt, SavedInsertPt); 865200581Srdivacky 866207618Srdivacky DL = DebugLoc(); 867200581Srdivacky return false; 868193323Sed} 869193323Sed 870193323Sed/// FastEmitBranch - Emit an unconditional branch to the given block, 871193323Sed/// unless it is the immediate (fall-through) successor, and update 872193323Sed/// the CFG. 873193323Sedvoid 874210299SedFastISel::FastEmitBranch(MachineBasicBlock *MSucc, DebugLoc DL) { 875235633Sdim 876252723Sdim if (FuncInfo.MBB->getBasicBlock()->size() > 1 && 877252723Sdim FuncInfo.MBB->isLayoutSuccessor(MSucc)) { 878235633Sdim // For more accurate line information if this is the only instruction 879235633Sdim // in the block then emit it, otherwise we have the unconditional 880235633Sdim // fall-through case, which needs no instructions. 881193323Sed } else { 882193323Sed // The unconditional branch case. 883210299Sed TII.InsertBranch(*FuncInfo.MBB, MSucc, NULL, 884210299Sed SmallVector<MachineOperand, 0>(), DL); 885193323Sed } 886210299Sed FuncInfo.MBB->addSuccessor(MSucc); 887193323Sed} 888193323Sed 889198090Srdivacky/// SelectFNeg - Emit an FNeg operation. 890198090Srdivacky/// 891193323Sedbool 892207618SrdivackyFastISel::SelectFNeg(const User *I) { 893198090Srdivacky unsigned OpReg = getRegForValue(BinaryOperator::getFNegArgument(I)); 894198090Srdivacky if (OpReg == 0) return false; 895198090Srdivacky 896208599Srdivacky bool OpRegIsKill = hasTrivialKill(I); 897208599Srdivacky 898198090Srdivacky // If the target has ISD::FNEG, use it. 899198090Srdivacky EVT VT = TLI.getValueType(I->getType()); 900198090Srdivacky unsigned ResultReg = FastEmit_r(VT.getSimpleVT(), VT.getSimpleVT(), 901208599Srdivacky ISD::FNEG, OpReg, OpRegIsKill); 902198090Srdivacky if (ResultReg != 0) { 903198090Srdivacky UpdateValueMap(I, ResultReg); 904198090Srdivacky return true; 905198090Srdivacky } 906198090Srdivacky 907198090Srdivacky // Bitcast the value to integer, twiddle the sign bit with xor, 908198090Srdivacky // and then bitcast it back to floating-point. 909198090Srdivacky if (VT.getSizeInBits() > 64) return false; 910198090Srdivacky EVT IntVT = EVT::getIntegerVT(I->getContext(), VT.getSizeInBits()); 911198090Srdivacky if (!TLI.isTypeLegal(IntVT)) 912198090Srdivacky return false; 913198090Srdivacky 914198090Srdivacky unsigned IntReg = FastEmit_r(VT.getSimpleVT(), IntVT.getSimpleVT(), 915218893Sdim ISD::BITCAST, OpReg, OpRegIsKill); 916198090Srdivacky if (IntReg == 0) 917198090Srdivacky return false; 918198090Srdivacky 919208599Srdivacky unsigned IntResultReg = FastEmit_ri_(IntVT.getSimpleVT(), ISD::XOR, 920208599Srdivacky IntReg, /*Kill=*/true, 921198090Srdivacky UINT64_C(1) << (VT.getSizeInBits()-1), 922198090Srdivacky IntVT.getSimpleVT()); 923198090Srdivacky if (IntResultReg == 0) 924198090Srdivacky return false; 925198090Srdivacky 926198090Srdivacky ResultReg = FastEmit_r(IntVT.getSimpleVT(), VT.getSimpleVT(), 927218893Sdim ISD::BITCAST, IntResultReg, /*Kill=*/true); 928198090Srdivacky if (ResultReg == 0) 929198090Srdivacky return false; 930198090Srdivacky 931198090Srdivacky UpdateValueMap(I, ResultReg); 932198090Srdivacky return true; 933198090Srdivacky} 934198090Srdivacky 935198090Srdivackybool 936223017SdimFastISel::SelectExtractValue(const User *U) { 937223017Sdim const ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(U); 938223017Sdim if (!EVI) 939223017Sdim return false; 940223017Sdim 941223017Sdim // Make sure we only try to handle extracts with a legal result. But also 942223017Sdim // allow i1 because it's easy. 943223017Sdim EVT RealVT = TLI.getValueType(EVI->getType(), /*AllowUnknown=*/true); 944223017Sdim if (!RealVT.isSimple()) 945223017Sdim return false; 946223017Sdim MVT VT = RealVT.getSimpleVT(); 947223017Sdim if (!TLI.isTypeLegal(VT) && VT != MVT::i1) 948223017Sdim return false; 949223017Sdim 950223017Sdim const Value *Op0 = EVI->getOperand(0); 951226890Sdim Type *AggTy = Op0->getType(); 952223017Sdim 953223017Sdim // Get the base result register. 954223017Sdim unsigned ResultReg; 955223017Sdim DenseMap<const Value *, unsigned>::iterator I = FuncInfo.ValueMap.find(Op0); 956223017Sdim if (I != FuncInfo.ValueMap.end()) 957223017Sdim ResultReg = I->second; 958223017Sdim else if (isa<Instruction>(Op0)) 959223017Sdim ResultReg = FuncInfo.InitializeRegForValue(Op0); 960223017Sdim else 961223017Sdim return false; // fast-isel can't handle aggregate constants at the moment 962223017Sdim 963223017Sdim // Get the actual result register, which is an offset from the base register. 964224145Sdim unsigned VTIndex = ComputeLinearIndex(AggTy, EVI->getIndices()); 965223017Sdim 966223017Sdim SmallVector<EVT, 4> AggValueVTs; 967223017Sdim ComputeValueVTs(TLI, AggTy, AggValueVTs); 968223017Sdim 969223017Sdim for (unsigned i = 0; i < VTIndex; i++) 970223017Sdim ResultReg += TLI.getNumRegisters(FuncInfo.Fn->getContext(), AggValueVTs[i]); 971223017Sdim 972223017Sdim UpdateValueMap(EVI, ResultReg); 973223017Sdim return true; 974223017Sdim} 975223017Sdim 976223017Sdimbool 977207618SrdivackyFastISel::SelectOperator(const User *I, unsigned Opcode) { 978193323Sed switch (Opcode) { 979193574Sed case Instruction::Add: 980193574Sed return SelectBinaryOp(I, ISD::ADD); 981193574Sed case Instruction::FAdd: 982193574Sed return SelectBinaryOp(I, ISD::FADD); 983193574Sed case Instruction::Sub: 984193574Sed return SelectBinaryOp(I, ISD::SUB); 985193574Sed case Instruction::FSub: 986198090Srdivacky // FNeg is currently represented in LLVM IR as a special case of FSub. 987198090Srdivacky if (BinaryOperator::isFNeg(I)) 988198090Srdivacky return SelectFNeg(I); 989193574Sed return SelectBinaryOp(I, ISD::FSUB); 990193574Sed case Instruction::Mul: 991193574Sed return SelectBinaryOp(I, ISD::MUL); 992193574Sed case Instruction::FMul: 993193574Sed return SelectBinaryOp(I, ISD::FMUL); 994193323Sed case Instruction::SDiv: 995193323Sed return SelectBinaryOp(I, ISD::SDIV); 996193323Sed case Instruction::UDiv: 997193323Sed return SelectBinaryOp(I, ISD::UDIV); 998193323Sed case Instruction::FDiv: 999193323Sed return SelectBinaryOp(I, ISD::FDIV); 1000193323Sed case Instruction::SRem: 1001193323Sed return SelectBinaryOp(I, ISD::SREM); 1002193323Sed case Instruction::URem: 1003193323Sed return SelectBinaryOp(I, ISD::UREM); 1004193323Sed case Instruction::FRem: 1005193323Sed return SelectBinaryOp(I, ISD::FREM); 1006193323Sed case Instruction::Shl: 1007193323Sed return SelectBinaryOp(I, ISD::SHL); 1008193323Sed case Instruction::LShr: 1009193323Sed return SelectBinaryOp(I, ISD::SRL); 1010193323Sed case Instruction::AShr: 1011193323Sed return SelectBinaryOp(I, ISD::SRA); 1012193323Sed case Instruction::And: 1013193323Sed return SelectBinaryOp(I, ISD::AND); 1014193323Sed case Instruction::Or: 1015193323Sed return SelectBinaryOp(I, ISD::OR); 1016193323Sed case Instruction::Xor: 1017193323Sed return SelectBinaryOp(I, ISD::XOR); 1018193323Sed 1019193323Sed case Instruction::GetElementPtr: 1020193323Sed return SelectGetElementPtr(I); 1021193323Sed 1022193323Sed case Instruction::Br: { 1023207618Srdivacky const BranchInst *BI = cast<BranchInst>(I); 1024193323Sed 1025193323Sed if (BI->isUnconditional()) { 1026207618Srdivacky const BasicBlock *LLVMSucc = BI->getSuccessor(0); 1027210299Sed MachineBasicBlock *MSucc = FuncInfo.MBBMap[LLVMSucc]; 1028210299Sed FastEmitBranch(MSucc, BI->getDebugLoc()); 1029193323Sed return true; 1030193323Sed } 1031193323Sed 1032193323Sed // Conditional branches are not handed yet. 1033193323Sed // Halt "fast" selection and bail. 1034193323Sed return false; 1035193323Sed } 1036193323Sed 1037193323Sed case Instruction::Unreachable: 1038193323Sed // Nothing to emit. 1039193323Sed return true; 1040193323Sed 1041193323Sed case Instruction::Alloca: 1042193323Sed // FunctionLowering has the static-sized case covered. 1043210299Sed if (FuncInfo.StaticAllocaMap.count(cast<AllocaInst>(I))) 1044193323Sed return true; 1045193323Sed 1046193323Sed // Dynamic-sized alloca is not handled yet. 1047193323Sed return false; 1048218893Sdim 1049193323Sed case Instruction::Call: 1050193323Sed return SelectCall(I); 1051218893Sdim 1052193323Sed case Instruction::BitCast: 1053193323Sed return SelectBitCast(I); 1054193323Sed 1055193323Sed case Instruction::FPToSI: 1056193323Sed return SelectCast(I, ISD::FP_TO_SINT); 1057193323Sed case Instruction::ZExt: 1058193323Sed return SelectCast(I, ISD::ZERO_EXTEND); 1059193323Sed case Instruction::SExt: 1060193323Sed return SelectCast(I, ISD::SIGN_EXTEND); 1061193323Sed case Instruction::Trunc: 1062193323Sed return SelectCast(I, ISD::TRUNCATE); 1063193323Sed case Instruction::SIToFP: 1064193323Sed return SelectCast(I, ISD::SINT_TO_FP); 1065193323Sed 1066193323Sed case Instruction::IntToPtr: // Deliberate fall-through. 1067193323Sed case Instruction::PtrToInt: { 1068198090Srdivacky EVT SrcVT = TLI.getValueType(I->getOperand(0)->getType()); 1069198090Srdivacky EVT DstVT = TLI.getValueType(I->getType()); 1070193323Sed if (DstVT.bitsGT(SrcVT)) 1071193323Sed return SelectCast(I, ISD::ZERO_EXTEND); 1072193323Sed if (DstVT.bitsLT(SrcVT)) 1073193323Sed return SelectCast(I, ISD::TRUNCATE); 1074193323Sed unsigned Reg = getRegForValue(I->getOperand(0)); 1075193323Sed if (Reg == 0) return false; 1076193323Sed UpdateValueMap(I, Reg); 1077193323Sed return true; 1078193323Sed } 1079193323Sed 1080223017Sdim case Instruction::ExtractValue: 1081223017Sdim return SelectExtractValue(I); 1082223017Sdim 1083207618Srdivacky case Instruction::PHI: 1084207618Srdivacky llvm_unreachable("FastISel shouldn't visit PHI nodes!"); 1085207618Srdivacky 1086193323Sed default: 1087193323Sed // Unhandled instruction. Halt "fast" selection and bail. 1088193323Sed return false; 1089193323Sed } 1090193323Sed} 1091193323Sed 1092245431SdimFastISel::FastISel(FunctionLoweringInfo &funcInfo, 1093245431Sdim const TargetLibraryInfo *libInfo) 1094210299Sed : FuncInfo(funcInfo), 1095210299Sed MRI(FuncInfo.MF->getRegInfo()), 1096210299Sed MFI(*FuncInfo.MF->getFrameInfo()), 1097210299Sed MCP(*FuncInfo.MF->getConstantPool()), 1098210299Sed TM(FuncInfo.MF->getTarget()), 1099245431Sdim TD(*TM.getDataLayout()), 1100193323Sed TII(*TM.getInstrInfo()), 1101208599Srdivacky TLI(*TM.getTargetLowering()), 1102245431Sdim TRI(*TM.getRegisterInfo()), 1103245431Sdim LibInfo(libInfo) { 1104193323Sed} 1105193323Sed 1106193323SedFastISel::~FastISel() {} 1107193323Sed 1108252723Sdimbool FastISel::FastLowerArguments() { 1109252723Sdim return false; 1110252723Sdim} 1111252723Sdim 1112198090Srdivackyunsigned FastISel::FastEmit_(MVT, MVT, 1113202375Srdivacky unsigned) { 1114193323Sed return 0; 1115193323Sed} 1116193323Sed 1117198090Srdivackyunsigned FastISel::FastEmit_r(MVT, MVT, 1118208599Srdivacky unsigned, 1119208599Srdivacky unsigned /*Op0*/, bool /*Op0IsKill*/) { 1120193323Sed return 0; 1121193323Sed} 1122193323Sed 1123218893Sdimunsigned FastISel::FastEmit_rr(MVT, MVT, 1124208599Srdivacky unsigned, 1125208599Srdivacky unsigned /*Op0*/, bool /*Op0IsKill*/, 1126208599Srdivacky unsigned /*Op1*/, bool /*Op1IsKill*/) { 1127193323Sed return 0; 1128193323Sed} 1129193323Sed 1130202375Srdivackyunsigned FastISel::FastEmit_i(MVT, MVT, unsigned, uint64_t /*Imm*/) { 1131193323Sed return 0; 1132193323Sed} 1133193323Sed 1134198090Srdivackyunsigned FastISel::FastEmit_f(MVT, MVT, 1135207618Srdivacky unsigned, const ConstantFP * /*FPImm*/) { 1136193323Sed return 0; 1137193323Sed} 1138193323Sed 1139198090Srdivackyunsigned FastISel::FastEmit_ri(MVT, MVT, 1140208599Srdivacky unsigned, 1141208599Srdivacky unsigned /*Op0*/, bool /*Op0IsKill*/, 1142193323Sed uint64_t /*Imm*/) { 1143193323Sed return 0; 1144193323Sed} 1145193323Sed 1146198090Srdivackyunsigned FastISel::FastEmit_rf(MVT, MVT, 1147208599Srdivacky unsigned, 1148208599Srdivacky unsigned /*Op0*/, bool /*Op0IsKill*/, 1149207618Srdivacky const ConstantFP * /*FPImm*/) { 1150193323Sed return 0; 1151193323Sed} 1152193323Sed 1153198090Srdivackyunsigned FastISel::FastEmit_rri(MVT, MVT, 1154202375Srdivacky unsigned, 1155208599Srdivacky unsigned /*Op0*/, bool /*Op0IsKill*/, 1156208599Srdivacky unsigned /*Op1*/, bool /*Op1IsKill*/, 1157193323Sed uint64_t /*Imm*/) { 1158193323Sed return 0; 1159193323Sed} 1160193323Sed 1161193323Sed/// FastEmit_ri_ - This method is a wrapper of FastEmit_ri. It first tries 1162193323Sed/// to emit an instruction with an immediate operand using FastEmit_ri. 1163193323Sed/// If that fails, it materializes the immediate into a register and try 1164193323Sed/// FastEmit_rr instead. 1165202375Srdivackyunsigned FastISel::FastEmit_ri_(MVT VT, unsigned Opcode, 1166208599Srdivacky unsigned Op0, bool Op0IsKill, 1167208599Srdivacky uint64_t Imm, MVT ImmType) { 1168221345Sdim // If this is a multiply by a power of two, emit this as a shift left. 1169221345Sdim if (Opcode == ISD::MUL && isPowerOf2_64(Imm)) { 1170221345Sdim Opcode = ISD::SHL; 1171221345Sdim Imm = Log2_64(Imm); 1172221345Sdim } else if (Opcode == ISD::UDIV && isPowerOf2_64(Imm)) { 1173221345Sdim // div x, 8 -> srl x, 3 1174221345Sdim Opcode = ISD::SRL; 1175221345Sdim Imm = Log2_64(Imm); 1176221345Sdim } 1177221345Sdim 1178221345Sdim // Horrible hack (to be removed), check to make sure shift amounts are 1179221345Sdim // in-range. 1180221345Sdim if ((Opcode == ISD::SHL || Opcode == ISD::SRA || Opcode == ISD::SRL) && 1181221345Sdim Imm >= VT.getSizeInBits()) 1182221345Sdim return 0; 1183221345Sdim 1184193323Sed // First check if immediate type is legal. If not, we can't use the ri form. 1185208599Srdivacky unsigned ResultReg = FastEmit_ri(VT, VT, Opcode, Op0, Op0IsKill, Imm); 1186193323Sed if (ResultReg != 0) 1187193323Sed return ResultReg; 1188193323Sed unsigned MaterialReg = FastEmit_i(ImmType, ImmType, ISD::Constant, Imm); 1189193323Sed if (MaterialReg == 0) { 1190221345Sdim // This is a bit ugly/slow, but failing here means falling out of 1191221345Sdim // fast-isel, which would be very slow. 1192226890Sdim IntegerType *ITy = IntegerType::get(FuncInfo.Fn->getContext(), 1193221345Sdim VT.getSizeInBits()); 1194221345Sdim MaterialReg = getRegForValue(ConstantInt::get(ITy, Imm)); 1195252723Sdim assert (MaterialReg != 0 && "Unable to materialize imm."); 1196252723Sdim if (MaterialReg == 0) return 0; 1197193323Sed } 1198208599Srdivacky return FastEmit_rr(VT, VT, Opcode, 1199208599Srdivacky Op0, Op0IsKill, 1200208599Srdivacky MaterialReg, /*Kill=*/true); 1201193323Sed} 1202193323Sed 1203193323Sedunsigned FastISel::createResultReg(const TargetRegisterClass* RC) { 1204193323Sed return MRI.createVirtualRegister(RC); 1205193323Sed} 1206193323Sed 1207193323Sedunsigned FastISel::FastEmitInst_(unsigned MachineInstOpcode, 1208193323Sed const TargetRegisterClass* RC) { 1209193323Sed unsigned ResultReg = createResultReg(RC); 1210224145Sdim const MCInstrDesc &II = TII.get(MachineInstOpcode); 1211193323Sed 1212210299Sed BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, II, ResultReg); 1213193323Sed return ResultReg; 1214193323Sed} 1215193323Sed 1216193323Sedunsigned FastISel::FastEmitInst_r(unsigned MachineInstOpcode, 1217193323Sed const TargetRegisterClass *RC, 1218208599Srdivacky unsigned Op0, bool Op0IsKill) { 1219193323Sed unsigned ResultReg = createResultReg(RC); 1220224145Sdim const MCInstrDesc &II = TII.get(MachineInstOpcode); 1221193323Sed 1222193323Sed if (II.getNumDefs() >= 1) 1223210299Sed BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, II, ResultReg) 1224210299Sed .addReg(Op0, Op0IsKill * RegState::Kill); 1225193323Sed else { 1226210299Sed BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, II) 1227210299Sed .addReg(Op0, Op0IsKill * RegState::Kill); 1228210299Sed BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, TII.get(TargetOpcode::COPY), 1229210299Sed ResultReg).addReg(II.ImplicitDefs[0]); 1230193323Sed } 1231193323Sed 1232193323Sed return ResultReg; 1233193323Sed} 1234193323Sed 1235193323Sedunsigned FastISel::FastEmitInst_rr(unsigned MachineInstOpcode, 1236193323Sed const TargetRegisterClass *RC, 1237208599Srdivacky unsigned Op0, bool Op0IsKill, 1238208599Srdivacky unsigned Op1, bool Op1IsKill) { 1239193323Sed unsigned ResultReg = createResultReg(RC); 1240224145Sdim const MCInstrDesc &II = TII.get(MachineInstOpcode); 1241193323Sed 1242193323Sed if (II.getNumDefs() >= 1) 1243210299Sed BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, II, ResultReg) 1244208599Srdivacky .addReg(Op0, Op0IsKill * RegState::Kill) 1245208599Srdivacky .addReg(Op1, Op1IsKill * RegState::Kill); 1246193323Sed else { 1247210299Sed BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, II) 1248208599Srdivacky .addReg(Op0, Op0IsKill * RegState::Kill) 1249208599Srdivacky .addReg(Op1, Op1IsKill * RegState::Kill); 1250210299Sed BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, TII.get(TargetOpcode::COPY), 1251210299Sed ResultReg).addReg(II.ImplicitDefs[0]); 1252193323Sed } 1253193323Sed return ResultReg; 1254193323Sed} 1255193323Sed 1256223017Sdimunsigned FastISel::FastEmitInst_rrr(unsigned MachineInstOpcode, 1257223017Sdim const TargetRegisterClass *RC, 1258223017Sdim unsigned Op0, bool Op0IsKill, 1259223017Sdim unsigned Op1, bool Op1IsKill, 1260223017Sdim unsigned Op2, bool Op2IsKill) { 1261223017Sdim unsigned ResultReg = createResultReg(RC); 1262224145Sdim const MCInstrDesc &II = TII.get(MachineInstOpcode); 1263223017Sdim 1264223017Sdim if (II.getNumDefs() >= 1) 1265223017Sdim BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, II, ResultReg) 1266223017Sdim .addReg(Op0, Op0IsKill * RegState::Kill) 1267223017Sdim .addReg(Op1, Op1IsKill * RegState::Kill) 1268223017Sdim .addReg(Op2, Op2IsKill * RegState::Kill); 1269223017Sdim else { 1270223017Sdim BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, II) 1271223017Sdim .addReg(Op0, Op0IsKill * RegState::Kill) 1272223017Sdim .addReg(Op1, Op1IsKill * RegState::Kill) 1273223017Sdim .addReg(Op2, Op2IsKill * RegState::Kill); 1274223017Sdim BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, TII.get(TargetOpcode::COPY), 1275223017Sdim ResultReg).addReg(II.ImplicitDefs[0]); 1276223017Sdim } 1277223017Sdim return ResultReg; 1278223017Sdim} 1279223017Sdim 1280193323Sedunsigned FastISel::FastEmitInst_ri(unsigned MachineInstOpcode, 1281193323Sed const TargetRegisterClass *RC, 1282208599Srdivacky unsigned Op0, bool Op0IsKill, 1283208599Srdivacky uint64_t Imm) { 1284193323Sed unsigned ResultReg = createResultReg(RC); 1285224145Sdim const MCInstrDesc &II = TII.get(MachineInstOpcode); 1286193323Sed 1287193323Sed if (II.getNumDefs() >= 1) 1288210299Sed BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, II, ResultReg) 1289208599Srdivacky .addReg(Op0, Op0IsKill * RegState::Kill) 1290208599Srdivacky .addImm(Imm); 1291193323Sed else { 1292210299Sed BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, II) 1293208599Srdivacky .addReg(Op0, Op0IsKill * RegState::Kill) 1294208599Srdivacky .addImm(Imm); 1295210299Sed BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, TII.get(TargetOpcode::COPY), 1296210299Sed ResultReg).addReg(II.ImplicitDefs[0]); 1297193323Sed } 1298193323Sed return ResultReg; 1299193323Sed} 1300193323Sed 1301221345Sdimunsigned FastISel::FastEmitInst_rii(unsigned MachineInstOpcode, 1302221345Sdim const TargetRegisterClass *RC, 1303221345Sdim unsigned Op0, bool Op0IsKill, 1304221345Sdim uint64_t Imm1, uint64_t Imm2) { 1305221345Sdim unsigned ResultReg = createResultReg(RC); 1306224145Sdim const MCInstrDesc &II = TII.get(MachineInstOpcode); 1307221345Sdim 1308221345Sdim if (II.getNumDefs() >= 1) 1309221345Sdim BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, II, ResultReg) 1310221345Sdim .addReg(Op0, Op0IsKill * RegState::Kill) 1311221345Sdim .addImm(Imm1) 1312221345Sdim .addImm(Imm2); 1313221345Sdim else { 1314221345Sdim BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, II) 1315221345Sdim .addReg(Op0, Op0IsKill * RegState::Kill) 1316221345Sdim .addImm(Imm1) 1317221345Sdim .addImm(Imm2); 1318221345Sdim BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, TII.get(TargetOpcode::COPY), 1319221345Sdim ResultReg).addReg(II.ImplicitDefs[0]); 1320221345Sdim } 1321221345Sdim return ResultReg; 1322221345Sdim} 1323221345Sdim 1324193323Sedunsigned FastISel::FastEmitInst_rf(unsigned MachineInstOpcode, 1325193323Sed const TargetRegisterClass *RC, 1326208599Srdivacky unsigned Op0, bool Op0IsKill, 1327208599Srdivacky const ConstantFP *FPImm) { 1328193323Sed unsigned ResultReg = createResultReg(RC); 1329224145Sdim const MCInstrDesc &II = TII.get(MachineInstOpcode); 1330193323Sed 1331193323Sed if (II.getNumDefs() >= 1) 1332210299Sed BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, II, ResultReg) 1333208599Srdivacky .addReg(Op0, Op0IsKill * RegState::Kill) 1334208599Srdivacky .addFPImm(FPImm); 1335193323Sed else { 1336210299Sed BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, II) 1337208599Srdivacky .addReg(Op0, Op0IsKill * RegState::Kill) 1338208599Srdivacky .addFPImm(FPImm); 1339210299Sed BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, TII.get(TargetOpcode::COPY), 1340210299Sed ResultReg).addReg(II.ImplicitDefs[0]); 1341193323Sed } 1342193323Sed return ResultReg; 1343193323Sed} 1344193323Sed 1345193323Sedunsigned FastISel::FastEmitInst_rri(unsigned MachineInstOpcode, 1346193323Sed const TargetRegisterClass *RC, 1347208599Srdivacky unsigned Op0, bool Op0IsKill, 1348208599Srdivacky unsigned Op1, bool Op1IsKill, 1349208599Srdivacky uint64_t Imm) { 1350193323Sed unsigned ResultReg = createResultReg(RC); 1351224145Sdim const MCInstrDesc &II = TII.get(MachineInstOpcode); 1352193323Sed 1353193323Sed if (II.getNumDefs() >= 1) 1354210299Sed BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, II, ResultReg) 1355208599Srdivacky .addReg(Op0, Op0IsKill * RegState::Kill) 1356208599Srdivacky .addReg(Op1, Op1IsKill * RegState::Kill) 1357208599Srdivacky .addImm(Imm); 1358193323Sed else { 1359210299Sed BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, II) 1360208599Srdivacky .addReg(Op0, Op0IsKill * RegState::Kill) 1361208599Srdivacky .addReg(Op1, Op1IsKill * RegState::Kill) 1362208599Srdivacky .addImm(Imm); 1363210299Sed BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, TII.get(TargetOpcode::COPY), 1364210299Sed ResultReg).addReg(II.ImplicitDefs[0]); 1365193323Sed } 1366193323Sed return ResultReg; 1367193323Sed} 1368193323Sed 1369245431Sdimunsigned FastISel::FastEmitInst_rrii(unsigned MachineInstOpcode, 1370245431Sdim const TargetRegisterClass *RC, 1371245431Sdim unsigned Op0, bool Op0IsKill, 1372245431Sdim unsigned Op1, bool Op1IsKill, 1373245431Sdim uint64_t Imm1, uint64_t Imm2) { 1374245431Sdim unsigned ResultReg = createResultReg(RC); 1375245431Sdim const MCInstrDesc &II = TII.get(MachineInstOpcode); 1376245431Sdim 1377245431Sdim if (II.getNumDefs() >= 1) 1378245431Sdim BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, II, ResultReg) 1379245431Sdim .addReg(Op0, Op0IsKill * RegState::Kill) 1380245431Sdim .addReg(Op1, Op1IsKill * RegState::Kill) 1381245431Sdim .addImm(Imm1).addImm(Imm2); 1382245431Sdim else { 1383245431Sdim BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, II) 1384245431Sdim .addReg(Op0, Op0IsKill * RegState::Kill) 1385245431Sdim .addReg(Op1, Op1IsKill * RegState::Kill) 1386245431Sdim .addImm(Imm1).addImm(Imm2); 1387245431Sdim BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, TII.get(TargetOpcode::COPY), 1388245431Sdim ResultReg).addReg(II.ImplicitDefs[0]); 1389245431Sdim } 1390245431Sdim return ResultReg; 1391245431Sdim} 1392245431Sdim 1393193323Sedunsigned FastISel::FastEmitInst_i(unsigned MachineInstOpcode, 1394193323Sed const TargetRegisterClass *RC, 1395193323Sed uint64_t Imm) { 1396193323Sed unsigned ResultReg = createResultReg(RC); 1397224145Sdim const MCInstrDesc &II = TII.get(MachineInstOpcode); 1398218893Sdim 1399193323Sed if (II.getNumDefs() >= 1) 1400210299Sed BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, II, ResultReg).addImm(Imm); 1401193323Sed else { 1402210299Sed BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, II).addImm(Imm); 1403210299Sed BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, TII.get(TargetOpcode::COPY), 1404210299Sed ResultReg).addReg(II.ImplicitDefs[0]); 1405193323Sed } 1406193323Sed return ResultReg; 1407193323Sed} 1408193323Sed 1409221345Sdimunsigned FastISel::FastEmitInst_ii(unsigned MachineInstOpcode, 1410221345Sdim const TargetRegisterClass *RC, 1411221345Sdim uint64_t Imm1, uint64_t Imm2) { 1412221345Sdim unsigned ResultReg = createResultReg(RC); 1413224145Sdim const MCInstrDesc &II = TII.get(MachineInstOpcode); 1414221345Sdim 1415221345Sdim if (II.getNumDefs() >= 1) 1416221345Sdim BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, II, ResultReg) 1417221345Sdim .addImm(Imm1).addImm(Imm2); 1418221345Sdim else { 1419221345Sdim BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, II).addImm(Imm1).addImm(Imm2); 1420221345Sdim BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, TII.get(TargetOpcode::COPY), 1421221345Sdim ResultReg).addReg(II.ImplicitDefs[0]); 1422221345Sdim } 1423221345Sdim return ResultReg; 1424221345Sdim} 1425221345Sdim 1426198090Srdivackyunsigned FastISel::FastEmitInst_extractsubreg(MVT RetVT, 1427208599Srdivacky unsigned Op0, bool Op0IsKill, 1428208599Srdivacky uint32_t Idx) { 1429193323Sed unsigned ResultReg = createResultReg(TLI.getRegClassFor(RetVT)); 1430210299Sed assert(TargetRegisterInfo::isVirtualRegister(Op0) && 1431210299Sed "Cannot yet extract from physregs"); 1432245431Sdim const TargetRegisterClass *RC = MRI.getRegClass(Op0); 1433245431Sdim MRI.constrainRegClass(Op0, TRI.getSubClassWithSubReg(RC, Idx)); 1434210299Sed BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, 1435210299Sed DL, TII.get(TargetOpcode::COPY), ResultReg) 1436210299Sed .addReg(Op0, getKillRegState(Op0IsKill), Idx); 1437193323Sed return ResultReg; 1438193323Sed} 1439193323Sed 1440193323Sed/// FastEmitZExtFromI1 - Emit MachineInstrs to compute the value of Op 1441193323Sed/// with all but the least significant bit set to zero. 1442208599Srdivackyunsigned FastISel::FastEmitZExtFromI1(MVT VT, unsigned Op0, bool Op0IsKill) { 1443208599Srdivacky return FastEmit_ri(VT, VT, ISD::AND, Op0, Op0IsKill, 1); 1444193323Sed} 1445207618Srdivacky 1446207618Srdivacky/// HandlePHINodesInSuccessorBlocks - Handle PHI nodes in successor blocks. 1447207618Srdivacky/// Emit code to ensure constants are copied into registers when needed. 1448207618Srdivacky/// Remember the virtual registers that need to be added to the Machine PHI 1449207618Srdivacky/// nodes as input. We cannot just directly add them, because expansion 1450207618Srdivacky/// might result in multiple MBB's for one BB. As such, the start of the 1451207618Srdivacky/// BB might correspond to a different MBB than the end. 1452207618Srdivackybool FastISel::HandlePHINodesInSuccessorBlocks(const BasicBlock *LLVMBB) { 1453207618Srdivacky const TerminatorInst *TI = LLVMBB->getTerminator(); 1454207618Srdivacky 1455207618Srdivacky SmallPtrSet<MachineBasicBlock *, 4> SuccsHandled; 1456210299Sed unsigned OrigNumPHINodesToUpdate = FuncInfo.PHINodesToUpdate.size(); 1457207618Srdivacky 1458207618Srdivacky // Check successor nodes' PHI nodes that expect a constant to be available 1459207618Srdivacky // from this block. 1460207618Srdivacky for (unsigned succ = 0, e = TI->getNumSuccessors(); succ != e; ++succ) { 1461207618Srdivacky const BasicBlock *SuccBB = TI->getSuccessor(succ); 1462207618Srdivacky if (!isa<PHINode>(SuccBB->begin())) continue; 1463210299Sed MachineBasicBlock *SuccMBB = FuncInfo.MBBMap[SuccBB]; 1464207618Srdivacky 1465207618Srdivacky // If this terminator has multiple identical successors (common for 1466207618Srdivacky // switches), only handle each succ once. 1467207618Srdivacky if (!SuccsHandled.insert(SuccMBB)) continue; 1468207618Srdivacky 1469207618Srdivacky MachineBasicBlock::iterator MBBI = SuccMBB->begin(); 1470207618Srdivacky 1471207618Srdivacky // At this point we know that there is a 1-1 correspondence between LLVM PHI 1472207618Srdivacky // nodes and Machine PHI nodes, but the incoming operands have not been 1473207618Srdivacky // emitted yet. 1474207618Srdivacky for (BasicBlock::const_iterator I = SuccBB->begin(); 1475207618Srdivacky const PHINode *PN = dyn_cast<PHINode>(I); ++I) { 1476208599Srdivacky 1477207618Srdivacky // Ignore dead phi's. 1478207618Srdivacky if (PN->use_empty()) continue; 1479207618Srdivacky 1480207618Srdivacky // Only handle legal types. Two interesting things to note here. First, 1481207618Srdivacky // by bailing out early, we may leave behind some dead instructions, 1482207618Srdivacky // since SelectionDAG's HandlePHINodesInSuccessorBlocks will insert its 1483221345Sdim // own moves. Second, this check is necessary because FastISel doesn't 1484210299Sed // use CreateRegs to create registers, so it always creates 1485207618Srdivacky // exactly one register for each non-void instruction. 1486207618Srdivacky EVT VT = TLI.getValueType(PN->getType(), /*AllowUnknown=*/true); 1487207618Srdivacky if (VT == MVT::Other || !TLI.isTypeLegal(VT)) { 1488235633Sdim // Handle integer promotions, though, because they're common and easy. 1489235633Sdim if (VT == MVT::i1 || VT == MVT::i8 || VT == MVT::i16) 1490207618Srdivacky VT = TLI.getTypeToTransformTo(LLVMBB->getContext(), VT); 1491207618Srdivacky else { 1492210299Sed FuncInfo.PHINodesToUpdate.resize(OrigNumPHINodesToUpdate); 1493207618Srdivacky return false; 1494207618Srdivacky } 1495207618Srdivacky } 1496207618Srdivacky 1497207618Srdivacky const Value *PHIOp = PN->getIncomingValueForBlock(LLVMBB); 1498207618Srdivacky 1499208599Srdivacky // Set the DebugLoc for the copy. Prefer the location of the operand 1500208599Srdivacky // if there is one; use the location of the PHI otherwise. 1501208599Srdivacky DL = PN->getDebugLoc(); 1502208599Srdivacky if (const Instruction *Inst = dyn_cast<Instruction>(PHIOp)) 1503208599Srdivacky DL = Inst->getDebugLoc(); 1504208599Srdivacky 1505207618Srdivacky unsigned Reg = getRegForValue(PHIOp); 1506207618Srdivacky if (Reg == 0) { 1507210299Sed FuncInfo.PHINodesToUpdate.resize(OrigNumPHINodesToUpdate); 1508207618Srdivacky return false; 1509207618Srdivacky } 1510210299Sed FuncInfo.PHINodesToUpdate.push_back(std::make_pair(MBBI++, Reg)); 1511208599Srdivacky DL = DebugLoc(); 1512207618Srdivacky } 1513207618Srdivacky } 1514207618Srdivacky 1515207618Srdivacky return true; 1516207618Srdivacky} 1517252723Sdim 1518252723Sdimbool FastISel::tryToFoldLoad(const LoadInst *LI, const Instruction *FoldInst) { 1519252723Sdim assert(LI->hasOneUse() && 1520252723Sdim "tryToFoldLoad expected a LoadInst with a single use"); 1521252723Sdim // We know that the load has a single use, but don't know what it is. If it 1522252723Sdim // isn't one of the folded instructions, then we can't succeed here. Handle 1523252723Sdim // this by scanning the single-use users of the load until we get to FoldInst. 1524252723Sdim unsigned MaxUsers = 6; // Don't scan down huge single-use chains of instrs. 1525252723Sdim 1526252723Sdim const Instruction *TheUser = LI->use_back(); 1527252723Sdim while (TheUser != FoldInst && // Scan up until we find FoldInst. 1528252723Sdim // Stay in the right block. 1529252723Sdim TheUser->getParent() == FoldInst->getParent() && 1530252723Sdim --MaxUsers) { // Don't scan too far. 1531252723Sdim // If there are multiple or no uses of this instruction, then bail out. 1532252723Sdim if (!TheUser->hasOneUse()) 1533252723Sdim return false; 1534252723Sdim 1535252723Sdim TheUser = TheUser->use_back(); 1536252723Sdim } 1537252723Sdim 1538252723Sdim // If we didn't find the fold instruction, then we failed to collapse the 1539252723Sdim // sequence. 1540252723Sdim if (TheUser != FoldInst) 1541252723Sdim return false; 1542252723Sdim 1543252723Sdim // Don't try to fold volatile loads. Target has to deal with alignment 1544252723Sdim // constraints. 1545252723Sdim if (LI->isVolatile()) 1546252723Sdim return false; 1547252723Sdim 1548252723Sdim // Figure out which vreg this is going into. If there is no assigned vreg yet 1549252723Sdim // then there actually was no reference to it. Perhaps the load is referenced 1550252723Sdim // by a dead instruction. 1551252723Sdim unsigned LoadReg = getRegForValue(LI); 1552252723Sdim if (LoadReg == 0) 1553252723Sdim return false; 1554252723Sdim 1555252723Sdim // We can't fold if this vreg has no uses or more than one use. Multiple uses 1556252723Sdim // may mean that the instruction got lowered to multiple MIs, or the use of 1557252723Sdim // the loaded value ended up being multiple operands of the result. 1558252723Sdim if (!MRI.hasOneUse(LoadReg)) 1559252723Sdim return false; 1560252723Sdim 1561252723Sdim MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(LoadReg); 1562252723Sdim MachineInstr *User = &*RI; 1563252723Sdim 1564252723Sdim // Set the insertion point properly. Folding the load can cause generation of 1565252723Sdim // other random instructions (like sign extends) for addressing modes; make 1566252723Sdim // sure they get inserted in a logical place before the new instruction. 1567252723Sdim FuncInfo.InsertPt = User; 1568252723Sdim FuncInfo.MBB = User->getParent(); 1569252723Sdim 1570252723Sdim // Ask the target to try folding the load. 1571252723Sdim return tryToFoldLoadIntoMI(User, RI.getOperandNo(), LI); 1572252723Sdim} 1573252723Sdim 1574263509Sdimbool FastISel::canFoldAddIntoGEP(const User *GEP, const Value *Add) { 1575263509Sdim // Must be an add. 1576263509Sdim if (!isa<AddOperator>(Add)) 1577263509Sdim return false; 1578263509Sdim // Type size needs to match. 1579263509Sdim if (TD.getTypeSizeInBits(GEP->getType()) != 1580263509Sdim TD.getTypeSizeInBits(Add->getType())) 1581263509Sdim return false; 1582263509Sdim // Must be in the same basic block. 1583263509Sdim if (isa<Instruction>(Add) && 1584263509Sdim FuncInfo.MBBMap[cast<Instruction>(Add)->getParent()] != FuncInfo.MBB) 1585263509Sdim return false; 1586263509Sdim // Must have a constant operand. 1587263509Sdim return isa<ConstantInt>(cast<AddOperator>(Add)->getOperand(1)); 1588263509Sdim} 1589252723Sdim 1590