FastISel.cpp revision 6e0066a16aaa8b4ca87bd319215d6811c515493a
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 unsigned Op0 = ValueMap[I->getOperand(0)]; 30 unsigned Op1 = ValueMap[I->getOperand(1)]; 31 if (Op0 == 0 || Op1 == 0) 32 // Unhandled operand. Halt "fast" selection and bail. 33 return false; 34 35 MVT VT = MVT::getMVT(I->getType(), /*HandleUnknown=*/true); 36 if (VT == MVT::Other || !VT.isSimple()) 37 // Unhandled type. Halt "fast" selection and bail. 38 return false; 39 40 unsigned ResultReg = FastEmit_rr(VT.getSimpleVT(), ISDOpcode, Op0, Op1); 41 if (ResultReg == 0) 42 // Target-specific code wasn't able to find a machine opcode for 43 // the given ISD opcode and type. Halt "fast" selection and bail. 44 return false; 45 46 // We successfully emitted code for the given LLVM Instruction. 47 ValueMap[I] = ResultReg; 48 return true; 49} 50 51bool FastISel::SelectGetElementPtr(Instruction *I, 52 DenseMap<const Value*, unsigned> &ValueMap) { 53 unsigned N = ValueMap[I->getOperand(0)]; 54 if (N == 0) 55 // Unhandled operand. Halt "fast" selection and bail. 56 return false; 57 58 const Type *Ty = I->getOperand(0)->getType(); 59 MVT VT = MVT::getMVT(Ty, /*HandleUnknown=*/false); 60 for (GetElementPtrInst::op_iterator OI = I->op_begin()+1, E = I->op_end(); 61 OI != E; ++OI) { 62 Value *Idx = *OI; 63 if (const StructType *StTy = dyn_cast<StructType>(Ty)) { 64 unsigned Field = cast<ConstantInt>(Idx)->getZExtValue(); 65 if (Field) { 66 // N = N + Offset 67 uint64_t Offs = TD.getStructLayout(StTy)->getElementOffset(Field); 68 // FIXME: This can be optimized by combining the add with a 69 // subsequent one. 70 N = FastEmit_ri(VT.getSimpleVT(), ISD::ADD, N, Offs, VT.getSimpleVT()); 71 if (N == 0) 72 // Unhandled operand. Halt "fast" selection and bail. 73 return false; 74 } 75 Ty = StTy->getElementType(Field); 76 } else { 77 Ty = cast<SequentialType>(Ty)->getElementType(); 78 79 // If this is a constant subscript, handle it quickly. 80 if (ConstantInt *CI = dyn_cast<ConstantInt>(Idx)) { 81 if (CI->getZExtValue() == 0) continue; 82 uint64_t Offs = 83 TD.getABITypeSize(Ty)*cast<ConstantInt>(CI)->getSExtValue(); 84 N = FastEmit_ri(VT.getSimpleVT(), ISD::ADD, N, Offs, VT.getSimpleVT()); 85 if (N == 0) 86 // Unhandled operand. Halt "fast" selection and bail. 87 return false; 88 continue; 89 } 90 91 // N = N + Idx * ElementSize; 92 uint64_t ElementSize = TD.getABITypeSize(Ty); 93 unsigned IdxN = ValueMap[Idx]; 94 if (IdxN == 0) 95 // Unhandled operand. Halt "fast" selection and bail. 96 return false; 97 98 // If the index is smaller or larger than intptr_t, truncate or extend 99 // it. 100 MVT IdxVT = MVT::getMVT(Idx->getType(), /*HandleUnknown=*/false); 101 if (IdxVT.bitsLT(VT)) 102 IdxN = FastEmit_r(VT.getSimpleVT(), ISD::SIGN_EXTEND, IdxN); 103 else if (IdxVT.bitsGT(VT)) 104 IdxN = FastEmit_r(VT.getSimpleVT(), ISD::TRUNCATE, IdxN); 105 if (IdxN == 0) 106 // Unhandled operand. Halt "fast" selection and bail. 107 return false; 108 109 // FIXME: If multiple is power of two, turn it into a shift. The 110 // optimization should be in FastEmit_ri? 111 IdxN = FastEmit_ri(VT.getSimpleVT(), ISD::MUL, IdxN, 112 ElementSize, VT.getSimpleVT()); 113 if (IdxN == 0) 114 // Unhandled operand. Halt "fast" selection and bail. 115 return false; 116 N = FastEmit_rr(VT.getSimpleVT(), ISD::ADD, N, IdxN); 117 if (N == 0) 118 // Unhandled operand. Halt "fast" selection and bail. 119 return false; 120 } 121 } 122 123 // We successfully emitted code for the given LLVM Instruction. 124 ValueMap[I] = N; 125 return true; 126} 127 128BasicBlock::iterator 129FastISel::SelectInstructions(BasicBlock::iterator Begin, 130 BasicBlock::iterator End, 131 DenseMap<const Value*, unsigned> &ValueMap, 132 MachineBasicBlock *mbb) { 133 MBB = mbb; 134 BasicBlock::iterator I = Begin; 135 136 for (; I != End; ++I) { 137 switch (I->getOpcode()) { 138 case Instruction::Add: { 139 ISD::NodeType Opc = I->getType()->isFPOrFPVector() ? ISD::FADD : ISD::ADD; 140 if (!SelectBinaryOp(I, Opc, ValueMap)) return I; break; 141 } 142 case Instruction::Sub: { 143 ISD::NodeType Opc = I->getType()->isFPOrFPVector() ? ISD::FSUB : ISD::SUB; 144 if (!SelectBinaryOp(I, Opc, ValueMap)) return I; break; 145 } 146 case Instruction::Mul: { 147 ISD::NodeType Opc = I->getType()->isFPOrFPVector() ? ISD::FMUL : ISD::MUL; 148 if (!SelectBinaryOp(I, Opc, ValueMap)) return I; break; 149 } 150 case Instruction::SDiv: 151 if (!SelectBinaryOp(I, ISD::SDIV, ValueMap)) return I; break; 152 case Instruction::UDiv: 153 if (!SelectBinaryOp(I, ISD::UDIV, ValueMap)) return I; break; 154 case Instruction::FDiv: 155 if (!SelectBinaryOp(I, ISD::FDIV, ValueMap)) return I; break; 156 case Instruction::SRem: 157 if (!SelectBinaryOp(I, ISD::SREM, ValueMap)) return I; break; 158 case Instruction::URem: 159 if (!SelectBinaryOp(I, ISD::UREM, ValueMap)) return I; break; 160 case Instruction::FRem: 161 if (!SelectBinaryOp(I, ISD::FREM, ValueMap)) return I; break; 162 case Instruction::Shl: 163 if (!SelectBinaryOp(I, ISD::SHL, ValueMap)) return I; break; 164 case Instruction::LShr: 165 if (!SelectBinaryOp(I, ISD::SRL, ValueMap)) return I; break; 166 case Instruction::AShr: 167 if (!SelectBinaryOp(I, ISD::SRA, ValueMap)) return I; break; 168 case Instruction::And: 169 if (!SelectBinaryOp(I, ISD::AND, ValueMap)) return I; break; 170 case Instruction::Or: 171 if (!SelectBinaryOp(I, ISD::OR, ValueMap)) return I; break; 172 case Instruction::Xor: 173 if (!SelectBinaryOp(I, ISD::XOR, ValueMap)) return I; break; 174 175 case Instruction::GetElementPtr: 176 if (!SelectGetElementPtr(I, ValueMap)) return I; 177 break; 178 179 case Instruction::Br: { 180 BranchInst *BI = cast<BranchInst>(I); 181 182 // For now, check for and handle just the most trivial case: an 183 // unconditional fall-through branch. 184 if (BI->isUnconditional()) { 185 MachineFunction::iterator NextMBB = 186 next(MachineFunction::iterator(MBB)); 187 if (NextMBB != MF.end() && 188 NextMBB->getBasicBlock() == BI->getSuccessor(0)) { 189 MBB->addSuccessor(NextMBB); 190 break; 191 } 192 } 193 194 // Something more complicated. Halt "fast" selection and bail. 195 return I; 196 } 197 default: 198 // Unhandled instruction. Halt "fast" selection and bail. 199 return I; 200 } 201 } 202 203 return I; 204} 205 206FastISel::FastISel(MachineFunction &mf) 207 : MF(mf), MRI(mf.getRegInfo()), 208 TD(*mf.getTarget().getTargetData()), 209 TII(*mf.getTarget().getInstrInfo()), 210 TLI(*mf.getTarget().getTargetLowering()) { 211} 212 213FastISel::~FastISel() {} 214 215unsigned FastISel::FastEmit_(MVT::SimpleValueType, ISD::NodeType) { 216 return 0; 217} 218 219unsigned FastISel::FastEmit_r(MVT::SimpleValueType, ISD::NodeType, 220 unsigned /*Op0*/) { 221 return 0; 222} 223 224unsigned FastISel::FastEmit_rr(MVT::SimpleValueType, ISD::NodeType, 225 unsigned /*Op0*/, unsigned /*Op0*/) { 226 return 0; 227} 228 229unsigned FastISel::FastEmit_i(MVT::SimpleValueType, uint64_t) { 230 return 0; 231} 232 233unsigned FastISel::FastEmit_ri(MVT::SimpleValueType, ISD::NodeType, 234 unsigned /*Op0*/, uint64_t Imm, 235 MVT::SimpleValueType ImmType) { 236 return 0; 237} 238 239/// FastEmit_ri_ - This method is a wrapper of FastEmit_ri. It first tries 240/// to emit an instruction with an immediate operand using FastEmit_ri. 241/// If that fails, it materializes the immediate into a register and try 242/// FastEmit_rr instead. 243unsigned FastISel::FastEmit_ri_(MVT::SimpleValueType VT, ISD::NodeType Opcode, 244 unsigned Op0, uint64_t Imm, 245 MVT::SimpleValueType ImmType) { 246 unsigned ResultReg = 0; 247 // First check if immediate type is legal. If not, we can't use the ri form. 248 if (TLI.getOperationAction(ISD::Constant, ImmType) == TargetLowering::Legal) 249 ResultReg = FastEmit_ri(VT, Opcode, Op0, Imm, ImmType); 250 if (ResultReg != 0) 251 return ResultReg; 252 return FastEmit_rr(VT, Opcode, Op0, FastEmit_i(ImmType, Imm)); 253} 254 255unsigned FastISel::FastEmitInst_(unsigned MachineInstOpcode, 256 const TargetRegisterClass* RC) { 257 unsigned ResultReg = MRI.createVirtualRegister(RC); 258 const TargetInstrDesc &II = TII.get(MachineInstOpcode); 259 260 BuildMI(MBB, II, ResultReg); 261 return ResultReg; 262} 263 264unsigned FastISel::FastEmitInst_r(unsigned MachineInstOpcode, 265 const TargetRegisterClass *RC, 266 unsigned Op0) { 267 unsigned ResultReg = MRI.createVirtualRegister(RC); 268 const TargetInstrDesc &II = TII.get(MachineInstOpcode); 269 270 BuildMI(MBB, II, ResultReg).addReg(Op0); 271 return ResultReg; 272} 273 274unsigned FastISel::FastEmitInst_rr(unsigned MachineInstOpcode, 275 const TargetRegisterClass *RC, 276 unsigned Op0, unsigned Op1) { 277 unsigned ResultReg = MRI.createVirtualRegister(RC); 278 const TargetInstrDesc &II = TII.get(MachineInstOpcode); 279 280 BuildMI(MBB, II, ResultReg).addReg(Op0).addReg(Op1); 281 return ResultReg; 282} 283