FastISel.cpp revision 7c3dd1f2cead8b5e37024f352716b1e7df6d231e
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(IdxVT.getSimpleVT(), VT, ISD::SIGN_EXTEND, IdxN); 128 else if (IdxVT.bitsGT(VT)) 129 IdxN = FastEmit_r(IdxVT.getSimpleVT(), 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 } 140 N = FastEmit_rr(VT, VT, ISD::ADD, N, IdxN); 141 if (N == 0) 142 // Unhandled operand. Halt "fast" selection and bail. 143 return false; 144 } 145 } 146 147 // We successfully emitted code for the given LLVM Instruction. 148 ValueMap[I] = N; 149 return true; 150} 151 152bool FastISel::SelectBitCast(Instruction *I, 153 DenseMap<const Value*, unsigned> &ValueMap) { 154 // BitCast consists of either an immediate to register move 155 // or a register to register move. 156 if (ConstantInt* CI = dyn_cast<ConstantInt>(I->getOperand(0))) { 157 if (I->getType()->isInteger()) { 158 MVT VT = MVT::getMVT(I->getType(), /*HandleUnknown=*/false); 159 unsigned result = FastEmit_i(VT.getSimpleVT(), VT.getSimpleVT(), 160 ISD::Constant, 161 CI->getZExtValue()); 162 if (!result) 163 return false; 164 165 ValueMap[I] = result; 166 return true; 167 } 168 169 // TODO: Support vector and fp constants. 170 return false; 171 } 172 173 if (!isa<Constant>(I->getOperand(0))) { 174 // Bitcasts of non-constant values become reg-reg copies. 175 MVT SrcVT = MVT::getMVT(I->getOperand(0)->getType()); 176 MVT DstVT = MVT::getMVT(I->getType()); 177 178 if (SrcVT == MVT::Other || !SrcVT.isSimple() || 179 DstVT == MVT::Other || !DstVT.isSimple() || 180 !TLI.isTypeLegal(SrcVT) || !TLI.isTypeLegal(DstVT)) 181 // Unhandled type. Halt "fast" selection and bail. 182 return false; 183 184 unsigned Op0 = ValueMap[I->getOperand(0)]; 185 if (Op0 == 0) 186 // Unhandled operand. Halt "fast" selection and bail. 187 return false; 188 189 // First, try to perform the bitcast by inserting a reg-reg copy. 190 unsigned ResultReg = 0; 191 if (SrcVT.getSimpleVT() == DstVT.getSimpleVT()) { 192 TargetRegisterClass* SrcClass = TLI.getRegClassFor(SrcVT); 193 TargetRegisterClass* DstClass = TLI.getRegClassFor(DstVT); 194 ResultReg = createResultReg(DstClass); 195 196 bool InsertedCopy = TII.copyRegToReg(*MBB, MBB->end(), ResultReg, 197 Op0, DstClass, SrcClass); 198 if (!InsertedCopy) 199 ResultReg = 0; 200 } 201 202 // If the reg-reg copy failed, select a BIT_CONVERT opcode. 203 if (!ResultReg) 204 ResultReg = FastEmit_r(SrcVT.getSimpleVT(), DstVT.getSimpleVT(), 205 ISD::BIT_CONVERT, Op0); 206 207 if (!ResultReg) 208 return false; 209 210 ValueMap[I] = ResultReg; 211 return true; 212 } 213 214 // TODO: Casting a non-integral constant? 215 return false; 216} 217 218BasicBlock::iterator 219FastISel::SelectInstructions(BasicBlock::iterator Begin, 220 BasicBlock::iterator End, 221 DenseMap<const Value*, unsigned> &ValueMap, 222 DenseMap<const BasicBlock*, 223 MachineBasicBlock *> &MBBMap, 224 MachineBasicBlock *mbb) { 225 MBB = mbb; 226 BasicBlock::iterator I = Begin; 227 228 for (; I != End; ++I) { 229 switch (I->getOpcode()) { 230 case Instruction::Add: { 231 ISD::NodeType Opc = I->getType()->isFPOrFPVector() ? ISD::FADD : ISD::ADD; 232 if (!SelectBinaryOp(I, Opc, ValueMap)) return I; break; 233 } 234 case Instruction::Sub: { 235 ISD::NodeType Opc = I->getType()->isFPOrFPVector() ? ISD::FSUB : ISD::SUB; 236 if (!SelectBinaryOp(I, Opc, ValueMap)) return I; break; 237 } 238 case Instruction::Mul: { 239 ISD::NodeType Opc = I->getType()->isFPOrFPVector() ? ISD::FMUL : ISD::MUL; 240 if (!SelectBinaryOp(I, Opc, ValueMap)) return I; break; 241 } 242 case Instruction::SDiv: 243 if (!SelectBinaryOp(I, ISD::SDIV, ValueMap)) return I; break; 244 case Instruction::UDiv: 245 if (!SelectBinaryOp(I, ISD::UDIV, ValueMap)) return I; break; 246 case Instruction::FDiv: 247 if (!SelectBinaryOp(I, ISD::FDIV, ValueMap)) return I; break; 248 case Instruction::SRem: 249 if (!SelectBinaryOp(I, ISD::SREM, ValueMap)) return I; break; 250 case Instruction::URem: 251 if (!SelectBinaryOp(I, ISD::UREM, ValueMap)) return I; break; 252 case Instruction::FRem: 253 if (!SelectBinaryOp(I, ISD::FREM, ValueMap)) return I; break; 254 case Instruction::Shl: 255 if (!SelectBinaryOp(I, ISD::SHL, ValueMap)) return I; break; 256 case Instruction::LShr: 257 if (!SelectBinaryOp(I, ISD::SRL, ValueMap)) return I; break; 258 case Instruction::AShr: 259 if (!SelectBinaryOp(I, ISD::SRA, ValueMap)) return I; break; 260 case Instruction::And: 261 if (!SelectBinaryOp(I, ISD::AND, ValueMap)) return I; break; 262 case Instruction::Or: 263 if (!SelectBinaryOp(I, ISD::OR, ValueMap)) return I; break; 264 case Instruction::Xor: 265 if (!SelectBinaryOp(I, ISD::XOR, ValueMap)) return I; break; 266 267 case Instruction::GetElementPtr: 268 if (!SelectGetElementPtr(I, ValueMap)) return I; 269 break; 270 271 case Instruction::Br: { 272 BranchInst *BI = cast<BranchInst>(I); 273 274 if (BI->isUnconditional()) { 275 MachineFunction::iterator NextMBB = 276 next(MachineFunction::iterator(MBB)); 277 BasicBlock *LLVMSucc = BI->getSuccessor(0); 278 MachineBasicBlock *MSucc = MBBMap[LLVMSucc]; 279 280 if (NextMBB != MF.end() && MSucc == NextMBB) { 281 // The unconditional fall-through case, which needs no instructions. 282 } else { 283 // The unconditional branch case. 284 TII.InsertBranch(*MBB, MSucc, NULL, SmallVector<MachineOperand, 0>()); 285 } 286 MBB->addSuccessor(MSucc); 287 break; 288 } 289 290 // Conditional branches are not handed yet. 291 // Halt "fast" selection and bail. 292 return I; 293 } 294 295 case Instruction::PHI: 296 // PHI nodes are already emitted. 297 break; 298 299 case Instruction::BitCast: 300 if (!SelectBitCast(I, ValueMap)) return I; 301 break; 302 303 case Instruction::FPToSI: 304 if (!isa<ConstantFP>(I->getOperand(0))) { 305 MVT SrcVT = MVT::getMVT(I->getOperand(0)->getType()); 306 MVT DstVT = MVT::getMVT(I->getType()); 307 308 if (SrcVT == MVT::Other || !SrcVT.isSimple() || 309 DstVT == MVT::Other || !DstVT.isSimple() || 310 !TLI.isTypeLegal(SrcVT) || !TLI.isTypeLegal(DstVT)) 311 // Unhandled type. Halt "fast" selection and bail. 312 return I; 313 314 unsigned InputReg = ValueMap[I->getOperand(0)]; 315 if (!InputReg) 316 // Unhandled operand. Halt "fast" selection and bail. 317 return I; 318 319 unsigned ResultReg = FastEmit_r(SrcVT.getSimpleVT(), 320 DstVT.getSimpleVT(), 321 ISD::FP_TO_SINT, 322 InputReg); 323 if (!ResultReg) 324 return I; 325 326 ValueMap[I] = ResultReg; 327 break; 328 } else 329 // TODO: Materialize the FP constant and then convert, 330 // or attempt constant folding. 331 return I; 332 333 case Instruction::ZExt: 334 if (!isa<ConstantInt>(I->getOperand(0))) { 335 MVT SrcVT = MVT::getMVT(I->getOperand(0)->getType()); 336 MVT DstVT = MVT::getMVT(I->getType()); 337 338 if (SrcVT == MVT::Other || !SrcVT.isSimple() || 339 DstVT == MVT::Other || !DstVT.isSimple() || 340 !TLI.isTypeLegal(SrcVT) || !TLI.isTypeLegal(DstVT)) 341 // Unhandled type. Halt "fast" selection and bail. 342 return I; 343 344 unsigned InputReg = ValueMap[I->getOperand(0)]; 345 if (!InputReg) 346 // Unhandled operand. Halt "fast" selection and bail. 347 return I; 348 349 unsigned ResultReg = FastEmit_r(SrcVT.getSimpleVT(), 350 DstVT.getSimpleVT(), 351 ISD::ZERO_EXTEND, 352 InputReg); 353 if (!ResultReg) 354 return I; 355 356 ValueMap[I] = ResultReg; 357 break; 358 } else 359 // TODO: Support constant operands 360 return I; 361 362 case Instruction::SIToFP: 363 if (!isa<ConstantInt>(I->getOperand(0))) { 364 MVT SrcVT = MVT::getMVT(I->getOperand(0)->getType()); 365 MVT DstVT = MVT::getMVT(I->getType()); 366 367 if (SrcVT == MVT::Other || !SrcVT.isSimple() || 368 DstVT == MVT::Other || !DstVT.isSimple() || 369 !TLI.isTypeLegal(SrcVT) || !TLI.isTypeLegal(DstVT)) 370 // Unhandled type. Halt "fast" selection and bail. 371 return I; 372 373 unsigned InputReg = ValueMap[I->getOperand(0)]; 374 if (!InputReg) 375 // Unhandled operan. Halt "fast" selection and bail. 376 return I; 377 378 unsigned ResultReg = FastEmit_r(SrcVT.getSimpleVT(), 379 DstVT.getSimpleVT(), 380 ISD::SINT_TO_FP, 381 InputReg); 382 if (!ResultReg) 383 return I; 384 385 ValueMap[I] = ResultReg; 386 break; 387 } else { 388 // Materialize constant and convert to FP. 389 // TODO: Attempt constant folding? 390 ConstantInt* CI = cast<ConstantInt>(I->getOperand(0)); 391 MVT SrcVT = MVT::getMVT(CI->getType()); 392 MVT DstVT = MVT::getMVT(I->getType()); 393 394 if (SrcVT == MVT::Other || !SrcVT.isSimple() || 395 DstVT == MVT::Other || !DstVT.isSimple() || 396 !TLI.isTypeLegal(SrcVT) || !TLI.isTypeLegal(DstVT)) 397 // Unhandled type. Halt "fast" selection and bail. 398 return I; 399 400 unsigned ResultReg1 = FastEmit_i(SrcVT.getSimpleVT(), 401 SrcVT.getSimpleVT(), 402 ISD::Constant, CI->getZExtValue()); 403 if (!ResultReg1) 404 return I; 405 406 unsigned ResultReg2 = FastEmit_r(SrcVT.getSimpleVT(), 407 DstVT.getSimpleVT(), 408 ISD::SINT_TO_FP, 409 ResultReg1); 410 if (!ResultReg2) 411 return I; 412 413 ValueMap[I] = ResultReg2; 414 break; 415 } 416 417 default: 418 // Unhandled instruction. Halt "fast" selection and bail. 419 return I; 420 } 421 } 422 423 return I; 424} 425 426FastISel::FastISel(MachineFunction &mf) 427 : MF(mf), 428 MRI(mf.getRegInfo()), 429 TM(mf.getTarget()), 430 TD(*TM.getTargetData()), 431 TII(*TM.getInstrInfo()), 432 TLI(*TM.getTargetLowering()) { 433} 434 435FastISel::~FastISel() {} 436 437unsigned FastISel::FastEmit_(MVT::SimpleValueType, MVT::SimpleValueType, ISD::NodeType) { 438 return 0; 439} 440 441unsigned FastISel::FastEmit_r(MVT::SimpleValueType, MVT::SimpleValueType, 442 ISD::NodeType, unsigned /*Op0*/) { 443 return 0; 444} 445 446unsigned FastISel::FastEmit_rr(MVT::SimpleValueType, MVT::SimpleValueType, 447 ISD::NodeType, unsigned /*Op0*/, 448 unsigned /*Op0*/) { 449 return 0; 450} 451 452unsigned FastISel::FastEmit_i(MVT::SimpleValueType, MVT::SimpleValueType, 453 ISD::NodeType, uint64_t /*Imm*/) { 454 return 0; 455} 456 457unsigned FastISel::FastEmit_ri(MVT::SimpleValueType, MVT::SimpleValueType, 458 ISD::NodeType, unsigned /*Op0*/, 459 uint64_t /*Imm*/) { 460 return 0; 461} 462 463unsigned FastISel::FastEmit_rri(MVT::SimpleValueType, MVT::SimpleValueType, 464 ISD::NodeType, 465 unsigned /*Op0*/, unsigned /*Op1*/, 466 uint64_t /*Imm*/) { 467 return 0; 468} 469 470/// FastEmit_ri_ - This method is a wrapper of FastEmit_ri. It first tries 471/// to emit an instruction with an immediate operand using FastEmit_ri. 472/// If that fails, it materializes the immediate into a register and try 473/// FastEmit_rr instead. 474unsigned FastISel::FastEmit_ri_(MVT::SimpleValueType VT, ISD::NodeType Opcode, 475 unsigned Op0, uint64_t Imm, 476 MVT::SimpleValueType ImmType) { 477 unsigned ResultReg = 0; 478 // First check if immediate type is legal. If not, we can't use the ri form. 479 if (TLI.getOperationAction(ISD::Constant, ImmType) == TargetLowering::Legal) 480 ResultReg = FastEmit_ri(VT, VT, Opcode, Op0, Imm); 481 if (ResultReg != 0) 482 return ResultReg; 483 unsigned MaterialReg = FastEmit_i(ImmType, ImmType, ISD::Constant, Imm); 484 if (MaterialReg == 0) 485 return 0; 486 return FastEmit_rr(VT, VT, Opcode, Op0, MaterialReg); 487} 488 489unsigned FastISel::createResultReg(const TargetRegisterClass* RC) { 490 return MRI.createVirtualRegister(RC); 491} 492 493unsigned FastISel::FastEmitInst_(unsigned MachineInstOpcode, 494 const TargetRegisterClass* RC) { 495 unsigned ResultReg = createResultReg(RC); 496 const TargetInstrDesc &II = TII.get(MachineInstOpcode); 497 498 BuildMI(MBB, II, ResultReg); 499 return ResultReg; 500} 501 502unsigned FastISel::FastEmitInst_r(unsigned MachineInstOpcode, 503 const TargetRegisterClass *RC, 504 unsigned Op0) { 505 unsigned ResultReg = createResultReg(RC); 506 const TargetInstrDesc &II = TII.get(MachineInstOpcode); 507 508 BuildMI(MBB, II, ResultReg).addReg(Op0); 509 return ResultReg; 510} 511 512unsigned FastISel::FastEmitInst_rr(unsigned MachineInstOpcode, 513 const TargetRegisterClass *RC, 514 unsigned Op0, unsigned Op1) { 515 unsigned ResultReg = createResultReg(RC); 516 const TargetInstrDesc &II = TII.get(MachineInstOpcode); 517 518 BuildMI(MBB, II, ResultReg).addReg(Op0).addReg(Op1); 519 return ResultReg; 520} 521 522unsigned FastISel::FastEmitInst_ri(unsigned MachineInstOpcode, 523 const TargetRegisterClass *RC, 524 unsigned Op0, uint64_t Imm) { 525 unsigned ResultReg = createResultReg(RC); 526 const TargetInstrDesc &II = TII.get(MachineInstOpcode); 527 528 BuildMI(MBB, II, ResultReg).addReg(Op0).addImm(Imm); 529 return ResultReg; 530} 531 532unsigned FastISel::FastEmitInst_rri(unsigned MachineInstOpcode, 533 const TargetRegisterClass *RC, 534 unsigned Op0, unsigned Op1, uint64_t Imm) { 535 unsigned ResultReg = createResultReg(RC); 536 const TargetInstrDesc &II = TII.get(MachineInstOpcode); 537 538 BuildMI(MBB, II, ResultReg).addReg(Op0).addReg(Op1).addImm(Imm); 539 return ResultReg; 540} 541 542unsigned FastISel::FastEmitInst_i(unsigned MachineInstOpcode, 543 const TargetRegisterClass *RC, 544 uint64_t Imm) { 545 unsigned ResultReg = createResultReg(RC); 546 const TargetInstrDesc &II = TII.get(MachineInstOpcode); 547 548 BuildMI(MBB, II, ResultReg).addImm(Imm); 549 return ResultReg; 550} 551