contrib/llvm/lib/Target/Hexagon/HexagonISelDAGToDAG.cpp

   1 //===-- HexagonISelDAGToDAG.cpp - A dag to dag inst selector for Hexagon --===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file defines an instruction selector for the Hexagon target.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  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/Support/CommandLine.h"
  23 #include "llvm/Support/Debug.h"
  24 using namespace llvm;
  25
  26 #define DEBUG_TYPE "hexagon-isel"
  27
  28 static
  29 cl::opt<bool>
  30 EnableAddressRebalancing("isel-rebalance-addr", cl::Hidden, cl::init(true),
  31   cl::desc("Rebalance address calculation trees to improve "
  32           "instruction selection"));
  33
  34 // Rebalance only if this allows e.g. combining a GA with an offset or
  35 // factoring out a shift.
  36 static
  37 cl::opt<bool>
  38 RebalanceOnlyForOptimizations("rebalance-only-opt", cl::Hidden, cl::init(false),
  39   cl::desc("Rebalance address tree only if this allows optimizations"));
  40
  41 static
  42 cl::opt<bool>
  43 RebalanceOnlyImbalancedTrees("rebalance-only-imbal", cl::Hidden,
  44   cl::init(false), cl::desc("Rebalance address tree only if it is imbalanced"));
  45
  46 //===----------------------------------------------------------------------===//
  47 // Instruction Selector Implementation
  48 //===----------------------------------------------------------------------===//
  49
  50 //===--------------------------------------------------------------------===//
  51 /// HexagonDAGToDAGISel - Hexagon specific code to select Hexagon machine
  52 /// instructions for SelectionDAG operations.
  53 ///
  54 namespace {
  55 class HexagonDAGToDAGISel : public SelectionDAGISel {
  56   const HexagonSubtarget *HST;
  57   const HexagonInstrInfo *HII;
  58   const HexagonRegisterInfo *HRI;
  59 public:
  60   explicit HexagonDAGToDAGISel(HexagonTargetMachine &tm,
  61                                CodeGenOpt::Level OptLevel)
  62       : SelectionDAGISel(tm, OptLevel), HST(nullptr), HII(nullptr),
  63         HRI(nullptr) {}
  64
  65   bool runOnMachineFunction(MachineFunction &MF) override {
  66     // Reset the subtarget each time through.
  67     HST = &MF.getSubtarget<HexagonSubtarget>();
  68     HII = HST->getInstrInfo();
  69     HRI = HST->getRegisterInfo();
  70     SelectionDAGISel::runOnMachineFunction(MF);
  71     return true;
  72   }
  73
  74   bool ComplexPatternFuncMutatesDAG() const override {
  75     return true;
  76   }
  77   void PreprocessISelDAG() override;
  78   void EmitFunctionEntryCode() override;
  79
  80   void Select(SDNode *N) override;
  81
  82   // Complex Pattern Selectors.
  83   inline bool SelectAddrGA(SDValue &N, SDValue &R);
  84   inline bool SelectAddrGP(SDValue &N, SDValue &R);
  85   bool SelectGlobalAddress(SDValue &N, SDValue &R, bool UseGP);
  86   bool SelectAddrFI(SDValue &N, SDValue &R);
  87   bool DetectUseSxtw(SDValue &N, SDValue &R);
  88
  89   StringRef getPassName() const override {
  90     return "Hexagon DAG->DAG Pattern Instruction Selection";
  91   }
  92
  93   // Generate a machine instruction node corresponding to the circ/brev
  94   // load intrinsic.
  95   MachineSDNode *LoadInstrForLoadIntrinsic(SDNode *IntN);
  96   // Given the circ/brev load intrinsic and the already generated machine
  97   // instruction, generate the appropriate store (that is a part of the
  98   // intrinsic's functionality).
  99   SDNode *StoreInstrForLoadIntrinsic(MachineSDNode *LoadN, SDNode *IntN);
 100
 101   void SelectFrameIndex(SDNode *N);
 102   /// SelectInlineAsmMemoryOperand - Implement addressing mode selection for
 103   /// inline asm expressions.
 104   bool SelectInlineAsmMemoryOperand(const SDValue &Op,
 105                                     unsigned ConstraintID,
 106                                     std::vector<SDValue> &OutOps) override;
 107   bool tryLoadOfLoadIntrinsic(LoadSDNode *N);
 108   void SelectLoad(SDNode *N);
 109   void SelectIndexedLoad(LoadSDNode *LD, const SDLoc &dl);
 110   void SelectIndexedStore(StoreSDNode *ST, const SDLoc &dl);
 111   void SelectStore(SDNode *N);
 112   void SelectSHL(SDNode *N);
 113   void SelectZeroExtend(SDNode *N);
 114   void SelectIntrinsicWChain(SDNode *N);
 115   void SelectIntrinsicWOChain(SDNode *N);
 116   void SelectConstant(SDNode *N);
 117   void SelectConstantFP(SDNode *N);
 118   void SelectBitcast(SDNode *N);
 119
 120   // Include the pieces autogenerated from the target description.
 121   #include "HexagonGenDAGISel.inc"
 122
 123 private:
 124   bool keepsLowBits(const SDValue &Val, unsigned NumBits, SDValue &Src);
 125   bool isOrEquivalentToAdd(const SDNode *N) const;
 126   bool isAlignedMemNode(const MemSDNode *N) const;
 127   bool isSmallStackStore(const StoreSDNode *N) const;
 128   bool isPositiveHalfWord(const SDNode *N) const;
 129
 130   // DAG preprocessing functions.
 131   void ppSimplifyOrSelect0(std::vector<SDNode*> &&Nodes);
 132   void ppAddrReorderAddShl(std::vector<SDNode*> &&Nodes);
 133   void ppAddrRewriteAndSrl(std::vector<SDNode*> &&Nodes);
 134   void ppHoistZextI1(std::vector<SDNode*> &&Nodes);
 135
 136   SmallDenseMap<SDNode *,int> RootWeights;
 137   SmallDenseMap<SDNode *,int> RootHeights;
 138   SmallDenseMap<const Value *,int> GAUsesInFunction;
 139   int getWeight(SDNode *N);
 140   int getHeight(SDNode *N);
 141   SDValue getMultiplierForSHL(SDNode *N);
 142   SDValue factorOutPowerOf2(SDValue V, unsigned Power);
 143   unsigned getUsesInFunction(const Value *V);
 144   SDValue balanceSubTree(SDNode *N, bool Factorize = false);
 145   void rebalanceAddressTrees();
 146 }; // end HexagonDAGToDAGISel
 147 }  // end anonymous namespace
 148
 149
 150 /// createHexagonISelDag - This pass converts a legalized DAG into a
 151 /// Hexagon-specific DAG, ready for instruction scheduling.
 152 ///
 153 namespace llvm {
 154 FunctionPass *createHexagonISelDag(HexagonTargetMachine &TM,
 155                                    CodeGenOpt::Level OptLevel) {
 156   return new HexagonDAGToDAGISel(TM, OptLevel);
 157 }
 158 }
 159
 160 // Intrinsics that return a a predicate.
 161 static bool doesIntrinsicReturnPredicate(unsigned ID) {
 162   switch (ID) {
 163     default:
 164       return false;
 165     case Intrinsic::hexagon_C2_cmpeq:
 166     case Intrinsic::hexagon_C2_cmpgt:
 167     case Intrinsic::hexagon_C2_cmpgtu:
 168     case Intrinsic::hexagon_C2_cmpgtup:
 169     case Intrinsic::hexagon_C2_cmpgtp:
 170     case Intrinsic::hexagon_C2_cmpeqp:
 171     case Intrinsic::hexagon_C2_bitsset:
 172     case Intrinsic::hexagon_C2_bitsclr:
 173     case Intrinsic::hexagon_C2_cmpeqi:
 174     case Intrinsic::hexagon_C2_cmpgti:
 175     case Intrinsic::hexagon_C2_cmpgtui:
 176     case Intrinsic::hexagon_C2_cmpgei:
 177     case Intrinsic::hexagon_C2_cmpgeui:
 178     case Intrinsic::hexagon_C2_cmplt:
 179     case Intrinsic::hexagon_C2_cmpltu:
 180     case Intrinsic::hexagon_C2_bitsclri:
 181     case Intrinsic::hexagon_C2_and:
 182     case Intrinsic::hexagon_C2_or:
 183     case Intrinsic::hexagon_C2_xor:
 184     case Intrinsic::hexagon_C2_andn:
 185     case Intrinsic::hexagon_C2_not:
 186     case Intrinsic::hexagon_C2_orn:
 187     case Intrinsic::hexagon_C2_pxfer_map:
 188     case Intrinsic::hexagon_C2_any8:
 189     case Intrinsic::hexagon_C2_all8:
 190     case Intrinsic::hexagon_A2_vcmpbeq:
 191     case Intrinsic::hexagon_A2_vcmpbgtu:
 192     case Intrinsic::hexagon_A2_vcmpheq:
 193     case Intrinsic::hexagon_A2_vcmphgt:
 194     case Intrinsic::hexagon_A2_vcmphgtu:
 195     case Intrinsic::hexagon_A2_vcmpweq:
 196     case Intrinsic::hexagon_A2_vcmpwgt:
 197     case Intrinsic::hexagon_A2_vcmpwgtu:
 198     case Intrinsic::hexagon_C2_tfrrp:
 199     case Intrinsic::hexagon_S2_tstbit_i:
 200     case Intrinsic::hexagon_S2_tstbit_r:
 201       return true;
 202   }
 203 }
 204
 205 void HexagonDAGToDAGISel::SelectIndexedLoad(LoadSDNode *LD, const SDLoc &dl) {
 206   SDValue Chain = LD->getChain();
 207   SDValue Base = LD->getBasePtr();
 208   SDValue Offset = LD->getOffset();
 209   int32_t Inc = cast<ConstantSDNode>(Offset.getNode())->getSExtValue();
 210   EVT LoadedVT = LD->getMemoryVT();
 211   unsigned Opcode = 0;
 212
 213   // Check for zero extended loads. Treat any-extend loads as zero extended
 214   // loads.
 215   ISD::LoadExtType ExtType = LD->getExtensionType();
 216   bool IsZeroExt = (ExtType == ISD::ZEXTLOAD || ExtType == ISD::EXTLOAD);
 217   bool IsValidInc = HII->isValidAutoIncImm(LoadedVT, Inc);
 218
 219   assert(LoadedVT.isSimple());
 220   switch (LoadedVT.getSimpleVT().SimpleTy) {
 221   case MVT::i8:
 222     if (IsZeroExt)
 223       Opcode = IsValidInc ? Hexagon::L2_loadrub_pi : Hexagon::L2_loadrub_io;
 224     else
 225       Opcode = IsValidInc ? Hexagon::L2_loadrb_pi : Hexagon::L2_loadrb_io;
 226     break;
 227   case MVT::i16:
 228     if (IsZeroExt)
 229       Opcode = IsValidInc ? Hexagon::L2_loadruh_pi : Hexagon::L2_loadruh_io;
 230     else
 231       Opcode = IsValidInc ? Hexagon::L2_loadrh_pi : Hexagon::L2_loadrh_io;
 232     break;
 233   case MVT::i32:
 234     Opcode = IsValidInc ? Hexagon::L2_loadri_pi : Hexagon::L2_loadri_io;
 235     break;
 236   case MVT::i64:
 237     Opcode = IsValidInc ? Hexagon::L2_loadrd_pi : Hexagon::L2_loadrd_io;
 238     break;
 239   // 64B
 240   case MVT::v64i8:
 241   case MVT::v32i16:
 242   case MVT::v16i32:
 243   case MVT::v8i64:
 244     if (isAlignedMemNode(LD))
 245       Opcode = IsValidInc ? Hexagon::V6_vL32b_pi : Hexagon::V6_vL32b_ai;
 246     else
 247       Opcode = IsValidInc ? Hexagon::V6_vL32Ub_pi : Hexagon::V6_vL32Ub_ai;
 248     break;
 249   // 128B
 250   case MVT::v128i8:
 251   case MVT::v64i16:
 252   case MVT::v32i32:
 253   case MVT::v16i64:
 254     if (isAlignedMemNode(LD))
 255       Opcode = IsValidInc ? Hexagon::V6_vL32b_pi_128B
 256                           : Hexagon::V6_vL32b_ai_128B;
 257     else
 258       Opcode = IsValidInc ? Hexagon::V6_vL32Ub_pi_128B
 259                           : Hexagon::V6_vL32Ub_ai_128B;
 260     break;
 261   default:
 262     llvm_unreachable("Unexpected memory type in indexed load");
 263   }
 264
 265   SDValue IncV = CurDAG->getTargetConstant(Inc, dl, MVT::i32);
 266   MachineSDNode::mmo_iterator MemOp = MF->allocateMemRefsArray(1);
 267   MemOp[0] = LD->getMemOperand();
 268
 269   auto getExt64 = [this,ExtType] (MachineSDNode *N, const SDLoc &dl)
 270         -> MachineSDNode* {
 271     if (ExtType == ISD::ZEXTLOAD || ExtType == ISD::EXTLOAD) {
 272       SDValue Zero = CurDAG->getTargetConstant(0, dl, MVT::i32);
 273       return CurDAG->getMachineNode(Hexagon::A4_combineir, dl, MVT::i64,
 274                                     Zero, SDValue(N, 0));
 275     }
 276     if (ExtType == ISD::SEXTLOAD)
 277       return CurDAG->getMachineNode(Hexagon::A2_sxtw, dl, MVT::i64,
 278                                     SDValue(N, 0));
 279     return N;
 280   };
 281
 282   //                  Loaded value   Next address   Chain
 283   SDValue From[3] = { SDValue(LD,0), SDValue(LD,1), SDValue(LD,2) };
 284   SDValue To[3];
 285
 286   EVT ValueVT = LD->getValueType(0);
 287   if (ValueVT == MVT::i64 && ExtType != ISD::NON_EXTLOAD) {
 288     // A load extending to i64 will actually produce i32, which will then
 289     // need to be extended to i64.
 290     assert(LoadedVT.getSizeInBits() <= 32);
 291     ValueVT = MVT::i32;
 292   }
 293
 294   if (IsValidInc) {
 295     MachineSDNode *L = CurDAG->getMachineNode(Opcode, dl, ValueVT,
 296                                               MVT::i32, MVT::Other, Base,
 297                                               IncV, Chain);
 298     L->setMemRefs(MemOp, MemOp+1);
 299     To[1] = SDValue(L, 1); // Next address.
 300     To[2] = SDValue(L, 2); // Chain.
 301     // Handle special case for extension to i64.
 302     if (LD->getValueType(0) == MVT::i64)
 303       L = getExt64(L, dl);
 304     To[0] = SDValue(L, 0); // Loaded (extended) value.
 305   } else {
 306     SDValue Zero = CurDAG->getTargetConstant(0, dl, MVT::i32);
 307     MachineSDNode *L = CurDAG->getMachineNode(Opcode, dl, ValueVT, MVT::Other,
 308                                               Base, Zero, Chain);
 309     L->setMemRefs(MemOp, MemOp+1);
 310     To[2] = SDValue(L, 1); // Chain.
 311     MachineSDNode *A = CurDAG->getMachineNode(Hexagon::A2_addi, dl, MVT::i32,
 312                                               Base, IncV);
 313     To[1] = SDValue(A, 0); // Next address.
 314     // Handle special case for extension to i64.
 315     if (LD->getValueType(0) == MVT::i64)
 316       L = getExt64(L, dl);
 317     To[0] = SDValue(L, 0); // Loaded (extended) value.
 318   }
 319   ReplaceUses(From, To, 3);
 320   CurDAG->RemoveDeadNode(LD);
 321 }
 322
 323
 324 MachineSDNode *HexagonDAGToDAGISel::LoadInstrForLoadIntrinsic(SDNode *IntN) {
 325   if (IntN->getOpcode() != ISD::INTRINSIC_W_CHAIN)
 326     return nullptr;
 327
 328   SDLoc dl(IntN);
 329   unsigned IntNo = cast<ConstantSDNode>(IntN->getOperand(1))->getZExtValue();
 330
 331   static std::map<unsigned,unsigned> LoadPciMap = {
 332     { Intrinsic::hexagon_circ_ldb,  Hexagon::L2_loadrb_pci  },
 333     { Intrinsic::hexagon_circ_ldub, Hexagon::L2_loadrub_pci },
 334     { Intrinsic::hexagon_circ_ldh,  Hexagon::L2_loadrh_pci  },
 335     { Intrinsic::hexagon_circ_lduh, Hexagon::L2_loadruh_pci },
 336     { Intrinsic::hexagon_circ_ldw,  Hexagon::L2_loadri_pci  },
 337     { Intrinsic::hexagon_circ_ldd,  Hexagon::L2_loadrd_pci  },
 338   };
 339   auto FLC = LoadPciMap.find(IntNo);
 340   if (FLC != LoadPciMap.end()) {
 341     SDNode *Mod = CurDAG->getMachineNode(Hexagon::A2_tfrrcr, dl, MVT::i32,
 342           IntN->getOperand(4));
 343     EVT ValTy = (IntNo == Intrinsic::hexagon_circ_ldd) ? MVT::i64 : MVT::i32;
 344     EVT RTys[] = { ValTy, MVT::i32, MVT::Other };
 345     // Operands: { Base, Increment, Modifier, Chain }
 346     auto Inc = cast<ConstantSDNode>(IntN->getOperand(5));
 347     SDValue I = CurDAG->getTargetConstant(Inc->getSExtValue(), dl, MVT::i32);
 348     MachineSDNode *Res = CurDAG->getMachineNode(FLC->second, dl, RTys,
 349           { IntN->getOperand(2), I, SDValue(Mod,0), IntN->getOperand(0) });
 350     return Res;
 351   }
 352
 353   static std::map<unsigned,unsigned> LoadPbrMap = {
 354     { Intrinsic::hexagon_brev_ldb,  Hexagon::L2_loadrb_pbr  },
 355     { Intrinsic::hexagon_brev_ldub, Hexagon::L2_loadrub_pbr },
 356     { Intrinsic::hexagon_brev_ldh,  Hexagon::L2_loadrh_pbr  },
 357     { Intrinsic::hexagon_brev_lduh, Hexagon::L2_loadruh_pbr },
 358     { Intrinsic::hexagon_brev_ldw,  Hexagon::L2_loadri_pbr  },
 359     { Intrinsic::hexagon_brev_ldd,  Hexagon::L2_loadrd_pbr  },
 360   };
 361   auto FLB = LoadPbrMap.find(IntNo);
 362   if (FLB != LoadPbrMap.end()) {
 363     SDNode *Mod = CurDAG->getMachineNode(Hexagon::A2_tfrrcr, dl, MVT::i32,
 364             IntN->getOperand(4));
 365     EVT ValTy = (IntNo == Intrinsic::hexagon_brev_ldd) ? MVT::i64 : MVT::i32;
 366     EVT RTys[] = { ValTy, MVT::i32, MVT::Other };
 367     // Operands: { Base, Modifier, Chain }
 368     MachineSDNode *Res = CurDAG->getMachineNode(FLB->second, dl, RTys,
 369           { IntN->getOperand(2), SDValue(Mod,0), IntN->getOperand(0) });
 370     return Res;
 371   }
 372
 373   return nullptr;
 374 }
 375
 376 SDNode *HexagonDAGToDAGISel::StoreInstrForLoadIntrinsic(MachineSDNode *LoadN,
 377       SDNode *IntN) {
 378   // The "LoadN" is just a machine load instruction. The intrinsic also
 379   // involves storing it. Generate an appropriate store to the location
 380   // given in the intrinsic's operand(3).
 381   uint64_t F = HII->get(LoadN->getMachineOpcode()).TSFlags;
 382   unsigned SizeBits = (F >> HexagonII::MemAccessSizePos) &
 383                       HexagonII::MemAccesSizeMask;
 384   unsigned Size = 1U << (SizeBits-1);
 385
 386   SDLoc dl(IntN);
 387   MachinePointerInfo PI;
 388   SDValue TS;
 389   SDValue Loc = IntN->getOperand(3);
 390
 391   if (Size >= 4)
 392     TS = CurDAG->getStore(SDValue(LoadN, 2), dl, SDValue(LoadN, 0), Loc, PI,
 393                           Size);
 394   else
 395     TS = CurDAG->getTruncStore(SDValue(LoadN, 2), dl, SDValue(LoadN, 0), Loc,
 396                                PI, MVT::getIntegerVT(Size * 8), Size);
 397
 398   SDNode *StoreN;
 399   {
 400     HandleSDNode Handle(TS);
 401     SelectStore(TS.getNode());
 402     StoreN = Handle.getValue().getNode();
 403   }
 404
 405   // Load's results are { Loaded value, Updated pointer, Chain }
 406   ReplaceUses(SDValue(IntN, 0), SDValue(LoadN, 1));
 407   ReplaceUses(SDValue(IntN, 1), SDValue(StoreN, 0));
 408   return StoreN;
 409 }
 410
 411 bool HexagonDAGToDAGISel::tryLoadOfLoadIntrinsic(LoadSDNode *N) {
 412   // The intrinsics for load circ/brev perform two operations:
 413   // 1. Load a value V from the specified location, using the addressing
 414   //    mode corresponding to the intrinsic.
 415   // 2. Store V into a specified location. This location is typically a
 416   //    local, temporary object.
 417   // In many cases, the program using these intrinsics will immediately
 418   // load V again from the local object. In those cases, when certain
 419   // conditions are met, the last load can be removed.
 420   // This function identifies and optimizes this pattern. If the pattern
 421   // cannot be optimized, it returns nullptr, which will cause the load
 422   // to be selected separately from the intrinsic (which will be handled
 423   // in SelectIntrinsicWChain).
 424
 425   SDValue Ch = N->getOperand(0);
 426   SDValue Loc = N->getOperand(1);
 427
 428   // Assume that the load and the intrinsic are connected directly with a
 429   // chain:
 430   //   t1: i32,ch = int.load ..., ..., ..., Loc, ...    // <-- C
 431   //   t2: i32,ch = load t1:1, Loc, ...
 432   SDNode *C = Ch.getNode();
 433
 434   if (C->getOpcode() != ISD::INTRINSIC_W_CHAIN)
 435     return false;
 436
 437   // The second load can only be eliminated if its extension type matches
 438   // that of the load instruction corresponding to the intrinsic. The user
 439   // can provide an address of an unsigned variable to store the result of
 440   // a sign-extending intrinsic into (or the other way around).
 441   ISD::LoadExtType IntExt;
 442   switch (cast<ConstantSDNode>(C->getOperand(1))->getZExtValue()) {
 443     case Intrinsic::hexagon_brev_ldub:
 444     case Intrinsic::hexagon_brev_lduh:
 445     case Intrinsic::hexagon_circ_ldub:
 446     case Intrinsic::hexagon_circ_lduh:
 447       IntExt = ISD::ZEXTLOAD;
 448       break;
 449     case Intrinsic::hexagon_brev_ldw:
 450     case Intrinsic::hexagon_brev_ldd:
 451     case Intrinsic::hexagon_circ_ldw:
 452     case Intrinsic::hexagon_circ_ldd:
 453       IntExt = ISD::NON_EXTLOAD;
 454       break;
 455     default:
 456       IntExt = ISD::SEXTLOAD;
 457       break;
 458   }
 459   if (N->getExtensionType() != IntExt)
 460     return false;
 461
 462   // Make sure the target location for the loaded value in the load intrinsic
 463   // is the location from which LD (or N) is loading.
 464   if (C->getNumOperands() < 4 || Loc.getNode() != C->getOperand(3).getNode())
 465     return false;
 466
 467   if (MachineSDNode *L = LoadInstrForLoadIntrinsic(C)) {
 468     SDNode *S = StoreInstrForLoadIntrinsic(L, C);
 469     SDValue F[] = { SDValue(N,0), SDValue(N,1), SDValue(C,0), SDValue(C,1) };
 470     SDValue T[] = { SDValue(L,0), SDValue(S,0), SDValue(L,1), SDValue(S,0) };
 471     ReplaceUses(F, T, array_lengthof(T));
 472     // This transformation will leave the intrinsic dead. If it remains in
 473     // the DAG, the selection code will see it again, but without the load,
 474     // and it will generate a store that is normally required for it.
 475     CurDAG->RemoveDeadNode(C);
 476     return true;
 477   }
 478
 479   return false;
 480 }
 481
 482 void HexagonDAGToDAGISel::SelectLoad(SDNode *N) {
 483   SDLoc dl(N);
 484   LoadSDNode *LD = cast<LoadSDNode>(N);
 485   ISD::MemIndexedMode AM = LD->getAddressingMode();
 486
 487   // Handle indexed loads.
 488   if (AM != ISD::UNINDEXED) {
 489     SelectIndexedLoad(LD, dl);
 490     return;
 491   }
 492
 493   // Handle patterns using circ/brev load intrinsics.
 494   if (tryLoadOfLoadIntrinsic(LD))
 495     return;
 496
 497   SelectCode(LD);
 498 }
 499
 500 void HexagonDAGToDAGISel::SelectIndexedStore(StoreSDNode *ST, const SDLoc &dl) {
 501   SDValue Chain = ST->getChain();
 502   SDValue Base = ST->getBasePtr();
 503   SDValue Offset = ST->getOffset();
 504   SDValue Value = ST->getValue();
 505   // Get the constant value.
 506   int32_t Inc = cast<ConstantSDNode>(Offset.getNode())->getSExtValue();
 507   EVT StoredVT = ST->getMemoryVT();
 508   EVT ValueVT = Value.getValueType();
 509
 510   bool IsValidInc = HII->isValidAutoIncImm(StoredVT, Inc);
 511   unsigned Opcode = 0;
 512
 513   assert(StoredVT.isSimple());
 514   switch (StoredVT.getSimpleVT().SimpleTy) {
 515   case MVT::i8:
 516     Opcode = IsValidInc ? Hexagon::S2_storerb_pi : Hexagon::S2_storerb_io;
 517     break;
 518   case MVT::i16:
 519     Opcode = IsValidInc ? Hexagon::S2_storerh_pi : Hexagon::S2_storerh_io;
 520     break;
 521   case MVT::i32:
 522     Opcode = IsValidInc ? Hexagon::S2_storeri_pi : Hexagon::S2_storeri_io;
 523     break;
 524   case MVT::i64:
 525     Opcode = IsValidInc ? Hexagon::S2_storerd_pi : Hexagon::S2_storerd_io;
 526     break;
 527   // 64B
 528   case MVT::v64i8:
 529   case MVT::v32i16:
 530   case MVT::v16i32:
 531   case MVT::v8i64:
 532     if (isAlignedMemNode(ST))
 533       Opcode = IsValidInc ? Hexagon::V6_vS32b_pi : Hexagon::V6_vS32b_ai;
 534     else
 535       Opcode = IsValidInc ? Hexagon::V6_vS32Ub_pi : Hexagon::V6_vS32Ub_ai;
 536     break;
 537   // 128B
 538   case MVT::v128i8:
 539   case MVT::v64i16:
 540   case MVT::v32i32:
 541   case MVT::v16i64:
 542     if (isAlignedMemNode(ST))
 543       Opcode = IsValidInc ? Hexagon::V6_vS32b_pi_128B
 544                           : Hexagon::V6_vS32b_ai_128B;
 545     else
 546       Opcode = IsValidInc ? Hexagon::V6_vS32Ub_pi_128B
 547                           : Hexagon::V6_vS32Ub_ai_128B;
 548     break;
 549   default:
 550     llvm_unreachable("Unexpected memory type in indexed store");
 551   }
 552
 553   if (ST->isTruncatingStore() && ValueVT.getSizeInBits() == 64) {
 554     assert(StoredVT.getSizeInBits() < 64 && "Not a truncating store");
 555     Value = CurDAG->getTargetExtractSubreg(Hexagon::isub_lo,
 556                                            dl, MVT::i32, Value);
 557   }
 558
 559   SDValue IncV = CurDAG->getTargetConstant(Inc, dl, MVT::i32);
 560   MachineSDNode::mmo_iterator MemOp = MF->allocateMemRefsArray(1);
 561   MemOp[0] = ST->getMemOperand();
 562
 563   //                  Next address   Chain
 564   SDValue From[2] = { SDValue(ST,0), SDValue(ST,1) };
 565   SDValue To[2];
 566
 567   if (IsValidInc) {
 568     // Build post increment store.
 569     SDValue Ops[] = { Base, IncV, Value, Chain };
 570     MachineSDNode *S = CurDAG->getMachineNode(Opcode, dl, MVT::i32, MVT::Other,
 571                                               Ops);
 572     S->setMemRefs(MemOp, MemOp + 1);
 573     To[0] = SDValue(S, 0);
 574     To[1] = SDValue(S, 1);
 575   } else {
 576     SDValue Zero = CurDAG->getTargetConstant(0, dl, MVT::i32);
 577     SDValue Ops[] = { Base, Zero, Value, Chain };
 578     MachineSDNode *S = CurDAG->getMachineNode(Opcode, dl, MVT::Other, Ops);
 579     S->setMemRefs(MemOp, MemOp + 1);
 580     To[1] = SDValue(S, 0);
 581     MachineSDNode *A = CurDAG->getMachineNode(Hexagon::A2_addi, dl, MVT::i32,
 582                                               Base, IncV);
 583     To[0] = SDValue(A, 0);
 584   }
 585
 586   ReplaceUses(From, To, 2);
 587   CurDAG->RemoveDeadNode(ST);
 588 }
 589
 590 void HexagonDAGToDAGISel::SelectStore(SDNode *N) {
 591   SDLoc dl(N);
 592   StoreSDNode *ST = cast<StoreSDNode>(N);
 593   ISD::MemIndexedMode AM = ST->getAddressingMode();
 594
 595   // Handle indexed stores.
 596   if (AM != ISD::UNINDEXED) {
 597     SelectIndexedStore(ST, dl);
 598     return;
 599   }
 600
 601   SelectCode(ST);
 602 }
 603
 604 void HexagonDAGToDAGISel::SelectSHL(SDNode *N) {
 605   SDLoc dl(N);
 606   SDValue Shl_0 = N->getOperand(0);
 607   SDValue Shl_1 = N->getOperand(1);
 608
 609   auto Default = [this,N] () -> void { SelectCode(N); };
 610
 611   if (N->getValueType(0) != MVT::i32 || Shl_1.getOpcode() != ISD::Constant)
 612     return Default();
 613
 614   // RHS is const.
 615   int32_t ShlConst = cast<ConstantSDNode>(Shl_1)->getSExtValue();
 616
 617   if (Shl_0.getOpcode() == ISD::MUL) {
 618     SDValue Mul_0 = Shl_0.getOperand(0); // Val
 619     SDValue Mul_1 = Shl_0.getOperand(1); // Const
 620     // RHS of mul is const.
 621     if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Mul_1)) {
 622       int32_t ValConst = C->getSExtValue() << ShlConst;
 623       if (isInt<9>(ValConst)) {
 624         SDValue Val = CurDAG->getTargetConstant(ValConst, dl, MVT::i32);
 625         SDNode *Result = CurDAG->getMachineNode(Hexagon::M2_mpysmi, dl,
 626                                                 MVT::i32, Mul_0, Val);
 627         ReplaceNode(N, Result);
 628         return;
 629       }
 630     }
 631     return Default();
 632   }
 633
 634   if (Shl_0.getOpcode() == ISD::SUB) {
 635     SDValue Sub_0 = Shl_0.getOperand(0); // Const 0
 636     SDValue Sub_1 = Shl_0.getOperand(1); // Val
 637     if (ConstantSDNode *C1 = dyn_cast<ConstantSDNode>(Sub_0)) {
 638       if (C1->getSExtValue() != 0 || Sub_1.getOpcode() != ISD::SHL)
 639         return Default();
 640       SDValue Shl2_0 = Sub_1.getOperand(0); // Val
 641       SDValue Shl2_1 = Sub_1.getOperand(1); // Const
 642       if (ConstantSDNode *C2 = dyn_cast<ConstantSDNode>(Shl2_1)) {
 643         int32_t ValConst = 1 << (ShlConst + C2->getSExtValue());
 644         if (isInt<9>(-ValConst)) {
 645           SDValue Val = CurDAG->getTargetConstant(-ValConst, dl, MVT::i32);
 646           SDNode *Result = CurDAG->getMachineNode(Hexagon::M2_mpysmi, dl,
 647                                                   MVT::i32, Shl2_0, Val);
 648           ReplaceNode(N, Result);
 649           return;
 650         }
 651       }
 652     }
 653   }
 654
 655   return Default();
 656 }
 657
 658
 659 //
 660 // If there is an zero_extend followed an intrinsic in DAG (this means - the
 661 // result of the intrinsic is predicate); convert the zero_extend to
 662 // transfer instruction.
 663 //
 664 // Zero extend -> transfer is lowered here. Otherwise, zero_extend will be
 665 // converted into a MUX as predicate registers defined as 1 bit in the
 666 // compiler. Architecture defines them as 8-bit registers.
 667 // We want to preserve all the lower 8-bits and, not just 1 LSB bit.
 668 //
 669 void HexagonDAGToDAGISel::SelectZeroExtend(SDNode *N) {
 670   SDLoc dl(N);
 671
 672   SDValue Op0 = N->getOperand(0);
 673   EVT OpVT = Op0.getValueType();
 674   unsigned OpBW = OpVT.getSizeInBits();
 675
 676   // Special handling for zero-extending a vector of booleans.
 677   if (OpVT.isVector() && OpVT.getVectorElementType() == MVT::i1 && OpBW <= 64) {
 678     SDNode *Mask = CurDAG->getMachineNode(Hexagon::C2_mask, dl, MVT::i64, Op0);
 679     unsigned NE = OpVT.getVectorNumElements();
 680     EVT ExVT = N->getValueType(0);
 681     unsigned ES = ExVT.getScalarSizeInBits();
 682     uint64_t MV = 0, Bit = 1;
 683     for (unsigned i = 0; i < NE; ++i) {
 684       MV |= Bit;
 685       Bit <<= ES;
 686     }
 687     SDValue Ones = CurDAG->getTargetConstant(MV, dl, MVT::i64);
 688     SDNode *OnesReg = CurDAG->getMachineNode(Hexagon::CONST64, dl,
 689                                              MVT::i64, Ones);
 690     if (ExVT.getSizeInBits() == 32) {
 691       SDNode *And = CurDAG->getMachineNode(Hexagon::A2_andp, dl, MVT::i64,
 692                                            SDValue(Mask,0), SDValue(OnesReg,0));
 693       SDValue SubR = CurDAG->getTargetConstant(Hexagon::isub_lo, dl, MVT::i32);
 694       ReplaceNode(N, CurDAG->getMachineNode(Hexagon::EXTRACT_SUBREG, dl, ExVT,
 695                                             SDValue(And, 0), SubR));
 696       return;
 697     }
 698     ReplaceNode(N,
 699                 CurDAG->getMachineNode(Hexagon::A2_andp, dl, ExVT,
 700                                        SDValue(Mask, 0), SDValue(OnesReg, 0)));
 701     return;
 702   }
 703
 704   SDNode *Int = N->getOperand(0).getNode();
 705   if ((Int->getOpcode() == ISD::INTRINSIC_WO_CHAIN)) {
 706     unsigned ID = cast<ConstantSDNode>(Int->getOperand(0))->getZExtValue();
 707     if (doesIntrinsicReturnPredicate(ID)) {
 708       // Now we need to differentiate target data types.
 709       if (N->getValueType(0) == MVT::i64) {
 710         // Convert the zero_extend to Rs = Pd followed by A2_combinew(0,Rs).
 711         SDValue TargetConst0 = CurDAG->getTargetConstant(0, dl, MVT::i32);
 712         SDNode *Result_1 = CurDAG->getMachineNode(Hexagon::C2_tfrpr, dl,
 713                                                   MVT::i32, SDValue(Int, 0));
 714         SDNode *Result_2 = CurDAG->getMachineNode(Hexagon::A2_tfrsi, dl,
 715                                                   MVT::i32, TargetConst0);
 716         SDNode *Result_3 = CurDAG->getMachineNode(Hexagon::A2_combinew, dl,
 717                                                   MVT::i64, MVT::Other,
 718                                                   SDValue(Result_2, 0),
 719                                                   SDValue(Result_1, 0));
 720         ReplaceNode(N, Result_3);
 721         return;
 722       }
 723       if (N->getValueType(0) == MVT::i32) {
 724         // Convert the zero_extend to Rs = Pd
 725         SDNode* RsPd = CurDAG->getMachineNode(Hexagon::C2_tfrpr, dl,
 726                                               MVT::i32, SDValue(Int, 0));
 727         ReplaceNode(N, RsPd);
 728         return;
 729       }
 730       llvm_unreachable("Unexpected value type");
 731     }
 732   }
 733   SelectCode(N);
 734 }
 735
 736
 737 //
 738 // Handling intrinsics for circular load and bitreverse load.
 739 //
 740 void HexagonDAGToDAGISel::SelectIntrinsicWChain(SDNode *N) {
 741   if (MachineSDNode *L = LoadInstrForLoadIntrinsic(N)) {
 742     StoreInstrForLoadIntrinsic(L, N);
 743     CurDAG->RemoveDeadNode(N);
 744     return;
 745   }
 746   SelectCode(N);
 747 }
 748
 749 void HexagonDAGToDAGISel::SelectIntrinsicWOChain(SDNode *N) {
 750   unsigned IID = cast<ConstantSDNode>(N->getOperand(0))->getZExtValue();
 751   unsigned Bits;
 752   switch (IID) {
 753   case Intrinsic::hexagon_S2_vsplatrb:
 754     Bits = 8;
 755     break;
 756   case Intrinsic::hexagon_S2_vsplatrh:
 757     Bits = 16;
 758     break;
 759   default:
 760     SelectCode(N);
 761     return;
 762   }
 763
 764   SDValue V = N->getOperand(1);
 765   SDValue U;
 766   if (keepsLowBits(V, Bits, U)) {
 767     SDValue R = CurDAG->getNode(N->getOpcode(), SDLoc(N), N->getValueType(0),
 768                                 N->getOperand(0), U);
 769     ReplaceNode(N, R.getNode());
 770     SelectCode(R.getNode());
 771     return;
 772   }
 773   SelectCode(N);
 774 }
 775
 776 //
 777 // Map floating point constant values.
 778 //
 779 void HexagonDAGToDAGISel::SelectConstantFP(SDNode *N) {
 780   SDLoc dl(N);
 781   ConstantFPSDNode *CN = dyn_cast<ConstantFPSDNode>(N);
 782   APInt A = CN->getValueAPF().bitcastToAPInt();
 783   if (N->getValueType(0) == MVT::f32) {
 784     SDValue V = CurDAG->getTargetConstant(A.getZExtValue(), dl, MVT::i32);
 785     ReplaceNode(N, CurDAG->getMachineNode(Hexagon::A2_tfrsi, dl, MVT::f32, V));
 786     return;
 787   }
 788   if (N->getValueType(0) == MVT::f64) {
 789     SDValue V = CurDAG->getTargetConstant(A.getZExtValue(), dl, MVT::i64);
 790     ReplaceNode(N, CurDAG->getMachineNode(Hexagon::CONST64, dl, MVT::f64, V));
 791     return;
 792   }
 793
 794   SelectCode(N);
 795 }
 796
 797 //
 798 // Map boolean values.
 799 //
 800 void HexagonDAGToDAGISel::SelectConstant(SDNode *N) {
 801   if (N->getValueType(0) == MVT::i1) {
 802     assert(!(cast<ConstantSDNode>(N)->getZExtValue() >> 1));
 803     unsigned Opc = (cast<ConstantSDNode>(N)->getSExtValue() != 0)
 804                       ? Hexagon::PS_true
 805                       : Hexagon::PS_false;
 806     ReplaceNode(N, CurDAG->getMachineNode(Opc, SDLoc(N), MVT::i1));
 807     return;
 808   }
 809
 810   SelectCode(N);
 811 }
 812
 813
 814 void HexagonDAGToDAGISel::SelectFrameIndex(SDNode *N) {
 815   MachineFrameInfo &MFI = MF->getFrameInfo();
 816   const HexagonFrameLowering *HFI = HST->getFrameLowering();
 817   int FX = cast<FrameIndexSDNode>(N)->getIndex();
 818   unsigned StkA = HFI->getStackAlignment();
 819   unsigned MaxA = MFI.getMaxAlignment();
 820   SDValue FI = CurDAG->getTargetFrameIndex(FX, MVT::i32);
 821   SDLoc DL(N);
 822   SDValue Zero = CurDAG->getTargetConstant(0, DL, MVT::i32);
 823   SDNode *R = nullptr;
 824
 825   // Use PS_fi when:
 826   // - the object is fixed, or
 827   // - there are no objects with higher-than-default alignment, or
 828   // - there are no dynamically allocated objects.
 829   // Otherwise, use PS_fia.
 830   if (FX < 0 || MaxA <= StkA || !MFI.hasVarSizedObjects()) {
 831     R = CurDAG->getMachineNode(Hexagon::PS_fi, DL, MVT::i32, FI, Zero);
 832   } else {
 833     auto &HMFI = *MF->getInfo<HexagonMachineFunctionInfo>();
 834     unsigned AR = HMFI.getStackAlignBaseVReg();
 835     SDValue CH = CurDAG->getEntryNode();
 836     SDValue Ops[] = { CurDAG->getCopyFromReg(CH, DL, AR, MVT::i32), FI, Zero };
 837     R = CurDAG->getMachineNode(Hexagon::PS_fia, DL, MVT::i32, Ops);
 838   }
 839
 840   ReplaceNode(N, R);
 841 }
 842
 843
 844 void HexagonDAGToDAGISel::SelectBitcast(SDNode *N) {
 845   EVT SVT = N->getOperand(0).getValueType();
 846   EVT DVT = N->getValueType(0);
 847   if (!SVT.isVector() || !DVT.isVector() ||
 848       SVT.getVectorElementType() == MVT::i1 ||
 849       DVT.getVectorElementType() == MVT::i1 ||
 850       SVT.getSizeInBits() != DVT.getSizeInBits()) {
 851     SelectCode(N);
 852     return;
 853   }
 854
 855   CurDAG->ReplaceAllUsesOfValueWith(SDValue(N,0), N->getOperand(0));
 856   CurDAG->RemoveDeadNode(N);
 857 }
 858
 859
 860 void HexagonDAGToDAGISel::Select(SDNode *N) {
 861   if (N->isMachineOpcode())
 862     return N->setNodeId(-1);  // Already selected.
 863
 864   switch (N->getOpcode()) {
 865   case ISD::Constant:             return SelectConstant(N);
 866   case ISD::ConstantFP:           return SelectConstantFP(N);
 867   case ISD::FrameIndex:           return SelectFrameIndex(N);
 868   case ISD::BITCAST:              return SelectBitcast(N);
 869   case ISD::SHL:                  return SelectSHL(N);
 870   case ISD::LOAD:                 return SelectLoad(N);
 871   case ISD::STORE:                return SelectStore(N);
 872   case ISD::ZERO_EXTEND:          return SelectZeroExtend(N);
 873   case ISD::INTRINSIC_W_CHAIN:    return SelectIntrinsicWChain(N);
 874   case ISD::INTRINSIC_WO_CHAIN:   return SelectIntrinsicWOChain(N);
 875   }
 876
 877   SelectCode(N);
 878 }
 879
 880 bool HexagonDAGToDAGISel::
 881 SelectInlineAsmMemoryOperand(const SDValue &Op, unsigned ConstraintID,
 882                              std::vector<SDValue> &OutOps) {
 883   SDValue Inp = Op, Res;
 884
 885   switch (ConstraintID) {
 886   default:
 887     return true;
 888   case InlineAsm::Constraint_i:
 889   case InlineAsm::Constraint_o: // Offsetable.
 890   case InlineAsm::Constraint_v: // Not offsetable.
 891   case InlineAsm::Constraint_m: // Memory.
 892     if (SelectAddrFI(Inp, Res))
 893       OutOps.push_back(Res);
 894     else
 895       OutOps.push_back(Inp);
 896     break;
 897   }
 898
 899   OutOps.push_back(CurDAG->getTargetConstant(0, SDLoc(Op), MVT::i32));
 900   return false;
 901 }
 902
 903
 904 static bool isMemOPCandidate(SDNode *I, SDNode *U) {
 905   // I is an operand of U. Check if U is an arithmetic (binary) operation
 906   // usable in a memop, where the other operand is a loaded value, and the
 907   // result of U is stored in the same location.
 908
 909   if (!U->hasOneUse())
 910     return false;
 911   unsigned Opc = U->getOpcode();
 912   switch (Opc) {
 913     case ISD::ADD:
 914     case ISD::SUB:
 915     case ISD::AND:
 916     case ISD::OR:
 917       break;
 918     default:
 919       return false;
 920   }
 921
 922   SDValue S0 = U->getOperand(0);
 923   SDValue S1 = U->getOperand(1);
 924   SDValue SY = (S0.getNode() == I) ? S1 : S0;
 925
 926   SDNode *UUse = *U->use_begin();
 927   if (UUse->getNumValues() != 1)
 928     return false;
 929
 930   // Check if one of the inputs to U is a load instruction and the output
 931   // is used by a store instruction. If so and they also have the same
 932   // base pointer, then don't preoprocess this node sequence as it
 933   // can be matched to a memop.
 934   SDNode *SYNode = SY.getNode();
 935   if (UUse->getOpcode() == ISD::STORE && SYNode->getOpcode() == ISD::LOAD) {
 936     SDValue LDBasePtr = cast<MemSDNode>(SYNode)->getBasePtr();
 937     SDValue STBasePtr = cast<MemSDNode>(UUse)->getBasePtr();
 938     if (LDBasePtr == STBasePtr)
 939       return true;
 940   }
 941   return false;
 942 }
 943
 944
 945 // Transform: (or (select c x 0) z)  ->  (select c (or x z) z)
 946 //            (or (select c 0 y) z)  ->  (select c z (or y z))
 947 void HexagonDAGToDAGISel::ppSimplifyOrSelect0(std::vector<SDNode*> &&Nodes) {
 948   SelectionDAG &DAG = *CurDAG;
 949
 950   for (auto I : Nodes) {
 951     if (I->getOpcode() != ISD::OR)
 952       continue;
 953
 954     auto IsZero = [] (const SDValue &V) -> bool {
 955       if (ConstantSDNode *SC = dyn_cast<ConstantSDNode>(V.getNode()))
 956         return SC->isNullValue();
 957       return false;
 958     };
 959     auto IsSelect0 = [IsZero] (const SDValue &Op) -> bool {
 960       if (Op.getOpcode() != ISD::SELECT)
 961         return false;
 962       return IsZero(Op.getOperand(1)) || IsZero(Op.getOperand(2));
 963     };
 964
 965     SDValue N0 = I->getOperand(0), N1 = I->getOperand(1);
 966     EVT VT = I->getValueType(0);
 967     bool SelN0 = IsSelect0(N0);
 968     SDValue SOp = SelN0 ? N0 : N1;
 969     SDValue VOp = SelN0 ? N1 : N0;
 970
 971     if (SOp.getOpcode() == ISD::SELECT && SOp.getNode()->hasOneUse()) {
 972       SDValue SC = SOp.getOperand(0);
 973       SDValue SX = SOp.getOperand(1);
 974       SDValue SY = SOp.getOperand(2);
 975       SDLoc DLS = SOp;
 976       if (IsZero(SY)) {
 977         SDValue NewOr = DAG.getNode(ISD::OR, DLS, VT, SX, VOp);
 978         SDValue NewSel = DAG.getNode(ISD::SELECT, DLS, VT, SC, NewOr, VOp);
 979         DAG.ReplaceAllUsesWith(I, NewSel.getNode());
 980       } else if (IsZero(SX)) {
 981         SDValue NewOr = DAG.getNode(ISD::OR, DLS, VT, SY, VOp);
 982         SDValue NewSel = DAG.getNode(ISD::SELECT, DLS, VT, SC, VOp, NewOr);
 983         DAG.ReplaceAllUsesWith(I, NewSel.getNode());
 984       }
 985     }
 986   }
 987 }
 988
 989 // Transform: (store ch val (add x (add (shl y c) e)))
 990 //        to: (store ch val (add x (shl (add y d) c))),
 991 // where e = (shl d c) for some integer d.
 992 // The purpose of this is to enable generation of loads/stores with
 993 // shifted addressing mode, i.e. mem(x+y<<#c). For that, the shift
 994 // value c must be 0, 1 or 2.
 995 void HexagonDAGToDAGISel::ppAddrReorderAddShl(std::vector<SDNode*> &&Nodes) {
 996   SelectionDAG &DAG = *CurDAG;
 997
 998   for (auto I : Nodes) {
 999     if (I->getOpcode() != ISD::STORE)
1000       continue;
1001
1002     // I matched: (store ch val Off)
1003     SDValue Off = I->getOperand(2);
1004     // Off needs to match: (add x (add (shl y c) (shl d c))))
1005     if (Off.getOpcode() != ISD::ADD)
1006       continue;
1007     // Off matched: (add x T0)
1008     SDValue T0 = Off.getOperand(1);
1009     // T0 needs to match: (add T1 T2):
1010     if (T0.getOpcode() != ISD::ADD)
1011       continue;
1012     // T0 matched: (add T1 T2)
1013     SDValue T1 = T0.getOperand(0);
1014     SDValue T2 = T0.getOperand(1);
1015     // T1 needs to match: (shl y c)
1016     if (T1.getOpcode() != ISD::SHL)
1017       continue;
1018     SDValue C = T1.getOperand(1);
1019     ConstantSDNode *CN = dyn_cast<ConstantSDNode>(C.getNode());
1020     if (CN == nullptr)
1021       continue;
1022     unsigned CV = CN->getZExtValue();
1023     if (CV > 2)
1024       continue;
1025     // T2 needs to match e, where e = (shl d c) for some d.
1026     ConstantSDNode *EN = dyn_cast<ConstantSDNode>(T2.getNode());
1027     if (EN == nullptr)
1028       continue;
1029     unsigned EV = EN->getZExtValue();
1030     if (EV % (1 << CV) != 0)
1031       continue;
1032     unsigned DV = EV / (1 << CV);
1033
1034     // Replace T0 with: (shl (add y d) c)
1035     SDLoc DL = SDLoc(I);
1036     EVT VT = T0.getValueType();
1037     SDValue D = DAG.getConstant(DV, DL, VT);
1038     // NewAdd = (add y d)
1039     SDValue NewAdd = DAG.getNode(ISD::ADD, DL, VT, T1.getOperand(0), D);
1040     // NewShl = (shl NewAdd c)
1041     SDValue NewShl = DAG.getNode(ISD::SHL, DL, VT, NewAdd, C);
1042     ReplaceNode(T0.getNode(), NewShl.getNode());
1043   }
1044 }
1045
1046 // Transform: (load ch (add x (and (srl y c) Mask)))
1047 //        to: (load ch (add x (shl (srl y d) d-c)))
1048 // where
1049 // Mask = 00..0 111..1 0.0
1050 //          |     |     +-- d-c 0s, and d-c is 0, 1 or 2.
1051 //          |     +-------- 1s
1052 //          +-------------- at most c 0s
1053 // Motivating example:
1054 // DAG combiner optimizes (add x (shl (srl y 5) 2))
1055 //                     to (add x (and (srl y 3) 1FFFFFFC))
1056 // which results in a constant-extended and(##...,lsr). This transformation
1057 // undoes this simplification for cases where the shl can be folded into
1058 // an addressing mode.
1059 void HexagonDAGToDAGISel::ppAddrRewriteAndSrl(std::vector<SDNode*> &&Nodes) {
1060   SelectionDAG &DAG = *CurDAG;
1061
1062   for (SDNode *N : Nodes) {
1063     unsigned Opc = N->getOpcode();
1064     if (Opc != ISD::LOAD && Opc != ISD::STORE)
1065       continue;
1066     SDValue Addr = Opc == ISD::LOAD ? N->getOperand(1) : N->getOperand(2);
1067     // Addr must match: (add x T0)
1068     if (Addr.getOpcode() != ISD::ADD)
1069       continue;
1070     SDValue T0 = Addr.getOperand(1);
1071     // T0 must match: (and T1 Mask)
1072     if (T0.getOpcode() != ISD::AND)
1073       continue;
1074
1075     // We have an AND.
1076     //
1077     // Check the first operand. It must be: (srl y c).
1078     SDValue S = T0.getOperand(0);
1079     if (S.getOpcode() != ISD::SRL)
1080       continue;
1081     ConstantSDNode *SN = dyn_cast<ConstantSDNode>(S.getOperand(1).getNode());
1082     if (SN == nullptr)
1083       continue;
1084     if (SN->getAPIntValue().getBitWidth() != 32)
1085       continue;
1086     uint32_t CV = SN->getZExtValue();
1087
1088     // Check the second operand: the supposed mask.
1089     ConstantSDNode *MN = dyn_cast<ConstantSDNode>(T0.getOperand(1).getNode());
1090     if (MN == nullptr)
1091       continue;
1092     if (MN->getAPIntValue().getBitWidth() != 32)
1093       continue;
1094     uint32_t Mask = MN->getZExtValue();
1095     // Examine the mask.
1096     uint32_t TZ = countTrailingZeros(Mask);
1097     uint32_t M1 = countTrailingOnes(Mask >> TZ);
1098     uint32_t LZ = countLeadingZeros(Mask);
1099     // Trailing zeros + middle ones + leading zeros must equal the width.
1100     if (TZ + M1 + LZ != 32)
1101       continue;
1102     // The number of trailing zeros will be encoded in the addressing mode.
1103     if (TZ > 2)
1104       continue;
1105     // The number of leading zeros must be at most c.
1106     if (LZ > CV)
1107       continue;
1108
1109     // All looks good.
1110     SDValue Y = S.getOperand(0);
1111     EVT VT = Addr.getValueType();
1112     SDLoc dl(S);
1113     // TZ = D-C, so D = TZ+C.
1114     SDValue D = DAG.getConstant(TZ+CV, dl, VT);
1115     SDValue DC = DAG.getConstant(TZ, dl, VT);
1116     SDValue NewSrl = DAG.getNode(ISD::SRL, dl, VT, Y, D);
1117     SDValue NewShl = DAG.getNode(ISD::SHL, dl, VT, NewSrl, DC);
1118     ReplaceNode(T0.getNode(), NewShl.getNode());
1119   }
1120 }
1121
1122 // Transform: (op ... (zext i1 c) ...) -> (select c (op ... 0 ...)
1123 //                                                  (op ... 1 ...))
1124 void HexagonDAGToDAGISel::ppHoistZextI1(std::vector<SDNode*> &&Nodes) {
1125   SelectionDAG &DAG = *CurDAG;
1126
1127   for (SDNode *N : Nodes) {
1128     unsigned Opc = N->getOpcode();
1129     if (Opc != ISD::ZERO_EXTEND)
1130       continue;
1131     SDValue OpI1 = N->getOperand(0);
1132     EVT OpVT = OpI1.getValueType();
1133     if (!OpVT.isSimple() || OpVT.getSimpleVT() != MVT::i1)
1134       continue;
1135     for (auto I = N->use_begin(), E = N->use_end(); I != E; ++I) {
1136       SDNode *U = *I;
1137       if (U->getNumValues() != 1)
1138         continue;
1139       EVT UVT = U->getValueType(0);
1140       if (!UVT.isSimple() || !UVT.isInteger() || UVT.getSimpleVT() == MVT::i1)
1141         continue;
1142       if (isMemOPCandidate(N, U))
1143         continue;
1144
1145       // Potentially simplifiable operation.
1146       unsigned I1N = I.getOperandNo();
1147       SmallVector<SDValue,2> Ops(U->getNumOperands());
1148       for (unsigned i = 0, n = U->getNumOperands(); i != n; ++i)
1149         Ops[i] = U->getOperand(i);
1150       EVT BVT = Ops[I1N].getValueType();
1151
1152       SDLoc dl(U);
1153       SDValue C0 = DAG.getConstant(0, dl, BVT);
1154       SDValue C1 = DAG.getConstant(1, dl, BVT);
1155       SDValue If0, If1;
1156
1157       if (isa<MachineSDNode>(U)) {
1158         unsigned UseOpc = U->getMachineOpcode();
1159         Ops[I1N] = C0;
1160         If0 = SDValue(DAG.getMachineNode(UseOpc, dl, UVT, Ops), 0);
1161         Ops[I1N] = C1;
1162         If1 = SDValue(DAG.getMachineNode(UseOpc, dl, UVT, Ops), 0);
1163       } else {
1164         unsigned UseOpc = U->getOpcode();
1165         Ops[I1N] = C0;
1166         If0 = DAG.getNode(UseOpc, dl, UVT, Ops);
1167         Ops[I1N] = C1;
1168         If1 = DAG.getNode(UseOpc, dl, UVT, Ops);
1169       }
1170       SDValue Sel = DAG.getNode(ISD::SELECT, dl, UVT, OpI1, If1, If0);
1171       DAG.ReplaceAllUsesWith(U, Sel.getNode());
1172     }
1173   }
1174 }
1175
1176 void HexagonDAGToDAGISel::PreprocessISelDAG() {
1177   // Repack all nodes before calling each preprocessing function,
1178   // because each of them can modify the set of nodes.
1179   auto getNodes = [this] () -> std::vector<SDNode*> {
1180     std::vector<SDNode*> T;
1181     T.reserve(CurDAG->allnodes_size());
1182     for (SDNode &N : CurDAG->allnodes())
1183       T.push_back(&N);
1184     return T;
1185   };
1186
1187   // Transform: (or (select c x 0) z)  ->  (select c (or x z) z)
1188   //            (or (select c 0 y) z)  ->  (select c z (or y z))
1189   ppSimplifyOrSelect0(getNodes());
1190
1191   // Transform: (store ch val (add x (add (shl y c) e)))
1192   //        to: (store ch val (add x (shl (add y d) c))),
1193   // where e = (shl d c) for some integer d.
1194   // The purpose of this is to enable generation of loads/stores with
1195   // shifted addressing mode, i.e. mem(x+y<<#c). For that, the shift
1196   // value c must be 0, 1 or 2.
1197   ppAddrReorderAddShl(getNodes());
1198
1199   // Transform: (load ch (add x (and (srl y c) Mask)))
1200   //        to: (load ch (add x (shl (srl y d) d-c)))
1201   // where
1202   // Mask = 00..0 111..1 0.0
1203   //          |     |     +-- d-c 0s, and d-c is 0, 1 or 2.
1204   //          |     +-------- 1s
1205   //          +-------------- at most c 0s
1206   // Motivating example:
1207   // DAG combiner optimizes (add x (shl (srl y 5) 2))
1208   //                     to (add x (and (srl y 3) 1FFFFFFC))
1209   // which results in a constant-extended and(##...,lsr). This transformation
1210   // undoes this simplification for cases where the shl can be folded into
1211   // an addressing mode.
1212   ppAddrRewriteAndSrl(getNodes());
1213
1214   // Transform: (op ... (zext i1 c) ...) -> (select c (op ... 0 ...)
1215   //                                                  (op ... 1 ...))
1216   ppHoistZextI1(getNodes());
1217
1218   DEBUG_WITH_TYPE("isel", {
1219     dbgs() << "Preprocessed (Hexagon) selection DAG:";
1220     CurDAG->dump();
1221   });
1222
1223   if (EnableAddressRebalancing) {
1224     rebalanceAddressTrees();
1225
1226     DEBUG_WITH_TYPE("isel", {
1227       dbgs() << "Address tree balanced selection DAG:";
1228       CurDAG->dump();
1229     });
1230   }
1231 }
1232
1233 void HexagonDAGToDAGISel::EmitFunctionEntryCode() {
1234   auto &HST = static_cast<const HexagonSubtarget&>(MF->getSubtarget());
1235   auto &HFI = *HST.getFrameLowering();
1236   if (!HFI.needsAligna(*MF))
1237     return;
1238
1239   MachineFrameInfo &MFI = MF->getFrameInfo();
1240   MachineBasicBlock *EntryBB = &MF->front();
1241   unsigned AR = FuncInfo->CreateReg(MVT::i32);
1242   unsigned MaxA = MFI.getMaxAlignment();
1243   BuildMI(EntryBB, DebugLoc(), HII->get(Hexagon::PS_aligna), AR)
1244       .addImm(MaxA);
1245   MF->getInfo<HexagonMachineFunctionInfo>()->setStackAlignBaseVReg(AR);
1246 }
1247
1248 // Match a frame index that can be used in an addressing mode.
1249 bool HexagonDAGToDAGISel::SelectAddrFI(SDValue &N, SDValue &R) {
1250   if (N.getOpcode() != ISD::FrameIndex)
1251     return false;
1252   auto &HFI = *HST->getFrameLowering();
1253   MachineFrameInfo &MFI = MF->getFrameInfo();
1254   int FX = cast<FrameIndexSDNode>(N)->getIndex();
1255   if (!MFI.isFixedObjectIndex(FX) && HFI.needsAligna(*MF))
1256     return false;
1257   R = CurDAG->getTargetFrameIndex(FX, MVT::i32);
1258   return true;
1259 }
1260
1261 inline bool HexagonDAGToDAGISel::SelectAddrGA(SDValue &N, SDValue &R) {
1262   return SelectGlobalAddress(N, R, false);
1263 }
1264
1265 inline bool HexagonDAGToDAGISel::SelectAddrGP(SDValue &N, SDValue &R) {
1266   return SelectGlobalAddress(N, R, true);
1267 }
1268
1269 bool HexagonDAGToDAGISel::SelectGlobalAddress(SDValue &N, SDValue &R,
1270                                               bool UseGP) {
1271   switch (N.getOpcode()) {
1272   case ISD::ADD: {
1273     SDValue N0 = N.getOperand(0);
1274     SDValue N1 = N.getOperand(1);
1275     unsigned GAOpc = N0.getOpcode();
1276     if (UseGP && GAOpc != HexagonISD::CONST32_GP)
1277       return false;
1278     if (!UseGP && GAOpc != HexagonISD::CONST32)
1279       return false;
1280     if (ConstantSDNode *Const = dyn_cast<ConstantSDNode>(N1)) {
1281       SDValue Addr = N0.getOperand(0);
1282       if (GlobalAddressSDNode *GA = dyn_cast<GlobalAddressSDNode>(Addr)) {
1283         if (GA->getOpcode() == ISD::TargetGlobalAddress) {
1284           uint64_t NewOff = GA->getOffset() + (uint64_t)Const->getSExtValue();
1285           R = CurDAG->getTargetGlobalAddress(GA->getGlobal(), SDLoc(Const),
1286                                              N.getValueType(), NewOff);
1287           return true;
1288         }
1289       }
1290     }
1291     break;
1292   }
1293   case HexagonISD::CONST32:
1294     // The operand(0) of CONST32 is TargetGlobalAddress, which is what we
1295     // want in the instruction.
1296     if (!UseGP)
1297       R = N.getOperand(0);
1298     return !UseGP;
1299   case HexagonISD::CONST32_GP:
1300     if (UseGP)
1301       R = N.getOperand(0);
1302     return UseGP;
1303   default:
1304     return false;
1305   }
1306
1307   return false;
1308 }
1309
1310 bool HexagonDAGToDAGISel::DetectUseSxtw(SDValue &N, SDValue &R) {
1311   // This (complex pattern) function is meant to detect a sign-extension
1312   // i32->i64 on a per-operand basis. This would allow writing single
1313   // patterns that would cover a number of combinations of different ways
1314   // a sign-extensions could be written. For example:
1315   //   (mul (DetectUseSxtw x) (DetectUseSxtw y)) -> (M2_dpmpyss_s0 x y)
1316   // could match either one of these:
1317   //   (mul (sext x) (sext_inreg y))
1318   //   (mul (sext-load *p) (sext_inreg y))
1319   //   (mul (sext_inreg x) (sext y))
1320   // etc.
1321   //
1322   // The returned value will have type i64 and its low word will
1323   // contain the value being extended. The high bits are not specified.
1324   // The returned type is i64 because the original type of N was i64,
1325   // but the users of this function should only use the low-word of the
1326   // result, e.g.
1327   //  (mul sxtw:x, sxtw:y) -> (M2_dpmpyss_s0 (LoReg sxtw:x), (LoReg sxtw:y))
1328
1329   if (N.getValueType() != MVT::i64)
1330     return false;
1331   EVT SrcVT;
1332   unsigned Opc = N.getOpcode();
1333   switch (Opc) {
1334     case ISD::SIGN_EXTEND:
1335     case ISD::SIGN_EXTEND_INREG: {
1336       // sext_inreg has the source type as a separate operand.
1337       EVT T = Opc == ISD::SIGN_EXTEND
1338                 ? N.getOperand(0).getValueType()
1339                 : cast<VTSDNode>(N.getOperand(1))->getVT();
1340       if (T.getSizeInBits() != 32)
1341         return false;
1342       R = N.getOperand(0);
1343       break;
1344     }
1345     case ISD::LOAD: {
1346       LoadSDNode *L = cast<LoadSDNode>(N);
1347       if (L->getExtensionType() != ISD::SEXTLOAD)
1348         return false;
1349       // All extending loads extend to i32, so even if the value in
1350       // memory is shorter than 32 bits, it will be i32 after the load.
1351       if (L->getMemoryVT().getSizeInBits() > 32)
1352         return false;
1353       R = N;
1354       break;
1355     }
1356     default:
1357       return false;
1358   }
1359   EVT RT = R.getValueType();
1360   if (RT == MVT::i64)
1361     return true;
1362   assert(RT == MVT::i32);
1363   // This is only to produce a value of type i64. Do not rely on the
1364   // high bits produced by this.
1365   const SDLoc &dl(N);
1366   SDValue Ops[] = {
1367     CurDAG->getTargetConstant(Hexagon::DoubleRegsRegClassID, dl, MVT::i32),
1368     R, CurDAG->getTargetConstant(Hexagon::isub_hi, dl, MVT::i32),
1369     R, CurDAG->getTargetConstant(Hexagon::isub_lo, dl, MVT::i32)
1370   };
1371   SDNode *T = CurDAG->getMachineNode(TargetOpcode::REG_SEQUENCE, dl,
1372                                      MVT::i64, Ops);
1373   R = SDValue(T, 0);
1374   return true;
1375 }
1376
1377 bool HexagonDAGToDAGISel::keepsLowBits(const SDValue &Val, unsigned NumBits,
1378       SDValue &Src) {
1379   unsigned Opc = Val.getOpcode();
1380   switch (Opc) {
1381   case ISD::SIGN_EXTEND:
1382   case ISD::ZERO_EXTEND:
1383   case ISD::ANY_EXTEND: {
1384     const SDValue &Op0 = Val.getOperand(0);
1385     EVT T = Op0.getValueType();
1386     if (T.isInteger() && T.getSizeInBits() == NumBits) {
1387       Src = Op0;
1388       return true;
1389     }
1390     break;
1391   }
1392   case ISD::SIGN_EXTEND_INREG:
1393   case ISD::AssertSext:
1394   case ISD::AssertZext:
1395     if (Val.getOperand(0).getValueType().isInteger()) {
1396       VTSDNode *T = cast<VTSDNode>(Val.getOperand(1));
1397       if (T->getVT().getSizeInBits() == NumBits) {
1398         Src = Val.getOperand(0);
1399         return true;
1400       }
1401     }
1402     break;
1403   case ISD::AND: {
1404     // Check if this is an AND with NumBits of lower bits set to 1.
1405     uint64_t Mask = (1 << NumBits) - 1;
1406     if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Val.getOperand(0))) {
1407       if (C->getZExtValue() == Mask) {
1408         Src = Val.getOperand(1);
1409         return true;
1410       }
1411     }
1412     if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Val.getOperand(1))) {
1413       if (C->getZExtValue() == Mask) {
1414         Src = Val.getOperand(0);
1415         return true;
1416       }
1417     }
1418     break;
1419   }
1420   case ISD::OR:
1421   case ISD::XOR: {
1422     // OR/XOR with the lower NumBits bits set to 0.
1423     uint64_t Mask = (1 << NumBits) - 1;
1424     if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Val.getOperand(0))) {
1425       if ((C->getZExtValue() & Mask) == 0) {
1426         Src = Val.getOperand(1);
1427         return true;
1428       }
1429     }
1430     if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Val.getOperand(1))) {
1431       if ((C->getZExtValue() & Mask) == 0) {
1432         Src = Val.getOperand(0);
1433         return true;
1434       }
1435     }
1436   }
1437   default:
1438     break;
1439   }
1440   return false;
1441 }
1442
1443
1444 bool HexagonDAGToDAGISel::isOrEquivalentToAdd(const SDNode *N) const {
1445   assert(N->getOpcode() == ISD::OR);
1446   auto *C = dyn_cast<ConstantSDNode>(N->getOperand(1));
1447   assert(C);
1448
1449   // Detect when "or" is used to add an offset to a stack object.
1450   if (auto *FN = dyn_cast<FrameIndexSDNode>(N->getOperand(0))) {
1451     MachineFrameInfo &MFI = MF->getFrameInfo();
1452     unsigned A = MFI.getObjectAlignment(FN->getIndex());
1453     assert(isPowerOf2_32(A));
1454     int32_t Off = C->getSExtValue();
1455     // If the alleged offset fits in the zero bits guaranteed by
1456     // the alignment, then this or is really an add.
1457     return (Off >= 0) && (((A-1) & Off) == unsigned(Off));
1458   }
1459   return false;
1460 }
1461
1462 bool HexagonDAGToDAGISel::isAlignedMemNode(const MemSDNode *N) const {
1463   return N->getAlignment() >= N->getMemoryVT().getStoreSize();
1464 }
1465
1466 bool HexagonDAGToDAGISel::isSmallStackStore(const StoreSDNode *N) const {
1467   unsigned StackSize = MF->getFrameInfo().estimateStackSize(*MF);
1468   switch (N->getMemoryVT().getStoreSize()) {
1469     case 1:
1470       return StackSize <= 56;   // 1*2^6 - 8
1471     case 2:
1472       return StackSize <= 120;  // 2*2^6 - 8
1473     case 4:
1474       return StackSize <= 248;  // 4*2^6 - 8
1475     default:
1476       return false;
1477   }
1478 }
1479
1480 // Return true when the given node fits in a positive half word.
1481 bool HexagonDAGToDAGISel::isPositiveHalfWord(const SDNode *N) const {
1482   if (const ConstantSDNode *CN = dyn_cast<const ConstantSDNode>(N)) {
1483     int64_t V = CN->getSExtValue();
1484     return V > 0 && isInt<16>(V);
1485   }
1486   if (N->getOpcode() == ISD::SIGN_EXTEND_INREG) {
1487     const VTSDNode *VN = dyn_cast<const VTSDNode>(N->getOperand(1));
1488     return VN->getVT().getSizeInBits() <= 16;
1489   }
1490   return false;
1491 }
1492
1493 ////////////////////////////////////////////////////////////////////////////////
1494 // Rebalancing of address calculation trees
1495
1496 static bool isOpcodeHandled(const SDNode *N) {
1497   switch (N->getOpcode()) {
1498     case ISD::ADD:
1499     case ISD::MUL:
1500       return true;
1501     case ISD::SHL:
1502       // We only handle constant shifts because these can be easily flattened
1503       // into multiplications by 2^Op1.
1504       return isa<ConstantSDNode>(N->getOperand(1).getNode());
1505     default:
1506       return false;
1507   }
1508 }
1509
1510 /// \brief Return the weight of an SDNode
1511 int HexagonDAGToDAGISel::getWeight(SDNode *N) {
1512   if (!isOpcodeHandled(N))
1513     return 1;
1514   assert(RootWeights.count(N) && "Cannot get weight of unseen root!");
1515   assert(RootWeights[N] != -1 && "Cannot get weight of unvisited root!");
1516   assert(RootWeights[N] != -2 && "Cannot get weight of RAWU'd root!");
1517   return RootWeights[N];
1518 }
1519
1520 int HexagonDAGToDAGISel::getHeight(SDNode *N) {
1521   if (!isOpcodeHandled(N))
1522     return 0;
1523   assert(RootWeights.count(N) && RootWeights[N] >= 0 &&
1524       "Cannot query height of unvisited/RAUW'd node!");
1525   return RootHeights[N];
1526 }
1527
1528 namespace {
1529 struct WeightedLeaf {
1530   SDValue Value;
1531   int Weight;
1532   int InsertionOrder;
1533
1534   WeightedLeaf() : Value(SDValue()) { }
1535
1536   WeightedLeaf(SDValue Value, int Weight, int InsertionOrder) :
1537     Value(Value), Weight(Weight), InsertionOrder(InsertionOrder) {
1538     assert(Weight >= 0 && "Weight must be >= 0");
1539   }
1540
1541   static bool Compare(const WeightedLeaf &A, const WeightedLeaf &B) {
1542     assert(A.Value.getNode() && B.Value.getNode());
1543     return A.Weight == B.Weight ?
1544             (A.InsertionOrder > B.InsertionOrder) :
1545             (A.Weight > B.Weight);
1546   }
1547 };
1548
1549 /// A specialized priority queue for WeigthedLeaves. It automatically folds
1550 /// constants and allows removal of non-top elements while maintaining the
1551 /// priority order.
1552 class LeafPrioQueue {
1553   SmallVector<WeightedLeaf, 8> Q;
1554   bool HaveConst;
1555   WeightedLeaf ConstElt;
1556   unsigned Opcode;
1557
1558 public:
1559   bool empty() {
1560     return (!HaveConst && Q.empty());
1561   }
1562
1563   size_t size() {
1564     return Q.size() + HaveConst;
1565   }
1566
1567   bool hasConst() {
1568     return HaveConst;
1569   }
1570
1571   const WeightedLeaf &top() {
1572     if (HaveConst)
1573       return ConstElt;
1574     return Q.front();
1575   }
1576
1577   WeightedLeaf pop() {
1578     if (HaveConst) {
1579       HaveConst = false;
1580       return ConstElt;
1581     }
1582     std::pop_heap(Q.begin(), Q.end(), WeightedLeaf::Compare);
1583     return Q.pop_back_val();
1584   }
1585
1586   void push(WeightedLeaf L, bool SeparateConst=true) {
1587     if (!HaveConst && SeparateConst && isa<ConstantSDNode>(L.Value)) {
1588       if (Opcode == ISD::MUL &&
1589           cast<ConstantSDNode>(L.Value)->getSExtValue() == 1)
1590         return;
1591       if (Opcode == ISD::ADD &&
1592           cast<ConstantSDNode>(L.Value)->getSExtValue() == 0)
1593         return;
1594
1595       HaveConst = true;
1596       ConstElt = L;
1597     } else {
1598       Q.push_back(L);
1599       std::push_heap(Q.begin(), Q.end(), WeightedLeaf::Compare);
1600     }
1601   }
1602
1603   /// Push L to the bottom of the queue regardless of its weight. If L is
1604   /// constant, it will not be folded with other constants in the queue.
1605   void pushToBottom(WeightedLeaf L) {
1606     L.Weight = 1000;
1607     push(L, false);
1608   }
1609
1610   /// Search for a SHL(x, [<=MaxAmount]) subtree in the queue, return the one of
1611   /// lowest weight and remove it from the queue.
1612   WeightedLeaf findSHL(uint64_t MaxAmount);
1613
1614   WeightedLeaf findMULbyConst();
1615
1616   LeafPrioQueue(unsigned Opcode) :
1617     HaveConst(false), Opcode(Opcode) { }
1618 };
1619 } // end anonymous namespace
1620
1621 WeightedLeaf LeafPrioQueue::findSHL(uint64_t MaxAmount) {
1622   int ResultPos;
1623   WeightedLeaf Result;
1624
1625   for (int Pos = 0, End = Q.size(); Pos != End; ++Pos) {
1626     const WeightedLeaf &L = Q[Pos];
1627     const SDValue &Val = L.Value;
1628     if (Val.getOpcode() != ISD::SHL ||
1629         !isa<ConstantSDNode>(Val.getOperand(1)) ||
1630         Val.getConstantOperandVal(1) > MaxAmount)
1631       continue;
1632     if (!Result.Value.getNode() || Result.Weight > L.Weight ||
1633         (Result.Weight == L.Weight && Result.InsertionOrder > L.InsertionOrder))
1634     {
1635       Result = L;
1636       ResultPos = Pos;
1637     }
1638   }
1639
1640   if (Result.Value.getNode()) {
1641     Q.erase(&Q[ResultPos]);
1642     std::make_heap(Q.begin(), Q.end(), WeightedLeaf::Compare);
1643   }
1644
1645   return Result;
1646 }
1647
1648 WeightedLeaf LeafPrioQueue::findMULbyConst() {
1649   int ResultPos;
1650   WeightedLeaf Result;
1651
1652   for (int Pos = 0, End = Q.size(); Pos != End; ++Pos) {
1653     const WeightedLeaf &L = Q[Pos];
1654     const SDValue &Val = L.Value;
1655     if (Val.getOpcode() != ISD::MUL ||
1656         !isa<ConstantSDNode>(Val.getOperand(1)) ||
1657         Val.getConstantOperandVal(1) > 127)
1658       continue;
1659     if (!Result.Value.getNode() || Result.Weight > L.Weight ||
1660         (Result.Weight == L.Weight && Result.InsertionOrder > L.InsertionOrder))
1661     {
1662       Result = L;
1663       ResultPos = Pos;
1664     }
1665   }
1666
1667   if (Result.Value.getNode()) {
1668     Q.erase(&Q[ResultPos]);
1669     std::make_heap(Q.begin(), Q.end(), WeightedLeaf::Compare);
1670   }
1671
1672   return Result;
1673 }
1674
1675 SDValue HexagonDAGToDAGISel::getMultiplierForSHL(SDNode *N) {
1676   uint64_t MulFactor = 1ull << N->getConstantOperandVal(1);
1677   return CurDAG->getConstant(MulFactor, SDLoc(N),
1678                              N->getOperand(1).getValueType());
1679 }
1680
1681 /// @returns the value x for which 2^x is a factor of Val
1682 static unsigned getPowerOf2Factor(SDValue Val) {
1683   if (Val.getOpcode() == ISD::MUL) {
1684     unsigned MaxFactor = 0;
1685     for (int i = 0; i < 2; ++i) {
1686       ConstantSDNode *C = dyn_cast<ConstantSDNode>(Val.getOperand(i));
1687       if (!C)
1688         continue;
1689       const APInt &CInt = C->getAPIntValue();
1690       if (CInt.getBoolValue())
1691         MaxFactor = CInt.countTrailingZeros();
1692     }
1693     return MaxFactor;
1694   }
1695   if (Val.getOpcode() == ISD::SHL) {
1696     if (!isa<ConstantSDNode>(Val.getOperand(1).getNode()))
1697       return 0;
1698     return (unsigned) Val.getConstantOperandVal(1);
1699   }
1700
1701   return 0;
1702 }
1703
1704 /// @returns true if V>>Amount will eliminate V's operation on its child
1705 static bool willShiftRightEliminate(SDValue V, unsigned Amount) {
1706   if (V.getOpcode() == ISD::MUL) {
1707     SDValue Ops[] = { V.getOperand(0), V.getOperand(1) };
1708     for (int i = 0; i < 2; ++i)
1709       if (isa<ConstantSDNode>(Ops[i].getNode()) &&
1710           V.getConstantOperandVal(i) % (1ULL << Amount) == 0) {
1711         uint64_t NewConst = V.getConstantOperandVal(i) >> Amount;
1712         return (NewConst == 1);
1713       }
1714   } else if (V.getOpcode() == ISD::SHL) {
1715     return (Amount == V.getConstantOperandVal(1));
1716   }
1717
1718   return false;
1719 }
1720
1721 SDValue HexagonDAGToDAGISel::factorOutPowerOf2(SDValue V, unsigned Power) {
1722   SDValue Ops[] = { V.getOperand(0), V.getOperand(1) };
1723   if (V.getOpcode() == ISD::MUL) {
1724     for (int i=0; i < 2; ++i) {
1725       if (isa<ConstantSDNode>(Ops[i].getNode()) &&
1726           V.getConstantOperandVal(i) % ((uint64_t)1 << Power) == 0) {
1727         uint64_t NewConst = V.getConstantOperandVal(i) >> Power;
1728         if (NewConst == 1)
1729           return Ops[!i];
1730         Ops[i] = CurDAG->getConstant(NewConst,
1731                                      SDLoc(V), V.getValueType());
1732         break;
1733       }
1734     }
1735   } else if (V.getOpcode() == ISD::SHL) {
1736     uint64_t ShiftAmount = V.getConstantOperandVal(1);
1737     if (ShiftAmount == Power)
1738       return Ops[0];
1739     Ops[1] = CurDAG->getConstant(ShiftAmount - Power,
1740                                  SDLoc(V), V.getValueType());
1741   }
1742
1743   return CurDAG->getNode(V.getOpcode(), SDLoc(V), V.getValueType(), Ops);
1744 }
1745
1746 static bool isTargetConstant(const SDValue &V) {
1747   return V.getOpcode() == HexagonISD::CONST32 ||
1748          V.getOpcode() == HexagonISD::CONST32_GP;
1749 }
1750
1751 unsigned HexagonDAGToDAGISel::getUsesInFunction(const Value *V) {
1752   if (GAUsesInFunction.count(V))
1753     return GAUsesInFunction[V];
1754
1755   unsigned Result = 0;
1756   const Function *CurF = CurDAG->getMachineFunction().getFunction();
1757   for (const User *U : V->users()) {
1758     if (isa<Instruction>(U) &&
1759         cast<Instruction>(U)->getParent()->getParent() == CurF)
1760       ++Result;
1761   }
1762
1763   GAUsesInFunction[V] = Result;
1764
1765   return Result;
1766 }
1767
1768 /// Note - After calling this, N may be dead. It may have been replaced by a
1769 /// new node, so always use the returned value in place of N.
1770 ///
1771 /// @returns The SDValue taking the place of N (which could be N if it is
1772 /// unchanged)
1773 SDValue HexagonDAGToDAGISel::balanceSubTree(SDNode *N, bool TopLevel) {
1774   assert(RootWeights.count(N) && "Cannot balance non-root node.");
1775   assert(RootWeights[N] != -2 && "This node was RAUW'd!");
1776   assert(!TopLevel || N->getOpcode() == ISD::ADD);
1777
1778   // Return early if this node was already visited
1779   if (RootWeights[N] != -1)
1780     return SDValue(N, 0);
1781
1782   assert(isOpcodeHandled(N));
1783
1784   SDValue Op0 = N->getOperand(0);
1785   SDValue Op1 = N->getOperand(1);
1786
1787   // Return early if the operands will remain unchanged or are all roots
1788   if ((!isOpcodeHandled(Op0.getNode()) || RootWeights.count(Op0.getNode())) &&
1789       (!isOpcodeHandled(Op1.getNode()) || RootWeights.count(Op1.getNode()))) {
1790     SDNode *Op0N = Op0.getNode();
1791     int Weight;
1792     if (isOpcodeHandled(Op0N) && RootWeights[Op0N] == -1) {
1793       Weight = getWeight(balanceSubTree(Op0N).getNode());
1794       // Weight = calculateWeight(Op0N);
1795     } else
1796       Weight = getWeight(Op0N);
1797
1798     SDNode *Op1N = N->getOperand(1).getNode(); // Op1 may have been RAUWd
1799     if (isOpcodeHandled(Op1N) && RootWeights[Op1N] == -1) {
1800       Weight += getWeight(balanceSubTree(Op1N).getNode());
1801       // Weight += calculateWeight(Op1N);
1802     } else
1803       Weight += getWeight(Op1N);
1804
1805     RootWeights[N] = Weight;
1806     RootHeights[N] = std::max(getHeight(N->getOperand(0).getNode()),
1807                               getHeight(N->getOperand(1).getNode())) + 1;
1808
1809     DEBUG(dbgs() << "--> No need to balance root (Weight=" << Weight
1810                  << " Height=" << RootHeights[N] << "): ");
1811     DEBUG(N->dump());
1812
1813     return SDValue(N, 0);
1814   }
1815
1816   DEBUG(dbgs() << "** Balancing root node: ");
1817   DEBUG(N->dump());
1818
1819   unsigned NOpcode = N->getOpcode();
1820
1821   LeafPrioQueue Leaves(NOpcode);
1822   SmallVector<SDValue, 4> Worklist;
1823   Worklist.push_back(SDValue(N, 0));
1824
1825   // SHL nodes will be converted to MUL nodes
1826   if (NOpcode == ISD::SHL)
1827     NOpcode = ISD::MUL;
1828
1829   bool CanFactorize = false;
1830   WeightedLeaf Mul1, Mul2;
1831   unsigned MaxPowerOf2 = 0;
1832   WeightedLeaf GA;
1833
1834   // Do not try to factor out a shift if there is already a shift at the tip of
1835   // the tree.
1836   bool HaveTopLevelShift = false;
1837   if (TopLevel &&
1838       ((isOpcodeHandled(Op0.getNode()) && Op0.getOpcode() == ISD::SHL &&
1839                         Op0.getConstantOperandVal(1) < 4) ||
1840        (isOpcodeHandled(Op1.getNode()) && Op1.getOpcode() == ISD::SHL &&
1841                         Op1.getConstantOperandVal(1) < 4)))
1842     HaveTopLevelShift = true;
1843
1844   // Flatten the subtree into an ordered list of leaves; at the same time
1845   // determine whether the tree is already balanced.
1846   int InsertionOrder = 0;
1847   SmallDenseMap<SDValue, int> NodeHeights;
1848   bool Imbalanced = false;
1849   int CurrentWeight = 0;
1850   while (!Worklist.empty()) {
1851     SDValue Child = Worklist.pop_back_val();
1852
1853     if (Child.getNode() != N && RootWeights.count(Child.getNode())) {
1854       // CASE 1: Child is a root note
1855
1856       int Weight = RootWeights[Child.getNode()];
1857       if (Weight == -1) {
1858         Child = balanceSubTree(Child.getNode());
1859         // calculateWeight(Child.getNode());
1860         Weight = getWeight(Child.getNode());
1861       } else if (Weight == -2) {
1862         // Whoops, this node was RAUWd by one of the balanceSubTree calls we
1863         // made. Our worklist isn't up to date anymore.
1864         // Restart the whole process.
1865         DEBUG(dbgs() << "--> Subtree was RAUWd. Restarting...\n");
1866         return balanceSubTree(N, TopLevel);
1867       }
1868
1869       NodeHeights[Child] = 1;
1870       CurrentWeight += Weight;
1871
1872       unsigned PowerOf2;
1873       if (TopLevel && !CanFactorize && !HaveTopLevelShift &&
1874           (Child.getOpcode() == ISD::MUL || Child.getOpcode() == ISD::SHL) &&
1875           Child.hasOneUse() && (PowerOf2 = getPowerOf2Factor(Child))) {
1876         // Try to identify two factorizable MUL/SHL children greedily. Leave
1877         // them out of the priority queue for now so we can deal with them
1878         // after.
1879         if (!Mul1.Value.getNode()) {
1880           Mul1 = WeightedLeaf(Child, Weight, InsertionOrder++);
1881           MaxPowerOf2 = PowerOf2;
1882         } else {
1883           Mul2 = WeightedLeaf(Child, Weight, InsertionOrder++);
1884           MaxPowerOf2 = std::min(MaxPowerOf2, PowerOf2);
1885
1886           // Our addressing modes can only shift by a maximum of 3
1887           if (MaxPowerOf2 > 3)
1888             MaxPowerOf2 = 3;
1889
1890           CanFactorize = true;
1891         }
1892       } else
1893         Leaves.push(WeightedLeaf(Child, Weight, InsertionOrder++));
1894     } else if (!isOpcodeHandled(Child.getNode())) {
1895       // CASE 2: Child is an unhandled kind of node (e.g. constant)
1896       int Weight = getWeight(Child.getNode());
1897
1898       NodeHeights[Child] = getHeight(Child.getNode());
1899       CurrentWeight += Weight;
1900
1901       if (isTargetConstant(Child) && !GA.Value.getNode())
1902         GA = WeightedLeaf(Child, Weight, InsertionOrder++);
1903       else
1904         Leaves.push(WeightedLeaf(Child, Weight, InsertionOrder++));
1905     } else {
1906       // CASE 3: Child is a subtree of same opcode
1907       // Visit children first, then flatten.
1908       unsigned ChildOpcode = Child.getOpcode();
1909       assert(ChildOpcode == NOpcode ||
1910              (NOpcode == ISD::MUL && ChildOpcode == ISD::SHL));
1911
1912       // Convert SHL to MUL
1913       SDValue Op1;
1914       if (ChildOpcode == ISD::SHL)
1915         Op1 = getMultiplierForSHL(Child.getNode());
1916       else
1917         Op1 = Child->getOperand(1);
1918
1919       if (!NodeHeights.count(Op1) || !NodeHeights.count(Child->getOperand(0))) {
1920         assert(!NodeHeights.count(Child) && "Parent visited before children?");
1921         // Visit children first, then re-visit this node
1922         Worklist.push_back(Child);
1923         Worklist.push_back(Op1);
1924         Worklist.push_back(Child->getOperand(0));
1925       } else {
1926         // Back at this node after visiting the children
1927         if (std::abs(NodeHeights[Op1] - NodeHeights[Child->getOperand(0)]) > 1)
1928           Imbalanced = true;
1929
1930         NodeHeights[Child] = std::max(NodeHeights[Op1],
1931                                       NodeHeights[Child->getOperand(0)]) + 1;
1932       }
1933     }
1934   }
1935
1936   DEBUG(dbgs() << "--> Current height=" << NodeHeights[SDValue(N, 0)]
1937                << " weight=" << CurrentWeight << " imbalanced="
1938                << Imbalanced << "\n");
1939
1940   // Transform MUL(x, C * 2^Y) + SHL(z, Y) -> SHL(ADD(MUL(x, C), z), Y)
1941   //  This factors out a shift in order to match memw(a<<Y+b).
1942   if (CanFactorize && (willShiftRightEliminate(Mul1.Value, MaxPowerOf2) ||
1943                        willShiftRightEliminate(Mul2.Value, MaxPowerOf2))) {
1944     DEBUG(dbgs() << "--> Found common factor for two MUL children!\n");
1945     int Weight = Mul1.Weight + Mul2.Weight;
1946     int Height = std::max(NodeHeights[Mul1.Value], NodeHeights[Mul2.Value]) + 1;
1947     SDValue Mul1Factored = factorOutPowerOf2(Mul1.Value, MaxPowerOf2);
1948     SDValue Mul2Factored = factorOutPowerOf2(Mul2.Value, MaxPowerOf2);
1949     SDValue Sum = CurDAG->getNode(ISD::ADD, SDLoc(N), Mul1.Value.getValueType(),
1950                                   Mul1Factored, Mul2Factored);
1951     SDValue Const = CurDAG->getConstant(MaxPowerOf2, SDLoc(N),
1952                                         Mul1.Value.getValueType());
1953     SDValue New = CurDAG->getNode(ISD::SHL, SDLoc(N), Mul1.Value.getValueType(),
1954                                   Sum, Const);
1955     NodeHeights[New] = Height;
1956     Leaves.push(WeightedLeaf(New, Weight, Mul1.InsertionOrder));
1957   } else if (Mul1.Value.getNode()) {
1958     // We failed to factorize two MULs, so now the Muls are left outside the
1959     // queue... add them back.
1960     Leaves.push(Mul1);
1961     if (Mul2.Value.getNode())
1962       Leaves.push(Mul2);
1963     CanFactorize = false;
1964   }
1965
1966   // Combine GA + Constant -> GA+Offset, but only if GA is not used elsewhere
1967   // and the root node itself is not used more than twice. This reduces the
1968   // amount of additional constant extenders introduced by this optimization.
1969   bool CombinedGA = false;
1970   if (NOpcode == ISD::ADD && GA.Value.getNode() && Leaves.hasConst() &&
1971       GA.Value.hasOneUse() && N->use_size() < 3) {
1972     GlobalAddressSDNode *GANode =
1973       cast<GlobalAddressSDNode>(GA.Value.getOperand(0));
1974     ConstantSDNode *Offset = cast<ConstantSDNode>(Leaves.top().Value);
1975
1976     if (getUsesInFunction(GANode->getGlobal()) == 1 && Offset->hasOneUse() &&
1977         getTargetLowering()->isOffsetFoldingLegal(GANode)) {
1978       DEBUG(dbgs() << "--> Combining GA and offset (" << Offset->getSExtValue()
1979           << "): ");
1980       DEBUG(GANode->dump());
1981
1982       SDValue NewTGA =
1983         CurDAG->getTargetGlobalAddress(GANode->getGlobal(), SDLoc(GA.Value),
1984             GANode->getValueType(0),
1985             GANode->getOffset() + (uint64_t)Offset->getSExtValue());
1986       GA.Value = CurDAG->getNode(GA.Value.getOpcode(), SDLoc(GA.Value),
1987           GA.Value.getValueType(), NewTGA);
1988       GA.Weight += Leaves.top().Weight;
1989
1990       NodeHeights[GA.Value] = getHeight(GA.Value.getNode());
1991       CombinedGA = true;
1992
1993       Leaves.pop(); // Remove the offset constant from the queue
1994     }
1995   }
1996
1997   if ((RebalanceOnlyForOptimizations && !CanFactorize && !CombinedGA) ||
1998       (RebalanceOnlyImbalancedTrees && !Imbalanced)) {
1999     RootWeights[N] = CurrentWeight;
2000     RootHeights[N] = NodeHeights[SDValue(N, 0)];
2001
2002     return SDValue(N, 0);
2003   }
2004
2005   // Combine GA + SHL(x, C<=31) so we will match Rx=add(#u8,asl(Rx,#U5))
2006   if (NOpcode == ISD::ADD && GA.Value.getNode()) {
2007     WeightedLeaf SHL = Leaves.findSHL(31);
2008     if (SHL.Value.getNode()) {
2009       int Height = std::max(NodeHeights[GA.Value], NodeHeights[SHL.Value]) + 1;
2010       GA.Value = CurDAG->getNode(ISD::ADD, SDLoc(GA.Value),
2011                                  GA.Value.getValueType(),
2012                                  GA.Value, SHL.Value);
2013       GA.Weight = SHL.Weight; // Specifically ignore the GA weight here
2014       NodeHeights[GA.Value] = Height;
2015     }
2016   }
2017
2018   if (GA.Value.getNode())
2019     Leaves.push(GA);
2020
2021   // If this is the top level and we haven't factored out a shift, we should try
2022   // to move a constant to the bottom to match addressing modes like memw(rX+C)
2023   if (TopLevel && !CanFactorize && Leaves.hasConst()) {
2024     DEBUG(dbgs() << "--> Pushing constant to tip of tree.");
2025     Leaves.pushToBottom(Leaves.pop());
2026   }
2027
2028   const DataLayout &DL = CurDAG->getDataLayout();
2029   const TargetLowering &TLI = *getTargetLowering();
2030
2031   // Rebuild the tree using Huffman's algorithm
2032   while (Leaves.size() > 1) {
2033     WeightedLeaf L0 = Leaves.pop();
2034
2035     // See whether we can grab a MUL to form an add(Rx,mpyi(Ry,#u6)),
2036     // otherwise just get the next leaf
2037     WeightedLeaf L1 = Leaves.findMULbyConst();
2038     if (!L1.Value.getNode())
2039       L1 = Leaves.pop();
2040
2041     assert(L0.Weight <= L1.Weight && "Priority queue is broken!");
2042
2043     SDValue V0 = L0.Value;
2044     int V0Weight = L0.Weight;
2045     SDValue V1 = L1.Value;
2046     int V1Weight = L1.Weight;
2047
2048     // Make sure that none of these nodes have been RAUW'd
2049     if ((RootWeights.count(V0.getNode()) && RootWeights[V0.getNode()] == -2) ||
2050         (RootWeights.count(V1.getNode()) && RootWeights[V1.getNode()] == -2)) {
2051       DEBUG(dbgs() << "--> Subtree was RAUWd. Restarting...\n");
2052       return balanceSubTree(N, TopLevel);
2053     }
2054
2055     ConstantSDNode *V0C = dyn_cast<ConstantSDNode>(V0);
2056     ConstantSDNode *V1C = dyn_cast<ConstantSDNode>(V1);
2057     EVT VT = N->getValueType(0);
2058     SDValue NewNode;
2059
2060     if (V0C && !V1C) {
2061       std::swap(V0, V1);
2062       std::swap(V0C, V1C);
2063     }
2064
2065     // Calculate height of this node
2066     assert(NodeHeights.count(V0) && NodeHeights.count(V1) &&
2067            "Children must have been visited before re-combining them!");
2068     int Height = std::max(NodeHeights[V0], NodeHeights[V1]) + 1;
2069
2070     // Rebuild this node (and restore SHL from MUL if needed)
2071     if (V1C && NOpcode == ISD::MUL && V1C->getAPIntValue().isPowerOf2())
2072       NewNode = CurDAG->getNode(
2073           ISD::SHL, SDLoc(V0), VT, V0,
2074           CurDAG->getConstant(
2075               V1C->getAPIntValue().logBase2(), SDLoc(N),
2076               TLI.getScalarShiftAmountTy(DL, V0.getValueType())));
2077     else
2078       NewNode = CurDAG->getNode(NOpcode, SDLoc(N), VT, V0, V1);
2079
2080     NodeHeights[NewNode] = Height;
2081
2082     int Weight = V0Weight + V1Weight;
2083     Leaves.push(WeightedLeaf(NewNode, Weight, L0.InsertionOrder));
2084
2085     DEBUG(dbgs() << "--> Built new node (Weight=" << Weight << ",Height="
2086                  << Height << "):\n");
2087     DEBUG(NewNode.dump());
2088   }
2089
2090   assert(Leaves.size() == 1);
2091   SDValue NewRoot = Leaves.top().Value;
2092
2093   assert(NodeHeights.count(NewRoot));
2094   int Height = NodeHeights[NewRoot];
2095
2096   // Restore SHL if we earlier converted it to a MUL
2097   if (NewRoot.getOpcode() == ISD::MUL) {
2098     ConstantSDNode *V1C = dyn_cast<ConstantSDNode>(NewRoot.getOperand(1));
2099     if (V1C && V1C->getAPIntValue().isPowerOf2()) {
2100       EVT VT = NewRoot.getValueType();
2101       SDValue V0 = NewRoot.getOperand(0);
2102       NewRoot = CurDAG->getNode(
2103           ISD::SHL, SDLoc(NewRoot), VT, V0,
2104           CurDAG->getConstant(
2105               V1C->getAPIntValue().logBase2(), SDLoc(NewRoot),
2106               TLI.getScalarShiftAmountTy(DL, V0.getValueType())));
2107     }
2108   }
2109
2110   if (N != NewRoot.getNode()) {
2111     DEBUG(dbgs() << "--> Root is now: ");
2112     DEBUG(NewRoot.dump());
2113
2114     // Replace all uses of old root by new root
2115     CurDAG->ReplaceAllUsesWith(N, NewRoot.getNode());
2116     // Mark that we have RAUW'd N
2117     RootWeights[N] = -2;
2118   } else {
2119     DEBUG(dbgs() << "--> Root unchanged.\n");
2120   }
2121
2122   RootWeights[NewRoot.getNode()] = Leaves.top().Weight;
2123   RootHeights[NewRoot.getNode()] = Height;
2124
2125   return NewRoot;
2126 }
2127
2128 void HexagonDAGToDAGISel::rebalanceAddressTrees() {
2129   for (auto I = CurDAG->allnodes_begin(), E = CurDAG->allnodes_end(); I != E;) {
2130     SDNode *N = &*I++;
2131     if (N->getOpcode() != ISD::LOAD && N->getOpcode() != ISD::STORE)
2132       continue;
2133
2134     SDValue BasePtr = cast<MemSDNode>(N)->getBasePtr();
2135     if (BasePtr.getOpcode() != ISD::ADD)
2136       continue;
2137
2138     // We've already processed this node
2139     if (RootWeights.count(BasePtr.getNode()))
2140       continue;
2141
2142     DEBUG(dbgs() << "** Rebalancing address calculation in node: ");
2143     DEBUG(N->dump());
2144
2145     // FindRoots
2146     SmallVector<SDNode *, 4> Worklist;
2147
2148     Worklist.push_back(BasePtr.getOperand(0).getNode());
2149     Worklist.push_back(BasePtr.getOperand(1).getNode());
2150
2151     while (!Worklist.empty()) {
2152       SDNode *N = Worklist.pop_back_val();
2153       unsigned Opcode = N->getOpcode();
2154
2155       if (!isOpcodeHandled(N))
2156         continue;
2157
2158       Worklist.push_back(N->getOperand(0).getNode());
2159       Worklist.push_back(N->getOperand(1).getNode());
2160
2161       // Not a root if it has only one use and same opcode as its parent
2162       if (N->hasOneUse() && Opcode == N->use_begin()->getOpcode())
2163         continue;
2164
2165       // This root node has already been processed
2166       if (RootWeights.count(N))
2167         continue;
2168
2169       RootWeights[N] = -1;
2170     }
2171
2172     // Balance node itself
2173     RootWeights[BasePtr.getNode()] = -1;
2174     SDValue NewBasePtr = balanceSubTree(BasePtr.getNode(), /*TopLevel=*/ true);
2175
2176     if (N->getOpcode() == ISD::LOAD)
2177       N = CurDAG->UpdateNodeOperands(N, N->getOperand(0),
2178             NewBasePtr, N->getOperand(2));
2179     else
2180       N = CurDAG->UpdateNodeOperands(N, N->getOperand(0), N->getOperand(1),
2181             NewBasePtr, N->getOperand(3));
2182
2183     DEBUG(dbgs() << "--> Final node: ");
2184     DEBUG(N->dump());
2185   }
2186
2187   CurDAG->RemoveDeadNodes();
2188   GAUsesInFunction.clear();
2189   RootHeights.clear();
2190   RootWeights.clear();
2191 }
2192