1 //===-- llvm/CodeGen/GlobalISel/IRTranslator.h - IRTranslator ---*- C++ -*-===// 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 /// \file 10 /// This file declares the IRTranslator pass. 11 /// This pass is responsible for translating LLVM IR into MachineInstr. 12 /// It uses target hooks to lower the ABI but aside from that, the pass 13 /// generated code is generic. This is the default translator used for 14 /// GlobalISel. 15 /// 16 /// \todo Replace the comments with actual doxygen comments. 17 //===----------------------------------------------------------------------===// 18 19 #ifndef LLVM_CODEGEN_GLOBALISEL_IRTRANSLATOR_H 20 #define LLVM_CODEGEN_GLOBALISEL_IRTRANSLATOR_H 21 22 #include "Types.h" 23 #include "llvm/ADT/DenseMap.h" 24 #include "llvm/ADT/SetVector.h" 25 #include "llvm/CodeGen/GlobalISel/MachineIRBuilder.h" 26 #include "llvm/CodeGen/MachineFunctionPass.h" 27 28 namespace llvm { 29 // Forward declarations. 30 class BasicBlock; 31 class CallLowering; 32 class Constant; 33 class Instruction; 34 class MachineBasicBlock; 35 class MachineFunction; 36 class MachineInstr; 37 class OptimizationRemarkEmitter; 38 class MachineRegisterInfo; 39 class TargetPassConfig; 40 41 // Technically the pass should run on an hypothetical MachineModule, 42 // since it should translate Global into some sort of MachineGlobal. 43 // The MachineGlobal should ultimately just be a transfer of ownership of 44 // the interesting bits that are relevant to represent a global value. 45 // That being said, we could investigate what would it cost to just duplicate 46 // the information from the LLVM IR. 47 // The idea is that ultimately we would be able to free up the memory used 48 // by the LLVM IR as soon as the translation is over. 49 class IRTranslator : public MachineFunctionPass { 50 public: 51 static char ID; 52 53 private: 54 /// Interface used to lower the everything related to calls. 55 const CallLowering *CLI; 56 /// Mapping of the values of the current LLVM IR function 57 /// to the related virtual registers. 58 ValueToVReg ValToVReg; 59 60 // N.b. it's not completely obvious that this will be sufficient for every 61 // LLVM IR construct (with "invoke" being the obvious candidate to mess up our 62 // lives. 63 DenseMap<const BasicBlock *, MachineBasicBlock *> BBToMBB; 64 65 // One BasicBlock can be translated to multiple MachineBasicBlocks. For such 66 // BasicBlocks translated to multiple MachineBasicBlocks, MachinePreds retains 67 // a mapping between the edges arriving at the BasicBlock to the corresponding 68 // created MachineBasicBlocks. Some BasicBlocks that get translated to a 69 // single MachineBasicBlock may also end up in this Map. 70 typedef std::pair<const BasicBlock *, const BasicBlock *> CFGEdge; 71 DenseMap<CFGEdge, SmallVector<MachineBasicBlock *, 1>> MachinePreds; 72 73 // List of stubbed PHI instructions, for values and basic blocks to be filled 74 // in once all MachineBasicBlocks have been created. 75 SmallVector<std::pair<const PHINode *, MachineInstr *>, 4> PendingPHIs; 76 77 /// Record of what frame index has been allocated to specified allocas for 78 /// this function. 79 DenseMap<const AllocaInst *, int> FrameIndices; 80 81 /// \name Methods for translating form LLVM IR to MachineInstr. 82 /// \see ::translate for general information on the translate methods. 83 /// @{ 84 85 /// Translate \p Inst into its corresponding MachineInstr instruction(s). 86 /// Insert the newly translated instruction(s) right where the CurBuilder 87 /// is set. 88 /// 89 /// The general algorithm is: 90 /// 1. Look for a virtual register for each operand or 91 /// create one. 92 /// 2 Update the ValToVReg accordingly. 93 /// 2.alt. For constant arguments, if they are compile time constants, 94 /// produce an immediate in the right operand and do not touch 95 /// ValToReg. Actually we will go with a virtual register for each 96 /// constants because it may be expensive to actually materialize the 97 /// constant. Moreover, if the constant spans on several instructions, 98 /// CSE may not catch them. 99 /// => Update ValToVReg and remember that we saw a constant in Constants. 100 /// We will materialize all the constants in finalize. 101 /// Note: we would need to do something so that we can recognize such operand 102 /// as constants. 103 /// 3. Create the generic instruction. 104 /// 105 /// \return true if the translation succeeded. 106 bool translate(const Instruction &Inst); 107 108 /// Materialize \p C into virtual-register \p Reg. The generic instructions 109 /// performing this materialization will be inserted into the entry block of 110 /// the function. 111 /// 112 /// \return true if the materialization succeeded. 113 bool translate(const Constant &C, unsigned Reg); 114 115 /// Translate an LLVM bitcast into generic IR. Either a COPY or a G_BITCAST is 116 /// emitted. 117 bool translateBitCast(const User &U, MachineIRBuilder &MIRBuilder); 118 119 /// Translate an LLVM load instruction into generic IR. 120 bool translateLoad(const User &U, MachineIRBuilder &MIRBuilder); 121 122 /// Translate an LLVM store instruction into generic IR. 123 bool translateStore(const User &U, MachineIRBuilder &MIRBuilder); 124 125 /// Translate an LLVM string intrinsic (memcpy, memset, ...). 126 bool translateMemfunc(const CallInst &CI, MachineIRBuilder &MIRBuilder, 127 unsigned Intrinsic); 128 129 void getStackGuard(unsigned DstReg, MachineIRBuilder &MIRBuilder); 130 131 bool translateOverflowIntrinsic(const CallInst &CI, unsigned Op, 132 MachineIRBuilder &MIRBuilder); 133 134 bool translateKnownIntrinsic(const CallInst &CI, Intrinsic::ID ID, 135 MachineIRBuilder &MIRBuilder); 136 137 bool translateInlineAsm(const CallInst &CI, MachineIRBuilder &MIRBuilder); 138 139 /// Translate call instruction. 140 /// \pre \p U is a call instruction. 141 bool translateCall(const User &U, MachineIRBuilder &MIRBuilder); 142 143 bool translateInvoke(const User &U, MachineIRBuilder &MIRBuilder); 144 145 bool translateLandingPad(const User &U, MachineIRBuilder &MIRBuilder); 146 147 /// Translate one of LLVM's cast instructions into MachineInstrs, with the 148 /// given generic Opcode. 149 bool translateCast(unsigned Opcode, const User &U, 150 MachineIRBuilder &MIRBuilder); 151 152 /// Translate a phi instruction. 153 bool translatePHI(const User &U, MachineIRBuilder &MIRBuilder); 154 155 /// Translate a comparison (icmp or fcmp) instruction or constant. 156 bool translateCompare(const User &U, MachineIRBuilder &MIRBuilder); 157 158 /// Translate an integer compare instruction (or constant). 159 bool translateICmp(const User &U, MachineIRBuilder &MIRBuilder) { 160 return translateCompare(U, MIRBuilder); 161 } 162 163 /// Translate a floating-point compare instruction (or constant). 164 bool translateFCmp(const User &U, MachineIRBuilder &MIRBuilder) { 165 return translateCompare(U, MIRBuilder); 166 } 167 168 169 /// Add remaining operands onto phis we've translated. Executed after all 170 /// MachineBasicBlocks for the function have been created. 171 void finishPendingPhis(); 172 173 /// Translate \p Inst into a binary operation \p Opcode. 174 /// \pre \p U is a binary operation. 175 bool translateBinaryOp(unsigned Opcode, const User &U, 176 MachineIRBuilder &MIRBuilder); 177 178 /// Translate branch (br) instruction. 179 /// \pre \p U is a branch instruction. 180 bool translateBr(const User &U, MachineIRBuilder &MIRBuilder); 181 182 bool translateSwitch(const User &U, MachineIRBuilder &MIRBuilder); 183 184 bool translateIndirectBr(const User &U, MachineIRBuilder &MIRBuilder); 185 186 bool translateExtractValue(const User &U, MachineIRBuilder &MIRBuilder); 187 188 bool translateInsertValue(const User &U, MachineIRBuilder &MIRBuilder); 189 190 bool translateSelect(const User &U, MachineIRBuilder &MIRBuilder); 191 192 bool translateGetElementPtr(const User &U, MachineIRBuilder &MIRBuilder); 193 194 bool translateAlloca(const User &U, MachineIRBuilder &MIRBuilder); 195 196 /// Translate return (ret) instruction. 197 /// The target needs to implement CallLowering::lowerReturn for 198 /// this to succeed. 199 /// \pre \p U is a return instruction. 200 bool translateRet(const User &U, MachineIRBuilder &MIRBuilder); 201 202 bool translateFSub(const User &U, MachineIRBuilder &MIRBuilder); 203 204 bool translateAdd(const User &U, MachineIRBuilder &MIRBuilder) { 205 return translateBinaryOp(TargetOpcode::G_ADD, U, MIRBuilder); 206 } 207 bool translateSub(const User &U, MachineIRBuilder &MIRBuilder) { 208 return translateBinaryOp(TargetOpcode::G_SUB, U, MIRBuilder); 209 } 210 bool translateAnd(const User &U, MachineIRBuilder &MIRBuilder) { 211 return translateBinaryOp(TargetOpcode::G_AND, U, MIRBuilder); 212 } 213 bool translateMul(const User &U, MachineIRBuilder &MIRBuilder) { 214 return translateBinaryOp(TargetOpcode::G_MUL, U, MIRBuilder); 215 } 216 bool translateOr(const User &U, MachineIRBuilder &MIRBuilder) { 217 return translateBinaryOp(TargetOpcode::G_OR, U, MIRBuilder); 218 } 219 bool translateXor(const User &U, MachineIRBuilder &MIRBuilder) { 220 return translateBinaryOp(TargetOpcode::G_XOR, U, MIRBuilder); 221 } 222 223 bool translateUDiv(const User &U, MachineIRBuilder &MIRBuilder) { 224 return translateBinaryOp(TargetOpcode::G_UDIV, U, MIRBuilder); 225 } 226 bool translateSDiv(const User &U, MachineIRBuilder &MIRBuilder) { 227 return translateBinaryOp(TargetOpcode::G_SDIV, U, MIRBuilder); 228 } 229 bool translateURem(const User &U, MachineIRBuilder &MIRBuilder) { 230 return translateBinaryOp(TargetOpcode::G_UREM, U, MIRBuilder); 231 } 232 bool translateSRem(const User &U, MachineIRBuilder &MIRBuilder) { 233 return translateBinaryOp(TargetOpcode::G_SREM, U, MIRBuilder); 234 } 235 bool translateIntToPtr(const User &U, MachineIRBuilder &MIRBuilder) { 236 return translateCast(TargetOpcode::G_INTTOPTR, U, MIRBuilder); 237 } 238 bool translatePtrToInt(const User &U, MachineIRBuilder &MIRBuilder) { 239 return translateCast(TargetOpcode::G_PTRTOINT, U, MIRBuilder); 240 } 241 bool translateTrunc(const User &U, MachineIRBuilder &MIRBuilder) { 242 return translateCast(TargetOpcode::G_TRUNC, U, MIRBuilder); 243 } 244 bool translateFPTrunc(const User &U, MachineIRBuilder &MIRBuilder) { 245 return translateCast(TargetOpcode::G_FPTRUNC, U, MIRBuilder); 246 } 247 bool translateFPExt(const User &U, MachineIRBuilder &MIRBuilder) { 248 return translateCast(TargetOpcode::G_FPEXT, U, MIRBuilder); 249 } 250 bool translateFPToUI(const User &U, MachineIRBuilder &MIRBuilder) { 251 return translateCast(TargetOpcode::G_FPTOUI, U, MIRBuilder); 252 } 253 bool translateFPToSI(const User &U, MachineIRBuilder &MIRBuilder) { 254 return translateCast(TargetOpcode::G_FPTOSI, U, MIRBuilder); 255 } 256 bool translateUIToFP(const User &U, MachineIRBuilder &MIRBuilder) { 257 return translateCast(TargetOpcode::G_UITOFP, U, MIRBuilder); 258 } 259 bool translateSIToFP(const User &U, MachineIRBuilder &MIRBuilder) { 260 return translateCast(TargetOpcode::G_SITOFP, U, MIRBuilder); 261 } 262 bool translateUnreachable(const User &U, MachineIRBuilder &MIRBuilder) { 263 return true; 264 } 265 bool translateSExt(const User &U, MachineIRBuilder &MIRBuilder) { 266 return translateCast(TargetOpcode::G_SEXT, U, MIRBuilder); 267 } 268 269 bool translateZExt(const User &U, MachineIRBuilder &MIRBuilder) { 270 return translateCast(TargetOpcode::G_ZEXT, U, MIRBuilder); 271 } 272 273 bool translateShl(const User &U, MachineIRBuilder &MIRBuilder) { 274 return translateBinaryOp(TargetOpcode::G_SHL, U, MIRBuilder); 275 } 276 bool translateLShr(const User &U, MachineIRBuilder &MIRBuilder) { 277 return translateBinaryOp(TargetOpcode::G_LSHR, U, MIRBuilder); 278 } 279 bool translateAShr(const User &U, MachineIRBuilder &MIRBuilder) { 280 return translateBinaryOp(TargetOpcode::G_ASHR, U, MIRBuilder); 281 } 282 283 bool translateFAdd(const User &U, MachineIRBuilder &MIRBuilder) { 284 return translateBinaryOp(TargetOpcode::G_FADD, U, MIRBuilder); 285 } 286 bool translateFMul(const User &U, MachineIRBuilder &MIRBuilder) { 287 return translateBinaryOp(TargetOpcode::G_FMUL, U, MIRBuilder); 288 } 289 bool translateFDiv(const User &U, MachineIRBuilder &MIRBuilder) { 290 return translateBinaryOp(TargetOpcode::G_FDIV, U, MIRBuilder); 291 } 292 bool translateFRem(const User &U, MachineIRBuilder &MIRBuilder) { 293 return translateBinaryOp(TargetOpcode::G_FREM, U, MIRBuilder); 294 } 295 296 bool translateVAArg(const User &U, MachineIRBuilder &MIRBuilder); 297 298 bool translateInsertElement(const User &U, MachineIRBuilder &MIRBuilder); 299 300 bool translateExtractElement(const User &U, MachineIRBuilder &MIRBuilder); 301 302 bool translateShuffleVector(const User &U, MachineIRBuilder &MIRBuilder); 303 304 // Stubs to keep the compiler happy while we implement the rest of the 305 // translation. 306 bool translateResume(const User &U, MachineIRBuilder &MIRBuilder) { 307 return false; 308 } 309 bool translateCleanupRet(const User &U, MachineIRBuilder &MIRBuilder) { 310 return false; 311 } 312 bool translateCatchRet(const User &U, MachineIRBuilder &MIRBuilder) { 313 return false; 314 } 315 bool translateCatchSwitch(const User &U, MachineIRBuilder &MIRBuilder) { 316 return false; 317 } 318 bool translateFence(const User &U, MachineIRBuilder &MIRBuilder) { 319 return false; 320 } 321 bool translateAtomicCmpXchg(const User &U, MachineIRBuilder &MIRBuilder) { 322 return false; 323 } 324 bool translateAtomicRMW(const User &U, MachineIRBuilder &MIRBuilder) { 325 return false; 326 } 327 bool translateAddrSpaceCast(const User &U, MachineIRBuilder &MIRBuilder) { 328 return false; 329 } 330 bool translateCleanupPad(const User &U, MachineIRBuilder &MIRBuilder) { 331 return false; 332 } 333 bool translateCatchPad(const User &U, MachineIRBuilder &MIRBuilder) { 334 return false; 335 } 336 bool translateUserOp1(const User &U, MachineIRBuilder &MIRBuilder) { 337 return false; 338 } 339 bool translateUserOp2(const User &U, MachineIRBuilder &MIRBuilder) { 340 return false; 341 } 342 343 /// @} 344 345 // Builder for machine instruction a la IRBuilder. 346 // I.e., compared to regular MIBuilder, this one also inserts the instruction 347 // in the current block, it can creates block, etc., basically a kind of 348 // IRBuilder, but for Machine IR. 349 MachineIRBuilder CurBuilder; 350 351 // Builder set to the entry block (just after ABI lowering instructions). Used 352 // as a convenient location for Constants. 353 MachineIRBuilder EntryBuilder; 354 355 // The MachineFunction currently being translated. 356 MachineFunction *MF; 357 358 /// MachineRegisterInfo used to create virtual registers. 359 MachineRegisterInfo *MRI; 360 361 const DataLayout *DL; 362 363 /// Current target configuration. Controls how the pass handles errors. 364 const TargetPassConfig *TPC; 365 366 /// Current optimization remark emitter. Used to report failures. 367 std::unique_ptr<OptimizationRemarkEmitter> ORE; 368 369 // * Insert all the code needed to materialize the constants 370 // at the proper place. E.g., Entry block or dominator block 371 // of each constant depending on how fancy we want to be. 372 // * Clear the different maps. 373 void finalizeFunction(); 374 375 /// Get the VReg that represents \p Val. 376 /// If such VReg does not exist, it is created. 377 unsigned getOrCreateVReg(const Value &Val); 378 379 /// Get the frame index that represents \p Val. 380 /// If such VReg does not exist, it is created. 381 int getOrCreateFrameIndex(const AllocaInst &AI); 382 383 /// Get the alignment of the given memory operation instruction. This will 384 /// either be the explicitly specified value or the ABI-required alignment for 385 /// the type being accessed (according to the Module's DataLayout). 386 unsigned getMemOpAlignment(const Instruction &I); 387 388 /// Get the MachineBasicBlock that represents \p BB. Specifically, the block 389 /// returned will be the head of the translated block (suitable for branch 390 /// destinations). 391 MachineBasicBlock &getMBB(const BasicBlock &BB); 392 393 /// Record \p NewPred as a Machine predecessor to `Edge.second`, corresponding 394 /// to `Edge.first` at the IR level. This is used when IRTranslation creates 395 /// multiple MachineBasicBlocks for a given IR block and the CFG is no longer 396 /// represented simply by the IR-level CFG. 397 void addMachineCFGPred(CFGEdge Edge, MachineBasicBlock *NewPred); 398 399 /// Returns the Machine IR predecessors for the given IR CFG edge. Usually 400 /// this is just the single MachineBasicBlock corresponding to the predecessor 401 /// in the IR. More complex lowering can result in multiple MachineBasicBlocks 402 /// preceding the original though (e.g. switch instructions). 403 SmallVector<MachineBasicBlock *, 1> getMachinePredBBs(CFGEdge Edge) { 404 auto RemappedEdge = MachinePreds.find(Edge); 405 if (RemappedEdge != MachinePreds.end()) 406 return RemappedEdge->second; 407 return SmallVector<MachineBasicBlock *, 4>(1, &getMBB(*Edge.first)); 408 } 409 410 public: 411 // Ctor, nothing fancy. 412 IRTranslator(); 413 414 StringRef getPassName() const override { return "IRTranslator"; } 415 416 void getAnalysisUsage(AnalysisUsage &AU) const override; 417 418 // Algo: 419 // CallLowering = MF.subtarget.getCallLowering() 420 // F = MF.getParent() 421 // MIRBuilder.reset(MF) 422 // getMBB(F.getEntryBB()) 423 // CallLowering->translateArguments(MIRBuilder, F, ValToVReg) 424 // for each bb in F 425 // getMBB(bb) 426 // for each inst in bb 427 // if (!translate(MIRBuilder, inst, ValToVReg, ConstantToSequence)) 428 // report_fatal_error("Don't know how to translate input"); 429 // finalize() 430 bool runOnMachineFunction(MachineFunction &MF) override; 431 }; 432 433 } // End namespace llvm. 434 #endif 435