CSKYConstantIslandPass.cpp Source File (original) (raw)

38#include "llvm/Config/llvm-config.h"

51#include

52#include

53#include

54#include

56using namespace llvm;

58#define DEBUG_TYPE "CSKY-constant-islands"

60 STATISTIC(NumCPEs, "Number of constpool entries");

61 STATISTIC(NumSplit, "Number of uncond branches inserted");

62 STATISTIC(NumCBrFixed, "Number of cond branches fixed");

63 STATISTIC(NumUBrFixed, "Number of uncond branches fixed");

65namespace {

100

101

102 unsigned Size = 0;

103

105

106 unsigned postOffset() const { return Offset + Size; }

107 };

108

109 std::vector BBInfo;

110

111

112

113

114 std::vector<MachineBasicBlock *> WaterList;

115

116

117

118 SmallPtrSet<MachineBasicBlock *, 4> NewWaterList;

119

120 using water_iterator = std::vector<MachineBasicBlock *>::iterator;

121

122

123

124

125

126

127

128

129

130

131

132

133

134 struct CPUser {

135 MachineInstr *MI;

136 MachineInstr *CPEMI;

137 MachineBasicBlock *HighWaterMark;

138

139 private:

140 unsigned MaxDisp;

141

142 public:

143 bool NegOk;

144

145 CPUser(MachineInstr *Mi, MachineInstr *Cpemi, unsigned Maxdisp, bool Neg)

146 : MI(Mi), CPEMI(Cpemi), MaxDisp(Maxdisp), NegOk(Neg) {

147 HighWaterMark = CPEMI->getParent();

148 }

149

150

151 unsigned getMaxDisp() const { return MaxDisp - 16; }

152

153 void setMaxDisp(unsigned Val) { MaxDisp = Val; }

154 };

155

156

157

158 std::vector CPUsers;

159

160

161

162

163 struct CPEntry {

164 MachineInstr *CPEMI;

165 unsigned CPI;

166 unsigned RefCount;

167

168 CPEntry(MachineInstr *Cpemi, unsigned Cpi, unsigned Rc = 0)

169 : CPEMI(Cpemi), CPI(Cpi), RefCount(Rc) {}

170 };

171

172

173

174

175

176

177 std::vector<std::vector> CPEntries;

178

179

180

181

182

183 struct ImmBranch {

184 MachineInstr *MI;

185 unsigned MaxDisp : 31;

187 unsigned IsCond : 1;

188 int UncondBr;

189

190 ImmBranch(MachineInstr *Mi, unsigned Maxdisp, bool Cond, int Ubr)

191 : MI(Mi), MaxDisp(Maxdisp), IsCond(Cond), UncondBr(Ubr) {}

192 };

193

194

195

196 std::vector ImmBranches;

197

198 const CSKYSubtarget *STI = nullptr;

199 const CSKYInstrInfo *TII;

200 CSKYMachineFunctionInfo *MFI;

201 MachineFunction *MF = nullptr;

202 MachineConstantPool *MCP = nullptr;

203

204 unsigned PICLabelUId;

205

206 void initPICLabelUId(unsigned UId) { PICLabelUId = UId; }

207

208 unsigned createPICLabelUId() { return PICLabelUId++; }

209

210public:

211 static char ID;

212

213 CSKYConstantIslands() : MachineFunctionPass(ID) {}

214

215 StringRef getPassName() const override { return "CSKY Constant Islands"; }

216

217 bool runOnMachineFunction(MachineFunction &F) override;

218

219 MachineFunctionProperties getRequiredProperties() const override {

220 return MachineFunctionProperties().setNoVRegs();

221 }

222

223 void doInitialPlacement(std::vector<MachineInstr *> &CPEMIs);

224 CPEntry *findConstPoolEntry(unsigned CPI, const MachineInstr *CPEMI);

225 Align getCPEAlign(const MachineInstr &CPEMI);

226 void initializeFunctionInfo(const std::vector<MachineInstr *> &CPEMIs);

227 unsigned getOffsetOf(MachineInstr *MI) const;

228 unsigned getUserOffset(CPUser &) const;

229 void dumpBBs();

230

231 bool isOffsetInRange(unsigned UserOffset, unsigned TrialOffset, unsigned Disp,

232 bool NegativeOK);

233 bool isOffsetInRange(unsigned UserOffset, unsigned TrialOffset,

234 const CPUser &U);

235

236 void computeBlockSize(MachineBasicBlock *MBB);

237 MachineBasicBlock *splitBlockBeforeInstr(MachineInstr &MI);

238 void updateForInsertedWaterBlock(MachineBasicBlock *NewBB);

239 void adjustBBOffsetsAfter(MachineBasicBlock *BB);

240 bool decrementCPEReferenceCount(unsigned CPI, MachineInstr *CPEMI);

241 int findInRangeCPEntry(CPUser &U, unsigned UserOffset);

242 bool findAvailableWater(CPUser &U, unsigned UserOffset,

243 water_iterator &WaterIter);

244 void createNewWater(unsigned CPUserIndex, unsigned UserOffset,

245 MachineBasicBlock *&NewMBB);

246 bool handleConstantPoolUser(unsigned CPUserIndex);

247 void removeDeadCPEMI(MachineInstr *CPEMI);

248 bool removeUnusedCPEntries();

249 bool isCPEntryInRange(MachineInstr *MI, unsigned UserOffset,

250 MachineInstr *CPEMI, unsigned Disp, bool NegOk,

251 bool DoDump = false);

252 bool isWaterInRange(unsigned UserOffset, MachineBasicBlock *Water, CPUser &U,

253 unsigned &Growth);

254 bool isBBInRange(MachineInstr *MI, MachineBasicBlock *BB, unsigned Disp);

255 bool fixupImmediateBr(ImmBranch &Br);

256 bool fixupConditionalBr(ImmBranch &Br);

257 bool fixupUnconditionalBr(ImmBranch &Br);

258};

259}

260

261char CSKYConstantIslands::ID = 0;

262

263bool CSKYConstantIslands::isOffsetInRange(unsigned UserOffset,

264 unsigned TrialOffset,

265 const CPUser &U) {

266 return isOffsetInRange(UserOffset, TrialOffset, U.getMaxDisp(), U.NegOk);

267}

268

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

270

272 for (unsigned J = 0, E = BBInfo.size(); J != E; ++J) {

273 const BasicBlockInfo &BBI = BBInfo[J];

275 << format(" size=%#x\n", BBInfo[J].Size);

276 }

277}

278#endif

279

280bool CSKYConstantIslands::runOnMachineFunction(MachineFunction &Mf) {

281 MF = &Mf;

284

286 << MCP->getConstants().size() << " CP entries, aligned to "

288

290 MFI = MF->getInfo();

291

292

294

295

296

298

299 bool MadeChange = false;

300

301

302

303 std::vector<MachineInstr *> CPEMIs;

305 doInitialPlacement(CPEMIs);

306

307

308 initPICLabelUId(CPEMIs.size());

309

310

311

312

313 initializeFunctionInfo(CPEMIs);

314 CPEMIs.clear();

316

317

318 MadeChange |= removeUnusedCPEntries();

319

320

321

322 unsigned NoCPIters = 0, NoBRIters = 0;

323 (void)NoBRIters;

324 while (true) {

325 LLVM_DEBUG(dbgs() << "Beginning CP iteration #" << NoCPIters << '\n');

326 bool CPChange = false;

327 for (unsigned I = 0, E = CPUsers.size(); I != E; ++I)

328 CPChange |= handleConstantPoolUser(I);

329 if (CPChange && ++NoCPIters > 30)

332

333

334

335 NewWaterList.clear();

336

337 LLVM_DEBUG(dbgs() << "Beginning BR iteration #" << NoBRIters << '\n');

338 bool BRChange = false;

339 for (unsigned I = 0, E = ImmBranches.size(); I != E; ++I)

340 BRChange |= fixupImmediateBr(ImmBranches[I]);

341 if (BRChange && ++NoBRIters > 30)

344 if (!CPChange && !BRChange)

345 break;

346 MadeChange = true;

347 }

348

350

351 BBInfo.clear();

352 WaterList.clear();

353 CPUsers.clear();

354 CPEntries.clear();

355 ImmBranches.clear();

356 return MadeChange;

357}

358

359

360

361void CSKYConstantIslands::doInitialPlacement(

362 std::vector<MachineInstr *> &CPEMIs) {

363

366

367

369

370

372

373

374

376

377

378

379

380

382 BB->end());

383

384

385

386 const std::vector &CPs = MCP->getConstants();

387

389 for (unsigned I = 0, E = CPs.size(); I != E; ++I) {

390 unsigned Size = CPs[I].getSizeInBytes(TD);

391 assert(Size >= 4 && "Too small constant pool entry");

392 Align Alignment = CPs[I].getAlign();

393

394

395 assert(isAligned(Alignment, Size) && "CP Entry not multiple of 4 bytes!");

396

397

398 unsigned LogAlign = Log2(Alignment);

400

401 MachineInstr *CPEMI =

406

407 CPEMIs.push_back(CPEMI);

408

409

410

411 for (unsigned A = LogAlign + 1; A <= Log2(MaxAlign); ++A)

412 if (InsPoint[A] == InsAt)

413 InsPoint[A] = CPEMI;

414

415 CPEntries.emplace_back(1, CPEntry(CPEMI, I));

416 ++NumCPEs;

417 LLVM_DEBUG(dbgs() << "Moved CPI#" << I << " to end of function, size = "

418 << Size << ", align = " << Alignment.value() << '\n');

419 }

421}

422

423

424

426

428

429 if (std::next(MBBI) == MBB->getParent()->end())

430 return false;

431

434 E = MBB->succ_end();

435 I != E; ++I)

436 if (*I == NextBB)

437 return true;

438

439 return false;

440}

441

442

443

444CSKYConstantIslands::CPEntry *

445CSKYConstantIslands::findConstPoolEntry(unsigned CPI,

446 const MachineInstr *CPEMI) {

447 std::vector &CPEs = CPEntries[CPI];

448

449

450 for (unsigned I = 0, E = CPEs.size(); I != E; ++I) {

451 if (CPEs[I].CPEMI == CPEMI)

452 return &CPEs[I];

453 }

454 return nullptr;

455}

456

457

458

459Align CSKYConstantIslands::getCPEAlign(const MachineInstr &CPEMI) {

461

463 assert(CPI < MCP->getConstants().size() && "Invalid constant pool index.");

465}

466

467

468

469

470void CSKYConstantIslands::initializeFunctionInfo(

471 const std::vector<MachineInstr *> &CPEMIs) {

472 BBInfo.clear();

474

475

476

477

478

480 computeBlockSize(&*I);

481

482

483 adjustBBOffsetsAfter(&MF->front());

484

485

486 for (MachineBasicBlock &MBB : *MF) {

487

488

490 WaterList.push_back(&MBB);

491 for (MachineInstr &MI : MBB) {

492 if (MI.isDebugInstr())

493 continue;

494

495 int Opc = MI.getOpcode();

496 if (MI.isBranch() && .isIndirectBranch()) {

497 bool IsCond = MI.isConditionalBranch();

498 unsigned Bits = 0;

499 unsigned Scale = 1;

500 int UOpc = CSKY::BR32;

501

502 switch (MI.getOpcode()) {

503 case CSKY::BR16:

504 case CSKY::BF16:

505 case CSKY::BT16:

507 Scale = 2;

508 break;

509 default:

511 Scale = 2;

512 break;

513 }

514

515

516 unsigned MaxOffs = ((1 << (Bits - 1)) - 1) * Scale;

517 ImmBranches.push_back(ImmBranch(&MI, MaxOffs, IsCond, UOpc));

518 }

519

520 if (Opc == CSKY::CONSTPOOL_ENTRY)

521 continue;

522

523

524 for (unsigned Op = 0, E = MI.getNumOperands(); Op != E; ++Op)

525 if (MI.getOperand(Op).isCPI()) {

526

527

528

529

530 unsigned Bits = 0;

531 unsigned Scale = 1;

532 bool NegOk = false;

533

534 switch (Opc) {

535 default:

536 llvm_unreachable("Unknown addressing mode for CP reference!");

537 case CSKY::MOVIH32:

538 case CSKY::ORI32:

539 continue;

540 case CSKY::PseudoTLSLA32:

541 case CSKY::JSRI32:

542 case CSKY::JMPI32:

543 case CSKY::LRW32:

544 case CSKY::LRW32_Gen:

546 Scale = 4;

547 break;

548 case CSKY::f2FLRW_S:

549 case CSKY::f2FLRW_D:

551 Scale = 4;

552 break;

553 case CSKY::GRS32:

555 Scale = 2;

556 NegOk = true;

557 break;

558 }

559

560 unsigned CPI = MI.getOperand(Op).getIndex();

561 MachineInstr *CPEMI = CPEMIs[CPI];

562 unsigned MaxOffs = ((1 << Bits) - 1) * Scale;

563 CPUsers.push_back(CPUser(&MI, CPEMI, MaxOffs, NegOk));

564

565

566 CPEntry *CPE = findConstPoolEntry(CPI, CPEMI);

567 assert(CPE && "Cannot find a corresponding CPEntry!");

568 CPE->RefCount++;

569 }

570 }

571 }

572}

573

574

575

576void CSKYConstantIslands::computeBlockSize(MachineBasicBlock *MBB) {

577 BasicBlockInfo &BBI = BBInfo[MBB->getNumber()];

578 BBI.Size = 0;

579

580 for (const MachineInstr &MI : *MBB)

582}

583

584

585

586

587unsigned CSKYConstantIslands::getOffsetOf(MachineInstr *MI) const {

588 MachineBasicBlock *MBB = MI->getParent();

589

590

591

592

594

595

597 assert(I != MBB->end() && "Didn't find MI in its own basic block?");

599 }

601}

602

603

604

607 return LHS->getNumber() < RHS->getNumber();

608}

609

610

611

612

613void CSKYConstantIslands::updateForInsertedWaterBlock(

614 MachineBasicBlock *NewBB) {

615

617

618

619

620 BBInfo.insert(BBInfo.begin() + NewBB->getNumber(), BasicBlockInfo());

621

622

623

625 WaterList.insert(IP, NewBB);

626}

627

628unsigned CSKYConstantIslands::getUserOffset(CPUser &U) const {

629 unsigned UserOffset = getOffsetOf(U.MI);

630

631 UserOffset &= ~3u;

632

633 return UserOffset;

634}

635

636

637

638

639MachineBasicBlock *

640CSKYConstantIslands::splitBlockBeforeInstr(MachineInstr &MI) {

641 MachineBasicBlock *OrigBB = MI.getParent();

642

643

644 MachineBasicBlock *NewBB =

645 MF->CreateMachineBasicBlock(OrigBB->getBasicBlock());

647 MF->insert(MBBI, NewBB);

648

649

650 NewBB->splice(NewBB->end(), OrigBB, MI, OrigBB->end());

651

652

653

654

655

656

657

659 ++NumSplit;

660

661

663

664

666

667

668

669

670 MF->RenumberBlocks(NewBB);

671

672

673

674 BBInfo.insert(BBInfo.begin() + NewBB->getNumber(), BasicBlockInfo());

675

676

677

678

679

681 MachineBasicBlock *WaterBB = *IP;

682 if (WaterBB == OrigBB)

683 WaterList.insert(std::next(IP), NewBB);

684 else

685 WaterList.insert(IP, OrigBB);

686 NewWaterList.insert(OrigBB);

687

688

689

690

691

692

693 computeBlockSize(OrigBB);

694

695

696

697 computeBlockSize(NewBB);

698

699

700 adjustBBOffsetsAfter(OrigBB);

701

702 return NewBB;

703}

704

705

706

707

708bool CSKYConstantIslands::isOffsetInRange(unsigned UserOffset,

709 unsigned TrialOffset,

710 unsigned MaxDisp, bool NegativeOK) {

711 if (UserOffset <= TrialOffset) {

712

713 if (TrialOffset - UserOffset <= MaxDisp)

714 return true;

715 } else if (NegativeOK) {

716 if (UserOffset - TrialOffset <= MaxDisp)

717 return true;

718 }

719 return false;

720}

721

722

723

724

725

726bool CSKYConstantIslands::isWaterInRange(unsigned UserOffset,

727 MachineBasicBlock *Water, CPUser &U,

728 unsigned &Growth) {

729 unsigned CPEOffset = BBInfo[Water->getNumber()].postOffset();

730 unsigned NextBlockOffset;

731 Align NextBlockAlignment;

733 if (NextBlock == MF->end()) {

734 NextBlockOffset = BBInfo[Water->getNumber()].postOffset();

735 NextBlockAlignment = Align(4);

736 } else {

737 NextBlockOffset = BBInfo[NextBlock->getNumber()].Offset;

738 NextBlockAlignment = NextBlock->getAlignment();

739 }

740 unsigned Size = U.CPEMI->getOperand(2).getImm();

741 unsigned CPEEnd = CPEOffset + Size;

742

743

744

745

746 if (CPEEnd > NextBlockOffset) {

747 Growth = CPEEnd - NextBlockOffset;

748

749

751

752

753

754

755 if (CPEOffset < UserOffset)

756 UserOffset += Growth;

757 } else

758

759 Growth = 0;

760

761 return isOffsetInRange(UserOffset, CPEOffset, U);

762}

763

764

765

766bool CSKYConstantIslands::isCPEntryInRange(MachineInstr *MI,

767 unsigned UserOffset,

768 MachineInstr *CPEMI,

769 unsigned MaxDisp, bool NegOk,

770 bool DoDump) {

771 unsigned CPEOffset = getOffsetOf(CPEMI);

772

773 if (DoDump) {

775 unsigned Block = MI->getParent()->getNumber();

776 const BasicBlockInfo &BBI = BBInfo[Block];

778 << " max delta=" << MaxDisp

779 << format(" insn address=%#x", UserOffset) << " in "

782 << format("CPE address=%#x offset=%+d: ", CPEOffset,

783 int(CPEOffset - UserOffset));

784 });

785 }

786

787 return isOffsetInRange(UserOffset, CPEOffset, MaxDisp, NegOk);

788}

789

790#ifndef NDEBUG

791

792

794 if (MBB->pred_size() != 1 || MBB->succ_size() != 1)

795 return false;

799 if (PredMI->getOpcode() == CSKY::BR32 )

801 return false;

802}

803#endif

804

805void CSKYConstantIslands::adjustBBOffsetsAfter(MachineBasicBlock *BB) {

806 unsigned BBNum = BB->getNumber();

807 for (unsigned I = BBNum + 1, E = MF->getNumBlockIDs(); I < E; ++I) {

808

809

810 unsigned Offset = BBInfo[I - 1].Offset + BBInfo[I - 1].Size;

811 BBInfo[I].Offset = Offset;

812 }

813}

814

815

816

817

818

819bool CSKYConstantIslands::decrementCPEReferenceCount(unsigned CPI,

820 MachineInstr *CPEMI) {

821

822 CPEntry *CPE = findConstPoolEntry(CPI, CPEMI);

823 assert(CPE && "Unexpected!");

824 if (--CPE->RefCount == 0) {

825 removeDeadCPEMI(CPEMI);

826 CPE->CPEMI = nullptr;

827 --NumCPEs;

828 return true;

829 }

830 return false;

831}

832

833

834

835

836

837

838

839int CSKYConstantIslands::findInRangeCPEntry(CPUser &U, unsigned UserOffset) {

840 MachineInstr *UserMI = U.MI;

841 MachineInstr *CPEMI = U.CPEMI;

842

843

844 if (isCPEntryInRange(UserMI, UserOffset, CPEMI, U.getMaxDisp(), U.NegOk,

845 true)) {

847 return 1;

848 }

849

850

852 std::vector &CPEs = CPEntries[CPI];

853 for (unsigned I = 0, E = CPEs.size(); I != E; ++I) {

854

855 if (CPEs[I].CPEMI == CPEMI)

856 continue;

857

858 if (CPEs[I].CPEMI == nullptr)

859 continue;

860 if (isCPEntryInRange(UserMI, UserOffset, CPEs[I].CPEMI, U.getMaxDisp(),

861 U.NegOk)) {

862 LLVM_DEBUG(dbgs() << "Replacing CPE#" << CPI << " with CPE#"

863 << CPEs[I].CPI << "\n");

864

865 U.CPEMI = CPEs[I].CPEMI;

866

867 for (unsigned J = 0, E = UserMI->getNumOperands(); J != E; ++J)

870 break;

871 }

872

873 CPEs[I].RefCount++;

874

875

876 return decrementCPEReferenceCount(CPI, CPEMI) ? 2 : 1;

877 }

878 }

879 return 0;

880}

881

882

883

885 unsigned Bits, Scale;

886

887 switch (Opc) {

888 case CSKY::BR16:

889 Bits = 10;

890 Scale = 2;

891 break;

892 case CSKY::BR32:

893 Bits = 16;

894 Scale = 2;

895 break;

896 default:

898 }

899

900 unsigned MaxOffs = ((1 << (Bits - 1)) - 1) * Scale;

901 return MaxOffs;

902}

903

904

905

906

907

908

909

910

911

912bool CSKYConstantIslands::findAvailableWater(CPUser &U, unsigned UserOffset,

913 water_iterator &WaterIter) {

914 if (WaterList.empty())

915 return false;

916

917 unsigned BestGrowth = ~0u;

918 for (water_iterator IP = std::prev(WaterList.end()), B = WaterList.begin();;

919 --IP) {

920 MachineBasicBlock *WaterBB = *IP;

921

922

923

924

925

926

927

928

929 unsigned Growth;

930 if (isWaterInRange(UserOffset, WaterBB, U, Growth) &&

931 (WaterBB->getNumber() < U.HighWaterMark->getNumber() ||

932 NewWaterList.count(WaterBB)) &&

933 Growth < BestGrowth) {

934

935 BestGrowth = Growth;

936 WaterIter = IP;

938 << " Growth=" << Growth << '\n');

939

940

941 if (BestGrowth == 0)

942 return true;

943 }

944 if (IP == B)

945 break;

946 }

947 return BestGrowth != ~0u;

948}

949

950

951

952

953

954

955

956

957void CSKYConstantIslands::createNewWater(unsigned CPUserIndex,

958 unsigned UserOffset,

959 MachineBasicBlock *&NewMBB) {

960 CPUser &U = CPUsers[CPUserIndex];

961 MachineInstr *UserMI = U.MI;

962 MachineInstr *CPEMI = U.CPEMI;

963 MachineBasicBlock *UserMBB = UserMI->getParent();

964 const BasicBlockInfo &UserBBI = BBInfo[UserMBB->getNumber()];

965

966

967

969

970 unsigned Delta = 4;

971

972 unsigned CPEOffset = UserBBI.postOffset() + Delta;

973

974 if (isOffsetInRange(UserOffset, CPEOffset, U)) {

976 << format(", expected CPE offset %#x\n", CPEOffset));

978

979

980

981

982

983

984

985 int UncondBr = CSKY::BR32;

990 ImmBranches.push_back(

991 ImmBranch(&UserMBB->back(), MaxDisp, false, UncondBr));

993 adjustBBOffsetsAfter(UserMBB);

994 return;

995 }

996 }

997

998

999

1000

1001

1002

1003 const Align Align = MF->getAlignment();

1004 unsigned BaseInsertOffset = UserOffset + U.getMaxDisp();

1006 BaseInsertOffset));

1007

1008

1009

1010

1011 BaseInsertOffset -= 4;

1012

1014 << " la=" << Log2(Align) << '\n');

1015

1016

1017

1018

1019

1020 if (BaseInsertOffset + 8 >= UserBBI.postOffset()) {

1021 BaseInsertOffset = UserBBI.postOffset() - 8;

1023 }

1024 unsigned EndInsertOffset =

1027 ++MI;

1028 unsigned CPUIndex = CPUserIndex + 1;

1029 unsigned NumCPUsers = CPUsers.size();

1031 Offset < BaseInsertOffset;

1033 assert(MI != UserMBB->end() && "Fell off end of block");

1034 if (CPUIndex < NumCPUsers && CPUsers[CPUIndex].MI == MI) {

1035 CPUser &U = CPUsers[CPUIndex];

1036 if (!isOffsetInRange(Offset, EndInsertOffset, U)) {

1037

1038 BaseInsertOffset -= Align.value();

1039 EndInsertOffset -= Align.value();

1040 }

1041

1042

1043

1044

1045 EndInsertOffset += U.CPEMI->getOperand(2).getImm();

1046 CPUIndex++;

1047 }

1048 }

1049

1050 NewMBB = splitBlockBeforeInstr(*--MI);

1051}

1052

1053

1054

1055

1056

1057bool CSKYConstantIslands::handleConstantPoolUser(unsigned CPUserIndex) {

1058 CPUser &U = CPUsers[CPUserIndex];

1059 MachineInstr *UserMI = U.MI;

1060 MachineInstr *CPEMI = U.CPEMI;

1063

1064 unsigned UserOffset = getUserOffset(U);

1065

1066

1067

1068 int result = findInRangeCPEntry(U, UserOffset);

1069 if (result == 1)

1070 return false;

1071 if (result == 2)

1072 return true;

1073

1074

1075 MachineBasicBlock *NewIsland = MF->CreateMachineBasicBlock();

1076 MachineBasicBlock *NewMBB;

1077 water_iterator IP;

1078 if (findAvailableWater(U, UserOffset, IP)) {

1080 MachineBasicBlock *WaterBB = *IP;

1081

1082

1083

1084

1085 if (NewWaterList.erase(WaterBB))

1086 NewWaterList.insert(NewIsland);

1087

1088

1090 } else {

1092 createNewWater(CPUserIndex, UserOffset, NewMBB);

1093

1094

1095

1096

1097

1098

1099 MachineBasicBlock *WaterBB = &*--NewMBB->getIterator();

1100 IP = llvm::find(WaterList, WaterBB);

1101 if (IP != WaterList.end())

1102 NewWaterList.erase(WaterBB);

1103

1104

1105 NewWaterList.insert(NewIsland);

1106 }

1107

1108

1109

1110

1111

1112 if (IP != WaterList.end())

1113 WaterList.erase(IP);

1114

1115

1116 MF->insert(NewMBB->getIterator(), NewIsland);

1117

1118

1119 updateForInsertedWaterBlock(NewIsland);

1120

1121

1122 decrementCPEReferenceCount(CPI, CPEMI);

1123

1124

1125

1126 unsigned ID = createPICLabelUId();

1127

1128

1129

1130 U.HighWaterMark = NewIsland;

1135 CPEntries[CPI].push_back(CPEntry(U.CPEMI, ID, 1));

1136 ++NumCPEs;

1137

1138

1140

1141

1143 adjustBBOffsetsAfter(&*--NewIsland->getIterator());

1144

1145

1149 break;

1150 }

1151

1153 dbgs() << " Moved CPE to #" << ID << " CPI=" << CPI

1154 << format(" offset=%#x\n", BBInfo[NewIsland->getNumber()].Offset));

1155

1156 return true;

1157}

1158

1159

1160

1161void CSKYConstantIslands::removeDeadCPEMI(MachineInstr *CPEMI) {

1162 MachineBasicBlock *CPEBB = CPEMI->getParent();

1166

1167 if (CPEBB->empty()) {

1168 BBInfo[CPEBB->getNumber()].Size = 0;

1169

1170

1172 } else {

1173

1175 }

1176

1177 adjustBBOffsetsAfter(CPEBB);

1178

1179

1180

1182

1183}

1184

1185

1186

1187bool CSKYConstantIslands::removeUnusedCPEntries() {

1188 unsigned MadeChange = false;

1189 for (unsigned I = 0, E = CPEntries.size(); I != E; ++I) {

1190 std::vector &CPEs = CPEntries[I];

1191 for (unsigned J = 0, Ee = CPEs.size(); J != Ee; ++J) {

1192 if (CPEs[J].RefCount == 0 && CPEs[J].CPEMI) {

1193 removeDeadCPEMI(CPEs[J].CPEMI);

1194 CPEs[J].CPEMI = nullptr;

1195 MadeChange = true;

1196 }

1197 }

1198 }

1199 return MadeChange;

1200}

1201

1202

1203

1204bool CSKYConstantIslands::isBBInRange(MachineInstr *MI,

1205 MachineBasicBlock *DestBB,

1206 unsigned MaxDisp) {

1207 unsigned BrOffset = getOffsetOf(MI);

1208 unsigned DestOffset = BBInfo[DestBB->getNumber()].Offset;

1209

1212 << " max delta=" << MaxDisp << " from " << getOffsetOf(MI)

1213 << " to " << DestOffset << " offset "

1214 << int(DestOffset - BrOffset) << "\t" << *MI);

1215

1216 if (BrOffset <= DestOffset) {

1217

1218 if (DestOffset - BrOffset <= MaxDisp)

1219 return true;

1220 } else {

1221 if (BrOffset - DestOffset <= MaxDisp)

1222 return true;

1223 }

1224 return false;

1225}

1226

1227

1228

1229bool CSKYConstantIslands::fixupImmediateBr(ImmBranch &Br) {

1230 MachineInstr *MI = Br.MI;

1232

1233

1234 if (isBBInRange(MI, DestBB, Br.MaxDisp))

1235 return false;

1236

1237 if (!Br.IsCond)

1238 return fixupUnconditionalBr(Br);

1239 return fixupConditionalBr(Br);

1240}

1241

1242

1243

1244

1245

1246bool CSKYConstantIslands::fixupUnconditionalBr(ImmBranch &Br) {

1247 MachineInstr *MI = Br.MI;

1248 MachineBasicBlock *MBB = MI->getParent();

1249

1252

1253

1254 Br.MaxDisp = ((1 << (26 - 1)) - 1) * 2;

1255 MI->setDesc(TII->get(CSKY::BSR32_BR));

1257 adjustBBOffsetsAfter(MBB);

1258 ++NumUBrFixed;

1259

1261

1262 return true;

1263}

1264

1265

1266

1267

1268bool CSKYConstantIslands::fixupConditionalBr(ImmBranch &Br) {

1269 MachineInstr *MI = Br.MI;

1271

1274 Cond.push_back(MI->getOperand(0));

1276

1277

1278

1279

1280

1281

1282

1283

1284

1285

1286

1287

1288 MachineBasicBlock *MBB = MI->getParent();

1289 MachineInstr *BMI = &MBB->back();

1291

1292 ++NumCBrFixed;

1293 if (BMI != MI) {

1296

1297

1298

1299

1300

1301

1302

1304 if (isBBInRange(MI, NewDest, Br.MaxDisp)) {

1306 dbgs() << " Invert Bcc condition and swap its destination with "

1307 << *BMI);

1309 MI->getOperand(MI->getNumExplicitOperands() - 1).setMBB(NewDest);

1310

1312 return true;

1313 }

1314 }

1315 }

1316

1317 if (NeedSplit) {

1318 splitBlockBeforeInstr(*MI);

1319

1320

1324

1325

1326

1327

1329 std::next(MBB->getIterator())->removeSuccessor(DestBB);

1330 }

1332

1334 << " also invert condition and change dest. to "

1336

1337

1338

1339

1341 .addReg(MI->getOperand(0).getReg())

1343

1349 ImmBranches.push_back(ImmBranch(&MBB->back(), MaxDisp, false, Br.UncondBr));

1350

1351

1353 MI->eraseFromParent();

1354 adjustBBOffsetsAfter(MBB);

1355 return true;

1356}

1357

1358

1360 return new CSKYConstantIslands();

1361}

1362

1364 "CSKY constant island placement and branch shortening pass",

1365 false, false)

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

const TargetInstrInfo & TII

static unsigned getUnconditionalBrDisp(int Opc)

getUnconditionalBrDisp - Returns the maximum displacement that can fit in the specific unconditional ...

MachineBasicBlock MachineBasicBlock::iterator MBBI

static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")

static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")

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

static bool bbHasFallthrough(MachineBasicBlock *MBB)

BBHasFallthrough - Return true if the specified basic block can fallthrough into the block immediatel...

Definition CSKYConstantIslandPass.cpp:425

static bool bbIsJumpedOver(MachineBasicBlock *MBB)

BBIsJumpedOver - Return true of the specified basic block's only predecessor unconditionally branches...

Definition CSKYConstantIslandPass.cpp:793

static bool compareMbbNumbers(const MachineBasicBlock *LHS, const MachineBasicBlock *RHS)

CompareMBBNumbers - Little predicate function to sort the WaterList by MBB ID.

Definition CSKYConstantIslandPass.cpp:605

#define LLVM_PREFERRED_TYPE(T)

\macro LLVM_PREFERRED_TYPE Adjust type of bit-field in debug info.

#define LLVM_DUMP_METHOD

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

This file contains the declarations for the subclasses of Constant, which represent the different fla...

This file declares the MachineConstantPool class which is an abstract constant pool to keep track of ...

#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)

const SmallVectorImpl< MachineOperand > & Cond

This file defines the SmallSet class.

This file defines the SmallVector class.

This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...

#define STATISTIC(VARNAME, DESC)

const CSKYInstrInfo * getInstrInfo() const override

FunctionPass class - This class is used to implement most global optimizations.

const MCInstrDesc & get(unsigned Opcode) const

Return the machine instruction descriptor that corresponds to the specified instruction opcode.

LLVM_ABI void transferSuccessors(MachineBasicBlock *FromMBB)

Transfers all the successors from MBB to this machine basic block (i.e., copies all the successors Fr...

int getNumber() const

MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...

void push_back(MachineInstr *MI)

const BasicBlock * getBasicBlock() const

Return the LLVM basic block that this instance corresponded to originally.

void setAlignment(Align A)

Set alignment of the basic block.

LLVM_ABI void dump() const

LLVM_ABI void addSuccessor(MachineBasicBlock *Succ, BranchProbability Prob=BranchProbability::getUnknown())

Add Succ as a successor of this MachineBasicBlock.

SmallVectorImpl< MachineBasicBlock * >::iterator succ_iterator

MachineInstrBundleIterator< MachineInstr, true > reverse_iterator

const MachineFunction * getParent() const

Return the MachineFunction containing this basic block.

void splice(iterator Where, MachineBasicBlock *Other, iterator From)

Take an instruction from MBB 'Other' at the position From, and insert it into this MBB right before '...

Align getAlignment() const

Return alignment of the basic block.

MachineInstrBundleIterator< MachineInstr > iterator

Align getConstantPoolAlign() const

Return the alignment required by the whole constant pool, of which the first element must be aligned.

const std::vector< MachineConstantPoolEntry > & getConstants() const

bool isEmpty() const

isEmpty - Return true if this constant pool contains no constants.

MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...

const TargetSubtargetInfo & getSubtarget() const

getSubtarget - Return the subtarget for which this machine code is being compiled.

void ensureAlignment(Align A)

ensureAlignment - Make sure the function is at least A bytes aligned.

void push_back(MachineBasicBlock *MBB)

MachineRegisterInfo & getRegInfo()

getRegInfo - Return information about the registers currently in use.

const DataLayout & getDataLayout() const

Return the DataLayout attached to the Module associated to this MF.

unsigned getNumBlockIDs() const

getNumBlockIDs - Return the number of MBB ID's allocated.

BasicBlockListType::iterator iterator

Ty * getInfo()

getInfo - Keep track of various per-function pieces of information for backends that would like to do...

MachineConstantPool * getConstantPool()

getConstantPool - Return the constant pool object for the current function.

void RenumberBlocks(MachineBasicBlock *MBBFrom=nullptr)

RenumberBlocks - This discards all of the MachineBasicBlock numbers and recomputes them.

const MachineBasicBlock & front() const

MachineBasicBlock * CreateMachineBasicBlock(const BasicBlock *BB=nullptr, std::optional< UniqueBBID > BBID=std::nullopt)

CreateMachineInstr - Allocate a new MachineInstr.

BasicBlockListType::const_iterator const_iterator

const MachineInstrBuilder & addImm(int64_t Val) const

Add a new immediate operand.

const MachineInstrBuilder & addConstantPoolIndex(unsigned Idx, int Offset=0, unsigned TargetFlags=0) const

const MachineInstrBuilder & addReg(Register RegNo, unsigned flags=0, unsigned SubReg=0) const

Add a new virtual register operand.

const MachineInstrBuilder & addMBB(MachineBasicBlock *MBB, unsigned TargetFlags=0) const

MachineInstr * getInstr() const

If conversion operators fail, use this method to get the MachineInstr explicitly.

Representation of each machine instruction.

unsigned getOpcode() const

Returns the opcode of this MachineInstr.

const MachineBasicBlock * getParent() const

unsigned getNumOperands() const

Retuns the total number of operands.

LLVM_ABI unsigned getNumExplicitOperands() const

Returns the number of non-implicit operands.

bool isUnconditionalBranch(QueryType Type=AnyInBundle) const

Return true if this is a branch which always transfers control flow to some other block.

LLVM_ABI void eraseFromParent()

Unlink 'this' from the containing basic block and delete it.

const MachineOperand & getOperand(unsigned i) const

MachineBasicBlock * getMBB() const

bool isCPI() const

isCPI - Tests if this is a MO_ConstantPoolIndex operand.

void setMBB(MachineBasicBlock *MBB)

static MachineOperand CreateImm(int64_t Val)

void invalidateLiveness()

invalidateLiveness - Indicates that register liveness is no longer being tracked accurately.

bool erase(PtrType Ptr)

Remove pointer from the set.

size_type count(ConstPtrType Ptr) const

count - Return 1 if the specified pointer is in the set, 0 otherwise.

std::pair< iterator, bool > insert(PtrType Ptr)

Inserts Ptr if and only if there is no element in the container equal to Ptr.

virtual bool reverseBranchCondition(SmallVectorImpl< MachineOperand > &Cond) const

Reverses the branch condition of the specified condition list, returning false on success and true if...

virtual MachineBasicBlock * getBranchDestBlock(const MachineInstr &MI) const

virtual unsigned getInstSizeInBytes(const MachineInstr &MI) const

Returns the size in bytes of the specified MachineInstr, or ~0U when this function is not implemented...

self_iterator getIterator()

#define llvm_unreachable(msg)

Marks that the current location is not supposed to be reachable.

constexpr char Align[]

Key for Kernel::Arg::Metadata::mAlign.

unsigned ID

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

This is an optimization pass for GlobalISel generic memory operations.

auto find(R &&Range, const T &Val)

Provide wrappers to std::find 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.

MachineInstrBuilder BuildMI(MachineFunction &MF, const MIMetadata &MIMD, const MCInstrDesc &MCID)

Builder interface. Specify how to create the initial instruction itself.

bool isAligned(Align Lhs, uint64_t SizeInBytes)

Checks that SizeInBytes is a multiple of the alignment.

LLVM_ABI raw_ostream & dbgs()

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

LLVM_ABI void report_fatal_error(Error Err, bool gen_crash_diag=true)

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.

uint64_t offsetToAlignment(uint64_t Value, Align Alignment)

Returns the offset to the next integer (mod 2**64) that is greater than or equal to Value and is a mu...

auto lower_bound(R &&Range, T &&Value)

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

FunctionPass * createCSKYConstantIslandPass()

Returns a pass that converts branches to long branches.

Definition CSKYConstantIslandPass.cpp:1359

DWARFExpression::Operation Op

unsigned Log2(Align A)

Returns the log2 of the alignment.

LLVM_ABI Printable printMBBReference(const MachineBasicBlock &MBB)

Prints a machine basic block reference.

constexpr uint64_t value() const

This is a hole in the type system and should not be abused.

BasicBlockInfo - Information about the offset and size of a single basic block.

unsigned Size

Size - Size of the basic block in bytes.

unsigned postOffset(Align Alignment=Align(1)) const

Compute the offset immediately following this block.

unsigned Offset

Offset - Distance from the beginning of the function to the beginning of this basic block.