brintos / llvm-project-archived public Read only

Text · 85.2 KiB · eadf020 Raw
2474 lines · cpp
1//===-- HexagonISelDAGToDAG.cpp - A dag to dag inst selector for Hexagon --===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8//9// This file defines an instruction selector for the Hexagon target.10//11//===----------------------------------------------------------------------===//12 13#include "HexagonISelDAGToDAG.h"14#include "Hexagon.h"15#include "HexagonISelLowering.h"16#include "HexagonMachineFunctionInfo.h"17#include "HexagonTargetMachine.h"18#include "llvm/CodeGen/FunctionLoweringInfo.h"19#include "llvm/CodeGen/MachineInstrBuilder.h"20#include "llvm/CodeGen/SelectionDAGISel.h"21#include "llvm/IR/Intrinsics.h"22#include "llvm/IR/IntrinsicsHexagon.h"23#include "llvm/Support/CommandLine.h"24#include "llvm/Support/Debug.h"25using namespace llvm;26 27#define DEBUG_TYPE "hexagon-isel"28#define PASS_NAME "Hexagon DAG->DAG Pattern Instruction Selection"29 30static31cl::opt<bool>32EnableAddressRebalancing("isel-rebalance-addr", cl::Hidden, cl::init(true),33  cl::desc("Rebalance address calculation trees to improve "34          "instruction selection"));35 36// Rebalance only if this allows e.g. combining a GA with an offset or37// factoring out a shift.38static39cl::opt<bool>40RebalanceOnlyForOptimizations("rebalance-only-opt", cl::Hidden, cl::init(false),41  cl::desc("Rebalance address tree only if this allows optimizations"));42 43static44cl::opt<bool>45RebalanceOnlyImbalancedTrees("rebalance-only-imbal", cl::Hidden,46  cl::init(false), cl::desc("Rebalance address tree only if it is imbalanced"));47 48static cl::opt<bool> CheckSingleUse("hexagon-isel-su", cl::Hidden,49  cl::init(true), cl::desc("Enable checking of SDNode's single-use status"));50 51//===----------------------------------------------------------------------===//52// Instruction Selector Implementation53//===----------------------------------------------------------------------===//54 55#define GET_DAGISEL_BODY HexagonDAGToDAGISel56#include "HexagonGenDAGISel.inc"57 58namespace llvm {59/// createHexagonISelDag - This pass converts a legalized DAG into a60/// Hexagon-specific DAG, ready for instruction scheduling.61FunctionPass *createHexagonISelDag(HexagonTargetMachine &TM,62                                   CodeGenOptLevel OptLevel) {63  return new HexagonDAGToDAGISelLegacy(TM, OptLevel);64}65}66 67HexagonDAGToDAGISelLegacy::HexagonDAGToDAGISelLegacy(HexagonTargetMachine &tm,68                                                     CodeGenOptLevel OptLevel)69    : SelectionDAGISelLegacy(70          ID, std::make_unique<HexagonDAGToDAGISel>(tm, OptLevel)) {}71 72char HexagonDAGToDAGISelLegacy::ID = 0;73 74INITIALIZE_PASS(HexagonDAGToDAGISelLegacy, DEBUG_TYPE, PASS_NAME, false, false)75 76void HexagonDAGToDAGISel::SelectIndexedLoad(LoadSDNode *LD, const SDLoc &dl) {77  SDValue Chain = LD->getChain();78  SDValue Base = LD->getBasePtr();79  SDValue Offset = LD->getOffset();80  int32_t Inc = cast<ConstantSDNode>(Offset.getNode())->getSExtValue();81  EVT LoadedVT = LD->getMemoryVT();82  unsigned Opcode = 0;83 84  // Check for zero extended loads. Treat any-extend loads as zero extended85  // loads.86  ISD::LoadExtType ExtType = LD->getExtensionType();87  bool IsZeroExt = (ExtType == ISD::ZEXTLOAD || ExtType == ISD::EXTLOAD);88  bool IsValidInc = HII->isValidAutoIncImm(LoadedVT, Inc);89 90  assert(LoadedVT.isSimple());91  switch (LoadedVT.getSimpleVT().SimpleTy) {92  case MVT::i8:93    if (IsZeroExt)94      Opcode = IsValidInc ? Hexagon::L2_loadrub_pi : Hexagon::L2_loadrub_io;95    else96      Opcode = IsValidInc ? Hexagon::L2_loadrb_pi : Hexagon::L2_loadrb_io;97    break;98  case MVT::i16:99    if (IsZeroExt)100      Opcode = IsValidInc ? Hexagon::L2_loadruh_pi : Hexagon::L2_loadruh_io;101    else102      Opcode = IsValidInc ? Hexagon::L2_loadrh_pi : Hexagon::L2_loadrh_io;103    break;104  case MVT::i32:105  case MVT::f32:106  case MVT::v2i16:107  case MVT::v4i8:108    Opcode = IsValidInc ? Hexagon::L2_loadri_pi : Hexagon::L2_loadri_io;109    break;110  case MVT::i64:111  case MVT::f64:112  case MVT::v2i32:113  case MVT::v4i16:114  case MVT::v8i8:115    Opcode = IsValidInc ? Hexagon::L2_loadrd_pi : Hexagon::L2_loadrd_io;116    break;117  case MVT::v64i8:118  case MVT::v32i16:119  case MVT::v16i32:120  case MVT::v8i64:121  case MVT::v128i8:122  case MVT::v64i16:123  case MVT::v32i32:124  case MVT::v16i64:125    if (isAlignedMemNode(LD)) {126      if (LD->isNonTemporal())127        Opcode = IsValidInc ? Hexagon::V6_vL32b_nt_pi : Hexagon::V6_vL32b_nt_ai;128      else129        Opcode = IsValidInc ? Hexagon::V6_vL32b_pi : Hexagon::V6_vL32b_ai;130    } else {131      Opcode = IsValidInc ? Hexagon::V6_vL32Ub_pi : Hexagon::V6_vL32Ub_ai;132    }133    break;134  default:135    llvm_unreachable("Unexpected memory type in indexed load");136  }137 138  SDValue IncV = CurDAG->getSignedTargetConstant(Inc, dl, MVT::i32);139  MachineMemOperand *MemOp = LD->getMemOperand();140 141  auto getExt64 = [this,ExtType] (MachineSDNode *N, const SDLoc &dl)142        -> MachineSDNode* {143    if (ExtType == ISD::ZEXTLOAD || ExtType == ISD::EXTLOAD) {144      SDValue Zero = CurDAG->getTargetConstant(0, dl, MVT::i32);145      return CurDAG->getMachineNode(Hexagon::A4_combineir, dl, MVT::i64,146                                    Zero, SDValue(N, 0));147    }148    if (ExtType == ISD::SEXTLOAD)149      return CurDAG->getMachineNode(Hexagon::A2_sxtw, dl, MVT::i64,150                                    SDValue(N, 0));151    return N;152  };153 154  //                  Loaded value   Next address   Chain155  SDValue From[3] = { SDValue(LD,0), SDValue(LD,1), SDValue(LD,2) };156  SDValue To[3];157 158  EVT ValueVT = LD->getValueType(0);159  if (ValueVT == MVT::i64 && ExtType != ISD::NON_EXTLOAD) {160    // A load extending to i64 will actually produce i32, which will then161    // need to be extended to i64.162    assert(LoadedVT.getSizeInBits() <= 32);163    ValueVT = MVT::i32;164  }165 166  if (IsValidInc) {167    MachineSDNode *L = CurDAG->getMachineNode(Opcode, dl, ValueVT,168                                              MVT::i32, MVT::Other, Base,169                                              IncV, Chain);170    CurDAG->setNodeMemRefs(L, {MemOp});171    To[1] = SDValue(L, 1); // Next address.172    To[2] = SDValue(L, 2); // Chain.173    // Handle special case for extension to i64.174    if (LD->getValueType(0) == MVT::i64)175      L = getExt64(L, dl);176    To[0] = SDValue(L, 0); // Loaded (extended) value.177  } else {178    SDValue Zero = CurDAG->getTargetConstant(0, dl, MVT::i32);179    MachineSDNode *L = CurDAG->getMachineNode(Opcode, dl, ValueVT, MVT::Other,180                                              Base, Zero, Chain);181    CurDAG->setNodeMemRefs(L, {MemOp});182    To[2] = SDValue(L, 1); // Chain.183    MachineSDNode *A = CurDAG->getMachineNode(Hexagon::A2_addi, dl, MVT::i32,184                                              Base, IncV);185    To[1] = SDValue(A, 0); // Next address.186    // Handle special case for extension to i64.187    if (LD->getValueType(0) == MVT::i64)188      L = getExt64(L, dl);189    To[0] = SDValue(L, 0); // Loaded (extended) value.190  }191  ReplaceUses(From, To, 3);192  CurDAG->RemoveDeadNode(LD);193}194 195MachineSDNode *HexagonDAGToDAGISel::LoadInstrForLoadIntrinsic(SDNode *IntN) {196  if (IntN->getOpcode() != ISD::INTRINSIC_W_CHAIN)197    return nullptr;198 199  SDLoc dl(IntN);200  unsigned IntNo = IntN->getConstantOperandVal(1);201 202  static std::map<unsigned,unsigned> LoadPciMap = {203    { Intrinsic::hexagon_circ_ldb,  Hexagon::L2_loadrb_pci  },204    { Intrinsic::hexagon_circ_ldub, Hexagon::L2_loadrub_pci },205    { Intrinsic::hexagon_circ_ldh,  Hexagon::L2_loadrh_pci  },206    { Intrinsic::hexagon_circ_lduh, Hexagon::L2_loadruh_pci },207    { Intrinsic::hexagon_circ_ldw,  Hexagon::L2_loadri_pci  },208    { Intrinsic::hexagon_circ_ldd,  Hexagon::L2_loadrd_pci  },209  };210  auto FLC = LoadPciMap.find(IntNo);211  if (FLC != LoadPciMap.end()) {212    EVT ValTy = (IntNo == Intrinsic::hexagon_circ_ldd) ? MVT::i64 : MVT::i32;213    EVT RTys[] = { ValTy, MVT::i32, MVT::Other };214    // Operands: { Base, Increment, Modifier, Chain }215    auto Inc = cast<ConstantSDNode>(IntN->getOperand(5));216    SDValue I =217        CurDAG->getSignedTargetConstant(Inc->getSExtValue(), dl, MVT::i32);218    MachineSDNode *Res = CurDAG->getMachineNode(FLC->second, dl, RTys,219          { IntN->getOperand(2), I, IntN->getOperand(4),220            IntN->getOperand(0) });221    return Res;222  }223 224  return nullptr;225}226 227SDNode *HexagonDAGToDAGISel::StoreInstrForLoadIntrinsic(MachineSDNode *LoadN,228      SDNode *IntN) {229  // The "LoadN" is just a machine load instruction. The intrinsic also230  // involves storing it. Generate an appropriate store to the location231  // given in the intrinsic's operand(3).232  uint64_t F = HII->get(LoadN->getMachineOpcode()).TSFlags;233  unsigned SizeBits = (F >> HexagonII::MemAccessSizePos) &234                      HexagonII::MemAccesSizeMask;235  unsigned Size = 1U << (SizeBits-1);236 237  SDLoc dl(IntN);238  MachinePointerInfo PI;239  SDValue TS;240  SDValue Loc = IntN->getOperand(3);241 242  if (Size >= 4)243    TS = CurDAG->getStore(SDValue(LoadN, 2), dl, SDValue(LoadN, 0), Loc, PI,244                          Align(Size));245  else246    TS = CurDAG->getTruncStore(SDValue(LoadN, 2), dl, SDValue(LoadN, 0), Loc,247                               PI, MVT::getIntegerVT(Size * 8), Align(Size));248 249  SDNode *StoreN;250  {251    HandleSDNode Handle(TS);252    SelectStore(TS.getNode());253    StoreN = Handle.getValue().getNode();254  }255 256  // Load's results are { Loaded value, Updated pointer, Chain }257  ReplaceUses(SDValue(IntN, 0), SDValue(LoadN, 1));258  ReplaceUses(SDValue(IntN, 1), SDValue(StoreN, 0));259  return StoreN;260}261 262bool HexagonDAGToDAGISel::tryLoadOfLoadIntrinsic(LoadSDNode *N) {263  // The intrinsics for load circ/brev perform two operations:264  // 1. Load a value V from the specified location, using the addressing265  //    mode corresponding to the intrinsic.266  // 2. Store V into a specified location. This location is typically a267  //    local, temporary object.268  // In many cases, the program using these intrinsics will immediately269  // load V again from the local object. In those cases, when certain270  // conditions are met, the last load can be removed.271  // This function identifies and optimizes this pattern. If the pattern272  // cannot be optimized, it returns nullptr, which will cause the load273  // to be selected separately from the intrinsic (which will be handled274  // in SelectIntrinsicWChain).275 276  SDValue Ch = N->getOperand(0);277  SDValue Loc = N->getOperand(1);278 279  // Assume that the load and the intrinsic are connected directly with a280  // chain:281  //   t1: i32,ch = int.load ..., ..., ..., Loc, ...    // <-- C282  //   t2: i32,ch = load t1:1, Loc, ...283  SDNode *C = Ch.getNode();284 285  if (C->getOpcode() != ISD::INTRINSIC_W_CHAIN)286    return false;287 288  // The second load can only be eliminated if its extension type matches289  // that of the load instruction corresponding to the intrinsic. The user290  // can provide an address of an unsigned variable to store the result of291  // a sign-extending intrinsic into (or the other way around).292  ISD::LoadExtType IntExt;293  switch (C->getConstantOperandVal(1)) {294  case Intrinsic::hexagon_circ_ldub:295  case Intrinsic::hexagon_circ_lduh:296    IntExt = ISD::ZEXTLOAD;297    break;298  case Intrinsic::hexagon_circ_ldw:299  case Intrinsic::hexagon_circ_ldd:300    IntExt = ISD::NON_EXTLOAD;301    break;302  default:303    IntExt = ISD::SEXTLOAD;304    break;305  }306  if (N->getExtensionType() != IntExt)307    return false;308 309  // Make sure the target location for the loaded value in the load intrinsic310  // is the location from which LD (or N) is loading.311  if (C->getNumOperands() < 4 || Loc.getNode() != C->getOperand(3).getNode())312    return false;313 314  if (MachineSDNode *L = LoadInstrForLoadIntrinsic(C)) {315    SDNode *S = StoreInstrForLoadIntrinsic(L, C);316    SDValue F[] = { SDValue(N,0), SDValue(N,1), SDValue(C,0), SDValue(C,1) };317    SDValue T[] = { SDValue(L,0), SDValue(S,0), SDValue(L,1), SDValue(S,0) };318    ReplaceUses(F, T, std::size(T));319    // This transformation will leave the intrinsic dead. If it remains in320    // the DAG, the selection code will see it again, but without the load,321    // and it will generate a store that is normally required for it.322    CurDAG->RemoveDeadNode(C);323    return true;324  }325  return false;326}327 328// Convert the bit-reverse load intrinsic to appropriate target instruction.329bool HexagonDAGToDAGISel::SelectBrevLdIntrinsic(SDNode *IntN) {330  if (IntN->getOpcode() != ISD::INTRINSIC_W_CHAIN)331    return false;332 333  const SDLoc &dl(IntN);334  unsigned IntNo = IntN->getConstantOperandVal(1);335 336  static const std::map<unsigned, unsigned> LoadBrevMap = {337    { Intrinsic::hexagon_L2_loadrb_pbr, Hexagon::L2_loadrb_pbr },338    { Intrinsic::hexagon_L2_loadrub_pbr, Hexagon::L2_loadrub_pbr },339    { Intrinsic::hexagon_L2_loadrh_pbr, Hexagon::L2_loadrh_pbr },340    { Intrinsic::hexagon_L2_loadruh_pbr, Hexagon::L2_loadruh_pbr },341    { Intrinsic::hexagon_L2_loadri_pbr, Hexagon::L2_loadri_pbr },342    { Intrinsic::hexagon_L2_loadrd_pbr, Hexagon::L2_loadrd_pbr }343  };344  auto FLI = LoadBrevMap.find(IntNo);345  if (FLI != LoadBrevMap.end()) {346    EVT ValTy =347        (IntNo == Intrinsic::hexagon_L2_loadrd_pbr) ? MVT::i64 : MVT::i32;348    EVT RTys[] = { ValTy, MVT::i32, MVT::Other };349    // Operands of Intrinsic: {chain, enum ID of intrinsic, baseptr,350    // modifier}.351    // Operands of target instruction: { Base, Modifier, Chain }.352    MachineSDNode *Res = CurDAG->getMachineNode(353        FLI->second, dl, RTys,354        {IntN->getOperand(2), IntN->getOperand(3), IntN->getOperand(0)});355 356    MachineMemOperand *MemOp = cast<MemIntrinsicSDNode>(IntN)->getMemOperand();357    CurDAG->setNodeMemRefs(Res, {MemOp});358 359    ReplaceUses(SDValue(IntN, 0), SDValue(Res, 0));360    ReplaceUses(SDValue(IntN, 1), SDValue(Res, 1));361    ReplaceUses(SDValue(IntN, 2), SDValue(Res, 2));362    CurDAG->RemoveDeadNode(IntN);363    return true;364  }365  return false;366}367 368/// Generate a machine instruction node for the new circular buffer intrinsics.369/// The new versions use a CSx register instead of the K field.370bool HexagonDAGToDAGISel::SelectNewCircIntrinsic(SDNode *IntN) {371  if (IntN->getOpcode() != ISD::INTRINSIC_W_CHAIN)372    return false;373 374  SDLoc DL(IntN);375  unsigned IntNo = IntN->getConstantOperandVal(1);376  SmallVector<SDValue, 7> Ops;377 378  static std::map<unsigned,unsigned> LoadNPcMap = {379    { Intrinsic::hexagon_L2_loadrub_pci, Hexagon::PS_loadrub_pci },380    { Intrinsic::hexagon_L2_loadrb_pci, Hexagon::PS_loadrb_pci },381    { Intrinsic::hexagon_L2_loadruh_pci, Hexagon::PS_loadruh_pci },382    { Intrinsic::hexagon_L2_loadrh_pci, Hexagon::PS_loadrh_pci },383    { Intrinsic::hexagon_L2_loadri_pci, Hexagon::PS_loadri_pci },384    { Intrinsic::hexagon_L2_loadrd_pci, Hexagon::PS_loadrd_pci },385    { Intrinsic::hexagon_L2_loadrub_pcr, Hexagon::PS_loadrub_pcr },386    { Intrinsic::hexagon_L2_loadrb_pcr, Hexagon::PS_loadrb_pcr },387    { Intrinsic::hexagon_L2_loadruh_pcr, Hexagon::PS_loadruh_pcr },388    { Intrinsic::hexagon_L2_loadrh_pcr, Hexagon::PS_loadrh_pcr },389    { Intrinsic::hexagon_L2_loadri_pcr, Hexagon::PS_loadri_pcr },390    { Intrinsic::hexagon_L2_loadrd_pcr, Hexagon::PS_loadrd_pcr }391  };392  auto FLI = LoadNPcMap.find (IntNo);393  if (FLI != LoadNPcMap.end()) {394    EVT ValTy = MVT::i32;395    if (IntNo == Intrinsic::hexagon_L2_loadrd_pci ||396        IntNo == Intrinsic::hexagon_L2_loadrd_pcr)397      ValTy = MVT::i64;398    EVT RTys[] = { ValTy, MVT::i32, MVT::Other };399    // Handle load.*_pci case which has 6 operands.400    if (IntN->getNumOperands() == 6) {401      auto Inc = cast<ConstantSDNode>(IntN->getOperand(3));402      SDValue I = CurDAG->getTargetConstant(Inc->getSExtValue(), DL, MVT::i32);403      // Operands: { Base, Increment, Modifier, Start, Chain }.404      Ops = { IntN->getOperand(2), I, IntN->getOperand(4), IntN->getOperand(5),405              IntN->getOperand(0) };406    } else407      // Handle load.*_pcr case which has 5 operands.408      // Operands: { Base, Modifier, Start, Chain }.409      Ops = { IntN->getOperand(2), IntN->getOperand(3), IntN->getOperand(4),410              IntN->getOperand(0) };411    MachineSDNode *Res = CurDAG->getMachineNode(FLI->second, DL, RTys, Ops);412    ReplaceUses(SDValue(IntN, 0), SDValue(Res, 0));413    ReplaceUses(SDValue(IntN, 1), SDValue(Res, 1));414    ReplaceUses(SDValue(IntN, 2), SDValue(Res, 2));415    CurDAG->RemoveDeadNode(IntN);416    return true;417  }418 419  static std::map<unsigned,unsigned> StoreNPcMap = {420    { Intrinsic::hexagon_S2_storerb_pci, Hexagon::PS_storerb_pci },421    { Intrinsic::hexagon_S2_storerh_pci, Hexagon::PS_storerh_pci },422    { Intrinsic::hexagon_S2_storerf_pci, Hexagon::PS_storerf_pci },423    { Intrinsic::hexagon_S2_storeri_pci, Hexagon::PS_storeri_pci },424    { Intrinsic::hexagon_S2_storerd_pci, Hexagon::PS_storerd_pci },425    { Intrinsic::hexagon_S2_storerb_pcr, Hexagon::PS_storerb_pcr },426    { Intrinsic::hexagon_S2_storerh_pcr, Hexagon::PS_storerh_pcr },427    { Intrinsic::hexagon_S2_storerf_pcr, Hexagon::PS_storerf_pcr },428    { Intrinsic::hexagon_S2_storeri_pcr, Hexagon::PS_storeri_pcr },429    { Intrinsic::hexagon_S2_storerd_pcr, Hexagon::PS_storerd_pcr }430  };431  auto FSI = StoreNPcMap.find (IntNo);432  if (FSI != StoreNPcMap.end()) {433    EVT RTys[] = { MVT::i32, MVT::Other };434    // Handle store.*_pci case which has 7 operands.435    if (IntN->getNumOperands() == 7) {436      auto Inc = cast<ConstantSDNode>(IntN->getOperand(3));437      SDValue I = CurDAG->getTargetConstant(Inc->getSExtValue(), DL, MVT::i32);438      // Operands: { Base, Increment, Modifier, Value, Start, Chain }.439      Ops = { IntN->getOperand(2), I, IntN->getOperand(4), IntN->getOperand(5),440              IntN->getOperand(6), IntN->getOperand(0) };441    } else442      // Handle store.*_pcr case which has 6 operands.443      // Operands: { Base, Modifier, Value, Start, Chain }.444      Ops = { IntN->getOperand(2), IntN->getOperand(3), IntN->getOperand(4),445              IntN->getOperand(5), IntN->getOperand(0) };446    MachineSDNode *Res = CurDAG->getMachineNode(FSI->second, DL, RTys, Ops);447    ReplaceUses(SDValue(IntN, 0), SDValue(Res, 0));448    ReplaceUses(SDValue(IntN, 1), SDValue(Res, 1));449    CurDAG->RemoveDeadNode(IntN);450    return true;451  }452 453  return false;454}455 456void HexagonDAGToDAGISel::SelectLoad(SDNode *N) {457  SDLoc dl(N);458  LoadSDNode *LD = cast<LoadSDNode>(N);459 460  // Handle indexed loads.461  ISD::MemIndexedMode AM = LD->getAddressingMode();462  if (AM != ISD::UNINDEXED) {463    SelectIndexedLoad(LD, dl);464    return;465  }466 467  // Handle patterns using circ/brev load intrinsics.468  if (tryLoadOfLoadIntrinsic(LD))469    return;470 471  SelectCode(LD);472}473 474void HexagonDAGToDAGISel::SelectIndexedStore(StoreSDNode *ST, const SDLoc &dl) {475  SDValue Chain = ST->getChain();476  SDValue Base = ST->getBasePtr();477  SDValue Offset = ST->getOffset();478  SDValue Value = ST->getValue();479  // Get the constant value.480  int32_t Inc = cast<ConstantSDNode>(Offset.getNode())->getSExtValue();481  EVT StoredVT = ST->getMemoryVT();482  EVT ValueVT = Value.getValueType();483 484  bool IsValidInc = HII->isValidAutoIncImm(StoredVT, Inc);485  unsigned Opcode = 0;486 487  assert(StoredVT.isSimple());488  switch (StoredVT.getSimpleVT().SimpleTy) {489  case MVT::i8:490    Opcode = IsValidInc ? Hexagon::S2_storerb_pi : Hexagon::S2_storerb_io;491    break;492  case MVT::i16:493    Opcode = IsValidInc ? Hexagon::S2_storerh_pi : Hexagon::S2_storerh_io;494    break;495  case MVT::i32:496  case MVT::f32:497  case MVT::v2i16:498  case MVT::v4i8:499    Opcode = IsValidInc ? Hexagon::S2_storeri_pi : Hexagon::S2_storeri_io;500    break;501  case MVT::i64:502  case MVT::f64:503  case MVT::v2i32:504  case MVT::v4i16:505  case MVT::v8i8:506    Opcode = IsValidInc ? Hexagon::S2_storerd_pi : Hexagon::S2_storerd_io;507    break;508  case MVT::v64i8:509  case MVT::v32i16:510  case MVT::v16i32:511  case MVT::v8i64:512  case MVT::v128i8:513  case MVT::v64i16:514  case MVT::v32i32:515  case MVT::v16i64:516    if (isAlignedMemNode(ST)) {517      if (ST->isNonTemporal())518        Opcode = IsValidInc ? Hexagon::V6_vS32b_nt_pi : Hexagon::V6_vS32b_nt_ai;519      else520        Opcode = IsValidInc ? Hexagon::V6_vS32b_pi : Hexagon::V6_vS32b_ai;521    } else {522      Opcode = IsValidInc ? Hexagon::V6_vS32Ub_pi : Hexagon::V6_vS32Ub_ai;523    }524    break;525  default:526    llvm_unreachable("Unexpected memory type in indexed store");527  }528 529  if (ST->isTruncatingStore() && ValueVT.getSizeInBits() == 64) {530    assert(StoredVT.getSizeInBits() < 64 && "Not a truncating store");531    Value = CurDAG->getTargetExtractSubreg(Hexagon::isub_lo,532                                           dl, MVT::i32, Value);533  }534 535  SDValue IncV = CurDAG->getSignedTargetConstant(Inc, dl, MVT::i32);536  MachineMemOperand *MemOp = ST->getMemOperand();537 538  //                  Next address   Chain539  SDValue From[2] = { SDValue(ST,0), SDValue(ST,1) };540  SDValue To[2];541 542  if (IsValidInc) {543    // Build post increment store.544    SDValue Ops[] = { Base, IncV, Value, Chain };545    MachineSDNode *S = CurDAG->getMachineNode(Opcode, dl, MVT::i32, MVT::Other,546                                              Ops);547    CurDAG->setNodeMemRefs(S, {MemOp});548    To[0] = SDValue(S, 0);549    To[1] = SDValue(S, 1);550  } else {551    SDValue Zero = CurDAG->getTargetConstant(0, dl, MVT::i32);552    SDValue Ops[] = { Base, Zero, Value, Chain };553    MachineSDNode *S = CurDAG->getMachineNode(Opcode, dl, MVT::Other, Ops);554    CurDAG->setNodeMemRefs(S, {MemOp});555    To[1] = SDValue(S, 0);556    MachineSDNode *A = CurDAG->getMachineNode(Hexagon::A2_addi, dl, MVT::i32,557                                              Base, IncV);558    To[0] = SDValue(A, 0);559  }560 561  ReplaceUses(From, To, 2);562  CurDAG->RemoveDeadNode(ST);563}564 565void HexagonDAGToDAGISel::SelectStore(SDNode *N) {566  SDLoc dl(N);567  StoreSDNode *ST = cast<StoreSDNode>(N);568 569  // Handle indexed stores.570  ISD::MemIndexedMode AM = ST->getAddressingMode();571  if (AM != ISD::UNINDEXED) {572    SelectIndexedStore(ST, dl);573    return;574  }575 576  SelectCode(ST);577}578 579void HexagonDAGToDAGISel::SelectSHL(SDNode *N) {580  SDLoc dl(N);581  SDValue Shl_0 = N->getOperand(0);582  SDValue Shl_1 = N->getOperand(1);583 584  auto Default = [this,N] () -> void { SelectCode(N); };585 586  if (N->getValueType(0) != MVT::i32 || Shl_1.getOpcode() != ISD::Constant)587    return Default();588 589  // RHS is const.590  int32_t ShlConst = cast<ConstantSDNode>(Shl_1)->getSExtValue();591 592  if (Shl_0.getOpcode() == ISD::MUL) {593    SDValue Mul_0 = Shl_0.getOperand(0); // Val594    SDValue Mul_1 = Shl_0.getOperand(1); // Const595    // RHS of mul is const.596    if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Mul_1)) {597      int32_t ValConst = C->getSExtValue() << ShlConst;598      if (isInt<9>(ValConst)) {599        SDValue Val = CurDAG->getTargetConstant(ValConst, dl, MVT::i32);600        SDNode *Result = CurDAG->getMachineNode(Hexagon::M2_mpysmi, dl,601                                                MVT::i32, Mul_0, Val);602        ReplaceNode(N, Result);603        return;604      }605    }606    return Default();607  }608 609  if (Shl_0.getOpcode() == ISD::SUB) {610    SDValue Sub_0 = Shl_0.getOperand(0); // Const 0611    SDValue Sub_1 = Shl_0.getOperand(1); // Val612    if (ConstantSDNode *C1 = dyn_cast<ConstantSDNode>(Sub_0)) {613      if (C1->getSExtValue() != 0 || Sub_1.getOpcode() != ISD::SHL)614        return Default();615      SDValue Shl2_0 = Sub_1.getOperand(0); // Val616      SDValue Shl2_1 = Sub_1.getOperand(1); // Const617      if (ConstantSDNode *C2 = dyn_cast<ConstantSDNode>(Shl2_1)) {618        int32_t ValConst = 1 << (ShlConst + C2->getSExtValue());619        if (isInt<9>(-ValConst)) {620          SDValue Val =621              CurDAG->getSignedTargetConstant(-ValConst, dl, MVT::i32);622          SDNode *Result = CurDAG->getMachineNode(Hexagon::M2_mpysmi, dl,623                                                  MVT::i32, Shl2_0, Val);624          ReplaceNode(N, Result);625          return;626        }627      }628    }629  }630 631  return Default();632}633 634//635// Handling intrinsics for circular load and bitreverse load.636//637void HexagonDAGToDAGISel::SelectIntrinsicWChain(SDNode *N) {638  if (MachineSDNode *L = LoadInstrForLoadIntrinsic(N)) {639    StoreInstrForLoadIntrinsic(L, N);640    CurDAG->RemoveDeadNode(N);641    return;642  }643 644  // Handle bit-reverse load intrinsics.645  if (SelectBrevLdIntrinsic(N))646    return;647 648  if (SelectNewCircIntrinsic(N))649    return;650 651  unsigned IntNo = N->getConstantOperandVal(1);652  if (IntNo == Intrinsic::hexagon_V6_vgathermw ||653      IntNo == Intrinsic::hexagon_V6_vgathermw_128B ||654      IntNo == Intrinsic::hexagon_V6_vgathermh ||655      IntNo == Intrinsic::hexagon_V6_vgathermh_128B ||656      IntNo == Intrinsic::hexagon_V6_vgathermhw ||657      IntNo == Intrinsic::hexagon_V6_vgathermhw_128B ||658      IntNo == Intrinsic::hexagon_V6_vgather_vscattermh ||659      IntNo == Intrinsic::hexagon_V6_vgather_vscattermh_128B) {660    SelectV65Gather(N);661    return;662  }663  if (IntNo == Intrinsic::hexagon_V6_vgathermwq ||664      IntNo == Intrinsic::hexagon_V6_vgathermwq_128B ||665      IntNo == Intrinsic::hexagon_V6_vgathermhq ||666      IntNo == Intrinsic::hexagon_V6_vgathermhq_128B ||667      IntNo == Intrinsic::hexagon_V6_vgathermhwq ||668      IntNo == Intrinsic::hexagon_V6_vgathermhwq_128B) {669    SelectV65GatherPred(N);670    return;671  }672 673  SelectCode(N);674}675 676void HexagonDAGToDAGISel::SelectIntrinsicWOChain(SDNode *N) {677  unsigned IID = N->getConstantOperandVal(0);678  unsigned Bits;679  switch (IID) {680  case Intrinsic::hexagon_S2_vsplatrb:681    Bits = 8;682    break;683  case Intrinsic::hexagon_S2_vsplatrh:684    Bits = 16;685    break;686  case Intrinsic::hexagon_V6_vaddcarry:687  case Intrinsic::hexagon_V6_vaddcarry_128B:688  case Intrinsic::hexagon_V6_vsubcarry:689  case Intrinsic::hexagon_V6_vsubcarry_128B:690    SelectHVXDualOutput(N);691    return;692  default:693    SelectCode(N);694    return;695  }696 697  SDValue V = N->getOperand(1);698  SDValue U;699  // Splat intrinsics.700  if (keepsLowBits(V, Bits, U)) {701    SDValue R = CurDAG->getNode(N->getOpcode(), SDLoc(N), N->getValueType(0),702                                N->getOperand(0), U);703    ReplaceNode(N, R.getNode());704    SelectCode(R.getNode());705    return;706  }707  SelectCode(N);708}709 710void HexagonDAGToDAGISel::SelectExtractSubvector(SDNode *N) {711  SDValue Inp = N->getOperand(0);712  MVT ResTy = N->getValueType(0).getSimpleVT();713  unsigned Idx = N->getConstantOperandVal(1);714 715  [[maybe_unused]] MVT InpTy = Inp.getValueType().getSimpleVT();716  [[maybe_unused]] unsigned ResLen = ResTy.getVectorNumElements();717  assert(InpTy.getVectorElementType() == ResTy.getVectorElementType());718  assert(2 * ResLen == InpTy.getVectorNumElements());719  assert(ResTy.getSizeInBits() == 32);720  assert(Idx == 0 || Idx == ResLen);721 722  unsigned SubReg = Idx == 0 ? Hexagon::isub_lo : Hexagon::isub_hi;723  SDValue Ext = CurDAG->getTargetExtractSubreg(SubReg, SDLoc(N), ResTy, Inp);724 725  ReplaceNode(N, Ext.getNode());726}727 728//729// Map floating point constant values.730//731void HexagonDAGToDAGISel::SelectConstantFP(SDNode *N) {732  SDLoc dl(N);733  auto *CN = cast<ConstantFPSDNode>(N);734  APInt A = CN->getValueAPF().bitcastToAPInt();735  if (N->getValueType(0) == MVT::f32) {736    SDValue V = CurDAG->getTargetConstant(A.getZExtValue(), dl, MVT::i32);737    ReplaceNode(N, CurDAG->getMachineNode(Hexagon::A2_tfrsi, dl, MVT::f32, V));738    return;739  }740  if (N->getValueType(0) == MVT::f64) {741    SDValue V = CurDAG->getTargetConstant(A.getZExtValue(), dl, MVT::i64);742    ReplaceNode(N, CurDAG->getMachineNode(Hexagon::CONST64, dl, MVT::f64, V));743    return;744  }745 746  SelectCode(N);747}748 749//750// Map boolean values.751//752void HexagonDAGToDAGISel::SelectConstant(SDNode *N) {753  if (N->getValueType(0) == MVT::i1) {754    assert(!(N->getAsZExtVal() >> 1));755    unsigned Opc = (cast<ConstantSDNode>(N)->getSExtValue() != 0)756                      ? Hexagon::PS_true757                      : Hexagon::PS_false;758    ReplaceNode(N, CurDAG->getMachineNode(Opc, SDLoc(N), MVT::i1));759    return;760  }761 762  SelectCode(N);763}764 765void HexagonDAGToDAGISel::SelectFrameIndex(SDNode *N) {766  MachineFrameInfo &MFI = MF->getFrameInfo();767  const HexagonFrameLowering *HFI = HST->getFrameLowering();768  int FX = cast<FrameIndexSDNode>(N)->getIndex();769  Align StkA = HFI->getStackAlign();770  Align MaxA = MFI.getMaxAlign();771  SDValue FI = CurDAG->getTargetFrameIndex(FX, MVT::i32);772  SDLoc DL(N);773  SDValue Zero = CurDAG->getTargetConstant(0, DL, MVT::i32);774  SDNode *R = nullptr;775 776  // Use PS_fi when:777  // - the object is fixed, or778  // - there are no objects with higher-than-default alignment, or779  // - there are no dynamically allocated objects.780  // Otherwise, use PS_fia.781  if (FX < 0 || MaxA <= StkA || !MFI.hasVarSizedObjects()) {782    R = CurDAG->getMachineNode(Hexagon::PS_fi, DL, MVT::i32, FI, Zero);783  } else {784    auto &HMFI = *MF->getInfo<HexagonMachineFunctionInfo>();785    Register AR = HMFI.getStackAlignBaseReg();786    SDValue CH = CurDAG->getEntryNode();787    SDValue Ops[] = { CurDAG->getCopyFromReg(CH, DL, AR, MVT::i32), FI, Zero };788    R = CurDAG->getMachineNode(Hexagon::PS_fia, DL, MVT::i32, Ops);789  }790 791  ReplaceNode(N, R);792}793 794void HexagonDAGToDAGISel::SelectAddSubCarry(SDNode *N) {795  unsigned OpcCarry = N->getOpcode() == HexagonISD::ADDC ? Hexagon::A4_addp_c796                                                         : Hexagon::A4_subp_c;797  SDNode *C = CurDAG->getMachineNode(OpcCarry, SDLoc(N), N->getVTList(),798                                     { N->getOperand(0), N->getOperand(1),799                                       N->getOperand(2) });800  ReplaceNode(N, C);801}802 803void HexagonDAGToDAGISel::SelectVAlign(SDNode *N) {804  MVT ResTy = N->getValueType(0).getSimpleVT();805  if (HST->isHVXVectorType(ResTy, true))806    return SelectHvxVAlign(N);807 808  const SDLoc &dl(N);809  unsigned VecLen = ResTy.getSizeInBits();810  if (VecLen == 32) {811    SDValue Ops[] = {812      CurDAG->getTargetConstant(Hexagon::DoubleRegsRegClassID, dl, MVT::i32),813      N->getOperand(0),814      CurDAG->getTargetConstant(Hexagon::isub_hi, dl, MVT::i32),815      N->getOperand(1),816      CurDAG->getTargetConstant(Hexagon::isub_lo, dl, MVT::i32)817    };818    SDNode *R = CurDAG->getMachineNode(TargetOpcode::REG_SEQUENCE, dl,819                                       MVT::i64, Ops);820 821    // Shift right by "(Addr & 0x3) * 8" bytes.822    SDNode *C;823    SDValue M0 = CurDAG->getTargetConstant(0x18, dl, MVT::i32);824    SDValue M1 = CurDAG->getTargetConstant(0x03, dl, MVT::i32);825    if (HST->useCompound()) {826      C = CurDAG->getMachineNode(Hexagon::S4_andi_asl_ri, dl, MVT::i32,827                                 M0, N->getOperand(2), M1);828    } else {829      SDNode *T = CurDAG->getMachineNode(Hexagon::S2_asl_i_r, dl, MVT::i32,830                                         N->getOperand(2), M1);831      C = CurDAG->getMachineNode(Hexagon::A2_andir, dl, MVT::i32,832                                 SDValue(T, 0), M0);833    }834    SDNode *S = CurDAG->getMachineNode(Hexagon::S2_lsr_r_p, dl, MVT::i64,835                                       SDValue(R, 0), SDValue(C, 0));836    SDValue E = CurDAG->getTargetExtractSubreg(Hexagon::isub_lo, dl, ResTy,837                                               SDValue(S, 0));838    ReplaceNode(N, E.getNode());839  } else {840    assert(VecLen == 64);841    SDNode *Pu = CurDAG->getMachineNode(Hexagon::C2_tfrrp, dl, MVT::v8i1,842                                        N->getOperand(2));843    SDNode *VA = CurDAG->getMachineNode(Hexagon::S2_valignrb, dl, ResTy,844                                        N->getOperand(0), N->getOperand(1),845                                        SDValue(Pu,0));846    ReplaceNode(N, VA);847  }848}849 850void HexagonDAGToDAGISel::SelectVAlignAddr(SDNode *N) {851  const SDLoc &dl(N);852  SDValue A = N->getOperand(1);853  int Mask = -cast<ConstantSDNode>(A.getNode())->getSExtValue();854  assert(isPowerOf2_32(-Mask));855 856  SDValue M = CurDAG->getTargetConstant(Mask, dl, MVT::i32);857  SDNode *AA = CurDAG->getMachineNode(Hexagon::A2_andir, dl, MVT::i32,858                                      N->getOperand(0), M);859  ReplaceNode(N, AA);860}861 862// Handle these nodes here to avoid having to write patterns for all863// combinations of input/output types. In all cases, the resulting864// instruction is the same.865void HexagonDAGToDAGISel::SelectTypecast(SDNode *N) {866  SDValue Op = N->getOperand(0);867  MVT OpTy = Op.getValueType().getSimpleVT();868  SDNode *T = CurDAG->MorphNodeTo(N, N->getOpcode(),869                                  CurDAG->getVTList(OpTy), {Op});870  ReplaceNode(T, Op.getNode());871}872 873void HexagonDAGToDAGISel::SelectP2D(SDNode *N) {874  MVT ResTy = N->getValueType(0).getSimpleVT();875  SDNode *T = CurDAG->getMachineNode(Hexagon::C2_mask, SDLoc(N), ResTy,876                                     N->getOperand(0));877  ReplaceNode(N, T);878}879 880void HexagonDAGToDAGISel::SelectD2P(SDNode *N) {881  const SDLoc &dl(N);882  MVT ResTy = N->getValueType(0).getSimpleVT();883  SDValue Zero = CurDAG->getTargetConstant(0, dl, MVT::i32);884  SDNode *T = CurDAG->getMachineNode(Hexagon::A4_vcmpbgtui, dl, ResTy,885                                     N->getOperand(0), Zero);886  ReplaceNode(N, T);887}888 889void HexagonDAGToDAGISel::SelectV2Q(SDNode *N) {890  const SDLoc &dl(N);891  MVT ResTy = N->getValueType(0).getSimpleVT();892  // The argument to V2Q should be a single vector.893  MVT OpTy = N->getOperand(0).getValueType().getSimpleVT(); (void)OpTy;894  assert(HST->getVectorLength() * 8 == OpTy.getSizeInBits());895 896  SDValue C = CurDAG->getSignedTargetConstant(-1, dl, MVT::i32);897  SDNode *R = CurDAG->getMachineNode(Hexagon::A2_tfrsi, dl, MVT::i32, C);898  SDNode *T = CurDAG->getMachineNode(Hexagon::V6_vandvrt, dl, ResTy,899                                     N->getOperand(0), SDValue(R,0));900  ReplaceNode(N, T);901}902 903void HexagonDAGToDAGISel::SelectQ2V(SDNode *N) {904  const SDLoc &dl(N);905  MVT ResTy = N->getValueType(0).getSimpleVT();906  // The result of V2Q should be a single vector.907  assert(HST->getVectorLength() * 8 == ResTy.getSizeInBits());908 909  SDValue C = CurDAG->getSignedTargetConstant(-1, dl, MVT::i32);910  SDNode *R = CurDAG->getMachineNode(Hexagon::A2_tfrsi, dl, MVT::i32, C);911  SDNode *T = CurDAG->getMachineNode(Hexagon::V6_vandqrt, dl, ResTy,912                                     N->getOperand(0), SDValue(R,0));913  ReplaceNode(N, T);914}915 916void HexagonDAGToDAGISel::FDiv(SDNode *N) {917  const SDLoc &dl(N);918  ArrayRef<EVT> ResultType(N->value_begin(), N->value_end());919  SmallVector<SDValue, 2> Ops;920  Ops = {N->getOperand(0), N->getOperand(1)};921  SDVTList VTs;922  VTs = CurDAG->getVTList(MVT::f32, MVT::f32);923  SDNode *ResScale = CurDAG->getMachineNode(Hexagon::F2_sfrecipa, dl, VTs, Ops);924  SDNode *D = CurDAG->getMachineNode(Hexagon::F2_sffixupd, dl, MVT::f32, Ops);925 926  SDValue C = CurDAG->getTargetConstant(0x3f800000, dl, MVT::i32);927  SDNode *constNode =928      CurDAG->getMachineNode(Hexagon::A2_tfrsi, dl, MVT::f32, C);929 930  SDNode *n = CurDAG->getMachineNode(Hexagon::F2_sffixupn, dl, MVT::f32, Ops);931  SDNode *Err = CurDAG->getMachineNode(Hexagon::F2_sffms_lib, dl, MVT::f32,932                                       SDValue(constNode, 0), SDValue(D, 0),933                                       SDValue(ResScale, 0));934  SDNode *NewRec = CurDAG->getMachineNode(Hexagon::F2_sffma_lib, dl, MVT::f32,935                                          SDValue(ResScale, 0), SDValue(Err, 0),936                                          SDValue(ResScale, 0));937  SDNode *newErr = CurDAG->getMachineNode(Hexagon::F2_sffms_lib, dl, MVT::f32,938                                          SDValue(constNode, 0), SDValue(D, 0),939                                          SDValue(NewRec, 0));940  SDNode *q = CurDAG->getMachineNode(941      Hexagon::A2_andir, dl, MVT::f32, SDValue(n, 0),942      CurDAG->getTargetConstant(0x80000000, dl, MVT::i32));943  SDNode *NewQ =944      CurDAG->getMachineNode(Hexagon::F2_sffma_lib, dl, MVT::f32, SDValue(q, 0),945                             SDValue(n, 0), SDValue(NewRec, 0));946  SDNode *NNewRec = CurDAG->getMachineNode(947      Hexagon::F2_sffma_lib, dl, MVT::f32, SDValue(NewRec, 0),948      SDValue(newErr, 0), SDValue(NewRec, 0));949  SDNode *qErr =950      CurDAG->getMachineNode(Hexagon::F2_sffms_lib, dl, MVT::f32, SDValue(n, 0),951                             SDValue(D, 0), SDValue(NewQ, 0));952  SDNode *NNewQ = CurDAG->getMachineNode(Hexagon::F2_sffma_lib, dl, MVT::f32,953                                         SDValue(NewQ, 0), SDValue(qErr, 0),954                                         SDValue(NNewRec, 0));955 956  SDNode *NqErr =957      CurDAG->getMachineNode(Hexagon::F2_sffms_lib, dl, MVT::f32, SDValue(n, 0),958                             SDValue(NNewQ, 0), SDValue(D, 0));959  std::array<SDValue, 4> temp1 = {SDValue(NNewQ, 0), SDValue(NqErr, 0),960                                  SDValue(NNewRec, 0), SDValue(ResScale, 1)};961  ArrayRef<SDValue> OpValue1(temp1);962  SDNode *FinalNewQ =963      CurDAG->getMachineNode(Hexagon::F2_sffma_sc, dl, MVT::f32, OpValue1);964  ReplaceNode(N, FinalNewQ);965}966 967void HexagonDAGToDAGISel::FastFDiv(SDNode *N) {968  const SDLoc &dl(N);969  ArrayRef<EVT> ResultType(N->value_begin(), N->value_end());970  SmallVector<SDValue, 2> Ops;971  Ops = {N->getOperand(0), N->getOperand(1)};972  SDVTList VTs;973  VTs = CurDAG->getVTList(MVT::f32, MVT::f32);974  SDNode *ResScale = CurDAG->getMachineNode(Hexagon::F2_sfrecipa, dl, VTs, Ops);975  SDNode *D = CurDAG->getMachineNode(Hexagon::F2_sffixupd, dl, MVT::f32, Ops);976 977  SDValue C = CurDAG->getTargetConstant(0x3f800000, dl, MVT::i32);978  SDNode *constNode =979      CurDAG->getMachineNode(Hexagon::A2_tfrsi, dl, MVT::f32, C);980 981  SDNode *n = CurDAG->getMachineNode(Hexagon::F2_sffixupn, dl, MVT::f32, Ops);982  SDNode *Err = CurDAG->getMachineNode(Hexagon::F2_sffms_lib, dl, MVT::f32,983                                       SDValue(constNode, 0), SDValue(D, 0),984                                       SDValue(ResScale, 0));985  SDNode *NewRec = CurDAG->getMachineNode(Hexagon::F2_sffma_lib, dl, MVT::f32,986                                          SDValue(ResScale, 0), SDValue(Err, 0),987                                          SDValue(ResScale, 0));988  SDNode *newErr = CurDAG->getMachineNode(Hexagon::F2_sffms_lib, dl, MVT::f32,989                                          SDValue(constNode, 0), SDValue(D, 0),990                                          SDValue(NewRec, 0));991 992  SDNode *NNewRec = CurDAG->getMachineNode(993      Hexagon::F2_sffma_lib, dl, MVT::f32, SDValue(NewRec, 0),994      SDValue(newErr, 0), SDValue(NewRec, 0));995  SDNode *FinalNewQ = CurDAG->getMachineNode(996      Hexagon::F2_sfmpy, dl, MVT::f32, SDValue(NNewRec, 0), SDValue(n, 0));997  ReplaceNode(N, FinalNewQ);998}999 1000void HexagonDAGToDAGISel::SelectFDiv(SDNode *N) {1001  if (N->getFlags().hasAllowReassociation())1002    FastFDiv(N);1003  else1004    FDiv(N);1005}1006 1007void HexagonDAGToDAGISel::Select(SDNode *N) {1008  if (N->isMachineOpcode())1009    return N->setNodeId(-1);  // Already selected.1010 1011  auto isHvxOp = [this](SDNode *N) {1012    for (unsigned i = 0, e = N->getNumValues(); i != e; ++i) {1013      if (HST->isHVXVectorType(N->getValueType(i), true))1014        return true;1015    }1016    for (SDValue I : N->ops()) {1017      if (HST->isHVXVectorType(I.getValueType(), true))1018        return true;1019    }1020    return false;1021  };1022 1023  if (HST->useHVXOps() && isHvxOp(N)) {1024    switch (N->getOpcode()) {1025    case ISD::EXTRACT_SUBVECTOR:  return SelectHvxExtractSubvector(N);1026    case ISD::VECTOR_SHUFFLE:     return SelectHvxShuffle(N);1027 1028    case HexagonISD::VROR:        return SelectHvxRor(N);1029    }1030  }1031 1032  switch (N->getOpcode()) {1033  case ISD::Constant:             return SelectConstant(N);1034  case ISD::ConstantFP:           return SelectConstantFP(N);1035  case ISD::FrameIndex:           return SelectFrameIndex(N);1036  case ISD::SHL:                  return SelectSHL(N);1037  case ISD::LOAD:                 return SelectLoad(N);1038  case ISD::STORE:                return SelectStore(N);1039  case ISD::INTRINSIC_W_CHAIN:    return SelectIntrinsicWChain(N);1040  case ISD::INTRINSIC_WO_CHAIN:   return SelectIntrinsicWOChain(N);1041  case ISD::EXTRACT_SUBVECTOR:    return SelectExtractSubvector(N);1042 1043  case HexagonISD::ADDC:1044  case HexagonISD::SUBC:          return SelectAddSubCarry(N);1045  case HexagonISD::VALIGN:        return SelectVAlign(N);1046  case HexagonISD::VALIGNADDR:    return SelectVAlignAddr(N);1047  case HexagonISD::TYPECAST:      return SelectTypecast(N);1048  case HexagonISD::P2D:           return SelectP2D(N);1049  case HexagonISD::D2P:           return SelectD2P(N);1050  case HexagonISD::Q2V:           return SelectQ2V(N);1051  case HexagonISD::V2Q:           return SelectV2Q(N);1052  case ISD::FDIV:1053    return SelectFDiv(N);1054  }1055 1056  SelectCode(N);1057}1058 1059bool HexagonDAGToDAGISel::SelectInlineAsmMemoryOperand(1060    const SDValue &Op, InlineAsm::ConstraintCode ConstraintID,1061    std::vector<SDValue> &OutOps) {1062  SDValue Inp = Op, Res;1063 1064  switch (ConstraintID) {1065  default:1066    return true;1067  case InlineAsm::ConstraintCode::o: // Offsetable.1068  case InlineAsm::ConstraintCode::v: // Not offsetable.1069  case InlineAsm::ConstraintCode::m: // Memory.1070    if (SelectAddrFI(Inp, Res))1071      OutOps.push_back(Res);1072    else1073      OutOps.push_back(Inp);1074    break;1075  }1076 1077  OutOps.push_back(CurDAG->getTargetConstant(0, SDLoc(Op), MVT::i32));1078  return false;1079}1080 1081static bool isMemOPCandidate(SDNode *I, SDNode *U) {1082  // I is an operand of U. Check if U is an arithmetic (binary) operation1083  // usable in a memop, where the other operand is a loaded value, and the1084  // result of U is stored in the same location.1085 1086  if (!U->hasOneUse())1087    return false;1088  unsigned Opc = U->getOpcode();1089  switch (Opc) {1090    case ISD::ADD:1091    case ISD::SUB:1092    case ISD::AND:1093    case ISD::OR:1094      break;1095    default:1096      return false;1097  }1098 1099  SDValue S0 = U->getOperand(0);1100  SDValue S1 = U->getOperand(1);1101  SDValue SY = (S0.getNode() == I) ? S1 : S0;1102 1103  SDNode *UUse = *U->user_begin();1104  if (UUse->getNumValues() != 1)1105    return false;1106 1107  // Check if one of the inputs to U is a load instruction and the output1108  // is used by a store instruction. If so and they also have the same1109  // base pointer, then don't preoprocess this node sequence as it1110  // can be matched to a memop.1111  SDNode *SYNode = SY.getNode();1112  if (UUse->getOpcode() == ISD::STORE && SYNode->getOpcode() == ISD::LOAD) {1113    SDValue LDBasePtr = cast<MemSDNode>(SYNode)->getBasePtr();1114    SDValue STBasePtr = cast<MemSDNode>(UUse)->getBasePtr();1115    if (LDBasePtr == STBasePtr)1116      return true;1117  }1118  return false;1119}1120 1121 1122// Transform: (or (select c x 0) z)  ->  (select c (or x z) z)1123//            (or (select c 0 y) z)  ->  (select c z (or y z))1124void HexagonDAGToDAGISel::ppSimplifyOrSelect0(std::vector<SDNode*> &&Nodes) {1125  SelectionDAG &DAG = *CurDAG;1126 1127  for (auto *I : Nodes) {1128    if (I->getOpcode() != ISD::OR)1129      continue;1130 1131    auto IsSelect0 = [](const SDValue &Op) -> bool {1132      if (Op.getOpcode() != ISD::SELECT)1133        return false;1134      return isNullConstant(Op.getOperand(1)) ||1135             isNullConstant(Op.getOperand(2));1136    };1137 1138    SDValue N0 = I->getOperand(0), N1 = I->getOperand(1);1139    EVT VT = I->getValueType(0);1140    bool SelN0 = IsSelect0(N0);1141    SDValue SOp = SelN0 ? N0 : N1;1142    SDValue VOp = SelN0 ? N1 : N0;1143 1144    if (SOp.getOpcode() == ISD::SELECT && SOp.getNode()->hasOneUse()) {1145      SDValue SC = SOp.getOperand(0);1146      SDValue SX = SOp.getOperand(1);1147      SDValue SY = SOp.getOperand(2);1148      SDLoc DLS = SOp;1149      if (isNullConstant(SY)) {1150        SDValue NewOr = DAG.getNode(ISD::OR, DLS, VT, SX, VOp);1151        SDValue NewSel = DAG.getNode(ISD::SELECT, DLS, VT, SC, NewOr, VOp);1152        DAG.ReplaceAllUsesWith(I, NewSel.getNode());1153      } else if (isNullConstant(SX)) {1154        SDValue NewOr = DAG.getNode(ISD::OR, DLS, VT, SY, VOp);1155        SDValue NewSel = DAG.getNode(ISD::SELECT, DLS, VT, SC, VOp, NewOr);1156        DAG.ReplaceAllUsesWith(I, NewSel.getNode());1157      }1158    }1159  }1160}1161 1162// Transform: (store ch val (add x (add (shl y c) e)))1163//        to: (store ch val (add x (shl (add y d) c))),1164// where e = (shl d c) for some integer d.1165// The purpose of this is to enable generation of loads/stores with1166// shifted addressing mode, i.e. mem(x+y<<#c). For that, the shift1167// value c must be 0, 1 or 2.1168void HexagonDAGToDAGISel::ppAddrReorderAddShl(std::vector<SDNode*> &&Nodes) {1169  SelectionDAG &DAG = *CurDAG;1170 1171  for (auto *I : Nodes) {1172    if (I->getOpcode() != ISD::STORE)1173      continue;1174 1175    // I matched: (store ch val Off)1176    SDValue Off = I->getOperand(2);1177    // Off needs to match: (add x (add (shl y c) (shl d c))))1178    if (Off.getOpcode() != ISD::ADD)1179      continue;1180    // Off matched: (add x T0)1181    SDValue T0 = Off.getOperand(1);1182    // T0 needs to match: (add T1 T2):1183    if (T0.getOpcode() != ISD::ADD)1184      continue;1185    // T0 matched: (add T1 T2)1186    SDValue T1 = T0.getOperand(0);1187    SDValue T2 = T0.getOperand(1);1188    // T1 needs to match: (shl y c)1189    if (T1.getOpcode() != ISD::SHL)1190      continue;1191    SDValue C = T1.getOperand(1);1192    ConstantSDNode *CN = dyn_cast<ConstantSDNode>(C.getNode());1193    if (CN == nullptr)1194      continue;1195    unsigned CV = CN->getZExtValue();1196    if (CV > 2)1197      continue;1198    // T2 needs to match e, where e = (shl d c) for some d.1199    ConstantSDNode *EN = dyn_cast<ConstantSDNode>(T2.getNode());1200    if (EN == nullptr)1201      continue;1202    unsigned EV = EN->getZExtValue();1203    if (EV % (1 << CV) != 0)1204      continue;1205    unsigned DV = EV / (1 << CV);1206 1207    // Replace T0 with: (shl (add y d) c)1208    SDLoc DL = SDLoc(I);1209    EVT VT = T0.getValueType();1210    SDValue D = DAG.getConstant(DV, DL, VT);1211    // NewAdd = (add y d)1212    SDValue NewAdd = DAG.getNode(ISD::ADD, DL, VT, T1.getOperand(0), D);1213    // NewShl = (shl NewAdd c)1214    SDValue NewShl = DAG.getNode(ISD::SHL, DL, VT, NewAdd, C);1215    ReplaceNode(T0.getNode(), NewShl.getNode());1216  }1217}1218 1219// Transform: (load ch (add x (and (srl y c) Mask)))1220//        to: (load ch (add x (shl (srl y d) d-c)))1221// where1222// Mask = 00..0 111..1 0.01223//          |     |     +-- d-c 0s, and d-c is 0, 1 or 2.1224//          |     +-------- 1s1225//          +-------------- at most c 0s1226// Motivating example:1227// DAG combiner optimizes (add x (shl (srl y 5) 2))1228//                     to (add x (and (srl y 3) 1FFFFFFC))1229// which results in a constant-extended and(##...,lsr). This transformation1230// undoes this simplification for cases where the shl can be folded into1231// an addressing mode.1232void HexagonDAGToDAGISel::ppAddrRewriteAndSrl(std::vector<SDNode*> &&Nodes) {1233  SelectionDAG &DAG = *CurDAG;1234 1235  for (SDNode *N : Nodes) {1236    unsigned Opc = N->getOpcode();1237    if (Opc != ISD::LOAD && Opc != ISD::STORE)1238      continue;1239    SDValue Addr = Opc == ISD::LOAD ? N->getOperand(1) : N->getOperand(2);1240    // Addr must match: (add x T0)1241    if (Addr.getOpcode() != ISD::ADD)1242      continue;1243    SDValue T0 = Addr.getOperand(1);1244    // T0 must match: (and T1 Mask)1245    if (T0.getOpcode() != ISD::AND)1246      continue;1247 1248    // We have an AND.1249    //1250    // Check the first operand. It must be: (srl y c).1251    SDValue S = T0.getOperand(0);1252    if (S.getOpcode() != ISD::SRL)1253      continue;1254    ConstantSDNode *SN = dyn_cast<ConstantSDNode>(S.getOperand(1).getNode());1255    if (SN == nullptr)1256      continue;1257    if (SN->getAPIntValue().getBitWidth() != 32)1258      continue;1259    uint32_t CV = SN->getZExtValue();1260 1261    // Check the second operand: the supposed mask.1262    ConstantSDNode *MN = dyn_cast<ConstantSDNode>(T0.getOperand(1).getNode());1263    if (MN == nullptr)1264      continue;1265    if (MN->getAPIntValue().getBitWidth() != 32)1266      continue;1267    uint32_t Mask = MN->getZExtValue();1268    // Examine the mask.1269    uint32_t TZ = llvm::countr_zero(Mask);1270    uint32_t M1 = llvm::countr_one(Mask >> TZ);1271    uint32_t LZ = llvm::countl_zero(Mask);1272    // Trailing zeros + middle ones + leading zeros must equal the width.1273    if (TZ + M1 + LZ != 32)1274      continue;1275    // The number of trailing zeros will be encoded in the addressing mode.1276    if (TZ > 2)1277      continue;1278    // The number of leading zeros must be at most c.1279    if (LZ > CV)1280      continue;1281 1282    // All looks good.1283    SDValue Y = S.getOperand(0);1284    EVT VT = Addr.getValueType();1285    SDLoc dl(S);1286    // TZ = D-C, so D = TZ+C.1287    SDValue D = DAG.getConstant(TZ+CV, dl, VT);1288    SDValue DC = DAG.getConstant(TZ, dl, VT);1289    SDValue NewSrl = DAG.getNode(ISD::SRL, dl, VT, Y, D);1290    SDValue NewShl = DAG.getNode(ISD::SHL, dl, VT, NewSrl, DC);1291    ReplaceNode(T0.getNode(), NewShl.getNode());1292  }1293}1294 1295// Transform: (op ... (zext i1 c) ...) -> (select c (op ... 0 ...)1296//                                                  (op ... 1 ...))1297void HexagonDAGToDAGISel::ppHoistZextI1(std::vector<SDNode*> &&Nodes) {1298  SelectionDAG &DAG = *CurDAG;1299 1300  for (SDNode *N : Nodes) {1301    unsigned Opc = N->getOpcode();1302    if (Opc != ISD::ZERO_EXTEND)1303      continue;1304    SDValue OpI1 = N->getOperand(0);1305    EVT OpVT = OpI1.getValueType();1306    if (!OpVT.isSimple() || OpVT.getSimpleVT() != MVT::i1)1307      continue;1308    for (SDUse &Use : N->uses()) {1309      SDNode *U = Use.getUser();1310      if (U->getNumValues() != 1)1311        continue;1312      EVT UVT = U->getValueType(0);1313      if (!UVT.isSimple() || !UVT.isInteger() || UVT.getSimpleVT() == MVT::i1)1314        continue;1315      // Do not generate select for all i1 vector type.1316      if (UVT.isVector() && UVT.getVectorElementType() == MVT::i1)1317        continue;1318      if (isMemOPCandidate(N, U))1319        continue;1320 1321      // Potentially simplifiable operation.1322      unsigned I1N = Use.getOperandNo();1323      SmallVector<SDValue,2> Ops(U->getNumOperands());1324      for (unsigned i = 0, n = U->getNumOperands(); i != n; ++i)1325        Ops[i] = U->getOperand(i);1326      EVT BVT = Ops[I1N].getValueType();1327 1328      const SDLoc &dl(U);1329      SDValue C0 = DAG.getConstant(0, dl, BVT);1330      SDValue C1 = DAG.getConstant(1, dl, BVT);1331      SDValue If0, If1;1332 1333      if (isa<MachineSDNode>(U)) {1334        unsigned UseOpc = U->getMachineOpcode();1335        Ops[I1N] = C0;1336        If0 = SDValue(DAG.getMachineNode(UseOpc, dl, UVT, Ops), 0);1337        Ops[I1N] = C1;1338        If1 = SDValue(DAG.getMachineNode(UseOpc, dl, UVT, Ops), 0);1339      } else {1340        unsigned UseOpc = U->getOpcode();1341        Ops[I1N] = C0;1342        If0 = DAG.getNode(UseOpc, dl, UVT, Ops);1343        Ops[I1N] = C1;1344        If1 = DAG.getNode(UseOpc, dl, UVT, Ops);1345      }1346      // We're generating a SELECT way after legalization, so keep the types1347      // simple.1348      unsigned UW = UVT.getSizeInBits();1349      EVT SVT = (UW == 32 || UW == 64) ? MVT::getIntegerVT(UW) : UVT;1350      SDValue Sel = DAG.getNode(ISD::SELECT, dl, SVT, OpI1,1351                                DAG.getBitcast(SVT, If1),1352                                DAG.getBitcast(SVT, If0));1353      SDValue Ret = DAG.getBitcast(UVT, Sel);1354      DAG.ReplaceAllUsesWith(U, Ret.getNode());1355    }1356  }1357}1358 1359void HexagonDAGToDAGISel::PreprocessISelDAG() {1360  // Repack all nodes before calling each preprocessing function,1361  // because each of them can modify the set of nodes.1362  auto getNodes = [this]() -> std::vector<SDNode *> {1363    std::vector<SDNode *> T;1364    T.reserve(CurDAG->allnodes_size());1365    for (SDNode &N : CurDAG->allnodes())1366      T.push_back(&N);1367    return T;1368  };1369 1370  if (HST->useHVXOps())1371    PreprocessHvxISelDAG();1372 1373  // Transform: (or (select c x 0) z)  ->  (select c (or x z) z)1374  //            (or (select c 0 y) z)  ->  (select c z (or y z))1375  ppSimplifyOrSelect0(getNodes());1376 1377  // Transform: (store ch val (add x (add (shl y c) e)))1378  //        to: (store ch val (add x (shl (add y d) c))),1379  // where e = (shl d c) for some integer d.1380  // The purpose of this is to enable generation of loads/stores with1381  // shifted addressing mode, i.e. mem(x+y<<#c). For that, the shift1382  // value c must be 0, 1 or 2.1383  ppAddrReorderAddShl(getNodes());1384 1385  // Transform: (load ch (add x (and (srl y c) Mask)))1386  //        to: (load ch (add x (shl (srl y d) d-c)))1387  // where1388  // Mask = 00..0 111..1 0.01389  //          |     |     +-- d-c 0s, and d-c is 0, 1 or 2.1390  //          |     +-------- 1s1391  //          +-------------- at most c 0s1392  // Motivating example:1393  // DAG combiner optimizes (add x (shl (srl y 5) 2))1394  //                     to (add x (and (srl y 3) 1FFFFFFC))1395  // which results in a constant-extended and(##...,lsr). This transformation1396  // undoes this simplification for cases where the shl can be folded into1397  // an addressing mode.1398  ppAddrRewriteAndSrl(getNodes());1399 1400  // Transform: (op ... (zext i1 c) ...) -> (select c (op ... 0 ...)1401  //                                                  (op ... 1 ...))1402  ppHoistZextI1(getNodes());1403 1404  DEBUG_WITH_TYPE("isel", {1405    dbgs() << "Preprocessed (Hexagon) selection DAG:";1406    CurDAG->dump();1407  });1408 1409  if (EnableAddressRebalancing) {1410    rebalanceAddressTrees();1411 1412    DEBUG_WITH_TYPE("isel", {1413      dbgs() << "Address tree balanced selection DAG:";1414      CurDAG->dump();1415    });1416  }1417}1418 1419void HexagonDAGToDAGISel::emitFunctionEntryCode() {1420  auto &HST = MF->getSubtarget<HexagonSubtarget>();1421  auto &HFI = *HST.getFrameLowering();1422  if (!HFI.needsAligna(*MF))1423    return;1424 1425  MachineFrameInfo &MFI = MF->getFrameInfo();1426  MachineBasicBlock *EntryBB = &MF->front();1427  Align EntryMaxA = MFI.getMaxAlign();1428 1429  // Reserve the first non-volatile register.1430  Register AP = 0;1431  auto &HRI = *HST.getRegisterInfo();1432  BitVector Reserved = HRI.getReservedRegs(*MF);1433  for (const MCPhysReg *R = HRI.getCalleeSavedRegs(MF); *R; ++R) {1434    if (Reserved[*R])1435      continue;1436    AP = *R;1437    break;1438  }1439  assert(AP.isValid() && "Couldn't reserve stack align register");1440  BuildMI(EntryBB, DebugLoc(), HII->get(Hexagon::PS_aligna), AP)1441      .addImm(EntryMaxA.value());1442  MF->getInfo<HexagonMachineFunctionInfo>()->setStackAlignBaseReg(AP);1443}1444 1445void HexagonDAGToDAGISel::updateAligna() {1446  auto &HFI = *MF->getSubtarget<HexagonSubtarget>().getFrameLowering();1447  if (!HFI.needsAligna(*MF))1448    return;1449  auto *AlignaI = const_cast<MachineInstr*>(HFI.getAlignaInstr(*MF));1450  assert(AlignaI != nullptr);1451  unsigned MaxA = MF->getFrameInfo().getMaxAlign().value();1452  if (AlignaI->getOperand(1).getImm() < MaxA)1453    AlignaI->getOperand(1).setImm(MaxA);1454}1455 1456// Match a frame index that can be used in an addressing mode.1457bool HexagonDAGToDAGISel::SelectAddrFI(SDValue &N, SDValue &R) {1458  if (N.getOpcode() != ISD::FrameIndex)1459    return false;1460  auto &HFI = *HST->getFrameLowering();1461  MachineFrameInfo &MFI = MF->getFrameInfo();1462  int FX = cast<FrameIndexSDNode>(N)->getIndex();1463  if (!MFI.isFixedObjectIndex(FX) && HFI.needsAligna(*MF))1464    return false;1465  R = CurDAG->getTargetFrameIndex(FX, MVT::i32);1466  return true;1467}1468 1469inline bool HexagonDAGToDAGISel::SelectAddrGA(SDValue &N, SDValue &R) {1470  return SelectGlobalAddress(N, R, false, Align(1));1471}1472 1473inline bool HexagonDAGToDAGISel::SelectAddrGP(SDValue &N, SDValue &R) {1474  return SelectGlobalAddress(N, R, true, Align(1));1475}1476 1477inline bool HexagonDAGToDAGISel::SelectAnyImm(SDValue &N, SDValue &R) {1478  return SelectAnyImmediate(N, R, Align(1));1479}1480 1481inline bool HexagonDAGToDAGISel::SelectAnyImm0(SDValue &N, SDValue &R) {1482  return SelectAnyImmediate(N, R, Align(1));1483}1484inline bool HexagonDAGToDAGISel::SelectAnyImm1(SDValue &N, SDValue &R) {1485  return SelectAnyImmediate(N, R, Align(2));1486}1487inline bool HexagonDAGToDAGISel::SelectAnyImm2(SDValue &N, SDValue &R) {1488  return SelectAnyImmediate(N, R, Align(4));1489}1490inline bool HexagonDAGToDAGISel::SelectAnyImm3(SDValue &N, SDValue &R) {1491  return SelectAnyImmediate(N, R, Align(8));1492}1493 1494inline bool HexagonDAGToDAGISel::SelectAnyInt(SDValue &N, SDValue &R) {1495  EVT T = N.getValueType();1496  if (!T.isInteger() || T.getSizeInBits() != 32 || !isa<ConstantSDNode>(N))1497    return false;1498  uint32_t V = cast<const ConstantSDNode>(N)->getZExtValue();1499  R = CurDAG->getTargetConstant(V, SDLoc(N), N.getValueType());1500  return true;1501}1502 1503bool HexagonDAGToDAGISel::SelectAnyImmediate(SDValue &N, SDValue &R,1504                                             Align Alignment) {1505  switch (N.getOpcode()) {1506  case ISD::Constant: {1507    if (N.getValueType() != MVT::i32)1508      return false;1509    uint32_t V = cast<const ConstantSDNode>(N)->getZExtValue();1510    if (!isAligned(Alignment, V))1511      return false;1512    R = CurDAG->getTargetConstant(V, SDLoc(N), N.getValueType());1513    return true;1514  }1515  case HexagonISD::JT:1516  case HexagonISD::CP:1517    // These are assumed to always be aligned at least 8-byte boundary.1518    if (Alignment > Align(8))1519      return false;1520    R = N.getOperand(0);1521    return true;1522  case ISD::ExternalSymbol:1523    // Symbols may be aligned at any boundary.1524    if (Alignment > Align(1))1525      return false;1526    R = N;1527    return true;1528  case ISD::BlockAddress:1529    // Block address is always aligned at least 4-byte boundary.1530    if (Alignment > Align(4) ||1531        !isAligned(Alignment, cast<BlockAddressSDNode>(N)->getOffset()))1532      return false;1533    R = N;1534    return true;1535  }1536 1537  if (SelectGlobalAddress(N, R, false, Alignment) ||1538      SelectGlobalAddress(N, R, true, Alignment))1539    return true;1540 1541  return false;1542}1543 1544bool HexagonDAGToDAGISel::SelectGlobalAddress(SDValue &N, SDValue &R,1545                                              bool UseGP, Align Alignment) {1546  switch (N.getOpcode()) {1547  case ISD::ADD: {1548    SDValue N0 = N.getOperand(0);1549    SDValue N1 = N.getOperand(1);1550    unsigned GAOpc = N0.getOpcode();1551    if (UseGP && GAOpc != HexagonISD::CONST32_GP)1552      return false;1553    if (!UseGP && GAOpc != HexagonISD::CONST32)1554      return false;1555    if (ConstantSDNode *Const = dyn_cast<ConstantSDNode>(N1)) {1556      if (!isAligned(Alignment, Const->getZExtValue()))1557        return false;1558      SDValue Addr = N0.getOperand(0);1559      if (GlobalAddressSDNode *GA = dyn_cast<GlobalAddressSDNode>(Addr)) {1560        if (GA->getOpcode() == ISD::TargetGlobalAddress) {1561          uint64_t NewOff = GA->getOffset() + (uint64_t)Const->getSExtValue();1562          R = CurDAG->getTargetGlobalAddress(GA->getGlobal(), SDLoc(Const),1563                                             N.getValueType(), NewOff);1564          return true;1565        }1566      }1567    }1568    break;1569  }1570  case HexagonISD::CP:1571  case HexagonISD::JT:1572  case HexagonISD::CONST32:1573    // The operand(0) of CONST32 is TargetGlobalAddress, which is what we1574    // want in the instruction.1575    if (!UseGP)1576      R = N.getOperand(0);1577    return !UseGP;1578  case HexagonISD::CONST32_GP:1579    if (UseGP)1580      R = N.getOperand(0);1581    return UseGP;1582  default:1583    return false;1584  }1585 1586  return false;1587}1588 1589bool HexagonDAGToDAGISel::DetectUseSxtw(SDValue &N, SDValue &R) {1590  // This (complex pattern) function is meant to detect a sign-extension1591  // i32->i64 on a per-operand basis. This would allow writing single1592  // patterns that would cover a number of combinations of different ways1593  // a sign-extensions could be written. For example:1594  //   (mul (DetectUseSxtw x) (DetectUseSxtw y)) -> (M2_dpmpyss_s0 x y)1595  // could match either one of these:1596  //   (mul (sext x) (sext_inreg y))1597  //   (mul (sext-load *p) (sext_inreg y))1598  //   (mul (sext_inreg x) (sext y))1599  // etc.1600  //1601  // The returned value will have type i64 and its low word will1602  // contain the value being extended. The high bits are not specified.1603  // The returned type is i64 because the original type of N was i64,1604  // but the users of this function should only use the low-word of the1605  // result, e.g.1606  //  (mul sxtw:x, sxtw:y) -> (M2_dpmpyss_s0 (LoReg sxtw:x), (LoReg sxtw:y))1607 1608  if (N.getValueType() != MVT::i64)1609    return false;1610  unsigned Opc = N.getOpcode();1611  switch (Opc) {1612    case ISD::SIGN_EXTEND:1613    case ISD::SIGN_EXTEND_INREG: {1614      // sext_inreg has the source type as a separate operand.1615      EVT T = Opc == ISD::SIGN_EXTEND1616                ? N.getOperand(0).getValueType()1617                : cast<VTSDNode>(N.getOperand(1))->getVT();1618      unsigned SW = T.getSizeInBits();1619      if (SW == 32)1620        R = N.getOperand(0);1621      else if (SW < 32)1622        R = N;1623      else1624        return false;1625      break;1626    }1627    case ISD::LOAD: {1628      LoadSDNode *L = cast<LoadSDNode>(N);1629      if (L->getExtensionType() != ISD::SEXTLOAD)1630        return false;1631      // All extending loads extend to i32, so even if the value in1632      // memory is shorter than 32 bits, it will be i32 after the load.1633      if (L->getMemoryVT().getSizeInBits() > 32)1634        return false;1635      R = N;1636      break;1637    }1638    case ISD::SRA: {1639      auto *S = dyn_cast<ConstantSDNode>(N.getOperand(1));1640      if (!S || S->getZExtValue() != 32)1641        return false;1642      R = N;1643      break;1644    }1645    case ISD::AssertSext: {1646      EVT T = cast<VTSDNode>(N.getOperand(1))->getVT();1647      if (T.getSizeInBits() == 32)1648        R = N.getOperand(0);1649      else1650        return false;1651      break;1652    }1653 1654    default:1655      return false;1656  }1657  EVT RT = R.getValueType();1658  if (RT == MVT::i64)1659    return true;1660  assert(RT == MVT::i32);1661  // This is only to produce a value of type i64. Do not rely on the1662  // high bits produced by this.1663  const SDLoc &dl(N);1664  SDValue Ops[] = {1665    CurDAG->getTargetConstant(Hexagon::DoubleRegsRegClassID, dl, MVT::i32),1666    R, CurDAG->getTargetConstant(Hexagon::isub_hi, dl, MVT::i32),1667    R, CurDAG->getTargetConstant(Hexagon::isub_lo, dl, MVT::i32)1668  };1669  SDNode *T = CurDAG->getMachineNode(TargetOpcode::REG_SEQUENCE, dl,1670                                     MVT::i64, Ops);1671  R = SDValue(T, 0);1672  return true;1673}1674 1675bool HexagonDAGToDAGISel::keepsLowBits(const SDValue &Val, unsigned NumBits,1676      SDValue &Src) {1677  unsigned Opc = Val.getOpcode();1678  switch (Opc) {1679  case ISD::SIGN_EXTEND:1680  case ISD::ZERO_EXTEND:1681  case ISD::ANY_EXTEND: {1682    const SDValue &Op0 = Val.getOperand(0);1683    EVT T = Op0.getValueType();1684    if (T.isInteger() && T.getSizeInBits() == NumBits) {1685      Src = Op0;1686      return true;1687    }1688    break;1689  }1690  case ISD::SIGN_EXTEND_INREG:1691  case ISD::AssertSext:1692  case ISD::AssertZext:1693    if (Val.getOperand(0).getValueType().isInteger()) {1694      VTSDNode *T = cast<VTSDNode>(Val.getOperand(1));1695      if (T->getVT().getSizeInBits() == NumBits) {1696        Src = Val.getOperand(0);1697        return true;1698      }1699    }1700    break;1701  case ISD::AND: {1702    // Check if this is an AND with NumBits of lower bits set to 1.1703    uint64_t Mask = (1ULL << NumBits) - 1;1704    if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Val.getOperand(0))) {1705      if (C->getZExtValue() == Mask) {1706        Src = Val.getOperand(1);1707        return true;1708      }1709    }1710    if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Val.getOperand(1))) {1711      if (C->getZExtValue() == Mask) {1712        Src = Val.getOperand(0);1713        return true;1714      }1715    }1716    break;1717  }1718  case ISD::OR:1719  case ISD::XOR: {1720    // OR/XOR with the lower NumBits bits set to 0.1721    uint64_t Mask = (1ULL << NumBits) - 1;1722    if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Val.getOperand(0))) {1723      if ((C->getZExtValue() & Mask) == 0) {1724        Src = Val.getOperand(1);1725        return true;1726      }1727    }1728    if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Val.getOperand(1))) {1729      if ((C->getZExtValue() & Mask) == 0) {1730        Src = Val.getOperand(0);1731        return true;1732      }1733    }1734    break;1735  }1736  default:1737    break;1738  }1739  return false;1740}1741 1742bool HexagonDAGToDAGISel::isAlignedMemNode(const MemSDNode *N) const {1743  return N->getAlign().value() >= N->getMemoryVT().getStoreSize();1744}1745 1746bool HexagonDAGToDAGISel::isSmallStackStore(const StoreSDNode *N) const {1747  unsigned StackSize = MF->getFrameInfo().estimateStackSize(*MF);1748  switch (N->getMemoryVT().getStoreSize()) {1749    case 1:1750      return StackSize <= 56;   // 1*2^6 - 81751    case 2:1752      return StackSize <= 120;  // 2*2^6 - 81753    case 4:1754      return StackSize <= 248;  // 4*2^6 - 81755    default:1756      return false;1757  }1758}1759 1760// Return true when the given node fits in a positive half word.1761bool HexagonDAGToDAGISel::isPositiveHalfWord(const SDNode *N) const {1762  if (const ConstantSDNode *CN = dyn_cast<const ConstantSDNode>(N)) {1763    int64_t V = CN->getSExtValue();1764    return V > 0 && isInt<16>(V);1765  }1766  if (N->getOpcode() == ISD::SIGN_EXTEND_INREG) {1767    const VTSDNode *VN = dyn_cast<const VTSDNode>(N->getOperand(1));1768    return VN->getVT().getSizeInBits() <= 16;1769  }1770  return false;1771}1772 1773bool HexagonDAGToDAGISel::hasOneUse(const SDNode *N) const {1774  return !CheckSingleUse || N->hasOneUse();1775}1776 1777////////////////////////////////////////////////////////////////////////////////1778// Rebalancing of address calculation trees1779 1780static bool isOpcodeHandled(const SDNode *N) {1781  switch (N->getOpcode()) {1782    case ISD::ADD:1783    case ISD::MUL:1784      return true;1785    case ISD::SHL:1786      // We only handle constant shifts because these can be easily flattened1787      // into multiplications by 2^Op1.1788      return isa<ConstantSDNode>(N->getOperand(1).getNode());1789    default:1790      return false;1791  }1792}1793 1794/// Return the weight of an SDNode1795int HexagonDAGToDAGISel::getWeight(SDNode *N) {1796  if (!isOpcodeHandled(N))1797    return 1;1798  assert(RootWeights.count(N) && "Cannot get weight of unseen root!");1799  assert(RootWeights[N] != -1 && "Cannot get weight of unvisited root!");1800  assert(RootWeights[N] != -2 && "Cannot get weight of RAWU'd root!");1801  return RootWeights[N];1802}1803 1804int HexagonDAGToDAGISel::getHeight(SDNode *N) {1805  if (!isOpcodeHandled(N))1806    return 0;1807  assert(RootWeights.count(N) && RootWeights[N] >= 0 &&1808      "Cannot query height of unvisited/RAUW'd node!");1809  return RootHeights[N];1810}1811 1812namespace {1813struct WeightedLeaf {1814  SDValue Value;1815  int Weight;1816  int InsertionOrder;1817 1818  WeightedLeaf() = default;1819 1820  WeightedLeaf(SDValue Value, int Weight, int InsertionOrder) :1821    Value(Value), Weight(Weight), InsertionOrder(InsertionOrder) {1822    assert(Weight >= 0 && "Weight must be >= 0");1823  }1824 1825  static bool Compare(const WeightedLeaf &A, const WeightedLeaf &B) {1826    assert(A.Value.getNode() && B.Value.getNode());1827    return A.Weight == B.Weight ?1828            (A.InsertionOrder > B.InsertionOrder) :1829            (A.Weight > B.Weight);1830  }1831};1832 1833/// A specialized priority queue for WeigthedLeaves. It automatically folds1834/// constants and allows removal of non-top elements while maintaining the1835/// priority order.1836class LeafPrioQueue {1837  SmallVector<WeightedLeaf, 8> Q;1838  bool HaveConst;1839  WeightedLeaf ConstElt;1840  unsigned Opcode;1841 1842public:1843  bool empty() {1844    return (!HaveConst && Q.empty());1845  }1846 1847  size_t size() {1848    return Q.size() + HaveConst;1849  }1850 1851  bool hasConst() {1852    return HaveConst;1853  }1854 1855  const WeightedLeaf &top() {1856    if (HaveConst)1857      return ConstElt;1858    return Q.front();1859  }1860 1861  WeightedLeaf pop() {1862    if (HaveConst) {1863      HaveConst = false;1864      return ConstElt;1865    }1866    std::pop_heap(Q.begin(), Q.end(), WeightedLeaf::Compare);1867    return Q.pop_back_val();1868  }1869 1870  void push(WeightedLeaf L, bool SeparateConst=true) {1871    if (!HaveConst && SeparateConst && isa<ConstantSDNode>(L.Value)) {1872      if (Opcode == ISD::MUL &&1873          cast<ConstantSDNode>(L.Value)->getSExtValue() == 1)1874        return;1875      if (Opcode == ISD::ADD &&1876          cast<ConstantSDNode>(L.Value)->getSExtValue() == 0)1877        return;1878 1879      HaveConst = true;1880      ConstElt = L;1881    } else {1882      Q.push_back(L);1883      std::push_heap(Q.begin(), Q.end(), WeightedLeaf::Compare);1884    }1885  }1886 1887  /// Push L to the bottom of the queue regardless of its weight. If L is1888  /// constant, it will not be folded with other constants in the queue.1889  void pushToBottom(WeightedLeaf L) {1890    L.Weight = 1000;1891    push(L, false);1892  }1893 1894  /// Search for a SHL(x, [<=MaxAmount]) subtree in the queue, return the one of1895  /// lowest weight and remove it from the queue.1896  WeightedLeaf findSHL(uint64_t MaxAmount);1897 1898  WeightedLeaf findMULbyConst();1899 1900  LeafPrioQueue(unsigned Opcode) :1901    HaveConst(false), Opcode(Opcode) { }1902};1903} // end anonymous namespace1904 1905WeightedLeaf LeafPrioQueue::findSHL(uint64_t MaxAmount) {1906  int ResultPos;1907  WeightedLeaf Result;1908 1909  for (int Pos = 0, End = Q.size(); Pos != End; ++Pos) {1910    const WeightedLeaf &L = Q[Pos];1911    const SDValue &Val = L.Value;1912    if (Val.getOpcode() != ISD::SHL ||1913        !isa<ConstantSDNode>(Val.getOperand(1)) ||1914        Val.getConstantOperandVal(1) > MaxAmount)1915      continue;1916    if (!Result.Value.getNode() || Result.Weight > L.Weight ||1917        (Result.Weight == L.Weight && Result.InsertionOrder > L.InsertionOrder))1918    {1919      Result = L;1920      ResultPos = Pos;1921    }1922  }1923 1924  if (Result.Value.getNode()) {1925    Q.erase(&Q[ResultPos]);1926    std::make_heap(Q.begin(), Q.end(), WeightedLeaf::Compare);1927  }1928 1929  return Result;1930}1931 1932WeightedLeaf LeafPrioQueue::findMULbyConst() {1933  int ResultPos;1934  WeightedLeaf Result;1935 1936  for (int Pos = 0, End = Q.size(); Pos != End; ++Pos) {1937    const WeightedLeaf &L = Q[Pos];1938    const SDValue &Val = L.Value;1939    if (Val.getOpcode() != ISD::MUL ||1940        !isa<ConstantSDNode>(Val.getOperand(1)) ||1941        Val.getConstantOperandVal(1) > 127)1942      continue;1943    if (!Result.Value.getNode() || Result.Weight > L.Weight ||1944        (Result.Weight == L.Weight && Result.InsertionOrder > L.InsertionOrder))1945    {1946      Result = L;1947      ResultPos = Pos;1948    }1949  }1950 1951  if (Result.Value.getNode()) {1952    Q.erase(&Q[ResultPos]);1953    std::make_heap(Q.begin(), Q.end(), WeightedLeaf::Compare);1954  }1955 1956  return Result;1957}1958 1959SDValue HexagonDAGToDAGISel::getMultiplierForSHL(SDNode *N) {1960  uint64_t MulFactor = 1ull << N->getConstantOperandVal(1);1961  return CurDAG->getConstant(MulFactor, SDLoc(N),1962                             N->getOperand(1).getValueType());1963}1964 1965/// @returns the value x for which 2^x is a factor of Val1966static unsigned getPowerOf2Factor(SDValue Val) {1967  if (Val.getOpcode() == ISD::MUL) {1968    unsigned MaxFactor = 0;1969    for (int i = 0; i < 2; ++i) {1970      ConstantSDNode *C = dyn_cast<ConstantSDNode>(Val.getOperand(i));1971      if (!C)1972        continue;1973      const APInt &CInt = C->getAPIntValue();1974      if (CInt.getBoolValue())1975        MaxFactor = CInt.countr_zero();1976    }1977    return MaxFactor;1978  }1979  if (Val.getOpcode() == ISD::SHL) {1980    if (!isa<ConstantSDNode>(Val.getOperand(1).getNode()))1981      return 0;1982    return (unsigned) Val.getConstantOperandVal(1);1983  }1984 1985  return 0;1986}1987 1988/// @returns true if V>>Amount will eliminate V's operation on its child1989static bool willShiftRightEliminate(SDValue V, unsigned Amount) {1990  if (V.getOpcode() == ISD::MUL) {1991    SDValue Ops[] = { V.getOperand(0), V.getOperand(1) };1992    for (int i = 0; i < 2; ++i)1993      if (isa<ConstantSDNode>(Ops[i].getNode()) &&1994          V.getConstantOperandVal(i) % (1ULL << Amount) == 0) {1995        uint64_t NewConst = V.getConstantOperandVal(i) >> Amount;1996        return (NewConst == 1);1997      }1998  } else if (V.getOpcode() == ISD::SHL) {1999    return (Amount == V.getConstantOperandVal(1));2000  }2001 2002  return false;2003}2004 2005SDValue HexagonDAGToDAGISel::factorOutPowerOf2(SDValue V, unsigned Power) {2006  SDValue Ops[] = { V.getOperand(0), V.getOperand(1) };2007  if (V.getOpcode() == ISD::MUL) {2008    for (int i=0; i < 2; ++i) {2009      if (isa<ConstantSDNode>(Ops[i].getNode()) &&2010          V.getConstantOperandVal(i) % ((uint64_t)1 << Power) == 0) {2011        uint64_t NewConst = V.getConstantOperandVal(i) >> Power;2012        if (NewConst == 1)2013          return Ops[!i];2014        Ops[i] = CurDAG->getConstant(NewConst,2015                                     SDLoc(V), V.getValueType());2016        break;2017      }2018    }2019  } else if (V.getOpcode() == ISD::SHL) {2020    uint64_t ShiftAmount = V.getConstantOperandVal(1);2021    if (ShiftAmount == Power)2022      return Ops[0];2023    Ops[1] = CurDAG->getConstant(ShiftAmount - Power,2024                                 SDLoc(V), V.getValueType());2025  }2026 2027  return CurDAG->getNode(V.getOpcode(), SDLoc(V), V.getValueType(), Ops);2028}2029 2030static bool isTargetConstant(const SDValue &V) {2031  return V.getOpcode() == HexagonISD::CONST32 ||2032         V.getOpcode() == HexagonISD::CONST32_GP;2033}2034 2035unsigned HexagonDAGToDAGISel::getUsesInFunction(const Value *V) {2036  auto [It, Inserted] = GAUsesInFunction.try_emplace(V);2037  if (!Inserted)2038    return It->second;2039 2040  unsigned Result = 0;2041  const Function &CurF = CurDAG->getMachineFunction().getFunction();2042  for (const User *U : V->users()) {2043    if (isa<Instruction>(U) &&2044        cast<Instruction>(U)->getParent()->getParent() == &CurF)2045      ++Result;2046  }2047 2048  It->second = Result;2049 2050  return Result;2051}2052 2053/// Note - After calling this, N may be dead. It may have been replaced by a2054/// new node, so always use the returned value in place of N.2055///2056/// @returns The SDValue taking the place of N (which could be N if it is2057/// unchanged)2058SDValue HexagonDAGToDAGISel::balanceSubTree(SDNode *N, bool TopLevel) {2059  assert(RootWeights.count(N) && "Cannot balance non-root node.");2060  assert(RootWeights[N] != -2 && "This node was RAUW'd!");2061  assert(!TopLevel || N->getOpcode() == ISD::ADD);2062 2063  // Return early if this node was already visited2064  if (RootWeights[N] != -1)2065    return SDValue(N, 0);2066 2067  assert(isOpcodeHandled(N));2068 2069  SDValue Op0 = N->getOperand(0);2070  SDValue Op1 = N->getOperand(1);2071 2072  // Return early if the operands will remain unchanged or are all roots2073  if ((!isOpcodeHandled(Op0.getNode()) || RootWeights.count(Op0.getNode())) &&2074      (!isOpcodeHandled(Op1.getNode()) || RootWeights.count(Op1.getNode()))) {2075    SDNode *Op0N = Op0.getNode();2076    int Weight;2077    if (isOpcodeHandled(Op0N) && RootWeights[Op0N] == -1) {2078      Weight = getWeight(balanceSubTree(Op0N).getNode());2079      // Weight = calculateWeight(Op0N);2080    } else2081      Weight = getWeight(Op0N);2082 2083    SDNode *Op1N = N->getOperand(1).getNode(); // Op1 may have been RAUWd2084    if (isOpcodeHandled(Op1N) && RootWeights[Op1N] == -1) {2085      Weight += getWeight(balanceSubTree(Op1N).getNode());2086      // Weight += calculateWeight(Op1N);2087    } else2088      Weight += getWeight(Op1N);2089 2090    RootWeights[N] = Weight;2091    RootHeights[N] = std::max(getHeight(N->getOperand(0).getNode()),2092                              getHeight(N->getOperand(1).getNode())) + 1;2093 2094    LLVM_DEBUG(dbgs() << "--> No need to balance root (Weight=" << Weight2095                      << " Height=" << RootHeights[N] << "): ");2096    LLVM_DEBUG(N->dump(CurDAG));2097 2098    return SDValue(N, 0);2099  }2100 2101  LLVM_DEBUG(dbgs() << "** Balancing root node: ");2102  LLVM_DEBUG(N->dump(CurDAG));2103 2104  unsigned NOpcode = N->getOpcode();2105 2106  LeafPrioQueue Leaves(NOpcode);2107  SmallVector<SDValue, 4> Worklist;2108  Worklist.push_back(SDValue(N, 0));2109 2110  // SHL nodes will be converted to MUL nodes2111  if (NOpcode == ISD::SHL)2112    NOpcode = ISD::MUL;2113 2114  bool CanFactorize = false;2115  WeightedLeaf Mul1, Mul2;2116  unsigned MaxPowerOf2 = 0;2117  WeightedLeaf GA;2118 2119  // Do not try to factor out a shift if there is already a shift at the tip of2120  // the tree.2121  bool HaveTopLevelShift = false;2122  if (TopLevel &&2123      ((isOpcodeHandled(Op0.getNode()) && Op0.getOpcode() == ISD::SHL &&2124                        Op0.getConstantOperandVal(1) < 4) ||2125       (isOpcodeHandled(Op1.getNode()) && Op1.getOpcode() == ISD::SHL &&2126                        Op1.getConstantOperandVal(1) < 4)))2127    HaveTopLevelShift = true;2128 2129  // Flatten the subtree into an ordered list of leaves; at the same time2130  // determine whether the tree is already balanced.2131  int InsertionOrder = 0;2132  SmallDenseMap<SDValue, int> NodeHeights;2133  bool Imbalanced = false;2134  int CurrentWeight = 0;2135  while (!Worklist.empty()) {2136    SDValue Child = Worklist.pop_back_val();2137 2138    if (Child.getNode() != N && RootWeights.count(Child.getNode())) {2139      // CASE 1: Child is a root note2140 2141      int Weight = RootWeights[Child.getNode()];2142      if (Weight == -1) {2143        Child = balanceSubTree(Child.getNode());2144        // calculateWeight(Child.getNode());2145        Weight = getWeight(Child.getNode());2146      } else if (Weight == -2) {2147        // Whoops, this node was RAUWd by one of the balanceSubTree calls we2148        // made. Our worklist isn't up to date anymore.2149        // Restart the whole process.2150        LLVM_DEBUG(dbgs() << "--> Subtree was RAUWd. Restarting...\n");2151        return balanceSubTree(N, TopLevel);2152      }2153 2154      NodeHeights[Child] = 1;2155      CurrentWeight += Weight;2156 2157      unsigned PowerOf2;2158      if (TopLevel && !CanFactorize && !HaveTopLevelShift &&2159          (Child.getOpcode() == ISD::MUL || Child.getOpcode() == ISD::SHL) &&2160          Child.hasOneUse() && (PowerOf2 = getPowerOf2Factor(Child))) {2161        // Try to identify two factorizable MUL/SHL children greedily. Leave2162        // them out of the priority queue for now so we can deal with them2163        // after.2164        if (!Mul1.Value.getNode()) {2165          Mul1 = WeightedLeaf(Child, Weight, InsertionOrder++);2166          MaxPowerOf2 = PowerOf2;2167        } else {2168          Mul2 = WeightedLeaf(Child, Weight, InsertionOrder++);2169          MaxPowerOf2 = std::min(MaxPowerOf2, PowerOf2);2170 2171          // Our addressing modes can only shift by a maximum of 32172          if (MaxPowerOf2 > 3)2173            MaxPowerOf2 = 3;2174 2175          CanFactorize = true;2176        }2177      } else2178        Leaves.push(WeightedLeaf(Child, Weight, InsertionOrder++));2179    } else if (!isOpcodeHandled(Child.getNode())) {2180      // CASE 2: Child is an unhandled kind of node (e.g. constant)2181      int Weight = getWeight(Child.getNode());2182 2183      NodeHeights[Child] = getHeight(Child.getNode());2184      CurrentWeight += Weight;2185 2186      if (isTargetConstant(Child) && !GA.Value.getNode())2187        GA = WeightedLeaf(Child, Weight, InsertionOrder++);2188      else2189        Leaves.push(WeightedLeaf(Child, Weight, InsertionOrder++));2190    } else {2191      // CASE 3: Child is a subtree of same opcode2192      // Visit children first, then flatten.2193      unsigned ChildOpcode = Child.getOpcode();2194      assert(ChildOpcode == NOpcode ||2195             (NOpcode == ISD::MUL && ChildOpcode == ISD::SHL));2196 2197      // Convert SHL to MUL2198      SDValue Op1;2199      if (ChildOpcode == ISD::SHL)2200        Op1 = getMultiplierForSHL(Child.getNode());2201      else2202        Op1 = Child->getOperand(1);2203 2204      if (!NodeHeights.count(Op1) || !NodeHeights.count(Child->getOperand(0))) {2205        assert(!NodeHeights.count(Child) && "Parent visited before children?");2206        // Visit children first, then re-visit this node2207        Worklist.push_back(Child);2208        Worklist.push_back(Op1);2209        Worklist.push_back(Child->getOperand(0));2210      } else {2211        // Back at this node after visiting the children2212        if (std::abs(NodeHeights[Op1] - NodeHeights[Child->getOperand(0)]) > 1)2213          Imbalanced = true;2214 2215        NodeHeights[Child] = std::max(NodeHeights[Op1],2216                                      NodeHeights[Child->getOperand(0)]) + 1;2217      }2218    }2219  }2220 2221  LLVM_DEBUG(dbgs() << "--> Current height=" << NodeHeights[SDValue(N, 0)]2222                    << " weight=" << CurrentWeight2223                    << " imbalanced=" << Imbalanced << "\n");2224 2225  // Transform MUL(x, C * 2^Y) + SHL(z, Y) -> SHL(ADD(MUL(x, C), z), Y)2226  //  This factors out a shift in order to match memw(a<<Y+b).2227  if (CanFactorize && (willShiftRightEliminate(Mul1.Value, MaxPowerOf2) ||2228                       willShiftRightEliminate(Mul2.Value, MaxPowerOf2))) {2229    LLVM_DEBUG(dbgs() << "--> Found common factor for two MUL children!\n");2230    int Weight = Mul1.Weight + Mul2.Weight;2231    int Height = std::max(NodeHeights[Mul1.Value], NodeHeights[Mul2.Value]) + 1;2232    SDValue Mul1Factored = factorOutPowerOf2(Mul1.Value, MaxPowerOf2);2233    SDValue Mul2Factored = factorOutPowerOf2(Mul2.Value, MaxPowerOf2);2234    SDValue Sum = CurDAG->getNode(ISD::ADD, SDLoc(N), Mul1.Value.getValueType(),2235                                  Mul1Factored, Mul2Factored);2236    SDValue Const = CurDAG->getConstant(MaxPowerOf2, SDLoc(N),2237                                        Mul1.Value.getValueType());2238    SDValue New = CurDAG->getNode(ISD::SHL, SDLoc(N), Mul1.Value.getValueType(),2239                                  Sum, Const);2240    NodeHeights[New] = Height;2241    Leaves.push(WeightedLeaf(New, Weight, Mul1.InsertionOrder));2242  } else if (Mul1.Value.getNode()) {2243    // We failed to factorize two MULs, so now the Muls are left outside the2244    // queue... add them back.2245    Leaves.push(Mul1);2246    if (Mul2.Value.getNode())2247      Leaves.push(Mul2);2248    CanFactorize = false;2249  }2250 2251  // Combine GA + Constant -> GA+Offset, but only if GA is not used elsewhere2252  // and the root node itself is not used more than twice. This reduces the2253  // amount of additional constant extenders introduced by this optimization.2254  bool CombinedGA = false;2255  if (NOpcode == ISD::ADD && GA.Value.getNode() && Leaves.hasConst() &&2256      GA.Value.hasOneUse() && N->use_size() < 3) {2257    GlobalAddressSDNode *GANode =2258      cast<GlobalAddressSDNode>(GA.Value.getOperand(0));2259    ConstantSDNode *Offset = cast<ConstantSDNode>(Leaves.top().Value);2260 2261    if (getUsesInFunction(GANode->getGlobal()) == 1 && Offset->hasOneUse() &&2262        getTargetLowering()->isOffsetFoldingLegal(GANode)) {2263      LLVM_DEBUG(dbgs() << "--> Combining GA and offset ("2264                        << Offset->getSExtValue() << "): ");2265      LLVM_DEBUG(GANode->dump(CurDAG));2266 2267      SDValue NewTGA =2268        CurDAG->getTargetGlobalAddress(GANode->getGlobal(), SDLoc(GA.Value),2269            GANode->getValueType(0),2270            GANode->getOffset() + (uint64_t)Offset->getSExtValue());2271      GA.Value = CurDAG->getNode(GA.Value.getOpcode(), SDLoc(GA.Value),2272          GA.Value.getValueType(), NewTGA);2273      GA.Weight += Leaves.top().Weight;2274 2275      NodeHeights[GA.Value] = getHeight(GA.Value.getNode());2276      CombinedGA = true;2277 2278      Leaves.pop(); // Remove the offset constant from the queue2279    }2280  }2281 2282  if ((RebalanceOnlyForOptimizations && !CanFactorize && !CombinedGA) ||2283      (RebalanceOnlyImbalancedTrees && !Imbalanced)) {2284    RootWeights[N] = CurrentWeight;2285    RootHeights[N] = NodeHeights[SDValue(N, 0)];2286 2287    return SDValue(N, 0);2288  }2289 2290  // Combine GA + SHL(x, C<=31) so we will match Rx=add(#u8,asl(Rx,#U5))2291  if (NOpcode == ISD::ADD && GA.Value.getNode()) {2292    WeightedLeaf SHL = Leaves.findSHL(31);2293    if (SHL.Value.getNode()) {2294      int Height = std::max(NodeHeights[GA.Value], NodeHeights[SHL.Value]) + 1;2295      GA.Value = CurDAG->getNode(ISD::ADD, SDLoc(GA.Value),2296                                 GA.Value.getValueType(),2297                                 GA.Value, SHL.Value);2298      GA.Weight = SHL.Weight; // Specifically ignore the GA weight here2299      NodeHeights[GA.Value] = Height;2300    }2301  }2302 2303  if (GA.Value.getNode())2304    Leaves.push(GA);2305 2306  // If this is the top level and we haven't factored out a shift, we should try2307  // to move a constant to the bottom to match addressing modes like memw(rX+C)2308  if (TopLevel && !CanFactorize && Leaves.hasConst()) {2309    LLVM_DEBUG(dbgs() << "--> Pushing constant to tip of tree.");2310    Leaves.pushToBottom(Leaves.pop());2311  }2312 2313  const DataLayout &DL = CurDAG->getDataLayout();2314  const TargetLowering &TLI = *getTargetLowering();2315 2316  // Rebuild the tree using Huffman's algorithm2317  while (Leaves.size() > 1) {2318    WeightedLeaf L0 = Leaves.pop();2319 2320    // See whether we can grab a MUL to form an add(Rx,mpyi(Ry,#u6)),2321    // otherwise just get the next leaf2322    WeightedLeaf L1 = Leaves.findMULbyConst();2323    if (!L1.Value.getNode())2324      L1 = Leaves.pop();2325 2326    assert(L0.Weight <= L1.Weight && "Priority queue is broken!");2327 2328    SDValue V0 = L0.Value;2329    int V0Weight = L0.Weight;2330    SDValue V1 = L1.Value;2331    int V1Weight = L1.Weight;2332 2333    // Make sure that none of these nodes have been RAUW'd2334    if ((RootWeights.count(V0.getNode()) && RootWeights[V0.getNode()] == -2) ||2335        (RootWeights.count(V1.getNode()) && RootWeights[V1.getNode()] == -2)) {2336      LLVM_DEBUG(dbgs() << "--> Subtree was RAUWd. Restarting...\n");2337      return balanceSubTree(N, TopLevel);2338    }2339 2340    ConstantSDNode *V0C = dyn_cast<ConstantSDNode>(V0);2341    ConstantSDNode *V1C = dyn_cast<ConstantSDNode>(V1);2342    EVT VT = N->getValueType(0);2343    SDValue NewNode;2344 2345    if (V0C && !V1C) {2346      std::swap(V0, V1);2347      std::swap(V0C, V1C);2348    }2349 2350    // Calculate height of this node2351    assert(NodeHeights.count(V0) && NodeHeights.count(V1) &&2352           "Children must have been visited before re-combining them!");2353    int Height = std::max(NodeHeights[V0], NodeHeights[V1]) + 1;2354 2355    // Rebuild this node (and restore SHL from MUL if needed)2356    if (V1C && NOpcode == ISD::MUL && V1C->getAPIntValue().isPowerOf2())2357      NewNode = CurDAG->getNode(2358          ISD::SHL, SDLoc(V0), VT, V0,2359          CurDAG->getConstant(2360              V1C->getAPIntValue().logBase2(), SDLoc(N),2361              TLI.getScalarShiftAmountTy(DL, V0.getValueType())));2362    else2363      NewNode = CurDAG->getNode(NOpcode, SDLoc(N), VT, V0, V1);2364 2365    NodeHeights[NewNode] = Height;2366 2367    int Weight = V0Weight + V1Weight;2368    Leaves.push(WeightedLeaf(NewNode, Weight, L0.InsertionOrder));2369 2370    LLVM_DEBUG(dbgs() << "--> Built new node (Weight=" << Weight2371                      << ",Height=" << Height << "):\n");2372    LLVM_DEBUG(NewNode.dump());2373  }2374 2375  assert(Leaves.size() == 1);2376  SDValue NewRoot = Leaves.top().Value;2377 2378  assert(NodeHeights.count(NewRoot));2379  int Height = NodeHeights[NewRoot];2380 2381  // Restore SHL if we earlier converted it to a MUL2382  if (NewRoot.getOpcode() == ISD::MUL) {2383    ConstantSDNode *V1C = dyn_cast<ConstantSDNode>(NewRoot.getOperand(1));2384    if (V1C && V1C->getAPIntValue().isPowerOf2()) {2385      EVT VT = NewRoot.getValueType();2386      SDValue V0 = NewRoot.getOperand(0);2387      NewRoot = CurDAG->getNode(2388          ISD::SHL, SDLoc(NewRoot), VT, V0,2389          CurDAG->getConstant(2390              V1C->getAPIntValue().logBase2(), SDLoc(NewRoot),2391              TLI.getScalarShiftAmountTy(DL, V0.getValueType())));2392    }2393  }2394 2395  if (N != NewRoot.getNode()) {2396    LLVM_DEBUG(dbgs() << "--> Root is now: ");2397    LLVM_DEBUG(NewRoot.dump());2398 2399    // Replace all uses of old root by new root2400    CurDAG->ReplaceAllUsesWith(N, NewRoot.getNode());2401    // Mark that we have RAUW'd N2402    RootWeights[N] = -2;2403  } else {2404    LLVM_DEBUG(dbgs() << "--> Root unchanged.\n");2405  }2406 2407  RootWeights[NewRoot.getNode()] = Leaves.top().Weight;2408  RootHeights[NewRoot.getNode()] = Height;2409 2410  return NewRoot;2411}2412 2413void HexagonDAGToDAGISel::rebalanceAddressTrees() {2414  for (SDNode &Node : llvm::make_early_inc_range(CurDAG->allnodes())) {2415    SDNode *N = &Node;2416    if (N->getOpcode() != ISD::LOAD && N->getOpcode() != ISD::STORE)2417      continue;2418 2419    SDValue BasePtr = cast<MemSDNode>(N)->getBasePtr();2420    if (BasePtr.getOpcode() != ISD::ADD)2421      continue;2422 2423    // We've already processed this node2424    if (RootWeights.count(BasePtr.getNode()))2425      continue;2426 2427    LLVM_DEBUG(dbgs() << "** Rebalancing address calculation in node: ");2428    LLVM_DEBUG(N->dump(CurDAG));2429 2430    // FindRoots2431    SmallVector<SDNode *, 4> Worklist;2432 2433    Worklist.push_back(BasePtr.getOperand(0).getNode());2434    Worklist.push_back(BasePtr.getOperand(1).getNode());2435 2436    while (!Worklist.empty()) {2437      SDNode *N = Worklist.pop_back_val();2438      unsigned Opcode = N->getOpcode();2439 2440      if (!isOpcodeHandled(N))2441        continue;2442 2443      Worklist.push_back(N->getOperand(0).getNode());2444      Worklist.push_back(N->getOperand(1).getNode());2445 2446      // Not a root if it has only one use and same opcode as its parent2447      if (N->hasOneUse() && Opcode == N->user_begin()->getOpcode())2448        continue;2449 2450      // This root node has already been processed2451      RootWeights.try_emplace(N, -1);2452    }2453 2454    // Balance node itself2455    RootWeights[BasePtr.getNode()] = -1;2456    SDValue NewBasePtr = balanceSubTree(BasePtr.getNode(), /*TopLevel=*/ true);2457 2458    if (N->getOpcode() == ISD::LOAD)2459      N = CurDAG->UpdateNodeOperands(N, N->getOperand(0),2460            NewBasePtr, N->getOperand(2));2461    else2462      N = CurDAG->UpdateNodeOperands(N, N->getOperand(0), N->getOperand(1),2463            NewBasePtr, N->getOperand(3));2464 2465    LLVM_DEBUG(dbgs() << "--> Final node: ");2466    LLVM_DEBUG(N->dump(CurDAG));2467  }2468 2469  CurDAG->RemoveDeadNodes();2470  GAUsesInFunction.clear();2471  RootHeights.clear();2472  RootWeights.clear();2473}2474