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