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