Target/Hexagon/HexagonOptAddrMode.cpp

//===- HexagonOptAddrMode.cpp ---------------------------------------------===//
//
// 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 implements a Hexagon-specific pass to optimize addressing mode for
// load/store instructions.
//===----------------------------------------------------------------------===//

#include "HexagonInstrInfo.h"
#include "HexagonSubtarget.h"
#include "MCTargetDesc/HexagonBaseInfo.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/StringRef.h"
#include "llvm/CodeGen/MachineBasicBlock.h"
#include "llvm/CodeGen/MachineDominanceFrontier.h"
#include "llvm/CodeGen/MachineDominators.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineInstr.h"
#include "llvm/CodeGen/MachineInstrBuilder.h"
#include "llvm/CodeGen/MachineOperand.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/RDFGraph.h"
#include "llvm/CodeGen/RDFLiveness.h"
#include "llvm/CodeGen/RDFRegisters.h"
#include "llvm/CodeGen/TargetSubtargetInfo.h"
#include "llvm/InitializePasses.h"
#include "llvm/MC/MCInstrDesc.h"
#include "llvm/Pass.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/raw_ostream.h"
#include <cassert>
#include <cstdint>

#define DEBUG_TYPE "opt-addr-mode"

using namespace llvm;
using namespace rdf;

static cl::opt<int> CodeGrowthLimit("hexagon-amode-growth-limit",
  cl::Hidden, cl::init(0), cl::desc("Code growth limit for address mode "
  "optimization"));

extern cl::opt<unsigned> RDFFuncBlockLimit;

namespace llvm {

  FunctionPass *createHexagonOptAddrMode();
  void initializeHexagonOptAddrModePass(PassRegistry&);

} // end namespace llvm

namespace {

class HexagonOptAddrMode : public MachineFunctionPass {
public:
  static char ID;

  HexagonOptAddrMode() : MachineFunctionPass(ID) {}

  StringRef getPassName() const override {
    return "Optimize addressing mode of load/store";
  }

  void getAnalysisUsage(AnalysisUsage &AU) const override {
    MachineFunctionPass::getAnalysisUsage(AU);
    AU.addRequired<MachineDominatorTreeWrapperPass>();
    AU.addRequired<MachineDominanceFrontier>();
    AU.setPreservesAll();
  }

  bool runOnMachineFunction(MachineFunction &MF) override;

private:
  using MISetType = DenseSet<MachineInstr *>;
  using InstrEvalMap = DenseMap<MachineInstr *, bool>;

  MachineRegisterInfo *MRI = nullptr;
  const HexagonInstrInfo *HII = nullptr;
  const HexagonRegisterInfo *HRI = nullptr;
  MachineDominatorTree *MDT = nullptr;
  DataFlowGraph *DFG = nullptr;
  DataFlowGraph::DefStackMap DefM;
  Liveness *LV = nullptr;
  MISetType Deleted;

  bool processBlock(NodeAddr<BlockNode *> BA);
  bool xformUseMI(MachineInstr *TfrMI, MachineInstr *UseMI,
                  NodeAddr<UseNode *> UseN, unsigned UseMOnum);
  bool processAddUses(NodeAddr<StmtNode *> AddSN, MachineInstr *AddMI,
                      const NodeList &UNodeList);
  bool updateAddUses(MachineInstr *AddMI, MachineInstr *UseMI);
  bool analyzeUses(unsigned DefR, const NodeList &UNodeList,
                   InstrEvalMap &InstrEvalResult, short &SizeInc);
  bool hasRepForm(MachineInstr &MI, unsigned TfrDefR);
  bool canRemoveAddasl(NodeAddr<StmtNode *> AddAslSN, MachineInstr &MI,
                       const NodeList &UNodeList);
  bool isSafeToExtLR(NodeAddr<StmtNode *> SN, MachineInstr *MI,
                     unsigned LRExtReg, const NodeList &UNodeList);
  void getAllRealUses(NodeAddr<StmtNode *> SN, NodeList &UNodeList);
  bool allValidCandidates(NodeAddr<StmtNode *> SA, NodeList &UNodeList);
  short getBaseWithLongOffset(const MachineInstr &MI) const;
  bool changeStore(MachineInstr *OldMI, MachineOperand ImmOp,
                   unsigned ImmOpNum);
  bool changeLoad(MachineInstr *OldMI, MachineOperand ImmOp, unsigned ImmOpNum);
  bool changeAddAsl(NodeAddr<UseNode *> AddAslUN, MachineInstr *AddAslMI,
                    const MachineOperand &ImmOp, unsigned ImmOpNum);
  bool isValidOffset(MachineInstr *MI, int Offset);
  unsigned getBaseOpPosition(MachineInstr *MI);
  unsigned getOffsetOpPosition(MachineInstr *MI);
};

} // end anonymous namespace

char HexagonOptAddrMode::ID = 0;

INITIALIZE_PASS_BEGIN(HexagonOptAddrMode, "amode-opt",
                      "Optimize addressing mode", false, false)
INITIALIZE_PASS_DEPENDENCY(MachineDominatorTreeWrapperPass)
INITIALIZE_PASS_DEPENDENCY(MachineDominanceFrontier)
INITIALIZE_PASS_END(HexagonOptAddrMode, "amode-opt", "Optimize addressing mode",
                    false, false)

bool HexagonOptAddrMode::hasRepForm(MachineInstr &MI, unsigned TfrDefR) {
  const MCInstrDesc &MID = MI.getDesc();

  if ((!MID.mayStore() && !MID.mayLoad()) || HII->isPredicated(MI))
    return false;

  if (MID.mayStore()) {
    MachineOperand StOp = MI.getOperand(MI.getNumOperands() - 1);
    if (StOp.isReg() && StOp.getReg() == TfrDefR)
      return false;
  }

  if (HII->getAddrMode(MI) == HexagonII::BaseRegOffset)
    // Tranform to Absolute plus register offset.
    return (HII->changeAddrMode_rr_ur(MI) >= 0);
  else if (HII->getAddrMode(MI) == HexagonII::BaseImmOffset)
    // Tranform to absolute addressing mode.
    return (HII->changeAddrMode_io_abs(MI) >= 0);

  return false;
}

// Check if addasl instruction can be removed. This is possible only
// if it's feeding to only load/store instructions with base + register
// offset as these instruction can be tranformed to use 'absolute plus
// shifted register offset'.
// ex:
// Rs = ##foo
// Rx = addasl(Rs, Rt, #2)
// Rd = memw(Rx + #28)
// Above three instructions can be replaced with Rd = memw(Rt<<#2 + ##foo+28)

bool HexagonOptAddrMode::canRemoveAddasl(NodeAddr<StmtNode *> AddAslSN,
                                         MachineInstr &MI,
                                         const NodeList &UNodeList) {
  // check offset size in addasl. if 'offset > 3' return false
  const MachineOperand &OffsetOp = MI.getOperand(3);
  if (!OffsetOp.isImm() || OffsetOp.getImm() > 3)
    return false;

  Register OffsetReg = MI.getOperand(2).getReg();
  RegisterRef OffsetRR;
  NodeId OffsetRegRD = 0;
  for (NodeAddr<UseNode *> UA : AddAslSN.Addr->members_if(DFG->IsUse, *DFG)) {
    RegisterRef RR = UA.Addr->getRegRef(*DFG);
    if (OffsetReg == RR.Reg) {
      OffsetRR = RR;
      OffsetRegRD = UA.Addr->getReachingDef();
    }
  }

  for (auto I = UNodeList.rbegin(), E = UNodeList.rend(); I != E; ++I) {
    NodeAddr<UseNode *> UA = *I;
    NodeAddr<InstrNode *> IA = UA.Addr->getOwner(*DFG);
    if (UA.Addr->getFlags() & NodeAttrs::PhiRef)
      return false;
    NodeAddr<RefNode*> AA = LV->getNearestAliasedRef(OffsetRR, IA);
    if ((DFG->IsDef(AA) && AA.Id != OffsetRegRD) ||
         AA.Addr->getReachingDef() != OffsetRegRD)
      return false;

    MachineInstr &UseMI = *NodeAddr<StmtNode *>(IA).Addr->getCode();
    NodeAddr<DefNode *> OffsetRegDN = DFG->addr<DefNode *>(OffsetRegRD);
    // Reaching Def to an offset register can't be a phi.
    if ((OffsetRegDN.Addr->getFlags() & NodeAttrs::PhiRef) &&
        MI.getParent() != UseMI.getParent())
    return false;

    const MCInstrDesc &UseMID = UseMI.getDesc();
    if ((!UseMID.mayLoad() && !UseMID.mayStore()) ||
        HII->getAddrMode(UseMI) != HexagonII::BaseImmOffset ||
        getBaseWithLongOffset(UseMI) < 0)
      return false;

    // Addasl output can't be a store value.
    if (UseMID.mayStore() && UseMI.getOperand(2).isReg() &&
        UseMI.getOperand(2).getReg() == MI.getOperand(0).getReg())
      return false;

    for (auto &Mo : UseMI.operands())
      if (Mo.isFI())
        return false;
  }
  return true;
}

bool HexagonOptAddrMode::allValidCandidates(NodeAddr<StmtNode *> SA,
                                            NodeList &UNodeList) {
  for (auto I = UNodeList.rbegin(), E = UNodeList.rend(); I != E; ++I) {
    NodeAddr<UseNode *> UN = *I;
    RegisterRef UR = UN.Addr->getRegRef(*DFG);
    NodeSet Visited, Defs;
    const auto &P = LV->getAllReachingDefsRec(UR, UN, Visited, Defs);
    if (!P.second) {
      LLVM_DEBUG({
        dbgs() << "*** Unable to collect all reaching defs for use ***\n"
               << PrintNode<UseNode*>(UN, *DFG) << '\n'
               << "The program's complexity may exceed the limits.\n";
      });
      return false;
    }
    const auto &ReachingDefs = P.first;
    if (ReachingDefs.size() > 1) {
      LLVM_DEBUG({
        dbgs() << "*** Multiple Reaching Defs found!!! ***\n";
        for (auto DI : ReachingDefs) {
          NodeAddr<UseNode *> DA = DFG->addr<UseNode *>(DI);
          NodeAddr<StmtNode *> TempIA = DA.Addr->getOwner(*DFG);
          dbgs() << "\t\t[Reaching Def]: "
                 << Print<NodeAddr<InstrNode *>>(TempIA, *DFG) << "\n";
        }
      });
      return false;
    }
  }
  return true;
}

void HexagonOptAddrMode::getAllRealUses(NodeAddr<StmtNode *> SA,
                                        NodeList &UNodeList) {
  for (NodeAddr<DefNode *> DA : SA.Addr->members_if(DFG->IsDef, *DFG)) {
    LLVM_DEBUG(dbgs() << "\t\t[DefNode]: "
                      << Print<NodeAddr<DefNode *>>(DA, *DFG) << "\n");
    RegisterRef DR = DA.Addr->getRegRef(*DFG);

    auto UseSet = LV->getAllReachedUses(DR, DA);

    for (auto UI : UseSet) {
      NodeAddr<UseNode *> UA = DFG->addr<UseNode *>(UI);
      LLVM_DEBUG({
        NodeAddr<StmtNode *> TempIA = UA.Addr->getOwner(*DFG);
        dbgs() << "\t\t\t[Reached Use]: "
               << Print<NodeAddr<InstrNode *>>(TempIA, *DFG) << "\n";
      });

      if (UA.Addr->getFlags() & NodeAttrs::PhiRef) {
        NodeAddr<PhiNode *> PA = UA.Addr->getOwner(*DFG);
        NodeId id = PA.Id;
        const Liveness::RefMap &phiUse = LV->getRealUses(id);
        LLVM_DEBUG(dbgs() << "\t\t\t\tphi real Uses"
                          << Print<Liveness::RefMap>(phiUse, *DFG) << "\n");
        if (!phiUse.empty()) {
          for (auto I : phiUse) {
            if (!DFG->getPRI().alias(RegisterRef(I.first), DR))
              continue;
            auto phiUseSet = I.second;
            for (auto phiUI : phiUseSet) {
              NodeAddr<UseNode *> phiUA = DFG->addr<UseNode *>(phiUI.first);
              UNodeList.push_back(phiUA);
            }
          }
        }
      } else
        UNodeList.push_back(UA);
    }
  }
}

bool HexagonOptAddrMode::isSafeToExtLR(NodeAddr<StmtNode *> SN,
                                       MachineInstr *MI, unsigned LRExtReg,
                                       const NodeList &UNodeList) {
  RegisterRef LRExtRR;
  NodeId LRExtRegRD = 0;
  // Iterate through all the UseNodes in SN and find the reaching def
  // for the LRExtReg.
  for (NodeAddr<UseNode *> UA : SN.Addr->members_if(DFG->IsUse, *DFG)) {
    RegisterRef RR = UA.Addr->getRegRef(*DFG);
    if (LRExtReg == RR.Reg) {
      LRExtRR = RR;
      LRExtRegRD = UA.Addr->getReachingDef();
    }
  }

  for (auto I = UNodeList.rbegin(), E = UNodeList.rend(); I != E; ++I) {
    NodeAddr<UseNode *> UA = *I;
    NodeAddr<InstrNode *> IA = UA.Addr->getOwner(*DFG);
    // The reaching def of LRExtRR at load/store node should be same as the
    // one reaching at the SN.
    if (UA.Addr->getFlags() & NodeAttrs::PhiRef)
      return false;
    NodeAddr<RefNode*> AA = LV->getNearestAliasedRef(LRExtRR, IA);
    if ((DFG->IsDef(AA) && AA.Id != LRExtRegRD) ||
        AA.Addr->getReachingDef() != LRExtRegRD) {
      LLVM_DEBUG(
          dbgs() << "isSafeToExtLR: Returning false; another reaching def\n");
      return false;
    }

    // If the register is undefined (for example if it's a reserved register),
    // it may still be possible to extend the range, but it's safer to be
    // conservative and just punt.
    if (LRExtRegRD == 0)
      return false;

    MachineInstr *UseMI = NodeAddr<StmtNode *>(IA).Addr->getCode();
    NodeAddr<DefNode *> LRExtRegDN = DFG->addr<DefNode *>(LRExtRegRD);
    // Reaching Def to LRExtReg can't be a phi.
    if ((LRExtRegDN.Addr->getFlags() & NodeAttrs::PhiRef) &&
        MI->getParent() != UseMI->getParent())
      return false;
  }
  return true;
}

bool HexagonOptAddrMode::isValidOffset(MachineInstr *MI, int Offset) {
  if (HII->isHVXVec(*MI)) {
    // only HVX vgather instructions handled
    // TODO: extend the pass to other vector load/store operations
    switch (MI->getOpcode()) {
    case Hexagon::V6_vgathermh_pseudo:
    case Hexagon::V6_vgathermw_pseudo:
    case Hexagon::V6_vgathermhw_pseudo:
    case Hexagon::V6_vgathermhq_pseudo:
    case Hexagon::V6_vgathermwq_pseudo:
    case Hexagon::V6_vgathermhwq_pseudo:
      return HII->isValidOffset(MI->getOpcode(), Offset, HRI, false);
    default:
      return false;
    }
  }

  if (HII->getAddrMode(*MI) != HexagonII::BaseImmOffset)
    return false;

  unsigned AlignMask = 0;
  switch (HII->getMemAccessSize(*MI)) {
  case HexagonII::MemAccessSize::DoubleWordAccess:
    AlignMask = 0x7;
    break;
  case HexagonII::MemAccessSize::WordAccess:
    AlignMask = 0x3;
    break;
  case HexagonII::MemAccessSize::HalfWordAccess:
    AlignMask = 0x1;
    break;
  case HexagonII::MemAccessSize::ByteAccess:
    AlignMask = 0x0;
    break;
  default:
    return false;
  }

  if ((AlignMask & Offset) != 0)
    return false;
  return HII->isValidOffset(MI->getOpcode(), Offset, HRI, false);
}

unsigned HexagonOptAddrMode::getBaseOpPosition(MachineInstr *MI) {
  const MCInstrDesc &MID = MI->getDesc();
  switch (MI->getOpcode()) {
  // vgather pseudos are mayLoad and mayStore
  // hence need to explicitly specify Base and
  // Offset operand positions
  case Hexagon::V6_vgathermh_pseudo:
  case Hexagon::V6_vgathermw_pseudo:
  case Hexagon::V6_vgathermhw_pseudo:
  case Hexagon::V6_vgathermhq_pseudo:
  case Hexagon::V6_vgathermwq_pseudo:
  case Hexagon::V6_vgathermhwq_pseudo:
    return 0;
  default:
    return MID.mayLoad() ? 1 : 0;
  }
}

unsigned HexagonOptAddrMode::getOffsetOpPosition(MachineInstr *MI) {
  assert(
      (HII->getAddrMode(*MI) == HexagonII::BaseImmOffset) &&
      "Looking for an offset in non-BaseImmOffset addressing mode instruction");

  const MCInstrDesc &MID = MI->getDesc();
  switch (MI->getOpcode()) {
  // vgather pseudos are mayLoad and mayStore
  // hence need to explicitly specify Base and
  // Offset operand positions
  case Hexagon::V6_vgathermh_pseudo:
  case Hexagon::V6_vgathermw_pseudo:
  case Hexagon::V6_vgathermhw_pseudo:
  case Hexagon::V6_vgathermhq_pseudo:
  case Hexagon::V6_vgathermwq_pseudo:
  case Hexagon::V6_vgathermhwq_pseudo:
    return 1;
  default:
    return MID.mayLoad() ? 2 : 1;
  }
}

bool HexagonOptAddrMode::processAddUses(NodeAddr<StmtNode *> AddSN,
                                        MachineInstr *AddMI,
                                        const NodeList &UNodeList) {

  Register AddDefR = AddMI->getOperand(0).getReg();
  Register BaseReg = AddMI->getOperand(1).getReg();
  for (auto I = UNodeList.rbegin(), E = UNodeList.rend(); I != E; ++I) {
    NodeAddr<UseNode *> UN = *I;
    NodeAddr<StmtNode *> SN = UN.Addr->getOwner(*DFG);
    MachineInstr *MI = SN.Addr->getCode();
    const MCInstrDesc &MID = MI->getDesc();
    if ((!MID.mayLoad() && !MID.mayStore()) ||
        HII->getAddrMode(*MI) != HexagonII::BaseImmOffset)
      return false;

    MachineOperand BaseOp = MI->getOperand(getBaseOpPosition(MI));

    if (!BaseOp.isReg() || BaseOp.getReg() != AddDefR)
      return false;

    MachineOperand OffsetOp = MI->getOperand(getOffsetOpPosition(MI));
    if (!OffsetOp.isImm())
      return false;

    int64_t newOffset = OffsetOp.getImm() + AddMI->getOperand(2).getImm();
    if (!isValidOffset(MI, newOffset))
      return false;

    // Since we'll be extending the live range of Rt in the following example,
    // make sure that is safe. another definition of Rt doesn't exist between 'add'
    // and load/store instruction.
    //
    // Ex: Rx= add(Rt,#10)
    //     memw(Rx+#0) = Rs
    // will be replaced with =>  memw(Rt+#10) = Rs
    if (!isSafeToExtLR(AddSN, AddMI, BaseReg, UNodeList))
      return false;
  }

  NodeId LRExtRegRD = 0;
  // Iterate through all the UseNodes in SN and find the reaching def
  // for the LRExtReg.
  for (NodeAddr<UseNode *> UA : AddSN.Addr->members_if(DFG->IsUse, *DFG)) {
    RegisterRef RR = UA.Addr->getRegRef(*DFG);
    if (BaseReg == RR.Reg)
      LRExtRegRD = UA.Addr->getReachingDef();
  }

  // Update all the uses of 'add' with the appropriate base and offset
  // values.
  bool Changed = false;
  for (auto I = UNodeList.rbegin(), E = UNodeList.rend(); I != E; ++I) {
    NodeAddr<UseNode *> UseN = *I;
    assert(!(UseN.Addr->getFlags() & NodeAttrs::PhiRef) &&
           "Found a PhiRef node as a real reached use!!");

    NodeAddr<StmtNode *> OwnerN = UseN.Addr->getOwner(*DFG);
    MachineInstr *UseMI = OwnerN.Addr->getCode();
    LLVM_DEBUG(dbgs() << "\t\t[MI <BB#" << UseMI->getParent()->getNumber()
                      << ">]: " << *UseMI << "\n");
    Changed |= updateAddUses(AddMI, UseMI);

    // Set the reachingDef for UseNode under consideration
    // after updating the Add use. This local change is
    // to avoid rebuilding of the RDF graph after update.
    NodeAddr<DefNode *> LRExtRegDN = DFG->addr<DefNode *>(LRExtRegRD);
    UseN.Addr->linkToDef(UseN.Id, LRExtRegDN);
  }

  if (Changed)
    Deleted.insert(AddMI);

  return Changed;
}

bool HexagonOptAddrMode::updateAddUses(MachineInstr *AddMI,
                                       MachineInstr *UseMI) {
  const MachineOperand ImmOp = AddMI->getOperand(2);
  const MachineOperand AddRegOp = AddMI->getOperand(1);
  Register NewReg = AddRegOp.getReg();

  MachineOperand &BaseOp = UseMI->getOperand(getBaseOpPosition(UseMI));
  MachineOperand &OffsetOp = UseMI->getOperand(getOffsetOpPosition(UseMI));
  BaseOp.setReg(NewReg);
  BaseOp.setIsUndef(AddRegOp.isUndef());
  BaseOp.setImplicit(AddRegOp.isImplicit());
  OffsetOp.setImm(ImmOp.getImm() + OffsetOp.getImm());
  MRI->clearKillFlags(NewReg);

  return true;
}

bool HexagonOptAddrMode::analyzeUses(unsigned tfrDefR,
                                     const NodeList &UNodeList,
                                     InstrEvalMap &InstrEvalResult,
                                     short &SizeInc) {
  bool KeepTfr = false;
  bool HasRepInstr = false;
  InstrEvalResult.clear();

  for (auto I = UNodeList.rbegin(), E = UNodeList.rend(); I != E; ++I) {
    bool CanBeReplaced = false;
    NodeAddr<UseNode *> UN = *I;
    NodeAddr<StmtNode *> SN = UN.Addr->getOwner(*DFG);
    MachineInstr &MI = *SN.Addr->getCode();
    const MCInstrDesc &MID = MI.getDesc();
    if ((MID.mayLoad() || MID.mayStore())) {
      if (!hasRepForm(MI, tfrDefR)) {
        KeepTfr = true;
        continue;
      }
      SizeInc++;
      CanBeReplaced = true;
    } else if (MI.getOpcode() == Hexagon::S2_addasl_rrri) {
      NodeList AddaslUseList;

      LLVM_DEBUG(dbgs() << "\nGetting ReachedUses for === " << MI << "\n");
      getAllRealUses(SN, AddaslUseList);
      // Process phi nodes.
      if (allValidCandidates(SN, AddaslUseList) &&
          canRemoveAddasl(SN, MI, AddaslUseList)) {
        SizeInc += AddaslUseList.size();
        SizeInc -= 1; // Reduce size by 1 as addasl itself can be removed.
        CanBeReplaced = true;
      } else
        SizeInc++;
    } else
      // Currently, only load/store and addasl are handled.
      // Some other instructions to consider -
      // A2_add -> A2_addi
      // M4_mpyrr_addr -> M4_mpyrr_addi
      KeepTfr = true;

    InstrEvalResult[&MI] = CanBeReplaced;
    HasRepInstr |= CanBeReplaced;
  }

  // Reduce total size by 2 if original tfr can be deleted.
  if (!KeepTfr)
    SizeInc -= 2;

  return HasRepInstr;
}

bool HexagonOptAddrMode::changeLoad(MachineInstr *OldMI, MachineOperand ImmOp,
                                    unsigned ImmOpNum) {
  bool Changed = false;
  MachineBasicBlock *BB = OldMI->getParent();
  auto UsePos = MachineBasicBlock::iterator(OldMI);
  MachineBasicBlock::instr_iterator InsertPt = UsePos.getInstrIterator();
  ++InsertPt;
  unsigned OpStart;
  unsigned OpEnd = OldMI->getNumOperands();
  MachineInstrBuilder MIB;

  if (ImmOpNum == 1) {
    if (HII->getAddrMode(*OldMI) == HexagonII::BaseRegOffset) {
      short NewOpCode = HII->changeAddrMode_rr_ur(*OldMI);
      assert(NewOpCode >= 0 && "Invalid New opcode\n");
      MIB = BuildMI(*BB, InsertPt, OldMI->getDebugLoc(), HII->get(NewOpCode));
      MIB.add(OldMI->getOperand(0));
      MIB.add(OldMI->getOperand(2));
      MIB.add(OldMI->getOperand(3));
      MIB.add(ImmOp);
      OpStart = 4;
      Changed = true;
    } else if (HII->getAddrMode(*OldMI) == HexagonII::BaseImmOffset &&
               OldMI->getOperand(2).isImm()) {
      short NewOpCode = HII->changeAddrMode_io_abs(*OldMI);
      assert(NewOpCode >= 0 && "Invalid New opcode\n");
      MIB = BuildMI(*BB, InsertPt, OldMI->getDebugLoc(), HII->get(NewOpCode))
                .add(OldMI->getOperand(0));
      const GlobalValue *GV = ImmOp.getGlobal();
      int64_t Offset = ImmOp.getOffset() + OldMI->getOperand(2).getImm();

      MIB.addGlobalAddress(GV, Offset, ImmOp.getTargetFlags());
      OpStart = 3;
      Changed = true;
    } else
      Changed = false;

    LLVM_DEBUG(dbgs() << "[Changing]: " << *OldMI << "\n");
    LLVM_DEBUG(dbgs() << "[TO]: " << *MIB << "\n");
  } else if (ImmOpNum == 2) {
    if (OldMI->getOperand(3).isImm() && OldMI->getOperand(3).getImm() == 0) {
      short NewOpCode = HII->changeAddrMode_rr_io(*OldMI);
      assert(NewOpCode >= 0 && "Invalid New opcode\n");
      MIB = BuildMI(*BB, InsertPt, OldMI->getDebugLoc(), HII->get(NewOpCode));
      MIB.add(OldMI->getOperand(0));
      MIB.add(OldMI->getOperand(1));
      MIB.add(ImmOp);
      OpStart = 4;
      Changed = true;
      LLVM_DEBUG(dbgs() << "[Changing]: " << *OldMI << "\n");
      LLVM_DEBUG(dbgs() << "[TO]: " << *MIB << "\n");
    }
  }

  if (Changed)
    for (unsigned i = OpStart; i < OpEnd; ++i)
      MIB.add(OldMI->getOperand(i));

  return Changed;
}

bool HexagonOptAddrMode::changeStore(MachineInstr *OldMI, MachineOperand ImmOp,
                                     unsigned ImmOpNum) {
  bool Changed = false;
  unsigned OpStart = 0;
  unsigned OpEnd = OldMI->getNumOperands();
  MachineBasicBlock *BB = OldMI->getParent();
  auto UsePos = MachineBasicBlock::iterator(OldMI);
  MachineBasicBlock::instr_iterator InsertPt = UsePos.getInstrIterator();
  ++InsertPt;
  MachineInstrBuilder MIB;
  if (ImmOpNum == 0) {
    if (HII->getAddrMode(*OldMI) == HexagonII::BaseRegOffset) {
      short NewOpCode = HII->changeAddrMode_rr_ur(*OldMI);
      assert(NewOpCode >= 0 && "Invalid New opcode\n");
      MIB = BuildMI(*BB, InsertPt, OldMI->getDebugLoc(), HII->get(NewOpCode));
      MIB.add(OldMI->getOperand(1));
      MIB.add(OldMI->getOperand(2));
      MIB.add(ImmOp);
      MIB.add(OldMI->getOperand(3));
      OpStart = 4;
      Changed = true;
    } else if (HII->getAddrMode(*OldMI) == HexagonII::BaseImmOffset) {
      short NewOpCode = HII->changeAddrMode_io_abs(*OldMI);
      assert(NewOpCode >= 0 && "Invalid New opcode\n");
      MIB = BuildMI(*BB, InsertPt, OldMI->getDebugLoc(), HII->get(NewOpCode));
      const GlobalValue *GV = ImmOp.getGlobal();
      int64_t Offset = ImmOp.getOffset() + OldMI->getOperand(1).getImm();
      MIB.addGlobalAddress(GV, Offset, ImmOp.getTargetFlags());
      MIB.add(OldMI->getOperand(2));
      OpStart = 3;
      Changed = true;
    }
  } else if (ImmOpNum == 1 && OldMI->getOperand(2).getImm() == 0) {
    short NewOpCode = HII->changeAddrMode_rr_io(*OldMI);
    assert(NewOpCode >= 0 && "Invalid New opcode\n");
    MIB = BuildMI(*BB, InsertPt, OldMI->getDebugLoc(), HII->get(NewOpCode));
    MIB.add(OldMI->getOperand(0));
    MIB.add(ImmOp);
    OpStart = 3;
    Changed = true;
  }
  if (Changed) {
    LLVM_DEBUG(dbgs() << "[Changing]: " << *OldMI << "\n");
    LLVM_DEBUG(dbgs() << "[TO]: " << *MIB << "\n");

    for (unsigned i = OpStart; i < OpEnd; ++i)
      MIB.add(OldMI->getOperand(i));
  }

  return Changed;
}

short HexagonOptAddrMode::getBaseWithLongOffset(const MachineInstr &MI) const {
  if (HII->getAddrMode(MI) == HexagonII::BaseImmOffset) {
    short TempOpCode = HII->changeAddrMode_io_rr(MI);
    return HII->changeAddrMode_rr_ur(TempOpCode);
  }
  return HII->changeAddrMode_rr_ur(MI);
}

bool HexagonOptAddrMode::changeAddAsl(NodeAddr<UseNode *> AddAslUN,
                                      MachineInstr *AddAslMI,
                                      const MachineOperand &ImmOp,
                                      unsigned ImmOpNum) {
  NodeAddr<StmtNode *> SA = AddAslUN.Addr->getOwner(*DFG);

  LLVM_DEBUG(dbgs() << "Processing addasl :" << *AddAslMI << "\n");

  NodeList UNodeList;
  getAllRealUses(SA, UNodeList);

  for (auto I = UNodeList.rbegin(), E = UNodeList.rend(); I != E; ++I) {
    NodeAddr<UseNode *> UseUN = *I;
    assert(!(UseUN.Addr->getFlags() & NodeAttrs::PhiRef) &&
           "Can't transform this 'AddAsl' instruction!");

    NodeAddr<StmtNode *> UseIA = UseUN.Addr->getOwner(*DFG);
    LLVM_DEBUG(dbgs() << "[InstrNode]: "
                      << Print<NodeAddr<InstrNode *>>(UseIA, *DFG) << "\n");
    MachineInstr *UseMI = UseIA.Addr->getCode();
    LLVM_DEBUG(dbgs() << "[MI <" << printMBBReference(*UseMI->getParent())
                      << ">]: " << *UseMI << "\n");
    const MCInstrDesc &UseMID = UseMI->getDesc();
    assert(HII->getAddrMode(*UseMI) == HexagonII::BaseImmOffset);

    auto UsePos = MachineBasicBlock::iterator(UseMI);
    MachineBasicBlock::instr_iterator InsertPt = UsePos.getInstrIterator();
    short NewOpCode = getBaseWithLongOffset(*UseMI);
    assert(NewOpCode >= 0 && "Invalid New opcode\n");

    unsigned OpStart;
    unsigned OpEnd = UseMI->getNumOperands();

    MachineBasicBlock *BB = UseMI->getParent();
    MachineInstrBuilder MIB =
        BuildMI(*BB, InsertPt, UseMI->getDebugLoc(), HII->get(NewOpCode));
    // change mem(Rs + # ) -> mem(Rt << # + ##)
    if (UseMID.mayLoad()) {
      MIB.add(UseMI->getOperand(0));
      MIB.add(AddAslMI->getOperand(2));
      MIB.add(AddAslMI->getOperand(3));
      const GlobalValue *GV = ImmOp.getGlobal();
      MIB.addGlobalAddress(GV, UseMI->getOperand(2).getImm()+ImmOp.getOffset(),
                           ImmOp.getTargetFlags());
      OpStart = 3;
    } else if (UseMID.mayStore()) {
      MIB.add(AddAslMI->getOperand(2));
      MIB.add(AddAslMI->getOperand(3));
      const GlobalValue *GV = ImmOp.getGlobal();
      MIB.addGlobalAddress(GV, UseMI->getOperand(1).getImm()+ImmOp.getOffset(),
                           ImmOp.getTargetFlags());
      MIB.add(UseMI->getOperand(2));
      OpStart = 3;
    } else
      llvm_unreachable("Unhandled instruction");

    for (unsigned i = OpStart; i < OpEnd; ++i)
      MIB.add(UseMI->getOperand(i));

    Deleted.insert(UseMI);
  }

  return true;
}

bool HexagonOptAddrMode::xformUseMI(MachineInstr *TfrMI, MachineInstr *UseMI,
                                    NodeAddr<UseNode *> UseN,
                                    unsigned UseMOnum) {
  const MachineOperand ImmOp = TfrMI->getOperand(1);
  const MCInstrDesc &MID = UseMI->getDesc();
  unsigned Changed = false;
  if (MID.mayLoad())
    Changed = changeLoad(UseMI, ImmOp, UseMOnum);
  else if (MID.mayStore())
    Changed = changeStore(UseMI, ImmOp, UseMOnum);
  else if (UseMI->getOpcode() == Hexagon::S2_addasl_rrri)
    Changed = changeAddAsl(UseN, UseMI, ImmOp, UseMOnum);

  if (Changed)
    Deleted.insert(UseMI);

  return Changed;
}

bool HexagonOptAddrMode::processBlock(NodeAddr<BlockNode *> BA) {
  bool Changed = false;

  for (auto IA : BA.Addr->members(*DFG)) {
    if (!DFG->IsCode<NodeAttrs::Stmt>(IA))
      continue;

    NodeAddr<StmtNode *> SA = IA;
    MachineInstr *MI = SA.Addr->getCode();
    if ((MI->getOpcode() != Hexagon::A2_tfrsi ||
         !MI->getOperand(1).isGlobal()) &&
        (MI->getOpcode() != Hexagon::A2_addi ||
         !MI->getOperand(2).isImm() || HII->isConstExtended(*MI)))
    continue;

    LLVM_DEBUG(dbgs() << "[Analyzing " << HII->getName(MI->getOpcode())
                      << "]: " << *MI << "\n\t[InstrNode]: "
                      << Print<NodeAddr<InstrNode *>>(IA, *DFG) << '\n');

    NodeList UNodeList;
    getAllRealUses(SA, UNodeList);

    if (!allValidCandidates(SA, UNodeList))
      continue;

    // Analyze all uses of 'add'. If the output of 'add' is used as an address
    // in the base+immediate addressing mode load/store instructions, see if
    // they can be updated to use the immediate value as an offet. Thus,
    // providing us the opportunity to eliminate 'add'.
    // Ex: Rx= add(Rt,#12)
    //     memw(Rx+#0) = Rs
    // This can be replaced with memw(Rt+#12) = Rs
    //
    // This transformation is only performed if all uses can be updated and
    // the offset isn't required to be constant extended.
    if (MI->getOpcode() == Hexagon::A2_addi) {
      Changed |= processAddUses(SA, MI, UNodeList);
      continue;
    }

    short SizeInc = 0;
    Register DefR = MI->getOperand(0).getReg();
    InstrEvalMap InstrEvalResult;

    // Analyze all uses and calculate increase in size. Perform the optimization
    // only if there is no increase in size.
    if (!analyzeUses(DefR, UNodeList, InstrEvalResult, SizeInc))
      continue;
    if (SizeInc > CodeGrowthLimit)
      continue;

    bool KeepTfr = false;

    LLVM_DEBUG(dbgs() << "\t[Total reached uses] : " << UNodeList.size()
                      << "\n");
    LLVM_DEBUG(dbgs() << "\t[Processing Reached Uses] ===\n");
    for (auto I = UNodeList.rbegin(), E = UNodeList.rend(); I != E; ++I) {
      NodeAddr<UseNode *> UseN = *I;
      assert(!(UseN.Addr->getFlags() & NodeAttrs::PhiRef) &&
             "Found a PhiRef node as a real reached use!!");

      NodeAddr<StmtNode *> OwnerN = UseN.Addr->getOwner(*DFG);
      MachineInstr *UseMI = OwnerN.Addr->getCode();
      LLVM_DEBUG(dbgs() << "\t\t[MI <" << printMBBReference(*UseMI->getParent())
                        << ">]: " << *UseMI << "\n");

      int UseMOnum = -1;
      unsigned NumOperands = UseMI->getNumOperands();
      for (unsigned j = 0; j < NumOperands - 1; ++j) {
        const MachineOperand &op = UseMI->getOperand(j);
        if (op.isReg() && op.isUse() && DefR == op.getReg())
          UseMOnum = j;
      }
      // It is possible that the register will not be found in any operand.
      // This could happen, for example, when DefR = R4, but the used
      // register is D2.

      // Change UseMI if replacement is possible. If any replacement failed,
      // or wasn't attempted, make sure to keep the TFR.
      bool Xformed = false;
      if (UseMOnum >= 0 && InstrEvalResult[UseMI])
        Xformed = xformUseMI(MI, UseMI, UseN, UseMOnum);
      Changed |=  Xformed;
      KeepTfr |= !Xformed;
    }
    if (!KeepTfr)
      Deleted.insert(MI);
  }
  return Changed;
}

bool HexagonOptAddrMode::runOnMachineFunction(MachineFunction &MF) {
  if (skipFunction(MF.getFunction()))
    return false;

  // Perform RDF optimizations only if number of basic blocks in the
  // function is less than the limit
  if (MF.size() > RDFFuncBlockLimit) {
    LLVM_DEBUG(dbgs() << "Skipping " << getPassName()
                      << ": too many basic blocks\n");
    return false;
  }

  bool Changed = false;
  auto &HST = MF.getSubtarget<HexagonSubtarget>();
  MRI = &MF.getRegInfo();
  HII = HST.getInstrInfo();
  HRI = HST.getRegisterInfo();
  const auto &MDF = getAnalysis<MachineDominanceFrontier>();
  MDT = &getAnalysis<MachineDominatorTreeWrapperPass>().getDomTree();

  DataFlowGraph G(MF, *HII, *HRI, *MDT, MDF);
  // Need to keep dead phis because we can propagate uses of registers into
  // nodes dominated by those would-be phis.
  G.build(BuildOptions::KeepDeadPhis);
  DFG = &G;

  Liveness L(*MRI, *DFG);
  L.computePhiInfo();
  LV = &L;

  Deleted.clear();
  NodeAddr<FuncNode *> FA = DFG->getFunc();
  LLVM_DEBUG(dbgs() << "==== [RefMap#]=====:\n "
                    << Print<NodeAddr<FuncNode *>>(FA, *DFG) << "\n");

  for (NodeAddr<BlockNode *> BA : FA.Addr->members(*DFG))
    Changed |= processBlock(BA);

  for (auto *MI : Deleted)
    MI->eraseFromParent();

  if (Changed) {
    G.build();
    L.computeLiveIns();
    L.resetLiveIns();
    L.resetKills();
  }

  return Changed;
}

//===----------------------------------------------------------------------===//
//                         Public Constructor Functions
//===----------------------------------------------------------------------===//

FunctionPass *llvm::createHexagonOptAddrMode() {
  return new HexagonOptAddrMode();
}