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