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