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