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