LLVM  10.0.0svn
ControlHeightReduction.cpp
Go to the documentation of this file.
1 //===-- ControlHeightReduction.cpp - Control Height Reduction -------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This pass merges conditional blocks of code and reduces the number of
10 // conditional branches in the hot paths based on profiles.
11 //
12 //===----------------------------------------------------------------------===//
13 
15 #include "llvm/ADT/DenseMap.h"
16 #include "llvm/ADT/DenseSet.h"
17 #include "llvm/ADT/SmallVector.h"
18 #include "llvm/ADT/StringSet.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"
32 #include "llvm/Transforms/Utils.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 
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 
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 
58  "chr-module-list", cl::init(""), cl::Hidden,
59  cl::desc("Specify file to retrieve the list of modules to apply CHR to"));
60 
62  "chr-function-list", cl::init(""), cl::Hidden,
63  cl::desc("Specify file to retrieve the list of functions to apply CHR to"));
64 
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();
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();
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) {
110  }
111 
112  bool runOnFunction(Function &F) override;
113  void getAnalysisUsage(AnalysisUsage &AU) const override {
119  }
120 };
121 } // end anonymous namespace
122 
124 
125 INITIALIZE_PASS_BEGIN(ControlHeightReductionLegacyPass,
126  "chr",
127  "Reduce control height in the hot paths",
128  false, false)
133 INITIALIZE_PASS_END(ControlHeightReductionLegacyPass,
134  "chr",
135  "Reduce control height in the hot paths",
136  false, false)
137 
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;
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;
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,
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,
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,
348  CHRScope *findScope(Region *R);
349  void checkScopeHoistable(CHRScope *Scope);
350 
351  void splitScopes(SmallVectorImpl<CHRScope *> &Input,
353  SmallVector<CHRScope *, 8> splitScope(CHRScope *Scope,
354  CHRScope *Outer,
355  DenseSet<Value *> *OuterConditionValues,
356  Instruction *OuterInsertPoint,
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,
365 
366  void setCHRRegions(SmallVectorImpl<CHRScope *> &Input,
368  void setCHRRegions(CHRScope *Scope, CHRScope *OutermostScope);
369 
370  void sortScopes(SmallVectorImpl<CHRScope *> &Input,
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;
404  DominatorTree &DT;
405  ProfileSummaryInfo &PSI;
406  RegionInfo &RI;
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
420  // A map from biased selects to their branch bias
422  // All the scopes.
423  DenseSet<CHRScope *> Scopes;
424 };
425 
426 } // end anonymous namespace
427 
428 static inline
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 
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.
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.
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
548  DenseSet<Instruction *> &Unhoistables,
549  DenseSet<Instruction *> *HoistStops,
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 
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) {
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,
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  // ...
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  }
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([&]() {
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) {
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([&]() {
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");
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");
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 
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) {
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,
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;
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([&]() {
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([&]() {
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];
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  }
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.
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.
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());
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.
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  SI->swapValues();
1542  SI->swapProfMetadata();
1543  if (Scope->TrueBiasedSelects.count(SI)) {
1544  assert(Scope->FalseBiasedSelects.count(SI) == 0 &&
1545  "Must not be already in");
1546  Scope->FalseBiasedSelects.insert(SI);
1547  } else if (Scope->FalseBiasedSelects.count(SI)) {
1548  assert(Scope->TrueBiasedSelects.count(SI) == 0 &&
1549  "Must not be already in");
1550  Scope->TrueBiasedSelects.insert(SI);
1551  }
1552  continue;
1553  }
1554  llvm_unreachable("Must be a branch or a select");
1555  }
1557  return true;
1558 }
1559 
1560 // A helper for transformScopes. Insert a trivial phi at the scope exit block
1561 // for a value that's defined in the scope but used outside it (meaning it's
1562 // alive at the exit block).
1563 static void insertTrivialPHIs(CHRScope *Scope,
1564  BasicBlock *EntryBlock, BasicBlock *ExitBlock,
1565  DenseSet<PHINode *> &TrivialPHIs) {
1566  DenseSet<BasicBlock *> BlocksInScopeSet;
1567  SmallVector<BasicBlock *, 8> BlocksInScopeVec;
1568  for (RegInfo &RI : Scope->RegInfos) {
1569  for (BasicBlock *BB : RI.R->blocks()) { // This includes the blocks in the
1570  // sub-Scopes.
1571  BlocksInScopeSet.insert(BB);
1572  BlocksInScopeVec.push_back(BB);
1573  }
1574  }
1575  CHR_DEBUG(
1576  dbgs() << "Inserting redudant phis\n";
1577  for (BasicBlock *BB : BlocksInScopeVec) {
1578  dbgs() << "BlockInScope " << BB->getName() << "\n";
1579  });
1580  for (BasicBlock *BB : BlocksInScopeVec) {
1581  for (Instruction &I : *BB) {
1583  for (User *U : I.users()) {
1584  if (auto *UI = dyn_cast<Instruction>(U)) {
1585  if (BlocksInScopeSet.count(UI->getParent()) == 0 &&
1586  // Unless there's already a phi for I at the exit block.
1587  !(isa<PHINode>(UI) && UI->getParent() == ExitBlock)) {
1588  CHR_DEBUG(dbgs() << "V " << I << "\n");
1589  CHR_DEBUG(dbgs() << "Used outside scope by user " << *UI << "\n");
1590  Users.push_back(UI);
1591  } else if (UI->getParent() == EntryBlock && isa<PHINode>(UI)) {
1592  // There's a loop backedge from a block that's dominated by this
1593  // scope to the entry block.
1594  CHR_DEBUG(dbgs() << "V " << I << "\n");
1595  CHR_DEBUG(dbgs()
1596  << "Used at entry block (for a back edge) by a phi user "
1597  << *UI << "\n");
1598  Users.push_back(UI);
1599  }
1600  }
1601  }
1602  if (Users.size() > 0) {
1603  // Insert a trivial phi for I (phi [&I, P0], [&I, P1], ...) at
1604  // ExitBlock. Replace I with the new phi in UI unless UI is another
1605  // phi at ExitBlock.
1606  unsigned PredCount = std::distance(pred_begin(ExitBlock),
1607  pred_end(ExitBlock));
1608  PHINode *PN = PHINode::Create(I.getType(), PredCount, "",
1609  &ExitBlock->front());
1610  for (BasicBlock *Pred : predecessors(ExitBlock)) {
1611  PN->addIncoming(&I, Pred);
1612  }
1613  TrivialPHIs.insert(PN);
1614  CHR_DEBUG(dbgs() << "Insert phi " << *PN << "\n");
1615  for (Instruction *UI : Users) {
1616  for (unsigned J = 0, NumOps = UI->getNumOperands(); J < NumOps; ++J) {
1617  if (UI->getOperand(J) == &I) {
1618  UI->setOperand(J, PN);
1619  }
1620  }
1621  CHR_DEBUG(dbgs() << "Updated user " << *UI << "\n");
1622  }
1623  }
1624  }
1625  }
1626 }
1627 
1628 // Assert that all the CHR regions of the scope have a biased branch or select.
1629 static void LLVM_ATTRIBUTE_UNUSED
1631 #ifndef NDEBUG
1632  auto HasBiasedBranchOrSelect = [](RegInfo &RI, CHRScope *Scope) {
1633  if (Scope->TrueBiasedRegions.count(RI.R) ||
1634  Scope->FalseBiasedRegions.count(RI.R))
1635  return true;
1636  for (SelectInst *SI : RI.Selects)
1637  if (Scope->TrueBiasedSelects.count(SI) ||
1638  Scope->FalseBiasedSelects.count(SI))
1639  return true;
1640  return false;
1641  };
1642  for (RegInfo &RI : Scope->CHRRegions) {
1643  assert(HasBiasedBranchOrSelect(RI, Scope) &&
1644  "Must have biased branch or select");
1645  }
1646 #endif
1647 }
1648 
1649 // Assert that all the condition values of the biased branches and selects have
1650 // been hoisted to the pre-entry block or outside of the scope.
1652  CHRScope *Scope, BasicBlock *PreEntryBlock) {
1653  CHR_DEBUG(dbgs() << "Biased regions condition values \n");
1654  for (RegInfo &RI : Scope->CHRRegions) {
1655  Region *R = RI.R;
1656  bool IsTrueBiased = Scope->TrueBiasedRegions.count(R);
1657  bool IsFalseBiased = Scope->FalseBiasedRegions.count(R);
1658  if (RI.HasBranch && (IsTrueBiased || IsFalseBiased)) {
1659  auto *BI = cast<BranchInst>(R->getEntry()->getTerminator());
1660  Value *V = BI->getCondition();
1661  CHR_DEBUG(dbgs() << *V << "\n");
1662  if (auto *I = dyn_cast<Instruction>(V)) {
1663  (void)(I); // Unused in release build.
1664  assert((I->getParent() == PreEntryBlock ||
1665  !Scope->contains(I)) &&
1666  "Must have been hoisted to PreEntryBlock or outside the scope");
1667  }
1668  }
1669  for (SelectInst *SI : RI.Selects) {
1670  bool IsTrueBiased = Scope->TrueBiasedSelects.count(SI);
1671  bool IsFalseBiased = Scope->FalseBiasedSelects.count(SI);
1672  if (!(IsTrueBiased || IsFalseBiased))
1673  continue;
1674  Value *V = SI->getCondition();
1675  CHR_DEBUG(dbgs() << *V << "\n");
1676  if (auto *I = dyn_cast<Instruction>(V)) {
1677  (void)(I); // Unused in release build.
1678  assert((I->getParent() == PreEntryBlock ||
1679  !Scope->contains(I)) &&
1680  "Must have been hoisted to PreEntryBlock or outside the scope");
1681  }
1682  }
1683  }
1684 }
1685 
1686 void CHR::transformScopes(CHRScope *Scope, DenseSet<PHINode *> &TrivialPHIs) {
1687  CHR_DEBUG(dbgs() << "transformScopes " << *Scope << "\n");
1688 
1689  assert(Scope->RegInfos.size() >= 1 && "Should have at least one Region");
1690  Region *FirstRegion = Scope->RegInfos[0].R;
1691  BasicBlock *EntryBlock = FirstRegion->getEntry();
1692  Region *LastRegion = Scope->RegInfos[Scope->RegInfos.size() - 1].R;
1693  BasicBlock *ExitBlock = LastRegion->getExit();
1694  Optional<uint64_t> ProfileCount = BFI.getBlockProfileCount(EntryBlock);
1695 
1696  if (ExitBlock) {
1697  // Insert a trivial phi at the exit block (where the CHR hot path and the
1698  // cold path merges) for a value that's defined in the scope but used
1699  // outside it (meaning it's alive at the exit block). We will add the
1700  // incoming values for the CHR cold paths to it below. Without this, we'd
1701  // miss updating phi's for such values unless there happens to already be a
1702  // phi for that value there.
1703  insertTrivialPHIs(Scope, EntryBlock, ExitBlock, TrivialPHIs);
1704  }
1705 
1706  // Split the entry block of the first region. The new block becomes the new
1707  // entry block of the first region. The old entry block becomes the block to
1708  // insert the CHR branch into. Note DT gets updated. Since DT gets updated
1709  // through the split, we update the entry of the first region after the split,
1710  // and Region only points to the entry and the exit blocks, rather than
1711  // keeping everything in a list or set, the blocks membership and the
1712  // entry/exit blocks of the region are still valid after the split.
1713  CHR_DEBUG(dbgs() << "Splitting entry block " << EntryBlock->getName()
1714  << " at " << *Scope->BranchInsertPoint << "\n");
1715  BasicBlock *NewEntryBlock =
1716  SplitBlock(EntryBlock, Scope->BranchInsertPoint, &DT);
1717  assert(NewEntryBlock->getSinglePredecessor() == EntryBlock &&
1718  "NewEntryBlock's only pred must be EntryBlock");
1719  FirstRegion->replaceEntryRecursive(NewEntryBlock);
1720  BasicBlock *PreEntryBlock = EntryBlock;
1721 
1722  ValueToValueMapTy VMap;
1723  // Clone the blocks in the scope (excluding the PreEntryBlock) to split into a
1724  // hot path (originals) and a cold path (clones) and update the PHIs at the
1725  // exit block.
1726  cloneScopeBlocks(Scope, PreEntryBlock, ExitBlock, LastRegion, VMap);
1727 
1728  // Replace the old (placeholder) branch with the new (merged) conditional
1729  // branch.
1730  BranchInst *MergedBr = createMergedBranch(PreEntryBlock, EntryBlock,
1731  NewEntryBlock, VMap);
1732 
1733 #ifndef NDEBUG
1735 #endif
1736 
1737  // Hoist the conditional values of the branches/selects.
1738  hoistScopeConditions(Scope, PreEntryBlock->getTerminator(), TrivialPHIs, DT);
1739 
1740 #ifndef NDEBUG
1741  assertBranchOrSelectConditionHoisted(Scope, PreEntryBlock);
1742 #endif
1743 
1744  // Create the combined branch condition and constant-fold the branches/selects
1745  // in the hot path.
1746  fixupBranchesAndSelects(Scope, PreEntryBlock, MergedBr,
1747  ProfileCount ? ProfileCount.getValue() : 0);
1748 }
1749 
1750 // A helper for transformScopes. Clone the blocks in the scope (excluding the
1751 // PreEntryBlock) to split into a hot path and a cold path and update the PHIs
1752 // at the exit block.
1753 void CHR::cloneScopeBlocks(CHRScope *Scope,
1754  BasicBlock *PreEntryBlock,
1755  BasicBlock *ExitBlock,
1756  Region *LastRegion,
1757  ValueToValueMapTy &VMap) {
1758  // Clone all the blocks. The original blocks will be the hot-path
1759  // CHR-optimized code and the cloned blocks will be the original unoptimized
1760  // code. This is so that the block pointers from the
1761  // CHRScope/Region/RegionInfo can stay valid in pointing to the hot-path code
1762  // which CHR should apply to.
1763  SmallVector<BasicBlock*, 8> NewBlocks;
1764  for (RegInfo &RI : Scope->RegInfos)
1765  for (BasicBlock *BB : RI.R->blocks()) { // This includes the blocks in the
1766  // sub-Scopes.
1767  assert(BB != PreEntryBlock && "Don't copy the preetntry block");
1768  BasicBlock *NewBB = CloneBasicBlock(BB, VMap, ".nonchr", &F);
1769  NewBlocks.push_back(NewBB);
1770  VMap[BB] = NewBB;
1771  }
1772 
1773  // Place the cloned blocks right after the original blocks (right before the
1774  // exit block of.)
1775  if (ExitBlock)
1776  F.getBasicBlockList().splice(ExitBlock->getIterator(),
1777  F.getBasicBlockList(),
1778  NewBlocks[0]->getIterator(), F.end());
1779 
1780  // Update the cloned blocks/instructions to refer to themselves.
1781  for (unsigned i = 0, e = NewBlocks.size(); i != e; ++i)
1782  for (Instruction &I : *NewBlocks[i])
1783  RemapInstruction(&I, VMap,
1785 
1786  // Add the cloned blocks to the PHIs of the exit blocks. ExitBlock is null for
1787  // the top-level region but we don't need to add PHIs. The trivial PHIs
1788  // inserted above will be updated here.
1789  if (ExitBlock)
1790  for (PHINode &PN : ExitBlock->phis())
1791  for (unsigned I = 0, NumOps = PN.getNumIncomingValues(); I < NumOps;
1792  ++I) {
1793  BasicBlock *Pred = PN.getIncomingBlock(I);
1794  if (LastRegion->contains(Pred)) {
1795  Value *V = PN.getIncomingValue(I);
1796  auto It = VMap.find(V);
1797  if (It != VMap.end()) V = It->second;
1798  assert(VMap.find(Pred) != VMap.end() && "Pred must have been cloned");
1799  PN.addIncoming(V, cast<BasicBlock>(VMap[Pred]));
1800  }
1801  }
1802 }
1803 
1804 // A helper for transformScope. Replace the old (placeholder) branch with the
1805 // new (merged) conditional branch.
1806 BranchInst *CHR::createMergedBranch(BasicBlock *PreEntryBlock,
1807  BasicBlock *EntryBlock,
1808  BasicBlock *NewEntryBlock,
1809  ValueToValueMapTy &VMap) {
1810  BranchInst *OldBR = cast<BranchInst>(PreEntryBlock->getTerminator());
1811  assert(OldBR->isUnconditional() && OldBR->getSuccessor(0) == NewEntryBlock &&
1812  "SplitBlock did not work correctly!");
1813  assert(NewEntryBlock->getSinglePredecessor() == EntryBlock &&
1814  "NewEntryBlock's only pred must be EntryBlock");
1815  assert(VMap.find(NewEntryBlock) != VMap.end() &&
1816  "NewEntryBlock must have been copied");
1817  OldBR->dropAllReferences();
1818  OldBR->eraseFromParent();
1819  // The true predicate is a placeholder. It will be replaced later in
1820  // fixupBranchesAndSelects().
1821  BranchInst *NewBR = BranchInst::Create(NewEntryBlock,
1822  cast<BasicBlock>(VMap[NewEntryBlock]),
1823  ConstantInt::getTrue(F.getContext()));
1824  PreEntryBlock->getInstList().push_back(NewBR);
1825  assert(NewEntryBlock->getSinglePredecessor() == EntryBlock &&
1826  "NewEntryBlock's only pred must be EntryBlock");
1827  return NewBR;
1828 }
1829 
1830 // A helper for transformScopes. Create the combined branch condition and
1831 // constant-fold the branches/selects in the hot path.
1832 void CHR::fixupBranchesAndSelects(CHRScope *Scope,
1833  BasicBlock *PreEntryBlock,
1834  BranchInst *MergedBR,
1835  uint64_t ProfileCount) {
1836  Value *MergedCondition = ConstantInt::getTrue(F.getContext());
1837  BranchProbability CHRBranchBias(1, 1);
1838  uint64_t NumCHRedBranches = 0;
1839  IRBuilder<> IRB(PreEntryBlock->getTerminator());
1840  for (RegInfo &RI : Scope->CHRRegions) {
1841  Region *R = RI.R;
1842  if (RI.HasBranch) {
1843  fixupBranch(R, Scope, IRB, MergedCondition, CHRBranchBias);
1844  ++NumCHRedBranches;
1845  }
1846  for (SelectInst *SI : RI.Selects) {
1847  fixupSelect(SI, Scope, IRB, MergedCondition, CHRBranchBias);
1848  ++NumCHRedBranches;
1849  }
1850  }
1851  Stats.NumBranchesDelta += NumCHRedBranches - 1;
1852  Stats.WeightedNumBranchesDelta += (NumCHRedBranches - 1) * ProfileCount;
1853  ORE.emit([&]() {
1855  "CHR",
1856  // Refer to the hot (original) path
1857  MergedBR->getSuccessor(0)->getTerminator())
1858  << "Merged " << ore::NV("NumCHRedBranches", NumCHRedBranches)
1859  << " branches or selects";
1860  });
1861  MergedBR->setCondition(MergedCondition);
1862  SmallVector<uint32_t, 2> Weights;
1863  Weights.push_back(static_cast<uint32_t>(CHRBranchBias.scale(1000)));
1864  Weights.push_back(static_cast<uint32_t>(CHRBranchBias.getCompl().scale(1000)));
1865  MDBuilder MDB(F.getContext());
1866  MergedBR->setMetadata(LLVMContext::MD_prof, MDB.createBranchWeights(Weights));
1867  CHR_DEBUG(dbgs() << "CHR branch bias " << Weights[0] << ":" << Weights[1]
1868  << "\n");
1869 }
1870 
1871 // A helper for fixupBranchesAndSelects. Add to the combined branch condition
1872 // and constant-fold a branch in the hot path.
1873 void CHR::fixupBranch(Region *R, CHRScope *Scope,
1874  IRBuilder<> &IRB,
1875  Value *&MergedCondition,
1876  BranchProbability &CHRBranchBias) {
1877  bool IsTrueBiased = Scope->TrueBiasedRegions.count(R);
1878  assert((IsTrueBiased || Scope->FalseBiasedRegions.count(R)) &&
1879  "Must be truthy or falsy");
1880  auto *BI = cast<BranchInst>(R->getEntry()->getTerminator());
1881  assert(BranchBiasMap.find(R) != BranchBiasMap.end() &&
1882  "Must be in the bias map");
1883  BranchProbability Bias = BranchBiasMap[R];
1884  assert(Bias >= getCHRBiasThreshold() && "Must be highly biased");
1885  // Take the min.
1886  if (CHRBranchBias > Bias)
1887  CHRBranchBias = Bias;
1888  BasicBlock *IfThen = BI->getSuccessor(1);
1889  BasicBlock *IfElse = BI->getSuccessor(0);
1890  BasicBlock *RegionExitBlock = R->getExit();
1891  assert(RegionExitBlock && "Null ExitBlock");
1892  assert((IfThen == RegionExitBlock || IfElse == RegionExitBlock) &&
1893  IfThen != IfElse && "Invariant from findScopes");
1894  if (IfThen == RegionExitBlock) {
1895  // Swap them so that IfThen means going into it and IfElse means skipping
1896  // it.
1897  std::swap(IfThen, IfElse);
1898  }
1899  CHR_DEBUG(dbgs() << "IfThen " << IfThen->getName()
1900  << " IfElse " << IfElse->getName() << "\n");
1901  Value *Cond = BI->getCondition();
1902  BasicBlock *HotTarget = IsTrueBiased ? IfThen : IfElse;
1903  bool ConditionTrue = HotTarget == BI->getSuccessor(0);
1904  addToMergedCondition(ConditionTrue, Cond, BI, Scope, IRB,
1905  MergedCondition);
1906  // Constant-fold the branch at ClonedEntryBlock.
1907  assert(ConditionTrue == (HotTarget == BI->getSuccessor(0)) &&
1908  "The successor shouldn't change");
1909  Value *NewCondition = ConditionTrue ?
1910  ConstantInt::getTrue(F.getContext()) :
1911  ConstantInt::getFalse(F.getContext());
1912  BI->setCondition(NewCondition);
1913 }
1914 
1915 // A helper for fixupBranchesAndSelects. Add to the combined branch condition
1916 // and constant-fold a select in the hot path.
1917 void CHR::fixupSelect(SelectInst *SI, CHRScope *Scope,
1918  IRBuilder<> &IRB,
1919  Value *&MergedCondition,
1920  BranchProbability &CHRBranchBias) {
1921  bool IsTrueBiased = Scope->TrueBiasedSelects.count(SI);
1922  assert((IsTrueBiased ||
1923  Scope->FalseBiasedSelects.count(SI)) && "Must be biased");
1924  assert(SelectBiasMap.find(SI) != SelectBiasMap.end() &&
1925  "Must be in the bias map");
1926  BranchProbability Bias = SelectBiasMap[SI];
1927  assert(Bias >= getCHRBiasThreshold() && "Must be highly biased");
1928  // Take the min.
1929  if (CHRBranchBias > Bias)
1930  CHRBranchBias = Bias;
1931  Value *Cond = SI->getCondition();
1932  addToMergedCondition(IsTrueBiased, Cond, SI, Scope, IRB,
1933  MergedCondition);
1934  Value *NewCondition = IsTrueBiased ?
1935  ConstantInt::getTrue(F.getContext()) :
1936  ConstantInt::getFalse(F.getContext());
1937  SI->setCondition(NewCondition);
1938 }
1939 
1940 // A helper for fixupBranch/fixupSelect. Add a branch condition to the merged
1941 // condition.
1942 void CHR::addToMergedCondition(bool IsTrueBiased, Value *Cond,
1943  Instruction *BranchOrSelect,
1944  CHRScope *Scope,
1945  IRBuilder<> &IRB,
1946  Value *&MergedCondition) {
1947  if (IsTrueBiased) {
1948  MergedCondition = IRB.CreateAnd(MergedCondition, Cond);
1949  } else {
1950  // If Cond is an icmp and all users of V except for BranchOrSelect is a
1951  // branch, negate the icmp predicate and swap the branch targets and avoid
1952  // inserting an Xor to negate Cond.
1953  bool Done = false;
1954  if (auto *ICmp = dyn_cast<ICmpInst>(Cond))
1955  if (negateICmpIfUsedByBranchOrSelectOnly(ICmp, BranchOrSelect, Scope)) {
1956  MergedCondition = IRB.CreateAnd(MergedCondition, Cond);
1957  Done = true;
1958  }
1959  if (!Done) {
1960  Value *Negate = IRB.CreateXor(
1961  ConstantInt::getTrue(F.getContext()), Cond);
1962  MergedCondition = IRB.CreateAnd(MergedCondition, Negate);
1963  }
1964  }
1965 }
1966 
1967 void CHR::transformScopes(SmallVectorImpl<CHRScope *> &CHRScopes) {
1968  unsigned I = 0;
1969  DenseSet<PHINode *> TrivialPHIs;
1970  for (CHRScope *Scope : CHRScopes) {
1971  transformScopes(Scope, TrivialPHIs);
1972  CHR_DEBUG(
1973  std::ostringstream oss;
1974  oss << " after transformScopes " << I++;
1975  dumpIR(F, oss.str().c_str(), nullptr));
1976  (void)I;
1977  }
1978 }
1979 
1980 static void LLVM_ATTRIBUTE_UNUSED
1981 dumpScopes(SmallVectorImpl<CHRScope *> &Scopes, const char *Label) {
1982  dbgs() << Label << " " << Scopes.size() << "\n";
1983  for (CHRScope *Scope : Scopes) {
1984  dbgs() << *Scope << "\n";
1985  }
1986 }
1987 
1988 bool CHR::run() {
1989  if (!shouldApply(F, PSI))
1990  return false;
1991 
1992  CHR_DEBUG(dumpIR(F, "before", nullptr));
1993 
1994  bool Changed = false;
1995  {
1996  CHR_DEBUG(
1997  dbgs() << "RegionInfo:\n";
1998  RI.print(dbgs()));
1999 
2000  // Recursively traverse the region tree and find regions that have biased
2001  // branches and/or selects and create scopes.
2002  SmallVector<CHRScope *, 8> AllScopes;
2003  findScopes(AllScopes);
2004  CHR_DEBUG(dumpScopes(AllScopes, "All scopes"));
2005 
2006  // Split the scopes if 1) the conditiona values of the biased
2007  // branches/selects of the inner/lower scope can't be hoisted up to the
2008  // outermost/uppermost scope entry, or 2) the condition values of the biased
2009  // branches/selects in a scope (including subscopes) don't share at least
2010  // one common value.
2011  SmallVector<CHRScope *, 8> SplitScopes;
2012  splitScopes(AllScopes, SplitScopes);
2013  CHR_DEBUG(dumpScopes(SplitScopes, "Split scopes"));
2014 
2015  // After splitting, set the biased regions and selects of a scope (a tree
2016  // root) that include those of the subscopes.
2017  classifyBiasedScopes(SplitScopes);
2018  CHR_DEBUG(dbgs() << "Set per-scope bias " << SplitScopes.size() << "\n");
2019 
2020  // Filter out the scopes that has only one biased region or select (CHR
2021  // isn't useful in such a case).
2022  SmallVector<CHRScope *, 8> FilteredScopes;
2023  filterScopes(SplitScopes, FilteredScopes);
2024  CHR_DEBUG(dumpScopes(FilteredScopes, "Filtered scopes"));
2025 
2026  // Set the regions to be CHR'ed and their hoist stops for each scope.
2027  SmallVector<CHRScope *, 8> SetScopes;
2028  setCHRRegions(FilteredScopes, SetScopes);
2029  CHR_DEBUG(dumpScopes(SetScopes, "Set CHR regions"));
2030 
2031  // Sort CHRScopes by the depth so that outer CHRScopes comes before inner
2032  // ones. We need to apply CHR from outer to inner so that we apply CHR only
2033  // to the hot path, rather than both hot and cold paths.
2034  SmallVector<CHRScope *, 8> SortedScopes;
2035  sortScopes(SetScopes, SortedScopes);
2036  CHR_DEBUG(dumpScopes(SortedScopes, "Sorted scopes"));
2037 
2038  CHR_DEBUG(
2039  dbgs() << "RegionInfo:\n";
2040  RI.print(dbgs()));
2041 
2042  // Apply the CHR transformation.
2043  if (!SortedScopes.empty()) {
2044  transformScopes(SortedScopes);
2045  Changed = true;
2046  }
2047  }
2048 
2049  if (Changed) {
2050  CHR_DEBUG(dumpIR(F, "after", &Stats));
2051  ORE.emit([&]() {
2052  return OptimizationRemark(DEBUG_TYPE, "Stats", &F)
2053  << ore::NV("Function", &F) << " "
2054  << "Reduced the number of branches in hot paths by "
2055  << ore::NV("NumBranchesDelta", Stats.NumBranchesDelta)
2056  << " (static) and "
2057  << ore::NV("WeightedNumBranchesDelta", Stats.WeightedNumBranchesDelta)
2058  << " (weighted by PGO count)";
2059  });
2060  }
2061 
2062  return Changed;
2063 }
2064 
2067  getAnalysis<BlockFrequencyInfoWrapperPass>().getBFI();
2068  DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
2069  ProfileSummaryInfo &PSI =
2070  getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();
2071  RegionInfo &RI = getAnalysis<RegionInfoPass>().getRegionInfo();
2072  std::unique_ptr<OptimizationRemarkEmitter> OwnedORE =
2073  std::make_unique<OptimizationRemarkEmitter>(&F);
2074  return CHR(F, BFI, DT, PSI, RI, *OwnedORE.get()).run();
2075 }
2076 
2077 namespace llvm {
2078 
2081 }
2082 
2084  Function &F,
2085  FunctionAnalysisManager &FAM) {
2086  auto &BFI = FAM.getResult<BlockFrequencyAnalysis>(F);
2087  auto &DT = FAM.getResult<DominatorTreeAnalysis>(F);
2088  auto &MAMProxy = FAM.getResult<ModuleAnalysisManagerFunctionProxy>(F);
2089  auto &MAM = MAMProxy.getManager();
2090  auto &PSI = *MAM.getCachedResult<ProfileSummaryAnalysis>(*F.getParent());
2091  auto &RI = FAM.getResult<RegionInfoAnalysis>(F);
2092  auto &ORE = FAM.getResult<OptimizationRemarkEmitterAnalysis>(F);
2093  bool Changed = CHR(F, BFI, DT, PSI, RI, ORE).run();
2094  if (!Changed)
2095  return PreservedAnalyses::all();
2096  auto PA = PreservedAnalyses();
2097  PA.preserve<GlobalsAA>();
2098  return PA;
2099 }
2100 
2101 } // namespace llvm
Legacy wrapper pass to provide the GlobalsAAResult object.
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks &#39;this&#39; from the containing basic block and deletes it.
Definition: Instruction.cpp:67
static ConstantInt * getFalse(LLVMContext &Context)
Definition: Constants.cpp:603
static bool checkMDProf(MDNode *MD, BranchProbability &TrueProb, BranchProbability &FalseProb)
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
raw_ostream & errs()
This returns a reference to a raw_ostream for standard error.
Diagnostic information for missed-optimization remarks.
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
uint64_t getZExtValue() const
Get zero extended value.
Definition: APInt.h:1569
DiagnosticInfoOptimizationBase::Argument NV
Result run(Function &F, FunctionAnalysisManager &AM)
Run the analysis pass over a function and produce BFI.
void dropAllReferences()
Drop all references to operands.
Definition: User.h:294
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:776
This class represents lattice values for constants.
Definition: AllocatorList.h:23
This is the interface for a simple mod/ref and alias analysis over globals.
Value * CreateXor(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:1320
static bool checkBias(K *Key, BranchProbability TrueProb, BranchProbability FalseProb, S &TrueSet, S &FalseSet, M &BiasMap)
Implements a dense probed hash-table based set.
Definition: DenseSet.h:249
static DenseSet< Value * > getCHRConditionValuesForRegion(RegInfo &RI)
Analysis providing profile information.
static bool checkHoistValue(Value *V, Instruction *InsertPoint, DominatorTree &DT, DenseSet< Instruction *> &Unhoistables, DenseSet< Instruction *> *HoistStops, DenseMap< Instruction *, bool > &Visited)
BasicBlock * getSuccessor(unsigned i) const
Metadata node.
Definition: Metadata.h:863
#define DEBUG_TYPE
StringRef getName() const
Get a short "name" for the module.
Definition: Module.h:227
static bool checkBiasedSelect(SelectInst *SI, Region *R, DenseSet< SelectInst *> &TrueBiasedSelectsGlobal, DenseSet< SelectInst *> &FalseBiasedSelectsGlobal, DenseMap< SelectInst *, BranchProbability > &SelectBiasMap)
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:230
F(f)
static void parseCHRFilterFiles()
static cl::opt< double > CHRBiasThreshold("chr-bias-threshold", cl::init(0.99), cl::Hidden, cl::desc("CHR considers a branch bias greater than this ratio as biased"))
static void hoistScopeConditions(CHRScope *Scope, Instruction *HoistPoint, DenseSet< PHINode *> &TrivialPHIs, DominatorTree &DT)
const MDOperand & getOperand(unsigned I) const
Definition: Metadata.h:1068
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.cpp:137
iv Induction Variable Users
Definition: IVUsers.cpp:51
static void getSelectsInScope(CHRScope *Scope, DenseSet< Instruction *> &Output)
BlockT * getExit() const
Get the exit BasicBlock of the Region.
Definition: RegionInfo.h:360
static BranchProbability getCHRBiasThreshold()
return AArch64::GPR64RegClass contains(Reg)
void dump() const
Support for debugging, callable in GDB: V->dump()
Definition: AsmWriter.cpp:4428
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:50
void append(SmallVectorImpl< char > &path, const Twine &a, const Twine &b="", const Twine &c="", const Twine &d="")
Append to path.
Definition: Path.cpp:455
coro split
Definition: CoroSplit.cpp:1597
This class represents the LLVM &#39;select&#39; instruction.
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE, etc.
Definition: InstrTypes.h:831
An analysis pass based on legacy pass manager to deliver ProfileSummaryInfo.
static bool checkBiasedBranch(BranchInst *BI, Region *R, DenseSet< Region *> &TrueBiasedRegionsGlobal, DenseSet< Region *> &FalseBiasedRegionsGlobal, DenseMap< Region *, BranchProbability > &BranchBiasMap)
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:41
iterator end()
Definition: RegionInfo.h:562
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:779
Legacy analysis pass which computes BlockFrequencyInfo.
static bool shouldApply(Function &F, ProfileSummaryInfo &PSI)
static void LLVM_ATTRIBUTE_UNUSED assertBranchOrSelectConditionHoisted(CHRScope *Scope, BasicBlock *PreEntryBlock)
block placement Basic Block Placement Stats
static cl::opt< unsigned > CHRMergeThreshold("chr-merge-threshold", cl::init(2), cl::Hidden, cl::desc("CHR merges a group of N branches/selects where N >= this value"))
static cl::opt< bool > ForceCHR("force-chr", cl::init(false), cl::Hidden, cl::desc("Apply CHR for all functions"))
Key
PAL metadata keys.
static cl::opt< std::string > CHRFunctionList("chr-function-list", cl::init(""), cl::Hidden, cl::desc("Specify file to retrieve the list of functions to apply CHR to"))
const T & getValue() const LLVM_LVALUE_FUNCTION
Definition: Optional.h:255
iterator find(const KeyT &Val)
Definition: ValueMap.h:161
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
Definition: Instruction.h:234
const APInt & getValue() const
Return the constant as an APInt value reference.
Definition: Constants.h:137
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:144
If this flag is set, the remapper knows that only local values within a function (such as an instruct...
Definition: ValueMapper.h:72
StringRef getString() const
Definition: Metadata.cpp:463
bool hasProfileSummary()
Returns true if profile summary is available.
BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...
static bool runOnFunction(Function &F, bool PostInlining)
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:432
static bool shouldSplit(Instruction *InsertPoint, DenseSet< Value *> &PrevConditionValues, DenseSet< Value *> &ConditionValues, DominatorTree &DT, DenseSet< Instruction *> &Unhoistables)
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:153
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
Definition: BasicBlock.cpp:233
static void insertTrivialPHIs(CHRScope *Scope, BasicBlock *EntryBlock, BasicBlock *ExitBlock, DenseSet< PHINode *> &TrivialPHIs)
size_type count(StringRef Key) const
count - Return 1 if the element is in the map, 0 otherwise.
Definition: StringMap.h:358
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
Conditional or Unconditional Branch instruction.
An analysis pass based on the new PM to deliver ProfileSummaryInfo.
static std::set< Value * > getBaseValues(Value *V, DominatorTree &DT)
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static StringSet CHRFunctions
static cl::opt< std::string > CHRModuleList("chr-module-list", cl::init(""), cl::Hidden, cl::desc("Specify file to retrieve the list of modules to apply CHR to"))
const Instruction & front() const
Definition: BasicBlock.h:280
Diagnostic information for applied optimization remarks.
Interval::pred_iterator pred_begin(Interval *I)
pred_begin/pred_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:112
Represent the analysis usage information of a pass.
PreservedAnalyses run(Function &F, FunctionAnalysisManager &FAM)
#define LLVM_ATTRIBUTE_UNUSED
Definition: Compiler.h:167
This instruction compares its operands according to the predicate given to the constructor.
Analysis pass providing a never-invalidated alias analysis result.
static bool isHoistableInstructionType(Instruction *I)
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:284
Interval::pred_iterator pred_end(Interval *I)
Definition: Interval.h:115
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
self_iterator getIterator()
Definition: ilist_node.h:81
auto find_if(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range))
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1205
bool isTopLevelRegion() const
Check if a Region is the TopLevel region.
Definition: RegionInfo.h:386
auto remove_if(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range))
Provide wrappers to std::remove_if which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1217
const Value * getCondition() const
void initializeControlHeightReductionLegacyPassPass(PassRegistry &)
Used in the streaming interface as the general argument type.
static void LLVM_ATTRIBUTE_UNUSED assertCHRRegionsHaveBiasedBranchOrSelect(CHRScope *Scope)
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:159
Class to represent profile counts.
Definition: Function.h:260
size_t size() const
Definition: SmallVector.h:52
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
void setMetadata(unsigned KindID, MDNode *Node)
Set the metadata of the specified kind to the specified node.
Definition: Metadata.cpp:1222
std::pair< typename base::iterator, bool > insert(StringRef Key)
Definition: StringSet.h:38
iterator begin()
Definition: RegionInfo.h:561
iterator end()
Definition: ValueMap.h:141
const InstListType & getInstList() const
Return the underlying instruction list container.
Definition: BasicBlock.h:333
Analysis pass which computes BlockFrequencyInfo.
This is the shared class of boolean and integer constants.
Definition: Constants.h:83
BlockT * getEntry() const
Get the entry BasicBlock of the Region.
Definition: RegionInfo.h:323
An analysis over an "inner" IR unit that provides access to an analysis manager over a "outer" IR uni...
Definition: PassManager.h:1160
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:837
bool dominates(const Instruction *Def, const Use &U) const
Return true if Def dominates a use in User.
Definition: Dominators.cpp:248
LLVM_NODISCARD std::pair< StringRef, StringRef > split(char Separator) const
Split into two substrings around the first occurrence of a separator character.
Definition: StringRef.h:696
static BranchProbability getBranchProbability(uint64_t Numerator, uint64_t Denominator)
static bool negateICmpIfUsedByBranchOrSelectOnly(ICmpInst *ICmp, Instruction *ExcludedUser, CHRScope *Scope)
static BranchInst * Create(BasicBlock *IfTrue, Instruction *InsertBefore=nullptr)
bool isConditional() const
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
pred_range predecessors(BasicBlock *BB)
Definition: CFG.h:124
static void LLVM_ATTRIBUTE_UNUSED dumpScopes(SmallVectorImpl< CHRScope *> &Scopes, const char *Label)
static ConstantInt * getTrue(LLVMContext &Context)
Definition: Constants.cpp:596
void setPredicate(Predicate P)
Set the predicate for this instruction to the specified value.
Definition: InstrTypes.h:812
Analysis pass that exposes the RegionInfo for a function.
Definition: RegionInfo.h:971
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:940
static StringSet CHRModules
void push_back(pointer val)
Definition: ilist.h:311
BasicBlock * CloneBasicBlock(const BasicBlock *BB, ValueToValueMapTy &VMap, const Twine &NameSuffix="", Function *F=nullptr, ClonedCodeInfo *CodeInfo=nullptr, DebugInfoFinder *DIFinder=nullptr)
Return a copy of the specified basic block, but without embedding the block into a particular functio...
iterator_range< user_iterator > users()
Definition: Value.h:419
void RemapInstruction(Instruction *I, ValueToValueMapTy &VM, RemapFlags Flags=RF_None, ValueMapTypeRemapper *TypeMapper=nullptr, ValueMaterializer *Materializer=nullptr)
Convert the instruction operands from referencing the current values into those specified by VM...
Definition: ValueMapper.h:251
static cl::opt< unsigned > Threshold("loop-unswitch-threshold", cl::desc("Max loop size to unswitch"), cl::init(100), cl::Hidden)
iterator insert(iterator I, T &&Elt)
Definition: SmallVector.h:467
void setCondition(Value *V)
If this flag is set, the remapper ignores missing function-local entries (Argument, Instruction, BasicBlock) that are not in the value map.
Definition: ValueMapper.h:90
static cl::opt< ITMode > IT(cl::desc("IT block support"), cl::Hidden, cl::init(DefaultIT), cl::ZeroOrMore, cl::values(clEnumValN(DefaultIT, "arm-default-it", "Generate IT block based on arch"), clEnumValN(RestrictedIT, "arm-restrict-it", "Disallow deprecated IT based on ARMv8"), clEnumValN(NoRestrictedIT, "arm-no-restrict-it", "Allow IT blocks based on ARMv7")))
static void LLVM_ATTRIBUTE_UNUSED dumpIR(Function &F, const char *Label, CHRStats *Stats)
std::string getNameStr() const
Returns the name of the Region.
Predicate getPredicate() const
Return the predicate for this instruction.
Definition: InstrTypes.h:807
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
bool isFunctionEntryHot(const Function *F)
Returns true if F has hot function entry.
bool contains(const BlockT *BB) const
Check if the region contains a BasicBlock.
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:55
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:214
static bool isHoistable(Instruction *I, DominatorTree &DT)
#define I(x, y, z)
Definition: MD5.cpp:58
static bool hasAtLeastTwoBiasedBranches(CHRScope *Scope)
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:332
static void hoistValue(Value *V, Instruction *HoistPoint, Region *R, HoistStopMapTy &HoistStopMap, DenseSet< Instruction *> &HoistedSet, DenseSet< PHINode *> &TrivialPHIs, DominatorTree &DT)
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
Definition: BasicBlock.h:324
size_type count(const_arg_type_t< ValueT > V) const
Return 1 if the specified key is in the set, 0 otherwise.
Definition: DenseSet.h:91
bool isUnconditional() const
raw_ostream & operator<<(raw_ostream &OS, const APInt &I)
Definition: APInt.h:2045
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
Definition: DenseMap.h:171
Value * CreateAnd(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:1268
void setCondition(Value *V)
static ErrorOr< std::unique_ptr< MemoryBuffer > > getFile(const Twine &Filename, int64_t FileSize=-1, bool RequiresNullTerminator=true, bool IsVolatile=false)
Open the specified file as a MemoryBuffer, returning a new MemoryBuffer if successful, otherwise returning null.
RegionT * getParent() const
Get the parent of the Region.
Definition: RegionInfo.h:365
static Instruction * getBranchInsertPoint(RegInfo &RI)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
bool isSafeToSpeculativelyExecute(const Value *V, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr)
Return true if the instruction does not have any effects besides calculating the result and does not ...
void stable_sort(R &&Range)
Definition: STLExtras.h:1301
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:575
LLVM Value Representation.
Definition: Value.h:73
StringSet - A wrapper for StringMap that provides set-like functionality.
Definition: StringSet.h:27
BasicBlock * SplitBlock(BasicBlock *Old, Instruction *SplitPt, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr)
Split the specified block at the specified instruction - everything before SplitPt stays in Old and e...
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:45
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:48
A single uniqued string.
Definition: Metadata.h:603
FunctionPass * createControlHeightReductionLegacyPass()
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:259
bool CHRScopeSorter(CHRScope *Scope1, CHRScope *Scope2)
#define CHR_DEBUG(X)
INITIALIZE_PASS_BEGIN(ControlHeightReductionLegacyPass, "chr", "Reduce control height in the hot paths", false, false) INITIALIZE_PASS_END(ControlHeightReductionLegacyPass
unsigned getNumOperands() const
Return number of MDNode operands.
Definition: Metadata.h:1074
OutputIt copy(R &&Range, OutputIt Out)
Definition: STLExtras.h:1229
iterator_range< element_iterator > elements()
Definition: RegionInfo.h:653
The optimization diagnostic interface.
const BasicBlock * getParent() const
Definition: Instruction.h:66
void resize(size_type N)
Definition: SmallVector.h:344