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