Codebase Browser
llvm
Go to App

llvm/llvm/lib/Target/Hexagon/HexagonISelDAGToDAGHVX.cpp 

//===-- 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/BitVector.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/CodeGen/MachineInstrBuilder.h"
#include "llvm/CodeGen/SelectionDAGISel.h"
#include "llvm/IR/Intrinsics.h"
#include "llvm/IR/IntrinsicsHexagon.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/MathExtras.h"

#include <algorithm>
#include <cmath>
#include <deque>
#include <functional>
#include <map>
#include <optional>
#include <set>
#include <unordered_map>
#include <utility>
#include <vector>

#define DEBUG_TYPE …
usingnamespacellvm;

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 { … };

// Graph coloring utility used to partition nodes into two groups:
// they will correspond to nodes routed to the upper and lower networks.
struct Coloring { … };
} // namespace

std::pair<bool, ColorKind> Coloring::getUniqueColor(const NodeSet &Nodes) { … }

void Coloring::build() { … }

bool Coloring::color() { … }

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
void Coloring::dump() const {
  dbgs() << "{ Order:   {";
  for (Node P : Order) {
    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 { … };

struct ForwardDeltaNetwork : public PermNetwork { … };

struct ReverseDeltaNetwork : public PermNetwork { … };

struct BenesNetwork : public PermNetwork { … };
} // namespace

bool ForwardDeltaNetwork::route(ElemType *P, RowType *T, unsigned Size,
                                unsigned Step) { … }

bool ReverseDeltaNetwork::route(ElemType *P, RowType *T, unsigned Size,
                                unsigned Step) { … }

bool BenesNetwork::route(ElemType *P, RowType *T, unsigned Size,
                         unsigned Step) { … }

// --------------------------------------------------------------------
// Support for building selection results (output instructions that are
// parts of the final selection).

namespace {
struct OpRef { … };

struct NodeTemplate { … };

struct ResultStack { … };
} // 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 { … };

LLVM_ATTRIBUTE_UNUSED
raw_ostream &operator<<(raw_ostream &OS, const ShuffleMask &SM) { … }
} // namespace

namespace shuffles {
MaskT;
// Vdd = vshuffvdd(Vu, Vv, Rt)
// Vdd = vdealvdd(Vu, Vv, Rt)
// Vd  = vpack(Vu, Vv, Size, TakeOdd)
// Vd  = vshuff(Vu, Vv, Size, TakeOdd)
// Vd  = vdeal(Vu, Vv, Size, TakeOdd)
// Vd  = vdealb4w(Vu, Vv)

ArrayRef<int> lo(ArrayRef<int> Vuu) { … }
ArrayRef<int> hi(ArrayRef<int> Vuu) { … }

MaskT vshuffvdd(ArrayRef<int> Vu, ArrayRef<int> Vv, unsigned Rt) { … }

MaskT vdealvdd(ArrayRef<int> Vu, ArrayRef<int> Vv, unsigned Rt) { … }

MaskT vpack(ArrayRef<int> Vu, ArrayRef<int> Vv, unsigned Size, bool TakeOdd) { … }

MaskT vshuff(ArrayRef<int> Vu, ArrayRef<int> Vv, unsigned Size, bool TakeOdd) { … }

MaskT vdeal(ArrayRef<int> Vu, ArrayRef<int> Vv, unsigned Size, bool TakeOdd) { … }

MaskT vdealb4w(ArrayRef<int> Vu, ArrayRef<int> Vv) { … }

template <typename ShuffFunc, typename... OptArgs>
auto mask(ShuffFunc S, unsigned Length, OptArgs... args) -> MaskT { … }

} // namespace shuffles

// --------------------------------------------------------------------
// The HvxSelector class.

static const HexagonTargetLowering &getHexagonLowering(SelectionDAG &G) { … }
static const HexagonSubtarget &getHexagonSubtarget(SelectionDAG &G) { … }

namespace llvm {
  struct HvxSelector { … };
} // namespace llvm

static void splitMask(ArrayRef<int> Mask, MutableArrayRef<int> MaskL,
                      MutableArrayRef<int> MaskR) { … }

static std::pair<int,unsigned> findStrip(ArrayRef<int> A, int Inc,
                                         unsigned MaxLen) { … }

static bool isUndef(ArrayRef<int> Mask) { … }

static bool isIdentity(ArrayRef<int> Mask) { … }

static bool isLowHalfOnly(ArrayRef<int> Mask) { … }

static SmallVector<unsigned, 4> getInputSegmentList(ShuffleMask SM,
                                                    unsigned SegLen) { … }

static SmallVector<unsigned, 4> getOutputSegmentMap(ShuffleMask SM,
                                                    unsigned SegLen) { … }

static void packSegmentMask(ArrayRef<int> Mask, ArrayRef<unsigned> OutSegMap,
                            unsigned SegLen, MutableArrayRef<int> PackedMask) { … }

bool HvxSelector::selectVectorConstants(SDNode *N) { … }

void HvxSelector::materialize(const ResultStack &Results) { … }

OpRef HvxSelector::concats(OpRef Lo, OpRef Hi, ResultStack &Results) { … }

OpRef HvxSelector::funnels(OpRef Va, OpRef Vb, int Amount,
                           ResultStack &Results) { … }

// Va, Vb are single vectors. If SM only uses two vector halves from Va/Vb,
// pack these halves into a single vector, and remap SM into NewMask to use
// the new vector instead.
OpRef HvxSelector::packs(ShuffleMask SM, OpRef Va, OpRef Vb,
                         ResultStack &Results, MutableArrayRef<int> NewMask,
                         unsigned Options) { … }

// Va, Vb are vector pairs. If SM only uses two single vectors from Va/Vb,
// pack these vectors into a pair, and remap SM into NewMask to use the
// new pair instead.
OpRef HvxSelector::packp(ShuffleMask SM, OpRef Va, OpRef Vb,
                         ResultStack &Results, MutableArrayRef<int> NewMask) { … }

OpRef HvxSelector::vmuxs(ArrayRef<uint8_t> Bytes, OpRef Va, OpRef Vb,
                         ResultStack &Results) { … }

OpRef HvxSelector::vmuxp(ArrayRef<uint8_t> Bytes, OpRef Va, OpRef Vb,
                         ResultStack &Results) { … }

OpRef HvxSelector::shuffs1(ShuffleMask SM, OpRef Va, ResultStack &Results) { … }

OpRef HvxSelector::shuffs2(ShuffleMask SM, OpRef Va, OpRef Vb,
                           ResultStack &Results) { … }

OpRef HvxSelector::shuffp1(ShuffleMask SM, OpRef Va, ResultStack &Results) { … }

OpRef HvxSelector::shuffp2(ShuffleMask SM, OpRef Va, OpRef Vb,
                           ResultStack &Results) { … }

namespace {
  struct Deleter : public SelectionDAG::DAGNodeDeletedListener { … };

  template <typename T>
  struct NullifyingVector : public T { … };
}

void HvxSelector::select(SDNode *ISelN) { … }

bool HvxSelector::scalarizeShuffle(ArrayRef<int> Mask, const SDLoc &dl,
                                   MVT ResTy, SDValue Va, SDValue Vb,
                                   SDNode *N) { … }

SmallVector<uint32_t, 8> HvxSelector::getPerfectCompletions(ShuffleMask SM,
                                                            unsigned Width) { … }

SmallVector<uint32_t, 8>
HvxSelector::completeToPerfect(ArrayRef<uint32_t> Completions, unsigned Width) { … }

std::optional<int> HvxSelector::rotationDistance(ShuffleMask SM,
                                                 unsigned WrapAt) { … }

OpRef HvxSelector::contracting(ShuffleMask SM, OpRef Va, OpRef Vb,
                               ResultStack &Results) { … }

OpRef HvxSelector::expanding(ShuffleMask SM, OpRef Va, ResultStack &Results) { … }

OpRef HvxSelector::perfect(ShuffleMask SM, OpRef Va, ResultStack &Results) { … }

OpRef HvxSelector::butterfly(ShuffleMask SM, OpRef Va, ResultStack &Results) { … }

SDValue HvxSelector::getConst32(int Val, const SDLoc &dl) { … }

SDValue HvxSelector::getVectorConstant(ArrayRef<uint8_t> Data,
                                       const SDLoc &dl) { … }

void HvxSelector::selectExtractSubvector(SDNode *N) { … }

void HvxSelector::selectShuffle(SDNode *N) { … }

void HvxSelector::selectRor(SDNode *N) { … }

void HvxSelector::selectVAlign(SDNode *N) { … }

void HexagonDAGToDAGISel::PreprocessHvxISelDAG() { … }

template <> struct std::hash<SDValue> { … };

void HexagonDAGToDAGISel::ppHvxShuffleOfShuffle(std::vector<SDNode *> &&Nodes) { … }

void HexagonDAGToDAGISel::SelectHvxExtractSubvector(SDNode *N) { … }

void HexagonDAGToDAGISel::SelectHvxShuffle(SDNode *N) { … }

void HexagonDAGToDAGISel::SelectHvxRor(SDNode *N) { … }

void HexagonDAGToDAGISel::SelectHvxVAlign(SDNode *N) { … }

void HexagonDAGToDAGISel::SelectV65GatherPred(SDNode *N) { … }

void HexagonDAGToDAGISel::SelectV65Gather(SDNode *N) { … }

void HexagonDAGToDAGISel::SelectHVXDualOutput(SDNode *N) { … }