106f32e7eSjoerg //===-- HexagonISelDAGToDAGHVX.cpp ----------------------------------------===//
206f32e7eSjoerg //
306f32e7eSjoerg // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
406f32e7eSjoerg // See https://llvm.org/LICENSE.txt for license information.
506f32e7eSjoerg // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
606f32e7eSjoerg //
706f32e7eSjoerg //===----------------------------------------------------------------------===//
806f32e7eSjoerg
906f32e7eSjoerg #include "Hexagon.h"
1006f32e7eSjoerg #include "HexagonISelDAGToDAG.h"
1106f32e7eSjoerg #include "HexagonISelLowering.h"
1206f32e7eSjoerg #include "HexagonTargetMachine.h"
1306f32e7eSjoerg #include "llvm/ADT/SetVector.h"
1406f32e7eSjoerg #include "llvm/CodeGen/MachineInstrBuilder.h"
1506f32e7eSjoerg #include "llvm/CodeGen/SelectionDAGISel.h"
1606f32e7eSjoerg #include "llvm/IR/Intrinsics.h"
17*da58b97aSjoerg #include "llvm/IR/IntrinsicsHexagon.h"
1806f32e7eSjoerg #include "llvm/Support/CommandLine.h"
1906f32e7eSjoerg #include "llvm/Support/Debug.h"
2006f32e7eSjoerg
2106f32e7eSjoerg #include <deque>
2206f32e7eSjoerg #include <map>
2306f32e7eSjoerg #include <set>
2406f32e7eSjoerg #include <utility>
2506f32e7eSjoerg #include <vector>
2606f32e7eSjoerg
2706f32e7eSjoerg #define DEBUG_TYPE "hexagon-isel"
2806f32e7eSjoerg
2906f32e7eSjoerg using namespace llvm;
3006f32e7eSjoerg
3106f32e7eSjoerg namespace {
3206f32e7eSjoerg
3306f32e7eSjoerg // --------------------------------------------------------------------
3406f32e7eSjoerg // Implementation of permutation networks.
3506f32e7eSjoerg
3606f32e7eSjoerg // Implementation of the node routing through butterfly networks:
3706f32e7eSjoerg // - Forward delta.
3806f32e7eSjoerg // - Reverse delta.
3906f32e7eSjoerg // - Benes.
4006f32e7eSjoerg //
4106f32e7eSjoerg //
4206f32e7eSjoerg // Forward delta network consists of log(N) steps, where N is the number
4306f32e7eSjoerg // of inputs. In each step, an input can stay in place, or it can get
4406f32e7eSjoerg // routed to another position[1]. The step after that consists of two
4506f32e7eSjoerg // networks, each half in size in terms of the number of nodes. In those
4606f32e7eSjoerg // terms, in the given step, an input can go to either the upper or the
4706f32e7eSjoerg // lower network in the next step.
4806f32e7eSjoerg //
4906f32e7eSjoerg // [1] Hexagon's vdelta/vrdelta allow an element to be routed to both
5006f32e7eSjoerg // positions as long as there is no conflict.
5106f32e7eSjoerg
5206f32e7eSjoerg // Here's a delta network for 8 inputs, only the switching routes are
5306f32e7eSjoerg // shown:
5406f32e7eSjoerg //
5506f32e7eSjoerg // Steps:
5606f32e7eSjoerg // |- 1 ---------------|- 2 -----|- 3 -|
5706f32e7eSjoerg //
5806f32e7eSjoerg // Inp[0] *** *** *** *** Out[0]
5906f32e7eSjoerg // \ / \ / \ /
6006f32e7eSjoerg // \ / \ / X
6106f32e7eSjoerg // \ / \ / / \
6206f32e7eSjoerg // Inp[1] *** \ / *** X *** *** Out[1]
6306f32e7eSjoerg // \ \ / / \ / \ /
6406f32e7eSjoerg // \ \ / / X X
6506f32e7eSjoerg // \ \ / / / \ / \
6606f32e7eSjoerg // Inp[2] *** \ \ / / *** X *** *** Out[2]
6706f32e7eSjoerg // \ \ X / / / \ \ /
6806f32e7eSjoerg // \ \ / \ / / / \ X
6906f32e7eSjoerg // \ X X / / \ / \
7006f32e7eSjoerg // Inp[3] *** \ / \ / \ / *** *** *** Out[3]
7106f32e7eSjoerg // \ X X X /
7206f32e7eSjoerg // \ / \ / \ / \ /
7306f32e7eSjoerg // X X X X
7406f32e7eSjoerg // / \ / \ / \ / \
7506f32e7eSjoerg // / X X X \
7606f32e7eSjoerg // Inp[4] *** / \ / \ / \ *** *** *** Out[4]
7706f32e7eSjoerg // / X X \ \ / \ /
7806f32e7eSjoerg // / / \ / \ \ \ / X
7906f32e7eSjoerg // / / X \ \ \ / / \
8006f32e7eSjoerg // Inp[5] *** / / \ \ *** X *** *** Out[5]
8106f32e7eSjoerg // / / \ \ \ / \ /
8206f32e7eSjoerg // / / \ \ X X
8306f32e7eSjoerg // / / \ \ / \ / \
8406f32e7eSjoerg // Inp[6] *** / \ *** X *** *** Out[6]
8506f32e7eSjoerg // / \ / \ \ /
8606f32e7eSjoerg // / \ / \ X
8706f32e7eSjoerg // / \ / \ / \
8806f32e7eSjoerg // Inp[7] *** *** *** *** Out[7]
8906f32e7eSjoerg //
9006f32e7eSjoerg //
9106f32e7eSjoerg // Reverse delta network is same as delta network, with the steps in
9206f32e7eSjoerg // the opposite order.
9306f32e7eSjoerg //
9406f32e7eSjoerg //
9506f32e7eSjoerg // Benes network is a forward delta network immediately followed by
9606f32e7eSjoerg // a reverse delta network.
9706f32e7eSjoerg
9806f32e7eSjoerg enum class ColorKind { None, Red, Black };
9906f32e7eSjoerg
10006f32e7eSjoerg // Graph coloring utility used to partition nodes into two groups:
10106f32e7eSjoerg // they will correspond to nodes routed to the upper and lower networks.
10206f32e7eSjoerg struct Coloring {
10306f32e7eSjoerg using Node = int;
10406f32e7eSjoerg using MapType = std::map<Node, ColorKind>;
10506f32e7eSjoerg static constexpr Node Ignore = Node(-1);
10606f32e7eSjoerg
Coloring__anon7c13adc80111::Coloring10706f32e7eSjoerg Coloring(ArrayRef<Node> Ord) : Order(Ord) {
10806f32e7eSjoerg build();
10906f32e7eSjoerg if (!color())
11006f32e7eSjoerg Colors.clear();
11106f32e7eSjoerg }
11206f32e7eSjoerg
colors__anon7c13adc80111::Coloring11306f32e7eSjoerg const MapType &colors() const {
11406f32e7eSjoerg return Colors;
11506f32e7eSjoerg }
11606f32e7eSjoerg
other__anon7c13adc80111::Coloring11706f32e7eSjoerg ColorKind other(ColorKind Color) {
11806f32e7eSjoerg if (Color == ColorKind::None)
11906f32e7eSjoerg return ColorKind::Red;
12006f32e7eSjoerg return Color == ColorKind::Red ? ColorKind::Black : ColorKind::Red;
12106f32e7eSjoerg }
12206f32e7eSjoerg
12306f32e7eSjoerg LLVM_DUMP_METHOD void dump() const;
12406f32e7eSjoerg
12506f32e7eSjoerg private:
12606f32e7eSjoerg ArrayRef<Node> Order;
12706f32e7eSjoerg MapType Colors;
12806f32e7eSjoerg std::set<Node> Needed;
12906f32e7eSjoerg
13006f32e7eSjoerg using NodeSet = std::set<Node>;
13106f32e7eSjoerg std::map<Node,NodeSet> Edges;
13206f32e7eSjoerg
conj__anon7c13adc80111::Coloring13306f32e7eSjoerg Node conj(Node Pos) {
13406f32e7eSjoerg Node Num = Order.size();
13506f32e7eSjoerg return (Pos < Num/2) ? Pos + Num/2 : Pos - Num/2;
13606f32e7eSjoerg }
13706f32e7eSjoerg
getColor__anon7c13adc80111::Coloring13806f32e7eSjoerg ColorKind getColor(Node N) {
13906f32e7eSjoerg auto F = Colors.find(N);
14006f32e7eSjoerg return F != Colors.end() ? F->second : ColorKind::None;
14106f32e7eSjoerg }
14206f32e7eSjoerg
14306f32e7eSjoerg std::pair<bool, ColorKind> getUniqueColor(const NodeSet &Nodes);
14406f32e7eSjoerg
14506f32e7eSjoerg void build();
14606f32e7eSjoerg bool color();
14706f32e7eSjoerg };
14806f32e7eSjoerg } // namespace
14906f32e7eSjoerg
getUniqueColor(const NodeSet & Nodes)15006f32e7eSjoerg std::pair<bool, ColorKind> Coloring::getUniqueColor(const NodeSet &Nodes) {
15106f32e7eSjoerg auto Color = ColorKind::None;
15206f32e7eSjoerg for (Node N : Nodes) {
15306f32e7eSjoerg ColorKind ColorN = getColor(N);
15406f32e7eSjoerg if (ColorN == ColorKind::None)
15506f32e7eSjoerg continue;
15606f32e7eSjoerg if (Color == ColorKind::None)
15706f32e7eSjoerg Color = ColorN;
15806f32e7eSjoerg else if (Color != ColorKind::None && Color != ColorN)
15906f32e7eSjoerg return { false, ColorKind::None };
16006f32e7eSjoerg }
16106f32e7eSjoerg return { true, Color };
16206f32e7eSjoerg }
16306f32e7eSjoerg
build()16406f32e7eSjoerg void Coloring::build() {
16506f32e7eSjoerg // Add Order[P] and Order[conj(P)] to Edges.
16606f32e7eSjoerg for (unsigned P = 0; P != Order.size(); ++P) {
16706f32e7eSjoerg Node I = Order[P];
16806f32e7eSjoerg if (I != Ignore) {
16906f32e7eSjoerg Needed.insert(I);
17006f32e7eSjoerg Node PC = Order[conj(P)];
17106f32e7eSjoerg if (PC != Ignore && PC != I)
17206f32e7eSjoerg Edges[I].insert(PC);
17306f32e7eSjoerg }
17406f32e7eSjoerg }
17506f32e7eSjoerg // Add I and conj(I) to Edges.
17606f32e7eSjoerg for (unsigned I = 0; I != Order.size(); ++I) {
17706f32e7eSjoerg if (!Needed.count(I))
17806f32e7eSjoerg continue;
17906f32e7eSjoerg Node C = conj(I);
18006f32e7eSjoerg // This will create an entry in the edge table, even if I is not
18106f32e7eSjoerg // connected to any other node. This is necessary, because it still
18206f32e7eSjoerg // needs to be colored.
18306f32e7eSjoerg NodeSet &Is = Edges[I];
18406f32e7eSjoerg if (Needed.count(C))
18506f32e7eSjoerg Is.insert(C);
18606f32e7eSjoerg }
18706f32e7eSjoerg }
18806f32e7eSjoerg
color()18906f32e7eSjoerg bool Coloring::color() {
19006f32e7eSjoerg SetVector<Node> FirstQ;
19106f32e7eSjoerg auto Enqueue = [this,&FirstQ] (Node N) {
19206f32e7eSjoerg SetVector<Node> Q;
19306f32e7eSjoerg Q.insert(N);
19406f32e7eSjoerg for (unsigned I = 0; I != Q.size(); ++I) {
19506f32e7eSjoerg NodeSet &Ns = Edges[Q[I]];
19606f32e7eSjoerg Q.insert(Ns.begin(), Ns.end());
19706f32e7eSjoerg }
19806f32e7eSjoerg FirstQ.insert(Q.begin(), Q.end());
19906f32e7eSjoerg };
20006f32e7eSjoerg for (Node N : Needed)
20106f32e7eSjoerg Enqueue(N);
20206f32e7eSjoerg
20306f32e7eSjoerg for (Node N : FirstQ) {
20406f32e7eSjoerg if (Colors.count(N))
20506f32e7eSjoerg continue;
20606f32e7eSjoerg NodeSet &Ns = Edges[N];
20706f32e7eSjoerg auto P = getUniqueColor(Ns);
20806f32e7eSjoerg if (!P.first)
20906f32e7eSjoerg return false;
21006f32e7eSjoerg Colors[N] = other(P.second);
21106f32e7eSjoerg }
21206f32e7eSjoerg
21306f32e7eSjoerg // First, color nodes that don't have any dups.
21406f32e7eSjoerg for (auto E : Edges) {
21506f32e7eSjoerg Node N = E.first;
21606f32e7eSjoerg if (!Needed.count(conj(N)) || Colors.count(N))
21706f32e7eSjoerg continue;
21806f32e7eSjoerg auto P = getUniqueColor(E.second);
21906f32e7eSjoerg if (!P.first)
22006f32e7eSjoerg return false;
22106f32e7eSjoerg Colors[N] = other(P.second);
22206f32e7eSjoerg }
22306f32e7eSjoerg
22406f32e7eSjoerg // Now, nodes that are still uncolored. Since the graph can be modified
22506f32e7eSjoerg // in this step, create a work queue.
22606f32e7eSjoerg std::vector<Node> WorkQ;
22706f32e7eSjoerg for (auto E : Edges) {
22806f32e7eSjoerg Node N = E.first;
22906f32e7eSjoerg if (!Colors.count(N))
23006f32e7eSjoerg WorkQ.push_back(N);
23106f32e7eSjoerg }
23206f32e7eSjoerg
23306f32e7eSjoerg for (unsigned I = 0; I < WorkQ.size(); ++I) {
23406f32e7eSjoerg Node N = WorkQ[I];
23506f32e7eSjoerg NodeSet &Ns = Edges[N];
23606f32e7eSjoerg auto P = getUniqueColor(Ns);
23706f32e7eSjoerg if (P.first) {
23806f32e7eSjoerg Colors[N] = other(P.second);
23906f32e7eSjoerg continue;
24006f32e7eSjoerg }
24106f32e7eSjoerg
24206f32e7eSjoerg // Coloring failed. Split this node.
24306f32e7eSjoerg Node C = conj(N);
24406f32e7eSjoerg ColorKind ColorN = other(ColorKind::None);
24506f32e7eSjoerg ColorKind ColorC = other(ColorN);
24606f32e7eSjoerg NodeSet &Cs = Edges[C];
24706f32e7eSjoerg NodeSet CopyNs = Ns;
24806f32e7eSjoerg for (Node M : CopyNs) {
24906f32e7eSjoerg ColorKind ColorM = getColor(M);
25006f32e7eSjoerg if (ColorM == ColorC) {
25106f32e7eSjoerg // Connect M with C, disconnect M from N.
25206f32e7eSjoerg Cs.insert(M);
25306f32e7eSjoerg Edges[M].insert(C);
25406f32e7eSjoerg Ns.erase(M);
25506f32e7eSjoerg Edges[M].erase(N);
25606f32e7eSjoerg }
25706f32e7eSjoerg }
25806f32e7eSjoerg Colors[N] = ColorN;
25906f32e7eSjoerg Colors[C] = ColorC;
26006f32e7eSjoerg }
26106f32e7eSjoerg
26206f32e7eSjoerg // Explicitly assign "None" to all uncolored nodes.
26306f32e7eSjoerg for (unsigned I = 0; I != Order.size(); ++I)
26406f32e7eSjoerg if (Colors.count(I) == 0)
26506f32e7eSjoerg Colors[I] = ColorKind::None;
26606f32e7eSjoerg
26706f32e7eSjoerg return true;
26806f32e7eSjoerg }
26906f32e7eSjoerg
27006f32e7eSjoerg #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
dump() const27106f32e7eSjoerg void Coloring::dump() const {
27206f32e7eSjoerg dbgs() << "{ Order: {";
27306f32e7eSjoerg for (unsigned I = 0; I != Order.size(); ++I) {
27406f32e7eSjoerg Node P = Order[I];
27506f32e7eSjoerg if (P != Ignore)
27606f32e7eSjoerg dbgs() << ' ' << P;
27706f32e7eSjoerg else
27806f32e7eSjoerg dbgs() << " -";
27906f32e7eSjoerg }
28006f32e7eSjoerg dbgs() << " }\n";
28106f32e7eSjoerg dbgs() << " Needed: {";
28206f32e7eSjoerg for (Node N : Needed)
28306f32e7eSjoerg dbgs() << ' ' << N;
28406f32e7eSjoerg dbgs() << " }\n";
28506f32e7eSjoerg
28606f32e7eSjoerg dbgs() << " Edges: {\n";
28706f32e7eSjoerg for (auto E : Edges) {
28806f32e7eSjoerg dbgs() << " " << E.first << " -> {";
28906f32e7eSjoerg for (auto N : E.second)
29006f32e7eSjoerg dbgs() << ' ' << N;
29106f32e7eSjoerg dbgs() << " }\n";
29206f32e7eSjoerg }
29306f32e7eSjoerg dbgs() << " }\n";
29406f32e7eSjoerg
29506f32e7eSjoerg auto ColorKindToName = [](ColorKind C) {
29606f32e7eSjoerg switch (C) {
29706f32e7eSjoerg case ColorKind::None:
29806f32e7eSjoerg return "None";
29906f32e7eSjoerg case ColorKind::Red:
30006f32e7eSjoerg return "Red";
30106f32e7eSjoerg case ColorKind::Black:
30206f32e7eSjoerg return "Black";
30306f32e7eSjoerg }
30406f32e7eSjoerg llvm_unreachable("all ColorKinds should be handled by the switch above");
30506f32e7eSjoerg };
30606f32e7eSjoerg
30706f32e7eSjoerg dbgs() << " Colors: {\n";
30806f32e7eSjoerg for (auto C : Colors)
30906f32e7eSjoerg dbgs() << " " << C.first << " -> " << ColorKindToName(C.second) << "\n";
31006f32e7eSjoerg dbgs() << " }\n}\n";
31106f32e7eSjoerg }
31206f32e7eSjoerg #endif
31306f32e7eSjoerg
31406f32e7eSjoerg namespace {
31506f32e7eSjoerg // Base class of for reordering networks. They don't strictly need to be
31606f32e7eSjoerg // permutations, as outputs with repeated occurrences of an input element
31706f32e7eSjoerg // are allowed.
31806f32e7eSjoerg struct PermNetwork {
31906f32e7eSjoerg using Controls = std::vector<uint8_t>;
32006f32e7eSjoerg using ElemType = int;
32106f32e7eSjoerg static constexpr ElemType Ignore = ElemType(-1);
32206f32e7eSjoerg
32306f32e7eSjoerg enum : uint8_t {
32406f32e7eSjoerg None,
32506f32e7eSjoerg Pass,
32606f32e7eSjoerg Switch
32706f32e7eSjoerg };
32806f32e7eSjoerg enum : uint8_t {
32906f32e7eSjoerg Forward,
33006f32e7eSjoerg Reverse
33106f32e7eSjoerg };
33206f32e7eSjoerg
PermNetwork__anon7c13adc80411::PermNetwork33306f32e7eSjoerg PermNetwork(ArrayRef<ElemType> Ord, unsigned Mult = 1) {
33406f32e7eSjoerg Order.assign(Ord.data(), Ord.data()+Ord.size());
33506f32e7eSjoerg Log = 0;
33606f32e7eSjoerg
33706f32e7eSjoerg unsigned S = Order.size();
33806f32e7eSjoerg while (S >>= 1)
33906f32e7eSjoerg ++Log;
34006f32e7eSjoerg
34106f32e7eSjoerg Table.resize(Order.size());
34206f32e7eSjoerg for (RowType &Row : Table)
34306f32e7eSjoerg Row.resize(Mult*Log, None);
34406f32e7eSjoerg }
34506f32e7eSjoerg
getControls__anon7c13adc80411::PermNetwork34606f32e7eSjoerg void getControls(Controls &V, unsigned StartAt, uint8_t Dir) const {
34706f32e7eSjoerg unsigned Size = Order.size();
34806f32e7eSjoerg V.resize(Size);
34906f32e7eSjoerg for (unsigned I = 0; I != Size; ++I) {
35006f32e7eSjoerg unsigned W = 0;
35106f32e7eSjoerg for (unsigned L = 0; L != Log; ++L) {
35206f32e7eSjoerg unsigned C = ctl(I, StartAt+L) == Switch;
35306f32e7eSjoerg if (Dir == Forward)
35406f32e7eSjoerg W |= C << (Log-1-L);
35506f32e7eSjoerg else
35606f32e7eSjoerg W |= C << L;
35706f32e7eSjoerg }
35806f32e7eSjoerg assert(isUInt<8>(W));
35906f32e7eSjoerg V[I] = uint8_t(W);
36006f32e7eSjoerg }
36106f32e7eSjoerg }
36206f32e7eSjoerg
ctl__anon7c13adc80411::PermNetwork36306f32e7eSjoerg uint8_t ctl(ElemType Pos, unsigned Step) const {
36406f32e7eSjoerg return Table[Pos][Step];
36506f32e7eSjoerg }
size__anon7c13adc80411::PermNetwork36606f32e7eSjoerg unsigned size() const {
36706f32e7eSjoerg return Order.size();
36806f32e7eSjoerg }
steps__anon7c13adc80411::PermNetwork36906f32e7eSjoerg unsigned steps() const {
37006f32e7eSjoerg return Log;
37106f32e7eSjoerg }
37206f32e7eSjoerg
37306f32e7eSjoerg protected:
37406f32e7eSjoerg unsigned Log;
37506f32e7eSjoerg std::vector<ElemType> Order;
37606f32e7eSjoerg using RowType = std::vector<uint8_t>;
37706f32e7eSjoerg std::vector<RowType> Table;
37806f32e7eSjoerg };
37906f32e7eSjoerg
38006f32e7eSjoerg struct ForwardDeltaNetwork : public PermNetwork {
ForwardDeltaNetwork__anon7c13adc80411::ForwardDeltaNetwork38106f32e7eSjoerg ForwardDeltaNetwork(ArrayRef<ElemType> Ord) : PermNetwork(Ord) {}
38206f32e7eSjoerg
run__anon7c13adc80411::ForwardDeltaNetwork38306f32e7eSjoerg bool run(Controls &V) {
38406f32e7eSjoerg if (!route(Order.data(), Table.data(), size(), 0))
38506f32e7eSjoerg return false;
38606f32e7eSjoerg getControls(V, 0, Forward);
38706f32e7eSjoerg return true;
38806f32e7eSjoerg }
38906f32e7eSjoerg
39006f32e7eSjoerg private:
39106f32e7eSjoerg bool route(ElemType *P, RowType *T, unsigned Size, unsigned Step);
39206f32e7eSjoerg };
39306f32e7eSjoerg
39406f32e7eSjoerg struct ReverseDeltaNetwork : public PermNetwork {
ReverseDeltaNetwork__anon7c13adc80411::ReverseDeltaNetwork39506f32e7eSjoerg ReverseDeltaNetwork(ArrayRef<ElemType> Ord) : PermNetwork(Ord) {}
39606f32e7eSjoerg
run__anon7c13adc80411::ReverseDeltaNetwork39706f32e7eSjoerg bool run(Controls &V) {
39806f32e7eSjoerg if (!route(Order.data(), Table.data(), size(), 0))
39906f32e7eSjoerg return false;
40006f32e7eSjoerg getControls(V, 0, Reverse);
40106f32e7eSjoerg return true;
40206f32e7eSjoerg }
40306f32e7eSjoerg
40406f32e7eSjoerg private:
40506f32e7eSjoerg bool route(ElemType *P, RowType *T, unsigned Size, unsigned Step);
40606f32e7eSjoerg };
40706f32e7eSjoerg
40806f32e7eSjoerg struct BenesNetwork : public PermNetwork {
BenesNetwork__anon7c13adc80411::BenesNetwork40906f32e7eSjoerg BenesNetwork(ArrayRef<ElemType> Ord) : PermNetwork(Ord, 2) {}
41006f32e7eSjoerg
run__anon7c13adc80411::BenesNetwork41106f32e7eSjoerg bool run(Controls &F, Controls &R) {
41206f32e7eSjoerg if (!route(Order.data(), Table.data(), size(), 0))
41306f32e7eSjoerg return false;
41406f32e7eSjoerg
41506f32e7eSjoerg getControls(F, 0, Forward);
41606f32e7eSjoerg getControls(R, Log, Reverse);
41706f32e7eSjoerg return true;
41806f32e7eSjoerg }
41906f32e7eSjoerg
42006f32e7eSjoerg private:
42106f32e7eSjoerg bool route(ElemType *P, RowType *T, unsigned Size, unsigned Step);
42206f32e7eSjoerg };
42306f32e7eSjoerg } // namespace
42406f32e7eSjoerg
route(ElemType * P,RowType * T,unsigned Size,unsigned Step)42506f32e7eSjoerg bool ForwardDeltaNetwork::route(ElemType *P, RowType *T, unsigned Size,
42606f32e7eSjoerg unsigned Step) {
42706f32e7eSjoerg bool UseUp = false, UseDown = false;
42806f32e7eSjoerg ElemType Num = Size;
42906f32e7eSjoerg
43006f32e7eSjoerg // Cannot use coloring here, because coloring is used to determine
43106f32e7eSjoerg // the "big" switch, i.e. the one that changes halves, and in a forward
43206f32e7eSjoerg // network, a color can be simultaneously routed to both halves in the
43306f32e7eSjoerg // step we're working on.
43406f32e7eSjoerg for (ElemType J = 0; J != Num; ++J) {
43506f32e7eSjoerg ElemType I = P[J];
43606f32e7eSjoerg // I is the position in the input,
43706f32e7eSjoerg // J is the position in the output.
43806f32e7eSjoerg if (I == Ignore)
43906f32e7eSjoerg continue;
44006f32e7eSjoerg uint8_t S;
44106f32e7eSjoerg if (I < Num/2)
44206f32e7eSjoerg S = (J < Num/2) ? Pass : Switch;
44306f32e7eSjoerg else
44406f32e7eSjoerg S = (J < Num/2) ? Switch : Pass;
44506f32e7eSjoerg
44606f32e7eSjoerg // U is the element in the table that needs to be updated.
44706f32e7eSjoerg ElemType U = (S == Pass) ? I : (I < Num/2 ? I+Num/2 : I-Num/2);
44806f32e7eSjoerg if (U < Num/2)
44906f32e7eSjoerg UseUp = true;
45006f32e7eSjoerg else
45106f32e7eSjoerg UseDown = true;
45206f32e7eSjoerg if (T[U][Step] != S && T[U][Step] != None)
45306f32e7eSjoerg return false;
45406f32e7eSjoerg T[U][Step] = S;
45506f32e7eSjoerg }
45606f32e7eSjoerg
45706f32e7eSjoerg for (ElemType J = 0; J != Num; ++J)
45806f32e7eSjoerg if (P[J] != Ignore && P[J] >= Num/2)
45906f32e7eSjoerg P[J] -= Num/2;
46006f32e7eSjoerg
46106f32e7eSjoerg if (Step+1 < Log) {
46206f32e7eSjoerg if (UseUp && !route(P, T, Size/2, Step+1))
46306f32e7eSjoerg return false;
46406f32e7eSjoerg if (UseDown && !route(P+Size/2, T+Size/2, Size/2, Step+1))
46506f32e7eSjoerg return false;
46606f32e7eSjoerg }
46706f32e7eSjoerg return true;
46806f32e7eSjoerg }
46906f32e7eSjoerg
route(ElemType * P,RowType * T,unsigned Size,unsigned Step)47006f32e7eSjoerg bool ReverseDeltaNetwork::route(ElemType *P, RowType *T, unsigned Size,
47106f32e7eSjoerg unsigned Step) {
47206f32e7eSjoerg unsigned Pets = Log-1 - Step;
47306f32e7eSjoerg bool UseUp = false, UseDown = false;
47406f32e7eSjoerg ElemType Num = Size;
47506f32e7eSjoerg
47606f32e7eSjoerg // In this step half-switching occurs, so coloring can be used.
47706f32e7eSjoerg Coloring G({P,Size});
47806f32e7eSjoerg const Coloring::MapType &M = G.colors();
47906f32e7eSjoerg if (M.empty())
48006f32e7eSjoerg return false;
48106f32e7eSjoerg
48206f32e7eSjoerg ColorKind ColorUp = ColorKind::None;
48306f32e7eSjoerg for (ElemType J = 0; J != Num; ++J) {
48406f32e7eSjoerg ElemType I = P[J];
48506f32e7eSjoerg // I is the position in the input,
48606f32e7eSjoerg // J is the position in the output.
48706f32e7eSjoerg if (I == Ignore)
48806f32e7eSjoerg continue;
48906f32e7eSjoerg ColorKind C = M.at(I);
49006f32e7eSjoerg if (C == ColorKind::None)
49106f32e7eSjoerg continue;
49206f32e7eSjoerg // During "Step", inputs cannot switch halves, so if the "up" color
49306f32e7eSjoerg // is still unknown, make sure that it is selected in such a way that
49406f32e7eSjoerg // "I" will stay in the same half.
49506f32e7eSjoerg bool InpUp = I < Num/2;
49606f32e7eSjoerg if (ColorUp == ColorKind::None)
49706f32e7eSjoerg ColorUp = InpUp ? C : G.other(C);
49806f32e7eSjoerg if ((C == ColorUp) != InpUp) {
49906f32e7eSjoerg // If I should go to a different half than where is it now, give up.
50006f32e7eSjoerg return false;
50106f32e7eSjoerg }
50206f32e7eSjoerg
50306f32e7eSjoerg uint8_t S;
50406f32e7eSjoerg if (InpUp) {
50506f32e7eSjoerg S = (J < Num/2) ? Pass : Switch;
50606f32e7eSjoerg UseUp = true;
50706f32e7eSjoerg } else {
50806f32e7eSjoerg S = (J < Num/2) ? Switch : Pass;
50906f32e7eSjoerg UseDown = true;
51006f32e7eSjoerg }
51106f32e7eSjoerg T[J][Pets] = S;
51206f32e7eSjoerg }
51306f32e7eSjoerg
51406f32e7eSjoerg // Reorder the working permutation according to the computed switch table
51506f32e7eSjoerg // for the last step (i.e. Pets).
51606f32e7eSjoerg for (ElemType J = 0, E = Size / 2; J != E; ++J) {
51706f32e7eSjoerg ElemType PJ = P[J]; // Current values of P[J]
51806f32e7eSjoerg ElemType PC = P[J+Size/2]; // and P[conj(J)]
51906f32e7eSjoerg ElemType QJ = PJ; // New values of P[J]
52006f32e7eSjoerg ElemType QC = PC; // and P[conj(J)]
52106f32e7eSjoerg if (T[J][Pets] == Switch)
52206f32e7eSjoerg QC = PJ;
52306f32e7eSjoerg if (T[J+Size/2][Pets] == Switch)
52406f32e7eSjoerg QJ = PC;
52506f32e7eSjoerg P[J] = QJ;
52606f32e7eSjoerg P[J+Size/2] = QC;
52706f32e7eSjoerg }
52806f32e7eSjoerg
52906f32e7eSjoerg for (ElemType J = 0; J != Num; ++J)
53006f32e7eSjoerg if (P[J] != Ignore && P[J] >= Num/2)
53106f32e7eSjoerg P[J] -= Num/2;
53206f32e7eSjoerg
53306f32e7eSjoerg if (Step+1 < Log) {
53406f32e7eSjoerg if (UseUp && !route(P, T, Size/2, Step+1))
53506f32e7eSjoerg return false;
53606f32e7eSjoerg if (UseDown && !route(P+Size/2, T+Size/2, Size/2, Step+1))
53706f32e7eSjoerg return false;
53806f32e7eSjoerg }
53906f32e7eSjoerg return true;
54006f32e7eSjoerg }
54106f32e7eSjoerg
route(ElemType * P,RowType * T,unsigned Size,unsigned Step)54206f32e7eSjoerg bool BenesNetwork::route(ElemType *P, RowType *T, unsigned Size,
54306f32e7eSjoerg unsigned Step) {
54406f32e7eSjoerg Coloring G({P,Size});
54506f32e7eSjoerg const Coloring::MapType &M = G.colors();
54606f32e7eSjoerg if (M.empty())
54706f32e7eSjoerg return false;
54806f32e7eSjoerg ElemType Num = Size;
54906f32e7eSjoerg
55006f32e7eSjoerg unsigned Pets = 2*Log-1 - Step;
55106f32e7eSjoerg bool UseUp = false, UseDown = false;
55206f32e7eSjoerg
55306f32e7eSjoerg // Both assignments, i.e. Red->Up and Red->Down are valid, but they will
55406f32e7eSjoerg // result in different controls. Let's pick the one where the first
55506f32e7eSjoerg // control will be "Pass".
55606f32e7eSjoerg ColorKind ColorUp = ColorKind::None;
55706f32e7eSjoerg for (ElemType J = 0; J != Num; ++J) {
55806f32e7eSjoerg ElemType I = P[J];
55906f32e7eSjoerg if (I == Ignore)
56006f32e7eSjoerg continue;
56106f32e7eSjoerg ColorKind C = M.at(I);
56206f32e7eSjoerg if (C == ColorKind::None)
56306f32e7eSjoerg continue;
56406f32e7eSjoerg if (ColorUp == ColorKind::None) {
56506f32e7eSjoerg ColorUp = (I < Num / 2) ? ColorKind::Red : ColorKind::Black;
56606f32e7eSjoerg }
56706f32e7eSjoerg unsigned CI = (I < Num/2) ? I+Num/2 : I-Num/2;
56806f32e7eSjoerg if (C == ColorUp) {
56906f32e7eSjoerg if (I < Num/2)
57006f32e7eSjoerg T[I][Step] = Pass;
57106f32e7eSjoerg else
57206f32e7eSjoerg T[CI][Step] = Switch;
57306f32e7eSjoerg T[J][Pets] = (J < Num/2) ? Pass : Switch;
57406f32e7eSjoerg UseUp = true;
57506f32e7eSjoerg } else { // Down
57606f32e7eSjoerg if (I < Num/2)
57706f32e7eSjoerg T[CI][Step] = Switch;
57806f32e7eSjoerg else
57906f32e7eSjoerg T[I][Step] = Pass;
58006f32e7eSjoerg T[J][Pets] = (J < Num/2) ? Switch : Pass;
58106f32e7eSjoerg UseDown = true;
58206f32e7eSjoerg }
58306f32e7eSjoerg }
58406f32e7eSjoerg
58506f32e7eSjoerg // Reorder the working permutation according to the computed switch table
58606f32e7eSjoerg // for the last step (i.e. Pets).
58706f32e7eSjoerg for (ElemType J = 0; J != Num/2; ++J) {
58806f32e7eSjoerg ElemType PJ = P[J]; // Current values of P[J]
58906f32e7eSjoerg ElemType PC = P[J+Num/2]; // and P[conj(J)]
59006f32e7eSjoerg ElemType QJ = PJ; // New values of P[J]
59106f32e7eSjoerg ElemType QC = PC; // and P[conj(J)]
59206f32e7eSjoerg if (T[J][Pets] == Switch)
59306f32e7eSjoerg QC = PJ;
59406f32e7eSjoerg if (T[J+Num/2][Pets] == Switch)
59506f32e7eSjoerg QJ = PC;
59606f32e7eSjoerg P[J] = QJ;
59706f32e7eSjoerg P[J+Num/2] = QC;
59806f32e7eSjoerg }
59906f32e7eSjoerg
60006f32e7eSjoerg for (ElemType J = 0; J != Num; ++J)
60106f32e7eSjoerg if (P[J] != Ignore && P[J] >= Num/2)
60206f32e7eSjoerg P[J] -= Num/2;
60306f32e7eSjoerg
60406f32e7eSjoerg if (Step+1 < Log) {
60506f32e7eSjoerg if (UseUp && !route(P, T, Size/2, Step+1))
60606f32e7eSjoerg return false;
60706f32e7eSjoerg if (UseDown && !route(P+Size/2, T+Size/2, Size/2, Step+1))
60806f32e7eSjoerg return false;
60906f32e7eSjoerg }
61006f32e7eSjoerg return true;
61106f32e7eSjoerg }
61206f32e7eSjoerg
61306f32e7eSjoerg // --------------------------------------------------------------------
61406f32e7eSjoerg // Support for building selection results (output instructions that are
61506f32e7eSjoerg // parts of the final selection).
61606f32e7eSjoerg
61706f32e7eSjoerg namespace {
61806f32e7eSjoerg struct OpRef {
OpRef__anon7c13adc80711::OpRef61906f32e7eSjoerg OpRef(SDValue V) : OpV(V) {}
isValue__anon7c13adc80711::OpRef62006f32e7eSjoerg bool isValue() const { return OpV.getNode() != nullptr; }
isValid__anon7c13adc80711::OpRef62106f32e7eSjoerg bool isValid() const { return isValue() || !(OpN & Invalid); }
res__anon7c13adc80711::OpRef62206f32e7eSjoerg static OpRef res(int N) { return OpRef(Whole | (N & Index)); }
fail__anon7c13adc80711::OpRef62306f32e7eSjoerg static OpRef fail() { return OpRef(Invalid); }
62406f32e7eSjoerg
lo__anon7c13adc80711::OpRef62506f32e7eSjoerg static OpRef lo(const OpRef &R) {
62606f32e7eSjoerg assert(!R.isValue());
62706f32e7eSjoerg return OpRef(R.OpN & (Undef | Index | LoHalf));
62806f32e7eSjoerg }
hi__anon7c13adc80711::OpRef62906f32e7eSjoerg static OpRef hi(const OpRef &R) {
63006f32e7eSjoerg assert(!R.isValue());
63106f32e7eSjoerg return OpRef(R.OpN & (Undef | Index | HiHalf));
63206f32e7eSjoerg }
undef__anon7c13adc80711::OpRef63306f32e7eSjoerg static OpRef undef(MVT Ty) { return OpRef(Undef | Ty.SimpleTy); }
63406f32e7eSjoerg
63506f32e7eSjoerg // Direct value.
63606f32e7eSjoerg SDValue OpV = SDValue();
63706f32e7eSjoerg
63806f32e7eSjoerg // Reference to the operand of the input node:
63906f32e7eSjoerg // If the 31st bit is 1, it's undef, otherwise, bits 28..0 are the
64006f32e7eSjoerg // operand index:
64106f32e7eSjoerg // If bit 30 is set, it's the high half of the operand.
64206f32e7eSjoerg // If bit 29 is set, it's the low half of the operand.
64306f32e7eSjoerg unsigned OpN = 0;
64406f32e7eSjoerg
64506f32e7eSjoerg enum : unsigned {
64606f32e7eSjoerg Invalid = 0x10000000,
64706f32e7eSjoerg LoHalf = 0x20000000,
64806f32e7eSjoerg HiHalf = 0x40000000,
64906f32e7eSjoerg Whole = LoHalf | HiHalf,
65006f32e7eSjoerg Undef = 0x80000000,
65106f32e7eSjoerg Index = 0x0FFFFFFF, // Mask of the index value.
65206f32e7eSjoerg IndexBits = 28,
65306f32e7eSjoerg };
65406f32e7eSjoerg
65506f32e7eSjoerg LLVM_DUMP_METHOD
65606f32e7eSjoerg void print(raw_ostream &OS, const SelectionDAG &G) const;
65706f32e7eSjoerg
65806f32e7eSjoerg private:
OpRef__anon7c13adc80711::OpRef65906f32e7eSjoerg OpRef(unsigned N) : OpN(N) {}
66006f32e7eSjoerg };
66106f32e7eSjoerg
66206f32e7eSjoerg struct NodeTemplate {
66306f32e7eSjoerg NodeTemplate() = default;
66406f32e7eSjoerg unsigned Opc = 0;
66506f32e7eSjoerg MVT Ty = MVT::Other;
66606f32e7eSjoerg std::vector<OpRef> Ops;
66706f32e7eSjoerg
66806f32e7eSjoerg LLVM_DUMP_METHOD void print(raw_ostream &OS, const SelectionDAG &G) const;
66906f32e7eSjoerg };
67006f32e7eSjoerg
67106f32e7eSjoerg struct ResultStack {
ResultStack__anon7c13adc80711::ResultStack67206f32e7eSjoerg ResultStack(SDNode *Inp)
67306f32e7eSjoerg : InpNode(Inp), InpTy(Inp->getValueType(0).getSimpleVT()) {}
67406f32e7eSjoerg SDNode *InpNode;
67506f32e7eSjoerg MVT InpTy;
push__anon7c13adc80711::ResultStack67606f32e7eSjoerg unsigned push(const NodeTemplate &Res) {
67706f32e7eSjoerg List.push_back(Res);
67806f32e7eSjoerg return List.size()-1;
67906f32e7eSjoerg }
push__anon7c13adc80711::ResultStack68006f32e7eSjoerg unsigned push(unsigned Opc, MVT Ty, std::vector<OpRef> &&Ops) {
68106f32e7eSjoerg NodeTemplate Res;
68206f32e7eSjoerg Res.Opc = Opc;
68306f32e7eSjoerg Res.Ty = Ty;
68406f32e7eSjoerg Res.Ops = Ops;
68506f32e7eSjoerg return push(Res);
68606f32e7eSjoerg }
empty__anon7c13adc80711::ResultStack68706f32e7eSjoerg bool empty() const { return List.empty(); }
size__anon7c13adc80711::ResultStack68806f32e7eSjoerg unsigned size() const { return List.size(); }
top__anon7c13adc80711::ResultStack68906f32e7eSjoerg unsigned top() const { return size()-1; }
operator []__anon7c13adc80711::ResultStack69006f32e7eSjoerg const NodeTemplate &operator[](unsigned I) const { return List[I]; }
reset__anon7c13adc80711::ResultStack69106f32e7eSjoerg unsigned reset(unsigned NewTop) {
69206f32e7eSjoerg List.resize(NewTop+1);
69306f32e7eSjoerg return NewTop;
69406f32e7eSjoerg }
69506f32e7eSjoerg
69606f32e7eSjoerg using BaseType = std::vector<NodeTemplate>;
begin__anon7c13adc80711::ResultStack69706f32e7eSjoerg BaseType::iterator begin() { return List.begin(); }
end__anon7c13adc80711::ResultStack69806f32e7eSjoerg BaseType::iterator end() { return List.end(); }
begin__anon7c13adc80711::ResultStack69906f32e7eSjoerg BaseType::const_iterator begin() const { return List.begin(); }
end__anon7c13adc80711::ResultStack70006f32e7eSjoerg BaseType::const_iterator end() const { return List.end(); }
70106f32e7eSjoerg
70206f32e7eSjoerg BaseType List;
70306f32e7eSjoerg
70406f32e7eSjoerg LLVM_DUMP_METHOD
70506f32e7eSjoerg void print(raw_ostream &OS, const SelectionDAG &G) const;
70606f32e7eSjoerg };
70706f32e7eSjoerg } // namespace
70806f32e7eSjoerg
70906f32e7eSjoerg #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
print(raw_ostream & OS,const SelectionDAG & G) const71006f32e7eSjoerg void OpRef::print(raw_ostream &OS, const SelectionDAG &G) const {
71106f32e7eSjoerg if (isValue()) {
71206f32e7eSjoerg OpV.getNode()->print(OS, &G);
71306f32e7eSjoerg return;
71406f32e7eSjoerg }
71506f32e7eSjoerg if (OpN & Invalid) {
71606f32e7eSjoerg OS << "invalid";
71706f32e7eSjoerg return;
71806f32e7eSjoerg }
71906f32e7eSjoerg if (OpN & Undef) {
72006f32e7eSjoerg OS << "undef";
72106f32e7eSjoerg return;
72206f32e7eSjoerg }
72306f32e7eSjoerg if ((OpN & Whole) != Whole) {
72406f32e7eSjoerg assert((OpN & Whole) == LoHalf || (OpN & Whole) == HiHalf);
72506f32e7eSjoerg if (OpN & LoHalf)
72606f32e7eSjoerg OS << "lo ";
72706f32e7eSjoerg else
72806f32e7eSjoerg OS << "hi ";
72906f32e7eSjoerg }
73006f32e7eSjoerg OS << '#' << SignExtend32(OpN & Index, IndexBits);
73106f32e7eSjoerg }
73206f32e7eSjoerg
print(raw_ostream & OS,const SelectionDAG & G) const73306f32e7eSjoerg void NodeTemplate::print(raw_ostream &OS, const SelectionDAG &G) const {
73406f32e7eSjoerg const TargetInstrInfo &TII = *G.getSubtarget().getInstrInfo();
73506f32e7eSjoerg OS << format("%8s", EVT(Ty).getEVTString().c_str()) << " "
73606f32e7eSjoerg << TII.getName(Opc);
73706f32e7eSjoerg bool Comma = false;
73806f32e7eSjoerg for (const auto &R : Ops) {
73906f32e7eSjoerg if (Comma)
74006f32e7eSjoerg OS << ',';
74106f32e7eSjoerg Comma = true;
74206f32e7eSjoerg OS << ' ';
74306f32e7eSjoerg R.print(OS, G);
74406f32e7eSjoerg }
74506f32e7eSjoerg }
74606f32e7eSjoerg
print(raw_ostream & OS,const SelectionDAG & G) const74706f32e7eSjoerg void ResultStack::print(raw_ostream &OS, const SelectionDAG &G) const {
74806f32e7eSjoerg OS << "Input node:\n";
74906f32e7eSjoerg #ifndef NDEBUG
75006f32e7eSjoerg InpNode->dumpr(&G);
75106f32e7eSjoerg #endif
75206f32e7eSjoerg OS << "Result templates:\n";
75306f32e7eSjoerg for (unsigned I = 0, E = List.size(); I != E; ++I) {
75406f32e7eSjoerg OS << '[' << I << "] ";
75506f32e7eSjoerg List[I].print(OS, G);
75606f32e7eSjoerg OS << '\n';
75706f32e7eSjoerg }
75806f32e7eSjoerg }
75906f32e7eSjoerg #endif
76006f32e7eSjoerg
76106f32e7eSjoerg namespace {
76206f32e7eSjoerg struct ShuffleMask {
ShuffleMask__anon7c13adc80911::ShuffleMask76306f32e7eSjoerg ShuffleMask(ArrayRef<int> M) : Mask(M) {
76406f32e7eSjoerg for (unsigned I = 0, E = Mask.size(); I != E; ++I) {
76506f32e7eSjoerg int M = Mask[I];
76606f32e7eSjoerg if (M == -1)
76706f32e7eSjoerg continue;
76806f32e7eSjoerg MinSrc = (MinSrc == -1) ? M : std::min(MinSrc, M);
76906f32e7eSjoerg MaxSrc = (MaxSrc == -1) ? M : std::max(MaxSrc, M);
77006f32e7eSjoerg }
77106f32e7eSjoerg }
77206f32e7eSjoerg
77306f32e7eSjoerg ArrayRef<int> Mask;
77406f32e7eSjoerg int MinSrc = -1, MaxSrc = -1;
77506f32e7eSjoerg
lo__anon7c13adc80911::ShuffleMask77606f32e7eSjoerg ShuffleMask lo() const {
77706f32e7eSjoerg size_t H = Mask.size()/2;
77806f32e7eSjoerg return ShuffleMask(Mask.take_front(H));
77906f32e7eSjoerg }
hi__anon7c13adc80911::ShuffleMask78006f32e7eSjoerg ShuffleMask hi() const {
78106f32e7eSjoerg size_t H = Mask.size()/2;
78206f32e7eSjoerg return ShuffleMask(Mask.take_back(H));
78306f32e7eSjoerg }
78406f32e7eSjoerg
print__anon7c13adc80911::ShuffleMask78506f32e7eSjoerg void print(raw_ostream &OS) const {
78606f32e7eSjoerg OS << "MinSrc:" << MinSrc << ", MaxSrc:" << MaxSrc << " {";
78706f32e7eSjoerg for (int M : Mask)
78806f32e7eSjoerg OS << ' ' << M;
78906f32e7eSjoerg OS << " }";
79006f32e7eSjoerg }
79106f32e7eSjoerg };
792*da58b97aSjoerg
793*da58b97aSjoerg LLVM_ATTRIBUTE_UNUSED
operator <<(raw_ostream & OS,const ShuffleMask & SM)794*da58b97aSjoerg raw_ostream &operator<<(raw_ostream &OS, const ShuffleMask &SM) {
795*da58b97aSjoerg SM.print(OS);
796*da58b97aSjoerg return OS;
797*da58b97aSjoerg }
79806f32e7eSjoerg } // namespace
79906f32e7eSjoerg
80006f32e7eSjoerg // --------------------------------------------------------------------
80106f32e7eSjoerg // The HvxSelector class.
80206f32e7eSjoerg
getHexagonLowering(SelectionDAG & G)80306f32e7eSjoerg static const HexagonTargetLowering &getHexagonLowering(SelectionDAG &G) {
80406f32e7eSjoerg return static_cast<const HexagonTargetLowering&>(G.getTargetLoweringInfo());
80506f32e7eSjoerg }
getHexagonSubtarget(SelectionDAG & G)80606f32e7eSjoerg static const HexagonSubtarget &getHexagonSubtarget(SelectionDAG &G) {
80706f32e7eSjoerg return static_cast<const HexagonSubtarget&>(G.getSubtarget());
80806f32e7eSjoerg }
80906f32e7eSjoerg
81006f32e7eSjoerg namespace llvm {
81106f32e7eSjoerg struct HvxSelector {
81206f32e7eSjoerg const HexagonTargetLowering &Lower;
81306f32e7eSjoerg HexagonDAGToDAGISel &ISel;
81406f32e7eSjoerg SelectionDAG &DAG;
81506f32e7eSjoerg const HexagonSubtarget &HST;
81606f32e7eSjoerg const unsigned HwLen;
81706f32e7eSjoerg
HvxSelectorllvm::HvxSelector81806f32e7eSjoerg HvxSelector(HexagonDAGToDAGISel &HS, SelectionDAG &G)
81906f32e7eSjoerg : Lower(getHexagonLowering(G)), ISel(HS), DAG(G),
82006f32e7eSjoerg HST(getHexagonSubtarget(G)), HwLen(HST.getVectorLength()) {}
82106f32e7eSjoerg
getSingleVTllvm::HvxSelector82206f32e7eSjoerg MVT getSingleVT(MVT ElemTy) const {
82306f32e7eSjoerg unsigned NumElems = HwLen / (ElemTy.getSizeInBits()/8);
82406f32e7eSjoerg return MVT::getVectorVT(ElemTy, NumElems);
82506f32e7eSjoerg }
82606f32e7eSjoerg
getPairVTllvm::HvxSelector82706f32e7eSjoerg MVT getPairVT(MVT ElemTy) const {
82806f32e7eSjoerg unsigned NumElems = (2*HwLen) / (ElemTy.getSizeInBits()/8);
82906f32e7eSjoerg return MVT::getVectorVT(ElemTy, NumElems);
83006f32e7eSjoerg }
83106f32e7eSjoerg
83206f32e7eSjoerg void selectShuffle(SDNode *N);
83306f32e7eSjoerg void selectRor(SDNode *N);
83406f32e7eSjoerg void selectVAlign(SDNode *N);
83506f32e7eSjoerg
83606f32e7eSjoerg private:
837*da58b97aSjoerg void select(SDNode *ISelN);
83806f32e7eSjoerg void materialize(const ResultStack &Results);
83906f32e7eSjoerg
84006f32e7eSjoerg SDValue getVectorConstant(ArrayRef<uint8_t> Data, const SDLoc &dl);
84106f32e7eSjoerg
84206f32e7eSjoerg enum : unsigned {
84306f32e7eSjoerg None,
84406f32e7eSjoerg PackMux,
84506f32e7eSjoerg };
84606f32e7eSjoerg OpRef concat(OpRef Va, OpRef Vb, ResultStack &Results);
84706f32e7eSjoerg OpRef packs(ShuffleMask SM, OpRef Va, OpRef Vb, ResultStack &Results,
84806f32e7eSjoerg MutableArrayRef<int> NewMask, unsigned Options = None);
84906f32e7eSjoerg OpRef packp(ShuffleMask SM, OpRef Va, OpRef Vb, ResultStack &Results,
85006f32e7eSjoerg MutableArrayRef<int> NewMask);
85106f32e7eSjoerg OpRef vmuxs(ArrayRef<uint8_t> Bytes, OpRef Va, OpRef Vb,
85206f32e7eSjoerg ResultStack &Results);
85306f32e7eSjoerg OpRef vmuxp(ArrayRef<uint8_t> Bytes, OpRef Va, OpRef Vb,
85406f32e7eSjoerg ResultStack &Results);
85506f32e7eSjoerg
85606f32e7eSjoerg OpRef shuffs1(ShuffleMask SM, OpRef Va, ResultStack &Results);
85706f32e7eSjoerg OpRef shuffs2(ShuffleMask SM, OpRef Va, OpRef Vb, ResultStack &Results);
85806f32e7eSjoerg OpRef shuffp1(ShuffleMask SM, OpRef Va, ResultStack &Results);
85906f32e7eSjoerg OpRef shuffp2(ShuffleMask SM, OpRef Va, OpRef Vb, ResultStack &Results);
86006f32e7eSjoerg
86106f32e7eSjoerg OpRef butterfly(ShuffleMask SM, OpRef Va, ResultStack &Results);
86206f32e7eSjoerg OpRef contracting(ShuffleMask SM, OpRef Va, OpRef Vb, ResultStack &Results);
86306f32e7eSjoerg OpRef expanding(ShuffleMask SM, OpRef Va, ResultStack &Results);
86406f32e7eSjoerg OpRef perfect(ShuffleMask SM, OpRef Va, ResultStack &Results);
86506f32e7eSjoerg
86606f32e7eSjoerg bool selectVectorConstants(SDNode *N);
86706f32e7eSjoerg bool scalarizeShuffle(ArrayRef<int> Mask, const SDLoc &dl, MVT ResTy,
86806f32e7eSjoerg SDValue Va, SDValue Vb, SDNode *N);
86906f32e7eSjoerg
87006f32e7eSjoerg };
87106f32e7eSjoerg }
87206f32e7eSjoerg
splitMask(ArrayRef<int> Mask,MutableArrayRef<int> MaskL,MutableArrayRef<int> MaskR)87306f32e7eSjoerg static void splitMask(ArrayRef<int> Mask, MutableArrayRef<int> MaskL,
87406f32e7eSjoerg MutableArrayRef<int> MaskR) {
87506f32e7eSjoerg unsigned VecLen = Mask.size();
87606f32e7eSjoerg assert(MaskL.size() == VecLen && MaskR.size() == VecLen);
87706f32e7eSjoerg for (unsigned I = 0; I != VecLen; ++I) {
87806f32e7eSjoerg int M = Mask[I];
87906f32e7eSjoerg if (M < 0) {
88006f32e7eSjoerg MaskL[I] = MaskR[I] = -1;
88106f32e7eSjoerg } else if (unsigned(M) < VecLen) {
88206f32e7eSjoerg MaskL[I] = M;
88306f32e7eSjoerg MaskR[I] = -1;
88406f32e7eSjoerg } else {
88506f32e7eSjoerg MaskL[I] = -1;
88606f32e7eSjoerg MaskR[I] = M-VecLen;
88706f32e7eSjoerg }
88806f32e7eSjoerg }
88906f32e7eSjoerg }
89006f32e7eSjoerg
findStrip(ArrayRef<int> A,int Inc,unsigned MaxLen)89106f32e7eSjoerg static std::pair<int,unsigned> findStrip(ArrayRef<int> A, int Inc,
89206f32e7eSjoerg unsigned MaxLen) {
89306f32e7eSjoerg assert(A.size() > 0 && A.size() >= MaxLen);
89406f32e7eSjoerg int F = A[0];
89506f32e7eSjoerg int E = F;
89606f32e7eSjoerg for (unsigned I = 1; I != MaxLen; ++I) {
89706f32e7eSjoerg if (A[I] - E != Inc)
89806f32e7eSjoerg return { F, I };
89906f32e7eSjoerg E = A[I];
90006f32e7eSjoerg }
90106f32e7eSjoerg return { F, MaxLen };
90206f32e7eSjoerg }
90306f32e7eSjoerg
isUndef(ArrayRef<int> Mask)90406f32e7eSjoerg static bool isUndef(ArrayRef<int> Mask) {
90506f32e7eSjoerg for (int Idx : Mask)
90606f32e7eSjoerg if (Idx != -1)
90706f32e7eSjoerg return false;
90806f32e7eSjoerg return true;
90906f32e7eSjoerg }
91006f32e7eSjoerg
isIdentity(ArrayRef<int> Mask)91106f32e7eSjoerg static bool isIdentity(ArrayRef<int> Mask) {
91206f32e7eSjoerg for (int I = 0, E = Mask.size(); I != E; ++I) {
91306f32e7eSjoerg int M = Mask[I];
91406f32e7eSjoerg if (M >= 0 && M != I)
91506f32e7eSjoerg return false;
91606f32e7eSjoerg }
91706f32e7eSjoerg return true;
91806f32e7eSjoerg }
91906f32e7eSjoerg
isPermutation(ArrayRef<int> Mask)92006f32e7eSjoerg static bool isPermutation(ArrayRef<int> Mask) {
92106f32e7eSjoerg // Check by adding all numbers only works if there is no overflow.
92206f32e7eSjoerg assert(Mask.size() < 0x00007FFF && "Sanity failure");
92306f32e7eSjoerg int Sum = 0;
92406f32e7eSjoerg for (int Idx : Mask) {
92506f32e7eSjoerg if (Idx == -1)
92606f32e7eSjoerg return false;
92706f32e7eSjoerg Sum += Idx;
92806f32e7eSjoerg }
92906f32e7eSjoerg int N = Mask.size();
93006f32e7eSjoerg return 2*Sum == N*(N-1);
93106f32e7eSjoerg }
93206f32e7eSjoerg
selectVectorConstants(SDNode * N)93306f32e7eSjoerg bool HvxSelector::selectVectorConstants(SDNode *N) {
93406f32e7eSjoerg // Constant vectors are generated as loads from constant pools or as
93506f32e7eSjoerg // splats of a constant value. Since they are generated during the
93606f32e7eSjoerg // selection process, the main selection algorithm is not aware of them.
93706f32e7eSjoerg // Select them directly here.
93806f32e7eSjoerg SmallVector<SDNode*,4> Nodes;
93906f32e7eSjoerg SetVector<SDNode*> WorkQ;
94006f32e7eSjoerg
94106f32e7eSjoerg // The DAG can change (due to CSE) during selection, so cache all the
94206f32e7eSjoerg // unselected nodes first to avoid traversing a mutating DAG.
94306f32e7eSjoerg WorkQ.insert(N);
94406f32e7eSjoerg for (unsigned i = 0; i != WorkQ.size(); ++i) {
94506f32e7eSjoerg SDNode *W = WorkQ[i];
946*da58b97aSjoerg if (!W->isMachineOpcode() && W->getOpcode() == HexagonISD::ISEL)
94706f32e7eSjoerg Nodes.push_back(W);
94806f32e7eSjoerg for (unsigned j = 0, f = W->getNumOperands(); j != f; ++j)
94906f32e7eSjoerg WorkQ.insert(W->getOperand(j).getNode());
95006f32e7eSjoerg }
95106f32e7eSjoerg
95206f32e7eSjoerg for (SDNode *L : Nodes)
953*da58b97aSjoerg select(L);
95406f32e7eSjoerg
95506f32e7eSjoerg return !Nodes.empty();
95606f32e7eSjoerg }
95706f32e7eSjoerg
materialize(const ResultStack & Results)95806f32e7eSjoerg void HvxSelector::materialize(const ResultStack &Results) {
95906f32e7eSjoerg DEBUG_WITH_TYPE("isel", {
96006f32e7eSjoerg dbgs() << "Materializing\n";
96106f32e7eSjoerg Results.print(dbgs(), DAG);
96206f32e7eSjoerg });
96306f32e7eSjoerg if (Results.empty())
96406f32e7eSjoerg return;
96506f32e7eSjoerg const SDLoc &dl(Results.InpNode);
96606f32e7eSjoerg std::vector<SDValue> Output;
96706f32e7eSjoerg
96806f32e7eSjoerg for (unsigned I = 0, E = Results.size(); I != E; ++I) {
96906f32e7eSjoerg const NodeTemplate &Node = Results[I];
97006f32e7eSjoerg std::vector<SDValue> Ops;
97106f32e7eSjoerg for (const OpRef &R : Node.Ops) {
97206f32e7eSjoerg assert(R.isValid());
97306f32e7eSjoerg if (R.isValue()) {
97406f32e7eSjoerg Ops.push_back(R.OpV);
97506f32e7eSjoerg continue;
97606f32e7eSjoerg }
97706f32e7eSjoerg if (R.OpN & OpRef::Undef) {
97806f32e7eSjoerg MVT::SimpleValueType SVT = MVT::SimpleValueType(R.OpN & OpRef::Index);
97906f32e7eSjoerg Ops.push_back(ISel.selectUndef(dl, MVT(SVT)));
98006f32e7eSjoerg continue;
98106f32e7eSjoerg }
98206f32e7eSjoerg // R is an index of a result.
98306f32e7eSjoerg unsigned Part = R.OpN & OpRef::Whole;
98406f32e7eSjoerg int Idx = SignExtend32(R.OpN & OpRef::Index, OpRef::IndexBits);
98506f32e7eSjoerg if (Idx < 0)
98606f32e7eSjoerg Idx += I;
98706f32e7eSjoerg assert(Idx >= 0 && unsigned(Idx) < Output.size());
98806f32e7eSjoerg SDValue Op = Output[Idx];
98906f32e7eSjoerg MVT OpTy = Op.getValueType().getSimpleVT();
99006f32e7eSjoerg if (Part != OpRef::Whole) {
99106f32e7eSjoerg assert(Part == OpRef::LoHalf || Part == OpRef::HiHalf);
99206f32e7eSjoerg MVT HalfTy = MVT::getVectorVT(OpTy.getVectorElementType(),
99306f32e7eSjoerg OpTy.getVectorNumElements()/2);
99406f32e7eSjoerg unsigned Sub = (Part == OpRef::LoHalf) ? Hexagon::vsub_lo
99506f32e7eSjoerg : Hexagon::vsub_hi;
99606f32e7eSjoerg Op = DAG.getTargetExtractSubreg(Sub, dl, HalfTy, Op);
99706f32e7eSjoerg }
99806f32e7eSjoerg Ops.push_back(Op);
99906f32e7eSjoerg } // for (Node : Results)
100006f32e7eSjoerg
100106f32e7eSjoerg assert(Node.Ty != MVT::Other);
100206f32e7eSjoerg SDNode *ResN = (Node.Opc == TargetOpcode::COPY)
100306f32e7eSjoerg ? Ops.front().getNode()
100406f32e7eSjoerg : DAG.getMachineNode(Node.Opc, dl, Node.Ty, Ops);
100506f32e7eSjoerg Output.push_back(SDValue(ResN, 0));
100606f32e7eSjoerg }
100706f32e7eSjoerg
100806f32e7eSjoerg SDNode *OutN = Output.back().getNode();
100906f32e7eSjoerg SDNode *InpN = Results.InpNode;
101006f32e7eSjoerg DEBUG_WITH_TYPE("isel", {
101106f32e7eSjoerg dbgs() << "Generated node:\n";
101206f32e7eSjoerg OutN->dumpr(&DAG);
101306f32e7eSjoerg });
101406f32e7eSjoerg
101506f32e7eSjoerg ISel.ReplaceNode(InpN, OutN);
101606f32e7eSjoerg selectVectorConstants(OutN);
101706f32e7eSjoerg DAG.RemoveDeadNodes();
101806f32e7eSjoerg }
101906f32e7eSjoerg
concat(OpRef Lo,OpRef Hi,ResultStack & Results)102006f32e7eSjoerg OpRef HvxSelector::concat(OpRef Lo, OpRef Hi, ResultStack &Results) {
102106f32e7eSjoerg DEBUG_WITH_TYPE("isel", {dbgs() << __func__ << '\n';});
102206f32e7eSjoerg const SDLoc &dl(Results.InpNode);
102306f32e7eSjoerg Results.push(TargetOpcode::REG_SEQUENCE, getPairVT(MVT::i8), {
102406f32e7eSjoerg DAG.getTargetConstant(Hexagon::HvxWRRegClassID, dl, MVT::i32),
102506f32e7eSjoerg Lo, DAG.getTargetConstant(Hexagon::vsub_lo, dl, MVT::i32),
102606f32e7eSjoerg Hi, DAG.getTargetConstant(Hexagon::vsub_hi, dl, MVT::i32),
102706f32e7eSjoerg });
102806f32e7eSjoerg return OpRef::res(Results.top());
102906f32e7eSjoerg }
103006f32e7eSjoerg
103106f32e7eSjoerg // Va, Vb are single vectors, SM can be arbitrarily long.
packs(ShuffleMask SM,OpRef Va,OpRef Vb,ResultStack & Results,MutableArrayRef<int> NewMask,unsigned Options)103206f32e7eSjoerg OpRef HvxSelector::packs(ShuffleMask SM, OpRef Va, OpRef Vb,
103306f32e7eSjoerg ResultStack &Results, MutableArrayRef<int> NewMask,
103406f32e7eSjoerg unsigned Options) {
103506f32e7eSjoerg DEBUG_WITH_TYPE("isel", {dbgs() << __func__ << '\n';});
103606f32e7eSjoerg if (!Va.isValid() || !Vb.isValid())
103706f32e7eSjoerg return OpRef::fail();
103806f32e7eSjoerg
103906f32e7eSjoerg int VecLen = SM.Mask.size();
104006f32e7eSjoerg MVT Ty = getSingleVT(MVT::i8);
104106f32e7eSjoerg
104206f32e7eSjoerg auto IsExtSubvector = [] (ShuffleMask M) {
104306f32e7eSjoerg assert(M.MinSrc >= 0 && M.MaxSrc >= 0);
104406f32e7eSjoerg for (int I = 0, E = M.Mask.size(); I != E; ++I) {
104506f32e7eSjoerg if (M.Mask[I] >= 0 && M.Mask[I]-I != M.MinSrc)
104606f32e7eSjoerg return false;
104706f32e7eSjoerg }
104806f32e7eSjoerg return true;
104906f32e7eSjoerg };
105006f32e7eSjoerg
105106f32e7eSjoerg if (SM.MaxSrc - SM.MinSrc < int(HwLen)) {
105206f32e7eSjoerg if (SM.MinSrc == 0 || SM.MinSrc == int(HwLen) || !IsExtSubvector(SM)) {
105306f32e7eSjoerg // If the mask picks elements from only one of the operands, return
105406f32e7eSjoerg // that operand, and update the mask to use index 0 to refer to the
105506f32e7eSjoerg // first element of that operand.
105606f32e7eSjoerg // If the mask extracts a subvector, it will be handled below, so
105706f32e7eSjoerg // skip it here.
105806f32e7eSjoerg if (SM.MaxSrc < int(HwLen)) {
105906f32e7eSjoerg memcpy(NewMask.data(), SM.Mask.data(), sizeof(int)*VecLen);
106006f32e7eSjoerg return Va;
106106f32e7eSjoerg }
106206f32e7eSjoerg if (SM.MinSrc >= int(HwLen)) {
106306f32e7eSjoerg for (int I = 0; I != VecLen; ++I) {
106406f32e7eSjoerg int M = SM.Mask[I];
106506f32e7eSjoerg if (M != -1)
106606f32e7eSjoerg M -= HwLen;
106706f32e7eSjoerg NewMask[I] = M;
106806f32e7eSjoerg }
106906f32e7eSjoerg return Vb;
107006f32e7eSjoerg }
107106f32e7eSjoerg }
107206f32e7eSjoerg int MinSrc = SM.MinSrc;
107306f32e7eSjoerg if (SM.MaxSrc < int(HwLen)) {
107406f32e7eSjoerg Vb = Va;
107506f32e7eSjoerg } else if (SM.MinSrc > int(HwLen)) {
107606f32e7eSjoerg Va = Vb;
107706f32e7eSjoerg MinSrc = SM.MinSrc - HwLen;
107806f32e7eSjoerg }
107906f32e7eSjoerg const SDLoc &dl(Results.InpNode);
108006f32e7eSjoerg if (isUInt<3>(MinSrc) || isUInt<3>(HwLen-MinSrc)) {
108106f32e7eSjoerg bool IsRight = isUInt<3>(MinSrc); // Right align.
108206f32e7eSjoerg SDValue S = DAG.getTargetConstant(IsRight ? MinSrc : HwLen-MinSrc,
108306f32e7eSjoerg dl, MVT::i32);
108406f32e7eSjoerg unsigned Opc = IsRight ? Hexagon::V6_valignbi
108506f32e7eSjoerg : Hexagon::V6_vlalignbi;
108606f32e7eSjoerg Results.push(Opc, Ty, {Vb, Va, S});
108706f32e7eSjoerg } else {
108806f32e7eSjoerg SDValue S = DAG.getTargetConstant(MinSrc, dl, MVT::i32);
108906f32e7eSjoerg Results.push(Hexagon::A2_tfrsi, MVT::i32, {S});
109006f32e7eSjoerg unsigned Top = Results.top();
109106f32e7eSjoerg Results.push(Hexagon::V6_valignb, Ty, {Vb, Va, OpRef::res(Top)});
109206f32e7eSjoerg }
109306f32e7eSjoerg for (int I = 0; I != VecLen; ++I) {
109406f32e7eSjoerg int M = SM.Mask[I];
109506f32e7eSjoerg if (M != -1)
109606f32e7eSjoerg M -= SM.MinSrc;
109706f32e7eSjoerg NewMask[I] = M;
109806f32e7eSjoerg }
109906f32e7eSjoerg return OpRef::res(Results.top());
110006f32e7eSjoerg }
110106f32e7eSjoerg
110206f32e7eSjoerg if (Options & PackMux) {
110306f32e7eSjoerg // If elements picked from Va and Vb have all different (source) indexes
110406f32e7eSjoerg // (relative to the start of the argument), do a mux, and update the mask.
110506f32e7eSjoerg BitVector Picked(HwLen);
110606f32e7eSjoerg SmallVector<uint8_t,128> MuxBytes(HwLen);
110706f32e7eSjoerg bool CanMux = true;
110806f32e7eSjoerg for (int I = 0; I != VecLen; ++I) {
110906f32e7eSjoerg int M = SM.Mask[I];
111006f32e7eSjoerg if (M == -1)
111106f32e7eSjoerg continue;
111206f32e7eSjoerg if (M >= int(HwLen))
111306f32e7eSjoerg M -= HwLen;
111406f32e7eSjoerg else
111506f32e7eSjoerg MuxBytes[M] = 0xFF;
111606f32e7eSjoerg if (Picked[M]) {
111706f32e7eSjoerg CanMux = false;
111806f32e7eSjoerg break;
111906f32e7eSjoerg }
112006f32e7eSjoerg NewMask[I] = M;
112106f32e7eSjoerg }
112206f32e7eSjoerg if (CanMux)
112306f32e7eSjoerg return vmuxs(MuxBytes, Va, Vb, Results);
112406f32e7eSjoerg }
112506f32e7eSjoerg
112606f32e7eSjoerg return OpRef::fail();
112706f32e7eSjoerg }
112806f32e7eSjoerg
packp(ShuffleMask SM,OpRef Va,OpRef Vb,ResultStack & Results,MutableArrayRef<int> NewMask)112906f32e7eSjoerg OpRef HvxSelector::packp(ShuffleMask SM, OpRef Va, OpRef Vb,
113006f32e7eSjoerg ResultStack &Results, MutableArrayRef<int> NewMask) {
113106f32e7eSjoerg DEBUG_WITH_TYPE("isel", {dbgs() << __func__ << '\n';});
113206f32e7eSjoerg unsigned HalfMask = 0;
113306f32e7eSjoerg unsigned LogHw = Log2_32(HwLen);
113406f32e7eSjoerg for (int M : SM.Mask) {
113506f32e7eSjoerg if (M == -1)
113606f32e7eSjoerg continue;
113706f32e7eSjoerg HalfMask |= (1u << (M >> LogHw));
113806f32e7eSjoerg }
113906f32e7eSjoerg
114006f32e7eSjoerg if (HalfMask == 0)
114106f32e7eSjoerg return OpRef::undef(getPairVT(MVT::i8));
114206f32e7eSjoerg
114306f32e7eSjoerg // If more than two halves are used, bail.
114406f32e7eSjoerg // TODO: be more aggressive here?
114506f32e7eSjoerg if (countPopulation(HalfMask) > 2)
114606f32e7eSjoerg return OpRef::fail();
114706f32e7eSjoerg
114806f32e7eSjoerg MVT HalfTy = getSingleVT(MVT::i8);
114906f32e7eSjoerg
115006f32e7eSjoerg OpRef Inp[2] = { Va, Vb };
115106f32e7eSjoerg OpRef Out[2] = { OpRef::undef(HalfTy), OpRef::undef(HalfTy) };
115206f32e7eSjoerg
115306f32e7eSjoerg uint8_t HalfIdx[4] = { 0xFF, 0xFF, 0xFF, 0xFF };
115406f32e7eSjoerg unsigned Idx = 0;
115506f32e7eSjoerg for (unsigned I = 0; I != 4; ++I) {
115606f32e7eSjoerg if ((HalfMask & (1u << I)) == 0)
115706f32e7eSjoerg continue;
115806f32e7eSjoerg assert(Idx < 2);
115906f32e7eSjoerg OpRef Op = Inp[I/2];
116006f32e7eSjoerg Out[Idx] = (I & 1) ? OpRef::hi(Op) : OpRef::lo(Op);
116106f32e7eSjoerg HalfIdx[I] = Idx++;
116206f32e7eSjoerg }
116306f32e7eSjoerg
116406f32e7eSjoerg int VecLen = SM.Mask.size();
116506f32e7eSjoerg for (int I = 0; I != VecLen; ++I) {
116606f32e7eSjoerg int M = SM.Mask[I];
116706f32e7eSjoerg if (M >= 0) {
116806f32e7eSjoerg uint8_t Idx = HalfIdx[M >> LogHw];
116906f32e7eSjoerg assert(Idx == 0 || Idx == 1);
117006f32e7eSjoerg M = (M & (HwLen-1)) + HwLen*Idx;
117106f32e7eSjoerg }
117206f32e7eSjoerg NewMask[I] = M;
117306f32e7eSjoerg }
117406f32e7eSjoerg
117506f32e7eSjoerg return concat(Out[0], Out[1], Results);
117606f32e7eSjoerg }
117706f32e7eSjoerg
vmuxs(ArrayRef<uint8_t> Bytes,OpRef Va,OpRef Vb,ResultStack & Results)117806f32e7eSjoerg OpRef HvxSelector::vmuxs(ArrayRef<uint8_t> Bytes, OpRef Va, OpRef Vb,
117906f32e7eSjoerg ResultStack &Results) {
118006f32e7eSjoerg DEBUG_WITH_TYPE("isel", {dbgs() << __func__ << '\n';});
118106f32e7eSjoerg MVT ByteTy = getSingleVT(MVT::i8);
1182*da58b97aSjoerg MVT BoolTy = MVT::getVectorVT(MVT::i1, HwLen);
118306f32e7eSjoerg const SDLoc &dl(Results.InpNode);
118406f32e7eSjoerg SDValue B = getVectorConstant(Bytes, dl);
118506f32e7eSjoerg Results.push(Hexagon::V6_vd0, ByteTy, {});
118606f32e7eSjoerg Results.push(Hexagon::V6_veqb, BoolTy, {OpRef(B), OpRef::res(-1)});
118706f32e7eSjoerg Results.push(Hexagon::V6_vmux, ByteTy, {OpRef::res(-1), Vb, Va});
118806f32e7eSjoerg return OpRef::res(Results.top());
118906f32e7eSjoerg }
119006f32e7eSjoerg
vmuxp(ArrayRef<uint8_t> Bytes,OpRef Va,OpRef Vb,ResultStack & Results)119106f32e7eSjoerg OpRef HvxSelector::vmuxp(ArrayRef<uint8_t> Bytes, OpRef Va, OpRef Vb,
119206f32e7eSjoerg ResultStack &Results) {
119306f32e7eSjoerg DEBUG_WITH_TYPE("isel", {dbgs() << __func__ << '\n';});
119406f32e7eSjoerg size_t S = Bytes.size() / 2;
119506f32e7eSjoerg OpRef L = vmuxs(Bytes.take_front(S), OpRef::lo(Va), OpRef::lo(Vb), Results);
119606f32e7eSjoerg OpRef H = vmuxs(Bytes.drop_front(S), OpRef::hi(Va), OpRef::hi(Vb), Results);
119706f32e7eSjoerg return concat(L, H, Results);
119806f32e7eSjoerg }
119906f32e7eSjoerg
shuffs1(ShuffleMask SM,OpRef Va,ResultStack & Results)120006f32e7eSjoerg OpRef HvxSelector::shuffs1(ShuffleMask SM, OpRef Va, ResultStack &Results) {
120106f32e7eSjoerg DEBUG_WITH_TYPE("isel", {dbgs() << __func__ << '\n';});
120206f32e7eSjoerg unsigned VecLen = SM.Mask.size();
120306f32e7eSjoerg assert(HwLen == VecLen);
120406f32e7eSjoerg (void)VecLen;
120506f32e7eSjoerg assert(all_of(SM.Mask, [this](int M) { return M == -1 || M < int(HwLen); }));
120606f32e7eSjoerg
120706f32e7eSjoerg if (isIdentity(SM.Mask))
120806f32e7eSjoerg return Va;
120906f32e7eSjoerg if (isUndef(SM.Mask))
121006f32e7eSjoerg return OpRef::undef(getSingleVT(MVT::i8));
121106f32e7eSjoerg
121206f32e7eSjoerg OpRef P = perfect(SM, Va, Results);
121306f32e7eSjoerg if (P.isValid())
121406f32e7eSjoerg return P;
121506f32e7eSjoerg return butterfly(SM, Va, Results);
121606f32e7eSjoerg }
121706f32e7eSjoerg
shuffs2(ShuffleMask SM,OpRef Va,OpRef Vb,ResultStack & Results)121806f32e7eSjoerg OpRef HvxSelector::shuffs2(ShuffleMask SM, OpRef Va, OpRef Vb,
121906f32e7eSjoerg ResultStack &Results) {
122006f32e7eSjoerg DEBUG_WITH_TYPE("isel", {dbgs() << __func__ << '\n';});
122106f32e7eSjoerg if (isUndef(SM.Mask))
122206f32e7eSjoerg return OpRef::undef(getSingleVT(MVT::i8));
122306f32e7eSjoerg
122406f32e7eSjoerg OpRef C = contracting(SM, Va, Vb, Results);
122506f32e7eSjoerg if (C.isValid())
122606f32e7eSjoerg return C;
122706f32e7eSjoerg
122806f32e7eSjoerg int VecLen = SM.Mask.size();
122906f32e7eSjoerg SmallVector<int,128> NewMask(VecLen);
123006f32e7eSjoerg OpRef P = packs(SM, Va, Vb, Results, NewMask);
123106f32e7eSjoerg if (P.isValid())
123206f32e7eSjoerg return shuffs1(ShuffleMask(NewMask), P, Results);
123306f32e7eSjoerg
123406f32e7eSjoerg SmallVector<int,128> MaskL(VecLen), MaskR(VecLen);
123506f32e7eSjoerg splitMask(SM.Mask, MaskL, MaskR);
123606f32e7eSjoerg
123706f32e7eSjoerg OpRef L = shuffs1(ShuffleMask(MaskL), Va, Results);
123806f32e7eSjoerg OpRef R = shuffs1(ShuffleMask(MaskR), Vb, Results);
123906f32e7eSjoerg if (!L.isValid() || !R.isValid())
124006f32e7eSjoerg return OpRef::fail();
124106f32e7eSjoerg
124206f32e7eSjoerg SmallVector<uint8_t,128> Bytes(VecLen);
124306f32e7eSjoerg for (int I = 0; I != VecLen; ++I) {
124406f32e7eSjoerg if (MaskL[I] != -1)
124506f32e7eSjoerg Bytes[I] = 0xFF;
124606f32e7eSjoerg }
124706f32e7eSjoerg return vmuxs(Bytes, L, R, Results);
124806f32e7eSjoerg }
124906f32e7eSjoerg
shuffp1(ShuffleMask SM,OpRef Va,ResultStack & Results)125006f32e7eSjoerg OpRef HvxSelector::shuffp1(ShuffleMask SM, OpRef Va, ResultStack &Results) {
125106f32e7eSjoerg DEBUG_WITH_TYPE("isel", {dbgs() << __func__ << '\n';});
125206f32e7eSjoerg int VecLen = SM.Mask.size();
125306f32e7eSjoerg
125406f32e7eSjoerg if (isIdentity(SM.Mask))
125506f32e7eSjoerg return Va;
125606f32e7eSjoerg if (isUndef(SM.Mask))
125706f32e7eSjoerg return OpRef::undef(getPairVT(MVT::i8));
125806f32e7eSjoerg
125906f32e7eSjoerg SmallVector<int,128> PackedMask(VecLen);
126006f32e7eSjoerg OpRef P = packs(SM, OpRef::lo(Va), OpRef::hi(Va), Results, PackedMask);
126106f32e7eSjoerg if (P.isValid()) {
126206f32e7eSjoerg ShuffleMask PM(PackedMask);
126306f32e7eSjoerg OpRef E = expanding(PM, P, Results);
126406f32e7eSjoerg if (E.isValid())
126506f32e7eSjoerg return E;
126606f32e7eSjoerg
126706f32e7eSjoerg OpRef L = shuffs1(PM.lo(), P, Results);
126806f32e7eSjoerg OpRef H = shuffs1(PM.hi(), P, Results);
126906f32e7eSjoerg if (L.isValid() && H.isValid())
127006f32e7eSjoerg return concat(L, H, Results);
127106f32e7eSjoerg }
127206f32e7eSjoerg
127306f32e7eSjoerg OpRef R = perfect(SM, Va, Results);
127406f32e7eSjoerg if (R.isValid())
127506f32e7eSjoerg return R;
127606f32e7eSjoerg // TODO commute the mask and try the opposite order of the halves.
127706f32e7eSjoerg
127806f32e7eSjoerg OpRef L = shuffs2(SM.lo(), OpRef::lo(Va), OpRef::hi(Va), Results);
127906f32e7eSjoerg OpRef H = shuffs2(SM.hi(), OpRef::lo(Va), OpRef::hi(Va), Results);
128006f32e7eSjoerg if (L.isValid() && H.isValid())
128106f32e7eSjoerg return concat(L, H, Results);
128206f32e7eSjoerg
128306f32e7eSjoerg return OpRef::fail();
128406f32e7eSjoerg }
128506f32e7eSjoerg
shuffp2(ShuffleMask SM,OpRef Va,OpRef Vb,ResultStack & Results)128606f32e7eSjoerg OpRef HvxSelector::shuffp2(ShuffleMask SM, OpRef Va, OpRef Vb,
128706f32e7eSjoerg ResultStack &Results) {
128806f32e7eSjoerg DEBUG_WITH_TYPE("isel", {dbgs() << __func__ << '\n';});
128906f32e7eSjoerg if (isUndef(SM.Mask))
129006f32e7eSjoerg return OpRef::undef(getPairVT(MVT::i8));
129106f32e7eSjoerg
129206f32e7eSjoerg int VecLen = SM.Mask.size();
129306f32e7eSjoerg SmallVector<int,256> PackedMask(VecLen);
129406f32e7eSjoerg OpRef P = packp(SM, Va, Vb, Results, PackedMask);
129506f32e7eSjoerg if (P.isValid())
129606f32e7eSjoerg return shuffp1(ShuffleMask(PackedMask), P, Results);
129706f32e7eSjoerg
129806f32e7eSjoerg SmallVector<int,256> MaskL(VecLen), MaskR(VecLen);
129906f32e7eSjoerg splitMask(SM.Mask, MaskL, MaskR);
130006f32e7eSjoerg
130106f32e7eSjoerg OpRef L = shuffp1(ShuffleMask(MaskL), Va, Results);
130206f32e7eSjoerg OpRef R = shuffp1(ShuffleMask(MaskR), Vb, Results);
130306f32e7eSjoerg if (!L.isValid() || !R.isValid())
130406f32e7eSjoerg return OpRef::fail();
130506f32e7eSjoerg
130606f32e7eSjoerg // Mux the results.
130706f32e7eSjoerg SmallVector<uint8_t,256> Bytes(VecLen);
130806f32e7eSjoerg for (int I = 0; I != VecLen; ++I) {
130906f32e7eSjoerg if (MaskL[I] != -1)
131006f32e7eSjoerg Bytes[I] = 0xFF;
131106f32e7eSjoerg }
131206f32e7eSjoerg return vmuxp(Bytes, L, R, Results);
131306f32e7eSjoerg }
131406f32e7eSjoerg
131506f32e7eSjoerg namespace {
131606f32e7eSjoerg struct Deleter : public SelectionDAG::DAGNodeDeletedListener {
131706f32e7eSjoerg template <typename T>
Deleter__anon7c13adc80d11::Deleter131806f32e7eSjoerg Deleter(SelectionDAG &D, T &C)
131906f32e7eSjoerg : SelectionDAG::DAGNodeDeletedListener(D, [&C] (SDNode *N, SDNode *E) {
132006f32e7eSjoerg C.erase(N);
132106f32e7eSjoerg }) {}
132206f32e7eSjoerg };
132306f32e7eSjoerg
132406f32e7eSjoerg template <typename T>
132506f32e7eSjoerg struct NullifyingVector : public T {
132606f32e7eSjoerg DenseMap<SDNode*, SDNode**> Refs;
NullifyingVector__anon7c13adc80d11::NullifyingVector132706f32e7eSjoerg NullifyingVector(T &&V) : T(V) {
132806f32e7eSjoerg for (unsigned i = 0, e = T::size(); i != e; ++i) {
132906f32e7eSjoerg SDNode *&N = T::operator[](i);
133006f32e7eSjoerg Refs[N] = &N;
133106f32e7eSjoerg }
133206f32e7eSjoerg }
erase__anon7c13adc80d11::NullifyingVector133306f32e7eSjoerg void erase(SDNode *N) {
133406f32e7eSjoerg auto F = Refs.find(N);
133506f32e7eSjoerg if (F != Refs.end())
133606f32e7eSjoerg *F->second = nullptr;
133706f32e7eSjoerg }
133806f32e7eSjoerg };
133906f32e7eSjoerg }
134006f32e7eSjoerg
select(SDNode * ISelN)1341*da58b97aSjoerg void HvxSelector::select(SDNode *ISelN) {
1342*da58b97aSjoerg // What's important here is to select the right set of nodes. The main
1343*da58b97aSjoerg // selection algorithm loops over nodes in a topological order, i.e. users
1344*da58b97aSjoerg // are visited before their operands.
1345*da58b97aSjoerg //
1346*da58b97aSjoerg // It is an error to have an unselected node with a selected operand, and
1347*da58b97aSjoerg // there is an assertion in the main selector code to enforce that.
1348*da58b97aSjoerg //
1349*da58b97aSjoerg // Such a situation could occur if we selected a node, which is both a
1350*da58b97aSjoerg // subnode of ISelN, and a subnode of an unrelated (and yet unselected)
1351*da58b97aSjoerg // node in the DAG.
1352*da58b97aSjoerg assert(ISelN->getOpcode() == HexagonISD::ISEL);
1353*da58b97aSjoerg SDNode *N0 = ISelN->getOperand(0).getNode();
1354*da58b97aSjoerg if (N0->isMachineOpcode()) {
1355*da58b97aSjoerg ISel.ReplaceNode(ISelN, N0);
1356*da58b97aSjoerg return;
1357*da58b97aSjoerg }
1358*da58b97aSjoerg
1359*da58b97aSjoerg // There could have been nodes created (i.e. inserted into the DAG)
1360*da58b97aSjoerg // that are now dead. Remove them, in case they use any of the nodes
1361*da58b97aSjoerg // to select (and make them look shared).
1362*da58b97aSjoerg DAG.RemoveDeadNodes();
1363*da58b97aSjoerg
1364*da58b97aSjoerg SetVector<SDNode*> SubNodes, TmpQ;
1365*da58b97aSjoerg std::map<SDNode*,unsigned> NumOps;
1366*da58b97aSjoerg
1367*da58b97aSjoerg // Don't want to select N0 if it's shared with another node, except if
1368*da58b97aSjoerg // it's shared with other ISELs.
1369*da58b97aSjoerg auto IsISelN = [](SDNode *T) { return T->getOpcode() == HexagonISD::ISEL; };
1370*da58b97aSjoerg if (llvm::all_of(N0->uses(), IsISelN))
1371*da58b97aSjoerg SubNodes.insert(N0);
1372*da58b97aSjoerg
1373*da58b97aSjoerg auto InSubNodes = [&SubNodes](SDNode *T) { return SubNodes.count(T); };
1374*da58b97aSjoerg for (unsigned I = 0; I != SubNodes.size(); ++I) {
1375*da58b97aSjoerg SDNode *S = SubNodes[I];
1376*da58b97aSjoerg unsigned OpN = 0;
1377*da58b97aSjoerg // Only add subnodes that are only reachable from N0.
1378*da58b97aSjoerg for (SDValue Op : S->ops()) {
1379*da58b97aSjoerg SDNode *O = Op.getNode();
1380*da58b97aSjoerg if (llvm::all_of(O->uses(), InSubNodes)) {
1381*da58b97aSjoerg SubNodes.insert(O);
1382*da58b97aSjoerg ++OpN;
1383*da58b97aSjoerg }
1384*da58b97aSjoerg }
1385*da58b97aSjoerg NumOps.insert({S, OpN});
1386*da58b97aSjoerg if (OpN == 0)
1387*da58b97aSjoerg TmpQ.insert(S);
1388*da58b97aSjoerg }
1389*da58b97aSjoerg
1390*da58b97aSjoerg for (unsigned I = 0; I != TmpQ.size(); ++I) {
1391*da58b97aSjoerg SDNode *S = TmpQ[I];
1392*da58b97aSjoerg for (SDNode *U : S->uses()) {
1393*da58b97aSjoerg if (U == ISelN)
1394*da58b97aSjoerg continue;
1395*da58b97aSjoerg auto F = NumOps.find(U);
1396*da58b97aSjoerg assert(F != NumOps.end());
1397*da58b97aSjoerg if (F->second > 0 && !--F->second)
1398*da58b97aSjoerg TmpQ.insert(F->first);
1399*da58b97aSjoerg }
1400*da58b97aSjoerg }
1401*da58b97aSjoerg
1402*da58b97aSjoerg // Remove the marker.
1403*da58b97aSjoerg ISel.ReplaceNode(ISelN, N0);
1404*da58b97aSjoerg
1405*da58b97aSjoerg assert(SubNodes.size() == TmpQ.size());
1406*da58b97aSjoerg NullifyingVector<decltype(TmpQ)::vector_type> Queue(TmpQ.takeVector());
1407*da58b97aSjoerg
1408*da58b97aSjoerg Deleter DUQ(DAG, Queue);
1409*da58b97aSjoerg for (SDNode *S : reverse(Queue)) {
1410*da58b97aSjoerg if (S == nullptr)
1411*da58b97aSjoerg continue;
1412*da58b97aSjoerg DEBUG_WITH_TYPE("isel", {dbgs() << "HVX selecting: "; S->dump(&DAG);});
1413*da58b97aSjoerg ISel.Select(S);
1414*da58b97aSjoerg }
1415*da58b97aSjoerg }
1416*da58b97aSjoerg
scalarizeShuffle(ArrayRef<int> Mask,const SDLoc & dl,MVT ResTy,SDValue Va,SDValue Vb,SDNode * N)141706f32e7eSjoerg bool HvxSelector::scalarizeShuffle(ArrayRef<int> Mask, const SDLoc &dl,
141806f32e7eSjoerg MVT ResTy, SDValue Va, SDValue Vb,
141906f32e7eSjoerg SDNode *N) {
142006f32e7eSjoerg DEBUG_WITH_TYPE("isel", {dbgs() << __func__ << '\n';});
142106f32e7eSjoerg MVT ElemTy = ResTy.getVectorElementType();
142206f32e7eSjoerg assert(ElemTy == MVT::i8);
142306f32e7eSjoerg unsigned VecLen = Mask.size();
142406f32e7eSjoerg bool HavePairs = (2*HwLen == VecLen);
142506f32e7eSjoerg MVT SingleTy = getSingleVT(MVT::i8);
142606f32e7eSjoerg
142706f32e7eSjoerg // The prior attempts to handle this shuffle may have left a bunch of
142806f32e7eSjoerg // dead nodes in the DAG (such as constants). These nodes will be added
142906f32e7eSjoerg // at the end of DAG's node list, which at that point had already been
143006f32e7eSjoerg // sorted topologically. In the main selection loop, the node list is
143106f32e7eSjoerg // traversed backwards from the root node, which means that any new
143206f32e7eSjoerg // nodes (from the end of the list) will not be visited.
143306f32e7eSjoerg // Scalarization will replace the shuffle node with the scalarized
143406f32e7eSjoerg // expression, and if that expression reused any if the leftoever (dead)
143506f32e7eSjoerg // nodes, these nodes would not be selected (since the "local" selection
143606f32e7eSjoerg // only visits nodes that are not in AllNodes).
143706f32e7eSjoerg // To avoid this issue, remove all dead nodes from the DAG now.
1438*da58b97aSjoerg // DAG.RemoveDeadNodes();
143906f32e7eSjoerg
144006f32e7eSjoerg SmallVector<SDValue,128> Ops;
144106f32e7eSjoerg LLVMContext &Ctx = *DAG.getContext();
144206f32e7eSjoerg MVT LegalTy = Lower.getTypeToTransformTo(Ctx, ElemTy).getSimpleVT();
144306f32e7eSjoerg for (int I : Mask) {
144406f32e7eSjoerg if (I < 0) {
144506f32e7eSjoerg Ops.push_back(ISel.selectUndef(dl, LegalTy));
144606f32e7eSjoerg continue;
144706f32e7eSjoerg }
144806f32e7eSjoerg SDValue Vec;
144906f32e7eSjoerg unsigned M = I;
145006f32e7eSjoerg if (M < VecLen) {
145106f32e7eSjoerg Vec = Va;
145206f32e7eSjoerg } else {
145306f32e7eSjoerg Vec = Vb;
145406f32e7eSjoerg M -= VecLen;
145506f32e7eSjoerg }
145606f32e7eSjoerg if (HavePairs) {
145706f32e7eSjoerg if (M < HwLen) {
145806f32e7eSjoerg Vec = DAG.getTargetExtractSubreg(Hexagon::vsub_lo, dl, SingleTy, Vec);
145906f32e7eSjoerg } else {
146006f32e7eSjoerg Vec = DAG.getTargetExtractSubreg(Hexagon::vsub_hi, dl, SingleTy, Vec);
146106f32e7eSjoerg M -= HwLen;
146206f32e7eSjoerg }
146306f32e7eSjoerg }
146406f32e7eSjoerg SDValue Idx = DAG.getConstant(M, dl, MVT::i32);
146506f32e7eSjoerg SDValue Ex = DAG.getNode(ISD::EXTRACT_VECTOR_ELT, dl, LegalTy, {Vec, Idx});
146606f32e7eSjoerg SDValue L = Lower.LowerOperation(Ex, DAG);
146706f32e7eSjoerg assert(L.getNode());
146806f32e7eSjoerg Ops.push_back(L);
146906f32e7eSjoerg }
147006f32e7eSjoerg
147106f32e7eSjoerg SDValue LV;
147206f32e7eSjoerg if (2*HwLen == VecLen) {
147306f32e7eSjoerg SDValue B0 = DAG.getBuildVector(SingleTy, dl, {Ops.data(), HwLen});
147406f32e7eSjoerg SDValue L0 = Lower.LowerOperation(B0, DAG);
147506f32e7eSjoerg SDValue B1 = DAG.getBuildVector(SingleTy, dl, {Ops.data()+HwLen, HwLen});
147606f32e7eSjoerg SDValue L1 = Lower.LowerOperation(B1, DAG);
147706f32e7eSjoerg // XXX CONCAT_VECTORS is legal for HVX vectors. Legalizing (lowering)
147806f32e7eSjoerg // functions may expect to be called only for illegal operations, so
147906f32e7eSjoerg // make sure that they are not called for legal ones. Develop a better
148006f32e7eSjoerg // mechanism for dealing with this.
148106f32e7eSjoerg LV = DAG.getNode(ISD::CONCAT_VECTORS, dl, ResTy, {L0, L1});
148206f32e7eSjoerg } else {
148306f32e7eSjoerg SDValue BV = DAG.getBuildVector(ResTy, dl, Ops);
148406f32e7eSjoerg LV = Lower.LowerOperation(BV, DAG);
148506f32e7eSjoerg }
148606f32e7eSjoerg
148706f32e7eSjoerg assert(!N->use_empty());
1488*da58b97aSjoerg SDValue IS = DAG.getNode(HexagonISD::ISEL, dl, ResTy, LV);
1489*da58b97aSjoerg ISel.ReplaceNode(N, IS.getNode());
1490*da58b97aSjoerg select(IS.getNode());
149106f32e7eSjoerg DAG.RemoveDeadNodes();
149206f32e7eSjoerg return true;
149306f32e7eSjoerg }
149406f32e7eSjoerg
contracting(ShuffleMask SM,OpRef Va,OpRef Vb,ResultStack & Results)149506f32e7eSjoerg OpRef HvxSelector::contracting(ShuffleMask SM, OpRef Va, OpRef Vb,
149606f32e7eSjoerg ResultStack &Results) {
149706f32e7eSjoerg DEBUG_WITH_TYPE("isel", {dbgs() << __func__ << '\n';});
149806f32e7eSjoerg if (!Va.isValid() || !Vb.isValid())
149906f32e7eSjoerg return OpRef::fail();
150006f32e7eSjoerg
150106f32e7eSjoerg // Contracting shuffles, i.e. instructions that always discard some bytes
150206f32e7eSjoerg // from the operand vectors.
150306f32e7eSjoerg //
150406f32e7eSjoerg // V6_vshuff{e,o}b
150506f32e7eSjoerg // V6_vdealb4w
150606f32e7eSjoerg // V6_vpack{e,o}{b,h}
150706f32e7eSjoerg
150806f32e7eSjoerg int VecLen = SM.Mask.size();
150906f32e7eSjoerg std::pair<int,unsigned> Strip = findStrip(SM.Mask, 1, VecLen);
151006f32e7eSjoerg MVT ResTy = getSingleVT(MVT::i8);
151106f32e7eSjoerg
151206f32e7eSjoerg // The following shuffles only work for bytes and halfwords. This requires
151306f32e7eSjoerg // the strip length to be 1 or 2.
151406f32e7eSjoerg if (Strip.second != 1 && Strip.second != 2)
151506f32e7eSjoerg return OpRef::fail();
151606f32e7eSjoerg
151706f32e7eSjoerg // The patterns for the shuffles, in terms of the starting offsets of the
151806f32e7eSjoerg // consecutive strips (L = length of the strip, N = VecLen):
151906f32e7eSjoerg //
152006f32e7eSjoerg // vpacke: 0, 2L, 4L ... N+0, N+2L, N+4L ... L = 1 or 2
152106f32e7eSjoerg // vpacko: L, 3L, 5L ... N+L, N+3L, N+5L ... L = 1 or 2
152206f32e7eSjoerg //
152306f32e7eSjoerg // vshuffe: 0, N+0, 2L, N+2L, 4L ... L = 1 or 2
152406f32e7eSjoerg // vshuffo: L, N+L, 3L, N+3L, 5L ... L = 1 or 2
152506f32e7eSjoerg //
152606f32e7eSjoerg // vdealb4w: 0, 4, 8 ... 2, 6, 10 ... N+0, N+4, N+8 ... N+2, N+6, N+10 ...
152706f32e7eSjoerg
152806f32e7eSjoerg // The value of the element in the mask following the strip will decide
152906f32e7eSjoerg // what kind of a shuffle this can be.
153006f32e7eSjoerg int NextInMask = SM.Mask[Strip.second];
153106f32e7eSjoerg
153206f32e7eSjoerg // Check if NextInMask could be 2L, 3L or 4, i.e. if it could be a mask
153306f32e7eSjoerg // for vpack or vdealb4w. VecLen > 4, so NextInMask for vdealb4w would
153406f32e7eSjoerg // satisfy this.
153506f32e7eSjoerg if (NextInMask < VecLen) {
153606f32e7eSjoerg // vpack{e,o} or vdealb4w
153706f32e7eSjoerg if (Strip.first == 0 && Strip.second == 1 && NextInMask == 4) {
153806f32e7eSjoerg int N = VecLen;
153906f32e7eSjoerg // Check if this is vdealb4w (L=1).
154006f32e7eSjoerg for (int I = 0; I != N/4; ++I)
154106f32e7eSjoerg if (SM.Mask[I] != 4*I)
154206f32e7eSjoerg return OpRef::fail();
154306f32e7eSjoerg for (int I = 0; I != N/4; ++I)
154406f32e7eSjoerg if (SM.Mask[I+N/4] != 2 + 4*I)
154506f32e7eSjoerg return OpRef::fail();
154606f32e7eSjoerg for (int I = 0; I != N/4; ++I)
154706f32e7eSjoerg if (SM.Mask[I+N/2] != N + 4*I)
154806f32e7eSjoerg return OpRef::fail();
154906f32e7eSjoerg for (int I = 0; I != N/4; ++I)
155006f32e7eSjoerg if (SM.Mask[I+3*N/4] != N+2 + 4*I)
155106f32e7eSjoerg return OpRef::fail();
155206f32e7eSjoerg // Matched mask for vdealb4w.
155306f32e7eSjoerg Results.push(Hexagon::V6_vdealb4w, ResTy, {Vb, Va});
155406f32e7eSjoerg return OpRef::res(Results.top());
155506f32e7eSjoerg }
155606f32e7eSjoerg
155706f32e7eSjoerg // Check if this is vpack{e,o}.
155806f32e7eSjoerg int N = VecLen;
155906f32e7eSjoerg int L = Strip.second;
156006f32e7eSjoerg // Check if the first strip starts at 0 or at L.
156106f32e7eSjoerg if (Strip.first != 0 && Strip.first != L)
156206f32e7eSjoerg return OpRef::fail();
156306f32e7eSjoerg // Examine the rest of the mask.
156406f32e7eSjoerg for (int I = L; I < N; I += L) {
156506f32e7eSjoerg auto S = findStrip(SM.Mask.drop_front(I), 1, N-I);
156606f32e7eSjoerg // Check whether the mask element at the beginning of each strip
156706f32e7eSjoerg // increases by 2L each time.
156806f32e7eSjoerg if (S.first - Strip.first != 2*I)
156906f32e7eSjoerg return OpRef::fail();
157006f32e7eSjoerg // Check whether each strip is of the same length.
157106f32e7eSjoerg if (S.second != unsigned(L))
157206f32e7eSjoerg return OpRef::fail();
157306f32e7eSjoerg }
157406f32e7eSjoerg
157506f32e7eSjoerg // Strip.first == 0 => vpacke
157606f32e7eSjoerg // Strip.first == L => vpacko
157706f32e7eSjoerg assert(Strip.first == 0 || Strip.first == L);
157806f32e7eSjoerg using namespace Hexagon;
157906f32e7eSjoerg NodeTemplate Res;
158006f32e7eSjoerg Res.Opc = Strip.second == 1 // Number of bytes.
158106f32e7eSjoerg ? (Strip.first == 0 ? V6_vpackeb : V6_vpackob)
158206f32e7eSjoerg : (Strip.first == 0 ? V6_vpackeh : V6_vpackoh);
158306f32e7eSjoerg Res.Ty = ResTy;
158406f32e7eSjoerg Res.Ops = { Vb, Va };
158506f32e7eSjoerg Results.push(Res);
158606f32e7eSjoerg return OpRef::res(Results.top());
158706f32e7eSjoerg }
158806f32e7eSjoerg
158906f32e7eSjoerg // Check if this is vshuff{e,o}.
159006f32e7eSjoerg int N = VecLen;
159106f32e7eSjoerg int L = Strip.second;
159206f32e7eSjoerg std::pair<int,unsigned> PrevS = Strip;
159306f32e7eSjoerg bool Flip = false;
159406f32e7eSjoerg for (int I = L; I < N; I += L) {
159506f32e7eSjoerg auto S = findStrip(SM.Mask.drop_front(I), 1, N-I);
159606f32e7eSjoerg if (S.second != PrevS.second)
159706f32e7eSjoerg return OpRef::fail();
159806f32e7eSjoerg int Diff = Flip ? PrevS.first - S.first + 2*L
159906f32e7eSjoerg : S.first - PrevS.first;
160006f32e7eSjoerg if (Diff != N)
160106f32e7eSjoerg return OpRef::fail();
160206f32e7eSjoerg Flip ^= true;
160306f32e7eSjoerg PrevS = S;
160406f32e7eSjoerg }
160506f32e7eSjoerg // Strip.first == 0 => vshuffe
160606f32e7eSjoerg // Strip.first == L => vshuffo
160706f32e7eSjoerg assert(Strip.first == 0 || Strip.first == L);
160806f32e7eSjoerg using namespace Hexagon;
160906f32e7eSjoerg NodeTemplate Res;
161006f32e7eSjoerg Res.Opc = Strip.second == 1 // Number of bytes.
161106f32e7eSjoerg ? (Strip.first == 0 ? V6_vshuffeb : V6_vshuffob)
161206f32e7eSjoerg : (Strip.first == 0 ? V6_vshufeh : V6_vshufoh);
161306f32e7eSjoerg Res.Ty = ResTy;
161406f32e7eSjoerg Res.Ops = { Vb, Va };
161506f32e7eSjoerg Results.push(Res);
161606f32e7eSjoerg return OpRef::res(Results.top());
161706f32e7eSjoerg }
161806f32e7eSjoerg
expanding(ShuffleMask SM,OpRef Va,ResultStack & Results)161906f32e7eSjoerg OpRef HvxSelector::expanding(ShuffleMask SM, OpRef Va, ResultStack &Results) {
162006f32e7eSjoerg DEBUG_WITH_TYPE("isel", {dbgs() << __func__ << '\n';});
162106f32e7eSjoerg // Expanding shuffles (using all elements and inserting into larger vector):
162206f32e7eSjoerg //
162306f32e7eSjoerg // V6_vunpacku{b,h} [*]
162406f32e7eSjoerg //
162506f32e7eSjoerg // [*] Only if the upper elements (filled with 0s) are "don't care" in Mask.
162606f32e7eSjoerg //
162706f32e7eSjoerg // Note: V6_vunpacko{b,h} are or-ing the high byte/half in the result, so
162806f32e7eSjoerg // they are not shuffles.
162906f32e7eSjoerg //
163006f32e7eSjoerg // The argument is a single vector.
163106f32e7eSjoerg
163206f32e7eSjoerg int VecLen = SM.Mask.size();
163306f32e7eSjoerg assert(2*HwLen == unsigned(VecLen) && "Expecting vector-pair type");
163406f32e7eSjoerg
163506f32e7eSjoerg std::pair<int,unsigned> Strip = findStrip(SM.Mask, 1, VecLen);
163606f32e7eSjoerg
163706f32e7eSjoerg // The patterns for the unpacks, in terms of the starting offsets of the
163806f32e7eSjoerg // consecutive strips (L = length of the strip, N = VecLen):
163906f32e7eSjoerg //
164006f32e7eSjoerg // vunpacku: 0, -1, L, -1, 2L, -1 ...
164106f32e7eSjoerg
164206f32e7eSjoerg if (Strip.first != 0)
164306f32e7eSjoerg return OpRef::fail();
164406f32e7eSjoerg
164506f32e7eSjoerg // The vunpackus only handle byte and half-word.
164606f32e7eSjoerg if (Strip.second != 1 && Strip.second != 2)
164706f32e7eSjoerg return OpRef::fail();
164806f32e7eSjoerg
164906f32e7eSjoerg int N = VecLen;
165006f32e7eSjoerg int L = Strip.second;
165106f32e7eSjoerg
165206f32e7eSjoerg // First, check the non-ignored strips.
165306f32e7eSjoerg for (int I = 2*L; I < 2*N; I += 2*L) {
165406f32e7eSjoerg auto S = findStrip(SM.Mask.drop_front(I), 1, N-I);
165506f32e7eSjoerg if (S.second != unsigned(L))
165606f32e7eSjoerg return OpRef::fail();
165706f32e7eSjoerg if (2*S.first != I)
165806f32e7eSjoerg return OpRef::fail();
165906f32e7eSjoerg }
166006f32e7eSjoerg // Check the -1s.
166106f32e7eSjoerg for (int I = L; I < 2*N; I += 2*L) {
166206f32e7eSjoerg auto S = findStrip(SM.Mask.drop_front(I), 0, N-I);
166306f32e7eSjoerg if (S.first != -1 || S.second != unsigned(L))
166406f32e7eSjoerg return OpRef::fail();
166506f32e7eSjoerg }
166606f32e7eSjoerg
166706f32e7eSjoerg unsigned Opc = Strip.second == 1 ? Hexagon::V6_vunpackub
166806f32e7eSjoerg : Hexagon::V6_vunpackuh;
166906f32e7eSjoerg Results.push(Opc, getPairVT(MVT::i8), {Va});
167006f32e7eSjoerg return OpRef::res(Results.top());
167106f32e7eSjoerg }
167206f32e7eSjoerg
perfect(ShuffleMask SM,OpRef Va,ResultStack & Results)167306f32e7eSjoerg OpRef HvxSelector::perfect(ShuffleMask SM, OpRef Va, ResultStack &Results) {
167406f32e7eSjoerg DEBUG_WITH_TYPE("isel", {dbgs() << __func__ << '\n';});
167506f32e7eSjoerg // V6_vdeal{b,h}
167606f32e7eSjoerg // V6_vshuff{b,h}
167706f32e7eSjoerg
167806f32e7eSjoerg // V6_vshufoe{b,h} those are quivalent to vshuffvdd(..,{1,2})
167906f32e7eSjoerg // V6_vshuffvdd (V6_vshuff)
168006f32e7eSjoerg // V6_dealvdd (V6_vdeal)
168106f32e7eSjoerg
168206f32e7eSjoerg int VecLen = SM.Mask.size();
168306f32e7eSjoerg assert(isPowerOf2_32(VecLen) && Log2_32(VecLen) <= 8);
168406f32e7eSjoerg unsigned LogLen = Log2_32(VecLen);
168506f32e7eSjoerg unsigned HwLog = Log2_32(HwLen);
168606f32e7eSjoerg // The result length must be the same as the length of a single vector,
168706f32e7eSjoerg // or a vector pair.
168806f32e7eSjoerg assert(LogLen == HwLog || LogLen == HwLog+1);
1689*da58b97aSjoerg bool HavePairs = LogLen == HwLog+1;
169006f32e7eSjoerg
169106f32e7eSjoerg if (!isPermutation(SM.Mask))
169206f32e7eSjoerg return OpRef::fail();
169306f32e7eSjoerg
169406f32e7eSjoerg SmallVector<unsigned,8> Perm(LogLen);
169506f32e7eSjoerg
169606f32e7eSjoerg // Check if this could be a perfect shuffle, or a combination of perfect
169706f32e7eSjoerg // shuffles.
169806f32e7eSjoerg //
169906f32e7eSjoerg // Consider this permutation (using hex digits to make the ASCII diagrams
170006f32e7eSjoerg // easier to read):
170106f32e7eSjoerg // { 0, 8, 1, 9, 2, A, 3, B, 4, C, 5, D, 6, E, 7, F }.
170206f32e7eSjoerg // This is a "deal" operation: divide the input into two halves, and
170306f32e7eSjoerg // create the output by picking elements by alternating between these two
170406f32e7eSjoerg // halves:
170506f32e7eSjoerg // 0 1 2 3 4 5 6 7 --> 0 8 1 9 2 A 3 B 4 C 5 D 6 E 7 F [*]
170606f32e7eSjoerg // 8 9 A B C D E F
170706f32e7eSjoerg //
170806f32e7eSjoerg // Aside from a few special explicit cases (V6_vdealb, etc.), HVX provides
170906f32e7eSjoerg // a somwehat different mechanism that could be used to perform shuffle/
171006f32e7eSjoerg // deal operations: a 2x2 transpose.
171106f32e7eSjoerg // Consider the halves of inputs again, they can be interpreted as a 2x8
171206f32e7eSjoerg // matrix. A 2x8 matrix can be looked at four 2x2 matrices concatenated
171306f32e7eSjoerg // together. Now, when considering 2 elements at a time, it will be a 2x4
171406f32e7eSjoerg // matrix (with elements 01, 23, 45, etc.), or two 2x2 matrices:
171506f32e7eSjoerg // 01 23 45 67
171606f32e7eSjoerg // 89 AB CD EF
171706f32e7eSjoerg // With groups of 4, this will become a single 2x2 matrix, and so on.
171806f32e7eSjoerg //
171906f32e7eSjoerg // The 2x2 transpose instruction works by transposing each of the 2x2
172006f32e7eSjoerg // matrices (or "sub-matrices"), given a specific group size. For example,
172106f32e7eSjoerg // if the group size is 1 (i.e. each element is its own group), there
172206f32e7eSjoerg // will be four transposes of the four 2x2 matrices that form the 2x8.
172306f32e7eSjoerg // For example, with the inputs as above, the result will be:
172406f32e7eSjoerg // 0 8 2 A 4 C 6 E
172506f32e7eSjoerg // 1 9 3 B 5 D 7 F
172606f32e7eSjoerg // Now, this result can be tranposed again, but with the group size of 2:
172706f32e7eSjoerg // 08 19 4C 5D
172806f32e7eSjoerg // 2A 3B 6E 7F
172906f32e7eSjoerg // If we then transpose that result, but with the group size of 4, we get:
173006f32e7eSjoerg // 0819 2A3B
173106f32e7eSjoerg // 4C5D 6E7F
173206f32e7eSjoerg // If we concatenate these two rows, it will be
173306f32e7eSjoerg // 0 8 1 9 2 A 3 B 4 C 5 D 6 E 7 F
173406f32e7eSjoerg // which is the same as the "deal" [*] above.
173506f32e7eSjoerg //
173606f32e7eSjoerg // In general, a "deal" of individual elements is a series of 2x2 transposes,
173706f32e7eSjoerg // with changing group size. HVX has two instructions:
173806f32e7eSjoerg // Vdd = V6_vdealvdd Vu, Vv, Rt
173906f32e7eSjoerg // Vdd = V6_shufvdd Vu, Vv, Rt
174006f32e7eSjoerg // that perform exactly that. The register Rt controls which transposes are
174106f32e7eSjoerg // going to happen: a bit at position n (counting from 0) indicates that a
174206f32e7eSjoerg // transpose with a group size of 2^n will take place. If multiple bits are
174306f32e7eSjoerg // set, multiple transposes will happen: vdealvdd will perform them starting
174406f32e7eSjoerg // with the largest group size, vshuffvdd will do them in the reverse order.
174506f32e7eSjoerg //
174606f32e7eSjoerg // The main observation is that each 2x2 transpose corresponds to swapping
174706f32e7eSjoerg // columns of bits in the binary representation of the values.
174806f32e7eSjoerg //
174906f32e7eSjoerg // The numbers {3,2,1,0} and the log2 of the number of contiguous 1 bits
175006f32e7eSjoerg // in a given column. The * denote the columns that will be swapped.
175106f32e7eSjoerg // The transpose with the group size 2^n corresponds to swapping columns
175206f32e7eSjoerg // 3 (the highest log) and log2(n):
175306f32e7eSjoerg //
175406f32e7eSjoerg // 3 2 1 0 0 2 1 3 0 2 3 1
175506f32e7eSjoerg // * * * * * *
175606f32e7eSjoerg // 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
175706f32e7eSjoerg // 1 0 0 0 1 8 1 0 0 0 8 1 0 0 0 8 1 0 0 0
175806f32e7eSjoerg // 2 0 0 1 0 2 0 0 1 0 1 0 0 0 1 1 0 0 0 1
175906f32e7eSjoerg // 3 0 0 1 1 A 1 0 1 0 9 1 0 0 1 9 1 0 0 1
176006f32e7eSjoerg // 4 0 1 0 0 4 0 1 0 0 4 0 1 0 0 2 0 0 1 0
176106f32e7eSjoerg // 5 0 1 0 1 C 1 1 0 0 C 1 1 0 0 A 1 0 1 0
176206f32e7eSjoerg // 6 0 1 1 0 6 0 1 1 0 5 0 1 0 1 3 0 0 1 1
176306f32e7eSjoerg // 7 0 1 1 1 E 1 1 1 0 D 1 1 0 1 B 1 0 1 1
176406f32e7eSjoerg // 8 1 0 0 0 1 0 0 0 1 2 0 0 1 0 4 0 1 0 0
176506f32e7eSjoerg // 9 1 0 0 1 9 1 0 0 1 A 1 0 1 0 C 1 1 0 0
176606f32e7eSjoerg // A 1 0 1 0 3 0 0 1 1 3 0 0 1 1 5 0 1 0 1
176706f32e7eSjoerg // B 1 0 1 1 B 1 0 1 1 B 1 0 1 1 D 1 1 0 1
176806f32e7eSjoerg // C 1 1 0 0 5 0 1 0 1 6 0 1 1 0 6 0 1 1 0
176906f32e7eSjoerg // D 1 1 0 1 D 1 1 0 1 E 1 1 1 0 E 1 1 1 0
177006f32e7eSjoerg // E 1 1 1 0 7 0 1 1 1 7 0 1 1 1 7 0 1 1 1
177106f32e7eSjoerg // F 1 1 1 1 F 1 1 1 1 F 1 1 1 1 F 1 1 1 1
177206f32e7eSjoerg
1773*da58b97aSjoerg // There is one special case that is not a perfect shuffle, but
1774*da58b97aSjoerg // can be turned into one easily: when the shuffle operates on
1775*da58b97aSjoerg // a vector pair, but the two vectors in the pair are swapped.
1776*da58b97aSjoerg // The code below that identifies perfect shuffles will reject
1777*da58b97aSjoerg // it, unless the order is reversed.
1778*da58b97aSjoerg SmallVector<int,128> MaskStorage(SM.Mask.begin(), SM.Mask.end());
1779*da58b97aSjoerg bool InvertedPair = false;
1780*da58b97aSjoerg if (HavePairs && SM.Mask[0] >= int(HwLen)) {
1781*da58b97aSjoerg for (int i = 0, e = SM.Mask.size(); i != e; ++i) {
1782*da58b97aSjoerg int M = SM.Mask[i];
1783*da58b97aSjoerg MaskStorage[i] = M >= int(HwLen) ? M-HwLen : M+HwLen;
1784*da58b97aSjoerg }
1785*da58b97aSjoerg InvertedPair = true;
1786*da58b97aSjoerg }
1787*da58b97aSjoerg ArrayRef<int> LocalMask(MaskStorage);
1788*da58b97aSjoerg
178906f32e7eSjoerg auto XorPow2 = [] (ArrayRef<int> Mask, unsigned Num) {
179006f32e7eSjoerg unsigned X = Mask[0] ^ Mask[Num/2];
179106f32e7eSjoerg // Check that the first half has the X's bits clear.
179206f32e7eSjoerg if ((Mask[0] & X) != 0)
179306f32e7eSjoerg return 0u;
179406f32e7eSjoerg for (unsigned I = 1; I != Num/2; ++I) {
179506f32e7eSjoerg if (unsigned(Mask[I] ^ Mask[I+Num/2]) != X)
179606f32e7eSjoerg return 0u;
179706f32e7eSjoerg if ((Mask[I] & X) != 0)
179806f32e7eSjoerg return 0u;
179906f32e7eSjoerg }
180006f32e7eSjoerg return X;
180106f32e7eSjoerg };
180206f32e7eSjoerg
180306f32e7eSjoerg // Create a vector of log2's for each column: Perm[i] corresponds to
180406f32e7eSjoerg // the i-th bit (lsb is 0).
180506f32e7eSjoerg assert(VecLen > 2);
180606f32e7eSjoerg for (unsigned I = VecLen; I >= 2; I >>= 1) {
180706f32e7eSjoerg // Examine the initial segment of Mask of size I.
1808*da58b97aSjoerg unsigned X = XorPow2(LocalMask, I);
180906f32e7eSjoerg if (!isPowerOf2_32(X))
181006f32e7eSjoerg return OpRef::fail();
181106f32e7eSjoerg // Check the other segments of Mask.
181206f32e7eSjoerg for (int J = I; J < VecLen; J += I) {
1813*da58b97aSjoerg if (XorPow2(LocalMask.slice(J, I), I) != X)
181406f32e7eSjoerg return OpRef::fail();
181506f32e7eSjoerg }
181606f32e7eSjoerg Perm[Log2_32(X)] = Log2_32(I)-1;
181706f32e7eSjoerg }
181806f32e7eSjoerg
181906f32e7eSjoerg // Once we have Perm, represent it as cycles. Denote the maximum log2
182006f32e7eSjoerg // (equal to log2(VecLen)-1) as M. The cycle containing M can then be
182106f32e7eSjoerg // written as (M a1 a2 a3 ... an). That cycle can be broken up into
182206f32e7eSjoerg // simple swaps as (M a1)(M a2)(M a3)...(M an), with the composition
182306f32e7eSjoerg // order being from left to right. Any (contiguous) segment where the
182406f32e7eSjoerg // values ai, ai+1...aj are either all increasing or all decreasing,
182506f32e7eSjoerg // can be implemented via a single vshuffvdd/vdealvdd respectively.
182606f32e7eSjoerg //
182706f32e7eSjoerg // If there is a cycle (a1 a2 ... an) that does not involve M, it can
182806f32e7eSjoerg // be written as (M an)(a1 a2 ... an)(M a1). The first two cycles can
182906f32e7eSjoerg // then be folded to get (M a1 a2 ... an)(M a1), and the above procedure
183006f32e7eSjoerg // can be used to generate a sequence of vshuffvdd/vdealvdd.
183106f32e7eSjoerg //
183206f32e7eSjoerg // Example:
183306f32e7eSjoerg // Assume M = 4 and consider a permutation (0 1)(2 3). It can be written
183406f32e7eSjoerg // as (4 0 1)(4 0) composed with (4 2 3)(4 2), or simply
183506f32e7eSjoerg // (4 0 1)(4 0)(4 2 3)(4 2).
183606f32e7eSjoerg // It can then be expanded into swaps as
183706f32e7eSjoerg // (4 0)(4 1)(4 0)(4 2)(4 3)(4 2),
183806f32e7eSjoerg // and broken up into "increasing" segments as
183906f32e7eSjoerg // [(4 0)(4 1)] [(4 0)(4 2)(4 3)] [(4 2)].
184006f32e7eSjoerg // This is equivalent to
184106f32e7eSjoerg // (4 0 1)(4 0 2 3)(4 2),
184206f32e7eSjoerg // which can be implemented as 3 vshufvdd instructions.
184306f32e7eSjoerg
184406f32e7eSjoerg using CycleType = SmallVector<unsigned,8>;
184506f32e7eSjoerg std::set<CycleType> Cycles;
184606f32e7eSjoerg std::set<unsigned> All;
184706f32e7eSjoerg
184806f32e7eSjoerg for (unsigned I : Perm)
184906f32e7eSjoerg All.insert(I);
185006f32e7eSjoerg
185106f32e7eSjoerg // If the cycle contains LogLen-1, move it to the front of the cycle.
185206f32e7eSjoerg // Otherwise, return the cycle unchanged.
185306f32e7eSjoerg auto canonicalize = [LogLen](const CycleType &C) -> CycleType {
185406f32e7eSjoerg unsigned LogPos, N = C.size();
185506f32e7eSjoerg for (LogPos = 0; LogPos != N; ++LogPos)
185606f32e7eSjoerg if (C[LogPos] == LogLen-1)
185706f32e7eSjoerg break;
185806f32e7eSjoerg if (LogPos == N)
185906f32e7eSjoerg return C;
186006f32e7eSjoerg
186106f32e7eSjoerg CycleType NewC(C.begin()+LogPos, C.end());
186206f32e7eSjoerg NewC.append(C.begin(), C.begin()+LogPos);
186306f32e7eSjoerg return NewC;
186406f32e7eSjoerg };
186506f32e7eSjoerg
186606f32e7eSjoerg auto pfs = [](const std::set<CycleType> &Cs, unsigned Len) {
186706f32e7eSjoerg // Ordering: shuff: 5 0 1 2 3 4, deal: 5 4 3 2 1 0 (for Log=6),
186806f32e7eSjoerg // for bytes zero is included, for halfwords is not.
186906f32e7eSjoerg if (Cs.size() != 1)
187006f32e7eSjoerg return 0u;
187106f32e7eSjoerg const CycleType &C = *Cs.begin();
187206f32e7eSjoerg if (C[0] != Len-1)
187306f32e7eSjoerg return 0u;
187406f32e7eSjoerg int D = Len - C.size();
187506f32e7eSjoerg if (D != 0 && D != 1)
187606f32e7eSjoerg return 0u;
187706f32e7eSjoerg
187806f32e7eSjoerg bool IsDeal = true, IsShuff = true;
187906f32e7eSjoerg for (unsigned I = 1; I != Len-D; ++I) {
188006f32e7eSjoerg if (C[I] != Len-1-I)
188106f32e7eSjoerg IsDeal = false;
188206f32e7eSjoerg if (C[I] != I-(1-D)) // I-1, I
188306f32e7eSjoerg IsShuff = false;
188406f32e7eSjoerg }
188506f32e7eSjoerg // At most one, IsDeal or IsShuff, can be non-zero.
188606f32e7eSjoerg assert(!(IsDeal || IsShuff) || IsDeal != IsShuff);
188706f32e7eSjoerg static unsigned Deals[] = { Hexagon::V6_vdealb, Hexagon::V6_vdealh };
188806f32e7eSjoerg static unsigned Shufs[] = { Hexagon::V6_vshuffb, Hexagon::V6_vshuffh };
188906f32e7eSjoerg return IsDeal ? Deals[D] : (IsShuff ? Shufs[D] : 0);
189006f32e7eSjoerg };
189106f32e7eSjoerg
189206f32e7eSjoerg while (!All.empty()) {
189306f32e7eSjoerg unsigned A = *All.begin();
189406f32e7eSjoerg All.erase(A);
189506f32e7eSjoerg CycleType C;
189606f32e7eSjoerg C.push_back(A);
189706f32e7eSjoerg for (unsigned B = Perm[A]; B != A; B = Perm[B]) {
189806f32e7eSjoerg C.push_back(B);
189906f32e7eSjoerg All.erase(B);
190006f32e7eSjoerg }
190106f32e7eSjoerg if (C.size() <= 1)
190206f32e7eSjoerg continue;
190306f32e7eSjoerg Cycles.insert(canonicalize(C));
190406f32e7eSjoerg }
190506f32e7eSjoerg
190606f32e7eSjoerg MVT SingleTy = getSingleVT(MVT::i8);
190706f32e7eSjoerg MVT PairTy = getPairVT(MVT::i8);
190806f32e7eSjoerg
190906f32e7eSjoerg // Recognize patterns for V6_vdeal{b,h} and V6_vshuff{b,h}.
191006f32e7eSjoerg if (unsigned(VecLen) == HwLen) {
191106f32e7eSjoerg if (unsigned SingleOpc = pfs(Cycles, LogLen)) {
191206f32e7eSjoerg Results.push(SingleOpc, SingleTy, {Va});
191306f32e7eSjoerg return OpRef::res(Results.top());
191406f32e7eSjoerg }
191506f32e7eSjoerg }
191606f32e7eSjoerg
1917*da58b97aSjoerg // From the cycles, construct the sequence of values that will
1918*da58b97aSjoerg // then form the control values for vdealvdd/vshuffvdd, i.e.
1919*da58b97aSjoerg // (M a1 a2)(M a3 a4 a5)... -> a1 a2 a3 a4 a5
1920*da58b97aSjoerg // This essentially strips the M value from the cycles where
1921*da58b97aSjoerg // it's present, and performs the insertion of M (then stripping)
1922*da58b97aSjoerg // for cycles without M (as described in an earlier comment).
192306f32e7eSjoerg SmallVector<unsigned,8> SwapElems;
1924*da58b97aSjoerg // When the input is extended (i.e. single vector becomes a pair),
1925*da58b97aSjoerg // this is done by using an "undef" vector as the second input.
1926*da58b97aSjoerg // However, then we get
1927*da58b97aSjoerg // input 1: GOODBITS
1928*da58b97aSjoerg // input 2: ........
1929*da58b97aSjoerg // but we need
1930*da58b97aSjoerg // input 1: ....BITS
1931*da58b97aSjoerg // input 2: ....GOOD
1932*da58b97aSjoerg // Then at the end, this needs to be undone. To accomplish this,
1933*da58b97aSjoerg // artificially add "LogLen-1" at both ends of the sequence.
1934*da58b97aSjoerg if (!HavePairs)
193506f32e7eSjoerg SwapElems.push_back(LogLen-1);
193606f32e7eSjoerg for (const CycleType &C : Cycles) {
1937*da58b97aSjoerg // Do the transformation: (a1..an) -> (M a1..an)(M a1).
193806f32e7eSjoerg unsigned First = (C[0] == LogLen-1) ? 1 : 0;
193906f32e7eSjoerg SwapElems.append(C.begin()+First, C.end());
194006f32e7eSjoerg if (First == 0)
194106f32e7eSjoerg SwapElems.push_back(C[0]);
194206f32e7eSjoerg }
1943*da58b97aSjoerg if (!HavePairs)
1944*da58b97aSjoerg SwapElems.push_back(LogLen-1);
194506f32e7eSjoerg
194606f32e7eSjoerg const SDLoc &dl(Results.InpNode);
1947*da58b97aSjoerg OpRef Arg = HavePairs ? Va
194806f32e7eSjoerg : concat(Va, OpRef::undef(SingleTy), Results);
1949*da58b97aSjoerg if (InvertedPair)
1950*da58b97aSjoerg Arg = concat(OpRef::hi(Arg), OpRef::lo(Arg), Results);
195106f32e7eSjoerg
195206f32e7eSjoerg for (unsigned I = 0, E = SwapElems.size(); I != E; ) {
195306f32e7eSjoerg bool IsInc = I == E-1 || SwapElems[I] < SwapElems[I+1];
195406f32e7eSjoerg unsigned S = (1u << SwapElems[I]);
195506f32e7eSjoerg if (I < E-1) {
195606f32e7eSjoerg while (++I < E-1 && IsInc == (SwapElems[I] < SwapElems[I+1]))
195706f32e7eSjoerg S |= 1u << SwapElems[I];
195806f32e7eSjoerg // The above loop will not add a bit for the final SwapElems[I+1],
195906f32e7eSjoerg // so add it here.
196006f32e7eSjoerg S |= 1u << SwapElems[I];
196106f32e7eSjoerg }
196206f32e7eSjoerg ++I;
196306f32e7eSjoerg
196406f32e7eSjoerg NodeTemplate Res;
196506f32e7eSjoerg Results.push(Hexagon::A2_tfrsi, MVT::i32,
196606f32e7eSjoerg { DAG.getTargetConstant(S, dl, MVT::i32) });
196706f32e7eSjoerg Res.Opc = IsInc ? Hexagon::V6_vshuffvdd : Hexagon::V6_vdealvdd;
196806f32e7eSjoerg Res.Ty = PairTy;
196906f32e7eSjoerg Res.Ops = { OpRef::hi(Arg), OpRef::lo(Arg), OpRef::res(-1) };
197006f32e7eSjoerg Results.push(Res);
197106f32e7eSjoerg Arg = OpRef::res(Results.top());
197206f32e7eSjoerg }
197306f32e7eSjoerg
1974*da58b97aSjoerg return HavePairs ? Arg : OpRef::lo(Arg);
197506f32e7eSjoerg }
197606f32e7eSjoerg
butterfly(ShuffleMask SM,OpRef Va,ResultStack & Results)197706f32e7eSjoerg OpRef HvxSelector::butterfly(ShuffleMask SM, OpRef Va, ResultStack &Results) {
197806f32e7eSjoerg DEBUG_WITH_TYPE("isel", {dbgs() << __func__ << '\n';});
197906f32e7eSjoerg // Butterfly shuffles.
198006f32e7eSjoerg //
198106f32e7eSjoerg // V6_vdelta
198206f32e7eSjoerg // V6_vrdelta
198306f32e7eSjoerg // V6_vror
198406f32e7eSjoerg
198506f32e7eSjoerg // The assumption here is that all elements picked by Mask are in the
198606f32e7eSjoerg // first operand to the vector_shuffle. This assumption is enforced
198706f32e7eSjoerg // by the caller.
198806f32e7eSjoerg
198906f32e7eSjoerg MVT ResTy = getSingleVT(MVT::i8);
199006f32e7eSjoerg PermNetwork::Controls FC, RC;
199106f32e7eSjoerg const SDLoc &dl(Results.InpNode);
199206f32e7eSjoerg int VecLen = SM.Mask.size();
199306f32e7eSjoerg
199406f32e7eSjoerg for (int M : SM.Mask) {
199506f32e7eSjoerg if (M != -1 && M >= VecLen)
199606f32e7eSjoerg return OpRef::fail();
199706f32e7eSjoerg }
199806f32e7eSjoerg
199906f32e7eSjoerg // Try the deltas/benes for both single vectors and vector pairs.
200006f32e7eSjoerg ForwardDeltaNetwork FN(SM.Mask);
200106f32e7eSjoerg if (FN.run(FC)) {
200206f32e7eSjoerg SDValue Ctl = getVectorConstant(FC, dl);
200306f32e7eSjoerg Results.push(Hexagon::V6_vdelta, ResTy, {Va, OpRef(Ctl)});
200406f32e7eSjoerg return OpRef::res(Results.top());
200506f32e7eSjoerg }
200606f32e7eSjoerg
200706f32e7eSjoerg // Try reverse delta.
200806f32e7eSjoerg ReverseDeltaNetwork RN(SM.Mask);
200906f32e7eSjoerg if (RN.run(RC)) {
201006f32e7eSjoerg SDValue Ctl = getVectorConstant(RC, dl);
201106f32e7eSjoerg Results.push(Hexagon::V6_vrdelta, ResTy, {Va, OpRef(Ctl)});
201206f32e7eSjoerg return OpRef::res(Results.top());
201306f32e7eSjoerg }
201406f32e7eSjoerg
201506f32e7eSjoerg // Do Benes.
201606f32e7eSjoerg BenesNetwork BN(SM.Mask);
201706f32e7eSjoerg if (BN.run(FC, RC)) {
201806f32e7eSjoerg SDValue CtlF = getVectorConstant(FC, dl);
201906f32e7eSjoerg SDValue CtlR = getVectorConstant(RC, dl);
202006f32e7eSjoerg Results.push(Hexagon::V6_vdelta, ResTy, {Va, OpRef(CtlF)});
202106f32e7eSjoerg Results.push(Hexagon::V6_vrdelta, ResTy,
202206f32e7eSjoerg {OpRef::res(-1), OpRef(CtlR)});
202306f32e7eSjoerg return OpRef::res(Results.top());
202406f32e7eSjoerg }
202506f32e7eSjoerg
202606f32e7eSjoerg return OpRef::fail();
202706f32e7eSjoerg }
202806f32e7eSjoerg
getVectorConstant(ArrayRef<uint8_t> Data,const SDLoc & dl)202906f32e7eSjoerg SDValue HvxSelector::getVectorConstant(ArrayRef<uint8_t> Data,
203006f32e7eSjoerg const SDLoc &dl) {
203106f32e7eSjoerg SmallVector<SDValue, 128> Elems;
203206f32e7eSjoerg for (uint8_t C : Data)
203306f32e7eSjoerg Elems.push_back(DAG.getConstant(C, dl, MVT::i8));
203406f32e7eSjoerg MVT VecTy = MVT::getVectorVT(MVT::i8, Data.size());
203506f32e7eSjoerg SDValue BV = DAG.getBuildVector(VecTy, dl, Elems);
203606f32e7eSjoerg SDValue LV = Lower.LowerOperation(BV, DAG);
203706f32e7eSjoerg DAG.RemoveDeadNode(BV.getNode());
2038*da58b97aSjoerg return DAG.getNode(HexagonISD::ISEL, dl, VecTy, LV);
203906f32e7eSjoerg }
204006f32e7eSjoerg
selectShuffle(SDNode * N)204106f32e7eSjoerg void HvxSelector::selectShuffle(SDNode *N) {
204206f32e7eSjoerg DEBUG_WITH_TYPE("isel", {
204306f32e7eSjoerg dbgs() << "Starting " << __func__ << " on node:\n";
204406f32e7eSjoerg N->dump(&DAG);
204506f32e7eSjoerg });
204606f32e7eSjoerg MVT ResTy = N->getValueType(0).getSimpleVT();
204706f32e7eSjoerg // Assume that vector shuffles operate on vectors of bytes.
204806f32e7eSjoerg assert(ResTy.isVector() && ResTy.getVectorElementType() == MVT::i8);
204906f32e7eSjoerg
205006f32e7eSjoerg auto *SN = cast<ShuffleVectorSDNode>(N);
205106f32e7eSjoerg std::vector<int> Mask(SN->getMask().begin(), SN->getMask().end());
205206f32e7eSjoerg // This shouldn't really be necessary. Is it?
205306f32e7eSjoerg for (int &Idx : Mask)
205406f32e7eSjoerg if (Idx != -1 && Idx < 0)
205506f32e7eSjoerg Idx = -1;
205606f32e7eSjoerg
205706f32e7eSjoerg unsigned VecLen = Mask.size();
205806f32e7eSjoerg bool HavePairs = (2*HwLen == VecLen);
205906f32e7eSjoerg assert(ResTy.getSizeInBits() / 8 == VecLen);
206006f32e7eSjoerg
206106f32e7eSjoerg // Vd = vector_shuffle Va, Vb, Mask
206206f32e7eSjoerg //
206306f32e7eSjoerg
206406f32e7eSjoerg bool UseLeft = false, UseRight = false;
206506f32e7eSjoerg for (unsigned I = 0; I != VecLen; ++I) {
206606f32e7eSjoerg if (Mask[I] == -1)
206706f32e7eSjoerg continue;
206806f32e7eSjoerg unsigned Idx = Mask[I];
206906f32e7eSjoerg assert(Idx < 2*VecLen);
207006f32e7eSjoerg if (Idx < VecLen)
207106f32e7eSjoerg UseLeft = true;
207206f32e7eSjoerg else
207306f32e7eSjoerg UseRight = true;
207406f32e7eSjoerg }
207506f32e7eSjoerg
207606f32e7eSjoerg DEBUG_WITH_TYPE("isel", {
207706f32e7eSjoerg dbgs() << "VecLen=" << VecLen << " HwLen=" << HwLen << " UseLeft="
207806f32e7eSjoerg << UseLeft << " UseRight=" << UseRight << " HavePairs="
207906f32e7eSjoerg << HavePairs << '\n';
208006f32e7eSjoerg });
208106f32e7eSjoerg // If the mask is all -1's, generate "undef".
208206f32e7eSjoerg if (!UseLeft && !UseRight) {
208306f32e7eSjoerg ISel.ReplaceNode(N, ISel.selectUndef(SDLoc(SN), ResTy).getNode());
208406f32e7eSjoerg return;
208506f32e7eSjoerg }
208606f32e7eSjoerg
208706f32e7eSjoerg SDValue Vec0 = N->getOperand(0);
208806f32e7eSjoerg SDValue Vec1 = N->getOperand(1);
208906f32e7eSjoerg ResultStack Results(SN);
209006f32e7eSjoerg Results.push(TargetOpcode::COPY, ResTy, {Vec0});
209106f32e7eSjoerg Results.push(TargetOpcode::COPY, ResTy, {Vec1});
209206f32e7eSjoerg OpRef Va = OpRef::res(Results.top()-1);
209306f32e7eSjoerg OpRef Vb = OpRef::res(Results.top());
209406f32e7eSjoerg
209506f32e7eSjoerg OpRef Res = !HavePairs ? shuffs2(ShuffleMask(Mask), Va, Vb, Results)
209606f32e7eSjoerg : shuffp2(ShuffleMask(Mask), Va, Vb, Results);
209706f32e7eSjoerg
209806f32e7eSjoerg bool Done = Res.isValid();
209906f32e7eSjoerg if (Done) {
210006f32e7eSjoerg // Make sure that Res is on the stack before materializing.
210106f32e7eSjoerg Results.push(TargetOpcode::COPY, ResTy, {Res});
210206f32e7eSjoerg materialize(Results);
210306f32e7eSjoerg } else {
210406f32e7eSjoerg Done = scalarizeShuffle(Mask, SDLoc(N), ResTy, Vec0, Vec1, N);
210506f32e7eSjoerg }
210606f32e7eSjoerg
210706f32e7eSjoerg if (!Done) {
210806f32e7eSjoerg #ifndef NDEBUG
210906f32e7eSjoerg dbgs() << "Unhandled shuffle:\n";
211006f32e7eSjoerg SN->dumpr(&DAG);
211106f32e7eSjoerg #endif
211206f32e7eSjoerg llvm_unreachable("Failed to select vector shuffle");
211306f32e7eSjoerg }
211406f32e7eSjoerg }
211506f32e7eSjoerg
selectRor(SDNode * N)211606f32e7eSjoerg void HvxSelector::selectRor(SDNode *N) {
211706f32e7eSjoerg // If this is a rotation by less than 8, use V6_valignbi.
211806f32e7eSjoerg MVT Ty = N->getValueType(0).getSimpleVT();
211906f32e7eSjoerg const SDLoc &dl(N);
212006f32e7eSjoerg SDValue VecV = N->getOperand(0);
212106f32e7eSjoerg SDValue RotV = N->getOperand(1);
212206f32e7eSjoerg SDNode *NewN = nullptr;
212306f32e7eSjoerg
212406f32e7eSjoerg if (auto *CN = dyn_cast<ConstantSDNode>(RotV.getNode())) {
212506f32e7eSjoerg unsigned S = CN->getZExtValue() % HST.getVectorLength();
212606f32e7eSjoerg if (S == 0) {
212706f32e7eSjoerg NewN = VecV.getNode();
212806f32e7eSjoerg } else if (isUInt<3>(S)) {
212906f32e7eSjoerg SDValue C = DAG.getTargetConstant(S, dl, MVT::i32);
213006f32e7eSjoerg NewN = DAG.getMachineNode(Hexagon::V6_valignbi, dl, Ty,
213106f32e7eSjoerg {VecV, VecV, C});
213206f32e7eSjoerg }
213306f32e7eSjoerg }
213406f32e7eSjoerg
213506f32e7eSjoerg if (!NewN)
213606f32e7eSjoerg NewN = DAG.getMachineNode(Hexagon::V6_vror, dl, Ty, {VecV, RotV});
213706f32e7eSjoerg
213806f32e7eSjoerg ISel.ReplaceNode(N, NewN);
213906f32e7eSjoerg }
214006f32e7eSjoerg
selectVAlign(SDNode * N)214106f32e7eSjoerg void HvxSelector::selectVAlign(SDNode *N) {
214206f32e7eSjoerg SDValue Vv = N->getOperand(0);
214306f32e7eSjoerg SDValue Vu = N->getOperand(1);
214406f32e7eSjoerg SDValue Rt = N->getOperand(2);
214506f32e7eSjoerg SDNode *NewN = DAG.getMachineNode(Hexagon::V6_valignb, SDLoc(N),
214606f32e7eSjoerg N->getValueType(0), {Vv, Vu, Rt});
214706f32e7eSjoerg ISel.ReplaceNode(N, NewN);
214806f32e7eSjoerg DAG.RemoveDeadNode(N);
214906f32e7eSjoerg }
215006f32e7eSjoerg
SelectHvxShuffle(SDNode * N)215106f32e7eSjoerg void HexagonDAGToDAGISel::SelectHvxShuffle(SDNode *N) {
215206f32e7eSjoerg HvxSelector(*this, *CurDAG).selectShuffle(N);
215306f32e7eSjoerg }
215406f32e7eSjoerg
SelectHvxRor(SDNode * N)215506f32e7eSjoerg void HexagonDAGToDAGISel::SelectHvxRor(SDNode *N) {
215606f32e7eSjoerg HvxSelector(*this, *CurDAG).selectRor(N);
215706f32e7eSjoerg }
215806f32e7eSjoerg
SelectHvxVAlign(SDNode * N)215906f32e7eSjoerg void HexagonDAGToDAGISel::SelectHvxVAlign(SDNode *N) {
216006f32e7eSjoerg HvxSelector(*this, *CurDAG).selectVAlign(N);
216106f32e7eSjoerg }
216206f32e7eSjoerg
SelectV65GatherPred(SDNode * N)216306f32e7eSjoerg void HexagonDAGToDAGISel::SelectV65GatherPred(SDNode *N) {
216406f32e7eSjoerg const SDLoc &dl(N);
216506f32e7eSjoerg SDValue Chain = N->getOperand(0);
216606f32e7eSjoerg SDValue Address = N->getOperand(2);
216706f32e7eSjoerg SDValue Predicate = N->getOperand(3);
216806f32e7eSjoerg SDValue Base = N->getOperand(4);
216906f32e7eSjoerg SDValue Modifier = N->getOperand(5);
217006f32e7eSjoerg SDValue Offset = N->getOperand(6);
217106f32e7eSjoerg
217206f32e7eSjoerg unsigned Opcode;
217306f32e7eSjoerg unsigned IntNo = cast<ConstantSDNode>(N->getOperand(1))->getZExtValue();
217406f32e7eSjoerg switch (IntNo) {
217506f32e7eSjoerg default:
217606f32e7eSjoerg llvm_unreachable("Unexpected HVX gather intrinsic.");
217706f32e7eSjoerg case Intrinsic::hexagon_V6_vgathermhq:
217806f32e7eSjoerg case Intrinsic::hexagon_V6_vgathermhq_128B:
217906f32e7eSjoerg Opcode = Hexagon::V6_vgathermhq_pseudo;
218006f32e7eSjoerg break;
218106f32e7eSjoerg case Intrinsic::hexagon_V6_vgathermwq:
218206f32e7eSjoerg case Intrinsic::hexagon_V6_vgathermwq_128B:
218306f32e7eSjoerg Opcode = Hexagon::V6_vgathermwq_pseudo;
218406f32e7eSjoerg break;
218506f32e7eSjoerg case Intrinsic::hexagon_V6_vgathermhwq:
218606f32e7eSjoerg case Intrinsic::hexagon_V6_vgathermhwq_128B:
218706f32e7eSjoerg Opcode = Hexagon::V6_vgathermhwq_pseudo;
218806f32e7eSjoerg break;
218906f32e7eSjoerg }
219006f32e7eSjoerg
219106f32e7eSjoerg SDVTList VTs = CurDAG->getVTList(MVT::Other);
219206f32e7eSjoerg SDValue Ops[] = { Address, Predicate, Base, Modifier, Offset, Chain };
219306f32e7eSjoerg SDNode *Result = CurDAG->getMachineNode(Opcode, dl, VTs, Ops);
219406f32e7eSjoerg
219506f32e7eSjoerg MachineMemOperand *MemOp = cast<MemIntrinsicSDNode>(N)->getMemOperand();
219606f32e7eSjoerg CurDAG->setNodeMemRefs(cast<MachineSDNode>(Result), {MemOp});
219706f32e7eSjoerg
219806f32e7eSjoerg ReplaceNode(N, Result);
219906f32e7eSjoerg }
220006f32e7eSjoerg
SelectV65Gather(SDNode * N)220106f32e7eSjoerg void HexagonDAGToDAGISel::SelectV65Gather(SDNode *N) {
220206f32e7eSjoerg const SDLoc &dl(N);
220306f32e7eSjoerg SDValue Chain = N->getOperand(0);
220406f32e7eSjoerg SDValue Address = N->getOperand(2);
220506f32e7eSjoerg SDValue Base = N->getOperand(3);
220606f32e7eSjoerg SDValue Modifier = N->getOperand(4);
220706f32e7eSjoerg SDValue Offset = N->getOperand(5);
220806f32e7eSjoerg
220906f32e7eSjoerg unsigned Opcode;
221006f32e7eSjoerg unsigned IntNo = cast<ConstantSDNode>(N->getOperand(1))->getZExtValue();
221106f32e7eSjoerg switch (IntNo) {
221206f32e7eSjoerg default:
221306f32e7eSjoerg llvm_unreachable("Unexpected HVX gather intrinsic.");
221406f32e7eSjoerg case Intrinsic::hexagon_V6_vgathermh:
221506f32e7eSjoerg case Intrinsic::hexagon_V6_vgathermh_128B:
221606f32e7eSjoerg Opcode = Hexagon::V6_vgathermh_pseudo;
221706f32e7eSjoerg break;
221806f32e7eSjoerg case Intrinsic::hexagon_V6_vgathermw:
221906f32e7eSjoerg case Intrinsic::hexagon_V6_vgathermw_128B:
222006f32e7eSjoerg Opcode = Hexagon::V6_vgathermw_pseudo;
222106f32e7eSjoerg break;
222206f32e7eSjoerg case Intrinsic::hexagon_V6_vgathermhw:
222306f32e7eSjoerg case Intrinsic::hexagon_V6_vgathermhw_128B:
222406f32e7eSjoerg Opcode = Hexagon::V6_vgathermhw_pseudo;
222506f32e7eSjoerg break;
222606f32e7eSjoerg }
222706f32e7eSjoerg
222806f32e7eSjoerg SDVTList VTs = CurDAG->getVTList(MVT::Other);
222906f32e7eSjoerg SDValue Ops[] = { Address, Base, Modifier, Offset, Chain };
223006f32e7eSjoerg SDNode *Result = CurDAG->getMachineNode(Opcode, dl, VTs, Ops);
223106f32e7eSjoerg
223206f32e7eSjoerg MachineMemOperand *MemOp = cast<MemIntrinsicSDNode>(N)->getMemOperand();
223306f32e7eSjoerg CurDAG->setNodeMemRefs(cast<MachineSDNode>(Result), {MemOp});
223406f32e7eSjoerg
223506f32e7eSjoerg ReplaceNode(N, Result);
223606f32e7eSjoerg }
223706f32e7eSjoerg
SelectHVXDualOutput(SDNode * N)223806f32e7eSjoerg void HexagonDAGToDAGISel::SelectHVXDualOutput(SDNode *N) {
223906f32e7eSjoerg unsigned IID = cast<ConstantSDNode>(N->getOperand(0))->getZExtValue();
224006f32e7eSjoerg SDNode *Result;
224106f32e7eSjoerg switch (IID) {
224206f32e7eSjoerg case Intrinsic::hexagon_V6_vaddcarry: {
2243*da58b97aSjoerg std::array<SDValue, 3> Ops = {
2244*da58b97aSjoerg {N->getOperand(1), N->getOperand(2), N->getOperand(3)}};
2245*da58b97aSjoerg SDVTList VTs = CurDAG->getVTList(MVT::v16i32, MVT::v64i1);
224606f32e7eSjoerg Result = CurDAG->getMachineNode(Hexagon::V6_vaddcarry, SDLoc(N), VTs, Ops);
224706f32e7eSjoerg break;
224806f32e7eSjoerg }
224906f32e7eSjoerg case Intrinsic::hexagon_V6_vaddcarry_128B: {
2250*da58b97aSjoerg std::array<SDValue, 3> Ops = {
2251*da58b97aSjoerg {N->getOperand(1), N->getOperand(2), N->getOperand(3)}};
2252*da58b97aSjoerg SDVTList VTs = CurDAG->getVTList(MVT::v32i32, MVT::v128i1);
225306f32e7eSjoerg Result = CurDAG->getMachineNode(Hexagon::V6_vaddcarry, SDLoc(N), VTs, Ops);
225406f32e7eSjoerg break;
225506f32e7eSjoerg }
225606f32e7eSjoerg case Intrinsic::hexagon_V6_vsubcarry: {
2257*da58b97aSjoerg std::array<SDValue, 3> Ops = {
2258*da58b97aSjoerg {N->getOperand(1), N->getOperand(2), N->getOperand(3)}};
2259*da58b97aSjoerg SDVTList VTs = CurDAG->getVTList(MVT::v16i32, MVT::v64i1);
226006f32e7eSjoerg Result = CurDAG->getMachineNode(Hexagon::V6_vsubcarry, SDLoc(N), VTs, Ops);
226106f32e7eSjoerg break;
226206f32e7eSjoerg }
226306f32e7eSjoerg case Intrinsic::hexagon_V6_vsubcarry_128B: {
2264*da58b97aSjoerg std::array<SDValue, 3> Ops = {
2265*da58b97aSjoerg {N->getOperand(1), N->getOperand(2), N->getOperand(3)}};
2266*da58b97aSjoerg SDVTList VTs = CurDAG->getVTList(MVT::v32i32, MVT::v128i1);
226706f32e7eSjoerg Result = CurDAG->getMachineNode(Hexagon::V6_vsubcarry, SDLoc(N), VTs, Ops);
226806f32e7eSjoerg break;
226906f32e7eSjoerg }
227006f32e7eSjoerg default:
227106f32e7eSjoerg llvm_unreachable("Unexpected HVX dual output intrinsic.");
227206f32e7eSjoerg }
227306f32e7eSjoerg ReplaceUses(N, Result);
227406f32e7eSjoerg ReplaceUses(SDValue(N, 0), SDValue(Result, 0));
227506f32e7eSjoerg ReplaceUses(SDValue(N, 1), SDValue(Result, 1));
227606f32e7eSjoerg CurDAG->RemoveDeadNode(N);
227706f32e7eSjoerg }
2278