xref: /freebsd/contrib/llvm-project/llvm/lib/Target/Hexagon/HexagonISelDAGToDAGHVX.cpp (revision cfd6422a5217410fbd66f7a7a8a64d9d85e61229)
1 //===-- HexagonISelDAGToDAGHVX.cpp ----------------------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 
9 #include "Hexagon.h"
10 #include "HexagonISelDAGToDAG.h"
11 #include "HexagonISelLowering.h"
12 #include "HexagonTargetMachine.h"
13 #include "llvm/ADT/SetVector.h"
14 #include "llvm/CodeGen/MachineInstrBuilder.h"
15 #include "llvm/CodeGen/SelectionDAGISel.h"
16 #include "llvm/IR/Intrinsics.h"
17 #include "llvm/IR/IntrinsicsHexagon.h"
18 #include "llvm/Support/CommandLine.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 
655   LLVM_DUMP_METHOD
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 
704   LLVM_DUMP_METHOD
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 {
734   const TargetInstrInfo &TII = *G.getSubtarget().getInstrInfo();
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 
773   ArrayRef<int> Mask;
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 
797 static const HexagonTargetLowering &getHexagonLowering(SelectionDAG &G) {
798   return static_cast<const HexagonTargetLowering&>(G.getTargetLoweringInfo());
799 }
800 static const HexagonSubtarget &getHexagonSubtarget(SelectionDAG &G) {
801   return static_cast<const HexagonSubtarget&>(G.getSubtarget());
802 }
803 
804 namespace llvm {
805   struct HvxSelector {
806     const HexagonTargetLowering &Lower;
807     HexagonDAGToDAGISel &ISel;
808     SelectionDAG &DAG;
809     const HexagonSubtarget &HST;
810     const unsigned HwLen;
811 
812     HvxSelector(HexagonDAGToDAGISel &HS, SelectionDAG &G)
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 
866 static void splitMask(ArrayRef<int> Mask, MutableArrayRef<int> MaskL,
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 
904 static bool isIdentity(ArrayRef<int> Mask) {
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 
913 static bool isPermutation(ArrayRef<int> Mask) {
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.
931   SmallVector<SDNode*,4> Nodes;
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.
936   DAG.RemoveDeadNodes();
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)
952           if (Addr.getOperand(0).getOpcode() == ISD::TargetConstantPool)
953             return true;
954       }
955       break;
956     }
957     // Make sure to select the operand of VSPLATW.
958     bool IsSplatOp = N->hasOneUse() &&
959                      N->use_begin()->getOpcode() == HexagonISD::VSPLATW;
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) {
998         MVT::SimpleValueType SVT = MVT::SimpleValueType(R.OpN & OpRef::Index);
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, HwLen);
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)
1339       : SelectionDAG::DAGNodeDeletedListener(D, [&C] (SDNode *N, SDNode *E) {
1340                                                   C.erase(N);
1341                                                 }) {}
1342   };
1343 
1344   template <typename T>
1345   struct NullifyingVector : public T {
1346     DenseMap<SDNode*, SDNode**> Refs;
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 
1389   SmallVector<SDValue,128> Ops;
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);
1888   MVT PairTy = getPairVT(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) {
1992   SmallVector<SDValue, 128> Elems;
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 
2002 void HvxSelector::selectShuffle(SDNode *N) {
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 
2077 void HvxSelector::selectRor(SDNode *N) {
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)) {
2090       SDValue C = DAG.getTargetConstant(S, dl, MVT::i32);
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 
2102 void HvxSelector::selectVAlign(SDNode *N) {
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 
2124 void HexagonDAGToDAGISel::SelectV65GatherPred(SDNode *N) {
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 
2162 void HexagonDAGToDAGISel::SelectV65Gather(SDNode *N) {
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 
2199 void HexagonDAGToDAGISel::SelectHVXDualOutput(SDNode *N) {
2200   unsigned IID = cast<ConstantSDNode>(N->getOperand(0))->getZExtValue();
2201   SDNode *Result;
2202   switch (IID) {
2203   case Intrinsic::hexagon_V6_vaddcarry: {
2204     std::array<SDValue, 3> Ops = {
2205         {N->getOperand(1), N->getOperand(2), N->getOperand(3)}};
2206     SDVTList VTs = CurDAG->getVTList(MVT::v16i32, MVT::v64i1);
2207     Result = CurDAG->getMachineNode(Hexagon::V6_vaddcarry, SDLoc(N), VTs, Ops);
2208     break;
2209   }
2210   case Intrinsic::hexagon_V6_vaddcarry_128B: {
2211     std::array<SDValue, 3> Ops = {
2212         {N->getOperand(1), N->getOperand(2), N->getOperand(3)}};
2213     SDVTList VTs = CurDAG->getVTList(MVT::v32i32, MVT::v128i1);
2214     Result = CurDAG->getMachineNode(Hexagon::V6_vaddcarry, SDLoc(N), VTs, Ops);
2215     break;
2216   }
2217   case Intrinsic::hexagon_V6_vsubcarry: {
2218     std::array<SDValue, 3> Ops = {
2219         {N->getOperand(1), N->getOperand(2), N->getOperand(3)}};
2220     SDVTList VTs = CurDAG->getVTList(MVT::v16i32, MVT::v64i1);
2221     Result = CurDAG->getMachineNode(Hexagon::V6_vsubcarry, SDLoc(N), VTs, Ops);
2222     break;
2223   }
2224   case Intrinsic::hexagon_V6_vsubcarry_128B: {
2225     std::array<SDValue, 3> Ops = {
2226         {N->getOperand(1), N->getOperand(2), N->getOperand(3)}};
2227     SDVTList VTs = CurDAG->getVTList(MVT::v32i32, MVT::v128i1);
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 }
2239