GVNHoist.cpp Source File (original) (raw)

71#include

72#include

73#include

74#include

75#include

77using namespace llvm;

79#define DEBUG_TYPE "gvn-hoist"

81 STATISTIC(NumHoisted, "Number of instructions hoisted");

82 STATISTIC(NumRemoved, "Number of instructions removed");

83 STATISTIC(NumLoadsHoisted, "Number of loads hoisted");

84 STATISTIC(NumLoadsRemoved, "Number of loads removed");

85 STATISTIC(NumStoresHoisted, "Number of stores hoisted");

86 STATISTIC(NumStoresRemoved, "Number of stores removed");

87 STATISTIC(NumCallsHoisted, "Number of calls hoisted");

88 STATISTIC(NumCallsRemoved, "Number of calls removed");

92 cl::desc("Max number of instructions to hoist "

93 "(default unlimited = -1)"));

97 cl::desc("Max number of basic blocks on the path between "

98 "hoisting locations (default = 4, unlimited = -1)"));

102 cl::desc("Hoist instructions from the beginning of the BB up to the "

103 "maximum specified depth (default = 100, unlimited = -1)"));

104

107 cl::desc("Maximum length of dependent chains to hoist "

108 "(default = 10, unlimited = -1)"));

109

110namespace llvm {

111

115

116

117

119

121

122

123using VNType = std::pair<unsigned, uintptr_t>;

124

126

127

128

129

130

131

132

133

134

135

136

139

140

142

143

145

148};

149

155

156

157

158enum : uintptr_t { InvalidVN = ~(uintptr_t)2 };

159

160

163

164public:

165

167

169 VNtoScalars[{V, InvalidVN}].push_back(I);

170 }

171

173};

174

175

178

179public:

180

182 if (Load->isSimple()) {

183 unsigned V = VN.lookupOrAdd(Load->getPointerOperand());

184

185

186 VNtoLoads[{V, (uintptr_t)Load->getType()}].push_back(Load);

187 }

188 }

189

191};

192

193

196

197public:

198

199

201 if (!Store->isSimple())

202 return;

203

204 Value *Ptr = Store->getPointerOperand();

205 Value *Val = Store->getValueOperand();

207 }

208

210};

211

212

217

218public:

219

221

222

223

225 auto Entry = std::make_pair(V, InvalidVN);

226

227 if (Call->doesNotAccessMemory())

228 VNtoCallsScalars[Entry].push_back(Call);

229 else if (Call->onlyReadsMemory())

230 VNtoCallsLoads[Entry].push_back(Call);

231 else

232 VNtoCallsStores[Entry].push_back(Call);

233 }

234

238};

239

240

241

242

244public:

247 : DT(DT), PDT(PDT), AA(AA), MD(MD), MSSA(MSSA),

249 MSSA->ensureOptimizedUses();

250 }

251

253

254

255

256

257

258

259

260 unsigned int rank(const Value *V) const;

261

262private:

269 std::unique_ptr MSSAUpdater;

274 unsigned NumFuncArgs;

275 const bool HoistingGeps = false;

276

277 enum InsKind { Unknown, Scalar, Load, Store };

278

279

281

282

285 unsigned I1DFS = DFSNumber.lookup(I1);

286 unsigned I2DFS = DFSNumber.lookup(I2);

287 assert(I1DFS && I2DFS);

288 return I1DFS < I2DFS;

289 }

290

291

292 bool hasMemoryUse(const Instruction *NewPt, MemoryDef *Def,

293 const BasicBlock *BB);

294

295 bool hasEHhelper(const BasicBlock *BB, const BasicBlock *SrcBB,

296 int &NBBsOnAllPaths);

297

298

299

300

301

302

303

304

305 bool hasEHOrLoadsOnPath(const Instruction *NewPt, MemoryDef *Def,

306 int &NBBsOnAllPaths);

307

308

309

310

311

312 bool hasEHOnPath(const BasicBlock *HoistPt, const BasicBlock *SrcBB,

313 int &NBBsOnAllPaths);

314

315

316

317 bool safeToHoistLdSt(const Instruction *NewPt, const Instruction *OldPt,

318 MemoryUseOrDef *U, InsKind K, int &NBBsOnAllPaths);

319

320

321

322 bool safeToHoistScalar(const BasicBlock *HoistBB, const BasicBlock *BB,

323 int &NBBsOnAllPaths) {

324 return !hasEHOnPath(HoistBB, BB, NBBsOnAllPaths);

325 }

326

327

328

329

330

331

332

333

334

335

336

337

338

339

340

341 bool valueAnticipable(CHIArgs C, Instruction *TI) const;

342

343

344

345 void checkSafety(CHIArgs C, BasicBlock *BB, InsKind K,

346 SmallVectorImpl &Safe);

347

348 using RenameStackType = DenseMap<VNType, SmallVector<Instruction *, 2>>;

349

350

351 void fillRenameStack(BasicBlock *BB, InValuesType &ValueBBs,

352 RenameStackType &RenameStack);

353

354 void fillChiArgs(BasicBlock *BB, OutValuesType &CHIBBs,

355 RenameStackType &RenameStack);

356

357

358

359

360

362 auto Root = PDT->getNode(nullptr);

363 if (!Root)

364 return;

365

368 if (!BB)

369 continue;

370

371 RenameStackType RenameStack;

372

373 fillRenameStack(BB, ValueBBs, RenameStack);

374

375

376 fillChiArgs(BB, CHIBBs, RenameStack);

377 }

378 }

379

380

381

382

383

384 void findHoistableCandidates(OutValuesType &CHIBBs, InsKind K,

386

387

388

390 InsKind K) {

391

392 std::vector Ranks;

393 for (const auto &Entry : Map) {

394 Ranks.push_back(Entry.first);

395 }

396

397

398

399

401 return (rank(*Map.lookup(r1).begin()) < rank(*Map.lookup(r2).begin()));

402 });

403

404

405

406

407

408

409

410

411

416 for (const auto &R : Ranks) {

418 if (V.size() < 2)

419 continue;

421 SmallPtrSet<BasicBlock *, 2> VNBlocks;

422 for (const auto &I : V) {

424 if (!hasEH(BBI))

425 VNBlocks.insert(BBI);

426 }

427

428

429

430

431

432

433 IDFs.setDefiningBlocks(VNBlocks);

434 IDFBlocks.clear();

435 IDFs.calculate(IDFBlocks);

436

437

438 for (unsigned i = 0; i < V.size(); ++i) {

439 InValue[V[i]->getParent()].push_back(std::make_pair(VN, V[i]));

440 }

441

442

443 CHIArg EmptyChi = {VN, nullptr, nullptr};

444 for (auto *IDFBB : IDFBlocks) {

445 for (unsigned i = 0; i < V.size(); ++i) {

446

447 if (DT->properlyDominates(IDFBB, V[i]->getParent())) {

448 OutValue[IDFBB].push_back(EmptyChi);

450 << IDFBB->getName() << ", for Insn: " << *V[i]);

451 }

452 }

453 }

454 }

455

456

457

458 insertCHI(InValue, OutValue);

459

460 findHoistableCandidates(OutValue, K, HPL);

461 }

462

463

464

465

466

467 bool allOperandsAvailable(const Instruction *I,

468 const BasicBlock *HoistPt) const;

469

470

471 bool allGepOperandsAvailable(const Instruction *I,

472 const BasicBlock *HoistPt) const;

473

474

475 void makeGepsAvailable(Instruction *Repl, BasicBlock *HoistPt,

477 Instruction *Gep) const;

478

479 void updateAlignment(Instruction *I, Instruction *Repl);

480

481

482

483 unsigned rauw(const SmallVecInsn &Candidates, Instruction *Repl,

484 MemoryUseOrDef *NewMemAcc);

485

486

487 void raMPHIuw(MemoryUseOrDef *NewMemAcc);

488

489

490 unsigned removeAndReplace(const SmallVecInsn &Candidates, Instruction *Repl,

491 BasicBlock *DestBB, bool MoveAccess);

492

493

494

495

496 bool makeGepOperandsAvailable(Instruction *Repl, BasicBlock *HoistPt,

497 const SmallVecInsn &InstructionsToHoist) const;

498

500

501

502

503 std::pair<unsigned, unsigned> hoistExpressions(Function &F);

504};

505

507 NumFuncArgs = F.arg_size();

508 VN.setDomTree(DT);

509 VN.setAliasAnalysis(AA);

510 VN.setMemDep(MD);

511 bool Res = false;

512

513 unsigned BBI = 0;

515 DFSNumber[BB] = ++BBI;

516 unsigned I = 0;

517 for (const auto &Inst : *BB)

518 DFSNumber[&Inst] = ++I;

519 }

520

521 int ChainLength = 0;

522

523

524 while (true) {

526 return Res;

527

528 auto HoistStat = hoistExpressions(F);

529 if (HoistStat.first + HoistStat.second == 0)

530 return Res;

531

532 if (HoistStat.second > 0)

533

534

535

536 VN.clear();

537

538 Res = true;

539 }

540

541 return Res;

542}

543

545

546

547

549 return 2;

551 return 1;

553 return 0;

555 return 3 + A->getArgNo();

556

557

558

559 auto Result = DFSNumber.lookup(V);

560 if (Result > 0)

561 return 4 + NumFuncArgs + Result;

562

563 return ~0;

564}

565

566bool GVNHoist::hasEH(const BasicBlock *BB) {

567 auto [It, Inserted] = BBSideEffects.try_emplace(BB);

568 if (!Inserted)

569 return It->second;

570

572 It->second = true;

573 return true;

574 }

575

577 It->second = true;

578 return true;

579 }

580

581 return false;

582}

583

587 if (!Acc)

588 return false;

589

593 bool ReachedNewPt = false;

594

595 for (const MemoryAccess &MA : *Acc)

598

599

600 if (BB == OldBB && firstInBB(OldPt, Insn))

601 break;

602

603

604 if (BB == NewBB) {

605 if (!ReachedNewPt) {

606 if (firstInBB(Insn, NewPt))

607 continue;

608 ReachedNewPt = true;

609 }

610 }

612 return true;

613 }

614

615 return false;

616}

617

619 int &NBBsOnAllPaths) {

620

621 if (NBBsOnAllPaths == 0)

622 return true;

623

624

625 if (hasEH(BB))

626 return true;

627

628

629

630

631 if ((BB != SrcBB) && HoistBarrier.count(BB))

632 return true;

633

634 return false;

635}

636

638 int &NBBsOnAllPaths) {

641 assert(DT->dominates(NewBB, OldBB) && "invalid path");

642 assert(DT->dominates(Def->getDefiningAccess()->getBlock(), NewBB) &&

643 "def does not dominate new hoisting point");

644

645

646

647

648

651 if (BB == NewBB) {

652

653 I.skipChildren();

654 continue;

655 }

656

657 if (hasEHhelper(BB, OldBB, NBBsOnAllPaths))

658 return true;

659

660

661 if (hasMemoryUse(NewPt, Def, BB))

662 return true;

663

664

665 if (NBBsOnAllPaths != -1)

666 --NBBsOnAllPaths;

667

668 ++I;

669 }

670

671 return false;

672}

673

674bool GVNHoist::hasEHOnPath(const BasicBlock *HoistPt, const BasicBlock *SrcBB,

675 int &NBBsOnAllPaths) {

676 assert(DT->dominates(HoistPt, SrcBB) && "Invalid path");

677

678

679

680

681

682

685 if (BB == HoistPt) {

686

687 I.skipChildren();

688 continue;

689 }

690

691 if (hasEHhelper(BB, SrcBB, NBBsOnAllPaths))

692 return true;

693

694

695 if (NBBsOnAllPaths != -1)

696 --NBBsOnAllPaths;

697

698 ++I;

699 }

700

701 return false;

702}

703

704bool GVNHoist::safeToHoistLdSt(const Instruction *NewPt,

706 GVNHoist::InsKind K, int &NBBsOnAllPaths) {

707

708 if (NewPt == OldPt)

709 return true;

710

714

715

716 MemoryAccess *D = U->getDefiningAccess();

718 if (DT->properlyDominates(NewBB, DBB))

719

720 return false;

721

722 if (NewBB == DBB && !MSSA->isLiveOnEntryDef(D))

724 if (!firstInBB(UD->getMemoryInst(), NewPt))

725

726 return false;

727

728

729 if (K == InsKind::Store) {

730 if (hasEHOrLoadsOnPath(NewPt, cast(U), NBBsOnAllPaths))

731 return false;

732 } else if (hasEHOnPath(NewBB, OldBB, NBBsOnAllPaths))

733 return false;

734

735 if (UBB == NewBB) {

736 if (DT->properlyDominates(DBB, NewBB))

737 return true;

739 assert(MSSA->locallyDominates(D, U));

740 }

741

742

743 return true;

744}

745

748 return false;

749

750 for (auto CHI : C) {

751

753 return false;

754 }

755 return true;

756}

757

758void GVNHoist::checkSafety(CHIArgs C, BasicBlock *BB, GVNHoist::InsKind K,

762 for (auto CHI : C) {

764 if (!Insn)

765 continue;

766

767

768

770 continue;

771 if (K == InsKind::Scalar) {

772 if (safeToHoistScalar(BB, Insn->getParent(), NumBBsOnAllPaths))

774 } else {

775 if (MemoryUseOrDef *UD = MSSA->getMemoryAccess(Insn))

776 if (safeToHoistLdSt(T, Insn, UD, K, NumBBsOnAllPaths))

778 }

779 }

780}

781

783 GVNHoist::RenameStackType &RenameStack) {

784 auto it1 = ValueBBs.find(BB);

785 if (it1 != ValueBBs.end()) {

786

788 << " for pushing instructions on stack";);

789 for (std::pair<VNType, Instruction *> &VI : reverse(it1->second)) {

790

792 RenameStack[VI.first].push_back(VI.second);

793 }

794 }

795}

796

798 GVNHoist::RenameStackType &RenameStack) {

799

801 auto P = CHIBBs.find(Pred);

802 if (P == CHIBBs.end()) {

803 continue;

804 }

805 LLVM_DEBUG(dbgs() << "\nLooking at CHIs in: " << Pred->getName(););

806

807

808 auto &VCHI = P->second;

809 for (auto It = VCHI.begin(), E = VCHI.end(); It != E;) {

810 CHIArg &C = *It;

811 if (.Dest) {

812 auto si = RenameStack.find(C.VN);

813

814

815

816 if (si != RenameStack.end() && si->second.size() &&

817 DT->properlyDominates(Pred, si->second.back()->getParent())) {

818 C.Dest = BB;

819 C.I = si->second.pop_back_val();

821 << "\nCHI Inserted in BB: " << C.Dest->getName() << *C.I

822 << ", VN: " << C.VN.first << ", " << C.VN.second);

823 }

824

825 It = std::find_if(It, VCHI.end(), [It](CHIArg &A) { return A != *It; });

826 } else

827 ++It;

828 }

829 }

830}

831

832void GVNHoist::findHoistableCandidates(OutValuesType &CHIBBs,

833 GVNHoist::InsKind K,

835 auto cmpVN = [](const CHIArg &A, const CHIArg &B) { return A.VN < B.VN; };

836

837

838

841 SmallVectorImpl &CHIs = A.second;

842

843

844

847 auto B = CHIs.begin();

848

849 auto PHIIt = llvm::find_if(CHIs, [B](CHIArg &A) { return A != *B; });

850 auto PrevIt = CHIs.begin();

851 while (PrevIt != PHIIt) {

852

854

855

856

857

858 checkSafety(make_range(PrevIt, PHIIt), BB, K, Safe);

859

860

864 for (auto B : Safe)

865 V.push_back(B.I);

866 }

867

868

869 PrevIt = PHIIt;

870 PHIIt = std::find_if(PrevIt, CHIs.end(),

871 [PrevIt](CHIArg &A) { return A != *PrevIt; });

872 }

873 }

874}

875

876bool GVNHoist::allOperandsAvailable(const Instruction *I,

878 for (const Use &Op : I->operands())

880 if (!DT->dominates(Inst->getParent(), HoistPt))

881 return false;

882

883 return true;

884}

885

886bool GVNHoist::allGepOperandsAvailable(const Instruction *I,

888 for (const Use &Op : I->operands())

890 if (!DT->dominates(Inst->getParent(), HoistPt)) {

891 if (const GetElementPtrInst *GepOp =

893 if (!allGepOperandsAvailable(GepOp, HoistPt))

894 return false;

895

896 } else {

897

898

899 return false;

900 }

901 }

902 return true;

903}

904

908 assert(allGepOperandsAvailable(Gep, HoistPt) && "GEP operands not available");

909

911 for (unsigned i = 0, e = Gep->getNumOperands(); i != e; ++i)

913

914 if (DT->dominates(Op->getParent(), HoistPt))

915 continue;

916

917

918

920 makeGepsAvailable(ClonedGep, HoistPt, InstructionsToHoist, GepOp);

921 }

922

923

925

926

927

929

930

931

932 for (const Instruction *OtherInst : InstructionsToHoist) {

933 const GetElementPtrInst *OtherGep;

936 else

940

941

942

943

944 if (OtherGep != Gep) {

947 }

948 }

949

950

952}

953

956 ReplacementLoad->setAlignment(

957 std::min(ReplacementLoad->getAlign(), cast(I)->getAlign()));

958 ++NumLoadsRemoved;

960 ReplacementStore->setAlignment(

961 std::min(ReplacementStore->getAlign(), cast(I)->getAlign()));

962 ++NumStoresRemoved;

964 ReplacementAlloca->setAlignment(std::max(ReplacementAlloca->getAlign(),

967 ++NumCallsRemoved;

968 }

969}

970

973 unsigned NR = 0;

974 for (Instruction *I : Candidates) {

975 if (I != Repl) {

976 ++NR;

977 updateAlignment(I, Repl);

978 if (NewMemAcc) {

979

980 MemoryAccess *OldMA = MSSA->getMemoryAccess(I);

982 MSSAUpdater->removeMemoryAccess(OldMA);

983 }

984

987 I->replaceAllUsesWith(Repl);

988

989 MD->removeInstruction(I);

990 I->eraseFromParent();

991 }

992 }

993 return NR;

994}

995

997 SmallPtrSet<MemoryPhi *, 4> UsePhis;

998 for (User *U : NewMemAcc->users())

1000 UsePhis.insert(Phi);

1001

1002 for (MemoryPhi *Phi : UsePhis) {

1003 auto In = Phi->incoming_values();

1004 if (llvm::all_of(In, [&](Use &U) { return U == NewMemAcc; })) {

1005 Phi->replaceAllUsesWith(NewMemAcc);

1006 MSSAUpdater->removeMemoryAccess(Phi);

1007 }

1008 }

1009}

1010

1011unsigned GVNHoist::removeAndReplace(const SmallVecInsn &Candidates,

1013 bool MoveAccess) {

1014 MemoryUseOrDef *NewMemAcc = MSSA->getMemoryAccess(Repl);

1015 if (MoveAccess && NewMemAcc) {

1016

1017

1019 }

1020

1021

1022 unsigned NR = rauw(Candidates, Repl, NewMemAcc);

1023

1024

1025 if (NewMemAcc)

1026 raMPHIuw(NewMemAcc);

1027 return NR;

1028}

1029

1030bool GVNHoist::makeGepOperandsAvailable(

1032 const SmallVecInsn &InstructionsToHoist) const {

1033

1034 GetElementPtrInst *Gep = nullptr;

1041

1042 if (Val) {

1044

1045 if (!allGepOperandsAvailable(Val, HoistPt))

1046 return false;

1047 } else if (!DT->dominates(Val->getParent(), HoistPt))

1048 return false;

1049 }

1050 }

1051

1052

1053 if (!Gep || !allGepOperandsAvailable(Gep, HoistPt))

1054 return false;

1055

1056 makeGepsAvailable(Repl, HoistPt, InstructionsToHoist, Gep);

1057

1059 makeGepsAvailable(Repl, HoistPt, InstructionsToHoist, Val);

1060

1061 return true;

1062}

1063

1064std::pair<unsigned, unsigned> GVNHoist::hoist(HoistingPointList &HPL) {

1065 unsigned NI = 0, NL = 0, NS = 0, NC = 0, NR = 0;

1067

1068

1070 const SmallVecInsn &InstructionsToHoist = HP.second;

1072 for (Instruction *I : InstructionsToHoist)

1073 if (I->getParent() == DestBB)

1074

1075

1076

1077 if (!Repl || firstInBB(I, Repl))

1078 Repl = I;

1079

1080

1081

1082 bool MoveAccess = true;

1083 if (Repl) {

1084

1085 assert(allOperandsAvailable(Repl, DestBB) &&

1086 "instruction depends on operands that are not available");

1087 MoveAccess = false;

1088 } else {

1089

1090

1091 Repl = InstructionsToHoist.front();

1092

1093

1094

1095

1096 if (!allOperandsAvailable(Repl, DestBB)) {

1097

1098

1099 if (HoistingGeps)

1100 continue;

1101

1102

1103 if (!makeGepOperandsAvailable(Repl, DestBB, InstructionsToHoist))

1104 continue;

1105 }

1106

1107

1109 MD->removeInstruction(Repl);

1111

1112 DFSNumber[Repl] = DFSNumber[Last]++;

1113 }

1114

1115

1117 NR += removeAndReplace(InstructionsToHoist, Repl, DestBB, MoveAccess);

1118

1120 ++NL;

1122 ++NS;

1124 ++NC;

1125 else

1126 ++NI;

1127 }

1128

1130 MSSA->verifyMemorySSA();

1131

1132 NumHoisted += NL + NS + NC + NI;

1133 NumRemoved += NR;

1134 NumLoadsHoisted += NL;

1135 NumStoresHoisted += NS;

1136 NumCallsHoisted += NC;

1137 return {NI, NL + NC + NS};

1138}

1139

1140std::pair<unsigned, unsigned> GVNHoist::hoistExpressions(Function &F) {

1141 InsnInfo II;

1142 LoadInfo LI;

1143 StoreInfo SI;

1144 CallInfo CI;

1145 for (BasicBlock *BB : depth_first(&F.getEntryBlock())) {

1146 int InstructionNb = 0;

1147 for (Instruction &I1 : *BB) {

1148

1149

1151 HoistBarrier.insert(BB);

1152 break;

1153 }

1154

1155

1157 break;

1158

1159

1160 if (I1.isTerminator())

1161 break;

1162

1164 LI.insert(Load, VN);

1166 SI.insert(Store, VN);

1169 if (Intr->getIntrinsicID() == Intrinsic::assume ||

1170 Intr->getIntrinsicID() == Intrinsic::sideeffect)

1171 continue;

1172 }

1174 break;

1175

1177 break;

1178

1179 CI.insert(Call, VN);

1181

1182

1183

1184

1185 II.insert(&I1, VN);

1186 }

1187 }

1188

1190 computeInsertionPoints(II.getVNTable(), HPL, InsKind::Scalar);

1191 computeInsertionPoints(LI.getVNTable(), HPL, InsKind::Load);

1192 computeInsertionPoints(SI.getVNTable(), HPL, InsKind::Store);

1193 computeInsertionPoints(CI.getScalarVNTable(), HPL, InsKind::Scalar);

1194 computeInsertionPoints(CI.getLoadVNTable(), HPL, InsKind::Load);

1195 computeInsertionPoints(CI.getStoreVNTable(), HPL, InsKind::Store);

1196 return hoist(HPL);

1197}

1198

1199}

1200

1208 if (.run(F))

1210

1214 return PA;

1215}

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

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

static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")

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

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

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

This file defines the DenseMap class.

This file defines the DenseSet and SmallDenseSet classes.

static cl::opt< int > MaxHoistedThreshold("gvn-max-hoisted", cl::Hidden, cl::init(-1), cl::desc("Max number of instructions to hoist " "(default unlimited = -1)"))

static cl::opt< int > MaxChainLength("gvn-hoist-max-chain-length", cl::Hidden, cl::init(10), cl::desc("Maximum length of dependent chains to hoist " "(default = 10, unlimited = -1)"))

static cl::opt< int > MaxDepthInBB("gvn-hoist-max-depth", cl::Hidden, cl::init(100), cl::desc("Hoist instructions from the beginning of the BB up to the " "maximum specified depth (default = 100, unlimited = -1)"))

static cl::opt< int > MaxNumberOfBBSInPath("gvn-hoist-max-bbs", cl::Hidden, cl::init(4), cl::desc("Max number of basic blocks on the path between " "hoisting locations (default = 4, unlimited = -1)"))

This file provides the interface for LLVM's Global Value Numbering pass which eliminates fully redund...

This is the interface for a simple mod/ref and alias analysis over globals.

This file provides various utilities for inspecting and working with the control flow graph in LLVM I...

This header defines various interfaces for pass management in LLVM.

This defines the Use class.

This file exposes an interface to building/using memory SSA to walk memory instructions using a use/d...

uint64_t IntrinsicInst * II

static void r2(uint32_t &A, uint32_t &B, uint32_t &C, uint32_t &D, uint32_t &E, int I, uint32_t *Buf)

static void r1(uint32_t &A, uint32_t &B, uint32_t &C, uint32_t &D, uint32_t &E, int I, uint32_t *Buf)

This file defines the SmallPtrSet class.

This file defines the SmallVector class.

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

#define STATISTIC(VARNAME, DESC)

A manager for alias analyses.

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

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

LLVM Basic Block Representation.

bool hasAddressTaken() const

Returns true if there are any uses of this basic block other than direct branches,...

bool isEHPad() const

Return true if this basic block is an exception handling block.

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

bool isConvergent() const

Determine if the invoke is convergent.

Definition GVNHoist.cpp:213

void insert(CallInst *Call, GVNPass::ValueTable &VN)

Definition GVNHoist.cpp:220

const VNtoInsns & getLoadVNTable() const

Definition GVNHoist.cpp:236

const VNtoInsns & getScalarVNTable() const

Definition GVNHoist.cpp:235

const VNtoInsns & getStoreVNTable() const

Definition GVNHoist.cpp:237

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

ValueT lookup(const_arg_type_t< KeyT > Val) const

lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...

std::pair< iterator, bool > try_emplace(KeyT &&Key, Ts &&...Args)

Implements a dense probed hash-table based set.

Analysis pass which computes a DominatorTree.

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

Definition GVNHoist.cpp:243

bool run(Function &F)

Definition GVNHoist.cpp:506

GVNHoist(DominatorTree *DT, PostDominatorTree *PDT, AliasAnalysis *AA, MemoryDependenceResults *MD, MemorySSA *MSSA)

Definition GVNHoist.cpp:245

unsigned int rank(const Value *V) const

Definition GVNHoist.cpp:544

This class holds the mapping between values and value numbers.

LLVM_ABI uint32_t lookupOrAdd(MemoryAccess *MA)

Definition GVNHoist.cpp:161

const VNtoInsns & getVNTable() const

Definition GVNHoist.cpp:172

void insert(Instruction *I, GVNPass::ValueTable &VN)

Definition GVNHoist.cpp:166

LLVM_ABI bool mayThrow(bool IncludePhaseOneUnwind=false) const LLVM_READONLY

Return true if this instruction may throw an exception.

LLVM_ABI Instruction * clone() const

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

LLVM_ABI unsigned getNumSuccessors() const LLVM_READONLY

Return the number of successors that this instruction has.

LLVM_ABI void dropLocation()

Drop the instruction's debug location.

const DebugLoc & getDebugLoc() const

Return the debug location for this node as a DebugLoc.

LLVM_ABI void andIRFlags(const Value *V)

Logical 'and' of any supported wrapping, exact, and fast-math flags of V and this instruction.

LLVM_ABI void moveBefore(InstListType::iterator InsertPos)

Unlink this instruction from its current basic block and insert it into the basic block that MovePos ...

LLVM_ABI void insertBefore(InstListType::iterator InsertPos)

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

LLVM_ABI bool mayHaveSideEffects() const LLVM_READONLY

Return true if the instruction may have side effects.

LLVM_ABI void dropUnknownNonDebugMetadata(ArrayRef< unsigned > KnownIDs={})

Drop all unknown metadata except for debug locations.

LLVM_ABI void applyMergedLocation(DebugLoc LocA, DebugLoc LocB)

Merge 2 debug locations and apply it to the Instruction.

Definition GVNHoist.cpp:176

const VNtoInsns & getVNTable() const

Definition GVNHoist.cpp:190

void insert(LoadInst *Load, GVNPass::ValueTable &VN)

Definition GVNHoist.cpp:181

An instruction for reading from memory.

Represents a read-write access to memory, whether it is a must-alias, or a may-alias.

An analysis that produces MemoryDependenceResults for a function.

Provides a lazy, caching interface for making common memory aliasing information queries,...

An analysis that produces MemorySSA for a function.

static LLVM_ABI bool defClobbersUseOrDef(MemoryDef *MD, const MemoryUseOrDef *MU, AliasAnalysis &AA)

Encapsulates MemorySSA, including all data associated with memory accesses.

iplist< MemoryAccess, ilist_tag< MSSAHelpers::AllAccessTag > > AccessList

Class that has the common methods + fields of memory uses/defs.

Analysis pass which computes a PostDominatorTree.

PostDominatorTree Class - Concrete subclass of DominatorTree that is used to compute the post-dominat...

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

static PreservedAnalyses all()

Construct a special preserved set that preserves all passes.

PreservedAnalyses & preserve()

Mark an analysis as preserved.

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

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

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

typename SuperClass::iterator iterator

void push_back(const T &Elt)

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

Definition GVNHoist.cpp:194

void insert(StoreInst *Store, GVNPass::ValueTable &VN)

Definition GVNHoist.cpp:200

const VNtoInsns & getVNTable() const

Definition GVNHoist.cpp:209

An instruction for storing to memory.

LLVM_ABI bool replaceUsesOfWith(Value *From, Value *To)

Replace uses of one Value with another.

Value * getOperand(unsigned i) const

unsigned getNumOperands() const

LLVM Value Representation.

LLVM_ABI void replaceAllUsesWith(Value *V)

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

iterator_range< user_iterator > users()

LLVM_ABI StringRef getName() const

Return a constant reference to the value's name.

const ParentTy * getParent() const

self_iterator getIterator()

A range adaptor for a pair of iterators.

This provides a very simple, boring adaptor for a begin and end iterator into a range type.

Abstract Attribute helper functions.

@ C

The default llvm calling convention, compatible with C.

@ BasicBlock

Various leaf nodes.

initializer< Ty > init(const Ty &Val)

NodeAddr< DefNode * > Def

NodeAddr< PhiNode * > Phi

NodeAddr< NodeBase * > Node

friend class Instruction

Iterator for Instructions in a `BasicBlock.

This is an optimization pass for GlobalISel generic memory operations.

DenseMap< BasicBlock *, SmallVector< std::pair< VNType, Instruction * >, 2 > > InValuesType

Definition GVNHoist.cpp:153

@ InvalidVN

Definition GVNHoist.cpp:158

void stable_sort(R &&Range)

SmallVector< HoistingPointInfo, 4 > HoistingPointList

Definition GVNHoist.cpp:120

bool all_of(R &&range, UnaryPredicate P)

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

auto size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)

Get the size of a range.

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< T > make_range(T x, T y)

Convenience function for iterating over sub-ranges.

SmallVectorImpl< Instruction * > SmallVecImplInsn

Definition GVNHoist.cpp:114

SmallVector< Instruction *, 4 > SmallVecInsn

Definition GVNHoist.cpp:113

const Value * getPointerOperand(const Value *V)

A helper function that returns the pointer operand of a load, store or GEP instruction.

SmallVectorImpl< CHIArg >::iterator CHIIt

Definition GVNHoist.cpp:150

DenseMap< VNType, SmallVector< Instruction *, 4 > > VNtoInsns

Definition GVNHoist.cpp:125

auto reverse(ContainerTy &&C)

std::pair< unsigned, uintptr_t > VNType

Definition GVNHoist.cpp:123

IDFCalculator< true > ReverseIDFCalculator

void sort(IteratorTy Start, IteratorTy End)

LLVM_ABI raw_ostream & dbgs()

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

std::pair< BasicBlock *, SmallVecInsn > HoistingPointInfo

Definition GVNHoist.cpp:118

idf_iterator< T > idf_end(const T &G)

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

LLVM_ABI void combineMetadataForCSE(Instruction *K, const Instruction *J, bool DoesKMove)

Combine the metadata of two instructions so that K can replace J.

LLVM_ABI bool VerifyMemorySSA

Enables verification of MemorySSA.

DWARFExpression::Operation Op

idf_iterator< T > idf_begin(const T &G)

DenseMap< BasicBlock *, SmallVector< CHIArg, 2 > > OutValuesType

Definition GVNHoist.cpp:152

LLVM_ABI bool isGuaranteedToTransferExecutionToSuccessor(const Instruction *I)

Return true if this function can prove that the instruction I will always transfer execution to one o...

decltype(auto) cast(const From &Val)

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

auto find_if(R &&Range, UnaryPredicate P)

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

iterator_range< CHIIt > CHIArgs

Definition GVNHoist.cpp:151

auto predecessors(const MachineBasicBlock *BB)

bool is_contained(R &&Range, const E &Element)

Returns true if Element is found in Range.

iterator_range< df_iterator< T > > depth_first(const T &G)

AnalysisManager< Function > FunctionAnalysisManager

Convenience typedef for the Function analysis manager.

AAResults AliasAnalysis

Temporary typedef for legacy code that uses a generic AliasAnalysis pointer or reference.

DenseMap< const BasicBlock *, bool > BBSideEffectsSet

Definition GVNHoist.cpp:112

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

Definition GVNHoist.cpp:137

bool operator!=(const CHIArg &A) const

Definition GVNHoist.cpp:147

BasicBlock * Dest

Definition GVNHoist.cpp:141

Instruction * I

Definition GVNHoist.cpp:144

bool operator==(const CHIArg &A) const

Definition GVNHoist.cpp:146

VNType VN

Definition GVNHoist.cpp:138

LLVM_ABI PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)

Run the pass over the function.

Definition GVNHoist.cpp:1201