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;

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

119 << " NumBranchesDelta " << NumBranchesDelta

120 << " WeightedNumBranchesDelta " << WeightedNumBranchesDelta;

121 }

122

124

125

126 uint64_t NumBranchesDelta = 0;

127

128 uint64_t WeightedNumBranchesDelta = 0;

129};

130

131

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");

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

173 BasicBlock *NextEntry = Next->getEntryBlock();

174 if (getExitBlock() != NextEntry)

175

176 return false;

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

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

180

181

182 return false;

183 return true;

184 }

185

186 void append(CHRScope *Next) {

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;

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:

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

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,

313 CHRScope *findScope(Region *R);

314 void checkScopeHoistable(CHRScope *Scope);

315

319 CHRScope *Outer,

324

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

327

330

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

334

337

340 void cloneScopeBlocks(CHRScope *Scope,

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

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 }

368 return Count;

369 }

370

378

379

381

383

385

387

389

391

393

395};

396

397}

398

399static inline

401 const CHRStats &Stats) {

403 return OS;

404}

405

406static inline

408 Scope.print(OS);

409 return OS;

410}

411

414 return false;

415

417 return true;

418

421 return true;

423 }

424

426}

427

429 CHRStats *Stats) {

432 (void)(FuncName);

433 (void)(ModuleName);

435 << FuncName);

440}

441

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

444 OS << "CHRScope[";

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

446 for (const RegInfo &RI : RegInfos) {

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

448 if (RI.HasBranch)

449 OS << " B";

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

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

452 OS << ", ";

453 }

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

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

456 } else {

457

458 OS << "]";

459 }

460 OS << ", Subs[";

461 for (CHRScope *Sub : Subs) {

462 OS << *Sub << ", ";

463 }

464 OS << "]]";

465}

466

467

469 return isa(I) || isa(I) || isa(I) ||

470 isa(I) || isa(I) ||

471 isa(I) || isa(I) ||

472 isa(I) || isa(I) ||

473 isa(I);

474}

475

476

479 return false;

481}

482

483

484

485

486

487

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

491 auto It = Visited.find(V);

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

493 return It->second;

494 }

495 std::set<Value *> Result;

496 if (auto *I = dyn_cast(V)) {

497

498

499

501 Result.insert(I);

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

503 }

504

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

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

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

508 }

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

510 }

511 if (isa(V)) {

512 Result.insert(V);

513 }

514

515

516

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

518}

519

520

521

522

523

524static bool

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

530 if (auto *I = dyn_cast(V)) {

531 auto It = Visited.find(I);

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

533 return It->second;

534 }

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

537 if (Unhoistables.count(I)) {

538

539 Visited[I] = false;

540 return false;

541 }

543

544 if (HoistStops)

546 Visited[I] = true;

547 return true;

548 }

549

550

552

554 bool AllOpsHoisted = true;

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

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

557 Visited)) {

558 AllOpsHoisted = false;

559 break;

560 }

561 }

562 if (AllOpsHoisted) {

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

564 if (HoistStops)

565 HoistStops->insert(OpsHoistStops.begin(), OpsHoistStops.end());

566 Visited[I] = true;

567 return true;

568 }

569 }

570 Visited[I] = false;

571 return false;

572 }

573

574 return true;

575}

576

577

578

585 return false;

586 uint64_t SumWeight = TrueWeight + FalseWeight;

587

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

589 "Overflow calculating branch probabilities.");

590

591

592 if (SumWeight == 0)

593 return false;

594

597 return true;

598}

599

603}

604

605

606

607

608

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

612 M &BiasMap) {

614 if (TrueProb >= Threshold) {

615 TrueSet.insert(Key);

616 BiasMap[Key] = TrueProb;

617 return true;

618 } else if (FalseProb >= Threshold) {

619 FalseSet.insert(Key);

620 BiasMap[Key] = FalseProb;

621 return true;

622 }

623 return false;

624}

625

626

627

633 return false;

636 return false;

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

640 IfThen != IfElse &&

641 "Invariant from findScopes");

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

643

644

647 }

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

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

651 return checkBias(R, ThenProb, ElseProb,

652 TrueBiasedRegionsGlobal, FalseBiasedRegionsGlobal,

653 BranchBiasMap);

654}

655

656

657

665 return false;

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

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

669 return checkBias(SI, TrueProb, FalseProb,

670 TrueBiasedSelectsGlobal, FalseBiasedSelectsGlobal,

671 SelectBiasMap);

672}

673

674

675

676

680

681

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

685

686

687 HoistPoint = SI;

688 break;

689 }

690 }

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

692#ifndef NDEBUG

693

694

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

698 EntryBlockSelectSet.insert(SI);

699 }

700 }

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

703 assert(&I == HoistPoint &&

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

705 break;

706 }

707 }

708#endif

709 return HoistPoint;

710}

711

712

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

714 CHRScope *Result = nullptr;

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

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

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

720 if (Entry)

722 else

724 if (Exit)

726 else

728

729

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

731 if (EntryInSubregion)

732 return nullptr;

733

735 if (R->contains(Pred))

736 return nullptr;

737

738

740 if (BB->hasAddressTaken())

741 return nullptr;

742

743

744

745

746

747

749 if (auto *II = dyn_cast(&I))

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

751 return nullptr;

752 }

753

754 if (Exit) {

755

756

757

758

759 auto *BI = dyn_cast(Entry->getTerminator());

760 if (BI)

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

762 else

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

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

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

772 BI, R, TrueBiasedRegionsGlobal, FalseBiasedRegionsGlobal,

773 BranchBiasMap);

774 Result = new CHRScope(RI);

775 Scopes.insert(Result);

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

777 ++Stats.NumBranches;

778 if (!RI.HasBranch) {

779 ORE.emit([&]() {

781 << "Branch not biased";

782 });

783 }

784 }

785 }

786 }

787 {

788

789

790

791

792

793

794

795

796

797

798

799

802 if (E->isSubRegion())

803 continue;

804

805

807

808

810 if (auto *SI = dyn_cast(&I)) {

812 ++Stats.NumBranches;

813 }

814 }

815 }

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

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

818 for (auto *SI : Selects)

820 TrueBiasedSelectsGlobal,

821 FalseBiasedSelectsGlobal,

822 SelectBiasMap))

823 RI.Selects.push_back(SI);

824 else

825 ORE.emit([&]() {

827 << "Select not biased";

828 });

829 };

830 if (!Result) {

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

833 AddSelects(RI);

834 Result = new CHRScope(RI);

835 Scopes.insert(Result);

836 } else {

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

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

839 }

840 }

841 }

842

843 if (Result) {

844 checkScopeHoistable(Result);

845 }

847}

848

849

850

851

852

853

854

855

856

857

858

859

860

861

862

863

864

865

866

867

868

869

870

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

875 auto *Branch = RI.HasBranch ?

876 cast(EntryBB->getTerminator()) : nullptr;

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

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

881

882

883

885

887 Unhoistables.insert(SI);

888 }

889

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

892 if (SI == InsertPoint) {

893 ++it;

894 continue;

895 }

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

898 DT, Unhoistables, nullptr, Visited);

899 if (!IsHoistable) {

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

901 ORE.emit([&]() {

903 "DropUnhoistableSelect", SI)

904 << "Dropped unhoistable select";

905 });

906 it = Selects.erase(it);

907

908

909 Unhoistables.erase(SI);

910 } else

911 ++it;

912 }

913

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

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

919 DT, Unhoistables, nullptr, Visited);

920 if (!IsHoistable) {

921

922

923

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

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

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

929 });

931 ORE.emit([&]() {

933 "DropSelectUnhoistableBranch", SI)

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

935 });

936 }

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

939 });

940 Unhoistables.clear();

941 InsertPoint = Branch;

942 }

943 }

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

945#ifndef NDEBUG

946 if (RI.HasBranch) {

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

951 DT, Unhoistables, nullptr, Visited) &&

952 "checkHoistValue for branch");

953 }

954 for (auto *SI : Selects) {

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

959 Unhoistables, nullptr, Visited) &&

960 "checkHoistValue for selects");

961 }

963 if (RI.HasBranch) {

965 }

966 for (auto *SI : Selects) {

968 }

969#endif

970 }

971}

972

973

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

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

977 CHRScope *Result = findScope(R);

978

979 CHRScope *ConsecutiveSubscope = nullptr;

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

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

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

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

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

986 << "\n");

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

988 if (SubCHRScope) {

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

990 } else {

992 }

993 if (SubCHRScope) {

994 if (!ConsecutiveSubscope)

995 ConsecutiveSubscope = SubCHRScope;

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

997 Subscopes.push_back(ConsecutiveSubscope);

998 ConsecutiveSubscope = SubCHRScope;

999 } else

1000 ConsecutiveSubscope->append(SubCHRScope);

1001 } else {

1002 if (ConsecutiveSubscope) {

1003 Subscopes.push_back(ConsecutiveSubscope);

1004 }

1005 ConsecutiveSubscope = nullptr;

1006 }

1007 }

1008 if (ConsecutiveSubscope) {

1009 Subscopes.push_back(ConsecutiveSubscope);

1010 }

1011 for (CHRScope *Sub : Subscopes) {

1012 if (Result) {

1013

1014 Result->addSub(Sub);

1015 } else {

1016

1017 Scopes.push_back(Sub);

1018 }

1019 }

1021}

1022

1025 if (RI.HasBranch) {

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

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

1028 }

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

1031 }

1032 return ConditionValues;

1033}

1034

1035

1036

1037

1038

1039

1040

1041

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

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

1050 for (Value *V : PrevConditionValues) {

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

1052 }

1053 dbgs() << " ConditionValues ";

1054 for (Value *V : ConditionValues) {

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

1056 }

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

1058

1059 for (Value *V : ConditionValues) {

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

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

1063 return true;

1064 }

1065 }

1066

1067

1068

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

1070

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

1073 for (Value *V : PrevConditionValues) {

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

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

1076 }

1077 for (Value *V : ConditionValues) {

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

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

1080 }

1082 dbgs() << "PrevBases ";

1083 for (Value *V : PrevBases) {

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

1085 }

1086 dbgs() << " Bases ";

1087 for (Value *V : Bases) {

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

1089 }

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

1091 std::vector<Value *> Intersection;

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

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

1094 if (Intersection.empty()) {

1095

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

1097 return true;

1098 }

1099 }

1101 return false;

1102}

1103

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

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

1111}

1112

1115 for (CHRScope *Scope : Input) {

1117 "BranchInsertPoint must not be set");

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

1121 }

1122#ifndef NDEBUG

1123 for (CHRScope *Scope : Output) {

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

1125 }

1126#endif

1127}

1128

1130 CHRScope *Scope,

1131 CHRScope *Outer,

1136 if (Outer) {

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

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

1139 }

1140 bool PrevSplitFromOuter = true;

1148 for (RegInfo &RI : RegInfos) {

1152 dbgs() << "ConditionValues ";

1153 for (Value *V : ConditionValues) {

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

1155 }

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

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

1158

1159 if (Outer) {

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

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

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

1163 if (shouldSplit(OuterInsertPoint, *OuterConditionValues,

1164 ConditionValues, DT, Unhoistables)) {

1165 PrevConditionValues = ConditionValues;

1166 PrevInsertPoint = InsertPoint;

1167 ORE.emit([&]() {

1169 "SplitScopeFromOuter",

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

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

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

1173 });

1174 } else {

1175

1176

1177 PrevSplitFromOuter = false;

1178 PrevConditionValues = *OuterConditionValues;

1179 PrevConditionValues.insert(ConditionValues.begin(),

1180 ConditionValues.end());

1181 PrevInsertPoint = OuterInsertPoint;

1182 }

1183 } else {

1185 PrevConditionValues = ConditionValues;

1186 PrevInsertPoint = InsertPoint;

1187 }

1188 } else {

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

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

1191 if (shouldSplit(PrevInsertPoint, PrevConditionValues, ConditionValues,

1192 DT, Unhoistables)) {

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

1196 SplitsSplitFromOuter.push_back(PrevSplitFromOuter);

1197 SplitsConditionValues.push_back(PrevConditionValues);

1198 SplitsInsertPoints.push_back(PrevInsertPoint);

1200 PrevConditionValues = ConditionValues;

1201 PrevInsertPoint = InsertPoint;

1202 PrevSplitFromOuter = true;

1203 ORE.emit([&]() {

1205 "SplitScopeFromPrev",

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

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

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

1209 });

1210 } else {

1211

1212 PrevConditionValues.insert(ConditionValues.begin(), ConditionValues.end());

1213 }

1214 }

1215 }

1217 SplitsSplitFromOuter.push_back(PrevSplitFromOuter);

1218 SplitsConditionValues.push_back(PrevConditionValues);

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

1220 SplitsInsertPoints.push_back(PrevInsertPoint);

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

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

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

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

1225 CHRScope *Split = Splits[I];

1227 Instruction *SplitInsertPoint = SplitsInsertPoints[I];

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

1233 Sub, Split, &SplitConditionValues, SplitInsertPoint, Output,

1234 SplitUnhoistables);

1236 }

1237 Split->Subs = NewSubs;

1238 }

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

1241 CHRScope *Split = Splits[I];

1242 if (SplitsSplitFromOuter[I]) {

1243

1245 Split->BranchInsertPoint = SplitsInsertPoints[I];

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

1247 << "\n");

1248 } else {

1249

1250 Result.push_back(Split);

1251 }

1252 }

1253 if (!Outer)

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

1257}

1258

1260 for (CHRScope *Scope : Scopes) {

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

1262 classifyBiasedScopes(Scope, Scope);

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

1265 dbgs() << "TrueBiasedRegions ";

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

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

1268 }

1269 dbgs() << "\n";

1270 dbgs() << "FalseBiasedRegions ";

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

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

1273 }

1274 dbgs() << "\n";

1275 dbgs() << "TrueBiasedSelects ";

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

1278 }

1279 dbgs() << "\n";

1280 dbgs() << "FalseBiasedSelects ";

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

1283 }

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

1285 }

1286}

1287

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

1290 if (RI.HasBranch) {

1292 if (TrueBiasedRegionsGlobal.contains(R))

1293 OutermostScope->TrueBiasedRegions.insert(R);

1294 else if (FalseBiasedRegionsGlobal.contains(R))

1295 OutermostScope->FalseBiasedRegions.insert(R);

1296 else

1298 }

1300 if (TrueBiasedSelectsGlobal.contains(SI))

1301 OutermostScope->TrueBiasedSelects.insert(SI);

1302 else if (FalseBiasedSelectsGlobal.contains(SI))

1303 OutermostScope->FalseBiasedSelects.insert(SI);

1304 else

1306 }

1307 }

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

1309 classifyBiasedScopes(Sub, OutermostScope);

1310 }

1311}

1312

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

1315 Scope->FalseBiasedRegions.size() +

1316 Scope->TrueBiasedSelects.size() +

1317 Scope->FalseBiasedSelects.size();

1319}

1320

1323 for (CHRScope *Scope : Input) {

1324

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

1327 << Scope->TrueBiasedRegions.size()

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

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

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

1331 ORE.emit([&]() {

1334 "DropScopeWithOneBranchOrSelect",

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

1336 << "Drop scope with < "

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

1339 });

1340 continue;

1341 }

1343 }

1344}

1345

1348 for (CHRScope *Scope : Input) {

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

1350 "Empty");

1351 setCHRRegions(Scope, Scope);

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

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

1356 Region *R = pair.first;

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

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

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

1360 }

1361 }

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

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

1365 });

1366 }

1367}

1368

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

1371

1372

1373

1376 Unhoistables.insert(SI);

1377 }

1378 }

1379 Instruction *InsertPoint = OutermostScope->BranchInsertPoint;

1383 bool IsHoisted = false;

1384 if (RI.HasBranch) {

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

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

1387 "Must be truthy or falsy");

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

1389

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

1392 Unhoistables, &HoistStops, Visited);

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

1394 (void)(IsHoistable);

1395 IsHoisted = true;

1396 }

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

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

1400 "Must be true or false biased");

1401

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

1404 Unhoistables, &HoistStops, Visited);

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

1406 (void)(IsHoistable);

1407 IsHoisted = true;

1408 }

1409 if (IsHoisted) {

1410 OutermostScope->CHRRegions.push_back(RI);

1411 OutermostScope->HoistStopMap[R] = HoistStops;

1412 }

1413 }

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

1415 setCHRRegions(Sub, OutermostScope);

1416}

1417

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

1420}

1421

1427}

1428

1429

1430

1432 HoistStopMapTy &HoistStopMap,

1436 auto IT = HoistStopMap.find(R);

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

1439 if (auto *I = dyn_cast(V)) {

1440 if (I == HoistPoint)

1441 return;

1442 if (HoistStops.count(I))

1443 return;

1444 if (auto *PN = dyn_cast(I))

1445 if (TrivialPHIs.count(PN))

1446

1447

1448

1449

1450 return;

1451 if (HoistedSet.count(I))

1452

1453 return;

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

1457 "DT must contain HoistPoint block");

1459

1460

1461

1462

1463

1464

1465

1466

1467 return;

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

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

1470 }

1471 I->moveBefore(HoistPoint);

1474 }

1475}

1476

1477

1478

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

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

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

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

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

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

1490 HoistedSet, TrivialPHIs, DT);

1491 }

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

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

1495 if (!(IsTrueBiased || IsFalseBiased))

1496 continue;

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

1498 HoistedSet, TrivialPHIs, DT);

1499 }

1500 }

1501}

1502

1503

1504

1507 CHRScope *Scope) {

1509 if (U == ExcludedUser)

1510 continue;

1511 if (isa(U) && cast(U)->isConditional())

1512 continue;

1513 if (isa(U) && cast(U)->getCondition() == ICmp)

1514 continue;

1515 return false;

1516 }

1518 if (U == ExcludedUser)

1519 continue;

1520 if (auto *BI = dyn_cast(U)) {

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

1522 BI->swapSuccessors();

1523

1524

1525

1526

1527

1528 continue;

1529 }

1530 if (auto *SI = dyn_cast(U)) {

1531

1532 SI->swapValues();

1533 SI->swapProfMetadata();

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

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

1536 "Must not be already in");

1537 Scope->FalseBiasedSelects.insert(SI);

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

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

1540 "Must not be already in");

1541 Scope->TrueBiasedSelects.insert(SI);

1542 }

1543 continue;

1544 }

1546 }

1548 return true;

1549}

1550

1551

1552

1553

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

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

1560

1561 BlocksInScope.insert(BB);

1562 }

1563 }

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

1566 for (BasicBlock *BB : BlocksInScope)

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

1568 });

1569 for (BasicBlock *BB : BlocksInScope) {

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

1573 if (auto *UI = dyn_cast(U)) {

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

1575

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

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

1579 Users.push_back(UI);

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

1581

1582

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

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

1587 Users.push_back(UI);

1588 }

1589 }

1590 }

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

1592

1593

1594

1599 }

1600 TrivialPHIs.insert(PN);

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

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 }

1612 }

1613}

1614

1615

1618#ifndef NDEBUG

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

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

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

1622 return true;

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

1625 Scope->FalseBiasedSelects.count(SI))

1626 return true;

1627 return false;

1628 };

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

1630 assert(HasBiasedBranchOrSelect(RI, Scope) &&

1631 "Must have biased branch or select");

1632 }

1633#endif

1634}

1635

1636

1637

1639 CHRScope *Scope, BasicBlock *PreEntryBlock) {

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

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

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

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

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

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

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

1649 if (auto *I = dyn_cast(V)) {

1650 (void)(I);

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

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

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

1654 }

1655 }

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

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

1659 if (!(IsTrueBiased || IsFalseBiased))

1660 continue;

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

1663 if (auto *I = dyn_cast(V)) {

1664 (void)(I);

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

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

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

1668 }

1669 }

1670 }

1671}

1672

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

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

1675

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

1677

1680 unsigned Duplication = getRegionDuplicationCount(R);

1682 << "\n");

1685 << " for this region");

1686 ORE.emit([&]() {

1688 R->getEntry()->getTerminator())

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

1690 });

1691 return;

1692 }

1693 }

1695 DuplicationCount[RI.R]++;

1696 }

1697

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

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

1702 std::optional<uint64_t> ProfileCount = BFI.getBlockProfileCount(EntryBlock);

1703

1704 if (ExitBlock) {

1705

1706

1707

1708

1709

1710

1712 }

1713

1714

1715

1716

1717

1718

1719

1720

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

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

1728 BasicBlock *PreEntryBlock = EntryBlock;

1729

1731

1732

1733

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

1735

1736

1737

1738 BranchInst *MergedBr = createMergedBranch(PreEntryBlock, EntryBlock,

1739 NewEntryBlock, VMap);

1740

1741#ifndef NDEBUG

1743#endif

1744

1745

1747

1748#ifndef NDEBUG

1750#endif

1751

1752

1753

1754 fixupBranchesAndSelects(Scope, PreEntryBlock, MergedBr,

1756}

1757

1758

1759

1760

1761void CHR::cloneScopeBlocks(CHRScope *Scope,

1766

1767

1768

1769

1770

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

1774

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

1778 VMap[BB] = NewBB;

1779

1780

1781

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

1785 });

1786 }

1787

1788

1789

1790 if (ExitBlock)

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

1792 F.end());

1793

1794

1799

1800

1801

1802

1803 if (ExitBlock)

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

1806 ++I) {

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

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

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

1810 auto It = VMap.find(V);

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

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

1813 PN.addIncoming(V, cast(VMap[Pred]));

1814 }

1815 }

1816}

1817

1818

1819

1826 "SplitBlock did not work correctly!");

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

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

1830 "NewEntryBlock must have been copied");

1833

1834

1836 cast(VMap[NewEntryBlock]),

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

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

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

1841 return NewBR;

1842}

1843

1844

1845

1846void CHR::fixupBranchesAndSelects(CHRScope *Scope,

1852 uint64_t NumCHRedBranches = 0;

1856 if (RI.HasBranch) {

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

1858 ++NumCHRedBranches;

1859 }

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

1862 ++NumCHRedBranches;

1863 }

1864 }

1865 assert(NumCHRedBranches > 0);

1866 Stats.NumBranchesDelta += NumCHRedBranches - 1;

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

1868 ORE.emit([&]() {

1870 "CHR",

1871

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

1874 << " branches or selects";

1875 });

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

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

1880 };

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

1883 << "\n");

1884}

1885

1886

1887

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

1890 Value *&MergedCondition,

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

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

1894 "Must be truthy or falsy");

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

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

1899

1900 if (CHRBranchBias > Bias)

1901 CHRBranchBias = Bias;

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

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

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

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

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

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

1908 if (IfThen == RegionExitBlock) {

1909

1910

1912 }

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

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

1916 BasicBlock *HotTarget = IsTrueBiased ? IfThen : IfElse;

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

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

1919 MergedCondition);

1920

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

1922 "The successor shouldn't change");

1923 Value *NewCondition = ConditionTrue ?

1926 BI->setCondition(NewCondition);

1927}

1928

1929

1930

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

1933 Value *&MergedCondition,

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

1936 assert((IsTrueBiased ||

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

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

1941

1942 if (CHRBranchBias > Bias)

1943 CHRBranchBias = Bias;

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

1946 MergedCondition);

1947 Value *NewCondition = IsTrueBiased ?

1950 SI->setCondition(NewCondition);

1951}

1952

1953

1954

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

1956 Instruction *BranchOrSelect, CHRScope *Scope,

1958 if (!IsTrueBiased) {

1959

1960

1961

1962 auto *ICmp = dyn_cast(Cond);

1963 if (!ICmp ||

1966 }

1967

1968

1971

1972

1974}

1975

1977 unsigned I = 0;

1979 for (CHRScope *Scope : CHRScopes) {

1980 transformScopes(Scope, TrivialPHIs);

1982 std::ostringstream oss;

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

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

1985 (void)I;

1986 }

1987}

1988

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

1992 for (CHRScope *Scope : Scopes) {

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

1994 }

1995}

1996

1997bool CHR::run() {

1999 return false;

2000

2002

2003 bool Changed = false;

2004 {

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

2007 RI.print(dbgs()));

2008

2009

2010

2012 findScopes(AllScopes);

2014

2015

2016

2017

2018

2019

2021 splitScopes(AllScopes, SplitScopes);

2023

2024

2025

2026 classifyBiasedScopes(SplitScopes);

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

2028

2029

2030

2032 filterScopes(SplitScopes, FilteredScopes);

2034

2035

2037 setCHRRegions(FilteredScopes, SetScopes);

2039

2040

2041

2042

2044 sortScopes(SetScopes, SortedScopes);

2046

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

2049 RI.print(dbgs()));

2050

2051

2052 if (!SortedScopes.empty()) {

2053 transformScopes(SortedScopes);

2054 Changed = true;

2055 }

2056 }

2057

2058 if (Changed) {

2060 ORE.emit([&]() {

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

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

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

2065 << " (static) and "

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

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

2068 });

2069 }

2070

2071 return Changed;

2072}

2073

2074namespace llvm {

2075

2078}

2079

2085

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

2088 auto &PSI = *PPSI;

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

2094 if (!Changed)

2097}

2098

2099}

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 void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)

#define LLVM_ATTRIBUTE_UNUSED

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

static raw_ostream LLVM_ATTRIBUTE_UNUSED & operator<<(raw_ostream &OS, const CHRStats &Stats)

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

static StringSet CHRFunctions

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

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

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)

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)

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

static StringSet CHRModules

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

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

static bool hasAtLeastTwoBiasedBranches(CHRScope *Scope)

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

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

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

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

static bool isHoistableInstructionType(Instruction *I)

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

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

static Instruction * getBranchInsertPoint(RegInfo &RI)

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

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 LLVM_ATTRIBUTE_UNUSED assertCHRRegionsHaveBiasedBranchOrSelect(CHRScope *Scope)

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 void LLVM_ATTRIBUTE_UNUSED dumpScopes(SmallVectorImpl< CHRScope * > &Scopes, const char *Label)

static BranchProbability getCHRBiasThreshold()

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)

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

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

static void parseCHRFilterFiles()

Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx

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.

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.

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

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

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

A container for analyses that lazily runs them and caches their results.

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

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

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.

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.

BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...

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

This is the shared class of boolean and integer constants.

static ConstantInt * getTrue(LLVMContext &Context)

ControlHeightReductionPass()

PreservedAnalyses run(Function &F, FunctionAnalysisManager &FAM)

This class represents an Operation in the Expression.

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.

bool isReachableFromEntry(const Use &U) const

Provide an overload for a Use.

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

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

Class to represent profile counts.

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="")

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

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

void insertBefore(Instruction *InsertPos)

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

InstListType::iterator eraseFromParent()

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

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

An analysis over an "inner" IR unit that provides access to an analysis manager over a "outer" IR uni...

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.

RegionT * getParent() const

Get the parent of the Region.

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 insert(const value_type &X)

Insert a new element into the SetVector.

bool contains(const key_type &key) const

Check if the SetVector contains the given key.

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

void push_back(const T &Elt)

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

size_type count(StringRef Key) const

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

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.

std::pair< typename Base::iterator, bool > insert(StringRef key)

void dropAllReferences()

Drop all references to operands.

iterator find(const KeyT &Val)

LLVM Value Representation.

iterator_range< user_iterator > users()

StringRef getName() const

Return a constant reference to the value's name.

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

bool contains(const_arg_type_t< ValueT > V) const

Check if the set contains the given element.

bool erase(const ValueT &V)

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

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

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.

void stable_sort(R &&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)

void setBranchWeights(Instruction &I, ArrayRef< uint32_t > Weights, bool IsExpected)

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

raw_ostream & dbgs()

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

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

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

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

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

raw_fd_ostream & errs()

This returns a reference to a raw_ostream for standard error.

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

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

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.

OutputIt copy(R &&Range, OutputIt Out)

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

Extract branch weights from MD_prof metadata.

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)

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

Implement std::swap in terms of BitVector swap.