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