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