ControlHeightReduction.cpp Source File (original) (raw)

41#include

42#include

43#include

45using namespace llvm;

47#define DEBUG_TYPE "chr"

49#define CHR_DEBUG(X) LLVM_DEBUG(X)

52 cl::desc("Disable CHR for all functions"));

55 cl::desc("Apply CHR for all functions"));

59 cl::desc("CHR considers a branch bias greater than this ratio as biased"));

63 cl::desc("CHR merges a group of N branches/selects where N >= this value"));

67 cl::desc("Specify file to retrieve the list of modules to apply CHR to"));

71 cl::desc("Specify file to retrieve the list of functions to apply CHR to"));

75 cl::desc("Max number of duplications by CHR for a region"));

83 if (!FileOrErr) {

84 errs() << "Error: Couldn't read the chr-module-list file " << CHRModuleList << "\n";

85 std::exit(1);

86 }

87 StringRef Buf = FileOrErr->get()->getBuffer();

89 Buf.split(Lines, '\n');

91 Line = Line.trim();

92 if (!Line.empty())

94 }

95 }

98 if (!FileOrErr) {

99 errs() << "Error: Couldn't read the chr-function-list file " << CHRFunctionList << "\n";

100 std::exit(1);

101 }

102 StringRef Buf = FileOrErr->get()->getBuffer();

104 Buf.split(Lines, '\n');

106 Line = Line.trim();

107 if (!Line.empty())

109 }

110 }

111}

112

113namespace {

114

115struct CHRStats {

116 CHRStats() = default;

117 void print(raw_ostream &OS) const {

118 OS << "CHRStats: NumBranches " << NumBranches

119 << " NumBranchesDelta " << NumBranchesDelta

120 << " WeightedNumBranchesDelta " << WeightedNumBranchesDelta;

121 }

122

123 uint64_t NumBranches = 0;

124

125

126 uint64_t NumBranchesDelta = 0;

127

128 uint64_t WeightedNumBranchesDelta = 0;

129};

130

131

133 RegInfo() = default;

134 RegInfo(Region *RegionIn) : R(RegionIn) {}

136 bool HasBranch = false;

138};

139

141

142

143

144

145class CHRScope {

146 public:

147 CHRScope(RegInfo RI) : BranchInsertPoint(nullptr) {

148 assert(RI.R && "Null RegionIn");

149 RegInfos.push_back(RI);

150 }

151

152 Region *getParentRegion() {

153 assert(RegInfos.size() > 0 && "Empty CHRScope");

154 Region *Parent = RegInfos[0].R->getParent();

155 assert(Parent && "Unexpected to call this on the top-level region");

156 return Parent;

157 }

158

160 assert(RegInfos.size() > 0 && "Empty CHRScope");

161 return RegInfos.front().R->getEntry();

162 }

163

165 assert(RegInfos.size() > 0 && "Empty CHRScope");

166 return RegInfos.back().R->getExit();

167 }

168

169 bool appendable(CHRScope *Next) {

170

171

172

174 if (getExitBlock() != NextEntry)

175

176 return false;

177 Region *LastRegion = RegInfos.back().R;

178 for (BasicBlock *Pred : predecessors(NextEntry))

179 if (!LastRegion->contains(Pred))

180

181

182 return false;

183 return true;

184 }

185

187 assert(RegInfos.size() > 0 && "Empty CHRScope");

188 assert(Next->RegInfos.size() > 0 && "Empty CHRScope");

189 assert(getParentRegion() == Next->getParentRegion() &&

190 "Must be siblings");

191 assert(getExitBlock() == Next->getEntryBlock() &&

192 "Must be adjacent");

193 RegInfos.append(Next->RegInfos.begin(), Next->RegInfos.end());

194 Subs.append(Next->Subs.begin(), Next->Subs.end());

195 }

196

197 void addSub(CHRScope *SubIn) {

198#ifndef NDEBUG

199 bool IsChild = false;

200 for (RegInfo &RI : RegInfos)

201 if (RI.R == SubIn->getParentRegion()) {

202 IsChild = true;

203 break;

204 }

205 assert(IsChild && "Must be a child");

206#endif

207 Subs.push_back(SubIn);

208 }

209

210

211

212 CHRScope *split(Region *Boundary) {

213 assert(Boundary && "Boundary null");

214 assert(RegInfos.begin()->R != Boundary &&

215 "Can't be split at beginning");

217 RegInfos, [&Boundary](const RegInfo &RI) { return Boundary == RI.R; });

218 if (BoundaryIt == RegInfos.end())

219 return nullptr;

221 DenseSet<Region *> TailRegionSet;

222 for (const RegInfo &RI : TailRegInfos)

223 TailRegionSet.insert(RI.R);

224

225 auto TailIt =

226 std::stable_partition(Subs.begin(), Subs.end(), [&](CHRScope *Sub) {

227 assert(Sub && "null Sub");

228 Region *Parent = Sub->getParentRegion();

229 if (TailRegionSet.count(Parent))

230 return false;

231

232 assert(llvm::any_of(

233 RegInfos,

234 [&Parent](const RegInfo &RI) { return Parent == RI.R; }) &&

235 "Must be in head");

236 return true;

237 });

239

240 assert(HoistStopMap.empty() && "MapHoistStops must be empty");

241 auto *Scope = new CHRScope(TailRegInfos, TailSubs);

242 RegInfos.erase(BoundaryIt, RegInfos.end());

243 Subs.erase(TailIt, Subs.end());

245 }

246

249 for (const RegInfo &RI : RegInfos)

250 if (RI.R->contains(Parent))

251 return true;

252 return false;

253 }

254

256

259

260

261

263

264

265

266

269

271

272

273

276

277

278

279 HoistStopMapTy HoistStopMap;

280

281 private:

283 : RegInfos(RegInfosIn), Subs(SubsIn), BranchInsertPoint(nullptr) {}

284};

285

286class CHR {

287 public:

288 CHR(Function &Fin, BlockFrequencyInfo &BFIin, DominatorTree &DTin,

289 ProfileSummaryInfo &PSIin, RegionInfo &RIin,

290 OptimizationRemarkEmitter &OREin)

291 : F(Fin), BFI(BFIin), DT(DTin), PSI(PSIin), RI(RIin), ORE(OREin) {}

292

293 ~CHR() {

294 for (CHRScope *Scope : Scopes) {

296 }

297 }

298

299 bool run();

300

301 private:

302

303

304

305 void findScopes(SmallVectorImpl<CHRScope *> &Output) {

306 Region *R = RI.getTopLevelRegion();

307 if (CHRScope *Scope = findScopes(R, nullptr, nullptr, Output)) {

309 }

310 }

311 CHRScope *findScopes(Region *R, Region *NextRegion, Region *ParentRegion,

312 SmallVectorImpl<CHRScope *> &Scopes);

313 CHRScope *findScope(Region *R);

314 void checkScopeHoistable(CHRScope *Scope);

315

316 void splitScopes(SmallVectorImpl<CHRScope *> &Input,

317 SmallVectorImpl<CHRScope *> &Output);

319 CHRScope *Outer,

320 DenseSet<Value *> *OuterConditionValues,

321 Instruction *OuterInsertPoint,

322 SmallVectorImpl<CHRScope *> &Output,

323 DenseSet<Instruction *> &Unhoistables);

324

325 void classifyBiasedScopes(SmallVectorImpl<CHRScope *> &Scopes);

326 void classifyBiasedScopes(CHRScope *Scope, CHRScope *OutermostScope);

327

328 void filterScopes(SmallVectorImpl<CHRScope *> &Input,

329 SmallVectorImpl<CHRScope *> &Output);

330

331 void setCHRRegions(SmallVectorImpl<CHRScope *> &Input,

332 SmallVectorImpl<CHRScope *> &Output);

333 void setCHRRegions(CHRScope *Scope, CHRScope *OutermostScope);

334

335 void sortScopes(SmallVectorImpl<CHRScope *> &Input,

336 SmallVectorImpl<CHRScope *> &Output);

337

338 void transformScopes(SmallVectorImpl<CHRScope *> &CHRScopes);

339 void transformScopes(CHRScope *Scope, DenseSet<PHINode *> &TrivialPHIs);

340 void cloneScopeBlocks(CHRScope *Scope,

341 BasicBlock *PreEntryBlock,

342 BasicBlock *ExitBlock,

343 Region *LastRegion,

345 BranchInst *createMergedBranch(BasicBlock *PreEntryBlock,

346 BasicBlock *EntryBlock,

347 BasicBlock *NewEntryBlock,

349 void fixupBranchesAndSelects(CHRScope *Scope, BasicBlock *PreEntryBlock,

350 BranchInst *MergedBR, uint64_t ProfileCount);

351 void fixupBranch(Region *R, CHRScope *Scope, IRBuilder<> &IRB,

352 Value *&MergedCondition, BranchProbability &CHRBranchBias);

353 void fixupSelect(SelectInst *SI, CHRScope *Scope, IRBuilder<> &IRB,

354 Value *&MergedCondition, BranchProbability &CHRBranchBias);

355 void addToMergedCondition(bool IsTrueBiased, Value *Cond,

356 Instruction *BranchOrSelect, CHRScope *Scope,

358 unsigned getRegionDuplicationCount(const Region *R) {

359 unsigned Count = 0;

360

361

362

363

364 while (R) {

365 Count += DuplicationCount[R];

366 R = R->getParent();

367 }

369 }

370

372 BlockFrequencyInfo &BFI;

373 DominatorTree &DT;

374 ProfileSummaryInfo &PSI;

375 RegionInfo &RI;

376 OptimizationRemarkEmitter &ORE;

377 CHRStats Stats;

378

379

380 DenseSet<Region *> TrueBiasedRegionsGlobal;

381

382 DenseSet<Region *> FalseBiasedRegionsGlobal;

383

384 DenseSet<SelectInst *> TrueBiasedSelectsGlobal;

385

386 DenseSet<SelectInst *> FalseBiasedSelectsGlobal;

387

388 DenseMap<Region *, BranchProbability> BranchBiasMap;

389

390 DenseMap<SelectInst *, BranchProbability> SelectBiasMap;

391

392 DenseSet<CHRScope *> Scopes;

393

394 DenseMap<const Region *, unsigned> DuplicationCount;

395};

396

397}

398

400 const CHRStats &Stats) {

402 return OS;

403}

404

405static inline

407 Scope.print(OS);

408 return OS;

409}

410

413 return false;

414

416 return true;

417

419 if (CHRModules.count(F.getParent()->getName()))

420 return true;

422 }

423

425}

426

428 CHRStats *Stats) {

431 (void)(FuncName);

432 (void)(ModuleName);

434 << FuncName);

439}

440

441void CHRScope::print(raw_ostream &OS) const {

442 assert(RegInfos.size() > 0 && "Empty CHRScope");

443 OS << "CHRScope[";

444 OS << RegInfos.size() << ", Regions[";

445 for (const RegInfo &RI : RegInfos) {

446 OS << RI.R->getNameStr();

447 if (RI.HasBranch)

448 OS << " B";

449 if (RI.Selects.size() > 0)

450 OS << " S" << RI.Selects.size();

451 OS << ", ";

452 }

453 if (RegInfos[0].R->getParent()) {

454 OS << "], Parent " << RegInfos[0].R->getParent()->getNameStr();

455 } else {

456

457 OS << "]";

458 }

459 OS << ", Subs[";

460 for (CHRScope *Sub : Subs) {

461 OS << *Sub << ", ";

462 }

463 OS << "]]";

464}

465

466

474

475

481

482

483

484

485

486

487static const std::set<Value *> &

490 auto It = Visited.find(V);

491 if (It != Visited.end()) {

492 return It->second;

493 }

494 std::set<Value *> Result;

496

497

498

500 Result.insert(I);

501 return Visited.insert(std::make_pair(V, std::move(Result))).first->second;

502 }

503

504 for (Value *Op : I->operands()) {

505 const std::set<Value *> &OpResult = getBaseValues(Op, DT, Visited);

506 Result.insert(OpResult.begin(), OpResult.end());

507 }

508 return Visited.insert(std::make_pair(V, std::move(Result))).first->second;

509 }

511 Result.insert(V);

512 }

513

514

515

516 return Visited.insert(std::make_pair(V, std::move(Result))).first->second;

517}

518

519

520

521

522

523static bool

528 assert(InsertPoint && "Null InsertPoint");

530 auto It = Visited.find(I);

531 if (It != Visited.end()) {

532 return It->second;

533 }

534 assert(DT.getNode(I->getParent()) && "DT must contain I's parent block");

536 if (Unhoistables.count(I)) {

537

538 Visited[I] = false;

539 return false;

540 }

542

543 if (HoistStops)

545 Visited[I] = true;

546 return true;

547 }

548

549

551

553 bool AllOpsHoisted = true;

554 for (Value *Op : I->operands()) {

555 if ( checkHoistValue (Op, InsertPoint, DT, Unhoistables, &OpsHoistStops,

556 Visited)) {

557 AllOpsHoisted = false;

558 break;

559 }

560 }

561 if (AllOpsHoisted) {

562 CHR_DEBUG(dbgs() << "checkHoistValue " << *I << "\n");

563 if (HoistStops)

565 Visited[I] = true;

566 return true;

567 }

568 }

569 Visited[I] = false;

570 return false;

571 }

572

573 return true;

574}

575

576

577

584 return false;

585 uint64_t SumWeight = TrueWeight + FalseWeight;

586

587 assert(SumWeight >= TrueWeight && SumWeight >= FalseWeight &&

588 "Overflow calculating branch probabilities.");

589

590

591 if (SumWeight == 0)

592 return false;

593

596 return true;

597}

598

603

604

605

606

607

608template <typename K, typename S, typename M>

611 M &BiasMap) {

613 if (TrueProb >= Threshold) {

614 TrueSet.insert(Key);

615 BiasMap[Key] = TrueProb;

616 return true;

617 } else if (FalseProb >= Threshold) {

618 FalseSet.insert(Key);

619 BiasMap[Key] = FalseProb;

620 return true;

621 }

622 return false;

623}

624

625

626

632 return false;

635 return false;

638 assert((IfThen == R->getExit() || IfElse == R->getExit()) &&

639 IfThen != IfElse &&

640 "Invariant from findScopes");

641 if (IfThen == R->getExit()) {

642

643

646 }

648 CHR_DEBUG(dbgs() << "ThenProb " << ThenProb << " ");

649 CHR_DEBUG(dbgs() << "ElseProb " << ElseProb << "\n");

650 return checkBias(R, ThenProb, ElseProb,

651 TrueBiasedRegionsGlobal, FalseBiasedRegionsGlobal,

652 BranchBiasMap);

653}

654

655

656

664 return false;

666 CHR_DEBUG(dbgs() << "TrueProb " << TrueProb << " ");

667 CHR_DEBUG(dbgs() << "FalseProb " << FalseProb << "\n");

668 return checkBias(SI, TrueProb, FalseProb,

669 TrueBiasedSelectsGlobal, FalseBiasedSelectsGlobal,

670 SelectBiasMap);

671}

672

673

674

675

679

680

683 if (SI->getParent() == EntryBB) {

684

685

686 HoistPoint = SI;

687 break;

688 }

689 }

690 assert(HoistPoint && "Null HoistPoint");

691#ifndef NDEBUG

692

693

696 if (SI->getParent() == EntryBB) {

697 EntryBlockSelectSet.insert(SI);

698 }

699 }

701 if (EntryBlockSelectSet.contains(&I)) {

702 assert(&I == HoistPoint &&

703 "HoistPoint must be the first one in Selects");

704 break;

705 }

706 }

707#endif

708 return HoistPoint;

709}

710

711

712CHRScope * CHR::findScope(Region *R) {

713 CHRScope *Result = nullptr;

716 assert(Entry && "Entry must not be null");

717 assert((Exit == nullptr) == (R->isTopLevelRegion()) &&

718 "Only top level region has a null exit");

719 if (Entry)

721 else

723 if (Exit)

725 else

727

728

729 bool EntryInSubregion = RI.getRegionFor(Entry) != R;

730 if (EntryInSubregion)

731 return nullptr;

732

734 if (R->contains(Pred))

735 return nullptr;

736

737

738 for (BasicBlock *BB : R->blocks()) {

739 if (BB->hasAddressTaken())

740 return nullptr;

741

742

743

744

745

746

747 for (Instruction &I : *BB)

749 if (II->getIntrinsicID() == Intrinsic::coro_id)

750 return nullptr;

751 }

752

753 if (Exit) {

754

755

756

757

759 if (BI)

760 CHR_DEBUG(dbgs() << "BI.isConditional " << BI->isConditional() << "\n");

761 else

763 if (BI && BI->isConditional()) {

764 BasicBlock *S0 = BI->getSuccessor(0);

768 if (S0 != S1 && (S0 == Exit || S1 == Exit)) {

769 RegInfo RI(R);

771 BI, R, TrueBiasedRegionsGlobal, FalseBiasedRegionsGlobal,

772 BranchBiasMap);

773 Result = new CHRScope(RI);

774 Scopes.insert(Result);

775 CHR_DEBUG(dbgs() << "Found a region with a branch\n");

776 ++Stats.NumBranches;

777 if (!RI.HasBranch) {

778 ORE.emit([&]() {

779 return OptimizationRemarkMissed(DEBUG_TYPE, "BranchNotBiased", BI)

780 << "Branch not biased";

781 });

782 }

783 }

784 }

785 }

786 {

787

788

789

790

791

792

793

794

795

796

797

798

800 for (RegionNode *E : R->elements()) {

801 if (E->isSubRegion())

802 continue;

803

804

806

807

808 for (Instruction &I : *BB) {

811 ++Stats.NumBranches;

812 }

813 }

814 }

815 if (Selects.size() > 0) {

816 auto AddSelects = [&](RegInfo &RI) {

817 for (auto *SI : Selects)

819 TrueBiasedSelectsGlobal,

820 FalseBiasedSelectsGlobal,

821 SelectBiasMap))

822 RI.Selects.push_back(SI);

823 else

824 ORE.emit([&]() {

825 return OptimizationRemarkMissed(DEBUG_TYPE, "SelectNotBiased", SI)

826 << "Select not biased";

827 });

828 };

829 if (!Result) {

830 CHR_DEBUG(dbgs() << "Found a select-only region\n");

831 RegInfo RI(R);

832 AddSelects(RI);

833 Result = new CHRScope(RI);

834 Scopes.insert(Result);

835 } else {

836 CHR_DEBUG(dbgs() << "Found select(s) in a region with a branch\n");

837 AddSelects(Result->RegInfos[0]);

838 }

839 }

840 }

841

842 if (Result) {

843 checkScopeHoistable(Result);

844 }

846}

847

848

849

850

851

852

853

854

855

856

857

858

859

860

861

862

863

864

865

866

867

868

869

870void CHR::checkScopeHoistable(CHRScope *Scope) {

871 RegInfo &RI = Scope->RegInfos[0];

874 auto *Branch = RI.HasBranch ?

877 if (RI.HasBranch || !Selects.empty()) {

879 CHR_DEBUG(dbgs() << "InsertPoint " << *InsertPoint << "\n");

880

881

882

883

884 DenseSet<Instruction *> Unhoistables(llvm::from_range, Selects);

885

886 for (auto it = Selects.begin(); it != Selects.end(); ) {

887 SelectInst *SI = *it;

888 if (SI == InsertPoint) {

889 ++it;

890 continue;

891 }

892 DenseMap<Instruction *, bool> Visited;

893 bool IsHoistable = checkHoistValue(SI->getCondition(), InsertPoint,

894 DT, Unhoistables, nullptr, Visited);

895 if (!IsHoistable) {

896 CHR_DEBUG(dbgs() << "Dropping select " << *SI << "\n");

897 ORE.emit([&]() {

898 return OptimizationRemarkMissed(DEBUG_TYPE,

899 "DropUnhoistableSelect", SI)

900 << "Dropped unhoistable select";

901 });

902 it = Selects.erase(it);

903

904

905 Unhoistables.erase(SI);

906 } else

907 ++it;

908 }

909

911 CHR_DEBUG(dbgs() << "InsertPoint " << *InsertPoint << "\n");

912 if (RI.HasBranch && InsertPoint != Branch) {

913 DenseMap<Instruction *, bool> Visited;

915 DT, Unhoistables, nullptr, Visited);

916 if (!IsHoistable) {

917

918

919

920 assert(InsertPoint != Branch && "Branch must not be the hoist point");

921 CHR_DEBUG(dbgs() << "Dropping selects in entry block \n");

923 for (SelectInst *SI : Selects) {

924 dbgs() << "SI " << *SI << "\n";

925 });

926 for (SelectInst *SI : Selects) {

927 ORE.emit([&]() {

928 return OptimizationRemarkMissed(DEBUG_TYPE,

929 "DropSelectUnhoistableBranch", SI)

930 << "Dropped select due to unhoistable branch";

931 });

932 }

934 return SI->getParent() == EntryBB;

935 });

936 Unhoistables.clear();

937 InsertPoint = Branch;

938 }

939 }

940 CHR_DEBUG(dbgs() << "InsertPoint " << *InsertPoint << "\n");

941#ifndef NDEBUG

942 if (RI.HasBranch) {

944 "Branch can't be already above the hoist point");

945 DenseMap<Instruction *, bool> Visited;

947 DT, Unhoistables, nullptr, Visited) &&

948 "checkHoistValue for branch");

949 }

950 for (auto *SI : Selects) {

952 "SI can't be already above the hoist point");

953 DenseMap<Instruction *, bool> Visited;

955 Unhoistables, nullptr, Visited) &&

956 "checkHoistValue for selects");

957 }

959 if (RI.HasBranch) {

961 }

962 for (auto *SI : Selects) {

964 }

965#endif

966 }

967}

968

969

970CHRScope * CHR::findScopes(Region *R, Region *NextRegion, Region *ParentRegion,

971 SmallVectorImpl<CHRScope *> &Scopes) {

972 CHR_DEBUG(dbgs() << "findScopes " << R->getNameStr() << "\n");

973 CHRScope *Result = findScope(R);

974

975 CHRScope *ConsecutiveSubscope = nullptr;

977 for (auto It = R->begin(); It != R->end(); ++It) {

978 const std::unique_ptr &SubR = *It;

979 auto NextIt = std::next(It);

980 Region *NextSubR = NextIt != R->end() ? NextIt->get() : nullptr;

981 CHR_DEBUG(dbgs() << "Looking at subregion " << SubR.get()->getNameStr()

982 << "\n");

983 CHRScope *SubCHRScope = findScopes(SubR.get(), NextSubR, R, Scopes);

984 if (SubCHRScope) {

985 CHR_DEBUG(dbgs() << "Subregion Scope " << *SubCHRScope << "\n");

986 } else {

988 }

989 if (SubCHRScope) {

990 if (!ConsecutiveSubscope)

991 ConsecutiveSubscope = SubCHRScope;

992 else if (!ConsecutiveSubscope->appendable(SubCHRScope)) {

993 Subscopes.push_back(ConsecutiveSubscope);

994 ConsecutiveSubscope = SubCHRScope;

995 } else

996 ConsecutiveSubscope->append(SubCHRScope);

997 } else {

998 if (ConsecutiveSubscope) {

999 Subscopes.push_back(ConsecutiveSubscope);

1000 }

1001 ConsecutiveSubscope = nullptr;

1002 }

1003 }

1004 if (ConsecutiveSubscope) {

1005 Subscopes.push_back(ConsecutiveSubscope);

1006 }

1007 for (CHRScope *Sub : Subscopes) {

1008 if (Result) {

1009

1011 } else {

1012

1014 }

1015 }

1017}

1018

1021 if (RI.HasBranch) {

1022 auto *BI = cast(RI.R->getEntry()->getTerminator());

1023 ConditionValues.insert(BI->getCondition());

1024 }

1026 ConditionValues.insert(SI->getCondition());

1027 }

1028 return ConditionValues;

1029}

1030

1031

1032

1033

1034

1035

1036

1037

1043 assert(InsertPoint && "Null InsertPoint");

1045 dbgs() << "shouldSplit " << *InsertPoint << " PrevConditionValues ";

1046 for (Value *V : PrevConditionValues) {

1047 dbgs() << *V << ", ";

1048 }

1049 dbgs() << " ConditionValues ";

1050 for (Value *V : ConditionValues) {

1051 dbgs() << *V << ", ";

1052 }

1053 dbgs() << "\n");

1054

1055 for (Value *V : ConditionValues) {

1057 if ( checkHoistValue (V, InsertPoint, DT, Unhoistables, nullptr, Visited)) {

1058 CHR_DEBUG(dbgs() << "Split. checkHoistValue false " << *V << "\n");

1059 return true;

1060 }

1061 }

1062

1063

1064

1065 if (!PrevConditionValues.empty() && !ConditionValues.empty()) {

1066

1067 std::set<Value *> PrevBases, Bases;

1069 for (Value *V : PrevConditionValues) {

1070 const std::set<Value *> &BaseValues = getBaseValues(V, DT, Visited);

1071 PrevBases.insert(BaseValues.begin(), BaseValues.end());

1072 }

1073 for (Value *V : ConditionValues) {

1074 const std::set<Value *> &BaseValues = getBaseValues(V, DT, Visited);

1075 Bases.insert(BaseValues.begin(), BaseValues.end());

1076 }

1078 dbgs() << "PrevBases ";

1079 for (Value *V : PrevBases) {

1080 dbgs() << *V << ", ";

1081 }

1082 dbgs() << " Bases ";

1083 for (Value *V : Bases) {

1084 dbgs() << *V << ", ";

1085 }

1086 dbgs() << "\n");

1087 std::vector<Value *> Intersection;

1088 std::set_intersection(PrevBases.begin(), PrevBases.end(), Bases.begin(),

1089 Bases.end(), std::back_inserter(Intersection));

1090 if (Intersection.empty()) {

1091

1092 CHR_DEBUG(dbgs() << "Split. Intersection empty\n");

1093 return true;

1094 }

1095 }

1097 return false;

1098}

1099

1102 for (RegInfo &RI : Scope->RegInfos)

1104 for (CHRScope *Sub : Scope->Subs)

1106}

1107

1108void CHR::splitScopes(SmallVectorImpl<CHRScope *> &Input,

1109 SmallVectorImpl<CHRScope *> &Output) {

1110 for (CHRScope *Scope : Input) {

1112 "BranchInsertPoint must not be set");

1113 DenseSet<Instruction *> Unhoistables;

1115 splitScope(Scope, nullptr, nullptr, nullptr, Output, Unhoistables);

1116 }

1117#ifndef NDEBUG

1118 for (CHRScope *Scope : Output) {

1119 assert(Scope->BranchInsertPoint && "BranchInsertPoint must be set");

1120 }

1121#endif

1122}

1123

1125 CHRScope *Scope,

1126 CHRScope *Outer,

1127 DenseSet<Value *> *OuterConditionValues,

1128 Instruction *OuterInsertPoint,

1129 SmallVectorImpl<CHRScope *> &Output,

1130 DenseSet<Instruction *> &Unhoistables) {

1131 if (Outer) {

1132 assert(OuterConditionValues && "Null OuterConditionValues");

1133 assert(OuterInsertPoint && "Null OuterInsertPoint");

1134 }

1135 bool PrevSplitFromOuter = true;

1136 DenseSet<Value *> PrevConditionValues;

1141 SmallVector<Instruction *, 8> SplitsInsertPoints;

1143 for (RegInfo &RI : RegInfos) {

1147 dbgs() << "ConditionValues ";

1148 for (Value *V : ConditionValues) {

1149 dbgs() << *V << ", ";

1150 }

1151 dbgs() << "\n");

1152 if (RI.R == RegInfos[0].R) {

1153

1154 if (Outer) {

1155 CHR_DEBUG(dbgs() << "Outer " << *Outer << "\n");

1156 CHR_DEBUG(dbgs() << "Should split from outer at "

1157 << RI.R->getNameStr() << "\n");

1158 if (shouldSplit(OuterInsertPoint, *OuterConditionValues,

1159 ConditionValues, DT, Unhoistables)) {

1160 PrevConditionValues = ConditionValues;

1161 PrevInsertPoint = InsertPoint;

1162 ORE.emit([&]() {

1163 return OptimizationRemarkMissed(DEBUG_TYPE,

1164 "SplitScopeFromOuter",

1165 RI.R->getEntry()->getTerminator())

1166 << "Split scope from outer due to unhoistable branch/select "

1167 << "and/or lack of common condition values";

1168 });

1169 } else {

1170

1171

1172 PrevSplitFromOuter = false;

1173 PrevConditionValues = *OuterConditionValues;

1174 PrevConditionValues.insert_range(ConditionValues);

1175 PrevInsertPoint = OuterInsertPoint;

1176 }

1177 } else {

1179 PrevConditionValues = ConditionValues;

1180 PrevInsertPoint = InsertPoint;

1181 }

1182 } else {

1183 CHR_DEBUG(dbgs() << "Should split from prev at "

1184 << RI.R->getNameStr() << "\n");

1185 if (shouldSplit(PrevInsertPoint, PrevConditionValues, ConditionValues,

1186 DT, Unhoistables)) {

1187 CHRScope *Tail = Scope->split(RI.R);

1190 SplitsSplitFromOuter.push_back(PrevSplitFromOuter);

1191 SplitsConditionValues.push_back(PrevConditionValues);

1192 SplitsInsertPoints.push_back(PrevInsertPoint);

1194 PrevConditionValues = ConditionValues;

1195 PrevInsertPoint = InsertPoint;

1196 PrevSplitFromOuter = true;

1197 ORE.emit([&]() {

1198 return OptimizationRemarkMissed(DEBUG_TYPE,

1199 "SplitScopeFromPrev",

1200 RI.R->getEntry()->getTerminator())

1201 << "Split scope from previous due to unhoistable branch/select "

1202 << "and/or lack of common condition values";

1203 });

1204 } else {

1205

1206 PrevConditionValues.insert_range(ConditionValues);

1207 }

1208 }

1209 }

1211 SplitsSplitFromOuter.push_back(PrevSplitFromOuter);

1212 SplitsConditionValues.push_back(PrevConditionValues);

1213 assert(PrevInsertPoint && "Null PrevInsertPoint");

1214 SplitsInsertPoints.push_back(PrevInsertPoint);

1215 assert(Splits.size() == SplitsConditionValues.size() &&

1216 Splits.size() == SplitsSplitFromOuter.size() &&

1217 Splits.size() == SplitsInsertPoints.size() && "Mismatching sizes");

1218 for (size_t I = 0; I < Splits.size(); ++I) {

1219 CHRScope *Split = Splits[I];

1220 DenseSet<Value *> &SplitConditionValues = SplitsConditionValues[I];

1221 Instruction *SplitInsertPoint = SplitsInsertPoints[I];

1223 DenseSet<Instruction *> SplitUnhoistables;

1225 for (CHRScope *Sub : Split->Subs) {

1227 Sub, Split, &SplitConditionValues, SplitInsertPoint, Output,

1228 SplitUnhoistables);

1230 }

1231 Split->Subs = NewSubs;

1232 }

1234 for (size_t I = 0; I < Splits.size(); ++I) {

1235 CHRScope *Split = Splits[I];

1236 if (SplitsSplitFromOuter[I]) {

1237

1239 Split->BranchInsertPoint = SplitsInsertPoints[I];

1240 CHR_DEBUG(dbgs() << "BranchInsertPoint " << *SplitsInsertPoints[I]

1241 << "\n");

1242 } else {

1243

1244 Result.push_back(Split);

1245 }

1246 }

1247 if (!Outer)

1249 "If no outer (top-level), must return no nested ones");

1251}

1252

1253void CHR::classifyBiasedScopes(SmallVectorImpl<CHRScope *> &Scopes) {

1254 for (CHRScope *Scope : Scopes) {

1255 assert(Scope->TrueBiasedRegions.empty() && Scope->FalseBiasedRegions.empty() && "Empty");

1256 classifyBiasedScopes(Scope, Scope);

1258 dbgs() << "classifyBiasedScopes " << *Scope << "\n";

1259 dbgs() << "TrueBiasedRegions ";

1260 for (Region *R : Scope->TrueBiasedRegions) {

1261 dbgs() << R->getNameStr() << ", ";

1262 }

1263 dbgs() << "\n";

1264 dbgs() << "FalseBiasedRegions ";

1265 for (Region *R : Scope->FalseBiasedRegions) {

1266 dbgs() << R->getNameStr() << ", ";

1267 }

1268 dbgs() << "\n";

1269 dbgs() << "TrueBiasedSelects ";

1270 for (SelectInst *SI : Scope->TrueBiasedSelects) {

1271 dbgs() << *SI << ", ";

1272 }

1273 dbgs() << "\n";

1274 dbgs() << "FalseBiasedSelects ";

1275 for (SelectInst *SI : Scope->FalseBiasedSelects) {

1276 dbgs() << *SI << ", ";

1277 }

1278 dbgs() << "\n";);

1279 }

1280}

1281

1282void CHR::classifyBiasedScopes(CHRScope *Scope, CHRScope *OutermostScope) {

1283 for (RegInfo &RI : Scope->RegInfos) {

1284 if (RI.HasBranch) {

1286 if (TrueBiasedRegionsGlobal.contains(R))

1287 OutermostScope->TrueBiasedRegions.insert(R);

1288 else if (FalseBiasedRegionsGlobal.contains(R))

1289 OutermostScope->FalseBiasedRegions.insert(R);

1290 else

1292 }

1293 for (SelectInst *SI : RI.Selects) {

1294 if (TrueBiasedSelectsGlobal.contains(SI))

1295 OutermostScope->TrueBiasedSelects.insert(SI);

1296 else if (FalseBiasedSelectsGlobal.contains(SI))

1297 OutermostScope->FalseBiasedSelects.insert(SI);

1298 else

1300 }

1301 }

1302 for (CHRScope *Sub : Scope->Subs) {

1303 classifyBiasedScopes(Sub, OutermostScope);

1304 }

1305}

1306

1308 unsigned NumBiased = Scope->TrueBiasedRegions.size() +

1309 Scope->FalseBiasedRegions.size() +

1310 Scope->TrueBiasedSelects.size() +

1311 Scope->FalseBiasedSelects.size();

1313}

1314

1315void CHR::filterScopes(SmallVectorImpl<CHRScope *> &Input,

1316 SmallVectorImpl<CHRScope *> &Output) {

1317 for (CHRScope *Scope : Input) {

1318

1320 CHR_DEBUG(dbgs() << "Filtered out by biased branches truthy-regions "

1321 << Scope->TrueBiasedRegions.size()

1322 << " falsy-regions " << Scope->FalseBiasedRegions.size()

1323 << " true-selects " << Scope->TrueBiasedSelects.size()

1324 << " false-selects " << Scope->FalseBiasedSelects.size() << "\n");

1325 ORE.emit([&]() {

1326 return OptimizationRemarkMissed(

1328 "DropScopeWithOneBranchOrSelect",

1329 Scope->RegInfos[0].R->getEntry()->getTerminator())

1330 << "Drop scope with < "

1332 << " biased branch(es) or select(s)";

1333 });

1334 continue;

1335 }

1337 }

1338}

1339

1340void CHR::setCHRRegions(SmallVectorImpl<CHRScope *> &Input,

1341 SmallVectorImpl<CHRScope *> &Output) {

1342 for (CHRScope *Scope : Input) {

1343 assert(Scope->HoistStopMap.empty() && Scope->CHRRegions.empty() &&

1344 "Empty");

1345 setCHRRegions(Scope, Scope);

1348 dbgs() << "setCHRRegions HoistStopMap " << *Scope << "\n";

1349 for (auto pair : Scope->HoistStopMap) {

1350 Region *R = pair.first;

1351 dbgs() << "Region " << R->getNameStr() << "\n";

1352 for (Instruction *I : pair.second) {

1353 dbgs() << "HoistStop " << *I << "\n";

1354 }

1355 }

1356 dbgs() << "CHRRegions" << "\n";

1357 for (RegInfo &RI : Scope->CHRRegions) {

1358 dbgs() << RI.R->getNameStr() << "\n";

1359 });

1360 }

1361}

1362

1363void CHR::setCHRRegions(CHRScope *Scope, CHRScope *OutermostScope) {

1364 DenseSet<Instruction *> Unhoistables;

1365

1366

1367

1368 for (RegInfo &RI : Scope->RegInfos)

1370 Instruction *InsertPoint = OutermostScope->BranchInsertPoint;

1371 for (RegInfo &RI : Scope->RegInfos) {

1373 DenseSet<Instruction *> HoistStops;

1374 bool IsHoisted = false;

1375 if (RI.HasBranch) {

1376 assert((OutermostScope->TrueBiasedRegions.contains(R) ||

1377 OutermostScope->FalseBiasedRegions.contains(R)) &&

1378 "Must be truthy or falsy");

1380

1381 DenseMap<Instruction *, bool> Visited;

1382 bool IsHoistable = checkHoistValue(BI->getCondition(), InsertPoint, DT,

1383 Unhoistables, &HoistStops, Visited);

1384 assert(IsHoistable && "Must be hoistable");

1385 (void)(IsHoistable);

1386 IsHoisted = true;

1387 }

1388 for (SelectInst *SI : RI.Selects) {

1389 assert((OutermostScope->TrueBiasedSelects.contains(SI) ||

1390 OutermostScope->FalseBiasedSelects.contains(SI)) &&

1391 "Must be true or false biased");

1392

1393 DenseMap<Instruction *, bool> Visited;

1394 bool IsHoistable = checkHoistValue(SI->getCondition(), InsertPoint, DT,

1395 Unhoistables, &HoistStops, Visited);

1396 assert(IsHoistable && "Must be hoistable");

1397 (void)(IsHoistable);

1398 IsHoisted = true;

1399 }

1400 if (IsHoisted) {

1401 OutermostScope->CHRRegions.push_back(RI);

1402 OutermostScope->HoistStopMap[R] = HoistStops;

1403 }

1404 }

1405 for (CHRScope *Sub : Scope->Subs)

1406 setCHRRegions(Sub, OutermostScope);

1407}

1408

1410 return Scope1->RegInfos[0].R->getDepth() < Scope2->RegInfos[0].R->getDepth();

1411}

1412

1413void CHR::sortScopes(SmallVectorImpl<CHRScope *> &Input,

1414 SmallVectorImpl<CHRScope *> &Output) {

1418}

1419

1420

1421

1423 HoistStopMapTy &HoistStopMap,

1427 auto IT = HoistStopMap.find(R);

1428 assert(IT != HoistStopMap.end() && "Region must be in hoist stop map");

1431 if (I == HoistPoint)

1432 return;

1433 if (HoistStops.count(I))

1434 return;

1436 if (TrivialPHIs.count(PN))

1437

1438

1439

1440

1441 return;

1442 if (HoistedSet.count(I))

1443

1444 return;

1446 assert(DT.getNode(I->getParent()) && "DT must contain I's block");

1448 "DT must contain HoistPoint block");

1450

1451

1452

1453

1454

1455

1456

1457

1458 return;

1459 for (Value *Op : I->operands()) {

1460 hoistValue(Op, HoistPoint, R, HoistStopMap, HoistedSet, TrivialPHIs, DT);

1461 }

1465 }

1466}

1467

1468

1469

1474 for (const RegInfo &RI : Scope->CHRRegions) {

1476 bool IsTrueBiased = Scope->TrueBiasedRegions.count(R);

1477 bool IsFalseBiased = Scope->FalseBiasedRegions.count(R);

1478 if (RI.HasBranch && (IsTrueBiased || IsFalseBiased)) {

1479 auto *BI = cast(R->getEntry()->getTerminator());

1480 hoistValue(BI->getCondition(), HoistPoint, R, Scope->HoistStopMap,

1481 HoistedSet, TrivialPHIs, DT);

1482 }

1484 bool IsTrueBiased = Scope->TrueBiasedSelects.count(SI);

1485 bool IsFalseBiased = Scope->FalseBiasedSelects.count(SI);

1486 if (!(IsTrueBiased || IsFalseBiased))

1487 continue;

1488 hoistValue(SI->getCondition(), HoistPoint, R, Scope->HoistStopMap,

1489 HoistedSet, TrivialPHIs, DT);

1490 }

1491 }

1492}

1493

1494

1495

1498 CHRScope *Scope) {

1500 if (U == ExcludedUser)

1501 continue;

1503 continue;

1505 continue;

1506 return false;

1507 }

1509 if (U == ExcludedUser)

1510 continue;

1512 assert(BI->isConditional() && "Must be conditional");

1513 BI->swapSuccessors();

1514

1515

1516

1517

1518

1519 continue;

1520 }

1522

1523 SI->swapValues();

1524 SI->swapProfMetadata();

1525 if (Scope->TrueBiasedSelects.count(SI)) {

1526 assert(!Scope->FalseBiasedSelects.contains(SI) &&

1527 "Must not be already in");

1528 Scope->FalseBiasedSelects.insert(SI);

1529 } else if (Scope->FalseBiasedSelects.count(SI)) {

1530 assert(!Scope->TrueBiasedSelects.contains(SI) &&

1531 "Must not be already in");

1532 Scope->TrueBiasedSelects.insert(SI);

1533 }

1534 continue;

1535 }

1537 }

1539 return true;

1540}

1541

1542

1543

1544

1549 for (RegInfo &RI : Scope->RegInfos) {

1550 for (BasicBlock *BB : RI.R->blocks()) {

1551

1552 BlocksInScope.insert(BB);

1553 }

1554 }

1556 dbgs() << "Inserting redundant phis\n";

1557 for (BasicBlock *BB : BlocksInScope)

1558 dbgs() << "BlockInScope " << BB->getName() << "\n";

1559 });

1560 for (BasicBlock *BB : BlocksInScope) {

1563 for (User *U : I.users()) {

1565 if (!BlocksInScope.contains(UI->getParent()) &&

1566

1567 !(isa(UI) && UI->getParent() == ExitBlock)) {

1569 CHR_DEBUG(dbgs() << "Used outside scope by user " << *UI << "\n");

1570 Users.push_back(UI);

1571 } else if (UI->getParent() == EntryBlock && isa(UI)) {

1572

1573

1576 << "Used at entry block (for a back edge) by a phi user "

1577 << *UI << "\n");

1578 Users.push_back(UI);

1579 }

1580 }

1581 }

1582 if (Users.size() > 0) {

1583

1584

1585

1590 }

1591 TrivialPHIs.insert(PN);

1592 CHR_DEBUG(dbgs() << "Insert phi " << *PN << "\n");

1593 bool FoundLifetimeAnnotation = false;

1595

1596

1597

1598 if (UI->isLifetimeStartOrEnd()) {

1599 UI->eraseFromParent();

1600 FoundLifetimeAnnotation = true;

1601 continue;

1602 }

1603 for (unsigned J = 0, NumOps = UI->getNumOperands(); J < NumOps; ++J) {

1604 if (UI->getOperand(J) == &I) {

1605 UI->setOperand(J, PN);

1606 }

1607 }

1608 CHR_DEBUG(dbgs() << "Updated user " << *UI << "\n");

1609 }

1610

1611 if (FoundLifetimeAnnotation) {

1614 if (UI->isLifetimeStartOrEnd())

1615 UI->eraseFromParent();

1616 }

1617 }

1618 }

1619 }

1620 }

1621}

1622

1623

1624[[maybe_unused]] static void

1626#ifndef NDEBUG

1627 auto HasBiasedBranchOrSelect = [](RegInfo &RI, CHRScope *Scope) {

1628 if (Scope->TrueBiasedRegions.count(RI.R) ||

1629 Scope->FalseBiasedRegions.count(RI.R))

1630 return true;

1632 if (Scope->TrueBiasedSelects.count(SI) ||

1633 Scope->FalseBiasedSelects.count(SI))

1634 return true;

1635 return false;

1636 };

1637 for (RegInfo &RI : Scope->CHRRegions) {

1638 assert(HasBiasedBranchOrSelect(RI, Scope) &&

1639 "Must have biased branch or select");

1640 }

1641#endif

1642}

1643

1644

1645

1646[[maybe_unused]] static void

1649 CHR_DEBUG(dbgs() << "Biased regions condition values \n");

1650 for (RegInfo &RI : Scope->CHRRegions) {

1652 bool IsTrueBiased = Scope->TrueBiasedRegions.count(R);

1653 bool IsFalseBiased = Scope->FalseBiasedRegions.count(R);

1654 if (RI.HasBranch && (IsTrueBiased || IsFalseBiased)) {

1655 auto *BI = cast(R->getEntry()->getTerminator());

1656 Value *V = BI->getCondition();

1659 (void)(I);

1660 assert((I->getParent() == PreEntryBlock ||

1661 !Scope->contains(I)) &&

1662 "Must have been hoisted to PreEntryBlock or outside the scope");

1663 }

1664 }

1666 bool IsTrueBiased = Scope->TrueBiasedSelects.count(SI);

1667 bool IsFalseBiased = Scope->FalseBiasedSelects.count(SI);

1668 if (!(IsTrueBiased || IsFalseBiased))

1669 continue;

1670 Value *V = SI->getCondition();

1673 (void)(I);

1674 assert((I->getParent() == PreEntryBlock ||

1675 !Scope->contains(I)) &&

1676 "Must have been hoisted to PreEntryBlock or outside the scope");

1677 }

1678 }

1679 }

1680}

1681

1682void CHR::transformScopes(CHRScope *Scope, DenseSet<PHINode *> &TrivialPHIs) {

1683 CHR_DEBUG(dbgs() << "transformScopes " << *Scope << "\n");

1684

1685 assert(Scope->RegInfos.size() >= 1 && "Should have at least one Region");

1686

1687 for (RegInfo &RI : Scope->RegInfos) {

1689 unsigned Duplication = getRegionDuplicationCount(R);

1691 << "\n");

1694 << " for this region");

1695 ORE.emit([&]() {

1696 return OptimizationRemarkMissed(DEBUG_TYPE, "DupThresholdReached",

1697 R->getEntry()->getTerminator())

1698 << "Reached the duplication threshold for the region";

1699 });

1700 return;

1701 }

1702 }

1703 for (RegInfo &RI : Scope->RegInfos) {

1704 DuplicationCount[RI.R]++;

1705 }

1706

1707 Region *FirstRegion = Scope->RegInfos[0].R;

1709 Region *LastRegion = Scope->RegInfos[Scope->RegInfos.size() - 1].R;

1712

1714 for (Instruction &I : *EntryBlock) {

1716 if (AI->isStaticAlloca())

1718 }

1719 }

1720

1721

1722

1723

1724

1725

1726

1727

1728 CHR_DEBUG(dbgs() << "Splitting entry block " << EntryBlock->getName()

1729 << " at " << *Scope->BranchInsertPoint << "\n");

1733 "NewEntryBlock's only pred must be EntryBlock");

1735 BasicBlock *PreEntryBlock = EntryBlock;

1736

1737

1738 for (AllocaInst *AI : StaticAllocas)

1739 AI->moveBefore(EntryBlock->begin());

1740

1741 if (ExitBlock) {

1742

1743

1744

1745

1746

1747

1749 }

1750

1752

1753

1754

1755 cloneScopeBlocks(Scope, PreEntryBlock, ExitBlock, LastRegion, VMap);

1756

1757

1758

1759 BranchInst *MergedBr = createMergedBranch(PreEntryBlock, EntryBlock,

1760 NewEntryBlock, VMap);

1761

1762#ifndef NDEBUG

1764#endif

1765

1766

1768

1769#ifndef NDEBUG

1771#endif

1772

1773

1774

1775 fixupBranchesAndSelects(Scope, PreEntryBlock, MergedBr,

1777}

1778

1779

1780

1781

1782void CHR::cloneScopeBlocks(CHRScope *Scope,

1783 BasicBlock *PreEntryBlock,

1784 BasicBlock *ExitBlock,

1785 Region *LastRegion,

1787

1788

1789

1790

1791

1792 SmallVector<BasicBlock*, 8> NewBlocks;

1793 for (RegInfo &RI : Scope->RegInfos)

1794 for (BasicBlock *BB : RI.R->blocks()) {

1795

1796 assert(BB != PreEntryBlock && "Don't copy the preetntry block");

1799 VMap[BB] = NewBB;

1800

1801

1802

1804 PN.removeIncomingValueIf([&](unsigned Idx) {

1806 });

1807 }

1808

1809

1810

1811 if (ExitBlock)

1812 F.splice(ExitBlock->getIterator(), &F, NewBlocks[0]->getIterator(),

1813 F.end());

1814

1815

1816 for (BasicBlock *NewBB : NewBlocks)

1817 for (Instruction &I : *NewBB)

1820

1821

1822

1823

1824 if (ExitBlock)

1825 for (PHINode &PN : ExitBlock->phis())

1826 for (unsigned I = 0, NumOps = PN.getNumIncomingValues(); I < NumOps;

1827 ++I) {

1828 BasicBlock *Pred = PN.getIncomingBlock(I);

1829 if (LastRegion->contains(Pred)) {

1830 Value *V = PN.getIncomingValue(I);

1831 auto It = VMap.find(V);

1832 if (It != VMap.end()) V = It->second;

1833 assert(VMap.find(Pred) != VMap.end() && "Pred must have been cloned");

1835 }

1836 }

1837}

1838

1839

1840

1841BranchInst *CHR::createMergedBranch(BasicBlock *PreEntryBlock,

1842 BasicBlock *EntryBlock,

1843 BasicBlock *NewEntryBlock,

1847 "SplitBlock did not work correctly!");

1849 "NewEntryBlock's only pred must be EntryBlock");

1850 assert(VMap.find(NewEntryBlock) != VMap.end() &&

1851 "NewEntryBlock must have been copied");

1854

1855

1859 NewBR->insertInto(PreEntryBlock, PreEntryBlock->end());

1860 assert(NewEntryBlock->getSinglePredecessor() == EntryBlock &&

1861 "NewEntryBlock's only pred must be EntryBlock");

1862 return NewBR;

1863}

1864

1865

1866

1867void CHR::fixupBranchesAndSelects(CHRScope *Scope,

1868 BasicBlock *PreEntryBlock,

1869 BranchInst *MergedBR,

1872 BranchProbability CHRBranchBias(1, 1);

1873 uint64_t NumCHRedBranches = 0;

1875 for (RegInfo &RI : Scope->CHRRegions) {

1877 if (RI.HasBranch) {

1878 fixupBranch(R, Scope, IRB, MergedCondition, CHRBranchBias);

1879 ++NumCHRedBranches;

1880 }

1881 for (SelectInst *SI : RI.Selects) {

1882 fixupSelect(SI, Scope, IRB, MergedCondition, CHRBranchBias);

1883 ++NumCHRedBranches;

1884 }

1885 }

1886 assert(NumCHRedBranches > 0);

1887 Stats.NumBranchesDelta += NumCHRedBranches - 1;

1888 Stats.WeightedNumBranchesDelta += (NumCHRedBranches - 1) * ProfileCount;

1889 ORE.emit([&]() {

1890 return OptimizationRemark(DEBUG_TYPE,

1891 "CHR",

1892

1894 << "Merged " << ore::NV("NumCHRedBranches", NumCHRedBranches)

1895 << " branches or selects";

1896 });

1898 uint32_t Weights[] = {

1899 static_cast<uint32_t>(CHRBranchBias.scale(1000)),

1900 static_cast<uint32_t>(CHRBranchBias.getCompl().scale(1000)),

1901 };

1903 CHR_DEBUG(dbgs() << "CHR branch bias " << Weights[0] << ":" << Weights[1]

1904 << "\n");

1905}

1906

1907

1908

1909void CHR::fixupBranch(Region *R, CHRScope *Scope,

1911 Value *&MergedCondition,

1912 BranchProbability &CHRBranchBias) {

1913 bool IsTrueBiased = Scope->TrueBiasedRegions.count(R);

1914 assert((IsTrueBiased || Scope->FalseBiasedRegions.count(R)) &&

1915 "Must be truthy or falsy");

1917 assert(BranchBiasMap.contains(R) && "Must be in the bias map");

1918 BranchProbability Bias = BranchBiasMap[R];

1920

1921 if (CHRBranchBias > Bias)

1922 CHRBranchBias = Bias;

1923 BasicBlock *IfThen = BI->getSuccessor(1);

1924 BasicBlock *IfElse = BI->getSuccessor(0);

1925 BasicBlock *RegionExitBlock = R->getExit();

1926 assert(RegionExitBlock && "Null ExitBlock");

1927 assert((IfThen == RegionExitBlock || IfElse == RegionExitBlock) &&

1928 IfThen != IfElse && "Invariant from findScopes");

1929 if (IfThen == RegionExitBlock) {

1930

1931

1933 }

1935 << " IfElse " << IfElse->getName() << "\n");

1936 Value *Cond = BI->getCondition();

1937 BasicBlock *HotTarget = IsTrueBiased ? IfThen : IfElse;

1938 bool ConditionTrue = HotTarget == BI->getSuccessor(0);

1939 addToMergedCondition(ConditionTrue, Cond, BI, Scope, IRB,

1940 MergedCondition);

1941

1942 assert(ConditionTrue == (HotTarget == BI->getSuccessor(0)) &&

1943 "The successor shouldn't change");

1944 Value *NewCondition = ConditionTrue ?

1947 BI->setCondition(NewCondition);

1948}

1949

1950

1951

1952void CHR::fixupSelect(SelectInst *SI, CHRScope *Scope,

1954 Value *&MergedCondition,

1955 BranchProbability &CHRBranchBias) {

1956 bool IsTrueBiased = Scope->TrueBiasedSelects.count(SI);

1957 assert((IsTrueBiased ||

1958 Scope->FalseBiasedSelects.count(SI)) && "Must be biased");

1959 assert(SelectBiasMap.contains(SI) && "Must be in the bias map");

1960 BranchProbability Bias = SelectBiasMap[SI];

1962

1963 if (CHRBranchBias > Bias)

1964 CHRBranchBias = Bias;

1966 addToMergedCondition(IsTrueBiased, Cond, SI, Scope, IRB,

1967 MergedCondition);

1968 Value *NewCondition = IsTrueBiased ?

1971 SI->setCondition(NewCondition);

1972}

1973

1974

1975

1976void CHR::addToMergedCondition(bool IsTrueBiased, Value *Cond,

1977 Instruction *BranchOrSelect, CHRScope *Scope,

1979 if (!IsTrueBiased) {

1980

1981

1982

1984 if (!ICmp ||

1987 }

1988

1989

1992

1993

1997}

1998

1999void CHR::transformScopes(SmallVectorImpl<CHRScope *> &CHRScopes) {

2000 unsigned I = 0;

2001 DenseSet<PHINode *> TrivialPHIs;

2002 for (CHRScope *Scope : CHRScopes) {

2003 transformScopes(Scope, TrivialPHIs);

2005 std::ostringstream oss;

2006 oss << " after transformScopes " << I++;

2007 dumpIR(F, oss.str().c_str(), nullptr));

2008 (void)I;

2009 }

2010}

2011

2013 const char *Label) {

2014 dbgs() << Label << " " << Scopes.size() << "\n";

2015 for (CHRScope *Scope : Scopes) {

2016 dbgs() << *Scope << "\n";

2017 }

2018}

2019

2020bool CHR::run() {

2022 return false;

2023

2025

2027 {

2029 dbgs() << "RegionInfo:\n";

2030 RI.print(dbgs()));

2031

2032

2033

2035 findScopes(AllScopes);

2037

2038

2039

2040

2041

2042

2044 splitScopes(AllScopes, SplitScopes);

2046

2047

2048

2049 classifyBiasedScopes(SplitScopes);

2050 CHR_DEBUG(dbgs() << "Set per-scope bias " << SplitScopes.size() << "\n");

2051

2052

2053

2055 filterScopes(SplitScopes, FilteredScopes);

2057

2058

2060 setCHRRegions(FilteredScopes, SetScopes);

2062

2063

2064

2065

2067 sortScopes(SetScopes, SortedScopes);

2069

2071 dbgs() << "RegionInfo:\n";

2072 RI.print(dbgs()));

2073

2074

2075 if (!SortedScopes.empty()) {

2076 transformScopes(SortedScopes);

2078 }

2079 }

2080

2083 ORE.emit([&]() {

2084 return OptimizationRemark(DEBUG_TYPE, "Stats", &F)

2085 << ore::NV("Function", &F) << " "

2086 << "Reduced the number of branches in hot paths by "

2087 << ore::NV("NumBranchesDelta", Stats.NumBranchesDelta)

2088 << " (static) and "

2089 << ore::NV("WeightedNumBranchesDelta", Stats.WeightedNumBranchesDelta)

2090 << " (weighted by PGO count)";

2091 });

2092 }

2093

2095}

2096

2100

2106

2107 if (!PPSI || !PPSI->hasProfileSummary())

2109 auto &PSI = *PPSI;

2114 bool Changed = CHR(F, BFI, DT, PSI, RI, ORE).run();

2118}

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

static cl::opt< ITMode > IT(cl::desc("IT block support"), cl::Hidden, cl::init(DefaultIT), cl::values(clEnumValN(DefaultIT, "arm-default-it", "Generate any type of IT block"), clEnumValN(RestrictedIT, "arm-restrict-it", "Disallow complex IT blocks")))

static uint64_t scale(uint64_t Num, uint32_t N, uint32_t D)

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

static void insertTrivialPHIs(CHRScope *Scope, BasicBlock *EntryBlock, BasicBlock *ExitBlock, DenseSet< PHINode * > &TrivialPHIs)

Definition ControlHeightReduction.cpp:1545

static cl::opt< bool > DisableCHR("disable-chr", cl::init(false), cl::Hidden, cl::desc("Disable CHR for all functions"))

static StringSet CHRFunctions

Definition ControlHeightReduction.cpp:78

static bool CHRScopeSorter(CHRScope *Scope1, CHRScope *Scope2)

Definition ControlHeightReduction.cpp:1409

static bool checkHoistValue(Value *V, Instruction *InsertPoint, DominatorTree &DT, DenseSet< Instruction * > &Unhoistables, DenseSet< Instruction * > *HoistStops, DenseMap< Instruction *, bool > &Visited)

Definition ControlHeightReduction.cpp:524

static cl::opt< unsigned > CHRMergeThreshold("chr-merge-threshold", cl::init(2), cl::Hidden, cl::desc("CHR merges a group of N branches/selects where N >= this value"))

static bool isHoistable(Instruction *I, DominatorTree &DT)

Definition ControlHeightReduction.cpp:476

static cl::opt< unsigned > CHRDupThreshsold("chr-dup-threshold", cl::init(3), cl::Hidden, cl::desc("Max number of duplications by CHR for a region"))

static bool shouldSplit(Instruction *InsertPoint, DenseSet< Value * > &PrevConditionValues, DenseSet< Value * > &ConditionValues, DominatorTree &DT, DenseSet< Instruction * > &Unhoistables)

Definition ControlHeightReduction.cpp:1038

static bool checkBias(K *Key, BranchProbability TrueProb, BranchProbability FalseProb, S &TrueSet, S &FalseSet, M &BiasMap)

Definition ControlHeightReduction.cpp:609

static StringSet CHRModules

Definition ControlHeightReduction.cpp:77

static bool checkBiasedSelect(SelectInst *SI, Region *R, DenseSet< SelectInst * > &TrueBiasedSelectsGlobal, DenseSet< SelectInst * > &FalseBiasedSelectsGlobal, DenseMap< SelectInst *, BranchProbability > &SelectBiasMap)

Definition ControlHeightReduction.cpp:657

static void hoistValue(Value *V, Instruction *HoistPoint, Region *R, HoistStopMapTy &HoistStopMap, DenseSet< Instruction * > &HoistedSet, DenseSet< PHINode * > &TrivialPHIs, DominatorTree &DT)

Definition ControlHeightReduction.cpp:1422

static void assertCHRRegionsHaveBiasedBranchOrSelect(CHRScope *Scope)

Definition ControlHeightReduction.cpp:1625

static bool hasAtLeastTwoBiasedBranches(CHRScope *Scope)

Definition ControlHeightReduction.cpp:1307

static bool shouldApply(Function &F, ProfileSummaryInfo &PSI)

Definition ControlHeightReduction.cpp:411

#define CHR_DEBUG(X)

Definition ControlHeightReduction.cpp:49

static void dumpIR(Function &F, const char *Label, CHRStats *Stats)

Definition ControlHeightReduction.cpp:427

static void getSelectsInScope(CHRScope *Scope, DenseSet< Instruction * > &Output)

Definition ControlHeightReduction.cpp:1100

static void dumpScopes(SmallVectorImpl< CHRScope * > &Scopes, const char *Label)

Definition ControlHeightReduction.cpp:2012

static void hoistScopeConditions(CHRScope *Scope, Instruction *HoistPoint, DenseSet< PHINode * > &TrivialPHIs, DominatorTree &DT)

Definition ControlHeightReduction.cpp:1470

static bool isHoistableInstructionType(Instruction *I)

Definition ControlHeightReduction.cpp:467

static DenseSet< Value * > getCHRConditionValuesForRegion(RegInfo &RI)

Definition ControlHeightReduction.cpp:1019

static bool negateICmpIfUsedByBranchOrSelectOnly(ICmpInst *ICmp, Instruction *ExcludedUser, CHRScope *Scope)

Definition ControlHeightReduction.cpp:1496

static Instruction * getBranchInsertPoint(RegInfo &RI)

Definition ControlHeightReduction.cpp:676

static cl::opt< std::string > CHRModuleList("chr-module-list", cl::init(""), cl::Hidden, cl::desc("Specify file to retrieve the list of modules to apply CHR to"))

static void assertBranchOrSelectConditionHoisted(CHRScope *Scope, BasicBlock *PreEntryBlock)

Definition ControlHeightReduction.cpp:1647

static cl::opt< double > CHRBiasThreshold("chr-bias-threshold", cl::init(0.99), cl::Hidden, cl::desc("CHR considers a branch bias greater than this ratio as biased"))

static BranchProbability getCHRBiasThreshold()

Definition ControlHeightReduction.cpp:599

static cl::opt< std::string > CHRFunctionList("chr-function-list", cl::init(""), cl::Hidden, cl::desc("Specify file to retrieve the list of functions to apply CHR to"))

static cl::opt< bool > ForceCHR("force-chr", cl::init(false), cl::Hidden, cl::desc("Apply CHR for all functions"))

static bool checkBiasedBranch(BranchInst *BI, Region *R, DenseSet< Region * > &TrueBiasedRegionsGlobal, DenseSet< Region * > &FalseBiasedRegionsGlobal, DenseMap< Region *, BranchProbability > &BranchBiasMap)

Definition ControlHeightReduction.cpp:627

static const std::set< Value * > & getBaseValues(Value *V, DominatorTree &DT, DenseMap< Value *, std::set< Value * > > &Visited)

Definition ControlHeightReduction.cpp:488

static bool extractBranchProbabilities(Instruction *I, BranchProbability &TrueProb, BranchProbability &FalseProb)

Definition ControlHeightReduction.cpp:578

static void parseCHRFilterFiles()

Definition ControlHeightReduction.cpp:80

This file defines the DenseMap class.

This file defines the DenseSet and SmallDenseSet classes.

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

static Value * getCondition(Instruction *I)

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

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

This header defines various interfaces for pass management in LLVM.

iv Induction Variable Users

static Constant * getFalse(Type *Ty)

For a boolean type or a vector of boolean type, return false or a vector with every element false.

const size_t AbstractManglingParser< Derived, Alloc >::NumOps

block placement Basic Block Placement Stats

uint64_t IntrinsicInst * II

FunctionAnalysisManager FAM

This file contains the declarations for profiling metadata utility functions.

const SmallVectorImpl< MachineOperand > & Cond

static bool contains(SmallPtrSetImpl< ConstantExpr * > &Cache, ConstantExpr *Expr, Constant *C)

This file defines the SmallVector class.

StringSet - A set-like wrapper for the StringMap.

early Early Tail Duplication

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

LLVM Basic Block Representation.

iterator begin()

Instruction iterator methods.

iterator_range< const_phi_iterator > phis() const

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

LLVM_ABI const BasicBlock * getSinglePredecessor() const

Return the predecessor of this block if it has a single predecessor 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...

Analysis pass which computes BlockFrequencyInfo.

LLVM_ABI std::optional< uint64_t > getBlockProfileCount(const BasicBlock *BB, bool AllowSynthetic=false) const

Returns the estimated profile count of BB.

Conditional or Unconditional Branch instruction.

void setCondition(Value *V)

bool isConditional() const

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

BasicBlock * getSuccessor(unsigned i) const

bool isUnconditional() const

static LLVM_ABI BranchProbability getBranchProbability(uint64_t Numerator, uint64_t Denominator)

void setPredicate(Predicate P)

Set the predicate for this instruction to the specified value.

Predicate getInversePredicate() const

For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE,...

Predicate getPredicate() const

Return the predicate for this instruction.

static LLVM_ABI ConstantInt * getTrue(LLVMContext &Context)

ControlHeightReductionPass()

Definition ControlHeightReduction.cpp:2097

PreservedAnalyses run(Function &F, FunctionAnalysisManager &FAM)

Definition ControlHeightReduction.cpp:2101

iterator find(const_arg_type_t< KeyT > Val)

Implements a dense probed hash-table based set.

Analysis pass which computes a DominatorTree.

DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const

getNode - return the (Post)DominatorTree node for the specified basic block.

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

LLVM_ABI bool isReachableFromEntry(const Use &U) const

Provide an overload for a Use.

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

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

This instruction compares its operands according to the predicate given to the constructor.

Value * CreateFreeze(Value *V, const Twine &Name="")

Value * CreateLogicalAnd(Value *Cond1, Value *Cond2, const Twine &Name="", Instruction *MDFrom=nullptr)

Value * CreateXor(Value *LHS, Value *RHS, const Twine &Name="")

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 InstListType::iterator insertInto(BasicBlock *ParentBB, InstListType::iterator It)

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

static ErrorOr< std::unique_ptr< MemoryBuffer > > getFile(const Twine &Filename, bool IsText=false, bool RequiresNullTerminator=true, bool IsVolatile=false, std::optional< Align > Alignment=std::nullopt)

Open the specified file as a MemoryBuffer, returning a new MemoryBuffer if successful,...

void addIncoming(Value *V, BasicBlock *BB)

Add an incoming value to the end of the PHI list.

static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", InsertPosition InsertBefore=nullptr)

Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...

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.

An analysis pass based on the new PM to deliver ProfileSummaryInfo.

Analysis providing profile information.

bool isFunctionEntryHot(const FuncT *F) const

Returns true if F has hot function entry.

BlockT * getExit() const

Get the exit BasicBlock of the Region.

void replaceEntryRecursive(BlockT *NewEntry)

Recursively replace the entry basic block of the region.

bool contains(const BlockT *BB) const

Check if the region contains a BasicBlock.

BlockT * getEntry() const

Get the entry BasicBlock of the Region.

Analysis pass that exposes the RegionInfo for a function.

This class represents the LLVM 'select' instruction.

bool contains(const_arg_type key) const

Check if the SetVector contains the given key.

bool insert(const value_type &X)

Insert a new element into the SetVector.

A SetVector that performs no allocations if smaller than a certain size.

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

iterator erase(const_iterator CI)

void push_back(const T &Elt)

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

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

std::pair< StringRef, StringRef > split(char Separator) const

Split into two substrings around the first occurrence of a separator character.

StringSet - A wrapper for StringMap that provides set-like functionality.

void dropAllReferences()

Drop all references to operands.

iterator find(const KeyT &Val)

LLVM Value Representation.

iterator_range< user_iterator > users()

LLVM_ABI StringRef getName() const

Return a constant reference to the value's name.

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

void insert_range(Range &&R)

bool contains(const_arg_type_t< ValueT > V) const

Check if the set contains the given element.

size_type count(const_arg_type_t< ValueT > V) const

Return 1 if the specified key is in the set, 0 otherwise.

const ParentTy * getParent() const

self_iterator getIterator()

This class implements an extremely fast bulk output stream that can only output to a stream.

#define llvm_unreachable(msg)

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

@ Tail

Attemps to make calls as fast as possible while guaranteeing that tail call optimization can always b...

@ BasicBlock

Various leaf nodes.

initializer< Ty > init(const Ty &Val)

PointerTypeMap run(const Module &M)

Compute the PointerTypeMap for the module M.

Scope

Defines the scope in which this symbol should be visible: Default – Visible in the public interface o...

DiagnosticInfoOptimizationBase::Argument NV

Context & getContext() const

friend class Instruction

Iterator for Instructions in a `BasicBlock.

LLVM_ABI void append(SmallVectorImpl< char > &path, const Twine &a, const Twine &b="", const Twine &c="", const Twine &d="")

Append to path.

This is an optimization pass for GlobalISel generic memory operations.

FunctionAddr VTableAddr Value

void stable_sort(R &&Range)

Printable print(const GCNRegPressure &RP, const GCNSubtarget *ST=nullptr, unsigned DynamicVGPRBlockSize=0)

LLVM_ABI BasicBlock * CloneBasicBlock(const BasicBlock *BB, ValueToValueMapTy &VMap, const Twine &NameSuffix="", Function *F=nullptr, ClonedCodeInfo *CodeInfo=nullptr, bool MapAtoms=true)

Return a copy of the specified basic block, but without embedding the block into a particular functio...

LLVM_ABI void setExplicitlyUnknownBranchWeightsIfProfiled(Instruction &I, StringRef PassName, const Function *F=nullptr)

Like setExplicitlyUnknownBranchWeights(...), but only sets unknown branch weights in the new instruct...

decltype(auto) dyn_cast(const From &Val)

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

OuterAnalysisManagerProxy< ModuleAnalysisManager, Function > ModuleAnalysisManagerFunctionProxy

Provide the ModuleAnalysisManager to Function proxy.

constexpr from_range_t from_range

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

Wrapper function to append range R to container C.

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

auto pred_size(const MachineBasicBlock *BB)

LLVM_ABI bool isSafeToSpeculativelyExecute(const Instruction *I, const Instruction *CtxI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr, bool UseVariableInfo=true, bool IgnoreUBImplyingAttrs=true)

Return true if the instruction does not have any effects besides calculating the result and does not ...

LLVM_ABI void setBranchWeights(Instruction &I, ArrayRef< uint32_t > Weights, bool IsExpected, bool ElideAllZero=false)

Create a new branch_weights metadata node and add or overwrite a prof metadata reference to instructi...

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

FunctionAddr VTableAddr Count

Function::ProfileCount ProfileCount

iterator_range< SplittingIterator > split(StringRef Str, StringRef Separator)

Split the specified string over a separator and return a range-compatible iterable over its partition...

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_ATTRIBUTE_VISIBILITY_DEFAULT AnalysisKey InnerAnalysisManagerProxy< AnalysisManagerT, IRUnitT, ExtraArgTs... >::Key

LLVM_ABI raw_fd_ostream & errs()

This returns a reference to a raw_ostream for standard error.

IRBuilder(LLVMContext &, FolderTy, InserterTy, MDNode *, ArrayRef< OperandBundleDef >) -> IRBuilder< FolderTy, InserterTy >

@ Sub

Subtraction of integers.

FunctionAddr VTableAddr Next

void RemapInstruction(Instruction *I, ValueToValueMapTy &VM, RemapFlags Flags=RF_None, ValueMapTypeRemapper *TypeMapper=nullptr, ValueMaterializer *Materializer=nullptr, const MetadataPredicate *IdentityMD=nullptr)

Convert the instruction operands from referencing the current values into those specified by VM.

DWARFExpression::Operation Op

raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)

LLVM_ABI bool isGuaranteedNotToBeUndefOrPoison(const Value *V, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)

Return true if this function can prove that V does not have undef bits and is never poison.

ArrayRef(const T &OneElt) -> ArrayRef< T >

OutputIt copy(R &&Range, OutputIt Out)

ValueMap< const Value *, WeakTrackingVH > ValueToValueMapTy

LLVM_ABI bool extractBranchWeights(const MDNode *ProfileData, SmallVectorImpl< uint32_t > &Weights)

Extract branch weights from MD_prof metadata.

decltype(auto) cast(const From &Val)

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

LLVM_ABI BasicBlock * SplitBlock(BasicBlock *Old, BasicBlock::iterator SplitPt, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="", bool Before=false)

Split the specified block at the specified instruction.

auto find_if(R &&Range, UnaryPredicate P)

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

void erase_if(Container &C, UnaryPredicate P)

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

auto predecessors(const MachineBasicBlock *BB)

AnalysisManager< Function > FunctionAnalysisManager

Convenience typedef for the Function analysis manager.

void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)

Implement std::swap in terms of BitVector swap.