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   void PreprocessISelDAG() override;
  75   void EmitFunctionEntryCode() override;
  76
  77   void Select(SDNode *N) override;
  78
  79   // Complex Pattern Selectors.
  80   inline bool SelectAddrGA(SDValue &N, SDValue &R);
  81   inline bool SelectAddrGP(SDValue &N, SDValue &R);
  82   bool SelectGlobalAddress(SDValue &N, SDValue &R, bool UseGP);
  83   bool SelectAddrFI(SDValue &N, SDValue &R);
  84
  85   StringRef getPassName() const override {
  86     return "Hexagon DAG->DAG Pattern Instruction Selection";
  87   }
  88
  89   // Generate a machine instruction node corresponding to the circ/brev
  90   // load intrinsic.
  91   MachineSDNode *LoadInstrForLoadIntrinsic(SDNode *IntN);
  92   // Given the circ/brev load intrinsic and the already generated machine
  93   // instruction, generate the appropriate store (that is a part of the
  94   // intrinsic's functionality).
  95   SDNode *StoreInstrForLoadIntrinsic(MachineSDNode *LoadN, SDNode *IntN);
  96
  97   void SelectFrameIndex(SDNode *N);
  98   /// SelectInlineAsmMemoryOperand - Implement addressing mode selection for
  99   /// inline asm expressions.
 100   bool SelectInlineAsmMemoryOperand(const SDValue &Op,
 101                                     unsigned ConstraintID,
 102                                     std::vector<SDValue> &OutOps) override;
 103   bool tryLoadOfLoadIntrinsic(LoadSDNode *N);
 104   void SelectLoad(SDNode *N);
 105   void SelectIndexedLoad(LoadSDNode *LD, const SDLoc &dl);
 106   void SelectIndexedStore(StoreSDNode *ST, const SDLoc &dl);
 107   void SelectStore(SDNode *N);
 108   void SelectSHL(SDNode *N);
 109   void SelectMul(SDNode *N);
 110   void SelectZeroExtend(SDNode *N);
 111   void SelectIntrinsicWChain(SDNode *N);
 112   void SelectIntrinsicWOChain(SDNode *N);
 113   void SelectConstant(SDNode *N);
 114   void SelectConstantFP(SDNode *N);
 115   void SelectBitcast(SDNode *N);
 116
 117   // Include the pieces autogenerated from the target description.
 118   #include "HexagonGenDAGISel.inc"
 119
 120 private:
 121   bool isValueExtension(const SDValue &Val, unsigned FromBits, SDValue &Src);
 122   bool isOrEquivalentToAdd(const SDNode *N) const;
 123   bool isAlignedMemNode(const MemSDNode *N) const;
 124   bool isPositiveHalfWord(const SDNode *N) const;
 125
 126   // DAG preprocessing functions.
 127   void ppSimplifyOrSelect0(std::vector<SDNode*> &&Nodes);
 128   void ppAddrReorderAddShl(std::vector<SDNode*> &&Nodes);
 129   void ppAddrRewriteAndSrl(std::vector<SDNode*> &&Nodes);
 130   void ppHoistZextI1(std::vector<SDNode*> &&Nodes);
 131
 132   SmallDenseMap<SDNode *,int> RootWeights;
 133   SmallDenseMap<SDNode *,int> RootHeights;
 134   SmallDenseMap<const Value *,int> GAUsesInFunction;
 135   int getWeight(SDNode *N);
 136   int getHeight(SDNode *N);
 137   SDValue getMultiplierForSHL(SDNode *N);
 138   SDValue factorOutPowerOf2(SDValue V, unsigned Power);
 139   unsigned getUsesInFunction(const Value *V);
 140   SDValue balanceSubTree(SDNode *N, bool Factorize = false);
 141   void rebalanceAddressTrees();
 142 }; // end HexagonDAGToDAGISel
 143 }  // end anonymous namespace
 144
 145
 146 /// createHexagonISelDag - This pass converts a legalized DAG into a
 147 /// Hexagon-specific DAG, ready for instruction scheduling.
 148 ///
 149 namespace llvm {
 150 FunctionPass *createHexagonISelDag(HexagonTargetMachine &TM,
 151                                    CodeGenOpt::Level OptLevel) {
 152   return new HexagonDAGToDAGISel(TM, OptLevel);
 153 }
 154 }
 155
 156 // Intrinsics that return a a predicate.
 157 static bool doesIntrinsicReturnPredicate(unsigned ID) {
 158   switch (ID) {
 159     default:
 160       return false;
 161     case Intrinsic::hexagon_C2_cmpeq:
 162     case Intrinsic::hexagon_C2_cmpgt:
 163     case Intrinsic::hexagon_C2_cmpgtu:
 164     case Intrinsic::hexagon_C2_cmpgtup:
 165     case Intrinsic::hexagon_C2_cmpgtp:
 166     case Intrinsic::hexagon_C2_cmpeqp:
 167     case Intrinsic::hexagon_C2_bitsset:
 168     case Intrinsic::hexagon_C2_bitsclr:
 169     case Intrinsic::hexagon_C2_cmpeqi:
 170     case Intrinsic::hexagon_C2_cmpgti:
 171     case Intrinsic::hexagon_C2_cmpgtui:
 172     case Intrinsic::hexagon_C2_cmpgei:
 173     case Intrinsic::hexagon_C2_cmpgeui:
 174     case Intrinsic::hexagon_C2_cmplt:
 175     case Intrinsic::hexagon_C2_cmpltu:
 176     case Intrinsic::hexagon_C2_bitsclri:
 177     case Intrinsic::hexagon_C2_and:
 178     case Intrinsic::hexagon_C2_or:
 179     case Intrinsic::hexagon_C2_xor:
 180     case Intrinsic::hexagon_C2_andn:
 181     case Intrinsic::hexagon_C2_not:
 182     case Intrinsic::hexagon_C2_orn:
 183     case Intrinsic::hexagon_C2_pxfer_map:
 184     case Intrinsic::hexagon_C2_any8:
 185     case Intrinsic::hexagon_C2_all8:
 186     case Intrinsic::hexagon_A2_vcmpbeq:
 187     case Intrinsic::hexagon_A2_vcmpbgtu:
 188     case Intrinsic::hexagon_A2_vcmpheq:
 189     case Intrinsic::hexagon_A2_vcmphgt:
 190     case Intrinsic::hexagon_A2_vcmphgtu:
 191     case Intrinsic::hexagon_A2_vcmpweq:
 192     case Intrinsic::hexagon_A2_vcmpwgt:
 193     case Intrinsic::hexagon_A2_vcmpwgtu:
 194     case Intrinsic::hexagon_C2_tfrrp:
 195     case Intrinsic::hexagon_S2_tstbit_i:
 196     case Intrinsic::hexagon_S2_tstbit_r:
 197       return true;
 198   }
 199 }
 200
 201 void HexagonDAGToDAGISel::SelectIndexedLoad(LoadSDNode *LD, const SDLoc &dl) {
 202   SDValue Chain = LD->getChain();
 203   SDValue Base = LD->getBasePtr();
 204   SDValue Offset = LD->getOffset();
 205   int32_t Inc = cast<ConstantSDNode>(Offset.getNode())->getSExtValue();
 206   EVT LoadedVT = LD->getMemoryVT();
 207   unsigned Opcode = 0;
 208
 209   // Check for zero extended loads. Treat any-extend loads as zero extended
 210   // loads.
 211   ISD::LoadExtType ExtType = LD->getExtensionType();
 212   bool IsZeroExt = (ExtType == ISD::ZEXTLOAD || ExtType == ISD::EXTLOAD);
 213   bool IsValidInc = HII->isValidAutoIncImm(LoadedVT, Inc);
 214
 215   assert(LoadedVT.isSimple());
 216   switch (LoadedVT.getSimpleVT().SimpleTy) {
 217   case MVT::i8:
 218     if (IsZeroExt)
 219       Opcode = IsValidInc ? Hexagon::L2_loadrub_pi : Hexagon::L2_loadrub_io;
 220     else
 221       Opcode = IsValidInc ? Hexagon::L2_loadrb_pi : Hexagon::L2_loadrb_io;
 222     break;
 223   case MVT::i16:
 224     if (IsZeroExt)
 225       Opcode = IsValidInc ? Hexagon::L2_loadruh_pi : Hexagon::L2_loadruh_io;
 226     else
 227       Opcode = IsValidInc ? Hexagon::L2_loadrh_pi : Hexagon::L2_loadrh_io;
 228     break;
 229   case MVT::i32:
 230     Opcode = IsValidInc ? Hexagon::L2_loadri_pi : Hexagon::L2_loadri_io;
 231     break;
 232   case MVT::i64:
 233     Opcode = IsValidInc ? Hexagon::L2_loadrd_pi : Hexagon::L2_loadrd_io;
 234     break;
 235   // 64B
 236   case MVT::v64i8:
 237   case MVT::v32i16:
 238   case MVT::v16i32:
 239   case MVT::v8i64:
 240     if (isAlignedMemNode(LD))
 241       Opcode = IsValidInc ? Hexagon::V6_vL32b_pi : Hexagon::V6_vL32b_ai;
 242     else
 243       Opcode = IsValidInc ? Hexagon::V6_vL32Ub_pi : Hexagon::V6_vL32Ub_ai;
 244     break;
 245   // 128B
 246   case MVT::v128i8:
 247   case MVT::v64i16:
 248   case MVT::v32i32:
 249   case MVT::v16i64:
 250     if (isAlignedMemNode(LD))
 251       Opcode = IsValidInc ? Hexagon::V6_vL32b_pi_128B
 252                           : Hexagon::V6_vL32b_ai_128B;
 253     else
 254       Opcode = IsValidInc ? Hexagon::V6_vL32Ub_pi_128B
 255                           : Hexagon::V6_vL32Ub_ai_128B;
 256     break;
 257   default:
 258     llvm_unreachable("Unexpected memory type in indexed load");
 259   }
 260
 261   SDValue IncV = CurDAG->getTargetConstant(Inc, dl, MVT::i32);
 262   MachineSDNode::mmo_iterator MemOp = MF->allocateMemRefsArray(1);
 263   MemOp[0] = LD->getMemOperand();
 264
 265   auto getExt64 = [this,ExtType] (MachineSDNode *N, const SDLoc &dl)
 266         -> MachineSDNode* {
 267     if (ExtType == ISD::ZEXTLOAD || ExtType == ISD::EXTLOAD) {
 268       SDValue Zero = CurDAG->getTargetConstant(0, dl, MVT::i32);
 269       return CurDAG->getMachineNode(Hexagon::A4_combineir, dl, MVT::i64,
 270                                     Zero, SDValue(N, 0));
 271     }
 272     if (ExtType == ISD::SEXTLOAD)
 273       return CurDAG->getMachineNode(Hexagon::A2_sxtw, dl, MVT::i64,
 274                                     SDValue(N, 0));
 275     return N;
 276   };
 277
 278   //                  Loaded value   Next address   Chain
 279   SDValue From[3] = { SDValue(LD,0), SDValue(LD,1), SDValue(LD,2) };
 280   SDValue To[3];
 281
 282   EVT ValueVT = LD->getValueType(0);
 283   if (ValueVT == MVT::i64 && ExtType != ISD::NON_EXTLOAD) {
 284     // A load extending to i64 will actually produce i32, which will then
 285     // need to be extended to i64.
 286     assert(LoadedVT.getSizeInBits() <= 32);
 287     ValueVT = MVT::i32;
 288   }
 289
 290   if (IsValidInc) {
 291     MachineSDNode *L = CurDAG->getMachineNode(Opcode, dl, ValueVT,
 292                                               MVT::i32, MVT::Other, Base,
 293                                               IncV, Chain);
 294     L->setMemRefs(MemOp, MemOp+1);
 295     To[1] = SDValue(L, 1); // Next address.
 296     To[2] = SDValue(L, 2); // Chain.
 297     // Handle special case for extension to i64.
 298     if (LD->getValueType(0) == MVT::i64)
 299       L = getExt64(L, dl);
 300     To[0] = SDValue(L, 0); // Loaded (extended) value.
 301   } else {
 302     SDValue Zero = CurDAG->getTargetConstant(0, dl, MVT::i32);
 303     MachineSDNode *L = CurDAG->getMachineNode(Opcode, dl, ValueVT, MVT::Other,
 304                                               Base, Zero, Chain);
 305     L->setMemRefs(MemOp, MemOp+1);
 306     To[2] = SDValue(L, 1); // Chain.
 307     MachineSDNode *A = CurDAG->getMachineNode(Hexagon::A2_addi, dl, MVT::i32,
 308                                               Base, IncV);
 309     To[1] = SDValue(A, 0); // Next address.
 310     // Handle special case for extension to i64.
 311     if (LD->getValueType(0) == MVT::i64)
 312       L = getExt64(L, dl);
 313     To[0] = SDValue(L, 0); // Loaded (extended) value.
 314   }
 315   ReplaceUses(From, To, 3);
 316   CurDAG->RemoveDeadNode(LD);
 317 }
 318
 319
 320 MachineSDNode *HexagonDAGToDAGISel::LoadInstrForLoadIntrinsic(SDNode *IntN) {
 321   if (IntN->getOpcode() != ISD::INTRINSIC_W_CHAIN)
 322     return nullptr;
 323
 324   SDLoc dl(IntN);
 325   unsigned IntNo = cast<ConstantSDNode>(IntN->getOperand(1))->getZExtValue();
 326
 327   static std::map<unsigned,unsigned> LoadPciMap = {
 328     { Intrinsic::hexagon_circ_ldb,  Hexagon::L2_loadrb_pci  },
 329     { Intrinsic::hexagon_circ_ldub, Hexagon::L2_loadrub_pci },
 330     { Intrinsic::hexagon_circ_ldh,  Hexagon::L2_loadrh_pci  },
 331     { Intrinsic::hexagon_circ_lduh, Hexagon::L2_loadruh_pci },
 332     { Intrinsic::hexagon_circ_ldw,  Hexagon::L2_loadri_pci  },
 333     { Intrinsic::hexagon_circ_ldd,  Hexagon::L2_loadrd_pci  },
 334   };
 335   auto FLC = LoadPciMap.find(IntNo);
 336   if (FLC != LoadPciMap.end()) {
 337     SDNode *Mod = CurDAG->getMachineNode(Hexagon::A2_tfrrcr, dl, MVT::i32,
 338           IntN->getOperand(4));
 339     EVT ValTy = (IntNo == Intrinsic::hexagon_circ_ldd) ? MVT::i64 : MVT::i32;
 340     EVT RTys[] = { ValTy, MVT::i32, MVT::Other };
 341     // Operands: { Base, Increment, Modifier, Chain }
 342     auto Inc = cast<ConstantSDNode>(IntN->getOperand(5));
 343     SDValue I = CurDAG->getTargetConstant(Inc->getSExtValue(), dl, MVT::i32);
 344     MachineSDNode *Res = CurDAG->getMachineNode(FLC->second, dl, RTys,
 345           { IntN->getOperand(2), I, SDValue(Mod,0), IntN->getOperand(0) });
 346     return Res;
 347   }
 348
 349   static std::map<unsigned,unsigned> LoadPbrMap = {
 350     { Intrinsic::hexagon_brev_ldb,  Hexagon::L2_loadrb_pbr  },
 351     { Intrinsic::hexagon_brev_ldub, Hexagon::L2_loadrub_pbr },
 352     { Intrinsic::hexagon_brev_ldh,  Hexagon::L2_loadrh_pbr  },
 353     { Intrinsic::hexagon_brev_lduh, Hexagon::L2_loadruh_pbr },
 354     { Intrinsic::hexagon_brev_ldw,  Hexagon::L2_loadri_pbr  },
 355     { Intrinsic::hexagon_brev_ldd,  Hexagon::L2_loadrd_pbr  },
 356   };
 357   auto FLB = LoadPbrMap.find(IntNo);
 358   if (FLB != LoadPbrMap.end()) {
 359     SDNode *Mod = CurDAG->getMachineNode(Hexagon::A2_tfrrcr, dl, MVT::i32,
 360             IntN->getOperand(4));
 361     EVT ValTy = (IntNo == Intrinsic::hexagon_brev_ldd) ? MVT::i64 : MVT::i32;
 362     EVT RTys[] = { ValTy, MVT::i32, MVT::Other };
 363     // Operands: { Base, Modifier, Chain }
 364     MachineSDNode *Res = CurDAG->getMachineNode(FLB->second, dl, RTys,
 365           { IntN->getOperand(2), SDValue(Mod,0), IntN->getOperand(0) });
 366     return Res;
 367   }
 368
 369   return nullptr;
 370 }
 371
 372 SDNode *HexagonDAGToDAGISel::StoreInstrForLoadIntrinsic(MachineSDNode *LoadN,
 373       SDNode *IntN) {
 374   // The "LoadN" is just a machine load instruction. The intrinsic also
 375   // involves storing it. Generate an appropriate store to the location
 376   // given in the intrinsic's operand(3).
 377   uint64_t F = HII->get(LoadN->getMachineOpcode()).TSFlags;
 378   unsigned SizeBits = (F >> HexagonII::MemAccessSizePos) &
 379                       HexagonII::MemAccesSizeMask;
 380   unsigned Size = 1U << (SizeBits-1);
 381
 382   SDLoc dl(IntN);
 383   MachinePointerInfo PI;
 384   SDValue TS;
 385   SDValue Loc = IntN->getOperand(3);
 386
 387   if (Size >= 4)
 388     TS = CurDAG->getStore(SDValue(LoadN, 2), dl, SDValue(LoadN, 0), Loc, PI,
 389                           Size);
 390   else
 391     TS = CurDAG->getTruncStore(SDValue(LoadN, 2), dl, SDValue(LoadN, 0), Loc,
 392                                PI, MVT::getIntegerVT(Size * 8), Size);
 393
 394   SDNode *StoreN;
 395   {
 396     HandleSDNode Handle(TS);
 397     SelectStore(TS.getNode());
 398     StoreN = Handle.getValue().getNode();
 399   }
 400
 401   // Load's results are { Loaded value, Updated pointer, Chain }
 402   ReplaceUses(SDValue(IntN, 0), SDValue(LoadN, 1));
 403   ReplaceUses(SDValue(IntN, 1), SDValue(StoreN, 0));
 404   return StoreN;
 405 }
 406
 407 bool HexagonDAGToDAGISel::tryLoadOfLoadIntrinsic(LoadSDNode *N) {
 408   // The intrinsics for load circ/brev perform two operations:
 409   // 1. Load a value V from the specified location, using the addressing
 410   //    mode corresponding to the intrinsic.
 411   // 2. Store V into a specified location. This location is typically a
 412   //    local, temporary object.
 413   // In many cases, the program using these intrinsics will immediately
 414   // load V again from the local object. In those cases, when certain
 415   // conditions are met, the last load can be removed.
 416   // This function identifies and optimizes this pattern. If the pattern
 417   // cannot be optimized, it returns nullptr, which will cause the load
 418   // to be selected separately from the intrinsic (which will be handled
 419   // in SelectIntrinsicWChain).
 420
 421   SDValue Ch = N->getOperand(0);
 422   SDValue Loc = N->getOperand(1);
 423
 424   // Assume that the load and the intrinsic are connected directly with a
 425   // chain:
 426   //   t1: i32,ch = int.load ..., ..., ..., Loc, ...    // <-- C
 427   //   t2: i32,ch = load t1:1, Loc, ...
 428   SDNode *C = Ch.getNode();
 429
 430   if (C->getOpcode() != ISD::INTRINSIC_W_CHAIN)
 431     return false;
 432
 433   // The second load can only be eliminated if its extension type matches
 434   // that of the load instruction corresponding to the intrinsic. The user
 435   // can provide an address of an unsigned variable to store the result of
 436   // a sign-extending intrinsic into (or the other way around).
 437   ISD::LoadExtType IntExt;
 438   switch (cast<ConstantSDNode>(C->getOperand(1))->getZExtValue()) {
 439     case Intrinsic::hexagon_brev_ldub:
 440     case Intrinsic::hexagon_brev_lduh:
 441     case Intrinsic::hexagon_circ_ldub:
 442     case Intrinsic::hexagon_circ_lduh:
 443       IntExt = ISD::ZEXTLOAD;
 444       break;
 445     case Intrinsic::hexagon_brev_ldw:
 446     case Intrinsic::hexagon_brev_ldd:
 447     case Intrinsic::hexagon_circ_ldw:
 448     case Intrinsic::hexagon_circ_ldd:
 449       IntExt = ISD::NON_EXTLOAD;
 450       break;
 451     default:
 452       IntExt = ISD::SEXTLOAD;
 453       break;
 454   }
 455   if (N->getExtensionType() != IntExt)
 456     return false;
 457
 458   // Make sure the target location for the loaded value in the load intrinsic
 459   // is the location from which LD (or N) is loading.
 460   if (C->getNumOperands() < 4 || Loc.getNode() != C->getOperand(3).getNode())
 461     return false;
 462
 463   if (MachineSDNode *L = LoadInstrForLoadIntrinsic(C)) {
 464     SDNode *S = StoreInstrForLoadIntrinsic(L, C);
 465     SDValue F[] = { SDValue(N,0), SDValue(N,1), SDValue(C,0), SDValue(C,1) };
 466     SDValue T[] = { SDValue(L,0), SDValue(S,0), SDValue(L,1), SDValue(S,0) };
 467     ReplaceUses(F, T, array_lengthof(T));
 468     // This transformation will leave the intrinsic dead. If it remains in
 469     // the DAG, the selection code will see it again, but without the load,
 470     // and it will generate a store that is normally required for it.
 471     CurDAG->RemoveDeadNode(C);
 472     return true;
 473   }
 474
 475   return false;
 476 }
 477
 478 void HexagonDAGToDAGISel::SelectLoad(SDNode *N) {
 479   SDLoc dl(N);
 480   LoadSDNode *LD = cast<LoadSDNode>(N);
 481   ISD::MemIndexedMode AM = LD->getAddressingMode();
 482
 483   // Handle indexed loads.
 484   if (AM != ISD::UNINDEXED) {
 485     SelectIndexedLoad(LD, dl);
 486     return;
 487   }
 488
 489   // Handle patterns using circ/brev load intrinsics.
 490   if (tryLoadOfLoadIntrinsic(LD))
 491     return;
 492
 493   SelectCode(LD);
 494 }
 495
 496 void HexagonDAGToDAGISel::SelectIndexedStore(StoreSDNode *ST, const SDLoc &dl) {
 497   SDValue Chain = ST->getChain();
 498   SDValue Base = ST->getBasePtr();
 499   SDValue Offset = ST->getOffset();
 500   SDValue Value = ST->getValue();
 501   // Get the constant value.
 502   int32_t Inc = cast<ConstantSDNode>(Offset.getNode())->getSExtValue();
 503   EVT StoredVT = ST->getMemoryVT();
 504   EVT ValueVT = Value.getValueType();
 505
 506   bool IsValidInc = HII->isValidAutoIncImm(StoredVT, Inc);
 507   unsigned Opcode = 0;
 508
 509   assert(StoredVT.isSimple());
 510   switch (StoredVT.getSimpleVT().SimpleTy) {
 511   case MVT::i8:
 512     Opcode = IsValidInc ? Hexagon::S2_storerb_pi : Hexagon::S2_storerb_io;
 513     break;
 514   case MVT::i16:
 515     Opcode = IsValidInc ? Hexagon::S2_storerh_pi : Hexagon::S2_storerh_io;
 516     break;
 517   case MVT::i32:
 518     Opcode = IsValidInc ? Hexagon::S2_storeri_pi : Hexagon::S2_storeri_io;
 519     break;
 520   case MVT::i64:
 521     Opcode = IsValidInc ? Hexagon::S2_storerd_pi : Hexagon::S2_storerd_io;
 522     break;
 523   // 64B
 524   case MVT::v64i8:
 525   case MVT::v32i16:
 526   case MVT::v16i32:
 527   case MVT::v8i64:
 528     if (isAlignedMemNode(ST))
 529       Opcode = IsValidInc ? Hexagon::V6_vS32b_pi : Hexagon::V6_vS32b_ai;
 530     else
 531       Opcode = IsValidInc ? Hexagon::V6_vS32Ub_pi : Hexagon::V6_vS32Ub_ai;
 532     break;
 533   // 128B
 534   case MVT::v128i8:
 535   case MVT::v64i16:
 536   case MVT::v32i32:
 537   case MVT::v16i64:
 538     if (isAlignedMemNode(ST))
 539       Opcode = IsValidInc ? Hexagon::V6_vS32b_pi_128B
 540                           : Hexagon::V6_vS32b_ai_128B;
 541     else
 542       Opcode = IsValidInc ? Hexagon::V6_vS32Ub_pi_128B
 543                           : Hexagon::V6_vS32Ub_ai_128B;
 544     break;
 545   default:
 546     llvm_unreachable("Unexpected memory type in indexed store");
 547   }
 548
 549   if (ST->isTruncatingStore() && ValueVT.getSizeInBits() == 64) {
 550     assert(StoredVT.getSizeInBits() < 64 && "Not a truncating store");
 551     Value = CurDAG->getTargetExtractSubreg(Hexagon::isub_lo,
 552                                            dl, MVT::i32, Value);
 553   }
 554
 555   SDValue IncV = CurDAG->getTargetConstant(Inc, dl, MVT::i32);
 556   MachineSDNode::mmo_iterator MemOp = MF->allocateMemRefsArray(1);
 557   MemOp[0] = ST->getMemOperand();
 558
 559   //                  Next address   Chain
 560   SDValue From[2] = { SDValue(ST,0), SDValue(ST,1) };
 561   SDValue To[2];
 562
 563   if (IsValidInc) {
 564     // Build post increment store.
 565     SDValue Ops[] = { Base, IncV, Value, Chain };
 566     MachineSDNode *S = CurDAG->getMachineNode(Opcode, dl, MVT::i32, MVT::Other,
 567                                               Ops);
 568     S->setMemRefs(MemOp, MemOp + 1);
 569     To[0] = SDValue(S, 0);
 570     To[1] = SDValue(S, 1);
 571   } else {
 572     SDValue Zero = CurDAG->getTargetConstant(0, dl, MVT::i32);
 573     SDValue Ops[] = { Base, Zero, Value, Chain };
 574     MachineSDNode *S = CurDAG->getMachineNode(Opcode, dl, MVT::Other, Ops);
 575     S->setMemRefs(MemOp, MemOp + 1);
 576     To[1] = SDValue(S, 0);
 577     MachineSDNode *A = CurDAG->getMachineNode(Hexagon::A2_addi, dl, MVT::i32,
 578                                               Base, IncV);
 579     To[0] = SDValue(A, 0);
 580   }
 581
 582   ReplaceUses(From, To, 2);
 583   CurDAG->RemoveDeadNode(ST);
 584 }
 585
 586 void HexagonDAGToDAGISel::SelectStore(SDNode *N) {
 587   SDLoc dl(N);
 588   StoreSDNode *ST = cast<StoreSDNode>(N);
 589   ISD::MemIndexedMode AM = ST->getAddressingMode();
 590
 591   // Handle indexed stores.
 592   if (AM != ISD::UNINDEXED) {
 593     SelectIndexedStore(ST, dl);
 594     return;
 595   }
 596
 597   SelectCode(ST);
 598 }
 599
 600 void HexagonDAGToDAGISel::SelectMul(SDNode *N) {
 601   SDLoc dl(N);
 602
 603   // %conv.i = sext i32 %tmp1 to i64
 604   // %conv2.i = sext i32 %add to i64
 605   // %mul.i = mul nsw i64 %conv2.i, %conv.i
 606   //
 607   //   --- match with the following ---
 608   //
 609   // %mul.i = mpy (%tmp1, %add)
 610   //
 611
 612   if (N->getValueType(0) == MVT::i64) {
 613     // Shifting a i64 signed multiply.
 614     SDValue MulOp0 = N->getOperand(0);
 615     SDValue MulOp1 = N->getOperand(1);
 616
 617     SDValue OP0;
 618     SDValue OP1;
 619
 620     // Handle sign_extend and sextload.
 621     if (MulOp0.getOpcode() == ISD::SIGN_EXTEND) {
 622       SDValue Sext0 = MulOp0.getOperand(0);
 623       if (Sext0.getNode()->getValueType(0) != MVT::i32) {
 624         SelectCode(N);
 625         return;
 626       }
 627       OP0 = Sext0;
 628     } else if (MulOp0.getOpcode() == ISD::LOAD) {
 629       LoadSDNode *LD = cast<LoadSDNode>(MulOp0.getNode());
 630       if (LD->getMemoryVT() != MVT::i32 ||
 631           LD->getExtensionType() != ISD::SEXTLOAD ||
 632           LD->getAddressingMode() != ISD::UNINDEXED) {
 633         SelectCode(N);
 634         return;
 635       }
 636       SDValue Chain = LD->getChain();
 637       SDValue TargetConst0 = CurDAG->getTargetConstant(0, dl, MVT::i32);
 638       OP0 = SDValue(CurDAG->getMachineNode(Hexagon::L2_loadri_io, dl, MVT::i32,
 639                                             MVT::Other,
 640                                             LD->getBasePtr(), TargetConst0,
 641                                             Chain), 0);
 642     } else {
 643       SelectCode(N);
 644       return;
 645     }
 646
 647     // Same goes for the second operand.
 648     if (MulOp1.getOpcode() == ISD::SIGN_EXTEND) {
 649       SDValue Sext1 = MulOp1.getOperand(0);
 650       if (Sext1.getNode()->getValueType(0) != MVT::i32) {
 651         SelectCode(N);
 652         return;
 653       }
 654       OP1 = Sext1;
 655     } else if (MulOp1.getOpcode() == ISD::LOAD) {
 656       LoadSDNode *LD = cast<LoadSDNode>(MulOp1.getNode());
 657       if (LD->getMemoryVT() != MVT::i32 ||
 658           LD->getExtensionType() != ISD::SEXTLOAD ||
 659           LD->getAddressingMode() != ISD::UNINDEXED) {
 660         SelectCode(N);
 661         return;
 662       }
 663       SDValue Chain = LD->getChain();
 664       SDValue TargetConst0 = CurDAG->getTargetConstant(0, dl, MVT::i32);
 665       OP1 = SDValue(CurDAG->getMachineNode(Hexagon::L2_loadri_io, dl, MVT::i32,
 666                                             MVT::Other,
 667                                             LD->getBasePtr(), TargetConst0,
 668                                             Chain), 0);
 669     } else {
 670       SelectCode(N);
 671       return;
 672     }
 673
 674     // Generate a mpy instruction.
 675     SDNode *Result = CurDAG->getMachineNode(Hexagon::M2_dpmpyss_s0, dl,
 676                                             MVT::i64, OP0, OP1);
 677     ReplaceNode(N, Result);
 678     return;
 679   }
 680
 681   SelectCode(N);
 682 }
 683
 684 void HexagonDAGToDAGISel::SelectSHL(SDNode *N) {
 685   SDLoc dl(N);
 686   SDValue Shl_0 = N->getOperand(0);
 687   SDValue Shl_1 = N->getOperand(1);
 688
 689   auto Default = [this,N] () -> void { SelectCode(N); };
 690
 691   if (N->getValueType(0) != MVT::i32 || Shl_1.getOpcode() != ISD::Constant)
 692     return Default();
 693
 694   // RHS is const.
 695   int32_t ShlConst = cast<ConstantSDNode>(Shl_1)->getSExtValue();
 696
 697   if (Shl_0.getOpcode() == ISD::MUL) {
 698     SDValue Mul_0 = Shl_0.getOperand(0); // Val
 699     SDValue Mul_1 = Shl_0.getOperand(1); // Const
 700     // RHS of mul is const.
 701     if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Mul_1)) {
 702       int32_t ValConst = C->getSExtValue() << ShlConst;
 703       if (isInt<9>(ValConst)) {
 704         SDValue Val = CurDAG->getTargetConstant(ValConst, dl, MVT::i32);
 705         SDNode *Result = CurDAG->getMachineNode(Hexagon::M2_mpysmi, dl,
 706                                                 MVT::i32, Mul_0, Val);
 707         ReplaceNode(N, Result);
 708         return;
 709       }
 710     }
 711     return Default();
 712   }
 713
 714   if (Shl_0.getOpcode() == ISD::SUB) {
 715     SDValue Sub_0 = Shl_0.getOperand(0); // Const 0
 716     SDValue Sub_1 = Shl_0.getOperand(1); // Val
 717     if (ConstantSDNode *C1 = dyn_cast<ConstantSDNode>(Sub_0)) {
 718       if (C1->getSExtValue() != 0 || Sub_1.getOpcode() != ISD::SHL)
 719         return Default();
 720       SDValue Shl2_0 = Sub_1.getOperand(0); // Val
 721       SDValue Shl2_1 = Sub_1.getOperand(1); // Const
 722       if (ConstantSDNode *C2 = dyn_cast<ConstantSDNode>(Shl2_1)) {
 723         int32_t ValConst = 1 << (ShlConst + C2->getSExtValue());
 724         if (isInt<9>(-ValConst)) {
 725           SDValue Val = CurDAG->getTargetConstant(-ValConst, dl, MVT::i32);
 726           SDNode *Result = CurDAG->getMachineNode(Hexagon::M2_mpysmi, dl,
 727                                                   MVT::i32, Shl2_0, Val);
 728           ReplaceNode(N, Result);
 729           return;
 730         }
 731       }
 732     }
 733   }
 734
 735   return Default();
 736 }
 737
 738
 739 //
 740 // If there is an zero_extend followed an intrinsic in DAG (this means - the
 741 // result of the intrinsic is predicate); convert the zero_extend to
 742 // transfer instruction.
 743 //
 744 // Zero extend -> transfer is lowered here. Otherwise, zero_extend will be
 745 // converted into a MUX as predicate registers defined as 1 bit in the
 746 // compiler. Architecture defines them as 8-bit registers.
 747 // We want to preserve all the lower 8-bits and, not just 1 LSB bit.
 748 //
 749 void HexagonDAGToDAGISel::SelectZeroExtend(SDNode *N) {
 750   SDLoc dl(N);
 751
 752   SDValue Op0 = N->getOperand(0);
 753   EVT OpVT = Op0.getValueType();
 754   unsigned OpBW = OpVT.getSizeInBits();
 755
 756   // Special handling for zero-extending a vector of booleans.
 757   if (OpVT.isVector() && OpVT.getVectorElementType() == MVT::i1 && OpBW <= 64) {
 758     SDNode *Mask = CurDAG->getMachineNode(Hexagon::C2_mask, dl, MVT::i64, Op0);
 759     unsigned NE = OpVT.getVectorNumElements();
 760     EVT ExVT = N->getValueType(0);
 761     unsigned ES = ExVT.getScalarSizeInBits();
 762     uint64_t MV = 0, Bit = 1;
 763     for (unsigned i = 0; i < NE; ++i) {
 764       MV |= Bit;
 765       Bit <<= ES;
 766     }
 767     SDValue Ones = CurDAG->getTargetConstant(MV, dl, MVT::i64);
 768     SDNode *OnesReg = CurDAG->getMachineNode(Hexagon::CONST64, dl,
 769                                              MVT::i64, Ones);
 770     if (ExVT.getSizeInBits() == 32) {
 771       SDNode *And = CurDAG->getMachineNode(Hexagon::A2_andp, dl, MVT::i64,
 772                                            SDValue(Mask,0), SDValue(OnesReg,0));
 773       SDValue SubR = CurDAG->getTargetConstant(Hexagon::isub_lo, dl, MVT::i32);
 774       ReplaceNode(N, CurDAG->getMachineNode(Hexagon::EXTRACT_SUBREG, dl, ExVT,
 775                                             SDValue(And, 0), SubR));
 776       return;
 777     }
 778     ReplaceNode(N,
 779                 CurDAG->getMachineNode(Hexagon::A2_andp, dl, ExVT,
 780                                        SDValue(Mask, 0), SDValue(OnesReg, 0)));
 781     return;
 782   }
 783
 784   SDNode *Int = N->getOperand(0).getNode();
 785   if ((Int->getOpcode() == ISD::INTRINSIC_WO_CHAIN)) {
 786     unsigned ID = cast<ConstantSDNode>(Int->getOperand(0))->getZExtValue();
 787     if (doesIntrinsicReturnPredicate(ID)) {
 788       // Now we need to differentiate target data types.
 789       if (N->getValueType(0) == MVT::i64) {
 790         // Convert the zero_extend to Rs = Pd followed by A2_combinew(0,Rs).
 791         SDValue TargetConst0 = CurDAG->getTargetConstant(0, dl, MVT::i32);
 792         SDNode *Result_1 = CurDAG->getMachineNode(Hexagon::C2_tfrpr, dl,
 793                                                   MVT::i32, SDValue(Int, 0));
 794         SDNode *Result_2 = CurDAG->getMachineNode(Hexagon::A2_tfrsi, dl,
 795                                                   MVT::i32, TargetConst0);
 796         SDNode *Result_3 = CurDAG->getMachineNode(Hexagon::A2_combinew, dl,
 797                                                   MVT::i64, MVT::Other,
 798                                                   SDValue(Result_2, 0),
 799                                                   SDValue(Result_1, 0));
 800         ReplaceNode(N, Result_3);
 801         return;
 802       }
 803       if (N->getValueType(0) == MVT::i32) {
 804         // Convert the zero_extend to Rs = Pd
 805         SDNode* RsPd = CurDAG->getMachineNode(Hexagon::C2_tfrpr, dl,
 806                                               MVT::i32, SDValue(Int, 0));
 807         ReplaceNode(N, RsPd);
 808         return;
 809       }
 810       llvm_unreachable("Unexpected value type");
 811     }
 812   }
 813   SelectCode(N);
 814 }
 815
 816
 817 //
 818 // Handling intrinsics for circular load and bitreverse load.
 819 //
 820 void HexagonDAGToDAGISel::SelectIntrinsicWChain(SDNode *N) {
 821   if (MachineSDNode *L = LoadInstrForLoadIntrinsic(N)) {
 822     StoreInstrForLoadIntrinsic(L, N);
 823     CurDAG->RemoveDeadNode(N);
 824     return;
 825   }
 826   SelectCode(N);
 827 }
 828
 829 void HexagonDAGToDAGISel::SelectIntrinsicWOChain(SDNode *N) {
 830   unsigned IID = cast<ConstantSDNode>(N->getOperand(0))->getZExtValue();
 831   unsigned Bits;
 832   switch (IID) {
 833   case Intrinsic::hexagon_S2_vsplatrb:
 834     Bits = 8;
 835     break;
 836   case Intrinsic::hexagon_S2_vsplatrh:
 837     Bits = 16;
 838     break;
 839   default:
 840     SelectCode(N);
 841     return;
 842   }
 843
 844   SDValue V = N->getOperand(1);
 845   SDValue U;
 846   if (isValueExtension(V, Bits, U)) {
 847     SDValue R = CurDAG->getNode(N->getOpcode(), SDLoc(N), N->getValueType(0),
 848                                 N->getOperand(0), U);
 849     ReplaceNode(N, R.getNode());
 850     SelectCode(R.getNode());
 851     return;
 852   }
 853   SelectCode(N);
 854 }
 855
 856 //
 857 // Map floating point constant values.
 858 //
 859 void HexagonDAGToDAGISel::SelectConstantFP(SDNode *N) {
 860   SDLoc dl(N);
 861   ConstantFPSDNode *CN = dyn_cast<ConstantFPSDNode>(N);
 862   APInt A = CN->getValueAPF().bitcastToAPInt();
 863   if (N->getValueType(0) == MVT::f32) {
 864     SDValue V = CurDAG->getTargetConstant(A.getZExtValue(), dl, MVT::i32);
 865     ReplaceNode(N, CurDAG->getMachineNode(Hexagon::A2_tfrsi, dl, MVT::f32, V));
 866     return;
 867   }
 868   if (N->getValueType(0) == MVT::f64) {
 869     SDValue V = CurDAG->getTargetConstant(A.getZExtValue(), dl, MVT::i64);
 870     ReplaceNode(N, CurDAG->getMachineNode(Hexagon::CONST64, dl, MVT::f64, V));
 871     return;
 872   }
 873
 874   SelectCode(N);
 875 }
 876
 877 //
 878 // Map boolean values.
 879 //
 880 void HexagonDAGToDAGISel::SelectConstant(SDNode *N) {
 881   if (N->getValueType(0) == MVT::i1) {
 882     assert(!(cast<ConstantSDNode>(N)->getZExtValue() >> 1));
 883     unsigned Opc = (cast<ConstantSDNode>(N)->getSExtValue() != 0)
 884                       ? Hexagon::PS_true
 885                       : Hexagon::PS_false;
 886     ReplaceNode(N, CurDAG->getMachineNode(Opc, SDLoc(N), MVT::i1));
 887     return;
 888   }
 889
 890   SelectCode(N);
 891 }
 892
 893
 894 void HexagonDAGToDAGISel::SelectFrameIndex(SDNode *N) {
 895   MachineFrameInfo &MFI = MF->getFrameInfo();
 896   const HexagonFrameLowering *HFI = HST->getFrameLowering();
 897   int FX = cast<FrameIndexSDNode>(N)->getIndex();
 898   unsigned StkA = HFI->getStackAlignment();
 899   unsigned MaxA = MFI.getMaxAlignment();
 900   SDValue FI = CurDAG->getTargetFrameIndex(FX, MVT::i32);
 901   SDLoc DL(N);
 902   SDValue Zero = CurDAG->getTargetConstant(0, DL, MVT::i32);
 903   SDNode *R = nullptr;
 904
 905   // Use PS_fi when:
 906   // - the object is fixed, or
 907   // - there are no objects with higher-than-default alignment, or
 908   // - there are no dynamically allocated objects.
 909   // Otherwise, use PS_fia.
 910   if (FX < 0 || MaxA <= StkA || !MFI.hasVarSizedObjects()) {
 911     R = CurDAG->getMachineNode(Hexagon::PS_fi, DL, MVT::i32, FI, Zero);
 912   } else {
 913     auto &HMFI = *MF->getInfo<HexagonMachineFunctionInfo>();
 914     unsigned AR = HMFI.getStackAlignBaseVReg();
 915     SDValue CH = CurDAG->getEntryNode();
 916     SDValue Ops[] = { CurDAG->getCopyFromReg(CH, DL, AR, MVT::i32), FI, Zero };
 917     R = CurDAG->getMachineNode(Hexagon::PS_fia, DL, MVT::i32, Ops);
 918   }
 919
 920   ReplaceNode(N, R);
 921 }
 922
 923
 924 void HexagonDAGToDAGISel::SelectBitcast(SDNode *N) {
 925   EVT SVT = N->getOperand(0).getValueType();
 926   EVT DVT = N->getValueType(0);
 927   if (!SVT.isVector() || !DVT.isVector() ||
 928       SVT.getVectorElementType() == MVT::i1 ||
 929       DVT.getVectorElementType() == MVT::i1 ||
 930       SVT.getSizeInBits() != DVT.getSizeInBits()) {
 931     SelectCode(N);
 932     return;
 933   }
 934
 935   CurDAG->ReplaceAllUsesOfValueWith(SDValue(N,0), N->getOperand(0));
 936   CurDAG->RemoveDeadNode(N);
 937 }
 938
 939
 940 void HexagonDAGToDAGISel::Select(SDNode *N) {
 941   if (N->isMachineOpcode())
 942     return N->setNodeId(-1);  // Already selected.
 943
 944   switch (N->getOpcode()) {
 945   case ISD::Constant:             return SelectConstant(N);
 946   case ISD::ConstantFP:           return SelectConstantFP(N);
 947   case ISD::FrameIndex:           return SelectFrameIndex(N);
 948   case ISD::BITCAST:              return SelectBitcast(N);
 949   case ISD::SHL:                  return SelectSHL(N);
 950   case ISD::LOAD:                 return SelectLoad(N);
 951   case ISD::STORE:                return SelectStore(N);
 952   case ISD::MUL:                  return SelectMul(N);
 953   case ISD::ZERO_EXTEND:          return SelectZeroExtend(N);
 954   case ISD::INTRINSIC_W_CHAIN:    return SelectIntrinsicWChain(N);
 955   case ISD::INTRINSIC_WO_CHAIN:   return SelectIntrinsicWOChain(N);
 956   }
 957
 958   SelectCode(N);
 959 }
 960
 961 bool HexagonDAGToDAGISel::
 962 SelectInlineAsmMemoryOperand(const SDValue &Op, unsigned ConstraintID,
 963                              std::vector<SDValue> &OutOps) {
 964   SDValue Inp = Op, Res;
 965
 966   switch (ConstraintID) {
 967   default:
 968     return true;
 969   case InlineAsm::Constraint_i:
 970   case InlineAsm::Constraint_o: // Offsetable.
 971   case InlineAsm::Constraint_v: // Not offsetable.
 972   case InlineAsm::Constraint_m: // Memory.
 973     if (SelectAddrFI(Inp, Res))
 974       OutOps.push_back(Res);
 975     else
 976       OutOps.push_back(Inp);
 977     break;
 978   }
 979
 980   OutOps.push_back(CurDAG->getTargetConstant(0, SDLoc(Op), MVT::i32));
 981   return false;
 982 }
 983
 984
 985 static bool isMemOPCandidate(SDNode *I, SDNode *U) {
 986   // I is an operand of U. Check if U is an arithmetic (binary) operation
 987   // usable in a memop, where the other operand is a loaded value, and the
 988   // result of U is stored in the same location.
 989
 990   if (!U->hasOneUse())
 991     return false;
 992   unsigned Opc = U->getOpcode();
 993   switch (Opc) {
 994     case ISD::ADD:
 995     case ISD::SUB:
 996     case ISD::AND:
 997     case ISD::OR:
 998       break;
 999     default:
1000       return false;
1001   }
1002
1003   SDValue S0 = U->getOperand(0);
1004   SDValue S1 = U->getOperand(1);
1005   SDValue SY = (S0.getNode() == I) ? S1 : S0;
1006
1007   SDNode *UUse = *U->use_begin();
1008   if (UUse->getNumValues() != 1)
1009     return false;
1010
1011   // Check if one of the inputs to U is a load instruction and the output
1012   // is used by a store instruction. If so and they also have the same
1013   // base pointer, then don't preoprocess this node sequence as it
1014   // can be matched to a memop.
1015   SDNode *SYNode = SY.getNode();
1016   if (UUse->getOpcode() == ISD::STORE && SYNode->getOpcode() == ISD::LOAD) {
1017     SDValue LDBasePtr = cast<MemSDNode>(SYNode)->getBasePtr();
1018     SDValue STBasePtr = cast<MemSDNode>(UUse)->getBasePtr();
1019     if (LDBasePtr == STBasePtr)
1020       return true;
1021   }
1022   return false;
1023 }
1024
1025
1026 // Transform: (or (select c x 0) z)  ->  (select c (or x z) z)
1027 //            (or (select c 0 y) z)  ->  (select c z (or y z))
1028 void HexagonDAGToDAGISel::ppSimplifyOrSelect0(std::vector<SDNode*> &&Nodes) {
1029   SelectionDAG &DAG = *CurDAG;
1030
1031   for (auto I : Nodes) {
1032     if (I->getOpcode() != ISD::OR)
1033       continue;
1034
1035     auto IsZero = [] (const SDValue &V) -> bool {
1036       if (ConstantSDNode *SC = dyn_cast<ConstantSDNode>(V.getNode()))
1037         return SC->isNullValue();
1038       return false;
1039     };
1040     auto IsSelect0 = [IsZero] (const SDValue &Op) -> bool {
1041       if (Op.getOpcode() != ISD::SELECT)
1042         return false;
1043       return IsZero(Op.getOperand(1)) || IsZero(Op.getOperand(2));
1044     };
1045
1046     SDValue N0 = I->getOperand(0), N1 = I->getOperand(1);
1047     EVT VT = I->getValueType(0);
1048     bool SelN0 = IsSelect0(N0);
1049     SDValue SOp = SelN0 ? N0 : N1;
1050     SDValue VOp = SelN0 ? N1 : N0;
1051
1052     if (SOp.getOpcode() == ISD::SELECT && SOp.getNode()->hasOneUse()) {
1053       SDValue SC = SOp.getOperand(0);
1054       SDValue SX = SOp.getOperand(1);
1055       SDValue SY = SOp.getOperand(2);
1056       SDLoc DLS = SOp;
1057       if (IsZero(SY)) {
1058         SDValue NewOr = DAG.getNode(ISD::OR, DLS, VT, SX, VOp);
1059         SDValue NewSel = DAG.getNode(ISD::SELECT, DLS, VT, SC, NewOr, VOp);
1060         DAG.ReplaceAllUsesWith(I, NewSel.getNode());
1061       } else if (IsZero(SX)) {
1062         SDValue NewOr = DAG.getNode(ISD::OR, DLS, VT, SY, VOp);
1063         SDValue NewSel = DAG.getNode(ISD::SELECT, DLS, VT, SC, VOp, NewOr);
1064         DAG.ReplaceAllUsesWith(I, NewSel.getNode());
1065       }
1066     }
1067   }
1068 }
1069
1070 // Transform: (store ch val (add x (add (shl y c) e)))
1071 //        to: (store ch val (add x (shl (add y d) c))),
1072 // where e = (shl d c) for some integer d.
1073 // The purpose of this is to enable generation of loads/stores with
1074 // shifted addressing mode, i.e. mem(x+y<<#c). For that, the shift
1075 // value c must be 0, 1 or 2.
1076 void HexagonDAGToDAGISel::ppAddrReorderAddShl(std::vector<SDNode*> &&Nodes) {
1077   SelectionDAG &DAG = *CurDAG;
1078
1079   for (auto I : Nodes) {
1080     if (I->getOpcode() != ISD::STORE)
1081       continue;
1082
1083     // I matched: (store ch val Off)
1084     SDValue Off = I->getOperand(2);
1085     // Off needs to match: (add x (add (shl y c) (shl d c))))
1086     if (Off.getOpcode() != ISD::ADD)
1087       continue;
1088     // Off matched: (add x T0)
1089     SDValue T0 = Off.getOperand(1);
1090     // T0 needs to match: (add T1 T2):
1091     if (T0.getOpcode() != ISD::ADD)
1092       continue;
1093     // T0 matched: (add T1 T2)
1094     SDValue T1 = T0.getOperand(0);
1095     SDValue T2 = T0.getOperand(1);
1096     // T1 needs to match: (shl y c)
1097     if (T1.getOpcode() != ISD::SHL)
1098       continue;
1099     SDValue C = T1.getOperand(1);
1100     ConstantSDNode *CN = dyn_cast<ConstantSDNode>(C.getNode());
1101     if (CN == nullptr)
1102       continue;
1103     unsigned CV = CN->getZExtValue();
1104     if (CV > 2)
1105       continue;
1106     // T2 needs to match e, where e = (shl d c) for some d.
1107     ConstantSDNode *EN = dyn_cast<ConstantSDNode>(T2.getNode());
1108     if (EN == nullptr)
1109       continue;
1110     unsigned EV = EN->getZExtValue();
1111     if (EV % (1 << CV) != 0)
1112       continue;
1113     unsigned DV = EV / (1 << CV);
1114
1115     // Replace T0 with: (shl (add y d) c)
1116     SDLoc DL = SDLoc(I);
1117     EVT VT = T0.getValueType();
1118     SDValue D = DAG.getConstant(DV, DL, VT);
1119     // NewAdd = (add y d)
1120     SDValue NewAdd = DAG.getNode(ISD::ADD, DL, VT, T1.getOperand(0), D);
1121     // NewShl = (shl NewAdd c)
1122     SDValue NewShl = DAG.getNode(ISD::SHL, DL, VT, NewAdd, C);
1123     ReplaceNode(T0.getNode(), NewShl.getNode());
1124   }
1125 }
1126
1127 // Transform: (load ch (add x (and (srl y c) Mask)))
1128 //        to: (load ch (add x (shl (srl y d) d-c)))
1129 // where
1130 // Mask = 00..0 111..1 0.0
1131 //          |     |     +-- d-c 0s, and d-c is 0, 1 or 2.
1132 //          |     +-------- 1s
1133 //          +-------------- at most c 0s
1134 // Motivating example:
1135 // DAG combiner optimizes (add x (shl (srl y 5) 2))
1136 //                     to (add x (and (srl y 3) 1FFFFFFC))
1137 // which results in a constant-extended and(##...,lsr). This transformation
1138 // undoes this simplification for cases where the shl can be folded into
1139 // an addressing mode.
1140 void HexagonDAGToDAGISel::ppAddrRewriteAndSrl(std::vector<SDNode*> &&Nodes) {
1141   SelectionDAG &DAG = *CurDAG;
1142
1143   for (SDNode *N : Nodes) {
1144     unsigned Opc = N->getOpcode();
1145     if (Opc != ISD::LOAD && Opc != ISD::STORE)
1146       continue;
1147     SDValue Addr = Opc == ISD::LOAD ? N->getOperand(1) : N->getOperand(2);
1148     // Addr must match: (add x T0)
1149     if (Addr.getOpcode() != ISD::ADD)
1150       continue;
1151     SDValue T0 = Addr.getOperand(1);
1152     // T0 must match: (and T1 Mask)
1153     if (T0.getOpcode() != ISD::AND)
1154       continue;
1155
1156     // We have an AND.
1157     //
1158     // Check the first operand. It must be: (srl y c).
1159     SDValue S = T0.getOperand(0);
1160     if (S.getOpcode() != ISD::SRL)
1161       continue;
1162     ConstantSDNode *SN = dyn_cast<ConstantSDNode>(S.getOperand(1).getNode());
1163     if (SN == nullptr)
1164       continue;
1165     if (SN->getAPIntValue().getBitWidth() != 32)
1166       continue;
1167     uint32_t CV = SN->getZExtValue();
1168
1169     // Check the second operand: the supposed mask.
1170     ConstantSDNode *MN = dyn_cast<ConstantSDNode>(T0.getOperand(1).getNode());
1171     if (MN == nullptr)
1172       continue;
1173     if (MN->getAPIntValue().getBitWidth() != 32)
1174       continue;
1175     uint32_t Mask = MN->getZExtValue();
1176     // Examine the mask.
1177     uint32_t TZ = countTrailingZeros(Mask);
1178     uint32_t M1 = countTrailingOnes(Mask >> TZ);
1179     uint32_t LZ = countLeadingZeros(Mask);
1180     // Trailing zeros + middle ones + leading zeros must equal the width.
1181     if (TZ + M1 + LZ != 32)
1182       continue;
1183     // The number of trailing zeros will be encoded in the addressing mode.
1184     if (TZ > 2)
1185       continue;
1186     // The number of leading zeros must be at most c.
1187     if (LZ > CV)
1188       continue;
1189
1190     // All looks good.
1191     SDValue Y = S.getOperand(0);
1192     EVT VT = Addr.getValueType();
1193     SDLoc dl(S);
1194     // TZ = D-C, so D = TZ+C.
1195     SDValue D = DAG.getConstant(TZ+CV, dl, VT);
1196     SDValue DC = DAG.getConstant(TZ, dl, VT);
1197     SDValue NewSrl = DAG.getNode(ISD::SRL, dl, VT, Y, D);
1198     SDValue NewShl = DAG.getNode(ISD::SHL, dl, VT, NewSrl, DC);
1199     ReplaceNode(T0.getNode(), NewShl.getNode());
1200   }
1201 }
1202
1203 // Transform: (op ... (zext i1 c) ...) -> (select c (op ... 0 ...)
1204 //                                                  (op ... 1 ...))
1205 void HexagonDAGToDAGISel::ppHoistZextI1(std::vector<SDNode*> &&Nodes) {
1206   SelectionDAG &DAG = *CurDAG;
1207
1208   for (SDNode *N : Nodes) {
1209     unsigned Opc = N->getOpcode();
1210     if (Opc != ISD::ZERO_EXTEND)
1211       continue;
1212     SDValue OpI1 = N->getOperand(0);
1213     EVT OpVT = OpI1.getValueType();
1214     if (!OpVT.isSimple() || OpVT.getSimpleVT() != MVT::i1)
1215       continue;
1216     for (auto I = N->use_begin(), E = N->use_end(); I != E; ++I) {
1217       SDNode *U = *I;
1218       if (U->getNumValues() != 1)
1219         continue;
1220       EVT UVT = U->getValueType(0);
1221       if (!UVT.isSimple() || !UVT.isInteger() || UVT.getSimpleVT() == MVT::i1)
1222         continue;
1223       if (isMemOPCandidate(N, U))
1224         continue;
1225
1226       // Potentially simplifiable operation.
1227       unsigned I1N = I.getOperandNo();
1228       SmallVector<SDValue,2> Ops(U->getNumOperands());
1229       for (unsigned i = 0, n = U->getNumOperands(); i != n; ++i)
1230         Ops[i] = U->getOperand(i);
1231       EVT BVT = Ops[I1N].getValueType();
1232
1233       SDLoc dl(U);
1234       SDValue C0 = DAG.getConstant(0, dl, BVT);
1235       SDValue C1 = DAG.getConstant(1, dl, BVT);
1236       SDValue If0, If1;
1237
1238       if (isa<MachineSDNode>(U)) {
1239         unsigned UseOpc = U->getMachineOpcode();
1240         Ops[I1N] = C0;
1241         If0 = SDValue(DAG.getMachineNode(UseOpc, dl, UVT, Ops), 0);
1242         Ops[I1N] = C1;
1243         If1 = SDValue(DAG.getMachineNode(UseOpc, dl, UVT, Ops), 0);
1244       } else {
1245         unsigned UseOpc = U->getOpcode();
1246         Ops[I1N] = C0;
1247         If0 = DAG.getNode(UseOpc, dl, UVT, Ops);
1248         Ops[I1N] = C1;
1249         If1 = DAG.getNode(UseOpc, dl, UVT, Ops);
1250       }
1251       SDValue Sel = DAG.getNode(ISD::SELECT, dl, UVT, OpI1, If1, If0);
1252       DAG.ReplaceAllUsesWith(U, Sel.getNode());
1253     }
1254   }
1255 }
1256
1257 void HexagonDAGToDAGISel::PreprocessISelDAG() {
1258   // Repack all nodes before calling each preprocessing function,
1259   // because each of them can modify the set of nodes.
1260   auto getNodes = [this] () -> std::vector<SDNode*> {
1261     std::vector<SDNode*> T;
1262     T.reserve(CurDAG->allnodes_size());
1263     for (SDNode &N : CurDAG->allnodes())
1264       T.push_back(&N);
1265     return T;
1266   };
1267
1268   // Transform: (or (select c x 0) z)  ->  (select c (or x z) z)
1269   //            (or (select c 0 y) z)  ->  (select c z (or y z))
1270   ppSimplifyOrSelect0(getNodes());
1271
1272   // Transform: (store ch val (add x (add (shl y c) e)))
1273   //        to: (store ch val (add x (shl (add y d) c))),
1274   // where e = (shl d c) for some integer d.
1275   // The purpose of this is to enable generation of loads/stores with
1276   // shifted addressing mode, i.e. mem(x+y<<#c). For that, the shift
1277   // value c must be 0, 1 or 2.
1278   ppAddrReorderAddShl(getNodes());
1279
1280   // Transform: (load ch (add x (and (srl y c) Mask)))
1281   //        to: (load ch (add x (shl (srl y d) d-c)))
1282   // where
1283   // Mask = 00..0 111..1 0.0
1284   //          |     |     +-- d-c 0s, and d-c is 0, 1 or 2.
1285   //          |     +-------- 1s
1286   //          +-------------- at most c 0s
1287   // Motivating example:
1288   // DAG combiner optimizes (add x (shl (srl y 5) 2))
1289   //                     to (add x (and (srl y 3) 1FFFFFFC))
1290   // which results in a constant-extended and(##...,lsr). This transformation
1291   // undoes this simplification for cases where the shl can be folded into
1292   // an addressing mode.
1293   ppAddrRewriteAndSrl(getNodes());
1294
1295   // Transform: (op ... (zext i1 c) ...) -> (select c (op ... 0 ...)
1296   //                                                  (op ... 1 ...))
1297   ppHoistZextI1(getNodes());
1298
1299   DEBUG_WITH_TYPE("isel", {
1300     dbgs() << "Preprocessed (Hexagon) selection DAG:";
1301     CurDAG->dump();
1302   });
1303
1304   if (EnableAddressRebalancing) {
1305     rebalanceAddressTrees();
1306
1307     DEBUG_WITH_TYPE("isel", {
1308       dbgs() << "Address tree balanced selection DAG:";
1309       CurDAG->dump();
1310     });
1311   }
1312 }
1313
1314 void HexagonDAGToDAGISel::EmitFunctionEntryCode() {
1315   auto &HST = static_cast<const HexagonSubtarget&>(MF->getSubtarget());
1316   auto &HFI = *HST.getFrameLowering();
1317   if (!HFI.needsAligna(*MF))
1318     return;
1319
1320   MachineFrameInfo &MFI = MF->getFrameInfo();
1321   MachineBasicBlock *EntryBB = &MF->front();
1322   unsigned AR = FuncInfo->CreateReg(MVT::i32);
1323   unsigned MaxA = MFI.getMaxAlignment();
1324   BuildMI(EntryBB, DebugLoc(), HII->get(Hexagon::PS_aligna), AR)
1325       .addImm(MaxA);
1326   MF->getInfo<HexagonMachineFunctionInfo>()->setStackAlignBaseVReg(AR);
1327 }
1328
1329 // Match a frame index that can be used in an addressing mode.
1330 bool HexagonDAGToDAGISel::SelectAddrFI(SDValue& N, SDValue &R) {
1331   if (N.getOpcode() != ISD::FrameIndex)
1332     return false;
1333   auto &HFI = *HST->getFrameLowering();
1334   MachineFrameInfo &MFI = MF->getFrameInfo();
1335   int FX = cast<FrameIndexSDNode>(N)->getIndex();
1336   if (!MFI.isFixedObjectIndex(FX) && HFI.needsAligna(*MF))
1337     return false;
1338   R = CurDAG->getTargetFrameIndex(FX, MVT::i32);
1339   return true;
1340 }
1341
1342 inline bool HexagonDAGToDAGISel::SelectAddrGA(SDValue &N, SDValue &R) {
1343   return SelectGlobalAddress(N, R, false);
1344 }
1345
1346 inline bool HexagonDAGToDAGISel::SelectAddrGP(SDValue &N, SDValue &R) {
1347   return SelectGlobalAddress(N, R, true);
1348 }
1349
1350 bool HexagonDAGToDAGISel::SelectGlobalAddress(SDValue &N, SDValue &R,
1351                                               bool UseGP) {
1352   switch (N.getOpcode()) {
1353   case ISD::ADD: {
1354     SDValue N0 = N.getOperand(0);
1355     SDValue N1 = N.getOperand(1);
1356     unsigned GAOpc = N0.getOpcode();
1357     if (UseGP && GAOpc != HexagonISD::CONST32_GP)
1358       return false;
1359     if (!UseGP && GAOpc != HexagonISD::CONST32)
1360       return false;
1361     if (ConstantSDNode *Const = dyn_cast<ConstantSDNode>(N1)) {
1362       SDValue Addr = N0.getOperand(0);
1363       if (GlobalAddressSDNode *GA = dyn_cast<GlobalAddressSDNode>(Addr)) {
1364         if (GA->getOpcode() == ISD::TargetGlobalAddress) {
1365           uint64_t NewOff = GA->getOffset() + (uint64_t)Const->getSExtValue();
1366           R = CurDAG->getTargetGlobalAddress(GA->getGlobal(), SDLoc(Const),
1367                                              N.getValueType(), NewOff);
1368           return true;
1369         }
1370       }
1371     }
1372     break;
1373   }
1374   case HexagonISD::CONST32:
1375     // The operand(0) of CONST32 is TargetGlobalAddress, which is what we
1376     // want in the instruction.
1377     if (!UseGP)
1378       R = N.getOperand(0);
1379     return !UseGP;
1380   case HexagonISD::CONST32_GP:
1381     if (UseGP)
1382       R = N.getOperand(0);
1383     return UseGP;
1384   default:
1385     return false;
1386   }
1387
1388   return false;
1389 }
1390
1391 bool HexagonDAGToDAGISel::isValueExtension(const SDValue &Val,
1392       unsigned FromBits, SDValue &Src) {
1393   unsigned Opc = Val.getOpcode();
1394   switch (Opc) {
1395   case ISD::SIGN_EXTEND:
1396   case ISD::ZERO_EXTEND:
1397   case ISD::ANY_EXTEND: {
1398     SDValue const &Op0 = Val.getOperand(0);
1399     EVT T = Op0.getValueType();
1400     if (T.isInteger() && T.getSizeInBits() == FromBits) {
1401       Src = Op0;
1402       return true;
1403     }
1404     break;
1405   }
1406   case ISD::SIGN_EXTEND_INREG:
1407   case ISD::AssertSext:
1408   case ISD::AssertZext:
1409     if (Val.getOperand(0).getValueType().isInteger()) {
1410       VTSDNode *T = cast<VTSDNode>(Val.getOperand(1));
1411       if (T->getVT().getSizeInBits() == FromBits) {
1412         Src = Val.getOperand(0);
1413         return true;
1414       }
1415     }
1416     break;
1417   case ISD::AND: {
1418     // Check if this is an AND with "FromBits" of lower bits set to 1.
1419     uint64_t FromMask = (1 << FromBits) - 1;
1420     if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Val.getOperand(0))) {
1421       if (C->getZExtValue() == FromMask) {
1422         Src = Val.getOperand(1);
1423         return true;
1424       }
1425     }
1426     if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Val.getOperand(1))) {
1427       if (C->getZExtValue() == FromMask) {
1428         Src = Val.getOperand(0);
1429         return true;
1430       }
1431     }
1432     break;
1433   }
1434   case ISD::OR:
1435   case ISD::XOR: {
1436     // OR/XOR with the lower "FromBits" bits set to 0.
1437     uint64_t FromMask = (1 << FromBits) - 1;
1438     if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Val.getOperand(0))) {
1439       if ((C->getZExtValue() & FromMask) == 0) {
1440         Src = Val.getOperand(1);
1441         return true;
1442       }
1443     }
1444     if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Val.getOperand(1))) {
1445       if ((C->getZExtValue() & FromMask) == 0) {
1446         Src = Val.getOperand(0);
1447         return true;
1448       }
1449     }
1450   }
1451   default:
1452     break;
1453   }
1454   return false;
1455 }
1456
1457
1458 bool HexagonDAGToDAGISel::isOrEquivalentToAdd(const SDNode *N) const {
1459   assert(N->getOpcode() == ISD::OR);
1460   auto *C = dyn_cast<ConstantSDNode>(N->getOperand(1));
1461   assert(C);
1462
1463   // Detect when "or" is used to add an offset to a stack object.
1464   if (auto *FN = dyn_cast<FrameIndexSDNode>(N->getOperand(0))) {
1465     MachineFrameInfo &MFI = MF->getFrameInfo();
1466     unsigned A = MFI.getObjectAlignment(FN->getIndex());
1467     assert(isPowerOf2_32(A));
1468     int32_t Off = C->getSExtValue();
1469     // If the alleged offset fits in the zero bits guaranteed by
1470     // the alignment, then this or is really an add.
1471     return (Off >= 0) && (((A-1) & Off) == unsigned(Off));
1472   }
1473   return false;
1474 }
1475
1476 bool HexagonDAGToDAGISel::isAlignedMemNode(const MemSDNode *N) const {
1477   return N->getAlignment() >= N->getMemoryVT().getStoreSize();
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