LLVM  8.0.0svn
HexagonISelDAGToDAGHVX.cpp
Go to the documentation of this file.
1 //===-- HexagonISelDAGToDAGHVX.cpp ----------------------------------------===//
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 #include "Hexagon.h"
11 #include "HexagonISelDAGToDAG.h"
12 #include "HexagonISelLowering.h"
13 #include "HexagonTargetMachine.h"
14 #include "llvm/ADT/SetVector.h"
17 #include "llvm/IR/Intrinsics.h"
19 #include "llvm/Support/Debug.h"
20 
21 #include <deque>
22 #include <map>
23 #include <set>
24 #include <utility>
25 #include <vector>
26 
27 #define DEBUG_TYPE "hexagon-isel"
28 
29 using namespace llvm;
30 
31 namespace {
32 
33 // --------------------------------------------------------------------
34 // Implementation of permutation networks.
35 
36 // Implementation of the node routing through butterfly networks:
37 // - Forward delta.
38 // - Reverse delta.
39 // - Benes.
40 //
41 //
42 // Forward delta network consists of log(N) steps, where N is the number
43 // of inputs. In each step, an input can stay in place, or it can get
44 // routed to another position[1]. The step after that consists of two
45 // networks, each half in size in terms of the number of nodes. In those
46 // terms, in the given step, an input can go to either the upper or the
47 // lower network in the next step.
48 //
49 // [1] Hexagon's vdelta/vrdelta allow an element to be routed to both
50 // positions as long as there is no conflict.
51 
52 // Here's a delta network for 8 inputs, only the switching routes are
53 // shown:
54 //
55 // Steps:
56 // |- 1 ---------------|- 2 -----|- 3 -|
57 //
58 // Inp[0] *** *** *** *** Out[0]
59 // \ / \ / \ /
60 // \ / \ / X
61 // \ / \ / / \
62 // Inp[1] *** \ / *** X *** *** Out[1]
63 // \ \ / / \ / \ /
64 // \ \ / / X X
65 // \ \ / / / \ / \
66 // Inp[2] *** \ \ / / *** X *** *** Out[2]
67 // \ \ X / / / \ \ /
68 // \ \ / \ / / / \ X
69 // \ X X / / \ / \
70 // Inp[3] *** \ / \ / \ / *** *** *** Out[3]
71 // \ X X X /
72 // \ / \ / \ / \ /
73 // X X X X
74 // / \ / \ / \ / \
75 // / X X X \
76 // Inp[4] *** / \ / \ / \ *** *** *** Out[4]
77 // / X X \ \ / \ /
78 // / / \ / \ \ \ / X
79 // / / X \ \ \ / / \
80 // Inp[5] *** / / \ \ *** X *** *** Out[5]
81 // / / \ \ \ / \ /
82 // / / \ \ X X
83 // / / \ \ / \ / \
84 // Inp[6] *** / \ *** X *** *** Out[6]
85 // / \ / \ \ /
86 // / \ / \ X
87 // / \ / \ / \
88 // Inp[7] *** *** *** *** Out[7]
89 //
90 //
91 // Reverse delta network is same as delta network, with the steps in
92 // the opposite order.
93 //
94 //
95 // Benes network is a forward delta network immediately followed by
96 // a reverse delta network.
97 
98 enum class ColorKind { None, Red, Black };
99 
100 // Graph coloring utility used to partition nodes into two groups:
101 // they will correspond to nodes routed to the upper and lower networks.
102 struct Coloring {
103  using Node = int;
104  using MapType = std::map<Node, ColorKind>;
105  static constexpr Node Ignore = Node(-1);
106 
107  Coloring(ArrayRef<Node> Ord) : Order(Ord) {
108  build();
109  if (!color())
110  Colors.clear();
111  }
112 
113  const MapType &colors() const {
114  return Colors;
115  }
116 
117  ColorKind other(ColorKind Color) {
118  if (Color == ColorKind::None)
119  return ColorKind::Red;
120  return Color == ColorKind::Red ? ColorKind::Black : ColorKind::Red;
121  }
122 
123  LLVM_DUMP_METHOD void dump() const;
124 
125 private:
126  ArrayRef<Node> Order;
127  MapType Colors;
128  std::set<Node> Needed;
129 
130  using NodeSet = std::set<Node>;
131  std::map<Node,NodeSet> Edges;
132 
133  Node conj(Node Pos) {
134  Node Num = Order.size();
135  return (Pos < Num/2) ? Pos + Num/2 : Pos - Num/2;
136  }
137 
138  ColorKind getColor(Node N) {
139  auto F = Colors.find(N);
140  return F != Colors.end() ? F->second : ColorKind::None;
141  }
142 
143  std::pair<bool, ColorKind> getUniqueColor(const NodeSet &Nodes);
144 
145  void build();
146  bool color();
147 };
148 } // namespace
149 
150 std::pair<bool, ColorKind> Coloring::getUniqueColor(const NodeSet &Nodes) {
151  auto Color = ColorKind::None;
152  for (Node N : Nodes) {
153  ColorKind ColorN = getColor(N);
154  if (ColorN == ColorKind::None)
155  continue;
156  if (Color == ColorKind::None)
157  Color = ColorN;
158  else if (Color != ColorKind::None && Color != ColorN)
159  return { false, ColorKind::None };
160  }
161  return { true, Color };
162 }
163 
164 void Coloring::build() {
165  // Add Order[P] and Order[conj(P)] to Edges.
166  for (unsigned P = 0; P != Order.size(); ++P) {
167  Node I = Order[P];
168  if (I != Ignore) {
169  Needed.insert(I);
170  Node PC = Order[conj(P)];
171  if (PC != Ignore && PC != I)
172  Edges[I].insert(PC);
173  }
174  }
175  // Add I and conj(I) to Edges.
176  for (unsigned I = 0; I != Order.size(); ++I) {
177  if (!Needed.count(I))
178  continue;
179  Node C = conj(I);
180  // This will create an entry in the edge table, even if I is not
181  // connected to any other node. This is necessary, because it still
182  // needs to be colored.
183  NodeSet &Is = Edges[I];
184  if (Needed.count(C))
185  Is.insert(C);
186  }
187 }
188 
189 bool Coloring::color() {
190  SetVector<Node> FirstQ;
191  auto Enqueue = [this,&FirstQ] (Node N) {
192  SetVector<Node> Q;
193  Q.insert(N);
194  for (unsigned I = 0; I != Q.size(); ++I) {
195  NodeSet &Ns = Edges[Q[I]];
196  Q.insert(Ns.begin(), Ns.end());
197  }
198  FirstQ.insert(Q.begin(), Q.end());
199  };
200  for (Node N : Needed)
201  Enqueue(N);
202 
203  for (Node N : FirstQ) {
204  if (Colors.count(N))
205  continue;
206  NodeSet &Ns = Edges[N];
207  auto P = getUniqueColor(Ns);
208  if (!P.first)
209  return false;
210  Colors[N] = other(P.second);
211  }
212 
213  // First, color nodes that don't have any dups.
214  for (auto E : Edges) {
215  Node N = E.first;
216  if (!Needed.count(conj(N)) || Colors.count(N))
217  continue;
218  auto P = getUniqueColor(E.second);
219  if (!P.first)
220  return false;
221  Colors[N] = other(P.second);
222  }
223 
224  // Now, nodes that are still uncolored. Since the graph can be modified
225  // in this step, create a work queue.
226  std::vector<Node> WorkQ;
227  for (auto E : Edges) {
228  Node N = E.first;
229  if (!Colors.count(N))
230  WorkQ.push_back(N);
231  }
232 
233  for (unsigned I = 0; I < WorkQ.size(); ++I) {
234  Node N = WorkQ[I];
235  NodeSet &Ns = Edges[N];
236  auto P = getUniqueColor(Ns);
237  if (P.first) {
238  Colors[N] = other(P.second);
239  continue;
240  }
241 
242  // Coloring failed. Split this node.
243  Node C = conj(N);
244  ColorKind ColorN = other(ColorKind::None);
245  ColorKind ColorC = other(ColorN);
246  NodeSet &Cs = Edges[C];
247  NodeSet CopyNs = Ns;
248  for (Node M : CopyNs) {
249  ColorKind ColorM = getColor(M);
250  if (ColorM == ColorC) {
251  // Connect M with C, disconnect M from N.
252  Cs.insert(M);
253  Edges[M].insert(C);
254  Ns.erase(M);
255  Edges[M].erase(N);
256  }
257  }
258  Colors[N] = ColorN;
259  Colors[C] = ColorC;
260  }
261 
262  // Explicitly assign "None" to all uncolored nodes.
263  for (unsigned I = 0; I != Order.size(); ++I)
264  if (Colors.count(I) == 0)
265  Colors[I] = ColorKind::None;
266 
267  return true;
268 }
269 
270 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
271 void Coloring::dump() const {
272  dbgs() << "{ Order: {";
273  for (unsigned I = 0; I != Order.size(); ++I) {
274  Node P = Order[I];
275  if (P != Ignore)
276  dbgs() << ' ' << P;
277  else
278  dbgs() << " -";
279  }
280  dbgs() << " }\n";
281  dbgs() << " Needed: {";
282  for (Node N : Needed)
283  dbgs() << ' ' << N;
284  dbgs() << " }\n";
285 
286  dbgs() << " Edges: {\n";
287  for (auto E : Edges) {
288  dbgs() << " " << E.first << " -> {";
289  for (auto N : E.second)
290  dbgs() << ' ' << N;
291  dbgs() << " }\n";
292  }
293  dbgs() << " }\n";
294 
295  auto ColorKindToName = [](ColorKind C) {
296  switch (C) {
297  case ColorKind::None:
298  return "None";
299  case ColorKind::Red:
300  return "Red";
301  case ColorKind::Black:
302  return "Black";
303  }
304  llvm_unreachable("all ColorKinds should be handled by the switch above");
305  };
306 
307  dbgs() << " Colors: {\n";
308  for (auto C : Colors)
309  dbgs() << " " << C.first << " -> " << ColorKindToName(C.second) << "\n";
310  dbgs() << " }\n}\n";
311 }
312 #endif
313 
314 namespace {
315 // Base class of for reordering networks. They don't strictly need to be
316 // permutations, as outputs with repeated occurrences of an input element
317 // are allowed.
318 struct PermNetwork {
319  using Controls = std::vector<uint8_t>;
320  using ElemType = int;
321  static constexpr ElemType Ignore = ElemType(-1);
322 
323  enum : uint8_t {
324  None,
325  Pass,
326  Switch
327  };
328  enum : uint8_t {
329  Forward,
330  Reverse
331  };
332 
333  PermNetwork(ArrayRef<ElemType> Ord, unsigned Mult = 1) {
334  Order.assign(Ord.data(), Ord.data()+Ord.size());
335  Log = 0;
336 
337  unsigned S = Order.size();
338  while (S >>= 1)
339  ++Log;
340 
341  Table.resize(Order.size());
342  for (RowType &Row : Table)
343  Row.resize(Mult*Log, None);
344  }
345 
346  void getControls(Controls &V, unsigned StartAt, uint8_t Dir) const {
347  unsigned Size = Order.size();
348  V.resize(Size);
349  for (unsigned I = 0; I != Size; ++I) {
350  unsigned W = 0;
351  for (unsigned L = 0; L != Log; ++L) {
352  unsigned C = ctl(I, StartAt+L) == Switch;
353  if (Dir == Forward)
354  W |= C << (Log-1-L);
355  else
356  W |= C << L;
357  }
358  assert(isUInt<8>(W));
359  V[I] = uint8_t(W);
360  }
361  }
362 
363  uint8_t ctl(ElemType Pos, unsigned Step) const {
364  return Table[Pos][Step];
365  }
366  unsigned size() const {
367  return Order.size();
368  }
369  unsigned steps() const {
370  return Log;
371  }
372 
373 protected:
374  unsigned Log;
375  std::vector<ElemType> Order;
376  using RowType = std::vector<uint8_t>;
377  std::vector<RowType> Table;
378 };
379 
380 struct ForwardDeltaNetwork : public PermNetwork {
381  ForwardDeltaNetwork(ArrayRef<ElemType> Ord) : PermNetwork(Ord) {}
382 
383  bool run(Controls &V) {
384  if (!route(Order.data(), Table.data(), size(), 0))
385  return false;
386  getControls(V, 0, Forward);
387  return true;
388  }
389 
390 private:
391  bool route(ElemType *P, RowType *T, unsigned Size, unsigned Step);
392 };
393 
394 struct ReverseDeltaNetwork : public PermNetwork {
395  ReverseDeltaNetwork(ArrayRef<ElemType> Ord) : PermNetwork(Ord) {}
396 
397  bool run(Controls &V) {
398  if (!route(Order.data(), Table.data(), size(), 0))
399  return false;
400  getControls(V, 0, Reverse);
401  return true;
402  }
403 
404 private:
405  bool route(ElemType *P, RowType *T, unsigned Size, unsigned Step);
406 };
407 
408 struct BenesNetwork : public PermNetwork {
409  BenesNetwork(ArrayRef<ElemType> Ord) : PermNetwork(Ord, 2) {}
410 
411  bool run(Controls &F, Controls &R) {
412  if (!route(Order.data(), Table.data(), size(), 0))
413  return false;
414 
415  getControls(F, 0, Forward);
416  getControls(R, Log, Reverse);
417  return true;
418  }
419 
420 private:
421  bool route(ElemType *P, RowType *T, unsigned Size, unsigned Step);
422 };
423 } // namespace
424 
425 bool ForwardDeltaNetwork::route(ElemType *P, RowType *T, unsigned Size,
426  unsigned Step) {
427  bool UseUp = false, UseDown = false;
428  ElemType Num = Size;
429 
430  // Cannot use coloring here, because coloring is used to determine
431  // the "big" switch, i.e. the one that changes halves, and in a forward
432  // network, a color can be simultaneously routed to both halves in the
433  // step we're working on.
434  for (ElemType J = 0; J != Num; ++J) {
435  ElemType I = P[J];
436  // I is the position in the input,
437  // J is the position in the output.
438  if (I == Ignore)
439  continue;
440  uint8_t S;
441  if (I < Num/2)
442  S = (J < Num/2) ? Pass : Switch;
443  else
444  S = (J < Num/2) ? Switch : Pass;
445 
446  // U is the element in the table that needs to be updated.
447  ElemType U = (S == Pass) ? I : (I < Num/2 ? I+Num/2 : I-Num/2);
448  if (U < Num/2)
449  UseUp = true;
450  else
451  UseDown = true;
452  if (T[U][Step] != S && T[U][Step] != None)
453  return false;
454  T[U][Step] = S;
455  }
456 
457  for (ElemType J = 0; J != Num; ++J)
458  if (P[J] != Ignore && P[J] >= Num/2)
459  P[J] -= Num/2;
460 
461  if (Step+1 < Log) {
462  if (UseUp && !route(P, T, Size/2, Step+1))
463  return false;
464  if (UseDown && !route(P+Size/2, T+Size/2, Size/2, Step+1))
465  return false;
466  }
467  return true;
468 }
469 
470 bool ReverseDeltaNetwork::route(ElemType *P, RowType *T, unsigned Size,
471  unsigned Step) {
472  unsigned Pets = Log-1 - Step;
473  bool UseUp = false, UseDown = false;
474  ElemType Num = Size;
475 
476  // In this step half-switching occurs, so coloring can be used.
477  Coloring G({P,Size});
478  const Coloring::MapType &M = G.colors();
479  if (M.empty())
480  return false;
481 
482  ColorKind ColorUp = ColorKind::None;
483  for (ElemType J = 0; J != Num; ++J) {
484  ElemType I = P[J];
485  // I is the position in the input,
486  // J is the position in the output.
487  if (I == Ignore)
488  continue;
489  ColorKind C = M.at(I);
490  if (C == ColorKind::None)
491  continue;
492  // During "Step", inputs cannot switch halves, so if the "up" color
493  // is still unknown, make sure that it is selected in such a way that
494  // "I" will stay in the same half.
495  bool InpUp = I < Num/2;
496  if (ColorUp == ColorKind::None)
497  ColorUp = InpUp ? C : G.other(C);
498  if ((C == ColorUp) != InpUp) {
499  // If I should go to a different half than where is it now, give up.
500  return false;
501  }
502 
503  uint8_t S;
504  if (InpUp) {
505  S = (J < Num/2) ? Pass : Switch;
506  UseUp = true;
507  } else {
508  S = (J < Num/2) ? Switch : Pass;
509  UseDown = true;
510  }
511  T[J][Pets] = S;
512  }
513 
514  // Reorder the working permutation according to the computed switch table
515  // for the last step (i.e. Pets).
516  for (ElemType J = 0, E = Size / 2; J != E; ++J) {
517  ElemType PJ = P[J]; // Current values of P[J]
518  ElemType PC = P[J+Size/2]; // and P[conj(J)]
519  ElemType QJ = PJ; // New values of P[J]
520  ElemType QC = PC; // and P[conj(J)]
521  if (T[J][Pets] == Switch)
522  QC = PJ;
523  if (T[J+Size/2][Pets] == Switch)
524  QJ = PC;
525  P[J] = QJ;
526  P[J+Size/2] = QC;
527  }
528 
529  for (ElemType J = 0; J != Num; ++J)
530  if (P[J] != Ignore && P[J] >= Num/2)
531  P[J] -= Num/2;
532 
533  if (Step+1 < Log) {
534  if (UseUp && !route(P, T, Size/2, Step+1))
535  return false;
536  if (UseDown && !route(P+Size/2, T+Size/2, Size/2, Step+1))
537  return false;
538  }
539  return true;
540 }
541 
542 bool BenesNetwork::route(ElemType *P, RowType *T, unsigned Size,
543  unsigned Step) {
544  Coloring G({P,Size});
545  const Coloring::MapType &M = G.colors();
546  if (M.empty())
547  return false;
548  ElemType Num = Size;
549 
550  unsigned Pets = 2*Log-1 - Step;
551  bool UseUp = false, UseDown = false;
552 
553  // Both assignments, i.e. Red->Up and Red->Down are valid, but they will
554  // result in different controls. Let's pick the one where the first
555  // control will be "Pass".
556  ColorKind ColorUp = ColorKind::None;
557  for (ElemType J = 0; J != Num; ++J) {
558  ElemType I = P[J];
559  if (I == Ignore)
560  continue;
561  ColorKind C = M.at(I);
562  if (C == ColorKind::None)
563  continue;
564  if (ColorUp == ColorKind::None) {
565  ColorUp = (I < Num / 2) ? ColorKind::Red : ColorKind::Black;
566  }
567  unsigned CI = (I < Num/2) ? I+Num/2 : I-Num/2;
568  if (C == ColorUp) {
569  if (I < Num/2)
570  T[I][Step] = Pass;
571  else
572  T[CI][Step] = Switch;
573  T[J][Pets] = (J < Num/2) ? Pass : Switch;
574  UseUp = true;
575  } else { // Down
576  if (I < Num/2)
577  T[CI][Step] = Switch;
578  else
579  T[I][Step] = Pass;
580  T[J][Pets] = (J < Num/2) ? Switch : Pass;
581  UseDown = true;
582  }
583  }
584 
585  // Reorder the working permutation according to the computed switch table
586  // for the last step (i.e. Pets).
587  for (ElemType J = 0; J != Num/2; ++J) {
588  ElemType PJ = P[J]; // Current values of P[J]
589  ElemType PC = P[J+Num/2]; // and P[conj(J)]
590  ElemType QJ = PJ; // New values of P[J]
591  ElemType QC = PC; // and P[conj(J)]
592  if (T[J][Pets] == Switch)
593  QC = PJ;
594  if (T[J+Num/2][Pets] == Switch)
595  QJ = PC;
596  P[J] = QJ;
597  P[J+Num/2] = QC;
598  }
599 
600  for (ElemType J = 0; J != Num; ++J)
601  if (P[J] != Ignore && P[J] >= Num/2)
602  P[J] -= Num/2;
603 
604  if (Step+1 < Log) {
605  if (UseUp && !route(P, T, Size/2, Step+1))
606  return false;
607  if (UseDown && !route(P+Size/2, T+Size/2, Size/2, Step+1))
608  return false;
609  }
610  return true;
611 }
612 
613 // --------------------------------------------------------------------
614 // Support for building selection results (output instructions that are
615 // parts of the final selection).
616 
617 namespace {
618 struct OpRef {
619  OpRef(SDValue V) : OpV(V) {}
620  bool isValue() const { return OpV.getNode() != nullptr; }
621  bool isValid() const { return isValue() || !(OpN & Invalid); }
622  static OpRef res(int N) { return OpRef(Whole | (N & Index)); }
623  static OpRef fail() { return OpRef(Invalid); }
624 
625  static OpRef lo(const OpRef &R) {
626  assert(!R.isValue());
627  return OpRef(R.OpN & (Undef | Index | LoHalf));
628  }
629  static OpRef hi(const OpRef &R) {
630  assert(!R.isValue());
631  return OpRef(R.OpN & (Undef | Index | HiHalf));
632  }
633  static OpRef undef(MVT Ty) { return OpRef(Undef | Ty.SimpleTy); }
634 
635  // Direct value.
636  SDValue OpV = SDValue();
637 
638  // Reference to the operand of the input node:
639  // If the 31st bit is 1, it's undef, otherwise, bits 28..0 are the
640  // operand index:
641  // If bit 30 is set, it's the high half of the operand.
642  // If bit 29 is set, it's the low half of the operand.
643  unsigned OpN = 0;
644 
645  enum : unsigned {
646  Invalid = 0x10000000,
647  LoHalf = 0x20000000,
648  HiHalf = 0x40000000,
649  Whole = LoHalf | HiHalf,
650  Undef = 0x80000000,
651  Index = 0x0FFFFFFF, // Mask of the index value.
652  IndexBits = 28,
653  };
654 
656  void print(raw_ostream &OS, const SelectionDAG &G) const;
657 
658 private:
659  OpRef(unsigned N) : OpN(N) {}
660 };
661 
662 struct NodeTemplate {
663  NodeTemplate() = default;
664  unsigned Opc = 0;
665  MVT Ty = MVT::Other;
666  std::vector<OpRef> Ops;
667 
668  LLVM_DUMP_METHOD void print(raw_ostream &OS, const SelectionDAG &G) const;
669 };
670 
671 struct ResultStack {
672  ResultStack(SDNode *Inp)
673  : InpNode(Inp), InpTy(Inp->getValueType(0).getSimpleVT()) {}
674  SDNode *InpNode;
675  MVT InpTy;
676  unsigned push(const NodeTemplate &Res) {
677  List.push_back(Res);
678  return List.size()-1;
679  }
680  unsigned push(unsigned Opc, MVT Ty, std::vector<OpRef> &&Ops) {
681  NodeTemplate Res;
682  Res.Opc = Opc;
683  Res.Ty = Ty;
684  Res.Ops = Ops;
685  return push(Res);
686  }
687  bool empty() const { return List.empty(); }
688  unsigned size() const { return List.size(); }
689  unsigned top() const { return size()-1; }
690  const NodeTemplate &operator[](unsigned I) const { return List[I]; }
691  unsigned reset(unsigned NewTop) {
692  List.resize(NewTop+1);
693  return NewTop;
694  }
695 
696  using BaseType = std::vector<NodeTemplate>;
697  BaseType::iterator begin() { return List.begin(); }
698  BaseType::iterator end() { return List.end(); }
699  BaseType::const_iterator begin() const { return List.begin(); }
700  BaseType::const_iterator end() const { return List.end(); }
701 
702  BaseType List;
703 
705  void print(raw_ostream &OS, const SelectionDAG &G) const;
706 };
707 } // namespace
708 
709 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
710 void OpRef::print(raw_ostream &OS, const SelectionDAG &G) const {
711  if (isValue()) {
712  OpV.getNode()->print(OS, &G);
713  return;
714  }
715  if (OpN & Invalid) {
716  OS << "invalid";
717  return;
718  }
719  if (OpN & Undef) {
720  OS << "undef";
721  return;
722  }
723  if ((OpN & Whole) != Whole) {
724  assert((OpN & Whole) == LoHalf || (OpN & Whole) == HiHalf);
725  if (OpN & LoHalf)
726  OS << "lo ";
727  else
728  OS << "hi ";
729  }
730  OS << '#' << SignExtend32(OpN & Index, IndexBits);
731 }
732 
733 void NodeTemplate::print(raw_ostream &OS, const SelectionDAG &G) const {
735  OS << format("%8s", EVT(Ty).getEVTString().c_str()) << " "
736  << TII.getName(Opc);
737  bool Comma = false;
738  for (const auto &R : Ops) {
739  if (Comma)
740  OS << ',';
741  Comma = true;
742  OS << ' ';
743  R.print(OS, G);
744  }
745 }
746 
747 void ResultStack::print(raw_ostream &OS, const SelectionDAG &G) const {
748  OS << "Input node:\n";
749 #ifndef NDEBUG
750  InpNode->dumpr(&G);
751 #endif
752  OS << "Result templates:\n";
753  for (unsigned I = 0, E = List.size(); I != E; ++I) {
754  OS << '[' << I << "] ";
755  List[I].print(OS, G);
756  OS << '\n';
757  }
758 }
759 #endif
760 
761 namespace {
762 struct ShuffleMask {
763  ShuffleMask(ArrayRef<int> M) : Mask(M) {
764  for (unsigned I = 0, E = Mask.size(); I != E; ++I) {
765  int M = Mask[I];
766  if (M == -1)
767  continue;
768  MinSrc = (MinSrc == -1) ? M : std::min(MinSrc, M);
769  MaxSrc = (MaxSrc == -1) ? M : std::max(MaxSrc, M);
770  }
771  }
772 
774  int MinSrc = -1, MaxSrc = -1;
775 
776  ShuffleMask lo() const {
777  size_t H = Mask.size()/2;
778  return ShuffleMask(Mask.take_front(H));
779  }
780  ShuffleMask hi() const {
781  size_t H = Mask.size()/2;
782  return ShuffleMask(Mask.take_back(H));
783  }
784 
785  void print(raw_ostream &OS) const {
786  OS << "MinSrc:" << MinSrc << ", MaxSrc:" << MaxSrc << " {";
787  for (int M : Mask)
788  OS << ' ' << M;
789  OS << " }";
790  }
791 };
792 } // namespace
793 
794 // --------------------------------------------------------------------
795 // The HvxSelector class.
796 
798  return static_cast<const HexagonTargetLowering&>(G.getTargetLoweringInfo());
799 }
801  return static_cast<const HexagonSubtarget&>(G.getSubtarget());
802 }
803 
804 namespace llvm {
805  struct HvxSelector {
810  const unsigned HwLen;
811 
813  : Lower(getHexagonLowering(G)), ISel(HS), DAG(G),
814  HST(getHexagonSubtarget(G)), HwLen(HST.getVectorLength()) {}
815 
816  MVT getSingleVT(MVT ElemTy) const {
817  unsigned NumElems = HwLen / (ElemTy.getSizeInBits()/8);
818  return MVT::getVectorVT(ElemTy, NumElems);
819  }
820 
821  MVT getPairVT(MVT ElemTy) const {
822  unsigned NumElems = (2*HwLen) / (ElemTy.getSizeInBits()/8);
823  return MVT::getVectorVT(ElemTy, NumElems);
824  }
825 
826  void selectShuffle(SDNode *N);
827  void selectRor(SDNode *N);
828  void selectVAlign(SDNode *N);
829 
830  private:
831  void materialize(const ResultStack &Results);
832 
833  SDValue getVectorConstant(ArrayRef<uint8_t> Data, const SDLoc &dl);
834 
835  enum : unsigned {
836  None,
837  PackMux,
838  };
839  OpRef concat(OpRef Va, OpRef Vb, ResultStack &Results);
840  OpRef packs(ShuffleMask SM, OpRef Va, OpRef Vb, ResultStack &Results,
841  MutableArrayRef<int> NewMask, unsigned Options = None);
842  OpRef packp(ShuffleMask SM, OpRef Va, OpRef Vb, ResultStack &Results,
843  MutableArrayRef<int> NewMask);
844  OpRef vmuxs(ArrayRef<uint8_t> Bytes, OpRef Va, OpRef Vb,
845  ResultStack &Results);
846  OpRef vmuxp(ArrayRef<uint8_t> Bytes, OpRef Va, OpRef Vb,
847  ResultStack &Results);
848 
849  OpRef shuffs1(ShuffleMask SM, OpRef Va, ResultStack &Results);
850  OpRef shuffs2(ShuffleMask SM, OpRef Va, OpRef Vb, ResultStack &Results);
851  OpRef shuffp1(ShuffleMask SM, OpRef Va, ResultStack &Results);
852  OpRef shuffp2(ShuffleMask SM, OpRef Va, OpRef Vb, ResultStack &Results);
853 
854  OpRef butterfly(ShuffleMask SM, OpRef Va, ResultStack &Results);
855  OpRef contracting(ShuffleMask SM, OpRef Va, OpRef Vb, ResultStack &Results);
856  OpRef expanding(ShuffleMask SM, OpRef Va, ResultStack &Results);
857  OpRef perfect(ShuffleMask SM, OpRef Va, ResultStack &Results);
858 
859  bool selectVectorConstants(SDNode *N);
860  bool scalarizeShuffle(ArrayRef<int> Mask, const SDLoc &dl, MVT ResTy,
861  SDValue Va, SDValue Vb, SDNode *N);
862 
863  };
864 }
865 
867  MutableArrayRef<int> MaskR) {
868  unsigned VecLen = Mask.size();
869  assert(MaskL.size() == VecLen && MaskR.size() == VecLen);
870  for (unsigned I = 0; I != VecLen; ++I) {
871  int M = Mask[I];
872  if (M < 0) {
873  MaskL[I] = MaskR[I] = -1;
874  } else if (unsigned(M) < VecLen) {
875  MaskL[I] = M;
876  MaskR[I] = -1;
877  } else {
878  MaskL[I] = -1;
879  MaskR[I] = M-VecLen;
880  }
881  }
882 }
883 
884 static std::pair<int,unsigned> findStrip(ArrayRef<int> A, int Inc,
885  unsigned MaxLen) {
886  assert(A.size() > 0 && A.size() >= MaxLen);
887  int F = A[0];
888  int E = F;
889  for (unsigned I = 1; I != MaxLen; ++I) {
890  if (A[I] - E != Inc)
891  return { F, I };
892  E = A[I];
893  }
894  return { F, MaxLen };
895 }
896 
897 static bool isUndef(ArrayRef<int> Mask) {
898  for (int Idx : Mask)
899  if (Idx != -1)
900  return false;
901  return true;
902 }
903 
905  for (int I = 0, E = Mask.size(); I != E; ++I) {
906  int M = Mask[I];
907  if (M >= 0 && M != I)
908  return false;
909  }
910  return true;
911 }
912 
914  // Check by adding all numbers only works if there is no overflow.
915  assert(Mask.size() < 0x00007FFF && "Sanity failure");
916  int Sum = 0;
917  for (int Idx : Mask) {
918  if (Idx == -1)
919  return false;
920  Sum += Idx;
921  }
922  int N = Mask.size();
923  return 2*Sum == N*(N-1);
924 }
925 
926 bool HvxSelector::selectVectorConstants(SDNode *N) {
927  // Constant vectors are generated as loads from constant pools or as
928  // splats of a constant value. Since they are generated during the
929  // selection process, the main selection algorithm is not aware of them.
930  // Select them directly here.
932  SetVector<SDNode*> WorkQ;
933 
934  // The one-use test for VSPLATW's operand may fail due to dead nodes
935  // left over in the DAG.
937 
938  // The DAG can change (due to CSE) during selection, so cache all the
939  // unselected nodes first to avoid traversing a mutating DAG.
940 
941  auto IsNodeToSelect = [] (SDNode *N) {
942  if (N->isMachineOpcode())
943  return false;
944  switch (N->getOpcode()) {
945  case HexagonISD::VZERO:
946  case HexagonISD::VSPLATW:
947  return true;
948  case ISD::LOAD: {
949  SDValue Addr = cast<LoadSDNode>(N)->getBasePtr();
950  unsigned AddrOpc = Addr.getOpcode();
951  if (AddrOpc == HexagonISD::AT_PCREL || AddrOpc == HexagonISD::CP)
953  return true;
954  }
955  break;
956  }
957  // Make sure to select the operand of VSPLATW.
958  bool IsSplatOp = N->hasOneUse() &&
960  return IsSplatOp;
961  };
962 
963  WorkQ.insert(N);
964  for (unsigned i = 0; i != WorkQ.size(); ++i) {
965  SDNode *W = WorkQ[i];
966  if (IsNodeToSelect(W))
967  Nodes.push_back(W);
968  for (unsigned j = 0, f = W->getNumOperands(); j != f; ++j)
969  WorkQ.insert(W->getOperand(j).getNode());
970  }
971 
972  for (SDNode *L : Nodes)
973  ISel.Select(L);
974 
975  return !Nodes.empty();
976 }
977 
978 void HvxSelector::materialize(const ResultStack &Results) {
979  DEBUG_WITH_TYPE("isel", {
980  dbgs() << "Materializing\n";
981  Results.print(dbgs(), DAG);
982  });
983  if (Results.empty())
984  return;
985  const SDLoc &dl(Results.InpNode);
986  std::vector<SDValue> Output;
987 
988  for (unsigned I = 0, E = Results.size(); I != E; ++I) {
989  const NodeTemplate &Node = Results[I];
990  std::vector<SDValue> Ops;
991  for (const OpRef &R : Node.Ops) {
992  assert(R.isValid());
993  if (R.isValue()) {
994  Ops.push_back(R.OpV);
995  continue;
996  }
997  if (R.OpN & OpRef::Undef) {
999  Ops.push_back(ISel.selectUndef(dl, MVT(SVT)));
1000  continue;
1001  }
1002  // R is an index of a result.
1003  unsigned Part = R.OpN & OpRef::Whole;
1004  int Idx = SignExtend32(R.OpN & OpRef::Index, OpRef::IndexBits);
1005  if (Idx < 0)
1006  Idx += I;
1007  assert(Idx >= 0 && unsigned(Idx) < Output.size());
1008  SDValue Op = Output[Idx];
1009  MVT OpTy = Op.getValueType().getSimpleVT();
1010  if (Part != OpRef::Whole) {
1011  assert(Part == OpRef::LoHalf || Part == OpRef::HiHalf);
1012  MVT HalfTy = MVT::getVectorVT(OpTy.getVectorElementType(),
1013  OpTy.getVectorNumElements()/2);
1014  unsigned Sub = (Part == OpRef::LoHalf) ? Hexagon::vsub_lo
1015  : Hexagon::vsub_hi;
1016  Op = DAG.getTargetExtractSubreg(Sub, dl, HalfTy, Op);
1017  }
1018  Ops.push_back(Op);
1019  } // for (Node : Results)
1020 
1021  assert(Node.Ty != MVT::Other);
1022  SDNode *ResN = (Node.Opc == TargetOpcode::COPY)
1023  ? Ops.front().getNode()
1024  : DAG.getMachineNode(Node.Opc, dl, Node.Ty, Ops);
1025  Output.push_back(SDValue(ResN, 0));
1026  }
1027 
1028  SDNode *OutN = Output.back().getNode();
1029  SDNode *InpN = Results.InpNode;
1030  DEBUG_WITH_TYPE("isel", {
1031  dbgs() << "Generated node:\n";
1032  OutN->dumpr(&DAG);
1033  });
1034 
1035  ISel.ReplaceNode(InpN, OutN);
1036  selectVectorConstants(OutN);
1037  DAG.RemoveDeadNodes();
1038 }
1039 
1040 OpRef HvxSelector::concat(OpRef Lo, OpRef Hi, ResultStack &Results) {
1041  DEBUG_WITH_TYPE("isel", {dbgs() << __func__ << '\n';});
1042  const SDLoc &dl(Results.InpNode);
1043  Results.push(TargetOpcode::REG_SEQUENCE, getPairVT(MVT::i8), {
1044  DAG.getTargetConstant(Hexagon::HvxWRRegClassID, dl, MVT::i32),
1045  Lo, DAG.getTargetConstant(Hexagon::vsub_lo, dl, MVT::i32),
1046  Hi, DAG.getTargetConstant(Hexagon::vsub_hi, dl, MVT::i32),
1047  });
1048  return OpRef::res(Results.top());
1049 }
1050 
1051 // Va, Vb are single vectors, SM can be arbitrarily long.
1052 OpRef HvxSelector::packs(ShuffleMask SM, OpRef Va, OpRef Vb,
1053  ResultStack &Results, MutableArrayRef<int> NewMask,
1054  unsigned Options) {
1055  DEBUG_WITH_TYPE("isel", {dbgs() << __func__ << '\n';});
1056  if (!Va.isValid() || !Vb.isValid())
1057  return OpRef::fail();
1058 
1059  int VecLen = SM.Mask.size();
1060  MVT Ty = getSingleVT(MVT::i8);
1061 
1062  auto IsExtSubvector = [] (ShuffleMask M) {
1063  assert(M.MinSrc >= 0 && M.MaxSrc >= 0);
1064  for (int I = 0, E = M.Mask.size(); I != E; ++I) {
1065  if (M.Mask[I] >= 0 && M.Mask[I]-I != M.MinSrc)
1066  return false;
1067  }
1068  return true;
1069  };
1070 
1071  if (SM.MaxSrc - SM.MinSrc < int(HwLen)) {
1072  if (SM.MinSrc == 0 || SM.MinSrc == int(HwLen) || !IsExtSubvector(SM)) {
1073  // If the mask picks elements from only one of the operands, return
1074  // that operand, and update the mask to use index 0 to refer to the
1075  // first element of that operand.
1076  // If the mask extracts a subvector, it will be handled below, so
1077  // skip it here.
1078  if (SM.MaxSrc < int(HwLen)) {
1079  memcpy(NewMask.data(), SM.Mask.data(), sizeof(int)*VecLen);
1080  return Va;
1081  }
1082  if (SM.MinSrc >= int(HwLen)) {
1083  for (int I = 0; I != VecLen; ++I) {
1084  int M = SM.Mask[I];
1085  if (M != -1)
1086  M -= HwLen;
1087  NewMask[I] = M;
1088  }
1089  return Vb;
1090  }
1091  }
1092  int MinSrc = SM.MinSrc;
1093  if (SM.MaxSrc < int(HwLen)) {
1094  Vb = Va;
1095  } else if (SM.MinSrc > int(HwLen)) {
1096  Va = Vb;
1097  MinSrc = SM.MinSrc - HwLen;
1098  }
1099  const SDLoc &dl(Results.InpNode);
1100  if (isUInt<3>(MinSrc) || isUInt<3>(HwLen-MinSrc)) {
1101  bool IsRight = isUInt<3>(MinSrc); // Right align.
1102  SDValue S = DAG.getTargetConstant(IsRight ? MinSrc : HwLen-MinSrc,
1103  dl, MVT::i32);
1104  unsigned Opc = IsRight ? Hexagon::V6_valignbi
1105  : Hexagon::V6_vlalignbi;
1106  Results.push(Opc, Ty, {Vb, Va, S});
1107  } else {
1108  SDValue S = DAG.getTargetConstant(MinSrc, dl, MVT::i32);
1109  Results.push(Hexagon::A2_tfrsi, MVT::i32, {S});
1110  unsigned Top = Results.top();
1111  Results.push(Hexagon::V6_valignb, Ty, {Vb, Va, OpRef::res(Top)});
1112  }
1113  for (int I = 0; I != VecLen; ++I) {
1114  int M = SM.Mask[I];
1115  if (M != -1)
1116  M -= SM.MinSrc;
1117  NewMask[I] = M;
1118  }
1119  return OpRef::res(Results.top());
1120  }
1121 
1122  if (Options & PackMux) {
1123  // If elements picked from Va and Vb have all different (source) indexes
1124  // (relative to the start of the argument), do a mux, and update the mask.
1125  BitVector Picked(HwLen);
1126  SmallVector<uint8_t,128> MuxBytes(HwLen);
1127  bool CanMux = true;
1128  for (int I = 0; I != VecLen; ++I) {
1129  int M = SM.Mask[I];
1130  if (M == -1)
1131  continue;
1132  if (M >= int(HwLen))
1133  M -= HwLen;
1134  else
1135  MuxBytes[M] = 0xFF;
1136  if (Picked[M]) {
1137  CanMux = false;
1138  break;
1139  }
1140  NewMask[I] = M;
1141  }
1142  if (CanMux)
1143  return vmuxs(MuxBytes, Va, Vb, Results);
1144  }
1145 
1146  return OpRef::fail();
1147 }
1148 
1149 OpRef HvxSelector::packp(ShuffleMask SM, OpRef Va, OpRef Vb,
1150  ResultStack &Results, MutableArrayRef<int> NewMask) {
1151  DEBUG_WITH_TYPE("isel", {dbgs() << __func__ << '\n';});
1152  unsigned HalfMask = 0;
1153  unsigned LogHw = Log2_32(HwLen);
1154  for (int M : SM.Mask) {
1155  if (M == -1)
1156  continue;
1157  HalfMask |= (1u << (M >> LogHw));
1158  }
1159 
1160  if (HalfMask == 0)
1161  return OpRef::undef(getPairVT(MVT::i8));
1162 
1163  // If more than two halves are used, bail.
1164  // TODO: be more aggressive here?
1165  if (countPopulation(HalfMask) > 2)
1166  return OpRef::fail();
1167 
1168  MVT HalfTy = getSingleVT(MVT::i8);
1169 
1170  OpRef Inp[2] = { Va, Vb };
1171  OpRef Out[2] = { OpRef::undef(HalfTy), OpRef::undef(HalfTy) };
1172 
1173  uint8_t HalfIdx[4] = { 0xFF, 0xFF, 0xFF, 0xFF };
1174  unsigned Idx = 0;
1175  for (unsigned I = 0; I != 4; ++I) {
1176  if ((HalfMask & (1u << I)) == 0)
1177  continue;
1178  assert(Idx < 2);
1179  OpRef Op = Inp[I/2];
1180  Out[Idx] = (I & 1) ? OpRef::hi(Op) : OpRef::lo(Op);
1181  HalfIdx[I] = Idx++;
1182  }
1183 
1184  int VecLen = SM.Mask.size();
1185  for (int I = 0; I != VecLen; ++I) {
1186  int M = SM.Mask[I];
1187  if (M >= 0) {
1188  uint8_t Idx = HalfIdx[M >> LogHw];
1189  assert(Idx == 0 || Idx == 1);
1190  M = (M & (HwLen-1)) + HwLen*Idx;
1191  }
1192  NewMask[I] = M;
1193  }
1194 
1195  return concat(Out[0], Out[1], Results);
1196 }
1197 
1198 OpRef HvxSelector::vmuxs(ArrayRef<uint8_t> Bytes, OpRef Va, OpRef Vb,
1199  ResultStack &Results) {
1200  DEBUG_WITH_TYPE("isel", {dbgs() << __func__ << '\n';});
1201  MVT ByteTy = getSingleVT(MVT::i8);
1202  MVT BoolTy = MVT::getVectorVT(MVT::i1, 8*HwLen); // XXX
1203  const SDLoc &dl(Results.InpNode);
1204  SDValue B = getVectorConstant(Bytes, dl);
1205  Results.push(Hexagon::V6_vd0, ByteTy, {});
1206  Results.push(Hexagon::V6_veqb, BoolTy, {OpRef(B), OpRef::res(-1)});
1207  Results.push(Hexagon::V6_vmux, ByteTy, {OpRef::res(-1), Vb, Va});
1208  return OpRef::res(Results.top());
1209 }
1210 
1211 OpRef HvxSelector::vmuxp(ArrayRef<uint8_t> Bytes, OpRef Va, OpRef Vb,
1212  ResultStack &Results) {
1213  DEBUG_WITH_TYPE("isel", {dbgs() << __func__ << '\n';});
1214  size_t S = Bytes.size() / 2;
1215  OpRef L = vmuxs(Bytes.take_front(S), OpRef::lo(Va), OpRef::lo(Vb), Results);
1216  OpRef H = vmuxs(Bytes.drop_front(S), OpRef::hi(Va), OpRef::hi(Vb), Results);
1217  return concat(L, H, Results);
1218 }
1219 
1220 OpRef HvxSelector::shuffs1(ShuffleMask SM, OpRef Va, ResultStack &Results) {
1221  DEBUG_WITH_TYPE("isel", {dbgs() << __func__ << '\n';});
1222  unsigned VecLen = SM.Mask.size();
1223  assert(HwLen == VecLen);
1224  (void)VecLen;
1225  assert(all_of(SM.Mask, [this](int M) { return M == -1 || M < int(HwLen); }));
1226 
1227  if (isIdentity(SM.Mask))
1228  return Va;
1229  if (isUndef(SM.Mask))
1230  return OpRef::undef(getSingleVT(MVT::i8));
1231 
1232  OpRef P = perfect(SM, Va, Results);
1233  if (P.isValid())
1234  return P;
1235  return butterfly(SM, Va, Results);
1236 }
1237 
1238 OpRef HvxSelector::shuffs2(ShuffleMask SM, OpRef Va, OpRef Vb,
1239  ResultStack &Results) {
1240  DEBUG_WITH_TYPE("isel", {dbgs() << __func__ << '\n';});
1241  if (isUndef(SM.Mask))
1242  return OpRef::undef(getSingleVT(MVT::i8));
1243 
1244  OpRef C = contracting(SM, Va, Vb, Results);
1245  if (C.isValid())
1246  return C;
1247 
1248  int VecLen = SM.Mask.size();
1249  SmallVector<int,128> NewMask(VecLen);
1250  OpRef P = packs(SM, Va, Vb, Results, NewMask);
1251  if (P.isValid())
1252  return shuffs1(ShuffleMask(NewMask), P, Results);
1253 
1254  SmallVector<int,128> MaskL(VecLen), MaskR(VecLen);
1255  splitMask(SM.Mask, MaskL, MaskR);
1256 
1257  OpRef L = shuffs1(ShuffleMask(MaskL), Va, Results);
1258  OpRef R = shuffs1(ShuffleMask(MaskR), Vb, Results);
1259  if (!L.isValid() || !R.isValid())
1260  return OpRef::fail();
1261 
1262  SmallVector<uint8_t,128> Bytes(VecLen);
1263  for (int I = 0; I != VecLen; ++I) {
1264  if (MaskL[I] != -1)
1265  Bytes[I] = 0xFF;
1266  }
1267  return vmuxs(Bytes, L, R, Results);
1268 }
1269 
1270 OpRef HvxSelector::shuffp1(ShuffleMask SM, OpRef Va, ResultStack &Results) {
1271  DEBUG_WITH_TYPE("isel", {dbgs() << __func__ << '\n';});
1272  int VecLen = SM.Mask.size();
1273 
1274  if (isIdentity(SM.Mask))
1275  return Va;
1276  if (isUndef(SM.Mask))
1277  return OpRef::undef(getPairVT(MVT::i8));
1278 
1279  SmallVector<int,128> PackedMask(VecLen);
1280  OpRef P = packs(SM, OpRef::lo(Va), OpRef::hi(Va), Results, PackedMask);
1281  if (P.isValid()) {
1282  ShuffleMask PM(PackedMask);
1283  OpRef E = expanding(PM, P, Results);
1284  if (E.isValid())
1285  return E;
1286 
1287  OpRef L = shuffs1(PM.lo(), P, Results);
1288  OpRef H = shuffs1(PM.hi(), P, Results);
1289  if (L.isValid() && H.isValid())
1290  return concat(L, H, Results);
1291  }
1292 
1293  OpRef R = perfect(SM, Va, Results);
1294  if (R.isValid())
1295  return R;
1296  // TODO commute the mask and try the opposite order of the halves.
1297 
1298  OpRef L = shuffs2(SM.lo(), OpRef::lo(Va), OpRef::hi(Va), Results);
1299  OpRef H = shuffs2(SM.hi(), OpRef::lo(Va), OpRef::hi(Va), Results);
1300  if (L.isValid() && H.isValid())
1301  return concat(L, H, Results);
1302 
1303  return OpRef::fail();
1304 }
1305 
1306 OpRef HvxSelector::shuffp2(ShuffleMask SM, OpRef Va, OpRef Vb,
1307  ResultStack &Results) {
1308  DEBUG_WITH_TYPE("isel", {dbgs() << __func__ << '\n';});
1309  if (isUndef(SM.Mask))
1310  return OpRef::undef(getPairVT(MVT::i8));
1311 
1312  int VecLen = SM.Mask.size();
1313  SmallVector<int,256> PackedMask(VecLen);
1314  OpRef P = packp(SM, Va, Vb, Results, PackedMask);
1315  if (P.isValid())
1316  return shuffp1(ShuffleMask(PackedMask), P, Results);
1317 
1318  SmallVector<int,256> MaskL(VecLen), MaskR(VecLen);
1319  splitMask(SM.Mask, MaskL, MaskR);
1320 
1321  OpRef L = shuffp1(ShuffleMask(MaskL), Va, Results);
1322  OpRef R = shuffp1(ShuffleMask(MaskR), Vb, Results);
1323  if (!L.isValid() || !R.isValid())
1324  return OpRef::fail();
1325 
1326  // Mux the results.
1327  SmallVector<uint8_t,256> Bytes(VecLen);
1328  for (int I = 0; I != VecLen; ++I) {
1329  if (MaskL[I] != -1)
1330  Bytes[I] = 0xFF;
1331  }
1332  return vmuxp(Bytes, L, R, Results);
1333 }
1334 
1335 namespace {
1336  struct Deleter : public SelectionDAG::DAGNodeDeletedListener {
1337  template <typename T>
1338  Deleter(SelectionDAG &D, T &C)
1340  C.erase(N);
1341  }) {}
1342  };
1343 
1344  template <typename T>
1345  struct NullifyingVector : public T {
1347  NullifyingVector(T &&V) : T(V) {
1348  for (unsigned i = 0, e = T::size(); i != e; ++i) {
1349  SDNode *&N = T::operator[](i);
1350  Refs[N] = &N;
1351  }
1352  }
1353  void erase(SDNode *N) {
1354  auto F = Refs.find(N);
1355  if (F != Refs.end())
1356  *F->second = nullptr;
1357  }
1358  };
1359 }
1360 
1361 bool HvxSelector::scalarizeShuffle(ArrayRef<int> Mask, const SDLoc &dl,
1362  MVT ResTy, SDValue Va, SDValue Vb,
1363  SDNode *N) {
1364  DEBUG_WITH_TYPE("isel", {dbgs() << __func__ << '\n';});
1365  MVT ElemTy = ResTy.getVectorElementType();
1366  assert(ElemTy == MVT::i8);
1367  unsigned VecLen = Mask.size();
1368  bool HavePairs = (2*HwLen == VecLen);
1369  MVT SingleTy = getSingleVT(MVT::i8);
1370 
1371  // The prior attempts to handle this shuffle may have left a bunch of
1372  // dead nodes in the DAG (such as constants). These nodes will be added
1373  // at the end of DAG's node list, which at that point had already been
1374  // sorted topologically. In the main selection loop, the node list is
1375  // traversed backwards from the root node, which means that any new
1376  // nodes (from the end of the list) will not be visited.
1377  // Scalarization will replace the shuffle node with the scalarized
1378  // expression, and if that expression reused any if the leftoever (dead)
1379  // nodes, these nodes would not be selected (since the "local" selection
1380  // only visits nodes that are not in AllNodes).
1381  // To avoid this issue, remove all dead nodes from the DAG now.
1382  DAG.RemoveDeadNodes();
1383  DenseSet<SDNode*> AllNodes;
1384  for (SDNode &S : DAG.allnodes())
1385  AllNodes.insert(&S);
1386 
1387  Deleter DUA(DAG, AllNodes);
1388 
1390  LLVMContext &Ctx = *DAG.getContext();
1391  MVT LegalTy = Lower.getTypeToTransformTo(Ctx, ElemTy).getSimpleVT();
1392  for (int I : Mask) {
1393  if (I < 0) {
1394  Ops.push_back(ISel.selectUndef(dl, LegalTy));
1395  continue;
1396  }
1397  SDValue Vec;
1398  unsigned M = I;
1399  if (M < VecLen) {
1400  Vec = Va;
1401  } else {
1402  Vec = Vb;
1403  M -= VecLen;
1404  }
1405  if (HavePairs) {
1406  if (M < HwLen) {
1407  Vec = DAG.getTargetExtractSubreg(Hexagon::vsub_lo, dl, SingleTy, Vec);
1408  } else {
1409  Vec = DAG.getTargetExtractSubreg(Hexagon::vsub_hi, dl, SingleTy, Vec);
1410  M -= HwLen;
1411  }
1412  }
1413  SDValue Idx = DAG.getConstant(M, dl, MVT::i32);
1414  SDValue Ex = DAG.getNode(ISD::EXTRACT_VECTOR_ELT, dl, LegalTy, {Vec, Idx});
1415  SDValue L = Lower.LowerOperation(Ex, DAG);
1416  assert(L.getNode());
1417  Ops.push_back(L);
1418  }
1419 
1420  SDValue LV;
1421  if (2*HwLen == VecLen) {
1422  SDValue B0 = DAG.getBuildVector(SingleTy, dl, {Ops.data(), HwLen});
1423  SDValue L0 = Lower.LowerOperation(B0, DAG);
1424  SDValue B1 = DAG.getBuildVector(SingleTy, dl, {Ops.data()+HwLen, HwLen});
1425  SDValue L1 = Lower.LowerOperation(B1, DAG);
1426  // XXX CONCAT_VECTORS is legal for HVX vectors. Legalizing (lowering)
1427  // functions may expect to be called only for illegal operations, so
1428  // make sure that they are not called for legal ones. Develop a better
1429  // mechanism for dealing with this.
1430  LV = DAG.getNode(ISD::CONCAT_VECTORS, dl, ResTy, {L0, L1});
1431  } else {
1432  SDValue BV = DAG.getBuildVector(ResTy, dl, Ops);
1433  LV = Lower.LowerOperation(BV, DAG);
1434  }
1435 
1436  assert(!N->use_empty());
1437  ISel.ReplaceNode(N, LV.getNode());
1438 
1439  if (AllNodes.count(LV.getNode())) {
1440  DAG.RemoveDeadNodes();
1441  return true;
1442  }
1443 
1444  // The lowered build-vector node will now need to be selected. It needs
1445  // to be done here because this node and its submodes are not included
1446  // in the main selection loop.
1447  // Implement essentially the same topological ordering algorithm as is
1448  // used in SelectionDAGISel.
1449 
1450  SetVector<SDNode*> SubNodes, TmpQ;
1451  std::map<SDNode*,unsigned> NumOps;
1452 
1453  SubNodes.insert(LV.getNode());
1454  for (unsigned I = 0; I != SubNodes.size(); ++I) {
1455  unsigned OpN = 0;
1456  SDNode *S = SubNodes[I];
1457  for (SDValue Op : S->ops()) {
1458  if (AllNodes.count(Op.getNode()))
1459  continue;
1460  SubNodes.insert(Op.getNode());
1461  ++OpN;
1462  }
1463  NumOps.insert({S, OpN});
1464  if (OpN == 0)
1465  TmpQ.insert(S);
1466  }
1467 
1468  for (unsigned I = 0; I != TmpQ.size(); ++I) {
1469  SDNode *S = TmpQ[I];
1470  for (SDNode *U : S->uses()) {
1471  if (!SubNodes.count(U))
1472  continue;
1473  auto F = NumOps.find(U);
1474  assert(F != NumOps.end());
1475  assert(F->second > 0);
1476  if (!--F->second)
1477  TmpQ.insert(F->first);
1478  }
1479  }
1480  assert(SubNodes.size() == TmpQ.size());
1481  NullifyingVector<decltype(TmpQ)::vector_type> Queue(TmpQ.takeVector());
1482 
1483  Deleter DUQ(DAG, Queue);
1484  for (SDNode *S : reverse(Queue))
1485  if (S != nullptr)
1486  ISel.Select(S);
1487 
1488  DAG.RemoveDeadNodes();
1489  return true;
1490 }
1491 
1492 OpRef HvxSelector::contracting(ShuffleMask SM, OpRef Va, OpRef Vb,
1493  ResultStack &Results) {
1494  DEBUG_WITH_TYPE("isel", {dbgs() << __func__ << '\n';});
1495  if (!Va.isValid() || !Vb.isValid())
1496  return OpRef::fail();
1497 
1498  // Contracting shuffles, i.e. instructions that always discard some bytes
1499  // from the operand vectors.
1500  //
1501  // V6_vshuff{e,o}b
1502  // V6_vdealb4w
1503  // V6_vpack{e,o}{b,h}
1504 
1505  int VecLen = SM.Mask.size();
1506  std::pair<int,unsigned> Strip = findStrip(SM.Mask, 1, VecLen);
1507  MVT ResTy = getSingleVT(MVT::i8);
1508 
1509  // The following shuffles only work for bytes and halfwords. This requires
1510  // the strip length to be 1 or 2.
1511  if (Strip.second != 1 && Strip.second != 2)
1512  return OpRef::fail();
1513 
1514  // The patterns for the shuffles, in terms of the starting offsets of the
1515  // consecutive strips (L = length of the strip, N = VecLen):
1516  //
1517  // vpacke: 0, 2L, 4L ... N+0, N+2L, N+4L ... L = 1 or 2
1518  // vpacko: L, 3L, 5L ... N+L, N+3L, N+5L ... L = 1 or 2
1519  //
1520  // vshuffe: 0, N+0, 2L, N+2L, 4L ... L = 1 or 2
1521  // vshuffo: L, N+L, 3L, N+3L, 5L ... L = 1 or 2
1522  //
1523  // vdealb4w: 0, 4, 8 ... 2, 6, 10 ... N+0, N+4, N+8 ... N+2, N+6, N+10 ...
1524 
1525  // The value of the element in the mask following the strip will decide
1526  // what kind of a shuffle this can be.
1527  int NextInMask = SM.Mask[Strip.second];
1528 
1529  // Check if NextInMask could be 2L, 3L or 4, i.e. if it could be a mask
1530  // for vpack or vdealb4w. VecLen > 4, so NextInMask for vdealb4w would
1531  // satisfy this.
1532  if (NextInMask < VecLen) {
1533  // vpack{e,o} or vdealb4w
1534  if (Strip.first == 0 && Strip.second == 1 && NextInMask == 4) {
1535  int N = VecLen;
1536  // Check if this is vdealb4w (L=1).
1537  for (int I = 0; I != N/4; ++I)
1538  if (SM.Mask[I] != 4*I)
1539  return OpRef::fail();
1540  for (int I = 0; I != N/4; ++I)
1541  if (SM.Mask[I+N/4] != 2 + 4*I)
1542  return OpRef::fail();
1543  for (int I = 0; I != N/4; ++I)
1544  if (SM.Mask[I+N/2] != N + 4*I)
1545  return OpRef::fail();
1546  for (int I = 0; I != N/4; ++I)
1547  if (SM.Mask[I+3*N/4] != N+2 + 4*I)
1548  return OpRef::fail();
1549  // Matched mask for vdealb4w.
1550  Results.push(Hexagon::V6_vdealb4w, ResTy, {Vb, Va});
1551  return OpRef::res(Results.top());
1552  }
1553 
1554  // Check if this is vpack{e,o}.
1555  int N = VecLen;
1556  int L = Strip.second;
1557  // Check if the first strip starts at 0 or at L.
1558  if (Strip.first != 0 && Strip.first != L)
1559  return OpRef::fail();
1560  // Examine the rest of the mask.
1561  for (int I = L; I < N; I += L) {
1562  auto S = findStrip(SM.Mask.drop_front(I), 1, N-I);
1563  // Check whether the mask element at the beginning of each strip
1564  // increases by 2L each time.
1565  if (S.first - Strip.first != 2*I)
1566  return OpRef::fail();
1567  // Check whether each strip is of the same length.
1568  if (S.second != unsigned(L))
1569  return OpRef::fail();
1570  }
1571 
1572  // Strip.first == 0 => vpacke
1573  // Strip.first == L => vpacko
1574  assert(Strip.first == 0 || Strip.first == L);
1575  using namespace Hexagon;
1576  NodeTemplate Res;
1577  Res.Opc = Strip.second == 1 // Number of bytes.
1578  ? (Strip.first == 0 ? V6_vpackeb : V6_vpackob)
1579  : (Strip.first == 0 ? V6_vpackeh : V6_vpackoh);
1580  Res.Ty = ResTy;
1581  Res.Ops = { Vb, Va };
1582  Results.push(Res);
1583  return OpRef::res(Results.top());
1584  }
1585 
1586  // Check if this is vshuff{e,o}.
1587  int N = VecLen;
1588  int L = Strip.second;
1589  std::pair<int,unsigned> PrevS = Strip;
1590  bool Flip = false;
1591  for (int I = L; I < N; I += L) {
1592  auto S = findStrip(SM.Mask.drop_front(I), 1, N-I);
1593  if (S.second != PrevS.second)
1594  return OpRef::fail();
1595  int Diff = Flip ? PrevS.first - S.first + 2*L
1596  : S.first - PrevS.first;
1597  if (Diff != N)
1598  return OpRef::fail();
1599  Flip ^= true;
1600  PrevS = S;
1601  }
1602  // Strip.first == 0 => vshuffe
1603  // Strip.first == L => vshuffo
1604  assert(Strip.first == 0 || Strip.first == L);
1605  using namespace Hexagon;
1606  NodeTemplate Res;
1607  Res.Opc = Strip.second == 1 // Number of bytes.
1608  ? (Strip.first == 0 ? V6_vshuffeb : V6_vshuffob)
1609  : (Strip.first == 0 ? V6_vshufeh : V6_vshufoh);
1610  Res.Ty = ResTy;
1611  Res.Ops = { Vb, Va };
1612  Results.push(Res);
1613  return OpRef::res(Results.top());
1614 }
1615 
1616 OpRef HvxSelector::expanding(ShuffleMask SM, OpRef Va, ResultStack &Results) {
1617  DEBUG_WITH_TYPE("isel", {dbgs() << __func__ << '\n';});
1618  // Expanding shuffles (using all elements and inserting into larger vector):
1619  //
1620  // V6_vunpacku{b,h} [*]
1621  //
1622  // [*] Only if the upper elements (filled with 0s) are "don't care" in Mask.
1623  //
1624  // Note: V6_vunpacko{b,h} are or-ing the high byte/half in the result, so
1625  // they are not shuffles.
1626  //
1627  // The argument is a single vector.
1628 
1629  int VecLen = SM.Mask.size();
1630  assert(2*HwLen == unsigned(VecLen) && "Expecting vector-pair type");
1631 
1632  std::pair<int,unsigned> Strip = findStrip(SM.Mask, 1, VecLen);
1633 
1634  // The patterns for the unpacks, in terms of the starting offsets of the
1635  // consecutive strips (L = length of the strip, N = VecLen):
1636  //
1637  // vunpacku: 0, -1, L, -1, 2L, -1 ...
1638 
1639  if (Strip.first != 0)
1640  return OpRef::fail();
1641 
1642  // The vunpackus only handle byte and half-word.
1643  if (Strip.second != 1 && Strip.second != 2)
1644  return OpRef::fail();
1645 
1646  int N = VecLen;
1647  int L = Strip.second;
1648 
1649  // First, check the non-ignored strips.
1650  for (int I = 2*L; I < 2*N; I += 2*L) {
1651  auto S = findStrip(SM.Mask.drop_front(I), 1, N-I);
1652  if (S.second != unsigned(L))
1653  return OpRef::fail();
1654  if (2*S.first != I)
1655  return OpRef::fail();
1656  }
1657  // Check the -1s.
1658  for (int I = L; I < 2*N; I += 2*L) {
1659  auto S = findStrip(SM.Mask.drop_front(I), 0, N-I);
1660  if (S.first != -1 || S.second != unsigned(L))
1661  return OpRef::fail();
1662  }
1663 
1664  unsigned Opc = Strip.second == 1 ? Hexagon::V6_vunpackub
1665  : Hexagon::V6_vunpackuh;
1666  Results.push(Opc, getPairVT(MVT::i8), {Va});
1667  return OpRef::res(Results.top());
1668 }
1669 
1670 OpRef HvxSelector::perfect(ShuffleMask SM, OpRef Va, ResultStack &Results) {
1671  DEBUG_WITH_TYPE("isel", {dbgs() << __func__ << '\n';});
1672  // V6_vdeal{b,h}
1673  // V6_vshuff{b,h}
1674 
1675  // V6_vshufoe{b,h} those are quivalent to vshuffvdd(..,{1,2})
1676  // V6_vshuffvdd (V6_vshuff)
1677  // V6_dealvdd (V6_vdeal)
1678 
1679  int VecLen = SM.Mask.size();
1680  assert(isPowerOf2_32(VecLen) && Log2_32(VecLen) <= 8);
1681  unsigned LogLen = Log2_32(VecLen);
1682  unsigned HwLog = Log2_32(HwLen);
1683  // The result length must be the same as the length of a single vector,
1684  // or a vector pair.
1685  assert(LogLen == HwLog || LogLen == HwLog+1);
1686  bool Extend = (LogLen == HwLog);
1687 
1688  if (!isPermutation(SM.Mask))
1689  return OpRef::fail();
1690 
1691  SmallVector<unsigned,8> Perm(LogLen);
1692 
1693  // Check if this could be a perfect shuffle, or a combination of perfect
1694  // shuffles.
1695  //
1696  // Consider this permutation (using hex digits to make the ASCII diagrams
1697  // easier to read):
1698  // { 0, 8, 1, 9, 2, A, 3, B, 4, C, 5, D, 6, E, 7, F }.
1699  // This is a "deal" operation: divide the input into two halves, and
1700  // create the output by picking elements by alternating between these two
1701  // halves:
1702  // 0 1 2 3 4 5 6 7 --> 0 8 1 9 2 A 3 B 4 C 5 D 6 E 7 F [*]
1703  // 8 9 A B C D E F
1704  //
1705  // Aside from a few special explicit cases (V6_vdealb, etc.), HVX provides
1706  // a somwehat different mechanism that could be used to perform shuffle/
1707  // deal operations: a 2x2 transpose.
1708  // Consider the halves of inputs again, they can be interpreted as a 2x8
1709  // matrix. A 2x8 matrix can be looked at four 2x2 matrices concatenated
1710  // together. Now, when considering 2 elements at a time, it will be a 2x4
1711  // matrix (with elements 01, 23, 45, etc.), or two 2x2 matrices:
1712  // 01 23 45 67
1713  // 89 AB CD EF
1714  // With groups of 4, this will become a single 2x2 matrix, and so on.
1715  //
1716  // The 2x2 transpose instruction works by transposing each of the 2x2
1717  // matrices (or "sub-matrices"), given a specific group size. For example,
1718  // if the group size is 1 (i.e. each element is its own group), there
1719  // will be four transposes of the four 2x2 matrices that form the 2x8.
1720  // For example, with the inputs as above, the result will be:
1721  // 0 8 2 A 4 C 6 E
1722  // 1 9 3 B 5 D 7 F
1723  // Now, this result can be tranposed again, but with the group size of 2:
1724  // 08 19 4C 5D
1725  // 2A 3B 6E 7F
1726  // If we then transpose that result, but with the group size of 4, we get:
1727  // 0819 2A3B
1728  // 4C5D 6E7F
1729  // If we concatenate these two rows, it will be
1730  // 0 8 1 9 2 A 3 B 4 C 5 D 6 E 7 F
1731  // which is the same as the "deal" [*] above.
1732  //
1733  // In general, a "deal" of individual elements is a series of 2x2 transposes,
1734  // with changing group size. HVX has two instructions:
1735  // Vdd = V6_vdealvdd Vu, Vv, Rt
1736  // Vdd = V6_shufvdd Vu, Vv, Rt
1737  // that perform exactly that. The register Rt controls which transposes are
1738  // going to happen: a bit at position n (counting from 0) indicates that a
1739  // transpose with a group size of 2^n will take place. If multiple bits are
1740  // set, multiple transposes will happen: vdealvdd will perform them starting
1741  // with the largest group size, vshuffvdd will do them in the reverse order.
1742  //
1743  // The main observation is that each 2x2 transpose corresponds to swapping
1744  // columns of bits in the binary representation of the values.
1745  //
1746  // The numbers {3,2,1,0} and the log2 of the number of contiguous 1 bits
1747  // in a given column. The * denote the columns that will be swapped.
1748  // The transpose with the group size 2^n corresponds to swapping columns
1749  // 3 (the highest log) and log2(n):
1750  //
1751  // 3 2 1 0 0 2 1 3 0 2 3 1
1752  // * * * * * *
1753  // 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1754  // 1 0 0 0 1 8 1 0 0 0 8 1 0 0 0 8 1 0 0 0
1755  // 2 0 0 1 0 2 0 0 1 0 1 0 0 0 1 1 0 0 0 1
1756  // 3 0 0 1 1 A 1 0 1 0 9 1 0 0 1 9 1 0 0 1
1757  // 4 0 1 0 0 4 0 1 0 0 4 0 1 0 0 2 0 0 1 0
1758  // 5 0 1 0 1 C 1 1 0 0 C 1 1 0 0 A 1 0 1 0
1759  // 6 0 1 1 0 6 0 1 1 0 5 0 1 0 1 3 0 0 1 1
1760  // 7 0 1 1 1 E 1 1 1 0 D 1 1 0 1 B 1 0 1 1
1761  // 8 1 0 0 0 1 0 0 0 1 2 0 0 1 0 4 0 1 0 0
1762  // 9 1 0 0 1 9 1 0 0 1 A 1 0 1 0 C 1 1 0 0
1763  // A 1 0 1 0 3 0 0 1 1 3 0 0 1 1 5 0 1 0 1
1764  // B 1 0 1 1 B 1 0 1 1 B 1 0 1 1 D 1 1 0 1
1765  // C 1 1 0 0 5 0 1 0 1 6 0 1 1 0 6 0 1 1 0
1766  // D 1 1 0 1 D 1 1 0 1 E 1 1 1 0 E 1 1 1 0
1767  // E 1 1 1 0 7 0 1 1 1 7 0 1 1 1 7 0 1 1 1
1768  // F 1 1 1 1 F 1 1 1 1 F 1 1 1 1 F 1 1 1 1
1769 
1770  auto XorPow2 = [] (ArrayRef<int> Mask, unsigned Num) {
1771  unsigned X = Mask[0] ^ Mask[Num/2];
1772  // Check that the first half has the X's bits clear.
1773  if ((Mask[0] & X) != 0)
1774  return 0u;
1775  for (unsigned I = 1; I != Num/2; ++I) {
1776  if (unsigned(Mask[I] ^ Mask[I+Num/2]) != X)
1777  return 0u;
1778  if ((Mask[I] & X) != 0)
1779  return 0u;
1780  }
1781  return X;
1782  };
1783 
1784  // Create a vector of log2's for each column: Perm[i] corresponds to
1785  // the i-th bit (lsb is 0).
1786  assert(VecLen > 2);
1787  for (unsigned I = VecLen; I >= 2; I >>= 1) {
1788  // Examine the initial segment of Mask of size I.
1789  unsigned X = XorPow2(SM.Mask, I);
1790  if (!isPowerOf2_32(X))
1791  return OpRef::fail();
1792  // Check the other segments of Mask.
1793  for (int J = I; J < VecLen; J += I) {
1794  if (XorPow2(SM.Mask.slice(J, I), I) != X)
1795  return OpRef::fail();
1796  }
1797  Perm[Log2_32(X)] = Log2_32(I)-1;
1798  }
1799 
1800  // Once we have Perm, represent it as cycles. Denote the maximum log2
1801  // (equal to log2(VecLen)-1) as M. The cycle containing M can then be
1802  // written as (M a1 a2 a3 ... an). That cycle can be broken up into
1803  // simple swaps as (M a1)(M a2)(M a3)...(M an), with the composition
1804  // order being from left to right. Any (contiguous) segment where the
1805  // values ai, ai+1...aj are either all increasing or all decreasing,
1806  // can be implemented via a single vshuffvdd/vdealvdd respectively.
1807  //
1808  // If there is a cycle (a1 a2 ... an) that does not involve M, it can
1809  // be written as (M an)(a1 a2 ... an)(M a1). The first two cycles can
1810  // then be folded to get (M a1 a2 ... an)(M a1), and the above procedure
1811  // can be used to generate a sequence of vshuffvdd/vdealvdd.
1812  //
1813  // Example:
1814  // Assume M = 4 and consider a permutation (0 1)(2 3). It can be written
1815  // as (4 0 1)(4 0) composed with (4 2 3)(4 2), or simply
1816  // (4 0 1)(4 0)(4 2 3)(4 2).
1817  // It can then be expanded into swaps as
1818  // (4 0)(4 1)(4 0)(4 2)(4 3)(4 2),
1819  // and broken up into "increasing" segments as
1820  // [(4 0)(4 1)] [(4 0)(4 2)(4 3)] [(4 2)].
1821  // This is equivalent to
1822  // (4 0 1)(4 0 2 3)(4 2),
1823  // which can be implemented as 3 vshufvdd instructions.
1824 
1825  using CycleType = SmallVector<unsigned,8>;
1826  std::set<CycleType> Cycles;
1827  std::set<unsigned> All;
1828 
1829  for (unsigned I : Perm)
1830  All.insert(I);
1831 
1832  // If the cycle contains LogLen-1, move it to the front of the cycle.
1833  // Otherwise, return the cycle unchanged.
1834  auto canonicalize = [LogLen](const CycleType &C) -> CycleType {
1835  unsigned LogPos, N = C.size();
1836  for (LogPos = 0; LogPos != N; ++LogPos)
1837  if (C[LogPos] == LogLen-1)
1838  break;
1839  if (LogPos == N)
1840  return C;
1841 
1842  CycleType NewC(C.begin()+LogPos, C.end());
1843  NewC.append(C.begin(), C.begin()+LogPos);
1844  return NewC;
1845  };
1846 
1847  auto pfs = [](const std::set<CycleType> &Cs, unsigned Len) {
1848  // Ordering: shuff: 5 0 1 2 3 4, deal: 5 4 3 2 1 0 (for Log=6),
1849  // for bytes zero is included, for halfwords is not.
1850  if (Cs.size() != 1)
1851  return 0u;
1852  const CycleType &C = *Cs.begin();
1853  if (C[0] != Len-1)
1854  return 0u;
1855  int D = Len - C.size();
1856  if (D != 0 && D != 1)
1857  return 0u;
1858 
1859  bool IsDeal = true, IsShuff = true;
1860  for (unsigned I = 1; I != Len-D; ++I) {
1861  if (C[I] != Len-1-I)
1862  IsDeal = false;
1863  if (C[I] != I-(1-D)) // I-1, I
1864  IsShuff = false;
1865  }
1866  // At most one, IsDeal or IsShuff, can be non-zero.
1867  assert(!(IsDeal || IsShuff) || IsDeal != IsShuff);
1868  static unsigned Deals[] = { Hexagon::V6_vdealb, Hexagon::V6_vdealh };
1869  static unsigned Shufs[] = { Hexagon::V6_vshuffb, Hexagon::V6_vshuffh };
1870  return IsDeal ? Deals[D] : (IsShuff ? Shufs[D] : 0);
1871  };
1872 
1873  while (!All.empty()) {
1874  unsigned A = *All.begin();
1875  All.erase(A);
1876  CycleType C;
1877  C.push_back(A);
1878  for (unsigned B = Perm[A]; B != A; B = Perm[B]) {
1879  C.push_back(B);
1880  All.erase(B);
1881  }
1882  if (C.size() <= 1)
1883  continue;
1884  Cycles.insert(canonicalize(C));
1885  }
1886 
1887  MVT SingleTy = getSingleVT(MVT::i8);
1889 
1890  // Recognize patterns for V6_vdeal{b,h} and V6_vshuff{b,h}.
1891  if (unsigned(VecLen) == HwLen) {
1892  if (unsigned SingleOpc = pfs(Cycles, LogLen)) {
1893  Results.push(SingleOpc, SingleTy, {Va});
1894  return OpRef::res(Results.top());
1895  }
1896  }
1897 
1898  SmallVector<unsigned,8> SwapElems;
1899  if (HwLen == unsigned(VecLen))
1900  SwapElems.push_back(LogLen-1);
1901 
1902  for (const CycleType &C : Cycles) {
1903  unsigned First = (C[0] == LogLen-1) ? 1 : 0;
1904  SwapElems.append(C.begin()+First, C.end());
1905  if (First == 0)
1906  SwapElems.push_back(C[0]);
1907  }
1908 
1909  const SDLoc &dl(Results.InpNode);
1910  OpRef Arg = !Extend ? Va
1911  : concat(Va, OpRef::undef(SingleTy), Results);
1912 
1913  for (unsigned I = 0, E = SwapElems.size(); I != E; ) {
1914  bool IsInc = I == E-1 || SwapElems[I] < SwapElems[I+1];
1915  unsigned S = (1u << SwapElems[I]);
1916  if (I < E-1) {
1917  while (++I < E-1 && IsInc == (SwapElems[I] < SwapElems[I+1]))
1918  S |= 1u << SwapElems[I];
1919  // The above loop will not add a bit for the final SwapElems[I+1],
1920  // so add it here.
1921  S |= 1u << SwapElems[I];
1922  }
1923  ++I;
1924 
1925  NodeTemplate Res;
1926  Results.push(Hexagon::A2_tfrsi, MVT::i32,
1927  { DAG.getTargetConstant(S, dl, MVT::i32) });
1928  Res.Opc = IsInc ? Hexagon::V6_vshuffvdd : Hexagon::V6_vdealvdd;
1929  Res.Ty = PairTy;
1930  Res.Ops = { OpRef::hi(Arg), OpRef::lo(Arg), OpRef::res(-1) };
1931  Results.push(Res);
1932  Arg = OpRef::res(Results.top());
1933  }
1934 
1935  return !Extend ? Arg : OpRef::lo(Arg);
1936 }
1937 
1938 OpRef HvxSelector::butterfly(ShuffleMask SM, OpRef Va, ResultStack &Results) {
1939  DEBUG_WITH_TYPE("isel", {dbgs() << __func__ << '\n';});
1940  // Butterfly shuffles.
1941  //
1942  // V6_vdelta
1943  // V6_vrdelta
1944  // V6_vror
1945 
1946  // The assumption here is that all elements picked by Mask are in the
1947  // first operand to the vector_shuffle. This assumption is enforced
1948  // by the caller.
1949 
1950  MVT ResTy = getSingleVT(MVT::i8);
1951  PermNetwork::Controls FC, RC;
1952  const SDLoc &dl(Results.InpNode);
1953  int VecLen = SM.Mask.size();
1954 
1955  for (int M : SM.Mask) {
1956  if (M != -1 && M >= VecLen)
1957  return OpRef::fail();
1958  }
1959 
1960  // Try the deltas/benes for both single vectors and vector pairs.
1961  ForwardDeltaNetwork FN(SM.Mask);
1962  if (FN.run(FC)) {
1963  SDValue Ctl = getVectorConstant(FC, dl);
1964  Results.push(Hexagon::V6_vdelta, ResTy, {Va, OpRef(Ctl)});
1965  return OpRef::res(Results.top());
1966  }
1967 
1968  // Try reverse delta.
1969  ReverseDeltaNetwork RN(SM.Mask);
1970  if (RN.run(RC)) {
1971  SDValue Ctl = getVectorConstant(RC, dl);
1972  Results.push(Hexagon::V6_vrdelta, ResTy, {Va, OpRef(Ctl)});
1973  return OpRef::res(Results.top());
1974  }
1975 
1976  // Do Benes.
1977  BenesNetwork BN(SM.Mask);
1978  if (BN.run(FC, RC)) {
1979  SDValue CtlF = getVectorConstant(FC, dl);
1980  SDValue CtlR = getVectorConstant(RC, dl);
1981  Results.push(Hexagon::V6_vdelta, ResTy, {Va, OpRef(CtlF)});
1982  Results.push(Hexagon::V6_vrdelta, ResTy,
1983  {OpRef::res(-1), OpRef(CtlR)});
1984  return OpRef::res(Results.top());
1985  }
1986 
1987  return OpRef::fail();
1988 }
1989 
1990 SDValue HvxSelector::getVectorConstant(ArrayRef<uint8_t> Data,
1991  const SDLoc &dl) {
1993  for (uint8_t C : Data)
1994  Elems.push_back(DAG.getConstant(C, dl, MVT::i8));
1995  MVT VecTy = MVT::getVectorVT(MVT::i8, Data.size());
1996  SDValue BV = DAG.getBuildVector(VecTy, dl, Elems);
1997  SDValue LV = Lower.LowerOperation(BV, DAG);
1998  DAG.RemoveDeadNode(BV.getNode());
1999  return LV;
2000 }
2001 
2003  DEBUG_WITH_TYPE("isel", {
2004  dbgs() << "Starting " << __func__ << " on node:\n";
2005  N->dump(&DAG);
2006  });
2007  MVT ResTy = N->getValueType(0).getSimpleVT();
2008  // Assume that vector shuffles operate on vectors of bytes.
2009  assert(ResTy.isVector() && ResTy.getVectorElementType() == MVT::i8);
2010 
2011  auto *SN = cast<ShuffleVectorSDNode>(N);
2012  std::vector<int> Mask(SN->getMask().begin(), SN->getMask().end());
2013  // This shouldn't really be necessary. Is it?
2014  for (int &Idx : Mask)
2015  if (Idx != -1 && Idx < 0)
2016  Idx = -1;
2017 
2018  unsigned VecLen = Mask.size();
2019  bool HavePairs = (2*HwLen == VecLen);
2020  assert(ResTy.getSizeInBits() / 8 == VecLen);
2021 
2022  // Vd = vector_shuffle Va, Vb, Mask
2023  //
2024 
2025  bool UseLeft = false, UseRight = false;
2026  for (unsigned I = 0; I != VecLen; ++I) {
2027  if (Mask[I] == -1)
2028  continue;
2029  unsigned Idx = Mask[I];
2030  assert(Idx < 2*VecLen);
2031  if (Idx < VecLen)
2032  UseLeft = true;
2033  else
2034  UseRight = true;
2035  }
2036 
2037  DEBUG_WITH_TYPE("isel", {
2038  dbgs() << "VecLen=" << VecLen << " HwLen=" << HwLen << " UseLeft="
2039  << UseLeft << " UseRight=" << UseRight << " HavePairs="
2040  << HavePairs << '\n';
2041  });
2042  // If the mask is all -1's, generate "undef".
2043  if (!UseLeft && !UseRight) {
2044  ISel.ReplaceNode(N, ISel.selectUndef(SDLoc(SN), ResTy).getNode());
2045  return;
2046  }
2047 
2048  SDValue Vec0 = N->getOperand(0);
2049  SDValue Vec1 = N->getOperand(1);
2050  ResultStack Results(SN);
2051  Results.push(TargetOpcode::COPY, ResTy, {Vec0});
2052  Results.push(TargetOpcode::COPY, ResTy, {Vec1});
2053  OpRef Va = OpRef::res(Results.top()-1);
2054  OpRef Vb = OpRef::res(Results.top());
2055 
2056  OpRef Res = !HavePairs ? shuffs2(ShuffleMask(Mask), Va, Vb, Results)
2057  : shuffp2(ShuffleMask(Mask), Va, Vb, Results);
2058 
2059  bool Done = Res.isValid();
2060  if (Done) {
2061  // Make sure that Res is on the stack before materializing.
2062  Results.push(TargetOpcode::COPY, ResTy, {Res});
2063  materialize(Results);
2064  } else {
2065  Done = scalarizeShuffle(Mask, SDLoc(N), ResTy, Vec0, Vec1, N);
2066  }
2067 
2068  if (!Done) {
2069 #ifndef NDEBUG
2070  dbgs() << "Unhandled shuffle:\n";
2071  SN->dumpr(&DAG);
2072 #endif
2073  llvm_unreachable("Failed to select vector shuffle");
2074  }
2075 }
2076 
2078  // If this is a rotation by less than 8, use V6_valignbi.
2079  MVT Ty = N->getValueType(0).getSimpleVT();
2080  const SDLoc &dl(N);
2081  SDValue VecV = N->getOperand(0);
2082  SDValue RotV = N->getOperand(1);
2083  SDNode *NewN = nullptr;
2084 
2085  if (auto *CN = dyn_cast<ConstantSDNode>(RotV.getNode())) {
2086  unsigned S = CN->getZExtValue() % HST.getVectorLength();
2087  if (S == 0) {
2088  NewN = VecV.getNode();
2089  } else if (isUInt<3>(S)) {
2091  NewN = DAG.getMachineNode(Hexagon::V6_valignbi, dl, Ty,
2092  {VecV, VecV, C});
2093  }
2094  }
2095 
2096  if (!NewN)
2097  NewN = DAG.getMachineNode(Hexagon::V6_vror, dl, Ty, {VecV, RotV});
2098 
2099  ISel.ReplaceNode(N, NewN);
2100 }
2101 
2103  SDValue Vv = N->getOperand(0);
2104  SDValue Vu = N->getOperand(1);
2105  SDValue Rt = N->getOperand(2);
2106  SDNode *NewN = DAG.getMachineNode(Hexagon::V6_valignb, SDLoc(N),
2107  N->getValueType(0), {Vv, Vu, Rt});
2108  ISel.ReplaceNode(N, NewN);
2109  DAG.RemoveDeadNode(N);
2110 }
2111 
2112 void HexagonDAGToDAGISel::SelectHvxShuffle(SDNode *N) {
2113  HvxSelector(*this, *CurDAG).selectShuffle(N);
2114 }
2115 
2116 void HexagonDAGToDAGISel::SelectHvxRor(SDNode *N) {
2117  HvxSelector(*this, *CurDAG).selectRor(N);
2118 }
2119 
2120 void HexagonDAGToDAGISel::SelectHvxVAlign(SDNode *N) {
2121  HvxSelector(*this, *CurDAG).selectVAlign(N);
2122 }
2123 
2125  const SDLoc &dl(N);
2126  SDValue Chain = N->getOperand(0);
2127  SDValue Address = N->getOperand(2);
2128  SDValue Predicate = N->getOperand(3);
2129  SDValue Base = N->getOperand(4);
2130  SDValue Modifier = N->getOperand(5);
2131  SDValue Offset = N->getOperand(6);
2132 
2133  unsigned Opcode;
2134  unsigned IntNo = cast<ConstantSDNode>(N->getOperand(1))->getZExtValue();
2135  switch (IntNo) {
2136  default:
2137  llvm_unreachable("Unexpected HVX gather intrinsic.");
2138  case Intrinsic::hexagon_V6_vgathermhq:
2139  case Intrinsic::hexagon_V6_vgathermhq_128B:
2140  Opcode = Hexagon::V6_vgathermhq_pseudo;
2141  break;
2142  case Intrinsic::hexagon_V6_vgathermwq:
2143  case Intrinsic::hexagon_V6_vgathermwq_128B:
2144  Opcode = Hexagon::V6_vgathermwq_pseudo;
2145  break;
2146  case Intrinsic::hexagon_V6_vgathermhwq:
2147  case Intrinsic::hexagon_V6_vgathermhwq_128B:
2148  Opcode = Hexagon::V6_vgathermhwq_pseudo;
2149  break;
2150  }
2151 
2152  SDVTList VTs = CurDAG->getVTList(MVT::Other);
2153  SDValue Ops[] = { Address, Predicate, Base, Modifier, Offset, Chain };
2154  SDNode *Result = CurDAG->getMachineNode(Opcode, dl, VTs, Ops);
2155 
2156  MachineMemOperand *MemOp = cast<MemIntrinsicSDNode>(N)->getMemOperand();
2157  CurDAG->setNodeMemRefs(cast<MachineSDNode>(Result), {MemOp});
2158 
2159  ReplaceNode(N, Result);
2160 }
2161 
2163  const SDLoc &dl(N);
2164  SDValue Chain = N->getOperand(0);
2165  SDValue Address = N->getOperand(2);
2166  SDValue Base = N->getOperand(3);
2167  SDValue Modifier = N->getOperand(4);
2168  SDValue Offset = N->getOperand(5);
2169 
2170  unsigned Opcode;
2171  unsigned IntNo = cast<ConstantSDNode>(N->getOperand(1))->getZExtValue();
2172  switch (IntNo) {
2173  default:
2174  llvm_unreachable("Unexpected HVX gather intrinsic.");
2175  case Intrinsic::hexagon_V6_vgathermh:
2176  case Intrinsic::hexagon_V6_vgathermh_128B:
2177  Opcode = Hexagon::V6_vgathermh_pseudo;
2178  break;
2179  case Intrinsic::hexagon_V6_vgathermw:
2180  case Intrinsic::hexagon_V6_vgathermw_128B:
2181  Opcode = Hexagon::V6_vgathermw_pseudo;
2182  break;
2183  case Intrinsic::hexagon_V6_vgathermhw:
2184  case Intrinsic::hexagon_V6_vgathermhw_128B:
2185  Opcode = Hexagon::V6_vgathermhw_pseudo;
2186  break;
2187  }
2188 
2189  SDVTList VTs = CurDAG->getVTList(MVT::Other);
2190  SDValue Ops[] = { Address, Base, Modifier, Offset, Chain };
2191  SDNode *Result = CurDAG->getMachineNode(Opcode, dl, VTs, Ops);
2192 
2193  MachineMemOperand *MemOp = cast<MemIntrinsicSDNode>(N)->getMemOperand();
2194  CurDAG->setNodeMemRefs(cast<MachineSDNode>(Result), {MemOp});
2195 
2196  ReplaceNode(N, Result);
2197 }
2198 
2200  unsigned IID = cast<ConstantSDNode>(N->getOperand(0))->getZExtValue();
2201  SDNode *Result;
2202  switch (IID) {
2203  case Intrinsic::hexagon_V6_vaddcarry: {
2204  SmallVector<SDValue, 3> Ops = { N->getOperand(1), N->getOperand(2),
2205  N->getOperand(3) };
2206  SDVTList VTs = CurDAG->getVTList(MVT::v16i32, MVT::v512i1);
2207  Result = CurDAG->getMachineNode(Hexagon::V6_vaddcarry, SDLoc(N), VTs, Ops);
2208  break;
2209  }
2210  case Intrinsic::hexagon_V6_vaddcarry_128B: {
2211  SmallVector<SDValue, 3> Ops = { N->getOperand(1), N->getOperand(2),
2212  N->getOperand(3) };
2213  SDVTList VTs = CurDAG->getVTList(MVT::v32i32, MVT::v1024i1);
2214  Result = CurDAG->getMachineNode(Hexagon::V6_vaddcarry, SDLoc(N), VTs, Ops);
2215  break;
2216  }
2217  case Intrinsic::hexagon_V6_vsubcarry: {
2218  SmallVector<SDValue, 3> Ops = { N->getOperand(1), N->getOperand(2),
2219  N->getOperand(3) };
2220  SDVTList VTs = CurDAG->getVTList(MVT::v16i32, MVT::v512i1);
2221  Result = CurDAG->getMachineNode(Hexagon::V6_vsubcarry, SDLoc(N), VTs, Ops);
2222  break;
2223  }
2224  case Intrinsic::hexagon_V6_vsubcarry_128B: {
2225  SmallVector<SDValue, 3> Ops = { N->getOperand(1), N->getOperand(2),
2226  N->getOperand(3) };
2227  SDVTList VTs = CurDAG->getVTList(MVT::v32i32, MVT::v1024i1);
2228  Result = CurDAG->getMachineNode(Hexagon::V6_vsubcarry, SDLoc(N), VTs, Ops);
2229  break;
2230  }
2231  default:
2232  llvm_unreachable("Unexpected HVX dual output intrinsic.");
2233  }
2234  ReplaceUses(N, Result);
2235  ReplaceUses(SDValue(N, 0), SDValue(Result, 0));
2236  ReplaceUses(SDValue(N, 1), SDValue(Result, 1));
2237  CurDAG->RemoveDeadNode(N);
2238 }
detail::concat_range< ValueT, RangeTs... > concat(RangeTs &&... Ranges)
Concatenated range across two or more ranges.
Definition: STLExtras.h:809
Pass interface - Implemented by all &#39;passes&#39;.
Definition: Pass.h:81
const NoneType None
Definition: None.h:24
uint64_t CallInst * C
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:259
const HexagonTargetLowering & Lower
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
ArrayRef< T > take_front(size_t N=1) const
Return a copy of *this with only the first N elements.
Definition: ArrayRef.h:212
GCNRegPressure max(const GCNRegPressure &P1, const GCNRegPressure &P2)
unsigned getOpcode() const
Return the SelectionDAG opcode value for this node.
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:250
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
size_type size() const
Determine the number of elements in the SetVector.
Definition: SetVector.h:78
static MVT getVectorVT(MVT VT, unsigned NumElements)
HexagonDAGToDAGISel & ISel
Implements a dense probed hash-table based set.
Definition: DenseSet.h:250
EVT getValueType(unsigned ResNo) const
Return the type of a specified result.
Stack Slot Coloring
format_object< Ts... > format(const char *Fmt, const Ts &... Vals)
These are helper functions used to produce formatted output.
Definition: Format.h:124
MVT getSimpleVT() const
Return the SimpleValueType held in the specified simple EVT.
Definition: ValueTypes.h:253
unsigned getVectorNumElements() const
Function Alias Analysis Results
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1048
static void dump(StringRef Title, SpillInfo const &Spills)
Definition: CoroFrame.cpp:299
static bool isPermutation(ArrayRef< int > Mask)
F(f)
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.
iterator end()
Get an iterator to the end of the SetVector.
Definition: SetVector.h:93
std::pair< MCSymbol *, MachineModuleInfoImpl::StubValueTy > PairTy
#define DEBUG_WITH_TYPE(TYPE, X)
DEBUG_WITH_TYPE macro - This macro should be used by passes to emit debug information.
Definition: Debug.h:65
static void splitMask(ArrayRef< int > Mask, MutableArrayRef< int > MaskL, MutableArrayRef< int > MaskR)
bool hasOneUse() const
Return true if there is exactly one use of this node.
A description of a memory reference used in the backend.
const HexagonInstrInfo * TII
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.
SimpleValueType SimpleTy
#define LLVM_DUMP_METHOD
Definition: Compiler.h:74
This represents a list of ValueType&#39;s that has been intern&#39;d by a SelectionDAG.
iterator_range< allnodes_iterator > allnodes()
Definition: SelectionDAG.h:446
unsigned getSizeInBits() const
auto reverse(ContainerTy &&C, typename std::enable_if< has_rbegin< ContainerTy >::value >::type *=nullptr) -> decltype(make_range(C.rbegin(), C.rend()))
Definition: STLExtras.h:257
MVT getSingleVT(MVT ElemTy) const
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:142
#define T
iterator begin()
Get an iterator to the beginning of the SetVector.
Definition: SetVector.h:83
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:33
virtual const TargetInstrInfo * getInstrInfo() const
SDValue getTargetConstant(uint64_t Val, const SDLoc &DL, EVT VT, bool isOpaque=false)
Definition: SelectionDAG.h:573
ArrayRef< SDUse > ops() const
MVT getVectorElementType() const
size_type count(const key_type &key) const
Count the number of elements of a given key in the SetVector.
Definition: SetVector.h:211
TargetInstrInfo - Interface to description of machine instruction set.
Error build(ArrayRef< Module *> Mods, SmallVector< char, 0 > &Symtab, StringTableBuilder &StrtabBuilder, BumpPtrAllocator &Alloc)
Fills in Symtab and StrtabBuilder with a valid symbol and string table for Mods.
Definition: IRSymtab.cpp:323
#define P(N)
static const HexagonTargetLowering & getHexagonLowering(SelectionDAG &G)
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
constexpr bool isUInt< 8 >(uint64_t x)
Definition: MathExtras.h:343
MutableArrayRef - Represent a mutable reference to an array (0 or more elements consecutively in memo...
Definition: ArrayRef.h:291
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:429
Machine Value Type.
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:69
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:149
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
const SDValue & getOperand(unsigned Num) const
static const HexagonSubtarget & getHexagonSubtarget(SelectionDAG &G)
static std::pair< int, unsigned > findStrip(ArrayRef< int > A, int Inc, unsigned MaxLen)
#define H(x, y, z)
Definition: MD5.cpp:57
void RemoveDeadNodes()
This method deletes all unreachable nodes in the SelectionDAG.
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
void RemoveDeadNode(SDNode *N)
Remove the specified node from the system.
Extended Value Type.
Definition: ValueTypes.h:34
StringRef getName(unsigned Opcode) const
Returns the name for the instructions with the given opcode.
Definition: MCInstrInfo.h:51
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.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
const HexagonSubtarget & HST
const T * data() const
Definition: ArrayRef.h:146
SDValue LowerOperation(SDValue Op, SelectionDAG &DAG) const override
This callback is invoked for operations that are unsupported by the target, which are registered to u...
constexpr bool empty(const T &RangeOrContainer)
Test whether RangeOrContainer is empty. Similar to C++17 std::empty.
Definition: STLExtras.h:200
BaseType
A given derived pointer can have multiple base pointers through phi/selects.
bool use_empty() const
Return true if there are no uses of this node.
static bool isUndef(ArrayRef< int > Mask)
void dump() const
Dump this node, for debugging.
const TargetLowering & getTargetLoweringInfo() const
Definition: SelectionDAG.h:401
print lazy value Lazy Value Info Printer Pass
Vector takeVector()
Clear the SetVector and return the underlying vector.
Definition: SetVector.h:67
SmallVectorImpl< T >::const_pointer c_str(SmallVectorImpl< T > &str)
unsigned countPopulation(T Value)
Count the number of set bits in a value.
Definition: MathExtras.h:520
Color
A "color", which is either even or odd.
auto size(R &&Range, typename std::enable_if< std::is_same< typename std::iterator_traits< decltype(Range.begin())>::iterator_category, std::random_access_iterator_tag >::value, void >::type *=nullptr) -> decltype(std::distance(Range.begin(), Range.end()))
Get the size of a range.
Definition: STLExtras.h:1029
EXTRACT_VECTOR_ELT(VECTOR, IDX) - Returns a single element from VECTOR identified by the (potentially...
Definition: ISDOpcodes.h:332
This is used to represent a portion of an LLVM function in a low-level Data Dependence DAG representa...
Definition: SelectionDAG.h:222
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:847
SDValue getBuildVector(EVT VT, const SDLoc &DL, ArrayRef< SDValue > Ops)
Return an ISD::BUILD_VECTOR node.
Definition: SelectionDAG.h:731
Predicate
Predicate - These are "(BI << 5) | BO" for various predicates.
Definition: PPCPredicates.h:27
const DataFlowGraph & G
Definition: RDFGraph.cpp:211
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.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:133
unsigned Log2_32(uint32_t Value)
Return the floor log base 2 of the specified value, -1 if the value is zero.
Definition: MathExtras.h:539
iterator_range< use_iterator > uses()
amdgpu Simplify well known AMD library false Value Value * Arg
std::set< NodeId > NodeSet
Definition: RDFGraph.h:514
HvxSelector(HexagonDAGToDAGISel &HS, SelectionDAG &G)
ArrayRef< T > take_back(size_t N=1) const
Return a copy of *this with only the last N elements.
Definition: ArrayRef.h:219
unsigned getVectorLength() const
pointer data()
Return a pointer to the vector&#39;s buffer, even if empty().
Definition: SmallVector.h:149
ArrayRef< T > drop_front(size_t N=1) const
Drop the first N elements of the array.
Definition: ArrayRef.h:188
LOAD and STORE have token chains as their first operand, then the same operands as an LLVM load/store...
Definition: ISDOpcodes.h:603
const NodeList & List
Definition: RDFGraph.cpp:210
#define I(x, y, z)
Definition: MD5.cpp:58
#define N
const TargetSubtargetInfo & getSubtarget() const
Definition: SelectionDAG.h:400
constexpr int32_t SignExtend32(uint32_t X)
Sign-extend the number in the bottom B bits of X to a 32-bit integer.
Definition: MathExtras.h:733
uint32_t Size
Definition: Profile.cpp:47
static bool isIdentity(ArrayRef< int > Mask)
size_type count(const_arg_type_t< ValueT > V) const
Return 1 if the specified key is in the set, 0 otherwise.
Definition: DenseSet.h:92
unsigned getOpcode() const
T * data() const
Definition: ArrayRef.h:329
SDValue getConstant(uint64_t Val, const SDLoc &DL, EVT VT, bool isTarget=false, bool isOpaque=false)
Create a ConstantSDNode wrapping a constant value.
CONCAT_VECTORS(VECTOR0, VECTOR1, ...) - Given a number of values of vector type with the same length ...
Definition: ISDOpcodes.h:338
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
void dumpr() const
Dump (recursively) this node and its use-def subgraph.
MVT getPairVT(MVT ElemTy) const
A vector that has set insertion semantics.
Definition: SetVector.h:41
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
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:46
void ReplaceNode(SDNode *F, SDNode *T)
Replace all uses of F with T, then remove F from the DAG.
const SDValue & getOperand(unsigned i) const
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...
EVT getTypeToTransformTo(LLVMContext &Context, EVT VT) const
For types supported by the target, this is an identity function.
static void fail(const SDLoc &DL, SelectionDAG &DAG, const Twine &Msg)
LLVMContext * getContext() const
Definition: SelectionDAG.h:404