//===- llvm/CodeGen/GlobalISel/IRTranslator.h - IRTranslator ----*- C++ -*-===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
/// \file
/// This file declares the IRTranslator pass.
/// This pass is responsible for translating LLVM IR into MachineInstr.
/// It uses target hooks to lower the ABI but aside from that, the pass
/// generated code is generic. This is the default translator used for
/// GlobalISel.
///
/// \todo Replace the comments with actual doxygen comments.
//===----------------------------------------------------------------------===//

#ifndef LLVM_CODEGEN_GLOBALISEL_IRTRANSLATOR_H
#define LLVM_CODEGEN_GLOBALISEL_IRTRANSLATOR_H

#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/CodeGen/GlobalISel/MachineIRBuilder.h"
#include "llvm/CodeGen/GlobalISel/Types.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/Support/Allocator.h"
#include "llvm/IR/Intrinsics.h"
#include <memory>
#include <utility>

namespace llvm {

class AllocaInst;
class BasicBlock;
class CallInst;
class CallLowering;
class Constant;
class DataLayout;
class Instruction;
class MachineBasicBlock;
class MachineFunction;
class MachineInstr;
class MachineRegisterInfo;
class OptimizationRemarkEmitter;
class PHINode;
class TargetPassConfig;
class User;
class Value;

// Technically the pass should run on an hypothetical MachineModule,
// since it should translate Global into some sort of MachineGlobal.
// The MachineGlobal should ultimately just be a transfer of ownership of
// the interesting bits that are relevant to represent a global value.
// That being said, we could investigate what would it cost to just duplicate
// the information from the LLVM IR.
// The idea is that ultimately we would be able to free up the memory used
// by the LLVM IR as soon as the translation is over.
class IRTranslator : public MachineFunctionPass {
public:
  static char ID;

private:
  /// Interface used to lower the everything related to calls.
  const CallLowering *CLI;

  /// This class contains the mapping between the Values to vreg related data.
  class ValueToVRegInfo {
  public:
    ValueToVRegInfo() = default;

    using VRegListT = SmallVector<unsigned, 1>;
    using OffsetListT = SmallVector<uint64_t, 1>;

    using const_vreg_iterator =
        DenseMap<const Value *, VRegListT *>::const_iterator;
    using const_offset_iterator =
        DenseMap<const Value *, OffsetListT *>::const_iterator;

    inline const_vreg_iterator vregs_end() const { return ValToVRegs.end(); }

    VRegListT *getVRegs(const Value &V) {
      auto It = ValToVRegs.find(&V);
      if (It != ValToVRegs.end())
        return It->second;

      return insertVRegs(V);
    }

    OffsetListT *getOffsets(const Value &V) {
      auto It = TypeToOffsets.find(V.getType());
      if (It != TypeToOffsets.end())
        return It->second;

      return insertOffsets(V);
    }

    const_vreg_iterator findVRegs(const Value &V) const {
      return ValToVRegs.find(&V);
    }

    bool contains(const Value &V) const {
      return ValToVRegs.find(&V) != ValToVRegs.end();
    }

    void reset() {
      ValToVRegs.clear();
      TypeToOffsets.clear();
      VRegAlloc.DestroyAll();
      OffsetAlloc.DestroyAll();
    }

  private:
    VRegListT *insertVRegs(const Value &V) {
      assert(ValToVRegs.find(&V) == ValToVRegs.end() && "Value already exists");

      // We placement new using our fast allocator since we never try to free
      // the vectors until translation is finished.
      auto *VRegList = new (VRegAlloc.Allocate()) VRegListT();
      ValToVRegs[&V] = VRegList;
      return VRegList;
    }

    OffsetListT *insertOffsets(const Value &V) {
      assert(TypeToOffsets.find(V.getType()) == TypeToOffsets.end() &&
             "Type already exists");

      auto *OffsetList = new (OffsetAlloc.Allocate()) OffsetListT();
      TypeToOffsets[V.getType()] = OffsetList;
      return OffsetList;
    }
    SpecificBumpPtrAllocator<VRegListT> VRegAlloc;
    SpecificBumpPtrAllocator<OffsetListT> OffsetAlloc;

    // We store pointers to vectors here since references may be invalidated
    // while we hold them if we stored the vectors directly.
    DenseMap<const Value *, VRegListT*> ValToVRegs;
    DenseMap<const Type *, OffsetListT*> TypeToOffsets;
  };

  /// Mapping of the values of the current LLVM IR function to the related
  /// virtual registers and offsets.
  ValueToVRegInfo VMap;

  // N.b. it's not completely obvious that this will be sufficient for every
  // LLVM IR construct (with "invoke" being the obvious candidate to mess up our
  // lives.
  DenseMap<const BasicBlock *, MachineBasicBlock *> BBToMBB;

  // One BasicBlock can be translated to multiple MachineBasicBlocks.  For such
  // BasicBlocks translated to multiple MachineBasicBlocks, MachinePreds retains
  // a mapping between the edges arriving at the BasicBlock to the corresponding
  // created MachineBasicBlocks. Some BasicBlocks that get translated to a
  // single MachineBasicBlock may also end up in this Map.
  using CFGEdge = std::pair<const BasicBlock *, const BasicBlock *>;
  DenseMap<CFGEdge, SmallVector<MachineBasicBlock *, 1>> MachinePreds;

  // List of stubbed PHI instructions, for values and basic blocks to be filled
  // in once all MachineBasicBlocks have been created.
  SmallVector<std::pair<const PHINode *, SmallVector<MachineInstr *, 1>>, 4>
      PendingPHIs;

  /// Record of what frame index has been allocated to specified allocas for
  /// this function.
  DenseMap<const AllocaInst *, int> FrameIndices;

  /// \name Methods for translating form LLVM IR to MachineInstr.
  /// \see ::translate for general information on the translate methods.
  /// @{

  /// Translate \p Inst into its corresponding MachineInstr instruction(s).
  /// Insert the newly translated instruction(s) right where the CurBuilder
  /// is set.
  ///
  /// The general algorithm is:
  /// 1. Look for a virtual register for each operand or
  ///    create one.
  /// 2 Update the VMap accordingly.
  /// 2.alt. For constant arguments, if they are compile time constants,
  ///   produce an immediate in the right operand and do not touch
  ///   ValToReg. Actually we will go with a virtual register for each
  ///   constants because it may be expensive to actually materialize the
  ///   constant. Moreover, if the constant spans on several instructions,
  ///   CSE may not catch them.
  ///   => Update ValToVReg and remember that we saw a constant in Constants.
  ///   We will materialize all the constants in finalize.
  /// Note: we would need to do something so that we can recognize such operand
  ///       as constants.
  /// 3. Create the generic instruction.
  ///
  /// \return true if the translation succeeded.
  bool translate(const Instruction &Inst);

  /// Materialize \p C into virtual-register \p Reg. The generic instructions
  /// performing this materialization will be inserted into the entry block of
  /// the function.
  ///
  /// \return true if the materialization succeeded.
  bool translate(const Constant &C, unsigned Reg);

  /// Translate an LLVM bitcast into generic IR. Either a COPY or a G_BITCAST is
  /// emitted.
  bool translateBitCast(const User &U, MachineIRBuilder &MIRBuilder);

  /// Translate an LLVM load instruction into generic IR.
  bool translateLoad(const User &U, MachineIRBuilder &MIRBuilder);

  /// Translate an LLVM store instruction into generic IR.
  bool translateStore(const User &U, MachineIRBuilder &MIRBuilder);

  /// Translate an LLVM string intrinsic (memcpy, memset, ...).
  bool translateMemfunc(const CallInst &CI, MachineIRBuilder &MIRBuilder,
                        unsigned ID);

  void getStackGuard(unsigned DstReg, MachineIRBuilder &MIRBuilder);

  bool translateOverflowIntrinsic(const CallInst &CI, unsigned Op,
                                  MachineIRBuilder &MIRBuilder);

  bool translateKnownIntrinsic(const CallInst &CI, Intrinsic::ID ID,
                               MachineIRBuilder &MIRBuilder);

  bool translateInlineAsm(const CallInst &CI, MachineIRBuilder &MIRBuilder);

  // FIXME: temporary function to expose previous interface to call lowering
  // until it is refactored.
  /// Combines all component registers of \p V into a single scalar with size
  /// "max(Offsets) + last size".
  unsigned packRegs(const Value &V, MachineIRBuilder &MIRBuilder);

  void unpackRegs(const Value &V, unsigned Src, MachineIRBuilder &MIRBuilder);

  /// Returns true if the value should be split into multiple LLTs.
  /// If \p Offsets is given then the split type's offsets will be stored in it.
  /// If \p Offsets is not empty it will be cleared first.
  bool valueIsSplit(const Value &V,
                    SmallVectorImpl<uint64_t> *Offsets = nullptr);

  /// Translate call instruction.
  /// \pre \p U is a call instruction.
  bool translateCall(const User &U, MachineIRBuilder &MIRBuilder);

  bool translateInvoke(const User &U, MachineIRBuilder &MIRBuilder);

  bool translateLandingPad(const User &U, MachineIRBuilder &MIRBuilder);

  /// Translate one of LLVM's cast instructions into MachineInstrs, with the
  /// given generic Opcode.
  bool translateCast(unsigned Opcode, const User &U,
                     MachineIRBuilder &MIRBuilder);

  /// Translate a phi instruction.
  bool translatePHI(const User &U, MachineIRBuilder &MIRBuilder);

  /// Translate a comparison (icmp or fcmp) instruction or constant.
  bool translateCompare(const User &U, MachineIRBuilder &MIRBuilder);

  /// Translate an integer compare instruction (or constant).
  bool translateICmp(const User &U, MachineIRBuilder &MIRBuilder) {
    return translateCompare(U, MIRBuilder);
  }

  /// Translate a floating-point compare instruction (or constant).
  bool translateFCmp(const User &U, MachineIRBuilder &MIRBuilder) {
    return translateCompare(U, MIRBuilder);
  }

  /// Add remaining operands onto phis we've translated. Executed after all
  /// MachineBasicBlocks for the function have been created.
  void finishPendingPhis();

  /// Translate \p Inst into a binary operation \p Opcode.
  /// \pre \p U is a binary operation.
  bool translateBinaryOp(unsigned Opcode, const User &U,
                         MachineIRBuilder &MIRBuilder);

  /// Translate branch (br) instruction.
  /// \pre \p U is a branch instruction.
  bool translateBr(const User &U, MachineIRBuilder &MIRBuilder);

  bool translateSwitch(const User &U, MachineIRBuilder &MIRBuilder);

  bool translateIndirectBr(const User &U, MachineIRBuilder &MIRBuilder);

  bool translateExtractValue(const User &U, MachineIRBuilder &MIRBuilder);

  bool translateInsertValue(const User &U, MachineIRBuilder &MIRBuilder);

  bool translateSelect(const User &U, MachineIRBuilder &MIRBuilder);

  bool translateGetElementPtr(const User &U, MachineIRBuilder &MIRBuilder);

  bool translateAlloca(const User &U, MachineIRBuilder &MIRBuilder);

  /// Translate return (ret) instruction.
  /// The target needs to implement CallLowering::lowerReturn for
  /// this to succeed.
  /// \pre \p U is a return instruction.
  bool translateRet(const User &U, MachineIRBuilder &MIRBuilder);

  bool translateFSub(const User &U, MachineIRBuilder &MIRBuilder);

  bool translateFNeg(const User &U, MachineIRBuilder &MIRBuilder);

  bool translateAdd(const User &U, MachineIRBuilder &MIRBuilder) {
    return translateBinaryOp(TargetOpcode::G_ADD, U, MIRBuilder);
  }
  bool translateSub(const User &U, MachineIRBuilder &MIRBuilder) {
    return translateBinaryOp(TargetOpcode::G_SUB, U, MIRBuilder);
  }
  bool translateAnd(const User &U, MachineIRBuilder &MIRBuilder) {
    return translateBinaryOp(TargetOpcode::G_AND, U, MIRBuilder);
  }
  bool translateMul(const User &U, MachineIRBuilder &MIRBuilder) {
    return translateBinaryOp(TargetOpcode::G_MUL, U, MIRBuilder);
  }
  bool translateOr(const User &U, MachineIRBuilder &MIRBuilder) {
    return translateBinaryOp(TargetOpcode::G_OR, U, MIRBuilder);
  }
  bool translateXor(const User &U, MachineIRBuilder &MIRBuilder) {
    return translateBinaryOp(TargetOpcode::G_XOR, U, MIRBuilder);
  }

  bool translateUDiv(const User &U, MachineIRBuilder &MIRBuilder) {
    return translateBinaryOp(TargetOpcode::G_UDIV, U, MIRBuilder);
  }
  bool translateSDiv(const User &U, MachineIRBuilder &MIRBuilder) {
    return translateBinaryOp(TargetOpcode::G_SDIV, U, MIRBuilder);
  }
  bool translateURem(const User &U, MachineIRBuilder &MIRBuilder) {
    return translateBinaryOp(TargetOpcode::G_UREM, U, MIRBuilder);
  }
  bool translateSRem(const User &U, MachineIRBuilder &MIRBuilder) {
    return translateBinaryOp(TargetOpcode::G_SREM, U, MIRBuilder);
  }
  bool translateIntToPtr(const User &U, MachineIRBuilder &MIRBuilder) {
    return translateCast(TargetOpcode::G_INTTOPTR, U, MIRBuilder);
  }
  bool translatePtrToInt(const User &U, MachineIRBuilder &MIRBuilder) {
    return translateCast(TargetOpcode::G_PTRTOINT, U, MIRBuilder);
  }
  bool translateTrunc(const User &U, MachineIRBuilder &MIRBuilder) {
    return translateCast(TargetOpcode::G_TRUNC, U, MIRBuilder);
  }
  bool translateFPTrunc(const User &U, MachineIRBuilder &MIRBuilder) {
    return translateCast(TargetOpcode::G_FPTRUNC, U, MIRBuilder);
  }
  bool translateFPExt(const User &U, MachineIRBuilder &MIRBuilder) {
    return translateCast(TargetOpcode::G_FPEXT, U, MIRBuilder);
  }
  bool translateFPToUI(const User &U, MachineIRBuilder &MIRBuilder) {
    return translateCast(TargetOpcode::G_FPTOUI, U, MIRBuilder);
  }
  bool translateFPToSI(const User &U, MachineIRBuilder &MIRBuilder) {
    return translateCast(TargetOpcode::G_FPTOSI, U, MIRBuilder);
  }
  bool translateUIToFP(const User &U, MachineIRBuilder &MIRBuilder) {
    return translateCast(TargetOpcode::G_UITOFP, U, MIRBuilder);
  }
  bool translateSIToFP(const User &U, MachineIRBuilder &MIRBuilder) {
    return translateCast(TargetOpcode::G_SITOFP, U, MIRBuilder);
  }
  bool translateUnreachable(const User &U, MachineIRBuilder &MIRBuilder) {
    return true;
  }
  bool translateSExt(const User &U, MachineIRBuilder &MIRBuilder) {
    return translateCast(TargetOpcode::G_SEXT, U, MIRBuilder);
  }

  bool translateZExt(const User &U, MachineIRBuilder &MIRBuilder) {
    return translateCast(TargetOpcode::G_ZEXT, U, MIRBuilder);
  }

  bool translateShl(const User &U, MachineIRBuilder &MIRBuilder) {
    return translateBinaryOp(TargetOpcode::G_SHL, U, MIRBuilder);
  }
  bool translateLShr(const User &U, MachineIRBuilder &MIRBuilder) {
    return translateBinaryOp(TargetOpcode::G_LSHR, U, MIRBuilder);
  }
  bool translateAShr(const User &U, MachineIRBuilder &MIRBuilder) {
    return translateBinaryOp(TargetOpcode::G_ASHR, U, MIRBuilder);
  }

  bool translateFAdd(const User &U, MachineIRBuilder &MIRBuilder) {
    return translateBinaryOp(TargetOpcode::G_FADD, U, MIRBuilder);
  }
  bool translateFMul(const User &U, MachineIRBuilder &MIRBuilder) {
    return translateBinaryOp(TargetOpcode::G_FMUL, U, MIRBuilder);
  }
  bool translateFDiv(const User &U, MachineIRBuilder &MIRBuilder) {
    return translateBinaryOp(TargetOpcode::G_FDIV, U, MIRBuilder);
  }
  bool translateFRem(const User &U, MachineIRBuilder &MIRBuilder) {
    return translateBinaryOp(TargetOpcode::G_FREM, U, MIRBuilder);
  }

  bool translateVAArg(const User &U, MachineIRBuilder &MIRBuilder);

  bool translateInsertElement(const User &U, MachineIRBuilder &MIRBuilder);

  bool translateExtractElement(const User &U, MachineIRBuilder &MIRBuilder);

  bool translateShuffleVector(const User &U, MachineIRBuilder &MIRBuilder);

  bool translateAtomicCmpXchg(const User &U, MachineIRBuilder &MIRBuilder);
  bool translateAtomicRMW(const User &U, MachineIRBuilder &MIRBuilder);

  // Stubs to keep the compiler happy while we implement the rest of the
  // translation.
  bool translateResume(const User &U, MachineIRBuilder &MIRBuilder) {
    return false;
  }
  bool translateCleanupRet(const User &U, MachineIRBuilder &MIRBuilder) {
    return false;
  }
  bool translateCatchRet(const User &U, MachineIRBuilder &MIRBuilder) {
    return false;
  }
  bool translateCatchSwitch(const User &U, MachineIRBuilder &MIRBuilder) {
    return false;
  }
  bool translateFence(const User &U, MachineIRBuilder &MIRBuilder) {
    return false;
  }
  bool translateAddrSpaceCast(const User &U, MachineIRBuilder &MIRBuilder) {
    return translateCast(TargetOpcode::G_ADDRSPACE_CAST, U, MIRBuilder);
  }
  bool translateCleanupPad(const User &U, MachineIRBuilder &MIRBuilder) {
    return false;
  }
  bool translateCatchPad(const User &U, MachineIRBuilder &MIRBuilder) {
    return false;
  }
  bool translateUserOp1(const User &U, MachineIRBuilder &MIRBuilder) {
    return false;
  }
  bool translateUserOp2(const User &U, MachineIRBuilder &MIRBuilder) {
    return false;
  }

  /// @}

  // Builder for machine instruction a la IRBuilder.
  // I.e., compared to regular MIBuilder, this one also inserts the instruction
  // in the current block, it can creates block, etc., basically a kind of
  // IRBuilder, but for Machine IR.
  MachineIRBuilder CurBuilder;

  // Builder set to the entry block (just after ABI lowering instructions). Used
  // as a convenient location for Constants.
  MachineIRBuilder EntryBuilder;

  // The MachineFunction currently being translated.
  MachineFunction *MF;

  /// MachineRegisterInfo used to create virtual registers.
  MachineRegisterInfo *MRI = nullptr;

  const DataLayout *DL;

  /// Current target configuration. Controls how the pass handles errors.
  const TargetPassConfig *TPC;

  /// Current optimization remark emitter. Used to report failures.
  std::unique_ptr<OptimizationRemarkEmitter> ORE;

  // * Insert all the code needed to materialize the constants
  // at the proper place. E.g., Entry block or dominator block
  // of each constant depending on how fancy we want to be.
  // * Clear the different maps.
  void finalizeFunction();

  /// Get the VRegs that represent \p Val.
  /// Non-aggregate types have just one corresponding VReg and the list can be
  /// used as a single "unsigned". Aggregates get flattened. If such VRegs do
  /// not exist, they are created.
  ArrayRef<unsigned> getOrCreateVRegs(const Value &Val);

  unsigned getOrCreateVReg(const Value &Val) {
    auto Regs = getOrCreateVRegs(Val);
    if (Regs.empty())
      return 0;
    assert(Regs.size() == 1 &&
           "attempt to get single VReg for aggregate or void");
    return Regs[0];
  }

  /// Allocate some vregs and offsets in the VMap. Then populate just the
  /// offsets while leaving the vregs empty.
  ValueToVRegInfo::VRegListT &allocateVRegs(const Value &Val);

  /// Get the frame index that represents \p Val.
  /// If such VReg does not exist, it is created.
  int getOrCreateFrameIndex(const AllocaInst &AI);

  /// Get the alignment of the given memory operation instruction. This will
  /// either be the explicitly specified value or the ABI-required alignment for
  /// the type being accessed (according to the Module's DataLayout).
  unsigned getMemOpAlignment(const Instruction &I);

  /// Get the MachineBasicBlock that represents \p BB. Specifically, the block
  /// returned will be the head of the translated block (suitable for branch
  /// destinations).
  MachineBasicBlock &getMBB(const BasicBlock &BB);

  /// Record \p NewPred as a Machine predecessor to `Edge.second`, corresponding
  /// to `Edge.first` at the IR level. This is used when IRTranslation creates
  /// multiple MachineBasicBlocks for a given IR block and the CFG is no longer
  /// represented simply by the IR-level CFG.
  void addMachineCFGPred(CFGEdge Edge, MachineBasicBlock *NewPred);

  /// Returns the Machine IR predecessors for the given IR CFG edge. Usually
  /// this is just the single MachineBasicBlock corresponding to the predecessor
  /// in the IR. More complex lowering can result in multiple MachineBasicBlocks
  /// preceding the original though (e.g. switch instructions).
  SmallVector<MachineBasicBlock *, 1> getMachinePredBBs(CFGEdge Edge) {
    auto RemappedEdge = MachinePreds.find(Edge);
    if (RemappedEdge != MachinePreds.end())
      return RemappedEdge->second;
    return SmallVector<MachineBasicBlock *, 4>(1, &getMBB(*Edge.first));
  }

public:
  // Ctor, nothing fancy.
  IRTranslator();

  StringRef getPassName() const override { return "IRTranslator"; }

  void getAnalysisUsage(AnalysisUsage &AU) const override;

  // Algo:
  //   CallLowering = MF.subtarget.getCallLowering()
  //   F = MF.getParent()
  //   MIRBuilder.reset(MF)
  //   getMBB(F.getEntryBB())
  //   CallLowering->translateArguments(MIRBuilder, F, ValToVReg)
  //   for each bb in F
  //     getMBB(bb)
  //     for each inst in bb
  //       if (!translate(MIRBuilder, inst, ValToVReg, ConstantToSequence))
  //         report_fatal_error("Don't know how to translate input");
  //   finalize()
  bool runOnMachineFunction(MachineFunction &MF) override;
};

} // end namespace llvm

#endif // LLVM_CODEGEN_GLOBALISEL_IRTRANSLATOR_H