| //===-- HexagonISelDAGToDAGHVX.cpp ----------------------------------------===// |
| // |
| // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| // See https://llvm.org/LICENSE.txt for license information. |
| // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| // |
| //===----------------------------------------------------------------------===// |
| |
| #include "Hexagon.h" |
| #include "HexagonISelDAGToDAG.h" |
| #include "HexagonISelLowering.h" |
| #include "HexagonTargetMachine.h" |
| #include "llvm/ADT/SetVector.h" |
| #include "llvm/CodeGen/MachineInstrBuilder.h" |
| #include "llvm/CodeGen/SelectionDAGISel.h" |
| #include "llvm/IR/Intrinsics.h" |
| #include "llvm/Support/CommandLine.h" |
| #include "llvm/Support/Debug.h" |
| |
| #include <deque> |
| #include <map> |
| #include <set> |
| #include <utility> |
| #include <vector> |
| |
| #define DEBUG_TYPE "hexagon-isel" |
| |
| using namespace llvm; |
| |
| namespace { |
| |
| // -------------------------------------------------------------------- |
| // Implementation of permutation networks. |
| |
| // Implementation of the node routing through butterfly networks: |
| // - Forward delta. |
| // - Reverse delta. |
| // - Benes. |
| // |
| // |
| // Forward delta network consists of log(N) steps, where N is the number |
| // of inputs. In each step, an input can stay in place, or it can get |
| // routed to another position[1]. The step after that consists of two |
| // networks, each half in size in terms of the number of nodes. In those |
| // terms, in the given step, an input can go to either the upper or the |
| // lower network in the next step. |
| // |
| // [1] Hexagon's vdelta/vrdelta allow an element to be routed to both |
| // positions as long as there is no conflict. |
| |
| // Here's a delta network for 8 inputs, only the switching routes are |
| // shown: |
| // |
| // Steps: |
| // |- 1 ---------------|- 2 -----|- 3 -| |
| // |
| // Inp[0] *** *** *** *** Out[0] |
| // \ / \ / \ / |
| // \ / \ / X |
| // \ / \ / / \ |
| // Inp[1] *** \ / *** X *** *** Out[1] |
| // \ \ / / \ / \ / |
| // \ \ / / X X |
| // \ \ / / / \ / \ |
| // Inp[2] *** \ \ / / *** X *** *** Out[2] |
| // \ \ X / / / \ \ / |
| // \ \ / \ / / / \ X |
| // \ X X / / \ / \ |
| // Inp[3] *** \ / \ / \ / *** *** *** Out[3] |
| // \ X X X / |
| // \ / \ / \ / \ / |
| // X X X X |
| // / \ / \ / \ / \ |
| // / X X X \ |
| // Inp[4] *** / \ / \ / \ *** *** *** Out[4] |
| // / X X \ \ / \ / |
| // / / \ / \ \ \ / X |
| // / / X \ \ \ / / \ |
| // Inp[5] *** / / \ \ *** X *** *** Out[5] |
| // / / \ \ \ / \ / |
| // / / \ \ X X |
| // / / \ \ / \ / \ |
| // Inp[6] *** / \ *** X *** *** Out[6] |
| // / \ / \ \ / |
| // / \ / \ X |
| // / \ / \ / \ |
| // Inp[7] *** *** *** *** Out[7] |
| // |
| // |
| // Reverse delta network is same as delta network, with the steps in |
| // the opposite order. |
| // |
| // |
| // Benes network is a forward delta network immediately followed by |
| // a reverse delta network. |
| |
| enum class ColorKind { None, Red, Black }; |
| |
| // Graph coloring utility used to partition nodes into two groups: |
| // they will correspond to nodes routed to the upper and lower networks. |
| struct Coloring { |
| using Node = int; |
| using MapType = std::map<Node, ColorKind>; |
| static constexpr Node Ignore = Node(-1); |
| |
| Coloring(ArrayRef<Node> Ord) : Order(Ord) { |
| build(); |
| if (!color()) |
| Colors.clear(); |
| } |
| |
| const MapType &colors() const { |
| return Colors; |
| } |
| |
| ColorKind other(ColorKind Color) { |
| if (Color == ColorKind::None) |
| return ColorKind::Red; |
| return Color == ColorKind::Red ? ColorKind::Black : ColorKind::Red; |
| } |
| |
| LLVM_DUMP_METHOD void dump() const; |
| |
| private: |
| ArrayRef<Node> Order; |
| MapType Colors; |
| std::set<Node> Needed; |
| |
| using NodeSet = std::set<Node>; |
| std::map<Node,NodeSet> Edges; |
| |
| Node conj(Node Pos) { |
| Node Num = Order.size(); |
| return (Pos < Num/2) ? Pos + Num/2 : Pos - Num/2; |
| } |
| |
| ColorKind getColor(Node N) { |
| auto F = Colors.find(N); |
| return F != Colors.end() ? F->second : ColorKind::None; |
| } |
| |
| std::pair<bool, ColorKind> getUniqueColor(const NodeSet &Nodes); |
| |
| void build(); |
| bool color(); |
| }; |
| } // namespace |
| |
| std::pair<bool, ColorKind> Coloring::getUniqueColor(const NodeSet &Nodes) { |
| auto Color = ColorKind::None; |
| for (Node N : Nodes) { |
| ColorKind ColorN = getColor(N); |
| if (ColorN == ColorKind::None) |
| continue; |
| if (Color == ColorKind::None) |
| Color = ColorN; |
| else if (Color != ColorKind::None && Color != ColorN) |
| return { false, ColorKind::None }; |
| } |
| return { true, Color }; |
| } |
| |
| void Coloring::build() { |
| // Add Order[P] and Order[conj(P)] to Edges. |
| for (unsigned P = 0; P != Order.size(); ++P) { |
| Node I = Order[P]; |
| if (I != Ignore) { |
| Needed.insert(I); |
| Node PC = Order[conj(P)]; |
| if (PC != Ignore && PC != I) |
| Edges[I].insert(PC); |
| } |
| } |
| // Add I and conj(I) to Edges. |
| for (unsigned I = 0; I != Order.size(); ++I) { |
| if (!Needed.count(I)) |
| continue; |
| Node C = conj(I); |
| // This will create an entry in the edge table, even if I is not |
| // connected to any other node. This is necessary, because it still |
| // needs to be colored. |
| NodeSet &Is = Edges[I]; |
| if (Needed.count(C)) |
| Is.insert(C); |
| } |
| } |
| |
| bool Coloring::color() { |
| SetVector<Node> FirstQ; |
| auto Enqueue = [this,&FirstQ] (Node N) { |
| SetVector<Node> Q; |
| Q.insert(N); |
| for (unsigned I = 0; I != Q.size(); ++I) { |
| NodeSet &Ns = Edges[Q[I]]; |
| Q.insert(Ns.begin(), Ns.end()); |
| } |
| FirstQ.insert(Q.begin(), Q.end()); |
| }; |
| for (Node N : Needed) |
| Enqueue(N); |
| |
| for (Node N : FirstQ) { |
| if (Colors.count(N)) |
| continue; |
| NodeSet &Ns = Edges[N]; |
| auto P = getUniqueColor(Ns); |
| if (!P.first) |
| return false; |
| Colors[N] = other(P.second); |
| } |
| |
| // First, color nodes that don't have any dups. |
| for (auto E : Edges) { |
| Node N = E.first; |
| if (!Needed.count(conj(N)) || Colors.count(N)) |
| continue; |
| auto P = getUniqueColor(E.second); |
| if (!P.first) |
| return false; |
| Colors[N] = other(P.second); |
| } |
| |
| // Now, nodes that are still uncolored. Since the graph can be modified |
| // in this step, create a work queue. |
| std::vector<Node> WorkQ; |
| for (auto E : Edges) { |
| Node N = E.first; |
| if (!Colors.count(N)) |
| WorkQ.push_back(N); |
| } |
| |
| for (unsigned I = 0; I < WorkQ.size(); ++I) { |
| Node N = WorkQ[I]; |
| NodeSet &Ns = Edges[N]; |
| auto P = getUniqueColor(Ns); |
| if (P.first) { |
| Colors[N] = other(P.second); |
| continue; |
| } |
| |
| // Coloring failed. Split this node. |
| Node C = conj(N); |
| ColorKind ColorN = other(ColorKind::None); |
| ColorKind ColorC = other(ColorN); |
| NodeSet &Cs = Edges[C]; |
| NodeSet CopyNs = Ns; |
| for (Node M : CopyNs) { |
| ColorKind ColorM = getColor(M); |
| if (ColorM == ColorC) { |
| // Connect M with C, disconnect M from N. |
| Cs.insert(M); |
| Edges[M].insert(C); |
| Ns.erase(M); |
| Edges[M].erase(N); |
| } |
| } |
| Colors[N] = ColorN; |
| Colors[C] = ColorC; |
| } |
| |
| // Explicitly assign "None" to all uncolored nodes. |
| for (unsigned I = 0; I != Order.size(); ++I) |
| if (Colors.count(I) == 0) |
| Colors[I] = ColorKind::None; |
| |
| return true; |
| } |
| |
| #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) |
| void Coloring::dump() const { |
| dbgs() << "{ Order: {"; |
| for (unsigned I = 0; I != Order.size(); ++I) { |
| Node P = Order[I]; |
| if (P != Ignore) |
| dbgs() << ' ' << P; |
| else |
| dbgs() << " -"; |
| } |
| dbgs() << " }\n"; |
| dbgs() << " Needed: {"; |
| for (Node N : Needed) |
| dbgs() << ' ' << N; |
| dbgs() << " }\n"; |
| |
| dbgs() << " Edges: {\n"; |
| for (auto E : Edges) { |
| dbgs() << " " << E.first << " -> {"; |
| for (auto N : E.second) |
| dbgs() << ' ' << N; |
| dbgs() << " }\n"; |
| } |
| dbgs() << " }\n"; |
| |
| auto ColorKindToName = [](ColorKind C) { |
| switch (C) { |
| case ColorKind::None: |
| return "None"; |
| case ColorKind::Red: |
| return "Red"; |
| case ColorKind::Black: |
| return "Black"; |
| } |
| llvm_unreachable("all ColorKinds should be handled by the switch above"); |
| }; |
| |
| dbgs() << " Colors: {\n"; |
| for (auto C : Colors) |
| dbgs() << " " << C.first << " -> " << ColorKindToName(C.second) << "\n"; |
| dbgs() << " }\n}\n"; |
| } |
| #endif |
| |
| namespace { |
| // Base class of for reordering networks. They don't strictly need to be |
| // permutations, as outputs with repeated occurrences of an input element |
| // are allowed. |
| struct PermNetwork { |
| using Controls = std::vector<uint8_t>; |
| using ElemType = int; |
| static constexpr ElemType Ignore = ElemType(-1); |
| |
| enum : uint8_t { |
| None, |
| Pass, |
| Switch |
| }; |
| enum : uint8_t { |
| Forward, |
| Reverse |
| }; |
| |
| PermNetwork(ArrayRef<ElemType> Ord, unsigned Mult = 1) { |
| Order.assign(Ord.data(), Ord.data()+Ord.size()); |
| Log = 0; |
| |
| unsigned S = Order.size(); |
| while (S >>= 1) |
| ++Log; |
| |
| Table.resize(Order.size()); |
| for (RowType &Row : Table) |
| Row.resize(Mult*Log, None); |
| } |
| |
| void getControls(Controls &V, unsigned StartAt, uint8_t Dir) const { |
| unsigned Size = Order.size(); |
| V.resize(Size); |
| for (unsigned I = 0; I != Size; ++I) { |
| unsigned W = 0; |
| for (unsigned L = 0; L != Log; ++L) { |
| unsigned C = ctl(I, StartAt+L) == Switch; |
| if (Dir == Forward) |
| W |= C << (Log-1-L); |
| else |
| W |= C << L; |
| } |
| assert(isUInt<8>(W)); |
| V[I] = uint8_t(W); |
| } |
| } |
| |
| uint8_t ctl(ElemType Pos, unsigned Step) const { |
| return Table[Pos][Step]; |
| } |
| unsigned size() const { |
| return Order.size(); |
| } |
| unsigned steps() const { |
| return Log; |
| } |
| |
| protected: |
| unsigned Log; |
| std::vector<ElemType> Order; |
| using RowType = std::vector<uint8_t>; |
| std::vector<RowType> Table; |
| }; |
| |
| struct ForwardDeltaNetwork : public PermNetwork { |
| ForwardDeltaNetwork(ArrayRef<ElemType> Ord) : PermNetwork(Ord) {} |
| |
| bool run(Controls &V) { |
| if (!route(Order.data(), Table.data(), size(), 0)) |
| return false; |
| getControls(V, 0, Forward); |
| return true; |
| } |
| |
| private: |
| bool route(ElemType *P, RowType *T, unsigned Size, unsigned Step); |
| }; |
| |
| struct ReverseDeltaNetwork : public PermNetwork { |
| ReverseDeltaNetwork(ArrayRef<ElemType> Ord) : PermNetwork(Ord) {} |
| |
| bool run(Controls &V) { |
| if (!route(Order.data(), Table.data(), size(), 0)) |
| return false; |
| getControls(V, 0, Reverse); |
| return true; |
| } |
| |
| private: |
| bool route(ElemType *P, RowType *T, unsigned Size, unsigned Step); |
| }; |
| |
| struct BenesNetwork : public PermNetwork { |
| BenesNetwork(ArrayRef<ElemType> Ord) : PermNetwork(Ord, 2) {} |
| |
| bool run(Controls &F, Controls &R) { |
| if (!route(Order.data(), Table.data(), size(), 0)) |
| return false; |
| |
| getControls(F, 0, Forward); |
| getControls(R, Log, Reverse); |
| return true; |
| } |
| |
| private: |
| bool route(ElemType *P, RowType *T, unsigned Size, unsigned Step); |
| }; |
| } // namespace |
| |
| bool ForwardDeltaNetwork::route(ElemType *P, RowType *T, unsigned Size, |
| unsigned Step) { |
| bool UseUp = false, UseDown = false; |
| ElemType Num = Size; |
| |
| // Cannot use coloring here, because coloring is used to determine |
| // the "big" switch, i.e. the one that changes halves, and in a forward |
| // network, a color can be simultaneously routed to both halves in the |
| // step we're working on. |
| for (ElemType J = 0; J != Num; ++J) { |
| ElemType I = P[J]; |
| // I is the position in the input, |
| // J is the position in the output. |
| if (I == Ignore) |
| continue; |
| uint8_t S; |
| if (I < Num/2) |
| S = (J < Num/2) ? Pass : Switch; |
| else |
| S = (J < Num/2) ? Switch : Pass; |
| |
| // U is the element in the table that needs to be updated. |
| ElemType U = (S == Pass) ? I : (I < Num/2 ? I+Num/2 : I-Num/2); |
| if (U < Num/2) |
| UseUp = true; |
| else |
| UseDown = true; |
| if (T[U][Step] != S && T[U][Step] != None) |
| return false; |
| T[U][Step] = S; |
| } |
| |
| for (ElemType J = 0; J != Num; ++J) |
| if (P[J] != Ignore && P[J] >= Num/2) |
| P[J] -= Num/2; |
| |
| if (Step+1 < Log) { |
| if (UseUp && !route(P, T, Size/2, Step+1)) |
| return false; |
| if (UseDown && !route(P+Size/2, T+Size/2, Size/2, Step+1)) |
| return false; |
| } |
| return true; |
| } |
| |
| bool ReverseDeltaNetwork::route(ElemType *P, RowType *T, unsigned Size, |
| unsigned Step) { |
| unsigned Pets = Log-1 - Step; |
| bool UseUp = false, UseDown = false; |
| ElemType Num = Size; |
| |
| // In this step half-switching occurs, so coloring can be used. |
| Coloring G({P,Size}); |
| const Coloring::MapType &M = G.colors(); |
| if (M.empty()) |
| return false; |
| |
| ColorKind ColorUp = ColorKind::None; |
| for (ElemType J = 0; J != Num; ++J) { |
| ElemType I = P[J]; |
| // I is the position in the input, |
| // J is the position in the output. |
| if (I == Ignore) |
| continue; |
| ColorKind C = M.at(I); |
| if (C == ColorKind::None) |
| continue; |
| // During "Step", inputs cannot switch halves, so if the "up" color |
| // is still unknown, make sure that it is selected in such a way that |
| // "I" will stay in the same half. |
| bool InpUp = I < Num/2; |
| if (ColorUp == ColorKind::None) |
| ColorUp = InpUp ? C : G.other(C); |
| if ((C == ColorUp) != InpUp) { |
| // If I should go to a different half than where is it now, give up. |
| return false; |
| } |
| |
| uint8_t S; |
| if (InpUp) { |
| S = (J < Num/2) ? Pass : Switch; |
| UseUp = true; |
| } else { |
| S = (J < Num/2) ? Switch : Pass; |
| UseDown = true; |
| } |
| T[J][Pets] = S; |
| } |
| |
| // Reorder the working permutation according to the computed switch table |
| // for the last step (i.e. Pets). |
| for (ElemType J = 0, E = Size / 2; J != E; ++J) { |
| ElemType PJ = P[J]; // Current values of P[J] |
| ElemType PC = P[J+Size/2]; // and P[conj(J)] |
| ElemType QJ = PJ; // New values of P[J] |
| ElemType QC = PC; // and P[conj(J)] |
| if (T[J][Pets] == Switch) |
| QC = PJ; |
| if (T[J+Size/2][Pets] == Switch) |
| QJ = PC; |
| P[J] = QJ; |
| P[J+Size/2] = QC; |
| } |
| |
| for (ElemType J = 0; J != Num; ++J) |
| if (P[J] != Ignore && P[J] >= Num/2) |
| P[J] -= Num/2; |
| |
| if (Step+1 < Log) { |
| if (UseUp && !route(P, T, Size/2, Step+1)) |
| return false; |
| if (UseDown && !route(P+Size/2, T+Size/2, Size/2, Step+1)) |
| return false; |
| } |
| return true; |
| } |
| |
| bool BenesNetwork::route(ElemType *P, RowType *T, unsigned Size, |
| unsigned Step) { |
| Coloring G({P,Size}); |
| const Coloring::MapType &M = G.colors(); |
| if (M.empty()) |
| return false; |
| ElemType Num = Size; |
| |
| unsigned Pets = 2*Log-1 - Step; |
| bool UseUp = false, UseDown = false; |
| |
| // Both assignments, i.e. Red->Up and Red->Down are valid, but they will |
| // result in different controls. Let's pick the one where the first |
| // control will be "Pass". |
| ColorKind ColorUp = ColorKind::None; |
| for (ElemType J = 0; J != Num; ++J) { |
| ElemType I = P[J]; |
| if (I == Ignore) |
| continue; |
| ColorKind C = M.at(I); |
| if (C == ColorKind::None) |
| continue; |
| if (ColorUp == ColorKind::None) { |
| ColorUp = (I < Num / 2) ? ColorKind::Red : ColorKind::Black; |
| } |
| unsigned CI = (I < Num/2) ? I+Num/2 : I-Num/2; |
| if (C == ColorUp) { |
| if (I < Num/2) |
| T[I][Step] = Pass; |
| else |
| T[CI][Step] = Switch; |
| T[J][Pets] = (J < Num/2) ? Pass : Switch; |
| UseUp = true; |
| } else { // Down |
| if (I < Num/2) |
| T[CI][Step] = Switch; |
| else |
| T[I][Step] = Pass; |
| T[J][Pets] = (J < Num/2) ? Switch : Pass; |
| UseDown = true; |
| } |
| } |
| |
| // Reorder the working permutation according to the computed switch table |
| // for the last step (i.e. Pets). |
| for (ElemType J = 0; J != Num/2; ++J) { |
| ElemType PJ = P[J]; // Current values of P[J] |
| ElemType PC = P[J+Num/2]; // and P[conj(J)] |
| ElemType QJ = PJ; // New values of P[J] |
| ElemType QC = PC; // and P[conj(J)] |
| if (T[J][Pets] == Switch) |
| QC = PJ; |
| if (T[J+Num/2][Pets] == Switch) |
| QJ = PC; |
| P[J] = QJ; |
| P[J+Num/2] = QC; |
| } |
| |
| for (ElemType J = 0; J != Num; ++J) |
| if (P[J] != Ignore && P[J] >= Num/2) |
| P[J] -= Num/2; |
| |
| if (Step+1 < Log) { |
| if (UseUp && !route(P, T, Size/2, Step+1)) |
| return false; |
| if (UseDown && !route(P+Size/2, T+Size/2, Size/2, Step+1)) |
| return false; |
| } |
| return true; |
| } |
| |
| // -------------------------------------------------------------------- |
| // Support for building selection results (output instructions that are |
| // parts of the final selection). |
| |
| namespace { |
| struct OpRef { |
| OpRef(SDValue V) : OpV(V) {} |
| bool isValue() const { return OpV.getNode() != nullptr; } |
| bool isValid() const { return isValue() || !(OpN & Invalid); } |
| static OpRef res(int N) { return OpRef(Whole | (N & Index)); } |
| static OpRef fail() { return OpRef(Invalid); } |
| |
| static OpRef lo(const OpRef &R) { |
| assert(!R.isValue()); |
| return OpRef(R.OpN & (Undef | Index | LoHalf)); |
| } |
| static OpRef hi(const OpRef &R) { |
| assert(!R.isValue()); |
| return OpRef(R.OpN & (Undef | Index | HiHalf)); |
| } |
| static OpRef undef(MVT Ty) { return OpRef(Undef | Ty.SimpleTy); } |
| |
| // Direct value. |
| SDValue OpV = SDValue(); |
| |
| // Reference to the operand of the input node: |
| // If the 31st bit is 1, it's undef, otherwise, bits 28..0 are the |
| // operand index: |
| // If bit 30 is set, it's the high half of the operand. |
| // If bit 29 is set, it's the low half of the operand. |
| unsigned OpN = 0; |
| |
| enum : unsigned { |
| Invalid = 0x10000000, |
| LoHalf = 0x20000000, |
| HiHalf = 0x40000000, |
| Whole = LoHalf | HiHalf, |
| Undef = 0x80000000, |
| Index = 0x0FFFFFFF, // Mask of the index value. |
| IndexBits = 28, |
| }; |
| |
| LLVM_DUMP_METHOD |
| void print(raw_ostream &OS, const SelectionDAG &G) const; |
| |
| private: |
| OpRef(unsigned N) : OpN(N) {} |
| }; |
| |
| struct NodeTemplate { |
| NodeTemplate() = default; |
| unsigned Opc = 0; |
| MVT Ty = MVT::Other; |
| std::vector<OpRef> Ops; |
| |
| LLVM_DUMP_METHOD void print(raw_ostream &OS, const SelectionDAG &G) const; |
| }; |
| |
| struct ResultStack { |
| ResultStack(SDNode *Inp) |
| : InpNode(Inp), InpTy(Inp->getValueType(0).getSimpleVT()) {} |
| SDNode *InpNode; |
| MVT InpTy; |
| unsigned push(const NodeTemplate &Res) { |
| List.push_back(Res); |
| return List.size()-1; |
| } |
| unsigned push(unsigned Opc, MVT Ty, std::vector<OpRef> &&Ops) { |
| NodeTemplate Res; |
| Res.Opc = Opc; |
| Res.Ty = Ty; |
| Res.Ops = Ops; |
| return push(Res); |
| } |
| bool empty() const { return List.empty(); } |
| unsigned size() const { return List.size(); } |
| unsigned top() const { return size()-1; } |
| const NodeTemplate &operator[](unsigned I) const { return List[I]; } |
| unsigned reset(unsigned NewTop) { |
| List.resize(NewTop+1); |
| return NewTop; |
| } |
| |
| using BaseType = std::vector<NodeTemplate>; |
| BaseType::iterator begin() { return List.begin(); } |
| BaseType::iterator end() { return List.end(); } |
| BaseType::const_iterator begin() const { return List.begin(); } |
| BaseType::const_iterator end() const { return List.end(); } |
| |
| BaseType List; |
| |
| LLVM_DUMP_METHOD |
| void print(raw_ostream &OS, const SelectionDAG &G) const; |
| }; |
| } // namespace |
| |
| #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) |
| void OpRef::print(raw_ostream &OS, const SelectionDAG &G) const { |
| if (isValue()) { |
| OpV.getNode()->print(OS, &G); |
| return; |
| } |
| if (OpN & Invalid) { |
| OS << "invalid"; |
| return; |
| } |
| if (OpN & Undef) { |
| OS << "undef"; |
| return; |
| } |
| if ((OpN & Whole) != Whole) { |
| assert((OpN & Whole) == LoHalf || (OpN & Whole) == HiHalf); |
| if (OpN & LoHalf) |
| OS << "lo "; |
| else |
| OS << "hi "; |
| } |
| OS << '#' << SignExtend32(OpN & Index, IndexBits); |
| } |
| |
| void NodeTemplate::print(raw_ostream &OS, const SelectionDAG &G) const { |
| const TargetInstrInfo &TII = *G.getSubtarget().getInstrInfo(); |
| OS << format("%8s", EVT(Ty).getEVTString().c_str()) << " " |
| << TII.getName(Opc); |
| bool Comma = false; |
| for (const auto &R : Ops) { |
| if (Comma) |
| OS << ','; |
| Comma = true; |
| OS << ' '; |
| R.print(OS, G); |
| } |
| } |
| |
| void ResultStack::print(raw_ostream &OS, const SelectionDAG &G) const { |
| OS << "Input node:\n"; |
| #ifndef NDEBUG |
| InpNode->dumpr(&G); |
| #endif |
| OS << "Result templates:\n"; |
| for (unsigned I = 0, E = List.size(); I != E; ++I) { |
| OS << '[' << I << "] "; |
| List[I].print(OS, G); |
| OS << '\n'; |
| } |
| } |
| #endif |
| |
| namespace { |
| struct ShuffleMask { |
| ShuffleMask(ArrayRef<int> M) : Mask(M) { |
| for (unsigned I = 0, E = Mask.size(); I != E; ++I) { |
| int M = Mask[I]; |
| if (M == -1) |
| continue; |
| MinSrc = (MinSrc == -1) ? M : std::min(MinSrc, M); |
| MaxSrc = (MaxSrc == -1) ? M : std::max(MaxSrc, M); |
| } |
| } |
| |
| ArrayRef<int> Mask; |
| int MinSrc = -1, MaxSrc = -1; |
| |
| ShuffleMask lo() const { |
| size_t H = Mask.size()/2; |
| return ShuffleMask(Mask.take_front(H)); |
| } |
| ShuffleMask hi() const { |
| size_t H = Mask.size()/2; |
| return ShuffleMask(Mask.take_back(H)); |
| } |
| |
| void print(raw_ostream &OS) const { |
| OS << "MinSrc:" << MinSrc << ", MaxSrc:" << MaxSrc << " {"; |
| for (int M : Mask) |
| OS << ' ' << M; |
| OS << " }"; |
| } |
| }; |
| } // namespace |
| |
| // -------------------------------------------------------------------- |
| // The HvxSelector class. |
| |
| static const HexagonTargetLowering &getHexagonLowering(SelectionDAG &G) { |
| return static_cast<const HexagonTargetLowering&>(G.getTargetLoweringInfo()); |
| } |
| static const HexagonSubtarget &getHexagonSubtarget(SelectionDAG &G) { |
| return static_cast<const HexagonSubtarget&>(G.getSubtarget()); |
| } |
| |
| namespace llvm { |
| struct HvxSelector { |
| const HexagonTargetLowering &Lower; |
| HexagonDAGToDAGISel &ISel; |
| SelectionDAG &DAG; |
| const HexagonSubtarget &HST; |
| const unsigned HwLen; |
| |
| HvxSelector(HexagonDAGToDAGISel &HS, SelectionDAG &G) |
| : Lower(getHexagonLowering(G)), ISel(HS), DAG(G), |
| HST(getHexagonSubtarget(G)), HwLen(HST.getVectorLength()) {} |
| |
| MVT getSingleVT(MVT ElemTy) const { |
| unsigned NumElems = HwLen / (ElemTy.getSizeInBits()/8); |
| return MVT::getVectorVT(ElemTy, NumElems); |
| } |
| |
| MVT getPairVT(MVT ElemTy) const { |
| unsigned NumElems = (2*HwLen) / (ElemTy.getSizeInBits()/8); |
| return MVT::getVectorVT(ElemTy, NumElems); |
| } |
| |
| void selectShuffle(SDNode *N); |
| void selectRor(SDNode *N); |
| void selectVAlign(SDNode *N); |
| |
| private: |
| void materialize(const ResultStack &Results); |
| |
| SDValue getVectorConstant(ArrayRef<uint8_t> Data, const SDLoc &dl); |
| |
| enum : unsigned { |
| None, |
| PackMux, |
| }; |
| OpRef concat(OpRef Va, OpRef Vb, ResultStack &Results); |
| OpRef packs(ShuffleMask SM, OpRef Va, OpRef Vb, ResultStack &Results, |
| MutableArrayRef<int> NewMask, unsigned Options = None); |
| OpRef packp(ShuffleMask SM, OpRef Va, OpRef Vb, ResultStack &Results, |
| MutableArrayRef<int> NewMask); |
| OpRef vmuxs(ArrayRef<uint8_t> Bytes, OpRef Va, OpRef Vb, |
| ResultStack &Results); |
| OpRef vmuxp(ArrayRef<uint8_t> Bytes, OpRef Va, OpRef Vb, |
| ResultStack &Results); |
| |
| OpRef shuffs1(ShuffleMask SM, OpRef Va, ResultStack &Results); |
| OpRef shuffs2(ShuffleMask SM, OpRef Va, OpRef Vb, ResultStack &Results); |
| OpRef shuffp1(ShuffleMask SM, OpRef Va, ResultStack &Results); |
| OpRef shuffp2(ShuffleMask SM, OpRef Va, OpRef Vb, ResultStack &Results); |
| |
| OpRef butterfly(ShuffleMask SM, OpRef Va, ResultStack &Results); |
| OpRef contracting(ShuffleMask SM, OpRef Va, OpRef Vb, ResultStack &Results); |
| OpRef expanding(ShuffleMask SM, OpRef Va, ResultStack &Results); |
| OpRef perfect(ShuffleMask SM, OpRef Va, ResultStack &Results); |
| |
| bool selectVectorConstants(SDNode *N); |
| bool scalarizeShuffle(ArrayRef<int> Mask, const SDLoc &dl, MVT ResTy, |
| SDValue Va, SDValue Vb, SDNode *N); |
| |
| }; |
| } |
| |
| static void splitMask(ArrayRef<int> Mask, MutableArrayRef<int> MaskL, |
| MutableArrayRef<int> MaskR) { |
| unsigned VecLen = Mask.size(); |
| assert(MaskL.size() == VecLen && MaskR.size() == VecLen); |
| for (unsigned I = 0; I != VecLen; ++I) { |
| int M = Mask[I]; |
| if (M < 0) { |
| MaskL[I] = MaskR[I] = -1; |
| } else if (unsigned(M) < VecLen) { |
| MaskL[I] = M; |
| MaskR[I] = -1; |
| } else { |
| MaskL[I] = -1; |
| MaskR[I] = M-VecLen; |
| } |
| } |
| } |
| |
| static std::pair<int,unsigned> findStrip(ArrayRef<int> A, int Inc, |
| unsigned MaxLen) { |
| assert(A.size() > 0 && A.size() >= MaxLen); |
| int F = A[0]; |
| int E = F; |
| for (unsigned I = 1; I != MaxLen; ++I) { |
| if (A[I] - E != Inc) |
| return { F, I }; |
| E = A[I]; |
| } |
| return { F, MaxLen }; |
| } |
| |
| static bool isUndef(ArrayRef<int> Mask) { |
| for (int Idx : Mask) |
| if (Idx != -1) |
| return false; |
| return true; |
| } |
| |
| static bool isIdentity(ArrayRef<int> Mask) { |
| for (int I = 0, E = Mask.size(); I != E; ++I) { |
| int M = Mask[I]; |
| if (M >= 0 && M != I) |
| return false; |
| } |
| return true; |
| } |
| |
| static bool isPermutation(ArrayRef<int> Mask) { |
| // Check by adding all numbers only works if there is no overflow. |
| assert(Mask.size() < 0x00007FFF && "Sanity failure"); |
| int Sum = 0; |
| for (int Idx : Mask) { |
| if (Idx == -1) |
| return false; |
| Sum += Idx; |
| } |
| int N = Mask.size(); |
| return 2*Sum == N*(N-1); |
| } |
| |
| bool HvxSelector::selectVectorConstants(SDNode *N) { |
| // Constant vectors are generated as loads from constant pools or as |
| // splats of a constant value. Since they are generated during the |
| // selection process, the main selection algorithm is not aware of them. |
| // Select them directly here. |
| SmallVector<SDNode*,4> Nodes; |
| SetVector<SDNode*> WorkQ; |
| |
| // The one-use test for VSPLATW's operand may fail due to dead nodes |
| // left over in the DAG. |
| DAG.RemoveDeadNodes(); |
| |
| // The DAG can change (due to CSE) during selection, so cache all the |
| // unselected nodes first to avoid traversing a mutating DAG. |
| |
| auto IsNodeToSelect = [] (SDNode *N) { |
| if (N->isMachineOpcode()) |
| return false; |
| switch (N->getOpcode()) { |
| case HexagonISD::VZERO: |
| case HexagonISD::VSPLATW: |
| return true; |
| case ISD::LOAD: { |
| SDValue Addr = cast<LoadSDNode>(N)->getBasePtr(); |
| unsigned AddrOpc = Addr.getOpcode(); |
| if (AddrOpc == HexagonISD::AT_PCREL || AddrOpc == HexagonISD::CP) |
| if (Addr.getOperand(0).getOpcode() == ISD::TargetConstantPool) |
| return true; |
| } |
| break; |
| } |
| // Make sure to select the operand of VSPLATW. |
| bool IsSplatOp = N->hasOneUse() && |
| N->use_begin()->getOpcode() == HexagonISD::VSPLATW; |
| return IsSplatOp; |
| }; |
| |
| WorkQ.insert(N); |
| for (unsigned i = 0; i != WorkQ.size(); ++i) { |
| SDNode *W = WorkQ[i]; |
| if (IsNodeToSelect(W)) |
| Nodes.push_back(W); |
| for (unsigned j = 0, f = W->getNumOperands(); j != f; ++j) |
| WorkQ.insert(W->getOperand(j).getNode()); |
| } |
| |
| for (SDNode *L : Nodes) |
| ISel.Select(L); |
| |
| return !Nodes.empty(); |
| } |
| |
| void HvxSelector::materialize(const ResultStack &Results) { |
| DEBUG_WITH_TYPE("isel", { |
| dbgs() << "Materializing\n"; |
| Results.print(dbgs(), DAG); |
| }); |
| if (Results.empty()) |
| return; |
| const SDLoc &dl(Results.InpNode); |
| std::vector<SDValue> Output; |
| |
| for (unsigned I = 0, E = Results.size(); I != E; ++I) { |
| const NodeTemplate &Node = Results[I]; |
| std::vector<SDValue> Ops; |
| for (const OpRef &R : Node.Ops) { |
| assert(R.isValid()); |
| if (R.isValue()) { |
| Ops.push_back(R.OpV); |
| continue; |
| } |
| if (R.OpN & OpRef::Undef) { |
| MVT::SimpleValueType SVT = MVT::SimpleValueType(R.OpN & OpRef::Index); |
| Ops.push_back(ISel.selectUndef(dl, MVT(SVT))); |
| continue; |
| } |
| // R is an index of a result. |
| unsigned Part = R.OpN & OpRef::Whole; |
| int Idx = SignExtend32(R.OpN & OpRef::Index, OpRef::IndexBits); |
| if (Idx < 0) |
| Idx += I; |
| assert(Idx >= 0 && unsigned(Idx) < Output.size()); |
| SDValue Op = Output[Idx]; |
| MVT OpTy = Op.getValueType().getSimpleVT(); |
| if (Part != OpRef::Whole) { |
| assert(Part == OpRef::LoHalf || Part == OpRef::HiHalf); |
| MVT HalfTy = MVT::getVectorVT(OpTy.getVectorElementType(), |
| OpTy.getVectorNumElements()/2); |
| unsigned Sub = (Part == OpRef::LoHalf) ? Hexagon::vsub_lo |
| : Hexagon::vsub_hi; |
| Op = DAG.getTargetExtractSubreg(Sub, dl, HalfTy, Op); |
| } |
| Ops.push_back(Op); |
| } // for (Node : Results) |
| |
| assert(Node.Ty != MVT::Other); |
| SDNode *ResN = (Node.Opc == TargetOpcode::COPY) |
| ? Ops.front().getNode() |
| : DAG.getMachineNode(Node.Opc, dl, Node.Ty, Ops); |
| Output.push_back(SDValue(ResN, 0)); |
| } |
| |
| SDNode *OutN = Output.back().getNode(); |
| SDNode *InpN = Results.InpNode; |
| DEBUG_WITH_TYPE("isel", { |
| dbgs() << "Generated node:\n"; |
| OutN->dumpr(&DAG); |
| }); |
| |
| ISel.ReplaceNode(InpN, OutN); |
| selectVectorConstants(OutN); |
| DAG.RemoveDeadNodes(); |
| } |
| |
| OpRef HvxSelector::concat(OpRef Lo, OpRef Hi, ResultStack &Results) { |
| DEBUG_WITH_TYPE("isel", {dbgs() << __func__ << '\n';}); |
| const SDLoc &dl(Results.InpNode); |
| Results.push(TargetOpcode::REG_SEQUENCE, getPairVT(MVT::i8), { |
| DAG.getTargetConstant(Hexagon::HvxWRRegClassID, dl, MVT::i32), |
| Lo, DAG.getTargetConstant(Hexagon::vsub_lo, dl, MVT::i32), |
| Hi, DAG.getTargetConstant(Hexagon::vsub_hi, dl, MVT::i32), |
| }); |
| return OpRef::res(Results.top()); |
| } |
| |
| // Va, Vb are single vectors, SM can be arbitrarily long. |
| OpRef HvxSelector::packs(ShuffleMask SM, OpRef Va, OpRef Vb, |
| ResultStack &Results, MutableArrayRef<int> NewMask, |
| unsigned Options) { |
| DEBUG_WITH_TYPE("isel", {dbgs() << __func__ << '\n';}); |
| if (!Va.isValid() || !Vb.isValid()) |
| return OpRef::fail(); |
| |
| int VecLen = SM.Mask.size(); |
| MVT Ty = getSingleVT(MVT::i8); |
| |
| auto IsExtSubvector = [] (ShuffleMask M) { |
| assert(M.MinSrc >= 0 && M.MaxSrc >= 0); |
| for (int I = 0, E = M.Mask.size(); I != E; ++I) { |
| if (M.Mask[I] >= 0 && M.Mask[I]-I != M.MinSrc) |
| return false; |
| } |
| return true; |
| }; |
| |
| if (SM.MaxSrc - SM.MinSrc < int(HwLen)) { |
| if (SM.MinSrc == 0 || SM.MinSrc == int(HwLen) || !IsExtSubvector(SM)) { |
| // If the mask picks elements from only one of the operands, return |
| // that operand, and update the mask to use index 0 to refer to the |
| // first element of that operand. |
| // If the mask extracts a subvector, it will be handled below, so |
| // skip it here. |
| if (SM.MaxSrc < int(HwLen)) { |
| memcpy(NewMask.data(), SM.Mask.data(), sizeof(int)*VecLen); |
| return Va; |
| } |
| if (SM.MinSrc >= int(HwLen)) { |
| for (int I = 0; I != VecLen; ++I) { |
| int M = SM.Mask[I]; |
| if (M != -1) |
| M -= HwLen; |
| NewMask[I] = M; |
| } |
| return Vb; |
| } |
| } |
| int MinSrc = SM.MinSrc; |
| if (SM.MaxSrc < int(HwLen)) { |
| Vb = Va; |
| } else if (SM.MinSrc > int(HwLen)) { |
| Va = Vb; |
| MinSrc = SM.MinSrc - HwLen; |
| } |
| const SDLoc &dl(Results.InpNode); |
| if (isUInt<3>(MinSrc) || isUInt<3>(HwLen-MinSrc)) { |
| bool IsRight = isUInt<3>(MinSrc); // Right align. |
| SDValue S = DAG.getTargetConstant(IsRight ? MinSrc : HwLen-MinSrc, |
| dl, MVT::i32); |
| unsigned Opc = IsRight ? Hexagon::V6_valignbi |
| : Hexagon::V6_vlalignbi; |
| Results.push(Opc, Ty, {Vb, Va, S}); |
| } else { |
| SDValue S = DAG.getTargetConstant(MinSrc, dl, MVT::i32); |
| Results.push(Hexagon::A2_tfrsi, MVT::i32, {S}); |
| unsigned Top = Results.top(); |
| Results.push(Hexagon::V6_valignb, Ty, {Vb, Va, OpRef::res(Top)}); |
| } |
| for (int I = 0; I != VecLen; ++I) { |
| int M = SM.Mask[I]; |
| if (M != -1) |
| M -= SM.MinSrc; |
| NewMask[I] = M; |
| } |
| return OpRef::res(Results.top()); |
| } |
| |
| if (Options & PackMux) { |
| // If elements picked from Va and Vb have all different (source) indexes |
| // (relative to the start of the argument), do a mux, and update the mask. |
| BitVector Picked(HwLen); |
| SmallVector<uint8_t,128> MuxBytes(HwLen); |
| bool CanMux = true; |
| for (int I = 0; I != VecLen; ++I) { |
| int M = SM.Mask[I]; |
| if (M == -1) |
| continue; |
| if (M >= int(HwLen)) |
| M -= HwLen; |
| else |
| MuxBytes[M] = 0xFF; |
| if (Picked[M]) { |
| CanMux = false; |
| break; |
| } |
| NewMask[I] = M; |
| } |
| if (CanMux) |
| return vmuxs(MuxBytes, Va, Vb, Results); |
| } |
| |
| return OpRef::fail(); |
| } |
| |
| OpRef HvxSelector::packp(ShuffleMask SM, OpRef Va, OpRef Vb, |
| ResultStack &Results, MutableArrayRef<int> NewMask) { |
| DEBUG_WITH_TYPE("isel", {dbgs() << __func__ << '\n';}); |
| unsigned HalfMask = 0; |
| unsigned LogHw = Log2_32(HwLen); |
| for (int M : SM.Mask) { |
| if (M == -1) |
| continue; |
| HalfMask |= (1u << (M >> LogHw)); |
| } |
| |
| if (HalfMask == 0) |
| return OpRef::undef(getPairVT(MVT::i8)); |
| |
| // If more than two halves are used, bail. |
| // TODO: be more aggressive here? |
| if (countPopulation(HalfMask) > 2) |
| return OpRef::fail(); |
| |
| MVT HalfTy = getSingleVT(MVT::i8); |
| |
| OpRef Inp[2] = { Va, Vb }; |
| OpRef Out[2] = { OpRef::undef(HalfTy), OpRef::undef(HalfTy) }; |
| |
| uint8_t HalfIdx[4] = { 0xFF, 0xFF, 0xFF, 0xFF }; |
| unsigned Idx = 0; |
| for (unsigned I = 0; I != 4; ++I) { |
| if ((HalfMask & (1u << I)) == 0) |
| continue; |
| assert(Idx < 2); |
| OpRef Op = Inp[I/2]; |
| Out[Idx] = (I & 1) ? OpRef::hi(Op) : OpRef::lo(Op); |
| HalfIdx[I] = Idx++; |
| } |
| |
| int VecLen = SM.Mask.size(); |
| for (int I = 0; I != VecLen; ++I) { |
| int M = SM.Mask[I]; |
| if (M >= 0) { |
| uint8_t Idx = HalfIdx[M >> LogHw]; |
| assert(Idx == 0 || Idx == 1); |
| M = (M & (HwLen-1)) + HwLen*Idx; |
| } |
| NewMask[I] = M; |
| } |
| |
| return concat(Out[0], Out[1], Results); |
| } |
| |
| OpRef HvxSelector::vmuxs(ArrayRef<uint8_t> Bytes, OpRef Va, OpRef Vb, |
| ResultStack &Results) { |
| DEBUG_WITH_TYPE("isel", {dbgs() << __func__ << '\n';}); |
| MVT ByteTy = getSingleVT(MVT::i8); |
| MVT BoolTy = MVT::getVectorVT(MVT::i1, 8*HwLen); // XXX |
| const SDLoc &dl(Results.InpNode); |
| SDValue B = getVectorConstant(Bytes, dl); |
| Results.push(Hexagon::V6_vd0, ByteTy, {}); |
| Results.push(Hexagon::V6_veqb, BoolTy, {OpRef(B), OpRef::res(-1)}); |
| Results.push(Hexagon::V6_vmux, ByteTy, {OpRef::res(-1), Vb, Va}); |
| return OpRef::res(Results.top()); |
| } |
| |
| OpRef HvxSelector::vmuxp(ArrayRef<uint8_t> Bytes, OpRef Va, OpRef Vb, |
| ResultStack &Results) { |
| DEBUG_WITH_TYPE("isel", {dbgs() << __func__ << '\n';}); |
| size_t S = Bytes.size() / 2; |
| OpRef L = vmuxs(Bytes.take_front(S), OpRef::lo(Va), OpRef::lo(Vb), Results); |
| OpRef H = vmuxs(Bytes.drop_front(S), OpRef::hi(Va), OpRef::hi(Vb), Results); |
| return concat(L, H, Results); |
| } |
| |
| OpRef HvxSelector::shuffs1(ShuffleMask SM, OpRef Va, ResultStack &Results) { |
| DEBUG_WITH_TYPE("isel", {dbgs() << __func__ << '\n';}); |
| unsigned VecLen = SM.Mask.size(); |
| assert(HwLen == VecLen); |
| (void)VecLen; |
| assert(all_of(SM.Mask, [this](int M) { return M == -1 || M < int(HwLen); })); |
| |
| if (isIdentity(SM.Mask)) |
| return Va; |
| if (isUndef(SM.Mask)) |
| return OpRef::undef(getSingleVT(MVT::i8)); |
| |
| OpRef P = perfect(SM, Va, Results); |
| if (P.isValid()) |
| return P; |
| return butterfly(SM, Va, Results); |
| } |
| |
| OpRef HvxSelector::shuffs2(ShuffleMask SM, OpRef Va, OpRef Vb, |
| ResultStack &Results) { |
| DEBUG_WITH_TYPE("isel", {dbgs() << __func__ << '\n';}); |
| if (isUndef(SM.Mask)) |
| return OpRef::undef(getSingleVT(MVT::i8)); |
| |
| OpRef C = contracting(SM, Va, Vb, Results); |
| if (C.isValid()) |
| return C; |
| |
| int VecLen = SM.Mask.size(); |
| SmallVector<int,128> NewMask(VecLen); |
| OpRef P = packs(SM, Va, Vb, Results, NewMask); |
| if (P.isValid()) |
| return shuffs1(ShuffleMask(NewMask), P, Results); |
| |
| SmallVector<int,128> MaskL(VecLen), MaskR(VecLen); |
| splitMask(SM.Mask, MaskL, MaskR); |
| |
| OpRef L = shuffs1(ShuffleMask(MaskL), Va, Results); |
| OpRef R = shuffs1(ShuffleMask(MaskR), Vb, Results); |
| if (!L.isValid() || !R.isValid()) |
| return OpRef::fail(); |
| |
| SmallVector<uint8_t,128> Bytes(VecLen); |
| for (int I = 0; I != VecLen; ++I) { |
| if (MaskL[I] != -1) |
| Bytes[I] = 0xFF; |
| } |
| return vmuxs(Bytes, L, R, Results); |
| } |
| |
| OpRef HvxSelector::shuffp1(ShuffleMask SM, OpRef Va, ResultStack &Results) { |
| DEBUG_WITH_TYPE("isel", {dbgs() << __func__ << '\n';}); |
| int VecLen = SM.Mask.size(); |
| |
| if (isIdentity(SM.Mask)) |
| return Va; |
| if (isUndef(SM.Mask)) |
| return OpRef::undef(getPairVT(MVT::i8)); |
| |
| SmallVector<int,128> PackedMask(VecLen); |
| OpRef P = packs(SM, OpRef::lo(Va), OpRef::hi(Va), Results, PackedMask); |
| if (P.isValid()) { |
| ShuffleMask PM(PackedMask); |
| OpRef E = expanding(PM, P, Results); |
| if (E.isValid()) |
| return E; |
| |
| OpRef L = shuffs1(PM.lo(), P, Results); |
| OpRef H = shuffs1(PM.hi(), P, Results); |
| if (L.isValid() && H.isValid()) |
| return concat(L, H, Results); |
| } |
| |
| OpRef R = perfect(SM, Va, Results); |
| if (R.isValid()) |
| return R; |
| // TODO commute the mask and try the opposite order of the halves. |
| |
| OpRef L = shuffs2(SM.lo(), OpRef::lo(Va), OpRef::hi(Va), Results); |
| OpRef H = shuffs2(SM.hi(), OpRef::lo(Va), OpRef::hi(Va), Results); |
| if (L.isValid() && H.isValid()) |
| return concat(L, H, Results); |
| |
| return OpRef::fail(); |
| } |
| |
| OpRef HvxSelector::shuffp2(ShuffleMask SM, OpRef Va, OpRef Vb, |
| ResultStack &Results) { |
| DEBUG_WITH_TYPE("isel", {dbgs() << __func__ << '\n';}); |
| if (isUndef(SM.Mask)) |
| return OpRef::undef(getPairVT(MVT::i8)); |
| |
| int VecLen = SM.Mask.size(); |
| SmallVector<int,256> PackedMask(VecLen); |
| OpRef P = packp(SM, Va, Vb, Results, PackedMask); |
| if (P.isValid()) |
| return shuffp1(ShuffleMask(PackedMask), P, Results); |
| |
| SmallVector<int,256> MaskL(VecLen), MaskR(VecLen); |
| splitMask(SM.Mask, MaskL, MaskR); |
| |
| OpRef L = shuffp1(ShuffleMask(MaskL), Va, Results); |
| OpRef R = shuffp1(ShuffleMask(MaskR), Vb, Results); |
| if (!L.isValid() || !R.isValid()) |
| return OpRef::fail(); |
| |
| // Mux the results. |
| SmallVector<uint8_t,256> Bytes(VecLen); |
| for (int I = 0; I != VecLen; ++I) { |
| if (MaskL[I] != -1) |
| Bytes[I] = 0xFF; |
| } |
| return vmuxp(Bytes, L, R, Results); |
| } |
| |
| namespace { |
| struct Deleter : public SelectionDAG::DAGNodeDeletedListener { |
| template <typename T> |
| Deleter(SelectionDAG &D, T &C) |
| : SelectionDAG::DAGNodeDeletedListener(D, [&C] (SDNode *N, SDNode *E) { |
| C.erase(N); |
| }) {} |
| }; |
| |
| template <typename T> |
| struct NullifyingVector : public T { |
| DenseMap<SDNode*, SDNode**> Refs; |
| NullifyingVector(T &&V) : T(V) { |
| for (unsigned i = 0, e = T::size(); i != e; ++i) { |
| SDNode *&N = T::operator[](i); |
| Refs[N] = &N; |
| } |
| } |
| void erase(SDNode *N) { |
| auto F = Refs.find(N); |
| if (F != Refs.end()) |
| *F->second = nullptr; |
| } |
| }; |
| } |
| |
| bool HvxSelector::scalarizeShuffle(ArrayRef<int> Mask, const SDLoc &dl, |
| MVT ResTy, SDValue Va, SDValue Vb, |
| SDNode *N) { |
| DEBUG_WITH_TYPE("isel", {dbgs() << __func__ << '\n';}); |
| MVT ElemTy = ResTy.getVectorElementType(); |
| assert(ElemTy == MVT::i8); |
| unsigned VecLen = Mask.size(); |
| bool HavePairs = (2*HwLen == VecLen); |
| MVT SingleTy = getSingleVT(MVT::i8); |
| |
| // The prior attempts to handle this shuffle may have left a bunch of |
| // dead nodes in the DAG (such as constants). These nodes will be added |
| // at the end of DAG's node list, which at that point had already been |
| // sorted topologically. In the main selection loop, the node list is |
| // traversed backwards from the root node, which means that any new |
| // nodes (from the end of the list) will not be visited. |
| // Scalarization will replace the shuffle node with the scalarized |
| // expression, and if that expression reused any if the leftoever (dead) |
| // nodes, these nodes would not be selected (since the "local" selection |
| // only visits nodes that are not in AllNodes). |
| // To avoid this issue, remove all dead nodes from the DAG now. |
| DAG.RemoveDeadNodes(); |
| DenseSet<SDNode*> AllNodes; |
| for (SDNode &S : DAG.allnodes()) |
| AllNodes.insert(&S); |
| |
| Deleter DUA(DAG, AllNodes); |
| |
| SmallVector<SDValue,128> Ops; |
| LLVMContext &Ctx = *DAG.getContext(); |
| MVT LegalTy = Lower.getTypeToTransformTo(Ctx, ElemTy).getSimpleVT(); |
| for (int I : Mask) { |
| if (I < 0) { |
| Ops.push_back(ISel.selectUndef(dl, LegalTy)); |
| continue; |
| } |
| SDValue Vec; |
| unsigned M = I; |
| if (M < VecLen) { |
| Vec = Va; |
| } else { |
| Vec = Vb; |
| M -= VecLen; |
| } |
| if (HavePairs) { |
| if (M < HwLen) { |
| Vec = DAG.getTargetExtractSubreg(Hexagon::vsub_lo, dl, SingleTy, Vec); |
| } else { |
| Vec = DAG.getTargetExtractSubreg(Hexagon::vsub_hi, dl, SingleTy, Vec); |
| M -= HwLen; |
| } |
| } |
| SDValue Idx = DAG.getConstant(M, dl, MVT::i32); |
| SDValue Ex = DAG.getNode(ISD::EXTRACT_VECTOR_ELT, dl, LegalTy, {Vec, Idx}); |
| SDValue L = Lower.LowerOperation(Ex, DAG); |
| assert(L.getNode()); |
| Ops.push_back(L); |
| } |
| |
| SDValue LV; |
| if (2*HwLen == VecLen) { |
| SDValue B0 = DAG.getBuildVector(SingleTy, dl, {Ops.data(), HwLen}); |
| SDValue L0 = Lower.LowerOperation(B0, DAG); |
| SDValue B1 = DAG.getBuildVector(SingleTy, dl, {Ops.data()+HwLen, HwLen}); |
| SDValue L1 = Lower.LowerOperation(B1, DAG); |
| // XXX CONCAT_VECTORS is legal for HVX vectors. Legalizing (lowering) |
| // functions may expect to be called only for illegal operations, so |
| // make sure that they are not called for legal ones. Develop a better |
| // mechanism for dealing with this. |
| LV = DAG.getNode(ISD::CONCAT_VECTORS, dl, ResTy, {L0, L1}); |
| } else { |
| SDValue BV = DAG.getBuildVector(ResTy, dl, Ops); |
| LV = Lower.LowerOperation(BV, DAG); |
| } |
| |
| assert(!N->use_empty()); |
| ISel.ReplaceNode(N, LV.getNode()); |
| |
| if (AllNodes.count(LV.getNode())) { |
| DAG.RemoveDeadNodes(); |
| return true; |
| } |
| |
| // The lowered build-vector node will now need to be selected. It needs |
| // to be done here because this node and its submodes are not included |
| // in the main selection loop. |
| // Implement essentially the same topological ordering algorithm as is |
| // used in SelectionDAGISel. |
| |
| SetVector<SDNode*> SubNodes, TmpQ; |
| std::map<SDNode*,unsigned> NumOps; |
| |
| SubNodes.insert(LV.getNode()); |
| for (unsigned I = 0; I != SubNodes.size(); ++I) { |
| unsigned OpN = 0; |
| SDNode *S = SubNodes[I]; |
| for (SDValue Op : S->ops()) { |
| if (AllNodes.count(Op.getNode())) |
| continue; |
| SubNodes.insert(Op.getNode()); |
| ++OpN; |
| } |
| NumOps.insert({S, OpN}); |
| if (OpN == 0) |
| TmpQ.insert(S); |
| } |
| |
| for (unsigned I = 0; I != TmpQ.size(); ++I) { |
| SDNode *S = TmpQ[I]; |
| for (SDNode *U : S->uses()) { |
| if (!SubNodes.count(U)) |
| continue; |
| auto F = NumOps.find(U); |
| assert(F != NumOps.end()); |
| assert(F->second > 0); |
| if (!--F->second) |
| TmpQ.insert(F->first); |
| } |
| } |
| assert(SubNodes.size() == TmpQ.size()); |
| NullifyingVector<decltype(TmpQ)::vector_type> Queue(TmpQ.takeVector()); |
| |
| Deleter DUQ(DAG, Queue); |
| for (SDNode *S : reverse(Queue)) |
| if (S != nullptr) |
| ISel.Select(S); |
| |
| DAG.RemoveDeadNodes(); |
| return true; |
| } |
| |
| OpRef HvxSelector::contracting(ShuffleMask SM, OpRef Va, OpRef Vb, |
| ResultStack &Results) { |
| DEBUG_WITH_TYPE("isel", {dbgs() << __func__ << '\n';}); |
| if (!Va.isValid() || !Vb.isValid()) |
| return OpRef::fail(); |
| |
| // Contracting shuffles, i.e. instructions that always discard some bytes |
| // from the operand vectors. |
| // |
| // V6_vshuff{e,o}b |
| // V6_vdealb4w |
| // V6_vpack{e,o}{b,h} |
| |
| int VecLen = SM.Mask.size(); |
| std::pair<int,unsigned> Strip = findStrip(SM.Mask, 1, VecLen); |
| MVT ResTy = getSingleVT(MVT::i8); |
| |
| // The following shuffles only work for bytes and halfwords. This requires |
| // the strip length to be 1 or 2. |
| if (Strip.second != 1 && Strip.second != 2) |
| return OpRef::fail(); |
| |
| // The patterns for the shuffles, in terms of the starting offsets of the |
| // consecutive strips (L = length of the strip, N = VecLen): |
| // |
| // vpacke: 0, 2L, 4L ... N+0, N+2L, N+4L ... L = 1 or 2 |
| // vpacko: L, 3L, 5L ... N+L, N+3L, N+5L ... L = 1 or 2 |
| // |
| // vshuffe: 0, N+0, 2L, N+2L, 4L ... L = 1 or 2 |
| // vshuffo: L, N+L, 3L, N+3L, 5L ... L = 1 or 2 |
| // |
| // vdealb4w: 0, 4, 8 ... 2, 6, 10 ... N+0, N+4, N+8 ... N+2, N+6, N+10 ... |
| |
| // The value of the element in the mask following the strip will decide |
| // what kind of a shuffle this can be. |
| int NextInMask = SM.Mask[Strip.second]; |
| |
| // Check if NextInMask could be 2L, 3L or 4, i.e. if it could be a mask |
| // for vpack or vdealb4w. VecLen > 4, so NextInMask for vdealb4w would |
| // satisfy this. |
| if (NextInMask < VecLen) { |
| // vpack{e,o} or vdealb4w |
| if (Strip.first == 0 && Strip.second == 1 && NextInMask == 4) { |
| int N = VecLen; |
| // Check if this is vdealb4w (L=1). |
| for (int I = 0; I != N/4; ++I) |
| if (SM.Mask[I] != 4*I) |
| return OpRef::fail(); |
| for (int I = 0; I != N/4; ++I) |
| if (SM.Mask[I+N/4] != 2 + 4*I) |
| return OpRef::fail(); |
| for (int I = 0; I != N/4; ++I) |
| if (SM.Mask[I+N/2] != N + 4*I) |
| return OpRef::fail(); |
| for (int I = 0; I != N/4; ++I) |
| if (SM.Mask[I+3*N/4] != N+2 + 4*I) |
| return OpRef::fail(); |
| // Matched mask for vdealb4w. |
| Results.push(Hexagon::V6_vdealb4w, ResTy, {Vb, Va}); |
| return OpRef::res(Results.top()); |
| } |
| |
| // Check if this is vpack{e,o}. |
| int N = VecLen; |
| int L = Strip.second; |
| // Check if the first strip starts at 0 or at L. |
| if (Strip.first != 0 && Strip.first != L) |
| return OpRef::fail(); |
| // Examine the rest of the mask. |
| for (int I = L; I < N; I += L) { |
| auto S = findStrip(SM.Mask.drop_front(I), 1, N-I); |
| // Check whether the mask element at the beginning of each strip |
| // increases by 2L each time. |
| if (S.first - Strip.first != 2*I) |
| return OpRef::fail(); |
| // Check whether each strip is of the same length. |
| if (S.second != unsigned(L)) |
| return OpRef::fail(); |
| } |
| |
| // Strip.first == 0 => vpacke |
| // Strip.first == L => vpacko |
| assert(Strip.first == 0 || Strip.first == L); |
| using namespace Hexagon; |
| NodeTemplate Res; |
| Res.Opc = Strip.second == 1 // Number of bytes. |
| ? (Strip.first == 0 ? V6_vpackeb : V6_vpackob) |
| : (Strip.first == 0 ? V6_vpackeh : V6_vpackoh); |
| Res.Ty = ResTy; |
| Res.Ops = { Vb, Va }; |
| Results.push(Res); |
| return OpRef::res(Results.top()); |
| } |
| |
| // Check if this is vshuff{e,o}. |
| int N = VecLen; |
| int L = Strip.second; |
| std::pair<int,unsigned> PrevS = Strip; |
| bool Flip = false; |
| for (int I = L; I < N; I += L) { |
| auto S = findStrip(SM.Mask.drop_front(I), 1, N-I); |
| if (S.second != PrevS.second) |
| return OpRef::fail(); |
| int Diff = Flip ? PrevS.first - S.first + 2*L |
| : S.first - PrevS.first; |
| if (Diff != N) |
| return OpRef::fail(); |
| Flip ^= true; |
| PrevS = S; |
| } |
| // Strip.first == 0 => vshuffe |
| // Strip.first == L => vshuffo |
| assert(Strip.first == 0 || Strip.first == L); |
| using namespace Hexagon; |
| NodeTemplate Res; |
| Res.Opc = Strip.second == 1 // Number of bytes. |
| ? (Strip.first == 0 ? V6_vshuffeb : V6_vshuffob) |
| : (Strip.first == 0 ? V6_vshufeh : V6_vshufoh); |
| Res.Ty = ResTy; |
| Res.Ops = { Vb, Va }; |
| Results.push(Res); |
| return OpRef::res(Results.top()); |
| } |
| |
| OpRef HvxSelector::expanding(ShuffleMask SM, OpRef Va, ResultStack &Results) { |
| DEBUG_WITH_TYPE("isel", {dbgs() << __func__ << '\n';}); |
| // Expanding shuffles (using all elements and inserting into larger vector): |
| // |
| // V6_vunpacku{b,h} [*] |
| // |
| // [*] Only if the upper elements (filled with 0s) are "don't care" in Mask. |
| // |
| // Note: V6_vunpacko{b,h} are or-ing the high byte/half in the result, so |
| // they are not shuffles. |
| // |
| // The argument is a single vector. |
| |
| int VecLen = SM.Mask.size(); |
| assert(2*HwLen == unsigned(VecLen) && "Expecting vector-pair type"); |
| |
| std::pair<int,unsigned> Strip = findStrip(SM.Mask, 1, VecLen); |
| |
| // The patterns for the unpacks, in terms of the starting offsets of the |
| // consecutive strips (L = length of the strip, N = VecLen): |
| // |
| // vunpacku: 0, -1, L, -1, 2L, -1 ... |
| |
| if (Strip.first != 0) |
| return OpRef::fail(); |
| |
| // The vunpackus only handle byte and half-word. |
| if (Strip.second != 1 && Strip.second != 2) |
| return OpRef::fail(); |
| |
| int N = VecLen; |
| int L = Strip.second; |
| |
| // First, check the non-ignored strips. |
| for (int I = 2*L; I < 2*N; I += 2*L) { |
| auto S = findStrip(SM.Mask.drop_front(I), 1, N-I); |
| if (S.second != unsigned(L)) |
| return OpRef::fail(); |
| if (2*S.first != I) |
| return OpRef::fail(); |
| } |
| // Check the -1s. |
| for (int I = L; I < 2*N; I += 2*L) { |
| auto S = findStrip(SM.Mask.drop_front(I), 0, N-I); |
| if (S.first != -1 || S.second != unsigned(L)) |
| return OpRef::fail(); |
| } |
| |
| unsigned Opc = Strip.second == 1 ? Hexagon::V6_vunpackub |
| : Hexagon::V6_vunpackuh; |
| Results.push(Opc, getPairVT(MVT::i8), {Va}); |
| return OpRef::res(Results.top()); |
| } |
| |
| OpRef HvxSelector::perfect(ShuffleMask SM, OpRef Va, ResultStack &Results) { |
| DEBUG_WITH_TYPE("isel", {dbgs() << __func__ << '\n';}); |
| // V6_vdeal{b,h} |
| // V6_vshuff{b,h} |
| |
| // V6_vshufoe{b,h} those are quivalent to vshuffvdd(..,{1,2}) |
| // V6_vshuffvdd (V6_vshuff) |
| // V6_dealvdd (V6_vdeal) |
| |
| int VecLen = SM.Mask.size(); |
| assert(isPowerOf2_32(VecLen) && Log2_32(VecLen) <= 8); |
| unsigned LogLen = Log2_32(VecLen); |
| unsigned HwLog = Log2_32(HwLen); |
| // The result length must be the same as the length of a single vector, |
| // or a vector pair. |
| assert(LogLen == HwLog || LogLen == HwLog+1); |
| bool Extend = (LogLen == HwLog); |
| |
| if (!isPermutation(SM.Mask)) |
| return OpRef::fail(); |
| |
| SmallVector<unsigned,8> Perm(LogLen); |
| |
| // Check if this could be a perfect shuffle, or a combination of perfect |
| // shuffles. |
| // |
| // Consider this permutation (using hex digits to make the ASCII diagrams |
| // easier to read): |
| // { 0, 8, 1, 9, 2, A, 3, B, 4, C, 5, D, 6, E, 7, F }. |
| // This is a "deal" operation: divide the input into two halves, and |
| // create the output by picking elements by alternating between these two |
| // halves: |
| // 0 1 2 3 4 5 6 7 --> 0 8 1 9 2 A 3 B 4 C 5 D 6 E 7 F [*] |
| // 8 9 A B C D E F |
| // |
| // Aside from a few special explicit cases (V6_vdealb, etc.), HVX provides |
| // a somwehat different mechanism that could be used to perform shuffle/ |
| // deal operations: a 2x2 transpose. |
| // Consider the halves of inputs again, they can be interpreted as a 2x8 |
| // matrix. A 2x8 matrix can be looked at four 2x2 matrices concatenated |
| // together. Now, when considering 2 elements at a time, it will be a 2x4 |
| // matrix (with elements 01, 23, 45, etc.), or two 2x2 matrices: |
| // 01 23 45 67 |
| // 89 AB CD EF |
| // With groups of 4, this will become a single 2x2 matrix, and so on. |
| // |
| // The 2x2 transpose instruction works by transposing each of the 2x2 |
| // matrices (or "sub-matrices"), given a specific group size. For example, |
| // if the group size is 1 (i.e. each element is its own group), there |
| // will be four transposes of the four 2x2 matrices that form the 2x8. |
| // For example, with the inputs as above, the result will be: |
| // 0 8 2 A 4 C 6 E |
| // 1 9 3 B 5 D 7 F |
| // Now, this result can be tranposed again, but with the group size of 2: |
| // 08 19 4C 5D |
| // 2A 3B 6E 7F |
| // If we then transpose that result, but with the group size of 4, we get: |
| // 0819 2A3B |
| // 4C5D 6E7F |
| // If we concatenate these two rows, it will be |
| // 0 8 1 9 2 A 3 B 4 C 5 D 6 E 7 F |
| // which is the same as the "deal" [*] above. |
| // |
| // In general, a "deal" of individual elements is a series of 2x2 transposes, |
| // with changing group size. HVX has two instructions: |
| // Vdd = V6_vdealvdd Vu, Vv, Rt |
| // Vdd = V6_shufvdd Vu, Vv, Rt |
| // that perform exactly that. The register Rt controls which transposes are |
| // going to happen: a bit at position n (counting from 0) indicates that a |
| // transpose with a group size of 2^n will take place. If multiple bits are |
| // set, multiple transposes will happen: vdealvdd will perform them starting |
| // with the largest group size, vshuffvdd will do them in the reverse order. |
| // |
| // The main observation is that each 2x2 transpose corresponds to swapping |
| // columns of bits in the binary representation of the values. |
| // |
| // The numbers {3,2,1,0} and the log2 of the number of contiguous 1 bits |
| // in a given column. The * denote the columns that will be swapped. |
| // The transpose with the group size 2^n corresponds to swapping columns |
| // 3 (the highest log) and log2(n): |
| // |
| // 3 2 1 0 0 2 1 3 0 2 3 1 |
| // * * * * * * |
| // 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 |
| // 1 0 0 0 1 8 1 0 0 0 8 1 0 0 0 8 1 0 0 0 |
| // 2 0 0 1 0 2 0 0 1 0 1 0 0 0 1 1 0 0 0 1 |
| // 3 0 0 1 1 A 1 0 1 0 9 1 0 0 1 9 1 0 0 1 |
| // 4 0 1 0 0 4 0 1 0 0 4 0 1 0 0 2 0 0 1 0 |
| // 5 0 1 0 1 C 1 1 0 0 C 1 1 0 0 A 1 0 1 0 |
| // 6 0 1 1 0 6 0 1 1 0 5 0 1 0 1 3 0 0 1 1 |
| // 7 0 1 1 1 E 1 1 1 0 D 1 1 0 1 B 1 0 1 1 |
| // 8 1 0 0 0 1 0 0 0 1 2 0 0 1 0 4 0 1 0 0 |
| // 9 1 0 0 1 9 1 0 0 1 A 1 0 1 0 C 1 1 0 0 |
| // A 1 0 1 0 3 0 0 1 1 3 0 0 1 1 5 0 1 0 1 |
| // B 1 0 1 1 B 1 0 1 1 B 1 0 1 1 D 1 1 0 1 |
| // C 1 1 0 0 5 0 1 0 1 6 0 1 1 0 6 0 1 1 0 |
| // D 1 1 0 1 D 1 1 0 1 E 1 1 1 0 E 1 1 1 0 |
| // E 1 1 1 0 7 0 1 1 1 7 0 1 1 1 7 0 1 1 1 |
| // F 1 1 1 1 F 1 1 1 1 F 1 1 1 1 F 1 1 1 1 |
| |
| auto XorPow2 = [] (ArrayRef<int> Mask, unsigned Num) { |
| unsigned X = Mask[0] ^ Mask[Num/2]; |
| // Check that the first half has the X's bits clear. |
| if ((Mask[0] & X) != 0) |
| return 0u; |
| for (unsigned I = 1; I != Num/2; ++I) { |
| if (unsigned(Mask[I] ^ Mask[I+Num/2]) != X) |
| return 0u; |
| if ((Mask[I] & X) != 0) |
| return 0u; |
| } |
| return X; |
| }; |
| |
| // Create a vector of log2's for each column: Perm[i] corresponds to |
| // the i-th bit (lsb is 0). |
| assert(VecLen > 2); |
| for (unsigned I = VecLen; I >= 2; I >>= 1) { |
| // Examine the initial segment of Mask of size I. |
| unsigned X = XorPow2(SM.Mask, I); |
| if (!isPowerOf2_32(X)) |
| return OpRef::fail(); |
| // Check the other segments of Mask. |
| for (int J = I; J < VecLen; J += I) { |
| if (XorPow2(SM.Mask.slice(J, I), I) != X) |
| return OpRef::fail(); |
| } |
| Perm[Log2_32(X)] = Log2_32(I)-1; |
| } |
| |
| // Once we have Perm, represent it as cycles. Denote the maximum log2 |
| // (equal to log2(VecLen)-1) as M. The cycle containing M can then be |
| // written as (M a1 a2 a3 ... an). That cycle can be broken up into |
| // simple swaps as (M a1)(M a2)(M a3)...(M an), with the composition |
| // order being from left to right. Any (contiguous) segment where the |
| // values ai, ai+1...aj are either all increasing or all decreasing, |
| // can be implemented via a single vshuffvdd/vdealvdd respectively. |
| // |
| // If there is a cycle (a1 a2 ... an) that does not involve M, it can |
| // be written as (M an)(a1 a2 ... an)(M a1). The first two cycles can |
| // then be folded to get (M a1 a2 ... an)(M a1), and the above procedure |
| // can be used to generate a sequence of vshuffvdd/vdealvdd. |
| // |
| // Example: |
| // Assume M = 4 and consider a permutation (0 1)(2 3). It can be written |
| // as (4 0 1)(4 0) composed with (4 2 3)(4 2), or simply |
| // (4 0 1)(4 0)(4 2 3)(4 2). |
| // It can then be expanded into swaps as |
| // (4 0)(4 1)(4 0)(4 2)(4 3)(4 2), |
| // and broken up into "increasing" segments as |
| // [(4 0)(4 1)] [(4 0)(4 2)(4 3)] [(4 2)]. |
| // This is equivalent to |
| // (4 0 1)(4 0 2 3)(4 2), |
| // which can be implemented as 3 vshufvdd instructions. |
| |
| using CycleType = SmallVector<unsigned,8>; |
| std::set<CycleType> Cycles; |
| std::set<unsigned> All; |
| |
| for (unsigned I : Perm) |
| All.insert(I); |
| |
| // If the cycle contains LogLen-1, move it to the front of the cycle. |
| // Otherwise, return the cycle unchanged. |
| auto canonicalize = [LogLen](const CycleType &C) -> CycleType { |
| unsigned LogPos, N = C.size(); |
| for (LogPos = 0; LogPos != N; ++LogPos) |
| if (C[LogPos] == LogLen-1) |
| break; |
| if (LogPos == N) |
| return C; |
| |
| CycleType NewC(C.begin()+LogPos, C.end()); |
| NewC.append(C.begin(), C.begin()+LogPos); |
| return NewC; |
| }; |
| |
| auto pfs = [](const std::set<CycleType> &Cs, unsigned Len) { |
| // Ordering: shuff: 5 0 1 2 3 4, deal: 5 4 3 2 1 0 (for Log=6), |
| // for bytes zero is included, for halfwords is not. |
| if (Cs.size() != 1) |
| return 0u; |
| const CycleType &C = *Cs.begin(); |
| if (C[0] != Len-1) |
| return 0u; |
| int D = Len - C.size(); |
| if (D != 0 && D != 1) |
| return 0u; |
| |
| bool IsDeal = true, IsShuff = true; |
| for (unsigned I = 1; I != Len-D; ++I) { |
| if (C[I] != Len-1-I) |
| IsDeal = false; |
| if (C[I] != I-(1-D)) // I-1, I |
| IsShuff = false; |
| } |
| // At most one, IsDeal or IsShuff, can be non-zero. |
| assert(!(IsDeal || IsShuff) || IsDeal != IsShuff); |
| static unsigned Deals[] = { Hexagon::V6_vdealb, Hexagon::V6_vdealh }; |
| static unsigned Shufs[] = { Hexagon::V6_vshuffb, Hexagon::V6_vshuffh }; |
| return IsDeal ? Deals[D] : (IsShuff ? Shufs[D] : 0); |
| }; |
| |
| while (!All.empty()) { |
| unsigned A = *All.begin(); |
| All.erase(A); |
| CycleType C; |
| C.push_back(A); |
| for (unsigned B = Perm[A]; B != A; B = Perm[B]) { |
| C.push_back(B); |
| All.erase(B); |
| } |
| if (C.size() <= 1) |
| continue; |
| Cycles.insert(canonicalize(C)); |
| } |
| |
| MVT SingleTy = getSingleVT(MVT::i8); |
| MVT PairTy = getPairVT(MVT::i8); |
| |
| // Recognize patterns for V6_vdeal{b,h} and V6_vshuff{b,h}. |
| if (unsigned(VecLen) == HwLen) { |
| if (unsigned SingleOpc = pfs(Cycles, LogLen)) { |
| Results.push(SingleOpc, SingleTy, {Va}); |
| return OpRef::res(Results.top()); |
| } |
| } |
| |
| SmallVector<unsigned,8> SwapElems; |
| if (HwLen == unsigned(VecLen)) |
| SwapElems.push_back(LogLen-1); |
| |
| for (const CycleType &C : Cycles) { |
| unsigned First = (C[0] == LogLen-1) ? 1 : 0; |
| SwapElems.append(C.begin()+First, C.end()); |
| if (First == 0) |
| SwapElems.push_back(C[0]); |
| } |
| |
| const SDLoc &dl(Results.InpNode); |
| OpRef Arg = !Extend ? Va |
| : concat(Va, OpRef::undef(SingleTy), Results); |
| |
| for (unsigned I = 0, E = SwapElems.size(); I != E; ) { |
| bool IsInc = I == E-1 || SwapElems[I] < SwapElems[I+1]; |
| unsigned S = (1u << SwapElems[I]); |
| if (I < E-1) { |
| while (++I < E-1 && IsInc == (SwapElems[I] < SwapElems[I+1])) |
| S |= 1u << SwapElems[I]; |
| // The above loop will not add a bit for the final SwapElems[I+1], |
| // so add it here. |
| S |= 1u << SwapElems[I]; |
| } |
| ++I; |
| |
| NodeTemplate Res; |
| Results.push(Hexagon::A2_tfrsi, MVT::i32, |
| { DAG.getTargetConstant(S, dl, MVT::i32) }); |
| Res.Opc = IsInc ? Hexagon::V6_vshuffvdd : Hexagon::V6_vdealvdd; |
| Res.Ty = PairTy; |
| Res.Ops = { OpRef::hi(Arg), OpRef::lo(Arg), OpRef::res(-1) }; |
| Results.push(Res); |
| Arg = OpRef::res(Results.top()); |
| } |
| |
| return !Extend ? Arg : OpRef::lo(Arg); |
| } |
| |
| OpRef HvxSelector::butterfly(ShuffleMask SM, OpRef Va, ResultStack &Results) { |
| DEBUG_WITH_TYPE("isel", {dbgs() << __func__ << '\n';}); |
| // Butterfly shuffles. |
| // |
| // V6_vdelta |
| // V6_vrdelta |
| // V6_vror |
| |
| // The assumption here is that all elements picked by Mask are in the |
| // first operand to the vector_shuffle. This assumption is enforced |
| // by the caller. |
| |
| MVT ResTy = getSingleVT(MVT::i8); |
| PermNetwork::Controls FC, RC; |
| const SDLoc &dl(Results.InpNode); |
| int VecLen = SM.Mask.size(); |
| |
| for (int M : SM.Mask) { |
| if (M != -1 && M >= VecLen) |
| return OpRef::fail(); |
| } |
| |
| // Try the deltas/benes for both single vectors and vector pairs. |
| ForwardDeltaNetwork FN(SM.Mask); |
| if (FN.run(FC)) { |
| SDValue Ctl = getVectorConstant(FC, dl); |
| Results.push(Hexagon::V6_vdelta, ResTy, {Va, OpRef(Ctl)}); |
| return OpRef::res(Results.top()); |
| } |
| |
| // Try reverse delta. |
| ReverseDeltaNetwork RN(SM.Mask); |
| if (RN.run(RC)) { |
| SDValue Ctl = getVectorConstant(RC, dl); |
| Results.push(Hexagon::V6_vrdelta, ResTy, {Va, OpRef(Ctl)}); |
| return OpRef::res(Results.top()); |
| } |
| |
| // Do Benes. |
| BenesNetwork BN(SM.Mask); |
| if (BN.run(FC, RC)) { |
| SDValue CtlF = getVectorConstant(FC, dl); |
| SDValue CtlR = getVectorConstant(RC, dl); |
| Results.push(Hexagon::V6_vdelta, ResTy, {Va, OpRef(CtlF)}); |
| Results.push(Hexagon::V6_vrdelta, ResTy, |
| {OpRef::res(-1), OpRef(CtlR)}); |
| return OpRef::res(Results.top()); |
| } |
| |
| return OpRef::fail(); |
| } |
| |
| SDValue HvxSelector::getVectorConstant(ArrayRef<uint8_t> Data, |
| const SDLoc &dl) { |
| SmallVector<SDValue, 128> Elems; |
| for (uint8_t C : Data) |
| Elems.push_back(DAG.getConstant(C, dl, MVT::i8)); |
| MVT VecTy = MVT::getVectorVT(MVT::i8, Data.size()); |
| SDValue BV = DAG.getBuildVector(VecTy, dl, Elems); |
| SDValue LV = Lower.LowerOperation(BV, DAG); |
| DAG.RemoveDeadNode(BV.getNode()); |
| return LV; |
| } |
| |
| void HvxSelector::selectShuffle(SDNode *N) { |
| DEBUG_WITH_TYPE("isel", { |
| dbgs() << "Starting " << __func__ << " on node:\n"; |
| N->dump(&DAG); |
| }); |
| MVT ResTy = N->getValueType(0).getSimpleVT(); |
| // Assume that vector shuffles operate on vectors of bytes. |
| assert(ResTy.isVector() && ResTy.getVectorElementType() == MVT::i8); |
| |
| auto *SN = cast<ShuffleVectorSDNode>(N); |
| std::vector<int> Mask(SN->getMask().begin(), SN->getMask().end()); |
| // This shouldn't really be necessary. Is it? |
| for (int &Idx : Mask) |
| if (Idx != -1 && Idx < 0) |
| Idx = -1; |
| |
| unsigned VecLen = Mask.size(); |
| bool HavePairs = (2*HwLen == VecLen); |
| assert(ResTy.getSizeInBits() / 8 == VecLen); |
| |
| // Vd = vector_shuffle Va, Vb, Mask |
| // |
| |
| bool UseLeft = false, UseRight = false; |
| for (unsigned I = 0; I != VecLen; ++I) { |
| if (Mask[I] == -1) |
| continue; |
| unsigned Idx = Mask[I]; |
| assert(Idx < 2*VecLen); |
| if (Idx < VecLen) |
| UseLeft = true; |
| else |
| UseRight = true; |
| } |
| |
| DEBUG_WITH_TYPE("isel", { |
| dbgs() << "VecLen=" << VecLen << " HwLen=" << HwLen << " UseLeft=" |
| << UseLeft << " UseRight=" << UseRight << " HavePairs=" |
| << HavePairs << '\n'; |
| }); |
| // If the mask is all -1's, generate "undef". |
| if (!UseLeft && !UseRight) { |
| ISel.ReplaceNode(N, ISel.selectUndef(SDLoc(SN), ResTy).getNode()); |
| return; |
| } |
| |
| SDValue Vec0 = N->getOperand(0); |
| SDValue Vec1 = N->getOperand(1); |
| ResultStack Results(SN); |
| Results.push(TargetOpcode::COPY, ResTy, {Vec0}); |
| Results.push(TargetOpcode::COPY, ResTy, {Vec1}); |
| OpRef Va = OpRef::res(Results.top()-1); |
| OpRef Vb = OpRef::res(Results.top()); |
| |
| OpRef Res = !HavePairs ? shuffs2(ShuffleMask(Mask), Va, Vb, Results) |
| : shuffp2(ShuffleMask(Mask), Va, Vb, Results); |
| |
| bool Done = Res.isValid(); |
| if (Done) { |
| // Make sure that Res is on the stack before materializing. |
| Results.push(TargetOpcode::COPY, ResTy, {Res}); |
| materialize(Results); |
| } else { |
| Done = scalarizeShuffle(Mask, SDLoc(N), ResTy, Vec0, Vec1, N); |
| } |
| |
| if (!Done) { |
| #ifndef NDEBUG |
| dbgs() << "Unhandled shuffle:\n"; |
| SN->dumpr(&DAG); |
| #endif |
| llvm_unreachable("Failed to select vector shuffle"); |
| } |
| } |
| |
| void HvxSelector::selectRor(SDNode *N) { |
| // If this is a rotation by less than 8, use V6_valignbi. |
| MVT Ty = N->getValueType(0).getSimpleVT(); |
| const SDLoc &dl(N); |
| SDValue VecV = N->getOperand(0); |
| SDValue RotV = N->getOperand(1); |
| SDNode *NewN = nullptr; |
| |
| if (auto *CN = dyn_cast<ConstantSDNode>(RotV.getNode())) { |
| unsigned S = CN->getZExtValue() % HST.getVectorLength(); |
| if (S == 0) { |
| NewN = VecV.getNode(); |
| } else if (isUInt<3>(S)) { |
| SDValue C = DAG.getTargetConstant(S, dl, MVT::i32); |
| NewN = DAG.getMachineNode(Hexagon::V6_valignbi, dl, Ty, |
| {VecV, VecV, C}); |
| } |
| } |
| |
| if (!NewN) |
| NewN = DAG.getMachineNode(Hexagon::V6_vror, dl, Ty, {VecV, RotV}); |
| |
| ISel.ReplaceNode(N, NewN); |
| } |
| |
| void HvxSelector::selectVAlign(SDNode *N) { |
| SDValue Vv = N->getOperand(0); |
| SDValue Vu = N->getOperand(1); |
| SDValue Rt = N->getOperand(2); |
| SDNode *NewN = DAG.getMachineNode(Hexagon::V6_valignb, SDLoc(N), |
| N->getValueType(0), {Vv, Vu, Rt}); |
| ISel.ReplaceNode(N, NewN); |
| DAG.RemoveDeadNode(N); |
| } |
| |
| void HexagonDAGToDAGISel::SelectHvxShuffle(SDNode *N) { |
| HvxSelector(*this, *CurDAG).selectShuffle(N); |
| } |
| |
| void HexagonDAGToDAGISel::SelectHvxRor(SDNode *N) { |
| HvxSelector(*this, *CurDAG).selectRor(N); |
| } |
| |
| void HexagonDAGToDAGISel::SelectHvxVAlign(SDNode *N) { |
| HvxSelector(*this, *CurDAG).selectVAlign(N); |
| } |
| |
| void HexagonDAGToDAGISel::SelectV65GatherPred(SDNode *N) { |
| const SDLoc &dl(N); |
| SDValue Chain = N->getOperand(0); |
| SDValue Address = N->getOperand(2); |
| SDValue Predicate = N->getOperand(3); |
| SDValue Base = N->getOperand(4); |
| SDValue Modifier = N->getOperand(5); |
| SDValue Offset = N->getOperand(6); |
| |
| unsigned Opcode; |
| unsigned IntNo = cast<ConstantSDNode>(N->getOperand(1))->getZExtValue(); |
| switch (IntNo) { |
| default: |
| llvm_unreachable("Unexpected HVX gather intrinsic."); |
| case Intrinsic::hexagon_V6_vgathermhq: |
| case Intrinsic::hexagon_V6_vgathermhq_128B: |
| Opcode = Hexagon::V6_vgathermhq_pseudo; |
| break; |
| case Intrinsic::hexagon_V6_vgathermwq: |
| case Intrinsic::hexagon_V6_vgathermwq_128B: |
| Opcode = Hexagon::V6_vgathermwq_pseudo; |
| break; |
| case Intrinsic::hexagon_V6_vgathermhwq: |
| case Intrinsic::hexagon_V6_vgathermhwq_128B: |
| Opcode = Hexagon::V6_vgathermhwq_pseudo; |
| break; |
| } |
| |
| SDVTList VTs = CurDAG->getVTList(MVT::Other); |
| SDValue Ops[] = { Address, Predicate, Base, Modifier, Offset, Chain }; |
| SDNode *Result = CurDAG->getMachineNode(Opcode, dl, VTs, Ops); |
| |
| MachineMemOperand *MemOp = cast<MemIntrinsicSDNode>(N)->getMemOperand(); |
| CurDAG->setNodeMemRefs(cast<MachineSDNode>(Result), {MemOp}); |
| |
| ReplaceNode(N, Result); |
| } |
| |
| void HexagonDAGToDAGISel::SelectV65Gather(SDNode *N) { |
| const SDLoc &dl(N); |
| SDValue Chain = N->getOperand(0); |
| SDValue Address = N->getOperand(2); |
| SDValue Base = N->getOperand(3); |
| SDValue Modifier = N->getOperand(4); |
| SDValue Offset = N->getOperand(5); |
| |
| unsigned Opcode; |
| unsigned IntNo = cast<ConstantSDNode>(N->getOperand(1))->getZExtValue(); |
| switch (IntNo) { |
| default: |
| llvm_unreachable("Unexpected HVX gather intrinsic."); |
| case Intrinsic::hexagon_V6_vgathermh: |
| case Intrinsic::hexagon_V6_vgathermh_128B: |
| Opcode = Hexagon::V6_vgathermh_pseudo; |
| break; |
| case Intrinsic::hexagon_V6_vgathermw: |
| case Intrinsic::hexagon_V6_vgathermw_128B: |
| Opcode = Hexagon::V6_vgathermw_pseudo; |
| break; |
| case Intrinsic::hexagon_V6_vgathermhw: |
| case Intrinsic::hexagon_V6_vgathermhw_128B: |
| Opcode = Hexagon::V6_vgathermhw_pseudo; |
| break; |
| } |
| |
| SDVTList VTs = CurDAG->getVTList(MVT::Other); |
| SDValue Ops[] = { Address, Base, Modifier, Offset, Chain }; |
| SDNode *Result = CurDAG->getMachineNode(Opcode, dl, VTs, Ops); |
| |
| MachineMemOperand *MemOp = cast<MemIntrinsicSDNode>(N)->getMemOperand(); |
| CurDAG->setNodeMemRefs(cast<MachineSDNode>(Result), {MemOp}); |
| |
| ReplaceNode(N, Result); |
| } |
| |
| void HexagonDAGToDAGISel::SelectHVXDualOutput(SDNode *N) { |
| unsigned IID = cast<ConstantSDNode>(N->getOperand(0))->getZExtValue(); |
| SDNode *Result; |
| switch (IID) { |
| case Intrinsic::hexagon_V6_vaddcarry: { |
| SmallVector<SDValue, 3> Ops = { N->getOperand(1), N->getOperand(2), |
| N->getOperand(3) }; |
| SDVTList VTs = CurDAG->getVTList(MVT::v16i32, MVT::v512i1); |
| Result = CurDAG->getMachineNode(Hexagon::V6_vaddcarry, SDLoc(N), VTs, Ops); |
| break; |
| } |
| case Intrinsic::hexagon_V6_vaddcarry_128B: { |
| SmallVector<SDValue, 3> Ops = { N->getOperand(1), N->getOperand(2), |
| N->getOperand(3) }; |
| SDVTList VTs = CurDAG->getVTList(MVT::v32i32, MVT::v1024i1); |
| Result = CurDAG->getMachineNode(Hexagon::V6_vaddcarry, SDLoc(N), VTs, Ops); |
| break; |
| } |
| case Intrinsic::hexagon_V6_vsubcarry: { |
| SmallVector<SDValue, 3> Ops = { N->getOperand(1), N->getOperand(2), |
| N->getOperand(3) }; |
| SDVTList VTs = CurDAG->getVTList(MVT::v16i32, MVT::v512i1); |
| Result = CurDAG->getMachineNode(Hexagon::V6_vsubcarry, SDLoc(N), VTs, Ops); |
| break; |
| } |
| case Intrinsic::hexagon_V6_vsubcarry_128B: { |
| SmallVector<SDValue, 3> Ops = { N->getOperand(1), N->getOperand(2), |
| N->getOperand(3) }; |
| SDVTList VTs = CurDAG->getVTList(MVT::v32i32, MVT::v1024i1); |
| Result = CurDAG->getMachineNode(Hexagon::V6_vsubcarry, SDLoc(N), VTs, Ops); |
| break; |
| } |
| default: |
| llvm_unreachable("Unexpected HVX dual output intrinsic."); |
| } |
| ReplaceUses(N, Result); |
| ReplaceUses(SDValue(N, 0), SDValue(Result, 0)); |
| ReplaceUses(SDValue(N, 1), SDValue(Result, 1)); |
| CurDAG->RemoveDeadNode(N); |
| } |