1//===-- ControlHeightReduction.cpp - Control Height Reduction -------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This pass merges conditional blocks of code and reduces the number of
10// conditional branches in the hot paths based on profiles.
11//
12//===----------------------------------------------------------------------===//
13
14#include "llvm/Transforms/Instrumentation/ControlHeightReduction.h"
15#include "InstrumentationOptions.h"
16#include "llvm/ADT/DenseMap.h"
17#include "llvm/ADT/DenseSet.h"
18#include "llvm/ADT/SmallVector.h"
19#include "llvm/ADT/StringSet.h"
20#include "llvm/Analysis/BlockFrequencyInfo.h"
21#include "llvm/Analysis/GlobalsModRef.h"
22#include "llvm/Analysis/OptimizationRemarkEmitter.h"
23#include "llvm/Analysis/ProfileSummaryInfo.h"
24#include "llvm/Analysis/RegionInfo.h"
25#include "llvm/Analysis/RegionIterator.h"
26#include "llvm/Analysis/ValueTracking.h"
27#include "llvm/IR/CFG.h"
28#include "llvm/IR/Dominators.h"
29#include "llvm/IR/IRBuilder.h"
30#include "llvm/IR/IntrinsicInst.h"
31#include "llvm/IR/MDBuilder.h"
32#include "llvm/IR/Module.h"
33#include "llvm/IR/PassManager.h"
34#include "llvm/IR/ProfDataUtils.h"
35#include "llvm/Support/BranchProbability.h"
36#include "llvm/Support/MemoryBuffer.h"
37#include "llvm/Transforms/Utils/BasicBlockUtils.h"
38#include "llvm/Transforms/Utils/Cloning.h"
39#include "llvm/Transforms/Utils/ValueMapper.h"
40
41#include <optional>
42#include <set>
43#include <sstream>
44
45using namespace llvm;
46
47#define DEBUG_TYPE "chr"
48
49#define CHR_DEBUG(X) LLVM_DEBUG(X)
50
51static void parseCHRFilterFiles(const InstrumentationOptions &Opts,
52 StringSet<> &CHRModules,
53 StringSet<> &CHRFunctions) {
54 if (!Opts.chr_module_list.empty()) {
55 auto FileOrErr = MemoryBuffer::getFile(Filename: Opts.chr_module_list);
56 if (!FileOrErr) {
57 errs() << "Error: Couldn't read the chr-module-list file "
58 << Opts.chr_module_list << "\n";
59 std::exit(status: 1);
60 }
61 StringRef Buf = FileOrErr->get()->getBuffer();
62 SmallVector<StringRef, 0> Lines;
63 Buf.split(A&: Lines, Separator: '\n');
64 for (StringRef Line : Lines) {
65 Line = Line.trim();
66 if (!Line.empty())
67 CHRModules.insert(key: Line);
68 }
69 }
70 if (!Opts.chr_function_list.empty()) {
71 auto FileOrErr = MemoryBuffer::getFile(Filename: Opts.chr_function_list);
72 if (!FileOrErr) {
73 errs() << "Error: Couldn't read the chr-function-list file "
74 << Opts.chr_function_list << "\n";
75 std::exit(status: 1);
76 }
77 StringRef Buf = FileOrErr->get()->getBuffer();
78 SmallVector<StringRef, 0> Lines;
79 Buf.split(A&: Lines, Separator: '\n');
80 for (StringRef Line : Lines) {
81 Line = Line.trim();
82 if (!Line.empty())
83 CHRFunctions.insert(key: Line);
84 }
85 }
86}
87
88namespace {
89
90struct CHRStats {
91 CHRStats() = default;
92 void print(raw_ostream &OS) const {
93 OS << "CHRStats: NumBranches " << NumBranches
94 << " NumBranchesDelta " << NumBranchesDelta
95 << " WeightedNumBranchesDelta " << WeightedNumBranchesDelta;
96 }
97 // The original number of conditional branches / selects
98 uint64_t NumBranches = 0;
99 // The decrease of the number of conditional branches / selects in the hot
100 // paths due to CHR.
101 uint64_t NumBranchesDelta = 0;
102 // NumBranchesDelta weighted by the profile count at the scope entry.
103 uint64_t WeightedNumBranchesDelta = 0;
104};
105
106// RegInfo - some properties of a Region.
107struct RegInfo {
108 RegInfo() = default;
109 RegInfo(Region *RegionIn) : R(RegionIn) {}
110 Region *R = nullptr;
111 bool HasBranch = false;
112 SmallVector<SelectInst *, 8> Selects;
113};
114
115typedef DenseMap<Region *, DenseSet<Instruction *>> HoistStopMapTy;
116
117// CHRScope - a sequence of regions to CHR together. It corresponds to a
118// sequence of conditional blocks. It can have subscopes which correspond to
119// nested conditional blocks. Nested CHRScopes form a tree.
120class CHRScope {
121 public:
122 CHRScope(RegInfo RI) : BranchInsertPoint(nullptr) {
123 assert(RI.R && "Null RegionIn");
124 RegInfos.push_back(Elt: RI);
125 }
126
127 Region *getParentRegion() {
128 assert(RegInfos.size() > 0 && "Empty CHRScope");
129 Region *Parent = RegInfos[0].R->getParent();
130 assert(Parent && "Unexpected to call this on the top-level region");
131 return Parent;
132 }
133
134 BasicBlock *getEntryBlock() {
135 assert(RegInfos.size() > 0 && "Empty CHRScope");
136 return RegInfos.front().R->getEntry();
137 }
138
139 BasicBlock *getExitBlock() {
140 assert(RegInfos.size() > 0 && "Empty CHRScope");
141 return RegInfos.back().R->getExit();
142 }
143
144 bool appendable(CHRScope *Next) {
145 // The next scope is appendable only if this scope is directly connected to
146 // it (which implies it post-dominates this scope) and this scope dominates
147 // it (no edge to the next scope outside this scope).
148 BasicBlock *NextEntry = Next->getEntryBlock();
149 if (getExitBlock() != NextEntry)
150 // Not directly connected.
151 return false;
152 Region *LastRegion = RegInfos.back().R;
153 for (BasicBlock *Pred : predecessors(BB: NextEntry))
154 if (!LastRegion->contains(BB: Pred))
155 // There's an edge going into the entry of the next scope from outside
156 // of this scope.
157 return false;
158 return true;
159 }
160
161 void append(CHRScope *Next) {
162 assert(RegInfos.size() > 0 && "Empty CHRScope");
163 assert(Next->RegInfos.size() > 0 && "Empty CHRScope");
164 assert(getParentRegion() == Next->getParentRegion() &&
165 "Must be siblings");
166 assert(getExitBlock() == Next->getEntryBlock() &&
167 "Must be adjacent");
168 RegInfos.append(in_start: Next->RegInfos.begin(), in_end: Next->RegInfos.end());
169 Subs.append(in_start: Next->Subs.begin(), in_end: Next->Subs.end());
170 }
171
172 void addSub(CHRScope *SubIn) {
173#ifndef NDEBUG
174 bool IsChild = false;
175 for (RegInfo &RI : RegInfos)
176 if (RI.R == SubIn->getParentRegion()) {
177 IsChild = true;
178 break;
179 }
180 assert(IsChild && "Must be a child");
181#endif
182 Subs.push_back(Elt: SubIn);
183 }
184
185 // Split this scope at the boundary region into two, which will belong to the
186 // tail and returns the tail.
187 CHRScope *split(Region *Boundary) {
188 assert(Boundary && "Boundary null");
189 assert(RegInfos.begin()->R != Boundary &&
190 "Can't be split at beginning");
191 auto BoundaryIt = llvm::find_if(
192 Range&: RegInfos, P: [&Boundary](const RegInfo &RI) { return Boundary == RI.R; });
193 if (BoundaryIt == RegInfos.end())
194 return nullptr;
195 ArrayRef<RegInfo> TailRegInfos(BoundaryIt, RegInfos.end());
196 DenseSet<Region *> TailRegionSet;
197 for (const RegInfo &RI : TailRegInfos)
198 TailRegionSet.insert(V: RI.R);
199
200 auto TailIt =
201 std::stable_partition(first: Subs.begin(), last: Subs.end(), pred: [&](CHRScope *Sub) {
202 assert(Sub && "null Sub");
203 Region *Parent = Sub->getParentRegion();
204 if (TailRegionSet.count(V: Parent))
205 return false;
206
207 assert(llvm::any_of(
208 RegInfos,
209 [&Parent](const RegInfo &RI) { return Parent == RI.R; }) &&
210 "Must be in head");
211 return true;
212 });
213 ArrayRef<CHRScope *> TailSubs(TailIt, Subs.end());
214
215 assert(HoistStopMap.empty() && "MapHoistStops must be empty");
216 auto *Scope = new CHRScope(TailRegInfos, TailSubs);
217 RegInfos.erase(CS: BoundaryIt, CE: RegInfos.end());
218 Subs.erase(CS: TailIt, CE: Subs.end());
219 return Scope;
220 }
221
222 bool contains(Instruction *I) const {
223 BasicBlock *Parent = I->getParent();
224 for (const RegInfo &RI : RegInfos)
225 if (RI.R->contains(BB: Parent))
226 return true;
227 return false;
228 }
229
230 void print(raw_ostream &OS) const;
231
232 SmallVector<RegInfo, 8> RegInfos; // Regions that belong to this scope
233 SmallVector<CHRScope *, 8> Subs; // Subscopes.
234
235 // The instruction at which to insert the CHR conditional branch (and hoist
236 // the dependent condition values).
237 Instruction *BranchInsertPoint;
238
239 // True-biased and false-biased regions (conditional blocks),
240 // respectively. Used only for the outermost scope and includes regions in
241 // subscopes. The rest are unbiased.
242 DenseSet<Region *> TrueBiasedRegions;
243 DenseSet<Region *> FalseBiasedRegions;
244 // Among the biased regions, the regions that get CHRed.
245 SmallVector<RegInfo, 8> CHRRegions;
246
247 // True-biased and false-biased selects, respectively. Used only for the
248 // outermost scope and includes ones in subscopes.
249 DenseSet<SelectInst *> TrueBiasedSelects;
250 DenseSet<SelectInst *> FalseBiasedSelects;
251
252 // Map from one of the above regions to the instructions to stop
253 // hoisting instructions at through use-def chains.
254 HoistStopMapTy HoistStopMap;
255
256 private:
257 CHRScope(ArrayRef<RegInfo> RegInfosIn, ArrayRef<CHRScope *> SubsIn)
258 : RegInfos(RegInfosIn), Subs(SubsIn), BranchInsertPoint(nullptr) {}
259};
260
261class CHR {
262public:
263 CHR(const InstrumentationOptions &Opts, const StringSet<> &CHRModules,
264 const StringSet<> &CHRFunctions, Function &Fin, BlockFrequencyInfo &BFIin,
265 DominatorTree &DTin, ProfileSummaryInfo &PSIin, RegionInfo &RIin,
266 OptimizationRemarkEmitter &OREin)
267 : Opts(Opts), CHRModules(CHRModules), CHRFunctions(CHRFunctions), F(Fin),
268 BFI(BFIin), DT(DTin), PSI(PSIin), RI(RIin), ORE(OREin) {}
269
270 ~CHR() {
271 for (CHRScope *Scope : Scopes) {
272 delete Scope;
273 }
274 }
275
276 bool run();
277
278 private:
279 // See the comments in CHR::run() for the high level flow of the algorithm and
280 // what the following functions do.
281
282 void findScopes(SmallVectorImpl<CHRScope *> &Output) {
283 Region *R = RI.getTopLevelRegion();
284 if (CHRScope *Scope = findScopes(R, NextRegion: nullptr, ParentRegion: nullptr, Scopes&: Output)) {
285 Output.push_back(Elt: Scope);
286 }
287 }
288 CHRScope *findScopes(Region *R, Region *NextRegion, Region *ParentRegion,
289 SmallVectorImpl<CHRScope *> &Scopes);
290 CHRScope *findScope(Region *R);
291 void checkScopeHoistable(CHRScope *Scope);
292
293 void splitScopes(SmallVectorImpl<CHRScope *> &Input,
294 SmallVectorImpl<CHRScope *> &Output);
295 SmallVector<CHRScope *, 8> splitScope(CHRScope *Scope,
296 CHRScope *Outer,
297 DenseSet<Value *> *OuterConditionValues,
298 Instruction *OuterInsertPoint,
299 SmallVectorImpl<CHRScope *> &Output,
300 DenseSet<Instruction *> &Unhoistables);
301
302 void classifyBiasedScopes(SmallVectorImpl<CHRScope *> &Scopes);
303 void classifyBiasedScopes(CHRScope *Scope, CHRScope *OutermostScope);
304
305 void filterScopes(SmallVectorImpl<CHRScope *> &Input,
306 SmallVectorImpl<CHRScope *> &Output);
307
308 void setCHRRegions(SmallVectorImpl<CHRScope *> &Input,
309 SmallVectorImpl<CHRScope *> &Output);
310 void setCHRRegions(CHRScope *Scope, CHRScope *OutermostScope);
311
312 void sortScopes(SmallVectorImpl<CHRScope *> &Input,
313 SmallVectorImpl<CHRScope *> &Output);
314
315 void transformScopes(SmallVectorImpl<CHRScope *> &CHRScopes);
316 void transformScopes(CHRScope *Scope, DenseSet<PHINode *> &TrivialPHIs);
317 void cloneScopeBlocks(CHRScope *Scope,
318 BasicBlock *PreEntryBlock,
319 BasicBlock *ExitBlock,
320 Region *LastRegion,
321 ValueToValueMapTy &VMap);
322 CondBrInst *createMergedBranch(BasicBlock *PreEntryBlock,
323 BasicBlock *EntryBlock,
324 BasicBlock *NewEntryBlock,
325 ValueToValueMapTy &VMap);
326 void fixupBranchesAndSelects(CHRScope *Scope, BasicBlock *PreEntryBlock,
327 CondBrInst *MergedBR, uint64_t ProfileCount);
328 void fixupBranch(Region *R, CHRScope *Scope, IRBuilder<> &IRB,
329 Value *&MergedCondition, BranchProbability &CHRBranchBias);
330 void fixupSelect(SelectInst *SI, CHRScope *Scope, IRBuilder<> &IRB,
331 Value *&MergedCondition, BranchProbability &CHRBranchBias);
332 void addToMergedCondition(bool IsTrueBiased, Value *Cond,
333 Instruction *BranchOrSelect, CHRScope *Scope,
334 IRBuilder<> &IRB, Value *&MergedCondition);
335 unsigned getRegionDuplicationCount(const Region *R) {
336 unsigned Count = 0;
337 // Find out how many times region R is cloned. Note that if the parent
338 // of R is cloned, R is also cloned, but R's clone count is not updated
339 // from the clone of the parent. We need to accumulate all the counts
340 // from the ancestors to get the clone count.
341 while (R) {
342 Count += DuplicationCount[R];
343 R = R->getParent();
344 }
345 return Count;
346 }
347
348 const InstrumentationOptions &Opts;
349 const StringSet<> &CHRModules;
350 const StringSet<> &CHRFunctions;
351 Function &F;
352 BlockFrequencyInfo &BFI;
353 DominatorTree &DT;
354 ProfileSummaryInfo &PSI;
355 RegionInfo &RI;
356 OptimizationRemarkEmitter &ORE;
357 CHRStats Stats;
358
359 // All the true-biased regions in the function
360 DenseSet<Region *> TrueBiasedRegionsGlobal;
361 // All the false-biased regions in the function
362 DenseSet<Region *> FalseBiasedRegionsGlobal;
363 // All the true-biased selects in the function
364 DenseSet<SelectInst *> TrueBiasedSelectsGlobal;
365 // All the false-biased selects in the function
366 DenseSet<SelectInst *> FalseBiasedSelectsGlobal;
367 // A map from biased regions to their branch bias
368 DenseMap<Region *, BranchProbability> BranchBiasMap;
369 // A map from biased selects to their branch bias
370 DenseMap<SelectInst *, BranchProbability> SelectBiasMap;
371 // All the scopes.
372 DenseSet<CHRScope *> Scopes;
373 // This maps records how many times this region is cloned.
374 DenseMap<const Region *, unsigned> DuplicationCount;
375};
376
377} // end anonymous namespace
378
379[[maybe_unused]] static inline raw_ostream &operator<<(raw_ostream &OS,
380 const CHRStats &Stats) {
381 Stats.print(OS);
382 return OS;
383}
384
385static inline
386raw_ostream &operator<<(raw_ostream &OS, const CHRScope &Scope) {
387 Scope.print(OS);
388 return OS;
389}
390
391static bool shouldApply(const InstrumentationOptions &Opts,
392 const StringSet<> &CHRModules,
393 const StringSet<> &CHRFunctions, Function &F,
394 ProfileSummaryInfo &PSI) {
395 if (Opts.disable_chr)
396 return false;
397
398 if (Opts.force_chr)
399 return true;
400
401 if (!Opts.chr_module_list.empty() || !Opts.chr_function_list.empty()) {
402 if (CHRModules.count(Key: F.getParent()->getName()))
403 return true;
404 return CHRFunctions.count(Key: F.getName());
405 }
406
407 return PSI.isFunctionEntryHot(F: &F);
408}
409
410[[maybe_unused]] static void dumpIR(Function &F, const char *Label,
411 CHRStats *Stats) {
412 StringRef FuncName = F.getName();
413 StringRef ModuleName = F.getParent()->getName();
414 (void)(FuncName); // Unused in release build.
415 (void)(ModuleName); // Unused in release build.
416 CHR_DEBUG(dbgs() << "CHR IR dump " << Label << " " << ModuleName << " "
417 << FuncName);
418 if (Stats)
419 CHR_DEBUG(dbgs() << " " << *Stats);
420 CHR_DEBUG(dbgs() << "\n");
421 CHR_DEBUG(F.dump());
422}
423
424void CHRScope::print(raw_ostream &OS) const {
425 assert(RegInfos.size() > 0 && "Empty CHRScope");
426 OS << "CHRScope[";
427 OS << RegInfos.size() << ", Regions[";
428 for (const RegInfo &RI : RegInfos) {
429 OS << RI.R->getNameStr();
430 if (RI.HasBranch)
431 OS << " B";
432 if (RI.Selects.size() > 0)
433 OS << " S" << RI.Selects.size();
434 OS << ", ";
435 }
436 if (RegInfos[0].R->getParent()) {
437 OS << "], Parent " << RegInfos[0].R->getParent()->getNameStr();
438 } else {
439 // top level region
440 OS << "]";
441 }
442 OS << ", Subs[";
443 for (CHRScope *Sub : Subs) {
444 OS << *Sub << ", ";
445 }
446 OS << "]]";
447}
448
449// Return true if the given instruction type can be hoisted by CHR.
450static bool isHoistableInstructionType(Instruction *I) {
451 return isa<BinaryOperator>(Val: I) || isa<CastInst>(Val: I) || isa<SelectInst>(Val: I) ||
452 isa<GetElementPtrInst>(Val: I) || isa<CmpInst>(Val: I) ||
453 isa<InsertElementInst>(Val: I) || isa<ExtractElementInst>(Val: I) ||
454 isa<ShuffleVectorInst>(Val: I) || isa<ExtractValueInst>(Val: I) ||
455 isa<InsertValueInst>(Val: I);
456}
457
458// Return true if the given instruction can be hoisted by CHR.
459static bool isHoistable(Instruction *I, DominatorTree &DT) {
460 if (!isHoistableInstructionType(I))
461 return false;
462 return isSafeToSpeculativelyExecute(I, CtxI: nullptr, AC: nullptr, DT: &DT);
463}
464
465// Recursively traverse the use-def chains of the given value and return a set
466// of the unhoistable base values defined within the scope (excluding the
467// first-region entry block) or the (hoistable or unhoistable) base values that
468// are defined outside (including the first-region entry block) of the
469// scope. The returned set doesn't include constants.
470static const std::set<Value *> &
471getBaseValues(Value *V, DominatorTree &DT,
472 DenseMap<Value *, std::set<Value *>> &Visited) {
473 auto It = Visited.find(Val: V);
474 if (It != Visited.end()) {
475 return It->second;
476 }
477 std::set<Value *> Result;
478 if (auto *I = dyn_cast<Instruction>(Val: V)) {
479 // We don't stop at a block that's not in the Scope because we would miss
480 // some instructions that are based on the same base values if we stop
481 // there.
482 if (!isHoistable(I, DT)) {
483 Result.insert(x: I);
484 return Visited.insert(KV: std::make_pair(x&: V, y: std::move(Result))).first->second;
485 }
486 // I is hoistable above the Scope.
487 for (Value *Op : I->operands()) {
488 const std::set<Value *> &OpResult = getBaseValues(V: Op, DT, Visited);
489 Result.insert(first: OpResult.begin(), last: OpResult.end());
490 }
491 return Visited.insert(KV: std::make_pair(x&: V, y: std::move(Result))).first->second;
492 }
493 if (isa<Argument>(Val: V)) {
494 Result.insert(x: V);
495 }
496 // We don't include others like constants because those won't lead to any
497 // chance of folding of conditions (eg two bit checks merged into one check)
498 // after CHR.
499 return Visited.insert(KV: std::make_pair(x&: V, y: std::move(Result))).first->second;
500}
501
502// Return true if V is already hoisted or can be hoisted (along with its
503// operands) above the insert point. When it returns true and HoistStops is
504// non-null, the instructions to stop hoisting at through the use-def chains are
505// inserted into HoistStops.
506static bool
507checkHoistValue(Value *V, Instruction *InsertPoint, DominatorTree &DT,
508 DenseSet<Instruction *> &Unhoistables,
509 DenseSet<Instruction *> *HoistStops,
510 DenseMap<Instruction *, bool> &Visited) {
511 assert(InsertPoint && "Null InsertPoint");
512 if (auto *I = dyn_cast<Instruction>(Val: V)) {
513 auto It = Visited.find(Val: I);
514 if (It != Visited.end()) {
515 return It->second;
516 }
517 assert(DT.getNode(I->getParent()) && "DT must contain I's parent block");
518 assert(DT.getNode(InsertPoint->getParent()) && "DT must contain Destination");
519 if (Unhoistables.count(V: I)) {
520 // Don't hoist if they are not to be hoisted.
521 Visited[I] = false;
522 return false;
523 }
524 if (DT.dominates(Def: I, User: InsertPoint)) {
525 // We are already above the insert point. Stop here.
526 if (HoistStops)
527 HoistStops->insert(V: I);
528 Visited[I] = true;
529 return true;
530 }
531 // We aren't not above the insert point, check if we can hoist it above the
532 // insert point.
533 if (isHoistable(I, DT)) {
534 // Check operands first.
535 DenseSet<Instruction *> OpsHoistStops;
536 bool AllOpsHoisted = true;
537 for (Value *Op : I->operands()) {
538 if (!checkHoistValue(V: Op, InsertPoint, DT, Unhoistables, HoistStops: &OpsHoistStops,
539 Visited)) {
540 AllOpsHoisted = false;
541 break;
542 }
543 }
544 if (AllOpsHoisted) {
545 CHR_DEBUG(dbgs() << "checkHoistValue " << *I << "\n");
546 if (HoistStops)
547 HoistStops->insert_range(R&: OpsHoistStops);
548 Visited[I] = true;
549 return true;
550 }
551 }
552 Visited[I] = false;
553 return false;
554 }
555 // Non-instructions are considered hoistable.
556 return true;
557}
558
559// Constructs the true and false branch probabilities if the the instruction has
560// valid branch weights. Returns true when this was successful, false otherwise.
561static bool extractBranchProbabilities(Instruction *I,
562 BranchProbability &TrueProb,
563 BranchProbability &FalseProb) {
564 uint64_t TrueWeight;
565 uint64_t FalseWeight;
566 if (!extractBranchWeights(I: *I, TrueVal&: TrueWeight, FalseVal&: FalseWeight))
567 return false;
568 uint64_t SumWeight = TrueWeight + FalseWeight;
569
570 assert(SumWeight >= TrueWeight && SumWeight >= FalseWeight &&
571 "Overflow calculating branch probabilities.");
572
573 // Guard against 0-to-0 branch weights to avoid a division-by-zero crash.
574 if (SumWeight == 0)
575 return false;
576
577 TrueProb = BranchProbability::getBranchProbability(Numerator: TrueWeight, Denominator: SumWeight);
578 FalseProb = BranchProbability::getBranchProbability(Numerator: FalseWeight, Denominator: SumWeight);
579 return true;
580}
581
582static BranchProbability
583getCHRBiasThreshold(const InstrumentationOptions &Opts) {
584 return BranchProbability::getBranchProbability(
585 Numerator: static_cast<uint64_t>(Opts.chr_bias_threshold * 1000000), Denominator: 1000000);
586}
587
588// A helper for CheckBiasedBranch and CheckBiasedSelect. If TrueProb >=
589// -chr-bias-threshold, put Key into TrueSet and return true. If FalseProb >=
590// -chr-bias-threshold, put Key into FalseSet and return true. Otherwise, return
591// false.
592template <typename K, typename S, typename M>
593static bool checkBias(const InstrumentationOptions &Opts, K *Key,
594 BranchProbability TrueProb, BranchProbability FalseProb,
595 S &TrueSet, S &FalseSet, M &BiasMap) {
596 BranchProbability Threshold = getCHRBiasThreshold(Opts);
597 if (TrueProb >= Threshold) {
598 TrueSet.insert(Key);
599 BiasMap[Key] = TrueProb;
600 return true;
601 } else if (FalseProb >= Threshold) {
602 FalseSet.insert(Key);
603 BiasMap[Key] = FalseProb;
604 return true;
605 }
606 return false;
607}
608
609// Returns true and insert a region into the right biased set and the map if the
610// branch of the region is biased.
611static bool
612checkBiasedBranch(const InstrumentationOptions &Opts, CondBrInst *BI, Region *R,
613 DenseSet<Region *> &TrueBiasedRegionsGlobal,
614 DenseSet<Region *> &FalseBiasedRegionsGlobal,
615 DenseMap<Region *, BranchProbability> &BranchBiasMap) {
616 BranchProbability ThenProb, ElseProb;
617 if (!extractBranchProbabilities(I: BI, TrueProb&: ThenProb, FalseProb&: ElseProb))
618 return false;
619 BasicBlock *IfThen = BI->getSuccessor(i: 0);
620 BasicBlock *IfElse = BI->getSuccessor(i: 1);
621 assert((IfThen == R->getExit() || IfElse == R->getExit()) &&
622 IfThen != IfElse &&
623 "Invariant from findScopes");
624 if (IfThen == R->getExit()) {
625 // Swap them so that IfThen/ThenProb means going into the conditional code
626 // and IfElse/ElseProb means skipping it.
627 std::swap(a&: IfThen, b&: IfElse);
628 std::swap(a&: ThenProb, b&: ElseProb);
629 }
630 CHR_DEBUG(dbgs() << "BI " << *BI << " ");
631 CHR_DEBUG(dbgs() << "ThenProb " << ThenProb << " ");
632 CHR_DEBUG(dbgs() << "ElseProb " << ElseProb << "\n");
633 return checkBias(Opts, Key: R, TrueProb: ThenProb, FalseProb: ElseProb, TrueSet&: TrueBiasedRegionsGlobal,
634 FalseSet&: FalseBiasedRegionsGlobal, BiasMap&: BranchBiasMap);
635}
636
637// Returns true and insert a select into the right biased set and the map if the
638// select is biased.
639static bool
640checkBiasedSelect(const InstrumentationOptions &Opts, SelectInst *SI, Region *R,
641 DenseSet<SelectInst *> &TrueBiasedSelectsGlobal,
642 DenseSet<SelectInst *> &FalseBiasedSelectsGlobal,
643 DenseMap<SelectInst *, BranchProbability> &SelectBiasMap) {
644 BranchProbability TrueProb, FalseProb;
645 if (!extractBranchProbabilities(I: SI, TrueProb, FalseProb))
646 return false;
647 CHR_DEBUG(dbgs() << "SI " << *SI << " ");
648 CHR_DEBUG(dbgs() << "TrueProb " << TrueProb << " ");
649 CHR_DEBUG(dbgs() << "FalseProb " << FalseProb << "\n");
650 return checkBias(Opts, Key: SI, TrueProb, FalseProb, TrueSet&: TrueBiasedSelectsGlobal,
651 FalseSet&: FalseBiasedSelectsGlobal, BiasMap&: SelectBiasMap);
652}
653
654// Returns the instruction at which to hoist the dependent condition values and
655// insert the CHR branch for a region. This is the terminator branch in the
656// entry block or the first select in the entry block, if any.
657static Instruction* getBranchInsertPoint(RegInfo &RI) {
658 Region *R = RI.R;
659 BasicBlock *EntryBB = R->getEntry();
660 // The hoist point is by default the terminator of the entry block, which is
661 // the same as the branch instruction if RI.HasBranch is true.
662 Instruction *HoistPoint = EntryBB->getTerminator();
663 for (SelectInst *SI : RI.Selects) {
664 if (SI->getParent() == EntryBB) {
665 // Pick the first select in Selects in the entry block. Note Selects is
666 // sorted in the instruction order within a block (asserted below).
667 HoistPoint = SI;
668 break;
669 }
670 }
671 assert(HoistPoint && "Null HoistPoint");
672#ifndef NDEBUG
673 // Check that HoistPoint is the first one in Selects in the entry block,
674 // if any.
675 DenseSet<Instruction *> EntryBlockSelectSet;
676 for (SelectInst *SI : RI.Selects) {
677 if (SI->getParent() == EntryBB) {
678 EntryBlockSelectSet.insert(SI);
679 }
680 }
681 for (Instruction &I : *EntryBB) {
682 if (EntryBlockSelectSet.contains(&I)) {
683 assert(&I == HoistPoint &&
684 "HoistPoint must be the first one in Selects");
685 break;
686 }
687 }
688#endif
689 return HoistPoint;
690}
691
692// Find a CHR scope in the given region.
693CHRScope * CHR::findScope(Region *R) {
694 CHRScope *Result = nullptr;
695 BasicBlock *Entry = R->getEntry();
696 BasicBlock *Exit = R->getExit(); // null if top level.
697 assert(Entry && "Entry must not be null");
698 assert((Exit == nullptr) == (R->isTopLevelRegion()) &&
699 "Only top level region has a null exit");
700 if (Entry)
701 CHR_DEBUG(dbgs() << "Entry " << Entry->getName() << "\n");
702 else
703 CHR_DEBUG(dbgs() << "Entry null\n");
704 if (Exit)
705 CHR_DEBUG(dbgs() << "Exit " << Exit->getName() << "\n");
706 else
707 CHR_DEBUG(dbgs() << "Exit null\n");
708 // Exclude cases where Entry is part of a subregion (hence it doesn't belong
709 // to this region).
710 bool EntryInSubregion = RI.getRegionFor(BB: Entry) != R;
711 if (EntryInSubregion)
712 return nullptr;
713 // Exclude loops
714 for (BasicBlock *Pred : predecessors(BB: Entry))
715 if (R->contains(BB: Pred))
716 return nullptr;
717 // If any of the basic blocks have address taken, we must skip this region
718 // because we cannot clone basic blocks that have address taken.
719 for (BasicBlock *BB : R->blocks()) {
720 if (BB->hasAddressTaken())
721 return nullptr;
722 // If we encounter llvm.coro.id, skip this region because if the basic block
723 // is cloned, we end up inserting a token type PHI node to the block with
724 // llvm.coro.begin.
725 // FIXME: This could lead to less optimal codegen, because the region is
726 // excluded, it can prevent CHR from merging adjacent regions into bigger
727 // scope and hoisting more branches.
728 for (Instruction &I : *BB) {
729 if (auto *II = dyn_cast<IntrinsicInst>(Val: &I))
730 if (II->getIntrinsicID() == Intrinsic::coro_id)
731 return nullptr;
732 // Can't clone regions containing convergent or noduplicate calls.
733 //
734 // CHR clones a region into hot/cold paths guarded by a merged
735 // speculative branch. On GPU targets, this branch may be divergent
736 // (different threads evaluate it differently), splitting the set of
737 // threads that reach each copy. A convergent call (e.g. a cross-lane
738 // operation like ds_bpermute on AMDGPU) requires a specific set of
739 // threads to be active; when CHR places a copy on the hot path, only
740 // the threads that took the hot branch are active, so the operation
741 // reads stale values from threads that went to the cold path.
742 //
743 // Similarly, noduplicate calls must not be duplicated by definition.
744 //
745 // This matches SimplifyCFG's block-duplication guard.
746 if (auto *CB = dyn_cast<CallBase>(Val: &I)) {
747 if (CB->cannotDuplicate() || CB->isConvergent())
748 return nullptr;
749 }
750 }
751 }
752
753 if (Exit) {
754 // Try to find an if-then block (check if R is an if-then).
755 // if (cond) {
756 // ...
757 // }
758 if (auto *BI = dyn_cast<CondBrInst>(Val: Entry->getTerminator())) {
759 CHR_DEBUG(dbgs() << "BI conditional\n");
760 BasicBlock *S0 = BI->getSuccessor(i: 0);
761 BasicBlock *S1 = BI->getSuccessor(i: 1);
762 CHR_DEBUG(dbgs() << "S0 " << S0->getName() << "\n");
763 CHR_DEBUG(dbgs() << "S1 " << S1->getName() << "\n");
764 if (S0 != S1 && (S0 == Exit || S1 == Exit)) {
765 RegInfo RI(R);
766 RI.HasBranch =
767 checkBiasedBranch(Opts, BI, R, TrueBiasedRegionsGlobal,
768 FalseBiasedRegionsGlobal, BranchBiasMap);
769 Result = new CHRScope(RI);
770 Scopes.insert(V: Result);
771 CHR_DEBUG(dbgs() << "Found a region with a branch\n");
772 ++Stats.NumBranches;
773 if (!RI.HasBranch) {
774 ORE.emit(RemarkBuilder: [&]() {
775 return OptimizationRemarkMissed(DEBUG_TYPE, "BranchNotBiased", BI)
776 << "Branch not biased";
777 });
778 }
779 }
780 }
781 }
782 {
783 // Try to look for selects in the direct child blocks (as opposed to in
784 // subregions) of R.
785 // ...
786 // if (..) { // Some subregion
787 // ...
788 // }
789 // if (..) { // Some subregion
790 // ...
791 // }
792 // ...
793 // a = cond ? b : c;
794 // ...
795 SmallVector<SelectInst *, 8> Selects;
796 for (RegionNode *E : R->elements()) {
797 if (E->isSubRegion())
798 continue;
799 // This returns the basic block of E if E is a direct child of R (not a
800 // subregion.)
801 BasicBlock *BB = E->getEntry();
802 // Need to push in the order to make it easier to find the first Select
803 // later.
804 for (Instruction &I : *BB) {
805 if (auto *SI = dyn_cast<SelectInst>(Val: &I)) {
806 // The fixupBranchesAndSelects function tries to merge
807 // the condition of select instruction with 'i1 true', which
808 // fails for non-integer condition type.
809 if (SI->getCondition()->getType()->isIntegerTy()) {
810 Selects.push_back(Elt: SI);
811 ++Stats.NumBranches;
812 }
813 }
814 }
815 }
816 if (Selects.size() > 0) {
817 auto AddSelects = [&](RegInfo &RI) {
818 for (auto *SI : Selects)
819 if (checkBiasedSelect(Opts, SI, R: RI.R, TrueBiasedSelectsGlobal,
820 FalseBiasedSelectsGlobal, SelectBiasMap))
821 RI.Selects.push_back(Elt: SI);
822 else
823 ORE.emit(RemarkBuilder: [&]() {
824 return OptimizationRemarkMissed(DEBUG_TYPE, "SelectNotBiased", SI)
825 << "Select not biased";
826 });
827 };
828 if (!Result) {
829 CHR_DEBUG(dbgs() << "Found a select-only region\n");
830 RegInfo RI(R);
831 AddSelects(RI);
832 Result = new CHRScope(RI);
833 Scopes.insert(V: Result);
834 } else {
835 CHR_DEBUG(dbgs() << "Found select(s) in a region with a branch\n");
836 AddSelects(Result->RegInfos[0]);
837 }
838 }
839 }
840
841 if (Result) {
842 checkScopeHoistable(Scope: Result);
843 }
844 return Result;
845}
846
847// Check that any of the branch and the selects in the region could be
848// hoisted above the the CHR branch insert point (the most dominating of
849// them, either the branch (at the end of the first block) or the first
850// select in the first block). If the branch can't be hoisted, drop the
851// selects in the first blocks.
852//
853// For example, for the following scope/region with selects, we want to insert
854// the merged branch right before the first select in the first/entry block by
855// hoisting c1, c2, c3, and c4.
856//
857// // Branch insert point here.
858// a = c1 ? b : c; // Select 1
859// d = c2 ? e : f; // Select 2
860// if (c3) { // Branch
861// ...
862// c4 = foo() // A call.
863// g = c4 ? h : i; // Select 3
864// }
865//
866// But suppose we can't hoist c4 because it's dependent on the preceding
867// call. Then, we drop Select 3. Furthermore, if we can't hoist c2, we also drop
868// Select 2. If we can't hoist c3, we drop Selects 1 & 2.
869void CHR::checkScopeHoistable(CHRScope *Scope) {
870 RegInfo &RI = Scope->RegInfos[0];
871 Region *R = RI.R;
872 BasicBlock *EntryBB = R->getEntry();
873 auto *Branch =
874 RI.HasBranch ? cast<CondBrInst>(Val: EntryBB->getTerminator()) : nullptr;
875 SmallVector<SelectInst *, 8> &Selects = RI.Selects;
876 if (RI.HasBranch || !Selects.empty()) {
877 Instruction *InsertPoint = getBranchInsertPoint(RI);
878 CHR_DEBUG(dbgs() << "InsertPoint " << *InsertPoint << "\n");
879 // Avoid a data dependence from a select or a branch to a(nother)
880 // select. Note no instruction can't data-depend on a branch (a branch
881 // instruction doesn't produce a value).
882 // Initialize Unhoistables with the selects.
883 DenseSet<Instruction *> Unhoistables(llvm::from_range, Selects);
884 // Remove Selects that can't be hoisted.
885 for (auto it = Selects.begin(); it != Selects.end(); ) {
886 SelectInst *SI = *it;
887 if (SI == InsertPoint) {
888 ++it;
889 continue;
890 }
891 DenseMap<Instruction *, bool> Visited;
892 bool IsHoistable = checkHoistValue(V: SI->getCondition(), InsertPoint,
893 DT, Unhoistables, HoistStops: nullptr, Visited);
894 if (!IsHoistable) {
895 CHR_DEBUG(dbgs() << "Dropping select " << *SI << "\n");
896 ORE.emit(RemarkBuilder: [&]() {
897 return OptimizationRemarkMissed(DEBUG_TYPE,
898 "DropUnhoistableSelect", SI)
899 << "Dropped unhoistable select";
900 });
901 it = Selects.erase(CI: it);
902 // Since we are dropping the select here, we also drop it from
903 // Unhoistables.
904 Unhoistables.erase(V: SI);
905 } else
906 ++it;
907 }
908 // Update InsertPoint after potentially removing selects.
909 InsertPoint = getBranchInsertPoint(RI);
910 CHR_DEBUG(dbgs() << "InsertPoint " << *InsertPoint << "\n");
911 if (RI.HasBranch && InsertPoint != Branch) {
912 DenseMap<Instruction *, bool> Visited;
913 bool IsHoistable = checkHoistValue(V: Branch->getCondition(), InsertPoint,
914 DT, Unhoistables, HoistStops: nullptr, Visited);
915 if (!IsHoistable) {
916 // If the branch isn't hoistable, drop the selects in the entry
917 // block, preferring the branch, which makes the branch the hoist
918 // point.
919 assert(InsertPoint != Branch && "Branch must not be the hoist point");
920 CHR_DEBUG(dbgs() << "Dropping selects in entry block \n");
921 CHR_DEBUG(
922 for (SelectInst *SI : Selects) {
923 dbgs() << "SI " << *SI << "\n";
924 });
925 for (SelectInst *SI : Selects) {
926 ORE.emit(RemarkBuilder: [&]() {
927 return OptimizationRemarkMissed(DEBUG_TYPE,
928 "DropSelectUnhoistableBranch", SI)
929 << "Dropped select due to unhoistable branch";
930 });
931 }
932 llvm::erase_if(C&: Selects, P: [EntryBB](SelectInst *SI) {
933 return SI->getParent() == EntryBB;
934 });
935 Unhoistables.clear();
936 InsertPoint = Branch;
937 }
938 }
939 CHR_DEBUG(dbgs() << "InsertPoint " << *InsertPoint << "\n");
940#ifndef NDEBUG
941 if (RI.HasBranch) {
942 assert(!DT.dominates(Branch, InsertPoint) &&
943 "Branch can't be already above the hoist point");
944 DenseMap<Instruction *, bool> Visited;
945 assert(checkHoistValue(Branch->getCondition(), InsertPoint,
946 DT, Unhoistables, nullptr, Visited) &&
947 "checkHoistValue for branch");
948 }
949 for (auto *SI : Selects) {
950 assert(!DT.dominates(SI, InsertPoint) &&
951 "SI can't be already above the hoist point");
952 DenseMap<Instruction *, bool> Visited;
953 assert(checkHoistValue(SI->getCondition(), InsertPoint, DT,
954 Unhoistables, nullptr, Visited) &&
955 "checkHoistValue for selects");
956 }
957 CHR_DEBUG(dbgs() << "Result\n");
958 if (RI.HasBranch) {
959 CHR_DEBUG(dbgs() << "BI " << *Branch << "\n");
960 }
961 for (auto *SI : Selects) {
962 CHR_DEBUG(dbgs() << "SI " << *SI << "\n");
963 }
964#endif
965 }
966}
967
968// Traverse the region tree, find all nested scopes and merge them if possible.
969CHRScope * CHR::findScopes(Region *R, Region *NextRegion, Region *ParentRegion,
970 SmallVectorImpl<CHRScope *> &Scopes) {
971 CHR_DEBUG(dbgs() << "findScopes " << R->getNameStr() << "\n");
972 CHRScope *Result = findScope(R);
973 // Visit subscopes.
974 CHRScope *ConsecutiveSubscope = nullptr;
975 SmallVector<CHRScope *, 8> Subscopes;
976 for (auto It = R->begin(); It != R->end(); ++It) {
977 const std::unique_ptr<Region> &SubR = *It;
978 auto NextIt = std::next(x: It);
979 Region *NextSubR = NextIt != R->end() ? NextIt->get() : nullptr;
980 CHR_DEBUG(dbgs() << "Looking at subregion " << SubR.get()->getNameStr()
981 << "\n");
982 CHRScope *SubCHRScope = findScopes(R: SubR.get(), NextRegion: NextSubR, ParentRegion: R, Scopes);
983 if (SubCHRScope) {
984 CHR_DEBUG(dbgs() << "Subregion Scope " << *SubCHRScope << "\n");
985 } else {
986 CHR_DEBUG(dbgs() << "Subregion Scope null\n");
987 }
988 if (SubCHRScope) {
989 if (!ConsecutiveSubscope)
990 ConsecutiveSubscope = SubCHRScope;
991 else if (!ConsecutiveSubscope->appendable(Next: SubCHRScope)) {
992 Subscopes.push_back(Elt: ConsecutiveSubscope);
993 ConsecutiveSubscope = SubCHRScope;
994 } else
995 ConsecutiveSubscope->append(Next: SubCHRScope);
996 } else {
997 if (ConsecutiveSubscope) {
998 Subscopes.push_back(Elt: ConsecutiveSubscope);
999 }
1000 ConsecutiveSubscope = nullptr;
1001 }
1002 }
1003 if (ConsecutiveSubscope) {
1004 Subscopes.push_back(Elt: ConsecutiveSubscope);
1005 }
1006 for (CHRScope *Sub : Subscopes) {
1007 if (Result) {
1008 // Combine it with the parent.
1009 Result->addSub(SubIn: Sub);
1010 } else {
1011 // Push Subscopes as they won't be combined with the parent.
1012 Scopes.push_back(Elt: Sub);
1013 }
1014 }
1015 return Result;
1016}
1017
1018static DenseSet<Value *> getCHRConditionValuesForRegion(RegInfo &RI) {
1019 DenseSet<Value *> ConditionValues;
1020 if (RI.HasBranch) {
1021 auto *BI = cast<CondBrInst>(Val: RI.R->getEntry()->getTerminator());
1022 ConditionValues.insert(V: BI->getCondition());
1023 }
1024 for (SelectInst *SI : RI.Selects) {
1025 ConditionValues.insert(V: SI->getCondition());
1026 }
1027 return ConditionValues;
1028}
1029
1030
1031// Determine whether to split a scope depending on the sets of the branch
1032// condition values of the previous region and the current region. We split
1033// (return true) it if 1) the condition values of the inner/lower scope can't be
1034// hoisted up to the outer/upper scope, or 2) the two sets of the condition
1035// values have an empty intersection (because the combined branch conditions
1036// won't probably lead to a simpler combined condition).
1037static bool shouldSplit(Instruction *InsertPoint,
1038 DenseSet<Value *> &PrevConditionValues,
1039 DenseSet<Value *> &ConditionValues,
1040 DominatorTree &DT,
1041 DenseSet<Instruction *> &Unhoistables) {
1042 assert(InsertPoint && "Null InsertPoint");
1043 CHR_DEBUG(
1044 dbgs() << "shouldSplit " << *InsertPoint << " PrevConditionValues ";
1045 for (Value *V : PrevConditionValues) {
1046 dbgs() << *V << ", ";
1047 }
1048 dbgs() << " ConditionValues ";
1049 for (Value *V : ConditionValues) {
1050 dbgs() << *V << ", ";
1051 }
1052 dbgs() << "\n");
1053 // If any of Bases isn't hoistable to the hoist point, split.
1054 for (Value *V : ConditionValues) {
1055 DenseMap<Instruction *, bool> Visited;
1056 if (!checkHoistValue(V, InsertPoint, DT, Unhoistables, HoistStops: nullptr, Visited)) {
1057 CHR_DEBUG(dbgs() << "Split. checkHoistValue false " << *V << "\n");
1058 return true; // Not hoistable, split.
1059 }
1060 }
1061 // If PrevConditionValues or ConditionValues is empty, don't split to avoid
1062 // unnecessary splits at scopes with no branch/selects. If
1063 // PrevConditionValues and ConditionValues don't intersect at all, split.
1064 if (!PrevConditionValues.empty() && !ConditionValues.empty()) {
1065 // Use std::set as DenseSet doesn't work with set_intersection.
1066 std::set<Value *> PrevBases, Bases;
1067 DenseMap<Value *, std::set<Value *>> Visited;
1068 for (Value *V : PrevConditionValues) {
1069 const std::set<Value *> &BaseValues = getBaseValues(V, DT, Visited);
1070 PrevBases.insert(first: BaseValues.begin(), last: BaseValues.end());
1071 }
1072 for (Value *V : ConditionValues) {
1073 const std::set<Value *> &BaseValues = getBaseValues(V, DT, Visited);
1074 Bases.insert(first: BaseValues.begin(), last: BaseValues.end());
1075 }
1076 CHR_DEBUG(
1077 dbgs() << "PrevBases ";
1078 for (Value *V : PrevBases) {
1079 dbgs() << *V << ", ";
1080 }
1081 dbgs() << " Bases ";
1082 for (Value *V : Bases) {
1083 dbgs() << *V << ", ";
1084 }
1085 dbgs() << "\n");
1086 std::vector<Value *> Intersection;
1087 std::set_intersection(first1: PrevBases.begin(), last1: PrevBases.end(), first2: Bases.begin(),
1088 last2: Bases.end(), result: std::back_inserter(x&: Intersection));
1089 if (Intersection.empty()) {
1090 // Empty intersection, split.
1091 CHR_DEBUG(dbgs() << "Split. Intersection empty\n");
1092 return true;
1093 }
1094 }
1095 CHR_DEBUG(dbgs() << "No split\n");
1096 return false; // Don't split.
1097}
1098
1099static void getSelectsInScope(CHRScope *Scope,
1100 DenseSet<Instruction *> &Output) {
1101 for (RegInfo &RI : Scope->RegInfos)
1102 Output.insert_range(R&: RI.Selects);
1103 for (CHRScope *Sub : Scope->Subs)
1104 getSelectsInScope(Scope: Sub, Output);
1105}
1106
1107void CHR::splitScopes(SmallVectorImpl<CHRScope *> &Input,
1108 SmallVectorImpl<CHRScope *> &Output) {
1109 for (CHRScope *Scope : Input) {
1110 assert(!Scope->BranchInsertPoint &&
1111 "BranchInsertPoint must not be set");
1112 DenseSet<Instruction *> Unhoistables;
1113 getSelectsInScope(Scope, Output&: Unhoistables);
1114 splitScope(Scope, Outer: nullptr, OuterConditionValues: nullptr, OuterInsertPoint: nullptr, Output, Unhoistables);
1115 }
1116#ifndef NDEBUG
1117 for (CHRScope *Scope : Output) {
1118 assert(Scope->BranchInsertPoint && "BranchInsertPoint must be set");
1119 }
1120#endif
1121}
1122
1123SmallVector<CHRScope *, 8> CHR::splitScope(
1124 CHRScope *Scope,
1125 CHRScope *Outer,
1126 DenseSet<Value *> *OuterConditionValues,
1127 Instruction *OuterInsertPoint,
1128 SmallVectorImpl<CHRScope *> &Output,
1129 DenseSet<Instruction *> &Unhoistables) {
1130 if (Outer) {
1131 assert(OuterConditionValues && "Null OuterConditionValues");
1132 assert(OuterInsertPoint && "Null OuterInsertPoint");
1133 }
1134 bool PrevSplitFromOuter = true;
1135 DenseSet<Value *> PrevConditionValues;
1136 Instruction *PrevInsertPoint = nullptr;
1137 SmallVector<CHRScope *, 8> Splits;
1138 SmallVector<bool, 8> SplitsSplitFromOuter;
1139 SmallVector<DenseSet<Value *>, 8> SplitsConditionValues;
1140 SmallVector<Instruction *, 8> SplitsInsertPoints;
1141 SmallVector<RegInfo, 8> RegInfos(Scope->RegInfos); // Copy
1142 for (RegInfo &RI : RegInfos) {
1143 Instruction *InsertPoint = getBranchInsertPoint(RI);
1144 DenseSet<Value *> ConditionValues = getCHRConditionValuesForRegion(RI);
1145 CHR_DEBUG(
1146 dbgs() << "ConditionValues ";
1147 for (Value *V : ConditionValues) {
1148 dbgs() << *V << ", ";
1149 }
1150 dbgs() << "\n");
1151 if (RI.R == RegInfos[0].R) {
1152 // First iteration. Check to see if we should split from the outer.
1153 if (Outer) {
1154 CHR_DEBUG(dbgs() << "Outer " << *Outer << "\n");
1155 CHR_DEBUG(dbgs() << "Should split from outer at "
1156 << RI.R->getNameStr() << "\n");
1157 if (shouldSplit(InsertPoint: OuterInsertPoint, PrevConditionValues&: *OuterConditionValues,
1158 ConditionValues, DT, Unhoistables)) {
1159 PrevConditionValues = ConditionValues;
1160 PrevInsertPoint = InsertPoint;
1161 ORE.emit(RemarkBuilder: [&]() {
1162 return OptimizationRemarkMissed(DEBUG_TYPE,
1163 "SplitScopeFromOuter",
1164 RI.R->getEntry()->getTerminator())
1165 << "Split scope from outer due to unhoistable branch/select "
1166 << "and/or lack of common condition values";
1167 });
1168 } else {
1169 // Not splitting from the outer. Use the outer bases and insert
1170 // point. Union the bases.
1171 PrevSplitFromOuter = false;
1172 PrevConditionValues = *OuterConditionValues;
1173 PrevConditionValues.insert_range(R&: ConditionValues);
1174 PrevInsertPoint = OuterInsertPoint;
1175 }
1176 } else {
1177 CHR_DEBUG(dbgs() << "Outer null\n");
1178 PrevConditionValues = ConditionValues;
1179 PrevInsertPoint = InsertPoint;
1180 }
1181 } else {
1182 CHR_DEBUG(dbgs() << "Should split from prev at "
1183 << RI.R->getNameStr() << "\n");
1184 if (shouldSplit(InsertPoint: PrevInsertPoint, PrevConditionValues, ConditionValues,
1185 DT, Unhoistables)) {
1186 CHRScope *Tail = Scope->split(Boundary: RI.R);
1187 Scopes.insert(V: Tail);
1188 Splits.push_back(Elt: Scope);
1189 SplitsSplitFromOuter.push_back(Elt: PrevSplitFromOuter);
1190 SplitsConditionValues.push_back(Elt: PrevConditionValues);
1191 SplitsInsertPoints.push_back(Elt: PrevInsertPoint);
1192 Scope = Tail;
1193 PrevConditionValues = ConditionValues;
1194 PrevInsertPoint = InsertPoint;
1195 PrevSplitFromOuter = true;
1196 ORE.emit(RemarkBuilder: [&]() {
1197 return OptimizationRemarkMissed(DEBUG_TYPE,
1198 "SplitScopeFromPrev",
1199 RI.R->getEntry()->getTerminator())
1200 << "Split scope from previous due to unhoistable branch/select "
1201 << "and/or lack of common condition values";
1202 });
1203 } else {
1204 // Not splitting. Union the bases. Keep the hoist point.
1205 PrevConditionValues.insert_range(R&: ConditionValues);
1206 }
1207 }
1208 }
1209 Splits.push_back(Elt: Scope);
1210 SplitsSplitFromOuter.push_back(Elt: PrevSplitFromOuter);
1211 SplitsConditionValues.push_back(Elt: PrevConditionValues);
1212 assert(PrevInsertPoint && "Null PrevInsertPoint");
1213 SplitsInsertPoints.push_back(Elt: PrevInsertPoint);
1214 assert(Splits.size() == SplitsConditionValues.size() &&
1215 Splits.size() == SplitsSplitFromOuter.size() &&
1216 Splits.size() == SplitsInsertPoints.size() && "Mismatching sizes");
1217 for (size_t I = 0; I < Splits.size(); ++I) {
1218 CHRScope *Split = Splits[I];
1219 DenseSet<Value *> &SplitConditionValues = SplitsConditionValues[I];
1220 Instruction *SplitInsertPoint = SplitsInsertPoints[I];
1221 SmallVector<CHRScope *, 8> NewSubs;
1222 DenseSet<Instruction *> SplitUnhoistables;
1223 getSelectsInScope(Scope: Split, Output&: SplitUnhoistables);
1224 for (CHRScope *Sub : Split->Subs) {
1225 SmallVector<CHRScope *, 8> SubSplits = splitScope(
1226 Scope: Sub, Outer: Split, OuterConditionValues: &SplitConditionValues, OuterInsertPoint: SplitInsertPoint, Output,
1227 Unhoistables&: SplitUnhoistables);
1228 llvm::append_range(C&: NewSubs, R&: SubSplits);
1229 }
1230 Split->Subs = NewSubs;
1231 }
1232 SmallVector<CHRScope *, 8> Result;
1233 for (size_t I = 0; I < Splits.size(); ++I) {
1234 CHRScope *Split = Splits[I];
1235 if (SplitsSplitFromOuter[I]) {
1236 // Split from the outer.
1237 Output.push_back(Elt: Split);
1238 Split->BranchInsertPoint = SplitsInsertPoints[I];
1239 CHR_DEBUG(dbgs() << "BranchInsertPoint " << *SplitsInsertPoints[I]
1240 << "\n");
1241 } else {
1242 // Connected to the outer.
1243 Result.push_back(Elt: Split);
1244 }
1245 }
1246 if (!Outer)
1247 assert(Result.empty() &&
1248 "If no outer (top-level), must return no nested ones");
1249 return Result;
1250}
1251
1252void CHR::classifyBiasedScopes(SmallVectorImpl<CHRScope *> &Scopes) {
1253 for (CHRScope *Scope : Scopes) {
1254 assert(Scope->TrueBiasedRegions.empty() && Scope->FalseBiasedRegions.empty() && "Empty");
1255 classifyBiasedScopes(Scope, OutermostScope: Scope);
1256 CHR_DEBUG(
1257 dbgs() << "classifyBiasedScopes " << *Scope << "\n";
1258 dbgs() << "TrueBiasedRegions ";
1259 for (Region *R : Scope->TrueBiasedRegions) {
1260 dbgs() << R->getNameStr() << ", ";
1261 }
1262 dbgs() << "\n";
1263 dbgs() << "FalseBiasedRegions ";
1264 for (Region *R : Scope->FalseBiasedRegions) {
1265 dbgs() << R->getNameStr() << ", ";
1266 }
1267 dbgs() << "\n";
1268 dbgs() << "TrueBiasedSelects ";
1269 for (SelectInst *SI : Scope->TrueBiasedSelects) {
1270 dbgs() << *SI << ", ";
1271 }
1272 dbgs() << "\n";
1273 dbgs() << "FalseBiasedSelects ";
1274 for (SelectInst *SI : Scope->FalseBiasedSelects) {
1275 dbgs() << *SI << ", ";
1276 }
1277 dbgs() << "\n";);
1278 }
1279}
1280
1281void CHR::classifyBiasedScopes(CHRScope *Scope, CHRScope *OutermostScope) {
1282 for (RegInfo &RI : Scope->RegInfos) {
1283 if (RI.HasBranch) {
1284 Region *R = RI.R;
1285 if (TrueBiasedRegionsGlobal.contains(V: R))
1286 OutermostScope->TrueBiasedRegions.insert(V: R);
1287 else if (FalseBiasedRegionsGlobal.contains(V: R))
1288 OutermostScope->FalseBiasedRegions.insert(V: R);
1289 else
1290 llvm_unreachable("Must be biased");
1291 }
1292 for (SelectInst *SI : RI.Selects) {
1293 if (TrueBiasedSelectsGlobal.contains(V: SI))
1294 OutermostScope->TrueBiasedSelects.insert(V: SI);
1295 else if (FalseBiasedSelectsGlobal.contains(V: SI))
1296 OutermostScope->FalseBiasedSelects.insert(V: SI);
1297 else
1298 llvm_unreachable("Must be biased");
1299 }
1300 }
1301 for (CHRScope *Sub : Scope->Subs) {
1302 classifyBiasedScopes(Scope: Sub, OutermostScope);
1303 }
1304}
1305
1306static bool hasAtLeastTwoBiasedBranches(const InstrumentationOptions &Opts,
1307 CHRScope *Scope) {
1308 unsigned NumBiased = Scope->TrueBiasedRegions.size() +
1309 Scope->FalseBiasedRegions.size() +
1310 Scope->TrueBiasedSelects.size() +
1311 Scope->FalseBiasedSelects.size();
1312 return NumBiased >= Opts.chr_merge_threshold;
1313}
1314
1315void CHR::filterScopes(SmallVectorImpl<CHRScope *> &Input,
1316 SmallVectorImpl<CHRScope *> &Output) {
1317 for (CHRScope *Scope : Input) {
1318 // Filter out the ones with only one region and no subs.
1319 if (!hasAtLeastTwoBiasedBranches(Opts, Scope)) {
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(RemarkBuilder: [&]() {
1326 return OptimizationRemarkMissed(
1327 DEBUG_TYPE, "DropScopeWithOneBranchOrSelect",
1328 Scope->RegInfos[0].R->getEntry()->getTerminator())
1329 << "Drop scope with < "
1330 << ore::NV("CHRMergeThreshold", Opts.chr_merge_threshold)
1331 << " biased branch(es) or select(s)";
1332 });
1333 continue;
1334 }
1335 Output.push_back(Elt: Scope);
1336 }
1337}
1338
1339void CHR::setCHRRegions(SmallVectorImpl<CHRScope *> &Input,
1340 SmallVectorImpl<CHRScope *> &Output) {
1341 for (CHRScope *Scope : Input) {
1342 assert(Scope->HoistStopMap.empty() && Scope->CHRRegions.empty() &&
1343 "Empty");
1344 setCHRRegions(Scope, OutermostScope: Scope);
1345 Output.push_back(Elt: Scope);
1346 CHR_DEBUG(
1347 dbgs() << "setCHRRegions HoistStopMap " << *Scope << "\n";
1348 for (auto pair : Scope->HoistStopMap) {
1349 Region *R = pair.first;
1350 dbgs() << "Region " << R->getNameStr() << "\n";
1351 for (Instruction *I : pair.second) {
1352 dbgs() << "HoistStop " << *I << "\n";
1353 }
1354 }
1355 dbgs() << "CHRRegions" << "\n";
1356 for (RegInfo &RI : Scope->CHRRegions) {
1357 dbgs() << RI.R->getNameStr() << "\n";
1358 });
1359 }
1360}
1361
1362void CHR::setCHRRegions(CHRScope *Scope, CHRScope *OutermostScope) {
1363 DenseSet<Instruction *> Unhoistables;
1364 // Put the biased selects in Unhoistables because they should stay where they
1365 // are and constant-folded after CHR (in case one biased select or a branch
1366 // can depend on another biased select.)
1367 for (RegInfo &RI : Scope->RegInfos)
1368 Unhoistables.insert_range(R&: RI.Selects);
1369 Instruction *InsertPoint = OutermostScope->BranchInsertPoint;
1370 for (RegInfo &RI : Scope->RegInfos) {
1371 Region *R = RI.R;
1372 DenseSet<Instruction *> HoistStops;
1373 bool IsHoisted = false;
1374 if (RI.HasBranch) {
1375 assert((OutermostScope->TrueBiasedRegions.contains(R) ||
1376 OutermostScope->FalseBiasedRegions.contains(R)) &&
1377 "Must be truthy or falsy");
1378 auto *BI = cast<CondBrInst>(Val: R->getEntry()->getTerminator());
1379 // Note checkHoistValue fills in HoistStops.
1380 DenseMap<Instruction *, bool> Visited;
1381 bool IsHoistable = checkHoistValue(V: BI->getCondition(), InsertPoint, DT,
1382 Unhoistables, HoistStops: &HoistStops, Visited);
1383 assert(IsHoistable && "Must be hoistable");
1384 (void)(IsHoistable); // Unused in release build
1385 IsHoisted = true;
1386 }
1387 for (SelectInst *SI : RI.Selects) {
1388 assert((OutermostScope->TrueBiasedSelects.contains(SI) ||
1389 OutermostScope->FalseBiasedSelects.contains(SI)) &&
1390 "Must be true or false biased");
1391 // Note checkHoistValue fills in HoistStops.
1392 DenseMap<Instruction *, bool> Visited;
1393 bool IsHoistable = checkHoistValue(V: SI->getCondition(), InsertPoint, DT,
1394 Unhoistables, HoistStops: &HoistStops, Visited);
1395 assert(IsHoistable && "Must be hoistable");
1396 (void)(IsHoistable); // Unused in release build
1397 IsHoisted = true;
1398 }
1399 if (IsHoisted) {
1400 OutermostScope->CHRRegions.push_back(Elt: RI);
1401 OutermostScope->HoistStopMap[R] = HoistStops;
1402 }
1403 }
1404 for (CHRScope *Sub : Scope->Subs)
1405 setCHRRegions(Scope: Sub, OutermostScope);
1406}
1407
1408static bool CHRScopeSorter(CHRScope *Scope1, CHRScope *Scope2) {
1409 return Scope1->RegInfos[0].R->getDepth() < Scope2->RegInfos[0].R->getDepth();
1410}
1411
1412void CHR::sortScopes(SmallVectorImpl<CHRScope *> &Input,
1413 SmallVectorImpl<CHRScope *> &Output) {
1414 Output.resize(N: Input.size());
1415 llvm::copy(Range&: Input, Out: Output.begin());
1416 llvm::stable_sort(Range&: Output, C: CHRScopeSorter);
1417}
1418
1419// Return true if V is already hoisted or was hoisted (along with its operands)
1420// to the insert point.
1421static void hoistValue(Value *V, Instruction *HoistPoint, Region *R,
1422 HoistStopMapTy &HoistStopMap,
1423 DenseSet<Instruction *> &HoistedSet,
1424 DenseSet<PHINode *> &TrivialPHIs,
1425 DominatorTree &DT) {
1426 auto IT = HoistStopMap.find(Val: R);
1427 assert(IT != HoistStopMap.end() && "Region must be in hoist stop map");
1428 DenseSet<Instruction *> &HoistStops = IT->second;
1429 if (auto *I = dyn_cast<Instruction>(Val: V)) {
1430 if (I == HoistPoint)
1431 return;
1432 if (HoistStops.count(V: I))
1433 return;
1434 if (auto *PN = dyn_cast<PHINode>(Val: I))
1435 if (TrivialPHIs.count(V: PN))
1436 // The trivial phi inserted by the previous CHR scope could replace a
1437 // non-phi in HoistStops. Note that since this phi is at the exit of a
1438 // previous CHR scope, which dominates this scope, it's safe to stop
1439 // hoisting there.
1440 return;
1441 if (HoistedSet.count(V: I))
1442 // Already hoisted, return.
1443 return;
1444 assert(isHoistableInstructionType(I) && "Unhoistable instruction type");
1445 assert(DT.getNode(I->getParent()) && "DT must contain I's block");
1446 assert(DT.getNode(HoistPoint->getParent()) &&
1447 "DT must contain HoistPoint block");
1448 if (DT.dominates(Def: I, User: HoistPoint))
1449 // We are already above the hoist point. Stop here. This may be necessary
1450 // when multiple scopes would independently hoist the same
1451 // instruction. Since an outer (dominating) scope would hoist it to its
1452 // entry before an inner (dominated) scope would to its entry, the inner
1453 // scope may see the instruction already hoisted, in which case it
1454 // potentially wrong for the inner scope to hoist it and could cause bad
1455 // IR (non-dominating def), but safe to skip hoisting it instead because
1456 // it's already in a block that dominates the inner scope.
1457 return;
1458 for (Value *Op : I->operands()) {
1459 hoistValue(V: Op, HoistPoint, R, HoistStopMap, HoistedSet, TrivialPHIs, DT);
1460 }
1461 I->moveBefore(InsertPos: HoistPoint->getIterator());
1462 HoistedSet.insert(V: I);
1463 CHR_DEBUG(dbgs() << "hoistValue " << *I << "\n");
1464 }
1465}
1466
1467// Hoist the dependent condition values of the branches and the selects in the
1468// scope to the insert point.
1469static void hoistScopeConditions(CHRScope *Scope, Instruction *HoistPoint,
1470 DenseSet<PHINode *> &TrivialPHIs,
1471 DominatorTree &DT) {
1472 DenseSet<Instruction *> HoistedSet;
1473 for (const RegInfo &RI : Scope->CHRRegions) {
1474 Region *R = RI.R;
1475 bool IsTrueBiased = Scope->TrueBiasedRegions.count(V: R);
1476 bool IsFalseBiased = Scope->FalseBiasedRegions.count(V: R);
1477 if (RI.HasBranch && (IsTrueBiased || IsFalseBiased)) {
1478 auto *BI = cast<CondBrInst>(Val: R->getEntry()->getTerminator());
1479 hoistValue(V: BI->getCondition(), HoistPoint, R, HoistStopMap&: Scope->HoistStopMap,
1480 HoistedSet, TrivialPHIs, DT);
1481 }
1482 for (SelectInst *SI : RI.Selects) {
1483 bool IsTrueBiased = Scope->TrueBiasedSelects.count(V: SI);
1484 bool IsFalseBiased = Scope->FalseBiasedSelects.count(V: SI);
1485 if (!(IsTrueBiased || IsFalseBiased))
1486 continue;
1487 hoistValue(V: SI->getCondition(), HoistPoint, R, HoistStopMap&: Scope->HoistStopMap,
1488 HoistedSet, TrivialPHIs, DT);
1489 }
1490 }
1491}
1492
1493// Negate the predicate if an ICmp if it's used only by branches or selects by
1494// swapping the operands of the branches or the selects. Returns true if success.
1495static bool negateICmpIfUsedByBranchOrSelectOnly(ICmpInst *ICmp,
1496 Instruction *ExcludedUser,
1497 CHRScope *Scope) {
1498 for (User *U : ICmp->users()) {
1499 if (U == ExcludedUser)
1500 continue;
1501 if (isa<CondBrInst>(Val: U))
1502 continue;
1503 if (isa<SelectInst>(Val: U) && cast<SelectInst>(Val: U)->getCondition() == ICmp)
1504 continue;
1505 return false;
1506 }
1507 for (User *U : ICmp->users()) {
1508 if (U == ExcludedUser)
1509 continue;
1510 if (auto *BI = dyn_cast<CondBrInst>(Val: U)) {
1511 BI->swapSuccessors();
1512 // Don't need to swap this in terms of
1513 // TrueBiasedRegions/FalseBiasedRegions because true-based/false-based
1514 // mean whether the branch is likely go into the if-then rather than
1515 // successor0/successor1 and because we can tell which edge is the then or
1516 // the else one by comparing the destination to the region exit block.
1517 continue;
1518 }
1519 if (auto *SI = dyn_cast<SelectInst>(Val: U)) {
1520 // Swap operands
1521 SI->swapValues();
1522 SI->swapProfMetadata();
1523 if (Scope->TrueBiasedSelects.count(V: SI)) {
1524 assert(!Scope->FalseBiasedSelects.contains(SI) &&
1525 "Must not be already in");
1526 Scope->FalseBiasedSelects.insert(V: SI);
1527 } else if (Scope->FalseBiasedSelects.count(V: SI)) {
1528 assert(!Scope->TrueBiasedSelects.contains(SI) &&
1529 "Must not be already in");
1530 Scope->TrueBiasedSelects.insert(V: SI);
1531 }
1532 continue;
1533 }
1534 llvm_unreachable("Must be a branch or a select");
1535 }
1536 ICmp->setPredicate(CmpInst::getInversePredicate(pred: ICmp->getPredicate()));
1537 return true;
1538}
1539
1540// A helper for transformScopes. Insert a trivial phi at the scope exit block
1541// for a value that's defined in the scope but used outside it (meaning it's
1542// alive at the exit block).
1543static void insertTrivialPHIs(CHRScope *Scope,
1544 BasicBlock *EntryBlock, BasicBlock *ExitBlock,
1545 DenseSet<PHINode *> &TrivialPHIs) {
1546 SmallSetVector<BasicBlock *, 8> BlocksInScope;
1547 for (RegInfo &RI : Scope->RegInfos) {
1548 for (BasicBlock *BB : RI.R->blocks()) { // This includes the blocks in the
1549 // sub-Scopes.
1550 BlocksInScope.insert(X: BB);
1551 }
1552 }
1553 CHR_DEBUG({
1554 dbgs() << "Inserting redundant phis\n";
1555 for (BasicBlock *BB : BlocksInScope)
1556 dbgs() << "BlockInScope " << BB->getName() << "\n";
1557 });
1558 for (BasicBlock *BB : BlocksInScope) {
1559 for (Instruction &I : *BB) {
1560 SmallVector<Instruction *, 8> Users;
1561 for (User *U : I.users()) {
1562 if (auto *UI = dyn_cast<Instruction>(Val: U)) {
1563 if (!BlocksInScope.contains(key: UI->getParent()) &&
1564 // Unless there's already a phi for I at the exit block.
1565 !(isa<PHINode>(Val: UI) && UI->getParent() == ExitBlock)) {
1566 CHR_DEBUG(dbgs() << "V " << I << "\n");
1567 CHR_DEBUG(dbgs() << "Used outside scope by user " << *UI << "\n");
1568 Users.push_back(Elt: UI);
1569 } else if (UI->getParent() == EntryBlock && isa<PHINode>(Val: UI)) {
1570 // There's a loop backedge from a block that's dominated by this
1571 // scope to the entry block.
1572 CHR_DEBUG(dbgs() << "V " << I << "\n");
1573 CHR_DEBUG(dbgs()
1574 << "Used at entry block (for a back edge) by a phi user "
1575 << *UI << "\n");
1576 Users.push_back(Elt: UI);
1577 }
1578 }
1579 }
1580 if (Users.size() > 0) {
1581 // Insert a trivial phi for I (phi [&I, P0], [&I, P1], ...) at
1582 // ExitBlock. Replace I with the new phi in UI unless UI is another
1583 // phi at ExitBlock.
1584 PHINode *PN = PHINode::Create(Ty: I.getType(), NumReservedValues: pred_size(BB: ExitBlock), NameStr: "");
1585 PN->insertBefore(InsertPos: ExitBlock->begin());
1586 for (BasicBlock *Pred : predecessors(BB: ExitBlock)) {
1587 PN->addIncoming(V: &I, BB: Pred);
1588 }
1589 TrivialPHIs.insert(V: PN);
1590 CHR_DEBUG(dbgs() << "Insert phi " << *PN << "\n");
1591 bool FoundLifetimeAnnotation = false;
1592 for (Instruction *UI : Users) {
1593 // If we found a lifetime annotation, remove it, but set a flag
1594 // to ensure that we remove all other lifetime annotations attached
1595 // to the alloca.
1596 if (UI->isLifetimeStartOrEnd()) {
1597 UI->eraseFromParent();
1598 FoundLifetimeAnnotation = true;
1599 continue;
1600 }
1601 for (unsigned J = 0, NumOps = UI->getNumOperands(); J < NumOps; ++J) {
1602 if (UI->getOperand(i: J) == &I) {
1603 UI->setOperand(i: J, Val: PN);
1604 }
1605 }
1606 CHR_DEBUG(dbgs() << "Updated user " << *UI << "\n");
1607 }
1608 // Erase any leftover lifetime annotations for a dynamic alloca.
1609 if (FoundLifetimeAnnotation) {
1610 for (User *U : make_early_inc_range(Range: I.users())) {
1611 if (auto *UI = dyn_cast<Instruction>(Val: U))
1612 if (UI->isLifetimeStartOrEnd())
1613 UI->eraseFromParent();
1614 }
1615 }
1616 }
1617 }
1618 }
1619}
1620
1621// Assert that all the CHR regions of the scope have a biased branch or select.
1622[[maybe_unused]] static void
1623assertCHRRegionsHaveBiasedBranchOrSelect(CHRScope *Scope) {
1624#ifndef NDEBUG
1625 auto HasBiasedBranchOrSelect = [](RegInfo &RI, CHRScope *Scope) {
1626 if (Scope->TrueBiasedRegions.count(RI.R) ||
1627 Scope->FalseBiasedRegions.count(RI.R))
1628 return true;
1629 for (SelectInst *SI : RI.Selects)
1630 if (Scope->TrueBiasedSelects.count(SI) ||
1631 Scope->FalseBiasedSelects.count(SI))
1632 return true;
1633 return false;
1634 };
1635 for (RegInfo &RI : Scope->CHRRegions) {
1636 assert(HasBiasedBranchOrSelect(RI, Scope) &&
1637 "Must have biased branch or select");
1638 }
1639#endif
1640}
1641
1642// Assert that all the condition values of the biased branches and selects have
1643// been hoisted to the pre-entry block or outside of the scope.
1644[[maybe_unused]] static void
1645assertBranchOrSelectConditionHoisted(CHRScope *Scope,
1646 BasicBlock *PreEntryBlock) {
1647 CHR_DEBUG(dbgs() << "Biased regions condition values \n");
1648 for (RegInfo &RI : Scope->CHRRegions) {
1649 Region *R = RI.R;
1650 bool IsTrueBiased = Scope->TrueBiasedRegions.count(V: R);
1651 bool IsFalseBiased = Scope->FalseBiasedRegions.count(V: R);
1652 if (RI.HasBranch && (IsTrueBiased || IsFalseBiased)) {
1653 auto *BI = cast<CondBrInst>(Val: R->getEntry()->getTerminator());
1654 Value *V = BI->getCondition();
1655 CHR_DEBUG(dbgs() << *V << "\n");
1656 if (auto *I = dyn_cast<Instruction>(Val: V)) {
1657 (void)(I); // Unused in release build.
1658 assert((I->getParent() == PreEntryBlock ||
1659 !Scope->contains(I)) &&
1660 "Must have been hoisted to PreEntryBlock or outside the scope");
1661 }
1662 }
1663 for (SelectInst *SI : RI.Selects) {
1664 bool IsTrueBiased = Scope->TrueBiasedSelects.count(V: SI);
1665 bool IsFalseBiased = Scope->FalseBiasedSelects.count(V: SI);
1666 if (!(IsTrueBiased || IsFalseBiased))
1667 continue;
1668 Value *V = SI->getCondition();
1669 CHR_DEBUG(dbgs() << *V << "\n");
1670 if (auto *I = dyn_cast<Instruction>(Val: V)) {
1671 (void)(I); // Unused in release build.
1672 assert((I->getParent() == PreEntryBlock ||
1673 !Scope->contains(I)) &&
1674 "Must have been hoisted to PreEntryBlock or outside the scope");
1675 }
1676 }
1677 }
1678}
1679
1680void CHR::transformScopes(CHRScope *Scope, DenseSet<PHINode *> &TrivialPHIs) {
1681 CHR_DEBUG(dbgs() << "transformScopes " << *Scope << "\n");
1682
1683 assert(Scope->RegInfos.size() >= 1 && "Should have at least one Region");
1684
1685 // An outer scope may have hoisted one of our selects out of this scope.
1686 // It can no longer be specialized under this scope's merged branch, and
1687 // may also be the cached branch insertion point.
1688 // TODO: Add inner selects to Unhoistables to avoid hoisting them out of
1689 // their scopes and allow those scopes to be transformed.
1690 for (const RegInfo &RI : Scope->CHRRegions)
1691 for (SelectInst *SI : RI.Selects)
1692 if (!Scope->contains(I: SI))
1693 return;
1694
1695 for (RegInfo &RI : Scope->RegInfos) {
1696 const Region *R = RI.R;
1697 unsigned Duplication = getRegionDuplicationCount(R);
1698 CHR_DEBUG(dbgs() << "Dup count for R=" << R << " is " << Duplication
1699 << "\n");
1700 if (Duplication >= Opts.chr_dup_threshold) {
1701 CHR_DEBUG(dbgs() << "Reached the dup threshold of " << Duplication
1702 << " for this region");
1703 ORE.emit(RemarkBuilder: [&]() {
1704 return OptimizationRemarkMissed(DEBUG_TYPE, "DupThresholdReached",
1705 R->getEntry()->getTerminator())
1706 << "Reached the duplication threshold for the region";
1707 });
1708 return;
1709 }
1710 }
1711 for (RegInfo &RI : Scope->RegInfos) {
1712 DuplicationCount[RI.R]++;
1713 }
1714
1715 Region *FirstRegion = Scope->RegInfos[0].R;
1716 BasicBlock *EntryBlock = FirstRegion->getEntry();
1717 Region *LastRegion = Scope->RegInfos[Scope->RegInfos.size() - 1].R;
1718 BasicBlock *ExitBlock = LastRegion->getExit();
1719 std::optional<uint64_t> ProfileCount = BFI.getBlockProfileCount(BB: EntryBlock);
1720
1721 SmallVector<AllocaInst *> StaticAllocas;
1722 for (Instruction &I : *EntryBlock) {
1723 if (auto *AI = dyn_cast<AllocaInst>(Val: &I)) {
1724 if (AI->isStaticAlloca())
1725 StaticAllocas.push_back(Elt: AI);
1726 }
1727 }
1728
1729 // Split the entry block of the first region. The new block becomes the new
1730 // entry block of the first region. The old entry block becomes the block to
1731 // insert the CHR branch into. Note DT gets updated. Since DT gets updated
1732 // through the split, we update the entry of the first region after the split,
1733 // and Region only points to the entry and the exit blocks, rather than
1734 // keeping everything in a list or set, the blocks membership and the
1735 // entry/exit blocks of the region are still valid after the split.
1736 CHR_DEBUG(dbgs() << "Splitting entry block " << EntryBlock->getName()
1737 << " at " << *Scope->BranchInsertPoint << "\n");
1738 BasicBlock *NewEntryBlock =
1739 SplitBlock(Old: EntryBlock, SplitPt: Scope->BranchInsertPoint, DT: &DT);
1740 assert(NewEntryBlock->getSinglePredecessor() == EntryBlock &&
1741 "NewEntryBlock's only pred must be EntryBlock");
1742 FirstRegion->replaceEntryRecursive(NewEntry: NewEntryBlock);
1743 BasicBlock *PreEntryBlock = EntryBlock;
1744
1745 // Move static allocas into the pre-entry block so they stay static.
1746 for (AllocaInst *AI : StaticAllocas)
1747 AI->moveBefore(InsertPos: EntryBlock->begin());
1748
1749 if (ExitBlock) {
1750 // Insert a trivial phi at the exit block (where the CHR hot path and the
1751 // cold path merges) for a value that's defined in the scope but used
1752 // outside it (meaning it's alive at the exit block). We will add the
1753 // incoming values for the CHR cold paths to it below. Without this, we'd
1754 // miss updating phi's for such values unless there happens to already be a
1755 // phi for that value there.
1756 insertTrivialPHIs(Scope, EntryBlock, ExitBlock, TrivialPHIs);
1757 }
1758
1759 ValueToValueMapTy VMap;
1760 // Clone the blocks in the scope (excluding the PreEntryBlock) to split into a
1761 // hot path (originals) and a cold path (clones) and update the PHIs at the
1762 // exit block.
1763 cloneScopeBlocks(Scope, PreEntryBlock, ExitBlock, LastRegion, VMap);
1764
1765 // Replace the old (placeholder) branch with the new (merged) conditional
1766 // branch.
1767 CondBrInst *MergedBr =
1768 createMergedBranch(PreEntryBlock, EntryBlock, NewEntryBlock, VMap);
1769
1770#ifndef NDEBUG
1771 assertCHRRegionsHaveBiasedBranchOrSelect(Scope);
1772#endif
1773
1774 // Hoist the conditional values of the branches/selects.
1775 hoistScopeConditions(Scope, HoistPoint: PreEntryBlock->getTerminator(), TrivialPHIs, DT);
1776
1777#ifndef NDEBUG
1778 assertBranchOrSelectConditionHoisted(Scope, PreEntryBlock);
1779#endif
1780
1781 // Create the combined branch condition and constant-fold the branches/selects
1782 // in the hot path.
1783 fixupBranchesAndSelects(Scope, PreEntryBlock, MergedBR: MergedBr,
1784 ProfileCount: ProfileCount.value_or(u: 0));
1785}
1786
1787// A helper for transformScopes. Clone the blocks in the scope (excluding the
1788// PreEntryBlock) to split into a hot path and a cold path and update the PHIs
1789// at the exit block.
1790void CHR::cloneScopeBlocks(CHRScope *Scope,
1791 BasicBlock *PreEntryBlock,
1792 BasicBlock *ExitBlock,
1793 Region *LastRegion,
1794 ValueToValueMapTy &VMap) {
1795 // Clone all the blocks. The original blocks will be the hot-path
1796 // CHR-optimized code and the cloned blocks will be the original unoptimized
1797 // code. This is so that the block pointers from the
1798 // CHRScope/Region/RegionInfo can stay valid in pointing to the hot-path code
1799 // which CHR should apply to.
1800 SmallVector<BasicBlock*, 8> NewBlocks;
1801 for (RegInfo &RI : Scope->RegInfos)
1802 for (BasicBlock *BB : RI.R->blocks()) { // This includes the blocks in the
1803 // sub-Scopes.
1804 assert(BB != PreEntryBlock && "Don't copy the preetntry block");
1805 BasicBlock *NewBB = CloneBasicBlock(BB, VMap, NameSuffix: ".nonchr", F: &F);
1806 NewBlocks.push_back(Elt: NewBB);
1807 VMap[BB] = NewBB;
1808
1809 // Unreachable predecessors will not be cloned and will not have an edge
1810 // to the cloned block. As such, also remove them from any phi nodes.
1811 for (PHINode &PN : make_early_inc_range(Range: NewBB->phis()))
1812 PN.removeIncomingValueIf(Predicate: [&](unsigned Idx) {
1813 return !DT.isReachableFromEntry(A: PN.getIncomingBlock(i: Idx));
1814 });
1815 }
1816
1817 // Place the cloned blocks right after the original blocks (right before the
1818 // exit block of.)
1819 if (ExitBlock)
1820 F.splice(ToIt: ExitBlock->getIterator(), FromF: &F, FromBeginIt: NewBlocks[0]->getIterator(),
1821 FromEndIt: F.end());
1822
1823 // Update the cloned blocks/instructions to refer to themselves.
1824 for (BasicBlock *NewBB : NewBlocks)
1825 for (Instruction &I : *NewBB)
1826 RemapInstruction(I: &I, VM&: VMap,
1827 Flags: RF_NoModuleLevelChanges | RF_IgnoreMissingLocals);
1828
1829 // Add the cloned blocks to the PHIs of the exit blocks. ExitBlock is null for
1830 // the top-level region but we don't need to add PHIs. The trivial PHIs
1831 // inserted above will be updated here.
1832 if (ExitBlock)
1833 for (PHINode &PN : ExitBlock->phis())
1834 for (unsigned I = 0, NumOps = PN.getNumIncomingValues(); I < NumOps;
1835 ++I) {
1836 BasicBlock *Pred = PN.getIncomingBlock(i: I);
1837 if (LastRegion->contains(BB: Pred)) {
1838 Value *V = PN.getIncomingValue(i: I);
1839 auto It = VMap.find(Val: V);
1840 if (It != VMap.end()) V = It->second;
1841 assert(VMap.find(Pred) != VMap.end() && "Pred must have been cloned");
1842 PN.addIncoming(V, BB: cast<BasicBlock>(Val&: VMap[Pred]));
1843 }
1844 }
1845}
1846
1847// A helper for transformScope. Replace the old (placeholder) branch with the
1848// new (merged) conditional branch.
1849CondBrInst *CHR::createMergedBranch(BasicBlock *PreEntryBlock,
1850 BasicBlock *EntryBlock,
1851 BasicBlock *NewEntryBlock,
1852 ValueToValueMapTy &VMap) {
1853 UncondBrInst *OldBR = cast<UncondBrInst>(Val: PreEntryBlock->getTerminator());
1854 assert(OldBR->getSuccessor() == NewEntryBlock &&
1855 "SplitBlock did not work correctly!");
1856 assert(NewEntryBlock->getSinglePredecessor() == EntryBlock &&
1857 "NewEntryBlock's only pred must be EntryBlock");
1858 assert(VMap.find(NewEntryBlock) != VMap.end() &&
1859 "NewEntryBlock must have been copied");
1860 OldBR->dropAllReferences();
1861 OldBR->eraseFromParent();
1862 // The true predicate is a placeholder. It will be replaced later in
1863 // fixupBranchesAndSelects().
1864 CondBrInst *NewBR =
1865 CondBrInst::Create(Cond: ConstantInt::getTrue(Context&: F.getContext()), IfTrue: NewEntryBlock,
1866 IfFalse: cast<BasicBlock>(Val&: VMap[NewEntryBlock]));
1867 NewBR->insertInto(ParentBB: PreEntryBlock, It: PreEntryBlock->end());
1868 assert(NewEntryBlock->getSinglePredecessor() == EntryBlock &&
1869 "NewEntryBlock's only pred must be EntryBlock");
1870 return NewBR;
1871}
1872
1873// A helper for transformScopes. Create the combined branch condition and
1874// constant-fold the branches/selects in the hot path.
1875void CHR::fixupBranchesAndSelects(CHRScope *Scope, BasicBlock *PreEntryBlock,
1876 CondBrInst *MergedBR, uint64_t ProfileCount) {
1877 Value *MergedCondition = ConstantInt::getTrue(Context&: F.getContext());
1878 BranchProbability CHRBranchBias(1, 1);
1879 uint64_t NumCHRedBranches = 0;
1880 IRBuilder<> IRB(PreEntryBlock->getTerminator());
1881 for (RegInfo &RI : Scope->CHRRegions) {
1882 Region *R = RI.R;
1883 if (RI.HasBranch) {
1884 fixupBranch(R, Scope, IRB, MergedCondition, CHRBranchBias);
1885 ++NumCHRedBranches;
1886 }
1887 for (SelectInst *SI : RI.Selects) {
1888 fixupSelect(SI, Scope, IRB, MergedCondition, CHRBranchBias);
1889 ++NumCHRedBranches;
1890 }
1891 }
1892 assert(NumCHRedBranches > 0);
1893 Stats.NumBranchesDelta += NumCHRedBranches - 1;
1894 Stats.WeightedNumBranchesDelta += (NumCHRedBranches - 1) * ProfileCount;
1895 ORE.emit(RemarkBuilder: [&]() {
1896 return OptimizationRemark(DEBUG_TYPE,
1897 "CHR",
1898 // Refer to the hot (original) path
1899 MergedBR->getSuccessor(i: 0)->getTerminator())
1900 << "Merged " << ore::NV("NumCHRedBranches", NumCHRedBranches)
1901 << " branches or selects";
1902 });
1903 MergedBR->setCondition(MergedCondition);
1904 uint32_t Weights[] = {
1905 static_cast<uint32_t>(CHRBranchBias.scale(Num: 1000)),
1906 static_cast<uint32_t>(CHRBranchBias.getCompl().scale(Num: 1000)),
1907 };
1908 setBranchWeights(I&: *MergedBR, Weights, /*IsExpected=*/false);
1909 CHR_DEBUG(dbgs() << "CHR branch bias " << Weights[0] << ":" << Weights[1]
1910 << "\n");
1911}
1912
1913// A helper for fixupBranchesAndSelects. Add to the combined branch condition
1914// and constant-fold a branch in the hot path.
1915void CHR::fixupBranch(Region *R, CHRScope *Scope,
1916 IRBuilder<> &IRB,
1917 Value *&MergedCondition,
1918 BranchProbability &CHRBranchBias) {
1919 bool IsTrueBiased = Scope->TrueBiasedRegions.count(V: R);
1920 assert((IsTrueBiased || Scope->FalseBiasedRegions.count(R)) &&
1921 "Must be truthy or falsy");
1922 auto *BI = cast<CondBrInst>(Val: R->getEntry()->getTerminator());
1923 assert(BranchBiasMap.contains(R) && "Must be in the bias map");
1924 BranchProbability Bias = BranchBiasMap[R];
1925 assert(Bias >= getCHRBiasThreshold(Opts) && "Must be highly biased");
1926 // Take the min.
1927 if (CHRBranchBias > Bias)
1928 CHRBranchBias = Bias;
1929 BasicBlock *IfThen = BI->getSuccessor(i: 1);
1930 BasicBlock *IfElse = BI->getSuccessor(i: 0);
1931 BasicBlock *RegionExitBlock = R->getExit();
1932 assert(RegionExitBlock && "Null ExitBlock");
1933 assert((IfThen == RegionExitBlock || IfElse == RegionExitBlock) &&
1934 IfThen != IfElse && "Invariant from findScopes");
1935 if (IfThen == RegionExitBlock) {
1936 // Swap them so that IfThen means going into it and IfElse means skipping
1937 // it.
1938 std::swap(a&: IfThen, b&: IfElse);
1939 }
1940 CHR_DEBUG(dbgs() << "IfThen " << IfThen->getName()
1941 << " IfElse " << IfElse->getName() << "\n");
1942 Value *Cond = BI->getCondition();
1943 BasicBlock *HotTarget = IsTrueBiased ? IfThen : IfElse;
1944 bool ConditionTrue = HotTarget == BI->getSuccessor(i: 0);
1945 addToMergedCondition(IsTrueBiased: ConditionTrue, Cond, BranchOrSelect: BI, Scope, IRB,
1946 MergedCondition);
1947 // Constant-fold the branch at ClonedEntryBlock.
1948 assert(ConditionTrue == (HotTarget == BI->getSuccessor(0)) &&
1949 "The successor shouldn't change");
1950 Value *NewCondition = ConditionTrue ?
1951 ConstantInt::getTrue(Context&: F.getContext()) :
1952 ConstantInt::getFalse(Context&: F.getContext());
1953 BI->setCondition(NewCondition);
1954}
1955
1956// A helper for fixupBranchesAndSelects. Add to the combined branch condition
1957// and constant-fold a select in the hot path.
1958void CHR::fixupSelect(SelectInst *SI, CHRScope *Scope,
1959 IRBuilder<> &IRB,
1960 Value *&MergedCondition,
1961 BranchProbability &CHRBranchBias) {
1962 bool IsTrueBiased = Scope->TrueBiasedSelects.count(V: SI);
1963 assert((IsTrueBiased ||
1964 Scope->FalseBiasedSelects.count(SI)) && "Must be biased");
1965 assert(SelectBiasMap.contains(SI) && "Must be in the bias map");
1966 BranchProbability Bias = SelectBiasMap[SI];
1967 assert(Bias >= getCHRBiasThreshold(Opts) && "Must be highly biased");
1968 // Take the min.
1969 if (CHRBranchBias > Bias)
1970 CHRBranchBias = Bias;
1971 Value *Cond = SI->getCondition();
1972 addToMergedCondition(IsTrueBiased, Cond, BranchOrSelect: SI, Scope, IRB,
1973 MergedCondition);
1974 Value *NewCondition = IsTrueBiased ?
1975 ConstantInt::getTrue(Context&: F.getContext()) :
1976 ConstantInt::getFalse(Context&: F.getContext());
1977 SI->setCondition(NewCondition);
1978}
1979
1980// A helper for fixupBranch/fixupSelect. Add a branch condition to the merged
1981// condition.
1982void CHR::addToMergedCondition(bool IsTrueBiased, Value *Cond,
1983 Instruction *BranchOrSelect, CHRScope *Scope,
1984 IRBuilder<> &IRB, Value *&MergedCondition) {
1985 if (!IsTrueBiased) {
1986 // If Cond is an icmp and all users of V except for BranchOrSelect is a
1987 // branch, negate the icmp predicate and swap the branch targets and avoid
1988 // inserting an Xor to negate Cond.
1989 auto *ICmp = dyn_cast<ICmpInst>(Val: Cond);
1990 if (!ICmp ||
1991 !negateICmpIfUsedByBranchOrSelectOnly(ICmp, ExcludedUser: BranchOrSelect, Scope))
1992 Cond = IRB.CreateXor(LHS: ConstantInt::getTrue(Context&: F.getContext()), RHS: Cond);
1993 }
1994
1995 // Freeze potentially poisonous conditions.
1996 if (!isGuaranteedNotToBeUndefOrPoison(V: Cond))
1997 Cond = IRB.CreateFreeze(V: Cond);
1998
1999 // Use logical and to avoid propagating poison from later conditions.
2000 MergedCondition = IRB.CreateLogicalAnd(Cond1: MergedCondition, Cond2: Cond);
2001 if (auto *MergedInst = dyn_cast<Instruction>(Val: MergedCondition))
2002 setExplicitlyUnknownBranchWeightsIfProfiled(I&: *MergedInst, DEBUG_TYPE, F: &F);
2003}
2004
2005void CHR::transformScopes(SmallVectorImpl<CHRScope *> &CHRScopes) {
2006 unsigned I = 0;
2007 DenseSet<PHINode *> TrivialPHIs;
2008 for (CHRScope *Scope : CHRScopes) {
2009 transformScopes(Scope, TrivialPHIs);
2010 CHR_DEBUG(
2011 std::ostringstream oss;
2012 oss << " after transformScopes " << I++;
2013 dumpIR(F, oss.str().c_str(), nullptr));
2014 (void)I;
2015 }
2016}
2017
2018[[maybe_unused]] static void dumpScopes(SmallVectorImpl<CHRScope *> &Scopes,
2019 const char *Label) {
2020 dbgs() << Label << " " << Scopes.size() << "\n";
2021 for (CHRScope *Scope : Scopes) {
2022 dbgs() << *Scope << "\n";
2023 }
2024}
2025
2026bool CHR::run() {
2027 if (!shouldApply(Opts, CHRModules, CHRFunctions, F, PSI))
2028 return false;
2029
2030 CHR_DEBUG(dumpIR(F, "before", nullptr));
2031
2032 bool Changed = false;
2033 {
2034 CHR_DEBUG(
2035 dbgs() << "RegionInfo:\n";
2036 RI.print(dbgs()));
2037
2038 // Recursively traverse the region tree and find regions that have biased
2039 // branches and/or selects and create scopes.
2040 SmallVector<CHRScope *, 8> AllScopes;
2041 findScopes(Output&: AllScopes);
2042 CHR_DEBUG(dumpScopes(AllScopes, "All scopes"));
2043
2044 // Split the scopes if 1) the conditional values of the biased
2045 // branches/selects of the inner/lower scope can't be hoisted up to the
2046 // outermost/uppermost scope entry, or 2) the condition values of the biased
2047 // branches/selects in a scope (including subscopes) don't share at least
2048 // one common value.
2049 SmallVector<CHRScope *, 8> SplitScopes;
2050 splitScopes(Input&: AllScopes, Output&: SplitScopes);
2051 CHR_DEBUG(dumpScopes(SplitScopes, "Split scopes"));
2052
2053 // After splitting, set the biased regions and selects of a scope (a tree
2054 // root) that include those of the subscopes.
2055 classifyBiasedScopes(Scopes&: SplitScopes);
2056 CHR_DEBUG(dbgs() << "Set per-scope bias " << SplitScopes.size() << "\n");
2057
2058 // Filter out the scopes that has only one biased region or select (CHR
2059 // isn't useful in such a case).
2060 SmallVector<CHRScope *, 8> FilteredScopes;
2061 filterScopes(Input&: SplitScopes, Output&: FilteredScopes);
2062 CHR_DEBUG(dumpScopes(FilteredScopes, "Filtered scopes"));
2063
2064 // Set the regions to be CHR'ed and their hoist stops for each scope.
2065 SmallVector<CHRScope *, 8> SetScopes;
2066 setCHRRegions(Input&: FilteredScopes, Output&: SetScopes);
2067 CHR_DEBUG(dumpScopes(SetScopes, "Set CHR regions"));
2068
2069 // Sort CHRScopes by the depth so that outer CHRScopes comes before inner
2070 // ones. We need to apply CHR from outer to inner so that we apply CHR only
2071 // to the hot path, rather than both hot and cold paths.
2072 SmallVector<CHRScope *, 8> SortedScopes;
2073 sortScopes(Input&: SetScopes, Output&: SortedScopes);
2074 CHR_DEBUG(dumpScopes(SortedScopes, "Sorted scopes"));
2075
2076 CHR_DEBUG(
2077 dbgs() << "RegionInfo:\n";
2078 RI.print(dbgs()));
2079
2080 // Apply the CHR transformation.
2081 if (!SortedScopes.empty()) {
2082 transformScopes(CHRScopes&: SortedScopes);
2083 Changed = true;
2084 }
2085 }
2086
2087 if (Changed) {
2088 CHR_DEBUG(dumpIR(F, "after", &Stats));
2089 ORE.emit(RemarkBuilder: [&]() {
2090 return OptimizationRemark(DEBUG_TYPE, "Stats", &F)
2091 << ore::NV("Function", &F) << " "
2092 << "Reduced the number of branches in hot paths by "
2093 << ore::NV("NumBranchesDelta", Stats.NumBranchesDelta)
2094 << " (static) and "
2095 << ore::NV("WeightedNumBranchesDelta", Stats.WeightedNumBranchesDelta)
2096 << " (weighted by PGO count)";
2097 });
2098 }
2099
2100 return Changed;
2101}
2102
2103PreservedAnalyses ControlHeightReductionPass::run(
2104 Function &F,
2105 FunctionAnalysisManager &FAM) {
2106 auto &MAMProxy = FAM.getResult<ModuleAnalysisManagerFunctionProxy>(IR&: F);
2107 auto PPSI = MAMProxy.getCachedResult<ProfileSummaryAnalysis>(IR&: *F.getParent());
2108 // If there is no profile summary, we should not do CHR.
2109 if (!PPSI || !PPSI->hasProfileSummary())
2110 return PreservedAnalyses::all();
2111 auto &PSI = *PPSI;
2112 auto &BFI = FAM.getResult<BlockFrequencyAnalysis>(IR&: F);
2113 auto &DT = FAM.getResult<DominatorTreeAnalysis>(IR&: F);
2114 auto &RI = FAM.getResult<RegionInfoAnalysis>(IR&: F);
2115 auto &ORE = FAM.getResult<OptimizationRemarkEmitterAnalysis>(IR&: F);
2116 const InstrumentationOptions &Opts = getInstrumentationOptions(F);
2117 if (&Opts != ParsedOpts &&
2118 (!Opts.chr_module_list.empty() || !Opts.chr_function_list.empty())) {
2119 CHRModules.clear();
2120 CHRFunctions.clear();
2121 parseCHRFilterFiles(Opts, CHRModules, CHRFunctions);
2122 ParsedOpts = &Opts;
2123 }
2124 bool Changed =
2125 CHR(Opts, CHRModules, CHRFunctions, F, BFI, DT, PSI, RI, ORE).run();
2126 if (!Changed)
2127 return PreservedAnalyses::all();
2128 return PreservedAnalyses::none();
2129}
2130