18#include "llvm/IR/IntrinsicsHexagon.h"
30#include <unordered_map>
34#define DEBUG_TYPE "hexagon-isel"
104enum class ColorKind {
None, Red, Black };
110 using MapType = std::map<Node, ColorKind>;
119 const MapType &colors()
const {
123 ColorKind other(ColorKind Color) {
124 if (Color == ColorKind::None)
125 return ColorKind::Red;
126 return Color == ColorKind::Red ? ColorKind::Black : ColorKind::Red;
134 std::set<Node> Needed;
136 using NodeSet = std::set<Node>;
137 std::map<Node,NodeSet> Edges;
141 return (Pos < Num/2) ? Pos + Num/2 : Pos - Num/2;
144 ColorKind getColor(
Node N) {
145 auto F = Colors.find(
N);
146 return F != Colors.end() ?
F->second : ColorKind::None;
149 std::pair<bool, ColorKind> getUniqueColor(
const NodeSet &Nodes);
156std::pair<bool, ColorKind> Coloring::getUniqueColor(
const NodeSet &Nodes) {
157 auto Color = ColorKind::None;
158 for (
Node N : Nodes) {
159 ColorKind ColorN = getColor(
N);
160 if (ColorN == ColorKind::None)
162 if (Color == ColorKind::None)
164 else if (Color != ColorKind::None && Color != ColorN)
165 return {
false, ColorKind::None };
167 return {
true, Color };
170void Coloring::build() {
172 for (
unsigned P = 0;
P != Order.size(); ++
P) {
176 Node PC = Order[conj(
P)];
182 for (
unsigned I = 0;
I != Order.size(); ++
I) {
183 if (!Needed.count(
I))
195bool Coloring::color() {
197 auto Enqueue = [
this,&FirstQ] (
Node N) {
200 for (
unsigned I = 0;
I != Q.
size(); ++
I) {
204 FirstQ.
insert(Q.begin(), Q.end());
206 for (
Node N : Needed)
209 for (
Node N : FirstQ) {
213 auto P = getUniqueColor(Ns);
216 Colors[
N] = other(
P.second);
220 for (
auto E : Edges) {
222 if (!Needed.count(conj(
N)) || Colors.count(
N))
224 auto P = getUniqueColor(
E.second);
227 Colors[
N] = other(
P.second);
232 std::vector<Node> WorkQ;
233 for (
auto E : Edges) {
235 if (!Colors.count(
N))
239 for (
Node N : WorkQ) {
241 auto P = getUniqueColor(Ns);
243 Colors[
N] = other(
P.second);
249 ColorKind ColorN = other(ColorKind::None);
250 ColorKind ColorC = other(ColorN);
253 for (
Node M : CopyNs) {
254 ColorKind ColorM = getColor(M);
255 if (ColorM == ColorC) {
268 for (
unsigned I = 0;
I != Order.size(); ++
I)
269 if (Colors.count(
I) == 0)
270 Colors[
I] = ColorKind::None;
275#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
276void Coloring::dump()
const {
277 dbgs() <<
"{ Order: {";
278 for (
Node P : Order) {
285 dbgs() <<
" Needed: {";
286 for (
Node N : Needed)
290 dbgs() <<
" Edges: {\n";
291 for (
auto E : Edges) {
292 dbgs() <<
" " <<
E.first <<
" -> {";
293 for (
auto N :
E.second)
299 auto ColorKindToName = [](ColorKind
C) {
301 case ColorKind::None:
305 case ColorKind::Black:
311 dbgs() <<
" Colors: {\n";
312 for (
auto C : Colors)
313 dbgs() <<
" " <<
C.first <<
" -> " << ColorKindToName(
C.second) <<
"\n";
323 using Controls = std::vector<uint8_t>;
324 using ElemType = int;
325 static constexpr ElemType
Ignore = ElemType(-1);
341 unsigned S = Order.size();
345 Table.resize(Order.size());
346 for (RowType &Row : Table)
347 Row.resize(Mult*Log, None);
350 void getControls(Controls &V,
unsigned StartAt, uint8_t Dir)
const {
351 unsigned Size = Order.size();
353 for (
unsigned I = 0;
I !=
Size; ++
I) {
355 for (
unsigned L = 0;
L != Log; ++
L) {
356 unsigned C = ctl(
I, StartAt+L) ==
Switch;
367 uint8_t ctl(ElemType Pos,
unsigned Step)
const {
368 return Table[Pos][Step];
370 unsigned size()
const {
373 unsigned steps()
const {
379 std::vector<ElemType> Order;
380 using RowType = std::vector<uint8_t>;
381 std::vector<RowType> Table;
384struct ForwardDeltaNetwork :
public PermNetwork {
387 bool run(Controls &V) {
388 if (!route(Order.data(), Table.data(),
size(), 0))
390 getControls(V, 0, Forward);
395 bool route(ElemType *
P, RowType *
T,
unsigned Size,
unsigned Step);
398struct ReverseDeltaNetwork :
public PermNetwork {
401 bool run(Controls &V) {
402 if (!route(Order.data(), Table.data(),
size(), 0))
409 bool route(ElemType *
P, RowType *
T,
unsigned Size,
unsigned Step);
412struct BenesNetwork :
public PermNetwork {
415 bool run(Controls &
F, Controls &R) {
416 if (!route(Order.data(), Table.data(),
size(), 0))
419 getControls(
F, 0, Forward);
425 bool route(ElemType *
P, RowType *
T,
unsigned Size,
unsigned Step);
429bool ForwardDeltaNetwork::route(ElemType *
P, RowType *
T,
unsigned Size,
431 bool UseUp =
false, UseDown =
false;
438 for (ElemType J = 0; J != Num; ++J) {
446 S = (J < Num/2) ?
Pass : Switch;
448 S = (J < Num/2) ? Switch :
Pass;
451 ElemType
U = (S ==
Pass) ?
I : (
I < Num/2 ?
I+Num/2 :
I-Num/2);
456 if (
T[U][Step] != S &&
T[U][Step] !=
None)
461 for (ElemType J = 0; J != Num; ++J)
462 if (
P[J] !=
Ignore &&
P[J] >= Num/2)
466 if (UseUp && !route(
P,
T,
Size/2, Step+1))
474bool ReverseDeltaNetwork::route(ElemType *
P, RowType *
T,
unsigned Size,
476 unsigned Pets = Log-1 - Step;
477 bool UseUp =
false, UseDown =
false;
482 const Coloring::MapType &
M =
G.colors();
486 ColorKind ColorUp = ColorKind::None;
487 for (ElemType J = 0; J != Num; ++J) {
493 ColorKind
C =
M.at(
I);
494 if (
C == ColorKind::None)
499 bool InpUp =
I < Num/2;
500 if (ColorUp == ColorKind::None)
501 ColorUp = InpUp ?
C :
G.other(
C);
502 if ((
C == ColorUp) != InpUp) {
509 S = (J < Num/2) ?
Pass : Switch;
512 S = (J < Num/2) ? Switch :
Pass;
520 for (ElemType J = 0,
E =
Size / 2; J !=
E; ++J) {
522 ElemType PC =
P[J+
Size/2];
525 if (
T[J][Pets] == Switch)
527 if (
T[J+
Size/2][Pets] == Switch)
533 for (ElemType J = 0; J != Num; ++J)
534 if (
P[J] !=
Ignore &&
P[J] >= Num/2)
538 if (UseUp && !route(
P,
T,
Size/2, Step+1))
546bool BenesNetwork::route(ElemType *
P, RowType *
T,
unsigned Size,
549 const Coloring::MapType &
M =
G.colors();
554 unsigned Pets = 2*Log-1 - Step;
555 bool UseUp =
false, UseDown =
false;
560 ColorKind ColorUp = ColorKind::None;
561 for (ElemType J = 0; J != Num; ++J) {
565 ColorKind
C =
M.at(
I);
566 if (
C == ColorKind::None)
568 if (ColorUp == ColorKind::None) {
569 ColorUp = (
I < Num / 2) ? ColorKind::Red : ColorKind::Black;
571 unsigned CI = (
I < Num/2) ?
I+Num/2 :
I-Num/2;
577 T[J][Pets] = (J < Num/2) ?
Pass : Switch;
584 T[J][Pets] = (J < Num/2) ? Switch :
Pass;
591 for (ElemType J = 0; J != Num/2; ++J) {
593 ElemType PC =
P[J+Num/2];
596 if (
T[J][Pets] == Switch)
598 if (
T[J+Num/2][Pets] == Switch)
604 for (ElemType J = 0; J != Num; ++J)
605 if (
P[J] !=
Ignore &&
P[J] >= Num/2)
609 if (UseUp && !route(
P,
T,
Size/2, Step+1))
624 bool isValue()
const {
return OpV.getNode() !=
nullptr; }
627 static OpRef res(
int N) {
return OpRef(Whole | (
N &
Index)); }
628 static OpRef
fail() {
return OpRef(Invalid); }
630 static OpRef
lo(
const OpRef &R) {
632 return OpRef(
R.OpN & (Undef |
Index | LoHalf));
634 static OpRef
hi(
const OpRef &R) {
636 return OpRef(
R.OpN & (Undef |
Index | HiHalf));
638 static OpRef undef(
MVT Ty) {
return OpRef(Undef | Ty.
SimpleTy); }
654 Whole = LoHalf | HiHalf,
664 OpRef(
unsigned N) : OpN(
N) {}
668 NodeTemplate() =
default;
671 std::vector<OpRef> Ops;
678 : InpNode(Inp), InpTy(Inp->getValueType(0).getSimpleVT()) {}
681 unsigned push(
const NodeTemplate &Res) {
683 return List.size()-1;
685 unsigned push(
unsigned Opc,
MVT Ty, std::vector<OpRef> &&Ops) {
692 bool empty()
const {
return List.empty(); }
693 unsigned size()
const {
return List.size(); }
694 unsigned top()
const {
return size()-1; }
695 const NodeTemplate &operator[](
unsigned I)
const {
return List[
I]; }
696 unsigned reset(
unsigned NewTop) {
697 List.resize(NewTop+1);
701 using BaseType = std::vector<NodeTemplate>;
702 BaseType::iterator
begin() {
return List.begin(); }
703 BaseType::iterator
end() {
return List.end(); }
704 BaseType::const_iterator
begin()
const {
return List.begin(); }
705 BaseType::const_iterator
end()
const {
return List.end(); }
714#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
717 OpV.getNode()->print(
OS, &
G);
728 if ((OpN & Whole) != Whole) {
729 assert((OpN & Whole) == LoHalf || (OpN & Whole) == HiHalf);
743 for (
const auto &R : Ops) {
753 OS <<
"Input node:\n";
757 OS <<
"Result templates:\n";
758 for (
unsigned I = 0,
E =
List.size();
I !=
E; ++
I) {
759 OS <<
'[' <<
I <<
"] ";
772 MinSrc = (MinSrc == -1) ? M : std::min(MinSrc, M);
773 MaxSrc = (MaxSrc == -1) ? M : std::max(MaxSrc, M);
778 int MinSrc = -1, MaxSrc = -1;
780 ShuffleMask
lo()
const {
781 size_t H =
Mask.size()/2;
782 return ShuffleMask(
Mask.take_front(
H));
784 ShuffleMask
hi()
const {
785 size_t H =
Mask.size()/2;
786 return ShuffleMask(
Mask.take_back(
H));
790 OS <<
"MinSrc:" << MinSrc <<
", MaxSrc:" << MaxSrc <<
" {";
828 for (
int i = 0; i != Len; ++i) {
848 for (
int i = 0; i != Len; ++i) {
859 auto Odd =
static_cast<int>(TakeOdd);
860 for (
int i = 0, e = Len / (2 *
Size); i != e; ++i) {
861 for (
int b = 0; b !=
static_cast<int>(
Size); ++b) {
863 Vd[i *
Size + b] = Vv[(2 * i + Odd) *
Size + b];
864 Vd[i *
Size + b + Len / 2] = Vu[(2 * i + Odd) *
Size + b];
874 auto Odd =
static_cast<int>(TakeOdd);
875 for (
int i = 0, e = Len / (2 *
Size); i != e; ++i) {
876 for (
int b = 0; b !=
static_cast<int>(
Size); ++b) {
877 Vd[(2 * i + 0) *
Size + b] = Vv[(2 * i + Odd) *
Size + b];
878 Vd[(2 * i + 1) *
Size + b] = Vu[(2 * i + Odd) *
Size + b];
893 for (
int i = 0, e = Len / 4; i != e; ++i) {
894 Vd[0 * (Len / 4) + i] = Vv[4 * i + 0];
895 Vd[1 * (Len / 4) + i] = Vv[4 * i + 2];
896 Vd[2 * (Len / 4) + i] = Vu[4 * i + 0];
897 Vd[3 * (Len / 4) + i] = Vu[4 * i + 2];
902template <
typename ShuffFunc,
typename... OptArgs>
905 std::iota(Vu.begin(), Vu.end(),
Length);
907 return S(Vu, Vv,
args...);
935 assert(ElemTy != MVT::i1 &&
"Use getBoolVT for predicates");
941 assert(ElemTy != MVT::i1);
960 static std::optional<int>
rotationDistance(ShuffleMask SM,
unsigned WrapAt);
963 void select(
SDNode *ISelN);
964 void materialize(
const ResultStack &
Results);
973 OpRef concats(OpRef Va, OpRef Vb, ResultStack &
Results);
974 OpRef funnels(OpRef Va, OpRef Vb,
int Amount, ResultStack &
Results);
976 OpRef packs(ShuffleMask SM, OpRef Va, OpRef Vb, ResultStack &
Results,
978 OpRef packp(ShuffleMask SM, OpRef Va, OpRef Vb, ResultStack &
Results,
985 OpRef shuffs1(ShuffleMask SM, OpRef Va, ResultStack &
Results);
986 OpRef shuffs2(ShuffleMask SM, OpRef Va, OpRef Vb, ResultStack &
Results);
987 OpRef shuffp1(ShuffleMask SM, OpRef Va, ResultStack &
Results);
988 OpRef shuffp2(ShuffleMask SM, OpRef Va, OpRef Vb, ResultStack &
Results);
990 OpRef butterfly(ShuffleMask SM, OpRef Va, ResultStack &
Results);
991 OpRef contracting(ShuffleMask SM, OpRef Va, OpRef Vb, ResultStack &
Results);
992 OpRef expanding(ShuffleMask SM, OpRef Va, ResultStack &
Results);
993 OpRef perfect(ShuffleMask SM, OpRef Va, ResultStack &
Results);
995 bool selectVectorConstants(
SDNode *
N);
1003 unsigned VecLen = Mask.size();
1005 for (
unsigned I = 0;
I != VecLen; ++
I) {
1008 MaskL[
I] = MaskR[
I] = -1;
1009 }
else if (
unsigned(M) < VecLen) {
1014 MaskR[
I] = M-VecLen;
1021 assert(
A.size() > 0 &&
A.size() >= MaxLen);
1024 for (
unsigned I = 1;
I != MaxLen; ++
I) {
1025 if (
A[
I] -
E != Inc)
1029 return {
F, MaxLen };
1033 for (
int Idx : Mask)
1040 for (
int I = 0,
E = Mask.size();
I !=
E; ++
I) {
1042 if (M >= 0 && M !=
I)
1049 int L = Mask.size();
1052 return llvm::all_of(Mask.drop_front(L / 2), [](
int M) { return M < 0; });
1059 if (SM.MaxSrc == -1)
1062 unsigned Shift =
Log2_32(SegLen);
1065 for (
int M : SM.Mask) {
1067 Segs.
set(M >> Shift);
1086 unsigned MaskLen = SM.Mask.
size();
1087 assert(MaskLen % SegLen == 0);
1090 for (
int S = 0,
E = Map.size(); S !=
E; ++S) {
1092 for (
int I = 0;
I !=
static_cast<int>(SegLen); ++
I) {
1093 int M = SM.Mask[S*SegLen +
I];
1096 unsigned G = M / SegLen;
1099 }
else if (
Idx !=
G) {
1113 for (
int I = OutSegMap.
size() - 1;
I >= 0; --
I) {
1114 unsigned S = OutSegMap[
I];
1115 assert(S != ~0u &&
"Unexpected undef");
1116 assert(S != ~1u &&
"Unexpected multi");
1117 if (InvMap.
size() <= S)
1122 unsigned Shift =
Log2_32(SegLen);
1123 for (
int I = 0,
E = Mask.size();
I !=
E; ++
I) {
1126 int OutIdx = InvMap[M >> Shift];
1127 M = (M & (SegLen-1)) + SegLen*OutIdx;
1133bool HvxSelector::selectVectorConstants(
SDNode *
N) {
1144 for (
unsigned i = 0; i != WorkQ.
size(); ++i) {
1148 for (
unsigned j = 0, f =
W->getNumOperands(); j != f; ++j)
1149 WorkQ.
insert(
W->getOperand(j).getNode());
1155 return !Nodes.empty();
1158void HvxSelector::materialize(
const ResultStack &
Results) {
1160 dbgs() <<
"Materializing\n";
1166 std::vector<SDValue> Output;
1170 std::vector<SDValue> Ops;
1171 for (
const OpRef &R :
Node.Ops) {
1174 Ops.push_back(
R.OpV);
1177 if (
R.OpN & OpRef::Undef) {
1179 Ops.push_back(
ISel.selectUndef(dl,
MVT(SVT)));
1183 unsigned Part =
R.OpN & OpRef::Whole;
1189 MVT OpTy =
Op.getValueType().getSimpleVT();
1190 if (Part != OpRef::Whole) {
1191 assert(Part == OpRef::LoHalf || Part == OpRef::HiHalf);
1194 unsigned Sub = (Part == OpRef::LoHalf) ? Hexagon::vsub_lo
1202 SDNode *ResN = (
Node.Opc == TargetOpcode::COPY)
1203 ? Ops.front().getNode()
1205 Output.push_back(
SDValue(ResN, 0));
1208 SDNode *OutN = Output.back().getNode();
1211 dbgs() <<
"Generated node:\n";
1216 selectVectorConstants(OutN);
1220OpRef HvxSelector::concats(OpRef
Lo, OpRef
Hi, ResultStack &
Results) {
1224 getConst32(Hexagon::HvxWRRegClassID, dl),
1225 Lo, getConst32(Hexagon::vsub_lo, dl),
1226 Hi, getConst32(Hexagon::vsub_hi, dl),
1228 return OpRef::res(
Results.top());
1231OpRef HvxSelector::funnels(OpRef Va, OpRef Vb,
int Amount,
1236 auto VecLen =
static_cast<int>(
HwLen);
1240 if (Amount == VecLen)
1248 if (Amount > VecLen) {
1253 if (isUInt<3>(Amount)) {
1254 SDValue A = getConst32(Amount, dl);
1255 Results.push(Hexagon::V6_valignbi, Ty, {Vb, Va,
A});
1256 }
else if (isUInt<3>(VecLen - Amount)) {
1257 SDValue A = getConst32(VecLen - Amount, dl);
1258 Results.push(Hexagon::V6_vlalignbi, Ty, {Vb, Va,
A});
1260 SDValue A = getConst32(Amount, dl);
1261 Results.push(Hexagon::A2_tfrsi, Ty, {
A});
1262 Results.push(Hexagon::V6_valignb, Ty, {Vb, Va, OpRef::res(-1)});
1264 return OpRef::res(
Results.top());
1270OpRef HvxSelector::packs(ShuffleMask SM, OpRef Va, OpRef Vb,
1274 if (!Va.isValid() || !Vb.isValid())
1275 return OpRef::fail();
1278 std::copy(SM.Mask.begin(), SM.Mask.end(), NewMask.
begin());
1282 std::copy(SM.Mask.begin(), SM.Mask.end(), NewMask.
begin());
1289 OpRef Inp[2] = {Va, Vb};
1290 unsigned VecLen = SM.Mask.size();
1292 auto valign = [
this](OpRef
Lo, OpRef
Hi,
unsigned Amt,
MVT Ty,
1297 if (isUInt<3>(Amt) || isUInt<3>(
HwLen - Amt)) {
1298 bool IsRight = isUInt<3>(Amt);
1299 SDValue S = getConst32(IsRight ? Amt :
HwLen - Amt, dl);
1300 unsigned Opc = IsRight ? Hexagon::V6_valignbi : Hexagon::V6_vlalignbi;
1302 return OpRef::res(
Results.top());
1304 Results.push(Hexagon::A2_tfrsi, MVT::i32, {getConst32(Amt, dl)});
1305 OpRef
A = OpRef::res(
Results.top());
1307 return OpRef::res(
Results.top());
1311 unsigned SegLen =
HwLen / 2;
1317 unsigned SegCount = SegList.
size();
1320 if (SegList.
empty())
1321 return OpRef::undef(Ty);
1339 unsigned Seg0 = ~0
u, Seg1 = ~0
u;
1340 for (
int I = 0,
E = SegMap.
size();
I !=
E; ++
I) {
1341 unsigned X = SegMap[
I];
1346 else if (Seg1 != ~0u)
1348 if (
X == ~1u ||
X != Seg0)
1352 if (SegCount == 1) {
1353 unsigned SrcOp = SegList[0] / 2;
1354 for (
int I = 0;
I !=
static_cast<int>(VecLen); ++
I) {
1365 if (SegCount == 2) {
1372 if (Seg0 == ~1u || Seg1 == ~1u) {
1376 }
else if (Seg0 == ~1u) {
1377 Seg0 = SegList[0] != Seg1 ? SegList[0] : SegList[1];
1380 Seg1 = SegList[0] != Seg0 ? SegList[0] : SegList[1];
1383 assert(Seg0 != ~1u && Seg1 != ~1u);
1385 assert(Seg0 != Seg1 &&
"Expecting different segments");
1387 Results.push(Hexagon::A2_tfrsi, MVT::i32, {getConst32(SegLen, dl)});
1388 OpRef HL = OpRef::res(
Results.top());
1392 if (Seg0 / 2 == Seg1 / 2) {
1397 Results.push(Hexagon::V6_vror, Ty, {Inp[Seg0 / 2], HL});
1398 Va = OpRef::res(
Results.top());
1401 }
else if (Seg0 % 2 == Seg1 % 2) {
1405 auto Vs = (Seg0 == 0 || Seg0 == 1) ? std::make_pair(Vb, Va)
1406 : std::make_pair(Va, Vb);
1407 Results.push(Hexagon::V6_vshuffvdd,
PairTy, {Vs.first, Vs.second, HL});
1408 OpRef
P = OpRef::res(
Results.top());
1409 Va = (Seg0 == 0 || Seg0 == 2) ? OpRef::lo(
P) : OpRef::hi(
P);
1413 if ((Seg0 == 0 && Seg1 == 3) || (Seg0 == 2 && Seg1 == 1)) {
1418 OpRef Qt = OpRef::res(
Results.top());
1419 auto Vs = (Seg0 == 0) ? std::make_pair(Va, Vb)
1420 : std::make_pair(Vb, Va);
1421 Results.push(Hexagon::V6_vmux, Ty, {Qt, Vs.first, Vs.second});
1422 Va = OpRef::res(
Results.top());
1428 assert(Seg0 == 1 || Seg0 == 3);
1435 ShuffleMask SMH(MaskH);
1436 assert(SMH.Mask.size() == VecLen);
1439 if (SMH.MaxSrc - SMH.MinSrc >=
static_cast<int>(
HwLen)) {
1443 ShuffleMask SW(Swapped);
1444 if (SW.MaxSrc - SW.MinSrc <
static_cast<int>(
HwLen)) {
1445 MaskA.assign(SW.Mask.begin(), SW.Mask.end());
1449 ShuffleMask SMA(MaskA);
1450 assert(SMA.Mask.size() == VecLen);
1452 if (SMA.MaxSrc - SMA.MinSrc <
static_cast<int>(
HwLen)) {
1453 int ShiftR = SMA.MinSrc;
1454 if (ShiftR >=
static_cast<int>(
HwLen)) {
1456 Vb = OpRef::undef(Ty);
1459 OpRef RetVal = valign(Va, Vb, ShiftR, Ty,
Results);
1461 for (
int I = 0;
I !=
static_cast<int>(VecLen); ++
I) {
1462 int M = SMA.Mask[
I];
1481 for (
int I = 0;
I !=
static_cast<int>(VecLen); ++
I) {
1485 if (M >=
static_cast<int>(
HwLen))
1496 return vmuxs(MuxBytes, Va, Vb,
Results);
1498 return OpRef::fail();
1504OpRef HvxSelector::packp(ShuffleMask SM, OpRef Va, OpRef Vb,
1508 if (SegList.empty())
1509 return OpRef::undef(
getPairVT(MVT::i8));
1513 unsigned SegCount = SegList.size();
1515 return OpRef::fail();
1519 OpRef Inp[2] = { Va, Vb };
1520 OpRef Out[2] = { OpRef::undef(HalfTy), OpRef::undef(HalfTy) };
1525 for (
int I = 0,
E = SegList.size();
I !=
E; ++
I) {
1526 unsigned S = SegList[
I];
1527 OpRef
Op = Inp[S / 2];
1528 Out[
I] = (S & 1) ? OpRef::hi(
Op) : OpRef::lo(
Op);
1538 return concats(Out[0], Out[1],
Results);
1547 SDValue B = getVectorConstant(Bytes, dl);
1548 Results.push(Hexagon::V6_vd0, ByteTy, {});
1549 Results.push(Hexagon::V6_veqb, BoolTy, {OpRef(
B), OpRef::res(-1)});
1550 Results.push(Hexagon::V6_vmux, ByteTy, {OpRef::res(-1), Vb, Va});
1551 return OpRef::res(
Results.top());
1557 size_t S = Bytes.
size() / 2;
1563OpRef HvxSelector::shuffs1(ShuffleMask SM, OpRef Va, ResultStack &
Results) {
1565 unsigned VecLen = SM.Mask.size();
1568 assert(
all_of(SM.Mask, [
this](
int M) { return M == -1 || M < int(HwLen); }));
1577 OpRef Rotate = funnels(Va, Va, *Dist,
Results);
1578 if (Rotate.isValid())
1581 unsigned HalfLen =
HwLen / 2;
1586 std::pair<int, unsigned> Strip1 =
findStrip(SM.Mask, 1, HalfLen);
1587 if ((Strip1.first & ~HalfLen) == 0 && Strip1.second == HalfLen) {
1588 std::pair<int, unsigned> Strip2 =
1589 findStrip(SM.Mask.drop_front(HalfLen), 1, HalfLen);
1590 if (Strip1 == Strip2) {
1592 Results.push(Hexagon::A2_tfrsi, MVT::i32, {getConst32(HalfLen, dl)});
1594 {Va, Va, OpRef::res(
Results.top())});
1595 OpRef S = OpRef::res(
Results.top());
1596 return (Strip1.first == 0) ? OpRef::lo(S) : OpRef::
hi(S);
1600 OpRef
P = perfect(SM, Va,
Results);
1603 return butterfly(SM, Va,
Results);
1606OpRef HvxSelector::shuffs2(ShuffleMask SM, OpRef Va, OpRef Vb,
1612 OpRef
C = contracting(SM, Va, Vb,
Results);
1616 int VecLen = SM.Mask.size();
1618 OpRef
P = packs(SM, Va, Vb,
Results, PackedMask);
1620 return shuffs1(ShuffleMask(PackedMask),
P,
Results);
1628 OpRef
L = shuffs1(ShuffleMask(MaskL), Va,
Results);
1629 OpRef
R = shuffs1(ShuffleMask(MaskR), Vb,
Results);
1630 if (!
L.isValid() || !
R.isValid())
1631 return OpRef::fail();
1634 for (
int I = 0;
I != VecLen; ++
I) {
1638 return vmuxs(Bytes, L, R,
Results);
1641OpRef HvxSelector::shuffp1(ShuffleMask SM, OpRef Va, ResultStack &
Results) {
1643 int VecLen = SM.Mask.size();
1648 return OpRef::undef(
getPairVT(MVT::i8));
1651 OpRef
P = packs(SM, OpRef::lo(Va), OpRef::hi(Va),
Results, PackedMask);
1653 ShuffleMask PM(PackedMask);
1660 if (
L.isValid() &&
H.isValid())
1670 OpRef
R = perfect(SM, Va,
Results);
1676 OpRef
L = shuffs2(SM.lo(), OpRef::lo(Va), OpRef::hi(Va),
Results);
1677 OpRef
H = shuffs2(SM.hi(), OpRef::lo(Va), OpRef::hi(Va),
Results);
1678 if (
L.isValid() &&
H.isValid())
1681 return OpRef::fail();
1684OpRef HvxSelector::shuffp2(ShuffleMask SM, OpRef Va, OpRef Vb,
1688 return OpRef::undef(
getPairVT(MVT::i8));
1690 int VecLen = SM.Mask.size();
1692 OpRef
P = packp(SM, Va, Vb,
Results, PackedMask);
1694 return shuffp1(ShuffleMask(PackedMask),
P,
Results);
1699 OpRef
L = shuffp1(ShuffleMask(MaskL), Va,
Results);
1700 OpRef
R = shuffp1(ShuffleMask(MaskR), Vb,
Results);
1701 if (!
L.isValid() || !
R.isValid())
1702 return OpRef::fail();
1706 for (
int I = 0;
I != VecLen; ++
I) {
1710 return vmuxp(Bytes, L, R,
Results);
1715 template <
typename T>
1722 template <
typename T>
1723 struct NullifyingVector :
public T {
1725 NullifyingVector(
T &&V) :
T(
V) {
1726 for (
unsigned i = 0, e = T::size(); i !=
e; ++i) {
1727 SDNode *&
N = T::operator[](i);
1733 if (
F != Refs.
end())
1734 *
F->second =
nullptr;
1739void HvxSelector::select(
SDNode *ISelN) {
1767 if (SubNodes.
empty()) {
1778 auto IsDomRec = [&Dom, &NonDom] (
SDNode *
T,
auto Rec) ->
bool {
1781 if (
T->use_empty() || NonDom.
count(
T))
1795 auto IsDom = [&IsDomRec] (
SDNode *
T) {
return IsDomRec(
T, IsDomRec); };
1798 for (
unsigned I = 0;
I != SubNodes.
size(); ++
I) {
1809 std::map<SDNode *, unsigned> OpCount;
1812 return Dom.count(U.getNode());
1815 OpCount.insert({
T, NumDomOps});
1820 for (
unsigned I = 0;
I != TmpQ.
size(); ++
I) {
1825 auto F = OpCount.find(U);
1827 if (
F->second > 0 && !--
F->second)
1836 NullifyingVector<
decltype(TmpQ)::vector_type>
Queue(TmpQ.
takeVector());
1838 Deleter DUQ(
DAG, Queue);
1852 assert(ElemTy == MVT::i8);
1853 unsigned VecLen =
Mask.size();
1854 bool HavePairs = (2*
HwLen == VecLen);
1873 for (
int I : Mask) {
1902 if (2*
HwLen == VecLen) {
1928 unsigned Impossible = ~(1u << Width) + 1;
1929 for (
unsigned I = 0,
E = Bs.
size();
I !=
E; ++
I) {
1933 if (~Impossible == 0)
1935 for (
unsigned Log = 0; Log != Width; ++Log) {
1936 if (Impossible & (1u << Log))
1940 Impossible |= (1u << Log);
1948 for (
unsigned BitIdx = 0; BitIdx != Width; ++BitIdx) {
1950 for (
int i = 0, e = SM.Mask.size(); i != e; ++i) {
1953 BitValues[i] = 0xff;
1955 BitValues[i] = (M & (1u << BitIdx)) != 0;
1957 Worklist[BitIdx] = possibilities(BitValues, Width);
1999 for (
unsigned I = 0,
E = Sorted.
size();
I !=
E;) {
2000 unsigned P = Sorted[
I], Count = 1;
2001 while (++
I !=
E &&
P == Sorted[
I])
2006 for (
unsigned &Q : Worklist) {
2022 for (
unsigned I = 0;
I != Width; ++
I) {
2030 for (
unsigned J =
I + 1; J != Width; ++J) {
2040 for (
unsigned I = 0,
E = Comps.
size();
I !=
E; ++
I) {
2045 assert(OrAll == (1u << Width) -1);
2053 std::optional<int> Dist;
2054 for (
int I = 0,
E = SM.Mask.size();
I !=
E; ++
I) {
2059 if ((
I + *Dist) %
static_cast<int>(WrapAt) != M)
2060 return std::nullopt;
2067 Dist = *Dist + WrapAt;
2073OpRef HvxSelector::contracting(ShuffleMask SM, OpRef Va, OpRef Vb,
2076 if (!Va.isValid() || !Vb.isValid())
2077 return OpRef::fail();
2088 int VecLen = SM.Mask.size();
2092 OpRef Funnel = funnels(Va, Vb, *Dist,
Results);
2093 if (Funnel.isValid())
2101 return Mask1 == Mask2;
2104 using PackConfig = std::pair<unsigned, bool>;
2105 PackConfig Packs[] = {
2113 unsigned Opcodes[] = {
2114 Hexagon::V6_vpackeb,
2115 Hexagon::V6_vpackob,
2116 Hexagon::V6_vpackeh,
2117 Hexagon::V6_vpackoh,
2119 for (
int i = 0, e = std::size(Opcodes); i !=
e; ++i) {
2120 auto [
Size, Odd] = Packs[i];
2122 Results.push(Opcodes[i], SingleTy, {Vb, Va});
2123 return OpRef::res(
Results.top());
2129 unsigned Opcodes[] = {
2130 Hexagon::V6_vshuffeb,
2131 Hexagon::V6_vshuffob,
2132 Hexagon::V6_vshufeh,
2133 Hexagon::V6_vshufoh,
2135 for (
int i = 0, e = std::size(Opcodes); i !=
e; ++i) {
2136 auto [
Size, Odd] = Packs[i];
2138 Results.push(Opcodes[i], SingleTy, {Vb, Va});
2139 return OpRef::res(
Results.top());
2148 unsigned Opcodes[] = {
2149 Hexagon::V6_vpackeb,
2150 Hexagon::V6_vpackob,
2151 Hexagon::V6_vpackeh,
2152 Hexagon::V6_vpackoh,
2156 for (
int i = 0, e = std::size(Opcodes); i !=
e; ++i) {
2157 auto [
Size, Odd] = Packs[i];
2159 Results.push(Hexagon::A2_tfrsi, MVT::i32, {getConst32(-2 *
Size, dl)});
2160 Results.push(Hexagon::V6_vdealvdd,
PairTy, {Vb, Va, OpRef::res(-1)});
2162 Results.push(Opcodes[i], SingleTy,
2163 {OpRef::hi(vdeal), OpRef::lo(vdeal)});
2164 return OpRef::res(
Results.top());
2170 Results.push(Hexagon::V6_vdealb4w, SingleTy, {Vb, Va});
2171 return OpRef::res(
Results.top());
2174 return OpRef::fail();
2177OpRef HvxSelector::expanding(ShuffleMask SM, OpRef Va, ResultStack &
Results) {
2190 int VecLen = SM.Mask.size();
2191 assert(2*
HwLen ==
unsigned(VecLen) &&
"Expecting vector-pair type");
2193 std::pair<int,unsigned> Strip =
findStrip(SM.Mask, 1, VecLen);
2200 if (Strip.first != 0)
2201 return OpRef::fail();
2204 if (Strip.second != 1 && Strip.second != 2)
2205 return OpRef::fail();
2208 int L = Strip.second;
2211 for (
int I = 2*L;
I <
N;
I += 2*
L) {
2213 if (S.second !=
unsigned(L))
2214 return OpRef::fail();
2216 return OpRef::fail();
2219 for (
int I = L;
I <
N;
I += 2*
L) {
2221 if (S.first != -1 || S.second !=
unsigned(L))
2222 return OpRef::fail();
2225 unsigned Opc = Strip.second == 1 ? Hexagon::V6_vunpackub
2226 : Hexagon::V6_vunpackuh;
2228 return OpRef::res(
Results.top());
2231OpRef HvxSelector::perfect(ShuffleMask SM, OpRef Va, ResultStack &
Results) {
2240 int VecLen = SM.Mask.size();
2242 unsigned LogLen =
Log2_32(VecLen);
2246 assert(LogLen == HwLog || LogLen == HwLog + 1);
2247 bool HavePairs = LogLen == HwLog + 1;
2333 bool InvertedPair =
false;
2334 if (HavePairs && SM.Mask[0] >=
int(
HwLen)) {
2335 for (
int i = 0, e = SM.Mask.size(); i != e; ++i) {
2339 InvertedPair =
true;
2340 SM = ShuffleMask(MaskStorage);
2345 return OpRef::fail();
2348 for (
unsigned I = 0;
I != LogLen; ++
I)
2377 std::set<CycleType> Cycles;
2378 std::set<unsigned>
All;
2380 for (
unsigned I : Perm)
2385 auto canonicalize = [LogLen](
const CycleType &
C) -> CycleType {
2386 unsigned LogPos,
N =
C.size();
2387 for (LogPos = 0; LogPos !=
N; ++LogPos)
2388 if (
C[LogPos] == LogLen - 1)
2393 CycleType NewC(
C.begin() + LogPos,
C.end());
2394 NewC.append(
C.begin(),
C.begin() + LogPos);
2398 auto pfs = [](
const std::set<CycleType> &Cs,
unsigned Len) {
2403 const CycleType &
C = *Cs.begin();
2404 if (
C[0] != Len - 1)
2406 int D =
Len -
C.size();
2407 if (
D != 0 &&
D != 1)
2410 bool IsDeal =
true, IsShuff =
true;
2411 for (
unsigned I = 1;
I !=
Len -
D; ++
I) {
2412 if (
C[
I] != Len - 1 -
I)
2414 if (
C[
I] !=
I - (1 -
D))
2418 assert(!(IsDeal || IsShuff) || IsDeal != IsShuff);
2419 static unsigned Deals[] = {Hexagon::V6_vdealb, Hexagon::V6_vdealh};
2420 static unsigned Shufs[] = {Hexagon::V6_vshuffb, Hexagon::V6_vshuffh};
2421 return IsDeal ? Deals[
D] : (IsShuff ? Shufs[
D] : 0);
2424 while (!
All.empty()) {
2425 unsigned A = *
All.begin();
2429 for (
unsigned B = Perm[
A];
B !=
A;
B = Perm[
B]) {
2435 Cycles.insert(canonicalize(
C));
2442 if (
unsigned(VecLen) ==
HwLen) {
2443 if (
unsigned SingleOpc = pfs(Cycles, LogLen)) {
2444 Results.push(SingleOpc, SingleTy, {Va});
2445 return OpRef::res(
Results.top());
2468 for (
const CycleType &
C : Cycles) {
2470 unsigned First = (
C[0] == LogLen - 1) ? 1 : 0;
2479 OpRef Arg = HavePairs ? Va : concats(Va, OpRef::undef(SingleTy),
Results);
2481 Arg = concats(OpRef::hi(Arg), OpRef::lo(Arg),
Results);
2483 for (
unsigned I = 0,
E = SwapElems.
size();
I !=
E;) {
2484 bool IsInc =
I ==
E - 1 || SwapElems[
I] < SwapElems[
I + 1];
2485 unsigned S = (1u << SwapElems[
I]);
2487 while (++
I <
E - 1 && IsInc == (SwapElems[
I] < SwapElems[
I + 1]))
2488 S |= 1u << SwapElems[
I];
2491 S |= 1u << SwapElems[
I];
2496 Results.push(Hexagon::A2_tfrsi, MVT::i32, {getConst32(S, dl)});
2497 Res.Opc = IsInc ? Hexagon::V6_vshuffvdd : Hexagon::V6_vdealvdd;
2499 Res.Ops = {OpRef::hi(Arg), OpRef::lo(Arg), OpRef::res(-1)};
2501 Arg = OpRef::res(
Results.top());
2504 return HavePairs ? Arg : OpRef::lo(Arg);
2507OpRef HvxSelector::butterfly(ShuffleMask SM, OpRef Va, ResultStack &
Results) {
2520 PermNetwork::Controls
FC, RC;
2522 int VecLen = SM.Mask.size();
2524 for (
int M : SM.Mask) {
2525 if (M != -1 && M >= VecLen)
2526 return OpRef::fail();
2530 ForwardDeltaNetwork FN(SM.Mask);
2532 SDValue Ctl = getVectorConstant(FC, dl);
2533 Results.push(Hexagon::V6_vdelta, ResTy, {Va, OpRef(Ctl)});
2534 return OpRef::res(
Results.top());
2538 ReverseDeltaNetwork
RN(SM.Mask);
2540 SDValue Ctl = getVectorConstant(RC, dl);
2541 Results.push(Hexagon::V6_vrdelta, ResTy, {Va, OpRef(Ctl)});
2542 return OpRef::res(
Results.top());
2546 BenesNetwork BN(SM.Mask);
2547 if (BN.run(FC, RC)) {
2548 SDValue CtlF = getVectorConstant(FC, dl);
2549 SDValue CtlR = getVectorConstant(RC, dl);
2550 Results.push(Hexagon::V6_vdelta, ResTy, {Va, OpRef(CtlF)});
2551 Results.push(Hexagon::V6_vrdelta, ResTy,
2552 {OpRef::res(-1), OpRef(CtlR)});
2553 return OpRef::res(
Results.top());
2556 return OpRef::fail();
2559SDValue HvxSelector::getConst32(
int Val,
const SDLoc &dl) {
2566 for (uint8_t
C :
Data)
2577 MVT ResTy =
N->getValueType(0).getSimpleVT();
2578 auto IdxN = cast<ConstantSDNode>(
N->getOperand(1));
2579 unsigned Idx = IdxN->getZExtValue();
2587 unsigned SubReg =
Idx == 0 ? Hexagon::vsub_lo : Hexagon::vsub_hi;
2595 dbgs() <<
"Starting " << __func__ <<
" on node:\n";
2598 MVT ResTy =
N->getValueType(0).getSimpleVT();
2600 assert(ResTy.isVector() && ResTy.getVectorElementType() == MVT::i8);
2602 auto *SN = cast<ShuffleVectorSDNode>(
N);
2603 std::vector<int> Mask(SN->getMask().begin(), SN->getMask().end());
2605 for (
int &
Idx : Mask)
2606 if (
Idx != -1 &&
Idx < 0)
2609 unsigned VecLen = Mask.size();
2610 bool HavePairs = (2*
HwLen == VecLen);
2611 assert(ResTy.getSizeInBits() / 8 == VecLen);
2616 bool UseLeft =
false, UseRight =
false;
2617 for (
unsigned I = 0;
I != VecLen; ++
I) {
2620 unsigned Idx = Mask[
I];
2629 dbgs() <<
"VecLen=" << VecLen <<
" HwLen=" <<
HwLen <<
" UseLeft="
2630 << UseLeft <<
" UseRight=" << UseRight <<
" HavePairs="
2631 << HavePairs <<
'\n';
2634 if (!UseLeft && !UseRight) {
2644 OpRef Va = OpRef::undef(ResTy);
2645 OpRef Vb = OpRef::undef(ResTy);
2648 Results.push(TargetOpcode::COPY, ResTy, {Vec0});
2649 Va = OpRef::OpRef::res(
Results.top());
2652 Results.push(TargetOpcode::COPY, ResTy, {Vec1});
2653 Vb = OpRef::res(
Results.top());
2656 OpRef Res = !HavePairs ? shuffs2(ShuffleMask(Mask), Va, Vb,
Results)
2657 : shuffp2(ShuffleMask(Mask), Va, Vb,
Results);
2659 bool Done = Res.isValid();
2662 Results.push(TargetOpcode::COPY, ResTy, {Res});
2665 Done = scalarizeShuffle(Mask,
SDLoc(
N), ResTy, Vec0, Vec1,
N);
2670 dbgs() <<
"Unhandled shuffle:\n";
2679 MVT Ty =
N->getValueType(0).getSimpleVT();
2685 if (
auto *CN = dyn_cast<ConstantSDNode>(RotV.
getNode())) {
2689 }
else if (isUInt<3>(S)) {
2691 {VecV, VecV, getConst32(S, dl)});
2706 N->getValueType(0), {Vv, Vu, Rt});
2711void HexagonDAGToDAGISel::PreprocessHvxISelDAG() {
2712 auto getNodes = [
this]() -> std::vector<SDNode *> {
2713 std::vector<SDNode *>
T;
2720 ppHvxShuffleOfShuffle(getNodes());
2725 return std::hash<const void *>()(V.getNode()) +
2726 std::hash<unsigned>()(V.getResNo());
2730void HexagonDAGToDAGISel::ppHvxShuffleOfShuffle(std::vector<SDNode *> &&Nodes) {
2743 struct SubVectorInfo {
2744 SubVectorInfo(
SDValue S,
unsigned H) : Src(S), HalfIdx(
H) {}
2749 using MapType = std::unordered_map<SDValue, unsigned>;
2753 const MapType &OpMap) ->
int {
2769 auto N =
static_cast<unsigned>(MaybeN);
2770 unsigned SrcBase =
N < HwLen ? OpMap.at(OpShuff->
getOperand(0))
2780 auto *
This = cast<ShuffleVectorSDNode>(TopShuff);
2781 auto *S0 = cast<ShuffleVectorSDNode>(TopShuff.
getOperand(0));
2782 auto *S1 = cast<ShuffleVectorSDNode>(TopShuff.
getOperand(1));
2786 assert(TopMask.
size() == S0->getMask().size() &&
2787 TopMask.
size() == S1->getMask().size());
2791 for (
unsigned I = 0;
I != HwLen; ++
I) {
2792 int MaybeM = TopMask[
I];
2795 getMaskElt(
static_cast<unsigned>(MaybeM), S0, S1, OpMap);
2801 std::fill(FoldedMask.begin() + HwLen, FoldedMask.end(), -1);
2806 const SDLoc &dl(TopShuff);
2816 auto getSourceInfo = [](
SDValue V) -> std::optional<SubVectorInfo> {
2818 V =
V.getOperand(0);
2820 return std::nullopt;
2821 return SubVectorInfo(
V.getOperand(0),
2822 !cast<ConstantSDNode>(
V.getOperand(1))->isZero());
2828 EVT ResTy =
N->getValueType(0);
2846 if (!V0A.has_value())
2849 if (!V0B.has_value() || V0B->Src != V0A->Src)
2852 if (!V1A.has_value() || V1A->Src != V0A->Src)
2855 if (!V1B.has_value() || V1B->Src != V0A->Src)
2860 assert(V0A->Src.getValueType().getSizeInBits() == 16 * HwLen);
2873void HexagonDAGToDAGISel::SelectHvxExtractSubvector(
SDNode *
N) {
2877void HexagonDAGToDAGISel::SelectHvxShuffle(
SDNode *
N) {
2881void HexagonDAGToDAGISel::SelectHvxRor(
SDNode *
N) {
2885void HexagonDAGToDAGISel::SelectHvxVAlign(
SDNode *
N) {
2893 SDValue Predicate =
N->getOperand(3);
2895 SDValue Modifier =
N->getOperand(5);
2900 unsigned IntNo = cast<ConstantSDNode>(
N->getOperand(1))->getZExtValue();
2904 case Intrinsic::hexagon_V6_vgathermhq:
2905 case Intrinsic::hexagon_V6_vgathermhq_128B:
2906 Opcode = Hexagon::V6_vgathermhq_pseudo;
2908 case Intrinsic::hexagon_V6_vgathermwq:
2909 case Intrinsic::hexagon_V6_vgathermwq_128B:
2910 Opcode = Hexagon::V6_vgathermwq_pseudo;
2912 case Intrinsic::hexagon_V6_vgathermhwq:
2913 case Intrinsic::hexagon_V6_vgathermhwq_128B:
2914 Opcode = Hexagon::V6_vgathermhwq_pseudo;
2934 SDValue Modifier =
N->getOperand(4);
2939 unsigned IntNo = cast<ConstantSDNode>(
N->getOperand(1))->getZExtValue();
2943 case Intrinsic::hexagon_V6_vgathermh:
2944 case Intrinsic::hexagon_V6_vgathermh_128B:
2945 Opcode = Hexagon::V6_vgathermh_pseudo;
2947 case Intrinsic::hexagon_V6_vgathermw:
2948 case Intrinsic::hexagon_V6_vgathermw_128B:
2949 Opcode = Hexagon::V6_vgathermw_pseudo;
2951 case Intrinsic::hexagon_V6_vgathermhw:
2952 case Intrinsic::hexagon_V6_vgathermhw_128B:
2953 Opcode = Hexagon::V6_vgathermhw_pseudo;
2968 unsigned IID = cast<ConstantSDNode>(
N->getOperand(0))->getZExtValue();
2971 case Intrinsic::hexagon_V6_vaddcarry: {
2972 std::array<SDValue, 3> Ops = {
2973 {
N->getOperand(1),
N->getOperand(2),
N->getOperand(3)}};
2978 case Intrinsic::hexagon_V6_vaddcarry_128B: {
2979 std::array<SDValue, 3> Ops = {
2980 {
N->getOperand(1),
N->getOperand(2),
N->getOperand(3)}};
2985 case Intrinsic::hexagon_V6_vsubcarry: {
2986 std::array<SDValue, 3> Ops = {
2987 {
N->getOperand(1),
N->getOperand(2),
N->getOperand(3)}};
2992 case Intrinsic::hexagon_V6_vsubcarry_128B: {
2993 std::array<SDValue, 3> Ops = {
2994 {
N->getOperand(1),
N->getOperand(2),
N->getOperand(3)}};
ReachingDefAnalysis InstSet InstSet & Ignore
Function Alias Analysis Results
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
static void fail(const SDLoc &DL, SelectionDAG &DAG, const Twine &Msg, SDValue Val={})
This file implements the BitVector class.
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
#define LLVM_ATTRIBUTE_UNUSED
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
#define DEBUG_WITH_TYPE(TYPE, X)
DEBUG_WITH_TYPE macro - This macro should be used by passes to emit debug information.
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
const HexagonInstrInfo * TII
static bool isIdentity(ArrayRef< int > Mask)
static std::pair< int, unsigned > findStrip(ArrayRef< int > A, int Inc, unsigned MaxLen)
static bool isUndef(ArrayRef< int > Mask)
static const HexagonSubtarget & getHexagonSubtarget(SelectionDAG &G)
static void splitMask(ArrayRef< int > Mask, MutableArrayRef< int > MaskL, MutableArrayRef< int > MaskR)
static void packSegmentMask(ArrayRef< int > Mask, ArrayRef< unsigned > OutSegMap, unsigned SegLen, MutableArrayRef< int > PackedMask)
static SmallVector< unsigned, 4 > getInputSegmentList(ShuffleMask SM, unsigned SegLen)
static const HexagonTargetLowering & getHexagonLowering(SelectionDAG &G)
static SmallVector< unsigned, 4 > getOutputSegmentMap(ShuffleMask SM, unsigned SegLen)
static bool isLowHalfOnly(ArrayRef< int > Mask)
std::pair< MCSymbol *, MachineModuleInfoImpl::StubValueTy > PairTy
static bool isValid(const char C)
Returns true if C is a valid mangled character: <0-9a-zA-Z_>.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file implements a set that has insertion order iteration characteristics.
static constexpr uint32_t Opcode
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
ArrayRef< T > take_front(size_t N=1) const
Return a copy of *this with only the first N elements.
ArrayRef< T > drop_front(size_t N=1) const
Drop the first N elements of the array.
size_t size() const
size - Get the array size.
ArrayRef< T > take_back(size_t N=1) const
Return a copy of *this with only the last N elements.
iterator_range< const_set_bits_iterator > set_bits() const
This class represents an Operation in the Expression.
iterator find(const_arg_type_t< KeyT > Val)
Tagged union holding either a T or a Error.
void print(raw_ostream &OS, AssemblyAnnotationWriter *AAW=nullptr, bool ShouldPreserveUseListOrder=false, bool IsForDebug=false) const
Print the function to an output stream with an optional AssemblyAnnotationWriter.
void Select(SDNode *N) override
Main hook for targets to transform nodes into machine nodes.
void SelectV65GatherPred(SDNode *N)
friend struct HvxSelector
void SelectV65Gather(SDNode *N)
void SelectHVXDualOutput(SDNode *N)
unsigned getVectorLength() const
SDValue LowerOperation(SDValue Op, SelectionDAG &DAG) const override
This callback is invoked for operations that are unsupported by the target, which are registered to u...
This is an important class for using LLVM in a threaded context.
unsigned getVectorNumElements() const
TypeSize getSizeInBits() const
Returns the size of the specified MVT in bits.
static MVT getVectorVT(MVT VT, unsigned NumElements)
MVT getVectorElementType() const
A description of a memory reference used in the backend.
MutableArrayRef - Represent a mutable reference to an array (0 or more elements consecutively in memo...
MutableArrayRef< T > take_back(size_t N=1) const
Return a copy of *this with only the last N elements.
MutableArrayRef< T > take_front(size_t N=1) const
Return a copy of *this with only the first N elements.
A NodeSet contains a set of SUnit DAG nodes with additional information that assigns a priority to th...
Pass interface - Implemented by all 'passes'.
Wrapper class for IR location info (IR ordering and DebugLoc) to be passed into SDNode creation funct...
Represents one node in the SelectionDAG.
bool isMachineOpcode() const
Test if this node has a post-isel opcode, directly corresponding to a MachineInstr opcode.
void dump() const
Dump this node, for debugging.
unsigned getOpcode() const
Return the SelectionDAG opcode value for this node.
iterator_range< use_iterator > uses()
void dumpr() const
Dump (recursively) this node and its use-def subgraph.
const SDValue & getOperand(unsigned Num) const
Represents a use of a SDNode.
Unlike LLVM values, Selection DAG nodes may return multiple values as the result of a computation.
SDNode * getNode() const
get the SDNode which holds the desired result
EVT getValueType() const
Return the ValueType of the referenced return value.
const SDValue & getOperand(unsigned i) const
unsigned getOpcode() const
void ReplaceUses(SDValue F, SDValue T)
ReplaceUses - replace all uses of the old node F with the use of the new node T.
void ReplaceNode(SDNode *F, SDNode *T)
Replace all uses of F with T, then remove F from the DAG.
This is used to represent a portion of an LLVM function in a low-level Data Dependence DAG representa...
SDVTList getVTList(EVT VT)
Return an SDVTList that represents the list of values specified.
MachineSDNode * getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT)
These are used for target selectors to create a new node with specified return type(s),...
SDValue getUNDEF(EVT VT)
Return an UNDEF node. UNDEF does not have a useful SDLoc.
SDValue getBuildVector(EVT VT, const SDLoc &DL, ArrayRef< SDValue > Ops)
Return an ISD::BUILD_VECTOR node.
SDValue getBitcast(EVT VT, SDValue V)
Return a bitcast using the SDLoc of the value operand, and casting to the provided type.
void setNodeMemRefs(MachineSDNode *N, ArrayRef< MachineMemOperand * > NewMemRefs)
Mutate the specified machine node's memory references to the provided list.
SDValue getConstant(uint64_t Val, const SDLoc &DL, EVT VT, bool isTarget=false, bool isOpaque=false)
Create a ConstantSDNode wrapping a constant value.
void RemoveDeadNodes()
This method deletes all unreachable nodes in the SelectionDAG.
void RemoveDeadNode(SDNode *N)
Remove the specified node from the system.
SDValue getTargetExtractSubreg(int SRIdx, const SDLoc &DL, EVT VT, SDValue Operand)
A convenience function for creating TargetInstrInfo::EXTRACT_SUBREG nodes.
iterator_range< allnodes_iterator > allnodes()
SDValue getNode(unsigned Opcode, const SDLoc &DL, EVT VT, ArrayRef< SDUse > Ops)
Gets or creates the specified node.
ilist< SDNode >::size_type allnodes_size() const
SDValue getTargetConstant(uint64_t Val, const SDLoc &DL, EVT VT, bool isOpaque=false)
LLVMContext * getContext() const
SDValue getVectorShuffle(EVT VT, const SDLoc &dl, SDValue N1, SDValue N2, ArrayRef< int > Mask)
Return an ISD::VECTOR_SHUFFLE node.
A vector that has set insertion semantics.
size_type size() const
Determine the number of elements in the SetVector.
Vector takeVector()
Clear the SetVector and return the underlying vector.
size_type count(const key_type &key) const
Count the number of elements of a given key in the SetVector.
bool empty() const
Determine if the SetVector is empty or not.
bool insert(const value_type &X)
Insert a new element into the SetVector.
This SDNode is used to implement the code generator support for the llvm IR shufflevector instruction...
int getMaskElt(unsigned Idx) const
static void commuteMask(MutableArrayRef< int > Mask)
Change values in a shuffle permute mask assuming the two vector operands have swapped position.
void append(ItTy in_start, ItTy in_end)
Add the specified range to the end of the SmallVector.
void push_back(const T &Elt)
pointer data()
Return a pointer to the vector's buffer, even if empty().
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
TargetInstrInfo - Interface to description of machine instruction set.
virtual EVT getTypeToTransformTo(LLVMContext &Context, EVT VT) const
For types supported by the target, this is an identity function.
This class implements an extremely fast bulk output stream that can only output to a stream.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
constexpr std::underlying_type_t< E > Mask()
Get a bitmask with 1s in all places up to the high-order bit of E's largest value.
@ C
The default llvm calling convention, compatible with C.
@ CONCAT_VECTORS
CONCAT_VECTORS(VECTOR0, VECTOR1, ...) - Given a number of values of vector type with the same length ...
@ BITCAST
BITCAST - This operator converts between integer, vector and FP values, as if the value was stored to...
@ VECTOR_SHUFFLE
VECTOR_SHUFFLE(VEC1, VEC2) - Returns a vector, of the same type as VEC1/VEC2.
@ EXTRACT_SUBVECTOR
EXTRACT_SUBVECTOR(VECTOR, IDX) - Returns a subvector from VECTOR.
@ EXTRACT_VECTOR_ELT
EXTRACT_VECTOR_ELT(VECTOR, IDX) - Returns a single element from VECTOR identified by the (potentially...
@ Invalid
Invalid file type.
@ Undef
Value of the register doesn't matter.
@ Switch
The "resume-switch" lowering, where there are separate resume and destroy functions that are shared b...
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
const_iterator end(StringRef path)
Get end iterator over path.
This is an optimization pass for GlobalISel generic memory operations.
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
int popcount(T Value) noexcept
Count the number of set bits in a value.
auto size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)
Get the size of a range.
SmallVectorImpl< T >::const_pointer c_str(SmallVectorImpl< T > &str)
void erase(Container &C, ValueType V)
Wrapper function to remove a value from a container:
unsigned Log2_32(uint32_t Value)
Return the floor log base 2 of the specified value, -1 if the value is zero.
auto reverse(ContainerTy &&C)
constexpr bool isPowerOf2_32(uint32_t Value)
Return true if the argument is a power of two > 0.
void sort(IteratorTy Start, IteratorTy End)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
format_object< Ts... > format(const char *Fmt, const Ts &... Vals)
These are helper functions used to produce formatted output.
@ First
Helpers to iterate all locations in the MemoryEffectsBase class.
uint64_t alignTo(uint64_t Size, Align A)
Returns a multiple of A needed to store Size bytes.
@ Invalid
Denotes invalid value.
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
constexpr int32_t SignExtend32(uint32_t X)
Sign-extend the number in the bottom B bits of X to a 32-bit integer.
auto count_if(R &&Range, UnaryPredicate P)
Wrapper function around std::count_if to count the number of times an element satisfying a given pred...
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
MaskT vshuffvdd(ArrayRef< int > Vu, ArrayRef< int > Vv, unsigned Rt)
MaskT vpack(ArrayRef< int > Vu, ArrayRef< int > Vv, unsigned Size, bool TakeOdd)
ArrayRef< int > hi(ArrayRef< int > Vuu)
auto mask(ShuffFunc S, unsigned Length, OptArgs... args) -> MaskT
MaskT vshuff(ArrayRef< int > Vu, ArrayRef< int > Vv, unsigned Size, bool TakeOdd)
MaskT vdealb4w(ArrayRef< int > Vu, ArrayRef< int > Vv)
MaskT vdeal(ArrayRef< int > Vu, ArrayRef< int > Vv, unsigned Size, bool TakeOdd)
ArrayRef< int > lo(ArrayRef< int > Vuu)
MaskT vdealvdd(ArrayRef< int > Vu, ArrayRef< int > Vv, unsigned Rt)
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
MVT getSimpleVT() const
Return the SimpleValueType held in the specified simple EVT.
EVT getVectorElementType() const
Given a vector type, return the type of each element.
unsigned getVectorNumElements() const
Given a vector type, return the number of elements it contains.
HvxSelector(HexagonDAGToDAGISel &HS, SelectionDAG &G)
MVT getSingleVT(MVT ElemTy) const
static SmallVector< uint32_t, 8 > completeToPerfect(ArrayRef< uint32_t > Completions, unsigned Width)
HexagonDAGToDAGISel & ISel
const HexagonTargetLowering & Lower
void selectVAlign(SDNode *N)
void selectExtractSubvector(SDNode *N)
void selectRor(SDNode *N)
void selectShuffle(SDNode *N)
static SmallVector< uint32_t, 8 > getPerfectCompletions(ShuffleMask SM, unsigned Width)
MVT getPairVT(MVT ElemTy) const
const HexagonSubtarget & HST
static std::optional< int > rotationDistance(ShuffleMask SM, unsigned WrapAt)
This represents a list of ValueType's that has been intern'd by a SelectionDAG.
std::size_t operator()(SDValue V) const