LLVM: lib/Transforms/Instrumentation/ControlHeightReduction.cpp Source File

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

AltStyle によって変換されたページ (->オリジナル) /