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 "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  SelectCode(N);
645 }
646 
648  unsigned IID = cast<ConstantSDNode>(N->getOperand(0))->getZExtValue();
649  unsigned Bits;
650  switch (IID) {
651  case Intrinsic::hexagon_S2_vsplatrb:
652  Bits = 8;
653  break;
654  case Intrinsic::hexagon_S2_vsplatrh:
655  Bits = 16;
656  break;
657  default:
658  SelectCode(N);
659  return;
660  }
661 
662  SDValue V = N->getOperand(1);
663  SDValue U;
664  if (keepsLowBits(V, Bits, U)) {
665  SDValue R = CurDAG->getNode(N->getOpcode(), SDLoc(N), N->getValueType(0),
666  N->getOperand(0), U);
667  ReplaceNode(N, R.getNode());
668  SelectCode(R.getNode());
669  return;
670  }
671  SelectCode(N);
672 }
673 
674 //
675 // Map floating point constant values.
676 //
678  SDLoc dl(N);
680  APInt A = CN->getValueAPF().bitcastToAPInt();
681  if (N->getValueType(0) == MVT::f32) {
682  SDValue V = CurDAG->getTargetConstant(A.getZExtValue(), dl, MVT::i32);
683  ReplaceNode(N, CurDAG->getMachineNode(Hexagon::A2_tfrsi, dl, MVT::f32, V));
684  return;
685  }
686  if (N->getValueType(0) == MVT::f64) {
687  SDValue V = CurDAG->getTargetConstant(A.getZExtValue(), dl, MVT::i64);
688  ReplaceNode(N, CurDAG->getMachineNode(Hexagon::CONST64, dl, MVT::f64, V));
689  return;
690  }
691 
692  SelectCode(N);
693 }
694 
695 //
696 // Map boolean values.
697 //
699  if (N->getValueType(0) == MVT::i1) {
700  assert(!(cast<ConstantSDNode>(N)->getZExtValue() >> 1));
701  unsigned Opc = (cast<ConstantSDNode>(N)->getSExtValue() != 0)
702  ? Hexagon::PS_true
703  : Hexagon::PS_false;
705  return;
706  }
707 
708  SelectCode(N);
709 }
710 
711 
713  MachineFrameInfo &MFI = MF->getFrameInfo();
714  const HexagonFrameLowering *HFI = HST->getFrameLowering();
715  int FX = cast<FrameIndexSDNode>(N)->getIndex();
716  unsigned StkA = HFI->getStackAlignment();
717  unsigned MaxA = MFI.getMaxAlignment();
719  SDLoc DL(N);
720  SDValue Zero = CurDAG->getTargetConstant(0, DL, MVT::i32);
721  SDNode *R = nullptr;
722 
723  // Use PS_fi when:
724  // - the object is fixed, or
725  // - there are no objects with higher-than-default alignment, or
726  // - there are no dynamically allocated objects.
727  // Otherwise, use PS_fia.
728  if (FX < 0 || MaxA <= StkA || !MFI.hasVarSizedObjects()) {
729  R = CurDAG->getMachineNode(Hexagon::PS_fi, DL, MVT::i32, FI, Zero);
730  } else {
731  auto &HMFI = *MF->getInfo<HexagonMachineFunctionInfo>();
732  unsigned AR = HMFI.getStackAlignBaseVReg();
733  SDValue CH = CurDAG->getEntryNode();
734  SDValue Ops[] = { CurDAG->getCopyFromReg(CH, DL, AR, MVT::i32), FI, Zero };
735  R = CurDAG->getMachineNode(Hexagon::PS_fia, DL, MVT::i32, Ops);
736  }
737 
738  ReplaceNode(N, R);
739 }
740 
741 
743  EVT SVT = N->getOperand(0).getValueType();
744  EVT DVT = N->getValueType(0);
745  if (!SVT.isVector() || !DVT.isVector() ||
746  SVT.getVectorElementType() == MVT::i1 ||
747  DVT.getVectorElementType() == MVT::i1 ||
748  SVT.getSizeInBits() != DVT.getSizeInBits()) {
749  SelectCode(N);
750  return;
751  }
752 
755 }
756 
757 
759  if (N->isMachineOpcode())
760  return N->setNodeId(-1); // Already selected.
761 
762  switch (N->getOpcode()) {
763  case ISD::Constant: return SelectConstant(N);
764  case ISD::ConstantFP: return SelectConstantFP(N);
765  case ISD::FrameIndex: return SelectFrameIndex(N);
766  case ISD::BITCAST: return SelectBitcast(N);
767  case ISD::SHL: return SelectSHL(N);
768  case ISD::LOAD: return SelectLoad(N);
769  case ISD::STORE: return SelectStore(N);
770  case ISD::ZERO_EXTEND: return SelectZeroExtend(N);
773  }
774 
775  SelectCode(N);
776 }
777 
779 SelectInlineAsmMemoryOperand(const SDValue &Op, unsigned ConstraintID,
780  std::vector<SDValue> &OutOps) {
781  SDValue Inp = Op, Res;
782 
783  switch (ConstraintID) {
784  default:
785  return true;
787  case InlineAsm::Constraint_o: // Offsetable.
788  case InlineAsm::Constraint_v: // Not offsetable.
789  case InlineAsm::Constraint_m: // Memory.
790  if (SelectAddrFI(Inp, Res))
791  OutOps.push_back(Res);
792  else
793  OutOps.push_back(Inp);
794  break;
795  }
796 
797  OutOps.push_back(CurDAG->getTargetConstant(0, SDLoc(Op), MVT::i32));
798  return false;
799 }
800 
801 
802 static bool isMemOPCandidate(SDNode *I, SDNode *U) {
803  // I is an operand of U. Check if U is an arithmetic (binary) operation
804  // usable in a memop, where the other operand is a loaded value, and the
805  // result of U is stored in the same location.
806 
807  if (!U->hasOneUse())
808  return false;
809  unsigned Opc = U->getOpcode();
810  switch (Opc) {
811  case ISD::ADD:
812  case ISD::SUB:
813  case ISD::AND:
814  case ISD::OR:
815  break;
816  default:
817  return false;
818  }
819 
820  SDValue S0 = U->getOperand(0);
821  SDValue S1 = U->getOperand(1);
822  SDValue SY = (S0.getNode() == I) ? S1 : S0;
823 
824  SDNode *UUse = *U->use_begin();
825  if (UUse->getNumValues() != 1)
826  return false;
827 
828  // Check if one of the inputs to U is a load instruction and the output
829  // is used by a store instruction. If so and they also have the same
830  // base pointer, then don't preoprocess this node sequence as it
831  // can be matched to a memop.
832  SDNode *SYNode = SY.getNode();
833  if (UUse->getOpcode() == ISD::STORE && SYNode->getOpcode() == ISD::LOAD) {
834  SDValue LDBasePtr = cast<MemSDNode>(SYNode)->getBasePtr();
835  SDValue STBasePtr = cast<MemSDNode>(UUse)->getBasePtr();
836  if (LDBasePtr == STBasePtr)
837  return true;
838  }
839  return false;
840 }
841 
842 
843 // Transform: (or (select c x 0) z) -> (select c (or x z) z)
844 // (or (select c 0 y) z) -> (select c z (or y z))
845 void HexagonDAGToDAGISel::ppSimplifyOrSelect0(std::vector<SDNode*> &&Nodes) {
846  SelectionDAG &DAG = *CurDAG;
847 
848  for (auto I : Nodes) {
849  if (I->getOpcode() != ISD::OR)
850  continue;
851 
852  auto IsZero = [] (const SDValue &V) -> bool {
853  if (ConstantSDNode *SC = dyn_cast<ConstantSDNode>(V.getNode()))
854  return SC->isNullValue();
855  return false;
856  };
857  auto IsSelect0 = [IsZero] (const SDValue &Op) -> bool {
858  if (Op.getOpcode() != ISD::SELECT)
859  return false;
860  return IsZero(Op.getOperand(1)) || IsZero(Op.getOperand(2));
861  };
862 
863  SDValue N0 = I->getOperand(0), N1 = I->getOperand(1);
864  EVT VT = I->getValueType(0);
865  bool SelN0 = IsSelect0(N0);
866  SDValue SOp = SelN0 ? N0 : N1;
867  SDValue VOp = SelN0 ? N1 : N0;
868 
869  if (SOp.getOpcode() == ISD::SELECT && SOp.getNode()->hasOneUse()) {
870  SDValue SC = SOp.getOperand(0);
871  SDValue SX = SOp.getOperand(1);
872  SDValue SY = SOp.getOperand(2);
873  SDLoc DLS = SOp;
874  if (IsZero(SY)) {
875  SDValue NewOr = DAG.getNode(ISD::OR, DLS, VT, SX, VOp);
876  SDValue NewSel = DAG.getNode(ISD::SELECT, DLS, VT, SC, NewOr, VOp);
877  DAG.ReplaceAllUsesWith(I, NewSel.getNode());
878  } else if (IsZero(SX)) {
879  SDValue NewOr = DAG.getNode(ISD::OR, DLS, VT, SY, VOp);
880  SDValue NewSel = DAG.getNode(ISD::SELECT, DLS, VT, SC, VOp, NewOr);
881  DAG.ReplaceAllUsesWith(I, NewSel.getNode());
882  }
883  }
884  }
885 }
886 
887 // Transform: (store ch val (add x (add (shl y c) e)))
888 // to: (store ch val (add x (shl (add y d) c))),
889 // where e = (shl d c) for some integer d.
890 // The purpose of this is to enable generation of loads/stores with
891 // shifted addressing mode, i.e. mem(x+y<<#c). For that, the shift
892 // value c must be 0, 1 or 2.
893 void HexagonDAGToDAGISel::ppAddrReorderAddShl(std::vector<SDNode*> &&Nodes) {
894  SelectionDAG &DAG = *CurDAG;
895 
896  for (auto I : Nodes) {
897  if (I->getOpcode() != ISD::STORE)
898  continue;
899 
900  // I matched: (store ch val Off)
901  SDValue Off = I->getOperand(2);
902  // Off needs to match: (add x (add (shl y c) (shl d c))))
903  if (Off.getOpcode() != ISD::ADD)
904  continue;
905  // Off matched: (add x T0)
906  SDValue T0 = Off.getOperand(1);
907  // T0 needs to match: (add T1 T2):
908  if (T0.getOpcode() != ISD::ADD)
909  continue;
910  // T0 matched: (add T1 T2)
911  SDValue T1 = T0.getOperand(0);
912  SDValue T2 = T0.getOperand(1);
913  // T1 needs to match: (shl y c)
914  if (T1.getOpcode() != ISD::SHL)
915  continue;
916  SDValue C = T1.getOperand(1);
918  if (CN == nullptr)
919  continue;
920  unsigned CV = CN->getZExtValue();
921  if (CV > 2)
922  continue;
923  // T2 needs to match e, where e = (shl d c) for some d.
925  if (EN == nullptr)
926  continue;
927  unsigned EV = EN->getZExtValue();
928  if (EV % (1 << CV) != 0)
929  continue;
930  unsigned DV = EV / (1 << CV);
931 
932  // Replace T0 with: (shl (add y d) c)
933  SDLoc DL = SDLoc(I);
934  EVT VT = T0.getValueType();
935  SDValue D = DAG.getConstant(DV, DL, VT);
936  // NewAdd = (add y d)
937  SDValue NewAdd = DAG.getNode(ISD::ADD, DL, VT, T1.getOperand(0), D);
938  // NewShl = (shl NewAdd c)
939  SDValue NewShl = DAG.getNode(ISD::SHL, DL, VT, NewAdd, C);
940  ReplaceNode(T0.getNode(), NewShl.getNode());
941  }
942 }
943 
944 // Transform: (load ch (add x (and (srl y c) Mask)))
945 // to: (load ch (add x (shl (srl y d) d-c)))
946 // where
947 // Mask = 00..0 111..1 0.0
948 // | | +-- d-c 0s, and d-c is 0, 1 or 2.
949 // | +-------- 1s
950 // +-------------- at most c 0s
951 // Motivating example:
952 // DAG combiner optimizes (add x (shl (srl y 5) 2))
953 // to (add x (and (srl y 3) 1FFFFFFC))
954 // which results in a constant-extended and(##...,lsr). This transformation
955 // undoes this simplification for cases where the shl can be folded into
956 // an addressing mode.
957 void HexagonDAGToDAGISel::ppAddrRewriteAndSrl(std::vector<SDNode*> &&Nodes) {
958  SelectionDAG &DAG = *CurDAG;
959 
960  for (SDNode *N : Nodes) {
961  unsigned Opc = N->getOpcode();
962  if (Opc != ISD::LOAD && Opc != ISD::STORE)
963  continue;
964  SDValue Addr = Opc == ISD::LOAD ? N->getOperand(1) : N->getOperand(2);
965  // Addr must match: (add x T0)
966  if (Addr.getOpcode() != ISD::ADD)
967  continue;
968  SDValue T0 = Addr.getOperand(1);
969  // T0 must match: (and T1 Mask)
970  if (T0.getOpcode() != ISD::AND)
971  continue;
972 
973  // We have an AND.
974  //
975  // Check the first operand. It must be: (srl y c).
976  SDValue S = T0.getOperand(0);
977  if (S.getOpcode() != ISD::SRL)
978  continue;
980  if (SN == nullptr)
981  continue;
982  if (SN->getAPIntValue().getBitWidth() != 32)
983  continue;
984  uint32_t CV = SN->getZExtValue();
985 
986  // Check the second operand: the supposed mask.
988  if (MN == nullptr)
989  continue;
990  if (MN->getAPIntValue().getBitWidth() != 32)
991  continue;
992  uint32_t Mask = MN->getZExtValue();
993  // Examine the mask.
994  uint32_t TZ = countTrailingZeros(Mask);
995  uint32_t M1 = countTrailingOnes(Mask >> TZ);
996  uint32_t LZ = countLeadingZeros(Mask);
997  // Trailing zeros + middle ones + leading zeros must equal the width.
998  if (TZ + M1 + LZ != 32)
999  continue;
1000  // The number of trailing zeros will be encoded in the addressing mode.
1001  if (TZ > 2)
1002  continue;
1003  // The number of leading zeros must be at most c.
1004  if (LZ > CV)
1005  continue;
1006 
1007  // All looks good.
1008  SDValue Y = S.getOperand(0);
1009  EVT VT = Addr.getValueType();
1010  SDLoc dl(S);
1011  // TZ = D-C, so D = TZ+C.
1012  SDValue D = DAG.getConstant(TZ+CV, dl, VT);
1013  SDValue DC = DAG.getConstant(TZ, dl, VT);
1014  SDValue NewSrl = DAG.getNode(ISD::SRL, dl, VT, Y, D);
1015  SDValue NewShl = DAG.getNode(ISD::SHL, dl, VT, NewSrl, DC);
1016  ReplaceNode(T0.getNode(), NewShl.getNode());
1017  }
1018 }
1019 
1020 // Transform: (op ... (zext i1 c) ...) -> (select c (op ... 0 ...)
1021 // (op ... 1 ...))
1022 void HexagonDAGToDAGISel::ppHoistZextI1(std::vector<SDNode*> &&Nodes) {
1023  SelectionDAG &DAG = *CurDAG;
1024 
1025  for (SDNode *N : Nodes) {
1026  unsigned Opc = N->getOpcode();
1027  if (Opc != ISD::ZERO_EXTEND)
1028  continue;
1029  SDValue OpI1 = N->getOperand(0);
1030  EVT OpVT = OpI1.getValueType();
1031  if (!OpVT.isSimple() || OpVT.getSimpleVT() != MVT::i1)
1032  continue;
1033  for (auto I = N->use_begin(), E = N->use_end(); I != E; ++I) {
1034  SDNode *U = *I;
1035  if (U->getNumValues() != 1)
1036  continue;
1037  EVT UVT = U->getValueType(0);
1038  if (!UVT.isSimple() || !UVT.isInteger() || UVT.getSimpleVT() == MVT::i1)
1039  continue;
1040  if (isMemOPCandidate(N, U))
1041  continue;
1042 
1043  // Potentially simplifiable operation.
1044  unsigned I1N = I.getOperandNo();
1046  for (unsigned i = 0, n = U->getNumOperands(); i != n; ++i)
1047  Ops[i] = U->getOperand(i);
1048  EVT BVT = Ops[I1N].getValueType();
1049 
1050  SDLoc dl(U);
1051  SDValue C0 = DAG.getConstant(0, dl, BVT);
1052  SDValue C1 = DAG.getConstant(1, dl, BVT);
1053  SDValue If0, If1;
1054 
1055  if (isa<MachineSDNode>(U)) {
1056  unsigned UseOpc = U->getMachineOpcode();
1057  Ops[I1N] = C0;
1058  If0 = SDValue(DAG.getMachineNode(UseOpc, dl, UVT, Ops), 0);
1059  Ops[I1N] = C1;
1060  If1 = SDValue(DAG.getMachineNode(UseOpc, dl, UVT, Ops), 0);
1061  } else {
1062  unsigned UseOpc = U->getOpcode();
1063  Ops[I1N] = C0;
1064  If0 = DAG.getNode(UseOpc, dl, UVT, Ops);
1065  Ops[I1N] = C1;
1066  If1 = DAG.getNode(UseOpc, dl, UVT, Ops);
1067  }
1068  SDValue Sel = DAG.getNode(ISD::SELECT, dl, UVT, OpI1, If1, If0);
1069  DAG.ReplaceAllUsesWith(U, Sel.getNode());
1070  }
1071  }
1072 }
1073 
1075  // Repack all nodes before calling each preprocessing function,
1076  // because each of them can modify the set of nodes.
1077  auto getNodes = [this] () -> std::vector<SDNode*> {
1078  std::vector<SDNode*> T;
1079  T.reserve(CurDAG->allnodes_size());
1080  for (SDNode &N : CurDAG->allnodes())
1081  T.push_back(&N);
1082  return T;
1083  };
1084 
1085  // Transform: (or (select c x 0) z) -> (select c (or x z) z)
1086  // (or (select c 0 y) z) -> (select c z (or y z))
1087  ppSimplifyOrSelect0(getNodes());
1088 
1089  // Transform: (store ch val (add x (add (shl y c) e)))
1090  // to: (store ch val (add x (shl (add y d) c))),
1091  // where e = (shl d c) for some integer d.
1092  // The purpose of this is to enable generation of loads/stores with
1093  // shifted addressing mode, i.e. mem(x+y<<#c). For that, the shift
1094  // value c must be 0, 1 or 2.
1095  ppAddrReorderAddShl(getNodes());
1096 
1097  // Transform: (load ch (add x (and (srl y c) Mask)))
1098  // to: (load ch (add x (shl (srl y d) d-c)))
1099  // where
1100  // Mask = 00..0 111..1 0.0
1101  // | | +-- d-c 0s, and d-c is 0, 1 or 2.
1102  // | +-------- 1s
1103  // +-------------- at most c 0s
1104  // Motivating example:
1105  // DAG combiner optimizes (add x (shl (srl y 5) 2))
1106  // to (add x (and (srl y 3) 1FFFFFFC))
1107  // which results in a constant-extended and(##...,lsr). This transformation
1108  // undoes this simplification for cases where the shl can be folded into
1109  // an addressing mode.
1110  ppAddrRewriteAndSrl(getNodes());
1111 
1112  // Transform: (op ... (zext i1 c) ...) -> (select c (op ... 0 ...)
1113  // (op ... 1 ...))
1114  ppHoistZextI1(getNodes());
1115 
1116  DEBUG_WITH_TYPE("isel", {
1117  dbgs() << "Preprocessed (Hexagon) selection DAG:";
1118  CurDAG->dump();
1119  });
1120 
1122  rebalanceAddressTrees();
1123 
1124  DEBUG_WITH_TYPE("isel", {
1125  dbgs() << "Address tree balanced selection DAG:";
1126  CurDAG->dump();
1127  });
1128  }
1129 }
1130 
1132  auto &HST = static_cast<const HexagonSubtarget&>(MF->getSubtarget());
1133  auto &HFI = *HST.getFrameLowering();
1134  if (!HFI.needsAligna(*MF))
1135  return;
1136 
1137  MachineFrameInfo &MFI = MF->getFrameInfo();
1138  MachineBasicBlock *EntryBB = &MF->front();
1139  unsigned AR = FuncInfo->CreateReg(MVT::i32);
1140  unsigned MaxA = MFI.getMaxAlignment();
1141  BuildMI(EntryBB, DebugLoc(), HII->get(Hexagon::PS_aligna), AR)
1142  .addImm(MaxA);
1143  MF->getInfo<HexagonMachineFunctionInfo>()->setStackAlignBaseVReg(AR);
1144 }
1145 
1146 // Match a frame index that can be used in an addressing mode.
1148  if (N.getOpcode() != ISD::FrameIndex)
1149  return false;
1150  auto &HFI = *HST->getFrameLowering();
1151  MachineFrameInfo &MFI = MF->getFrameInfo();
1152  int FX = cast<FrameIndexSDNode>(N)->getIndex();
1153  if (!MFI.isFixedObjectIndex(FX) && HFI.needsAligna(*MF))
1154  return false;
1156  return true;
1157 }
1158 
1160  return SelectGlobalAddress(N, R, false, 0);
1161 }
1162 
1164  return SelectGlobalAddress(N, R, true, 0);
1165 }
1166 
1168  return SelectAnyImmediate(N, R, 0);
1169 }
1170 
1172  return SelectAnyImmediate(N, R, 0);
1173 }
1175  return SelectAnyImmediate(N, R, 1);
1176 }
1178  return SelectAnyImmediate(N, R, 2);
1179 }
1181  return SelectAnyImmediate(N, R, 3);
1182 }
1183 
1185  EVT T = N.getValueType();
1186  if (!T.isInteger() || T.getSizeInBits() != 32 || !isa<ConstantSDNode>(N))
1187  return false;
1188  R = N;
1189  return true;
1190 }
1191 
1193  uint32_t LogAlign) {
1194  auto IsAligned = [LogAlign] (uint64_t V) -> bool {
1195  return alignTo(V, (uint64_t)1 << LogAlign) == V;
1196  };
1197 
1198  switch (N.getOpcode()) {
1199  case ISD::Constant: {
1200  if (N.getValueType() != MVT::i32)
1201  return false;
1202  int32_t V = cast<const ConstantSDNode>(N)->getZExtValue();
1203  if (!IsAligned(V))
1204  return false;
1205  R = CurDAG->getTargetConstant(V, SDLoc(N), N.getValueType());
1206  return true;
1207  }
1208  case HexagonISD::JT:
1209  case HexagonISD::CP:
1210  // These are assumed to always be aligned at at least 8-byte boundary.
1211  if (LogAlign > 3)
1212  return false;
1213  R = N.getOperand(0);
1214  return true;
1215  case ISD::ExternalSymbol:
1216  // Symbols may be aligned at any boundary.
1217  if (LogAlign > 0)
1218  return false;
1219  R = N;
1220  return true;
1221  case ISD::BlockAddress:
1222  // Block address is always aligned at at least 4-byte boundary.
1223  if (LogAlign > 2 || !IsAligned(cast<BlockAddressSDNode>(N)->getOffset()))
1224  return false;
1225  R = N;
1226  return true;
1227  }
1228 
1229  if (SelectGlobalAddress(N, R, false, LogAlign) ||
1230  SelectGlobalAddress(N, R, true, LogAlign))
1231  return true;
1232 
1233  return false;
1234 }
1235 
1237  bool UseGP, uint32_t LogAlign) {
1238  auto IsAligned = [LogAlign] (uint64_t V) -> bool {
1239  return alignTo(V, (uint64_t)1 << LogAlign) == V;
1240  };
1241 
1242  switch (N.getOpcode()) {
1243  case ISD::ADD: {
1244  SDValue N0 = N.getOperand(0);
1245  SDValue N1 = N.getOperand(1);
1246  unsigned GAOpc = N0.getOpcode();
1247  if (UseGP && GAOpc != HexagonISD::CONST32_GP)
1248  return false;
1249  if (!UseGP && GAOpc != HexagonISD::CONST32)
1250  return false;
1251  if (ConstantSDNode *Const = dyn_cast<ConstantSDNode>(N1)) {
1252  SDValue Addr = N0.getOperand(0);
1253  // For the purpose of alignment, sextvalue and zextvalue are the same.
1254  if (!IsAligned(Const->getZExtValue()))
1255  return false;
1256  if (GlobalAddressSDNode *GA = dyn_cast<GlobalAddressSDNode>(Addr)) {
1257  if (GA->getOpcode() == ISD::TargetGlobalAddress) {
1258  uint64_t NewOff = GA->getOffset() + (uint64_t)Const->getSExtValue();
1259  R = CurDAG->getTargetGlobalAddress(GA->getGlobal(), SDLoc(Const),
1260  N.getValueType(), NewOff);
1261  return true;
1262  }
1263  }
1264  }
1265  break;
1266  }
1267  case HexagonISD::CP:
1268  case HexagonISD::JT:
1269  case HexagonISD::CONST32:
1270  // The operand(0) of CONST32 is TargetGlobalAddress, which is what we
1271  // want in the instruction.
1272  if (!UseGP)
1273  R = N.getOperand(0);
1274  return !UseGP;
1276  if (UseGP)
1277  R = N.getOperand(0);
1278  return UseGP;
1279  default:
1280  return false;
1281  }
1282 
1283  return false;
1284 }
1285 
1287  // This (complex pattern) function is meant to detect a sign-extension
1288  // i32->i64 on a per-operand basis. This would allow writing single
1289  // patterns that would cover a number of combinations of different ways
1290  // a sign-extensions could be written. For example:
1291  // (mul (DetectUseSxtw x) (DetectUseSxtw y)) -> (M2_dpmpyss_s0 x y)
1292  // could match either one of these:
1293  // (mul (sext x) (sext_inreg y))
1294  // (mul (sext-load *p) (sext_inreg y))
1295  // (mul (sext_inreg x) (sext y))
1296  // etc.
1297  //
1298  // The returned value will have type i64 and its low word will
1299  // contain the value being extended. The high bits are not specified.
1300  // The returned type is i64 because the original type of N was i64,
1301  // but the users of this function should only use the low-word of the
1302  // result, e.g.
1303  // (mul sxtw:x, sxtw:y) -> (M2_dpmpyss_s0 (LoReg sxtw:x), (LoReg sxtw:y))
1304 
1305  if (N.getValueType() != MVT::i64)
1306  return false;
1307  unsigned Opc = N.getOpcode();
1308  switch (Opc) {
1309  case ISD::SIGN_EXTEND:
1310  case ISD::SIGN_EXTEND_INREG: {
1311  // sext_inreg has the source type as a separate operand.
1312  EVT T = Opc == ISD::SIGN_EXTEND
1313  ? N.getOperand(0).getValueType()
1314  : cast<VTSDNode>(N.getOperand(1))->getVT();
1315  if (T.getSizeInBits() != 32)
1316  return false;
1317  R = N.getOperand(0);
1318  break;
1319  }
1320  case ISD::LOAD: {
1321  LoadSDNode *L = cast<LoadSDNode>(N);
1322  if (L->getExtensionType() != ISD::SEXTLOAD)
1323  return false;
1324  // All extending loads extend to i32, so even if the value in
1325  // memory is shorter than 32 bits, it will be i32 after the load.
1326  if (L->getMemoryVT().getSizeInBits() > 32)
1327  return false;
1328  R = N;
1329  break;
1330  }
1331  default:
1332  return false;
1333  }
1334  EVT RT = R.getValueType();
1335  if (RT == MVT::i64)
1336  return true;
1337  assert(RT == MVT::i32);
1338  // This is only to produce a value of type i64. Do not rely on the
1339  // high bits produced by this.
1340  const SDLoc &dl(N);
1341  SDValue Ops[] = {
1342  CurDAG->getTargetConstant(Hexagon::DoubleRegsRegClassID, dl, MVT::i32),
1343  R, CurDAG->getTargetConstant(Hexagon::isub_hi, dl, MVT::i32),
1344  R, CurDAG->getTargetConstant(Hexagon::isub_lo, dl, MVT::i32)
1345  };
1346  SDNode *T = CurDAG->getMachineNode(TargetOpcode::REG_SEQUENCE, dl,
1347  MVT::i64, Ops);
1348  R = SDValue(T, 0);
1349  return true;
1350 }
1351 
1352 bool HexagonDAGToDAGISel::keepsLowBits(const SDValue &Val, unsigned NumBits,
1353  SDValue &Src) {
1354  unsigned Opc = Val.getOpcode();
1355  switch (Opc) {
1356  case ISD::SIGN_EXTEND:
1357  case ISD::ZERO_EXTEND:
1358  case ISD::ANY_EXTEND: {
1359  const SDValue &Op0 = Val.getOperand(0);
1360  EVT T = Op0.getValueType();
1361  if (T.isInteger() && T.getSizeInBits() == NumBits) {
1362  Src = Op0;
1363  return true;
1364  }
1365  break;
1366  }
1368  case ISD::AssertSext:
1369  case ISD::AssertZext:
1370  if (Val.getOperand(0).getValueType().isInteger()) {
1371  VTSDNode *T = cast<VTSDNode>(Val.getOperand(1));
1372  if (T->getVT().getSizeInBits() == NumBits) {
1373  Src = Val.getOperand(0);
1374  return true;
1375  }
1376  }
1377  break;
1378  case ISD::AND: {
1379  // Check if this is an AND with NumBits of lower bits set to 1.
1380  uint64_t Mask = (1 << NumBits) - 1;
1381  if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Val.getOperand(0))) {
1382  if (C->getZExtValue() == Mask) {
1383  Src = Val.getOperand(1);
1384  return true;
1385  }
1386  }
1387  if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Val.getOperand(1))) {
1388  if (C->getZExtValue() == Mask) {
1389  Src = Val.getOperand(0);
1390  return true;
1391  }
1392  }
1393  break;
1394  }
1395  case ISD::OR:
1396  case ISD::XOR: {
1397  // OR/XOR with the lower NumBits bits set to 0.
1398  uint64_t Mask = (1 << NumBits) - 1;
1399  if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Val.getOperand(0))) {
1400  if ((C->getZExtValue() & Mask) == 0) {
1401  Src = Val.getOperand(1);
1402  return true;
1403  }
1404  }
1405  if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Val.getOperand(1))) {
1406  if ((C->getZExtValue() & Mask) == 0) {
1407  Src = Val.getOperand(0);
1408  return true;
1409  }
1410  }
1411  }
1412  default:
1413  break;
1414  }
1415  return false;
1416 }
1417 
1418 
1419 bool HexagonDAGToDAGISel::isOrEquivalentToAdd(const SDNode *N) const {
1420  assert(N->getOpcode() == ISD::OR);
1421  auto *C = dyn_cast<ConstantSDNode>(N->getOperand(1));
1422  if (!C)
1423  return false;
1424 
1425  // Detect when "or" is used to add an offset to a stack object.
1426  if (auto *FN = dyn_cast<FrameIndexSDNode>(N->getOperand(0))) {
1427  MachineFrameInfo &MFI = MF->getFrameInfo();
1428  unsigned A = MFI.getObjectAlignment(FN->getIndex());
1429  assert(isPowerOf2_32(A));
1430  int32_t Off = C->getSExtValue();
1431  // If the alleged offset fits in the zero bits guaranteed by
1432  // the alignment, then this or is really an add.
1433  return (Off >= 0) && (((A-1) & Off) == unsigned(Off));
1434  }
1435  return false;
1436 }
1437 
1438 bool HexagonDAGToDAGISel::isAlignedMemNode(const MemSDNode *N) const {
1439  return N->getAlignment() >= N->getMemoryVT().getStoreSize();
1440 }
1441 
1442 bool HexagonDAGToDAGISel::isSmallStackStore(const StoreSDNode *N) const {
1443  unsigned StackSize = MF->getFrameInfo().estimateStackSize(*MF);
1444  switch (N->getMemoryVT().getStoreSize()) {
1445  case 1:
1446  return StackSize <= 56; // 1*2^6 - 8
1447  case 2:
1448  return StackSize <= 120; // 2*2^6 - 8
1449  case 4:
1450  return StackSize <= 248; // 4*2^6 - 8
1451  default:
1452  return false;
1453  }
1454 }
1455 
1456 // Return true when the given node fits in a positive half word.
1457 bool HexagonDAGToDAGISel::isPositiveHalfWord(const SDNode *N) const {
1458  if (const ConstantSDNode *CN = dyn_cast<const ConstantSDNode>(N)) {
1459  int64_t V = CN->getSExtValue();
1460  return V > 0 && isInt<16>(V);
1461  }
1462  if (N->getOpcode() == ISD::SIGN_EXTEND_INREG) {
1463  const VTSDNode *VN = dyn_cast<const VTSDNode>(N->getOperand(1));
1464  return VN->getVT().getSizeInBits() <= 16;
1465  }
1466  return false;
1467 }
1468 
1469 bool HexagonDAGToDAGISel::hasOneUse(const SDNode *N) const {
1470  return !CheckSingleUse || N->hasOneUse();
1471 }
1472 
1473 ////////////////////////////////////////////////////////////////////////////////
1474 // Rebalancing of address calculation trees
1475 
1476 static bool isOpcodeHandled(const SDNode *N) {
1477  switch (N->getOpcode()) {
1478  case ISD::ADD:
1479  case ISD::MUL:
1480  return true;
1481  case ISD::SHL:
1482  // We only handle constant shifts because these can be easily flattened
1483  // into multiplications by 2^Op1.
1484  return isa<ConstantSDNode>(N->getOperand(1).getNode());
1485  default:
1486  return false;
1487  }
1488 }
1489 
1490 /// \brief Return the weight of an SDNode
1491 int HexagonDAGToDAGISel::getWeight(SDNode *N) {
1492  if (!isOpcodeHandled(N))
1493  return 1;
1494  assert(RootWeights.count(N) && "Cannot get weight of unseen root!");
1495  assert(RootWeights[N] != -1 && "Cannot get weight of unvisited root!");
1496  assert(RootWeights[N] != -2 && "Cannot get weight of RAWU'd root!");
1497  return RootWeights[N];
1498 }
1499 
1500 int HexagonDAGToDAGISel::getHeight(SDNode *N) {
1501  if (!isOpcodeHandled(N))
1502  return 0;
1503  assert(RootWeights.count(N) && RootWeights[N] >= 0 &&
1504  "Cannot query height of unvisited/RAUW'd node!");
1505  return RootHeights[N];
1506 }
1507 
1508 namespace {
1509 struct WeightedLeaf {
1510  SDValue Value;
1511  int Weight;
1512  int InsertionOrder;
1513 
1514  WeightedLeaf() : Value(SDValue()) { }
1515 
1516  WeightedLeaf(SDValue Value, int Weight, int InsertionOrder) :
1517  Value(Value), Weight(Weight), InsertionOrder(InsertionOrder) {
1518  assert(Weight >= 0 && "Weight must be >= 0");
1519  }
1520 
1521  static bool Compare(const WeightedLeaf &A, const WeightedLeaf &B) {
1522  assert(A.Value.getNode() && B.Value.getNode());
1523  return A.Weight == B.Weight ?
1524  (A.InsertionOrder > B.InsertionOrder) :
1525  (A.Weight > B.Weight);
1526  }
1527 };
1528 
1529 /// A specialized priority queue for WeigthedLeaves. It automatically folds
1530 /// constants and allows removal of non-top elements while maintaining the
1531 /// priority order.
1532 class LeafPrioQueue {
1534  bool HaveConst;
1535  WeightedLeaf ConstElt;
1536  unsigned Opcode;
1537 
1538 public:
1539  bool empty() {
1540  return (!HaveConst && Q.empty());
1541  }
1542 
1543  size_t size() {
1544  return Q.size() + HaveConst;
1545  }
1546 
1547  bool hasConst() {
1548  return HaveConst;
1549  }
1550 
1551  const WeightedLeaf &top() {
1552  if (HaveConst)
1553  return ConstElt;
1554  return Q.front();
1555  }
1556 
1557  WeightedLeaf pop() {
1558  if (HaveConst) {
1559  HaveConst = false;
1560  return ConstElt;
1561  }
1562  std::pop_heap(Q.begin(), Q.end(), WeightedLeaf::Compare);
1563  return Q.pop_back_val();
1564  }
1565 
1566  void push(WeightedLeaf L, bool SeparateConst=true) {
1567  if (!HaveConst && SeparateConst && isa<ConstantSDNode>(L.Value)) {
1568  if (Opcode == ISD::MUL &&
1569  cast<ConstantSDNode>(L.Value)->getSExtValue() == 1)
1570  return;
1571  if (Opcode == ISD::ADD &&
1572  cast<ConstantSDNode>(L.Value)->getSExtValue() == 0)
1573  return;
1574 
1575  HaveConst = true;
1576  ConstElt = L;
1577  } else {
1578  Q.push_back(L);
1579  std::push_heap(Q.begin(), Q.end(), WeightedLeaf::Compare);
1580  }
1581  }
1582 
1583  /// Push L to the bottom of the queue regardless of its weight. If L is
1584  /// constant, it will not be folded with other constants in the queue.
1585  void pushToBottom(WeightedLeaf L) {
1586  L.Weight = 1000;
1587  push(L, false);
1588  }
1589 
1590  /// Search for a SHL(x, [<=MaxAmount]) subtree in the queue, return the one of
1591  /// lowest weight and remove it from the queue.
1592  WeightedLeaf findSHL(uint64_t MaxAmount);
1593 
1594  WeightedLeaf findMULbyConst();
1595 
1596  LeafPrioQueue(unsigned Opcode) :
1597  HaveConst(false), Opcode(Opcode) { }
1598 };
1599 } // end anonymous namespace
1600 
1601 WeightedLeaf LeafPrioQueue::findSHL(uint64_t MaxAmount) {
1602  int ResultPos;
1603  WeightedLeaf Result;
1604 
1605  for (int Pos = 0, End = Q.size(); Pos != End; ++Pos) {
1606  const WeightedLeaf &L = Q[Pos];
1607  const SDValue &Val = L.Value;
1608  if (Val.getOpcode() != ISD::SHL ||
1609  !isa<ConstantSDNode>(Val.getOperand(1)) ||
1610  Val.getConstantOperandVal(1) > MaxAmount)
1611  continue;
1612  if (!Result.Value.getNode() || Result.Weight > L.Weight ||
1613  (Result.Weight == L.Weight && Result.InsertionOrder > L.InsertionOrder))
1614  {
1615  Result = L;
1616  ResultPos = Pos;
1617  }
1618  }
1619 
1620  if (Result.Value.getNode()) {
1621  Q.erase(&Q[ResultPos]);
1622  std::make_heap(Q.begin(), Q.end(), WeightedLeaf::Compare);
1623  }
1624 
1625  return Result;
1626 }
1627 
1628 WeightedLeaf LeafPrioQueue::findMULbyConst() {
1629  int ResultPos;
1630  WeightedLeaf Result;
1631 
1632  for (int Pos = 0, End = Q.size(); Pos != End; ++Pos) {
1633  const WeightedLeaf &L = Q[Pos];
1634  const SDValue &Val = L.Value;
1635  if (Val.getOpcode() != ISD::MUL ||
1636  !isa<ConstantSDNode>(Val.getOperand(1)) ||
1637  Val.getConstantOperandVal(1) > 127)
1638  continue;
1639  if (!Result.Value.getNode() || Result.Weight > L.Weight ||
1640  (Result.Weight == L.Weight && Result.InsertionOrder > L.InsertionOrder))
1641  {
1642  Result = L;
1643  ResultPos = Pos;
1644  }
1645  }
1646 
1647  if (Result.Value.getNode()) {
1648  Q.erase(&Q[ResultPos]);
1649  std::make_heap(Q.begin(), Q.end(), WeightedLeaf::Compare);
1650  }
1651 
1652  return Result;
1653 }
1654 
1655 SDValue HexagonDAGToDAGISel::getMultiplierForSHL(SDNode *N) {
1656  uint64_t MulFactor = 1ull << N->getConstantOperandVal(1);
1657  return CurDAG->getConstant(MulFactor, SDLoc(N),
1658  N->getOperand(1).getValueType());
1659 }
1660 
1661 /// @returns the value x for which 2^x is a factor of Val
1662 static unsigned getPowerOf2Factor(SDValue Val) {
1663  if (Val.getOpcode() == ISD::MUL) {
1664  unsigned MaxFactor = 0;
1665  for (int i = 0; i < 2; ++i) {
1667  if (!C)
1668  continue;
1669  const APInt &CInt = C->getAPIntValue();
1670  if (CInt.getBoolValue())
1671  MaxFactor = CInt.countTrailingZeros();
1672  }
1673  return MaxFactor;
1674  }
1675  if (Val.getOpcode() == ISD::SHL) {
1676  if (!isa<ConstantSDNode>(Val.getOperand(1).getNode()))
1677  return 0;
1678  return (unsigned) Val.getConstantOperandVal(1);
1679  }
1680 
1681  return 0;
1682 }
1683 
1684 /// @returns true if V>>Amount will eliminate V's operation on its child
1685 static bool willShiftRightEliminate(SDValue V, unsigned Amount) {
1686  if (V.getOpcode() == ISD::MUL) {
1687  SDValue Ops[] = { V.getOperand(0), V.getOperand(1) };
1688  for (int i = 0; i < 2; ++i)
1689  if (isa<ConstantSDNode>(Ops[i].getNode()) &&
1690  V.getConstantOperandVal(i) % (1ULL << Amount) == 0) {
1691  uint64_t NewConst = V.getConstantOperandVal(i) >> Amount;
1692  return (NewConst == 1);
1693  }
1694  } else if (V.getOpcode() == ISD::SHL) {
1695  return (Amount == V.getConstantOperandVal(1));
1696  }
1697 
1698  return false;
1699 }
1700 
1701 SDValue HexagonDAGToDAGISel::factorOutPowerOf2(SDValue V, unsigned Power) {
1702  SDValue Ops[] = { V.getOperand(0), V.getOperand(1) };
1703  if (V.getOpcode() == ISD::MUL) {
1704  for (int i=0; i < 2; ++i) {
1705  if (isa<ConstantSDNode>(Ops[i].getNode()) &&
1706  V.getConstantOperandVal(i) % ((uint64_t)1 << Power) == 0) {
1707  uint64_t NewConst = V.getConstantOperandVal(i) >> Power;
1708  if (NewConst == 1)
1709  return Ops[!i];
1710  Ops[i] = CurDAG->getConstant(NewConst,
1711  SDLoc(V), V.getValueType());
1712  break;
1713  }
1714  }
1715  } else if (V.getOpcode() == ISD::SHL) {
1716  uint64_t ShiftAmount = V.getConstantOperandVal(1);
1717  if (ShiftAmount == Power)
1718  return Ops[0];
1719  Ops[1] = CurDAG->getConstant(ShiftAmount - Power,
1720  SDLoc(V), V.getValueType());
1721  }
1722 
1723  return CurDAG->getNode(V.getOpcode(), SDLoc(V), V.getValueType(), Ops);
1724 }
1725 
1726 static bool isTargetConstant(const SDValue &V) {
1727  return V.getOpcode() == HexagonISD::CONST32 ||
1729 }
1730 
1731 unsigned HexagonDAGToDAGISel::getUsesInFunction(const Value *V) {
1732  if (GAUsesInFunction.count(V))
1733  return GAUsesInFunction[V];
1734 
1735  unsigned Result = 0;
1736  const Function *CurF = CurDAG->getMachineFunction().getFunction();
1737  for (const User *U : V->users()) {
1738  if (isa<Instruction>(U) &&
1739  cast<Instruction>(U)->getParent()->getParent() == CurF)
1740  ++Result;
1741  }
1742 
1743  GAUsesInFunction[V] = Result;
1744 
1745  return Result;
1746 }
1747 
1748 /// Note - After calling this, N may be dead. It may have been replaced by a
1749 /// new node, so always use the returned value in place of N.
1750 ///
1751 /// @returns The SDValue taking the place of N (which could be N if it is
1752 /// unchanged)
1753 SDValue HexagonDAGToDAGISel::balanceSubTree(SDNode *N, bool TopLevel) {
1754  assert(RootWeights.count(N) && "Cannot balance non-root node.");
1755  assert(RootWeights[N] != -2 && "This node was RAUW'd!");
1756  assert(!TopLevel || N->getOpcode() == ISD::ADD);
1757 
1758  // Return early if this node was already visited
1759  if (RootWeights[N] != -1)
1760  return SDValue(N, 0);
1761 
1762  assert(isOpcodeHandled(N));
1763 
1764  SDValue Op0 = N->getOperand(0);
1765  SDValue Op1 = N->getOperand(1);
1766 
1767  // Return early if the operands will remain unchanged or are all roots
1768  if ((!isOpcodeHandled(Op0.getNode()) || RootWeights.count(Op0.getNode())) &&
1769  (!isOpcodeHandled(Op1.getNode()) || RootWeights.count(Op1.getNode()))) {
1770  SDNode *Op0N = Op0.getNode();
1771  int Weight;
1772  if (isOpcodeHandled(Op0N) && RootWeights[Op0N] == -1) {
1773  Weight = getWeight(balanceSubTree(Op0N).getNode());
1774  // Weight = calculateWeight(Op0N);
1775  } else
1776  Weight = getWeight(Op0N);
1777 
1778  SDNode *Op1N = N->getOperand(1).getNode(); // Op1 may have been RAUWd
1779  if (isOpcodeHandled(Op1N) && RootWeights[Op1N] == -1) {
1780  Weight += getWeight(balanceSubTree(Op1N).getNode());
1781  // Weight += calculateWeight(Op1N);
1782  } else
1783  Weight += getWeight(Op1N);
1784 
1785  RootWeights[N] = Weight;
1786  RootHeights[N] = std::max(getHeight(N->getOperand(0).getNode()),
1787  getHeight(N->getOperand(1).getNode())) + 1;
1788 
1789  DEBUG(dbgs() << "--> No need to balance root (Weight=" << Weight
1790  << " Height=" << RootHeights[N] << "): ");
1791  DEBUG(N->dump());
1792 
1793  return SDValue(N, 0);
1794  }
1795 
1796  DEBUG(dbgs() << "** Balancing root node: ");
1797  DEBUG(N->dump());
1798 
1799  unsigned NOpcode = N->getOpcode();
1800 
1801  LeafPrioQueue Leaves(NOpcode);
1802  SmallVector<SDValue, 4> Worklist;
1803  Worklist.push_back(SDValue(N, 0));
1804 
1805  // SHL nodes will be converted to MUL nodes
1806  if (NOpcode == ISD::SHL)
1807  NOpcode = ISD::MUL;
1808 
1809  bool CanFactorize = false;
1810  WeightedLeaf Mul1, Mul2;
1811  unsigned MaxPowerOf2 = 0;
1812  WeightedLeaf GA;
1813 
1814  // Do not try to factor out a shift if there is already a shift at the tip of
1815  // the tree.
1816  bool HaveTopLevelShift = false;
1817  if (TopLevel &&
1818  ((isOpcodeHandled(Op0.getNode()) && Op0.getOpcode() == ISD::SHL &&
1819  Op0.getConstantOperandVal(1) < 4) ||
1820  (isOpcodeHandled(Op1.getNode()) && Op1.getOpcode() == ISD::SHL &&
1821  Op1.getConstantOperandVal(1) < 4)))
1822  HaveTopLevelShift = true;
1823 
1824  // Flatten the subtree into an ordered list of leaves; at the same time
1825  // determine whether the tree is already balanced.
1826  int InsertionOrder = 0;
1827  SmallDenseMap<SDValue, int> NodeHeights;
1828  bool Imbalanced = false;
1829  int CurrentWeight = 0;
1830  while (!Worklist.empty()) {
1831  SDValue Child = Worklist.pop_back_val();
1832 
1833  if (Child.getNode() != N && RootWeights.count(Child.getNode())) {
1834  // CASE 1: Child is a root note
1835 
1836  int Weight = RootWeights[Child.getNode()];
1837  if (Weight == -1) {
1838  Child = balanceSubTree(Child.getNode());
1839  // calculateWeight(Child.getNode());
1840  Weight = getWeight(Child.getNode());
1841  } else if (Weight == -2) {
1842  // Whoops, this node was RAUWd by one of the balanceSubTree calls we
1843  // made. Our worklist isn't up to date anymore.
1844  // Restart the whole process.
1845  DEBUG(dbgs() << "--> Subtree was RAUWd. Restarting...\n");
1846  return balanceSubTree(N, TopLevel);
1847  }
1848 
1849  NodeHeights[Child] = 1;
1850  CurrentWeight += Weight;
1851 
1852  unsigned PowerOf2;
1853  if (TopLevel && !CanFactorize && !HaveTopLevelShift &&
1854  (Child.getOpcode() == ISD::MUL || Child.getOpcode() == ISD::SHL) &&
1855  Child.hasOneUse() && (PowerOf2 = getPowerOf2Factor(Child))) {
1856  // Try to identify two factorizable MUL/SHL children greedily. Leave
1857  // them out of the priority queue for now so we can deal with them
1858  // after.
1859  if (!Mul1.Value.getNode()) {
1860  Mul1 = WeightedLeaf(Child, Weight, InsertionOrder++);
1861  MaxPowerOf2 = PowerOf2;
1862  } else {
1863  Mul2 = WeightedLeaf(Child, Weight, InsertionOrder++);
1864  MaxPowerOf2 = std::min(MaxPowerOf2, PowerOf2);
1865 
1866  // Our addressing modes can only shift by a maximum of 3
1867  if (MaxPowerOf2 > 3)
1868  MaxPowerOf2 = 3;
1869 
1870  CanFactorize = true;
1871  }
1872  } else
1873  Leaves.push(WeightedLeaf(Child, Weight, InsertionOrder++));
1874  } else if (!isOpcodeHandled(Child.getNode())) {
1875  // CASE 2: Child is an unhandled kind of node (e.g. constant)
1876  int Weight = getWeight(Child.getNode());
1877 
1878  NodeHeights[Child] = getHeight(Child.getNode());
1879  CurrentWeight += Weight;
1880 
1881  if (isTargetConstant(Child) && !GA.Value.getNode())
1882  GA = WeightedLeaf(Child, Weight, InsertionOrder++);
1883  else
1884  Leaves.push(WeightedLeaf(Child, Weight, InsertionOrder++));
1885  } else {
1886  // CASE 3: Child is a subtree of same opcode
1887  // Visit children first, then flatten.
1888  unsigned ChildOpcode = Child.getOpcode();
1889  assert(ChildOpcode == NOpcode ||
1890  (NOpcode == ISD::MUL && ChildOpcode == ISD::SHL));
1891 
1892  // Convert SHL to MUL
1893  SDValue Op1;
1894  if (ChildOpcode == ISD::SHL)
1895  Op1 = getMultiplierForSHL(Child.getNode());
1896  else
1897  Op1 = Child->getOperand(1);
1898 
1899  if (!NodeHeights.count(Op1) || !NodeHeights.count(Child->getOperand(0))) {
1900  assert(!NodeHeights.count(Child) && "Parent visited before children?");
1901  // Visit children first, then re-visit this node
1902  Worklist.push_back(Child);
1903  Worklist.push_back(Op1);
1904  Worklist.push_back(Child->getOperand(0));
1905  } else {
1906  // Back at this node after visiting the children
1907  if (std::abs(NodeHeights[Op1] - NodeHeights[Child->getOperand(0)]) > 1)
1908  Imbalanced = true;
1909 
1910  NodeHeights[Child] = std::max(NodeHeights[Op1],
1911  NodeHeights[Child->getOperand(0)]) + 1;
1912  }
1913  }
1914  }
1915 
1916  DEBUG(dbgs() << "--> Current height=" << NodeHeights[SDValue(N, 0)]
1917  << " weight=" << CurrentWeight << " imbalanced="
1918  << Imbalanced << "\n");
1919 
1920  // Transform MUL(x, C * 2^Y) + SHL(z, Y) -> SHL(ADD(MUL(x, C), z), Y)
1921  // This factors out a shift in order to match memw(a<<Y+b).
1922  if (CanFactorize && (willShiftRightEliminate(Mul1.Value, MaxPowerOf2) ||
1923  willShiftRightEliminate(Mul2.Value, MaxPowerOf2))) {
1924  DEBUG(dbgs() << "--> Found common factor for two MUL children!\n");
1925  int Weight = Mul1.Weight + Mul2.Weight;
1926  int Height = std::max(NodeHeights[Mul1.Value], NodeHeights[Mul2.Value]) + 1;
1927  SDValue Mul1Factored = factorOutPowerOf2(Mul1.Value, MaxPowerOf2);
1928  SDValue Mul2Factored = factorOutPowerOf2(Mul2.Value, MaxPowerOf2);
1929  SDValue Sum = CurDAG->getNode(ISD::ADD, SDLoc(N), Mul1.Value.getValueType(),
1930  Mul1Factored, Mul2Factored);
1931  SDValue Const = CurDAG->getConstant(MaxPowerOf2, SDLoc(N),
1932  Mul1.Value.getValueType());
1933  SDValue New = CurDAG->getNode(ISD::SHL, SDLoc(N), Mul1.Value.getValueType(),
1934  Sum, Const);
1935  NodeHeights[New] = Height;
1936  Leaves.push(WeightedLeaf(New, Weight, Mul1.InsertionOrder));
1937  } else if (Mul1.Value.getNode()) {
1938  // We failed to factorize two MULs, so now the Muls are left outside the
1939  // queue... add them back.
1940  Leaves.push(Mul1);
1941  if (Mul2.Value.getNode())
1942  Leaves.push(Mul2);
1943  CanFactorize = false;
1944  }
1945 
1946  // Combine GA + Constant -> GA+Offset, but only if GA is not used elsewhere
1947  // and the root node itself is not used more than twice. This reduces the
1948  // amount of additional constant extenders introduced by this optimization.
1949  bool CombinedGA = false;
1950  if (NOpcode == ISD::ADD && GA.Value.getNode() && Leaves.hasConst() &&
1951  GA.Value.hasOneUse() && N->use_size() < 3) {
1952  GlobalAddressSDNode *GANode =
1953  cast<GlobalAddressSDNode>(GA.Value.getOperand(0));
1954  ConstantSDNode *Offset = cast<ConstantSDNode>(Leaves.top().Value);
1955 
1956  if (getUsesInFunction(GANode->getGlobal()) == 1 && Offset->hasOneUse() &&
1958  DEBUG(dbgs() << "--> Combining GA and offset (" << Offset->getSExtValue()
1959  << "): ");
1960  DEBUG(GANode->dump());
1961 
1962  SDValue NewTGA =
1963  CurDAG->getTargetGlobalAddress(GANode->getGlobal(), SDLoc(GA.Value),
1964  GANode->getValueType(0),
1965  GANode->getOffset() + (uint64_t)Offset->getSExtValue());
1966  GA.Value = CurDAG->getNode(GA.Value.getOpcode(), SDLoc(GA.Value),
1967  GA.Value.getValueType(), NewTGA);
1968  GA.Weight += Leaves.top().Weight;
1969 
1970  NodeHeights[GA.Value] = getHeight(GA.Value.getNode());
1971  CombinedGA = true;
1972 
1973  Leaves.pop(); // Remove the offset constant from the queue
1974  }
1975  }
1976 
1977  if ((RebalanceOnlyForOptimizations && !CanFactorize && !CombinedGA) ||
1978  (RebalanceOnlyImbalancedTrees && !Imbalanced)) {
1979  RootWeights[N] = CurrentWeight;
1980  RootHeights[N] = NodeHeights[SDValue(N, 0)];
1981 
1982  return SDValue(N, 0);
1983  }
1984 
1985  // Combine GA + SHL(x, C<=31) so we will match Rx=add(#u8,asl(Rx,#U5))
1986  if (NOpcode == ISD::ADD && GA.Value.getNode()) {
1987  WeightedLeaf SHL = Leaves.findSHL(31);
1988  if (SHL.Value.getNode()) {
1989  int Height = std::max(NodeHeights[GA.Value], NodeHeights[SHL.Value]) + 1;
1990  GA.Value = CurDAG->getNode(ISD::ADD, SDLoc(GA.Value),
1991  GA.Value.getValueType(),
1992  GA.Value, SHL.Value);
1993  GA.Weight = SHL.Weight; // Specifically ignore the GA weight here
1994  NodeHeights[GA.Value] = Height;
1995  }
1996  }
1997 
1998  if (GA.Value.getNode())
1999  Leaves.push(GA);
2000 
2001  // If this is the top level and we haven't factored out a shift, we should try
2002  // to move a constant to the bottom to match addressing modes like memw(rX+C)
2003  if (TopLevel && !CanFactorize && Leaves.hasConst()) {
2004  DEBUG(dbgs() << "--> Pushing constant to tip of tree.");
2005  Leaves.pushToBottom(Leaves.pop());
2006  }
2007 
2008  const DataLayout &DL = CurDAG->getDataLayout();
2009  const TargetLowering &TLI = *getTargetLowering();
2010 
2011  // Rebuild the tree using Huffman's algorithm
2012  while (Leaves.size() > 1) {
2013  WeightedLeaf L0 = Leaves.pop();
2014 
2015  // See whether we can grab a MUL to form an add(Rx,mpyi(Ry,#u6)),
2016  // otherwise just get the next leaf
2017  WeightedLeaf L1 = Leaves.findMULbyConst();
2018  if (!L1.Value.getNode())
2019  L1 = Leaves.pop();
2020 
2021  assert(L0.Weight <= L1.Weight && "Priority queue is broken!");
2022 
2023  SDValue V0 = L0.Value;
2024  int V0Weight = L0.Weight;
2025  SDValue V1 = L1.Value;
2026  int V1Weight = L1.Weight;
2027 
2028  // Make sure that none of these nodes have been RAUW'd
2029  if ((RootWeights.count(V0.getNode()) && RootWeights[V0.getNode()] == -2) ||
2030  (RootWeights.count(V1.getNode()) && RootWeights[V1.getNode()] == -2)) {
2031  DEBUG(dbgs() << "--> Subtree was RAUWd. Restarting...\n");
2032  return balanceSubTree(N, TopLevel);
2033  }
2034 
2037  EVT VT = N->getValueType(0);
2038  SDValue NewNode;
2039 
2040  if (V0C && !V1C) {
2041  std::swap(V0, V1);
2042  std::swap(V0C, V1C);
2043  }
2044 
2045  // Calculate height of this node
2046  assert(NodeHeights.count(V0) && NodeHeights.count(V1) &&
2047  "Children must have been visited before re-combining them!");
2048  int Height = std::max(NodeHeights[V0], NodeHeights[V1]) + 1;
2049 
2050  // Rebuild this node (and restore SHL from MUL if needed)
2051  if (V1C && NOpcode == ISD::MUL && V1C->getAPIntValue().isPowerOf2())
2052  NewNode = CurDAG->getNode(
2053  ISD::SHL, SDLoc(V0), VT, V0,
2055  V1C->getAPIntValue().logBase2(), SDLoc(N),
2056  TLI.getScalarShiftAmountTy(DL, V0.getValueType())));
2057  else
2058  NewNode = CurDAG->getNode(NOpcode, SDLoc(N), VT, V0, V1);
2059 
2060  NodeHeights[NewNode] = Height;
2061 
2062  int Weight = V0Weight + V1Weight;
2063  Leaves.push(WeightedLeaf(NewNode, Weight, L0.InsertionOrder));
2064 
2065  DEBUG(dbgs() << "--> Built new node (Weight=" << Weight << ",Height="
2066  << Height << "):\n");
2067  DEBUG(NewNode.dump());
2068  }
2069 
2070  assert(Leaves.size() == 1);
2071  SDValue NewRoot = Leaves.top().Value;
2072 
2073  assert(NodeHeights.count(NewRoot));
2074  int Height = NodeHeights[NewRoot];
2075 
2076  // Restore SHL if we earlier converted it to a MUL
2077  if (NewRoot.getOpcode() == ISD::MUL) {
2078  ConstantSDNode *V1C = dyn_cast<ConstantSDNode>(NewRoot.getOperand(1));
2079  if (V1C && V1C->getAPIntValue().isPowerOf2()) {
2080  EVT VT = NewRoot.getValueType();
2081  SDValue V0 = NewRoot.getOperand(0);
2082  NewRoot = CurDAG->getNode(
2083  ISD::SHL, SDLoc(NewRoot), VT, V0,
2085  V1C->getAPIntValue().logBase2(), SDLoc(NewRoot),
2086  TLI.getScalarShiftAmountTy(DL, V0.getValueType())));
2087  }
2088  }
2089 
2090  if (N != NewRoot.getNode()) {
2091  DEBUG(dbgs() << "--> Root is now: ");
2092  DEBUG(NewRoot.dump());
2093 
2094  // Replace all uses of old root by new root
2095  CurDAG->ReplaceAllUsesWith(N, NewRoot.getNode());
2096  // Mark that we have RAUW'd N
2097  RootWeights[N] = -2;
2098  } else {
2099  DEBUG(dbgs() << "--> Root unchanged.\n");
2100  }
2101 
2102  RootWeights[NewRoot.getNode()] = Leaves.top().Weight;
2103  RootHeights[NewRoot.getNode()] = Height;
2104 
2105  return NewRoot;
2106 }
2107 
2108 void HexagonDAGToDAGISel::rebalanceAddressTrees() {
2109  for (auto I = CurDAG->allnodes_begin(), E = CurDAG->allnodes_end(); I != E;) {
2110  SDNode *N = &*I++;
2111  if (N->getOpcode() != ISD::LOAD && N->getOpcode() != ISD::STORE)
2112  continue;
2113 
2114  SDValue BasePtr = cast<MemSDNode>(N)->getBasePtr();
2115  if (BasePtr.getOpcode() != ISD::ADD)
2116  continue;
2117 
2118  // We've already processed this node
2119  if (RootWeights.count(BasePtr.getNode()))
2120  continue;
2121 
2122  DEBUG(dbgs() << "** Rebalancing address calculation in node: ");
2123  DEBUG(N->dump());
2124 
2125  // FindRoots
2126  SmallVector<SDNode *, 4> Worklist;
2127 
2128  Worklist.push_back(BasePtr.getOperand(0).getNode());
2129  Worklist.push_back(BasePtr.getOperand(1).getNode());
2130 
2131  while (!Worklist.empty()) {
2132  SDNode *N = Worklist.pop_back_val();
2133  unsigned Opcode = N->getOpcode();
2134 
2135  if (!isOpcodeHandled(N))
2136  continue;
2137 
2138  Worklist.push_back(N->getOperand(0).getNode());
2139  Worklist.push_back(N->getOperand(1).getNode());
2140 
2141  // Not a root if it has only one use and same opcode as its parent
2142  if (N->hasOneUse() && Opcode == N->use_begin()->getOpcode())
2143  continue;
2144 
2145  // This root node has already been processed
2146  if (RootWeights.count(N))
2147  continue;
2148 
2149  RootWeights[N] = -1;
2150  }
2151 
2152  // Balance node itself
2153  RootWeights[BasePtr.getNode()] = -1;
2154  SDValue NewBasePtr = balanceSubTree(BasePtr.getNode(), /*TopLevel=*/ true);
2155 
2156  if (N->getOpcode() == ISD::LOAD)
2157  N = CurDAG->UpdateNodeOperands(N, N->getOperand(0),
2158  NewBasePtr, N->getOperand(2));
2159  else
2160  N = CurDAG->UpdateNodeOperands(N, N->getOperand(0), N->getOperand(1),
2161  NewBasePtr, N->getOperand(3));
2162 
2163  DEBUG(dbgs() << "--> Final node: ");
2164  DEBUG(N->dump());
2165  }
2166 
2168  GAUsesInFunction.clear();
2169  RootHeights.clear();
2170  RootWeights.clear();
2171 }
2172 
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:545
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)
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:379
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:446
const DataLayout & getDataLayout() const
Definition: SelectionDAG.h:388
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:435
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:385
SDValue getTargetFrameIndex(int FI, EVT VT)
Definition: SelectionDAG.h:606
#define T
Simple integer binary arithmetic operators.
Definition: ISDOpcodes.h:200
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:558
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.
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: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.
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.
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:891
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:431
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: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
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.
void dump() const
constexpr size_t array_lengthof(T(&)[N])
Find the length of an array.
Definition: STLExtras.h:674
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: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...
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:423
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:389
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:401
ZERO_EXTEND - Used for integer types, zeroing the new bits.
Definition: ISDOpcodes.h:445
ANY_EXTEND - Used for integer types. The high bits are undefined.
Definition: ISDOpcodes.h:448
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)
allnodes_const_iterator allnodes_end() const
Definition: SelectionDAG.h:424
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:362
SDValue getCopyFromReg(SDValue Chain, const SDLoc &dl, unsigned Reg, EVT VT)
Definition: SelectionDAG.h:683
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:463
LOAD and STORE have token chains as their first operand, then the same operands as an LLVM load/store...
Definition: ISDOpcodes.h:581
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)
const Function * getFunction() const
getFunction - Return the LLVM function that this machine code represents
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:556
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.Val 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:442
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:600
MemIndexedMode
MemIndexedMode enum - This enum defines the load / store indexed addressing modes.
Definition: ISDOpcodes.h:871
This class is used to represent ISD::LOAD nodes.