FastISel.cpp revision b71fea248fd7cf9ab2c5737997a3dc5682948dc4
1///===-- FastISel.cpp - Implementation of the FastISel class --------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file contains the implementation of the FastISel class. 11// 12//===----------------------------------------------------------------------===// 13 14#include "llvm/Instructions.h" 15#include "llvm/CodeGen/FastISel.h" 16#include "llvm/CodeGen/MachineInstrBuilder.h" 17#include "llvm/CodeGen/MachineRegisterInfo.h" 18#include "llvm/Target/TargetData.h" 19#include "llvm/Target/TargetInstrInfo.h" 20#include "llvm/Target/TargetLowering.h" 21#include "llvm/Target/TargetMachine.h" 22using namespace llvm; 23 24/// SelectBinaryOp - Select and emit code for a binary operator instruction, 25/// which has an opcode which directly corresponds to the given ISD opcode. 26/// 27bool FastISel::SelectBinaryOp(Instruction *I, ISD::NodeType ISDOpcode, 28 DenseMap<const Value*, unsigned> &ValueMap) { 29 MVT VT = MVT::getMVT(I->getType(), /*HandleUnknown=*/true); 30 if (VT == MVT::Other || !VT.isSimple()) 31 // Unhandled type. Halt "fast" selection and bail. 32 return false; 33 // We only handle legal types. For example, on x86-32 the instruction 34 // selector contains all of the 64-bit instructions from x86-64, 35 // under the assumption that i64 won't be used if the target doesn't 36 // support it. 37 if (!TLI.isTypeLegal(VT)) 38 return false; 39 40 unsigned Op0 = ValueMap[I->getOperand(0)]; 41 if (Op0 == 0) 42 // Unhandled operand. Halt "fast" selection and bail. 43 return false; 44 45 // Check if the second operand is a constant and handle it appropriately. 46 if (ConstantInt *CI = dyn_cast<ConstantInt>(I->getOperand(1))) { 47 unsigned ResultReg = FastEmit_ri_(VT.getSimpleVT(), ISDOpcode, Op0, 48 CI->getZExtValue(), VT.getSimpleVT()); 49 if (ResultReg == 0) 50 // Target-specific code wasn't able to find a machine opcode for 51 // the given ISD opcode and type. Halt "fast" selection and bail. 52 return false; 53 54 // We successfully emitted code for the given LLVM Instruction. 55 ValueMap[I] = ResultReg; 56 return true; 57 } 58 59 unsigned Op1 = ValueMap[I->getOperand(1)]; 60 if (Op1 == 0) 61 // Unhandled operand. Halt "fast" selection and bail. 62 return false; 63 64 unsigned ResultReg = FastEmit_rr(VT.getSimpleVT(), VT.getSimpleVT(), 65 ISDOpcode, Op0, Op1); 66 if (ResultReg == 0) 67 // Target-specific code wasn't able to find a machine opcode for 68 // the given ISD opcode and type. Halt "fast" selection and bail. 69 return false; 70 71 // We successfully emitted code for the given LLVM Instruction. 72 ValueMap[I] = ResultReg; 73 return true; 74} 75 76bool FastISel::SelectGetElementPtr(Instruction *I, 77 DenseMap<const Value*, unsigned> &ValueMap) { 78 unsigned N = ValueMap[I->getOperand(0)]; 79 if (N == 0) 80 // Unhandled operand. Halt "fast" selection and bail. 81 return false; 82 83 const Type *Ty = I->getOperand(0)->getType(); 84 MVT::SimpleValueType VT = TLI.getPointerTy().getSimpleVT(); 85 for (GetElementPtrInst::op_iterator OI = I->op_begin()+1, E = I->op_end(); 86 OI != E; ++OI) { 87 Value *Idx = *OI; 88 if (const StructType *StTy = dyn_cast<StructType>(Ty)) { 89 unsigned Field = cast<ConstantInt>(Idx)->getZExtValue(); 90 if (Field) { 91 // N = N + Offset 92 uint64_t Offs = TD.getStructLayout(StTy)->getElementOffset(Field); 93 // FIXME: This can be optimized by combining the add with a 94 // subsequent one. 95 N = FastEmit_ri_(VT, ISD::ADD, N, Offs, VT); 96 if (N == 0) 97 // Unhandled operand. Halt "fast" selection and bail. 98 return false; 99 } 100 Ty = StTy->getElementType(Field); 101 } else { 102 Ty = cast<SequentialType>(Ty)->getElementType(); 103 104 // If this is a constant subscript, handle it quickly. 105 if (ConstantInt *CI = dyn_cast<ConstantInt>(Idx)) { 106 if (CI->getZExtValue() == 0) continue; 107 uint64_t Offs = 108 TD.getABITypeSize(Ty)*cast<ConstantInt>(CI)->getSExtValue(); 109 N = FastEmit_ri_(VT, ISD::ADD, N, Offs, VT); 110 if (N == 0) 111 // Unhandled operand. Halt "fast" selection and bail. 112 return false; 113 continue; 114 } 115 116 // N = N + Idx * ElementSize; 117 uint64_t ElementSize = TD.getABITypeSize(Ty); 118 unsigned IdxN = ValueMap[Idx]; 119 if (IdxN == 0) 120 // Unhandled operand. Halt "fast" selection and bail. 121 return false; 122 123 // If the index is smaller or larger than intptr_t, truncate or extend 124 // it. 125 MVT IdxVT = MVT::getMVT(Idx->getType(), /*HandleUnknown=*/false); 126 if (IdxVT.bitsLT(VT)) 127 IdxN = FastEmit_r(VT, VT, ISD::SIGN_EXTEND, IdxN); 128 else if (IdxVT.bitsGT(VT)) 129 IdxN = FastEmit_r(VT, VT, ISD::TRUNCATE, IdxN); 130 if (IdxN == 0) 131 // Unhandled operand. Halt "fast" selection and bail. 132 return false; 133 134 if (ElementSize != 1) 135 IdxN = FastEmit_ri_(VT, ISD::MUL, IdxN, ElementSize, VT); 136 if (IdxN == 0) 137 // Unhandled operand. Halt "fast" selection and bail. 138 return false; 139 N = FastEmit_rr(VT, VT, ISD::ADD, N, IdxN); 140 if (N == 0) 141 // Unhandled operand. Halt "fast" selection and bail. 142 return false; 143 } 144 } 145 146 // We successfully emitted code for the given LLVM Instruction. 147 ValueMap[I] = N; 148 return true; 149} 150 151BasicBlock::iterator 152FastISel::SelectInstructions(BasicBlock::iterator Begin, 153 BasicBlock::iterator End, 154 DenseMap<const Value*, unsigned> &ValueMap, 155 DenseMap<const BasicBlock*, 156 MachineBasicBlock *> &MBBMap, 157 MachineBasicBlock *mbb) { 158 MBB = mbb; 159 BasicBlock::iterator I = Begin; 160 161 for (; I != End; ++I) { 162 switch (I->getOpcode()) { 163 case Instruction::Add: { 164 ISD::NodeType Opc = I->getType()->isFPOrFPVector() ? ISD::FADD : ISD::ADD; 165 if (!SelectBinaryOp(I, Opc, ValueMap)) return I; break; 166 } 167 case Instruction::Sub: { 168 ISD::NodeType Opc = I->getType()->isFPOrFPVector() ? ISD::FSUB : ISD::SUB; 169 if (!SelectBinaryOp(I, Opc, ValueMap)) return I; break; 170 } 171 case Instruction::Mul: { 172 ISD::NodeType Opc = I->getType()->isFPOrFPVector() ? ISD::FMUL : ISD::MUL; 173 if (!SelectBinaryOp(I, Opc, ValueMap)) return I; break; 174 } 175 case Instruction::SDiv: 176 if (!SelectBinaryOp(I, ISD::SDIV, ValueMap)) return I; break; 177 case Instruction::UDiv: 178 if (!SelectBinaryOp(I, ISD::UDIV, ValueMap)) return I; break; 179 case Instruction::FDiv: 180 if (!SelectBinaryOp(I, ISD::FDIV, ValueMap)) return I; break; 181 case Instruction::SRem: 182 if (!SelectBinaryOp(I, ISD::SREM, ValueMap)) return I; break; 183 case Instruction::URem: 184 if (!SelectBinaryOp(I, ISD::UREM, ValueMap)) return I; break; 185 case Instruction::FRem: 186 if (!SelectBinaryOp(I, ISD::FREM, ValueMap)) return I; break; 187 case Instruction::Shl: 188 if (!SelectBinaryOp(I, ISD::SHL, ValueMap)) return I; break; 189 case Instruction::LShr: 190 if (!SelectBinaryOp(I, ISD::SRL, ValueMap)) return I; break; 191 case Instruction::AShr: 192 if (!SelectBinaryOp(I, ISD::SRA, ValueMap)) return I; break; 193 case Instruction::And: 194 if (!SelectBinaryOp(I, ISD::AND, ValueMap)) return I; break; 195 case Instruction::Or: 196 if (!SelectBinaryOp(I, ISD::OR, ValueMap)) return I; break; 197 case Instruction::Xor: 198 if (!SelectBinaryOp(I, ISD::XOR, ValueMap)) return I; break; 199 200 case Instruction::GetElementPtr: 201 if (!SelectGetElementPtr(I, ValueMap)) return I; 202 break; 203 204 case Instruction::Br: { 205 BranchInst *BI = cast<BranchInst>(I); 206 207 if (BI->isUnconditional()) { 208 MachineFunction::iterator NextMBB = 209 next(MachineFunction::iterator(MBB)); 210 BasicBlock *LLVMSucc = BI->getSuccessor(0); 211 MachineBasicBlock *MSucc = MBBMap[LLVMSucc]; 212 213 if (NextMBB != MF.end() && MSucc == NextMBB) { 214 // The unconditional fall-through case, which needs no instructions. 215 } else { 216 // The unconditional branch case. 217 TII.InsertBranch(*MBB, MSucc, NULL, SmallVector<MachineOperand, 0>()); 218 } 219 MBB->addSuccessor(MSucc); 220 break; 221 } 222 223 // Conditional branches are not handed yet. 224 // Halt "fast" selection and bail. 225 return I; 226 } 227 228 case Instruction::PHI: 229 // PHI nodes are already emitted. 230 break; 231 232 case Instruction::BitCast: 233 // BitCast consists of either an immediate to register move 234 // or a register to register move. 235 if (ConstantInt* CI = dyn_cast<ConstantInt>(I->getOperand(0))) { 236 if (I->getType()->isInteger()) { 237 MVT VT = MVT::getMVT(I->getType(), /*HandleUnknown=*/false); 238 unsigned result = FastEmit_i(VT.getSimpleVT(), VT.getSimpleVT(), 239 ISD::Constant, 240 CI->getZExtValue()); 241 if (!result) 242 return I; 243 244 ValueMap[I] = result; 245 break; 246 } else 247 // TODO: Support vector and fp constants. 248 return I; 249 } else if (!isa<Constant>(I->getOperand(0))) { 250 // Bitcasts of non-constant values become reg-reg copies. 251 MVT SrcVT = MVT::getMVT(I->getOperand(0)->getType()); 252 MVT DstVT = MVT::getMVT(I->getType()); 253 254 if (SrcVT == MVT::Other || !SrcVT.isSimple() || 255 DstVT == MVT::Other || !DstVT.isSimple() || 256 !TLI.isTypeLegal(SrcVT) || !TLI.isTypeLegal(DstVT)) 257 // Unhandled type. Halt "fast" selection and bail. 258 return I; 259 260 unsigned Op0 = ValueMap[I->getOperand(0)]; 261 if (Op0 == 0) 262 // Unhandled operand. Halt "fast" selection and bail. 263 return false; 264 265 // First, try to perform the bitcast by inserting a reg-reg copy. 266 unsigned ResultReg = 0; 267 if (SrcVT.getSimpleVT() == DstVT.getSimpleVT()) { 268 TargetRegisterClass* SrcClass = TLI.getRegClassFor(SrcVT); 269 TargetRegisterClass* DstClass = TLI.getRegClassFor(DstVT); 270 ResultReg = createResultReg(DstClass); 271 272 bool InsertedCopy = TII.copyRegToReg(*MBB, MBB->end(), ResultReg, 273 Op0, DstClass, SrcClass); 274 if (!InsertedCopy) 275 ResultReg = 0; 276 } 277 278 // If the reg-reg copy failed, select a BIT_CONVERT opcode. 279 if (!ResultReg) 280 ResultReg = FastEmit_r(SrcVT.getSimpleVT(), DstVT.getSimpleVT(), 281 ISD::BIT_CONVERT, Op0); 282 283 if (!ResultReg) 284 return I; 285 286 ValueMap[I] = ResultReg; 287 break; 288 } else 289 // TODO: Casting a non-integral constant? 290 return I; 291 292 case Instruction::FPToSI: 293 if (!isa<ConstantFP>(I->getOperand(0))) { 294 MVT SrcVT = MVT::getMVT(I->getOperand(0)->getType()); 295 MVT DstVT = MVT::getMVT(I->getType()); 296 297 if (SrcVT == MVT::Other || !SrcVT.isSimple() || 298 DstVT == MVT::Other || !DstVT.isSimple() || 299 !TLI.isTypeLegal(SrcVT) || !TLI.isTypeLegal(DstVT)) 300 // Unhandled type. Halt "fast" selection and bail. 301 return I; 302 303 unsigned InputReg = ValueMap[I->getOperand(0)]; 304 if (!InputReg) 305 // Unhandled operand. Halt "fast" selection and bail. 306 return I; 307 308 unsigned ResultReg = FastEmit_r(SrcVT.getSimpleVT(), 309 DstVT.getSimpleVT(), 310 ISD::FP_TO_SINT, 311 InputReg); 312 if (!ResultReg) 313 return I; 314 315 ValueMap[I] = ResultReg; 316 break; 317 } else 318 // TODO: Materialize the FP constant and then convert, 319 // or attempt constant folding. 320 return I; 321 322 case Instruction::SIToFP: 323 if (!isa<ConstantInt>(I->getOperand(0))) { 324 MVT SrcVT = MVT::getMVT(I->getOperand(0)->getType()); 325 MVT DstVT = MVT::getMVT(I->getType()); 326 327 if (SrcVT == MVT::Other || !SrcVT.isSimple() || 328 DstVT == MVT::Other || !DstVT.isSimple() || 329 !TLI.isTypeLegal(SrcVT) || !TLI.isTypeLegal(DstVT)) 330 // Unhandled type. Halt "fast" selection and bail. 331 return I; 332 333 unsigned InputReg = ValueMap[I->getOperand(0)]; 334 if (!InputReg) 335 // Unhandled operan. Halt "fast" selection and bail. 336 return I; 337 338 unsigned ResultReg = FastEmit_r(SrcVT.getSimpleVT(), 339 DstVT.getSimpleVT(), 340 ISD::SINT_TO_FP, 341 InputReg); 342 if (!ResultReg) 343 return I; 344 345 ValueMap[I] = ResultReg; 346 break; 347 } else 348 // TODO: Materialize constant and convert to FP. 349 return I; 350 default: 351 // Unhandled instruction. Halt "fast" selection and bail. 352 return I; 353 } 354 } 355 356 return I; 357} 358 359FastISel::FastISel(MachineFunction &mf) 360 : MF(mf), 361 MRI(mf.getRegInfo()), 362 TM(mf.getTarget()), 363 TD(*TM.getTargetData()), 364 TII(*TM.getInstrInfo()), 365 TLI(*TM.getTargetLowering()) { 366} 367 368FastISel::~FastISel() {} 369 370unsigned FastISel::FastEmit_(MVT::SimpleValueType, MVT::SimpleValueType, ISD::NodeType) { 371 return 0; 372} 373 374unsigned FastISel::FastEmit_r(MVT::SimpleValueType, MVT::SimpleValueType, 375 ISD::NodeType, unsigned /*Op0*/) { 376 return 0; 377} 378 379unsigned FastISel::FastEmit_rr(MVT::SimpleValueType, MVT::SimpleValueType, 380 ISD::NodeType, unsigned /*Op0*/, 381 unsigned /*Op0*/) { 382 return 0; 383} 384 385unsigned FastISel::FastEmit_i(MVT::SimpleValueType, MVT::SimpleValueType, 386 ISD::NodeType, uint64_t /*Imm*/) { 387 return 0; 388} 389 390unsigned FastISel::FastEmit_ri(MVT::SimpleValueType, MVT::SimpleValueType, 391 ISD::NodeType, unsigned /*Op0*/, 392 uint64_t /*Imm*/) { 393 return 0; 394} 395 396unsigned FastISel::FastEmit_rri(MVT::SimpleValueType, MVT::SimpleValueType, 397 ISD::NodeType, 398 unsigned /*Op0*/, unsigned /*Op1*/, 399 uint64_t /*Imm*/) { 400 return 0; 401} 402 403/// FastEmit_ri_ - This method is a wrapper of FastEmit_ri. It first tries 404/// to emit an instruction with an immediate operand using FastEmit_ri. 405/// If that fails, it materializes the immediate into a register and try 406/// FastEmit_rr instead. 407unsigned FastISel::FastEmit_ri_(MVT::SimpleValueType VT, ISD::NodeType Opcode, 408 unsigned Op0, uint64_t Imm, 409 MVT::SimpleValueType ImmType) { 410 unsigned ResultReg = 0; 411 // First check if immediate type is legal. If not, we can't use the ri form. 412 if (TLI.getOperationAction(ISD::Constant, ImmType) == TargetLowering::Legal) 413 ResultReg = FastEmit_ri(VT, VT, Opcode, Op0, Imm); 414 if (ResultReg != 0) 415 return ResultReg; 416 unsigned MaterialReg = FastEmit_i(ImmType, ImmType, ISD::Constant, Imm); 417 if (MaterialReg == 0) 418 return 0; 419 return FastEmit_rr(VT, VT, Opcode, Op0, MaterialReg); 420} 421 422unsigned FastISel::createResultReg(const TargetRegisterClass* RC) { 423 return MRI.createVirtualRegister(RC); 424} 425 426unsigned FastISel::FastEmitInst_(unsigned MachineInstOpcode, 427 const TargetRegisterClass* RC) { 428 unsigned ResultReg = createResultReg(RC); 429 const TargetInstrDesc &II = TII.get(MachineInstOpcode); 430 431 BuildMI(MBB, II, ResultReg); 432 return ResultReg; 433} 434 435unsigned FastISel::FastEmitInst_r(unsigned MachineInstOpcode, 436 const TargetRegisterClass *RC, 437 unsigned Op0) { 438 unsigned ResultReg = createResultReg(RC); 439 const TargetInstrDesc &II = TII.get(MachineInstOpcode); 440 441 BuildMI(MBB, II, ResultReg).addReg(Op0); 442 return ResultReg; 443} 444 445unsigned FastISel::FastEmitInst_rr(unsigned MachineInstOpcode, 446 const TargetRegisterClass *RC, 447 unsigned Op0, unsigned Op1) { 448 unsigned ResultReg = createResultReg(RC); 449 const TargetInstrDesc &II = TII.get(MachineInstOpcode); 450 451 BuildMI(MBB, II, ResultReg).addReg(Op0).addReg(Op1); 452 return ResultReg; 453} 454 455unsigned FastISel::FastEmitInst_ri(unsigned MachineInstOpcode, 456 const TargetRegisterClass *RC, 457 unsigned Op0, uint64_t Imm) { 458 unsigned ResultReg = createResultReg(RC); 459 const TargetInstrDesc &II = TII.get(MachineInstOpcode); 460 461 BuildMI(MBB, II, ResultReg).addReg(Op0).addImm(Imm); 462 return ResultReg; 463} 464 465unsigned FastISel::FastEmitInst_rri(unsigned MachineInstOpcode, 466 const TargetRegisterClass *RC, 467 unsigned Op0, unsigned Op1, uint64_t Imm) { 468 unsigned ResultReg = createResultReg(RC); 469 const TargetInstrDesc &II = TII.get(MachineInstOpcode); 470 471 BuildMI(MBB, II, ResultReg).addReg(Op0).addReg(Op1).addImm(Imm); 472 return ResultReg; 473} 474 475unsigned FastISel::FastEmitInst_i(unsigned MachineInstOpcode, 476 const TargetRegisterClass *RC, 477 uint64_t Imm) { 478 unsigned ResultReg = createResultReg(RC); 479 const TargetInstrDesc &II = TII.get(MachineInstOpcode); 480 481 BuildMI(MBB, II, ResultReg).addImm(Imm); 482 return ResultReg; 483} 484