109467b48Spatrick //===-- HexagonISelDAGToDAGHVX.cpp ----------------------------------------===//
209467b48Spatrick //
309467b48Spatrick // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
409467b48Spatrick // See https://llvm.org/LICENSE.txt for license information.
509467b48Spatrick // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
609467b48Spatrick //
709467b48Spatrick //===----------------------------------------------------------------------===//
809467b48Spatrick
909467b48Spatrick #include "Hexagon.h"
1009467b48Spatrick #include "HexagonISelDAGToDAG.h"
1109467b48Spatrick #include "HexagonISelLowering.h"
1209467b48Spatrick #include "HexagonTargetMachine.h"
13*d415bd75Srobert #include "llvm/ADT/BitVector.h"
1409467b48Spatrick #include "llvm/ADT/SetVector.h"
1509467b48Spatrick #include "llvm/CodeGen/MachineInstrBuilder.h"
1609467b48Spatrick #include "llvm/CodeGen/SelectionDAGISel.h"
1709467b48Spatrick #include "llvm/IR/Intrinsics.h"
1809467b48Spatrick #include "llvm/IR/IntrinsicsHexagon.h"
1909467b48Spatrick #include "llvm/Support/CommandLine.h"
2009467b48Spatrick #include "llvm/Support/Debug.h"
21*d415bd75Srobert #include "llvm/Support/MathExtras.h"
2209467b48Spatrick
23*d415bd75Srobert #include <algorithm>
24*d415bd75Srobert #include <cmath>
2509467b48Spatrick #include <deque>
26*d415bd75Srobert #include <functional>
2709467b48Spatrick #include <map>
28*d415bd75Srobert #include <optional>
2909467b48Spatrick #include <set>
30*d415bd75Srobert #include <unordered_map>
3109467b48Spatrick #include <utility>
3209467b48Spatrick #include <vector>
3309467b48Spatrick
3409467b48Spatrick #define DEBUG_TYPE "hexagon-isel"
3509467b48Spatrick using namespace llvm;
3609467b48Spatrick
3709467b48Spatrick namespace {
3809467b48Spatrick
3909467b48Spatrick // --------------------------------------------------------------------
4009467b48Spatrick // Implementation of permutation networks.
4109467b48Spatrick
4209467b48Spatrick // Implementation of the node routing through butterfly networks:
4309467b48Spatrick // - Forward delta.
4409467b48Spatrick // - Reverse delta.
4509467b48Spatrick // - Benes.
4609467b48Spatrick //
4709467b48Spatrick //
4809467b48Spatrick // Forward delta network consists of log(N) steps, where N is the number
4909467b48Spatrick // of inputs. In each step, an input can stay in place, or it can get
5009467b48Spatrick // routed to another position[1]. The step after that consists of two
5109467b48Spatrick // networks, each half in size in terms of the number of nodes. In those
5209467b48Spatrick // terms, in the given step, an input can go to either the upper or the
5309467b48Spatrick // lower network in the next step.
5409467b48Spatrick //
5509467b48Spatrick // [1] Hexagon's vdelta/vrdelta allow an element to be routed to both
5609467b48Spatrick // positions as long as there is no conflict.
5709467b48Spatrick
5809467b48Spatrick // Here's a delta network for 8 inputs, only the switching routes are
5909467b48Spatrick // shown:
6009467b48Spatrick //
6109467b48Spatrick // Steps:
6209467b48Spatrick // |- 1 ---------------|- 2 -----|- 3 -|
6309467b48Spatrick //
6409467b48Spatrick // Inp[0] *** *** *** *** Out[0]
6509467b48Spatrick // \ / \ / \ /
6609467b48Spatrick // \ / \ / X
6709467b48Spatrick // \ / \ / / \
6809467b48Spatrick // Inp[1] *** \ / *** X *** *** Out[1]
6909467b48Spatrick // \ \ / / \ / \ /
7009467b48Spatrick // \ \ / / X X
7109467b48Spatrick // \ \ / / / \ / \
7209467b48Spatrick // Inp[2] *** \ \ / / *** X *** *** Out[2]
7309467b48Spatrick // \ \ X / / / \ \ /
7409467b48Spatrick // \ \ / \ / / / \ X
7509467b48Spatrick // \ X X / / \ / \
7609467b48Spatrick // Inp[3] *** \ / \ / \ / *** *** *** Out[3]
7709467b48Spatrick // \ X X X /
7809467b48Spatrick // \ / \ / \ / \ /
7909467b48Spatrick // X X X X
8009467b48Spatrick // / \ / \ / \ / \
8109467b48Spatrick // / X X X \
8209467b48Spatrick // Inp[4] *** / \ / \ / \ *** *** *** Out[4]
8309467b48Spatrick // / X X \ \ / \ /
8409467b48Spatrick // / / \ / \ \ \ / X
8509467b48Spatrick // / / X \ \ \ / / \
8609467b48Spatrick // Inp[5] *** / / \ \ *** X *** *** Out[5]
8709467b48Spatrick // / / \ \ \ / \ /
8809467b48Spatrick // / / \ \ X X
8909467b48Spatrick // / / \ \ / \ / \
9009467b48Spatrick // Inp[6] *** / \ *** X *** *** Out[6]
9109467b48Spatrick // / \ / \ \ /
9209467b48Spatrick // / \ / \ X
9309467b48Spatrick // / \ / \ / \
9409467b48Spatrick // Inp[7] *** *** *** *** Out[7]
9509467b48Spatrick //
9609467b48Spatrick //
9709467b48Spatrick // Reverse delta network is same as delta network, with the steps in
9809467b48Spatrick // the opposite order.
9909467b48Spatrick //
10009467b48Spatrick //
10109467b48Spatrick // Benes network is a forward delta network immediately followed by
10209467b48Spatrick // a reverse delta network.
10309467b48Spatrick
10409467b48Spatrick enum class ColorKind { None, Red, Black };
10509467b48Spatrick
10609467b48Spatrick // Graph coloring utility used to partition nodes into two groups:
10709467b48Spatrick // they will correspond to nodes routed to the upper and lower networks.
10809467b48Spatrick struct Coloring {
10909467b48Spatrick using Node = int;
11009467b48Spatrick using MapType = std::map<Node, ColorKind>;
11109467b48Spatrick static constexpr Node Ignore = Node(-1);
11209467b48Spatrick
Coloring__anona824ea740111::Coloring11309467b48Spatrick Coloring(ArrayRef<Node> Ord) : Order(Ord) {
11409467b48Spatrick build();
11509467b48Spatrick if (!color())
11609467b48Spatrick Colors.clear();
11709467b48Spatrick }
11809467b48Spatrick
colors__anona824ea740111::Coloring11909467b48Spatrick const MapType &colors() const {
12009467b48Spatrick return Colors;
12109467b48Spatrick }
12209467b48Spatrick
other__anona824ea740111::Coloring12309467b48Spatrick ColorKind other(ColorKind Color) {
12409467b48Spatrick if (Color == ColorKind::None)
12509467b48Spatrick return ColorKind::Red;
12609467b48Spatrick return Color == ColorKind::Red ? ColorKind::Black : ColorKind::Red;
12709467b48Spatrick }
12809467b48Spatrick
12909467b48Spatrick LLVM_DUMP_METHOD void dump() const;
13009467b48Spatrick
13109467b48Spatrick private:
13209467b48Spatrick ArrayRef<Node> Order;
13309467b48Spatrick MapType Colors;
13409467b48Spatrick std::set<Node> Needed;
13509467b48Spatrick
13609467b48Spatrick using NodeSet = std::set<Node>;
13709467b48Spatrick std::map<Node,NodeSet> Edges;
13809467b48Spatrick
conj__anona824ea740111::Coloring13909467b48Spatrick Node conj(Node Pos) {
14009467b48Spatrick Node Num = Order.size();
14109467b48Spatrick return (Pos < Num/2) ? Pos + Num/2 : Pos - Num/2;
14209467b48Spatrick }
14309467b48Spatrick
getColor__anona824ea740111::Coloring14409467b48Spatrick ColorKind getColor(Node N) {
14509467b48Spatrick auto F = Colors.find(N);
14609467b48Spatrick return F != Colors.end() ? F->second : ColorKind::None;
14709467b48Spatrick }
14809467b48Spatrick
14909467b48Spatrick std::pair<bool, ColorKind> getUniqueColor(const NodeSet &Nodes);
15009467b48Spatrick
15109467b48Spatrick void build();
15209467b48Spatrick bool color();
15309467b48Spatrick };
15409467b48Spatrick } // namespace
15509467b48Spatrick
getUniqueColor(const NodeSet & Nodes)15609467b48Spatrick std::pair<bool, ColorKind> Coloring::getUniqueColor(const NodeSet &Nodes) {
15709467b48Spatrick auto Color = ColorKind::None;
15809467b48Spatrick for (Node N : Nodes) {
15909467b48Spatrick ColorKind ColorN = getColor(N);
16009467b48Spatrick if (ColorN == ColorKind::None)
16109467b48Spatrick continue;
16209467b48Spatrick if (Color == ColorKind::None)
16309467b48Spatrick Color = ColorN;
16409467b48Spatrick else if (Color != ColorKind::None && Color != ColorN)
16509467b48Spatrick return { false, ColorKind::None };
16609467b48Spatrick }
16709467b48Spatrick return { true, Color };
16809467b48Spatrick }
16909467b48Spatrick
build()17009467b48Spatrick void Coloring::build() {
17109467b48Spatrick // Add Order[P] and Order[conj(P)] to Edges.
17209467b48Spatrick for (unsigned P = 0; P != Order.size(); ++P) {
17309467b48Spatrick Node I = Order[P];
17409467b48Spatrick if (I != Ignore) {
17509467b48Spatrick Needed.insert(I);
17609467b48Spatrick Node PC = Order[conj(P)];
17709467b48Spatrick if (PC != Ignore && PC != I)
17809467b48Spatrick Edges[I].insert(PC);
17909467b48Spatrick }
18009467b48Spatrick }
18109467b48Spatrick // Add I and conj(I) to Edges.
18209467b48Spatrick for (unsigned I = 0; I != Order.size(); ++I) {
18309467b48Spatrick if (!Needed.count(I))
18409467b48Spatrick continue;
18509467b48Spatrick Node C = conj(I);
18609467b48Spatrick // This will create an entry in the edge table, even if I is not
18709467b48Spatrick // connected to any other node. This is necessary, because it still
18809467b48Spatrick // needs to be colored.
18909467b48Spatrick NodeSet &Is = Edges[I];
19009467b48Spatrick if (Needed.count(C))
19109467b48Spatrick Is.insert(C);
19209467b48Spatrick }
19309467b48Spatrick }
19409467b48Spatrick
color()19509467b48Spatrick bool Coloring::color() {
19609467b48Spatrick SetVector<Node> FirstQ;
19709467b48Spatrick auto Enqueue = [this,&FirstQ] (Node N) {
19809467b48Spatrick SetVector<Node> Q;
19909467b48Spatrick Q.insert(N);
20009467b48Spatrick for (unsigned I = 0; I != Q.size(); ++I) {
20109467b48Spatrick NodeSet &Ns = Edges[Q[I]];
20209467b48Spatrick Q.insert(Ns.begin(), Ns.end());
20309467b48Spatrick }
20409467b48Spatrick FirstQ.insert(Q.begin(), Q.end());
20509467b48Spatrick };
20609467b48Spatrick for (Node N : Needed)
20709467b48Spatrick Enqueue(N);
20809467b48Spatrick
20909467b48Spatrick for (Node N : FirstQ) {
21009467b48Spatrick if (Colors.count(N))
21109467b48Spatrick continue;
21209467b48Spatrick NodeSet &Ns = Edges[N];
21309467b48Spatrick auto P = getUniqueColor(Ns);
21409467b48Spatrick if (!P.first)
21509467b48Spatrick return false;
21609467b48Spatrick Colors[N] = other(P.second);
21709467b48Spatrick }
21809467b48Spatrick
21909467b48Spatrick // First, color nodes that don't have any dups.
22009467b48Spatrick for (auto E : Edges) {
22109467b48Spatrick Node N = E.first;
22209467b48Spatrick if (!Needed.count(conj(N)) || Colors.count(N))
22309467b48Spatrick continue;
22409467b48Spatrick auto P = getUniqueColor(E.second);
22509467b48Spatrick if (!P.first)
22609467b48Spatrick return false;
22709467b48Spatrick Colors[N] = other(P.second);
22809467b48Spatrick }
22909467b48Spatrick
23009467b48Spatrick // Now, nodes that are still uncolored. Since the graph can be modified
23109467b48Spatrick // in this step, create a work queue.
23209467b48Spatrick std::vector<Node> WorkQ;
23309467b48Spatrick for (auto E : Edges) {
23409467b48Spatrick Node N = E.first;
23509467b48Spatrick if (!Colors.count(N))
23609467b48Spatrick WorkQ.push_back(N);
23709467b48Spatrick }
23809467b48Spatrick
239*d415bd75Srobert for (Node N : WorkQ) {
24009467b48Spatrick NodeSet &Ns = Edges[N];
24109467b48Spatrick auto P = getUniqueColor(Ns);
24209467b48Spatrick if (P.first) {
24309467b48Spatrick Colors[N] = other(P.second);
24409467b48Spatrick continue;
24509467b48Spatrick }
24609467b48Spatrick
24709467b48Spatrick // Coloring failed. Split this node.
24809467b48Spatrick Node C = conj(N);
24909467b48Spatrick ColorKind ColorN = other(ColorKind::None);
25009467b48Spatrick ColorKind ColorC = other(ColorN);
25109467b48Spatrick NodeSet &Cs = Edges[C];
25209467b48Spatrick NodeSet CopyNs = Ns;
25309467b48Spatrick for (Node M : CopyNs) {
25409467b48Spatrick ColorKind ColorM = getColor(M);
25509467b48Spatrick if (ColorM == ColorC) {
25609467b48Spatrick // Connect M with C, disconnect M from N.
25709467b48Spatrick Cs.insert(M);
25809467b48Spatrick Edges[M].insert(C);
25909467b48Spatrick Ns.erase(M);
26009467b48Spatrick Edges[M].erase(N);
26109467b48Spatrick }
26209467b48Spatrick }
26309467b48Spatrick Colors[N] = ColorN;
26409467b48Spatrick Colors[C] = ColorC;
26509467b48Spatrick }
26609467b48Spatrick
26709467b48Spatrick // Explicitly assign "None" to all uncolored nodes.
26809467b48Spatrick for (unsigned I = 0; I != Order.size(); ++I)
26909467b48Spatrick if (Colors.count(I) == 0)
27009467b48Spatrick Colors[I] = ColorKind::None;
27109467b48Spatrick
27209467b48Spatrick return true;
27309467b48Spatrick }
27409467b48Spatrick
27509467b48Spatrick #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
dump() const27609467b48Spatrick void Coloring::dump() const {
27709467b48Spatrick dbgs() << "{ Order: {";
278*d415bd75Srobert for (Node P : Order) {
27909467b48Spatrick if (P != Ignore)
28009467b48Spatrick dbgs() << ' ' << P;
28109467b48Spatrick else
28209467b48Spatrick dbgs() << " -";
28309467b48Spatrick }
28409467b48Spatrick dbgs() << " }\n";
28509467b48Spatrick dbgs() << " Needed: {";
28609467b48Spatrick for (Node N : Needed)
28709467b48Spatrick dbgs() << ' ' << N;
28809467b48Spatrick dbgs() << " }\n";
28909467b48Spatrick
29009467b48Spatrick dbgs() << " Edges: {\n";
29109467b48Spatrick for (auto E : Edges) {
29209467b48Spatrick dbgs() << " " << E.first << " -> {";
29309467b48Spatrick for (auto N : E.second)
29409467b48Spatrick dbgs() << ' ' << N;
29509467b48Spatrick dbgs() << " }\n";
29609467b48Spatrick }
29709467b48Spatrick dbgs() << " }\n";
29809467b48Spatrick
29909467b48Spatrick auto ColorKindToName = [](ColorKind C) {
30009467b48Spatrick switch (C) {
30109467b48Spatrick case ColorKind::None:
30209467b48Spatrick return "None";
30309467b48Spatrick case ColorKind::Red:
30409467b48Spatrick return "Red";
30509467b48Spatrick case ColorKind::Black:
30609467b48Spatrick return "Black";
30709467b48Spatrick }
30809467b48Spatrick llvm_unreachable("all ColorKinds should be handled by the switch above");
30909467b48Spatrick };
31009467b48Spatrick
31109467b48Spatrick dbgs() << " Colors: {\n";
31209467b48Spatrick for (auto C : Colors)
31309467b48Spatrick dbgs() << " " << C.first << " -> " << ColorKindToName(C.second) << "\n";
31409467b48Spatrick dbgs() << " }\n}\n";
31509467b48Spatrick }
31609467b48Spatrick #endif
31709467b48Spatrick
31809467b48Spatrick namespace {
31909467b48Spatrick // Base class of for reordering networks. They don't strictly need to be
32009467b48Spatrick // permutations, as outputs with repeated occurrences of an input element
32109467b48Spatrick // are allowed.
32209467b48Spatrick struct PermNetwork {
32309467b48Spatrick using Controls = std::vector<uint8_t>;
32409467b48Spatrick using ElemType = int;
32509467b48Spatrick static constexpr ElemType Ignore = ElemType(-1);
32609467b48Spatrick
32709467b48Spatrick enum : uint8_t {
32809467b48Spatrick None,
32909467b48Spatrick Pass,
33009467b48Spatrick Switch
33109467b48Spatrick };
33209467b48Spatrick enum : uint8_t {
33309467b48Spatrick Forward,
33409467b48Spatrick Reverse
33509467b48Spatrick };
33609467b48Spatrick
PermNetwork__anona824ea740411::PermNetwork33709467b48Spatrick PermNetwork(ArrayRef<ElemType> Ord, unsigned Mult = 1) {
33809467b48Spatrick Order.assign(Ord.data(), Ord.data()+Ord.size());
33909467b48Spatrick Log = 0;
34009467b48Spatrick
34109467b48Spatrick unsigned S = Order.size();
34209467b48Spatrick while (S >>= 1)
34309467b48Spatrick ++Log;
34409467b48Spatrick
34509467b48Spatrick Table.resize(Order.size());
34609467b48Spatrick for (RowType &Row : Table)
34709467b48Spatrick Row.resize(Mult*Log, None);
34809467b48Spatrick }
34909467b48Spatrick
getControls__anona824ea740411::PermNetwork35009467b48Spatrick void getControls(Controls &V, unsigned StartAt, uint8_t Dir) const {
35109467b48Spatrick unsigned Size = Order.size();
35209467b48Spatrick V.resize(Size);
35309467b48Spatrick for (unsigned I = 0; I != Size; ++I) {
35409467b48Spatrick unsigned W = 0;
35509467b48Spatrick for (unsigned L = 0; L != Log; ++L) {
35609467b48Spatrick unsigned C = ctl(I, StartAt+L) == Switch;
35709467b48Spatrick if (Dir == Forward)
35809467b48Spatrick W |= C << (Log-1-L);
35909467b48Spatrick else
36009467b48Spatrick W |= C << L;
36109467b48Spatrick }
36209467b48Spatrick assert(isUInt<8>(W));
36309467b48Spatrick V[I] = uint8_t(W);
36409467b48Spatrick }
36509467b48Spatrick }
36609467b48Spatrick
ctl__anona824ea740411::PermNetwork36709467b48Spatrick uint8_t ctl(ElemType Pos, unsigned Step) const {
36809467b48Spatrick return Table[Pos][Step];
36909467b48Spatrick }
size__anona824ea740411::PermNetwork37009467b48Spatrick unsigned size() const {
37109467b48Spatrick return Order.size();
37209467b48Spatrick }
steps__anona824ea740411::PermNetwork37309467b48Spatrick unsigned steps() const {
37409467b48Spatrick return Log;
37509467b48Spatrick }
37609467b48Spatrick
37709467b48Spatrick protected:
37809467b48Spatrick unsigned Log;
37909467b48Spatrick std::vector<ElemType> Order;
38009467b48Spatrick using RowType = std::vector<uint8_t>;
38109467b48Spatrick std::vector<RowType> Table;
38209467b48Spatrick };
38309467b48Spatrick
38409467b48Spatrick struct ForwardDeltaNetwork : public PermNetwork {
ForwardDeltaNetwork__anona824ea740411::ForwardDeltaNetwork38509467b48Spatrick ForwardDeltaNetwork(ArrayRef<ElemType> Ord) : PermNetwork(Ord) {}
38609467b48Spatrick
run__anona824ea740411::ForwardDeltaNetwork38709467b48Spatrick bool run(Controls &V) {
38809467b48Spatrick if (!route(Order.data(), Table.data(), size(), 0))
38909467b48Spatrick return false;
39009467b48Spatrick getControls(V, 0, Forward);
39109467b48Spatrick return true;
39209467b48Spatrick }
39309467b48Spatrick
39409467b48Spatrick private:
39509467b48Spatrick bool route(ElemType *P, RowType *T, unsigned Size, unsigned Step);
39609467b48Spatrick };
39709467b48Spatrick
39809467b48Spatrick struct ReverseDeltaNetwork : public PermNetwork {
ReverseDeltaNetwork__anona824ea740411::ReverseDeltaNetwork39909467b48Spatrick ReverseDeltaNetwork(ArrayRef<ElemType> Ord) : PermNetwork(Ord) {}
40009467b48Spatrick
run__anona824ea740411::ReverseDeltaNetwork40109467b48Spatrick bool run(Controls &V) {
40209467b48Spatrick if (!route(Order.data(), Table.data(), size(), 0))
40309467b48Spatrick return false;
40409467b48Spatrick getControls(V, 0, Reverse);
40509467b48Spatrick return true;
40609467b48Spatrick }
40709467b48Spatrick
40809467b48Spatrick private:
40909467b48Spatrick bool route(ElemType *P, RowType *T, unsigned Size, unsigned Step);
41009467b48Spatrick };
41109467b48Spatrick
41209467b48Spatrick struct BenesNetwork : public PermNetwork {
BenesNetwork__anona824ea740411::BenesNetwork41309467b48Spatrick BenesNetwork(ArrayRef<ElemType> Ord) : PermNetwork(Ord, 2) {}
41409467b48Spatrick
run__anona824ea740411::BenesNetwork41509467b48Spatrick bool run(Controls &F, Controls &R) {
41609467b48Spatrick if (!route(Order.data(), Table.data(), size(), 0))
41709467b48Spatrick return false;
41809467b48Spatrick
41909467b48Spatrick getControls(F, 0, Forward);
42009467b48Spatrick getControls(R, Log, Reverse);
42109467b48Spatrick return true;
42209467b48Spatrick }
42309467b48Spatrick
42409467b48Spatrick private:
42509467b48Spatrick bool route(ElemType *P, RowType *T, unsigned Size, unsigned Step);
42609467b48Spatrick };
42709467b48Spatrick } // namespace
42809467b48Spatrick
route(ElemType * P,RowType * T,unsigned Size,unsigned Step)42909467b48Spatrick bool ForwardDeltaNetwork::route(ElemType *P, RowType *T, unsigned Size,
43009467b48Spatrick unsigned Step) {
43109467b48Spatrick bool UseUp = false, UseDown = false;
43209467b48Spatrick ElemType Num = Size;
43309467b48Spatrick
43409467b48Spatrick // Cannot use coloring here, because coloring is used to determine
43509467b48Spatrick // the "big" switch, i.e. the one that changes halves, and in a forward
43609467b48Spatrick // network, a color can be simultaneously routed to both halves in the
43709467b48Spatrick // step we're working on.
43809467b48Spatrick for (ElemType J = 0; J != Num; ++J) {
43909467b48Spatrick ElemType I = P[J];
44009467b48Spatrick // I is the position in the input,
44109467b48Spatrick // J is the position in the output.
44209467b48Spatrick if (I == Ignore)
44309467b48Spatrick continue;
44409467b48Spatrick uint8_t S;
44509467b48Spatrick if (I < Num/2)
44609467b48Spatrick S = (J < Num/2) ? Pass : Switch;
44709467b48Spatrick else
44809467b48Spatrick S = (J < Num/2) ? Switch : Pass;
44909467b48Spatrick
45009467b48Spatrick // U is the element in the table that needs to be updated.
45109467b48Spatrick ElemType U = (S == Pass) ? I : (I < Num/2 ? I+Num/2 : I-Num/2);
45209467b48Spatrick if (U < Num/2)
45309467b48Spatrick UseUp = true;
45409467b48Spatrick else
45509467b48Spatrick UseDown = true;
45609467b48Spatrick if (T[U][Step] != S && T[U][Step] != None)
45709467b48Spatrick return false;
45809467b48Spatrick T[U][Step] = S;
45909467b48Spatrick }
46009467b48Spatrick
46109467b48Spatrick for (ElemType J = 0; J != Num; ++J)
46209467b48Spatrick if (P[J] != Ignore && P[J] >= Num/2)
46309467b48Spatrick P[J] -= Num/2;
46409467b48Spatrick
46509467b48Spatrick if (Step+1 < Log) {
46609467b48Spatrick if (UseUp && !route(P, T, Size/2, Step+1))
46709467b48Spatrick return false;
46809467b48Spatrick if (UseDown && !route(P+Size/2, T+Size/2, Size/2, Step+1))
46909467b48Spatrick return false;
47009467b48Spatrick }
47109467b48Spatrick return true;
47209467b48Spatrick }
47309467b48Spatrick
route(ElemType * P,RowType * T,unsigned Size,unsigned Step)47409467b48Spatrick bool ReverseDeltaNetwork::route(ElemType *P, RowType *T, unsigned Size,
47509467b48Spatrick unsigned Step) {
47609467b48Spatrick unsigned Pets = Log-1 - Step;
47709467b48Spatrick bool UseUp = false, UseDown = false;
47809467b48Spatrick ElemType Num = Size;
47909467b48Spatrick
48009467b48Spatrick // In this step half-switching occurs, so coloring can be used.
48109467b48Spatrick Coloring G({P,Size});
48209467b48Spatrick const Coloring::MapType &M = G.colors();
48309467b48Spatrick if (M.empty())
48409467b48Spatrick return false;
48509467b48Spatrick
48609467b48Spatrick ColorKind ColorUp = ColorKind::None;
48709467b48Spatrick for (ElemType J = 0; J != Num; ++J) {
48809467b48Spatrick ElemType I = P[J];
48909467b48Spatrick // I is the position in the input,
49009467b48Spatrick // J is the position in the output.
49109467b48Spatrick if (I == Ignore)
49209467b48Spatrick continue;
49309467b48Spatrick ColorKind C = M.at(I);
49409467b48Spatrick if (C == ColorKind::None)
49509467b48Spatrick continue;
49609467b48Spatrick // During "Step", inputs cannot switch halves, so if the "up" color
49709467b48Spatrick // is still unknown, make sure that it is selected in such a way that
49809467b48Spatrick // "I" will stay in the same half.
49909467b48Spatrick bool InpUp = I < Num/2;
50009467b48Spatrick if (ColorUp == ColorKind::None)
50109467b48Spatrick ColorUp = InpUp ? C : G.other(C);
50209467b48Spatrick if ((C == ColorUp) != InpUp) {
50309467b48Spatrick // If I should go to a different half than where is it now, give up.
50409467b48Spatrick return false;
50509467b48Spatrick }
50609467b48Spatrick
50709467b48Spatrick uint8_t S;
50809467b48Spatrick if (InpUp) {
50909467b48Spatrick S = (J < Num/2) ? Pass : Switch;
51009467b48Spatrick UseUp = true;
51109467b48Spatrick } else {
51209467b48Spatrick S = (J < Num/2) ? Switch : Pass;
51309467b48Spatrick UseDown = true;
51409467b48Spatrick }
51509467b48Spatrick T[J][Pets] = S;
51609467b48Spatrick }
51709467b48Spatrick
51809467b48Spatrick // Reorder the working permutation according to the computed switch table
51909467b48Spatrick // for the last step (i.e. Pets).
52009467b48Spatrick for (ElemType J = 0, E = Size / 2; J != E; ++J) {
52109467b48Spatrick ElemType PJ = P[J]; // Current values of P[J]
52209467b48Spatrick ElemType PC = P[J+Size/2]; // and P[conj(J)]
52309467b48Spatrick ElemType QJ = PJ; // New values of P[J]
52409467b48Spatrick ElemType QC = PC; // and P[conj(J)]
52509467b48Spatrick if (T[J][Pets] == Switch)
52609467b48Spatrick QC = PJ;
52709467b48Spatrick if (T[J+Size/2][Pets] == Switch)
52809467b48Spatrick QJ = PC;
52909467b48Spatrick P[J] = QJ;
53009467b48Spatrick P[J+Size/2] = QC;
53109467b48Spatrick }
53209467b48Spatrick
53309467b48Spatrick for (ElemType J = 0; J != Num; ++J)
53409467b48Spatrick if (P[J] != Ignore && P[J] >= Num/2)
53509467b48Spatrick P[J] -= Num/2;
53609467b48Spatrick
53709467b48Spatrick if (Step+1 < Log) {
53809467b48Spatrick if (UseUp && !route(P, T, Size/2, Step+1))
53909467b48Spatrick return false;
54009467b48Spatrick if (UseDown && !route(P+Size/2, T+Size/2, Size/2, Step+1))
54109467b48Spatrick return false;
54209467b48Spatrick }
54309467b48Spatrick return true;
54409467b48Spatrick }
54509467b48Spatrick
route(ElemType * P,RowType * T,unsigned Size,unsigned Step)54609467b48Spatrick bool BenesNetwork::route(ElemType *P, RowType *T, unsigned Size,
54709467b48Spatrick unsigned Step) {
54809467b48Spatrick Coloring G({P,Size});
54909467b48Spatrick const Coloring::MapType &M = G.colors();
55009467b48Spatrick if (M.empty())
55109467b48Spatrick return false;
55209467b48Spatrick ElemType Num = Size;
55309467b48Spatrick
55409467b48Spatrick unsigned Pets = 2*Log-1 - Step;
55509467b48Spatrick bool UseUp = false, UseDown = false;
55609467b48Spatrick
55709467b48Spatrick // Both assignments, i.e. Red->Up and Red->Down are valid, but they will
55809467b48Spatrick // result in different controls. Let's pick the one where the first
55909467b48Spatrick // control will be "Pass".
56009467b48Spatrick ColorKind ColorUp = ColorKind::None;
56109467b48Spatrick for (ElemType J = 0; J != Num; ++J) {
56209467b48Spatrick ElemType I = P[J];
56309467b48Spatrick if (I == Ignore)
56409467b48Spatrick continue;
56509467b48Spatrick ColorKind C = M.at(I);
56609467b48Spatrick if (C == ColorKind::None)
56709467b48Spatrick continue;
56809467b48Spatrick if (ColorUp == ColorKind::None) {
56909467b48Spatrick ColorUp = (I < Num / 2) ? ColorKind::Red : ColorKind::Black;
57009467b48Spatrick }
57109467b48Spatrick unsigned CI = (I < Num/2) ? I+Num/2 : I-Num/2;
57209467b48Spatrick if (C == ColorUp) {
57309467b48Spatrick if (I < Num/2)
57409467b48Spatrick T[I][Step] = Pass;
57509467b48Spatrick else
57609467b48Spatrick T[CI][Step] = Switch;
57709467b48Spatrick T[J][Pets] = (J < Num/2) ? Pass : Switch;
57809467b48Spatrick UseUp = true;
57909467b48Spatrick } else { // Down
58009467b48Spatrick if (I < Num/2)
58109467b48Spatrick T[CI][Step] = Switch;
58209467b48Spatrick else
58309467b48Spatrick T[I][Step] = Pass;
58409467b48Spatrick T[J][Pets] = (J < Num/2) ? Switch : Pass;
58509467b48Spatrick UseDown = true;
58609467b48Spatrick }
58709467b48Spatrick }
58809467b48Spatrick
58909467b48Spatrick // Reorder the working permutation according to the computed switch table
59009467b48Spatrick // for the last step (i.e. Pets).
59109467b48Spatrick for (ElemType J = 0; J != Num/2; ++J) {
59209467b48Spatrick ElemType PJ = P[J]; // Current values of P[J]
59309467b48Spatrick ElemType PC = P[J+Num/2]; // and P[conj(J)]
59409467b48Spatrick ElemType QJ = PJ; // New values of P[J]
59509467b48Spatrick ElemType QC = PC; // and P[conj(J)]
59609467b48Spatrick if (T[J][Pets] == Switch)
59709467b48Spatrick QC = PJ;
59809467b48Spatrick if (T[J+Num/2][Pets] == Switch)
59909467b48Spatrick QJ = PC;
60009467b48Spatrick P[J] = QJ;
60109467b48Spatrick P[J+Num/2] = QC;
60209467b48Spatrick }
60309467b48Spatrick
60409467b48Spatrick for (ElemType J = 0; J != Num; ++J)
60509467b48Spatrick if (P[J] != Ignore && P[J] >= Num/2)
60609467b48Spatrick P[J] -= Num/2;
60709467b48Spatrick
60809467b48Spatrick if (Step+1 < Log) {
60909467b48Spatrick if (UseUp && !route(P, T, Size/2, Step+1))
61009467b48Spatrick return false;
61109467b48Spatrick if (UseDown && !route(P+Size/2, T+Size/2, Size/2, Step+1))
61209467b48Spatrick return false;
61309467b48Spatrick }
61409467b48Spatrick return true;
61509467b48Spatrick }
61609467b48Spatrick
61709467b48Spatrick // --------------------------------------------------------------------
61809467b48Spatrick // Support for building selection results (output instructions that are
61909467b48Spatrick // parts of the final selection).
62009467b48Spatrick
62109467b48Spatrick namespace {
62209467b48Spatrick struct OpRef {
OpRef__anona824ea740711::OpRef62309467b48Spatrick OpRef(SDValue V) : OpV(V) {}
isValue__anona824ea740711::OpRef62409467b48Spatrick bool isValue() const { return OpV.getNode() != nullptr; }
isValid__anona824ea740711::OpRef62509467b48Spatrick bool isValid() const { return isValue() || !(OpN & Invalid); }
isUndef__anona824ea740711::OpRef626*d415bd75Srobert bool isUndef() const { return OpN & Undef; }
res__anona824ea740711::OpRef62709467b48Spatrick static OpRef res(int N) { return OpRef(Whole | (N & Index)); }
fail__anona824ea740711::OpRef62809467b48Spatrick static OpRef fail() { return OpRef(Invalid); }
62909467b48Spatrick
lo__anona824ea740711::OpRef63009467b48Spatrick static OpRef lo(const OpRef &R) {
63109467b48Spatrick assert(!R.isValue());
63209467b48Spatrick return OpRef(R.OpN & (Undef | Index | LoHalf));
63309467b48Spatrick }
hi__anona824ea740711::OpRef63409467b48Spatrick static OpRef hi(const OpRef &R) {
63509467b48Spatrick assert(!R.isValue());
63609467b48Spatrick return OpRef(R.OpN & (Undef | Index | HiHalf));
63709467b48Spatrick }
undef__anona824ea740711::OpRef63809467b48Spatrick static OpRef undef(MVT Ty) { return OpRef(Undef | Ty.SimpleTy); }
63909467b48Spatrick
64009467b48Spatrick // Direct value.
64109467b48Spatrick SDValue OpV = SDValue();
64209467b48Spatrick
64309467b48Spatrick // Reference to the operand of the input node:
64409467b48Spatrick // If the 31st bit is 1, it's undef, otherwise, bits 28..0 are the
64509467b48Spatrick // operand index:
64609467b48Spatrick // If bit 30 is set, it's the high half of the operand.
64709467b48Spatrick // If bit 29 is set, it's the low half of the operand.
64809467b48Spatrick unsigned OpN = 0;
64909467b48Spatrick
65009467b48Spatrick enum : unsigned {
65109467b48Spatrick Invalid = 0x10000000,
65209467b48Spatrick LoHalf = 0x20000000,
65309467b48Spatrick HiHalf = 0x40000000,
65409467b48Spatrick Whole = LoHalf | HiHalf,
65509467b48Spatrick Undef = 0x80000000,
65609467b48Spatrick Index = 0x0FFFFFFF, // Mask of the index value.
65709467b48Spatrick IndexBits = 28,
65809467b48Spatrick };
65909467b48Spatrick
66009467b48Spatrick LLVM_DUMP_METHOD
66109467b48Spatrick void print(raw_ostream &OS, const SelectionDAG &G) const;
66209467b48Spatrick
66309467b48Spatrick private:
OpRef__anona824ea740711::OpRef66409467b48Spatrick OpRef(unsigned N) : OpN(N) {}
66509467b48Spatrick };
66609467b48Spatrick
66709467b48Spatrick struct NodeTemplate {
66809467b48Spatrick NodeTemplate() = default;
66909467b48Spatrick unsigned Opc = 0;
67009467b48Spatrick MVT Ty = MVT::Other;
67109467b48Spatrick std::vector<OpRef> Ops;
67209467b48Spatrick
67309467b48Spatrick LLVM_DUMP_METHOD void print(raw_ostream &OS, const SelectionDAG &G) const;
67409467b48Spatrick };
67509467b48Spatrick
67609467b48Spatrick struct ResultStack {
ResultStack__anona824ea740711::ResultStack67709467b48Spatrick ResultStack(SDNode *Inp)
67809467b48Spatrick : InpNode(Inp), InpTy(Inp->getValueType(0).getSimpleVT()) {}
67909467b48Spatrick SDNode *InpNode;
68009467b48Spatrick MVT InpTy;
push__anona824ea740711::ResultStack68109467b48Spatrick unsigned push(const NodeTemplate &Res) {
68209467b48Spatrick List.push_back(Res);
68309467b48Spatrick return List.size()-1;
68409467b48Spatrick }
push__anona824ea740711::ResultStack68509467b48Spatrick unsigned push(unsigned Opc, MVT Ty, std::vector<OpRef> &&Ops) {
68609467b48Spatrick NodeTemplate Res;
68709467b48Spatrick Res.Opc = Opc;
68809467b48Spatrick Res.Ty = Ty;
68909467b48Spatrick Res.Ops = Ops;
69009467b48Spatrick return push(Res);
69109467b48Spatrick }
empty__anona824ea740711::ResultStack69209467b48Spatrick bool empty() const { return List.empty(); }
size__anona824ea740711::ResultStack69309467b48Spatrick unsigned size() const { return List.size(); }
top__anona824ea740711::ResultStack69409467b48Spatrick unsigned top() const { return size()-1; }
operator []__anona824ea740711::ResultStack69509467b48Spatrick const NodeTemplate &operator[](unsigned I) const { return List[I]; }
reset__anona824ea740711::ResultStack69609467b48Spatrick unsigned reset(unsigned NewTop) {
69709467b48Spatrick List.resize(NewTop+1);
69809467b48Spatrick return NewTop;
69909467b48Spatrick }
70009467b48Spatrick
70109467b48Spatrick using BaseType = std::vector<NodeTemplate>;
begin__anona824ea740711::ResultStack70209467b48Spatrick BaseType::iterator begin() { return List.begin(); }
end__anona824ea740711::ResultStack70309467b48Spatrick BaseType::iterator end() { return List.end(); }
begin__anona824ea740711::ResultStack70409467b48Spatrick BaseType::const_iterator begin() const { return List.begin(); }
end__anona824ea740711::ResultStack70509467b48Spatrick BaseType::const_iterator end() const { return List.end(); }
70609467b48Spatrick
70709467b48Spatrick BaseType List;
70809467b48Spatrick
70909467b48Spatrick LLVM_DUMP_METHOD
71009467b48Spatrick void print(raw_ostream &OS, const SelectionDAG &G) const;
71109467b48Spatrick };
71209467b48Spatrick } // namespace
71309467b48Spatrick
71409467b48Spatrick #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
print(raw_ostream & OS,const SelectionDAG & G) const71509467b48Spatrick void OpRef::print(raw_ostream &OS, const SelectionDAG &G) const {
71609467b48Spatrick if (isValue()) {
71709467b48Spatrick OpV.getNode()->print(OS, &G);
71809467b48Spatrick return;
71909467b48Spatrick }
72009467b48Spatrick if (OpN & Invalid) {
72109467b48Spatrick OS << "invalid";
72209467b48Spatrick return;
72309467b48Spatrick }
72409467b48Spatrick if (OpN & Undef) {
72509467b48Spatrick OS << "undef";
72609467b48Spatrick return;
72709467b48Spatrick }
72809467b48Spatrick if ((OpN & Whole) != Whole) {
72909467b48Spatrick assert((OpN & Whole) == LoHalf || (OpN & Whole) == HiHalf);
73009467b48Spatrick if (OpN & LoHalf)
73109467b48Spatrick OS << "lo ";
73209467b48Spatrick else
73309467b48Spatrick OS << "hi ";
73409467b48Spatrick }
73509467b48Spatrick OS << '#' << SignExtend32(OpN & Index, IndexBits);
73609467b48Spatrick }
73709467b48Spatrick
print(raw_ostream & OS,const SelectionDAG & G) const73809467b48Spatrick void NodeTemplate::print(raw_ostream &OS, const SelectionDAG &G) const {
73909467b48Spatrick const TargetInstrInfo &TII = *G.getSubtarget().getInstrInfo();
74009467b48Spatrick OS << format("%8s", EVT(Ty).getEVTString().c_str()) << " "
74109467b48Spatrick << TII.getName(Opc);
74209467b48Spatrick bool Comma = false;
74309467b48Spatrick for (const auto &R : Ops) {
74409467b48Spatrick if (Comma)
74509467b48Spatrick OS << ',';
74609467b48Spatrick Comma = true;
74709467b48Spatrick OS << ' ';
74809467b48Spatrick R.print(OS, G);
74909467b48Spatrick }
75009467b48Spatrick }
75109467b48Spatrick
print(raw_ostream & OS,const SelectionDAG & G) const75209467b48Spatrick void ResultStack::print(raw_ostream &OS, const SelectionDAG &G) const {
75309467b48Spatrick OS << "Input node:\n";
75409467b48Spatrick #ifndef NDEBUG
75509467b48Spatrick InpNode->dumpr(&G);
75609467b48Spatrick #endif
75709467b48Spatrick OS << "Result templates:\n";
75809467b48Spatrick for (unsigned I = 0, E = List.size(); I != E; ++I) {
75909467b48Spatrick OS << '[' << I << "] ";
76009467b48Spatrick List[I].print(OS, G);
76109467b48Spatrick OS << '\n';
76209467b48Spatrick }
76309467b48Spatrick }
76409467b48Spatrick #endif
76509467b48Spatrick
76609467b48Spatrick namespace {
76709467b48Spatrick struct ShuffleMask {
ShuffleMask__anona824ea740911::ShuffleMask76809467b48Spatrick ShuffleMask(ArrayRef<int> M) : Mask(M) {
769*d415bd75Srobert for (int M : Mask) {
77009467b48Spatrick if (M == -1)
77109467b48Spatrick continue;
77209467b48Spatrick MinSrc = (MinSrc == -1) ? M : std::min(MinSrc, M);
77309467b48Spatrick MaxSrc = (MaxSrc == -1) ? M : std::max(MaxSrc, M);
77409467b48Spatrick }
77509467b48Spatrick }
77609467b48Spatrick
77709467b48Spatrick ArrayRef<int> Mask;
77809467b48Spatrick int MinSrc = -1, MaxSrc = -1;
77909467b48Spatrick
lo__anona824ea740911::ShuffleMask78009467b48Spatrick ShuffleMask lo() const {
78109467b48Spatrick size_t H = Mask.size()/2;
78209467b48Spatrick return ShuffleMask(Mask.take_front(H));
78309467b48Spatrick }
hi__anona824ea740911::ShuffleMask78409467b48Spatrick ShuffleMask hi() const {
78509467b48Spatrick size_t H = Mask.size()/2;
78609467b48Spatrick return ShuffleMask(Mask.take_back(H));
78709467b48Spatrick }
78809467b48Spatrick
print__anona824ea740911::ShuffleMask78909467b48Spatrick void print(raw_ostream &OS) const {
79009467b48Spatrick OS << "MinSrc:" << MinSrc << ", MaxSrc:" << MaxSrc << " {";
79109467b48Spatrick for (int M : Mask)
79209467b48Spatrick OS << ' ' << M;
79309467b48Spatrick OS << " }";
79409467b48Spatrick }
79509467b48Spatrick };
79673471bf0Spatrick
79773471bf0Spatrick LLVM_ATTRIBUTE_UNUSED
operator <<(raw_ostream & OS,const ShuffleMask & SM)79873471bf0Spatrick raw_ostream &operator<<(raw_ostream &OS, const ShuffleMask &SM) {
79973471bf0Spatrick SM.print(OS);
80073471bf0Spatrick return OS;
80173471bf0Spatrick }
80209467b48Spatrick } // namespace
80309467b48Spatrick
804*d415bd75Srobert namespace shuffles {
805*d415bd75Srobert using MaskT = SmallVector<int, 128>;
806*d415bd75Srobert // Vdd = vshuffvdd(Vu, Vv, Rt)
807*d415bd75Srobert // Vdd = vdealvdd(Vu, Vv, Rt)
808*d415bd75Srobert // Vd = vpack(Vu, Vv, Size, TakeOdd)
809*d415bd75Srobert // Vd = vshuff(Vu, Vv, Size, TakeOdd)
810*d415bd75Srobert // Vd = vdeal(Vu, Vv, Size, TakeOdd)
811*d415bd75Srobert // Vd = vdealb4w(Vu, Vv)
812*d415bd75Srobert
lo(ArrayRef<int> Vuu)813*d415bd75Srobert ArrayRef<int> lo(ArrayRef<int> Vuu) { return Vuu.take_front(Vuu.size() / 2); }
hi(ArrayRef<int> Vuu)814*d415bd75Srobert ArrayRef<int> hi(ArrayRef<int> Vuu) { return Vuu.take_back(Vuu.size() / 2); }
815*d415bd75Srobert
vshuffvdd(ArrayRef<int> Vu,ArrayRef<int> Vv,unsigned Rt)816*d415bd75Srobert MaskT vshuffvdd(ArrayRef<int> Vu, ArrayRef<int> Vv, unsigned Rt) {
817*d415bd75Srobert int Len = Vu.size();
818*d415bd75Srobert MaskT Vdd(2 * Len);
819*d415bd75Srobert std::copy(Vv.begin(), Vv.end(), Vdd.begin());
820*d415bd75Srobert std::copy(Vu.begin(), Vu.end(), Vdd.begin() + Len);
821*d415bd75Srobert
822*d415bd75Srobert auto Vd0 = MutableArrayRef<int>(Vdd).take_front(Len);
823*d415bd75Srobert auto Vd1 = MutableArrayRef<int>(Vdd).take_back(Len);
824*d415bd75Srobert
825*d415bd75Srobert for (int Offset = 1; Offset < Len; Offset *= 2) {
826*d415bd75Srobert if ((Rt & Offset) == 0)
827*d415bd75Srobert continue;
828*d415bd75Srobert for (int i = 0; i != Len; ++i) {
829*d415bd75Srobert if ((i & Offset) == 0)
830*d415bd75Srobert std::swap(Vd1[i], Vd0[i + Offset]);
831*d415bd75Srobert }
832*d415bd75Srobert }
833*d415bd75Srobert return Vdd;
834*d415bd75Srobert }
835*d415bd75Srobert
vdealvdd(ArrayRef<int> Vu,ArrayRef<int> Vv,unsigned Rt)836*d415bd75Srobert MaskT vdealvdd(ArrayRef<int> Vu, ArrayRef<int> Vv, unsigned Rt) {
837*d415bd75Srobert int Len = Vu.size();
838*d415bd75Srobert MaskT Vdd(2 * Len);
839*d415bd75Srobert std::copy(Vv.begin(), Vv.end(), Vdd.begin());
840*d415bd75Srobert std::copy(Vu.begin(), Vu.end(), Vdd.begin() + Len);
841*d415bd75Srobert
842*d415bd75Srobert auto Vd0 = MutableArrayRef<int>(Vdd).take_front(Len);
843*d415bd75Srobert auto Vd1 = MutableArrayRef<int>(Vdd).take_back(Len);
844*d415bd75Srobert
845*d415bd75Srobert for (int Offset = Len / 2; Offset > 0; Offset /= 2) {
846*d415bd75Srobert if ((Rt & Offset) == 0)
847*d415bd75Srobert continue;
848*d415bd75Srobert for (int i = 0; i != Len; ++i) {
849*d415bd75Srobert if ((i & Offset) == 0)
850*d415bd75Srobert std::swap(Vd1[i], Vd0[i + Offset]);
851*d415bd75Srobert }
852*d415bd75Srobert }
853*d415bd75Srobert return Vdd;
854*d415bd75Srobert }
855*d415bd75Srobert
vpack(ArrayRef<int> Vu,ArrayRef<int> Vv,unsigned Size,bool TakeOdd)856*d415bd75Srobert MaskT vpack(ArrayRef<int> Vu, ArrayRef<int> Vv, unsigned Size, bool TakeOdd) {
857*d415bd75Srobert int Len = Vu.size();
858*d415bd75Srobert MaskT Vd(Len);
859*d415bd75Srobert auto Odd = static_cast<int>(TakeOdd);
860*d415bd75Srobert for (int i = 0, e = Len / (2 * Size); i != e; ++i) {
861*d415bd75Srobert for (int b = 0; b != static_cast<int>(Size); ++b) {
862*d415bd75Srobert // clang-format off
863*d415bd75Srobert Vd[i * Size + b] = Vv[(2 * i + Odd) * Size + b];
864*d415bd75Srobert Vd[i * Size + b + Len / 2] = Vu[(2 * i + Odd) * Size + b];
865*d415bd75Srobert // clang-format on
866*d415bd75Srobert }
867*d415bd75Srobert }
868*d415bd75Srobert return Vd;
869*d415bd75Srobert }
870*d415bd75Srobert
vshuff(ArrayRef<int> Vu,ArrayRef<int> Vv,unsigned Size,bool TakeOdd)871*d415bd75Srobert MaskT vshuff(ArrayRef<int> Vu, ArrayRef<int> Vv, unsigned Size, bool TakeOdd) {
872*d415bd75Srobert int Len = Vu.size();
873*d415bd75Srobert MaskT Vd(Len);
874*d415bd75Srobert auto Odd = static_cast<int>(TakeOdd);
875*d415bd75Srobert for (int i = 0, e = Len / (2 * Size); i != e; ++i) {
876*d415bd75Srobert for (int b = 0; b != static_cast<int>(Size); ++b) {
877*d415bd75Srobert Vd[(2 * i + 0) * Size + b] = Vv[(2 * i + Odd) * Size + b];
878*d415bd75Srobert Vd[(2 * i + 1) * Size + b] = Vu[(2 * i + Odd) * Size + b];
879*d415bd75Srobert }
880*d415bd75Srobert }
881*d415bd75Srobert return Vd;
882*d415bd75Srobert }
883*d415bd75Srobert
vdeal(ArrayRef<int> Vu,ArrayRef<int> Vv,unsigned Size,bool TakeOdd)884*d415bd75Srobert MaskT vdeal(ArrayRef<int> Vu, ArrayRef<int> Vv, unsigned Size, bool TakeOdd) {
885*d415bd75Srobert int Len = Vu.size();
886*d415bd75Srobert MaskT T = vdealvdd(Vu, Vv, Len - 2 * Size);
887*d415bd75Srobert return vpack(hi(T), lo(T), Size, TakeOdd);
888*d415bd75Srobert }
889*d415bd75Srobert
vdealb4w(ArrayRef<int> Vu,ArrayRef<int> Vv)890*d415bd75Srobert MaskT vdealb4w(ArrayRef<int> Vu, ArrayRef<int> Vv) {
891*d415bd75Srobert int Len = Vu.size();
892*d415bd75Srobert MaskT Vd(Len);
893*d415bd75Srobert for (int i = 0, e = Len / 4; i != e; ++i) {
894*d415bd75Srobert Vd[0 * (Len / 4) + i] = Vv[4 * i + 0];
895*d415bd75Srobert Vd[1 * (Len / 4) + i] = Vv[4 * i + 2];
896*d415bd75Srobert Vd[2 * (Len / 4) + i] = Vu[4 * i + 0];
897*d415bd75Srobert Vd[3 * (Len / 4) + i] = Vu[4 * i + 2];
898*d415bd75Srobert }
899*d415bd75Srobert return Vd;
900*d415bd75Srobert }
901*d415bd75Srobert
902*d415bd75Srobert template <typename ShuffFunc, typename... OptArgs>
mask(ShuffFunc S,unsigned Length,OptArgs...args)903*d415bd75Srobert auto mask(ShuffFunc S, unsigned Length, OptArgs... args) -> MaskT {
904*d415bd75Srobert MaskT Vu(Length), Vv(Length);
905*d415bd75Srobert std::iota(Vu.begin(), Vu.end(), Length); // High
906*d415bd75Srobert std::iota(Vv.begin(), Vv.end(), 0); // Low
907*d415bd75Srobert return S(Vu, Vv, args...);
908*d415bd75Srobert }
909*d415bd75Srobert
910*d415bd75Srobert } // namespace shuffles
911*d415bd75Srobert
91209467b48Spatrick // --------------------------------------------------------------------
91309467b48Spatrick // The HvxSelector class.
91409467b48Spatrick
getHexagonLowering(SelectionDAG & G)91509467b48Spatrick static const HexagonTargetLowering &getHexagonLowering(SelectionDAG &G) {
91609467b48Spatrick return static_cast<const HexagonTargetLowering&>(G.getTargetLoweringInfo());
91709467b48Spatrick }
getHexagonSubtarget(SelectionDAG & G)91809467b48Spatrick static const HexagonSubtarget &getHexagonSubtarget(SelectionDAG &G) {
919*d415bd75Srobert return G.getSubtarget<HexagonSubtarget>();
92009467b48Spatrick }
92109467b48Spatrick
92209467b48Spatrick namespace llvm {
92309467b48Spatrick struct HvxSelector {
92409467b48Spatrick const HexagonTargetLowering &Lower;
92509467b48Spatrick HexagonDAGToDAGISel &ISel;
92609467b48Spatrick SelectionDAG &DAG;
92709467b48Spatrick const HexagonSubtarget &HST;
92809467b48Spatrick const unsigned HwLen;
92909467b48Spatrick
HvxSelectorllvm::HvxSelector93009467b48Spatrick HvxSelector(HexagonDAGToDAGISel &HS, SelectionDAG &G)
93109467b48Spatrick : Lower(getHexagonLowering(G)), ISel(HS), DAG(G),
93209467b48Spatrick HST(getHexagonSubtarget(G)), HwLen(HST.getVectorLength()) {}
93309467b48Spatrick
getSingleVTllvm::HvxSelector93409467b48Spatrick MVT getSingleVT(MVT ElemTy) const {
93573471bf0Spatrick assert(ElemTy != MVT::i1 && "Use getBoolVT for predicates");
93609467b48Spatrick unsigned NumElems = HwLen / (ElemTy.getSizeInBits() / 8);
93709467b48Spatrick return MVT::getVectorVT(ElemTy, NumElems);
93809467b48Spatrick }
93909467b48Spatrick
getPairVTllvm::HvxSelector94009467b48Spatrick MVT getPairVT(MVT ElemTy) const {
94173471bf0Spatrick assert(ElemTy != MVT::i1); // Suspicious: there are no predicate pairs.
94209467b48Spatrick unsigned NumElems = (2 * HwLen) / (ElemTy.getSizeInBits() / 8);
94309467b48Spatrick return MVT::getVectorVT(ElemTy, NumElems);
94409467b48Spatrick }
94509467b48Spatrick
getBoolVTllvm::HvxSelector94673471bf0Spatrick MVT getBoolVT() const {
94773471bf0Spatrick // Return HwLen x i1.
94873471bf0Spatrick return MVT::getVectorVT(MVT::i1, HwLen);
94973471bf0Spatrick }
95073471bf0Spatrick
951*d415bd75Srobert void selectExtractSubvector(SDNode *N);
95209467b48Spatrick void selectShuffle(SDNode *N);
95309467b48Spatrick void selectRor(SDNode *N);
95409467b48Spatrick void selectVAlign(SDNode *N);
95509467b48Spatrick
956*d415bd75Srobert static SmallVector<uint32_t, 8> getPerfectCompletions(ShuffleMask SM,
957*d415bd75Srobert unsigned Width);
958*d415bd75Srobert static SmallVector<uint32_t, 8> completeToPerfect(
959*d415bd75Srobert ArrayRef<uint32_t> Completions, unsigned Width);
960*d415bd75Srobert static std::optional<int> rotationDistance(ShuffleMask SM, unsigned WrapAt);
961*d415bd75Srobert
96209467b48Spatrick private:
96373471bf0Spatrick void select(SDNode *ISelN);
96409467b48Spatrick void materialize(const ResultStack &Results);
96509467b48Spatrick
96673471bf0Spatrick SDValue getConst32(int Val, const SDLoc &dl);
96709467b48Spatrick SDValue getVectorConstant(ArrayRef<uint8_t> Data, const SDLoc &dl);
96809467b48Spatrick
96909467b48Spatrick enum : unsigned {
97009467b48Spatrick None,
97109467b48Spatrick PackMux,
97209467b48Spatrick };
97373471bf0Spatrick OpRef concats(OpRef Va, OpRef Vb, ResultStack &Results);
974*d415bd75Srobert OpRef funnels(OpRef Va, OpRef Vb, int Amount, ResultStack &Results);
975*d415bd75Srobert
97609467b48Spatrick OpRef packs(ShuffleMask SM, OpRef Va, OpRef Vb, ResultStack &Results,
97709467b48Spatrick MutableArrayRef<int> NewMask, unsigned Options = None);
97809467b48Spatrick OpRef packp(ShuffleMask SM, OpRef Va, OpRef Vb, ResultStack &Results,
97909467b48Spatrick MutableArrayRef<int> NewMask);
98009467b48Spatrick OpRef vmuxs(ArrayRef<uint8_t> Bytes, OpRef Va, OpRef Vb,
98109467b48Spatrick ResultStack &Results);
98209467b48Spatrick OpRef vmuxp(ArrayRef<uint8_t> Bytes, OpRef Va, OpRef Vb,
98309467b48Spatrick ResultStack &Results);
98409467b48Spatrick
98509467b48Spatrick OpRef shuffs1(ShuffleMask SM, OpRef Va, ResultStack &Results);
98609467b48Spatrick OpRef shuffs2(ShuffleMask SM, OpRef Va, OpRef Vb, ResultStack &Results);
98709467b48Spatrick OpRef shuffp1(ShuffleMask SM, OpRef Va, ResultStack &Results);
98809467b48Spatrick OpRef shuffp2(ShuffleMask SM, OpRef Va, OpRef Vb, ResultStack &Results);
98909467b48Spatrick
99009467b48Spatrick OpRef butterfly(ShuffleMask SM, OpRef Va, ResultStack &Results);
99109467b48Spatrick OpRef contracting(ShuffleMask SM, OpRef Va, OpRef Vb, ResultStack &Results);
99209467b48Spatrick OpRef expanding(ShuffleMask SM, OpRef Va, ResultStack &Results);
99309467b48Spatrick OpRef perfect(ShuffleMask SM, OpRef Va, ResultStack &Results);
99409467b48Spatrick
99509467b48Spatrick bool selectVectorConstants(SDNode *N);
99609467b48Spatrick bool scalarizeShuffle(ArrayRef<int> Mask, const SDLoc &dl, MVT ResTy,
99709467b48Spatrick SDValue Va, SDValue Vb, SDNode *N);
99809467b48Spatrick };
999*d415bd75Srobert } // namespace llvm
100009467b48Spatrick
splitMask(ArrayRef<int> Mask,MutableArrayRef<int> MaskL,MutableArrayRef<int> MaskR)100109467b48Spatrick static void splitMask(ArrayRef<int> Mask, MutableArrayRef<int> MaskL,
100209467b48Spatrick MutableArrayRef<int> MaskR) {
100309467b48Spatrick unsigned VecLen = Mask.size();
100409467b48Spatrick assert(MaskL.size() == VecLen && MaskR.size() == VecLen);
100509467b48Spatrick for (unsigned I = 0; I != VecLen; ++I) {
100609467b48Spatrick int M = Mask[I];
100709467b48Spatrick if (M < 0) {
100809467b48Spatrick MaskL[I] = MaskR[I] = -1;
100909467b48Spatrick } else if (unsigned(M) < VecLen) {
101009467b48Spatrick MaskL[I] = M;
101109467b48Spatrick MaskR[I] = -1;
101209467b48Spatrick } else {
101309467b48Spatrick MaskL[I] = -1;
101409467b48Spatrick MaskR[I] = M-VecLen;
101509467b48Spatrick }
101609467b48Spatrick }
101709467b48Spatrick }
101809467b48Spatrick
findStrip(ArrayRef<int> A,int Inc,unsigned MaxLen)101909467b48Spatrick static std::pair<int,unsigned> findStrip(ArrayRef<int> A, int Inc,
102009467b48Spatrick unsigned MaxLen) {
102109467b48Spatrick assert(A.size() > 0 && A.size() >= MaxLen);
102209467b48Spatrick int F = A[0];
102309467b48Spatrick int E = F;
102409467b48Spatrick for (unsigned I = 1; I != MaxLen; ++I) {
102509467b48Spatrick if (A[I] - E != Inc)
102609467b48Spatrick return { F, I };
102709467b48Spatrick E = A[I];
102809467b48Spatrick }
102909467b48Spatrick return { F, MaxLen };
103009467b48Spatrick }
103109467b48Spatrick
isUndef(ArrayRef<int> Mask)103209467b48Spatrick static bool isUndef(ArrayRef<int> Mask) {
103309467b48Spatrick for (int Idx : Mask)
103409467b48Spatrick if (Idx != -1)
103509467b48Spatrick return false;
103609467b48Spatrick return true;
103709467b48Spatrick }
103809467b48Spatrick
isIdentity(ArrayRef<int> Mask)103909467b48Spatrick static bool isIdentity(ArrayRef<int> Mask) {
104009467b48Spatrick for (int I = 0, E = Mask.size(); I != E; ++I) {
104109467b48Spatrick int M = Mask[I];
104209467b48Spatrick if (M >= 0 && M != I)
104309467b48Spatrick return false;
104409467b48Spatrick }
104509467b48Spatrick return true;
104609467b48Spatrick }
104709467b48Spatrick
isLowHalfOnly(ArrayRef<int> Mask)1048*d415bd75Srobert static bool isLowHalfOnly(ArrayRef<int> Mask) {
1049*d415bd75Srobert int L = Mask.size();
1050*d415bd75Srobert assert(L % 2 == 0);
1051*d415bd75Srobert // Check if the second half of the mask is all-undef.
1052*d415bd75Srobert return llvm::all_of(Mask.drop_front(L / 2), [](int M) { return M < 0; });
1053*d415bd75Srobert }
1054*d415bd75Srobert
getInputSegmentList(ShuffleMask SM,unsigned SegLen)105573471bf0Spatrick static SmallVector<unsigned, 4> getInputSegmentList(ShuffleMask SM,
105673471bf0Spatrick unsigned SegLen) {
105773471bf0Spatrick assert(isPowerOf2_32(SegLen));
105873471bf0Spatrick SmallVector<unsigned, 4> SegList;
105973471bf0Spatrick if (SM.MaxSrc == -1)
106073471bf0Spatrick return SegList;
106173471bf0Spatrick
106273471bf0Spatrick unsigned Shift = Log2_32(SegLen);
106373471bf0Spatrick BitVector Segs(alignTo(SM.MaxSrc + 1, SegLen) >> Shift);
106473471bf0Spatrick
1065*d415bd75Srobert for (int M : SM.Mask) {
106673471bf0Spatrick if (M >= 0)
106773471bf0Spatrick Segs.set(M >> Shift);
106873471bf0Spatrick }
106973471bf0Spatrick
107073471bf0Spatrick for (unsigned B : Segs.set_bits())
107173471bf0Spatrick SegList.push_back(B);
107273471bf0Spatrick return SegList;
107373471bf0Spatrick }
107473471bf0Spatrick
getOutputSegmentMap(ShuffleMask SM,unsigned SegLen)107573471bf0Spatrick static SmallVector<unsigned, 4> getOutputSegmentMap(ShuffleMask SM,
107673471bf0Spatrick unsigned SegLen) {
107773471bf0Spatrick // Calculate the layout of the output segments in terms of the input
107873471bf0Spatrick // segments.
107973471bf0Spatrick // For example [1,3,1,0] means that the output consists of 4 output
108073471bf0Spatrick // segments, where the first output segment has only elements of the
108173471bf0Spatrick // input segment at index 1. The next output segment only has elements
108273471bf0Spatrick // of the input segment 3, etc.
108373471bf0Spatrick // If an output segment only has undef elements, the value will be ~0u.
108473471bf0Spatrick // If an output segment has elements from more than one input segment,
108573471bf0Spatrick // the corresponding value will be ~1u.
108673471bf0Spatrick unsigned MaskLen = SM.Mask.size();
108773471bf0Spatrick assert(MaskLen % SegLen == 0);
108873471bf0Spatrick SmallVector<unsigned, 4> Map(MaskLen / SegLen);
108973471bf0Spatrick
109073471bf0Spatrick for (int S = 0, E = Map.size(); S != E; ++S) {
109173471bf0Spatrick unsigned Idx = ~0u;
109273471bf0Spatrick for (int I = 0; I != static_cast<int>(SegLen); ++I) {
109373471bf0Spatrick int M = SM.Mask[S*SegLen + I];
109473471bf0Spatrick if (M < 0)
109573471bf0Spatrick continue;
109673471bf0Spatrick unsigned G = M / SegLen; // Input segment of this element.
109773471bf0Spatrick if (Idx == ~0u) {
109873471bf0Spatrick Idx = G;
109973471bf0Spatrick } else if (Idx != G) {
110073471bf0Spatrick Idx = ~1u;
110173471bf0Spatrick break;
110273471bf0Spatrick }
110373471bf0Spatrick }
110473471bf0Spatrick Map[S] = Idx;
110573471bf0Spatrick }
110673471bf0Spatrick
110773471bf0Spatrick return Map;
110873471bf0Spatrick }
110973471bf0Spatrick
packSegmentMask(ArrayRef<int> Mask,ArrayRef<unsigned> OutSegMap,unsigned SegLen,MutableArrayRef<int> PackedMask)111073471bf0Spatrick static void packSegmentMask(ArrayRef<int> Mask, ArrayRef<unsigned> OutSegMap,
111173471bf0Spatrick unsigned SegLen, MutableArrayRef<int> PackedMask) {
111273471bf0Spatrick SmallVector<unsigned, 4> InvMap;
111373471bf0Spatrick for (int I = OutSegMap.size() - 1; I >= 0; --I) {
111473471bf0Spatrick unsigned S = OutSegMap[I];
111573471bf0Spatrick assert(S != ~0u && "Unexpected undef");
111673471bf0Spatrick assert(S != ~1u && "Unexpected multi");
111773471bf0Spatrick if (InvMap.size() <= S)
111873471bf0Spatrick InvMap.resize(S+1);
111973471bf0Spatrick InvMap[S] = I;
112073471bf0Spatrick }
112173471bf0Spatrick
112273471bf0Spatrick unsigned Shift = Log2_32(SegLen);
112373471bf0Spatrick for (int I = 0, E = Mask.size(); I != E; ++I) {
112473471bf0Spatrick int M = Mask[I];
112573471bf0Spatrick if (M >= 0) {
112673471bf0Spatrick int OutIdx = InvMap[M >> Shift];
112773471bf0Spatrick M = (M & (SegLen-1)) + SegLen*OutIdx;
112873471bf0Spatrick }
112973471bf0Spatrick PackedMask[I] = M;
113073471bf0Spatrick }
113173471bf0Spatrick }
113273471bf0Spatrick
selectVectorConstants(SDNode * N)113309467b48Spatrick bool HvxSelector::selectVectorConstants(SDNode *N) {
113409467b48Spatrick // Constant vectors are generated as loads from constant pools or as
113509467b48Spatrick // splats of a constant value. Since they are generated during the
113609467b48Spatrick // selection process, the main selection algorithm is not aware of them.
113709467b48Spatrick // Select them directly here.
113809467b48Spatrick SmallVector<SDNode*,4> Nodes;
113909467b48Spatrick SetVector<SDNode*> WorkQ;
114009467b48Spatrick
114109467b48Spatrick // The DAG can change (due to CSE) during selection, so cache all the
114209467b48Spatrick // unselected nodes first to avoid traversing a mutating DAG.
114309467b48Spatrick WorkQ.insert(N);
114409467b48Spatrick for (unsigned i = 0; i != WorkQ.size(); ++i) {
114509467b48Spatrick SDNode *W = WorkQ[i];
114673471bf0Spatrick if (!W->isMachineOpcode() && W->getOpcode() == HexagonISD::ISEL)
114709467b48Spatrick Nodes.push_back(W);
114809467b48Spatrick for (unsigned j = 0, f = W->getNumOperands(); j != f; ++j)
114909467b48Spatrick WorkQ.insert(W->getOperand(j).getNode());
115009467b48Spatrick }
115109467b48Spatrick
115209467b48Spatrick for (SDNode *L : Nodes)
115373471bf0Spatrick select(L);
115409467b48Spatrick
115509467b48Spatrick return !Nodes.empty();
115609467b48Spatrick }
115709467b48Spatrick
materialize(const ResultStack & Results)115809467b48Spatrick void HvxSelector::materialize(const ResultStack &Results) {
115909467b48Spatrick DEBUG_WITH_TYPE("isel", {
116009467b48Spatrick dbgs() << "Materializing\n";
116109467b48Spatrick Results.print(dbgs(), DAG);
116209467b48Spatrick });
116309467b48Spatrick if (Results.empty())
116409467b48Spatrick return;
116509467b48Spatrick const SDLoc &dl(Results.InpNode);
116609467b48Spatrick std::vector<SDValue> Output;
116709467b48Spatrick
116809467b48Spatrick for (unsigned I = 0, E = Results.size(); I != E; ++I) {
116909467b48Spatrick const NodeTemplate &Node = Results[I];
117009467b48Spatrick std::vector<SDValue> Ops;
117109467b48Spatrick for (const OpRef &R : Node.Ops) {
117209467b48Spatrick assert(R.isValid());
117309467b48Spatrick if (R.isValue()) {
117409467b48Spatrick Ops.push_back(R.OpV);
117509467b48Spatrick continue;
117609467b48Spatrick }
117709467b48Spatrick if (R.OpN & OpRef::Undef) {
117809467b48Spatrick MVT::SimpleValueType SVT = MVT::SimpleValueType(R.OpN & OpRef::Index);
117909467b48Spatrick Ops.push_back(ISel.selectUndef(dl, MVT(SVT)));
118009467b48Spatrick continue;
118109467b48Spatrick }
118209467b48Spatrick // R is an index of a result.
118309467b48Spatrick unsigned Part = R.OpN & OpRef::Whole;
118409467b48Spatrick int Idx = SignExtend32(R.OpN & OpRef::Index, OpRef::IndexBits);
118509467b48Spatrick if (Idx < 0)
118609467b48Spatrick Idx += I;
118709467b48Spatrick assert(Idx >= 0 && unsigned(Idx) < Output.size());
118809467b48Spatrick SDValue Op = Output[Idx];
118909467b48Spatrick MVT OpTy = Op.getValueType().getSimpleVT();
119009467b48Spatrick if (Part != OpRef::Whole) {
119109467b48Spatrick assert(Part == OpRef::LoHalf || Part == OpRef::HiHalf);
119209467b48Spatrick MVT HalfTy = MVT::getVectorVT(OpTy.getVectorElementType(),
119309467b48Spatrick OpTy.getVectorNumElements()/2);
119409467b48Spatrick unsigned Sub = (Part == OpRef::LoHalf) ? Hexagon::vsub_lo
119509467b48Spatrick : Hexagon::vsub_hi;
119609467b48Spatrick Op = DAG.getTargetExtractSubreg(Sub, dl, HalfTy, Op);
119709467b48Spatrick }
119809467b48Spatrick Ops.push_back(Op);
119909467b48Spatrick } // for (Node : Results)
120009467b48Spatrick
120109467b48Spatrick assert(Node.Ty != MVT::Other);
120209467b48Spatrick SDNode *ResN = (Node.Opc == TargetOpcode::COPY)
120309467b48Spatrick ? Ops.front().getNode()
120409467b48Spatrick : DAG.getMachineNode(Node.Opc, dl, Node.Ty, Ops);
120509467b48Spatrick Output.push_back(SDValue(ResN, 0));
120609467b48Spatrick }
120709467b48Spatrick
120809467b48Spatrick SDNode *OutN = Output.back().getNode();
120909467b48Spatrick SDNode *InpN = Results.InpNode;
121009467b48Spatrick DEBUG_WITH_TYPE("isel", {
121109467b48Spatrick dbgs() << "Generated node:\n";
121209467b48Spatrick OutN->dumpr(&DAG);
121309467b48Spatrick });
121409467b48Spatrick
121509467b48Spatrick ISel.ReplaceNode(InpN, OutN);
121609467b48Spatrick selectVectorConstants(OutN);
121709467b48Spatrick DAG.RemoveDeadNodes();
121809467b48Spatrick }
121909467b48Spatrick
concats(OpRef Lo,OpRef Hi,ResultStack & Results)122073471bf0Spatrick OpRef HvxSelector::concats(OpRef Lo, OpRef Hi, ResultStack &Results) {
122109467b48Spatrick DEBUG_WITH_TYPE("isel", {dbgs() << __func__ << '\n';});
122209467b48Spatrick const SDLoc &dl(Results.InpNode);
122309467b48Spatrick Results.push(TargetOpcode::REG_SEQUENCE, getPairVT(MVT::i8), {
122473471bf0Spatrick getConst32(Hexagon::HvxWRRegClassID, dl),
122573471bf0Spatrick Lo, getConst32(Hexagon::vsub_lo, dl),
122673471bf0Spatrick Hi, getConst32(Hexagon::vsub_hi, dl),
122709467b48Spatrick });
122809467b48Spatrick return OpRef::res(Results.top());
122909467b48Spatrick }
123009467b48Spatrick
funnels(OpRef Va,OpRef Vb,int Amount,ResultStack & Results)1231*d415bd75Srobert OpRef HvxSelector::funnels(OpRef Va, OpRef Vb, int Amount,
1232*d415bd75Srobert ResultStack &Results) {
1233*d415bd75Srobert // Do a funnel shift towards the low end (shift right) by Amount bytes.
1234*d415bd75Srobert // If Amount < 0, treat it as shift left, i.e. do a shift right by
1235*d415bd75Srobert // Amount + HwLen.
1236*d415bd75Srobert auto VecLen = static_cast<int>(HwLen);
1237*d415bd75Srobert
1238*d415bd75Srobert if (Amount == 0)
1239*d415bd75Srobert return Va;
1240*d415bd75Srobert if (Amount == VecLen)
1241*d415bd75Srobert return Vb;
1242*d415bd75Srobert
1243*d415bd75Srobert MVT Ty = getSingleVT(MVT::i8);
1244*d415bd75Srobert const SDLoc &dl(Results.InpNode);
1245*d415bd75Srobert
1246*d415bd75Srobert if (Amount < 0)
1247*d415bd75Srobert Amount += VecLen;
1248*d415bd75Srobert if (Amount > VecLen) {
1249*d415bd75Srobert Amount -= VecLen;
1250*d415bd75Srobert std::swap(Va, Vb);
1251*d415bd75Srobert }
1252*d415bd75Srobert
1253*d415bd75Srobert if (isUInt<3>(Amount)) {
1254*d415bd75Srobert SDValue A = getConst32(Amount, dl);
1255*d415bd75Srobert Results.push(Hexagon::V6_valignbi, Ty, {Vb, Va, A});
1256*d415bd75Srobert } else if (isUInt<3>(VecLen - Amount)) {
1257*d415bd75Srobert SDValue A = getConst32(VecLen - Amount, dl);
1258*d415bd75Srobert Results.push(Hexagon::V6_vlalignbi, Ty, {Vb, Va, A});
1259*d415bd75Srobert } else {
1260*d415bd75Srobert SDValue A = getConst32(Amount, dl);
1261*d415bd75Srobert Results.push(Hexagon::A2_tfrsi, Ty, {A});
1262*d415bd75Srobert Results.push(Hexagon::V6_valignb, Ty, {Vb, Va, OpRef::res(-1)});
1263*d415bd75Srobert }
1264*d415bd75Srobert return OpRef::res(Results.top());
1265*d415bd75Srobert }
1266*d415bd75Srobert
126773471bf0Spatrick // Va, Vb are single vectors. If SM only uses two vector halves from Va/Vb,
126873471bf0Spatrick // pack these halves into a single vector, and remap SM into NewMask to use
126973471bf0Spatrick // the new vector instead.
packs(ShuffleMask SM,OpRef Va,OpRef Vb,ResultStack & Results,MutableArrayRef<int> NewMask,unsigned Options)127009467b48Spatrick OpRef HvxSelector::packs(ShuffleMask SM, OpRef Va, OpRef Vb,
127109467b48Spatrick ResultStack &Results, MutableArrayRef<int> NewMask,
127209467b48Spatrick unsigned Options) {
127309467b48Spatrick DEBUG_WITH_TYPE("isel", {dbgs() << __func__ << '\n';});
127409467b48Spatrick if (!Va.isValid() || !Vb.isValid())
127509467b48Spatrick return OpRef::fail();
127609467b48Spatrick
1277*d415bd75Srobert if (Vb.isUndef()) {
1278*d415bd75Srobert std::copy(SM.Mask.begin(), SM.Mask.end(), NewMask.begin());
1279*d415bd75Srobert return Va;
1280*d415bd75Srobert }
1281*d415bd75Srobert if (Va.isUndef()) {
1282*d415bd75Srobert std::copy(SM.Mask.begin(), SM.Mask.end(), NewMask.begin());
1283*d415bd75Srobert ShuffleVectorSDNode::commuteMask(NewMask);
1284*d415bd75Srobert return Vb;
1285*d415bd75Srobert }
1286*d415bd75Srobert
128709467b48Spatrick MVT Ty = getSingleVT(MVT::i8);
128873471bf0Spatrick MVT PairTy = getPairVT(MVT::i8);
128973471bf0Spatrick OpRef Inp[2] = {Va, Vb};
129073471bf0Spatrick unsigned VecLen = SM.Mask.size();
129109467b48Spatrick
129273471bf0Spatrick auto valign = [this](OpRef Lo, OpRef Hi, unsigned Amt, MVT Ty,
129373471bf0Spatrick ResultStack &Results) {
129473471bf0Spatrick if (Amt == 0)
129573471bf0Spatrick return Lo;
129609467b48Spatrick const SDLoc &dl(Results.InpNode);
129773471bf0Spatrick if (isUInt<3>(Amt) || isUInt<3>(HwLen - Amt)) {
129873471bf0Spatrick bool IsRight = isUInt<3>(Amt); // Right align.
129973471bf0Spatrick SDValue S = getConst32(IsRight ? Amt : HwLen - Amt, dl);
130073471bf0Spatrick unsigned Opc = IsRight ? Hexagon::V6_valignbi : Hexagon::V6_vlalignbi;
130173471bf0Spatrick Results.push(Opc, Ty, {Hi, Lo, S});
130209467b48Spatrick return OpRef::res(Results.top());
130309467b48Spatrick }
130473471bf0Spatrick Results.push(Hexagon::A2_tfrsi, MVT::i32, {getConst32(Amt, dl)});
130573471bf0Spatrick OpRef A = OpRef::res(Results.top());
130673471bf0Spatrick Results.push(Hexagon::V6_valignb, Ty, {Hi, Lo, A});
130773471bf0Spatrick return OpRef::res(Results.top());
130873471bf0Spatrick };
130973471bf0Spatrick
131073471bf0Spatrick // Segment is a vector half.
131173471bf0Spatrick unsigned SegLen = HwLen / 2;
131273471bf0Spatrick
131373471bf0Spatrick // Check if we can shuffle vector halves around to get the used elements
131473471bf0Spatrick // into a single vector.
1315*d415bd75Srobert shuffles::MaskT MaskH(SM.Mask);
131673471bf0Spatrick SmallVector<unsigned, 4> SegList = getInputSegmentList(SM.Mask, SegLen);
131773471bf0Spatrick unsigned SegCount = SegList.size();
131873471bf0Spatrick SmallVector<unsigned, 4> SegMap = getOutputSegmentMap(SM.Mask, SegLen);
131973471bf0Spatrick
132073471bf0Spatrick if (SegList.empty())
132173471bf0Spatrick return OpRef::undef(Ty);
132273471bf0Spatrick
132373471bf0Spatrick // NOTE:
132473471bf0Spatrick // In the following part of the function, where the segments are rearranged,
132573471bf0Spatrick // the shuffle mask SM can be of any length that is a multiple of a vector
132673471bf0Spatrick // (i.e. a multiple of 2*SegLen), and non-zero.
132773471bf0Spatrick // The output segment map is computed, and it may have any even number of
132873471bf0Spatrick // entries, but the rearrangement of input segments will be done based only
132973471bf0Spatrick // on the first two (non-undef) entries in the segment map.
133073471bf0Spatrick // For example, if the output map is 3, 1, 1, 3 (it can have at most two
133173471bf0Spatrick // distinct entries!), the segments 1 and 3 of Va/Vb will be packaged into
133273471bf0Spatrick // a single vector V = 3:1. The output mask will then be updated to use
133373471bf0Spatrick // seg(0,V), seg(1,V), seg(1,V), seg(0,V).
133473471bf0Spatrick //
133573471bf0Spatrick // Picking the segments based on the output map is an optimization. For
133673471bf0Spatrick // correctness it is only necessary that Seg0 and Seg1 are the two input
133773471bf0Spatrick // segments that are used in the output.
133873471bf0Spatrick
133973471bf0Spatrick unsigned Seg0 = ~0u, Seg1 = ~0u;
134073471bf0Spatrick for (int I = 0, E = SegMap.size(); I != E; ++I) {
134173471bf0Spatrick unsigned X = SegMap[I];
134273471bf0Spatrick if (X == ~0u)
134373471bf0Spatrick continue;
134473471bf0Spatrick if (Seg0 == ~0u)
134573471bf0Spatrick Seg0 = X;
134673471bf0Spatrick else if (Seg1 != ~0u)
134773471bf0Spatrick break;
134873471bf0Spatrick if (X == ~1u || X != Seg0)
134973471bf0Spatrick Seg1 = X;
135073471bf0Spatrick }
135173471bf0Spatrick
135273471bf0Spatrick if (SegCount == 1) {
135373471bf0Spatrick unsigned SrcOp = SegList[0] / 2;
135473471bf0Spatrick for (int I = 0; I != static_cast<int>(VecLen); ++I) {
135573471bf0Spatrick int M = SM.Mask[I];
135673471bf0Spatrick if (M >= 0) {
135773471bf0Spatrick M -= SrcOp * HwLen;
135873471bf0Spatrick assert(M >= 0);
135973471bf0Spatrick }
136073471bf0Spatrick NewMask[I] = M;
136173471bf0Spatrick }
136273471bf0Spatrick return Inp[SrcOp];
136373471bf0Spatrick }
136473471bf0Spatrick
136573471bf0Spatrick if (SegCount == 2) {
136673471bf0Spatrick // Seg0 should not be undef here: this would imply a SegList
136773471bf0Spatrick // with <= 1 elements, which was checked earlier.
136873471bf0Spatrick assert(Seg0 != ~0u);
136973471bf0Spatrick
137073471bf0Spatrick // If Seg0 or Seg1 are "multi-defined", pick them from the input
137173471bf0Spatrick // segment list instead.
137273471bf0Spatrick if (Seg0 == ~1u || Seg1 == ~1u) {
137373471bf0Spatrick if (Seg0 == Seg1) {
137473471bf0Spatrick Seg0 = SegList[0];
137573471bf0Spatrick Seg1 = SegList[1];
137673471bf0Spatrick } else if (Seg0 == ~1u) {
137773471bf0Spatrick Seg0 = SegList[0] != Seg1 ? SegList[0] : SegList[1];
137873471bf0Spatrick } else {
1379*d415bd75Srobert assert(Seg1 == ~1u);
138073471bf0Spatrick Seg1 = SegList[0] != Seg0 ? SegList[0] : SegList[1];
138173471bf0Spatrick }
138273471bf0Spatrick }
138373471bf0Spatrick assert(Seg0 != ~1u && Seg1 != ~1u);
138473471bf0Spatrick
138573471bf0Spatrick assert(Seg0 != Seg1 && "Expecting different segments");
138673471bf0Spatrick const SDLoc &dl(Results.InpNode);
138773471bf0Spatrick Results.push(Hexagon::A2_tfrsi, MVT::i32, {getConst32(SegLen, dl)});
138873471bf0Spatrick OpRef HL = OpRef::res(Results.top());
138973471bf0Spatrick
139073471bf0Spatrick // Va = AB, Vb = CD
139173471bf0Spatrick
139273471bf0Spatrick if (Seg0 / 2 == Seg1 / 2) {
139373471bf0Spatrick // Same input vector.
139473471bf0Spatrick Va = Inp[Seg0 / 2];
139573471bf0Spatrick if (Seg0 > Seg1) {
139673471bf0Spatrick // Swap halves.
139773471bf0Spatrick Results.push(Hexagon::V6_vror, Ty, {Inp[Seg0 / 2], HL});
139873471bf0Spatrick Va = OpRef::res(Results.top());
139973471bf0Spatrick }
140073471bf0Spatrick packSegmentMask(SM.Mask, {Seg0, Seg1}, SegLen, MaskH);
140173471bf0Spatrick } else if (Seg0 % 2 == Seg1 % 2) {
140273471bf0Spatrick // Picking AC, BD, CA, or DB.
140373471bf0Spatrick // vshuff(CD,AB,HL) -> BD:AC
140473471bf0Spatrick // vshuff(AB,CD,HL) -> DB:CA
140573471bf0Spatrick auto Vs = (Seg0 == 0 || Seg0 == 1) ? std::make_pair(Vb, Va) // AC or BD
140673471bf0Spatrick : std::make_pair(Va, Vb); // CA or DB
140773471bf0Spatrick Results.push(Hexagon::V6_vshuffvdd, PairTy, {Vs.first, Vs.second, HL});
140873471bf0Spatrick OpRef P = OpRef::res(Results.top());
140973471bf0Spatrick Va = (Seg0 == 0 || Seg0 == 2) ? OpRef::lo(P) : OpRef::hi(P);
141073471bf0Spatrick packSegmentMask(SM.Mask, {Seg0, Seg1}, SegLen, MaskH);
141173471bf0Spatrick } else {
141273471bf0Spatrick // Picking AD, BC, CB, or DA.
141373471bf0Spatrick if ((Seg0 == 0 && Seg1 == 3) || (Seg0 == 2 && Seg1 == 1)) {
141473471bf0Spatrick // AD or BC: this can be done using vmux.
141573471bf0Spatrick // Q = V6_pred_scalar2 SegLen
141673471bf0Spatrick // V = V6_vmux Q, (Va, Vb) or (Vb, Va)
141773471bf0Spatrick Results.push(Hexagon::V6_pred_scalar2, getBoolVT(), {HL});
141873471bf0Spatrick OpRef Qt = OpRef::res(Results.top());
141973471bf0Spatrick auto Vs = (Seg0 == 0) ? std::make_pair(Va, Vb) // AD
142073471bf0Spatrick : std::make_pair(Vb, Va); // CB
142173471bf0Spatrick Results.push(Hexagon::V6_vmux, Ty, {Qt, Vs.first, Vs.second});
142273471bf0Spatrick Va = OpRef::res(Results.top());
142373471bf0Spatrick packSegmentMask(SM.Mask, {Seg0, Seg1}, SegLen, MaskH);
142473471bf0Spatrick } else {
142573471bf0Spatrick // BC or DA: this could be done via valign by SegLen.
142673471bf0Spatrick // Do nothing here, because valign (if possible) will be generated
1427*d415bd75Srobert // later on (make sure the Seg0 values are as expected).
142873471bf0Spatrick assert(Seg0 == 1 || Seg0 == 3);
142973471bf0Spatrick }
143073471bf0Spatrick }
143173471bf0Spatrick }
143273471bf0Spatrick
143373471bf0Spatrick // Check if the arguments can be packed by valign(Va,Vb) or valign(Vb,Va).
1434*d415bd75Srobert // FIXME: maybe remove this?
143573471bf0Spatrick ShuffleMask SMH(MaskH);
143673471bf0Spatrick assert(SMH.Mask.size() == VecLen);
1437*d415bd75Srobert shuffles::MaskT MaskA(SMH.Mask);
143873471bf0Spatrick
143973471bf0Spatrick if (SMH.MaxSrc - SMH.MinSrc >= static_cast<int>(HwLen)) {
144073471bf0Spatrick // valign(Lo=Va,Hi=Vb) won't work. Try swapping Va/Vb.
1441*d415bd75Srobert shuffles::MaskT Swapped(SMH.Mask);
144273471bf0Spatrick ShuffleVectorSDNode::commuteMask(Swapped);
144373471bf0Spatrick ShuffleMask SW(Swapped);
144473471bf0Spatrick if (SW.MaxSrc - SW.MinSrc < static_cast<int>(HwLen)) {
144573471bf0Spatrick MaskA.assign(SW.Mask.begin(), SW.Mask.end());
144673471bf0Spatrick std::swap(Va, Vb);
144773471bf0Spatrick }
144873471bf0Spatrick }
144973471bf0Spatrick ShuffleMask SMA(MaskA);
145073471bf0Spatrick assert(SMA.Mask.size() == VecLen);
145173471bf0Spatrick
145273471bf0Spatrick if (SMA.MaxSrc - SMA.MinSrc < static_cast<int>(HwLen)) {
145373471bf0Spatrick int ShiftR = SMA.MinSrc;
145473471bf0Spatrick if (ShiftR >= static_cast<int>(HwLen)) {
145573471bf0Spatrick Va = Vb;
145673471bf0Spatrick Vb = OpRef::undef(Ty);
145773471bf0Spatrick ShiftR -= HwLen;
145873471bf0Spatrick }
145973471bf0Spatrick OpRef RetVal = valign(Va, Vb, ShiftR, Ty, Results);
146073471bf0Spatrick
146173471bf0Spatrick for (int I = 0; I != static_cast<int>(VecLen); ++I) {
146273471bf0Spatrick int M = SMA.Mask[I];
146373471bf0Spatrick if (M != -1)
146473471bf0Spatrick M -= SMA.MinSrc;
146573471bf0Spatrick NewMask[I] = M;
146673471bf0Spatrick }
146773471bf0Spatrick return RetVal;
146873471bf0Spatrick }
146973471bf0Spatrick
147073471bf0Spatrick // By here, packing by segment (half-vector) shuffling, and vector alignment
147173471bf0Spatrick // failed. Try vmux.
147273471bf0Spatrick // Note: since this is using the original mask, Va and Vb must not have been
147373471bf0Spatrick // modified.
147409467b48Spatrick
147509467b48Spatrick if (Options & PackMux) {
147609467b48Spatrick // If elements picked from Va and Vb have all different (source) indexes
147709467b48Spatrick // (relative to the start of the argument), do a mux, and update the mask.
147809467b48Spatrick BitVector Picked(HwLen);
147909467b48Spatrick SmallVector<uint8_t,128> MuxBytes(HwLen);
148009467b48Spatrick bool CanMux = true;
148173471bf0Spatrick for (int I = 0; I != static_cast<int>(VecLen); ++I) {
148209467b48Spatrick int M = SM.Mask[I];
148309467b48Spatrick if (M == -1)
148409467b48Spatrick continue;
148573471bf0Spatrick if (M >= static_cast<int>(HwLen))
148609467b48Spatrick M -= HwLen;
148709467b48Spatrick else
148809467b48Spatrick MuxBytes[M] = 0xFF;
148909467b48Spatrick if (Picked[M]) {
149009467b48Spatrick CanMux = false;
149109467b48Spatrick break;
149209467b48Spatrick }
149309467b48Spatrick NewMask[I] = M;
149409467b48Spatrick }
149509467b48Spatrick if (CanMux)
149609467b48Spatrick return vmuxs(MuxBytes, Va, Vb, Results);
149709467b48Spatrick }
149809467b48Spatrick return OpRef::fail();
149909467b48Spatrick }
150009467b48Spatrick
150173471bf0Spatrick // Va, Vb are vector pairs. If SM only uses two single vectors from Va/Vb,
150273471bf0Spatrick // pack these vectors into a pair, and remap SM into NewMask to use the
150373471bf0Spatrick // new pair instead.
packp(ShuffleMask SM,OpRef Va,OpRef Vb,ResultStack & Results,MutableArrayRef<int> NewMask)150409467b48Spatrick OpRef HvxSelector::packp(ShuffleMask SM, OpRef Va, OpRef Vb,
150509467b48Spatrick ResultStack &Results, MutableArrayRef<int> NewMask) {
150609467b48Spatrick DEBUG_WITH_TYPE("isel", {dbgs() << __func__ << '\n';});
150773471bf0Spatrick SmallVector<unsigned, 4> SegList = getInputSegmentList(SM.Mask, HwLen);
150873471bf0Spatrick if (SegList.empty())
150909467b48Spatrick return OpRef::undef(getPairVT(MVT::i8));
151009467b48Spatrick
151109467b48Spatrick // If more than two halves are used, bail.
151209467b48Spatrick // TODO: be more aggressive here?
151373471bf0Spatrick unsigned SegCount = SegList.size();
151473471bf0Spatrick if (SegCount > 2)
151509467b48Spatrick return OpRef::fail();
151609467b48Spatrick
151709467b48Spatrick MVT HalfTy = getSingleVT(MVT::i8);
151809467b48Spatrick
151909467b48Spatrick OpRef Inp[2] = { Va, Vb };
152009467b48Spatrick OpRef Out[2] = { OpRef::undef(HalfTy), OpRef::undef(HalfTy) };
152109467b48Spatrick
152273471bf0Spatrick // Really make sure we have at most 2 vectors used in the mask.
152373471bf0Spatrick assert(SegCount <= 2);
152473471bf0Spatrick
152573471bf0Spatrick for (int I = 0, E = SegList.size(); I != E; ++I) {
152673471bf0Spatrick unsigned S = SegList[I];
152773471bf0Spatrick OpRef Op = Inp[S / 2];
152873471bf0Spatrick Out[I] = (S & 1) ? OpRef::hi(Op) : OpRef::lo(Op);
152909467b48Spatrick }
153009467b48Spatrick
153173471bf0Spatrick // NOTE: Using SegList as the packing map here (not SegMap). This works,
153273471bf0Spatrick // because we're not concerned here about the order of the segments (i.e.
153373471bf0Spatrick // single vectors) in the output pair. Changing the order of vectors is
153473471bf0Spatrick // free (as opposed to changing the order of vector halves as in packs),
153573471bf0Spatrick // and so there is no extra cost added in case the order needs to be
153673471bf0Spatrick // changed later.
153773471bf0Spatrick packSegmentMask(SM.Mask, SegList, HwLen, NewMask);
153873471bf0Spatrick return concats(Out[0], Out[1], Results);
153909467b48Spatrick }
154009467b48Spatrick
vmuxs(ArrayRef<uint8_t> Bytes,OpRef Va,OpRef Vb,ResultStack & Results)154109467b48Spatrick OpRef HvxSelector::vmuxs(ArrayRef<uint8_t> Bytes, OpRef Va, OpRef Vb,
154209467b48Spatrick ResultStack &Results) {
154309467b48Spatrick DEBUG_WITH_TYPE("isel", {dbgs() << __func__ << '\n';});
154409467b48Spatrick MVT ByteTy = getSingleVT(MVT::i8);
1545097a140dSpatrick MVT BoolTy = MVT::getVectorVT(MVT::i1, HwLen);
154609467b48Spatrick const SDLoc &dl(Results.InpNode);
154709467b48Spatrick SDValue B = getVectorConstant(Bytes, dl);
154809467b48Spatrick Results.push(Hexagon::V6_vd0, ByteTy, {});
154909467b48Spatrick Results.push(Hexagon::V6_veqb, BoolTy, {OpRef(B), OpRef::res(-1)});
155009467b48Spatrick Results.push(Hexagon::V6_vmux, ByteTy, {OpRef::res(-1), Vb, Va});
155109467b48Spatrick return OpRef::res(Results.top());
155209467b48Spatrick }
155309467b48Spatrick
vmuxp(ArrayRef<uint8_t> Bytes,OpRef Va,OpRef Vb,ResultStack & Results)155409467b48Spatrick OpRef HvxSelector::vmuxp(ArrayRef<uint8_t> Bytes, OpRef Va, OpRef Vb,
155509467b48Spatrick ResultStack &Results) {
155609467b48Spatrick DEBUG_WITH_TYPE("isel", {dbgs() << __func__ << '\n';});
155709467b48Spatrick size_t S = Bytes.size() / 2;
155809467b48Spatrick OpRef L = vmuxs(Bytes.take_front(S), OpRef::lo(Va), OpRef::lo(Vb), Results);
155909467b48Spatrick OpRef H = vmuxs(Bytes.drop_front(S), OpRef::hi(Va), OpRef::hi(Vb), Results);
156073471bf0Spatrick return concats(L, H, Results);
156109467b48Spatrick }
156209467b48Spatrick
shuffs1(ShuffleMask SM,OpRef Va,ResultStack & Results)156309467b48Spatrick OpRef HvxSelector::shuffs1(ShuffleMask SM, OpRef Va, ResultStack &Results) {
156409467b48Spatrick DEBUG_WITH_TYPE("isel", {dbgs() << __func__ << '\n';});
156509467b48Spatrick unsigned VecLen = SM.Mask.size();
156609467b48Spatrick assert(HwLen == VecLen);
156709467b48Spatrick (void)VecLen;
156809467b48Spatrick assert(all_of(SM.Mask, [this](int M) { return M == -1 || M < int(HwLen); }));
156909467b48Spatrick
157009467b48Spatrick if (isIdentity(SM.Mask))
157109467b48Spatrick return Va;
157209467b48Spatrick if (isUndef(SM.Mask))
157309467b48Spatrick return OpRef::undef(getSingleVT(MVT::i8));
157409467b48Spatrick
1575*d415bd75Srobert // First, check for rotations.
1576*d415bd75Srobert if (auto Dist = rotationDistance(SM, VecLen)) {
1577*d415bd75Srobert OpRef Rotate = funnels(Va, Va, *Dist, Results);
1578*d415bd75Srobert if (Rotate.isValid())
1579*d415bd75Srobert return Rotate;
1580*d415bd75Srobert }
158173471bf0Spatrick unsigned HalfLen = HwLen / 2;
1582*d415bd75Srobert assert(isPowerOf2_32(HalfLen));
158373471bf0Spatrick
158473471bf0Spatrick // Handle special case where the output is the same half of the input
158573471bf0Spatrick // repeated twice, i.e. if Va = AB, then handle the output of AA or BB.
158673471bf0Spatrick std::pair<int, unsigned> Strip1 = findStrip(SM.Mask, 1, HalfLen);
158773471bf0Spatrick if ((Strip1.first & ~HalfLen) == 0 && Strip1.second == HalfLen) {
158873471bf0Spatrick std::pair<int, unsigned> Strip2 =
158973471bf0Spatrick findStrip(SM.Mask.drop_front(HalfLen), 1, HalfLen);
159073471bf0Spatrick if (Strip1 == Strip2) {
159173471bf0Spatrick const SDLoc &dl(Results.InpNode);
159273471bf0Spatrick Results.push(Hexagon::A2_tfrsi, MVT::i32, {getConst32(HalfLen, dl)});
159373471bf0Spatrick Results.push(Hexagon::V6_vshuffvdd, getPairVT(MVT::i8),
159473471bf0Spatrick {Va, Va, OpRef::res(Results.top())});
159573471bf0Spatrick OpRef S = OpRef::res(Results.top());
159673471bf0Spatrick return (Strip1.first == 0) ? OpRef::lo(S) : OpRef::hi(S);
159773471bf0Spatrick }
159873471bf0Spatrick }
159973471bf0Spatrick
160009467b48Spatrick OpRef P = perfect(SM, Va, Results);
160109467b48Spatrick if (P.isValid())
160209467b48Spatrick return P;
160309467b48Spatrick return butterfly(SM, Va, Results);
160409467b48Spatrick }
160509467b48Spatrick
shuffs2(ShuffleMask SM,OpRef Va,OpRef Vb,ResultStack & Results)160609467b48Spatrick OpRef HvxSelector::shuffs2(ShuffleMask SM, OpRef Va, OpRef Vb,
160709467b48Spatrick ResultStack &Results) {
160809467b48Spatrick DEBUG_WITH_TYPE("isel", {dbgs() << __func__ << '\n';});
160909467b48Spatrick if (isUndef(SM.Mask))
161009467b48Spatrick return OpRef::undef(getSingleVT(MVT::i8));
161109467b48Spatrick
161209467b48Spatrick OpRef C = contracting(SM, Va, Vb, Results);
161309467b48Spatrick if (C.isValid())
161409467b48Spatrick return C;
161509467b48Spatrick
161609467b48Spatrick int VecLen = SM.Mask.size();
1617*d415bd75Srobert shuffles::MaskT PackedMask(VecLen);
161873471bf0Spatrick OpRef P = packs(SM, Va, Vb, Results, PackedMask);
161909467b48Spatrick if (P.isValid())
162073471bf0Spatrick return shuffs1(ShuffleMask(PackedMask), P, Results);
162173471bf0Spatrick
162273471bf0Spatrick // TODO: Before we split the mask, try perfect shuffle on concatenated
1623*d415bd75Srobert // operands.
162409467b48Spatrick
1625*d415bd75Srobert shuffles::MaskT MaskL(VecLen), MaskR(VecLen);
162609467b48Spatrick splitMask(SM.Mask, MaskL, MaskR);
162709467b48Spatrick
162809467b48Spatrick OpRef L = shuffs1(ShuffleMask(MaskL), Va, Results);
162909467b48Spatrick OpRef R = shuffs1(ShuffleMask(MaskR), Vb, Results);
163009467b48Spatrick if (!L.isValid() || !R.isValid())
163109467b48Spatrick return OpRef::fail();
163209467b48Spatrick
163309467b48Spatrick SmallVector<uint8_t, 128> Bytes(VecLen);
163409467b48Spatrick for (int I = 0; I != VecLen; ++I) {
163509467b48Spatrick if (MaskL[I] != -1)
163609467b48Spatrick Bytes[I] = 0xFF;
163709467b48Spatrick }
163809467b48Spatrick return vmuxs(Bytes, L, R, Results);
163909467b48Spatrick }
164009467b48Spatrick
shuffp1(ShuffleMask SM,OpRef Va,ResultStack & Results)164109467b48Spatrick OpRef HvxSelector::shuffp1(ShuffleMask SM, OpRef Va, ResultStack &Results) {
164209467b48Spatrick DEBUG_WITH_TYPE("isel", {dbgs() << __func__ << '\n';});
164309467b48Spatrick int VecLen = SM.Mask.size();
164409467b48Spatrick
164509467b48Spatrick if (isIdentity(SM.Mask))
164609467b48Spatrick return Va;
164709467b48Spatrick if (isUndef(SM.Mask))
164809467b48Spatrick return OpRef::undef(getPairVT(MVT::i8));
164909467b48Spatrick
1650*d415bd75Srobert shuffles::MaskT PackedMask(VecLen);
165109467b48Spatrick OpRef P = packs(SM, OpRef::lo(Va), OpRef::hi(Va), Results, PackedMask);
165209467b48Spatrick if (P.isValid()) {
165309467b48Spatrick ShuffleMask PM(PackedMask);
165409467b48Spatrick OpRef E = expanding(PM, P, Results);
165509467b48Spatrick if (E.isValid())
165609467b48Spatrick return E;
165709467b48Spatrick
165809467b48Spatrick OpRef L = shuffs1(PM.lo(), P, Results);
165909467b48Spatrick OpRef H = shuffs1(PM.hi(), P, Results);
166009467b48Spatrick if (L.isValid() && H.isValid())
166173471bf0Spatrick return concats(L, H, Results);
166209467b48Spatrick }
166309467b48Spatrick
1664*d415bd75Srobert if (!isLowHalfOnly(SM.Mask)) {
1665*d415bd75Srobert // Doing a perfect shuffle on a low-half mask (i.e. where the upper half
1666*d415bd75Srobert // is all-undef) may produce a perfect shuffle that generates legitimate
1667*d415bd75Srobert // upper half. This isn't wrong, but if the perfect shuffle was possible,
1668*d415bd75Srobert // then there is a good chance that a shorter (contracting) code may be
1669*d415bd75Srobert // used as well (e.g. V6_vshuffeb, etc).
167009467b48Spatrick OpRef R = perfect(SM, Va, Results);
167109467b48Spatrick if (R.isValid())
167209467b48Spatrick return R;
167309467b48Spatrick // TODO commute the mask and try the opposite order of the halves.
1674*d415bd75Srobert }
167509467b48Spatrick
167609467b48Spatrick OpRef L = shuffs2(SM.lo(), OpRef::lo(Va), OpRef::hi(Va), Results);
167709467b48Spatrick OpRef H = shuffs2(SM.hi(), OpRef::lo(Va), OpRef::hi(Va), Results);
167809467b48Spatrick if (L.isValid() && H.isValid())
167973471bf0Spatrick return concats(L, H, Results);
168009467b48Spatrick
168109467b48Spatrick return OpRef::fail();
168209467b48Spatrick }
168309467b48Spatrick
shuffp2(ShuffleMask SM,OpRef Va,OpRef Vb,ResultStack & Results)168409467b48Spatrick OpRef HvxSelector::shuffp2(ShuffleMask SM, OpRef Va, OpRef Vb,
168509467b48Spatrick ResultStack &Results) {
168609467b48Spatrick DEBUG_WITH_TYPE("isel", {dbgs() << __func__ << '\n';});
168709467b48Spatrick if (isUndef(SM.Mask))
168809467b48Spatrick return OpRef::undef(getPairVT(MVT::i8));
168909467b48Spatrick
169009467b48Spatrick int VecLen = SM.Mask.size();
169109467b48Spatrick SmallVector<int,256> PackedMask(VecLen);
169209467b48Spatrick OpRef P = packp(SM, Va, Vb, Results, PackedMask);
169309467b48Spatrick if (P.isValid())
169409467b48Spatrick return shuffp1(ShuffleMask(PackedMask), P, Results);
169509467b48Spatrick
169609467b48Spatrick SmallVector<int,256> MaskL(VecLen), MaskR(VecLen);
169709467b48Spatrick splitMask(SM.Mask, MaskL, MaskR);
169809467b48Spatrick
169909467b48Spatrick OpRef L = shuffp1(ShuffleMask(MaskL), Va, Results);
170009467b48Spatrick OpRef R = shuffp1(ShuffleMask(MaskR), Vb, Results);
170109467b48Spatrick if (!L.isValid() || !R.isValid())
170209467b48Spatrick return OpRef::fail();
170309467b48Spatrick
170409467b48Spatrick // Mux the results.
170509467b48Spatrick SmallVector<uint8_t,256> Bytes(VecLen);
170609467b48Spatrick for (int I = 0; I != VecLen; ++I) {
170709467b48Spatrick if (MaskL[I] != -1)
170809467b48Spatrick Bytes[I] = 0xFF;
170909467b48Spatrick }
171009467b48Spatrick return vmuxp(Bytes, L, R, Results);
171109467b48Spatrick }
171209467b48Spatrick
171309467b48Spatrick namespace {
171409467b48Spatrick struct Deleter : public SelectionDAG::DAGNodeDeletedListener {
171509467b48Spatrick template <typename T>
Deleter__anona824ea740e11::Deleter171609467b48Spatrick Deleter(SelectionDAG &D, T &C)
171709467b48Spatrick : SelectionDAG::DAGNodeDeletedListener(D, [&C] (SDNode *N, SDNode *E) {
171809467b48Spatrick C.erase(N);
171909467b48Spatrick }) {}
172009467b48Spatrick };
172109467b48Spatrick
172209467b48Spatrick template <typename T>
172309467b48Spatrick struct NullifyingVector : public T {
172409467b48Spatrick DenseMap<SDNode*, SDNode**> Refs;
NullifyingVector__anona824ea740e11::NullifyingVector172509467b48Spatrick NullifyingVector(T &&V) : T(V) {
172609467b48Spatrick for (unsigned i = 0, e = T::size(); i != e; ++i) {
172709467b48Spatrick SDNode *&N = T::operator[](i);
172809467b48Spatrick Refs[N] = &N;
172909467b48Spatrick }
173009467b48Spatrick }
erase__anona824ea740e11::NullifyingVector173109467b48Spatrick void erase(SDNode *N) {
173209467b48Spatrick auto F = Refs.find(N);
173309467b48Spatrick if (F != Refs.end())
173409467b48Spatrick *F->second = nullptr;
173509467b48Spatrick }
173609467b48Spatrick };
173709467b48Spatrick }
173809467b48Spatrick
select(SDNode * ISelN)173973471bf0Spatrick void HvxSelector::select(SDNode *ISelN) {
174073471bf0Spatrick // What's important here is to select the right set of nodes. The main
174173471bf0Spatrick // selection algorithm loops over nodes in a topological order, i.e. users
174273471bf0Spatrick // are visited before their operands.
174373471bf0Spatrick //
174473471bf0Spatrick // It is an error to have an unselected node with a selected operand, and
174573471bf0Spatrick // there is an assertion in the main selector code to enforce that.
174673471bf0Spatrick //
174773471bf0Spatrick // Such a situation could occur if we selected a node, which is both a
174873471bf0Spatrick // subnode of ISelN, and a subnode of an unrelated (and yet unselected)
174973471bf0Spatrick // node in the DAG.
175073471bf0Spatrick assert(ISelN->getOpcode() == HexagonISD::ISEL);
175173471bf0Spatrick SDNode *N0 = ISelN->getOperand(0).getNode();
175273471bf0Spatrick if (N0->isMachineOpcode()) {
175373471bf0Spatrick ISel.ReplaceNode(ISelN, N0);
175473471bf0Spatrick return;
175573471bf0Spatrick }
175673471bf0Spatrick
175773471bf0Spatrick // There could have been nodes created (i.e. inserted into the DAG)
175873471bf0Spatrick // that are now dead. Remove them, in case they use any of the nodes
175973471bf0Spatrick // to select (and make them look shared).
176073471bf0Spatrick DAG.RemoveDeadNodes();
176173471bf0Spatrick
176273471bf0Spatrick SetVector<SDNode*> SubNodes, TmpQ;
176373471bf0Spatrick std::map<SDNode*,unsigned> NumOps;
176473471bf0Spatrick
176573471bf0Spatrick // Don't want to select N0 if it's shared with another node, except if
176673471bf0Spatrick // it's shared with other ISELs.
176773471bf0Spatrick auto IsISelN = [](SDNode *T) { return T->getOpcode() == HexagonISD::ISEL; };
176873471bf0Spatrick if (llvm::all_of(N0->uses(), IsISelN))
176973471bf0Spatrick SubNodes.insert(N0);
177073471bf0Spatrick
177173471bf0Spatrick auto InSubNodes = [&SubNodes](SDNode *T) { return SubNodes.count(T); };
177273471bf0Spatrick for (unsigned I = 0; I != SubNodes.size(); ++I) {
177373471bf0Spatrick SDNode *S = SubNodes[I];
177473471bf0Spatrick unsigned OpN = 0;
177573471bf0Spatrick // Only add subnodes that are only reachable from N0.
177673471bf0Spatrick for (SDValue Op : S->ops()) {
177773471bf0Spatrick SDNode *O = Op.getNode();
177873471bf0Spatrick if (llvm::all_of(O->uses(), InSubNodes)) {
177973471bf0Spatrick SubNodes.insert(O);
178073471bf0Spatrick ++OpN;
178173471bf0Spatrick }
178273471bf0Spatrick }
178373471bf0Spatrick NumOps.insert({S, OpN});
178473471bf0Spatrick if (OpN == 0)
178573471bf0Spatrick TmpQ.insert(S);
178673471bf0Spatrick }
178773471bf0Spatrick
178873471bf0Spatrick for (unsigned I = 0; I != TmpQ.size(); ++I) {
178973471bf0Spatrick SDNode *S = TmpQ[I];
179073471bf0Spatrick for (SDNode *U : S->uses()) {
179173471bf0Spatrick if (U == ISelN)
179273471bf0Spatrick continue;
179373471bf0Spatrick auto F = NumOps.find(U);
179473471bf0Spatrick assert(F != NumOps.end());
179573471bf0Spatrick if (F->second > 0 && !--F->second)
179673471bf0Spatrick TmpQ.insert(F->first);
179773471bf0Spatrick }
179873471bf0Spatrick }
179973471bf0Spatrick
180073471bf0Spatrick // Remove the marker.
180173471bf0Spatrick ISel.ReplaceNode(ISelN, N0);
180273471bf0Spatrick
180373471bf0Spatrick assert(SubNodes.size() == TmpQ.size());
180473471bf0Spatrick NullifyingVector<decltype(TmpQ)::vector_type> Queue(TmpQ.takeVector());
180573471bf0Spatrick
180673471bf0Spatrick Deleter DUQ(DAG, Queue);
180773471bf0Spatrick for (SDNode *S : reverse(Queue)) {
180873471bf0Spatrick if (S == nullptr)
180973471bf0Spatrick continue;
181073471bf0Spatrick DEBUG_WITH_TYPE("isel", {dbgs() << "HVX selecting: "; S->dump(&DAG);});
181173471bf0Spatrick ISel.Select(S);
181273471bf0Spatrick }
181373471bf0Spatrick }
181473471bf0Spatrick
scalarizeShuffle(ArrayRef<int> Mask,const SDLoc & dl,MVT ResTy,SDValue Va,SDValue Vb,SDNode * N)181509467b48Spatrick bool HvxSelector::scalarizeShuffle(ArrayRef<int> Mask, const SDLoc &dl,
181609467b48Spatrick MVT ResTy, SDValue Va, SDValue Vb,
181709467b48Spatrick SDNode *N) {
181809467b48Spatrick DEBUG_WITH_TYPE("isel", {dbgs() << __func__ << '\n';});
181909467b48Spatrick MVT ElemTy = ResTy.getVectorElementType();
182009467b48Spatrick assert(ElemTy == MVT::i8);
182109467b48Spatrick unsigned VecLen = Mask.size();
182209467b48Spatrick bool HavePairs = (2*HwLen == VecLen);
182309467b48Spatrick MVT SingleTy = getSingleVT(MVT::i8);
182409467b48Spatrick
182509467b48Spatrick // The prior attempts to handle this shuffle may have left a bunch of
182609467b48Spatrick // dead nodes in the DAG (such as constants). These nodes will be added
182709467b48Spatrick // at the end of DAG's node list, which at that point had already been
182809467b48Spatrick // sorted topologically. In the main selection loop, the node list is
182909467b48Spatrick // traversed backwards from the root node, which means that any new
183009467b48Spatrick // nodes (from the end of the list) will not be visited.
183109467b48Spatrick // Scalarization will replace the shuffle node with the scalarized
183209467b48Spatrick // expression, and if that expression reused any if the leftoever (dead)
183309467b48Spatrick // nodes, these nodes would not be selected (since the "local" selection
183409467b48Spatrick // only visits nodes that are not in AllNodes).
183509467b48Spatrick // To avoid this issue, remove all dead nodes from the DAG now.
183673471bf0Spatrick // DAG.RemoveDeadNodes();
183709467b48Spatrick
183809467b48Spatrick SmallVector<SDValue,128> Ops;
183909467b48Spatrick LLVMContext &Ctx = *DAG.getContext();
184009467b48Spatrick MVT LegalTy = Lower.getTypeToTransformTo(Ctx, ElemTy).getSimpleVT();
184109467b48Spatrick for (int I : Mask) {
184209467b48Spatrick if (I < 0) {
184309467b48Spatrick Ops.push_back(ISel.selectUndef(dl, LegalTy));
184409467b48Spatrick continue;
184509467b48Spatrick }
184609467b48Spatrick SDValue Vec;
184709467b48Spatrick unsigned M = I;
184809467b48Spatrick if (M < VecLen) {
184909467b48Spatrick Vec = Va;
185009467b48Spatrick } else {
185109467b48Spatrick Vec = Vb;
185209467b48Spatrick M -= VecLen;
185309467b48Spatrick }
185409467b48Spatrick if (HavePairs) {
185509467b48Spatrick if (M < HwLen) {
185609467b48Spatrick Vec = DAG.getTargetExtractSubreg(Hexagon::vsub_lo, dl, SingleTy, Vec);
185709467b48Spatrick } else {
185809467b48Spatrick Vec = DAG.getTargetExtractSubreg(Hexagon::vsub_hi, dl, SingleTy, Vec);
185909467b48Spatrick M -= HwLen;
186009467b48Spatrick }
186109467b48Spatrick }
186209467b48Spatrick SDValue Idx = DAG.getConstant(M, dl, MVT::i32);
186309467b48Spatrick SDValue Ex = DAG.getNode(ISD::EXTRACT_VECTOR_ELT, dl, LegalTy, {Vec, Idx});
186409467b48Spatrick SDValue L = Lower.LowerOperation(Ex, DAG);
186509467b48Spatrick assert(L.getNode());
186609467b48Spatrick Ops.push_back(L);
186709467b48Spatrick }
186809467b48Spatrick
186909467b48Spatrick SDValue LV;
187009467b48Spatrick if (2*HwLen == VecLen) {
187109467b48Spatrick SDValue B0 = DAG.getBuildVector(SingleTy, dl, {Ops.data(), HwLen});
187209467b48Spatrick SDValue L0 = Lower.LowerOperation(B0, DAG);
187309467b48Spatrick SDValue B1 = DAG.getBuildVector(SingleTy, dl, {Ops.data()+HwLen, HwLen});
187409467b48Spatrick SDValue L1 = Lower.LowerOperation(B1, DAG);
187509467b48Spatrick // XXX CONCAT_VECTORS is legal for HVX vectors. Legalizing (lowering)
187609467b48Spatrick // functions may expect to be called only for illegal operations, so
187709467b48Spatrick // make sure that they are not called for legal ones. Develop a better
187809467b48Spatrick // mechanism for dealing with this.
187909467b48Spatrick LV = DAG.getNode(ISD::CONCAT_VECTORS, dl, ResTy, {L0, L1});
188009467b48Spatrick } else {
188109467b48Spatrick SDValue BV = DAG.getBuildVector(ResTy, dl, Ops);
188209467b48Spatrick LV = Lower.LowerOperation(BV, DAG);
188309467b48Spatrick }
188409467b48Spatrick
188509467b48Spatrick assert(!N->use_empty());
188673471bf0Spatrick SDValue IS = DAG.getNode(HexagonISD::ISEL, dl, ResTy, LV);
188773471bf0Spatrick ISel.ReplaceNode(N, IS.getNode());
188873471bf0Spatrick select(IS.getNode());
188909467b48Spatrick DAG.RemoveDeadNodes();
189009467b48Spatrick return true;
189109467b48Spatrick }
189209467b48Spatrick
getPerfectCompletions(ShuffleMask SM,unsigned Width)1893*d415bd75Srobert SmallVector<uint32_t, 8> HvxSelector::getPerfectCompletions(ShuffleMask SM,
1894*d415bd75Srobert unsigned Width) {
1895*d415bd75Srobert auto possibilities = [](ArrayRef<uint8_t> Bs, unsigned Width) -> uint32_t {
1896*d415bd75Srobert unsigned Impossible = ~(1u << Width) + 1;
1897*d415bd75Srobert for (unsigned I = 0, E = Bs.size(); I != E; ++I) {
1898*d415bd75Srobert uint8_t B = Bs[I];
1899*d415bd75Srobert if (B == 0xff)
1900*d415bd75Srobert continue;
1901*d415bd75Srobert if (~Impossible == 0)
1902*d415bd75Srobert break;
1903*d415bd75Srobert for (unsigned Log = 0; Log != Width; ++Log) {
1904*d415bd75Srobert if (Impossible & (1u << Log))
1905*d415bd75Srobert continue;
1906*d415bd75Srobert unsigned Expected = (I >> Log) % 2;
1907*d415bd75Srobert if (B != Expected)
1908*d415bd75Srobert Impossible |= (1u << Log);
1909*d415bd75Srobert }
1910*d415bd75Srobert }
1911*d415bd75Srobert return ~Impossible;
1912*d415bd75Srobert };
1913*d415bd75Srobert
1914*d415bd75Srobert SmallVector<uint32_t, 8> Worklist(Width);
1915*d415bd75Srobert
1916*d415bd75Srobert for (unsigned BitIdx = 0; BitIdx != Width; ++BitIdx) {
1917*d415bd75Srobert SmallVector<uint8_t> BitValues(SM.Mask.size());
1918*d415bd75Srobert for (int i = 0, e = SM.Mask.size(); i != e; ++i) {
1919*d415bd75Srobert int M = SM.Mask[i];
1920*d415bd75Srobert if (M < 0)
1921*d415bd75Srobert BitValues[i] = 0xff;
1922*d415bd75Srobert else
1923*d415bd75Srobert BitValues[i] = (M & (1u << BitIdx)) != 0;
1924*d415bd75Srobert }
1925*d415bd75Srobert Worklist[BitIdx] = possibilities(BitValues, Width);
1926*d415bd75Srobert }
1927*d415bd75Srobert
1928*d415bd75Srobert // If there is a word P in Worklist that matches multiple possibilities,
1929*d415bd75Srobert // then if any other word Q matches any of the possibilities matched by P,
1930*d415bd75Srobert // then Q matches all the possibilities matched by P. In fact, P == Q.
1931*d415bd75Srobert // In other words, for each words P, Q, the sets of possibilities matched
1932*d415bd75Srobert // by P and Q are either equal or disjoint (no partial overlap).
1933*d415bd75Srobert //
1934*d415bd75Srobert // Illustration: For 4-bit values there are 4 complete sequences:
1935*d415bd75Srobert // a: 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
1936*d415bd75Srobert // b: 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
1937*d415bd75Srobert // c: 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
1938*d415bd75Srobert // d: 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
1939*d415bd75Srobert //
1940*d415bd75Srobert // Words containing unknown bits that match two of the complete
1941*d415bd75Srobert // sequences:
1942*d415bd75Srobert // ab: 0 u u 1 0 u u 1 0 u u 1 0 u u 1
1943*d415bd75Srobert // ac: 0 u 0 u u 1 u 1 0 u 0 u u 1 u 1
1944*d415bd75Srobert // ad: 0 u 0 u 0 u 0 u u 1 u 1 u 1 u 1
1945*d415bd75Srobert // bc: 0 0 u u u u 1 1 0 0 u u u u 1 1
1946*d415bd75Srobert // bd: 0 0 u u 0 0 u u u u 1 1 u u 1 1
1947*d415bd75Srobert // cd: 0 0 0 0 u u u u u u u u 1 1 1 1
1948*d415bd75Srobert //
1949*d415bd75Srobert // Proof of the claim above:
1950*d415bd75Srobert // Let P be a word that matches s0 and s1. For that to happen, all known
1951*d415bd75Srobert // bits in P must match s0 and s1 exactly.
1952*d415bd75Srobert // Assume there is Q that matches s1. Note that since P and Q came from
1953*d415bd75Srobert // the same shuffle mask, the positions of unknown bits in P and Q match
1954*d415bd75Srobert // exactly, which makes the indices of known bits be exactly the same
1955*d415bd75Srobert // between P and Q. Since P matches s0 and s1, the known bits of P much
1956*d415bd75Srobert // match both s0 and s1. Also, since Q matches s1, the known bits in Q
1957*d415bd75Srobert // are exactly the same as in s1, which means that they are exactly the
1958*d415bd75Srobert // same as in P. This implies that P == Q.
1959*d415bd75Srobert
1960*d415bd75Srobert // There can be a situation where there are more entries with the same
1961*d415bd75Srobert // bits set than there are set bits (e.g. value 9 occuring more than 2
1962*d415bd75Srobert // times). In such cases it will be impossible to complete this to a
1963*d415bd75Srobert // perfect shuffle.
1964*d415bd75Srobert SmallVector<uint32_t, 8> Sorted(Worklist);
1965*d415bd75Srobert llvm::sort(Sorted.begin(), Sorted.end());
1966*d415bd75Srobert
1967*d415bd75Srobert for (unsigned I = 0, E = Sorted.size(); I != E;) {
1968*d415bd75Srobert unsigned P = Sorted[I], Count = 1;
1969*d415bd75Srobert while (++I != E && P == Sorted[I])
1970*d415bd75Srobert ++Count;
1971*d415bd75Srobert if ((unsigned)llvm::popcount(P) < Count) {
1972*d415bd75Srobert // Reset all occurences of P, if there are more occurrences of P
1973*d415bd75Srobert // than there are bits in P.
1974*d415bd75Srobert for_each(Worklist, [P](unsigned &Q) {
1975*d415bd75Srobert if (Q == P)
1976*d415bd75Srobert Q = 0;
1977*d415bd75Srobert });
1978*d415bd75Srobert }
1979*d415bd75Srobert }
1980*d415bd75Srobert
1981*d415bd75Srobert return Worklist;
1982*d415bd75Srobert }
1983*d415bd75Srobert
1984*d415bd75Srobert SmallVector<uint32_t, 8>
completeToPerfect(ArrayRef<uint32_t> Completions,unsigned Width)1985*d415bd75Srobert HvxSelector::completeToPerfect(ArrayRef<uint32_t> Completions, unsigned Width) {
1986*d415bd75Srobert // Pick a completion if there are multiple possibilities. For now just
1987*d415bd75Srobert // select any valid completion.
1988*d415bd75Srobert SmallVector<uint32_t, 8> Comps(Completions);
1989*d415bd75Srobert
1990*d415bd75Srobert for (unsigned I = 0; I != Width; ++I) {
1991*d415bd75Srobert uint32_t P = Comps[I];
1992*d415bd75Srobert assert(P != 0);
1993*d415bd75Srobert if (isPowerOf2_32(P))
1994*d415bd75Srobert continue;
1995*d415bd75Srobert // T = least significant bit of P.
1996*d415bd75Srobert uint32_t T = P ^ ((P - 1) & P);
1997*d415bd75Srobert // Clear T in all remaining words matching P.
1998*d415bd75Srobert for (unsigned J = I + 1; J != Width; ++J) {
1999*d415bd75Srobert if (Comps[J] == P)
2000*d415bd75Srobert Comps[J] ^= T;
2001*d415bd75Srobert }
2002*d415bd75Srobert Comps[I] = T;
2003*d415bd75Srobert }
2004*d415bd75Srobert
2005*d415bd75Srobert #ifndef NDEBUG
2006*d415bd75Srobert // Check that we have generated a valid completion.
2007*d415bd75Srobert uint32_t OrAll = 0;
2008*d415bd75Srobert for (unsigned I = 0, E = Comps.size(); I != E; ++I) {
2009*d415bd75Srobert uint32_t C = Comps[I];
2010*d415bd75Srobert assert(isPowerOf2_32(C));
2011*d415bd75Srobert OrAll |= C;
2012*d415bd75Srobert }
2013*d415bd75Srobert assert(OrAll == (1u << Width) -1);
2014*d415bd75Srobert #endif
2015*d415bd75Srobert
2016*d415bd75Srobert return Comps;
2017*d415bd75Srobert }
2018*d415bd75Srobert
rotationDistance(ShuffleMask SM,unsigned WrapAt)2019*d415bd75Srobert std::optional<int> HvxSelector::rotationDistance(ShuffleMask SM,
2020*d415bd75Srobert unsigned WrapAt) {
2021*d415bd75Srobert std::optional<int> Dist;
2022*d415bd75Srobert for (int I = 0, E = SM.Mask.size(); I != E; ++I) {
2023*d415bd75Srobert int M = SM.Mask[I];
2024*d415bd75Srobert if (M < 0)
2025*d415bd75Srobert continue;
2026*d415bd75Srobert if (Dist) {
2027*d415bd75Srobert if ((I + *Dist) % static_cast<int>(WrapAt) != M)
2028*d415bd75Srobert return std::nullopt;
2029*d415bd75Srobert } else {
2030*d415bd75Srobert // Integer a%b operator assumes rounding towards zero by /, so it
2031*d415bd75Srobert // "misbehaves" when a crosses 0 (the remainder also changes sign).
2032*d415bd75Srobert // Add WrapAt in an attempt to keep I+Dist non-negative.
2033*d415bd75Srobert Dist = M - I;
2034*d415bd75Srobert if (Dist < 0)
2035*d415bd75Srobert Dist = *Dist + WrapAt;
2036*d415bd75Srobert }
2037*d415bd75Srobert }
2038*d415bd75Srobert return Dist;
2039*d415bd75Srobert }
2040*d415bd75Srobert
contracting(ShuffleMask SM,OpRef Va,OpRef Vb,ResultStack & Results)204109467b48Spatrick OpRef HvxSelector::contracting(ShuffleMask SM, OpRef Va, OpRef Vb,
204209467b48Spatrick ResultStack &Results) {
204309467b48Spatrick DEBUG_WITH_TYPE("isel", { dbgs() << __func__ << '\n'; });
204409467b48Spatrick if (!Va.isValid() || !Vb.isValid())
204509467b48Spatrick return OpRef::fail();
204609467b48Spatrick
204709467b48Spatrick // Contracting shuffles, i.e. instructions that always discard some bytes
204809467b48Spatrick // from the operand vectors.
204909467b48Spatrick //
2050*d415bd75Srobert // Funnel shifts
205109467b48Spatrick // V6_vshuff{e,o}b
2052*d415bd75Srobert // V6_vshuf{e,o}h
205309467b48Spatrick // V6_vdealb4w
205409467b48Spatrick // V6_vpack{e,o}{b,h}
205509467b48Spatrick
205609467b48Spatrick int VecLen = SM.Mask.size();
205709467b48Spatrick
2058*d415bd75Srobert // First, check for funnel shifts.
2059*d415bd75Srobert if (auto Dist = rotationDistance(SM, 2 * VecLen)) {
2060*d415bd75Srobert OpRef Funnel = funnels(Va, Vb, *Dist, Results);
2061*d415bd75Srobert if (Funnel.isValid())
2062*d415bd75Srobert return Funnel;
2063*d415bd75Srobert }
206409467b48Spatrick
2065*d415bd75Srobert MVT SingleTy = getSingleVT(MVT::i8);
2066*d415bd75Srobert MVT PairTy = getPairVT(MVT::i8);
206709467b48Spatrick
2068*d415bd75Srobert auto same = [](ArrayRef<int> Mask1, ArrayRef<int> Mask2) -> bool {
2069*d415bd75Srobert return Mask1 == Mask2;
2070*d415bd75Srobert };
207109467b48Spatrick
2072*d415bd75Srobert using PackConfig = std::pair<unsigned, bool>;
2073*d415bd75Srobert PackConfig Packs[] = {
2074*d415bd75Srobert {1, false}, // byte, even
2075*d415bd75Srobert {1, true}, // byte, odd
2076*d415bd75Srobert {2, false}, // half, even
2077*d415bd75Srobert {2, true}, // half, odd
2078*d415bd75Srobert };
2079*d415bd75Srobert
2080*d415bd75Srobert { // Check vpack
2081*d415bd75Srobert unsigned Opcodes[] = {
2082*d415bd75Srobert Hexagon::V6_vpackeb,
2083*d415bd75Srobert Hexagon::V6_vpackob,
2084*d415bd75Srobert Hexagon::V6_vpackeh,
2085*d415bd75Srobert Hexagon::V6_vpackoh,
2086*d415bd75Srobert };
2087*d415bd75Srobert for (int i = 0, e = std::size(Opcodes); i != e; ++i) {
2088*d415bd75Srobert auto [Size, Odd] = Packs[i];
2089*d415bd75Srobert if (same(SM.Mask, shuffles::mask(shuffles::vpack, HwLen, Size, Odd))) {
2090*d415bd75Srobert Results.push(Opcodes[i], SingleTy, {Vb, Va});
2091*d415bd75Srobert return OpRef::res(Results.top());
2092*d415bd75Srobert }
2093*d415bd75Srobert }
2094*d415bd75Srobert }
2095*d415bd75Srobert
2096*d415bd75Srobert { // Check vshuff
2097*d415bd75Srobert unsigned Opcodes[] = {
2098*d415bd75Srobert Hexagon::V6_vshuffeb,
2099*d415bd75Srobert Hexagon::V6_vshuffob,
2100*d415bd75Srobert Hexagon::V6_vshufeh,
2101*d415bd75Srobert Hexagon::V6_vshufoh,
2102*d415bd75Srobert };
2103*d415bd75Srobert for (int i = 0, e = std::size(Opcodes); i != e; ++i) {
2104*d415bd75Srobert auto [Size, Odd] = Packs[i];
2105*d415bd75Srobert if (same(SM.Mask, shuffles::mask(shuffles::vshuff, HwLen, Size, Odd))) {
2106*d415bd75Srobert Results.push(Opcodes[i], SingleTy, {Vb, Va});
2107*d415bd75Srobert return OpRef::res(Results.top());
2108*d415bd75Srobert }
2109*d415bd75Srobert }
2110*d415bd75Srobert }
2111*d415bd75Srobert
2112*d415bd75Srobert { // Check vdeal
2113*d415bd75Srobert // There is no "V6_vdealeb", etc, but the supposed behavior of vdealeb
2114*d415bd75Srobert // is equivalent to "(V6_vpackeb (V6_vdealvdd Vu, Vv, -2))". Other such
2115*d415bd75Srobert // variants of "deal" can be done similarly.
2116*d415bd75Srobert unsigned Opcodes[] = {
2117*d415bd75Srobert Hexagon::V6_vpackeb,
2118*d415bd75Srobert Hexagon::V6_vpackob,
2119*d415bd75Srobert Hexagon::V6_vpackeh,
2120*d415bd75Srobert Hexagon::V6_vpackoh,
2121*d415bd75Srobert };
2122*d415bd75Srobert const SDLoc &dl(Results.InpNode);
2123*d415bd75Srobert
2124*d415bd75Srobert for (int i = 0, e = std::size(Opcodes); i != e; ++i) {
2125*d415bd75Srobert auto [Size, Odd] = Packs[i];
2126*d415bd75Srobert if (same(SM.Mask, shuffles::mask(shuffles::vdeal, HwLen, Size, Odd))) {
2127*d415bd75Srobert Results.push(Hexagon::A2_tfrsi, MVT::i32, {getConst32(-2 * Size, dl)});
2128*d415bd75Srobert Results.push(Hexagon::V6_vdealvdd, PairTy, {Vb, Va, OpRef::res(-1)});
2129*d415bd75Srobert auto vdeal = OpRef::res(Results.top());
2130*d415bd75Srobert Results.push(Opcodes[i], SingleTy,
2131*d415bd75Srobert {OpRef::hi(vdeal), OpRef::lo(vdeal)});
2132*d415bd75Srobert return OpRef::res(Results.top());
2133*d415bd75Srobert }
2134*d415bd75Srobert }
2135*d415bd75Srobert }
2136*d415bd75Srobert
2137*d415bd75Srobert if (same(SM.Mask, shuffles::mask(shuffles::vdealb4w, HwLen))) {
2138*d415bd75Srobert Results.push(Hexagon::V6_vdealb4w, SingleTy, {Vb, Va});
213909467b48Spatrick return OpRef::res(Results.top());
214009467b48Spatrick }
214109467b48Spatrick
214209467b48Spatrick return OpRef::fail();
214309467b48Spatrick }
214409467b48Spatrick
expanding(ShuffleMask SM,OpRef Va,ResultStack & Results)214509467b48Spatrick OpRef HvxSelector::expanding(ShuffleMask SM, OpRef Va, ResultStack &Results) {
214609467b48Spatrick DEBUG_WITH_TYPE("isel", {dbgs() << __func__ << '\n';});
214709467b48Spatrick // Expanding shuffles (using all elements and inserting into larger vector):
214809467b48Spatrick //
214909467b48Spatrick // V6_vunpacku{b,h} [*]
215009467b48Spatrick //
215109467b48Spatrick // [*] Only if the upper elements (filled with 0s) are "don't care" in Mask.
215209467b48Spatrick //
215309467b48Spatrick // Note: V6_vunpacko{b,h} are or-ing the high byte/half in the result, so
215409467b48Spatrick // they are not shuffles.
215509467b48Spatrick //
215609467b48Spatrick // The argument is a single vector.
215709467b48Spatrick
215809467b48Spatrick int VecLen = SM.Mask.size();
215909467b48Spatrick assert(2*HwLen == unsigned(VecLen) && "Expecting vector-pair type");
216009467b48Spatrick
216109467b48Spatrick std::pair<int,unsigned> Strip = findStrip(SM.Mask, 1, VecLen);
216209467b48Spatrick
216309467b48Spatrick // The patterns for the unpacks, in terms of the starting offsets of the
216409467b48Spatrick // consecutive strips (L = length of the strip, N = VecLen):
216509467b48Spatrick //
216609467b48Spatrick // vunpacku: 0, -1, L, -1, 2L, -1 ...
216709467b48Spatrick
216809467b48Spatrick if (Strip.first != 0)
216909467b48Spatrick return OpRef::fail();
217009467b48Spatrick
217109467b48Spatrick // The vunpackus only handle byte and half-word.
217209467b48Spatrick if (Strip.second != 1 && Strip.second != 2)
217309467b48Spatrick return OpRef::fail();
217409467b48Spatrick
217509467b48Spatrick int N = VecLen;
217609467b48Spatrick int L = Strip.second;
217709467b48Spatrick
217809467b48Spatrick // First, check the non-ignored strips.
217973471bf0Spatrick for (int I = 2*L; I < N; I += 2*L) {
218009467b48Spatrick auto S = findStrip(SM.Mask.drop_front(I), 1, N-I);
218109467b48Spatrick if (S.second != unsigned(L))
218209467b48Spatrick return OpRef::fail();
218309467b48Spatrick if (2*S.first != I)
218409467b48Spatrick return OpRef::fail();
218509467b48Spatrick }
218609467b48Spatrick // Check the -1s.
218773471bf0Spatrick for (int I = L; I < N; I += 2*L) {
218809467b48Spatrick auto S = findStrip(SM.Mask.drop_front(I), 0, N-I);
218909467b48Spatrick if (S.first != -1 || S.second != unsigned(L))
219009467b48Spatrick return OpRef::fail();
219109467b48Spatrick }
219209467b48Spatrick
219309467b48Spatrick unsigned Opc = Strip.second == 1 ? Hexagon::V6_vunpackub
219409467b48Spatrick : Hexagon::V6_vunpackuh;
219509467b48Spatrick Results.push(Opc, getPairVT(MVT::i8), {Va});
219609467b48Spatrick return OpRef::res(Results.top());
219709467b48Spatrick }
219809467b48Spatrick
perfect(ShuffleMask SM,OpRef Va,ResultStack & Results)219909467b48Spatrick OpRef HvxSelector::perfect(ShuffleMask SM, OpRef Va, ResultStack &Results) {
220009467b48Spatrick DEBUG_WITH_TYPE("isel", { dbgs() << __func__ << '\n'; });
220109467b48Spatrick // V6_vdeal{b,h}
220209467b48Spatrick // V6_vshuff{b,h}
220309467b48Spatrick
220409467b48Spatrick // V6_vshufoe{b,h} those are quivalent to vshuffvdd(..,{1,2})
220509467b48Spatrick // V6_vshuffvdd (V6_vshuff)
220609467b48Spatrick // V6_dealvdd (V6_vdeal)
220709467b48Spatrick
220809467b48Spatrick int VecLen = SM.Mask.size();
220909467b48Spatrick assert(isPowerOf2_32(VecLen) && Log2_32(VecLen) <= 8);
221009467b48Spatrick unsigned LogLen = Log2_32(VecLen);
221109467b48Spatrick unsigned HwLog = Log2_32(HwLen);
221209467b48Spatrick // The result length must be the same as the length of a single vector,
221309467b48Spatrick // or a vector pair.
221409467b48Spatrick assert(LogLen == HwLog || LogLen == HwLog + 1);
221573471bf0Spatrick bool HavePairs = LogLen == HwLog + 1;
221609467b48Spatrick
221709467b48Spatrick SmallVector<unsigned, 8> Perm(LogLen);
221809467b48Spatrick
221909467b48Spatrick // Check if this could be a perfect shuffle, or a combination of perfect
222009467b48Spatrick // shuffles.
222109467b48Spatrick //
222209467b48Spatrick // Consider this permutation (using hex digits to make the ASCII diagrams
222309467b48Spatrick // easier to read):
222409467b48Spatrick // { 0, 8, 1, 9, 2, A, 3, B, 4, C, 5, D, 6, E, 7, F }.
222509467b48Spatrick // This is a "deal" operation: divide the input into two halves, and
222609467b48Spatrick // create the output by picking elements by alternating between these two
222709467b48Spatrick // halves:
222809467b48Spatrick // 0 1 2 3 4 5 6 7 --> 0 8 1 9 2 A 3 B 4 C 5 D 6 E 7 F [*]
222909467b48Spatrick // 8 9 A B C D E F
223009467b48Spatrick //
223109467b48Spatrick // Aside from a few special explicit cases (V6_vdealb, etc.), HVX provides
223209467b48Spatrick // a somwehat different mechanism that could be used to perform shuffle/
223309467b48Spatrick // deal operations: a 2x2 transpose.
223409467b48Spatrick // Consider the halves of inputs again, they can be interpreted as a 2x8
223509467b48Spatrick // matrix. A 2x8 matrix can be looked at four 2x2 matrices concatenated
223609467b48Spatrick // together. Now, when considering 2 elements at a time, it will be a 2x4
223709467b48Spatrick // matrix (with elements 01, 23, 45, etc.), or two 2x2 matrices:
223809467b48Spatrick // 01 23 45 67
223909467b48Spatrick // 89 AB CD EF
224009467b48Spatrick // With groups of 4, this will become a single 2x2 matrix, and so on.
224109467b48Spatrick //
224209467b48Spatrick // The 2x2 transpose instruction works by transposing each of the 2x2
224309467b48Spatrick // matrices (or "sub-matrices"), given a specific group size. For example,
224409467b48Spatrick // if the group size is 1 (i.e. each element is its own group), there
224509467b48Spatrick // will be four transposes of the four 2x2 matrices that form the 2x8.
224609467b48Spatrick // For example, with the inputs as above, the result will be:
224709467b48Spatrick // 0 8 2 A 4 C 6 E
224809467b48Spatrick // 1 9 3 B 5 D 7 F
224909467b48Spatrick // Now, this result can be tranposed again, but with the group size of 2:
225009467b48Spatrick // 08 19 4C 5D
225109467b48Spatrick // 2A 3B 6E 7F
225209467b48Spatrick // If we then transpose that result, but with the group size of 4, we get:
225309467b48Spatrick // 0819 2A3B
225409467b48Spatrick // 4C5D 6E7F
225509467b48Spatrick // If we concatenate these two rows, it will be
225609467b48Spatrick // 0 8 1 9 2 A 3 B 4 C 5 D 6 E 7 F
225709467b48Spatrick // which is the same as the "deal" [*] above.
225809467b48Spatrick //
225909467b48Spatrick // In general, a "deal" of individual elements is a series of 2x2 transposes,
226009467b48Spatrick // with changing group size. HVX has two instructions:
226109467b48Spatrick // Vdd = V6_vdealvdd Vu, Vv, Rt
226209467b48Spatrick // Vdd = V6_shufvdd Vu, Vv, Rt
226309467b48Spatrick // that perform exactly that. The register Rt controls which transposes are
226409467b48Spatrick // going to happen: a bit at position n (counting from 0) indicates that a
226509467b48Spatrick // transpose with a group size of 2^n will take place. If multiple bits are
226609467b48Spatrick // set, multiple transposes will happen: vdealvdd will perform them starting
226709467b48Spatrick // with the largest group size, vshuffvdd will do them in the reverse order.
226809467b48Spatrick //
226909467b48Spatrick // The main observation is that each 2x2 transpose corresponds to swapping
227009467b48Spatrick // columns of bits in the binary representation of the values.
227109467b48Spatrick //
227209467b48Spatrick // The numbers {3,2,1,0} and the log2 of the number of contiguous 1 bits
227309467b48Spatrick // in a given column. The * denote the columns that will be swapped.
227409467b48Spatrick // The transpose with the group size 2^n corresponds to swapping columns
227509467b48Spatrick // 3 (the highest log) and log2(n):
227609467b48Spatrick //
227709467b48Spatrick // 3 2 1 0 0 2 1 3 0 2 3 1
227809467b48Spatrick // * * * * * *
227909467b48Spatrick // 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
228009467b48Spatrick // 1 0 0 0 1 8 1 0 0 0 8 1 0 0 0 8 1 0 0 0
228109467b48Spatrick // 2 0 0 1 0 2 0 0 1 0 1 0 0 0 1 1 0 0 0 1
228209467b48Spatrick // 3 0 0 1 1 A 1 0 1 0 9 1 0 0 1 9 1 0 0 1
228309467b48Spatrick // 4 0 1 0 0 4 0 1 0 0 4 0 1 0 0 2 0 0 1 0
228409467b48Spatrick // 5 0 1 0 1 C 1 1 0 0 C 1 1 0 0 A 1 0 1 0
228509467b48Spatrick // 6 0 1 1 0 6 0 1 1 0 5 0 1 0 1 3 0 0 1 1
228609467b48Spatrick // 7 0 1 1 1 E 1 1 1 0 D 1 1 0 1 B 1 0 1 1
228709467b48Spatrick // 8 1 0 0 0 1 0 0 0 1 2 0 0 1 0 4 0 1 0 0
228809467b48Spatrick // 9 1 0 0 1 9 1 0 0 1 A 1 0 1 0 C 1 1 0 0
228909467b48Spatrick // A 1 0 1 0 3 0 0 1 1 3 0 0 1 1 5 0 1 0 1
229009467b48Spatrick // B 1 0 1 1 B 1 0 1 1 B 1 0 1 1 D 1 1 0 1
229109467b48Spatrick // C 1 1 0 0 5 0 1 0 1 6 0 1 1 0 6 0 1 1 0
229209467b48Spatrick // D 1 1 0 1 D 1 1 0 1 E 1 1 1 0 E 1 1 1 0
229309467b48Spatrick // E 1 1 1 0 7 0 1 1 1 7 0 1 1 1 7 0 1 1 1
229409467b48Spatrick // F 1 1 1 1 F 1 1 1 1 F 1 1 1 1 F 1 1 1 1
229509467b48Spatrick
2296*d415bd75Srobert // There is one special case that is not a perfect shuffle, but can be
2297*d415bd75Srobert // turned into one easily: when the shuffle operates on a vector pair,
2298*d415bd75Srobert // but the two vectors in the pair are swapped. The code that identifies
2299*d415bd75Srobert // perfect shuffles will reject it, unless the order is reversed.
2300*d415bd75Srobert shuffles::MaskT MaskStorage(SM.Mask);
230173471bf0Spatrick bool InvertedPair = false;
230273471bf0Spatrick if (HavePairs && SM.Mask[0] >= int(HwLen)) {
230373471bf0Spatrick for (int i = 0, e = SM.Mask.size(); i != e; ++i) {
230473471bf0Spatrick int M = SM.Mask[i];
230573471bf0Spatrick MaskStorage[i] = M >= int(HwLen) ? M - HwLen : M + HwLen;
230673471bf0Spatrick }
230773471bf0Spatrick InvertedPair = true;
2308*d415bd75Srobert SM = ShuffleMask(MaskStorage);
230973471bf0Spatrick }
231073471bf0Spatrick
2311*d415bd75Srobert auto Comps = getPerfectCompletions(SM, LogLen);
2312*d415bd75Srobert if (llvm::any_of(Comps, [](uint32_t P) { return P == 0; }))
2313*d415bd75Srobert return OpRef::fail();
231409467b48Spatrick
2315*d415bd75Srobert auto Pick = completeToPerfect(Comps, LogLen);
2316*d415bd75Srobert for (unsigned I = 0; I != LogLen; ++I)
2317*d415bd75Srobert Perm[I] = Log2_32(Pick[I]);
231809467b48Spatrick
231909467b48Spatrick // Once we have Perm, represent it as cycles. Denote the maximum log2
232009467b48Spatrick // (equal to log2(VecLen)-1) as M. The cycle containing M can then be
232109467b48Spatrick // written as (M a1 a2 a3 ... an). That cycle can be broken up into
232209467b48Spatrick // simple swaps as (M a1)(M a2)(M a3)...(M an), with the composition
232309467b48Spatrick // order being from left to right. Any (contiguous) segment where the
232409467b48Spatrick // values ai, ai+1...aj are either all increasing or all decreasing,
232509467b48Spatrick // can be implemented via a single vshuffvdd/vdealvdd respectively.
232609467b48Spatrick //
232709467b48Spatrick // If there is a cycle (a1 a2 ... an) that does not involve M, it can
232809467b48Spatrick // be written as (M an)(a1 a2 ... an)(M a1). The first two cycles can
232909467b48Spatrick // then be folded to get (M a1 a2 ... an)(M a1), and the above procedure
233009467b48Spatrick // can be used to generate a sequence of vshuffvdd/vdealvdd.
233109467b48Spatrick //
233209467b48Spatrick // Example:
233309467b48Spatrick // Assume M = 4 and consider a permutation (0 1)(2 3). It can be written
233409467b48Spatrick // as (4 0 1)(4 0) composed with (4 2 3)(4 2), or simply
233509467b48Spatrick // (4 0 1)(4 0)(4 2 3)(4 2).
233609467b48Spatrick // It can then be expanded into swaps as
233709467b48Spatrick // (4 0)(4 1)(4 0)(4 2)(4 3)(4 2),
233809467b48Spatrick // and broken up into "increasing" segments as
233909467b48Spatrick // [(4 0)(4 1)] [(4 0)(4 2)(4 3)] [(4 2)].
234009467b48Spatrick // This is equivalent to
234109467b48Spatrick // (4 0 1)(4 0 2 3)(4 2),
234209467b48Spatrick // which can be implemented as 3 vshufvdd instructions.
234309467b48Spatrick
234409467b48Spatrick using CycleType = SmallVector<unsigned, 8>;
234509467b48Spatrick std::set<CycleType> Cycles;
234609467b48Spatrick std::set<unsigned> All;
234709467b48Spatrick
234809467b48Spatrick for (unsigned I : Perm)
234909467b48Spatrick All.insert(I);
235009467b48Spatrick
235109467b48Spatrick // If the cycle contains LogLen-1, move it to the front of the cycle.
235209467b48Spatrick // Otherwise, return the cycle unchanged.
235309467b48Spatrick auto canonicalize = [LogLen](const CycleType &C) -> CycleType {
235409467b48Spatrick unsigned LogPos, N = C.size();
235509467b48Spatrick for (LogPos = 0; LogPos != N; ++LogPos)
235609467b48Spatrick if (C[LogPos] == LogLen - 1)
235709467b48Spatrick break;
235809467b48Spatrick if (LogPos == N)
235909467b48Spatrick return C;
236009467b48Spatrick
236109467b48Spatrick CycleType NewC(C.begin() + LogPos, C.end());
236209467b48Spatrick NewC.append(C.begin(), C.begin() + LogPos);
236309467b48Spatrick return NewC;
236409467b48Spatrick };
236509467b48Spatrick
236609467b48Spatrick auto pfs = [](const std::set<CycleType> &Cs, unsigned Len) {
236709467b48Spatrick // Ordering: shuff: 5 0 1 2 3 4, deal: 5 4 3 2 1 0 (for Log=6),
236809467b48Spatrick // for bytes zero is included, for halfwords is not.
236909467b48Spatrick if (Cs.size() != 1)
237009467b48Spatrick return 0u;
237109467b48Spatrick const CycleType &C = *Cs.begin();
237209467b48Spatrick if (C[0] != Len - 1)
237309467b48Spatrick return 0u;
237409467b48Spatrick int D = Len - C.size();
237509467b48Spatrick if (D != 0 && D != 1)
237609467b48Spatrick return 0u;
237709467b48Spatrick
237809467b48Spatrick bool IsDeal = true, IsShuff = true;
237909467b48Spatrick for (unsigned I = 1; I != Len - D; ++I) {
238009467b48Spatrick if (C[I] != Len - 1 - I)
238109467b48Spatrick IsDeal = false;
238209467b48Spatrick if (C[I] != I - (1 - D)) // I-1, I
238309467b48Spatrick IsShuff = false;
238409467b48Spatrick }
238509467b48Spatrick // At most one, IsDeal or IsShuff, can be non-zero.
238609467b48Spatrick assert(!(IsDeal || IsShuff) || IsDeal != IsShuff);
238709467b48Spatrick static unsigned Deals[] = {Hexagon::V6_vdealb, Hexagon::V6_vdealh};
238809467b48Spatrick static unsigned Shufs[] = {Hexagon::V6_vshuffb, Hexagon::V6_vshuffh};
238909467b48Spatrick return IsDeal ? Deals[D] : (IsShuff ? Shufs[D] : 0);
239009467b48Spatrick };
239109467b48Spatrick
239209467b48Spatrick while (!All.empty()) {
239309467b48Spatrick unsigned A = *All.begin();
239409467b48Spatrick All.erase(A);
239509467b48Spatrick CycleType C;
239609467b48Spatrick C.push_back(A);
239709467b48Spatrick for (unsigned B = Perm[A]; B != A; B = Perm[B]) {
239809467b48Spatrick C.push_back(B);
239909467b48Spatrick All.erase(B);
240009467b48Spatrick }
240109467b48Spatrick if (C.size() <= 1)
240209467b48Spatrick continue;
240309467b48Spatrick Cycles.insert(canonicalize(C));
240409467b48Spatrick }
240509467b48Spatrick
240609467b48Spatrick MVT SingleTy = getSingleVT(MVT::i8);
240709467b48Spatrick MVT PairTy = getPairVT(MVT::i8);
240809467b48Spatrick
240909467b48Spatrick // Recognize patterns for V6_vdeal{b,h} and V6_vshuff{b,h}.
241009467b48Spatrick if (unsigned(VecLen) == HwLen) {
241109467b48Spatrick if (unsigned SingleOpc = pfs(Cycles, LogLen)) {
241209467b48Spatrick Results.push(SingleOpc, SingleTy, {Va});
241309467b48Spatrick return OpRef::res(Results.top());
241409467b48Spatrick }
241509467b48Spatrick }
241609467b48Spatrick
241773471bf0Spatrick // From the cycles, construct the sequence of values that will
241873471bf0Spatrick // then form the control values for vdealvdd/vshuffvdd, i.e.
241973471bf0Spatrick // (M a1 a2)(M a3 a4 a5)... -> a1 a2 a3 a4 a5
242073471bf0Spatrick // This essentially strips the M value from the cycles where
242173471bf0Spatrick // it's present, and performs the insertion of M (then stripping)
242273471bf0Spatrick // for cycles without M (as described in an earlier comment).
242309467b48Spatrick SmallVector<unsigned, 8> SwapElems;
242473471bf0Spatrick // When the input is extended (i.e. single vector becomes a pair),
242573471bf0Spatrick // this is done by using an "undef" vector as the second input.
242673471bf0Spatrick // However, then we get
242773471bf0Spatrick // input 1: GOODBITS
242873471bf0Spatrick // input 2: ........
242973471bf0Spatrick // but we need
243073471bf0Spatrick // input 1: ....BITS
243173471bf0Spatrick // input 2: ....GOOD
243273471bf0Spatrick // Then at the end, this needs to be undone. To accomplish this,
243373471bf0Spatrick // artificially add "LogLen-1" at both ends of the sequence.
243473471bf0Spatrick if (!HavePairs)
243509467b48Spatrick SwapElems.push_back(LogLen - 1);
243609467b48Spatrick for (const CycleType &C : Cycles) {
243773471bf0Spatrick // Do the transformation: (a1..an) -> (M a1..an)(M a1).
243809467b48Spatrick unsigned First = (C[0] == LogLen - 1) ? 1 : 0;
243909467b48Spatrick SwapElems.append(C.begin() + First, C.end());
244009467b48Spatrick if (First == 0)
244109467b48Spatrick SwapElems.push_back(C[0]);
244209467b48Spatrick }
244373471bf0Spatrick if (!HavePairs)
244473471bf0Spatrick SwapElems.push_back(LogLen - 1);
244509467b48Spatrick
244609467b48Spatrick const SDLoc &dl(Results.InpNode);
2447*d415bd75Srobert OpRef Arg = HavePairs ? Va : concats(Va, OpRef::undef(SingleTy), Results);
244873471bf0Spatrick if (InvertedPair)
244973471bf0Spatrick Arg = concats(OpRef::hi(Arg), OpRef::lo(Arg), Results);
245009467b48Spatrick
245109467b48Spatrick for (unsigned I = 0, E = SwapElems.size(); I != E;) {
245209467b48Spatrick bool IsInc = I == E - 1 || SwapElems[I] < SwapElems[I + 1];
245309467b48Spatrick unsigned S = (1u << SwapElems[I]);
245409467b48Spatrick if (I < E - 1) {
245509467b48Spatrick while (++I < E - 1 && IsInc == (SwapElems[I] < SwapElems[I + 1]))
245609467b48Spatrick S |= 1u << SwapElems[I];
245709467b48Spatrick // The above loop will not add a bit for the final SwapElems[I+1],
245809467b48Spatrick // so add it here.
245909467b48Spatrick S |= 1u << SwapElems[I];
246009467b48Spatrick }
246109467b48Spatrick ++I;
246209467b48Spatrick
246309467b48Spatrick NodeTemplate Res;
246473471bf0Spatrick Results.push(Hexagon::A2_tfrsi, MVT::i32, {getConst32(S, dl)});
246509467b48Spatrick Res.Opc = IsInc ? Hexagon::V6_vshuffvdd : Hexagon::V6_vdealvdd;
246609467b48Spatrick Res.Ty = PairTy;
246709467b48Spatrick Res.Ops = {OpRef::hi(Arg), OpRef::lo(Arg), OpRef::res(-1)};
246809467b48Spatrick Results.push(Res);
246909467b48Spatrick Arg = OpRef::res(Results.top());
247009467b48Spatrick }
247109467b48Spatrick
247273471bf0Spatrick return HavePairs ? Arg : OpRef::lo(Arg);
247309467b48Spatrick }
247409467b48Spatrick
butterfly(ShuffleMask SM,OpRef Va,ResultStack & Results)247509467b48Spatrick OpRef HvxSelector::butterfly(ShuffleMask SM, OpRef Va, ResultStack &Results) {
247609467b48Spatrick DEBUG_WITH_TYPE("isel", {dbgs() << __func__ << '\n';});
247709467b48Spatrick // Butterfly shuffles.
247809467b48Spatrick //
247909467b48Spatrick // V6_vdelta
248009467b48Spatrick // V6_vrdelta
248109467b48Spatrick // V6_vror
248209467b48Spatrick
248309467b48Spatrick // The assumption here is that all elements picked by Mask are in the
248409467b48Spatrick // first operand to the vector_shuffle. This assumption is enforced
248509467b48Spatrick // by the caller.
248609467b48Spatrick
248709467b48Spatrick MVT ResTy = getSingleVT(MVT::i8);
248809467b48Spatrick PermNetwork::Controls FC, RC;
248909467b48Spatrick const SDLoc &dl(Results.InpNode);
249009467b48Spatrick int VecLen = SM.Mask.size();
249109467b48Spatrick
249209467b48Spatrick for (int M : SM.Mask) {
249309467b48Spatrick if (M != -1 && M >= VecLen)
249409467b48Spatrick return OpRef::fail();
249509467b48Spatrick }
249609467b48Spatrick
249709467b48Spatrick // Try the deltas/benes for both single vectors and vector pairs.
249809467b48Spatrick ForwardDeltaNetwork FN(SM.Mask);
249909467b48Spatrick if (FN.run(FC)) {
250009467b48Spatrick SDValue Ctl = getVectorConstant(FC, dl);
250109467b48Spatrick Results.push(Hexagon::V6_vdelta, ResTy, {Va, OpRef(Ctl)});
250209467b48Spatrick return OpRef::res(Results.top());
250309467b48Spatrick }
250409467b48Spatrick
250509467b48Spatrick // Try reverse delta.
250609467b48Spatrick ReverseDeltaNetwork RN(SM.Mask);
250709467b48Spatrick if (RN.run(RC)) {
250809467b48Spatrick SDValue Ctl = getVectorConstant(RC, dl);
250909467b48Spatrick Results.push(Hexagon::V6_vrdelta, ResTy, {Va, OpRef(Ctl)});
251009467b48Spatrick return OpRef::res(Results.top());
251109467b48Spatrick }
251209467b48Spatrick
251309467b48Spatrick // Do Benes.
251409467b48Spatrick BenesNetwork BN(SM.Mask);
251509467b48Spatrick if (BN.run(FC, RC)) {
251609467b48Spatrick SDValue CtlF = getVectorConstant(FC, dl);
251709467b48Spatrick SDValue CtlR = getVectorConstant(RC, dl);
251809467b48Spatrick Results.push(Hexagon::V6_vdelta, ResTy, {Va, OpRef(CtlF)});
251909467b48Spatrick Results.push(Hexagon::V6_vrdelta, ResTy,
252009467b48Spatrick {OpRef::res(-1), OpRef(CtlR)});
252109467b48Spatrick return OpRef::res(Results.top());
252209467b48Spatrick }
252309467b48Spatrick
252409467b48Spatrick return OpRef::fail();
252509467b48Spatrick }
252609467b48Spatrick
getConst32(int Val,const SDLoc & dl)252773471bf0Spatrick SDValue HvxSelector::getConst32(int Val, const SDLoc &dl) {
252873471bf0Spatrick return DAG.getTargetConstant(Val, dl, MVT::i32);
252973471bf0Spatrick }
253073471bf0Spatrick
getVectorConstant(ArrayRef<uint8_t> Data,const SDLoc & dl)253109467b48Spatrick SDValue HvxSelector::getVectorConstant(ArrayRef<uint8_t> Data,
253209467b48Spatrick const SDLoc &dl) {
253309467b48Spatrick SmallVector<SDValue, 128> Elems;
253409467b48Spatrick for (uint8_t C : Data)
253509467b48Spatrick Elems.push_back(DAG.getConstant(C, dl, MVT::i8));
253609467b48Spatrick MVT VecTy = MVT::getVectorVT(MVT::i8, Data.size());
253709467b48Spatrick SDValue BV = DAG.getBuildVector(VecTy, dl, Elems);
253809467b48Spatrick SDValue LV = Lower.LowerOperation(BV, DAG);
253909467b48Spatrick DAG.RemoveDeadNode(BV.getNode());
254073471bf0Spatrick return DAG.getNode(HexagonISD::ISEL, dl, VecTy, LV);
254109467b48Spatrick }
254209467b48Spatrick
selectExtractSubvector(SDNode * N)2543*d415bd75Srobert void HvxSelector::selectExtractSubvector(SDNode *N) {
2544*d415bd75Srobert SDValue Inp = N->getOperand(0);
2545*d415bd75Srobert MVT ResTy = N->getValueType(0).getSimpleVT();
2546*d415bd75Srobert auto IdxN = cast<ConstantSDNode>(N->getOperand(1));
2547*d415bd75Srobert unsigned Idx = IdxN->getZExtValue();
2548*d415bd75Srobert
2549*d415bd75Srobert [[maybe_unused]] MVT InpTy = Inp.getValueType().getSimpleVT();
2550*d415bd75Srobert [[maybe_unused]] unsigned ResLen = ResTy.getVectorNumElements();
2551*d415bd75Srobert assert(InpTy.getVectorElementType() == ResTy.getVectorElementType());
2552*d415bd75Srobert assert(2 * ResLen == InpTy.getVectorNumElements());
2553*d415bd75Srobert assert(Idx == 0 || Idx == ResLen);
2554*d415bd75Srobert
2555*d415bd75Srobert unsigned SubReg = Idx == 0 ? Hexagon::vsub_lo : Hexagon::vsub_hi;
2556*d415bd75Srobert SDValue Ext = DAG.getTargetExtractSubreg(SubReg, SDLoc(N), ResTy, Inp);
2557*d415bd75Srobert
2558*d415bd75Srobert ISel.ReplaceNode(N, Ext.getNode());
2559*d415bd75Srobert }
2560*d415bd75Srobert
selectShuffle(SDNode * N)256109467b48Spatrick void HvxSelector::selectShuffle(SDNode *N) {
256209467b48Spatrick DEBUG_WITH_TYPE("isel", {
256309467b48Spatrick dbgs() << "Starting " << __func__ << " on node:\n";
256409467b48Spatrick N->dump(&DAG);
256509467b48Spatrick });
256609467b48Spatrick MVT ResTy = N->getValueType(0).getSimpleVT();
256709467b48Spatrick // Assume that vector shuffles operate on vectors of bytes.
256809467b48Spatrick assert(ResTy.isVector() && ResTy.getVectorElementType() == MVT::i8);
256909467b48Spatrick
257009467b48Spatrick auto *SN = cast<ShuffleVectorSDNode>(N);
257109467b48Spatrick std::vector<int> Mask(SN->getMask().begin(), SN->getMask().end());
257209467b48Spatrick // This shouldn't really be necessary. Is it?
257309467b48Spatrick for (int &Idx : Mask)
257409467b48Spatrick if (Idx != -1 && Idx < 0)
257509467b48Spatrick Idx = -1;
257609467b48Spatrick
257709467b48Spatrick unsigned VecLen = Mask.size();
257809467b48Spatrick bool HavePairs = (2*HwLen == VecLen);
257909467b48Spatrick assert(ResTy.getSizeInBits() / 8 == VecLen);
258009467b48Spatrick
258109467b48Spatrick // Vd = vector_shuffle Va, Vb, Mask
258209467b48Spatrick //
258309467b48Spatrick
258409467b48Spatrick bool UseLeft = false, UseRight = false;
258509467b48Spatrick for (unsigned I = 0; I != VecLen; ++I) {
258609467b48Spatrick if (Mask[I] == -1)
258709467b48Spatrick continue;
258809467b48Spatrick unsigned Idx = Mask[I];
258909467b48Spatrick assert(Idx < 2*VecLen);
259009467b48Spatrick if (Idx < VecLen)
259109467b48Spatrick UseLeft = true;
259209467b48Spatrick else
259309467b48Spatrick UseRight = true;
259409467b48Spatrick }
259509467b48Spatrick
259609467b48Spatrick DEBUG_WITH_TYPE("isel", {
259709467b48Spatrick dbgs() << "VecLen=" << VecLen << " HwLen=" << HwLen << " UseLeft="
259809467b48Spatrick << UseLeft << " UseRight=" << UseRight << " HavePairs="
259909467b48Spatrick << HavePairs << '\n';
260009467b48Spatrick });
260109467b48Spatrick // If the mask is all -1's, generate "undef".
260209467b48Spatrick if (!UseLeft && !UseRight) {
260309467b48Spatrick ISel.ReplaceNode(N, ISel.selectUndef(SDLoc(SN), ResTy).getNode());
260409467b48Spatrick return;
260509467b48Spatrick }
260609467b48Spatrick
260709467b48Spatrick SDValue Vec0 = N->getOperand(0);
260809467b48Spatrick SDValue Vec1 = N->getOperand(1);
2609*d415bd75Srobert assert(Vec0.getValueType() == ResTy && Vec1.getValueType() == ResTy);
2610*d415bd75Srobert
261109467b48Spatrick ResultStack Results(SN);
2612*d415bd75Srobert OpRef Va = OpRef::undef(ResTy);
2613*d415bd75Srobert OpRef Vb = OpRef::undef(ResTy);
2614*d415bd75Srobert
2615*d415bd75Srobert if (!Vec0.isUndef()) {
261609467b48Spatrick Results.push(TargetOpcode::COPY, ResTy, {Vec0});
2617*d415bd75Srobert Va = OpRef::OpRef::res(Results.top());
2618*d415bd75Srobert }
2619*d415bd75Srobert if (!Vec1.isUndef()) {
262009467b48Spatrick Results.push(TargetOpcode::COPY, ResTy, {Vec1});
2621*d415bd75Srobert Vb = OpRef::res(Results.top());
2622*d415bd75Srobert }
262309467b48Spatrick
262409467b48Spatrick OpRef Res = !HavePairs ? shuffs2(ShuffleMask(Mask), Va, Vb, Results)
262509467b48Spatrick : shuffp2(ShuffleMask(Mask), Va, Vb, Results);
262609467b48Spatrick
262709467b48Spatrick bool Done = Res.isValid();
262809467b48Spatrick if (Done) {
262909467b48Spatrick // Make sure that Res is on the stack before materializing.
263009467b48Spatrick Results.push(TargetOpcode::COPY, ResTy, {Res});
263109467b48Spatrick materialize(Results);
263209467b48Spatrick } else {
263309467b48Spatrick Done = scalarizeShuffle(Mask, SDLoc(N), ResTy, Vec0, Vec1, N);
263409467b48Spatrick }
263509467b48Spatrick
263609467b48Spatrick if (!Done) {
263709467b48Spatrick #ifndef NDEBUG
263809467b48Spatrick dbgs() << "Unhandled shuffle:\n";
263909467b48Spatrick SN->dumpr(&DAG);
264009467b48Spatrick #endif
264109467b48Spatrick llvm_unreachable("Failed to select vector shuffle");
264209467b48Spatrick }
264309467b48Spatrick }
264409467b48Spatrick
selectRor(SDNode * N)264509467b48Spatrick void HvxSelector::selectRor(SDNode *N) {
264609467b48Spatrick // If this is a rotation by less than 8, use V6_valignbi.
264709467b48Spatrick MVT Ty = N->getValueType(0).getSimpleVT();
264809467b48Spatrick const SDLoc &dl(N);
264909467b48Spatrick SDValue VecV = N->getOperand(0);
265009467b48Spatrick SDValue RotV = N->getOperand(1);
265109467b48Spatrick SDNode *NewN = nullptr;
265209467b48Spatrick
265309467b48Spatrick if (auto *CN = dyn_cast<ConstantSDNode>(RotV.getNode())) {
265409467b48Spatrick unsigned S = CN->getZExtValue() % HST.getVectorLength();
265509467b48Spatrick if (S == 0) {
265609467b48Spatrick NewN = VecV.getNode();
265709467b48Spatrick } else if (isUInt<3>(S)) {
265809467b48Spatrick NewN = DAG.getMachineNode(Hexagon::V6_valignbi, dl, Ty,
265973471bf0Spatrick {VecV, VecV, getConst32(S, dl)});
266009467b48Spatrick }
266109467b48Spatrick }
266209467b48Spatrick
266309467b48Spatrick if (!NewN)
266409467b48Spatrick NewN = DAG.getMachineNode(Hexagon::V6_vror, dl, Ty, {VecV, RotV});
266509467b48Spatrick
266609467b48Spatrick ISel.ReplaceNode(N, NewN);
266709467b48Spatrick }
266809467b48Spatrick
selectVAlign(SDNode * N)266909467b48Spatrick void HvxSelector::selectVAlign(SDNode *N) {
267009467b48Spatrick SDValue Vv = N->getOperand(0);
267109467b48Spatrick SDValue Vu = N->getOperand(1);
267209467b48Spatrick SDValue Rt = N->getOperand(2);
267309467b48Spatrick SDNode *NewN = DAG.getMachineNode(Hexagon::V6_valignb, SDLoc(N),
267409467b48Spatrick N->getValueType(0), {Vv, Vu, Rt});
267509467b48Spatrick ISel.ReplaceNode(N, NewN);
267609467b48Spatrick DAG.RemoveDeadNode(N);
267709467b48Spatrick }
267809467b48Spatrick
PreprocessHvxISelDAG()2679*d415bd75Srobert void HexagonDAGToDAGISel::PreprocessHvxISelDAG() {
2680*d415bd75Srobert auto getNodes = [this]() -> std::vector<SDNode *> {
2681*d415bd75Srobert std::vector<SDNode *> T;
2682*d415bd75Srobert T.reserve(CurDAG->allnodes_size());
2683*d415bd75Srobert for (SDNode &N : CurDAG->allnodes())
2684*d415bd75Srobert T.push_back(&N);
2685*d415bd75Srobert return T;
2686*d415bd75Srobert };
2687*d415bd75Srobert
2688*d415bd75Srobert ppHvxShuffleOfShuffle(getNodes());
2689*d415bd75Srobert }
2690*d415bd75Srobert
2691*d415bd75Srobert template <> struct std::hash<SDValue> {
operator ()std::hash2692*d415bd75Srobert std::size_t operator()(SDValue V) const {
2693*d415bd75Srobert return std::hash<const void *>()(V.getNode()) +
2694*d415bd75Srobert std::hash<unsigned>()(V.getResNo());
2695*d415bd75Srobert };
2696*d415bd75Srobert };
2697*d415bd75Srobert
ppHvxShuffleOfShuffle(std::vector<SDNode * > && Nodes)2698*d415bd75Srobert void HexagonDAGToDAGISel::ppHvxShuffleOfShuffle(std::vector<SDNode *> &&Nodes) {
2699*d415bd75Srobert // Motivating case:
2700*d415bd75Srobert // t10: v64i32 = ...
2701*d415bd75Srobert // t46: v128i8 = vector_shuffle<...> t44, t45
2702*d415bd75Srobert // t48: v128i8 = vector_shuffle<...> t44, t45
2703*d415bd75Srobert // t42: v128i8 = vector_shuffle<...> t46, t48
2704*d415bd75Srobert // t12: v32i32 = extract_subvector t10, Constant:i32<0>
2705*d415bd75Srobert // t44: v128i8 = bitcast t12
2706*d415bd75Srobert // t15: v32i32 = extract_subvector t10, Constant:i32<32>
2707*d415bd75Srobert // t45: v128i8 = bitcast t15
2708*d415bd75Srobert SelectionDAG &DAG = *CurDAG;
2709*d415bd75Srobert unsigned HwLen = HST->getVectorLength();
2710*d415bd75Srobert
2711*d415bd75Srobert struct SubVectorInfo {
2712*d415bd75Srobert SubVectorInfo(SDValue S, unsigned H) : Src(S), HalfIdx(H) {}
2713*d415bd75Srobert SDValue Src;
2714*d415bd75Srobert unsigned HalfIdx;
2715*d415bd75Srobert };
2716*d415bd75Srobert
2717*d415bd75Srobert using MapType = std::unordered_map<SDValue, unsigned>;
2718*d415bd75Srobert
2719*d415bd75Srobert auto getMaskElt = [&](unsigned Idx, ShuffleVectorSDNode *Shuff0,
2720*d415bd75Srobert ShuffleVectorSDNode *Shuff1,
2721*d415bd75Srobert const MapType &OpMap) -> int {
2722*d415bd75Srobert // Treat Shuff0 and Shuff1 as operands to another vector shuffle, and
2723*d415bd75Srobert // Idx as a (non-undef) element of the top level shuffle's mask, that
2724*d415bd75Srobert // is, index into concat(Shuff0, Shuff1).
2725*d415bd75Srobert // Assuming that Shuff0 and Shuff1 both operate on subvectors of the
2726*d415bd75Srobert // same source vector (as described by OpMap), return the index of
2727*d415bd75Srobert // that source vector corresponding to Idx.
2728*d415bd75Srobert ShuffleVectorSDNode *OpShuff = Idx < HwLen ? Shuff0 : Shuff1;
2729*d415bd75Srobert if (Idx >= HwLen)
2730*d415bd75Srobert Idx -= HwLen;
2731*d415bd75Srobert
2732*d415bd75Srobert // Get the mask index that M points at in the corresponding operand.
2733*d415bd75Srobert int MaybeN = OpShuff->getMaskElt(Idx);
2734*d415bd75Srobert if (MaybeN < 0)
2735*d415bd75Srobert return -1;
2736*d415bd75Srobert
2737*d415bd75Srobert auto N = static_cast<unsigned>(MaybeN);
2738*d415bd75Srobert unsigned SrcBase = N < HwLen ? OpMap.at(OpShuff->getOperand(0))
2739*d415bd75Srobert : OpMap.at(OpShuff->getOperand(1));
2740*d415bd75Srobert if (N >= HwLen)
2741*d415bd75Srobert N -= HwLen;
2742*d415bd75Srobert
2743*d415bd75Srobert return N + SrcBase;
2744*d415bd75Srobert };
2745*d415bd75Srobert
2746*d415bd75Srobert auto fold3 = [&](SDValue TopShuff, SDValue Inp, MapType &&OpMap) -> SDValue {
2747*d415bd75Srobert // Fold all 3 shuffles into a single one.
2748*d415bd75Srobert auto *This = cast<ShuffleVectorSDNode>(TopShuff);
2749*d415bd75Srobert auto *S0 = cast<ShuffleVectorSDNode>(TopShuff.getOperand(0));
2750*d415bd75Srobert auto *S1 = cast<ShuffleVectorSDNode>(TopShuff.getOperand(1));
2751*d415bd75Srobert ArrayRef<int> TopMask = This->getMask();
2752*d415bd75Srobert // This should be guaranteed by type checks in the caller, and the fact
2753*d415bd75Srobert // that all shuffles should have been promoted to operate on MVT::i8.
2754*d415bd75Srobert assert(TopMask.size() == S0->getMask().size() &&
2755*d415bd75Srobert TopMask.size() == S1->getMask().size());
2756*d415bd75Srobert assert(TopMask.size() == HwLen);
2757*d415bd75Srobert
2758*d415bd75Srobert SmallVector<int, 256> FoldedMask(2 * HwLen);
2759*d415bd75Srobert for (unsigned I = 0; I != HwLen; ++I) {
2760*d415bd75Srobert int MaybeM = TopMask[I];
2761*d415bd75Srobert if (MaybeM >= 0) {
2762*d415bd75Srobert FoldedMask[I] =
2763*d415bd75Srobert getMaskElt(static_cast<unsigned>(MaybeM), S0, S1, OpMap);
2764*d415bd75Srobert } else {
2765*d415bd75Srobert FoldedMask[I] = -1;
2766*d415bd75Srobert }
2767*d415bd75Srobert }
2768*d415bd75Srobert // The second half of the result will be all-undef.
2769*d415bd75Srobert std::fill(FoldedMask.begin() + HwLen, FoldedMask.end(), -1);
2770*d415bd75Srobert
2771*d415bd75Srobert // Return
2772*d415bd75Srobert // FoldedShuffle = (Shuffle Inp, undef, FoldedMask)
2773*d415bd75Srobert // (LoHalf FoldedShuffle)
2774*d415bd75Srobert const SDLoc &dl(TopShuff);
2775*d415bd75Srobert MVT SingleTy = MVT::getVectorVT(MVT::i8, HwLen);
2776*d415bd75Srobert MVT PairTy = MVT::getVectorVT(MVT::i8, 2 * HwLen);
2777*d415bd75Srobert SDValue FoldedShuff =
2778*d415bd75Srobert DAG.getVectorShuffle(PairTy, dl, DAG.getBitcast(PairTy, Inp),
2779*d415bd75Srobert DAG.getUNDEF(PairTy), FoldedMask);
2780*d415bd75Srobert return DAG.getNode(ISD::EXTRACT_SUBVECTOR, dl, SingleTy, FoldedShuff,
2781*d415bd75Srobert DAG.getConstant(0, dl, MVT::i32));
2782*d415bd75Srobert };
2783*d415bd75Srobert
2784*d415bd75Srobert auto getSourceInfo = [](SDValue V) -> std::optional<SubVectorInfo> {
2785*d415bd75Srobert while (V.getOpcode() == ISD::BITCAST)
2786*d415bd75Srobert V = V.getOperand(0);
2787*d415bd75Srobert if (V.getOpcode() != ISD::EXTRACT_SUBVECTOR)
2788*d415bd75Srobert return std::nullopt;
2789*d415bd75Srobert return SubVectorInfo(V.getOperand(0),
2790*d415bd75Srobert !cast<ConstantSDNode>(V.getOperand(1))->isZero());
2791*d415bd75Srobert };
2792*d415bd75Srobert
2793*d415bd75Srobert for (SDNode *N : Nodes) {
2794*d415bd75Srobert if (N->getOpcode() != ISD::VECTOR_SHUFFLE)
2795*d415bd75Srobert continue;
2796*d415bd75Srobert EVT ResTy = N->getValueType(0);
2797*d415bd75Srobert if (ResTy.getVectorElementType() != MVT::i8)
2798*d415bd75Srobert continue;
2799*d415bd75Srobert if (ResTy.getVectorNumElements() != HwLen)
2800*d415bd75Srobert continue;
2801*d415bd75Srobert
2802*d415bd75Srobert SDValue V0 = N->getOperand(0);
2803*d415bd75Srobert SDValue V1 = N->getOperand(1);
2804*d415bd75Srobert if (V0.getOpcode() != ISD::VECTOR_SHUFFLE)
2805*d415bd75Srobert continue;
2806*d415bd75Srobert if (V1.getOpcode() != ISD::VECTOR_SHUFFLE)
2807*d415bd75Srobert continue;
2808*d415bd75Srobert if (V0.getValueType() != ResTy || V1.getValueType() != ResTy)
2809*d415bd75Srobert continue;
2810*d415bd75Srobert
2811*d415bd75Srobert // Check if all operands of the two operand shuffles are extract_subvectors
2812*d415bd75Srobert // from the same vector pair.
2813*d415bd75Srobert auto V0A = getSourceInfo(V0.getOperand(0));
2814*d415bd75Srobert if (!V0A.has_value())
2815*d415bd75Srobert continue;
2816*d415bd75Srobert auto V0B = getSourceInfo(V0.getOperand(1));
2817*d415bd75Srobert if (!V0B.has_value() || V0B->Src != V0A->Src)
2818*d415bd75Srobert continue;
2819*d415bd75Srobert auto V1A = getSourceInfo(V1.getOperand(0));
2820*d415bd75Srobert if (!V1A.has_value() || V1A->Src != V0A->Src)
2821*d415bd75Srobert continue;
2822*d415bd75Srobert auto V1B = getSourceInfo(V1.getOperand(1));
2823*d415bd75Srobert if (!V1B.has_value() || V1B->Src != V0A->Src)
2824*d415bd75Srobert continue;
2825*d415bd75Srobert
2826*d415bd75Srobert // The source must be a pair. This should be guaranteed here,
2827*d415bd75Srobert // but check just in case.
2828*d415bd75Srobert assert(V0A->Src.getValueType().getSizeInBits() == 16 * HwLen);
2829*d415bd75Srobert
2830*d415bd75Srobert MapType OpMap = {
2831*d415bd75Srobert {V0.getOperand(0), V0A->HalfIdx * HwLen},
2832*d415bd75Srobert {V0.getOperand(1), V0B->HalfIdx * HwLen},
2833*d415bd75Srobert {V1.getOperand(0), V1A->HalfIdx * HwLen},
2834*d415bd75Srobert {V1.getOperand(1), V1B->HalfIdx * HwLen},
2835*d415bd75Srobert };
2836*d415bd75Srobert SDValue NewS = fold3(SDValue(N, 0), V0A->Src, std::move(OpMap));
2837*d415bd75Srobert ReplaceNode(N, NewS.getNode());
2838*d415bd75Srobert }
2839*d415bd75Srobert }
2840*d415bd75Srobert
SelectHvxExtractSubvector(SDNode * N)2841*d415bd75Srobert void HexagonDAGToDAGISel::SelectHvxExtractSubvector(SDNode *N) {
2842*d415bd75Srobert HvxSelector(*this, *CurDAG).selectExtractSubvector(N);
2843*d415bd75Srobert }
2844*d415bd75Srobert
SelectHvxShuffle(SDNode * N)284509467b48Spatrick void HexagonDAGToDAGISel::SelectHvxShuffle(SDNode *N) {
284609467b48Spatrick HvxSelector(*this, *CurDAG).selectShuffle(N);
284709467b48Spatrick }
284809467b48Spatrick
SelectHvxRor(SDNode * N)284909467b48Spatrick void HexagonDAGToDAGISel::SelectHvxRor(SDNode *N) {
285009467b48Spatrick HvxSelector(*this, *CurDAG).selectRor(N);
285109467b48Spatrick }
285209467b48Spatrick
SelectHvxVAlign(SDNode * N)285309467b48Spatrick void HexagonDAGToDAGISel::SelectHvxVAlign(SDNode *N) {
285409467b48Spatrick HvxSelector(*this, *CurDAG).selectVAlign(N);
285509467b48Spatrick }
285609467b48Spatrick
SelectV65GatherPred(SDNode * N)285709467b48Spatrick void HexagonDAGToDAGISel::SelectV65GatherPred(SDNode *N) {
285809467b48Spatrick const SDLoc &dl(N);
285909467b48Spatrick SDValue Chain = N->getOperand(0);
286009467b48Spatrick SDValue Address = N->getOperand(2);
286109467b48Spatrick SDValue Predicate = N->getOperand(3);
286209467b48Spatrick SDValue Base = N->getOperand(4);
286309467b48Spatrick SDValue Modifier = N->getOperand(5);
286409467b48Spatrick SDValue Offset = N->getOperand(6);
2865*d415bd75Srobert SDValue ImmOperand = CurDAG->getTargetConstant(0, dl, MVT::i32);
286609467b48Spatrick
286709467b48Spatrick unsigned Opcode;
286809467b48Spatrick unsigned IntNo = cast<ConstantSDNode>(N->getOperand(1))->getZExtValue();
286909467b48Spatrick switch (IntNo) {
287009467b48Spatrick default:
287109467b48Spatrick llvm_unreachable("Unexpected HVX gather intrinsic.");
287209467b48Spatrick case Intrinsic::hexagon_V6_vgathermhq:
287309467b48Spatrick case Intrinsic::hexagon_V6_vgathermhq_128B:
287409467b48Spatrick Opcode = Hexagon::V6_vgathermhq_pseudo;
287509467b48Spatrick break;
287609467b48Spatrick case Intrinsic::hexagon_V6_vgathermwq:
287709467b48Spatrick case Intrinsic::hexagon_V6_vgathermwq_128B:
287809467b48Spatrick Opcode = Hexagon::V6_vgathermwq_pseudo;
287909467b48Spatrick break;
288009467b48Spatrick case Intrinsic::hexagon_V6_vgathermhwq:
288109467b48Spatrick case Intrinsic::hexagon_V6_vgathermhwq_128B:
288209467b48Spatrick Opcode = Hexagon::V6_vgathermhwq_pseudo;
288309467b48Spatrick break;
288409467b48Spatrick }
288509467b48Spatrick
288609467b48Spatrick SDVTList VTs = CurDAG->getVTList(MVT::Other);
2887*d415bd75Srobert SDValue Ops[] = { Address, ImmOperand,
2888*d415bd75Srobert Predicate, Base, Modifier, Offset, Chain };
288909467b48Spatrick SDNode *Result = CurDAG->getMachineNode(Opcode, dl, VTs, Ops);
289009467b48Spatrick
289109467b48Spatrick MachineMemOperand *MemOp = cast<MemIntrinsicSDNode>(N)->getMemOperand();
289209467b48Spatrick CurDAG->setNodeMemRefs(cast<MachineSDNode>(Result), {MemOp});
289309467b48Spatrick
289409467b48Spatrick ReplaceNode(N, Result);
289509467b48Spatrick }
289609467b48Spatrick
SelectV65Gather(SDNode * N)289709467b48Spatrick void HexagonDAGToDAGISel::SelectV65Gather(SDNode *N) {
289809467b48Spatrick const SDLoc &dl(N);
289909467b48Spatrick SDValue Chain = N->getOperand(0);
290009467b48Spatrick SDValue Address = N->getOperand(2);
290109467b48Spatrick SDValue Base = N->getOperand(3);
290209467b48Spatrick SDValue Modifier = N->getOperand(4);
290309467b48Spatrick SDValue Offset = N->getOperand(5);
2904*d415bd75Srobert SDValue ImmOperand = CurDAG->getTargetConstant(0, dl, MVT::i32);
290509467b48Spatrick
290609467b48Spatrick unsigned Opcode;
290709467b48Spatrick unsigned IntNo = cast<ConstantSDNode>(N->getOperand(1))->getZExtValue();
290809467b48Spatrick switch (IntNo) {
290909467b48Spatrick default:
291009467b48Spatrick llvm_unreachable("Unexpected HVX gather intrinsic.");
291109467b48Spatrick case Intrinsic::hexagon_V6_vgathermh:
291209467b48Spatrick case Intrinsic::hexagon_V6_vgathermh_128B:
291309467b48Spatrick Opcode = Hexagon::V6_vgathermh_pseudo;
291409467b48Spatrick break;
291509467b48Spatrick case Intrinsic::hexagon_V6_vgathermw:
291609467b48Spatrick case Intrinsic::hexagon_V6_vgathermw_128B:
291709467b48Spatrick Opcode = Hexagon::V6_vgathermw_pseudo;
291809467b48Spatrick break;
291909467b48Spatrick case Intrinsic::hexagon_V6_vgathermhw:
292009467b48Spatrick case Intrinsic::hexagon_V6_vgathermhw_128B:
292109467b48Spatrick Opcode = Hexagon::V6_vgathermhw_pseudo;
292209467b48Spatrick break;
292309467b48Spatrick }
292409467b48Spatrick
292509467b48Spatrick SDVTList VTs = CurDAG->getVTList(MVT::Other);
2926*d415bd75Srobert SDValue Ops[] = { Address, ImmOperand, Base, Modifier, Offset, Chain };
292709467b48Spatrick SDNode *Result = CurDAG->getMachineNode(Opcode, dl, VTs, Ops);
292809467b48Spatrick
292909467b48Spatrick MachineMemOperand *MemOp = cast<MemIntrinsicSDNode>(N)->getMemOperand();
293009467b48Spatrick CurDAG->setNodeMemRefs(cast<MachineSDNode>(Result), {MemOp});
293109467b48Spatrick
293209467b48Spatrick ReplaceNode(N, Result);
293309467b48Spatrick }
293409467b48Spatrick
SelectHVXDualOutput(SDNode * N)293509467b48Spatrick void HexagonDAGToDAGISel::SelectHVXDualOutput(SDNode *N) {
293609467b48Spatrick unsigned IID = cast<ConstantSDNode>(N->getOperand(0))->getZExtValue();
293709467b48Spatrick SDNode *Result;
293809467b48Spatrick switch (IID) {
293909467b48Spatrick case Intrinsic::hexagon_V6_vaddcarry: {
2940097a140dSpatrick std::array<SDValue, 3> Ops = {
2941097a140dSpatrick {N->getOperand(1), N->getOperand(2), N->getOperand(3)}};
2942097a140dSpatrick SDVTList VTs = CurDAG->getVTList(MVT::v16i32, MVT::v64i1);
294309467b48Spatrick Result = CurDAG->getMachineNode(Hexagon::V6_vaddcarry, SDLoc(N), VTs, Ops);
294409467b48Spatrick break;
294509467b48Spatrick }
294609467b48Spatrick case Intrinsic::hexagon_V6_vaddcarry_128B: {
2947097a140dSpatrick std::array<SDValue, 3> Ops = {
2948097a140dSpatrick {N->getOperand(1), N->getOperand(2), N->getOperand(3)}};
2949097a140dSpatrick SDVTList VTs = CurDAG->getVTList(MVT::v32i32, MVT::v128i1);
295009467b48Spatrick Result = CurDAG->getMachineNode(Hexagon::V6_vaddcarry, SDLoc(N), VTs, Ops);
295109467b48Spatrick break;
295209467b48Spatrick }
295309467b48Spatrick case Intrinsic::hexagon_V6_vsubcarry: {
2954097a140dSpatrick std::array<SDValue, 3> Ops = {
2955097a140dSpatrick {N->getOperand(1), N->getOperand(2), N->getOperand(3)}};
2956097a140dSpatrick SDVTList VTs = CurDAG->getVTList(MVT::v16i32, MVT::v64i1);
295709467b48Spatrick Result = CurDAG->getMachineNode(Hexagon::V6_vsubcarry, SDLoc(N), VTs, Ops);
295809467b48Spatrick break;
295909467b48Spatrick }
296009467b48Spatrick case Intrinsic::hexagon_V6_vsubcarry_128B: {
2961097a140dSpatrick std::array<SDValue, 3> Ops = {
2962097a140dSpatrick {N->getOperand(1), N->getOperand(2), N->getOperand(3)}};
2963097a140dSpatrick SDVTList VTs = CurDAG->getVTList(MVT::v32i32, MVT::v128i1);
296409467b48Spatrick Result = CurDAG->getMachineNode(Hexagon::V6_vsubcarry, SDLoc(N), VTs, Ops);
296509467b48Spatrick break;
296609467b48Spatrick }
296709467b48Spatrick default:
296809467b48Spatrick llvm_unreachable("Unexpected HVX dual output intrinsic.");
296909467b48Spatrick }
297009467b48Spatrick ReplaceUses(N, Result);
297109467b48Spatrick ReplaceUses(SDValue(N, 0), SDValue(Result, 0));
297209467b48Spatrick ReplaceUses(SDValue(N, 1), SDValue(Result, 1));
297309467b48Spatrick CurDAG->RemoveDeadNode(N);
297409467b48Spatrick }
2975