IROutliner.cpp Source File (original) (raw)

28#include

29#include

31#define DEBUG_TYPE "iroutliner"

33using namespace llvm;

38namespace llvm {

49}

57 "enable-linkonceodr-ir-outlining", cl::Hidden,

58 cl::desc("Enable the IR outliner on linkonceodr functions"),

65 cl::desc("Debug option to outline greedily, without restriction that "

66 "calculated benefit outweighs cost"));

75 std::vector<OutlinableRegion *> Regions;

100

101

102

104

105

106

108

109

110

112

113

114

116

117

118

119

121

126

127

128

130

131

133

134

135

137

138

139

140

141

142

144

145

146

147

148

149

151};

152

153

154

155

156

158 TargetBB.splice(TargetBB.end(), &SourceBB);

159}

160

161

162

163

164

165

168 for (auto &VtoBB : Map)

169 SortedKeys.push_back(VtoBB.first);

170

171

172

173 if (SortedKeys.size() == 1) {

174 assert(!SortedKeys[0] && "Expected a single void value.");

175 return;

176 }

177

179 assert(LHS && RHS && "Expected non void values.");

182

184 });

185}

186

189 std::optional GVN = Candidate->getGVN(V);

190 assert(GVN && "No GVN for incoming value");

191 std::optional CanonNum = Candidate->getCanonicalNum(*GVN);

192 std::optional FirstGVN =

193 Other.Candidate->fromCanonicalNum(*CanonNum);

194 std::optional<Value *> FoundValueOpt = Other.Candidate->fromGVN(*FirstGVN);

195 return FoundValueOpt.value_or(nullptr);

196}

197

202 assert(FirstNonPHI && "block is empty?");

204 if (!CorrespondingVal)

205 return nullptr;

208 return CorrespondingBlock;

209}

210

211

212

213

214

215

216

217

218

219

220

225 for (unsigned Idx = 0, PNEnd = PN.getNumIncomingValues(); Idx != PNEnd;

226 ++Idx) {

227

228

231 continue;

232

234 assert(BI && "Not a branch instruction?");

235

236

237 for (unsigned Succ = 0, End = BI->getNumSuccessors(); Succ != End;

238 Succ++) {

239

241 continue;

243 }

244 }

245 }

246}

247

248

251

253

255

256

257

258

259

262 EndInst = Candidate->end()->Inst;

263 assert(EndInst && "Expected an end instruction?");

264 }

265

266

267

268

269

271 return;

272

274 assert(StartInst && "Expected a start instruction?");

277

279 Candidate->getBasicBlocks(BBSet);

280

281

282

283

284

285

286

287

292 bool EndBBTermAndBackInstDifferent = EndBB->getTerminator() != BackInst;

294 unsigned NumPredsOutsideRegion = 0;

295 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {

296 if (!BBSet.contains(PN->getIncomingBlock(i))) {

297 PHIPredBlock = PN->getIncomingBlock(i);

298 ++NumPredsOutsideRegion;

299 continue;

300 }

301

302

303

304

305 IBlock = PN->getIncomingBlock(i);

306 if (IBlock == EndBB && EndBBTermAndBackInstDifferent) {

307 PHIPredBlock = PN->getIncomingBlock(i);

308 ++NumPredsOutsideRegion;

309 }

310 }

311

312 if (NumPredsOutsideRegion > 1)

313 return;

314

315 It++;

316 }

317

318

319

321 return;

322

323

324

326 BackInst != &*std::prev(EndBB->getFirstInsertionPt()))

327 return;

328

329

330

331

332

333

334

335

336

337

338

339

340

341

342

343

344 std::string OriginalName = PrevBB->getName().str();

345

346 StartBB = PrevBB->splitBasicBlock(StartInst, OriginalName + "_to_outline");

348

349

350 if (PHIPredBlock)

351 PrevBB->replaceSuccessorsPhiUsesWith(PHIPredBlock, PrevBB);

352

356 FollowBB = EndBB->splitBasicBlock(EndInst, OriginalName + "_after_outline");

359 } else {

363 }

364

365

367 Candidate->getBasicBlocks(BBSet);

368

369

373}

374

377

378

379

380

381

382

383

384

385

386

387

388

389

390

391

392 assert(StartBB != nullptr && "StartBB for Candidate is not defined!");

393

394 assert(PrevBB->getTerminator() && "Terminator removed from PrevBB!");

395

396

397

398

399

400

401

402

403

404

405

406

410 "PrevBB has more than one predecessor. Should be 0 or 1.");

412 PrevBB->replaceSuccessorsPhiUsesWith(PrevBB, BeforePrevBB);

413 }

414 PrevBB->getTerminator()->eraseFromParent();

415

416

417

418

421 Candidate->getBasicBlocks(BBSet);

422

426 }

427

429

432 PlacementBB = EndBB;

434 assert(FollowBB != nullptr && "FollowBB for Candidate is not defined!");

435 assert(PlacementBB->getTerminator() && "Terminator removed from EndBB!");

440 }

441

443 StartBB->eraseFromParent();

444

445

450

452}

453

454

455

456

457

458

459

460

461

462static std::optional

465

467 if (!CST)

468 return std::nullopt;

469

470

472 bool Inserted;

473

474

475

476 std::tie(GVNToConstantIt, Inserted) =

477 GVNToConstant.insert(std::make_pair(GVN, CST));

478

479

480 if (Inserted || (GVNToConstantIt->second == CST))

481 return true;

482

483 return false;

484}

485

488

489

490

491

492

493

494

495

496

497

498

499

500

503 switch (I->getOpcode()) {

504 case Instruction::FDiv:

505 case Instruction::FRem:

506 case Instruction::SDiv:

507 case Instruction::SRem:

508 case Instruction::UDiv:

509 case Instruction::URem:

510 Benefit += 1;

511 break;

512 default:

514 break;

515 }

516 }

517

518 return Benefit;

519}

520

521

522

523

524

525

526

527

528

529

534 if (OutputMapping != OutputMappings.end())

535 return OutputMapping->second;

537}

538

539

540

541

542

543

544

545

546

547

548static bool

552 bool ConstantsTheSame = true;

553

556

557

558

559

560 for (Value *V : ID.OperVals) {

561 std::optional GVNOpt = C.getGVN(V);

562 assert(GVNOpt && "Expected a GVN for operand?");

563 unsigned GVN = *GVNOpt;

564

565

568 ConstantsTheSame = false;

569 continue;

570 }

571

572

573

574

575

576 std::optional ConstantMatches =

578 if (ConstantMatches) {

579 if (*ConstantMatches)

580 continue;

581 else

582 ConstantsTheSame = false;

583 }

584

585

586

587

588 if (GVNToConstant.contains(GVN))

589 ConstantsTheSame = false;

590

592 }

593 }

594

595 return ConstantsTheSame;

596}

597

604

615

616

617

618

619

624 return SP;

625

626 return nullptr;

627}

628

629Function *IROutliner::createFunction(Module &M, OutlinableGroup &Group,

630 unsigned FunctionNameSuffix) {

632

634

635

636

637

638

639

640

641

642 for (OutlinableRegion *R : Group.Regions) {

643 Type *ExtractedFuncType = R->ExtractedFunction->getReturnType();

646 RetTy = ExtractedFuncType;

647 }

648

651

652

653

656 "outlined_ir_func_" + std::to_string(FunctionNameSuffix), M);

657

658

661 Attribute::SwiftError);

662

665

666

667

670

671 DICompileUnit *CU = SP->getUnit();

672 DIBuilder DB(M, true, CU);

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

674 Mangler Mg;

675

676 std::string Dummy;

677 llvm::raw_string_ostream MangledNameStream(Dummy);

679

680 DISubprogram *OutlinedSP = DB.createFunction(

681 Unit , F->getName(), Dummy, Unit ,

682 0 ,

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

684 0,

685 DINode::DIFlags::FlagArtificial ,

686

687 DISubprogram::SPFlagDefinition | DISubprogram::SPFlagOptimized);

688

689

690 F->setSubprogram(OutlinedSP);

691

692 DB.finalize();

693 }

694

696}

697

698

699

700

701

702

706 CurrBB.removeFromParent();

707 CurrBB.insertInto(&New);

709

710

711

712

714 NewEnds.insert(std::make_pair(RI->getReturnValue(), &CurrBB));

715

717

718

719

720

721 Val.dropDbgRecords();

722

723

724

726

728

729

730

731

732 auto updateLoopInfoLoc = [&New](Metadata *MD) -> Metadata * {

736 Loc->getColumn(), SP, nullptr);

737 return MD;

738 };

740 continue;

741 }

742

743

744 if (DISubprogram *SP = New.getSubprogram()) {

746 Val.setDebugLoc(DI);

747 }

748 }

749 }

750}

751

752

753

754

755

756

757

758

759

760

762 std::vector &Inputs) {

764

765

766 for (IRInstructionDataList::iterator IDIt = C.begin(), EndIDIt = C.end();

767 IDIt != EndIDIt; IDIt++) {

768 for (Value *V : (*IDIt).OperVals) {

769

770

771 unsigned GVN = *C.getGVN(V);

773 if (NotSame.contains(GVN) && Seen.insert(GVN).second)

774 Inputs.push_back(GVN);

775 }

776 }

777}

778

779

780

781

782

783

784

785

786

787

788

792 std::vector &EndInputNumbers) {

793

794

795

797 assert(Input && "Have a nullptr as an input");

798 auto It = OutputMappings.find(Input);

799 if (It != OutputMappings.end())

800 Input = It->second;

801 assert(C.getGVN(Input) && "Could not find a numbering for the given input");

802 EndInputNumbers.push_back(*C.getGVN(Input));

803 }

804}

805

806

807

808

809

810

811

812

813

814static void

818

819

821 auto It = OutputMappings.find(Input);

822 if (It != OutputMappings.end())

823 Input = It->second;

825 }

826}

827

828

829

830

831

832

833

834

835

836

837

838

839

840

841

842

843

844

845

851

852

853

854

855

856

857

858

859

860

861 SetVector<Value *> OverallInputs, PremappedInputs, SinkCands, HoistCands,

862 DummyOutputs;

863

864

865

867 CE->findInputsOutputs(OverallInputs, DummyOutputs, SinkCands);

868 assert(Region.StartBB && "Region must have a start BasicBlock!");

872

873

874

875 if (!CE->isEligible()) {

876 Region.IgnoreRegion = true;

877 return;

878 }

879

880

881 CE->findAllocas(CEAC, SinkCands, HoistCands, Dummy);

882 CE->findInputsOutputs(PremappedInputs, Outputs, SinkCands);

883

884

885

886

887

888

889 if (OverallInputs.size() != PremappedInputs.size()) {

890 Region.IgnoreRegion = true;

891 return;

892 }

893

895

896 mapInputsToGVNs(C, OverallInputs, OutputMappings, InputGVNs);

897

899 ArgInputs);

900

901

902

904}

905

906

907

908

909

910

911

912

913

914

915

916static void

918 std::vector &InputGVNs,

920

923

924

925 unsigned TypeIndex = 0;

926

927

928 unsigned OriginalIndex = 0;

929

930

931

932

933

934

935

936

937

938

939 for (unsigned InputVal : InputGVNs) {

940 std::optional CanonicalNumberOpt = C.getCanonicalNum(InputVal);

941 assert(CanonicalNumberOpt && "Canonical number not found?");

942 unsigned CanonicalNumber = *CanonicalNumberOpt;

943

944 std::optional<Value *> InputOpt = C.fromGVN(InputVal);

945 assert(InputOpt && "Global value number not found?");

947

950

953

954

955 if (Input->isSwiftError()) {

958 "Argument already marked with swifterr for this OutlinableGroup!");

960 }

961 }

962

963

964

967 Region.AggArgToConstant.insert(std::make_pair(AggArgIt->second, CST));

968 else {

970 std::make_pair(CanonicalNumber, TypeIndex));

971 Region.AggArgToConstant.insert(std::make_pair(TypeIndex, CST));

972 }

973 TypeIndex++;

974 continue;

975 }

976

977

978

980

982 if (OriginalIndex != AggArgIt->second)

983 Region.ChangedArgOrder = true;

984 Region.ExtractedArgToAgg.insert(

985 std::make_pair(OriginalIndex, AggArgIt->second));

986 Region.AggArgToExtracted.insert(

987 std::make_pair(AggArgIt->second, OriginalIndex));

988 } else {

990 std::make_pair(CanonicalNumber, TypeIndex));

991 Region.ExtractedArgToAgg.insert(std::make_pair(OriginalIndex, TypeIndex));

992 Region.AggArgToExtracted.insert(std::make_pair(TypeIndex, OriginalIndex));

993 }

994 OriginalIndex++;

995 TypeIndex++;

996 }

997

998

999

1000

1001

1005 }

1006

1007 Region.NumExtractedInputs = OriginalIndex;

1008}

1009

1010

1011

1012

1013

1014

1015

1016

1017

1018

1022

1023

1024

1026 [PHILoc, &PN, V, &BlocksInRegion](unsigned Idx) {

1027 return (Idx != PHILoc && V == PN.getIncomingValue(Idx) &&

1028 !BlocksInRegion.contains(PN.getIncomingBlock(Idx)));

1029 }))

1030 return true;

1031

1032

1033 return any_of(V->users(), [&Exits, &BlocksInRegion](User *U) {

1034 Instruction *I = dyn_cast(U);

1035 if (!I)

1036 return false;

1037

1038

1039

1040

1041 BasicBlock *Parent = I->getParent();

1042 if (BlocksInRegion.contains(Parent))

1043 return false;

1044

1045

1046

1047

1048 if (!isa(I))

1049 return true;

1050

1051

1052

1053

1054

1055 if (!Exits.contains(Parent))

1056 return true;

1057

1058 return false;

1059 });

1060}

1061

1062

1063

1064

1065

1066

1067

1068

1069

1070

1071

1072

1073

1074

1075

1082 for (PHINode &PN : CurrentExitFromRegion->phis()) {

1083

1085 for (unsigned I = 0, E = PN.getNumIncomingValues(); I < E; ++I)

1086 if (RegionBlocks.contains(PN.getIncomingBlock(I)))

1088

1089

1090 unsigned NumIncomingVals = IncomingVals.size();

1091 if (NumIncomingVals == 0)

1092 continue;

1093

1094

1095

1096 if (NumIncomingVals == 1) {

1097 Value *V = PN.getIncomingValue(*IncomingVals.begin());

1098 OutputsWithNonPhiUses.insert(V);

1099 OutputsReplacedByPHINode.erase(V);

1100 continue;

1101 }

1102

1103

1104 Outputs.insert(&PN);

1105

1106

1107

1108

1109 for (unsigned Idx : IncomingVals) {

1110 Value *V = PN.getIncomingValue(Idx);

1112 outputHasNonPHI(V, Idx, PN, PotentialExitsFromRegion, RegionBlocks)) {

1113 OutputsWithNonPhiUses.insert(V);

1114 OutputsReplacedByPHINode.erase(V);

1115 continue;

1116 }

1117 if (!OutputsWithNonPhiUses.contains(V))

1118 OutputsReplacedByPHINode.insert(V);

1119 }

1120 }

1121}

1122

1123

1124

1126

1128

1129

1130using PHINodeData = std::pair<ArgLocWithBBCanon, CanonList>;

1131

1132

1133

1134

1135

1136

1137

1143

1144

1145

1146

1147

1148

1149

1150

1151

1152

1153

1154

1155

1156

1157

1161 unsigned AggArgIdx) {

1168 for (unsigned Idx = 0, EIdx = PN->getNumIncomingValues(); Idx < EIdx; Idx++) {

1171

1172

1173 if (!Blocks.contains(IncomingBlock))

1174 continue;

1175

1176

1177

1178

1179

1180

1181 std::optional OGVN = Cand.getGVN(Incoming);

1182 if (!OGVN) {

1183 Region.IgnoreRegion = true;

1184 return std::nullopt;

1185 }

1186

1187

1188 unsigned GVN = *OGVN;

1190 assert(OGVN && "No GVN found for incoming value?");

1192

1193

1194

1195 OGVN = Cand.getGVN(IncomingBlock);

1196

1197

1198

1199

1200 if (!OGVN) {

1202 "Unknown basic block used in exit path PHINode.");

1203

1205

1206

1207

1208

1210 if (!Blocks.contains(Pred)) {

1211 PrevBlock = Pred;

1212 break;

1213 }

1214 assert(PrevBlock && "Expected a predecessor not in the reigon!");

1215 OGVN = Cand.getGVN(PrevBlock);

1216 }

1217 GVN = *OGVN;

1219 assert(OGVN && "No GVN found for incoming block?");

1221 }

1222

1223

1224

1225

1228 std::optional BBGVN = Cand.getGVN(PHIBB);

1229 assert(BBGVN && "Could not find GVN for the incoming block!");

1230

1232 assert(BBGVN && "Could not find canonical number for the incoming block!");

1233

1234

1235

1237 std::make_pair(std::make_pair(*BBGVN, AggArgIdx), PHIGVNs);

1239

1240

1241

1244 bool Inserted = false;

1245 std::tie(PHIToGVNIt, Inserted) = Group.PHINodeGVNToGVNs.insert(

1247 std::tie(GVNToPHIIt, Inserted) = Group.GVNsToPHINodeGVN.insert(

1249 }

1250

1251 return GVNToPHIIt->second;

1252}

1253

1254

1255

1256

1257

1258

1259static void

1264

1267 C.getBasicBlocks(BlocksInRegion, BE);

1268

1269

1273 if (!BlocksInRegion.contains(Succ))

1275

1276

1277

1278

1283 OutputsReplacedByPHINode,

1284 OutputsWithNonPhiUses);

1285

1286

1287 unsigned OriginalIndex = Region.NumExtractedInputs;

1288

1289

1291 bool TypeFound;

1293

1294

1295

1296

1297

1298

1299

1300 for (Value *Output : Outputs) {

1301 TypeFound = false;

1302

1303

1304

1305

1306

1307 unsigned ArgumentSize = Group.ArgumentTypes.size();

1308

1309

1310 if (OutputsReplacedByPHINode.contains(Output))

1311 continue;

1312

1313 unsigned AggArgIdx = 0;

1314 for (unsigned Jdx = TypeIndex; Jdx < ArgumentSize; Jdx++) {

1316 continue;

1317

1318 if (!AggArgsUsed.insert(Jdx).second)

1319 continue;

1320

1321 TypeFound = true;

1322 Region.ExtractedArgToAgg.insert(std::make_pair(OriginalIndex, Jdx));

1323 Region.AggArgToExtracted.insert(std::make_pair(Jdx, OriginalIndex));

1324 AggArgIdx = Jdx;

1325 break;

1326 }

1327

1328

1329

1330

1331 if (!TypeFound) {

1333 M.getDataLayout().getAllocaAddrSpace()));

1334

1335

1336 unsigned ArgTypeIdx = Group.ArgumentTypes.size() - 1;

1337 AggArgsUsed.insert(ArgTypeIdx);

1338 Region.ExtractedArgToAgg.insert(

1339 std::make_pair(OriginalIndex, ArgTypeIdx));

1340 Region.AggArgToExtracted.insert(

1341 std::make_pair(ArgTypeIdx, OriginalIndex));

1342 AggArgIdx = ArgTypeIdx;

1343 }

1344

1345

1347

1348 std::optional GVN;

1350

1351

1352

1353

1354

1355

1356

1357

1358

1360 if (!GVN)

1361 return;

1362 } else {

1363

1364

1365

1366 GVN = C.getGVN(Output);

1367 GVN = C.getCanonicalNum(*GVN);

1368 }

1369

1370

1371

1372

1373 Region.GVNStores.push_back(*GVN);

1374

1375 OriginalIndex++;

1376 TypeIndex++;

1377 }

1378

1379

1380

1382}

1383

1386 std::vector Inputs;

1387 SetVector<Value *> ArgInputs, Outputs;

1388

1390 Outputs);

1391

1392 if (Region.IgnoreRegion)

1393 return;

1394

1395

1396

1398

1399

1400

1402}

1403

1404

1405

1406

1407

1408

1409

1410

1411

1412

1414 std::vector<Value *> NewCallArgs;

1416

1419 assert(Call && "Call to replace is nullptr?");

1421 assert(AggFunc && "Function to replace with is nullptr?");

1422

1423

1424

1425

1426

1427 if ( Region .ChangedArgOrder && AggFunc->arg_size() == Call->arg_size()) {

1428 LLVM_DEBUG(dbgs() << "Replace call to " << *Call << " with call to "

1429 << *AggFunc << " with same number of arguments\n");

1430 Call->setCalledFunction(AggFunc);

1431 return Call;

1432 }

1433

1434

1435

1436

1437

1438 for (unsigned AggArgIdx = 0; AggArgIdx < AggFunc->arg_size(); AggArgIdx++) {

1439

1440 if (AggArgIdx == AggFunc->arg_size() - 1 &&

1442

1443

1444

1445 LLVM_DEBUG(dbgs() << "Set switch block argument to "

1446 << Region.OutputBlockNum << "\n");

1447 NewCallArgs.push_back(ConstantInt::get(Type::getInt32Ty(M.getContext()),

1448 Region.OutputBlockNum));

1449 continue;

1450 }

1451

1452 ArgPair = Region.AggArgToExtracted.find(AggArgIdx);

1453 if (ArgPair != Region.AggArgToExtracted.end()) {

1454 Value *ArgumentValue = Call->getArgOperand(ArgPair->second);

1455

1456

1457

1458 LLVM_DEBUG(dbgs() << "Setting argument " << AggArgIdx << " to value "

1459 << *ArgumentValue << "\n");

1460 NewCallArgs.push_back(ArgumentValue);

1461 continue;

1462 }

1463

1464

1465 if (auto It = Region.AggArgToConstant.find(AggArgIdx);

1466 It != Region.AggArgToConstant.end()) {

1468 LLVM_DEBUG(dbgs() << "Setting argument " << AggArgIdx << " to value "

1469 << *CST << "\n");

1470 NewCallArgs.push_back(CST);

1471 continue;

1472 }

1473

1474

1475

1476

1477 LLVM_DEBUG(dbgs() << "Setting argument " << AggArgIdx << " to nullptr\n");

1480 }

1481

1482 LLVM_DEBUG(dbgs() << "Replace call to " << *Call << " with call to "

1483 << *AggFunc << " with new set of arguments\n");

1484

1486 Call->getIterator());

1487

1488

1489

1490

1491

1493 if (Region.NewFront->Inst == OldCall)

1495 if (Region.NewBack->Inst == OldCall)

1497

1498

1499 Call->setDebugLoc(Region.Call->getDebugLoc());

1500

1501

1503

1504

1507

1508

1509

1512

1513 return Call;

1514}

1515

1516

1517

1518

1519

1520

1521

1522

1523

1524

1526

1527

1528 auto [PhiBlockForRetVal, Inserted] = Group.PHIBlocks.try_emplace(RetVal);

1529 if (!Inserted)

1530 return PhiBlockForRetVal->second;

1531

1532 auto ReturnBlockForRetVal = Group.EndBBs.find(RetVal);

1533 assert(ReturnBlockForRetVal != Group.EndBBs.end() &&

1534 "Could not find output value!");

1535 BasicBlock *ReturnBB = ReturnBlockForRetVal->second;

1536

1537

1538

1541 PhiBlockForRetVal->second = PHIBlock;

1542

1543

1544

1545

1549

1550

1551

1552 for (BranchInst *BI : BranchesToChange)

1553 for (unsigned Succ = 0, End = BI->getNumSuccessors(); Succ < End; Succ++) {

1554 if (BI->getSuccessor(Succ) != ReturnBB)

1555 continue;

1556 BI->setSuccessor(Succ, PHIBlock);

1557 }

1558

1560

1561 return PhiBlockForRetVal->second;

1562}

1563

1564

1565

1566

1567

1568

1569

1570

1571

1575

1576

1577

1578 return Region.Call->getArgOperand(A->getArgNo());

1579}

1580

1581

1582

1583

1584

1585

1586

1587

1591 unsigned ArgNum = A->getArgNo();

1592

1593

1594

1595 if (auto It = Region.AggArgToConstant.find(ArgNum);

1596 It != Region.AggArgToConstant.end())

1597 return It->second;

1598

1599

1600

1601 ArgNum = Region.AggArgToExtracted.find(ArgNum)->second;

1602 return Region.Call->getArgOperand(ArgNum);

1603}

1604

1605

1606

1607

1608

1609

1610

1611

1612

1613

1614

1618 SmallVector<std::pair<unsigned, BasicBlock *>> &CanonNums,

1619 bool ReplacedWithOutlinedCall = true) {

1620

1621 for (unsigned Idx = 0, EIdx = PN->getNumIncomingValues(); Idx < EIdx; Idx++) {

1624

1625

1627 if (ReplacedWithOutlinedCall)

1629 else

1631 }

1632

1633

1635

1636

1637 std::optional GVN = Region.Candidate->getGVN(IVal);

1638 assert(GVN && "No GVN for incoming value");

1639 std::optional CanonNum = Region.Candidate->getCanonicalNum(*GVN);

1640 assert(CanonNum && "No Canonical Number for GVN");

1641 CanonNums.push_back(std::make_pair(*CanonNum, IBlock));

1642 }

1643}

1644

1645

1646

1647

1648

1649

1650

1651

1652

1653

1654

1655

1656

1657

1664

1665

1666

1667

1669

1670

1671

1672

1673

1675 false);

1676

1678

1679

1680

1681

1683

1684

1685

1686 for (PHINode &CurrPN : OverallPhiBlock->phis()) {

1687

1688

1689 if (UsedPHIs.contains(&CurrPN))

1690 continue;

1691

1692 CurrentCanonNums.clear();

1693 findCanonNumsForPHI(&CurrPN, *FirstRegion, OutputMappings, CurrentCanonNums,

1694 true);

1695

1696

1697

1698 if (PNCanonNums.size() != CurrentCanonNums.size())

1699 continue;

1700

1701 bool FoundMatch = true;

1702

1703

1704

1705

1706

1707

1708

1709

1710 for (unsigned Idx = 0, Edx = PNCanonNums.size(); Idx < Edx; ++Idx) {

1711 std::pair<unsigned, BasicBlock *> ToCompareTo = CurrentCanonNums[Idx];

1712 std::pair<unsigned, BasicBlock *> ToAdd = PNCanonNums[Idx];

1713 if (ToCompareTo.first != ToAdd.first) {

1714 FoundMatch = false;

1715 break;

1716 }

1717

1719 Region.findCorrespondingBlockIn(*FirstRegion, ToAdd.second);

1720 assert(CorrespondingBlock && "Found block is nullptr");

1721 if (CorrespondingBlock != ToCompareTo.second) {

1722 FoundMatch = false;

1723 break;

1724 }

1725 }

1726

1727

1728

1729 if (FoundMatch) {

1730 UsedPHIs.insert(&CurrPN);

1731 return &CurrPN;

1732 }

1733 }

1734

1735

1736

1740 Idx++) {

1743

1744

1745

1747 Region.findCorrespondingBlockIn(*FirstRegion, IncomingBlock);

1749

1750

1751

1755 continue;

1756 }

1757

1758

1760 Value *Val = Region.findCorrespondingValueIn(*FirstRegion, IncomingVal);

1761 assert(Val && "Value is nullptr?");

1765 Val = RemappedIt->second;

1767 }

1768 return NewPN;

1769}

1770

1771

1772

1773

1774

1775

1776

1777

1778

1779

1780static void

1784 bool FirstFunction = false) {

1786 assert(Region.ExtractedFunction && "Region has no extracted function?");

1787

1788 Function *DominatingFunction = Region.ExtractedFunction;

1789 if (FirstFunction)

1793

1794 for (unsigned ArgIdx = 0; ArgIdx < Region.ExtractedFunction->arg_size();

1795 ArgIdx++) {

1797 "No mapping from extracted to outlined?");

1798 unsigned AggArgIdx = Region.ExtractedArgToAgg.find(ArgIdx)->second;

1800 Argument *Arg = Region.ExtractedFunction->getArg(ArgIdx);

1801

1802

1803 if (ArgIdx < Region.NumExtractedInputs) {

1804 LLVM_DEBUG(dbgs() << "Replacing uses of input " << *Arg << " in function "

1805 << *Region.ExtractedFunction << " with " << *AggArg

1808 Value *V = Region.Call->getArgOperand(ArgIdx);

1809 Region.RemappedArguments.insert(std::make_pair(V, AggArg));

1810 continue;

1811 }

1812

1813

1814

1815

1816 assert(Arg->hasOneUse() && "Output argument can only have one use");

1818 assert(InstAsUser && "User is nullptr!");

1819

1824 bool EdgeAdded = false;

1825 if (Descendants.size() == 0) {

1826 EdgeAdded = true;

1829 }

1830

1831

1832

1833

1834 for (BasicBlock *DescendBB : Descendants) {

1836 if (!RI)

1837 continue;

1839 auto VBBIt = OutputBBs.find(RetVal);

1840 assert(VBBIt != OutputBBs.end() && "Could not find output value!");

1841

1842

1843

1845

1846 Value *ValueOperand = SI->getValueOperand();

1847

1850 BasicBlock *OutputBB = VBBIt->second;

1852 LLVM_DEBUG(dbgs() << "Move store for instruction " << *I << " to "

1853 << *OutputBB << "\n");

1854

1855

1856

1858 Region.Candidate->getGVN(ValueOperand).has_value()) {

1859 if (FirstFunction)

1860 continue;

1861 Value *CorrVal =

1862 Region.findCorrespondingValueIn(*Group.Regions[0], ValueOperand);

1863 assert(CorrVal && "Value is nullptr?");

1865 continue;

1866 }

1868

1869

1870 if (Region.Candidate->getGVN(PN))

1871 continue;

1872

1873

1874

1875 Region.PHIBlocks.insert(std::make_pair(RetVal, PN->getParent()));

1876

1877

1878

1879

1880 if (FirstFunction) {

1882 Group.PHIBlocks.insert(std::make_pair(RetVal, PHIBlock));

1883 continue;

1884 }

1885

1886

1887

1889

1890

1891

1892

1894 OutputMappings, UsedPHIs);

1896 }

1897

1898

1899

1900 if (EdgeAdded)

1902 I->eraseFromParent();

1903

1904 LLVM_DEBUG(dbgs() << "Replacing uses of output " << *Arg << " in function "

1905 << *Region.ExtractedFunction << " with " << *AggArg

1908 }

1909}

1910

1911

1912

1913

1914

1919

1920

1921 for (std::pair<unsigned, Constant *> &Const : Region.AggArgToConstant) {

1922 unsigned AggArgIdx = Const.first;

1923 assert(OutlinedFunction && "Overall Function is not defined?");

1924 Constant *CST = Const.second;

1926

1927

1928 VMap[CST] = Arg;

1929 LLVM_DEBUG(dbgs() << "Replacing uses of constant " << *CST

1930 << " in function " << *OutlinedFunction << " with "

1931 << *Arg << '\n');

1932 }

1933

1936}

1937

1938

1939

1940

1941

1942

1943

1947

1948 bool Mismatch = false;

1949 unsigned MatchingNum = 0;

1950

1951

1952

1954 Mismatch = false;

1955 for (std::pair<Value *, BasicBlock *> &VToB : CompBBs) {

1957 OutputBBs.find(VToB.first);

1958 if (OutputBBIt == OutputBBs.end()) {

1959 Mismatch = true;

1960 break;

1961 }

1962

1964 BasicBlock *OutputBB = OutputBBIt->second;

1965 if (CompBB->size() - 1 != OutputBB->size()) {

1966 Mismatch = true;

1967 break;

1968 }

1969

1973 continue;

1974

1975 if (.isIdenticalTo(&(*NIt))) {

1976 Mismatch = true;

1977 break;

1978 }

1979

1980 NIt++;

1981 }

1982 }

1983

1984 if (!Mismatch)

1985 return MatchingNum;

1986

1987 MatchingNum++;

1988 }

1989

1990 return std::nullopt;

1991}

1992

1993

1994

1995

1996

1997

1998static bool

2001 bool AllRemoved = true;

2002 Value *RetValueForBB;

2005

2006 for (std::pair<Value *, BasicBlock *> &VtoBB : BlocksToPrune) {

2007 RetValueForBB = VtoBB.first;

2008 NewBB = VtoBB.second;

2009

2010

2011

2012 if (NewBB->size() == 0) {

2014 ToRemove.push_back(RetValueForBB);

2015 continue;

2016 }

2017

2018

2019

2020 AllRemoved = false;

2021 }

2022

2023

2025 BlocksToPrune.erase(V);

2026

2027

2028 if (AllRemoved)

2029 Region.OutputBlockNum = -1;

2030

2031 return AllRemoved;

2032}

2033

2034

2035

2036

2037

2038

2039

2040

2041

2042

2043

2044

2045

2052

2053

2054

2056 return;

2057

2058

2059 std::optional MatchingBB =

2061

2062

2063

2064 if (MatchingBB) {

2065 LLVM_DEBUG(dbgs() << "Set output block for region in function"

2066 << Region.ExtractedFunction << " to " << *MatchingBB);

2067

2068 Region.OutputBlockNum = *MatchingBB;

2069 for (std::pair<Value *, BasicBlock *> &VtoBB : OutputBBs)

2070 VtoBB.second->eraseFromParent();

2071 return;

2072 }

2073

2074 Region.OutputBlockNum = OutputStoreBBs.size();

2075

2076 Value *RetValueForBB;

2079 for (std::pair<Value *, BasicBlock *> &VtoBB : OutputBBs) {

2080 RetValueForBB = VtoBB.first;

2081 NewBB = VtoBB.second;

2083 EndBBs.find(RetValueForBB);

2084 LLVM_DEBUG(dbgs() << "Create output block for region in"

2085 << Region.ExtractedFunction << " to "

2086 << *NewBB);

2088 OutputStoreBBs.back().insert(std::make_pair(RetValueForBB, NewBB));

2089 }

2090}

2091

2092

2093

2094

2095

2096

2097

2098

2099

2100

2104 unsigned Idx = 0;

2105 std::vector<Value *> SortedKeys;

2106

2108

2109 for (Value *RetVal : SortedKeys) {

2112 ParentFunc);

2113 NewMap.insert(std::make_pair(RetVal, NewBB));

2114 }

2115}

2116

2117

2118

2119

2120

2121

2122

2123

2124

2125

2129

2130

2131

2132

2133

2134

2135

2138

2141

2142 for (std::pair<Value *, BasicBlock *> &RetBlockPair : ReturnBBs) {

2143 std::pair<Value *, BasicBlock *> &OutputBlock =

2144 *OG.EndBBs.find(RetBlockPair.first);

2145 BasicBlock *ReturnBlock = RetBlockPair.second;

2146 BasicBlock *EndBB = OutputBlock.second;

2148

2149

2150 Term->moveBefore(*ReturnBlock, ReturnBlock->end());

2151

2152

2153 LLVM_DEBUG(dbgs() << "Create switch statement in " << *AggFunc << " for "

2154 << OutputStoreBBs.size() << "\n");

2157 ReturnBlock, OutputStoreBBs.size(), EndBB);

2158

2159 unsigned Idx = 0;

2162 OutputStoreBB.find(OutputBlock.first);

2163

2164 if (OSBBIt == OutputStoreBB.end())

2165 continue;

2166

2169 ConstantInt::get(Type::getInt32Ty(M.getContext()), Idx), BB);

2171 Term->setSuccessor(0, ReturnBlock);

2172 Idx++;

2173 }

2174 }

2175 return;

2176 }

2177

2178 assert(OutputStoreBBs.size() < 2 && "Different store sets not handled!");

2179

2180

2181

2182

2183

2184

2185

2186 if (OutputStoreBBs.size() == 1) {

2187 LLVM_DEBUG(dbgs() << "Move store instructions to the end block in "

2190 for (std::pair<Value *, BasicBlock *> &VBPair : OutputBlocks) {

2192 EndBBs.find(VBPair.first);

2193 assert(EndBBIt != EndBBs.end() && "Could not find end block");

2194 BasicBlock *EndBB = EndBBIt->second;

2195 BasicBlock *OutputBB = VBPair.second;

2197 Term->eraseFromParent();

2200 Term->moveBefore(*EndBB, EndBB->end());

2202 }

2203 }

2204}

2205

2206

2207

2208

2209

2210

2211

2212

2213

2214

2215

2216

2217

2218

2222 std::vector<Function *> &FuncsToRemove,

2225

2226

2232

2233

2236

2237

2242

2245

2246

2247

2248

2251 for (std::pair<Value *, BasicBlock *> &VToBB : NewBBs) {

2253 CurrentGroup.EndBBs.find(VToBB.first);

2256 OutputStoreBBs.back().insert(VToBB);

2257 }

2258 }

2259

2260

2262

2263

2264

2266}

2267

2268void IROutliner::deduplicateExtractedSections(

2269 Module &M, OutlinableGroup &CurrentGroup,

2270 std::vector<Function *> &FuncsToRemove, unsigned &OutlinedFunctionNum) {

2271 createFunction(M, CurrentGroup, OutlinedFunctionNum);

2272

2273 std::vector<DenseMap<Value *, BasicBlock *>> OutputStoreBBs;

2274

2275 OutlinableRegion *CurrentOS;

2276

2278 OutputMappings);

2279

2280 for (unsigned Idx = 1; Idx < CurrentGroup.Regions.size(); Idx++) {

2281 CurrentOS = CurrentGroup.Regions[Idx];

2282 AttributeFuncs::mergeAttributesForOutlining(*CurrentGroup.OutlinedFunction,

2284

2285

2286

2287 DenseMap<Value *, BasicBlock *> NewBBs;

2290 "output_block_" + Twine(Idx));

2293 CurrentGroup.EndBBs, OutputMappings,

2294 OutputStoreBBs);

2295

2298 }

2299

2300

2302

2303 OutlinedFunctionNum++;

2304}

2305

2306

2307

2308

2309

2310

2311

2313

2314

2315

2316

2317

2318

2319

2320 IRInstructionDataList::iterator NextIDIt = std::next(ID.getIterator());

2321 Instruction *NextIDLInst = NextIDIt->Inst;

2323 if (.Inst->isTerminator())

2324 NextModuleInst = ID.Inst->getNextNode();

2325 else if (NextIDLInst != nullptr)

2326 NextModuleInst =

2327 &*NextIDIt->Inst->getParent()->instructionsWithoutDebug().begin();

2328

2329 if (NextIDLInst && NextIDLInst != NextModuleInst)

2330 return false;

2331

2332 return true;

2333}

2334

2335bool IROutliner::isCompatibleWithAlreadyOutlinedCode(

2337 IRSimilarityCandidate *IRSC = Region.Candidate;

2338 unsigned StartIdx = IRSC->getStartIdx();

2339 unsigned EndIdx = IRSC->getEndIdx();

2340

2341

2342

2343 for (unsigned Idx = StartIdx; Idx <= EndIdx; Idx++)

2344 if (Outlined.contains(Idx))

2345 return false;

2346

2347

2348

2349 if ( Region .Candidate->backInstruction()->isTerminator()) {

2351 Region.Candidate->backInstruction()->getNextNode();

2352 assert(NewEndInst && "Next instruction is a nullptr?");

2353 if (Region.Candidate->end()->Inst != NewEndInst) {

2354 IRInstructionDataList *IDL = Region.Candidate->front()->IDL;

2355 IRInstructionData *NewEndIRID = new (InstDataAllocator.Allocate())

2356 IRInstructionData(*NewEndInst,

2357 InstructionClassifier.visit(*NewEndInst), *IDL);

2358

2359

2360

2361 IDL->insert(Region.Candidate->end(), *NewEndIRID);

2362 }

2363 }

2364

2365 return none_of(*IRSC, [this](IRInstructionData &ID) {

2367 return true;

2368

2369 return !this->InstructionClassifier.visit(ID.Inst);

2370 });

2371}

2372

2373void IROutliner::pruneIncompatibleRegions(

2374 std::vector &CandidateVec,

2375 OutlinableGroup &CurrentGroup) {

2376 bool PreviouslyOutlined;

2377

2378

2379 stable_sort(CandidateVec, [](const IRSimilarityCandidate &LHS,

2380 const IRSimilarityCandidate &RHS) {

2381 return LHS.getStartIdx() < RHS.getStartIdx();

2382 });

2383

2384 IRSimilarityCandidate &FirstCandidate = CandidateVec[0];

2385

2386

2387 if (FirstCandidate.getLength() == 2) {

2388 if (isa(FirstCandidate.front()->Inst) &&

2390 return;

2391 }

2392

2393 unsigned CurrentEndIdx = 0;

2394 for (IRSimilarityCandidate &IRSC : CandidateVec) {

2395 PreviouslyOutlined = false;

2397 unsigned EndIdx = IRSC.getEndIdx();

2399

2400 for (unsigned Idx = StartIdx; Idx <= EndIdx; Idx++)

2401 if (Outlined.contains(Idx)) {

2402 PreviouslyOutlined = true;

2403 break;

2404 }

2405

2406 if (PreviouslyOutlined)

2407 continue;

2408

2409

2410

2411 bool BBHasAddressTaken = any_of(IRSC, [](IRInstructionData &ID){

2412 return ID.Inst->getParent()->hasAddressTaken();

2413 });

2414

2415 if (BBHasAddressTaken)

2416 continue;

2417

2419 continue;

2420

2423 dbgs() << "... Skipping function with nooutline attribute: "

2424 << FnForCurrCand.getName() << "\n";

2425 });

2426 continue;

2427 }

2428

2430 !OutlineFromLinkODRs)

2431 continue;

2432

2433

2434

2435 if (CurrentEndIdx != 0 && StartIdx <= CurrentEndIdx)

2436 continue;

2437

2438 bool BadInst = any_of(IRSC, [this](IRInstructionData &ID) {

2440 return true;

2441

2442 return !this->InstructionClassifier.visit(ID.Inst);

2443 });

2444

2445 if (BadInst)

2446 continue;

2447

2448 OutlinableRegion *OS = new (RegionAllocator.Allocate())

2449 OutlinableRegion(IRSC, CurrentGroup);

2450 CurrentGroup.Regions.push_back(OS);

2451

2452 CurrentEndIdx = EndIdx;

2453 }

2454}

2455

2457IROutliner::findBenefitFromAllRegions(OutlinableGroup &CurrentGroup) {

2459 for (OutlinableRegion *Region : CurrentGroup.Regions) {

2460 TargetTransformInfo &TTI = getTTI(*Region->StartBB->getParent());

2461

2462

2463 RegionBenefit += Region->getBenefit(TTI);

2465 << " saved instructions to overfall benefit.\n");

2466 }

2467

2468 return RegionBenefit;

2469}

2470

2471

2472

2473

2474

2475

2476

2477

2478

2480 unsigned OutputCanon) {

2482

2483

2484

2488 "Could not find GVN set for PHINode number!");

2489 assert(It->second.second.size() > 0 && "PHINode does not have any values!");

2490 OutputCanon = *It->second.second.begin();

2491 }

2492 std::optional OGVN =

2493 Region.Candidate->fromCanonicalNum(OutputCanon);

2494 assert(OGVN && "Could not find GVN for Canonical Number?");

2495 std::optional<Value *> OV = Region.Candidate->fromGVN(*OGVN);

2496 assert(OV && "Could not find value for GVN?");

2497 return *OV;

2498}

2499

2501IROutliner::findCostOutputReloads(OutlinableGroup &CurrentGroup) {

2503 for (OutlinableRegion *Region : CurrentGroup.Regions) {

2504 TargetTransformInfo &TTI = getTTI(*Region->StartBB->getParent());

2505

2506

2507 for (unsigned OutputCanon : Region->GVNStores) {

2512

2514 << " instructions to cost for output of type "

2515 << *V->getType() << "\n");

2516 OverallCost += LoadCost;

2517 }

2518 }

2519

2520 return OverallCost;

2521}

2522

2523

2524

2525

2526

2527

2528

2529

2530

2535 unsigned NumOutputBranches = 0;

2536

2541

2542

2543

2547 continue;

2548

2549 for (Value *V : ID.OperVals) {

2551 if (!CandidateBlocks.contains(BB) && FoundBlocks.insert(BB).second)

2552 NumOutputBranches++;

2553 }

2554 }

2555

2557

2560 for (unsigned OutputCanon : OutputUse) {

2563 TTI.getMemoryOpCost(Instruction::Load, V->getType(), Align(1), 0,

2565

2566

2567

2568

2570 << " instructions to cost for output of type "

2571 << *V->getType() << "\n");

2572 OutputCost += StoreCost * NumOutputBranches;

2573 }

2574

2577 LLVM_DEBUG(dbgs() << "Adding " << BranchCost << " to the current cost for"

2578 << " a branch instruction\n");

2579 OutputCost += BranchCost * NumOutputBranches;

2580 }

2581

2582

2583

2591

2593 InstructionCost TotalCost = ComparisonCost * BranchCost * DifferentBlocks;

2594

2596 << " instructions for each switch case for each different"

2597 << " output path in a function\n");

2598 OutputCost += TotalCost * NumOutputBranches;

2599 }

2600

2601 return OutputCost;

2602}

2603

2604void IROutliner::findCostBenefit(Module &M, OutlinableGroup &CurrentGroup) {

2605 InstructionCost RegionBenefit = findBenefitFromAllRegions(CurrentGroup);

2606 CurrentGroup.Benefit += RegionBenefit;

2608

2609 InstructionCost OutputReloadCost = findCostOutputReloads(CurrentGroup);

2610 CurrentGroup.Cost += OutputReloadCost;

2611 LLVM_DEBUG(dbgs() << "Current Cost: " << CurrentGroup.Cost << "\n");

2612

2614 RegionBenefit / CurrentGroup.Regions.size();

2615 unsigned OverallArgumentNum = CurrentGroup.ArgumentTypes.size();

2616 unsigned NumRegions = CurrentGroup.Regions.size();

2617 TargetTransformInfo &TTI =

2618 getTTI(*CurrentGroup.Regions[0]->Candidate->getFunction());

2619

2620

2621

2622 LLVM_DEBUG(dbgs() << "Adding: " << AverageRegionBenefit

2623 << " instructions to cost for body of new function.\n");

2624 CurrentGroup.Cost += AverageRegionBenefit;

2625 LLVM_DEBUG(dbgs() << "Current Cost: " << CurrentGroup.Cost << "\n");

2626

2627

2628

2629 LLVM_DEBUG(dbgs() << "Adding: " << OverallArgumentNum

2630 << " instructions to cost for each argument in the new"

2631 << " function.\n");

2632 CurrentGroup.Cost +=

2634 LLVM_DEBUG(dbgs() << "Current Cost: " << CurrentGroup.Cost << "\n");

2635

2636

2637

2638

2639 LLVM_DEBUG(dbgs() << "Adding: " << OverallArgumentNum

2640 << " instructions to cost for each argument in the new"

2641 << " function " << NumRegions << " times for the "

2642 << "needed argument handling at the call site.\n");

2643 CurrentGroup.Cost +=

2645 LLVM_DEBUG(dbgs() << "Current Cost: " << CurrentGroup.Cost << "\n");

2646

2648 LLVM_DEBUG(dbgs() << "Current Cost: " << CurrentGroup.Cost << "\n");

2649}

2650

2654

2656 std::optional OutputIdx;

2657

2658 for (unsigned ArgIdx = Region.NumExtractedInputs;

2659 ArgIdx < Region.Call->arg_size(); ArgIdx++) {

2660 if (Operand == Region.Call->getArgOperand(ArgIdx)) {

2661 OutputIdx = ArgIdx - Region.NumExtractedInputs;

2662 break;

2663 }

2664 }

2665

2666

2667

2668 if (!OutputIdx)

2669 return;

2670

2671 auto It = OutputMappings.find(Outputs[*OutputIdx]);

2672 if (It == OutputMappings.end()) {

2673 LLVM_DEBUG(dbgs() << "Mapping extracted output " << *LI << " to "

2674 << *Outputs[*OutputIdx] << "\n");

2675 OutputMappings.insert(std::make_pair(LI, Outputs[*OutputIdx]));

2676 } else {

2677 Value *Orig = It->second;

2678 LLVM_DEBUG(dbgs() << "Mapping extracted output " << *Orig << " to "

2679 << *Outputs[*OutputIdx] << "\n");

2680 OutputMappings.insert(std::make_pair(LI, Orig));

2681 }

2682}

2683

2685 SetVector<Value *> ArgInputs, Outputs;

2686 assert(Region.StartBB && "StartBB for the OutlinableRegion is nullptr!");

2689 CodeExtractorAnalysisCache CEAC(*OrigF);

2690 Region.ExtractedFunction =

2691 Region.CE->extractCodeRegion(CEAC, ArgInputs, Outputs);

2692

2693

2694

2695 if ( Region .ExtractedFunction) {

2697 << "\n");

2698 Region.reattachCandidate();

2699 return false;

2700 }

2701

2702

2703

2704

2705

2706 User *InstAsUser = Region.ExtractedFunction->user_back();

2709 assert(Region.PrevBB && "PrevBB is nullptr?");

2710 if (Region.PrevBB == InitialStart) {

2715 Region.PrevBB = NewPrev;

2717 }

2718

2719 Region.StartBB = RewrittenBB;

2720 Region.EndBB = RewrittenBB;

2721

2722

2723

2724

2725

2726

2727 IRInstructionDataList *IDL = Region.Candidate->front()->IDL;

2730 Region.NewFront = new (InstDataAllocator.Allocate()) IRInstructionData(

2731 *BeginRewritten, InstructionClassifier.visit(*BeginRewritten), *IDL);

2732 Region.NewBack = new (InstDataAllocator.Allocate()) IRInstructionData(

2733 *EndRewritten, InstructionClassifier.visit(*EndRewritten), *IDL);

2734

2735

2736

2738

2739

2741

2742 IDL->erase(Region.Candidate->begin(), std::prev(Region.Candidate->end()));

2743

2744 assert(RewrittenBB != nullptr &&

2745 "Could not find a predecessor after extraction!");

2746

2747

2748

2749 for (Instruction &I : *RewrittenBB)

2751 if (Region.ExtractedFunction == CI->getCalledFunction())

2754 updateOutputMapping(Region, Outputs.getArrayRef(), LI);

2755 Region.reattachCandidate();

2756 return true;

2757}

2758

2759unsigned IROutliner::doOutline(Module &M) {

2760

2761 InstructionClassifier.EnableBranches = DisableBranches ;

2764

2765 IRSimilarityIdentifier &Identifier = getIRSI(M);

2767

2768

2769 unsigned OutlinedFunctionNum = 0;

2770

2771

2772 if (SimilarityCandidates.size() > 1)

2774 [](const std::vector &LHS,

2775 const std::vector &RHS) {

2776 return LHS[0].getLength() * LHS.size() >

2777 RHS[0].getLength() * RHS.size();

2778 });

2779

2780

2781 std::vector PotentialGroups(SimilarityCandidates.size());

2782

2783 DenseSet NotSame;

2784 std::vector<OutlinableGroup *> NegativeCostGroups;

2785 std::vector<OutlinableRegion *> OutlinedRegions;

2786

2787 unsigned PotentialGroupIdx = 0;

2788 for (SimilarityGroup &CandidateVec : SimilarityCandidates) {

2789 OutlinableGroup &CurrentGroup = PotentialGroups[PotentialGroupIdx++];

2790

2791

2792 pruneIncompatibleRegions(CandidateVec, CurrentGroup);

2793

2794

2795

2796

2797 if (CurrentGroup.Regions.size() < 2)

2798 continue;

2799

2800

2801

2802 NotSame.clear();

2804

2806 continue;

2807

2808

2809

2810

2811 OutlinedRegions.clear();

2812 for (OutlinableRegion *OS : CurrentGroup.Regions) {

2813

2814

2816

2817

2818

2819

2821 continue;

2822

2824 DenseSet<BasicBlock *> BlocksInRegion;

2826 OS->CE = new (ExtractorAllocator.Allocate())

2827 CodeExtractor(BE, nullptr, false, nullptr, nullptr, nullptr, false,

2828 false, nullptr, "outlined");

2829 findAddInputsOutputs(M, *OS, NotSame);

2831 OutlinedRegions.push_back(OS);

2832

2833

2834

2836 }

2837

2838 CurrentGroup.Regions = std::move(OutlinedRegions);

2839

2840 if (CurrentGroup.Regions.empty())

2841 continue;

2842

2844

2845 if (CostModel)

2846 findCostBenefit(M, CurrentGroup);

2847

2848

2849

2850 if (CurrentGroup.Cost >= CurrentGroup.Benefit && CostModel) {

2851 OptimizationRemarkEmitter &ORE =

2852 getORE(*CurrentGroup.Regions[0]->Candidate->getFunction());

2853 ORE.emit([&]() {

2854 IRSimilarityCandidate *C = CurrentGroup.Regions[0]->Candidate;

2855 OptimizationRemarkMissed R(DEBUG_TYPE, "WouldNotDecreaseSize",

2856 C->frontInstruction());

2857 R << "did not outline "

2858 << ore::NV(std::to_string(CurrentGroup.Regions.size()))

2859 << " regions due to estimated increase of "

2860 << ore::NV("InstructionIncrease",

2861 CurrentGroup.Cost - CurrentGroup.Benefit)

2862 << " instructions at locations ";

2864 CurrentGroup.Regions.begin(), CurrentGroup.Regions.end(),

2865 [&R](OutlinableRegion *Region) {

2866 R << ore::NV(

2867 "DebugLoc",

2868 Region->Candidate->frontInstruction()->getDebugLoc());

2869 },

2870 [&R]() { R << " "; });

2871 return R;

2872 });

2873 continue;

2874 }

2875

2876 NegativeCostGroups.push_back(&CurrentGroup);

2877 }

2878

2879 ExtractorAllocator.DestroyAll();

2880

2881 if (NegativeCostGroups.size() > 1)

2883 [](const OutlinableGroup *LHS, const OutlinableGroup *RHS) {

2884 return LHS->Benefit - LHS->Cost > RHS->Benefit - RHS->Cost;

2885 });

2886

2887 std::vector<Function *> FuncsToRemove;

2888 for (OutlinableGroup *CG : NegativeCostGroups) {

2889 OutlinableGroup &CurrentGroup = *CG;

2890

2891 OutlinedRegions.clear();

2892 for (OutlinableRegion *Region : CurrentGroup.Regions) {

2893

2894

2895 if (!isCompatibleWithAlreadyOutlinedCode(*Region))

2896 continue;

2897 OutlinedRegions.push_back(Region);

2898 }

2899

2900 if (OutlinedRegions.size() < 2)

2901 continue;

2902

2903

2904

2905 CurrentGroup.Regions = std::move(OutlinedRegions);

2906 if (CostModel) {

2907 CurrentGroup.Benefit = 0;

2908 CurrentGroup.Cost = 0;

2909 findCostBenefit(M, CurrentGroup);

2910 if (CurrentGroup.Cost >= CurrentGroup.Benefit)

2911 continue;

2912 }

2913 OutlinedRegions.clear();

2914 for (OutlinableRegion *Region : CurrentGroup.Regions) {

2915 Region->splitCandidate();

2916 if ( Region ->CandidateSplit)

2917 continue;

2918 OutlinedRegions.push_back(Region);

2919 }

2920

2921 CurrentGroup.Regions = std::move(OutlinedRegions);

2922 if (CurrentGroup.Regions.size() < 2) {

2923 for (OutlinableRegion *R : CurrentGroup.Regions)

2924 R->reattachCandidate();

2925 continue;

2926 }

2927

2928 LLVM_DEBUG(dbgs() << "Outlining regions with cost " << CurrentGroup.Cost

2929 << " and benefit " << CurrentGroup.Benefit << "\n");

2930

2931

2932 OutlinedRegions.clear();

2933 for (OutlinableRegion *OS : CurrentGroup.Regions) {

2935 DenseSet<BasicBlock *> BlocksInRegion;

2937 OS->CE = new (ExtractorAllocator.Allocate())

2938 CodeExtractor(BE, nullptr, false, nullptr, nullptr, nullptr, false,

2939 false, nullptr, "outlined");

2940 bool FunctionOutlined = extractSection(*OS);

2941 if (FunctionOutlined) {

2944 for (unsigned Idx = StartIdx; Idx <= EndIdx; Idx++)

2945 Outlined.insert(Idx);

2946

2947 OutlinedRegions.push_back(OS);

2948 }

2949 }

2950

2951 LLVM_DEBUG(dbgs() << "Outlined " << OutlinedRegions.size()

2952 << " with benefit " << CurrentGroup.Benefit

2953 << " and cost " << CurrentGroup.Cost << "\n");

2954

2955 CurrentGroup.Regions = std::move(OutlinedRegions);

2956

2957 if (CurrentGroup.Regions.empty())

2958 continue;

2959

2960 OptimizationRemarkEmitter &ORE =

2961 getORE(*CurrentGroup.Regions[0]->Call->getFunction());

2962 ORE.emit([&]() {

2963 IRSimilarityCandidate *C = CurrentGroup.Regions[0]->Candidate;

2964 OptimizationRemark R(DEBUG_TYPE, "Outlined", C->front()->Inst);

2965 R << "outlined " << ore::NV(std::to_string(CurrentGroup.Regions.size()))

2966 << " regions with decrease of "

2968 << " instructions at locations ";

2970 CurrentGroup.Regions.begin(), CurrentGroup.Regions.end(),

2971 [&R](OutlinableRegion *Region) {

2972 R << ore::NV("DebugLoc",

2973 Region->Candidate->frontInstruction()->getDebugLoc());

2974 },

2975 [&R]() { R << " "; });

2976 return R;

2977 });

2978

2979 deduplicateExtractedSections(M, CurrentGroup, FuncsToRemove,

2980 OutlinedFunctionNum);

2981 }

2982

2983 for (Function *F : FuncsToRemove)

2984 F->eraseFromParent();

2985

2986 return OutlinedFunctionNum;

2987}

2988

2992

2993 return doOutline(M) > 0;

2994}

2995

2998

3002 };

3003

3007 };

3008

3009 std::unique_ptr ORE;

3013 return *ORE;

3014 };

3015

3019}

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

ReachingDefInfo InstSet & ToRemove

This file contains the simple types necessary to represent the attributes associated with functions a...

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

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

std::pair< ArgLocWithBBCanon, CanonList > PHINodeData

Definition IROutliner.cpp:1130

static void remapExtractedInputs(const ArrayRef< Value * > ArgInputs, const DenseMap< Value *, Value * > &OutputMappings, SetVector< Value * > &RemappedArgInputs)

Find the original value for the ArgInput values if any one of them was replaced during a previous ext...

Definition IROutliner.cpp:815

static std::optional< unsigned > getGVNForPHINode(OutlinableRegion &Region, PHINode *PN, DenseSet< BasicBlock * > &Blocks, unsigned AggArgIdx)

Create a special GVN for PHINodes that will be used outside of the region.

Definition IROutliner.cpp:1158

static Value * getPassedArgumentAndAdjustArgumentLocation(const Argument *A, const OutlinableRegion &Region)

For the function call now representing the Region, find the passed value to that call that represents...

Definition IROutliner.cpp:1589

static void findCanonNumsForPHI(PHINode *PN, OutlinableRegion &Region, const DenseMap< Value *, Value * > &OutputMappings, SmallVector< std::pair< unsigned, BasicBlock * > > &CanonNums, bool ReplacedWithOutlinedCall=true)

Find the canonical numbering for the incoming Values into the PHINode PN.

Definition IROutliner.cpp:1615

static cl::opt< bool > NoCostModel("ir-outlining-no-cost", cl::init(false), cl::ReallyHidden, cl::desc("Debug option to outline greedily, without restriction that " "calculated benefit outweighs cost"))

static void moveBBContents(BasicBlock &SourceBB, BasicBlock &TargetBB)

Move the contents of SourceBB to before the last instruction of TargetBB.

Definition IROutliner.cpp:157

static bool nextIRInstructionDataMatchesNextInst(IRInstructionData &ID)

Checks that the next instruction in the InstructionDataList matches the next instruction in the modul...

Definition IROutliner.cpp:2312

static void moveFunctionData(Function &Old, Function &New, DenseMap< Value *, BasicBlock * > &NewEnds)

Move each BasicBlock in Old to New.

Definition IROutliner.cpp:703

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

static void getCodeExtractorArguments(OutlinableRegion &Region, std::vector< unsigned > &InputGVNs, DenseSet< unsigned > &NotSame, DenseMap< Value *, Value * > &OutputMappings, SetVector< Value * > &ArgInputs, SetVector< Value * > &Outputs)

Find the input GVNs and the output values for a region of Instructions.

Definition IROutliner.cpp:846

static void fillOverallFunction(Module &M, OutlinableGroup &CurrentGroup, std::vector< DenseMap< Value *, BasicBlock * > > &OutputStoreBBs, std::vector< Function * > &FuncsToRemove, const DenseMap< Value *, Value * > &OutputMappings)

Fill the new function that will serve as the replacement function for all of the extracted regions of...

Definition IROutliner.cpp:2219

static void findExtractedOutputToOverallOutputMapping(Module &M, OutlinableRegion &Region, SetVector< Value * > &Outputs)

Create a mapping of the output arguments for the Region to the output arguments of the overall outlin...

Definition IROutliner.cpp:1260

static void alignOutputBlockWithAggFunc(OutlinableGroup &OG, OutlinableRegion &Region, DenseMap< Value *, BasicBlock * > &OutputBBs, DenseMap< Value *, BasicBlock * > &EndBBs, const DenseMap< Value *, Value * > &OutputMappings, std::vector< DenseMap< Value *, BasicBlock * > > &OutputStoreBBs)

For the outlined section, move needed the StoreInsts for the output registers into their own block.

Definition IROutliner.cpp:2046

static bool collectRegionsConstants(OutlinableRegion &Region, DenseMap< unsigned, Constant * > &GVNToConstant, DenseSet< unsigned > &NotSame)

Find whether Region matches the global value numbering to Constant mapping found so far.

Definition IROutliner.cpp:549

static PHINode * findOrCreatePHIInBlock(PHINode &PN, OutlinableRegion &Region, BasicBlock *OverallPhiBlock, const DenseMap< Value *, Value * > &OutputMappings, DenseSet< PHINode * > &UsedPHIs)

Find, or add PHINode PN to the combined PHINode Block OverallPHIBlock in order to condense the number...

Definition IROutliner.cpp:1659

static bool analyzeAndPruneOutputBlocks(DenseMap< Value *, BasicBlock * > &BlocksToPrune, OutlinableRegion &Region)

Remove empty output blocks from the outlined region.

Definition IROutliner.cpp:1999

static hash_code encodePHINodeData(PHINodeData &PND)

Encode PND as an integer for easy lookup based on the argument location, the parent BasicBlock canoni...

Definition IROutliner.cpp:1138

SmallVector< unsigned, 2 > CanonList

Definition IROutliner.cpp:1127

CallInst * replaceCalledFunction(Module &M, OutlinableRegion &Region)

Replace the extracted function in the Region with a call to the overall function constructed from the...

Definition IROutliner.cpp:1413

static void createAndInsertBasicBlocks(DenseMap< Value *, BasicBlock * > &OldMap, DenseMap< Value *, BasicBlock * > &NewMap, Function *ParentFunc, Twine BaseName)

Takes in a mapping, OldMap of ConstantValues to BasicBlocks, sorts keys, before creating a basic bloc...

Definition IROutliner.cpp:2101

static bool outputHasNonPHI(Value *V, unsigned PHILoc, PHINode &PN, SmallPtrSet< BasicBlock *, 1 > &Exits, DenseSet< BasicBlock * > &BlocksInRegion)

Check if the V has any uses outside of the region other than PN.

Definition IROutliner.cpp:1019

static void analyzeExitPHIsForOutputUses(BasicBlock *CurrentExitFromRegion, SmallPtrSet< BasicBlock *, 1 > &PotentialExitsFromRegion, DenseSet< BasicBlock * > &RegionBlocks, SetVector< Value * > &Outputs, DenseSet< Value * > &OutputsReplacedByPHINode, DenseSet< Value * > &OutputsWithNonPhiUses)

Test whether CurrentExitFromRegion contains any PhiNodes that should be considered outputs.

Definition IROutliner.cpp:1076

static void getSortedConstantKeys(std::vector< Value * > &SortedKeys, DenseMap< Value *, BasicBlock * > &Map)

A function to sort the keys of Map, which must be a mapping of constant values to basic blocks and re...

Definition IROutliner.cpp:166

static InstructionCost findCostForOutputBlocks(Module &M, OutlinableGroup &CurrentGroup, TargetTransformInfo &TTI)

Find the extra instructions needed to handle any output values for the region.

Definition IROutliner.cpp:2531

static void replaceTargetsFromPHINode(BasicBlock *PHIBlock, BasicBlock *Find, BasicBlock *Replace, DenseSet< BasicBlock * > &Included)

Rewrite the BranchInsts in the incoming blocks to PHIBlock that are found in Included to branch to Ba...

Definition IROutliner.cpp:221

static void findExtractedInputToOverallInputMapping(OutlinableRegion &Region, std::vector< unsigned > &InputGVNs, SetVector< Value * > &ArgInputs)

Look over the inputs and map each input argument to an argument in the overall function for the Outli...

Definition IROutliner.cpp:917

static void mapInputsToGVNs(IRSimilarityCandidate &C, SetVector< Value * > &CurrentInputs, const DenseMap< Value *, Value * > &OutputMappings, std::vector< unsigned > &EndInputNumbers)

Find the GVN for the inputs that have been found by the CodeExtractor.

Definition IROutliner.cpp:789

static void replaceArgumentUses(OutlinableRegion &Region, DenseMap< Value *, BasicBlock * > &OutputBBs, const DenseMap< Value *, Value * > &OutputMappings, bool FirstFunction=false)

Definition IROutliner.cpp:1781

static DISubprogram * getSubprogramOrNull(OutlinableGroup &Group)

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

Definition IROutliner.cpp:620

static Value * findOutputMapping(const DenseMap< Value *, Value * > OutputMappings, Value *Input)

Check the OutputMappings structure for value Input, if it exists it has been used as an output for ou...

Definition IROutliner.cpp:530

static Value * findOutputValueInRegion(OutlinableRegion &Region, unsigned OutputCanon)

For the OutputCanon number passed in find the value represented by this canonical number.

Definition IROutliner.cpp:2479

static std::optional< bool > constantMatches(Value *V, unsigned GVN, DenseMap< unsigned, Constant * > &GVNToConstant)

Find whether V matches the Constants previously found for the GVN.

Definition IROutliner.cpp:463

static void findConstants(IRSimilarityCandidate &C, DenseSet< unsigned > &NotSame, std::vector< unsigned > &Inputs)

Find the constants that will need to be lifted into arguments as they are not the same in each instan...

Definition IROutliner.cpp:761

void replaceConstants(OutlinableRegion &Region)

Within an extracted function, replace the constants that need to be lifted into arguments with the ac...

Definition IROutliner.cpp:1915

std::pair< unsigned, unsigned > ArgLocWithBBCanon

Definition IROutliner.cpp:1125

static Value * getPassedArgumentInAlreadyOutlinedFunction(const Argument *A, const OutlinableRegion &Region)

For the function call now representing the Region, find the passed value to that call that represents...

Definition IROutliner.cpp:1573

void createSwitchStatement(Module &M, OutlinableGroup &OG, DenseMap< Value *, BasicBlock * > &EndBBs, std::vector< DenseMap< Value *, BasicBlock * > > &OutputStoreBBs)

Create the switch statement for outlined function to differentiate between all the output blocks.

Definition IROutliner.cpp:2126

static BasicBlock * findOrCreatePHIBlock(OutlinableGroup &Group, Value *RetVal)

Find or create a BasicBlock in the outlined function containing PhiBlocks for RetVal.

Definition IROutliner.cpp:1525

std::optional< unsigned > findDuplicateOutputBlock(DenseMap< Value *, BasicBlock * > &OutputBBs, std::vector< DenseMap< Value *, BasicBlock * > > &OutputStoreBBs)

It is possible that there is a basic block that already performs the same stores.

Definition IROutliner.cpp:1944

This header defines various interfaces for pass management in LLVM.

static const T * Find(StringRef S, ArrayRef< T > A)

Find KV in array using binary search.

FunctionAnalysisManager FAM

This pass exposes codegen information to IR-level passes.

The Input class is used to parse a yaml document into in-memory structs and vectors.

PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)

Get the result of an analysis pass for a given IR unit.

This class represents an incoming formal argument to a Function.

ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...

Functions, function parameters, and return types can have attributes to indicate how they should be t...

LLVM Basic Block Representation.

LLVM_ABI void replaceSuccessorsPhiUsesWith(BasicBlock *Old, BasicBlock *New)

Update all phi nodes in this basic block's successors to refer to basic block New instead of basic bl...

iterator begin()

Instruction iterator methods.

iterator_range< const_phi_iterator > phis() const

Returns a range that iterates over the phis in the basic block.

const Function * getParent() const

Return the enclosing method, or null if none.

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

Creates a new BasicBlock.

LLVM_ABI InstListType::const_iterator getFirstNonPHIOrDbg(bool SkipPseudoOp=true) const

Returns a pointer to the first instruction in this block that is not a PHINode or a debug intrinsic,...

LLVM_ABI const BasicBlock * getUniqueSuccessor() const

Return the successor of this block if it has a unique successor.

LLVM_ABI const BasicBlock * getSinglePredecessor() const

Return the predecessor of this block if it has a single predecessor block.

LLVM_ABI SymbolTableList< BasicBlock >::iterator eraseFromParent()

Unlink 'this' from the containing function and delete it.

InstListType::iterator iterator

Instruction iterators...

LLVM_ABI LLVMContext & getContext() const

Get the context in which this basic block lives.

const Instruction * getTerminator() const LLVM_READONLY

Returns the terminator instruction if the block is well formed or null if the block is not well forme...

void splice(BasicBlock::iterator ToIt, BasicBlock *FromBB)

Transfer all instructions from FromBB to this basic block at ToIt.

Conditional or Unconditional Branch instruction.

unsigned getNumSuccessors() const

static BranchInst * Create(BasicBlock *IfTrue, InsertPosition InsertBefore=nullptr)

BasicBlock * getSuccessor(unsigned i) const

void setSuccessor(unsigned idx, BasicBlock *NewSucc)

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

static CallInst * Create(FunctionType *Ty, Value *F, const Twine &NameStr="", InsertPosition InsertBefore=nullptr)

This is the shared class of boolean and integer constants.

uint64_t getLimitedValue(uint64_t Limit=~0ULL) const

getLimitedValue - If the value is smaller than the specified limit, return it, otherwise return the l...

static LLVM_ABI ConstantPointerNull * get(PointerType *T)

Static factory methods - Return objects of the specified value.

This is an important base class in LLVM.

Subprogram description. Uses SubclassData1.

static DebugLoc getDropped()

iterator find(const_arg_type_t< KeyT > Val)

bool erase(const KeyT &Val)

bool contains(const_arg_type_t< KeyT > Val) const

Return true if the specified key is in the map, false otherwise.

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

Implements a dense probed hash-table based set.

void getDescendants(NodeT *R, SmallVectorImpl< NodeT * > &Result) const

Get all nodes dominated by R, including R itself.

void insertEdge(NodeT *From, NodeT *To)

Inform the dominator tree about a CFG edge insertion and update the tree.

void deleteEdge(NodeT *From, NodeT *To)

Inform the dominator tree about a CFG edge deletion and update the tree.

Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.

Class to represent function types.

static LLVM_ABI FunctionType * get(Type *Result, ArrayRef< Type * > Params, bool isVarArg)

This static method is the primary way of constructing a FunctionType.

void addFnAttr(Attribute::AttrKind Kind)

Add function attributes to this function.

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

const BasicBlock & getEntryBlock() const

FunctionType * getFunctionType() const

Returns the FunctionType for me.

const BasicBlock & back() const

AttributeList getAttributes() const

Return the attribute list for this Function.

bool hasOptNone() const

Do not optimize this function (-O0).

LLVMContext & getContext() const

getContext - Return a reference to the LLVMContext associated with this function.

void addParamAttr(unsigned ArgNo, Attribute::AttrKind Kind)

adds the attribute to the list of attributes for the given arg.

Argument * getArg(unsigned i) const

bool hasFnAttribute(Attribute::AttrKind Kind) const

Return true if the function has the attribute.

bool hasLinkOnceODRLinkage() const

@ InternalLinkage

Rename collisions when linking (static functions).

PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM)

Definition IROutliner.cpp:2996

This class is a pass that identifies similarity in a Module, extracts instances of the similarity,...

bool run(Module &M)

Definition IROutliner.cpp:2989

An analysis pass that runs and returns the IRSimilarityIdentifier run on the Module.

This is a class that wraps a range of IRInstructionData from one point to another in the vector of IR...

std::optional< unsigned > getGVN(Value *V)

Finds the positive number associated with V if it has been mapped.

unsigned getEndIdx() const

void getBasicBlocks(DenseSet< BasicBlock * > &BBSet) const

unsigned getStartIdx() const

BasicBlock * getStartBB()

std::optional< unsigned > getCanonicalNum(unsigned N)

Find the canonical number from the global value number N stored in the candidate.

IRInstructionData * front() const

This class puts all the pieces of the IRInstructionData, IRInstructionMapper, IRSimilarityCandidate t...

LLVM_ABI Instruction * clone() const

Create a copy of 'this' instruction that is identical in all ways except the following:

LLVM_ABI void insertBefore(InstListType::iterator InsertPos)

Insert an unlinked instruction into a basic block immediately before the specified position.

LLVM_ABI InstListType::iterator eraseFromParent()

This method unlinks 'this' from the containing basic block and deletes it.

LLVM_ABI const Function * getFunction() const

Return the function this instruction belongs to.

bool isTerminator() const

void setDebugLoc(DebugLoc Loc)

Set the debug location information for this instruction.

LLVM_ABI InstListType::iterator insertInto(BasicBlock *ParentBB, InstListType::iterator It)

Inserts an unlinked instruction into ParentBB at position It and returns the iterator of the inserted...

An instruction for reading from memory.

Value * getPointerOperand()

static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata * > MDs)

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

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

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

void setIncomingBlock(unsigned i, BasicBlock *BB)

void setIncomingValue(unsigned i, Value *V)

BasicBlock * getIncomingBlock(unsigned i) const

Return incoming basic block number i.

Value * getIncomingValue(unsigned i) const

Return incoming value number x.

unsigned getNumIncomingValues() const

Return the number of incoming edges.

static LLVM_ABI PointerType * get(Type *ElementType, unsigned AddressSpace)

This constructs a pointer to an object of the specified type in a numbered address space.

A set of analyses that are preserved following a run of a transformation pass.

static PreservedAnalyses none()

Convenience factory function for the empty preserved set.

static PreservedAnalyses all()

Construct a special preserved set that preserves all passes.

bool contains(const BlockT *BB) const

Check if the region contains a BasicBlock.

RegionT * getParent() const

Get the parent of the Region.

Return a value (possibly void), from a function.

Value * getReturnValue() const

Convenience accessor. Returns null if there is no return value.

A vector that has set insertion semantics.

ArrayRef< value_type > getArrayRef() const

size_type size() const

Determine the number of elements in the SetVector.

size_type count(const_arg_type key) const

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

bool insert(const value_type &X)

Insert a new element into the SetVector.

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

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

SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.

void push_back(const T &Elt)

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

An instruction for storing to memory.

static SwitchInst * Create(Value *Value, BasicBlock *Default, unsigned NumCases, InsertPosition InsertBefore=nullptr)

LLVM_ABI void addCase(ConstantInt *OnVal, BasicBlock *Dest)

Add an entry to the switch instruction.

Analysis pass providing the TargetTransformInfo.

This pass provides access to the codegen interfaces that are needed for IR-level transformations.

LLVM_ABI InstructionCost getMemoryOpCost(unsigned Opcode, Type *Src, Align Alignment, unsigned AddressSpace, TTI::TargetCostKind CostKind=TTI::TCK_RecipThroughput, OperandValueInfo OpdInfo={OK_AnyValue, OP_None}, const Instruction *I=nullptr) const

@ TCK_CodeSize

Instruction code size.

@ TCC_Basic

The cost of a typical 'add' instruction.

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

static LLVM_ABI IntegerType * getInt32Ty(LLVMContext &C)

static LLVM_ABI Type * getVoidTy(LLVMContext &C)

bool isIntegerTy() const

True if this is an instance of IntegerType.

bool isVoidTy() const

Return true if this is 'void'.

void setOperand(unsigned i, Value *Val)

LLVM Value Representation.

Type * getType() const

All values are typed, get the type of this value.

bool hasOneUse() const

Return true if there is exactly one use of this value.

LLVM_ABI void replaceAllUsesWith(Value *V)

Change all uses of this to point to a new Value.

LLVM_ABI StringRef getName() const

Return a constant reference to the value's name.

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

bool contains(const_arg_type_t< ValueT > V) const

Check if the set contains the given element.

bool erase(const ValueT &V)

An opaque object representing a hash code.

const ParentTy * getParent() const

self_iterator getIterator()

NodeTy * getNextNode()

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

iterator erase(iterator I)

Remove a node by iterator; never deletes.

iterator insert(iterator I, reference Node)

Insert a node by reference; never copies.

constexpr char Align[]

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

unsigned ID

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

@ C

The default llvm calling convention, compatible with C.

std::vector< SimilarityGroup > SimilarityGroupList

std::vector< IRSimilarityCandidate > SimilarityGroup

@ BasicBlock

Various leaf nodes.

initializer< Ty > init(const Ty &Val)

@ User

could "use" a pointer

DiagnosticInfoOptimizationBase::Argument NV

friend class Instruction

Iterator for Instructions in a `BasicBlock.

This is an optimization pass for GlobalISel generic memory operations.

FunctionAddr VTableAddr Value

void stable_sort(R &&Range)

hash_code hash_value(const FixedPointSemantics &Val)

void interleave(ForwardIterator begin, ForwardIterator end, UnaryFunctor each_fn, NullaryFunctor between_fn)

An STL-style algorithm similar to std::for_each that applies a second functor between every pair of e...

decltype(auto) dyn_cast(const From &Val)

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

auto successors(const MachineBasicBlock *BB)

iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)

Make a range that does early increment to allow mutation of the underlying range without disrupting i...

InnerAnalysisManagerProxy< FunctionAnalysisManager, Module > FunctionAnalysisManagerModuleProxy

Provide the FunctionAnalysisManager to Module proxy.

cl::opt< bool > DisableIndirectCalls("no-ir-sim-indirect-calls", cl::init(false), cl::ReallyHidden, cl::desc("disable outlining indirect calls."))

Definition IROutliner.cpp:43

auto dyn_cast_or_null(const Y &Val)

bool any_of(R &&range, UnaryPredicate P)

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

@ RF_IgnoreMissingLocals

If this flag is set, the remapper ignores missing function-local entries (Argument,...

@ RF_NoModuleLevelChanges

If this flag is set, the remapper knows that only local values within a function (such as an instruct...

LLVM_ABI raw_ostream & dbgs()

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

bool none_of(R &&Range, UnaryPredicate P)

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

class LLVM_GSL_OWNER SmallVector

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

bool isa(const From &Val)

isa - Return true if the parameter to the template is an instance of one of the template type argu...

cl::opt< bool > DisableBranches("no-ir-sim-branch-matching", cl::init(false), cl::ReallyHidden, cl::desc("disable similarity matching, and outlining, " "across branches for debugging purposes."))

Definition IROutliner.cpp:39

cl::opt< bool > DisableIntrinsics("no-ir-sim-intrinsics", cl::init(false), cl::ReallyHidden, cl::desc("Don't match or outline intrinsics"))

Definition IROutliner.cpp:47

ValueMap< const Value *, WeakTrackingVH > ValueToValueMapTy

decltype(auto) cast(const From &Val)

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

void RemapFunction(Function &F, ValueToValueMapTy &VM, RemapFlags Flags=RF_None, ValueMapTypeRemapper *TypeMapper=nullptr, ValueMaterializer *Materializer=nullptr, const MetadataPredicate *IdentityMD=nullptr)

Remap the operands, metadata, arguments, and instructions of a function.

auto predecessors(const MachineBasicBlock *BB)

auto seq(T Begin, T End)

Iterate over an integral type from Begin up to - but not including - End.

hash_code hash_combine(const Ts &...args)

Combine values into a single hash_code.

LLVM_ABI void updateLoopMetadataDebugLocations(Instruction &I, function_ref< Metadata *(Metadata *)> Updater)

Update the debug locations contained within the MD_loop metadata attached to the instruction I,...

hash_code hash_combine_range(InputIteratorT first, InputIteratorT last)

Compute a hash_code for a sequence of values.

AnalysisManager< Module > ModuleAnalysisManager

Convenience typedef for the Module analysis manager.

The OutlinableGroup holds all the overarching information for outlining a set of regions that are str...

Definition IROutliner.cpp:73

std::optional< unsigned > SwiftErrorArgument

The argument that needs to be marked with the swifterr attribute.

Definition IROutliner.cpp:136

std::vector< Type * > ArgumentTypes

The argument types for the function created as the overall function to replace the extracted function...

Definition IROutliner.cpp:79

DenseSet< ArrayRef< unsigned > > OutputGVNCombinations

A set containing the different GVN store sets needed.

Definition IROutliner.cpp:99

void findSameConstants(DenseSet< unsigned > &NotSame)

For the Regions, we look at every Value.

Definition IROutliner.cpp:598

InstructionCost Cost

The number of added instructions needed for the outlining of the Regions.

Definition IROutliner.cpp:132

DenseMap< unsigned, std::pair< std::pair< unsigned, unsigned >, SmallVector< unsigned, 2 > > > PHINodeGVNToGVNs

Definition IROutliner.cpp:124

unsigned PHINodeGVNTracker

Tracker counting backwards from the highest unsigned value possible to avoid conflicting with the GVN...

Definition IROutliner.cpp:120

std::vector< OutlinableRegion * > Regions

The sections that could be outlined.

Definition IROutliner.cpp:75

DenseMap< hash_code, unsigned > GVNsToPHINodeGVN

Definition IROutliner.cpp:125

bool IgnoreGroup

Flag for whether we should not consider this group of OutlinableRegions for extraction.

Definition IROutliner.cpp:87

DenseMap< Value *, BasicBlock * > EndBBs

The return blocks for the overall function.

Definition IROutliner.cpp:90

unsigned BranchesToOutside

The number of branches in the region target a basic block that is outside of the region.

Definition IROutliner.cpp:115

Function * OutlinedFunction

The Function for the collective overall function.

Definition IROutliner.cpp:83

bool InputTypesSet

Flag for whether the ArgumentTypes have been defined after the extraction of the first region.

Definition IROutliner.cpp:103

DenseMap< Value *, BasicBlock * > PHIBlocks

The PHIBlocks with their corresponding return block based on the return value as the key.

Definition IROutliner.cpp:94

FunctionType * OutlinedFunctionType

The FunctionType for the overall function.

Definition IROutliner.cpp:81

DenseMap< unsigned, unsigned > CanonicalNumberToAggArg

The mapping of the canonical numbering of the values in outlined sections to specific arguments.

Definition IROutliner.cpp:111

void collectGVNStoreSets(Module &M)

For the regions, look at each set of GVN stores needed and account for each combination.

Definition IROutliner.cpp:605

InstructionCost Benefit

The number of instructions that will be outlined by extracting Regions.

Definition IROutliner.cpp:129

unsigned NumAggregateInputs

The number of input values in ArgumentTypes.

Definition IROutliner.cpp:107

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

This provides the utilities for hashing an Instruction to an unsigned integer.

Instruction * Inst

The source Instruction that is being wrapped.

Incoming for lane maks phi as machine instruction, incoming register Reg and incoming block Block are...

The OutlinableRegion holds all the information for a specific region, or sequence of instructions.

CallInst * Call

The call site of the extracted region.

CodeExtractor * CE

Used to create an outlined function.

InstructionCost getBenefit(TargetTransformInfo &TTI)

Get the size of the code removed from the region.

Definition IROutliner.cpp:486

BasicBlock * FollowBB

The BasicBlock that is after the start of the region BasicBlock, only defined when the region has bee...

unsigned OutputBlockNum

The corresponding BasicBlock with the appropriate stores for this OutlinableRegion in the overall fun...

bool CandidateSplit

Flag for whether we have split out the IRSimilarityCanidate.

bool IgnoreRegion

Flag for whether we should not consider this region for extraction.

void splitCandidate()

For the contained region, split the parent BasicBlock at the starting and ending instructions of the ...

Definition IROutliner.cpp:249

Value * findCorrespondingValueIn(const OutlinableRegion &Other, Value *V)

Find a corresponding value for V in similar OutlinableRegion Other.

Definition IROutliner.cpp:187

BasicBlock * findCorrespondingBlockIn(const OutlinableRegion &Other, BasicBlock *BB)

Find a corresponding BasicBlock for BB in similar OutlinableRegion Other.

Definition IROutliner.cpp:199

BasicBlock * PrevBB

The BasicBlock that is before the start of the region BasicBlock, only defined when the region has be...

BasicBlock * EndBB

The BasicBlock that contains the ending instruction of the region.

IRSimilarityCandidate * Candidate

Describes the region of code.

DenseMap< Value *, Value * > RemappedArguments

Values in the outlined functions will often be replaced by arguments.

OutlinableRegion(IRSimilarityCandidate &C, OutlinableGroup &Group)

Function * ExtractedFunction

The function for the extracted region.

bool EndsInBranch

Marks whether this region ends in a branch, there is special handling required for the following basi...

BasicBlock * StartBB

The BasicBlock that contains the starting instruction of the region.

void reattachCandidate()

For the contained region, reattach the BasicBlock at the starting and ending instructions of the cont...

Definition IROutliner.cpp:375