HexagonShuffler.cpp Source File (original) (raw)

29#include

30#include

31#include

32#include

34#define DEBUG_TYPE "hexagon-shuffle"

36using namespace llvm;

38namespace {

41class HexagonBid {

45 enum { MAX = 360360 };

46 unsigned Bid = 0;

48public:

49 HexagonBid() = default;

53 bool isSold() const { return (Bid >= MAX); }

55 HexagonBid &operator+=(const HexagonBid &B) {

56 Bid += B.Bid;

57 return *this;

58 }

59};

62class HexagonUnitAuction {

67public:

68 HexagonUnitAuction(unsigned cs = 0) : isSold(cs) {}

71 bool bid(unsigned B) {

73 unsigned b = B & ~isSold;

74 if (b) {

76 if (b & (1 << i)) {

78 Scores[i] += HexagonBid(b);

79 isSold |= Scores[i].isSold() << i;

80 }

81 return true;

82 } else

84 return false;

85 }

86};

88}

91 const unsigned SlotWeight = 8;

92 const unsigned MaskWeight = SlotWeight - 1;

94 unsigned Key = ((1u << s) & Units) != 0;

99 if (Key == 0 || Units == 0 || (SlotWeight * s >= 32))

100 return Weight = 0;

101

104 Weight = (1u << (SlotWeight * s)) * ((MaskWeight - Ctpop) << Cttz);

105 return Weight;

106}

107

110 unsigned s,

113

115 unsigned Lanes;

117

118 if (Units == 0 && Lanes == 0) {

119

120 Valid = false;

122 setLanes(0);

123 setLoad(false);

124 setStore(false);

125 } else {

126

127 Valid = true;

129 setLanes(Lanes);

132 }

133}

134

140

141static unsigned makeAllBits(unsigned startBit, unsigned Lanes)

142{

143 for (unsigned i = 1; i < Lanes; ++i)

144 startBit = (startBit << 1) | startBit;

145 return startBit;

146}

147

149 unsigned usedUnits) {

150 if (startIdx < hvxInsts.size()) {

151 if (!hvxInsts[startIdx].Units)

152 return checkHVXPipes(hvxInsts, startIdx + 1, usedUnits);

153 for (unsigned b = 0x1; b <= 0x8; b <<= 1) {

154 if ((hvxInsts[startIdx].Units & b) == 0)

155 continue;

156 unsigned allBits = makeAllBits(b, hvxInsts[startIdx].Lanes);

157 if ((allBits & usedUnits) == 0) {

158 if (checkHVXPipes(hvxInsts, startIdx + 1, usedUnits | allBits))

159 return true;

160 }

161 }

162 return false;

163 }

164 return true;

165}

166

174

180

182 unsigned S) {

184

185 Packet.push_back(PI);

186}

187

188

194

196 if (Summary.Slot1AOKLoc)

198 MCInst const &Inst = ISJ.getDesc();

203 const unsigned Units = ISJ.Core.getUnits();

204

208 "Instruction was restricted from being in slot 1"));

210 *Summary.Slot1AOKLoc, "Instruction can only be combined "

211 "with an ALU instruction in slot 1"));

212 ISJ.Core.setUnits(Units & ~Slot1Mask);

213 }

214 }

215 }

216}

217

219 HexagonPacketSummary const &Summary) {

220

221

222

223

224 if (!Summary.NoSlot1StoreLoc)

225 return;

226

227 bool AppliedRestriction = false;

228

230 MCInst const &Inst = ISJ.getDesc();

232 unsigned Units = ISJ.Core.getUnits();

234 AppliedRestriction = true;

236 Inst.getLoc(), "Instruction was restricted from being in slot 1"));

237 ISJ.Core.setUnits(Units & ~Slot1Mask);

238 }

239 }

240 }

241

242 if (AppliedRestriction)

244 std::make_pair(*Summary.NoSlot1StoreLoc,

245 "Instruction does not allow a store in slot 1"));

246}

247

249 const bool DoShuffle) {

250

251

252

255

257

258

259

260

268}

269

271

272 const bool HasMultipleBranches = Summary.branchInsts.size() > 1;

273 if (!HasMultipleBranches)

274 return;

275

276 if (Summary.branchInsts.size() > 2) {

278 return;

279 }

280

281 const static std::pair<unsigned, unsigned> jumpSlots[] = {

282 {8, 4}, {8, 2}, {8, 1}, {4, 2}, {4, 1}, {2, 1}};

283

284 for (std::pair<unsigned, unsigned> jumpSlot : jumpSlots) {

285

286 if (!(jumpSlot.first & Summary.branchInsts[0]->Core.getUnits()))

287 continue;

288

289

290 if (!(jumpSlot.second & Summary.branchInsts[1]->Core.getUnits()))

291 continue;

292

293

294 const HexagonPacket PacketSave = Packet;

295 Summary.branchInsts[0]->Core.setUnits(jumpSlot.first);

296 Summary.branchInsts[1]->Core.setUnits(jumpSlot.second);

297

298 const bool HasShuffledPacket = tryAuction(Summary).has_value();

299 if (HasShuffledPacket)

300 return;

301

302

303

304 Packet = PacketSave;

305 }

306

308}

309

313 if (!RequiresSlot)

314 ISJ.Core.setAllUnits();

315 }

316}

317

319 std::optional ShuffledPacket = tryAuction(Summary);

320

321 if (!ShuffledPacket) {

323 return false;

324 }

325

326

328

330 hvxInsts.clear();

331 for (const auto &I : *ShuffledPacket) {

333 inst.Units = I.CVI.getUnits();

334 inst.Lanes = I.CVI.getLanes();

335 if (inst.Units == 0)

336 continue;

338 }

339

340

341 if (hvxInsts.size() > 0) {

342 unsigned startIdx, usedUnits;

343 startIdx = usedUnits = 0x0;

344 if ( checkHVXPipes (hvxInsts, startIdx, usedUnits)) {

345

346 reportError(Twine("invalid instruction packet: slot error"));

347 return false;

348 }

349 }

350

351 Packet = *ShuffledPacket;

352

353 return true;

354}

355

357 HexagonPacketSummary const &Summary) {

358

359

360 static const unsigned slotFirstLoadStore = Slot1Mask;

361 static const unsigned slotLastLoadStore = Slot0Mask;

362 unsigned slotLoadStore = slotFirstLoadStore;

363

365 MCInst const &ID = ISJ->getDesc();

366

367 if (!ISJ->Core.getUnits())

368

369 return false;

370

371

373 if (Summary.loads == 1 && Summary.loads == Summary.memory &&

374 Summary.memops == 0)

375

376 switch (ID.getOpcode()) {

377 case Hexagon::V6_vgathermw:

378 case Hexagon::V6_vgathermh:

379 case Hexagon::V6_vgathermhw:

380 case Hexagon::V6_vgathermwq:

381 case Hexagon::V6_vgathermhq:

382 case Hexagon::V6_vgathermhwq:

383

384 break;

385 default:

386 ISJ->Core.setUnits(ISJ->Core.getUnits() & slotSingleLoad);

387 break;

388 }

390

391

392 if (slotLoadStore < slotLastLoadStore) {

393

394 reportError("invalid instruction packet: too many loads");

395 return false;

396 }

397

398 ISJ->Core.setUnits(ISJ->Core.getUnits() & slotLoadStore);

399

400 slotLoadStore >>= 1;

401 }

402 }

403

404

406 if (!Summary.store0) {

407 const bool PacketHasNoOnlySlot0 =

409 return I.Core.getUnits() == Slot0Mask &&

410 I.ID->getOpcode() != ID.getOpcode();

411 });

412 const bool SafeToMoveToSlot0 =

413 (Summary.loads == 0) ||

415

416 if (Summary.stores == 1 && SafeToMoveToSlot0)

417

418 ISJ->Core.setUnits(ISJ->Core.getUnits() & slotSingleStore);

419 else if (Summary.stores >= 1) {

420 if (slotLoadStore < slotLastLoadStore) {

421

422 reportError("invalid instruction packet: too many stores");

423 return false;

424 }

425

426 ISJ->Core.setUnits(ISJ->Core.getUnits() & slotLoadStore);

427

428 slotLoadStore >>= 1;

429 }

430 }

431 if (Summary.store1 && Summary.stores > 1) {

432

433 reportError("invalid instruction packet: too many stores");

434 return false;

435 }

436 }

437 }

438

439 return true;

440}

441

445 if ((SlotMask & (1 << SlotNum)) != 0)

447

449}

450

452 HexagonPacketSummary Summary = HexagonPacketSummary();

453

454

456 MCInst const &ID = ISJ->getDesc();

457

459 Summary.Slot1AOKLoc = ID.getLoc();

461 Summary.NoSlot1StoreLoc = ID.getLoc();

462

464 ++Summary.pSlot3Cnt;

465 Summary.PrefSlot3Inst = ISJ;

466 }

467 const unsigned ReservedSlots =

469 Summary.ReservedSlotMask |= ReservedSlots;

470 if (ReservedSlots != 0)

472 (Twine("Instruction has reserved slots: ") +

474

479 break;

482 Summary.branchInsts.push_back(ISJ);

483 break;

490 ++Summary.NonZCVIloads;

491 [[fallthrough]];

493 ++Summary.AllCVIloads;

494 [[fallthrough]];

496 ++Summary.loads;

497 ++Summary.memory;

500 ++Summary.load0;

502 Summary.branchInsts.push_back(ISJ);

503 break;

512 ++Summary.CVIstores;

513 [[fallthrough]];

515 ++Summary.stores;

516 ++Summary.memory;

519 ++Summary.store0;

520 break;

522 ++Summary.loads;

523 ++Summary.stores;

524 ++Summary.store1;

525 ++Summary.memops;

526 ++Summary.memory;

527 break;

529 ++Summary.memory;

530 Summary.branchInsts.push_back(ISJ);

531 break;

534 ++Summary.loads;

535 ++Summary.memory;

539 ++Summary.load0;

540 } else {

542 ++Summary.memory;

543 ++Summary.stores;

544 }

545 break;

547

550 Summary.branchInsts.push_back(ISJ);

551 break;

553 ++Summary.duplex;

554 MCInst const &Inst0 = *ID.getOperand(0).getInst();

555 MCInst const &Inst1 = *ID.getOperand(1).getInst();

557 Summary.branchInsts.push_back(ISJ);

559 Summary.branchInsts.push_back(ISJ);

561 Summary.branchInsts.push_back(ISJ);

563 Summary.branchInsts.push_back(ISJ);

564 break;

565 }

566 }

567 }

568 return Summary;

569}

570

572 HexagonPacketSummary const &Summary) const {

573

574 const unsigned ZCVIloads = Summary.AllCVIloads - Summary.NonZCVIloads;

575 const bool ValidHVXMem =

576 Summary.NonZCVIloads <= 1 && ZCVIloads <= 1 && Summary.CVIstores <= 1;

577 const bool InvalidPacket =

578 ((Summary.load0 > 1 || Summary.store0 > 1 || !ValidHVXMem) ||

579 (Summary.duplex > 1 || (Summary.duplex && Summary.memory)));

580

581 return !InvalidPacket;

582}

583

585 const bool DoShuffle) {

586

588 return (I.Core.getUnits() == Slot3Mask);

589 });

590 const bool NeedsPrefSlot3Shuffle = Summary.branchInsts.size() <= 1 &&

591 !HasOnlySlot3 && Summary.pSlot3Cnt == 1 &&

592 Summary.PrefSlot3Inst && DoShuffle;

593

594 if (!NeedsPrefSlot3Shuffle)

595 return;

596

597 HexagonInstr *PrefSlot3Inst = *Summary.PrefSlot3Inst;

598

599

600 const unsigned saveUnits = PrefSlot3Inst->Core.getUnits();

602 const bool HasShuffledPacket = tryAuction(Summary).has_value();

603 if (HasShuffledPacket)

604 return;

605

606 PrefSlot3Inst->Core.setUnits(saveUnits);

607}

608

609

613 return false;

614

616 reportError("invalid instruction packet");

617 return false;

618 }

619

620 if (RequireShuffle)

622

624}

625

626std::optionalHexagonShuffler::HexagonPacket

628 HexagonPacket PacketResult = Packet;

629 HexagonUnitAuction AuctionCore(Summary.ReservedSlotMask);

631

632 const bool ValidSlots =

634 return AuctionCore.bid(I.Core.getUnits());

635 });

636

638 dbgs() << "Shuffle attempt: " << (ValidSlots ? "passed" : "failed")

639 << "\n";

643 );

644

645 std::optional Res;

646 if (ValidSlots)

647 Res = PacketResult;

648

649 return Res;

650}

651

654

655

656 reportError("invalid instruction packet");

657 return false;

658 }

659

660

661 bool Ok = check();

662 if (size() > 1 && Ok)

663

665 ++nSlot) {

667 unsigned slotSkip, slotWeight;

668

669

670 for (ISJ = ISK = Packet.begin(), slotSkip = slotWeight = 0;

671 ISK != Packet.end(); ++ISK, ++slotSkip)

672 if (slotSkip < nSlot - emptySlots)

673

674 ++ISJ;

675 else

676

678

679 if (slotWeight)

680

681

682 std::stable_sort(ISJ, Packet.end());

683 else

684

685 ++emptySlots;

686 }

687

691 if (ISJ.CVI.isValid()) {

692 dbgs() << '/';

694 dbgs() << ISJ.CVI.getLanes();

695 }

696 dbgs() << ':'

698 << '\n';

699 } dbgs() << '\n';

700 );

701

702 return Ok;

703}

704

710

711

713 auto SM = Context.getSourceManager();

714 if (SM) {

716 const unsigned Units = I.Core.getUnits();

717

719 const std::string UnitsText = Units ? SlotMaskToText(Units) : "";

721 Twine("Instruction can utilize slots: ") +

722 UnitsText);

723 }

726 "Instruction does not require a slot");

727 }

728 }

729}

730

735 auto SM = Context.getSourceManager();

736 if (SM)

738 }

740 }

741}

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

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

#define HEXAGON_PACKET_SIZE

static const unsigned Slot1Mask

Definition HexagonShuffler.cpp:190

static const unsigned Slot0Mask

Definition HexagonShuffler.cpp:189

static std::string SlotMaskToText(unsigned SlotMask)

Definition HexagonShuffler.cpp:442

static const unsigned slotSingleLoad

Definition HexagonShuffler.cpp:192

static const unsigned slotSingleStore

Definition HexagonShuffler.cpp:193

static bool checkHVXPipes(const HVXInstsT &hvxInsts, unsigned startIdx, unsigned usedUnits)

Definition HexagonShuffler.cpp:148

static const unsigned Slot3Mask

Definition HexagonShuffler.cpp:191

SmallVector< struct CVIUnits, 8 > HVXInstsT

Definition HexagonShuffler.cpp:139

static unsigned makeAllBits(unsigned startBit, unsigned Lanes)

Definition HexagonShuffler.cpp:141

static bool isBranch(unsigned Opcode)

This file defines the SmallVector class.

HexagonCVIResource(MCInstrInfo const &MCII, MCSubtargetInfo const &STI, unsigned s, MCInst const *id)

Definition HexagonShuffler.cpp:108

static bool lessCore(const HexagonInstr &A, const HexagonInstr &B)

static bool lessCVI(const HexagonInstr &A, const HexagonInstr &B)

unsigned setWeight(unsigned s)

Definition HexagonShuffler.cpp:90

unsigned getUnits() const

HexagonResource(unsigned s)

void setUnits(unsigned s)

HexagonShuffler(MCContext &Context, bool ReportErrors, MCInstrInfo const &MCII, MCSubtargetInfo const &STI)

Definition HexagonShuffler.cpp:167

void reset()

Definition HexagonShuffler.cpp:175

bool isMemReorderDisabled() const

void permitNonSlot()

Definition HexagonShuffler.cpp:310

void restrictNoSlot1Store(HexagonPacketSummary const &Summary)

Definition HexagonShuffler.cpp:218

bool check(const bool RequireShuffle=true)

Check that the packet is legal and enforce relative insn order.

Definition HexagonShuffler.cpp:610

bool shuffle()

Definition HexagonShuffler.cpp:652

void restrictSlot1AOK(HexagonPacketSummary const &Summary)

Definition HexagonShuffler.cpp:195

bool restrictStoreLoadOrder(HexagonPacketSummary const &Summary)

Definition HexagonShuffler.cpp:356

void reportError(Twine const &Msg)

Definition HexagonShuffler.cpp:731

HexagonPacket::iterator iterator

void reportResourceError(HexagonPacketSummary const &Summary, StringRef Err)

Definition HexagonShuffler.cpp:705

HexagonPacketSummary GetPacketSummary()

Definition HexagonShuffler.cpp:451

bool ValidResourceUsage(HexagonPacketSummary const &Summary)

Definition HexagonShuffler.cpp:318

MCSubtargetInfo const & STI

void restrictBranchOrder(HexagonPacketSummary const &Summary)

Definition HexagonShuffler.cpp:270

void append(MCInst const &ID, MCInst const *Extender, unsigned S)

Definition HexagonShuffler.cpp:181

bool applySlotRestrictions(HexagonPacketSummary const &Summary, const bool DoShuffle)

Definition HexagonShuffler.cpp:248

void reportResourceUsage(HexagonPacketSummary const &Summary)

Definition HexagonShuffler.cpp:712

bool ValidPacketMemoryOps(HexagonPacketSummary const &Summary) const

Definition HexagonShuffler.cpp:571

void restrictPreferSlot3(HexagonPacketSummary const &Summary, const bool DoShuffle)

Definition HexagonShuffler.cpp:584

std::vector< std::pair< SMLoc, std::string > > AppliedRestrictions

std::optional< HexagonPacket > tryAuction(HexagonPacketSummary const &Summary)

Definition HexagonShuffler.cpp:627

Context object for machine code objects.

Instances of this class represent a single low-level machine instruction.

unsigned getOpcode() const

Return the opcode number for this descriptor.

Interface to description of machine instruction set.

Generic base class for all target subtargets.

void push_back(const T &Elt)

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

StringRef - Represent a constant reference to a string, i.e.

Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...

The instances of the Type class are immutable: once they are created, they are never changed.

raw_ostream & write_hex(unsigned long long N)

Output N in hexadecimal, without any prefix or padding.

unsigned ID

LLVM IR allows to use arbitrary numbers as calling convention identifiers.

@ TypeCVI_SCATTER_NEW_RST

bool isRestrictSlot1AOK(MCInstrInfo const &MCII, MCInst const &MCI)

Return whether the insn can be packaged only with an A-type insn in slot #1.

bool IsABranchingInst(MCInstrInfo const &MCII, MCSubtargetInfo const &STI, MCInst const &I)

unsigned getCVIResources(MCInstrInfo const &MCII, MCSubtargetInfo const &STI, MCInst const &MCI)

Return the resources used by this instruction.

MCInstrDesc const & getDesc(MCInstrInfo const &MCII, MCInst const &MCI)

bool prefersSlot3(MCInstrInfo const &MCII, MCInst const &MCI)

unsigned getType(MCInstrInfo const &MCII, MCInst const &MCI)

Return the Hexagon ISA class for the insn.

bool isImmext(MCInst const &MCI)

unsigned getOtherReservedSlots(MCInstrInfo const &MCII, MCSubtargetInfo const &STI, MCInst const &MCI)

Return the slots this instruction consumes in addition to the slot(s) it can execute out of.

bool requiresSlot(MCSubtargetInfo const &STI, MCInst const &MCI)

StringRef getName(MCInstrInfo const &MCII, MCInst const &MCI)

bool isRestrictNoSlot1Store(MCInstrInfo const &MCII, MCInst const &MCI)

This is an optimization pass for GlobalISel generic memory operations.

void stable_sort(R &&Range)

bool all_of(R &&range, UnaryPredicate P)

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

unsigned HexagonConvertUnits(unsigned ItinUnits, unsigned *Lanes)

LLVM_ATTRIBUTE_ALWAYS_INLINE DynamicAPInt & operator+=(DynamicAPInt &A, int64_t B)

std::string utostr(uint64_t X, bool isNeg=false)

constexpr int popcount(T Value) noexcept

Count the number of set bits in a value.

int countr_zero(T Val)

Count number of 0's from the least significant bit to the most stopping at the first 1.

bool any_of(R &&range, UnaryPredicate P)

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

LLVM_ABI raw_ostream & dbgs()

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

bool none_of(R &&Range, UnaryPredicate P)

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

FormattedNumber format_hex(uint64_t N, unsigned Width, bool Upper=false)

format_hex - Output N as a fixed width hexadecimal.

LLVM_ATTRIBUTE_VISIBILITY_DEFAULT AnalysisKey InnerAnalysisManagerProxy< AnalysisManagerT, IRUnitT, ExtraArgTs... >::Key

std::string join(IteratorT Begin, IteratorT End, StringRef Separator)

Joins the strings in the range [Begin, End), adding Separator between the elements.

unsigned Lanes

Definition HexagonShuffler.cpp:137

unsigned Units

Definition HexagonShuffler.cpp:136