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