MachineOutliner.cpp Source File (original) (raw)

81#include

82#include

84#define DEBUG_TYPE "machine-outliner"

86using namespace llvm;

87using namespace ore;

88using namespace outliner;

91 STATISTIC(NumOutlined, "Number of candidates outlined");

92 STATISTIC(FunctionsCreated, "Number of functions created");

95 STATISTIC(NumLegalInUnsignedVec, "Outlinable instructions mapped");

97 "Unoutlinable instructions mapped + number of sentinel values");

98 STATISTIC(NumSentinels, "Sentinel values inserted during mapping");

100 "Invisible instructions skipped during mapping");

102 "Total number of instructions mapped and saved to mapping vector");

104 "Count of hashing attempts made for outlined functions");

106 "Count of unsuccessful hashing attempts for outlined functions");

107

108

109

110

111

112

114 "enable-linkonceodr-outlining", cl::Hidden,

115 cl::desc("Enable the machine outliner on linkonceodr functions"),

117

118

119

120

124 "Number of times to rerun the outliner after the initial outline"));

125

129 "The minimum size in bytes before an outlining candidate is accepted"));

130

133 cl::desc("Consider all leaf descendants of internal nodes of the suffix "

134 "tree as candidates for outlining (if false, only leaf children "

135 "are considered)"));

136

139 cl::desc("Disable global outlining only by ignoring "

140 "the codegen data generation or use"),

142

144 "append-content-hash-outlined-name", cl::Hidden,

145 cl::desc("This appends the content hash to the globally outlined function "

146 "name. It's beneficial for enhancing the precision of the stable "

147 "hash and for ordering the outlined functions."),

149

150namespace {

151

152

153struct InstructionMapper {

155

156

157

158

159

160 unsigned IllegalInstrNumber = -3;

161

162

163

164 unsigned LegalInstrNumber = 0;

165

166

168 InstructionIntegerMap;

169

170

172

173

175

176

177

179

180

181

182

183

184 bool AddedIllegalLastTime = false;

185

186

187

188

189

190

191

192 unsigned mapToLegalUnsigned(

194 bool &HaveLegalRange, unsigned &NumLegalInBlock,

197

198

199 AddedIllegalLastTime = false;

200

201

202

203 if (CanOutlineWithPrevInstr)

204 HaveLegalRange = true;

205 CanOutlineWithPrevInstr = true;

206

207

208 NumLegalInBlock++;

209

210

211

214 bool WasInserted;

216 ResultIt;

217 std::tie(ResultIt, WasInserted) =

218 InstructionIntegerMap.insert(std::make_pair(&MI, LegalInstrNumber));

219 unsigned MINumber = ResultIt->second;

220

221

222 if (WasInserted)

223 LegalInstrNumber++;

224

225 UnsignedVecForMBB.push_back(MINumber);

226

227

228 if (LegalInstrNumber >= IllegalInstrNumber)

230

232 "Tried to assign DenseMap tombstone or empty key to instruction.");

234 "Tried to assign DenseMap tombstone or empty key to instruction.");

235

236

237 ++NumLegalInUnsignedVec;

238 return MINumber;

239 }

240

241

242

243

244

245

246

247 unsigned mapToIllegalUnsigned(

251

252 CanOutlineWithPrevInstr = false;

253

254

255 if (AddedIllegalLastTime)

256 return IllegalInstrNumber;

257

258

259 AddedIllegalLastTime = true;

260 unsigned MINumber = IllegalInstrNumber;

261

263 UnsignedVecForMBB.push_back(IllegalInstrNumber);

264 IllegalInstrNumber--;

265

266 ++NumIllegalInUnsignedVec;

267

268 assert(LegalInstrNumber < IllegalInstrNumber &&

269 "Instruction mapping overflow!");

270

272 "IllegalInstrNumber cannot be DenseMap tombstone or empty key!");

273

275 "IllegalInstrNumber cannot be DenseMap tombstone or empty key!");

276

277 return MINumber;

278 }

279

280

281

282

283

284

285

286

287

288

289

293 << "' to unsigned vector ***\n");

294 unsigned Flags = 0;

295

296

297 if ( TII .isMBBSafeToOutlineFrom(MBB, Flags))

298 return;

299

300 auto OutlinableRanges = TII.getOutlinableRanges(MBB, Flags);

302 << " outlinable range(s)\n");

303 if (OutlinableRanges.empty())

304 return;

305

306

308

310

311

312

313 unsigned NumLegalInBlock = 0;

314

315

316

317 bool HaveLegalRange = false;

318

319

320

321 bool CanOutlineWithPrevInstr = false;

322

323

324

327

328 LLVM_DEBUG(dbgs() << "*** Mapping outlinable ranges ***\n");

329 for (auto &OutlinableRange : OutlinableRanges) {

330 auto OutlinableRangeBegin = OutlinableRange.first;

331 auto OutlinableRangeEnd = OutlinableRange.second;

332#ifndef NDEBUG

334 dbgs() << "Mapping "

335 << std::distance(OutlinableRangeBegin, OutlinableRangeEnd)

336 << " instruction range\n");

337

338 unsigned NumSkippedInRange = 0;

339#endif

340 for (; It != OutlinableRangeBegin; ++It) {

341#ifndef NDEBUG

342 ++NumSkippedInRange;

343#endif

344 mapToIllegalUnsigned(It, CanOutlineWithPrevInstr, UnsignedVecForMBB,

345 InstrListForMBB);

346 }

347#ifndef NDEBUG

349 << " instructions outside outlinable range\n");

350#endif

351 assert(It != MBB.end() && "Should still have instructions?");

352

353

354 for (; It != OutlinableRangeEnd; ++It) {

355

356 switch (TII.getOutliningType(MMI, It, Flags)) {

357 case InstrType::Illegal:

358 mapToIllegalUnsigned(It, CanOutlineWithPrevInstr, UnsignedVecForMBB,

359 InstrListForMBB);

360 break;

361

362 case InstrType::Legal:

363 mapToLegalUnsigned(It, CanOutlineWithPrevInstr, HaveLegalRange,

364 NumLegalInBlock, UnsignedVecForMBB,

365 InstrListForMBB);

366 break;

367

368 case InstrType::LegalTerminator:

369 mapToLegalUnsigned(It, CanOutlineWithPrevInstr, HaveLegalRange,

370 NumLegalInBlock, UnsignedVecForMBB,

371 InstrListForMBB);

372

373

374 mapToIllegalUnsigned(It, CanOutlineWithPrevInstr, UnsignedVecForMBB,

375 InstrListForMBB);

376 break;

377

378 case InstrType::Invisible:

379

380

381 ++NumInvisible;

382 AddedIllegalLastTime = false;

383 break;

384 }

385 }

386 }

387

388 LLVM_DEBUG(dbgs() << "HaveLegalRange = " << HaveLegalRange << "\n");

389

390

391

392 if (HaveLegalRange) {

393

394

395

396

397 mapToIllegalUnsigned(It, CanOutlineWithPrevInstr, UnsignedVecForMBB,

398 InstrListForMBB);

399 ++NumSentinels;

401 append_range(UnsignedVec, UnsignedVecForMBB);

402 }

403 }

404

406

407

409 "DenseMapInfo's empty key isn't -1!");

411 "DenseMapInfo's tombstone key isn't -2!");

412 }

413};

414

415

416

417

418

419

420

421

422

423

424struct MachineOutliner : public ModulePass {

425

426 static char ID;

427

429

430

431

432 bool OutlineFromLinkOnceODRs = false;

433

434

435 unsigned OutlineRepeatedNum = 0;

436

437

438

439

440

441 bool RunOnAllFunctions = true;

442

443

444

445

446

447

448

449 std::unique_ptr LocalHashTree;

450

451

452

453

454

455

456

457

458 CGDataMode OutlinerMode = CGDataMode::None;

459

461

468 }

469

472 }

473

474

475

476 void emitNotOutliningCheaperRemark(

477 unsigned StringLen, std::vector &CandidatesForRepeatedSeq,

479

480

482

483

484

485

486

487

488

489

490

491

492

493

494

495

496 void

497 findCandidates(InstructionMapper &Mapper,

498 std::vector<std::unique_ptr> &FunctionList);

499

500

501

502

503

504

505

506 void findGlobalCandidates(

507 InstructionMapper &Mapper,

508 std::vector<std::unique_ptr> &FunctionList);

509

510

511

512

513

514

515

516

517 bool outline(Module &M,

518 std::vector<std::unique_ptr> &FunctionList,

519 InstructionMapper &Mapper, unsigned &OutlinedFunctionNum);

520

521

523 InstructionMapper &Mapper,

524 unsigned Name);

525

526

527

528

529 void computeAndPublishHashSequence(MachineFunction &MF, unsigned CandSize);

530

531

532 void initializeOutlinerMode(const Module &M);

533

534

535 void emitOutlinedHashTree(Module &M);

536

537

539

540

541

542 bool doOutline(Module &M, unsigned &OutlinedFunctionNum);

543

544

545

550 return SP;

551 return nullptr;

552 }

553

554

555

556 void populateMapper(InstructionMapper &Mapper, Module &M);

557

558

559

560

561

562 void initSizeRemarkInfo(const Module &M,

564

565

566

567 void

568 emitInstrCountChangedRemark(const Module &M,

570};

571}

572

573char MachineOutliner::ID = 0;

574

575namespace llvm {

577 MachineOutliner *OL = new MachineOutliner();

578 OL->RunOnAllFunctions = RunOnAllFunctions;

579 return OL;

580}

581

582}

583

585 false)

586

587void MachineOutliner::emitNotOutliningCheaperRemark(

588 unsigned StringLen, std::vector<Candidate> &CandidatesForRepeatedSeq,

590

591

592

593

594 Candidate &C = CandidatesForRepeatedSeq.front();

596 MORE.emit([&]() {

598 C.front().getDebugLoc(), C.getMBB());

599 R << "Did not outline " << NV("Length", StringLen) << " instructions"

600 << " from " << NV("NumOccurrences", CandidatesForRepeatedSeq.size())

601 << " locations."

602 << " Bytes from outlining all occurrences ("

603 << NV("OutliningCost", OF.getOutliningCost()) << ")"

604 << " >= Unoutlined instruction bytes ("

605 << NV("NotOutliningCost", OF.getNotOutlinedCost()) << ")"

606 << " (Also found at: ";

607

608

609 for (unsigned i = 1, e = CandidatesForRepeatedSeq.size(); i < e; i++) {

610 R << NV((Twine("OtherStartLoc") + Twine(i)).str(),

611 CandidatesForRepeatedSeq[i].front().getDebugLoc());

612 if (i != e - 1)

613 R << ", ";

614 }

615

616 R << ")";

617 return R;

618 });

619}

620

621void MachineOutliner::emitOutlinedFunctionRemark(OutlinedFunction &OF) {

626 R << "Saved " << NV("OutliningBenefit", OF.getBenefit()) << " bytes by "

627 << "outlining " << NV("Length", OF.getNumInstrs()) << " instructions "

629 << " locations. "

630 << "(Found at: ";

631

632

633 for (size_t i = 0, e = OF.Candidates.size(); i < e; i++) {

634

636 OF.Candidates[i].front().getDebugLoc());

637 if (i != e - 1)

638 R << ", ";

639 }

640

641 R << ")";

642

643 MORE.emit(R);

644}

645

653};

654

655

656

657

659 auto &InstrList = Mapper.InstrList;

660 auto &UnsignedVec = Mapper.UnsignedVec;

661

663 auto Size = UnsignedVec.size();

664

665

668

669 auto getValidInstr = [&](unsigned Index) -> const MachineInstr * {

670 if (UnsignedVec[Index] >= Mapper.LegalInstrNumber)

671 return nullptr;

672 return &(*InstrList[Index]);

673 };

674

675 auto getStableHashAndFollow =

678 if (!StableHash)

679 return nullptr;

680 auto It = CurrNode->Successors.find(StableHash);

681 return (It == CurrNode->Successors.end()) ? nullptr : It->second.get();

682 };

683

684 for (unsigned I = 0; I < Size; ++I) {

686 if ( || MI->isDebugInstr())

687 continue;

688 const HashNode *CurrNode = getStableHashAndFollow(*MI, RootNode);

689 if (!CurrNode)

690 continue;

691

692 for (unsigned J = I + 1; J < Size; ++J) {

694 if (!MJ)

695 break;

696

698 continue;

699 CurrNode = getStableHashAndFollow(*MJ, CurrNode);

700 if (!CurrNode)

701 break;

702

703

704 if (auto Count = CurrNode->Terminals)

706 }

707 }

708

709 return MatchedEntries;

710}

711

712void MachineOutliner::findGlobalCandidates(

713 InstructionMapper &Mapper,

714 std::vector<std::unique_ptr> &FunctionList) {

715 FunctionList.clear();

716 auto &InstrList = Mapper.InstrList;

717 auto &MBBFlagsMap = Mapper.MBBFlagsMap;

718

719 std::vector CandidatesForRepeatedSeq;

721 CandidatesForRepeatedSeq.clear();

724 auto Length = ME.EndIdx - ME.StartIdx + 1;

726 CandidatesForRepeatedSeq.emplace_back(ME.StartIdx, Length, StartIt, EndIt,

727 MBB, FunctionList.size(),

728 MBBFlagsMap[MBB]);

731 unsigned MinRepeats = 1;

732 std::optional<std::unique_ptr> OF =

733 TII->getOutliningCandidateInfo(*MMI, CandidatesForRepeatedSeq,

734 MinRepeats);

735 if (!OF.has_value() || OF.value()->Candidates.empty())

736 continue;

737

738 assert(OF.value()->Candidates.size() == MinRepeats);

739 FunctionList.emplace_back(std::make_unique(

740 std::move(OF.value()), ME.Count));

741 }

742}

743

744void MachineOutliner::findCandidates(

745 InstructionMapper &Mapper,

746 std::vector<std::unique_ptr> &FunctionList) {

747 FunctionList.clear();

749

750

751

752 std::vector CandidatesForRepeatedSeq;

753 LLVM_DEBUG(dbgs() << "*** Discarding overlapping candidates *** \n");

755 dbgs() << "Searching for overlaps in all repeated sequences...\n");

757 CandidatesForRepeatedSeq.clear();

758 unsigned StringLen = RS.Length;

759 LLVM_DEBUG(dbgs() << " Sequence length: " << StringLen << "\n");

760

761#ifndef NDEBUG

762 unsigned NumDiscarded = 0;

763 unsigned NumKept = 0;

764#endif

765

766

768 for (const unsigned &StartIdx : RS.StartIndices) {

769

770

771

772

773

774

775

776

777

778

779

780

781

782

783

784

785

786

787

788

789

790 unsigned EndIdx = StartIdx + StringLen - 1;

791 if (!CandidatesForRepeatedSeq.empty() &&

792 StartIdx <= CandidatesForRepeatedSeq.back().getEndIdx()) {

793#ifndef NDEBUG

794 ++NumDiscarded;

795 LLVM_DEBUG(dbgs() << " .. DISCARD candidate @ [" << StartIdx << ", "

796 << EndIdx << "]; overlaps with candidate @ ["

797 << CandidatesForRepeatedSeq.back().getStartIdx()

798 << ", " << CandidatesForRepeatedSeq.back().getEndIdx()

799 << "]\n");

800#endif

801 continue;

802 }

803

804

805

806#ifndef NDEBUG

807 ++NumKept;

808#endif

812 CandidatesForRepeatedSeq.emplace_back(StartIdx, StringLen, StartIt, EndIt,

813 MBB, FunctionList.size(),

814 Mapper.MBBFlagsMap[MBB]);

815 }

816#ifndef NDEBUG

817 LLVM_DEBUG(dbgs() << " Candidates discarded: " << NumDiscarded

818 << "\n");

819 LLVM_DEBUG(dbgs() << " Candidates kept: " << NumKept << "\n\n");

820#endif

821 unsigned MinRepeats = 2;

822

823

824

825

826 if (CandidatesForRepeatedSeq.size() < MinRepeats)

827 continue;

828

829

830

832 CandidatesForRepeatedSeq[0].getMF()->getSubtarget().getInstrInfo();

833

834 std::optional<std::unique_ptr> OF =

835 TII->getOutliningCandidateInfo(*MMI, CandidatesForRepeatedSeq,

836 MinRepeats);

837

838

839

840 if (!OF.has_value() || OF.value()->Candidates.size() < MinRepeats)

841 continue;

842

843

845 emitNotOutliningCheaperRemark(StringLen, CandidatesForRepeatedSeq,

846 *OF.value());

847 continue;

848 }

849

850 FunctionList.emplace_back(std::move(OF.value()));

851 }

852}

853

854void MachineOutliner::computeAndPublishHashSequence(MachineFunction &MF,

855 unsigned CandSize) {

856

858 for (auto &MBB : MF) {

859 for (auto &NewMI : MBB) {

861 if (!Hash) {

862 OutlinedHashSequence.clear();

863 break;

864 }

865 OutlinedHashSequence.push_back(Hash);

866 }

867 }

868

869

872 auto NewName =

873 MF.getName().str() + ".content." + std::to_string(CombinedHash);

874 MF.getFunction().setName(NewName);

875 }

876

877

878 if (OutlinerMode == CGDataMode::Write) {

879 StableHashAttempts++;

880 if (!OutlinedHashSequence.empty())

881 LocalHashTree->insert({OutlinedHashSequence, CandSize});

882 else

883 StableHashDropped++;

884 }

885}

886

889

890

891

892

893 std::string FunctionName = "OUTLINED_FUNCTION_";

894 if (OutlineRepeatedNum > 0)

895 FunctionName += std::to_string(OutlineRepeatedNum + 1) + "_";

896 FunctionName += std::to_string(Name);

897 LLVM_DEBUG(dbgs() << "NEW FUNCTION: " << FunctionName << "\n");

898

899

902 Function::ExternalLinkage, FunctionName, M);

903

904

905

907 F->setUnnamedAddr(GlobalValue::UnnamedAddr::Global);

908

909

910

911 F->addFnAttr(Attribute::OptimizeForSize);

912 F->addFnAttr(Attribute::MinSize);

913

917

918 TII.mergeOutliningCandidateAttributes(*F, OF.Candidates);

919

920

924 return std::max(K, C.getMF()->getFunction().getUWTableKind());

925 });

926 F->setUWTableKind(UW);

927

930 Builder.CreateRetVoid();

931

932 MachineModuleInfo &MMI = getAnalysis().getMMI();

936

937

939

941 const std::vector &Instrs =

943 for (auto &MI : FirstCand) {

944 if (MI.isDebugInstr())

945 continue;

946

947

949 if (MI.isCFIInstruction()) {

950 unsigned CFIIndex = MI.getOperand(0).getCFIIndex();

954 } else {

958 }

959 }

960

961 if (OutlinerMode != CGDataMode::None)

962 computeAndPublishHashSequence(MF, OF.Candidates.size());

963

964

965 MF.getProperties().reset(MachineFunctionProperties::Property::IsSSA);

966 MF.getProperties().set(MachineFunctionProperties::Property::NoPHIs);

967 MF.getProperties().set(MachineFunctionProperties::Property::NoVRegs);

968 MF.getProperties().set(MachineFunctionProperties::Property::TracksLiveness);

970

971

976

979 CandLiveIns.addLiveOuts(OutlineBB);

982 CandLiveIns.stepBackward(MI);

983

984

985

986 for (MCPhysReg Reg : CandLiveIns)

987 LiveIns.addReg(Reg);

988 }

990

991 TII.buildOutlinedFrame(MBB, MF, OF);

992

993

994

996

999 DIFile *Unit = SP->getFile();

1001

1002 std::string Dummy;

1005

1007 Unit , F->getName(), StringRef(Dummy), Unit ,

1008 0 ,

1009 DB.createSubroutineType(DB.getOrCreateTypeArray({})),

1010 0,

1011 DINode::DIFlags::FlagArtificial ,

1012

1013 DISubprogram::SPFlagDefinition | DISubprogram::SPFlagOptimized);

1014

1015

1016 DB.finalizeSubprogram(OutlinedSP);

1017

1018

1019 F->setSubprogram(OutlinedSP);

1020

1021 DB.finalize();

1022 }

1023

1024 return &MF;

1025}

1026

1027bool MachineOutliner::outline(

1028 Module &M, std::vector<std::unique_ptr> &FunctionList,

1029 InstructionMapper &Mapper, unsigned &OutlinedFunctionNum) {

1031 LLVM_DEBUG(dbgs() << "NUMBER OF POTENTIAL FUNCTIONS: " << FunctionList.size()

1032 << "\n");

1033 bool OutlinedSomething = false;

1034

1035

1036

1037 stable_sort(FunctionList, [](const std::unique_ptr &LHS,

1038 const std::unique_ptr &RHS) {

1039 return LHS->getNotOutlinedCost() * RHS->getOutliningCost() >

1040 RHS->getNotOutlinedCost() * LHS->getOutliningCost();

1041 });

1042

1043

1044

1045 auto *UnsignedVecBegin = Mapper.UnsignedVec.begin();

1047 for (auto &OF : FunctionList) {

1048#ifndef NDEBUG

1049 auto NumCandidatesBefore = OF->Candidates.size();

1050#endif

1051

1052

1054 return std::any_of(UnsignedVecBegin + C.getStartIdx(),

1055 UnsignedVecBegin + C.getEndIdx() + 1, [](unsigned I) {

1056 return I == static_cast(-1);

1057 });

1058 });

1059

1060#ifndef NDEBUG

1061 auto NumCandidatesAfter = OF->Candidates.size();

1062 LLVM_DEBUG(dbgs() << "PRUNED: " << NumCandidatesBefore - NumCandidatesAfter

1063 << "/" << NumCandidatesBefore << " candidates\n");

1064#endif

1065

1066

1070 << " B)\n");

1071 continue;

1072 }

1073

1076 << " B)\n");

1077

1078

1079

1081 emitOutlinedFunctionRemark(*OF);

1082 FunctionsCreated++;

1083 OutlinedFunctionNum++;

1087

1088

1094

1095

1096 auto CallInst = TII.insertOutlinedCall(M, MBB, StartIt, *MF, C);

1097

1098#ifndef NDEBUG

1099 auto MBBBeingOutlinedFromName =

1102 ? ""

1105 << MFBeingOutlinedFromName << ":"

1106 << MBBBeingOutlinedFromName << "\n");

1108#endif

1109

1110

1111

1112

1113

1115 MachineFunctionProperties::Property::TracksLiveness)) {

1116

1117

1118

1120

1121

1122

1123

1124

1125

1129 Iter != Last; Iter++) {

1133

1134 if (!MOP.isReg())

1135 continue;

1136

1137 if (MOP.isDef()) {

1138

1139 DefRegs.insert(MOP.getReg());

1140 if (UseRegs.count(MOP.getReg()) &&

1141 !InstrUseRegs.count(MOP.getReg()))

1142

1143

1144 UseRegs.erase(MOP.getReg());

1145 } else if (!MOP.isUndef()) {

1146

1147

1148 UseRegs.insert(MOP.getReg());

1149 InstrUseRegs.insert(MOP.getReg());

1150 }

1151 }

1152 if (MI->isCandidateForAdditionalCallInfo())

1153 MI->getMF()->eraseAdditionalCallInfo(MI);

1154 }

1155

1156 for (const Register &I : DefRegs)

1157

1160 true ));

1161

1162 for (const Register &I : UseRegs)

1163

1166 true ));

1167 }

1168

1169

1170

1171

1172 MBB.erase(std::next(StartIt), std::next(EndIt));

1173

1174

1175 for (unsigned &I : make_range(UnsignedVecBegin + C.getStartIdx(),

1176 UnsignedVecBegin + C.getEndIdx() + 1))

1177 I = static_cast<unsigned>(-1);

1178 OutlinedSomething = true;

1179

1180

1181 NumOutlined++;

1182 }

1183 }

1184

1185 LLVM_DEBUG(dbgs() << "OutlinedSomething = " << OutlinedSomething << "\n");

1186 return OutlinedSomething;

1187}

1188

1189void MachineOutliner::populateMapper(InstructionMapper &Mapper, Module &M) {

1190

1191

1192 LLVM_DEBUG(dbgs() << "*** Populating mapper ***\n");

1194 LLVM_DEBUG(dbgs() << "MAPPING FUNCTION: " << F.getName() << "\n");

1195

1196 if (F.hasFnAttribute("nooutline")) {

1197 LLVM_DEBUG(dbgs() << "SKIP: Function has nooutline attribute\n");

1198 continue;

1199 }

1200

1201

1202

1204

1205

1206

1207 if (!MF) {

1208 LLVM_DEBUG(dbgs() << "SKIP: Function does not have a MachineFunction\n");

1209 continue;

1210 }

1211

1213 if (!RunOnAllFunctions && TII ->shouldOutlineFromFunctionByDefault(*MF)) {

1214 LLVM_DEBUG(dbgs() << "SKIP: Target does not want to outline from "

1215 "function by default\n");

1216 continue;

1217 }

1218

1219

1220

1221 if ( TII ->isFunctionSafeToOutlineFrom(*MF, OutlineFromLinkOnceODRs)) {

1223 << ": unsafe to outline from\n");

1224 continue;

1225 }

1226

1227

1228

1229

1230 const unsigned MinMBBSize = 2;

1231

1234

1235

1236

1237

1238

1239

1240 if (MBB.size() < MinMBBSize) {

1241 LLVM_DEBUG(dbgs() << " SKIP: MBB size less than minimum size of "

1242 << MinMBBSize << "\n");

1243 continue;

1244 }

1245

1246

1247

1249 LLVM_DEBUG(dbgs() << " SKIP: MBB's address is taken\n");

1250 continue;

1251 }

1252

1253

1254 Mapper.convertToUnsignedVec(MBB, *TII);

1255 }

1256 }

1257

1258 UnsignedVecSize = Mapper.UnsignedVec.size();

1259}

1260

1261void MachineOutliner::initSizeRemarkInfo(

1263

1264

1267

1268

1269

1270 if (!MF)

1271 continue;

1273 }

1274}

1275

1276void MachineOutliner::emitInstrCountChangedRemark(

1278

1279

1280

1283

1284

1285

1286 if (!MF)

1287 continue;

1288

1289 std::string Fname = std::string(F.getName());

1291 unsigned FnCountBefore = 0;

1292

1293

1294 auto It = FunctionToInstrCount.find(Fname);

1295

1296

1297

1298 if (It != FunctionToInstrCount.end())

1299 FnCountBefore = It->second;

1300

1301

1302 int64_t FnDelta = static_cast<int64_t>(FnCountAfter) -

1303 static_cast<int64_t>(FnCountBefore);

1304 if (FnDelta == 0)

1305 continue;

1306

1308 MORE.emit([&]() {

1312 << ": Function: "

1314 << ": MI instruction count changed from "

1316 FnCountBefore)

1317 << " to "

1319 FnCountAfter)

1320 << "; Delta: "

1322 return R;

1323 });

1324 }

1325}

1326

1327void MachineOutliner::initializeOutlinerMode(const Module &M) {

1329 return;

1330

1331 if (auto *IndexWrapperPass =

1332 getAnalysisIfAvailable()) {

1333 auto *TheIndex = IndexWrapperPass->getIndex();

1334

1335

1336 if (TheIndex && !TheIndex->hasExportedFunctions(M))

1337 return;

1338 }

1339

1340

1341

1342

1343

1345 OutlinerMode = CGDataMode::Write;

1346

1347 LocalHashTree = std::make_unique();

1348

1350 OutlinerMode = CGDataMode::Read;

1351}

1352

1353void MachineOutliner::emitOutlinedHashTree(Module &M) {

1354 assert(LocalHashTree);

1355 if (!LocalHashTree->empty()) {

1357 dbgs() << "Emit outlined hash tree. Size: " << LocalHashTree->size()

1358 << "\n";

1359 });

1362

1364 HTR.serialize(OS);

1365

1367 std::unique_ptr Buffer =

1369

1372 M, *Buffer,

1374 }

1375}

1376

1377bool MachineOutliner::runOnModule(Module &M) {

1378

1379

1380 if (M.empty())

1381 return false;

1382

1383

1384 initializeOutlinerMode(M);

1385

1386 MMI = &getAnalysis().getMMI();

1387

1388

1389 unsigned OutlinedFunctionNum = 0;

1390

1391 OutlineRepeatedNum = 0;

1392 if (!doOutline(M, OutlinedFunctionNum))

1393 return false;

1394

1396 OutlinedFunctionNum = 0;

1397 OutlineRepeatedNum++;

1398 if (!doOutline(M, OutlinedFunctionNum)) {

1400 dbgs() << "Did not outline on iteration " << I + 2 << " out of "

1402 });

1403 break;

1404 }

1405 }

1406

1407 if (OutlinerMode == CGDataMode::Write)

1408 emitOutlinedHashTree(M);

1409

1410 return true;

1411}

1412

1413bool MachineOutliner::doOutline(Module &M, unsigned &OutlinedFunctionNum) {

1414

1415

1416

1417

1418

1420 dbgs() << "Machine Outliner: Running on ";

1421 if (RunOnAllFunctions)

1422 dbgs() << "all functions";

1423 else

1424 dbgs() << "target-default functions";

1425 dbgs() << "\n";

1426 });

1427

1428

1429

1431 InstructionMapper Mapper(*MMI);

1432

1433

1434 populateMapper(Mapper, M);

1435 std::vector<std::unique_ptr> FunctionList;

1436

1437

1438 if (OutlinerMode == CGDataMode::Read)

1439 findGlobalCandidates(Mapper, FunctionList);

1440 else

1441 findCandidates(Mapper, FunctionList);

1442

1443

1444

1445

1446

1447

1448

1449

1450

1451

1452 bool ShouldEmitSizeRemarks = M.shouldEmitInstrCountChangedRemark();

1454 if (ShouldEmitSizeRemarks)

1455 initSizeRemarkInfo(M, FunctionToInstrCount);

1456

1457

1458 bool OutlinedSomething =

1459 outline(M, FunctionList, Mapper, OutlinedFunctionNum);

1460

1461

1462

1463

1464 if (ShouldEmitSizeRemarks && OutlinedSomething)

1465 emitInstrCountChangedRemark(M, FunctionToInstrCount);

1466

1468 if (!OutlinedSomething)

1469 dbgs() << "Stopped outlining at iteration " << OutlineRepeatedNum

1470 << " because no changes were found.\n";

1471 });

1472

1473 return OutlinedSomething;

1474}

unsigned const MachineRegisterInfo * MRI

MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL

This file defines the DenseMap class.

const HexagonInstrInfo * TII

static DISubprogram * getSubprogramOrNull(OutlinableGroup &Group)

Get the subprogram if it exists for one of the outlined regions.

Module.h This file contains the declarations for the Module class.

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

static DebugLoc getDebugLoc(MachineBasicBlock::instr_iterator FirstMI, MachineBasicBlock::instr_iterator LastMI)

Return the first found DebugLoc that has a DILocation, given a range of instructions.

static cl::opt< bool > DisableGlobalOutlining("disable-global-outlining", cl::Hidden, cl::desc("Disable global outlining only by ignoring " "the codegen data generation or use"), cl::init(false))

static cl::opt< unsigned > OutlinerBenefitThreshold("outliner-benefit-threshold", cl::init(1), cl::Hidden, cl::desc("The minimum size in bytes before an outlining candidate is accepted"))

static cl::opt< bool > OutlinerLeafDescendants("outliner-leaf-descendants", cl::init(true), cl::Hidden, cl::desc("Consider all leaf descendants of internal nodes of the suffix " "tree as candidates for outlining (if false, only leaf children " "are considered)"))

static cl::opt< bool > AppendContentHashToOutlinedName("append-content-hash-outlined-name", cl::Hidden, cl::desc("This appends the content hash to the globally outlined function " "name. It's beneficial for enhancing the precision of the stable " "hash and for ordering the outlined functions."), cl::init(true))

static cl::opt< unsigned > OutlinerReruns("machine-outliner-reruns", cl::init(0), cl::Hidden, cl::desc("Number of times to rerun the outliner after the initial outline"))

Number of times to re-run the outliner.

static cl::opt< bool > EnableLinkOnceODROutlining("enable-linkonceodr-outlining", cl::Hidden, cl::desc("Enable the machine outliner on linkonceodr functions"), cl::init(false))

static SmallVector< MatchedEntry > getMatchedEntries(InstructionMapper &Mapper)

Contains all data structures shared between the outliner implemented in MachineOutliner....

unsigned const TargetRegisterInfo * TRI

This is the interface to build a ModuleSummaryIndex for a module.

static Expected< Function * > createOutlinedFunction(OpenMPIRBuilder &OMPBuilder, IRBuilderBase &Builder, const OpenMPIRBuilder::TargetKernelDefaultAttrs &DefaultAttrs, StringRef FuncName, SmallVectorImpl< Value * > &Inputs, OpenMPIRBuilder::TargetBodyGenCallbackTy &CBFunc, OpenMPIRBuilder::TargetGenArgAccessorsCallbackTy &ArgAccessorFuncCB)

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

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

This file defines the SmallSet class.

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

#define STATISTIC(VARNAME, DESC)

Represent the analysis usage information of a pass.

AnalysisUsage & addUsedIfAvailable()

Add the specified Pass class to the set of analyses used by this pass.

AnalysisUsage & addRequired()

AnalysisUsage & addPreserved()

Add the specified Pass class to the set of analyses preserved by this pass.

void setPreservesAll()

Set by analyses that do not transform their input at all.

LLVM Basic Block Representation.

static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)

Creates a new BasicBlock.

This class represents a function call, abstracting a target machine's calling convention.

DISubprogram * getSubprogram() const

Get the subprogram for this scope.

std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)

static Function * Create(FunctionType *Ty, LinkageTypes Linkage, unsigned AddrSpace, const Twine &N="", Module *M=nullptr)

@ InternalLinkage

Rename collisions when linking (static functions).

This provides a uniform API for creating instructions and inserting them into a basic block: either a...

Legacy wrapper pass to provide the ModuleSummaryIndex object.

This is an important class for using LLVM in a threaded context.

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

bool hasAddressTaken() const

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

DebugLoc findDebugLoc(instr_iterator MBBI)

Find the next valid DebugLoc starting at MBBI, skipping any debug instructions.

const MachineFunction * getParent() const

Return the MachineFunction containing this basic block.

instr_iterator erase(instr_iterator I)

Remove an instruction from the instruction list and delete it.

StringRef getName() const

Return the name of the corresponding LLVM basic block, or an empty string.

MachineFunctionProperties & set(Property P)

bool hasProperty(Property P) const

MachineFunctionProperties & reset(Property P)

unsigned getInstructionCount() const

Return the number of MachineInstrs in this MachineFunction.

unsigned addFrameInst(const MCCFIInstruction &Inst)

const TargetSubtargetInfo & getSubtarget() const

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

const std::vector< MCCFIInstruction > & getFrameInstructions() const

Returns a reference to a list of cfi instructions in the function's prologue.

StringRef getName() const

getName - Return the name of the corresponding LLVM function.

MachineRegisterInfo & getRegInfo()

getRegInfo - Return information about the registers currently in use.

void setIsOutlined(bool V)

const MachineFunctionProperties & getProperties() const

Get the function properties.

const MachineBasicBlock & front() const

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

CreateMachineBasicBlock - Allocate a new MachineBasicBlock.

void insert(iterator MBBI, MachineBasicBlock *MBB)

const MachineInstrBuilder & addCFIIndex(unsigned CFIIndex) const

reverse_iterator getReverse() const

Get a reverse iterator to the same node.

Representation of each machine instruction.

const MachineBasicBlock * getParent() const

bool isDebugInstr() const

void dropMemRefs(MachineFunction &MF)

Clear this MachineInstr's memory reference descriptor list.

const MachineFunction * getMF() const

Return the function that contains the basic block that this instruction belongs to.

void setDebugLoc(DebugLoc DL)

Replace current source information with new such.

This class contains meta information specific to a module.

MachineFunction & getOrCreateMachineFunction(Function &F)

Returns the MachineFunction constructed for the IR function F.

MachineFunction * getMachineFunction(const Function &F) const

Returns the MachineFunction associated to IR function F if there is one, otherwise nullptr.

MachineOperand class - Representation of each machine instruction operand.

static MachineOperand CreateReg(Register Reg, bool isDef, bool isImp=false, bool isKill=false, bool isDead=false, bool isUndef=false, bool isEarlyClobber=false, unsigned SubReg=0, bool isDebug=false, bool isInternalRead=false, bool isRenamable=false)

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

void freezeReservedRegs()

freezeReservedRegs - Called by the register allocator to freeze the set of reserved registers before ...

void getNameWithPrefix(raw_ostream &OS, const GlobalValue *GV, bool CannotUsePrivateLabel) const

Print the appropriate prefix and the specified global variable's name.

static std::unique_ptr< MemoryBuffer > getMemBuffer(StringRef InputData, StringRef BufferName="", bool RequiresNullTerminator=true)

Open the specified memory range as a MemoryBuffer.

ModulePass class - This class is used to implement unstructured interprocedural optimizations and ana...

virtual bool runOnModule(Module &M)=0

runOnModule - Virtual method overriden by subclasses to process the module being operated on.

A Module instance is used to store all the information related to an LLVM module.

const HashNode * getRoot() const

static PassRegistry * getPassRegistry()

getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...

virtual void getAnalysisUsage(AnalysisUsage &) const

getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...

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.

reference emplace_back(ArgTypes &&... Args)

void push_back(const T &Elt)

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

StringMap - This is an unconventional map that is specialized for handling keys that are "strings",...

iterator find(StringRef Key)

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

std::string str() const

str - Get the contents as an std::string.

constexpr bool empty() const

empty - Check if the string is empty.

constexpr size_t size() const

size - Get the string size.

TargetInstrInfo - Interface to description of machine instruction set.

TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...

TargetSubtargetInfo - Generic base class for all target subtargets.

virtual const TargetInstrInfo * getInstrInfo() const

Triple - Helper class for working with autoconf configuration names.

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

static Type * getVoidTy(LLVMContext &C)

A raw_ostream that writes to an std::string.

A raw_ostream that writes to an SmallVector or SmallString.

@ C

The default llvm calling convention, compatible with C.

unsigned ID

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

SmallVector< const MachineInstr * > InstrList

bool hasOutlinedHashTree()

const OutlinedHashTree * getOutlinedHashTree()

initializer< Ty > init(const Ty &Val)

DiagnosticInfoOptimizationBase::Argument NV

This is an optimization pass for GlobalISel generic memory operations.

void stable_sort(R &&Range)

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

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

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

Convenience function for iterating over sub-ranges.

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

Wrapper function to append range R to container C.

auto reverse(ContainerTy &&C)

void sort(IteratorTy Start, IteratorTy End)

stable_hash stableHashValue(const MachineOperand &MO)

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.

void initializeMachineOutlinerPass(PassRegistry &)

ModulePass * createMachineOutlinerPass(bool RunOnAllFunctions=true)

This pass performs outlining on machine instructions directly before printing assembly.

void erase_if(Container &C, UnaryPredicate P)

Provide a container algorithm similar to C++ Library Fundamentals v2's erase_if which is equivalent t...

stable_hash stable_hash_combine(ArrayRef< stable_hash > Buffer)

void embedBufferInModule(Module &M, MemoryBufferRef Buf, StringRef SectionName, Align Alignment=Align(1))

Embed the memory buffer Buf into the module M as a global using the specified section name.

void addLiveIns(MachineBasicBlock &MBB, const LivePhysRegs &LiveRegs)

Adds registers contained in LiveRegs to the block live-in list of MBB.

std::string getCodeGenDataSectionName(CGDataSectKind CGSK, Triple::ObjectFormatType OF, bool AddSegmentInfo=true)

Implement std::hash so that hash_code can be used in STL containers.

MatchedEntry(unsigned StartIdx, unsigned EndIdx, unsigned Count)

An information struct used to provide DenseMap with the various necessary components for a given valu...

Used in the streaming interface as the general argument type.

A HashNode is an entry in an OutlinedHashTree, holding a hash value and a collection of Successors (o...

std::optional< unsigned > Terminals

The number of terminals in the sequence ending at this node.

A repeated substring in the tree.

An individual sequence of instructions to be replaced with a call to an outlined function.

MachineFunction * getMF() const

The information necessary to create an outlined function for some class of candidate.

virtual unsigned getOccurrenceCount() const

Return the number of candidates for this OutlinedFunction.

unsigned getBenefit() const

Return the number of instructions that would be saved by outlining this function.

MachineFunction * MF

The actual outlined function created.

unsigned getNumInstrs() const

Return the number of instructions in this sequence.

std::vector< Candidate > Candidates