HexagonISelDAGToDAGHVX.cpp Source File (original) (raw)

15#include "llvm/IR/IntrinsicsHexagon.h"

19#include

20#include

21#include

22#include

23#include

24#include

25#include

26#include <unordered_map>

27#include

28#include

30#define DEBUG_TYPE "hexagon-isel"

31using namespace llvm;

33namespace {

100enum class ColorKind { None, Red, Black };

101

102

103

104struct Coloring {

105 using Node = int;

106 using MapType = std::map<Node, ColorKind>;

108

110 build();

111 if (!color())

112 Colors.clear();

113 }

114

115 const MapType &colors() const {

116 return Colors;

117 }

118

119 ColorKind other(ColorKind Color) {

120 if (Color == ColorKind::None)

121 return ColorKind::Red;

122 return Color == ColorKind::Red ? ColorKind::Black : ColorKind::Red;

123 }

124

126

127private:

129 MapType Colors;

130 std::set Needed;

131

132 using NodeSet = std::set;

133 std::map<Node,NodeSet> Edges;

134

137 return (Pos < Num/2) ? Pos + Num/2 : Pos - Num/2;

138 }

139

140 ColorKind getColor(Node N) {

141 auto F = Colors.find(N);

142 return F != Colors.end() ? F->second : ColorKind::None;

143 }

144

145 std::pair<bool, ColorKind> getUniqueColor(const NodeSet &Nodes);

146

147 void build();

148 bool color();

149};

150}

151

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

153 auto Color = ColorKind::None;

154 for (Node N : Nodes) {

155 ColorKind ColorN = getColor(N);

156 if (ColorN == ColorKind::None)

157 continue;

158 if (Color == ColorKind::None)

159 Color = ColorN;

160 else if (Color != ColorKind::None && Color != ColorN)

161 return { false, ColorKind::None };

162 }

163 return { true, Color };

164}

165

166void Coloring::build() {

167

168 for (unsigned P = 0; P != Order.size(); ++P) {

169 Node I = Order[P];

171 Needed.insert(I);

172 Node PC = Order[conj(P)];

173 if (PC != Ignore && PC != I)

174 Edges[I].insert(PC);

175 }

176 }

177

178 for (unsigned I = 0; I != Order.size(); ++I) {

179 if (!Needed.count(I))

180 continue;

181 Node C = conj(I);

182

183

184

185 NodeSet &Is = Edges[I];

186 if (Needed.count(C))

188 }

189}

190

191bool Coloring::color() {

192 SetVector FirstQ;

193 auto Enqueue = [this,&FirstQ] (Node N) {

194 SetVector Q;

196 for (unsigned I = 0; I != Q.size(); ++I) {

197 NodeSet &Ns = Edges[Q[I]];

198 Q.insert_range(Ns);

199 }

201 };

202 for (Node N : Needed)

203 Enqueue(N);

204

205 for (Node N : FirstQ) {

206 if (Colors.count(N))

207 continue;

208 NodeSet &Ns = Edges[N];

209 auto P = getUniqueColor(Ns);

210 if (.first)

211 return false;

212 Colors[N] = other(P.second);

213 }

214

215

216 for (auto E : Edges) {

217 Node N = E.first;

218 if (!Needed.count(conj(N)) || Colors.count(N))

219 continue;

220 auto P = getUniqueColor(E.second);

221 if (.first)

222 return false;

223 Colors[N] = other(P.second);

224 }

225

226

227

228 std::vector WorkQ;

229 for (auto E : Edges) {

230 Node N = E.first;

231 if (!Colors.count(N))

232 WorkQ.push_back(N);

233 }

234

235 for (Node N : WorkQ) {

236 NodeSet &Ns = Edges[N];

237 auto P = getUniqueColor(Ns);

238 if (P.first) {

239 Colors[N] = other(P.second);

240 continue;

241 }

242

243

244 Node C = conj(N);

245 ColorKind ColorN = other(ColorKind::None);

246 ColorKind ColorC = other(ColorN);

247 NodeSet &Cs = Edges[C];

248 NodeSet CopyNs = Ns;

249 for (Node M : CopyNs) {

250 ColorKind ColorM = getColor(M);

251 if (ColorM == ColorC) {

252

254 Edges[M].insert(C);

255 Ns.erase(M);

256 Edges[M].erase(N);

257 }

258 }

259 Colors[N] = ColorN;

260 Colors[C] = ColorC;

261 }

262

263

264 for (unsigned I = 0; I != Order.size(); ++I)

265 Colors.try_emplace(I, ColorKind::None);

266

267 return true;

268}

269

270#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)

271void Coloring::dump() const {

272 dbgs() << "{ Order: {";

273 for (Node P : Order) {

275 dbgs() << ' ' << P;

276 else

277 dbgs() << " -";

278 }

279 dbgs() << " }\n";

280 dbgs() << " Needed: {";

281 for (Node N : Needed)

282 dbgs() << ' ' << N;

283 dbgs() << " }\n";

284

285 dbgs() << " Edges: {\n";

286 for (auto E : Edges) {

287 dbgs() << " " << E.first << " -> {";

288 for (auto N : E.second)

289 dbgs() << ' ' << N;

290 dbgs() << " }\n";

291 }

292 dbgs() << " }\n";

293

294 auto ColorKindToName = [](ColorKind C) {

295 switch (C) {

296 case ColorKind::None:

297 return "None";

298 case ColorKind::Red:

299 return "Red";

300 case ColorKind::Black:

301 return "Black";

302 }

303 llvm_unreachable("all ColorKinds should be handled by the switch above");

304 };

305

306 dbgs() << " Colors: {\n";

307 for (auto C : Colors)

308 dbgs() << " " << C.first << " -> " << ColorKindToName(C.second) << "\n";

309 dbgs() << " }\n}\n";

310}

311#endif

312

313namespace {

314

315

316

317struct PermNetwork {

318 using Controls = std::vector<uint8_t>;

319 using ElemType = int;

320 static constexpr ElemType Ignore = ElemType(-1);

321

322 enum : uint8_t {

325 Switch

326 };

327 enum : uint8_t {

328 Forward,

330 };

331

333 Order.assign(Ord.data(), Ord.data()+Ord.size());

334 Log = 0;

335

336 unsigned S = Order.size();

337 while (S >>= 1)

338 ++Log;

339

340 Table.resize(Order.size());

341 for (RowType &Row : Table)

342 Row.resize(Mult*Log, None);

343 }

344

345 void getControls(Controls &V, unsigned StartAt, uint8_t Dir) const {

346 unsigned Size = Order.size();

348 for (unsigned I = 0; I != Size; ++I) {

349 unsigned W = 0;

350 for (unsigned L = 0; L != Log; ++L) {

351 unsigned C = ctl(I, StartAt+L) == Switch;

352 if (Dir == Forward)

353 W |= C << (Log-1-L);

354 else

355 W |= C << L;

356 }

358 V[I] = uint8_t(W);

359 }

360 }

361

362 uint8_t ctl(ElemType Pos, unsigned Step) const {

363 return Table[Pos][Step];

364 }

365 unsigned size() const {

366 return Order.size();

367 }

368 unsigned steps() const {

369 return Log;

370 }

371

372protected:

373 unsigned Log;

374 std::vector Order;

375 using RowType = std::vector<uint8_t>;

376 std::vector Table;

377};

378

379struct ForwardDeltaNetwork : public PermNetwork {

381

382 bool run(Controls &V) {

383 if (!route(Order.data(), Table.data(), size(), 0))

384 return false;

385 getControls(V, 0, Forward);

386 return true;

387 }

388

389private:

390 bool route(ElemType *P, RowType *T, unsigned Size, unsigned Step);

391};

392

393struct ReverseDeltaNetwork : public PermNetwork {

395

396 bool run(Controls &V) {

397 if (!route(Order.data(), Table.data(), size(), 0))

398 return false;

399 getControls(V, 0, Reverse);

400 return true;

401 }

402

403private:

404 bool route(ElemType *P, RowType *T, unsigned Size, unsigned Step);

405};

406

407struct BenesNetwork : public PermNetwork {

409

410 bool run(Controls &F, Controls &R) {

411 if (!route(Order.data(), Table.data(), size(), 0))

412 return false;

413

414 getControls(F, 0, Forward);

415 getControls(R, Log, Reverse);

416 return true;

417 }

418

419private:

420 bool route(ElemType *P, RowType *T, unsigned Size, unsigned Step);

421};

422}

423

424bool ForwardDeltaNetwork::route(ElemType *P, RowType *T, unsigned Size,

425 unsigned Step) {

426 bool UseUp = false, UseDown = false;

427 ElemType Num = Size;

428

429

430

431

432

433 for (ElemType J = 0; J != Num; ++J) {

434 ElemType I = P[J];

435

436

438 continue;

439 uint8_t S;

440 if (I < Num/2)

442 else

443 S = (J < Num/2) ? Switch : Pass;

444

445

446 ElemType U = (S == Pass) ? I : (I < Num/2 ? I+Num/2 : I-Num/2);

447 if (U < Num/2)

448 UseUp = true;

449 else

450 UseDown = true;

451 if (T[U][Step] != S && T[U][Step] != None)

452 return false;

453 T[U][Step] = S;

454 }

455

456 for (ElemType J = 0; J != Num; ++J)

457 if (P[J] != Ignore && P[J] >= Num/2)

458 P[J] -= Num/2;

459

460 if (Step+1 < Log) {

461 if (UseUp && !route(P, T, Size/2, Step+1))

462 return false;

463 if (UseDown && !route(P+Size/2, T+Size/2, Size/2, Step+1))

464 return false;

465 }

466 return true;

467}

468

469bool ReverseDeltaNetwork::route(ElemType *P, RowType *T, unsigned Size,

470 unsigned Step) {

471 unsigned Pets = Log-1 - Step;

472 bool UseUp = false, UseDown = false;

473 ElemType Num = Size;

474

475

477 const Coloring::MapType &M = G.colors();

478 if (M.empty())

479 return false;

480

481 ColorKind ColorUp = ColorKind::None;

482 for (ElemType J = 0; J != Num; ++J) {

483 ElemType I = P[J];

484

485

487 continue;

488 ColorKind C = M.at(I);

489 if (C == ColorKind::None)

490 continue;

491

492

493

494 bool InpUp = I < Num/2;

495 if (ColorUp == ColorKind::None)

496 ColorUp = InpUp ? C : G.other(C);

497 if ((C == ColorUp) != InpUp) {

498

499 return false;

500 }

501

502 uint8_t S;

503 if (InpUp) {

505 UseUp = true;

506 } else {

507 S = (J < Num/2) ? Switch : Pass;

508 UseDown = true;

509 }

510 T[J][Pets] = S;

511 }

512

513

514

515 for (ElemType J = 0, E = Size / 2; J != E; ++J) {

516 ElemType PJ = P[J];

517 ElemType PC = P[J+Size/2];

518 ElemType QJ = PJ;

519 ElemType QC = PC;

520 if (T[J][Pets] == Switch)

521 QC = PJ;

522 if (T[J+Size/2][Pets] == Switch)

523 QJ = PC;

524 P[J] = QJ;

525 P[J+Size/2] = QC;

526 }

527

528 for (ElemType J = 0; J != Num; ++J)

529 if (P[J] != Ignore && P[J] >= Num/2)

530 P[J] -= Num/2;

531

532 if (Step+1 < Log) {

533 if (UseUp && !route(P, T, Size/2, Step+1))

534 return false;

535 if (UseDown && !route(P+Size/2, T+Size/2, Size/2, Step+1))

536 return false;

537 }

538 return true;

539}

540

541bool BenesNetwork::route(ElemType *P, RowType *T, unsigned Size,

542 unsigned Step) {

544 const Coloring::MapType &M = G.colors();

545 if (M.empty())

546 return false;

547 ElemType Num = Size;

548

549 unsigned Pets = 2*Log-1 - Step;

550 bool UseUp = false, UseDown = false;

551

552

553

554

555 ColorKind ColorUp = ColorKind::None;

556 for (ElemType J = 0; J != Num; ++J) {

557 ElemType I = P[J];

559 continue;

560 ColorKind C = M.at(I);

561 if (C == ColorKind::None)

562 continue;

563 if (ColorUp == ColorKind::None) {

564 ColorUp = (I < Num / 2) ? ColorKind::Red : ColorKind::Black;

565 }

566 unsigned CI = (I < Num/2) ? I+Num/2 : I-Num/2;

567 if (C == ColorUp) {

568 if (I < Num/2)

570 else

572 T[J][Pets] = (J < Num/2) ? Pass : Switch;

573 UseUp = true;

574 } else {

575 if (I < Num/2)

577 else

579 T[J][Pets] = (J < Num/2) ? Switch : Pass;

580 UseDown = true;

581 }

582 }

583

584

585

586 for (ElemType J = 0; J != Num/2; ++J) {

587 ElemType PJ = P[J];

588 ElemType PC = P[J+Num/2];

589 ElemType QJ = PJ;

590 ElemType QC = PC;

591 if (T[J][Pets] == Switch)

592 QC = PJ;

593 if (T[J+Num/2][Pets] == Switch)

594 QJ = PC;

595 P[J] = QJ;

596 P[J+Num/2] = QC;

597 }

598

599 for (ElemType J = 0; J != Num; ++J)

600 if (P[J] != Ignore && P[J] >= Num/2)

601 P[J] -= Num/2;

602

603 if (Step+1 < Log) {

604 if (UseUp && !route(P, T, Size/2, Step+1))

605 return false;

606 if (UseDown && !route(P+Size/2, T+Size/2, Size/2, Step+1))

607 return false;

608 }

609 return true;

610}

611

612

613

614

615

616namespace {

617struct OpRef {

619 bool isValue() const { return OpV.getNode() != nullptr; }

620 bool isValid() const { return isValue() || !(OpN & Invalid); }

621 bool isUndef() const { return OpN & Undef; }

622 static OpRef res(int N) { return OpRef(Whole | (N & Index)); }

623 static OpRef fail() { return OpRef(Invalid); }

624

625 static OpRef lo(const OpRef &R) {

627 return OpRef(R.OpN & (Undef | Index | LoHalf));

628 }

629 static OpRef hi(const OpRef &R) {

631 return OpRef(R.OpN & (Undef | Index | HiHalf));

632 }

633 static OpRef undef(MVT Ty) { return OpRef(Undef | Ty.SimpleTy); }

634

635

637

638

639

640

641

642

643 unsigned OpN = 0;

644

645 enum : unsigned {

647 LoHalf = 0x20000000,

648 HiHalf = 0x40000000,

649 Whole = LoHalf | HiHalf,

650 Undef = 0x80000000,

651 Index = 0x0FFFFFFF,

652 IndexBits = 28,

653 };

654

656 void print(raw_ostream &OS, const SelectionDAG &G) const;

657

658private:

659 OpRef(unsigned N) : OpN(N) {}

660};

661

662struct NodeTemplate {

663 NodeTemplate() = default;

664 unsigned Opc = 0;

665 MVT Ty = MVT::Other;

666 std::vector Ops;

667

669};

670

671struct ResultStack {

672 ResultStack(SDNode *Inp)

674 SDNode *InpNode;

675 MVT InpTy;

676 unsigned push(const NodeTemplate &Res) {

677 List.push_back(Res);

678 return List.size()-1;

679 }

680 unsigned push(unsigned Opc, MVT Ty, std::vector &&Ops) {

681 NodeTemplate Res;

682 Res.Opc = Opc;

683 Res.Ty = Ty;

684 Res.Ops = Ops;

685 return push(Res);

686 }

687 bool empty() const { return List.empty(); }

688 unsigned size() const { return List.size(); }

689 unsigned top() const { return size()-1; }

690 const NodeTemplate &operator[](unsigned I) const { return List[I]; }

691 unsigned reset(unsigned NewTop) {

692 List.resize(NewTop+1);

693 return NewTop;

694 }

695

696 using BaseType = std::vector;

697 BaseType::iterator begin() { return List.begin(); }

698 BaseType::iterator end() { return List.end(); }

699 BaseType::const_iterator begin() const { return List.begin(); }

700 BaseType::const_iterator end() const { return List.end(); }

701

703

705 void print(raw_ostream &OS, const SelectionDAG &G) const;

706};

707}

708

709#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)

710void OpRef::print(raw_ostream &OS, const SelectionDAG &G) const {

711 if (isValue()) {

713 return;

714 }

716 OS << "invalid";

717 return;

718 }

719 if (OpN & Undef) {

720 OS << "undef";

721 return;

722 }

723 if ((OpN & Whole) != Whole) {

724 assert((OpN & Whole) == LoHalf || (OpN & Whole) == HiHalf);

725 if (OpN & LoHalf)

726 OS << "lo ";

727 else

728 OS << "hi ";

729 }

730 OS << '#' << SignExtend32(OpN & Index, IndexBits);

731}

732

733void NodeTemplate::print(raw_ostream &OS, const SelectionDAG &G) const {

734 const TargetInstrInfo &TII = *G.getSubtarget().getInstrInfo();

735 OS << format("%8s", EVT(Ty).getEVTString().c_str()) << " "

737 bool Comma = false;

738 for (const auto &R : Ops) {

739 if (Comma)

740 OS << ',';

742 OS << ' ';

743 R.print(OS, G);

744 }

745}

746

747void ResultStack::print(raw_ostream &OS, const SelectionDAG &G) const {

748 OS << "Input node:\n";

749#ifndef NDEBUG

751#endif

752 OS << "Result templates:\n";

753 for (unsigned I = 0, E = List.size(); I != E; ++I) {

754 OS << '[' << I << "] ";

755 List[I].print(OS, G);

756 OS << '\n';

757 }

758}

759#endif

760

761namespace {

762struct ShuffleMask {

763 ShuffleMask(ArrayRef M) : Mask(M) {

764 for (int M : Mask) {

765 if (M == -1)

766 continue;

767 MinSrc = (MinSrc == -1) ? M : std::min(MinSrc, M);

768 MaxSrc = (MaxSrc == -1) ? M : std::max(MaxSrc, M);

769 }

770 }

771

772 ArrayRef Mask;

773 int MinSrc = -1, MaxSrc = -1;

774

775 ShuffleMask lo() const {

776 size_t H = Mask.size()/2;

777 return ShuffleMask(Mask.take_front(H));

778 }

779 ShuffleMask hi() const {

780 size_t H = Mask.size()/2;

781 return ShuffleMask(Mask.take_back(H));

782 }

783

784 void print(raw_ostream &OS) const {

785 OS << "MinSrc:" << MinSrc << ", MaxSrc:" << MaxSrc << " {";

786 for (int M : Mask)

787 OS << ' ' << M;

788 OS << " }";

789 }

790};

791

792[[maybe_unused]]

793raw_ostream &operator<<(raw_ostream &OS, const ShuffleMask &SM) {

794 SM.print(OS);

795 return OS;

796}

797}

798

801

802

803

804

805

806

807

810

812 int Len = Vu.size();

813 MaskT Vdd(2 * Len);

816

819

821 if ((Rt & Offset) == 0)

822 continue;

823 for (int i = 0; i != Len; ++i) {

824 if ((i & Offset) == 0)

826 }

827 }

828 return Vdd;

829}

830

832 int Len = Vu.size();

833 MaskT Vdd(2 * Len);

836

839

841 if ((Rt & Offset) == 0)

842 continue;

843 for (int i = 0; i != Len; ++i) {

844 if ((i & Offset) == 0)

846 }

847 }

848 return Vdd;

849}

850

852 int Len = Vu.size();

854 auto Odd = static_cast<int>(TakeOdd);

855 for (int i = 0, e = Len / (2 * Size); i != e; ++i) {

856 for (int b = 0; b != static_cast<int>(Size); ++b) {

857

858 Vd[i * Size + b] = Vv[(2 * i + Odd) * Size + b];

859 Vd[i * Size + b + Len / 2] = Vu[(2 * i + Odd) * Size + b];

860

861 }

862 }

863 return Vd;

864}

865

867 int Len = Vu.size();

869 auto Odd = static_cast<int>(TakeOdd);

870 for (int i = 0, e = Len / (2 * Size); i != e; ++i) {

871 for (int b = 0; b != static_cast<int>(Size); ++b) {

872 Vd[(2 * i + 0) * Size + b] = Vv[(2 * i + Odd) * Size + b];

873 Vd[(2 * i + 1) * Size + b] = Vu[(2 * i + Odd) * Size + b];

874 }

875 }

876 return Vd;

877}

878

880 int Len = Vu.size();

883}

884

886 int Len = Vu.size();

888 for (int i = 0, e = Len / 4; i != e; ++i) {

889 Vd[0 * (Len / 4) + i] = Vv[4 * i + 0];

890 Vd[1 * (Len / 4) + i] = Vv[4 * i + 2];

891 Vd[2 * (Len / 4) + i] = Vu[4 * i + 0];

892 Vd[3 * (Len / 4) + i] = Vu[4 * i + 2];

893 }

894 return Vd;

895}

896

897template <typename ShuffFunc, typename... OptArgs>

900 std::iota(Vu.begin(), Vu.end(), Length);

901 std::iota(Vv.begin(), Vv.end(), 0);

902 return S(Vu, Vv, args...);

903}

904

905}

906

907

908

909

916

917namespace llvm {

924

928

930 assert(ElemTy != MVT::i1 && "Use getBoolVT for predicates");

931 unsigned NumElems = HwLen / (ElemTy.getSizeInBits() / 8);

933 }

934

936 assert(ElemTy != MVT::i1);

937 unsigned NumElems = (2 * HwLen) / (ElemTy.getSizeInBits() / 8);

939 }

940

945

946 void selectExtractSubvector(SDNode *N);

947 void selectShuffle(SDNode *N);

948 void selectRor(SDNode *N);

949 void selectVAlign(SDNode *N);

950

952 unsigned Width);

955 static std::optional rotationDistance(ShuffleMask SM, unsigned WrapAt);

956

957 private:

958 void select(SDNode *ISelN);

959 void materialize(const ResultStack &Results);

960

961 SDValue getConst32(unsigned Val, const SDLoc &dl);

962 SDValue getSignedConst32(int Val, const SDLoc &dl);

964

965 enum : unsigned {

967 PackMux,

968 };

969 OpRef concats(OpRef Va, OpRef Vb, ResultStack &Results);

970 OpRef funnels(OpRef Va, OpRef Vb, int Amount, ResultStack &Results);

971

972 OpRef packs(ShuffleMask SM, OpRef Va, OpRef Vb, ResultStack &Results,

974 OpRef packp(ShuffleMask SM, OpRef Va, OpRef Vb, ResultStack &Results,

980

981 OpRef shuffs1(ShuffleMask SM, OpRef Va, ResultStack &Results);

982 OpRef shuffs2(ShuffleMask SM, OpRef Va, OpRef Vb, ResultStack &Results);

983 OpRef shuffp1(ShuffleMask SM, OpRef Va, ResultStack &Results);

984 OpRef shuffp2(ShuffleMask SM, OpRef Va, OpRef Vb, ResultStack &Results);

985

986 OpRef butterfly(ShuffleMask SM, OpRef Va, ResultStack &Results);

987 OpRef contracting(ShuffleMask SM, OpRef Va, OpRef Vb, ResultStack &Results);

988 OpRef expanding(ShuffleMask SM, OpRef Va, ResultStack &Results);

989 OpRef perfect(ShuffleMask SM, OpRef Va, ResultStack &Results);

990

991 bool selectVectorConstants(SDNode *N);

994 };

995}

996

999 unsigned VecLen = Mask.size();

1000 assert(MaskL.size() == VecLen && MaskR.size() == VecLen);

1001 for (unsigned I = 0; I != VecLen; ++I) {

1002 int M = Mask[I];

1003 if (M < 0) {

1004 MaskL[I] = MaskR[I] = -1;

1005 } else if (unsigned(M) < VecLen) {

1006 MaskL[I] = M;

1007 MaskR[I] = -1;

1008 } else {

1009 MaskL[I] = -1;

1010 MaskR[I] = M-VecLen;

1011 }

1012 }

1013}

1014

1016 unsigned MaxLen) {

1017 assert(A.size() > 0 && A.size() >= MaxLen);

1018 int F = A[0];

1019 int E = F;

1020 for (unsigned I = 1; I != MaxLen; ++I) {

1021 if (A[I] - E != Inc)

1022 return { F, I };

1023 E = A[I];

1024 }

1025 return { F, MaxLen };

1026}

1027

1029 for (int Idx : Mask)

1030 if (Idx != -1)

1031 return false;

1032 return true;

1033}

1034

1036 for (int I = 0, E = Mask.size(); I != E; ++I) {

1037 int M = Mask[I];

1038 if (M >= 0 && M != I)

1039 return false;

1040 }

1041 return true;

1042}

1043

1045 int L = Mask.size();

1047

1048 return llvm::all_of(Mask.drop_front(L / 2), [](int M) { return M < 0; });

1049}

1050

1052 unsigned SegLen) {

1055 if (SM.MaxSrc == -1)

1056 return SegList;

1057

1058 unsigned Shift = Log2_32(SegLen);

1060

1061 for (int M : SM.Mask) {

1062 if (M >= 0)

1063 Segs.set(M >> Shift);

1064 }

1065

1067 return SegList;

1068}

1069

1071 unsigned SegLen) {

1072

1073

1074

1075

1076

1077

1078

1079

1080

1081 unsigned MaskLen = SM.Mask.size();

1082 assert(MaskLen % SegLen == 0);

1084

1085 for (int S = 0, E = Map.size(); S != E; ++S) {

1086 unsigned Idx = ~0u;

1087 for (int I = 0; I != static_cast<int>(SegLen); ++I) {

1088 int M = SM.Mask[S*SegLen + I];

1089 if (M < 0)

1090 continue;

1091 unsigned G = M / SegLen;

1092 if (Idx == ~0u) {

1093 Idx = G;

1094 } else if (Idx != G) {

1095 Idx = ~1u;

1096 break;

1097 }

1098 }

1099 Map[S] = Idx;

1100 }

1101

1102 return Map;

1103}

1104

1108 for (int I = OutSegMap.size() - 1; I >= 0; --I) {

1109 unsigned S = OutSegMap[I];

1110 assert(S != ~0u && "Unexpected undef");

1111 assert(S != ~1u && "Unexpected multi");

1112 if (InvMap.size() <= S)

1114 InvMap[S] = I;

1115 }

1116

1117 unsigned Shift = Log2_32(SegLen);

1118 for (int I = 0, E = Mask.size(); I != E; ++I) {

1119 int M = Mask[I];

1120 if (M >= 0) {

1121 int OutIdx = InvMap[M >> Shift];

1122 M = (M & (SegLen-1)) + SegLen*OutIdx;

1123 }

1124 PackedMask[I] = M;

1125 }

1126}

1127

1128bool HvxSelector::selectVectorConstants(SDNode *N) {

1129

1130

1131

1132

1134 SetVector<SDNode*> WorkQ;

1135

1136

1137

1139 for (unsigned i = 0; i != WorkQ.size(); ++i) {

1140 SDNode *W = WorkQ[i];

1143 for (unsigned j = 0, f = W->getNumOperands(); j != f; ++j)

1144 WorkQ.insert(W->getOperand(j).getNode());

1145 }

1146

1147 for (SDNode *L : Nodes)

1148 select(L);

1149

1150 return !Nodes.empty();

1151}

1152

1153void HvxSelector::materialize(const ResultStack &Results) {

1155 dbgs() << "Materializing\n";

1157 });

1159 return;

1160 const SDLoc &dl(Results.InpNode);

1161 std::vector Output;

1162

1165 std::vector Ops;

1166 for (const OpRef &R : Node.Ops) {

1168 if (R.isValue()) {

1169 Ops.push_back(R.OpV);

1170 continue;

1171 }

1172 if (R.OpN & OpRef::Undef) {

1174 Ops.push_back(ISel.selectUndef(dl, MVT(SVT)));

1175 continue;

1176 }

1177

1178 unsigned Part = R.OpN & OpRef::Whole;

1179 int Idx = SignExtend32(R.OpN & OpRef::Index, OpRef::IndexBits);

1180 if (Idx < 0)

1181 Idx += I;

1182 assert(Idx >= 0 && unsigned(Idx) < Output.size());

1184 MVT OpTy = Op.getValueType().getSimpleVT();

1185 if (Part != OpRef::Whole) {

1186 assert(Part == OpRef::LoHalf || Part == OpRef::HiHalf);

1189 unsigned Sub = (Part == OpRef::LoHalf) ? Hexagon::vsub_lo

1190 : Hexagon::vsub_hi;

1191 Op = DAG.getTargetExtractSubreg(Sub, dl, HalfTy, Op);

1192 }

1193 Ops.push_back(Op);

1194 }

1195

1197 SDNode *ResN = (Node.Opc == TargetOpcode::COPY)

1198 ? Ops.front().getNode()

1199 : DAG.getMachineNode(Node.Opc, dl, Node.Ty, Ops);

1200 Output.push_back(SDValue(ResN, 0));

1201 }

1202

1203 SDNode *OutN = Output.back().getNode();

1204 SDNode *InpN = Results.InpNode;

1206 dbgs() << "Generated node:\n";

1207 OutN->dumpr(&DAG);

1208 });

1209

1210 ISel.ReplaceNode(InpN, OutN);

1211 selectVectorConstants(OutN);

1212 DAG.RemoveDeadNodes();

1213}

1214

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

1217 const SDLoc &dl(Results.InpNode);

1218 Results.push(TargetOpcode::REG_SEQUENCE, getPairVT(MVT::i8), {

1219 getConst32(Hexagon::HvxWRRegClassID, dl),

1220 Lo, getConst32(Hexagon::vsub_lo, dl),

1221 Hi, getConst32(Hexagon::vsub_hi, dl),

1222 });

1223 return OpRef::res(Results.top());

1224}

1225

1226OpRef HvxSelector::funnels(OpRef Va, OpRef Vb, int Amount,

1228

1229

1230

1231 auto VecLen = static_cast<int>(HwLen);

1232

1233 if (Amount == 0)

1234 return Va;

1235 if (Amount == VecLen)

1236 return Vb;

1237

1238 MVT Ty = getSingleVT(MVT::i8);

1239 const SDLoc &dl(Results.InpNode);

1240

1241 if (Amount < 0)

1242 Amount += VecLen;

1243 if (Amount > VecLen) {

1244 Amount -= VecLen;

1246 }

1247

1249 SDValue A = getConst32(Amount, dl);

1250 Results.push(Hexagon::V6_valignbi, Ty, {Vb, Va, A});

1251 } else if (isUInt<3>(VecLen - Amount)) {

1252 SDValue A = getConst32(VecLen - Amount, dl);

1253 Results.push(Hexagon::V6_vlalignbi, Ty, {Vb, Va, A});

1254 } else {

1255 SDValue A = getConst32(Amount, dl);

1256 Results.push(Hexagon::A2_tfrsi, Ty, {A});

1257 Results.push(Hexagon::V6_valignb, Ty, {Vb, Va, OpRef::res(-1)});

1258 }

1259 return OpRef::res(Results.top());

1260}

1261

1262

1263

1264

1265OpRef HvxSelector::packs(ShuffleMask SM, OpRef Va, OpRef Vb,

1269 if (!Va.isValid() || !Vb.isValid())

1270 return OpRef::fail();

1271

1272 if (Vb.isUndef()) {

1274 return Va;

1275 }

1276 if (Va.isUndef()) {

1279 return Vb;

1280 }

1281

1282 MVT Ty = getSingleVT(MVT::i8);

1283 MVT PairTy = getPairVT(MVT::i8);

1284 OpRef Inp[2] = {Va, Vb};

1285 unsigned VecLen = SM.Mask.size();

1286

1287 auto valign = [this](OpRef Lo, OpRef Hi, unsigned Amt, MVT Ty,

1289 if (Amt == 0)

1290 return Lo;

1291 const SDLoc &dl(Results.InpNode);

1293 bool IsRight = isUInt<3>(Amt);

1294 SDValue S = getConst32(IsRight ? Amt : HwLen - Amt, dl);

1295 unsigned Opc = IsRight ? Hexagon::V6_valignbi : Hexagon::V6_vlalignbi;

1297 return OpRef::res(Results.top());

1298 }

1299 Results.push(Hexagon::A2_tfrsi, MVT::i32, {getConst32(Amt, dl)});

1300 OpRef A = OpRef::res(Results.top());

1301 Results.push(Hexagon::V6_valignb, Ty, {Hi, Lo, A});

1302 return OpRef::res(Results.top());

1303 };

1304

1305

1306 unsigned SegLen = HwLen / 2;

1307

1308

1309

1311 SmallVector<unsigned, 4> SegList = getInputSegmentList(SM.Mask, SegLen);

1312 unsigned SegCount = SegList.size();

1314

1315 if (SegList.empty())

1316 return OpRef::undef(Ty);

1317

1318

1319

1320

1321

1322

1323

1324

1325

1326

1327

1328

1329

1330

1331

1332

1333

1334 unsigned Seg0 = ~0u, Seg1 = ~0u;

1335 for (unsigned X : SegMap) {

1336 if (X == ~0u)

1337 continue;

1338 if (Seg0 == ~0u)

1339 Seg0 = X;

1340 else if (Seg1 != ~0u)

1341 break;

1342 if (X == ~1u || X != Seg0)

1343 Seg1 = X;

1344 }

1345

1346 if (SegCount == 1) {

1347 unsigned SrcOp = SegList[0] / 2;

1348 for (int I = 0; I != static_cast<int>(VecLen); ++I) {

1349 int M = SM.Mask[I];

1350 if (M >= 0) {

1351 M -= SrcOp * HwLen;

1353 }

1354 NewMask[I] = M;

1355 }

1356 return Inp[SrcOp];

1357 }

1358

1359 if (SegCount == 2) {

1360

1361

1362 assert(Seg0 != ~0u);

1363

1364

1365

1366 if (Seg0 == ~1u || Seg1 == ~1u) {

1367 if (Seg0 == Seg1) {

1368 Seg0 = SegList[0];

1369 Seg1 = SegList[1];

1370 } else if (Seg0 == ~1u) {

1371 Seg0 = SegList[0] != Seg1 ? SegList[0] : SegList[1];

1372 } else {

1373 assert(Seg1 == ~1u);

1374 Seg1 = SegList[0] != Seg0 ? SegList[0] : SegList[1];

1375 }

1376 }

1377 assert(Seg0 != ~1u && Seg1 != ~1u);

1378

1379 assert(Seg0 != Seg1 && "Expecting different segments");

1380 const SDLoc &dl(Results.InpNode);

1381 Results.push(Hexagon::A2_tfrsi, MVT::i32, {getConst32(SegLen, dl)});

1382 OpRef HL = OpRef::res(Results.top());

1383

1384

1385

1386 if (Seg0 / 2 == Seg1 / 2) {

1387

1388 Va = Inp[Seg0 / 2];

1389 if (Seg0 > Seg1) {

1390

1391 Results.push(Hexagon::V6_vror, Ty, {Inp[Seg0 / 2], HL});

1392 Va = OpRef::res(Results.top());

1393 }

1395 } else if (Seg0 % 2 == Seg1 % 2) {

1396

1397

1398

1399 auto Vs = (Seg0 == 0 || Seg0 == 1) ? std::make_pair(Vb, Va)

1400 : std::make_pair(Va, Vb);

1401 Results.push(Hexagon::V6_vshuffvdd, PairTy, {Vs.first, Vs.second, HL});

1402 OpRef P = OpRef::res(Results.top());

1403 Va = (Seg0 == 0 || Seg0 == 2) ? OpRef::lo(P) : OpRef::hi(P);

1405 } else {

1406

1407 if ((Seg0 == 0 && Seg1 == 3) || (Seg0 == 2 && Seg1 == 1)) {

1408

1409

1410

1411 Results.push(Hexagon::V6_pred_scalar2, getBoolVT(), {HL});

1412 OpRef Qt = OpRef::res(Results.top());

1413 auto Vs = (Seg0 == 0) ? std::make_pair(Va, Vb)

1414 : std::make_pair(Vb, Va);

1415 Results.push(Hexagon::V6_vmux, Ty, {Qt, Vs.first, Vs.second});

1416 Va = OpRef::res(Results.top());

1418 } else {

1419

1420

1421

1422 assert(Seg0 == 1 || Seg0 == 3);

1423 }

1424 }

1425 }

1426

1427

1428

1429 ShuffleMask SMH(MaskH);

1430 assert(SMH.Mask.size() == VecLen);

1432

1433 if (SMH.MaxSrc - SMH.MinSrc >= static_cast<int>(HwLen)) {

1434

1437 ShuffleMask SW(Swapped);

1438 if (SW.MaxSrc - SW.MinSrc < static_cast<int>(HwLen)) {

1439 MaskA.assign(SW.Mask.begin(), SW.Mask.end());

1441 }

1442 }

1443 ShuffleMask SMA(MaskA);

1444 assert(SMA.Mask.size() == VecLen);

1445

1446 if (SMA.MaxSrc - SMA.MinSrc < static_cast<int>(HwLen)) {

1447 int ShiftR = SMA.MinSrc;

1448 if (ShiftR >= static_cast<int>(HwLen)) {

1449 Va = Vb;

1450 Vb = OpRef::undef(Ty);

1451 ShiftR -= HwLen;

1452 }

1453 OpRef RetVal = valign(Va, Vb, ShiftR, Ty, Results);

1454

1455 for (int I = 0; I != static_cast<int>(VecLen); ++I) {

1456 int M = SMA.Mask[I];

1457 if (M != -1)

1458 M -= SMA.MinSrc;

1459 NewMask[I] = M;

1460 }

1461 return RetVal;

1462 }

1463

1464

1465

1466

1467

1468

1469 if (Options & PackMux) {

1470

1471

1472 BitVector Picked(HwLen);

1473 SmallVector<uint8_t,128> MuxBytes(HwLen);

1474 bool CanMux = true;

1475 for (int I = 0; I != static_cast<int>(VecLen); ++I) {

1476 int M = SM.Mask[I];

1477 if (M == -1)

1478 continue;

1479 if (M >= static_cast<int>(HwLen))

1480 M -= HwLen;

1481 else

1482 MuxBytes[M] = 0xFF;

1483 if (Picked[M]) {

1484 CanMux = false;

1485 break;

1486 }

1487 NewMask[I] = M;

1488 }

1489 if (CanMux)

1490 return vmuxs(MuxBytes, Va, Vb, Results);

1491 }

1492 return OpRef::fail();

1493}

1494

1495

1496

1497

1498OpRef HvxSelector::packp(ShuffleMask SM, OpRef Va, OpRef Vb,

1502 if (SegList.empty())

1503 return OpRef::undef(getPairVT(MVT::i8));

1504

1505

1506

1507 unsigned SegCount = SegList.size();

1508 if (SegCount > 2)

1509 return OpRef::fail();

1510

1511 MVT HalfTy = getSingleVT(MVT::i8);

1512

1513 OpRef Inp[2] = { Va, Vb };

1514 OpRef Out[2] = { OpRef::undef(HalfTy), OpRef::undef(HalfTy) };

1515

1516

1517 assert(SegCount <= 2);

1518

1519 for (int I = 0, E = SegList.size(); I != E; ++I) {

1520 unsigned S = SegList[I];

1521 OpRef Op = Inp[S / 2];

1522 Out[I] = (S & 1) ? OpRef::hi(Op) : OpRef::lo(Op);

1523 }

1524

1525

1526

1527

1528

1529

1530

1532 return concats(Out[0], Out[1], Results);

1533}

1534

1535OpRef HvxSelector::vmuxs(ArrayRef<uint8_t> Bytes, OpRef Va, OpRef Vb,

1538 MVT ByteTy = getSingleVT(MVT::i8);

1540 const SDLoc &dl(Results.InpNode);

1541 SDValue B = getVectorConstant(Bytes, dl);

1542 Results.push(Hexagon::V6_vd0, ByteTy, {});

1543 Results.push(Hexagon::V6_veqb, BoolTy, {OpRef(B), OpRef::res(-1)});

1544 Results.push(Hexagon::V6_vmux, ByteTy, {OpRef::res(-1), Vb, Va});

1545 return OpRef::res(Results.top());

1546}

1547

1548OpRef HvxSelector::vmuxp(ArrayRef<uint8_t> Bytes, OpRef Va, OpRef Vb,

1551 size_t S = Bytes.size() / 2;

1552 OpRef L = vmuxs(Bytes.take_front(S), OpRef::lo(Va), OpRef::lo(Vb), Results);

1553 OpRef H = vmuxs(Bytes.drop_front(S), OpRef::hi(Va), OpRef::hi(Vb), Results);

1554 return concats(L, H, Results);

1555}

1556

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

1559 unsigned VecLen = SM.Mask.size();

1560 assert(HwLen == VecLen);

1561 (void)VecLen;

1562 assert(all_of(SM.Mask, [this](int M) { return M == -1 || M < int(HwLen); }));

1563

1565 return Va;

1567 return OpRef::undef(getSingleVT(MVT::i8));

1568

1569

1570 if (auto Dist = rotationDistance(SM, VecLen)) {

1571 OpRef Rotate = funnels(Va, Va, *Dist, Results);

1572 if (Rotate.isValid())

1573 return Rotate;

1574 }

1575 unsigned HalfLen = HwLen / 2;

1577

1578

1579

1580 std::pair<int, unsigned> Strip1 = findStrip(SM.Mask, 1, HalfLen);

1581 if ((Strip1.first & ~HalfLen) == 0 && Strip1.second == HalfLen) {

1582 std::pair<int, unsigned> Strip2 =

1584 if (Strip1 == Strip2) {

1585 const SDLoc &dl(Results.InpNode);

1586 Results.push(Hexagon::A2_tfrsi, MVT::i32, {getConst32(HalfLen, dl)});

1587 Results.push(Hexagon::V6_vshuffvdd, getPairVT(MVT::i8),

1588 {Va, Va, OpRef::res(Results.top())});

1589 OpRef S = OpRef::res(Results.top());

1590 return (Strip1.first == 0) ? OpRef::lo(S) : OpRef::hi(S);

1591 }

1592 }

1593

1594 OpRef P = perfect(SM, Va, Results);

1595 if (P.isValid())

1596 return P;

1597 return butterfly(SM, Va, Results);

1598}

1599

1600OpRef HvxSelector::shuffs2(ShuffleMask SM, OpRef Va, OpRef Vb,

1604 return OpRef::undef(getSingleVT(MVT::i8));

1605

1606 OpRef C = contracting(SM, Va, Vb, Results);

1607 if (C.isValid())

1608 return C;

1609

1610 int VecLen = SM.Mask.size();

1612 OpRef P = packs(SM, Va, Vb, Results, PackedMask);

1613 if (P.isValid())

1614 return shuffs1(ShuffleMask(PackedMask), P, Results);

1615

1616

1617

1618

1620 splitMask(SM.Mask, MaskL, MaskR);

1621

1622 OpRef L = shuffs1(ShuffleMask(MaskL), Va, Results);

1623 OpRef R = shuffs1(ShuffleMask(MaskR), Vb, Results);

1624 if (.isValid() || .isValid())

1625 return OpRef::fail();

1626

1627 SmallVector<uint8_t, 128> Bytes(VecLen);

1628 for (int I = 0; I != VecLen; ++I) {

1629 if (MaskL[I] != -1)

1630 Bytes[I] = 0xFF;

1631 }

1632 return vmuxs(Bytes, L, R, Results);

1633}

1634

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

1637 int VecLen = SM.Mask.size();

1638

1640 return Va;

1642 return OpRef::undef(getPairVT(MVT::i8));

1643

1645 OpRef P = packs(SM, OpRef::lo(Va), OpRef::hi(Va), Results, PackedMask);

1646 if (P.isValid()) {

1647 ShuffleMask PM(PackedMask);

1648 OpRef E = expanding(PM, P, Results);

1649 if (E.isValid())

1650 return E;

1651

1652 OpRef L = shuffs1(PM.lo(), P, Results);

1653 OpRef H = shuffs1(PM.hi(), P, Results);

1654 if (L.isValid() && H.isValid())

1655 return concats(L, H, Results);

1656 }

1657

1659

1660

1661

1662

1663

1664 OpRef R = perfect(SM, Va, Results);

1665 if (R.isValid())

1666 return R;

1667

1668 }

1669

1670 OpRef L = shuffs2(SM.lo(), OpRef::lo(Va), OpRef::hi(Va), Results);

1671 OpRef H = shuffs2(SM.hi(), OpRef::lo(Va), OpRef::hi(Va), Results);

1672 if (L.isValid() && H.isValid())

1673 return concats(L, H, Results);

1674

1675 return OpRef::fail();

1676}

1677

1678OpRef HvxSelector::shuffp2(ShuffleMask SM, OpRef Va, OpRef Vb,

1682 return OpRef::undef(getPairVT(MVT::i8));

1683

1684 int VecLen = SM.Mask.size();

1686 OpRef P = packp(SM, Va, Vb, Results, PackedMask);

1687 if (P.isValid())

1688 return shuffp1(ShuffleMask(PackedMask), P, Results);

1689

1691 splitMask(SM.Mask, MaskL, MaskR);

1692

1693 OpRef L = shuffp1(ShuffleMask(MaskL), Va, Results);

1694 OpRef R = shuffp1(ShuffleMask(MaskR), Vb, Results);

1695 if (.isValid() || .isValid())

1696 return OpRef::fail();

1697

1698

1700 for (int I = 0; I != VecLen; ++I) {

1701 if (MaskL[I] != -1)

1702 Bytes[I] = 0xFF;

1703 }

1704 return vmuxp(Bytes, L, R, Results);

1705}

1706

1707namespace {

1708 struct Deleter : public SelectionDAG::DAGNodeDeletedListener {

1709 template

1710 Deleter(SelectionDAG &D, T &C)

1711 : SelectionDAG::DAGNodeDeletedListener(D, [&C] (SDNode *N, SDNode *E) {

1712 C.erase(N);

1713 }) {}

1714 };

1715

1716 template

1717 struct NullifyingVector : public T {

1718 DenseMap<SDNode*, SDNode**> Refs;

1719 NullifyingVector(T &&V) : T(V) {

1720 for (unsigned i = 0, e = T::size(); i != e; ++i) {

1721 SDNode *&N = T::operator[](i);

1722 Refs[N] = &N;

1723 }

1724 }

1725 void erase(SDNode *N) {

1726 auto F = Refs.find(N);

1727 if (F != Refs.end())

1728 *F->second = nullptr;

1729 }

1730 };

1731}

1732

1733void HvxSelector::select(SDNode *ISelN) {

1734

1735

1736

1737

1738

1739

1740

1741

1742

1743

1746

1747

1748

1749

1750 DAG.RemoveDeadNodes();

1751

1752 SetVector<SDNode *> SubNodes;

1753

1755

1756

1757 auto IsISelN = [](SDNode *T) { return T->getOpcode() == HexagonISD::ISEL; };

1759 SubNodes.insert(N0);

1760 }

1761 if (SubNodes.empty()) {

1762 ISel.ReplaceNode(ISelN, N0);

1763 return;

1764 }

1765

1766

1767

1768

1769 SetVector<SDNode*> Dom, NonDom;

1771

1772 auto IsDomRec = [&Dom, &NonDom] (SDNode *T, auto Rec) -> bool {

1774 return true;

1775 if (T->use_empty() || NonDom.count(T))

1776 return false;

1777 for (SDNode *U : T->users()) {

1778

1779

1780 if (!Rec(U, Rec)) {

1782 return false;

1783 }

1784 }

1786 return true;

1787 };

1788

1789 auto IsDom = [&IsDomRec] (SDNode *T) { return IsDomRec(T, IsDomRec); };

1790

1791

1792 for (unsigned I = 0; I != SubNodes.size(); ++I) {

1794 SDNode *O = Op.getNode();

1795 if (IsDom(O))

1797 }

1798 }

1799

1800

1801 SetVector<SDNode*> TmpQ;

1802

1803 std::map<SDNode *, unsigned> OpCount;

1804 for (SDNode *T : Dom) {

1805 unsigned NumDomOps = llvm::count_if(T->ops(), [&Dom](const SDUse &U) {

1806 return Dom.count(U.getNode());

1807 });

1808

1809 OpCount.insert({T, NumDomOps});

1810 if (NumDomOps == 0)

1812 }

1813

1814 for (unsigned I = 0; I != TmpQ.size(); ++I) {

1815 SDNode *S = TmpQ[I];

1816 for (SDNode *U : S->users()) {

1817 if (U == ISelN)

1818 continue;

1819 auto F = OpCount.find(U);

1820 assert(F != OpCount.end());

1821 if (F->second > 0 && !--F->second)

1823 }

1824 }

1825

1826

1827 ISel.ReplaceNode(ISelN, N0);

1828

1830 NullifyingVector<decltype(TmpQ)::vector_type> Queue(TmpQ.takeVector());

1831

1832 Deleter DUQ(DAG, Queue);

1833 for (SDNode *S : reverse(Queue)) {

1834 if (S == nullptr)

1835 continue;

1837 ISel.Select(S);

1838 }

1839}

1840

1841bool HvxSelector::scalarizeShuffle(ArrayRef Mask, const SDLoc &dl,

1843 SDNode *N) {

1846 assert(ElemTy == MVT::i8);

1847 unsigned VecLen = Mask.size();

1848 bool HavePairs = (2*HwLen == VecLen);

1849 MVT SingleTy = getSingleVT(MVT::i8);

1850

1851

1852

1853

1854

1855

1856

1857

1858

1859

1860

1861

1862

1863

1865 LLVMContext &Ctx = *DAG.getContext();

1866 MVT LegalTy = Lower.getTypeToTransformTo(Ctx, ElemTy).getSimpleVT();

1867 for (int I : Mask) {

1868 if (I < 0) {

1869 Ops.push_back(ISel.selectUndef(dl, LegalTy));

1870 continue;

1871 }

1873 unsigned M = I;

1874 if (M < VecLen) {

1875 Vec = Va;

1876 } else {

1877 Vec = Vb;

1878 M -= VecLen;

1879 }

1880 if (HavePairs) {

1881 if (M < HwLen) {

1882 Vec = DAG.getTargetExtractSubreg(Hexagon::vsub_lo, dl, SingleTy, Vec);

1883 } else {

1884 Vec = DAG.getTargetExtractSubreg(Hexagon::vsub_hi, dl, SingleTy, Vec);

1885 M -= HwLen;

1886 }

1887 }

1888 SDValue Idx = DAG.getConstant(M, dl, MVT::i32);

1892 Ops.push_back(L);

1893 }

1894

1896 if (2*HwLen == VecLen) {

1897 SDValue B0 = DAG.getBuildVector(SingleTy, dl, {Ops.data(), HwLen});

1899 SDValue B1 = DAG.getBuildVector(SingleTy, dl, {Ops.data()+HwLen, HwLen});

1901

1902

1903

1904

1906 } else {

1907 SDValue BV = DAG.getBuildVector(ResTy, dl, Ops);

1908 LV = Lower.LowerOperation(BV, DAG);

1909 }

1910

1911 assert(->use_empty());

1913 ISel.ReplaceNode(N, IS.getNode());

1915 DAG.RemoveDeadNodes();

1916 return true;

1917}

1918

1920 unsigned Width) {

1922 unsigned Impossible = ~(1u << Width) + 1;

1923 for (unsigned I = 0, E = Bs.size(); I != E; ++I) {

1925 if (B == 0xff)

1926 continue;

1927 if (~Impossible == 0)

1928 break;

1929 for (unsigned Log = 0; Log != Width; ++Log) {

1930 if (Impossible & (1u << Log))

1931 continue;

1932 unsigned Expected = (I >> Log) % 2;

1934 Impossible |= (1u << Log);

1935 }

1936 }

1937 return ~Impossible;

1938 };

1939

1941

1942 for (unsigned BitIdx = 0; BitIdx != Width; ++BitIdx) {

1944 for (int i = 0, e = SM.Mask.size(); i != e; ++i) {

1945 int M = SM.Mask[i];

1946 if (M < 0)

1947 BitValues[i] = 0xff;

1948 else

1949 BitValues[i] = (M & (1u << BitIdx)) != 0;

1950 }

1951 Worklist[BitIdx] = possibilities(BitValues, Width);

1952 }

1953

1954

1955

1956

1957

1958

1959

1960

1961

1962

1963

1964

1965

1966

1967

1968

1969

1970

1971

1972

1973

1974

1975

1976

1977

1978

1979

1980

1981

1982

1983

1984

1985

1986

1987

1988

1989

1992

1993 for (unsigned I = 0, E = Sorted.size(); I != E;) {

1994 unsigned P = Sorted[I], Count = 1;

1995 while (++I != E && P == Sorted[I])

1998

1999

2001 }

2002 }

2003

2004 return Worklist;

2005}

2006

2009

2010

2012

2013 for (unsigned I = 0; I != Width; ++I) {

2017 continue;

2018

2020

2021 for (unsigned J = I + 1; J != Width; ++J) {

2022 if (Comps[J] == P)

2023 Comps[J] ^= T;

2024 }

2025 Comps[I] = T;

2026 }

2027

2028#ifndef NDEBUG

2029

2033 OrAll |= C;

2034 }

2035 assert(OrAll == (1u << Width) -1);

2036#endif

2037

2038 return Comps;

2039}

2040

2042 unsigned WrapAt) {

2043 std::optional Dist;

2044 for (int I = 0, E = SM.Mask.size(); I != E; ++I) {

2045 int M = SM.Mask[I];

2046 if (M < 0)

2047 continue;

2048 if (Dist) {

2049 if ((I + *Dist) % static_cast<int>(WrapAt) != M)

2050 return std::nullopt;

2051 } else {

2052

2053

2054

2055 Dist = M - I;

2056 if (Dist < 0)

2057 Dist = *Dist + WrapAt;

2058 }

2059 }

2060 return Dist;

2061}

2062

2063OpRef HvxSelector::contracting(ShuffleMask SM, OpRef Va, OpRef Vb,

2066 if (!Va.isValid() || !Vb.isValid())

2067 return OpRef::fail();

2068

2069

2070

2071

2072

2073

2074

2075

2076

2077

2078 int VecLen = SM.Mask.size();

2079

2080

2081 if (auto Dist = rotationDistance(SM, 2 * VecLen)) {

2082 OpRef Funnel = funnels(Va, Vb, *Dist, Results);

2083 if (Funnel.isValid())

2084 return Funnel;

2085 }

2086

2087 MVT SingleTy = getSingleVT(MVT::i8);

2088 MVT PairTy = getPairVT(MVT::i8);

2089

2090 auto same = [](ArrayRef Mask1, ArrayRef Mask2) -> bool {

2091 return Mask1 == Mask2;

2092 };

2093

2094 using PackConfig = std::pair<unsigned, bool>;

2095 PackConfig Packs[] = {

2096 {1, false},

2097 {1, true},

2098 {2, false},

2099 {2, true},

2100 };

2101

2102 {

2103 unsigned Opcodes[] = {

2104 Hexagon::V6_vpackeb,

2105 Hexagon::V6_vpackob,

2106 Hexagon::V6_vpackeh,

2107 Hexagon::V6_vpackoh,

2108 };

2109 for (int i = 0, e = std::size(Opcodes); i != e; ++i) {

2110 auto [Size, Odd] = Packs[i];

2112 Results.push(Opcodes[i], SingleTy, {Vb, Va});

2113 return OpRef::res(Results.top());

2114 }

2115 }

2116 }

2117

2118 {

2119 unsigned Opcodes[] = {

2120 Hexagon::V6_vshuffeb,

2121 Hexagon::V6_vshuffob,

2122 Hexagon::V6_vshufeh,

2123 Hexagon::V6_vshufoh,

2124 };

2125 for (int i = 0, e = std::size(Opcodes); i != e; ++i) {

2126 auto [Size, Odd] = Packs[i];

2128 Results.push(Opcodes[i], SingleTy, {Vb, Va});

2129 return OpRef::res(Results.top());

2130 }

2131 }

2132 }

2133

2134 {

2135

2136

2137

2138 unsigned Opcodes[] = {

2139 Hexagon::V6_vpackeb,

2140 Hexagon::V6_vpackob,

2141 Hexagon::V6_vpackeh,

2142 Hexagon::V6_vpackoh,

2143 };

2144 const SDLoc &dl(Results.InpNode);

2145

2146 for (int i = 0, e = std::size(Opcodes); i != e; ++i) {

2147 auto [Size, Odd] = Packs[i];

2149 Results.push(Hexagon::A2_tfrsi, MVT::i32,

2150 {getSignedConst32(-2 * Size, dl)});

2151 Results.push(Hexagon::V6_vdealvdd, PairTy, {Vb, Va, OpRef::res(-1)});

2153 Results.push(Opcodes[i], SingleTy,

2154 {OpRef::hi(vdeal), OpRef::lo(vdeal)});

2155 return OpRef::res(Results.top());

2156 }

2157 }

2158 }

2159

2161 Results.push(Hexagon::V6_vdealb4w, SingleTy, {Vb, Va});

2162 return OpRef::res(Results.top());

2163 }

2164

2165 return OpRef::fail();

2166}

2167

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

2170

2171

2172

2173

2174

2175

2176

2177

2178

2179

2180

2181 int VecLen = SM.Mask.size();

2182 assert(2*HwLen == unsigned(VecLen) && "Expecting vector-pair type");

2183

2184 std::pair<int,unsigned> Strip = findStrip(SM.Mask, 1, VecLen);

2185

2186

2187

2188

2189

2190

2191 if (Strip.first != 0)

2192 return OpRef::fail();

2193

2194

2195 if (Strip.second != 1 && Strip.second != 2)

2196 return OpRef::fail();

2197

2198 int N = VecLen;

2199 int L = Strip.second;

2200

2201

2202 for (int I = 2*L; I < N; I += 2*L) {

2204 if (S.second != unsigned(L))

2205 return OpRef::fail();

2206 if (2*S.first != I)

2207 return OpRef::fail();

2208 }

2209

2210 for (int I = L; I < N; I += 2*L) {

2212 if (S.first != -1 || S.second != unsigned(L))

2213 return OpRef::fail();

2214 }

2215

2216 unsigned Opc = Strip.second == 1 ? Hexagon::V6_vunpackub

2217 : Hexagon::V6_vunpackuh;

2218 Results.push(Opc, getPairVT(MVT::i8), {Va});

2219 return OpRef::res(Results.top());

2220}

2221

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

2224

2225

2226

2227

2228

2229

2230

2231 int VecLen = SM.Mask.size();

2233 unsigned LogLen = Log2_32(VecLen);

2234 unsigned HwLog = Log2_32(HwLen);

2235

2236

2237 assert(LogLen == HwLog || LogLen == HwLog + 1);

2238 bool HavePairs = LogLen == HwLog + 1;

2239

2240 SmallVector<unsigned, 8> Perm(LogLen);

2241

2242

2243

2244

2245

2246

2247

2248

2249

2250

2251

2252

2253

2254

2255

2256

2257

2258

2259

2260

2261

2262

2263

2264

2265

2266

2267

2268

2269

2270

2271

2272

2273

2274

2275

2276

2277

2278

2279

2280

2281

2282

2283

2284

2285

2286

2287

2288

2289

2290

2291

2292

2293

2294

2295

2296

2297

2298

2299

2300

2301

2302

2303

2304

2305

2306

2307

2308

2309

2310

2311

2312

2313

2314

2315

2316

2317

2318

2319

2320

2321

2322

2324 bool InvertedPair = false;

2325 if (HavePairs && SM.Mask[0] >= int(HwLen)) {

2326 for (int i = 0, e = SM.Mask.size(); i != e; ++i) {

2327 int M = SM.Mask[i];

2328 MaskStorage[i] = M >= int(HwLen) ? M - HwLen : M + HwLen;

2329 }

2330 InvertedPair = true;

2331 SM = ShuffleMask(MaskStorage);

2332 }

2333

2334 auto Comps = getPerfectCompletions(SM, LogLen);

2336 return OpRef::fail();

2337

2338 auto Pick = completeToPerfect(Comps, LogLen);

2339 for (unsigned I = 0; I != LogLen; ++I)

2341

2342

2343

2344

2345

2346

2347

2348

2349

2350

2351

2352

2353

2354

2355

2356

2357

2358

2359

2360

2361

2362

2363

2364

2365

2366

2367 using CycleType = SmallVector<unsigned, 8>;

2368 std::set Cycles;

2369 std::set All;

2370

2371 for (unsigned I : Perm)

2372 All.insert(I);

2373

2374

2375

2376 auto canonicalize = [LogLen](const CycleType &C) -> CycleType {

2377 unsigned LogPos, N = C.size();

2378 for (LogPos = 0; LogPos != N; ++LogPos)

2379 if (C[LogPos] == LogLen - 1)

2380 break;

2381 if (LogPos == N)

2382 return C;

2383

2384 CycleType NewC(C.begin() + LogPos, C.end());

2385 NewC.append(C.begin(), C.begin() + LogPos);

2386 return NewC;

2387 };

2388

2389 auto pfs = [](const std::set &Cs, unsigned Len) {

2390

2391

2392 if (Cs.size() != 1)

2393 return 0u;

2394 const CycleType &C = *Cs.begin();

2395 if (C[0] != Len - 1)

2396 return 0u;

2397 int D = Len - C.size();

2398 if (D != 0 && D != 1)

2399 return 0u;

2400

2401 bool IsDeal = true, IsShuff = true;

2402 for (unsigned I = 1; I != Len - D; ++I) {

2403 if (C[I] != Len - 1 - I)

2404 IsDeal = false;

2405 if (C[I] != I - (1 - D))

2406 IsShuff = false;

2407 }

2408

2409 assert(!(IsDeal || IsShuff) || IsDeal != IsShuff);

2410 static unsigned Deals[] = {Hexagon::V6_vdealb, Hexagon::V6_vdealh};

2411 static unsigned Shufs[] = {Hexagon::V6_vshuffb, Hexagon::V6_vshuffh};

2412 return IsDeal ? Deals[D] : (IsShuff ? Shufs[D] : 0);

2413 };

2414

2415 while ( All .empty()) {

2416 unsigned A = *All.begin();

2417 All.erase(A);

2418 CycleType C;

2419 C.push_back(A);

2420 for (unsigned B = Perm[A]; B != A; B = Perm[B]) {

2421 C.push_back(B);

2422 All.erase(B);

2423 }

2424 if (C.size() <= 1)

2425 continue;

2426 Cycles.insert(canonicalize(C));

2427 }

2428

2429 MVT SingleTy = getSingleVT(MVT::i8);

2430 MVT PairTy = getPairVT(MVT::i8);

2431

2432

2433 if (unsigned(VecLen) == HwLen) {

2434 if (unsigned SingleOpc = pfs(Cycles, LogLen)) {

2435 Results.push(SingleOpc, SingleTy, {Va});

2436 return OpRef::res(Results.top());

2437 }

2438 }

2439

2440

2441

2442

2443

2444

2445

2446 SmallVector<unsigned, 8> SwapElems;

2447

2448

2449

2450

2451

2452

2453

2454

2455

2456

2457 if (!HavePairs)

2458 SwapElems.push_back(LogLen - 1);

2459 for (const CycleType &C : Cycles) {

2460

2461 unsigned First = (C[0] == LogLen - 1) ? 1 : 0;

2465 }

2466 if (!HavePairs)

2467 SwapElems.push_back(LogLen - 1);

2468

2469 const SDLoc &dl(Results.InpNode);

2470 OpRef Arg = HavePairs ? Va : concats(Va, OpRef::undef(SingleTy), Results);

2471 if (InvertedPair)

2472 Arg = concats(OpRef::hi(Arg), OpRef::lo(Arg), Results);

2473

2474 for (unsigned I = 0, E = SwapElems.size(); I != E;) {

2475 bool IsInc = I == E - 1 || SwapElems[I] < SwapElems[I + 1];

2476 unsigned S = (1u << SwapElems[I]);

2477 if (I < E - 1) {

2478 while (++I < E - 1 && IsInc == (SwapElems[I] < SwapElems[I + 1]))

2479 S |= 1u << SwapElems[I];

2480

2481

2482 S |= 1u << SwapElems[I];

2483 }

2484 ++I;

2485

2486

2487

2488

2489

2490

2492

2493 NodeTemplate Res;

2494 Results.push(Hexagon::A2_tfrsi, MVT::i32, {getSignedConst32(SS, dl)});

2495 Res.Opc = IsInc ? Hexagon::V6_vshuffvdd : Hexagon::V6_vdealvdd;

2497 Res.Ops = {OpRef::hi(Arg), OpRef::lo(Arg), OpRef::res(-1)};

2499 Arg = OpRef::res(Results.top());

2500 }

2501

2502 return HavePairs ? Arg : OpRef::lo(Arg);

2503}

2504

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

2507

2508

2509

2510

2511

2512

2513

2514

2515

2516

2517 MVT ResTy = getSingleVT(MVT::i8);

2518 PermNetwork::Controls FC, RC;

2519 const SDLoc &dl(Results.InpNode);

2520 int VecLen = SM.Mask.size();

2521

2522 for (int M : SM.Mask) {

2523 if (M != -1 && M >= VecLen)

2524 return OpRef::fail();

2525 }

2526

2527

2528 ForwardDeltaNetwork FN(SM.Mask);

2529 if (FN.run(FC)) {

2530 SDValue Ctl = getVectorConstant(FC, dl);

2531 Results.push(Hexagon::V6_vdelta, ResTy, {Va, OpRef(Ctl)});

2532 return OpRef::res(Results.top());

2533 }

2534

2535

2536 ReverseDeltaNetwork RN(SM.Mask);

2537 if (RN.run(RC)) {

2538 SDValue Ctl = getVectorConstant(RC, dl);

2539 Results.push(Hexagon::V6_vrdelta, ResTy, {Va, OpRef(Ctl)});

2540 return OpRef::res(Results.top());

2541 }

2542

2543

2544 BenesNetwork BN(SM.Mask);

2545 if (BN.run(FC, RC)) {

2546 SDValue CtlF = getVectorConstant(FC, dl);

2547 SDValue CtlR = getVectorConstant(RC, dl);

2548 Results.push(Hexagon::V6_vdelta, ResTy, {Va, OpRef(CtlF)});

2549 Results.push(Hexagon::V6_vrdelta, ResTy,

2550 {OpRef::res(-1), OpRef(CtlR)});

2551 return OpRef::res(Results.top());

2552 }

2553

2554 return OpRef::fail();

2555}

2556

2557SDValue HvxSelector::getConst32(unsigned Val, const SDLoc &dl) {

2558 return DAG.getTargetConstant(Val, dl, MVT::i32);

2559}

2560

2561SDValue HvxSelector::getSignedConst32(int Val, const SDLoc &dl) {

2562 return DAG.getSignedTargetConstant(Val, dl, MVT::i32);

2563}

2564

2565SDValue HvxSelector::getVectorConstant(ArrayRef<uint8_t> Data,

2566 const SDLoc &dl) {

2568 for (uint8_t C : Data)

2569 Elems.push_back(DAG.getConstant(C, dl, MVT::i8));

2571 SDValue BV = DAG.getBuildVector(VecTy, dl, Elems);

2573 DAG.RemoveDeadNode(BV.getNode());

2575}

2576

2578 SDValue Inp = N->getOperand(0);

2579 MVT ResTy = N->getValueType(0).getSimpleVT();

2580 unsigned Idx = N->getConstantOperandVal(1);

2581

2586 assert(Idx == 0 || Idx == ResLen);

2587

2588 unsigned SubReg = Idx == 0 ? Hexagon::vsub_lo : Hexagon::vsub_hi;

2590

2592}

2593

2596 dbgs() << "Starting " << __func__ << " on node:\n";

2597 N->dump(&DAG);

2598 });

2599 MVT ResTy = N->getValueType(0).getSimpleVT();

2600

2601 assert(ResTy.isVector() && ResTy.getVectorElementType() == MVT::i8);

2602

2604 std::vector Mask(SN->getMask().begin(), SN->getMask().end());

2605

2606 for (int &Idx : Mask)

2607 if (Idx != -1 && Idx < 0)

2608 Idx = -1;

2609

2610 unsigned VecLen = Mask.size();

2611 bool HavePairs = (2*HwLen == VecLen);

2612 assert(ResTy.getSizeInBits() / 8 == VecLen);

2613

2614

2615

2616

2617 bool UseLeft = false, UseRight = false;

2618 for (unsigned I = 0; I != VecLen; ++I) {

2619 if (Mask[I] == -1)

2620 continue;

2621 unsigned Idx = Mask[I];

2622 assert(Idx < 2*VecLen);

2623 if (Idx < VecLen)

2624 UseLeft = true;

2625 else

2626 UseRight = true;

2627 }

2628

2630 dbgs() << "VecLen=" << VecLen << " HwLen=" << HwLen << " UseLeft="

2631 << UseLeft << " UseRight=" << UseRight << " HavePairs="

2632 << HavePairs << '\n';

2633 });

2634

2635 if (!UseLeft && !UseRight) {

2637 return;

2638 }

2639

2640 SDValue Vec0 = N->getOperand(0);

2641 SDValue Vec1 = N->getOperand(1);

2643

2644 ResultStack Results(SN);

2645 OpRef Va = OpRef::undef(ResTy);

2646 OpRef Vb = OpRef::undef(ResTy);

2647

2649 Results.push(TargetOpcode::COPY, ResTy, {Vec0});

2650 Va = OpRef::OpRef::res(Results.top());

2651 }

2653 Results.push(TargetOpcode::COPY, ResTy, {Vec1});

2654 Vb = OpRef::res(Results.top());

2655 }

2656

2657 OpRef Res = !HavePairs ? shuffs2(ShuffleMask(Mask), Va, Vb, Results)

2658 : shuffp2(ShuffleMask(Mask), Va, Vb, Results);

2659

2660 bool Done = Res.isValid();

2662

2663 Results.push(TargetOpcode::COPY, ResTy, {Res});

2665 } else {

2666 Done = scalarizeShuffle(Mask, SDLoc(N), ResTy, Vec0, Vec1, N);

2667 }

2668

2669 if ( Done ) {

2670#ifndef NDEBUG

2671 dbgs() << "Unhandled shuffle:\n";

2672 SN->dumpr(&DAG);

2673#endif

2675 }

2676}

2677

2679

2680 MVT Ty = N->getValueType(0).getSimpleVT();

2682 SDValue VecV = N->getOperand(0);

2683 SDValue RotV = N->getOperand(1);

2684 SDNode *NewN = nullptr;

2685

2687 unsigned S = CN->getZExtValue() % HST.getVectorLength();

2688 if (S == 0) {

2691 NewN = DAG.getMachineNode(Hexagon::V6_valignbi, dl, Ty,

2692 {VecV, VecV, getConst32(S, dl)});

2693 }

2694 }

2695

2696 if (!NewN)

2697 NewN = DAG.getMachineNode(Hexagon::V6_vror, dl, Ty, {VecV, RotV});

2698

2699 ISel.ReplaceNode(N, NewN);

2700}

2701

2703 SDValue Vv = N->getOperand(0);

2704 SDValue Vu = N->getOperand(1);

2705 SDValue Rt = N->getOperand(2);

2706 SDNode *NewN = DAG.getMachineNode(Hexagon::V6_valignb, SDLoc(N),

2707 N->getValueType(0), {Vv, Vu, Rt});

2708 ISel.ReplaceNode(N, NewN);

2709 DAG.RemoveDeadNode(N);

2710}

2711

2712void HexagonDAGToDAGISel::PreprocessHvxISelDAG() {

2713 auto getNodes = [this]() -> std::vector<SDNode *> {

2714 std::vector<SDNode *> T;

2715 T.reserve(CurDAG->allnodes_size());

2716 for (SDNode &N : CurDAG->allnodes())

2717 T.push_back(&N);

2718 return T;

2719 };

2720

2721 ppHvxShuffleOfShuffle(getNodes());

2722}

2723

2726 return std::hash<const void *>()(V.getNode()) +

2727 std::hash()(V.getResNo());

2728 };

2729};

2730

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

2732

2733

2734

2735

2736

2737

2738

2739

2740

2742 unsigned HwLen = HST->getVectorLength();

2743

2744 struct SubVectorInfo {

2745 SubVectorInfo(SDValue S, unsigned H) : Src(S), HalfIdx(H) {}

2747 unsigned HalfIdx;

2748 };

2749

2750 using MapType = std::unordered_map<SDValue, unsigned>;

2751

2752 auto getMaskElt = [&](unsigned Idx, ShuffleVectorSDNode *Shuff0,

2753 ShuffleVectorSDNode *Shuff1,

2754 const MapType &OpMap) -> int {

2755

2756

2757

2758

2759

2760

2761 ShuffleVectorSDNode *OpShuff = Idx < HwLen ? Shuff0 : Shuff1;

2762 if (Idx >= HwLen)

2763 Idx -= HwLen;

2764

2765

2766 int MaybeN = OpShuff->getMaskElt(Idx);

2767 if (MaybeN < 0)

2768 return -1;

2769

2770 auto N = static_cast<unsigned>(MaybeN);

2771 unsigned SrcBase = N < HwLen ? OpMap.at(OpShuff->getOperand(0))

2773 if (N >= HwLen)

2774 N -= HwLen;

2775

2776 return N + SrcBase;

2777 };

2778

2780

2784 ArrayRef TopMask = This->getMask();

2785

2786

2787 assert(TopMask.size() == S0->getMask().size() &&

2788 TopMask.size() == S1->getMask().size());

2790

2792 for (unsigned I = 0; I != HwLen; ++I) {

2793 int MaybeM = TopMask[I];

2794 if (MaybeM >= 0) {

2795 FoldedMask[I] =

2796 getMaskElt(static_cast<unsigned>(MaybeM), S0, S1, OpMap);

2797 } else {

2798 FoldedMask[I] = -1;

2799 }

2800 }

2801

2802 std::fill(FoldedMask.begin() + HwLen, FoldedMask.end(), -1);

2803

2804

2805

2806

2807 const SDLoc &dl(TopShuff);

2815 };

2816

2817 auto getSourceInfo = [](SDValue V) -> std::optional {

2818 while (V.getOpcode() == ISD::BITCAST)

2819 V = V.getOperand(0);

2821 return std::nullopt;

2822 return SubVectorInfo(V.getOperand(0),

2824 };

2825

2826 for (SDNode *N : Nodes) {

2828 continue;

2829 EVT ResTy = N->getValueType(0);

2831 continue;

2833 continue;

2834

2835 SDValue V0 = N->getOperand(0);

2836 SDValue V1 = N->getOperand(1);

2838 continue;

2840 continue;

2842 continue;

2843

2844

2845

2846 auto V0A = getSourceInfo(V0.getOperand(0));

2847 if (!V0A.has_value())

2848 continue;

2849 auto V0B = getSourceInfo(V0.getOperand(1));

2850 if (!V0B.has_value() || V0B->Src != V0A->Src)

2851 continue;

2852 auto V1A = getSourceInfo(V1.getOperand(0));

2853 if (!V1A.has_value() || V1A->Src != V0A->Src)

2854 continue;

2855 auto V1B = getSourceInfo(V1.getOperand(1));

2856 if (!V1B.has_value() || V1B->Src != V0A->Src)

2857 continue;

2858

2859

2860

2861 assert(V0A->Src.getValueType().getSizeInBits() == 16 * HwLen);

2862

2863 MapType OpMap = {

2864 {V0.getOperand(0), V0A->HalfIdx * HwLen},

2865 {V0.getOperand(1), V0B->HalfIdx * HwLen},

2866 {V1.getOperand(0), V1A->HalfIdx * HwLen},

2867 {V1.getOperand(1), V1B->HalfIdx * HwLen},

2868 };

2869 SDValue NewS = fold3(SDValue(N, 0), V0A->Src, std::move(OpMap));

2870 ReplaceNode(N, NewS.getNode());

2871 }

2872}

2873

2874void HexagonDAGToDAGISel::SelectHvxExtractSubvector(SDNode *N) {

2875 HvxSelector(*this, *CurDAG).selectExtractSubvector(N);

2876}

2877

2878void HexagonDAGToDAGISel::SelectHvxShuffle(SDNode *N) {

2879 HvxSelector(*this, *CurDAG).selectShuffle(N);

2880}

2881

2882void HexagonDAGToDAGISel::SelectHvxRor(SDNode *N) {

2883 HvxSelector(*this, *CurDAG).selectRor(N);

2884}

2885

2886void HexagonDAGToDAGISel::SelectHvxVAlign(SDNode *N) {

2887 HvxSelector(*this, *CurDAG).selectVAlign(N);

2888}

2889

2892 SDValue Chain = N->getOperand(0);

2894 SDValue Predicate = N->getOperand(3);

2896 SDValue Modifier = N->getOperand(5);

2898 SDValue ImmOperand = CurDAG->getTargetConstant(0, dl, MVT::i32);

2899

2900 unsigned Opcode;

2901 unsigned IntNo = N->getConstantOperandVal(1);

2902 switch (IntNo) {

2903 default:

2905 case Intrinsic::hexagon_V6_vgathermhq:

2906 case Intrinsic::hexagon_V6_vgathermhq_128B:

2907 Opcode = Hexagon::V6_vgathermhq_pseudo;

2908 break;

2909 case Intrinsic::hexagon_V6_vgathermwq:

2910 case Intrinsic::hexagon_V6_vgathermwq_128B:

2911 Opcode = Hexagon::V6_vgathermwq_pseudo;

2912 break;

2913 case Intrinsic::hexagon_V6_vgathermhwq:

2914 case Intrinsic::hexagon_V6_vgathermhwq_128B:

2915 Opcode = Hexagon::V6_vgathermhwq_pseudo;

2916 break;

2917 }

2918

2921 Predicate, Base, Modifier, Offset, Chain };

2922 SDNode *Result = CurDAG->getMachineNode(Opcode, dl, VTs, Ops);

2923

2926

2928}

2929

2932 SDValue Chain = N->getOperand(0);

2935 SDValue Modifier = N->getOperand(4);

2937 SDValue ImmOperand = CurDAG->getTargetConstant(0, dl, MVT::i32);

2938

2939 unsigned Opcode;

2940 unsigned IntNo = N->getConstantOperandVal(1);

2941 switch (IntNo) {

2942 default:

2944 case Intrinsic::hexagon_V6_vgathermh:

2945 case Intrinsic::hexagon_V6_vgathermh_128B:

2946 Opcode = Hexagon::V6_vgathermh_pseudo;

2947 break;

2948 case Intrinsic::hexagon_V6_vgathermw:

2949 case Intrinsic::hexagon_V6_vgathermw_128B:

2950 Opcode = Hexagon::V6_vgathermw_pseudo;

2951 break;

2952 case Intrinsic::hexagon_V6_vgathermhw:

2953 case Intrinsic::hexagon_V6_vgathermhw_128B:

2954 Opcode = Hexagon::V6_vgathermhw_pseudo;

2955 break;

2956 case Intrinsic::hexagon_V6_vgather_vscattermh:

2957 case Intrinsic::hexagon_V6_vgather_vscattermh_128B:

2958 Opcode = Hexagon::V6_vgather_vscatter_mh_pseudo;

2959 break;

2960 }

2961

2964 SDNode *Result = CurDAG->getMachineNode(Opcode, dl, VTs, Ops);

2965

2968

2970}

2971

2973 unsigned IID = N->getConstantOperandVal(0);

2975 switch (IID) {

2976 case Intrinsic::hexagon_V6_vaddcarry: {

2977 std::array<SDValue, 3> Ops = {

2978 {N->getOperand(1), N->getOperand(2), N->getOperand(3)}};

2979 SDVTList VTs = CurDAG->getVTList(MVT::v16i32, MVT::v64i1);

2980 Result = CurDAG->getMachineNode(Hexagon::V6_vaddcarry, SDLoc(N), VTs, Ops);

2981 break;

2982 }

2983 case Intrinsic::hexagon_V6_vaddcarry_128B: {

2984 std::array<SDValue, 3> Ops = {

2985 {N->getOperand(1), N->getOperand(2), N->getOperand(3)}};

2986 SDVTList VTs = CurDAG->getVTList(MVT::v32i32, MVT::v128i1);

2987 Result = CurDAG->getMachineNode(Hexagon::V6_vaddcarry, SDLoc(N), VTs, Ops);

2988 break;

2989 }

2990 case Intrinsic::hexagon_V6_vsubcarry: {

2991 std::array<SDValue, 3> Ops = {

2992 {N->getOperand(1), N->getOperand(2), N->getOperand(3)}};

2993 SDVTList VTs = CurDAG->getVTList(MVT::v16i32, MVT::v64i1);

2994 Result = CurDAG->getMachineNode(Hexagon::V6_vsubcarry, SDLoc(N), VTs, Ops);

2995 break;

2996 }

2997 case Intrinsic::hexagon_V6_vsubcarry_128B: {

2998 std::array<SDValue, 3> Ops = {

2999 {N->getOperand(1), N->getOperand(2), N->getOperand(3)}};

3000 SDVTList VTs = CurDAG->getVTList(MVT::v32i32, MVT::v128i1);

3001 Result = CurDAG->getMachineNode(Hexagon::V6_vsubcarry, SDLoc(N), VTs, Ops);

3002 break;

3003 }

3004 default:

3006 }

3010 CurDAG->RemoveDeadNode(N);

3011}

assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")

const TargetInstrInfo & TII

static msgpack::DocNode getNode(msgpack::DocNode DN, msgpack::Type Type, MCValue Val)

ReachingDefInfo 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 constexpr unsigned long long mask(BlockVerifier::State S)

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")

static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")

#define LLVM_DUMP_METHOD

Mark debug helper function definitions like dump() that should not be stripped from debug builds.

static bool isIdentity(ArrayRef< int > Mask)

Definition HexagonISelDAGToDAGHVX.cpp:1035

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

Definition HexagonISelDAGToDAGHVX.cpp:1015

static const HexagonSubtarget & getHexagonSubtarget(SelectionDAG &G)

Definition HexagonISelDAGToDAGHVX.cpp:913

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

Definition HexagonISelDAGToDAGHVX.cpp:997

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

Definition HexagonISelDAGToDAGHVX.cpp:1105

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

Definition HexagonISelDAGToDAGHVX.cpp:1051

static const HexagonTargetLowering & getHexagonLowering(SelectionDAG &G)

Definition HexagonISelDAGToDAGHVX.cpp:910

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

Definition HexagonISelDAGToDAGHVX.cpp:1070

static bool isLowHalfOnly(ArrayRef< int > Mask)

Definition HexagonISelDAGToDAGHVX.cpp:1044

const AbstractManglingParser< Derived, Alloc >::OperatorInfo AbstractManglingParser< Derived, Alloc >::Ops[]

print mir2vec MIR2Vec Vocabulary Printer Pass

std::pair< MCSymbol *, MachineModuleInfoImpl::StubValueTy > PairTy

static bool isUndef(const MachineInstr &MI)

static bool isValid(const char C)

Returns true if C is a valid mangled character: <0-9a-zA-Z_>.

static Type * getValueType(Value *V)

Returns the type of the given value/instruction V.

BaseType

A given derived pointer can have multiple base pointers through phi/selects.

static LLVM_ATTRIBUTE_ALWAYS_INLINE MVT::SimpleValueType getSimpleVT(const unsigned char *MatcherTable, unsigned &MatcherIndex)

getSimpleVT - Decode a value in MatcherTable, if it's a VBR encoded value, use GetVBR to decode it.

This file implements a set that has insertion order iteration characteristics.

#define DEBUG_WITH_TYPE(TYPE,...)

DEBUG_WITH_TYPE macro - This macro should be used by passes to emit debug information.

static TableGen::Emitter::OptClass< SkeletonEmitter > X("gen-skeleton-class", "Generate example skeleton class")

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

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 SelectV65GatherPred(SDNode *N)

Definition HexagonISelDAGToDAGHVX.cpp:2890

void SelectV65Gather(SDNode *N)

Definition HexagonISelDAGToDAGHVX.cpp:2930

void SelectHVXDualOutput(SDNode *N)

Definition HexagonISelDAGToDAGHVX.cpp:2972

StringRef getName(unsigned Opcode) const

Returns the name for the instructions with the given opcode.

unsigned getVectorNumElements() const

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...

A NodeSet contains a set of SUnit DAG nodes with additional information that assigns a priority to th...

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.

LLVM_ABI void dump() const

Dump this node, for debugging.

unsigned getOpcode() const

Return the SelectionDAG opcode value for this node.

LLVM_ABI void dumpr() const

Dump (recursively) this node and its use-def subgraph.

const SDValue & getOperand(unsigned Num) const

LLVM_ABI void print(raw_ostream &OS, const SelectionDAG *G=nullptr) const

iterator_range< user_iterator > users()

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...

SDValue getUNDEF(EVT VT)

Return an UNDEF node. UNDEF does not have a useful SDLoc.

LLVM_ABI SDValue getBitcast(EVT VT, SDValue V)

Return a bitcast using the SDLoc of the value operand, and casting to the provided type.

LLVM_ABI SDValue getConstant(uint64_t Val, const SDLoc &DL, EVT VT, bool isTarget=false, bool isOpaque=false)

Create a ConstantSDNode wrapping a constant value.

LLVM_ABI SDValue getNode(unsigned Opcode, const SDLoc &DL, EVT VT, ArrayRef< SDUse > Ops)

Gets or creates the specified node.

LLVM_ABI SDValue getVectorShuffle(EVT VT, const SDLoc &dl, SDValue N1, SDValue N2, ArrayRef< int > Mask)

Return an ISD::VECTOR_SHUFFLE node.

size_type size() const

Determine the number of elements in the SetVector.

void insert_range(Range &&R)

size_type count(const_arg_type key) const

Count the number of elements of a given key in the SetVector.

Vector takeVector()

Clear the SetVector and return the underlying vector.

bool empty() const

Determine if the SetVector is empty or not.

bool insert(const value_type &X)

Insert a new element into the SetVector.

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)

This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.

#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 ...

@ 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...

@ 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.

NodeAddr< NodeBase * > Node

LLVM_ABI iterator begin() const

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.

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.

decltype(auto) dyn_cast(const From &Val)

dyn_cast - Return the argument parameter cast to the specified type.

SmallVectorImpl< T >::const_pointer c_str(SmallVectorImpl< T > &str)

void append_range(Container &C, Range &&R)

Wrapper function to append range R to container C.

constexpr int popcount(T Value) noexcept

Count the number of set bits in a value.

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)

LLVM_ABI raw_ostream & dbgs()

dbgs() - This returns a reference to a raw_ostream for debugging messages.

FunctionAddr VTableAddr Count

constexpr bool isUInt(uint64_t x)

Checks if an unsigned integer fits into the given bit width.

class LLVM_GSL_OWNER SmallVector

Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...

format_object< Ts... > format(const char *Fmt, const Ts &... Vals)

These are helper functions used to produce formatted output.

MutableArrayRef(T &OneElt) -> MutableArrayRef< T >

@ First

Helpers to iterate all locations in the MemoryEffectsBase class.

FunctionAddr VTableAddr uintptr_t uintptr_t Data

void replace(R &&Range, const T &OldValue, const T &NewValue)

Provide wrappers to std::replace which take ranges instead of having to pass begin/end explicitly.

@ Sub

Subtraction of integers.

uint64_t alignTo(uint64_t Size, Align A)

Returns a multiple of A needed to store Size bytes.

DWARFExpression::Operation Op

raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)

ArrayRef(const T &OneElt) -> ArrayRef< T >

OutputIt copy(R &&Range, OutputIt Out)

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...

decltype(auto) cast(const From &Val)

cast - Return the argument parameter cast to the specified type.

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)

Definition HexagonISelDAGToDAGHVX.cpp:811

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

Definition HexagonISelDAGToDAGHVX.cpp:851

ArrayRef< int > hi(ArrayRef< int > Vuu)

Definition HexagonISelDAGToDAGHVX.cpp:809

auto mask(ShuffFunc S, unsigned Length, OptArgs... args) -> MaskT

Definition HexagonISelDAGToDAGHVX.cpp:898

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

Definition HexagonISelDAGToDAGHVX.cpp:866

MaskT vdealb4w(ArrayRef< int > Vu, ArrayRef< int > Vv)

Definition HexagonISelDAGToDAGHVX.cpp:885

SmallVector< int, 128 > MaskT

Definition HexagonISelDAGToDAGHVX.cpp:800

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

Definition HexagonISelDAGToDAGHVX.cpp:879

ArrayRef< int > lo(ArrayRef< int > Vuu)

Definition HexagonISelDAGToDAGHVX.cpp:808

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

Definition HexagonISelDAGToDAGHVX.cpp:831

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)

Definition HexagonISelDAGToDAGHVX.cpp:925

MVT getSingleVT(MVT ElemTy) const

Definition HexagonISelDAGToDAGHVX.cpp:929

static SmallVector< uint32_t, 8 > completeToPerfect(ArrayRef< uint32_t > Completions, unsigned Width)

Definition HexagonISelDAGToDAGHVX.cpp:2008

const unsigned HwLen

Definition HexagonISelDAGToDAGHVX.cpp:923

HexagonDAGToDAGISel & ISel

Definition HexagonISelDAGToDAGHVX.cpp:920

SelectionDAG & DAG

Definition HexagonISelDAGToDAGHVX.cpp:921

const HexagonTargetLowering & Lower

Definition HexagonISelDAGToDAGHVX.cpp:919

void selectVAlign(SDNode *N)

Definition HexagonISelDAGToDAGHVX.cpp:2702

void selectExtractSubvector(SDNode *N)

Definition HexagonISelDAGToDAGHVX.cpp:2577

MVT getBoolVT() const

Definition HexagonISelDAGToDAGHVX.cpp:941

void selectRor(SDNode *N)

Definition HexagonISelDAGToDAGHVX.cpp:2678

void selectShuffle(SDNode *N)

Definition HexagonISelDAGToDAGHVX.cpp:2594

static SmallVector< uint32_t, 8 > getPerfectCompletions(ShuffleMask SM, unsigned Width)

Definition HexagonISelDAGToDAGHVX.cpp:1919

MVT getPairVT(MVT ElemTy) const

Definition HexagonISelDAGToDAGHVX.cpp:935

const HexagonSubtarget & HST

Definition HexagonISelDAGToDAGHVX.cpp:922

static std::optional< int > rotationDistance(ShuffleMask SM, unsigned WrapAt)

Definition HexagonISelDAGToDAGHVX.cpp:2041

This represents a list of ValueType's that has been intern'd by a SelectionDAG.

std::size_t operator()(SDValue V) const

Definition HexagonISelDAGToDAGHVX.cpp:2725