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