ARMConstantIslandPass.cpp Source File (original) (raw)

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

51#include

52#include

53#include

54#include

55#include

56#include

58using namespace llvm;

60#define DEBUG_TYPE "arm-cp-islands"

62#define ARM_CP_ISLANDS_OPT_NAME \

63 "ARM constant island placement and branch shortening pass"

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

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

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

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

68 STATISTIC(NumTBs, "Number of table branches generated");

69 STATISTIC(NumT2CPShrunk, "Number of Thumb2 constantpool instructions shrunk");

70 STATISTIC(NumT2BrShrunk, "Number of Thumb2 immediate branches shrunk");

71 STATISTIC(NumCBZ, "Number of CBZ / CBNZ formed");

72 STATISTIC(NumJTMoved, "Number of jump table destination blocks moved");

73 STATISTIC(NumJTInserted, "Number of jump table intermediate blocks inserted");

74 STATISTIC(NumLEInserted, "Number of LE backwards branches inserted");

78 cl::desc("Adjust basic block layout to better use TB[BH]"));

82 cl::desc("The max number of iteration for converge"));

86 cl::desc("Use compressed jump tables in Thumb-1 by synthesizing an "

87 "equivalent to the TBB/TBH instructions"));

89namespace {

100

101

103 std::unique_ptr BBUtils = nullptr;

104

105

106

107

108 std::vector<MachineBasicBlock*> WaterList;

109

110

111

113

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

115

116

117

118

119

120

121

122

123

124

125

126

127

128 struct CPUser {

132 unsigned MaxDisp;

133 bool NegOk;

134 bool IsSoImm;

135 bool KnownAlignment = false;

136

138 bool neg, bool soimm)

139 : MI(mi), CPEMI(cpemi), MaxDisp(maxdisp), NegOk(neg), IsSoImm(soimm) {

140 HighWaterMark = CPEMI->getParent();

141 }

142

143

144

145

146 unsigned getMaxDisp() const {

147 return (KnownAlignment ? MaxDisp : MaxDisp - 2) - 2;

148 }

149 };

150

151

152

153 std::vector CPUsers;

154

155

156

157

158 struct CPEntry {

160 unsigned CPI;

161 unsigned RefCount;

162

163 CPEntry(MachineInstr *cpemi, unsigned cpi, unsigned rc = 0)

164 : CPEMI(cpemi), CPI(cpi), RefCount(rc) {}

165 };

166

167

168

169

170

171

172

173

174

175

176 std::vector<std::vector> CPEntries;

177

178

179

181

182

183

185

186

188

189

190

191

192

193 struct ImmBranch {

195 unsigned MaxDisp : 31;

196 bool isCond : 1;

197 unsigned UncondBr;

198

199 ImmBranch(MachineInstr *mi, unsigned maxdisp, bool cond, unsigned ubr)

200 : MI(mi), MaxDisp(maxdisp), isCond(cond), UncondBr(ubr) {}

201 };

202

203

204 std::vector ImmBranches;

205

206

208

209

211

219 bool isThumb1;

220 bool isThumb2;

221 bool isPositionIndependentOrROPI;

222

223 public:

224 static char ID;

225

227

229

233 }

234

237 MachineFunctionProperties::Property::NoVRegs);

238 }

239

242 }

243

244 private:

245 void doInitialConstPlacement(std::vector<MachineInstr *> &CPEMIs);

246 void doInitialJumpTablePlacement(std::vector<MachineInstr *> &CPEMIs);

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

250 void scanFunctionJumpTables();

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

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

255 unsigned getCombinedIndex(const MachineInstr *CPEMI);

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

257 bool findAvailableWater(CPUser&U, unsigned UserOffset,

258 water_iterator &WaterIter, bool CloserWater);

259 void createNewWater(unsigned CPUserIndex, unsigned UserOffset,

261 bool handleConstantPoolUser(unsigned CPUserIndex, bool CloserWater);

263 bool removeUnusedCPEntries();

264 bool isCPEntryInRange(MachineInstr *MI, unsigned UserOffset,

265 MachineInstr *CPEMI, unsigned Disp, bool NegOk,

266 bool DoDump = false);

267 bool isWaterInRange(unsigned UserOffset, MachineBasicBlock *Water,

268 CPUser &U, unsigned &Growth);

269 bool fixupImmediateBr(ImmBranch &Br);

270 bool fixupConditionalBr(ImmBranch &Br);

271 bool fixupUnconditionalBr(ImmBranch &Br);

272 bool optimizeThumb2Instructions();

273 bool optimizeThumb2Branches();

274 bool reorderThumb2JumpTables();

276 unsigned &DeadSize, bool &CanDeleteLEA,

277 bool &BaseRegKill);

278 bool optimizeThumb2JumpTables();

282

283 unsigned getUserOffset(CPUser&) const;

284 void dumpBBs();

286

287 bool isOffsetInRange(unsigned UserOffset, unsigned TrialOffset,

288 unsigned Disp, bool NegativeOK, bool IsSoImm = false);

289 bool isOffsetInRange(unsigned UserOffset, unsigned TrialOffset,

290 const CPUser &U) {

291 return isOffsetInRange(UserOffset, TrialOffset,

292 U.getMaxDisp(), U.NegOk, U.IsSoImm);

293 }

294 };

295

296}

297

298char ARMConstantIslands::ID = 0;

299

300

301void ARMConstantIslands::verify() {

302#ifndef NDEBUG

306 return BBInfo[LHS.getNumber()].postOffset() <

307 BBInfo[RHS.getNumber()].postOffset();

308 }));

309 LLVM_DEBUG(dbgs() << "Verifying " << CPUsers.size() << " CP users.\n");

310 for (CPUser &U : CPUsers) {

311 unsigned UserOffset = getUserOffset(U);

312

313

314 if (isCPEntryInRange(U.MI, UserOffset, U.CPEMI, U.getMaxDisp()+2, U.NegOk,

315 true)) {

317 continue;

318 }

320 dumpBBs();

323 }

324#endif

325}

326

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

328

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

333 const BasicBlockInfo &BBI = BBInfo[J];

334 dbgs() << format("%08x %bb.%u\t", BBI.Offset, J)

335 << " kb=" << unsigned(BBI.KnownBits)

336 << " ua=" << unsigned(BBI.Unalign) << " pa=" << Log2(BBI.PostAlign)

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

338 }

339 });

340}

341#endif

342

343

344

345

349 return false;

350

352 const Align Alignment = TLI->getPrefLoopAlignment();

353 if (Alignment < 4)

354 return false;

355

356 bool Changed = false;

357 bool PrevCanFallthough = true;

358 for (auto &MBB : *MF) {

359 if (!PrevCanFallthough) {

360 Changed = true;

362 }

363

365

366

367

368 if (STI->hasLOB()) {

370 if (MI.getOpcode() == ARM::t2B &&

372 continue;

373 if (isLoopStart(MI) || MI.getOpcode() == ARM::t2LoopEnd ||

374 MI.getOpcode() == ARM::t2LoopEndDec) {

375 PrevCanFallthough = true;

376 break;

377 }

378

379 break;

380 }

381 }

382 }

383

384 return Changed;

385}

386

387bool ARMConstantIslands::runOnMachineFunction(MachineFunction &mf) {

388 MF = &mf;

390 BBUtils = std::make_unique(mf);

391

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

394 << MCP->getConstantPoolAlign().value() << " bytes *****\n");

395

397 TII = STI->getInstrInfo();

398 isPositionIndependentOrROPI =

399 STI->getTargetLowering()->isPositionIndependent() || STI->isROPI();

401 DT = &getAnalysis().getDomTree();

402

403 isThumb = AFI->isThumbFunction();

404 isThumb1 = AFI->isThumb1OnlyFunction();

405 isThumb2 = AFI->isThumb2Function();

406

408

409

410 if (STI->hardenSlsRetBr())

411 GenerateTBB = false;

412

413

414

415 MF->RenumberBlocks();

417

418

419

420 bool MadeChange = false;

422 scanFunctionJumpTables();

423 MadeChange |= reorderThumb2JumpTables();

424

425 T2JumpTables.clear();

426

427 MF->RenumberBlocks();

429 }

430

431

433

434

435

436 std::vector<MachineInstr*> CPEMIs;

437 if (!MCP->isEmpty())

438 doInitialConstPlacement(CPEMIs);

439

440 if (MF->getJumpTableInfo())

441 doInitialJumpTablePlacement(CPEMIs);

442

443

444 AFI->initPICLabelUId(CPEMIs.size());

445

446

447

448

449 initializeFunctionInfo(CPEMIs);

450 CPEMIs.clear();

452

453

454

455 if (!T2JumpTables.empty())

456 MF->ensureAlignment(Align(4));

457

458

459 MadeChange |= removeUnusedCPEntries();

460

461

462

463 unsigned NoCPIters = 0, NoBRIters = 0;

464 while (true) {

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

466 bool CPChange = false;

467 for (unsigned i = 0, e = CPUsers.size(); i != e; ++i)

468

469

470

471 CPChange |= handleConstantPoolUser(i, NoCPIters >= CPMaxIteration / 2);

475

476

477

478 NewWaterList.clear();

479

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

481 bool BRChange = false;

482 for (unsigned i = 0, e = ImmBranches.size(); i != e; ++i)

483 BRChange |= fixupImmediateBr(ImmBranches[i]);

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

487

488 if (!CPChange && !BRChange)

489 break;

490 MadeChange = true;

491 }

492

493

494 if (isThumb2 && !STI->prefers32BitThumb())

495 MadeChange |= optimizeThumb2Instructions();

496

497

498 if (isThumb && STI->hasV8MBaselineOps())

499 MadeChange |= optimizeThumb2Branches();

500

501

502 if (GenerateTBB && !STI->genExecuteOnly())

503 MadeChange |= optimizeThumb2JumpTables();

504

505

507

508

509 for (unsigned i = 0, e = CPEntries.size(); i != e; ++i) {

510 for (unsigned j = 0, je = CPEntries[i].size(); j != je; ++j) {

511 const CPEntry & CPE = CPEntries[i][j];

512 if (CPE.CPEMI && CPE.CPEMI->getOperand(1).isCPI())

513 AFI->recordCPEClone(i, CPE.CPI);

514 }

515 }

516

518

519 BBUtils->clear();

520 WaterList.clear();

521 CPUsers.clear();

522 CPEntries.clear();

523 JumpTableEntryIndices.clear();

524 JumpTableUserIndices.clear();

525 BlockJumpTableRefCount.clear();

526 ImmBranches.clear();

527 PushPopMIs.clear();

528 T2JumpTables.clear();

529

530 return MadeChange;

531}

532

533

534

535void

536ARMConstantIslands::doInitialConstPlacement(std::vector<MachineInstr*> &CPEMIs) {

537

540

541

542 const Align MaxAlign = MCP->getConstantPoolAlign();

543 const unsigned MaxLogAlign = Log2(MaxAlign);

544

545

547

548

549

550

551 Align FuncAlign = MaxAlign;

552 if (MaxAlign == 2)

553 FuncAlign = Align(4);

554 MF->ensureAlignment(FuncAlign);

555

556

557

558

559

561 BB->end());

562

563

564

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

566

567 const DataLayout &TD = MF->getDataLayout();

568 for (unsigned i = 0, e = CPs.size(); i != e; ++i) {

569 unsigned Size = CPs[i].getSizeInBytes(TD);

570 Align Alignment = CPs[i].getAlign();

571

572

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

574

575

576 unsigned LogAlign = Log2(Alignment);

581 CPEMIs.push_back(CPEMI);

582

583

584

585 for (unsigned a = LogAlign + 1; a <= MaxLogAlign; ++a)

586 if (InsPoint[a] == InsAt)

587 InsPoint[a] = CPEMI;

588

589

590 CPEntries.emplace_back(1, CPEntry(CPEMI, i));

591 ++NumCPEs;

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

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

594 }

596}

597

598

599

600

601

602

603void ARMConstantIslands::doInitialJumpTablePlacement(

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

605 unsigned i = CPEntries.size();

606 auto MJTI = MF->getJumpTableInfo();

607 const std::vector &JT = MJTI->getJumpTables();

608

609

611 return;

612

616

619 MI->isDebugInstr()))

620 --MI;

621

623 continue;

624

625 unsigned JTOpcode;

626 switch (MI->getOpcode()) {

627 default:

628 continue;

629 case ARM::BR_JTadd:

630 case ARM::BR_JTr:

631 case ARM::tBR_JTr:

632 case ARM::BR_JTm_i12:

633 case ARM::BR_JTm_rs:

634

635

636

638 "Branch protection must not be enabled for Arm or Thumb1 modes");

639 JTOpcode = ARM::JUMPTABLE_ADDRS;

640 break;

641 case ARM::t2BR_JT:

642 JTOpcode = ARM::JUMPTABLE_INSTS;

643 break;

644 case ARM::tTBB_JT:

645 case ARM::t2TBB_JT:

646 JTOpcode = ARM::JUMPTABLE_TBB;

647 break;

648 case ARM::tTBH_JT:

649 case ARM::t2TBH_JT:

650 JTOpcode = ARM::JUMPTABLE_TBH;

651 break;

652 }

653

654 unsigned NumOps = MI->getDesc().getNumOperands();

656 MI->getOperand(NumOps - (MI->isPredicable() ? 2 : 1));

657 unsigned JTI = JTOp.getIndex();

658 unsigned Size = JT[JTI].MBBs.size() * sizeof(uint32_t);

666 CPEMIs.push_back(CPEMI);

667 CPEntries.emplace_back(1, CPEntry(CPEMI, JTI));

668 JumpTableEntryIndices.insert(std::make_pair(JTI, CPEntries.size() - 1));

669 if (!LastCorrectlyNumberedBB)

670 LastCorrectlyNumberedBB = &MBB;

671 }

672

673

674 if (LastCorrectlyNumberedBB) {

675 MF->RenumberBlocks(LastCorrectlyNumberedBB);

677 }

678}

679

680

681

683

685

687 return false;

688

691 return false;

692

693

694

698 return TooDifficult || FBB == nullptr;

699}

700

701

702

703ARMConstantIslands::CPEntry *

704ARMConstantIslands::findConstPoolEntry(unsigned CPI,

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

707

708

709 for (CPEntry &CPE : CPEs)

710 if (CPE.CPEMI == CPEMI)

711 return &CPE;

712 return nullptr;

713}

714

715

716

717Align ARMConstantIslands::getCPEAlign(const MachineInstr *CPEMI) {

719 case ARM::CONSTPOOL_ENTRY:

720 break;

721 case ARM::JUMPTABLE_TBB:

722 return isThumb1 ? Align(4) : Align(1);

723 case ARM::JUMPTABLE_TBH:

724 return isThumb1 ? Align(4) : Align(2);

725 case ARM::JUMPTABLE_INSTS:

727 case ARM::JUMPTABLE_ADDRS:

729 default:

731 }

732

733 unsigned CPI = getCombinedIndex(CPEMI);

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

735 return MCP->getConstants()[CPI].getAlign();

736}

737

738

739

740

744}

745

746

747

748

749void ARMConstantIslands::scanFunctionJumpTables() {

752 if (I.isBranch() &&

753 (I.getOpcode() == ARM::t2BR_JT || I.getOpcode() == ARM::tBR_JTr))

755 }

756

758 return;

759

764

765

766 BlockJumpTableRefCount[MBB] = std::numeric_limits::max();

767 else

768 ++BlockJumpTableRefCount[MBB];

769 }

770}

771

772

773

774

775void ARMConstantIslands::

776initializeFunctionInfo(const std::vector<MachineInstr*> &CPEMIs) {

777

778 BBUtils->computeAllBlockSizes();

780

781

782 BBInfo.front().KnownBits = Log2(MF->getAlignment());

783

784

785 BBUtils->adjustBBOffsetsAfter(&MF->front());

786

787

789 bool InlineJumpTables =

791

792

794

795

797 WaterList.push_back(&MBB);

798

800 if (I.isDebugInstr())

801 continue;

802

803 unsigned Opc = I.getOpcode();

804 if (I.isBranch()) {

805 bool isCond = false;

806 unsigned Bits = 0;

807 unsigned Scale = 1;

808 int UOpc = Opc;

809 switch (Opc) {

810 default:

811 continue;

812 case ARM::t2BR_JT:

813 case ARM::tBR_JTr:

814 if (InlineJumpTables)

815 T2JumpTables.push_back(&I);

816 continue;

817 case ARM::Bcc:

818 isCond = true;

819 UOpc = ARM::B;

820 [[fallthrough]];

821 case ARM::B:

823 Scale = 4;

824 break;

825 case ARM::tBcc:

826 isCond = true;

827 UOpc = ARM::tB;

829 Scale = 2;

830 break;

831 case ARM::tB:

833 Scale = 2;

834 break;

835 case ARM::t2Bcc:

836 isCond = true;

837 UOpc = ARM::t2B;

839 Scale = 2;

840 break;

841 case ARM::t2B:

843 Scale = 2;

844 break;

845 }

846

847

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

849 ImmBranches.push_back(ImmBranch(&I, MaxOffs, isCond, UOpc));

850 }

851

852 if (Opc == ARM::tPUSH || Opc == ARM::tPOP_RET)

853 PushPopMIs.push_back(&I);

854

855 if (Opc == ARM::CONSTPOOL_ENTRY || Opc == ARM::JUMPTABLE_ADDRS ||

856 Opc == ARM::JUMPTABLE_INSTS || Opc == ARM::JUMPTABLE_TBB ||

857 Opc == ARM::JUMPTABLE_TBH)

858 continue;

859

860

861 for (unsigned op = 0, e = I.getNumOperands(); op != e; ++op)

862 if (I.getOperand(op).isCPI() ||

863 (I.getOperand(op).isJTI() && InlineJumpTables)) {

864

865

866

867

868 unsigned Bits = 0;

869 unsigned Scale = 1;

870 bool NegOk = false;

871 bool IsSoImm = false;

872

873 switch (Opc) {

874 default:

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

876

877

878 case ARM::LEApcrel:

879 case ARM::LEApcrelJT: {

880

881

882

883

885 NegOk = true;

886 IsSoImm = true;

887 unsigned CPI = I.getOperand(op).getIndex();

888 assert(CPI < CPEMIs.size());

890 const Align CPEAlign = getCPEAlign(CPEMI);

891 const unsigned LogCPEAlign = Log2(CPEAlign);

892 if (LogCPEAlign >= 2)

893 Scale = 4;

894 else

895

896

897 Scale = 1;

898 }

899 break;

900 case ARM::t2LEApcrel:

901 case ARM::t2LEApcrelJT:

903 NegOk = true;

904 break;

905 case ARM::tLEApcrel:

906 case ARM::tLEApcrelJT:

908 Scale = 4;

909 break;

910

911 case ARM::LDRBi12:

912 case ARM::LDRi12:

913 case ARM::LDRcp:

914 case ARM::t2LDRpci:

915 case ARM::t2LDRHpci:

916 case ARM::t2LDRSHpci:

917 case ARM::t2LDRBpci:

918 case ARM::t2LDRSBpci:

919 Bits = 12;

920 NegOk = true;

921 break;

922

923 case ARM::tLDRpci:

925 Scale = 4;

926 break;

927

928 case ARM::VLDRD:

929 case ARM::VLDRS:

931 Scale = 4;

932 NegOk = true;

933 break;

934 case ARM::VLDRH:

936 Scale = 2;

937 NegOk = true;

938 break;

939 }

940

941

942 unsigned CPI = I.getOperand(op).getIndex();

943 if (I.getOperand(op).isJTI()) {

944 JumpTableUserIndices.insert(std::make_pair(CPI, CPUsers.size()));

945 CPI = JumpTableEntryIndices[CPI];

946 }

947

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

950 CPUsers.push_back(CPUser(&I, CPEMI, MaxOffs, NegOk, IsSoImm));

951

952

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

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

955 CPE->RefCount++;

956

957

958

959 break;

960 }

961 }

962 }

963}

964

965

966

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

970}

971

972

973

974

975void ARMConstantIslands::updateForInsertedWaterBlock(MachineBasicBlock *NewBB) {

976

979

980

981

983

984

985

987 WaterList.insert(IP, NewBB);

988}

989

990

991

992

995

996

997 LivePhysRegs LRs(*MF->getSubtarget().getRegisterInfo());

998 LRs.addLiveOuts(*OrigBB);

1001 LRs.stepBackward(LiveMI);

1002

1003

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

1007 MF->insert(MBBI, NewBB);

1008

1009

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

1011

1012

1013

1014

1015

1016 unsigned Opc = isThumb ? (isThumb2 ? ARM::t2B : ARM::tB) : ARM::B;

1019 else

1023 ++NumSplit;

1024

1025

1027

1028

1030

1031

1034 if ( MRI .isReserved(L))

1036

1037

1038

1039

1040 MF->RenumberBlocks(NewBB);

1042

1043

1044

1046

1047

1048

1049

1050

1053 if (WaterBB == OrigBB)

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

1055 else

1056 WaterList.insert(IP, OrigBB);

1057 NewWaterList.insert(OrigBB);

1058

1059

1060

1061

1062

1063

1064 BBUtils->computeBlockSize(OrigBB);

1065

1066

1067

1068 BBUtils->computeBlockSize(NewBB);

1069

1070

1071 BBUtils->adjustBBOffsetsAfter(OrigBB);

1072

1073 return NewBB;

1074}

1075

1076

1077

1078

1079unsigned ARMConstantIslands::getUserOffset(CPUser &U) const {

1080 unsigned UserOffset = BBUtils->getOffsetOf(U.MI);

1081

1083 const BasicBlockInfo &BBI = BBInfo[U.MI->getParent()->getNumber()];

1085

1086

1087 UserOffset += (isThumb ? 4 : 8);

1088

1089

1090

1091 U.KnownAlignment = (KnownBits >= 2);

1092

1093

1094

1095

1096 if (isThumb && U.KnownAlignment)

1097 UserOffset &= ~3u;

1098

1099 return UserOffset;

1100}

1101

1102

1103

1104

1105

1106

1107

1108bool ARMConstantIslands::isOffsetInRange(unsigned UserOffset,

1109 unsigned TrialOffset, unsigned MaxDisp,

1110 bool NegativeOK, bool IsSoImm) {

1111 if (UserOffset <= TrialOffset) {

1112

1113 if (TrialOffset - UserOffset <= MaxDisp)

1114 return true;

1115

1116 } else if (NegativeOK) {

1117 if (UserOffset - TrialOffset <= MaxDisp)

1118 return true;

1119

1120 }

1121 return false;

1122}

1123

1124

1125

1126

1127

1128bool ARMConstantIslands::isWaterInRange(unsigned UserOffset,

1130 unsigned &Growth) {

1131 BBInfoVector &BBInfo = BBUtils->getBBInfo();

1132 const Align CPEAlign = getCPEAlign(U.CPEMI);

1133 const unsigned CPEOffset = BBInfo[Water->getNumber()].postOffset(CPEAlign);

1134 unsigned NextBlockOffset;

1135 Align NextBlockAlignment;

1137 if (++NextBlock == MF->end()) {

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

1139 } else {

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

1141 NextBlockAlignment = NextBlock->getAlignment();

1142 }

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

1144 unsigned CPEEnd = CPEOffset + Size;

1145

1146

1147

1148

1149 if (CPEEnd > NextBlockOffset) {

1150 Growth = CPEEnd - NextBlockOffset;

1151

1152

1154

1155

1156

1157

1158 if (CPEOffset < UserOffset)

1159 UserOffset += Growth + UnknownPadding(MF->getAlignment(), Log2(CPEAlign));

1160 } else

1161

1162 Growth = 0;

1163

1164 return isOffsetInRange(UserOffset, CPEOffset, U);

1165}

1166

1167

1168

1169bool ARMConstantIslands::isCPEntryInRange(MachineInstr *MI, unsigned UserOffset,

1171 bool NegOk, bool DoDump) {

1172 unsigned CPEOffset = BBUtils->getOffsetOf(CPEMI);

1173

1174 if (DoDump) {

1176 BBInfoVector &BBInfo = BBUtils->getBBInfo();

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

1180 << " max delta=" << MaxDisp

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

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

1185 int(CPEOffset - UserOffset));

1186 });

1187 }

1188

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

1190}

1191

1192#ifndef NDEBUG

1193

1194

1197 return false;

1198

1203 || PredMI->getOpcode() == ARM::t2B)

1205 return false;

1206}

1207#endif

1208

1209

1210

1211

1212

1213bool ARMConstantIslands::decrementCPEReferenceCount(unsigned CPI,

1215

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

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

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

1219 removeDeadCPEMI(CPEMI);

1220 CPE->CPEMI = nullptr;

1221 --NumCPEs;

1222 return true;

1223 }

1224 return false;

1225}

1226

1227unsigned ARMConstantIslands::getCombinedIndex(const MachineInstr *CPEMI) {

1230

1232}

1233

1234

1235

1236

1237

1238

1239

1240int ARMConstantIslands::findInRangeCPEntry(CPUser& U, unsigned UserOffset) {

1243

1244

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

1246 true)) {

1248 return 1;

1249 }

1250

1251

1252 unsigned CPI = getCombinedIndex(CPEMI);

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

1254 for (CPEntry &CPE : CPEs) {

1255

1256 if (CPE.CPEMI == CPEMI)

1257 continue;

1258

1259 if (CPE.CPEMI == nullptr)

1260 continue;

1261 if (isCPEntryInRange(UserMI, UserOffset, CPE.CPEMI, U.getMaxDisp(),

1262 U.NegOk)) {

1263 LLVM_DEBUG(dbgs() << "Replacing CPE#" << CPI << " with CPE#" << CPE.CPI

1264 << "\n");

1265

1266 U.CPEMI = CPE.CPEMI;

1267

1269 if (MO.isCPI()) {

1270 MO.setIndex(CPE.CPI);

1271 break;

1272 }

1273

1274 CPE.RefCount++;

1275

1276

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

1278 }

1279 }

1280 return 0;

1281}

1282

1283

1284

1286 switch (Opc) {

1287 case ARM::tB:

1288 return ((1<<10)-1)*2;

1289 case ARM::t2B:

1290 return ((1<<23)-1)*2;

1291 default:

1292 break;

1293 }

1294

1295 return ((1<<23)-1)*4;

1296}

1297

1298

1299

1300

1301

1302

1303

1304

1305

1306bool ARMConstantIslands::findAvailableWater(CPUser &U, unsigned UserOffset,

1307 water_iterator &WaterIter,

1308 bool CloserWater) {

1309 if (WaterList.empty())

1310 return false;

1311

1312 unsigned BestGrowth = ~0u;

1313

1314

1315

1316

1317

1318

1319

1320

1321

1322

1324 BBInfoVector &BBInfo = BBUtils->getBBInfo();

1325 const Align CPEAlign = getCPEAlign(U.CPEMI);

1326 unsigned MinNoSplitDisp =

1327 BBInfo[UserBB->getNumber()].postOffset(CPEAlign) - UserOffset;

1328 if (CloserWater && MinNoSplitDisp > U.getMaxDisp() / 2)

1329 return false;

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

1331 --IP) {

1333

1334

1335

1336

1337

1338

1339

1340

1341

1342

1343 unsigned Growth;

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

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

1346 NewWaterList.count(WaterBB) || WaterBB == U.MI->getParent()) &&

1347 Growth < BestGrowth) {

1348

1349 BestGrowth = Growth;

1350 WaterIter = IP;

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

1353

1354 if (CloserWater && WaterBB == U.MI->getParent())

1355 return true;

1356

1357

1358 if (!CloserWater && BestGrowth == 0)

1359 return true;

1360 }

1361 if (IP == B)

1362 break;

1363 }

1364 return BestGrowth != ~0u;

1365}

1366

1367

1368

1369

1370

1371

1372

1373

1374void ARMConstantIslands::createNewWater(unsigned CPUserIndex,

1375 unsigned UserOffset,

1377 CPUser &U = CPUsers[CPUserIndex];

1380 const Align CPEAlign = getCPEAlign(CPEMI);

1382 BBInfoVector &BBInfo = BBUtils->getBBInfo();

1384

1385

1386

1387

1388

1390

1391 unsigned Delta = isThumb1 ? 2 : 4;

1392

1393 unsigned CPEOffset = UserBBI.postOffset(CPEAlign) + Delta;

1394

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

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

1399

1400

1401

1402

1403

1404 int UncondBr = isThumb ? ((isThumb2) ? ARM::t2B : ARM::tB) : ARM::B;

1407 else

1412 ImmBranches.push_back(ImmBranch(&UserMBB->back(),

1413 MaxDisp, false, UncondBr));

1414 BBUtils->computeBlockSize(UserMBB);

1415 BBUtils->adjustBBOffsetsAfter(UserMBB);

1416 return;

1417 }

1418 }

1419

1420

1421

1422

1423

1424

1425

1426

1427

1428

1429

1430

1431

1432

1433

1434

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

1436 assert(Align >= CPEAlign && "Over-aligned constant pool entry");

1439 unsigned BaseInsertOffset = UserOffset + U.getMaxDisp() - UPad;

1441 BaseInsertOffset));

1442

1443

1444

1445

1446 BaseInsertOffset -= 4;

1447

1450 << " up=" << UPad << '\n');

1451

1452

1453

1454

1455

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

1457

1458

1459

1460 BaseInsertOffset =

1461 std::max(UserBBI.postOffset() - UPad - 8,

1462 UserOffset + TII->getInstSizeInBytes(*UserMI) + 1);

1463

1464

1465

1466

1467

1468

1469

1470

1471

1472

1473

1475 ++I;

1477 for (unsigned Offset = UserOffset + TII->getInstSizeInBytes(*UserMI);

1478 I->getOpcode() != ARM::t2IT &&

1480 Offset += TII->getInstSizeInBytes(*I), I = std::next(I)) {

1481 BaseInsertOffset =

1482 std::max(BaseInsertOffset, Offset + TII->getInstSizeInBytes(*I) + 1);

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

1484 }

1486 }

1487 unsigned EndInsertOffset = BaseInsertOffset + 4 + UPad +

1490 ++MI;

1491 unsigned CPUIndex = CPUserIndex+1;

1492 unsigned NumCPUsers = CPUsers.size();

1494 for (unsigned Offset = UserOffset + TII->getInstSizeInBytes(*UserMI);

1495 Offset < BaseInsertOffset;

1496 Offset += TII->getInstSizeInBytes(*MI), MI = std::next(MI)) {

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

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

1499 CPUser &U = CPUsers[CPUIndex];

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

1501

1504 }

1505

1506

1507

1508

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

1510 CPUIndex++;

1511 }

1512

1513

1514 if (MI->getOpcode() == ARM::t2IT)

1515 LastIT = &*MI;

1516 }

1517

1518 --MI;

1519

1520

1521 if (LastIT) {

1525 MI = LastIT;

1526 }

1527

1528

1529

1530

1531

1532

1533

1534

1535 if (STI->isTargetWindows() && isThumb && MI->getOpcode() == ARM::t2MOVTi16 &&

1538 --MI;

1539 assert(MI->getOpcode() == ARM::t2MOVi16 &&

1542 }

1543

1544

1545#ifndef NDEBUG

1548#endif

1549 NewMBB = splitBlockBeforeInstr(&*MI);

1550}

1551

1552

1553

1554

1555

1556bool ARMConstantIslands::handleConstantPoolUser(unsigned CPUserIndex,

1557 bool CloserWater) {

1558 CPUser &U = CPUsers[CPUserIndex];

1561 unsigned CPI = getCombinedIndex(CPEMI);

1563

1564 unsigned UserOffset = getUserOffset(U);

1565

1566

1567

1568 int result = findInRangeCPEntry(U, UserOffset);

1569 if (result==1) return false;

1570 else if (result==2) return true;

1571

1572

1573

1574 unsigned ID = AFI->createPICLabelUId();

1575

1576

1579 water_iterator IP;

1580 if (findAvailableWater(U, UserOffset, IP, CloserWater)) {

1583

1584

1585

1586

1587 if (NewWaterList.erase(WaterBB))

1588 NewWaterList.insert(NewIsland);

1589

1590

1592 } else {

1593

1595 createNewWater(CPUserIndex, UserOffset, NewMBB);

1596

1597

1598

1599

1600

1601

1603 IP = find(WaterList, WaterBB);

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

1605 NewWaterList.erase(WaterBB);

1606

1607

1608 NewWaterList.insert(NewIsland);

1609 }

1610

1611

1612

1616

1617

1618

1619

1620

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

1622 WaterList.erase(IP);

1623

1624

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

1626

1627

1628 updateForInsertedWaterBlock(NewIsland);

1629

1630

1631

1632 U.HighWaterMark = NewIsland;

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

1638 ++NumCPEs;

1639

1640

1641 decrementCPEReferenceCount(CPI, CPEMI);

1642

1643

1645

1646

1647 BBUtils->adjustBBSize(NewIsland, Size);

1648 BBUtils->adjustBBOffsetsAfter(&*--NewIsland->getIterator());

1649

1650

1652 if (MO.isCPI()) {

1653 MO.setIndex(ID);

1654 break;

1655 }

1656

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

1659 << format(" offset=%#x\n",

1660 BBUtils->getBBInfo()[NewIsland->getNumber()].Offset));

1661

1662 return true;

1663}

1664

1665

1666

1667void ARMConstantIslands::removeDeadCPEMI(MachineInstr *CPEMI) {

1671 BBInfoVector &BBInfo = BBUtils->getBBInfo();

1672 BBUtils->adjustBBSize(CPEBB, -Size);

1673

1674 if (CPEBB->empty()) {

1676

1677

1679 } else {

1680

1682 }

1683

1684 BBUtils->adjustBBOffsetsAfter(CPEBB);

1685

1686

1687

1689

1690}

1691

1692

1693

1694bool ARMConstantIslands::removeUnusedCPEntries() {

1695 unsigned MadeChange = false;

1696 for (std::vector &CPEs : CPEntries) {

1697 for (CPEntry &CPE : CPEs) {

1698 if (CPE.RefCount == 0 && CPE.CPEMI) {

1699 removeDeadCPEMI(CPE.CPEMI);

1700 CPE.CPEMI = nullptr;

1701 MadeChange = true;

1702 }

1703 }

1704 }

1705 return MadeChange;

1706}

1707

1708

1709

1710

1711bool ARMConstantIslands::fixupImmediateBr(ImmBranch &Br) {

1714

1715

1716 if (BBUtils->isBBInRange(MI, DestBB, Br.MaxDisp))

1717 return false;

1718

1719 if (!Br.isCond)

1720 return fixupUnconditionalBr(Br);

1721 return fixupConditionalBr(Br);

1722}

1723

1724

1725

1726

1727

1728bool

1729ARMConstantIslands::fixupUnconditionalBr(ImmBranch &Br) {

1732 if (!isThumb1)

1734

1735 if (!AFI->isLRSpilled())

1737

1738

1739 Br.MaxDisp = (1 << 21) * 2;

1740 MI->setDesc(TII->get(ARM::tBfar));

1741 BBInfoVector &BBInfo = BBUtils->getBBInfo();

1743 BBUtils->adjustBBOffsetsAfter(MBB);

1744 ++NumUBrFixed;

1745

1747

1748 return true;

1749}

1750

1751

1752

1753

1754bool

1755ARMConstantIslands::fixupConditionalBr(ImmBranch &Br) {

1758

1759

1760

1761

1762

1763

1764

1765

1768 Register CCReg = MI->getOperand(2).getReg();

1769

1770

1771

1772

1776

1777 ++NumCBrFixed;

1778 if (BMI != MI) {

1780 BMI->getOpcode() == Br.UncondBr) {

1781

1782

1783

1784

1785

1786

1787

1789 if (BBUtils->isBBInRange(MI, NewDest, Br.MaxDisp)) {

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

1792 << *BMI);

1794 MI->getOperand(0).setMBB(NewDest);

1795 MI->getOperand(1).setImm(CC);

1796 return true;

1797 }

1798 }

1799 }

1800

1801 if (NeedSplit) {

1802 splitBlockBeforeInstr(MI);

1803

1804

1805 int delta = TII->getInstSizeInBytes(MBB->back());

1806 BBUtils->adjustBBSize(MBB, -delta);

1808

1809

1810

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

1813

1814

1815 }

1817

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

1821

1822

1823

1827 BBUtils->adjustBBSize(MBB, TII->getInstSizeInBytes(MBB->back()));

1832 else

1834 BBUtils->adjustBBSize(MBB, TII->getInstSizeInBytes(MBB->back()));

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

1837

1838

1839 BBUtils->adjustBBSize(MI->getParent(), -TII->getInstSizeInBytes(*MI));

1840 MI->eraseFromParent();

1841 BBUtils->adjustBBOffsetsAfter(MBB);

1842 return true;

1843}

1844

1845bool ARMConstantIslands::optimizeThumb2Instructions() {

1846 bool MadeChange = false;

1847

1848

1849 for (CPUser &U : CPUsers) {

1850 unsigned Opcode = U.MI->getOpcode();

1851 unsigned NewOpc = 0;

1852 unsigned Scale = 1;

1853 unsigned Bits = 0;

1854 switch (Opcode) {

1855 default: break;

1856 case ARM::t2LEApcrel:

1858 NewOpc = ARM::tLEApcrel;

1860 Scale = 4;

1861 }

1862 break;

1863 case ARM::t2LDRpci:

1865 NewOpc = ARM::tLDRpci;

1867 Scale = 4;

1868 }

1869 break;

1870 }

1871

1872 if (!NewOpc)

1873 continue;

1874

1875 unsigned UserOffset = getUserOffset(U);

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

1877

1878

1879 if (.KnownAlignment)

1880 MaxOffs -= 2;

1881

1882

1883 if (isCPEntryInRange(U.MI, UserOffset, U.CPEMI, MaxOffs, false, true)) {

1885 U.MI->setDesc(TII->get(NewOpc));

1887 BBUtils->adjustBBSize(MBB, -2);

1888 BBUtils->adjustBBOffsetsAfter(MBB);

1889 ++NumT2CPShrunk;

1890 MadeChange = true;

1891 }

1892 }

1893

1894 return MadeChange;

1895}

1896

1897

1898bool ARMConstantIslands::optimizeThumb2Branches() {

1899

1900 auto TryShrinkBranch = [this](ImmBranch &Br) {

1901 unsigned Opcode = Br.MI->getOpcode();

1902 unsigned NewOpc = 0;

1903 unsigned Scale = 1;

1904 unsigned Bits = 0;

1905 switch (Opcode) {

1906 default: break;

1907 case ARM::t2B:

1908 NewOpc = ARM::tB;

1910 Scale = 2;

1911 break;

1912 case ARM::t2Bcc:

1913 NewOpc = ARM::tBcc;

1915 Scale = 2;

1916 break;

1917 }

1918 if (NewOpc) {

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

1921 if (BBUtils->isBBInRange(Br.MI, DestBB, MaxOffs)) {

1923 Br.MI->setDesc(TII->get(NewOpc));

1925 BBUtils->adjustBBSize(MBB, -2);

1926 BBUtils->adjustBBOffsetsAfter(MBB);

1927 ++NumT2BrShrunk;

1928 return true;

1929 }

1930 }

1931 return false;

1932 };

1933

1934 struct ImmCompare {

1936 unsigned NewOpc = 0;

1937 };

1938

1939 auto FindCmpForCBZ = [this](ImmBranch &Br, ImmCompare &ImmCmp,

1941 ImmCmp.MI = nullptr;

1942 ImmCmp.NewOpc = 0;

1943

1944

1945

1946 if (!Br.MI->killsRegister(ARM::CPSR, nullptr))

1947 return false;

1948

1950 unsigned NewOpc = 0;

1953 NewOpc = ARM::tCBZ;

1955 NewOpc = ARM::tCBNZ;

1956 else

1957 return false;

1958

1959

1960

1961 unsigned BrOffset = BBUtils->getOffsetOf(Br.MI) + 4 - 2;

1962 BBInfoVector &BBInfo = BBUtils->getBBInfo();

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

1964 if (BrOffset >= DestOffset || (DestOffset - BrOffset) > 126)

1965 return false;

1966

1967

1968 auto *TRI = STI->getRegisterInfo();

1970 if (!CmpMI || CmpMI->getOpcode() != ARM::tCMPi8)

1971 return false;

1972

1973 ImmCmp.MI = CmpMI;

1974 ImmCmp.NewOpc = NewOpc;

1975 return true;

1976 };

1977

1978 auto TryConvertToLE = [this](ImmBranch &Br, ImmCompare &Cmp) {

1979 if (Br.MI->getOpcode() != ARM::t2Bcc || !STI->hasLOB() ||

1980 STI->hasMinSize())

1981 return false;

1982

1985 if (BBUtils->getOffsetOf(MBB) < BBUtils->getOffsetOf(DestBB) ||

1986 !BBUtils->isBBInRange(Br.MI, DestBB, 4094))

1987 return false;

1988

1990 return false;

1991

1992

1993

1994 Cmp.NewOpc = Cmp.NewOpc == ARM::tCBZ ? ARM::tCBNZ : ARM::tCBZ;

1995

1997 TII->get(ARM::t2LE));

1998

1999 MIB.add(Br.MI->getOperand(0));

2001 Br.MI = MIB;

2002 ++NumLEInserted;

2003 return true;

2004 };

2005

2006 bool MadeChange = false;

2007

2008

2009

2010

2011

2012

2013 for (ImmBranch &Br : reverse(ImmBranches)) {

2019

2020 ImmCompare Cmp;

2021 if (FindCmpForCBZ(Br, Cmp, ExitBB) && TryConvertToLE(Br, Cmp)) {

2022 DestBB = ExitBB;

2023 MadeChange = true;

2024 } else {

2025 FindCmpForCBZ(Br, Cmp, DestBB);

2026 MadeChange |= TryShrinkBranch(Br);

2027 }

2028

2029 unsigned Opcode = Br.MI->getOpcode();

2030 if ((Opcode != ARM::tBcc && Opcode != ARM::t2LE) || Cmp .NewOpc)

2031 continue;

2032

2034

2035

2036

2037 auto *TRI = STI->getRegisterInfo();

2039 bool RegKilled = false;

2040 do {

2041 --KillMI;

2042 if (KillMI->killsRegister(Reg, TRI)) {

2043 KillMI->clearRegisterKills(Reg, TRI);

2044 RegKilled = true;

2045 break;

2046 }

2047 } while (KillMI != Cmp.MI);

2048

2049

2050 LLVM_DEBUG(dbgs() << "Fold: " << *Cmp.MI << " and: " << *Br.MI);

2052 BuildMI(*MBB, Br.MI, Br.MI->getDebugLoc(), TII->get(Cmp.NewOpc))

2055 .addMBB(DestBB, Br.MI->getOperand(0).getTargetFlags());

2056

2057 Cmp.MI->eraseFromParent();

2058

2059 if (Br.MI->getOpcode() == ARM::tBcc) {

2060 Br.MI->eraseFromParent();

2061 Br.MI = NewBR;

2062 BBUtils->adjustBBSize(MBB, -2);

2064

2065

2066

2067

2068

2072 }

2073 BBUtils->adjustBBOffsetsAfter(MBB);

2074 ++NumCBZ;

2075 MadeChange = true;

2076 }

2077

2078 return MadeChange;

2079}

2080

2082 unsigned BaseReg) {

2083 if (I.getOpcode() != ARM::t2ADDrs)

2084 return false;

2085

2086 if (I.getOperand(0).getReg() != EntryReg)

2087 return false;

2088

2089 if (I.getOperand(1).getReg() != BaseReg)

2090 return false;

2091

2092

2093 return true;

2094}

2095

2096

2097

2098

2099

2100

2101

2102bool ARMConstantIslands::preserveBaseRegister(MachineInstr *JumpMI,

2104 unsigned &DeadSize,

2105 bool &CanDeleteLEA,

2106 bool &BaseRegKill) {

2108 return false;

2109

2110

2111

2112

2113

2114

2115

2116

2117

2118

2119

2120

2121

2122

2123

2124

2125

2128

2129 CanDeleteLEA = true;

2130 BaseRegKill = false;

2133 for (++I; &*I != JumpMI; ++I) {

2135 RemovableAdd = &*I;

2136 break;

2137 }

2138

2140 if (!MO.isReg() || !MO.getReg())

2141 continue;

2142 if (MO.isDef() && MO.getReg() == BaseReg)

2143 return false;

2144 if (MO.isUse() && MO.getReg() == BaseReg) {

2145 BaseRegKill = BaseRegKill || MO.isKill();

2146 CanDeleteLEA = false;

2147 }

2148 }

2149 }

2150

2151 if (!RemovableAdd)

2152 return true;

2153

2154

2155

2156 for (++I; &*I != JumpMI; ++I) {

2158 if (!MO.isReg() || !MO.getReg())

2159 continue;

2160 if (MO.isDef() && MO.getReg() == BaseReg)

2161 return false;

2162 if (MO.isUse() && MO.getReg() == EntryReg)

2163 RemovableAdd = nullptr;

2164 }

2165 }

2166

2167 if (RemovableAdd) {

2169 DeadSize += isThumb2 ? 4 : 2;

2170 } else if (BaseReg == EntryReg) {

2171

2172

2173 return false;

2174 }

2175

2176

2177

2178

2179 return true;

2180}

2181

2182

2183

2184

2185

2190

2192}

2193

2196 unsigned &DeadSize) {

2197

2198

2199

2202

2203

2205 for (++I; &*I != JumpMI; ++I) {

2206 if (I->getOpcode() == ARM::t2ADDrs && I->getOperand(0).getReg() == EntryReg)

2207 RemovableAdd = &*I;

2208 }

2209

2210 if (!RemovableAdd)

2211 return;

2212

2213

2215 for (++J; &*J != JumpMI; ++J) {

2217 if (!MO.isReg() || !MO.getReg())

2218 continue;

2219 if (MO.isDef() && MO.getReg() == EntryReg)

2220 return;

2221 if (MO.isUse() && MO.getReg() == EntryReg)

2222 return;

2223 }

2224 }

2225

2226 LLVM_DEBUG(dbgs() << "Removing Dead Add: " << *RemovableAdd);

2228 DeadSize += 4;

2229}

2230

2231

2232

2233bool ARMConstantIslands::optimizeThumb2JumpTables() {

2234 bool MadeChange = false;

2235

2236

2237

2239 if (!MJTI) return false;

2240

2241 const std::vector &JT = MJTI->getJumpTables();

2245 unsigned JTOpIdx = NumOps - (MI->isPredicable() ? 2 : 1);

2247 unsigned JTI = JTOP.getIndex();

2249

2250 bool ByteOk = true;

2251 bool HalfWordOk = true;

2252 unsigned JTOffset = BBUtils->getOffsetOf(MI) + 4;

2253 const std::vector<MachineBasicBlock*> &JTBBs = JT[JTI].MBBs;

2254 BBInfoVector &BBInfo = BBUtils->getBBInfo();

2256 unsigned DstOffset = BBInfo[MBB->getNumber()].Offset;

2257

2258

2259 if (ByteOk && (DstOffset - JTOffset) > ((1<<8)-1)*2)

2260 ByteOk = false;

2261 unsigned TBHLimit = ((1<<16)-1)*2;

2262 if (HalfWordOk && (DstOffset - JTOffset) > TBHLimit)

2263 HalfWordOk = false;

2264 if (!ByteOk && !HalfWordOk)

2265 break;

2266 }

2267

2268 if (!ByteOk && !HalfWordOk)

2269 continue;

2270

2271 CPUser &User = CPUsers[JumpTableUserIndices[JTI]];

2273 if (->getOperand(0).isKill())

2274 continue;

2275

2276 unsigned DeadSize = 0;

2277 bool CanDeleteLEA = false;

2278 bool BaseRegKill = false;

2279

2280 unsigned IdxReg = ~0U;

2281 bool IdxRegKill = true;

2282 if (isThumb2) {

2283 IdxReg = MI->getOperand(1).getReg();

2284 IdxRegKill = MI->getOperand(1).isKill();

2285

2286 bool PreservedBaseReg =

2287 preserveBaseRegister(MI, User.MI, DeadSize, CanDeleteLEA, BaseRegKill);

2289 continue;

2290 } else {

2291

2292

2293

2294

2296

2299 if (Shift == UserMBB->begin())

2300 continue;

2301

2303 if (Shift->getOpcode() != ARM::tLSLri ||

2304 Shift->getOperand(3).getImm() != 2 ||

2305 !Shift->getOperand(2).isKill())

2306 continue;

2307 IdxReg = Shift->getOperand(2).getReg();

2308 Register ShiftedIdxReg = Shift->getOperand(0).getReg();

2309

2310

2311

2312

2314 continue;

2315

2317 if (Load->getOpcode() != ARM::tLDRr)

2318 continue;

2319 if (Load->getOperand(1).getReg() != BaseReg ||

2320 Load->getOperand(2).getReg() != ShiftedIdxReg ||

2321 Load ->getOperand(2).isKill())

2322 continue;

2323

2324

2325 auto *TRI = STI->getRegisterInfo();

2326

2327

2328

2329

2330

2331

2333 continue;

2334

2335 if (isPositionIndependentOrROPI) {

2337 if (Add->getOpcode() != ARM::tADDrr ||

2338 Add->getOperand(2).getReg() != BaseReg ||

2339 Add->getOperand(3).getReg() != Load->getOperand(0).getReg() ||

2340 Add ->getOperand(3).isKill())

2341 continue;

2342 if (Add->getOperand(0).getReg() != MI->getOperand(0).getReg())

2343 continue;

2345

2346 continue;

2347 Add->eraseFromParent();

2348 DeadSize += 2;

2349 } else {

2350 if (Load->getOperand(0).getReg() != MI->getOperand(0).getReg())

2351 continue;

2353

2354 continue;

2355 }

2356

2357

2358 CanDeleteLEA = true;

2359 Shift->eraseFromParent();

2360 Load->eraseFromParent();

2361 DeadSize += 4;

2362 }

2363

2366 unsigned Opc = ByteOk ? ARM::t2TBB_JT : ARM::t2TBH_JT;

2367 if (!isThumb2)

2368 Opc = ByteOk ? ARM::tTBB_JT : ARM::tTBH_JT;

2369

2379

2380 unsigned JTOpc = ByteOk ? ARM::JUMPTABLE_TBB : ARM::JUMPTABLE_TBH;

2382

2386

2387 if (CanDeleteLEA) {

2388 if (isThumb2)

2390

2391 User.MI->eraseFromParent();

2392 DeadSize += isThumb2 ? 4 : 2;

2393

2394

2395

2396 User.MI = NewJTMI;

2397 User.MaxDisp = 4;

2398 User.NegOk = false;

2399 User.IsSoImm = false;

2400 User.KnownAlignment = false;

2401 } else {

2402

2403

2404 int CPEntryIdx = JumpTableEntryIndices[JTI];

2405 auto &CPEs = CPEntries[CPEntryIdx];

2407 find_if(CPEs, [&](CPEntry &E) { return E.CPEMI == User.CPEMI; });

2408 ++Entry->RefCount;

2409 CPUsers.emplace_back(CPUser(NewJTMI, User.CPEMI, 4, false, false));

2410 }

2411 }

2412

2413 unsigned NewSize = TII->getInstSizeInBytes(*NewJTMI);

2414 unsigned OrigSize = TII->getInstSizeInBytes(*MI);

2415 MI->eraseFromParent();

2416

2417 int Delta = OrigSize - NewSize + DeadSize;

2419 BBUtils->adjustBBOffsetsAfter(MBB);

2420

2421 ++NumTBs;

2422 MadeChange = true;

2423 }

2424

2425 return MadeChange;

2426}

2427

2428

2429

2430bool ARMConstantIslands::reorderThumb2JumpTables() {

2431 bool MadeChange = false;

2432

2434 if (!MJTI) return false;

2435

2436 const std::vector &JT = MJTI->getJumpTables();

2440 unsigned JTOpIdx = NumOps - (MI->isPredicable() ? 2 : 1);

2442 unsigned JTI = JTOP.getIndex();

2444

2445

2446

2447

2448 int JTNumber = MI->getParent()->getNumber();

2449 const std::vector<MachineBasicBlock*> &JTBBs = JT[JTI].MBBs;

2452

2453 if (DTNumber < JTNumber) {

2454

2455

2457 adjustJTTargetBlockForward(JTI, MBB, MI->getParent());

2458 if (NewBB)

2460 MadeChange = true;

2461 }

2462 }

2463 }

2464

2465 return MadeChange;

2466}

2467

2468MachineBasicBlock *ARMConstantIslands::adjustJTTargetBlockForward(

2470

2471

2472

2473

2480

2481

2483

2484

2485

2486

2487 if ( && Cond.empty() && BB != &MF->front() &&

2490 OldPrior->updateTerminator(BB);

2491 BB->updateTerminator(OldNext != MF->end() ? &*OldNext : nullptr);

2492

2493 MF->RenumberBlocks();

2495 ++NumJTMoved;

2496 return nullptr;

2497 }

2498

2499

2501 MF->CreateMachineBasicBlock(JTBB->getBasicBlock());

2503 MF->insert(MBBI, NewBB);

2504

2505

2508

2509

2510

2511

2512 if (isThumb2)

2516 else

2520

2521

2522 MF->RenumberBlocks(NewBB);

2524

2525

2528

2529 ++NumJTInserted;

2530 return NewBB;

2531}

2532

2533

2534

2536 return new ARMConstantIslands();

2537}

2538

2540 false, false)

unsigned const MachineRegisterInfo * MRI

static bool isThumb(const MCSubtargetInfo &STI)

static cl::opt< unsigned > CPMaxIteration("arm-constant-island-max-iteration", cl::Hidden, cl::init(30), cl::desc("The max number of iteration for converge"))

static bool isSimpleIndexCalc(MachineInstr &I, unsigned EntryReg, unsigned BaseReg)

static bool jumpTableFollowsTB(MachineInstr *JTMI, MachineInstr *CPEMI)

Returns whether CPEMI is the first instruction in the block immediately following JTMI (assumed to be...

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

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

static unsigned getUnconditionalBrDisp(int Opc)

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

static void RemoveDeadAddBetweenLEAAndJT(MachineInstr *LEAMI, MachineInstr *JumpMI, unsigned &DeadSize)

static bool isAlwaysIndirectTarget(const MachineBasicBlock &MBB)

static bool AlignBlocks(MachineFunction *MF, const ARMSubtarget *STI)

static cl::opt< bool > SynthesizeThumb1TBB("arm-synthesize-thumb-1-tbb", cl::Hidden, cl::init(true), cl::desc("Use compressed jump tables in Thumb-1 by synthesizing an " "equivalent to the TBB/TBH instructions"))

static cl::opt< bool > AdjustJumpTableBlocks("arm-adjust-jump-tables", cl::Hidden, cl::init(true), cl::desc("Adjust basic block layout to better use TB[BH]"))

#define ARM_CP_ISLANDS_OPT_NAME

static bool BBIsJumpedOver(MachineBasicBlock *MBB)

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

MachineBasicBlock MachineBasicBlock::iterator MBBI

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.

This file defines the DenseMap class.

const HexagonInstrInfo * TII

This file implements the LivePhysRegs utility for tracking liveness of physical registers.

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

unsigned const TargetRegisterInfo * TRI

static bool BBHasFallthrough(MachineBasicBlock *MBB)

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

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

const SmallVectorImpl< MachineOperand > MachineBasicBlock * TBB

const SmallVectorImpl< MachineOperand > & Cond

assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())

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)

ARMFunctionInfo - This class is derived from MachineFunctionInfo and contains private ARM-specific in...

bool branchTargetEnforcement() const

const ARMTargetLowering * getTargetLowering() const override

Represent the analysis usage information of a pass.

AnalysisUsage & addRequired()

A parsed version of the target data layout string in and methods for querying it.

std::enable_if_t< GraphHasNodeNumbers< T * >, void > updateBlockNumbers()

Update dominator tree after renumbering blocks.

bool dominates(const BasicBlock *BB, const Use &U) const

Return true if the (end of the) basic block BB dominates the use U.

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

bool hasOptSize() const

Optimize this function for size (-Os) or minimum size (-Oz).

bool analyzeBranch(MachineBasicBlock &MBB, MachineBasicBlock *&TBB, MachineBasicBlock *&FBB, SmallVectorImpl< MachineOperand > &Cond, bool AllowModify) const override

Analyze the branching code at the end of MBB, returning true if it cannot be understood (e....

A set of physical registers with utility functions to track liveness when walking backward/forward th...

Describe properties that are true of each instruction in the target description file.

unsigned getNumOperands() const

Return the number of declared MachineOperands for this MachineInstruction.

unsigned getSize() const

Return the number of bytes in the encoding of this instruction, or zero if the encoding size cannot b...

unsigned pred_size() const

bool isEHPad() const

Returns true if the block is a landing pad.

void replaceSuccessor(MachineBasicBlock *Old, MachineBasicBlock *New)

Replace successor OLD with NEW and update probability info.

MachineBasicBlock * getFallThrough(bool JumpToFallThrough=true)

Return the fallthrough block if the block can implicitly transfer control to the block after it by fa...

void transferSuccessors(MachineBasicBlock *FromMBB)

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

instr_iterator insert(instr_iterator I, MachineInstr *M)

Insert MI into the instruction list before I, possibly inside a bundle.

iterator_range< livein_iterator > liveins() const

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 updateTerminator(MachineBasicBlock *PreviousLayoutSuccessor)

Update the terminator instructions in block to account for changes to block layout which may have bee...

bool canFallThrough()

Return true if the block can implicitly transfer control to the block after it by falling off the end...

succ_iterator succ_begin()

unsigned succ_size() const

bool hasAddressTaken() const

Test whether this block is used as something other than the target of a terminator,...

void setAlignment(Align A)

Set alignment of the basic block.

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

Add Succ as a successor of this MachineBasicBlock.

pred_iterator pred_begin()

iterator getLastNonDebugInstr(bool SkipPseudoOp=true)

Returns an iterator to the last non-debug instruction in the basic block, or end().

void addLiveIn(MCRegister PhysReg, LaneBitmask LaneMask=LaneBitmask::getAll())

Adds the specified register as a live in.

const MachineFunction * getParent() const

Return the MachineFunction containing this basic block.

iterator_range< iterator > terminators()

reverse_iterator rbegin()

bool isSuccessor(const MachineBasicBlock *MBB) const

Return true if the specified MBB is a successor of this 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

void moveAfter(MachineBasicBlock *NewBefore)

The MachineConstantPool class keeps track of constants referenced by a function which must be spilled...

Analysis pass which computes a MachineDominatorTree.

DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...

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

void getAnalysisUsage(AnalysisUsage &AU) const override

getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.

virtual bool runOnMachineFunction(MachineFunction &MF)=0

runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...

virtual MachineFunctionProperties getRequiredProperties() const

Properties which a MachineFunction may have at a given point in time.

MachineFunctionProperties & set(Property P)

Function & getFunction()

Return the LLVM function that this machine code represents.

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

const TargetMachine & getTarget() const

getTarget - Return the target machine this machine code is compiled with

BasicBlockListType::const_iterator const_iterator

const MachineInstrBuilder & addImm(int64_t Val) const

Add a new immediate operand.

const MachineInstrBuilder & add(const MachineOperand &MO) const

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 & addJumpTableIndex(unsigned Idx, unsigned TargetFlags=0) const

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

reverse_iterator getReverse() const

Get a reverse iterator to the same node.

Representation of each machine instruction.

unsigned getOpcode() const

Returns the opcode of this MachineInstr.

const MachineBasicBlock * getParent() const

const MCInstrDesc & getDesc() const

Returns the target instruction descriptor of this MachineInstr.

void setDesc(const MCInstrDesc &TID)

Replace the instruction descriptor (thus opcode) of the current instruction with a new one.

iterator_range< mop_iterator > operands()

void eraseFromParent()

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

const MachineOperand & getOperand(unsigned i) const

bool ReplaceMBBInJumpTable(unsigned Idx, MachineBasicBlock *Old, MachineBasicBlock *New)

ReplaceMBBInJumpTable - If Old is a target of the jump tables, update the jump table to branch to New...

@ EK_Inline

EK_Inline - Jump table entries are emitted inline at their point of use.

JTEntryKind getEntryKind() const

const std::vector< MachineJumpTableEntry > & getJumpTables() const

MachineOperand class - Representation of each machine instruction operand.

MachineBasicBlock * getMBB() const

bool isCPI() const

isCPI - Tests if this is a MO_ConstantPoolIndex operand.

void setReg(Register Reg)

Change the register this operand corresponds to.

void setIsKill(bool Val=true)

void setMBB(MachineBasicBlock *MBB)

getReg - Returns the register number.

MachineRegisterInfo - Keep track of information for virtual and physical registers,...

virtual StringRef getPassName() const

getPassName - Return a nice clean name for a pass.

Wrapper class representing virtual and physical registers.

SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...

size_type count(const T &V) const

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

std::pair< const_iterator, bool > insert(const T &V)

insert - Insert an element into the set if it isn't already there.

This class consists of common code factored out of the SmallVector class to reduce code duplication b...

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.

CodeGenOptLevel getOptLevel() const

Returns the optimization level: None, Less, Default, or Aggressive.

Value * getOperand(unsigned i) const

self_iterator getIterator()

NodeTy * getNextNode()

Get the next node, or nullptr for the list tail.

#define llvm_unreachable(msg)

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

static CondCodes getOppositeCondition(CondCodes CC)

@ MO_OPTION_MASK

MO_OPTION_MASK - Most flags are mutually exclusive; this mask selects just that part of the flag set.

@ MO_LO16

MO_LO16 - On a symbol operand, this represents a relocation containing lower 16 bit of the address.

@ MO_HI16

MO_HI16 - On a symbol operand, this represents a relocation containing higher 16 bit of the address.

unsigned ID

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

Reg

All possible values of the reg field in the ModR/M byte.

initializer< Ty > init(const Ty &Val)

This is an optimization pass for GlobalISel generic memory operations.

MachineInstr * findCMPToFoldIntoCBZ(MachineInstr *Br, const TargetRegisterInfo *TRI)

Search backwards from a tBcc to find a tCMPi8 against 0, meaning we can convert them to a tCBZ or tCB...

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.

static bool isARMLowRegister(MCRegister Reg)

isARMLowRegister - Returns true if the register is a low register (r0-r7).

bool isAligned(Align Lhs, uint64_t SizeInBytes)

Checks that SizeInBytes is a multiple of the alignment.

iterator_range< T > make_range(T x, T y)

Convenience function for iterating over sub-ranges.

bool registerDefinedBetween(unsigned Reg, MachineBasicBlock::iterator From, MachineBasicBlock::iterator To, const TargetRegisterInfo *TRI)

Return true if Reg is defd between From and To.

static std::array< MachineOperand, 2 > predOps(ARMCC::CondCodes Pred, unsigned PredReg=0)

Get the operands corresponding to the given Pred value.

ARMCC::CondCodes getITInstrPredicate(const MachineInstr &MI, Register &PredReg)

getITInstrPredicate - Valid only in Thumb2 mode.

auto reverse(ContainerTy &&C)

raw_ostream & dbgs()

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

void report_fatal_error(Error Err, bool gen_crash_diag=true)

Report a serious error, calling any installed error handler.

static bool isLoopStart(const MachineInstr &MI)

bool is_sorted(R &&Range, Compare C)

Wrapper function around std::is_sorted to check if elements in a range R are sorted with respect to a...

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

unsigned getRegState(const MachineOperand &RegOp)

Get all register state flags from machine operand RegOp.

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

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

unsigned getKillRegState(bool B)

ARMCC::CondCodes getInstrPredicate(const MachineInstr &MI, Register &PredReg)

getInstrPredicate - If instruction is predicated, returns its predicate condition,...

FunctionPass * createARMConstantIslandPass()

createARMConstantIslandPass - returns an instance of the constpool island pass.

auto find_if(R &&Range, UnaryPredicate P)

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

unsigned UnknownPadding(Align Alignment, unsigned KnownBits)

UnknownPadding - Return the worst case padding that could result from unknown offset bits.

APFloat neg(APFloat X)

Returns the negated value of the argument.

unsigned Log2(Align A)

Returns the log2 of the alignment.

static bool isSpeculationBarrierEndBBOpcode(int Opc)

IterT prev_nodbg(IterT It, IterT Begin, bool SkipPseudoOp=true)

Decrement It, then continue decrementing it while it points to a debug instruction.

Printable printMBBReference(const MachineBasicBlock &MBB)

Prints a machine basic block reference.

This struct is a compact representation of a valid (non-zero power of two) alignment.

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 internalKnownBits() const

Compute the number of known offset bits internally to this block.

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.

Pair of physical register and lane mask.

MachineJumpTableEntry - One jump table in the jump table info.