text: //===-- RISCVISelDAGToDAG.cpp - A dag to dag inst selector for RISCV ------===//
  //
  // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
  // See https://llvm.org/LICENSE.txt for license information.
  // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
  //
  //===----------------------------------------------------------------------===//
  //
  // This file defines an instruction selector for the RISCV target.
  //
  //===----------------------------------------------------------------------===//
  
  #include "MCTargetDesc/RISCVMCTargetDesc.h"
  #include "RISCV.h"
  #include "RISCVTargetMachine.h"
  #include "Utils/RISCVMatInt.h"
  #include "llvm/CodeGen/MachineFrameInfo.h"
  #include "llvm/CodeGen/SelectionDAGISel.h"
  #include "llvm/Support/Debug.h"
  #include "llvm/Support/MathExtras.h"
  #include "llvm/Support/raw_ostream.h"
  using namespace llvm;
  
  #define DEBUG_TYPE "riscv-isel"
  
  // RISCV-specific code to select RISCV machine instructions for
  // SelectionDAG operations.
  namespace {
  class RISCVDAGToDAGISel final : public SelectionDAGISel {
    const RISCVSubtarget *Subtarget;
  
  public:
    explicit RISCVDAGToDAGISel(RISCVTargetMachine &TargetMachine)
        : SelectionDAGISel(TargetMachine) {}
  
    StringRef getPassName() const override {
      return "RISCV DAG->DAG Pattern Instruction Selection";
    }
  
    bool runOnMachineFunction(MachineFunction &MF) override {
      Subtarget = &MF.getSubtarget<RISCVSubtarget>();
      return SelectionDAGISel::runOnMachineFunction(MF);
    }
  
    void PostprocessISelDAG() override;
  
    void Select(SDNode *Node) override;
  
    bool SelectInlineAsmMemoryOperand(const SDValue &Op, unsigned ConstraintID,
                                      std::vector<SDValue> &OutOps) override;
  
    bool SelectAddrFI(SDValue Addr, SDValue &Base);
  
  // Include the pieces autogenerated from the target description.
  #include "RISCVGenDAGISel.inc"
  
  private:
    void doPeepholeLoadStoreADDI();
  };
  }
  
  void RISCVDAGToDAGISel::PostprocessISelDAG() {
    doPeepholeLoadStoreADDI();
  }
  
  static SDNode *selectImm(SelectionDAG *CurDAG, const SDLoc &DL, int64_t Imm,
                           MVT XLenVT) {
    RISCVMatInt::InstSeq Seq;
    RISCVMatInt::generateInstSeq(Imm, XLenVT == MVT::i64, Seq);
  
    SDNode *Result;
    SDValue SrcReg = CurDAG->getRegister(RISCV::X0, XLenVT);
    for (RISCVMatInt::Inst &Inst : Seq) {
      SDValue SDImm = CurDAG->getTargetConstant(Inst.Imm, DL, XLenVT);
      if (Inst.Opc == RISCV::LUI)
        Result = CurDAG->getMachineNode(RISCV::LUI, DL, XLenVT, SDImm);
      else
        Result = CurDAG->getMachineNode(Inst.Opc, DL, XLenVT, SrcReg, SDImm);
  
      // Only the first instruction has X0 as its source.
      SrcReg = SDValue(Result, 0);
    }
  
    return Result;
  }
  
  // Returns true if the Node is an ISD::AND with a constant argument. If so,
  // set Mask to that constant value.
  static bool isConstantMask(SDNode *Node, uint64_t &Mask) {
    if (Node->getOpcode() == ISD::AND &&
        Node->getOperand(1).getOpcode() == ISD::Constant) {
      Mask = cast<ConstantSDNode>(Node->getOperand(1))->getZExtValue();
      return true;
    }
    return false;
  }
  
  void RISCVDAGToDAGISel::Select(SDNode *Node) {
    // If we have a custom node, we have already selected.
    if (Node->isMachineOpcode()) {
      LLVM_DEBUG(dbgs() << "== "; Node->dump(CurDAG); dbgs() << "\n");
      Node->setNodeId(-1);
      return;
    }
  
    // Instruction Selection not handled by the auto-generated tablegen selection
    // should be handled here.
    unsigned Opcode = Node->getOpcode();
    MVT XLenVT = Subtarget->getXLenVT();
    SDLoc DL(Node);
    EVT VT = Node->getValueType(0);
  
    switch (Opcode) {
    case ISD::Constant: {
      auto ConstNode = cast<ConstantSDNode>(Node);
      if (VT == XLenVT && ConstNode->isNullValue()) {
        SDValue New = CurDAG->getCopyFromReg(CurDAG->getEntryNode(), SDLoc(Node),
                                             RISCV::X0, XLenVT);
        ReplaceNode(Node, New.getNode());
        return;
      }
      int64_t Imm = ConstNode->getSExtValue();
      if (XLenVT == MVT::i64) {
        ReplaceNode(Node, selectImm(CurDAG, SDLoc(Node), Imm, XLenVT));
        return;
      }
      break;
    }
    case ISD::FrameIndex: {
      SDValue Imm = CurDAG->getTargetConstant(0, DL, XLenVT);
      int FI = cast<FrameIndexSDNode>(Node)->getIndex();
      SDValue TFI = CurDAG->getTargetFrameIndex(FI, VT);
      ReplaceNode(Node, CurDAG->getMachineNode(RISCV::ADDI, DL, VT, TFI, Imm));
      return;
    }
    case ISD::SRL: {
      if (!Subtarget->is64Bit())
        break;
      SDValue Op0 = Node->getOperand(0);
      SDValue Op1 = Node->getOperand(1);
      uint64_t Mask;
      // Match (srl (and val, mask), imm) where the result would be a
      // zero-extended 32-bit integer. i.e. the mask is 0xffffffff or the result
      // is equivalent to this (SimplifyDemandedBits may have removed lower bits
      // from the mask that aren't necessary due to the right-shifting).
      if (Op1.getOpcode() == ISD::Constant &&
          isConstantMask(Op0.getNode(), Mask)) {
        uint64_t ShAmt = cast<ConstantSDNode>(Op1.getNode())->getZExtValue();
  
        if ((Mask | maskTrailingOnes<uint64_t>(ShAmt)) == 0xffffffff) {
          SDValue ShAmtVal =
              CurDAG->getTargetConstant(ShAmt, SDLoc(Node), XLenVT);
          CurDAG->SelectNodeTo(Node, RISCV::SRLIW, XLenVT, Op0.getOperand(0),
                               ShAmtVal);
          return;
        }
      }
      break;
    }
    case RISCVISD::READ_CYCLE_WIDE:
      assert(!Subtarget->is64Bit() && "READ_CYCLE_WIDE is only used on riscv32");
  
      ReplaceNode(Node, CurDAG->getMachineNode(RISCV::ReadCycleWide, DL, MVT::i32,
                                               MVT::i32, MVT::Other,
                                               Node->getOperand(0)));
      return;
    }
  
    // Select the default instruction.
    SelectCode(Node);
  }
  
  bool RISCVDAGToDAGISel::SelectInlineAsmMemoryOperand(
      const SDValue &Op, unsigned ConstraintID, std::vector<SDValue> &OutOps) {
    switch (ConstraintID) {
    case InlineAsm::Constraint_i:
    case InlineAsm::Constraint_m:
      // We just support simple memory operands that have a single address
      // operand and need no special handling.
      OutOps.push_back(Op);
      return false;
    case InlineAsm::Constraint_A:
      OutOps.push_back(Op);
      return false;
    default:
      break;
    }
  
    return true;
  }
  
  bool RISCVDAGToDAGISel::SelectAddrFI(SDValue Addr, SDValue &Base) {
    if (auto FIN = dyn_cast<FrameIndexSDNode>(Addr)) {
      Base = CurDAG->getTargetFrameIndex(FIN->getIndex(), Subtarget->getXLenVT());
      return true;
    }
    return false;
  }
  
  // Merge an ADDI into the offset of a load/store instruction where possible.
  // (load (add base, off), 0) -> (load base, off)
  // (store val, (add base, off)) -> (store val, base, off)
  void RISCVDAGToDAGISel::doPeepholeLoadStoreADDI() {
    SelectionDAG::allnodes_iterator Position(CurDAG->getRoot().getNode());
    ++Position;
  
    while (Position != CurDAG->allnodes_begin()) {
      SDNode *N = &*--Position;
      // Skip dead nodes and any non-machine opcodes.
      if (N->use_empty() || !N->isMachineOpcode())
        continue;
  
      int OffsetOpIdx;
      int BaseOpIdx;
  
      // Only attempt this optimisation for I-type loads and S-type stores.
      switch (N->getMachineOpcode()) {
      default:
        continue;
      case RISCV::LB:
      case RISCV::LH:
      case RISCV::LW:
      case RISCV::LBU:
      case RISCV::LHU:
      case RISCV::LWU:
      case RISCV::LD:
      case RISCV::FLW:
      case RISCV::FLD:
        BaseOpIdx = 0;
        OffsetOpIdx = 1;
        break;
      case RISCV::SB:
      case RISCV::SH:
      case RISCV::SW:
      case RISCV::SD:
      case RISCV::FSW:
      case RISCV::FSD:
        BaseOpIdx = 1;
        OffsetOpIdx = 2;
        break;
      }
  
      // Currently, the load/store offset must be 0 to be considered for this
      // peephole optimisation.
      if (!isa<ConstantSDNode>(N->getOperand(OffsetOpIdx)) ||
          N->getConstantOperandVal(OffsetOpIdx) != 0)
        continue;
  
      SDValue Base = N->getOperand(BaseOpIdx);
  
      // If the base is an ADDI, we can merge it in to the load/store.
      if (!Base.isMachineOpcode() || Base.getMachineOpcode() != RISCV::ADDI)
        continue;
  
      SDValue ImmOperand = Base.getOperand(1);
  
      if (auto Const = dyn_cast<ConstantSDNode>(ImmOperand)) {
        ImmOperand = CurDAG->getTargetConstant(
            Const->getSExtValue(), SDLoc(ImmOperand), ImmOperand.getValueType());
      } else if (auto GA = dyn_cast<GlobalAddressSDNode>(ImmOperand)) {
        ImmOperand = CurDAG->getTargetGlobalAddress(
            GA->getGlobal(), SDLoc(ImmOperand), ImmOperand.getValueType(),
            GA->getOffset(), GA->getTargetFlags());
      } else {
        continue;
      }
  
      LLVM_DEBUG(dbgs() << "Folding add-immediate into mem-op:\nBase:    ");
      LLVM_DEBUG(Base->dump(CurDAG));
      LLVM_DEBUG(dbgs() << "\nN: ");
      LLVM_DEBUG(N->dump(CurDAG));
      LLVM_DEBUG(dbgs() << "\n");
  
      // Modify the offset operand of the load/store.
      if (BaseOpIdx == 0) // Load
        CurDAG->UpdateNodeOperands(N, Base.getOperand(0), ImmOperand,
                                   N->getOperand(2));
      else // Store
        CurDAG->UpdateNodeOperands(N, N->getOperand(0), Base.getOperand(0),
                                   ImmOperand, N->getOperand(3));
  
      // The add-immediate may now be dead, in which case remove it.
      if (Base.getNode()->use_empty())
        CurDAG->RemoveDeadNode(Base.getNode());
    }
  }
  
  // This pass converts a legalized DAG into a RISCV-specific DAG, ready
  // for instruction scheduling.
  FunctionPass *llvm::createRISCVISelDag(RISCVTargetMachine &TM) {
    return new RISCVDAGToDAGISel(TM);
  }
  