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 42234353Sdim#define DEBUG_TYPE "isel" 43249423Sdim#include "llvm/CodeGen/FastISel.h" 44263508Sdim#include "llvm/ADT/Optional.h" 45249423Sdim#include "llvm/ADT/Statistic.h" 46249423Sdim#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" 52249423Sdim#include "llvm/DebugInfo.h" 53249423Sdim#include "llvm/IR/DataLayout.h" 54249423Sdim#include "llvm/IR/Function.h" 55249423Sdim#include "llvm/IR/GlobalVariable.h" 56249423Sdim#include "llvm/IR/Instructions.h" 57249423Sdim#include "llvm/IR/IntrinsicInst.h" 58249423Sdim#include "llvm/IR/Operator.h" 59249423Sdim#include "llvm/Support/Debug.h" 60249423Sdim#include "llvm/Support/ErrorHandling.h" 61193323Sed#include "llvm/Target/TargetInstrInfo.h" 62239462Sdim#include "llvm/Target/TargetLibraryInfo.h" 63193323Sed#include "llvm/Target/TargetLowering.h" 64193323Sed#include "llvm/Target/TargetMachine.h" 65193323Sedusing namespace llvm; 66193323Sed 67234353SdimSTATISTIC(NumFastIselSuccessIndependent, "Number of insts selected by " 68234353Sdim "target-independent selector"); 69234353SdimSTATISTIC(NumFastIselSuccessTarget, "Number of insts selected by " 70234353Sdim "target-specific selector"); 71234353SdimSTATISTIC(NumFastIselDead, "Number of dead insts removed on failure"); 72234353Sdim 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 79253042Sdim // Instructions are appended to FuncInfo.MBB. If the basic block already 80253042Sdim // contains labels or copies, use the last instruction as the last local 81253042Sdim // value. 82226633Sdim EmitStartPt = 0; 83253042Sdim if (!FuncInfo.MBB->empty()) 84253042Sdim EmitStartPt = &FuncInfo.MBB->back(); 85226633Sdim LastLocalValue = EmitStartPt; 86210299Sed} 87210299Sed 88249423Sdimbool FastISel::LowerArguments() { 89249423Sdim if (!FuncInfo.CanLowerReturn) 90249423Sdim // Fallback to SDISel argument lowering code to deal with sret pointer 91249423Sdim // parameter. 92249423Sdim return false; 93263508Sdim 94249423Sdim if (!FastLowerArguments()) 95249423Sdim return false; 96249423Sdim 97263508Sdim // Enter arguments into ValueMap for uses in non-entry BBs. 98249423Sdim for (Function::const_arg_iterator I = FuncInfo.Fn->arg_begin(), 99249423Sdim E = FuncInfo.Fn->arg_end(); I != E; ++I) { 100263508Sdim DenseMap<const Value *, unsigned>::iterator VI = LocalValueMap.find(I); 101263508Sdim assert(VI != LocalValueMap.end() && "Missed an argument?"); 102263508Sdim FuncInfo.ValueMap[I] = VI->second; 103249423Sdim } 104249423Sdim return true; 105249423Sdim} 106249423Sdim 107226633Sdimvoid FastISel::flushLocalValueMap() { 108226633Sdim LocalValueMap.clear(); 109226633Sdim LastLocalValue = EmitStartPt; 110226633Sdim recomputeInsertPt(); 111226633Sdim} 112226633Sdim 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 125234353Sdim // GEPs with all zero indices are trivially coalesced by fast-isel. 126234353Sdim if (const GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(I)) 127234353Sdim if (GEP->hasAllZeroIndices() && !hasTrivialKill(GEP->getOperand(0))) 128234353Sdim return false; 129234353Sdim 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 157234353Sdim // Look up the value to see if we already have a register for it. 158234353Sdim 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, 213234353Sdim APFloat::rmTowardZero, &isExact); 214193323Sed if (isExact) { 215226633Sdim 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 324234353Sdimvoid FastISel::removeDeadCode(MachineBasicBlock::iterator I, 325234353Sdim MachineBasicBlock::iterator E) { 326234353Sdim assert (I && E && std::distance(I, E) > 0 && "Invalid iterator!"); 327234353Sdim while (I != E) { 328234353Sdim MachineInstr *Dead = &*I; 329234353Sdim ++I; 330234353Sdim Dead->eraseFromParent(); 331234353Sdim ++NumFastIselDead; 332234353Sdim } 333234353Sdim recomputeInsertPt(); 334234353Sdim} 335234353Sdim 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 416234353Sdim // Transform "urem x, pow2" -> "and x, pow2-1". 417234353Sdim if (ISDOpcode == ISD::UREM && isa<BinaryOperator>(I) && 418234353Sdim isPowerOf2_64(Imm)) { 419234353Sdim --Imm; 420234353Sdim ISDOpcode = ISD::AND; 421234353Sdim } 422234353Sdim 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 473234353Sdim // Keep a running tab of the total offset to coalesce multiple N = N + Offset 474234353Sdim // into a single N = N + TotalOffset. 475234353Sdim uint64_t TotalOffs = 0; 476234353Sdim // FIXME: What's a good SWAG number for MaxOffs? 477234353Sdim uint64_t MaxOffs = 2048; 478226633Sdim 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; 483226633Sdim if (StructType *StTy = dyn_cast<StructType>(Ty)) { 484193323Sed unsigned Field = cast<ConstantInt>(Idx)->getZExtValue(); 485193323Sed if (Field) { 486193323Sed // N = N + Offset 487234353Sdim TotalOffs += TD.getStructLayout(StTy)->getElementOffset(Field); 488234353Sdim if (TotalOffs >= MaxOffs) { 489234353Sdim N = FastEmit_ri_(VT, ISD::ADD, N, NIsKill, TotalOffs, VT); 490234353Sdim if (N == 0) 491234353Sdim // Unhandled operand. Halt "fast" selection and bail. 492234353Sdim return false; 493234353Sdim NIsKill = true; 494234353Sdim TotalOffs = 0; 495234353Sdim } 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; 504234353Sdim // N = N + Offset 505239462Sdim TotalOffs += 506193323Sed TD.getTypeAllocSize(Ty)*cast<ConstantInt>(CI)->getSExtValue(); 507234353Sdim if (TotalOffs >= MaxOffs) { 508234353Sdim N = FastEmit_ri_(VT, ISD::ADD, N, NIsKill, TotalOffs, VT); 509234353Sdim if (N == 0) 510234353Sdim // Unhandled operand. Halt "fast" selection and bail. 511234353Sdim return false; 512234353Sdim NIsKill = true; 513234353Sdim TotalOffs = 0; 514234353Sdim } 515234353Sdim continue; 516234353Sdim } 517234353Sdim if (TotalOffs) { 518234353Sdim 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; 523234353Sdim 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 } 548234353Sdim if (TotalOffs) { 549234353Sdim N = FastEmit_ri_(VT, ISD::ADD, N, NIsKill, TotalOffs, VT); 550234353Sdim if (N == 0) 551234353Sdim // Unhandled operand. Halt "fast" selection and bail. 552234353Sdim return false; 553234353Sdim } 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. 564226633Sdim 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 582234353Sdim MachineModuleInfo &MMI = FuncInfo.MF->getMMI(); 583234353Sdim ComputeUsesVAFloatArgument(*Call, &MMI); 584234353Sdim 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; 591234353Sdim // At -O0 we don't care about the lifetime intrinsics. 592234353Sdim case Intrinsic::lifetime_start: 593234353Sdim case Intrinsic::lifetime_end: 594239462Sdim // The donothing intrinsic does, well, nothing. 595239462Sdim case Intrinsic::donothing: 596234353Sdim return true; 597239462Sdim 598193323Sed case Intrinsic::dbg_declare: { 599221345Sdim const DbgDeclareInst *DI = cast<DbgDeclareInst>(Call); 600263508Sdim DIVariable DIVar(DI->getVariable()); 601263508Sdim assert((!DIVar || DIVar.isVariable()) && 602263508Sdim "Variable in DbgDeclareInst should be either null or a DIVariable."); 603263508Sdim if (!DIVar || 604234353Sdim !FuncInfo.MF->getMMI().hasDebugInfo()) { 605234353Sdim DEBUG(dbgs() << "Dropping debug info for " << *DI << "\n"); 606195340Sed return true; 607234353Sdim } 608195340Sed 609207618Srdivacky const Value *Address = DI->getAddress(); 610234353Sdim if (!Address || isa<UndefValue>(Address)) { 611234353Sdim DEBUG(dbgs() << "Dropping debug info for " << *DI << "\n"); 612203954Srdivacky return true; 613234353Sdim } 614218893Sdim 615218893Sdim unsigned Offset = 0; 616263508Sdim Optional<MachineOperand> Op; 617263508Sdim if (const Argument *Arg = dyn_cast<Argument>(Address)) 618226633Sdim // Some arguments' frame index is recorded during argument lowering. 619226633Sdim Offset = FuncInfo.getArgumentFrameIndex(Arg); 620263508Sdim if (Offset) 621263508Sdim Op = MachineOperand::CreateFI(Offset); 622263508Sdim if (!Op) 623263508Sdim if (unsigned Reg = lookUpRegForValue(Address)) 624263508Sdim Op = MachineOperand::CreateReg(Reg, false); 625218893Sdim 626234353Sdim // If we have a VLA that has a "use" in a metadata node that's then used 627234353Sdim // here but it has no other uses, then we have a problem. E.g., 628234353Sdim // 629234353Sdim // int foo (const int *x) { 630234353Sdim // char a[*x]; 631234353Sdim // return 0; 632234353Sdim // } 633234353Sdim // 634234353Sdim // If we assign 'a' a vreg and fast isel later on has to use the selection 635234353Sdim // DAG isel, it will want to copy the value to the vreg. However, there are 636234353Sdim // no uses, which goes counter to what selection DAG isel expects. 637263508Sdim if (!Op && !Address->use_empty() && isa<Instruction>(Address) && 638234353Sdim (!isa<AllocaInst>(Address) || 639234353Sdim !FuncInfo.StaticAllocaMap.count(cast<AllocaInst>(Address)))) 640263508Sdim Op = MachineOperand::CreateReg(FuncInfo.InitializeRegForValue(Address), 641263508Sdim false); 642234353Sdim 643263508Sdim if (Op) { 644263508Sdim if (Op->isReg()) { 645263508Sdim Op->setIsDebug(true); 646263508Sdim BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, 647263508Sdim TII.get(TargetOpcode::DBG_VALUE), false, Op->getReg(), 0, 648263508Sdim DI->getVariable()); 649263508Sdim } else 650263508Sdim BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, 651263508Sdim TII.get(TargetOpcode::DBG_VALUE)) 652263508Sdim .addOperand(*Op) 653263508Sdim .addImm(0) 654263508Sdim .addMetadata(DI->getVariable()); 655263508Sdim } else { 656234353Sdim // We can't yet handle anything else here because it would require 657234353Sdim // generating code, thus altering codegen because of debug info. 658263508Sdim DEBUG(dbgs() << "Dropping debug info for " << *DI << "\n"); 659263508Sdim } 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()); 678239462Sdim 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)) { 687263508Sdim // FIXME: This does not handle register-indirect values at offset 0. 688263508Sdim bool IsIndirect = DI->getOffset() != 0; 689263508Sdim BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, II, IsIndirect, 690263508Sdim 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. 694263508Sdim 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 } 708249423Sdim case Intrinsic::expect: { 709249423Sdim unsigned ResultReg = getRegForValue(Call->getArgOperand(0)); 710249423Sdim if (ResultReg == 0) 711249423Sdim return false; 712249423Sdim UpdateValueMap(Call, ResultReg); 713249423Sdim return true; 714223017Sdim } 715249423Sdim } 716207618Srdivacky 717226633Sdim // Usually, it does not make sense to initialize a value, 718226633Sdim // make an unrelated function call and use the value, because 719226633Sdim // it tends to be spilled on the stack. So, we move the pointer 720226633Sdim // to the last local value to the beginning of the block, so that 721226633Sdim // all the values which have already been materialized, 722226633Sdim // appear after the call. It also makes sense to skip intrinsics 723226633Sdim // since they tend to be inlined. 724249423Sdim if (!isa<IntrinsicInst>(Call)) 725226633Sdim flushLocalValueMap(); 726226633Sdim 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. 777249423Sdim EVT SrcEVT = TLI.getValueType(I->getOperand(0)->getType()); 778249423Sdim EVT DstEVT = TLI.getValueType(I->getType()); 779249423Sdim if (SrcEVT == MVT::Other || DstEVT == MVT::Other || 780249423Sdim !TLI.isTypeLegal(SrcEVT) || !TLI.isTypeLegal(DstEVT)) 781193323Sed // Unhandled type. Halt "fast" selection and bail. 782193323Sed return false; 783218893Sdim 784249423Sdim MVT SrcVT = SrcEVT.getSimpleVT(); 785249423Sdim 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; 795249423Sdim if (SrcVT == DstVT) { 796234353Sdim const TargetRegisterClass* SrcClass = TLI.getRegClassFor(SrcVT); 797234353Sdim 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) 808249423Sdim 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 827234353Sdim MachineBasicBlock::iterator SavedInsertPt = FuncInfo.InsertPt; 828234353Sdim 829239462Sdim // As a special case, don't handle calls to builtin library functions that 830239462Sdim // may be translated directly to target instructions. 831239462Sdim if (const CallInst *Call = dyn_cast<CallInst>(I)) { 832239462Sdim const Function *F = Call->getCalledFunction(); 833239462Sdim LibFunc::Func Func; 834239462Sdim if (F && !F->hasLocalLinkage() && F->hasName() && 835239462Sdim LibInfo->getLibFunc(F->getName(), Func) && 836239462Sdim LibInfo->hasOptimizedCodeGen(Func)) 837239462Sdim return false; 838239462Sdim } 839239462Sdim 840200581Srdivacky // First, try doing target-independent selection. 841207618Srdivacky if (SelectOperator(I, I->getOpcode())) { 842234353Sdim ++NumFastIselSuccessIndependent; 843207618Srdivacky DL = DebugLoc(); 844200581Srdivacky return true; 845207618Srdivacky } 846239462Sdim // Remove dead code. However, ignore call instructions since we've flushed 847234353Sdim // the local value map and recomputed the insert point. 848234353Sdim if (!isa<CallInst>(I)) { 849234353Sdim recomputeInsertPt(); 850234353Sdim if (SavedInsertPt != FuncInfo.InsertPt) 851234353Sdim removeDeadCode(FuncInfo.InsertPt, SavedInsertPt); 852234353Sdim } 853200581Srdivacky 854200581Srdivacky // Next, try calling the target to attempt to handle the instruction. 855234353Sdim SavedInsertPt = FuncInfo.InsertPt; 856207618Srdivacky if (TargetSelectInstruction(I)) { 857234353Sdim ++NumFastIselSuccessTarget; 858207618Srdivacky DL = DebugLoc(); 859200581Srdivacky return true; 860207618Srdivacky } 861234353Sdim // Check for dead code and remove as necessary. 862234353Sdim recomputeInsertPt(); 863234353Sdim if (SavedInsertPt != FuncInfo.InsertPt) 864234353Sdim 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) { 875234353Sdim 876249423Sdim if (FuncInfo.MBB->getBasicBlock()->size() > 1 && 877249423Sdim FuncInfo.MBB->isLayoutSuccessor(MSucc)) { 878234353Sdim // For more accurate line information if this is the only instruction 879234353Sdim // in the block then emit it, otherwise we have the unconditional 880234353Sdim // 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); 951226633Sdim 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 1092239462SdimFastISel::FastISel(FunctionLoweringInfo &funcInfo, 1093239462Sdim 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()), 1099243830Sdim TD(*TM.getDataLayout()), 1100193323Sed TII(*TM.getInstrInfo()), 1101208599Srdivacky TLI(*TM.getTargetLowering()), 1102239462Sdim TRI(*TM.getRegisterInfo()), 1103239462Sdim LibInfo(libInfo) { 1104193323Sed} 1105193323Sed 1106193323SedFastISel::~FastISel() {} 1107193323Sed 1108249423Sdimbool FastISel::FastLowerArguments() { 1109249423Sdim return false; 1110249423Sdim} 1111249423Sdim 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. 1192226633Sdim IntegerType *ITy = IntegerType::get(FuncInfo.Fn->getContext(), 1193221345Sdim VT.getSizeInBits()); 1194221345Sdim MaterialReg = getRegForValue(ConstantInt::get(ITy, Imm)); 1195249423Sdim assert (MaterialReg != 0 && "Unable to materialize imm."); 1196249423Sdim 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 1369239462Sdimunsigned FastISel::FastEmitInst_rrii(unsigned MachineInstOpcode, 1370239462Sdim const TargetRegisterClass *RC, 1371239462Sdim unsigned Op0, bool Op0IsKill, 1372239462Sdim unsigned Op1, bool Op1IsKill, 1373239462Sdim uint64_t Imm1, uint64_t Imm2) { 1374239462Sdim unsigned ResultReg = createResultReg(RC); 1375239462Sdim const MCInstrDesc &II = TII.get(MachineInstOpcode); 1376239462Sdim 1377239462Sdim if (II.getNumDefs() >= 1) 1378239462Sdim BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, II, ResultReg) 1379239462Sdim .addReg(Op0, Op0IsKill * RegState::Kill) 1380239462Sdim .addReg(Op1, Op1IsKill * RegState::Kill) 1381239462Sdim .addImm(Imm1).addImm(Imm2); 1382239462Sdim else { 1383239462Sdim BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, II) 1384239462Sdim .addReg(Op0, Op0IsKill * RegState::Kill) 1385239462Sdim .addReg(Op1, Op1IsKill * RegState::Kill) 1386239462Sdim .addImm(Imm1).addImm(Imm2); 1387239462Sdim BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DL, TII.get(TargetOpcode::COPY), 1388239462Sdim ResultReg).addReg(II.ImplicitDefs[0]); 1389239462Sdim } 1390239462Sdim return ResultReg; 1391239462Sdim} 1392239462Sdim 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"); 1432239462Sdim const TargetRegisterClass *RC = MRI.getRegClass(Op0); 1433239462Sdim 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)) { 1488234353Sdim // Handle integer promotions, though, because they're common and easy. 1489234353Sdim 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} 1517251662Sdim 1518251662Sdimbool FastISel::tryToFoldLoad(const LoadInst *LI, const Instruction *FoldInst) { 1519251662Sdim assert(LI->hasOneUse() && 1520251662Sdim "tryToFoldLoad expected a LoadInst with a single use"); 1521251662Sdim // We know that the load has a single use, but don't know what it is. If it 1522251662Sdim // isn't one of the folded instructions, then we can't succeed here. Handle 1523251662Sdim // this by scanning the single-use users of the load until we get to FoldInst. 1524251662Sdim unsigned MaxUsers = 6; // Don't scan down huge single-use chains of instrs. 1525251662Sdim 1526251662Sdim const Instruction *TheUser = LI->use_back(); 1527251662Sdim while (TheUser != FoldInst && // Scan up until we find FoldInst. 1528251662Sdim // Stay in the right block. 1529251662Sdim TheUser->getParent() == FoldInst->getParent() && 1530251662Sdim --MaxUsers) { // Don't scan too far. 1531251662Sdim // If there are multiple or no uses of this instruction, then bail out. 1532251662Sdim if (!TheUser->hasOneUse()) 1533251662Sdim return false; 1534251662Sdim 1535251662Sdim TheUser = TheUser->use_back(); 1536251662Sdim } 1537251662Sdim 1538251662Sdim // If we didn't find the fold instruction, then we failed to collapse the 1539251662Sdim // sequence. 1540251662Sdim if (TheUser != FoldInst) 1541251662Sdim return false; 1542251662Sdim 1543251662Sdim // Don't try to fold volatile loads. Target has to deal with alignment 1544251662Sdim // constraints. 1545251662Sdim if (LI->isVolatile()) 1546251662Sdim return false; 1547251662Sdim 1548251662Sdim // Figure out which vreg this is going into. If there is no assigned vreg yet 1549251662Sdim // then there actually was no reference to it. Perhaps the load is referenced 1550251662Sdim // by a dead instruction. 1551251662Sdim unsigned LoadReg = getRegForValue(LI); 1552251662Sdim if (LoadReg == 0) 1553251662Sdim return false; 1554251662Sdim 1555251662Sdim // We can't fold if this vreg has no uses or more than one use. Multiple uses 1556251662Sdim // may mean that the instruction got lowered to multiple MIs, or the use of 1557251662Sdim // the loaded value ended up being multiple operands of the result. 1558251662Sdim if (!MRI.hasOneUse(LoadReg)) 1559251662Sdim return false; 1560251662Sdim 1561251662Sdim MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(LoadReg); 1562251662Sdim MachineInstr *User = &*RI; 1563251662Sdim 1564251662Sdim // Set the insertion point properly. Folding the load can cause generation of 1565251662Sdim // other random instructions (like sign extends) for addressing modes; make 1566251662Sdim // sure they get inserted in a logical place before the new instruction. 1567251662Sdim FuncInfo.InsertPt = User; 1568251662Sdim FuncInfo.MBB = User->getParent(); 1569251662Sdim 1570251662Sdim // Ask the target to try folding the load. 1571251662Sdim return tryToFoldLoadIntoMI(User, RI.getOperandNo(), LI); 1572251662Sdim} 1573251662Sdim 1574263508Sdimbool FastISel::canFoldAddIntoGEP(const User *GEP, const Value *Add) { 1575263508Sdim // Must be an add. 1576263508Sdim if (!isa<AddOperator>(Add)) 1577263508Sdim return false; 1578263508Sdim // Type size needs to match. 1579263508Sdim if (TD.getTypeSizeInBits(GEP->getType()) != 1580263508Sdim TD.getTypeSizeInBits(Add->getType())) 1581263508Sdim return false; 1582263508Sdim // Must be in the same basic block. 1583263508Sdim if (isa<Instruction>(Add) && 1584263508Sdim FuncInfo.MBBMap[cast<Instruction>(Add)->getParent()] != FuncInfo.MBB) 1585263508Sdim return false; 1586263508Sdim // Must have a constant operand. 1587263508Sdim return isa<ConstantInt>(cast<AddOperator>(Add)->getOperand(1)); 1588263508Sdim} 1589251662Sdim 1590