LLVM API Documentation
00001 ///===-- FastISel.cpp - Implementation of the FastISel class --------------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file contains the implementation of the FastISel class. 00011 // 00012 // "Fast" instruction selection is designed to emit very poor code quickly. 00013 // Also, it is not designed to be able to do much lowering, so most illegal 00014 // types (e.g. i64 on 32-bit targets) and operations are not supported. It is 00015 // also not intended to be able to do much optimization, except in a few cases 00016 // where doing optimizations reduces overall compile time. For example, folding 00017 // constants into immediate fields is often done, because it's cheap and it 00018 // reduces the number of instructions later phases have to examine. 00019 // 00020 // "Fast" instruction selection is able to fail gracefully and transfer 00021 // control to the SelectionDAG selector for operations that it doesn't 00022 // support. In many cases, this allows us to avoid duplicating a lot of 00023 // the complicated lowering logic that SelectionDAG currently has. 00024 // 00025 // The intended use for "fast" instruction selection is "-O0" mode 00026 // compilation, where the quality of the generated code is irrelevant when 00027 // weighed against the speed at which the code can be generated. Also, 00028 // at -O0, the LLVM optimizers are not running, and this makes the 00029 // compile time of codegen a much higher portion of the overall compile 00030 // time. Despite its limitations, "fast" instruction selection is able to 00031 // handle enough code on its own to provide noticeable overall speedups 00032 // in -O0 compiles. 00033 // 00034 // Basic operations are supported in a target-independent way, by reading 00035 // the same instruction descriptions that the SelectionDAG selector reads, 00036 // and identifying simple arithmetic operations that can be directly selected 00037 // from simple operators. More complicated operations currently require 00038 // target-specific code. 00039 // 00040 //===----------------------------------------------------------------------===// 00041 00042 #include "llvm/Function.h" 00043 #include "llvm/GlobalVariable.h" 00044 #include "llvm/Instructions.h" 00045 #include "llvm/IntrinsicInst.h" 00046 #include "llvm/CodeGen/FastISel.h" 00047 #include "llvm/CodeGen/MachineInstrBuilder.h" 00048 #include "llvm/CodeGen/MachineModuleInfo.h" 00049 #include "llvm/CodeGen/MachineRegisterInfo.h" 00050 #include "llvm/CodeGen/DwarfWriter.h" 00051 #include "llvm/Analysis/DebugInfo.h" 00052 #include "llvm/Target/TargetData.h" 00053 #include "llvm/Target/TargetInstrInfo.h" 00054 #include "llvm/Target/TargetLowering.h" 00055 #include "llvm/Target/TargetMachine.h" 00056 #include "SelectionDAGBuild.h" 00057 using namespace llvm; 00058 00059 unsigned FastISel::getRegForValue(Value *V) { 00060 EVT RealVT = TLI.getValueType(V->getType(), /*AllowUnknown=*/true); 00061 // Don't handle non-simple values in FastISel. 00062 if (!RealVT.isSimple()) 00063 return 0; 00064 00065 // Ignore illegal types. We must do this before looking up the value 00066 // in ValueMap because Arguments are given virtual registers regardless 00067 // of whether FastISel can handle them. 00068 MVT VT = RealVT.getSimpleVT(); 00069 if (!TLI.isTypeLegal(VT)) { 00070 // Promote MVT::i1 to a legal type though, because it's common and easy. 00071 if (VT == MVT::i1) 00072 VT = TLI.getTypeToTransformTo(V->getContext(), VT).getSimpleVT(); 00073 else 00074 return 0; 00075 } 00076 00077 // Look up the value to see if we already have a register for it. We 00078 // cache values defined by Instructions across blocks, and other values 00079 // only locally. This is because Instructions already have the SSA 00080 // def-dominatess-use requirement enforced. 00081 if (ValueMap.count(V)) 00082 return ValueMap[V]; 00083 unsigned Reg = LocalValueMap[V]; 00084 if (Reg != 0) 00085 return Reg; 00086 00087 if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) { 00088 if (CI->getValue().getActiveBits() <= 64) 00089 Reg = FastEmit_i(VT, VT, ISD::Constant, CI->getZExtValue()); 00090 } else if (isa<AllocaInst>(V)) { 00091 Reg = TargetMaterializeAlloca(cast<AllocaInst>(V)); 00092 } else if (isa<ConstantPointerNull>(V)) { 00093 // Translate this as an integer zero so that it can be 00094 // local-CSE'd with actual integer zeros. 00095 Reg = 00096 getRegForValue(Constant::getNullValue(TD.getIntPtrType(V->getContext()))); 00097 } else if (ConstantFP *CF = dyn_cast<ConstantFP>(V)) { 00098 Reg = FastEmit_f(VT, VT, ISD::ConstantFP, CF); 00099 00100 if (!Reg) { 00101 const APFloat &Flt = CF->getValueAPF(); 00102 EVT IntVT = TLI.getPointerTy(); 00103 00104 uint64_t x[2]; 00105 uint32_t IntBitWidth = IntVT.getSizeInBits(); 00106 bool isExact; 00107 (void) Flt.convertToInteger(x, IntBitWidth, /*isSigned=*/true, 00108 APFloat::rmTowardZero, &isExact); 00109 if (isExact) { 00110 APInt IntVal(IntBitWidth, 2, x); 00111 00112 unsigned IntegerReg = 00113 getRegForValue(ConstantInt::get(V->getContext(), IntVal)); 00114 if (IntegerReg != 0) 00115 Reg = FastEmit_r(IntVT.getSimpleVT(), VT, ISD::SINT_TO_FP, IntegerReg); 00116 } 00117 } 00118 } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) { 00119 if (!SelectOperator(CE, CE->getOpcode())) return 0; 00120 Reg = LocalValueMap[CE]; 00121 } else if (isa<UndefValue>(V)) { 00122 Reg = createResultReg(TLI.getRegClassFor(VT)); 00123 BuildMI(MBB, DL, TII.get(TargetInstrInfo::IMPLICIT_DEF), Reg); 00124 } 00125 00126 // If target-independent code couldn't handle the value, give target-specific 00127 // code a try. 00128 if (!Reg && isa<Constant>(V)) 00129 Reg = TargetMaterializeConstant(cast<Constant>(V)); 00130 00131 // Don't cache constant materializations in the general ValueMap. 00132 // To do so would require tracking what uses they dominate. 00133 if (Reg != 0) 00134 LocalValueMap[V] = Reg; 00135 return Reg; 00136 } 00137 00138 unsigned FastISel::lookUpRegForValue(Value *V) { 00139 // Look up the value to see if we already have a register for it. We 00140 // cache values defined by Instructions across blocks, and other values 00141 // only locally. This is because Instructions already have the SSA 00142 // def-dominatess-use requirement enforced. 00143 if (ValueMap.count(V)) 00144 return ValueMap[V]; 00145 return LocalValueMap[V]; 00146 } 00147 00148 /// UpdateValueMap - Update the value map to include the new mapping for this 00149 /// instruction, or insert an extra copy to get the result in a previous 00150 /// determined register. 00151 /// NOTE: This is only necessary because we might select a block that uses 00152 /// a value before we select the block that defines the value. It might be 00153 /// possible to fix this by selecting blocks in reverse postorder. 00154 unsigned FastISel::UpdateValueMap(Value* I, unsigned Reg) { 00155 if (!isa<Instruction>(I)) { 00156 LocalValueMap[I] = Reg; 00157 return Reg; 00158 } 00159 00160 unsigned &AssignedReg = ValueMap[I]; 00161 if (AssignedReg == 0) 00162 AssignedReg = Reg; 00163 else if (Reg != AssignedReg) { 00164 const TargetRegisterClass *RegClass = MRI.getRegClass(Reg); 00165 TII.copyRegToReg(*MBB, MBB->end(), AssignedReg, 00166 Reg, RegClass, RegClass); 00167 } 00168 return AssignedReg; 00169 } 00170 00171 unsigned FastISel::getRegForGEPIndex(Value *Idx) { 00172 unsigned IdxN = getRegForValue(Idx); 00173 if (IdxN == 0) 00174 // Unhandled operand. Halt "fast" selection and bail. 00175 return 0; 00176 00177 // If the index is smaller or larger than intptr_t, truncate or extend it. 00178 MVT PtrVT = TLI.getPointerTy(); 00179 EVT IdxVT = EVT::getEVT(Idx->getType(), /*HandleUnknown=*/false); 00180 if (IdxVT.bitsLT(PtrVT)) 00181 IdxN = FastEmit_r(IdxVT.getSimpleVT(), PtrVT, ISD::SIGN_EXTEND, IdxN); 00182 else if (IdxVT.bitsGT(PtrVT)) 00183 IdxN = FastEmit_r(IdxVT.getSimpleVT(), PtrVT, ISD::TRUNCATE, IdxN); 00184 return IdxN; 00185 } 00186 00187 /// SelectBinaryOp - Select and emit code for a binary operator instruction, 00188 /// which has an opcode which directly corresponds to the given ISD opcode. 00189 /// 00190 bool FastISel::SelectBinaryOp(User *I, ISD::NodeType ISDOpcode) { 00191 EVT VT = EVT::getEVT(I->getType(), /*HandleUnknown=*/true); 00192 if (VT == MVT::Other || !VT.isSimple()) 00193 // Unhandled type. Halt "fast" selection and bail. 00194 return false; 00195 00196 // We only handle legal types. For example, on x86-32 the instruction 00197 // selector contains all of the 64-bit instructions from x86-64, 00198 // under the assumption that i64 won't be used if the target doesn't 00199 // support it. 00200 if (!TLI.isTypeLegal(VT)) { 00201 // MVT::i1 is special. Allow AND, OR, or XOR because they 00202 // don't require additional zeroing, which makes them easy. 00203 if (VT == MVT::i1 && 00204 (ISDOpcode == ISD::AND || ISDOpcode == ISD::OR || 00205 ISDOpcode == ISD::XOR)) 00206 VT = TLI.getTypeToTransformTo(I->getContext(), VT); 00207 else 00208 return false; 00209 } 00210 00211 unsigned Op0 = getRegForValue(I->getOperand(0)); 00212 if (Op0 == 0) 00213 // Unhandled operand. Halt "fast" selection and bail. 00214 return false; 00215 00216 // Check if the second operand is a constant and handle it appropriately. 00217 if (ConstantInt *CI = dyn_cast<ConstantInt>(I->getOperand(1))) { 00218 unsigned ResultReg = FastEmit_ri(VT.getSimpleVT(), VT.getSimpleVT(), 00219 ISDOpcode, Op0, CI->getZExtValue()); 00220 if (ResultReg != 0) { 00221 // We successfully emitted code for the given LLVM Instruction. 00222 UpdateValueMap(I, ResultReg); 00223 return true; 00224 } 00225 } 00226 00227 // Check if the second operand is a constant float. 00228 if (ConstantFP *CF = dyn_cast<ConstantFP>(I->getOperand(1))) { 00229 unsigned ResultReg = FastEmit_rf(VT.getSimpleVT(), VT.getSimpleVT(), 00230 ISDOpcode, Op0, CF); 00231 if (ResultReg != 0) { 00232 // We successfully emitted code for the given LLVM Instruction. 00233 UpdateValueMap(I, ResultReg); 00234 return true; 00235 } 00236 } 00237 00238 unsigned Op1 = getRegForValue(I->getOperand(1)); 00239 if (Op1 == 0) 00240 // Unhandled operand. Halt "fast" selection and bail. 00241 return false; 00242 00243 // Now we have both operands in registers. Emit the instruction. 00244 unsigned ResultReg = FastEmit_rr(VT.getSimpleVT(), VT.getSimpleVT(), 00245 ISDOpcode, Op0, Op1); 00246 if (ResultReg == 0) 00247 // Target-specific code wasn't able to find a machine opcode for 00248 // the given ISD opcode and type. Halt "fast" selection and bail. 00249 return false; 00250 00251 // We successfully emitted code for the given LLVM Instruction. 00252 UpdateValueMap(I, ResultReg); 00253 return true; 00254 } 00255 00256 bool FastISel::SelectGetElementPtr(User *I) { 00257 unsigned N = getRegForValue(I->getOperand(0)); 00258 if (N == 0) 00259 // Unhandled operand. Halt "fast" selection and bail. 00260 return false; 00261 00262 const Type *Ty = I->getOperand(0)->getType(); 00263 MVT VT = TLI.getPointerTy(); 00264 for (GetElementPtrInst::op_iterator OI = I->op_begin()+1, E = I->op_end(); 00265 OI != E; ++OI) { 00266 Value *Idx = *OI; 00267 if (const StructType *StTy = dyn_cast<StructType>(Ty)) { 00268 unsigned Field = cast<ConstantInt>(Idx)->getZExtValue(); 00269 if (Field) { 00270 // N = N + Offset 00271 uint64_t Offs = TD.getStructLayout(StTy)->getElementOffset(Field); 00272 // FIXME: This can be optimized by combining the add with a 00273 // subsequent one. 00274 N = FastEmit_ri_(VT, ISD::ADD, N, Offs, VT); 00275 if (N == 0) 00276 // Unhandled operand. Halt "fast" selection and bail. 00277 return false; 00278 } 00279 Ty = StTy->getElementType(Field); 00280 } else { 00281 Ty = cast<SequentialType>(Ty)->getElementType(); 00282 00283 // If this is a constant subscript, handle it quickly. 00284 if (ConstantInt *CI = dyn_cast<ConstantInt>(Idx)) { 00285 if (CI->getZExtValue() == 0) continue; 00286 uint64_t Offs = 00287 TD.getTypeAllocSize(Ty)*cast<ConstantInt>(CI)->getSExtValue(); 00288 N = FastEmit_ri_(VT, ISD::ADD, N, Offs, VT); 00289 if (N == 0) 00290 // Unhandled operand. Halt "fast" selection and bail. 00291 return false; 00292 continue; 00293 } 00294 00295 // N = N + Idx * ElementSize; 00296 uint64_t ElementSize = TD.getTypeAllocSize(Ty); 00297 unsigned IdxN = getRegForGEPIndex(Idx); 00298 if (IdxN == 0) 00299 // Unhandled operand. Halt "fast" selection and bail. 00300 return false; 00301 00302 if (ElementSize != 1) { 00303 IdxN = FastEmit_ri_(VT, ISD::MUL, IdxN, ElementSize, VT); 00304 if (IdxN == 0) 00305 // Unhandled operand. Halt "fast" selection and bail. 00306 return false; 00307 } 00308 N = FastEmit_rr(VT, VT, ISD::ADD, N, IdxN); 00309 if (N == 0) 00310 // Unhandled operand. Halt "fast" selection and bail. 00311 return false; 00312 } 00313 } 00314 00315 // We successfully emitted code for the given LLVM Instruction. 00316 UpdateValueMap(I, N); 00317 return true; 00318 } 00319 00320 bool FastISel::SelectCall(User *I) { 00321 Function *F = cast<CallInst>(I)->getCalledFunction(); 00322 if (!F) return false; 00323 00324 unsigned IID = F->getIntrinsicID(); 00325 switch (IID) { 00326 default: break; 00327 case Intrinsic::dbg_stoppoint: { 00328 DbgStopPointInst *SPI = cast<DbgStopPointInst>(I); 00329 if (isValidDebugInfoIntrinsic(*SPI, CodeGenOpt::None)) 00330 setCurDebugLoc(ExtractDebugLocation(*SPI, MF.getDebugLocInfo())); 00331 return true; 00332 } 00333 case Intrinsic::dbg_region_start: { 00334 DbgRegionStartInst *RSI = cast<DbgRegionStartInst>(I); 00335 if (isValidDebugInfoIntrinsic(*RSI, CodeGenOpt::None) && DW 00336 && DW->ShouldEmitDwarfDebug()) { 00337 unsigned ID = 00338 DW->RecordRegionStart(cast<GlobalVariable>(RSI->getContext())); 00339 const TargetInstrDesc &II = TII.get(TargetInstrInfo::DBG_LABEL); 00340 BuildMI(MBB, DL, II).addImm(ID); 00341 } 00342 return true; 00343 } 00344 case Intrinsic::dbg_region_end: { 00345 DbgRegionEndInst *REI = cast<DbgRegionEndInst>(I); 00346 if (isValidDebugInfoIntrinsic(*REI, CodeGenOpt::None) && DW 00347 && DW->ShouldEmitDwarfDebug()) { 00348 unsigned ID = 0; 00349 DISubprogram Subprogram(cast<GlobalVariable>(REI->getContext())); 00350 if (isInlinedFnEnd(*REI, MF.getFunction())) { 00351 // This is end of an inlined function. 00352 const TargetInstrDesc &II = TII.get(TargetInstrInfo::DBG_LABEL); 00353 ID = DW->RecordInlinedFnEnd(Subprogram); 00354 if (ID) 00355 // Returned ID is 0 if this is unbalanced "end of inlined 00356 // scope". This could happen if optimizer eats dbg intrinsics 00357 // or "beginning of inlined scope" is not recoginized due to 00358 // missing location info. In such cases, ignore this region.end. 00359 BuildMI(MBB, DL, II).addImm(ID); 00360 } else { 00361 const TargetInstrDesc &II = TII.get(TargetInstrInfo::DBG_LABEL); 00362 ID = DW->RecordRegionEnd(cast<GlobalVariable>(REI->getContext())); 00363 BuildMI(MBB, DL, II).addImm(ID); 00364 } 00365 } 00366 return true; 00367 } 00368 case Intrinsic::dbg_func_start: { 00369 DbgFuncStartInst *FSI = cast<DbgFuncStartInst>(I); 00370 if (!isValidDebugInfoIntrinsic(*FSI, CodeGenOpt::None) || !DW 00371 || !DW->ShouldEmitDwarfDebug()) 00372 return true; 00373 00374 if (isInlinedFnStart(*FSI, MF.getFunction())) { 00375 // This is a beginning of an inlined function. 00376 00377 // If llvm.dbg.func.start is seen in a new block before any 00378 // llvm.dbg.stoppoint intrinsic then the location info is unknown. 00379 // FIXME : Why DebugLoc is reset at the beginning of each block ? 00380 DebugLoc PrevLoc = DL; 00381 if (PrevLoc.isUnknown()) 00382 return true; 00383 // Record the source line. 00384 setCurDebugLoc(ExtractDebugLocation(*FSI, MF.getDebugLocInfo())); 00385 00386 DebugLocTuple PrevLocTpl = MF.getDebugLocTuple(PrevLoc); 00387 DISubprogram SP(cast<GlobalVariable>(FSI->getSubprogram())); 00388 unsigned LabelID = DW->RecordInlinedFnStart(SP, 00389 DICompileUnit(PrevLocTpl.CompileUnit), 00390 PrevLocTpl.Line, 00391 PrevLocTpl.Col); 00392 const TargetInstrDesc &II = TII.get(TargetInstrInfo::DBG_LABEL); 00393 BuildMI(MBB, DL, II).addImm(LabelID); 00394 return true; 00395 } 00396 00397 // This is a beginning of a new function. 00398 MF.setDefaultDebugLoc(ExtractDebugLocation(*FSI, MF.getDebugLocInfo())); 00399 00400 // llvm.dbg.func_start also defines beginning of function scope. 00401 DW->RecordRegionStart(cast<GlobalVariable>(FSI->getSubprogram())); 00402 return true; 00403 } 00404 case Intrinsic::dbg_declare: { 00405 DbgDeclareInst *DI = cast<DbgDeclareInst>(I); 00406 if (!isValidDebugInfoIntrinsic(*DI, CodeGenOpt::None) || !DW 00407 || !DW->ShouldEmitDwarfDebug()) 00408 return true; 00409 00410 Value *Variable = DI->getVariable(); 00411 Value *Address = DI->getAddress(); 00412 if (BitCastInst *BCI = dyn_cast<BitCastInst>(Address)) 00413 Address = BCI->getOperand(0); 00414 AllocaInst *AI = dyn_cast<AllocaInst>(Address); 00415 // Don't handle byval struct arguments or VLAs, for example. 00416 if (!AI) break; 00417 DenseMap<const AllocaInst*, int>::iterator SI = 00418 StaticAllocaMap.find(AI); 00419 if (SI == StaticAllocaMap.end()) break; // VLAs. 00420 int FI = SI->second; 00421 00422 // Determine the debug globalvariable. 00423 GlobalValue *GV = cast<GlobalVariable>(Variable); 00424 00425 // Build the DECLARE instruction. 00426 const TargetInstrDesc &II = TII.get(TargetInstrInfo::DECLARE); 00427 MachineInstr *DeclareMI 00428 = BuildMI(MBB, DL, II).addFrameIndex(FI).addGlobalAddress(GV); 00429 DIVariable DV(cast<GlobalVariable>(GV)); 00430 DW->RecordVariableScope(DV, DeclareMI); 00431 return true; 00432 } 00433 case Intrinsic::eh_exception: { 00434 EVT VT = TLI.getValueType(I->getType()); 00435 switch (TLI.getOperationAction(ISD::EXCEPTIONADDR, VT)) { 00436 default: break; 00437 case TargetLowering::Expand: { 00438 assert(MBB->isLandingPad() && "Call to eh.exception not in landing pad!"); 00439 unsigned Reg = TLI.getExceptionAddressRegister(); 00440 const TargetRegisterClass *RC = TLI.getRegClassFor(VT); 00441 unsigned ResultReg = createResultReg(RC); 00442 bool InsertedCopy = TII.copyRegToReg(*MBB, MBB->end(), ResultReg, 00443 Reg, RC, RC); 00444 assert(InsertedCopy && "Can't copy address registers!"); 00445 InsertedCopy = InsertedCopy; 00446 UpdateValueMap(I, ResultReg); 00447 return true; 00448 } 00449 } 00450 break; 00451 } 00452 case Intrinsic::eh_selector_i32: 00453 case Intrinsic::eh_selector_i64: { 00454 EVT VT = TLI.getValueType(I->getType()); 00455 switch (TLI.getOperationAction(ISD::EHSELECTION, VT)) { 00456 default: break; 00457 case TargetLowering::Expand: { 00458 EVT VT = (IID == Intrinsic::eh_selector_i32 ? 00459 MVT::i32 : MVT::i64); 00460 00461 if (MMI) { 00462 if (MBB->isLandingPad()) 00463 AddCatchInfo(*cast<CallInst>(I), MMI, MBB); 00464 else { 00465 #ifndef NDEBUG 00466 CatchInfoLost.insert(cast<CallInst>(I)); 00467 #endif 00468 // FIXME: Mark exception selector register as live in. Hack for PR1508. 00469 unsigned Reg = TLI.getExceptionSelectorRegister(); 00470 if (Reg) MBB->addLiveIn(Reg); 00471 } 00472 00473 unsigned Reg = TLI.getExceptionSelectorRegister(); 00474 const TargetRegisterClass *RC = TLI.getRegClassFor(VT); 00475 unsigned ResultReg = createResultReg(RC); 00476 bool InsertedCopy = TII.copyRegToReg(*MBB, MBB->end(), ResultReg, 00477 Reg, RC, RC); 00478 assert(InsertedCopy && "Can't copy address registers!"); 00479 InsertedCopy = InsertedCopy; 00480 UpdateValueMap(I, ResultReg); 00481 } else { 00482 unsigned ResultReg = 00483 getRegForValue(Constant::getNullValue(I->getType())); 00484 UpdateValueMap(I, ResultReg); 00485 } 00486 return true; 00487 } 00488 } 00489 break; 00490 } 00491 } 00492 return false; 00493 } 00494 00495 bool FastISel::SelectCast(User *I, ISD::NodeType Opcode) { 00496 EVT SrcVT = TLI.getValueType(I->getOperand(0)->getType()); 00497 EVT DstVT = TLI.getValueType(I->getType()); 00498 00499 if (SrcVT == MVT::Other || !SrcVT.isSimple() || 00500 DstVT == MVT::Other || !DstVT.isSimple()) 00501 // Unhandled type. Halt "fast" selection and bail. 00502 return false; 00503 00504 // Check if the destination type is legal. Or as a special case, 00505 // it may be i1 if we're doing a truncate because that's 00506 // easy and somewhat common. 00507 if (!TLI.isTypeLegal(DstVT)) 00508 if (DstVT != MVT::i1 || Opcode != ISD::TRUNCATE) 00509 // Unhandled type. Halt "fast" selection and bail. 00510 return false; 00511 00512 // Check if the source operand is legal. Or as a special case, 00513 // it may be i1 if we're doing zero-extension because that's 00514 // easy and somewhat common. 00515 if (!TLI.isTypeLegal(SrcVT)) 00516 if (SrcVT != MVT::i1 || Opcode != ISD::ZERO_EXTEND) 00517 // Unhandled type. Halt "fast" selection and bail. 00518 return false; 00519 00520 unsigned InputReg = getRegForValue(I->getOperand(0)); 00521 if (!InputReg) 00522 // Unhandled operand. Halt "fast" selection and bail. 00523 return false; 00524 00525 // If the operand is i1, arrange for the high bits in the register to be zero. 00526 if (SrcVT == MVT::i1) { 00527 SrcVT = TLI.getTypeToTransformTo(I->getContext(), SrcVT); 00528 InputReg = FastEmitZExtFromI1(SrcVT.getSimpleVT(), InputReg); 00529 if (!InputReg) 00530 return false; 00531 } 00532 // If the result is i1, truncate to the target's type for i1 first. 00533 if (DstVT == MVT::i1) 00534 DstVT = TLI.getTypeToTransformTo(I->getContext(), DstVT); 00535 00536 unsigned ResultReg = FastEmit_r(SrcVT.getSimpleVT(), 00537 DstVT.getSimpleVT(), 00538 Opcode, 00539 InputReg); 00540 if (!ResultReg) 00541 return false; 00542 00543 UpdateValueMap(I, ResultReg); 00544 return true; 00545 } 00546 00547 bool FastISel::SelectBitCast(User *I) { 00548 // If the bitcast doesn't change the type, just use the operand value. 00549 if (I->getType() == I->getOperand(0)->getType()) { 00550 unsigned Reg = getRegForValue(I->getOperand(0)); 00551 if (Reg == 0) 00552 return false; 00553 UpdateValueMap(I, Reg); 00554 return true; 00555 } 00556 00557 // Bitcasts of other values become reg-reg copies or BIT_CONVERT operators. 00558 EVT SrcVT = TLI.getValueType(I->getOperand(0)->getType()); 00559 EVT DstVT = TLI.getValueType(I->getType()); 00560 00561 if (SrcVT == MVT::Other || !SrcVT.isSimple() || 00562 DstVT == MVT::Other || !DstVT.isSimple() || 00563 !TLI.isTypeLegal(SrcVT) || !TLI.isTypeLegal(DstVT)) 00564 // Unhandled type. Halt "fast" selection and bail. 00565 return false; 00566 00567 unsigned Op0 = getRegForValue(I->getOperand(0)); 00568 if (Op0 == 0) 00569 // Unhandled operand. Halt "fast" selection and bail. 00570 return false; 00571 00572 // First, try to perform the bitcast by inserting a reg-reg copy. 00573 unsigned ResultReg = 0; 00574 if (SrcVT.getSimpleVT() == DstVT.getSimpleVT()) { 00575 TargetRegisterClass* SrcClass = TLI.getRegClassFor(SrcVT); 00576 TargetRegisterClass* DstClass = TLI.getRegClassFor(DstVT); 00577 ResultReg = createResultReg(DstClass); 00578 00579 bool InsertedCopy = TII.copyRegToReg(*MBB, MBB->end(), ResultReg, 00580 Op0, DstClass, SrcClass); 00581 if (!InsertedCopy) 00582 ResultReg = 0; 00583 } 00584 00585 // If the reg-reg copy failed, select a BIT_CONVERT opcode. 00586 if (!ResultReg) 00587 ResultReg = FastEmit_r(SrcVT.getSimpleVT(), DstVT.getSimpleVT(), 00588 ISD::BIT_CONVERT, Op0); 00589 00590 if (!ResultReg) 00591 return false; 00592 00593 UpdateValueMap(I, ResultReg); 00594 return true; 00595 } 00596 00597 bool 00598 FastISel::SelectInstruction(Instruction *I) { 00599 return SelectOperator(I, I->getOpcode()); 00600 } 00601 00602 /// FastEmitBranch - Emit an unconditional branch to the given block, 00603 /// unless it is the immediate (fall-through) successor, and update 00604 /// the CFG. 00605 void 00606 FastISel::FastEmitBranch(MachineBasicBlock *MSucc) { 00607 MachineFunction::iterator NextMBB = 00608 next(MachineFunction::iterator(MBB)); 00609 00610 if (MBB->isLayoutSuccessor(MSucc)) { 00611 // The unconditional fall-through case, which needs no instructions. 00612 } else { 00613 // The unconditional branch case. 00614 TII.InsertBranch(*MBB, MSucc, NULL, SmallVector<MachineOperand, 0>()); 00615 } 00616 MBB->addSuccessor(MSucc); 00617 } 00618 00619 bool 00620 FastISel::SelectOperator(User *I, unsigned Opcode) { 00621 switch (Opcode) { 00622 case Instruction::Add: 00623 return SelectBinaryOp(I, ISD::ADD); 00624 case Instruction::FAdd: 00625 return SelectBinaryOp(I, ISD::FADD); 00626 case Instruction::Sub: 00627 return SelectBinaryOp(I, ISD::SUB); 00628 case Instruction::FSub: 00629 return SelectBinaryOp(I, ISD::FSUB); 00630 case Instruction::Mul: 00631 return SelectBinaryOp(I, ISD::MUL); 00632 case Instruction::FMul: 00633 return SelectBinaryOp(I, ISD::FMUL); 00634 case Instruction::SDiv: 00635 return SelectBinaryOp(I, ISD::SDIV); 00636 case Instruction::UDiv: 00637 return SelectBinaryOp(I, ISD::UDIV); 00638 case Instruction::FDiv: 00639 return SelectBinaryOp(I, ISD::FDIV); 00640 case Instruction::SRem: 00641 return SelectBinaryOp(I, ISD::SREM); 00642 case Instruction::URem: 00643 return SelectBinaryOp(I, ISD::UREM); 00644 case Instruction::FRem: 00645 return SelectBinaryOp(I, ISD::FREM); 00646 case Instruction::Shl: 00647 return SelectBinaryOp(I, ISD::SHL); 00648 case Instruction::LShr: 00649 return SelectBinaryOp(I, ISD::SRL); 00650 case Instruction::AShr: 00651 return SelectBinaryOp(I, ISD::SRA); 00652 case Instruction::And: 00653 return SelectBinaryOp(I, ISD::AND); 00654 case Instruction::Or: 00655 return SelectBinaryOp(I, ISD::OR); 00656 case Instruction::Xor: 00657 return SelectBinaryOp(I, ISD::XOR); 00658 00659 case Instruction::GetElementPtr: 00660 return SelectGetElementPtr(I); 00661 00662 case Instruction::Br: { 00663 BranchInst *BI = cast<BranchInst>(I); 00664 00665 if (BI->isUnconditional()) { 00666 BasicBlock *LLVMSucc = BI->getSuccessor(0); 00667 MachineBasicBlock *MSucc = MBBMap[LLVMSucc]; 00668 FastEmitBranch(MSucc); 00669 return true; 00670 } 00671 00672 // Conditional branches are not handed yet. 00673 // Halt "fast" selection and bail. 00674 return false; 00675 } 00676 00677 case Instruction::Unreachable: 00678 // Nothing to emit. 00679 return true; 00680 00681 case Instruction::PHI: 00682 // PHI nodes are already emitted. 00683 return true; 00684 00685 case Instruction::Alloca: 00686 // FunctionLowering has the static-sized case covered. 00687 if (StaticAllocaMap.count(cast<AllocaInst>(I))) 00688 return true; 00689 00690 // Dynamic-sized alloca is not handled yet. 00691 return false; 00692 00693 case Instruction::Call: 00694 return SelectCall(I); 00695 00696 case Instruction::BitCast: 00697 return SelectBitCast(I); 00698 00699 case Instruction::FPToSI: 00700 return SelectCast(I, ISD::FP_TO_SINT); 00701 case Instruction::ZExt: 00702 return SelectCast(I, ISD::ZERO_EXTEND); 00703 case Instruction::SExt: 00704 return SelectCast(I, ISD::SIGN_EXTEND); 00705 case Instruction::Trunc: 00706 return SelectCast(I, ISD::TRUNCATE); 00707 case Instruction::SIToFP: 00708 return SelectCast(I, ISD::SINT_TO_FP); 00709 00710 case Instruction::IntToPtr: // Deliberate fall-through. 00711 case Instruction::PtrToInt: { 00712 EVT SrcVT = TLI.getValueType(I->getOperand(0)->getType()); 00713 EVT DstVT = TLI.getValueType(I->getType()); 00714 if (DstVT.bitsGT(SrcVT)) 00715 return SelectCast(I, ISD::ZERO_EXTEND); 00716 if (DstVT.bitsLT(SrcVT)) 00717 return SelectCast(I, ISD::TRUNCATE); 00718 unsigned Reg = getRegForValue(I->getOperand(0)); 00719 if (Reg == 0) return false; 00720 UpdateValueMap(I, Reg); 00721 return true; 00722 } 00723 00724 default: 00725 // Unhandled instruction. Halt "fast" selection and bail. 00726 return false; 00727 } 00728 } 00729 00730 FastISel::FastISel(MachineFunction &mf, 00731 MachineModuleInfo *mmi, 00732 DwarfWriter *dw, 00733 DenseMap<const Value *, unsigned> &vm, 00734 DenseMap<const BasicBlock *, MachineBasicBlock *> &bm, 00735 DenseMap<const AllocaInst *, int> &am 00736 #ifndef NDEBUG 00737 , SmallSet<Instruction*, 8> &cil 00738 #endif 00739 ) 00740 : MBB(0), 00741 ValueMap(vm), 00742 MBBMap(bm), 00743 StaticAllocaMap(am), 00744 #ifndef NDEBUG 00745 CatchInfoLost(cil), 00746 #endif 00747 MF(mf), 00748 MMI(mmi), 00749 DW(dw), 00750 MRI(MF.getRegInfo()), 00751 MFI(*MF.getFrameInfo()), 00752 MCP(*MF.getConstantPool()), 00753 TM(MF.getTarget()), 00754 TD(*TM.getTargetData()), 00755 TII(*TM.getInstrInfo()), 00756 TLI(*TM.getTargetLowering()) { 00757 } 00758 00759 FastISel::~FastISel() {} 00760 00761 unsigned FastISel::FastEmit_(MVT, MVT, 00762 ISD::NodeType) { 00763 return 0; 00764 } 00765 00766 unsigned FastISel::FastEmit_r(MVT, MVT, 00767 ISD::NodeType, unsigned /*Op0*/) { 00768 return 0; 00769 } 00770 00771 unsigned FastISel::FastEmit_rr(MVT, MVT, 00772 ISD::NodeType, unsigned /*Op0*/, 00773 unsigned /*Op0*/) { 00774 return 0; 00775 } 00776 00777 unsigned FastISel::FastEmit_i(MVT, MVT, ISD::NodeType, uint64_t /*Imm*/) { 00778 return 0; 00779 } 00780 00781 unsigned FastISel::FastEmit_f(MVT, MVT, 00782 ISD::NodeType, ConstantFP * /*FPImm*/) { 00783 return 0; 00784 } 00785 00786 unsigned FastISel::FastEmit_ri(MVT, MVT, 00787 ISD::NodeType, unsigned /*Op0*/, 00788 uint64_t /*Imm*/) { 00789 return 0; 00790 } 00791 00792 unsigned FastISel::FastEmit_rf(MVT, MVT, 00793 ISD::NodeType, unsigned /*Op0*/, 00794 ConstantFP * /*FPImm*/) { 00795 return 0; 00796 } 00797 00798 unsigned FastISel::FastEmit_rri(MVT, MVT, 00799 ISD::NodeType, 00800 unsigned /*Op0*/, unsigned /*Op1*/, 00801 uint64_t /*Imm*/) { 00802 return 0; 00803 } 00804 00805 /// FastEmit_ri_ - This method is a wrapper of FastEmit_ri. It first tries 00806 /// to emit an instruction with an immediate operand using FastEmit_ri. 00807 /// If that fails, it materializes the immediate into a register and try 00808 /// FastEmit_rr instead. 00809 unsigned FastISel::FastEmit_ri_(MVT VT, ISD::NodeType Opcode, 00810 unsigned Op0, uint64_t Imm, 00811 MVT ImmType) { 00812 // First check if immediate type is legal. If not, we can't use the ri form. 00813 unsigned ResultReg = FastEmit_ri(VT, VT, Opcode, Op0, Imm); 00814 if (ResultReg != 0) 00815 return ResultReg; 00816 unsigned MaterialReg = FastEmit_i(ImmType, ImmType, ISD::Constant, Imm); 00817 if (MaterialReg == 0) 00818 return 0; 00819 return FastEmit_rr(VT, VT, Opcode, Op0, MaterialReg); 00820 } 00821 00822 /// FastEmit_rf_ - This method is a wrapper of FastEmit_ri. It first tries 00823 /// to emit an instruction with a floating-point immediate operand using 00824 /// FastEmit_rf. If that fails, it materializes the immediate into a register 00825 /// and try FastEmit_rr instead. 00826 unsigned FastISel::FastEmit_rf_(MVT VT, ISD::NodeType Opcode, 00827 unsigned Op0, ConstantFP *FPImm, 00828 MVT ImmType) { 00829 // First check if immediate type is legal. If not, we can't use the rf form. 00830 unsigned ResultReg = FastEmit_rf(VT, VT, Opcode, Op0, FPImm); 00831 if (ResultReg != 0) 00832 return ResultReg; 00833 00834 // Materialize the constant in a register. 00835 unsigned MaterialReg = FastEmit_f(ImmType, ImmType, ISD::ConstantFP, FPImm); 00836 if (MaterialReg == 0) { 00837 // If the target doesn't have a way to directly enter a floating-point 00838 // value into a register, use an alternate approach. 00839 // TODO: The current approach only supports floating-point constants 00840 // that can be constructed by conversion from integer values. This should 00841 // be replaced by code that creates a load from a constant-pool entry, 00842 // which will require some target-specific work. 00843 const APFloat &Flt = FPImm->getValueAPF(); 00844 EVT IntVT = TLI.getPointerTy(); 00845 00846 uint64_t x[2]; 00847 uint32_t IntBitWidth = IntVT.getSizeInBits(); 00848 bool isExact; 00849 (void) Flt.convertToInteger(x, IntBitWidth, /*isSigned=*/true, 00850 APFloat::rmTowardZero, &isExact); 00851 if (!isExact) 00852 return 0; 00853 APInt IntVal(IntBitWidth, 2, x); 00854 00855 unsigned IntegerReg = FastEmit_i(IntVT.getSimpleVT(), IntVT.getSimpleVT(), 00856 ISD::Constant, IntVal.getZExtValue()); 00857 if (IntegerReg == 0) 00858 return 0; 00859 MaterialReg = FastEmit_r(IntVT.getSimpleVT(), VT, 00860 ISD::SINT_TO_FP, IntegerReg); 00861 if (MaterialReg == 0) 00862 return 0; 00863 } 00864 return FastEmit_rr(VT, VT, Opcode, Op0, MaterialReg); 00865 } 00866 00867 unsigned FastISel::createResultReg(const TargetRegisterClass* RC) { 00868 return MRI.createVirtualRegister(RC); 00869 } 00870 00871 unsigned FastISel::FastEmitInst_(unsigned MachineInstOpcode, 00872 const TargetRegisterClass* RC) { 00873 unsigned ResultReg = createResultReg(RC); 00874 const TargetInstrDesc &II = TII.get(MachineInstOpcode); 00875 00876 BuildMI(MBB, DL, II, ResultReg); 00877 return ResultReg; 00878 } 00879 00880 unsigned FastISel::FastEmitInst_r(unsigned MachineInstOpcode, 00881 const TargetRegisterClass *RC, 00882 unsigned Op0) { 00883 unsigned ResultReg = createResultReg(RC); 00884 const TargetInstrDesc &II = TII.get(MachineInstOpcode); 00885 00886 if (II.getNumDefs() >= 1) 00887 BuildMI(MBB, DL, II, ResultReg).addReg(Op0); 00888 else { 00889 BuildMI(MBB, DL, II).addReg(Op0); 00890 bool InsertedCopy = TII.copyRegToReg(*MBB, MBB->end(), ResultReg, 00891 II.ImplicitDefs[0], RC, RC); 00892 if (!InsertedCopy) 00893 ResultReg = 0; 00894 } 00895 00896 return ResultReg; 00897 } 00898 00899 unsigned FastISel::FastEmitInst_rr(unsigned MachineInstOpcode, 00900 const TargetRegisterClass *RC, 00901 unsigned Op0, unsigned Op1) { 00902 unsigned ResultReg = createResultReg(RC); 00903 const TargetInstrDesc &II = TII.get(MachineInstOpcode); 00904 00905 if (II.getNumDefs() >= 1) 00906 BuildMI(MBB, DL, II, ResultReg).addReg(Op0).addReg(Op1); 00907 else { 00908 BuildMI(MBB, DL, II).addReg(Op0).addReg(Op1); 00909 bool InsertedCopy = TII.copyRegToReg(*MBB, MBB->end(), ResultReg, 00910 II.ImplicitDefs[0], RC, RC); 00911 if (!InsertedCopy) 00912 ResultReg = 0; 00913 } 00914 return ResultReg; 00915 } 00916 00917 unsigned FastISel::FastEmitInst_ri(unsigned MachineInstOpcode, 00918 const TargetRegisterClass *RC, 00919 unsigned Op0, uint64_t Imm) { 00920 unsigned ResultReg = createResultReg(RC); 00921 const TargetInstrDesc &II = TII.get(MachineInstOpcode); 00922 00923 if (II.getNumDefs() >= 1) 00924 BuildMI(MBB, DL, II, ResultReg).addReg(Op0).addImm(Imm); 00925 else { 00926 BuildMI(MBB, DL, II).addReg(Op0).addImm(Imm); 00927 bool InsertedCopy = TII.copyRegToReg(*MBB, MBB->end(), ResultReg, 00928 II.ImplicitDefs[0], RC, RC); 00929 if (!InsertedCopy) 00930 ResultReg = 0; 00931 } 00932 return ResultReg; 00933 } 00934 00935 unsigned FastISel::FastEmitInst_rf(unsigned MachineInstOpcode, 00936 const TargetRegisterClass *RC, 00937 unsigned Op0, ConstantFP *FPImm) { 00938 unsigned ResultReg = createResultReg(RC); 00939 const TargetInstrDesc &II = TII.get(MachineInstOpcode); 00940 00941 if (II.getNumDefs() >= 1) 00942 BuildMI(MBB, DL, II, ResultReg).addReg(Op0).addFPImm(FPImm); 00943 else { 00944 BuildMI(MBB, DL, II).addReg(Op0).addFPImm(FPImm); 00945 bool InsertedCopy = TII.copyRegToReg(*MBB, MBB->end(), ResultReg, 00946 II.ImplicitDefs[0], RC, RC); 00947 if (!InsertedCopy) 00948 ResultReg = 0; 00949 } 00950 return ResultReg; 00951 } 00952 00953 unsigned FastISel::FastEmitInst_rri(unsigned MachineInstOpcode, 00954 const TargetRegisterClass *RC, 00955 unsigned Op0, unsigned Op1, uint64_t Imm) { 00956 unsigned ResultReg = createResultReg(RC); 00957 const TargetInstrDesc &II = TII.get(MachineInstOpcode); 00958 00959 if (II.getNumDefs() >= 1) 00960 BuildMI(MBB, DL, II, ResultReg).addReg(Op0).addReg(Op1).addImm(Imm); 00961 else { 00962 BuildMI(MBB, DL, II).addReg(Op0).addReg(Op1).addImm(Imm); 00963 bool InsertedCopy = TII.copyRegToReg(*MBB, MBB->end(), ResultReg, 00964 II.ImplicitDefs[0], RC, RC); 00965 if (!InsertedCopy) 00966 ResultReg = 0; 00967 } 00968 return ResultReg; 00969 } 00970 00971 unsigned FastISel::FastEmitInst_i(unsigned MachineInstOpcode, 00972 const TargetRegisterClass *RC, 00973 uint64_t Imm) { 00974 unsigned ResultReg = createResultReg(RC); 00975 const TargetInstrDesc &II = TII.get(MachineInstOpcode); 00976 00977 if (II.getNumDefs() >= 1) 00978 BuildMI(MBB, DL, II, ResultReg).addImm(Imm); 00979 else { 00980 BuildMI(MBB, DL, II).addImm(Imm); 00981 bool InsertedCopy = TII.copyRegToReg(*MBB, MBB->end(), ResultReg, 00982 II.ImplicitDefs[0], RC, RC); 00983 if (!InsertedCopy) 00984 ResultReg = 0; 00985 } 00986 return ResultReg; 00987 } 00988 00989 unsigned FastISel::FastEmitInst_extractsubreg(MVT RetVT, 00990 unsigned Op0, uint32_t Idx) { 00991 const TargetRegisterClass* RC = MRI.getRegClass(Op0); 00992 00993 unsigned ResultReg = createResultReg(TLI.getRegClassFor(RetVT)); 00994 const TargetInstrDesc &II = TII.get(TargetInstrInfo::EXTRACT_SUBREG); 00995 00996 if (II.getNumDefs() >= 1) 00997 BuildMI(MBB, DL, II, ResultReg).addReg(Op0).addImm(Idx); 00998 else { 00999 BuildMI(MBB, DL, II).addReg(Op0).addImm(Idx); 01000 bool InsertedCopy = TII.copyRegToReg(*MBB, MBB->end(), ResultReg, 01001 II.ImplicitDefs[0], RC, RC); 01002 if (!InsertedCopy) 01003 ResultReg = 0; 01004 } 01005 return ResultReg; 01006 } 01007 01008 /// FastEmitZExtFromI1 - Emit MachineInstrs to compute the value of Op 01009 /// with all but the least significant bit set to zero. 01010 unsigned FastISel::FastEmitZExtFromI1(MVT VT, unsigned Op) { 01011 return FastEmit_ri(VT, VT, ISD::AND, Op, 1); 01012 }