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(
516  Value *V, DominatorTree &DT,
517  DenseMap<Value *, std::set<Value *>> &Visited) {
518  if (Visited.count(V)) {
519  return Visited[V];
520  }
521  std::set<Value *> Result;
522  if (auto *I = dyn_cast<Instruction>(V)) {
523  // We don't stop at a block that's not in the Scope because we would miss some
524  // instructions that are based on the same base values if we stop there.
525  if (!isHoistable(I, DT)) {
526  Result.insert(I);
527  Visited.insert(std::make_pair(V, Result));
528  return Result;
529  }
530  // I is hoistable above the Scope.
531  for (Value *Op : I->operands()) {
532  std::set<Value *> OpResult = getBaseValues(Op, DT, Visited);
533  Result.insert(OpResult.begin(), OpResult.end());
534  }
535  Visited.insert(std::make_pair(V, Result));
536  return Result;
537  }
538  if (isa<Argument>(V)) {
539  Result.insert(V);
540  Visited.insert(std::make_pair(V, Result));
541  return Result;
542  }
543  // We don't include others like constants because those won't lead to any
544  // chance of folding of conditions (eg two bit checks merged into one check)
545  // after CHR.
546  Visited.insert(std::make_pair(V, Result));
547  return Result; // empty
548 }
549 
550 // Return true if V is already hoisted or can be hoisted (along with its
551 // operands) above the insert point. When it returns true and HoistStops is
552 // non-null, the instructions to stop hoisting at through the use-def chains are
553 // inserted into HoistStops.
554 static bool
556  DenseSet<Instruction *> &Unhoistables,
557  DenseSet<Instruction *> *HoistStops,
559  assert(InsertPoint && "Null InsertPoint");
560  if (auto *I = dyn_cast<Instruction>(V)) {
561  if (Visited.count(I)) {
562  return Visited[I];
563  }
564  assert(DT.getNode(I->getParent()) && "DT must contain I's parent block");
565  assert(DT.getNode(InsertPoint->getParent()) && "DT must contain Destination");
566  if (Unhoistables.count(I)) {
567  // Don't hoist if they are not to be hoisted.
568  Visited[I] = false;
569  return false;
570  }
571  if (DT.dominates(I, InsertPoint)) {
572  // We are already above the insert point. Stop here.
573  if (HoistStops)
574  HoistStops->insert(I);
575  Visited[I] = true;
576  return true;
577  }
578  // We aren't not above the insert point, check if we can hoist it above the
579  // insert point.
580  if (isHoistable(I, DT)) {
581  // Check operands first.
582  DenseSet<Instruction *> OpsHoistStops;
583  bool AllOpsHoisted = true;
584  for (Value *Op : I->operands()) {
585  if (!checkHoistValue(Op, InsertPoint, DT, Unhoistables, &OpsHoistStops,
586  Visited)) {
587  AllOpsHoisted = false;
588  break;
589  }
590  }
591  if (AllOpsHoisted) {
592  CHR_DEBUG(dbgs() << "checkHoistValue " << *I << "\n");
593  if (HoistStops)
594  HoistStops->insert(OpsHoistStops.begin(), OpsHoistStops.end());
595  Visited[I] = true;
596  return true;
597  }
598  }
599  Visited[I] = false;
600  return false;
601  }
602  // Non-instructions are considered hoistable.
603  return true;
604 }
605 
606 // Returns true and sets the true probability and false probability of an
607 // MD_prof metadata if it's well-formed.
608 static bool checkMDProf(MDNode *MD, BranchProbability &TrueProb,
609  BranchProbability &FalseProb) {
610  if (!MD) return false;
611  MDString *MDName = cast<MDString>(MD->getOperand(0));
612  if (MDName->getString() != "branch_weights" ||
613  MD->getNumOperands() != 3)
614  return false;
615  ConstantInt *TrueWeight = mdconst::extract<ConstantInt>(MD->getOperand(1));
616  ConstantInt *FalseWeight = mdconst::extract<ConstantInt>(MD->getOperand(2));
617  if (!TrueWeight || !FalseWeight)
618  return false;
619  uint64_t TrueWt = TrueWeight->getValue().getZExtValue();
620  uint64_t FalseWt = FalseWeight->getValue().getZExtValue();
621  uint64_t SumWt = TrueWt + FalseWt;
622 
623  assert(SumWt >= TrueWt && SumWt >= FalseWt &&
624  "Overflow calculating branch probabilities.");
625 
626  TrueProb = BranchProbability::getBranchProbability(TrueWt, SumWt);
627  FalseProb = BranchProbability::getBranchProbability(FalseWt, SumWt);
628  return true;
629 }
630 
633  static_cast<uint64_t>(CHRBiasThreshold * 1000000), 1000000);
634 }
635 
636 // A helper for CheckBiasedBranch and CheckBiasedSelect. If TrueProb >=
637 // CHRBiasThreshold, put Key into TrueSet and return true. If FalseProb >=
638 // CHRBiasThreshold, put Key into FalseSet and return true. Otherwise, return
639 // false.
640 template <typename K, typename S, typename M>
641 static bool checkBias(K *Key, BranchProbability TrueProb,
642  BranchProbability FalseProb, S &TrueSet, S &FalseSet,
643  M &BiasMap) {
645  if (TrueProb >= Threshold) {
646  TrueSet.insert(Key);
647  BiasMap[Key] = TrueProb;
648  return true;
649  } else if (FalseProb >= Threshold) {
650  FalseSet.insert(Key);
651  BiasMap[Key] = FalseProb;
652  return true;
653  }
654  return false;
655 }
656 
657 // Returns true and insert a region into the right biased set and the map if the
658 // branch of the region is biased.
659 static bool checkBiasedBranch(BranchInst *BI, Region *R,
660  DenseSet<Region *> &TrueBiasedRegionsGlobal,
661  DenseSet<Region *> &FalseBiasedRegionsGlobal,
662  DenseMap<Region *, BranchProbability> &BranchBiasMap) {
663  if (!BI->isConditional())
664  return false;
665  BranchProbability ThenProb, ElseProb;
666  if (!checkMDProf(BI->getMetadata(LLVMContext::MD_prof),
667  ThenProb, ElseProb))
668  return false;
669  BasicBlock *IfThen = BI->getSuccessor(0);
670  BasicBlock *IfElse = BI->getSuccessor(1);
671  assert((IfThen == R->getExit() || IfElse == R->getExit()) &&
672  IfThen != IfElse &&
673  "Invariant from findScopes");
674  if (IfThen == R->getExit()) {
675  // Swap them so that IfThen/ThenProb means going into the conditional code
676  // and IfElse/ElseProb means skipping it.
677  std::swap(IfThen, IfElse);
678  std::swap(ThenProb, ElseProb);
679  }
680  CHR_DEBUG(dbgs() << "BI " << *BI << " ");
681  CHR_DEBUG(dbgs() << "ThenProb " << ThenProb << " ");
682  CHR_DEBUG(dbgs() << "ElseProb " << ElseProb << "\n");
683  return checkBias(R, ThenProb, ElseProb,
684  TrueBiasedRegionsGlobal, FalseBiasedRegionsGlobal,
685  BranchBiasMap);
686 }
687 
688 // Returns true and insert a select into the right biased set and the map if the
689 // select is biased.
690 static bool checkBiasedSelect(
691  SelectInst *SI, Region *R,
692  DenseSet<SelectInst *> &TrueBiasedSelectsGlobal,
693  DenseSet<SelectInst *> &FalseBiasedSelectsGlobal,
695  BranchProbability TrueProb, FalseProb;
696  if (!checkMDProf(SI->getMetadata(LLVMContext::MD_prof),
697  TrueProb, FalseProb))
698  return false;
699  CHR_DEBUG(dbgs() << "SI " << *SI << " ");
700  CHR_DEBUG(dbgs() << "TrueProb " << TrueProb << " ");
701  CHR_DEBUG(dbgs() << "FalseProb " << FalseProb << "\n");
702  return checkBias(SI, TrueProb, FalseProb,
703  TrueBiasedSelectsGlobal, FalseBiasedSelectsGlobal,
704  SelectBiasMap);
705 }
706 
707 // Returns the instruction at which to hoist the dependent condition values and
708 // insert the CHR branch for a region. This is the terminator branch in the
709 // entry block or the first select in the entry block, if any.
710 static Instruction* getBranchInsertPoint(RegInfo &RI) {
711  Region *R = RI.R;
712  BasicBlock *EntryBB = R->getEntry();
713  // The hoist point is by default the terminator of the entry block, which is
714  // the same as the branch instruction if RI.HasBranch is true.
715  Instruction *HoistPoint = EntryBB->getTerminator();
716  for (SelectInst *SI : RI.Selects) {
717  if (SI->getParent() == EntryBB) {
718  // Pick the first select in Selects in the entry block. Note Selects is
719  // sorted in the instruction order within a block (asserted below).
720  HoistPoint = SI;
721  break;
722  }
723  }
724  assert(HoistPoint && "Null HoistPoint");
725 #ifndef NDEBUG
726  // Check that HoistPoint is the first one in Selects in the entry block,
727  // if any.
728  DenseSet<Instruction *> EntryBlockSelectSet;
729  for (SelectInst *SI : RI.Selects) {
730  if (SI->getParent() == EntryBB) {
731  EntryBlockSelectSet.insert(SI);
732  }
733  }
734  for (Instruction &I : *EntryBB) {
735  if (EntryBlockSelectSet.count(&I) > 0) {
736  assert(&I == HoistPoint &&
737  "HoistPoint must be the first one in Selects");
738  break;
739  }
740  }
741 #endif
742  return HoistPoint;
743 }
744 
745 // Find a CHR scope in the given region.
746 CHRScope * CHR::findScope(Region *R) {
747  CHRScope *Result = nullptr;
748  BasicBlock *Entry = R->getEntry();
749  BasicBlock *Exit = R->getExit(); // null if top level.
750  assert(Entry && "Entry must not be null");
751  assert((Exit == nullptr) == (R->isTopLevelRegion()) &&
752  "Only top level region has a null exit");
753  if (Entry)
754  CHR_DEBUG(dbgs() << "Entry " << Entry->getName() << "\n");
755  else
756  CHR_DEBUG(dbgs() << "Entry null\n");
757  if (Exit)
758  CHR_DEBUG(dbgs() << "Exit " << Exit->getName() << "\n");
759  else
760  CHR_DEBUG(dbgs() << "Exit null\n");
761  // Exclude cases where Entry is part of a subregion (hence it doesn't belong
762  // to this region).
763  bool EntryInSubregion = RI.getRegionFor(Entry) != R;
764  if (EntryInSubregion)
765  return nullptr;
766  // Exclude loops
767  for (BasicBlock *Pred : predecessors(Entry))
768  if (R->contains(Pred))
769  return nullptr;
770  if (Exit) {
771  // Try to find an if-then block (check if R is an if-then).
772  // if (cond) {
773  // ...
774  // }
775  auto *BI = dyn_cast<BranchInst>(Entry->getTerminator());
776  if (BI)
777  CHR_DEBUG(dbgs() << "BI.isConditional " << BI->isConditional() << "\n");
778  else
779  CHR_DEBUG(dbgs() << "BI null\n");
780  if (BI && BI->isConditional()) {
781  BasicBlock *S0 = BI->getSuccessor(0);
782  BasicBlock *S1 = BI->getSuccessor(1);
783  CHR_DEBUG(dbgs() << "S0 " << S0->getName() << "\n");
784  CHR_DEBUG(dbgs() << "S1 " << S1->getName() << "\n");
785  if (S0 != S1 && (S0 == Exit || S1 == Exit)) {
786  RegInfo RI(R);
787  RI.HasBranch = checkBiasedBranch(
788  BI, R, TrueBiasedRegionsGlobal, FalseBiasedRegionsGlobal,
789  BranchBiasMap);
790  Result = new CHRScope(RI);
791  Scopes.insert(Result);
792  CHR_DEBUG(dbgs() << "Found a region with a branch\n");
793  ++Stats.NumBranches;
794  if (!RI.HasBranch) {
795  ORE.emit([&]() {
796  return OptimizationRemarkMissed(DEBUG_TYPE, "BranchNotBiased", BI)
797  << "Branch not biased";
798  });
799  }
800  }
801  }
802  }
803  {
804  // Try to look for selects in the direct child blocks (as opposed to in
805  // subregions) of R.
806  // ...
807  // if (..) { // Some subregion
808  // ...
809  // }
810  // if (..) { // Some subregion
811  // ...
812  // }
813  // ...
814  // a = cond ? b : c;
815  // ...
817  for (RegionNode *E : R->elements()) {
818  if (E->isSubRegion())
819  continue;
820  // This returns the basic block of E if E is a direct child of R (not a
821  // subregion.)
822  BasicBlock *BB = E->getEntry();
823  // Need to push in the order to make it easier to find the first Select
824  // later.
825  for (Instruction &I : *BB) {
826  if (auto *SI = dyn_cast<SelectInst>(&I)) {
827  Selects.push_back(SI);
828  ++Stats.NumBranches;
829  }
830  }
831  }
832  if (Selects.size() > 0) {
833  auto AddSelects = [&](RegInfo &RI) {
834  for (auto *SI : Selects)
835  if (checkBiasedSelect(SI, RI.R,
836  TrueBiasedSelectsGlobal,
837  FalseBiasedSelectsGlobal,
838  SelectBiasMap))
839  RI.Selects.push_back(SI);
840  else
841  ORE.emit([&]() {
842  return OptimizationRemarkMissed(DEBUG_TYPE, "SelectNotBiased", SI)
843  << "Select not biased";
844  });
845  };
846  if (!Result) {
847  CHR_DEBUG(dbgs() << "Found a select-only region\n");
848  RegInfo RI(R);
849  AddSelects(RI);
850  Result = new CHRScope(RI);
851  Scopes.insert(Result);
852  } else {
853  CHR_DEBUG(dbgs() << "Found select(s) in a region with a branch\n");
854  AddSelects(Result->RegInfos[0]);
855  }
856  }
857  }
858 
859  if (Result) {
860  checkScopeHoistable(Result);
861  }
862  return Result;
863 }
864 
865 // Check that any of the branch and the selects in the region could be
866 // hoisted above the the CHR branch insert point (the most dominating of
867 // them, either the branch (at the end of the first block) or the first
868 // select in the first block). If the branch can't be hoisted, drop the
869 // selects in the first blocks.
870 //
871 // For example, for the following scope/region with selects, we want to insert
872 // the merged branch right before the first select in the first/entry block by
873 // hoisting c1, c2, c3, and c4.
874 //
875 // // Branch insert point here.
876 // a = c1 ? b : c; // Select 1
877 // d = c2 ? e : f; // Select 2
878 // if (c3) { // Branch
879 // ...
880 // c4 = foo() // A call.
881 // g = c4 ? h : i; // Select 3
882 // }
883 //
884 // But suppose we can't hoist c4 because it's dependent on the preceding
885 // call. Then, we drop Select 3. Furthermore, if we can't hoist c2, we also drop
886 // Select 2. If we can't hoist c3, we drop Selects 1 & 2.
887 void CHR::checkScopeHoistable(CHRScope *Scope) {
888  RegInfo &RI = Scope->RegInfos[0];
889  Region *R = RI.R;
890  BasicBlock *EntryBB = R->getEntry();
891  auto *Branch = RI.HasBranch ?
892  cast<BranchInst>(EntryBB->getTerminator()) : nullptr;
893  SmallVector<SelectInst *, 8> &Selects = RI.Selects;
894  if (RI.HasBranch || !Selects.empty()) {
895  Instruction *InsertPoint = getBranchInsertPoint(RI);
896  CHR_DEBUG(dbgs() << "InsertPoint " << *InsertPoint << "\n");
897  // Avoid a data dependence from a select or a branch to a(nother)
898  // select. Note no instruction can't data-depend on a branch (a branch
899  // instruction doesn't produce a value).
900  DenseSet<Instruction *> Unhoistables;
901  // Initialize Unhoistables with the selects.
902  for (SelectInst *SI : Selects) {
903  Unhoistables.insert(SI);
904  }
905  // Remove Selects that can't be hoisted.
906  for (auto it = Selects.begin(); it != Selects.end(); ) {
907  SelectInst *SI = *it;
908  if (SI == InsertPoint) {
909  ++it;
910  continue;
911  }
913  bool IsHoistable = checkHoistValue(SI->getCondition(), InsertPoint,
914  DT, Unhoistables, nullptr, Visited);
915  if (!IsHoistable) {
916  CHR_DEBUG(dbgs() << "Dropping select " << *SI << "\n");
917  ORE.emit([&]() {
919  "DropUnhoistableSelect", SI)
920  << "Dropped unhoistable select";
921  });
922  it = Selects.erase(it);
923  // Since we are dropping the select here, we also drop it from
924  // Unhoistables.
925  Unhoistables.erase(SI);
926  } else
927  ++it;
928  }
929  // Update InsertPoint after potentially removing selects.
930  InsertPoint = getBranchInsertPoint(RI);
931  CHR_DEBUG(dbgs() << "InsertPoint " << *InsertPoint << "\n");
932  if (RI.HasBranch && InsertPoint != Branch) {
934  bool IsHoistable = checkHoistValue(Branch->getCondition(), InsertPoint,
935  DT, Unhoistables, nullptr, Visited);
936  if (!IsHoistable) {
937  // If the branch isn't hoistable, drop the selects in the entry
938  // block, preferring the branch, which makes the branch the hoist
939  // point.
940  assert(InsertPoint != Branch && "Branch must not be the hoist point");
941  CHR_DEBUG(dbgs() << "Dropping selects in entry block \n");
942  CHR_DEBUG(
943  for (SelectInst *SI : Selects) {
944  dbgs() << "SI " << *SI << "\n";
945  });
946  for (SelectInst *SI : Selects) {
947  ORE.emit([&]() {
949  "DropSelectUnhoistableBranch", SI)
950  << "Dropped select due to unhoistable branch";
951  });
952  }
953  Selects.erase(std::remove_if(Selects.begin(), Selects.end(),
954  [EntryBB](SelectInst *SI) {
955  return SI->getParent() == EntryBB;
956  }), Selects.end());
957  Unhoistables.clear();
958  InsertPoint = Branch;
959  }
960  }
961  CHR_DEBUG(dbgs() << "InsertPoint " << *InsertPoint << "\n");
962 #ifndef NDEBUG
963  if (RI.HasBranch) {
964  assert(!DT.dominates(Branch, InsertPoint) &&
965  "Branch can't be already above the hoist point");
967  assert(checkHoistValue(Branch->getCondition(), InsertPoint,
968  DT, Unhoistables, nullptr, Visited) &&
969  "checkHoistValue for branch");
970  }
971  for (auto *SI : Selects) {
972  assert(!DT.dominates(SI, InsertPoint) &&
973  "SI can't be already above the hoist point");
975  assert(checkHoistValue(SI->getCondition(), InsertPoint, DT,
976  Unhoistables, nullptr, Visited) &&
977  "checkHoistValue for selects");
978  }
979  CHR_DEBUG(dbgs() << "Result\n");
980  if (RI.HasBranch) {
981  CHR_DEBUG(dbgs() << "BI " << *Branch << "\n");
982  }
983  for (auto *SI : Selects) {
984  CHR_DEBUG(dbgs() << "SI " << *SI << "\n");
985  }
986 #endif
987  }
988 }
989 
990 // Traverse the region tree, find all nested scopes and merge them if possible.
991 CHRScope * CHR::findScopes(Region *R, Region *NextRegion, Region *ParentRegion,
992  SmallVectorImpl<CHRScope *> &Scopes) {
993  CHR_DEBUG(dbgs() << "findScopes " << R->getNameStr() << "\n");
994  CHRScope *Result = findScope(R);
995  // Visit subscopes.
996  CHRScope *ConsecutiveSubscope = nullptr;
997  SmallVector<CHRScope *, 8> Subscopes;
998  for (auto It = R->begin(); It != R->end(); ++It) {
999  const std::unique_ptr<Region> &SubR = *It;
1000  auto NextIt = std::next(It);
1001  Region *NextSubR = NextIt != R->end() ? NextIt->get() : nullptr;
1002  CHR_DEBUG(dbgs() << "Looking at subregion " << SubR.get()->getNameStr()
1003  << "\n");
1004  CHRScope *SubCHRScope = findScopes(SubR.get(), NextSubR, R, Scopes);
1005  if (SubCHRScope) {
1006  CHR_DEBUG(dbgs() << "Subregion Scope " << *SubCHRScope << "\n");
1007  } else {
1008  CHR_DEBUG(dbgs() << "Subregion Scope null\n");
1009  }
1010  if (SubCHRScope) {
1011  if (!ConsecutiveSubscope)
1012  ConsecutiveSubscope = SubCHRScope;
1013  else if (!ConsecutiveSubscope->appendable(SubCHRScope)) {
1014  Subscopes.push_back(ConsecutiveSubscope);
1015  ConsecutiveSubscope = SubCHRScope;
1016  } else
1017  ConsecutiveSubscope->append(SubCHRScope);
1018  } else {
1019  if (ConsecutiveSubscope) {
1020  Subscopes.push_back(ConsecutiveSubscope);
1021  }
1022  ConsecutiveSubscope = nullptr;
1023  }
1024  }
1025  if (ConsecutiveSubscope) {
1026  Subscopes.push_back(ConsecutiveSubscope);
1027  }
1028  for (CHRScope *Sub : Subscopes) {
1029  if (Result) {
1030  // Combine it with the parent.
1031  Result->addSub(Sub);
1032  } else {
1033  // Push Subscopes as they won't be combined with the parent.
1034  Scopes.push_back(Sub);
1035  }
1036  }
1037  return Result;
1038 }
1039 
1041  DenseSet<Value *> ConditionValues;
1042  if (RI.HasBranch) {
1043  auto *BI = cast<BranchInst>(RI.R->getEntry()->getTerminator());
1044  ConditionValues.insert(BI->getCondition());
1045  }
1046  for (SelectInst *SI : RI.Selects) {
1047  ConditionValues.insert(SI->getCondition());
1048  }
1049  return ConditionValues;
1050 }
1051 
1052 
1053 // Determine whether to split a scope depending on the sets of the branch
1054 // condition values of the previous region and the current region. We split
1055 // (return true) it if 1) the condition values of the inner/lower scope can't be
1056 // hoisted up to the outer/upper scope, or 2) the two sets of the condition
1057 // values have an empty intersection (because the combined branch conditions
1058 // won't probably lead to a simpler combined condition).
1059 static bool shouldSplit(Instruction *InsertPoint,
1060  DenseSet<Value *> &PrevConditionValues,
1061  DenseSet<Value *> &ConditionValues,
1062  DominatorTree &DT,
1063  DenseSet<Instruction *> &Unhoistables) {
1064  CHR_DEBUG(
1065  dbgs() << "shouldSplit " << *InsertPoint << " PrevConditionValues ";
1066  for (Value *V : PrevConditionValues) {
1067  dbgs() << *V << ", ";
1068  }
1069  dbgs() << " ConditionValues ";
1070  for (Value *V : ConditionValues) {
1071  dbgs() << *V << ", ";
1072  }
1073  dbgs() << "\n");
1074  assert(InsertPoint && "Null InsertPoint");
1075  // If any of Bases isn't hoistable to the hoist point, split.
1076  for (Value *V : ConditionValues) {
1078  if (!checkHoistValue(V, InsertPoint, DT, Unhoistables, nullptr, Visited)) {
1079  CHR_DEBUG(dbgs() << "Split. checkHoistValue false " << *V << "\n");
1080  return true; // Not hoistable, split.
1081  }
1082  }
1083  // If PrevConditionValues or ConditionValues is empty, don't split to avoid
1084  // unnecessary splits at scopes with no branch/selects. If
1085  // PrevConditionValues and ConditionValues don't intersect at all, split.
1086  if (!PrevConditionValues.empty() && !ConditionValues.empty()) {
1087  // Use std::set as DenseSet doesn't work with set_intersection.
1088  std::set<Value *> PrevBases, Bases;
1090  for (Value *V : PrevConditionValues) {
1091  std::set<Value *> BaseValues = getBaseValues(V, DT, Visited);
1092  PrevBases.insert(BaseValues.begin(), BaseValues.end());
1093  }
1094  for (Value *V : ConditionValues) {
1095  std::set<Value *> BaseValues = getBaseValues(V, DT, Visited);
1096  Bases.insert(BaseValues.begin(), BaseValues.end());
1097  }
1098  CHR_DEBUG(
1099  dbgs() << "PrevBases ";
1100  for (Value *V : PrevBases) {
1101  dbgs() << *V << ", ";
1102  }
1103  dbgs() << " Bases ";
1104  for (Value *V : Bases) {
1105  dbgs() << *V << ", ";
1106  }
1107  dbgs() << "\n");
1108  std::set<Value *> Intersection;
1109  std::set_intersection(PrevBases.begin(), PrevBases.end(),
1110  Bases.begin(), Bases.end(),
1111  std::inserter(Intersection, Intersection.begin()));
1112  if (Intersection.empty()) {
1113  // Empty intersection, split.
1114  CHR_DEBUG(dbgs() << "Split. Intersection empty\n");
1115  return true;
1116  }
1117  }
1118  CHR_DEBUG(dbgs() << "No split\n");
1119  return false; // Don't split.
1120 }
1121 
1122 static void getSelectsInScope(CHRScope *Scope,
1123  DenseSet<Instruction *> &Output) {
1124  for (RegInfo &RI : Scope->RegInfos)
1125  for (SelectInst *SI : RI.Selects)
1126  Output.insert(SI);
1127  for (CHRScope *Sub : Scope->Subs)
1128  getSelectsInScope(Sub, Output);
1129 }
1130 
1131 void CHR::splitScopes(SmallVectorImpl<CHRScope *> &Input,
1132  SmallVectorImpl<CHRScope *> &Output) {
1133  for (CHRScope *Scope : Input) {
1134  assert(!Scope->BranchInsertPoint &&
1135  "BranchInsertPoint must not be set");
1136  DenseSet<Instruction *> Unhoistables;
1137  getSelectsInScope(Scope, Unhoistables);
1138  splitScope(Scope, nullptr, nullptr, nullptr, Output, Unhoistables);
1139  }
1140 #ifndef NDEBUG
1141  for (CHRScope *Scope : Output) {
1142  assert(Scope->BranchInsertPoint && "BranchInsertPoint must be set");
1143  }
1144 #endif
1145 }
1146 
1147 SmallVector<CHRScope *, 8> CHR::splitScope(
1148  CHRScope *Scope,
1149  CHRScope *Outer,
1150  DenseSet<Value *> *OuterConditionValues,
1151  Instruction *OuterInsertPoint,
1153  DenseSet<Instruction *> &Unhoistables) {
1154  if (Outer) {
1155  assert(OuterConditionValues && "Null OuterConditionValues");
1156  assert(OuterInsertPoint && "Null OuterInsertPoint");
1157  }
1158  bool PrevSplitFromOuter = true;
1159  DenseSet<Value *> PrevConditionValues;
1160  Instruction *PrevInsertPoint = nullptr;
1162  SmallVector<bool, 8> SplitsSplitFromOuter;
1163  SmallVector<DenseSet<Value *>, 8> SplitsConditionValues;
1164  SmallVector<Instruction *, 8> SplitsInsertPoints;
1165  SmallVector<RegInfo, 8> RegInfos(Scope->RegInfos); // Copy
1166  for (RegInfo &RI : RegInfos) {
1167  Instruction *InsertPoint = getBranchInsertPoint(RI);
1168  DenseSet<Value *> ConditionValues = getCHRConditionValuesForRegion(RI);
1169  CHR_DEBUG(
1170  dbgs() << "ConditionValues ";
1171  for (Value *V : ConditionValues) {
1172  dbgs() << *V << ", ";
1173  }
1174  dbgs() << "\n");
1175  if (RI.R == RegInfos[0].R) {
1176  // First iteration. Check to see if we should split from the outer.
1177  if (Outer) {
1178  CHR_DEBUG(dbgs() << "Outer " << *Outer << "\n");
1179  CHR_DEBUG(dbgs() << "Should split from outer at "
1180  << RI.R->getNameStr() << "\n");
1181  if (shouldSplit(OuterInsertPoint, *OuterConditionValues,
1182  ConditionValues, DT, Unhoistables)) {
1183  PrevConditionValues = ConditionValues;
1184  PrevInsertPoint = InsertPoint;
1185  ORE.emit([&]() {
1187  "SplitScopeFromOuter",
1188  RI.R->getEntry()->getTerminator())
1189  << "Split scope from outer due to unhoistable branch/select "
1190  << "and/or lack of common condition values";
1191  });
1192  } else {
1193  // Not splitting from the outer. Use the outer bases and insert
1194  // point. Union the bases.
1195  PrevSplitFromOuter = false;
1196  PrevConditionValues = *OuterConditionValues;
1197  PrevConditionValues.insert(ConditionValues.begin(),
1198  ConditionValues.end());
1199  PrevInsertPoint = OuterInsertPoint;
1200  }
1201  } else {
1202  CHR_DEBUG(dbgs() << "Outer null\n");
1203  PrevConditionValues = ConditionValues;
1204  PrevInsertPoint = InsertPoint;
1205  }
1206  } else {
1207  CHR_DEBUG(dbgs() << "Should split from prev at "
1208  << RI.R->getNameStr() << "\n");
1209  if (shouldSplit(PrevInsertPoint, PrevConditionValues, ConditionValues,
1210  DT, Unhoistables)) {
1211  CHRScope *Tail = Scope->split(RI.R);
1212  Scopes.insert(Tail);
1213  Splits.push_back(Scope);
1214  SplitsSplitFromOuter.push_back(PrevSplitFromOuter);
1215  SplitsConditionValues.push_back(PrevConditionValues);
1216  SplitsInsertPoints.push_back(PrevInsertPoint);
1217  Scope = Tail;
1218  PrevConditionValues = ConditionValues;
1219  PrevInsertPoint = InsertPoint;
1220  PrevSplitFromOuter = true;
1221  ORE.emit([&]() {
1223  "SplitScopeFromPrev",
1224  RI.R->getEntry()->getTerminator())
1225  << "Split scope from previous due to unhoistable branch/select "
1226  << "and/or lack of common condition values";
1227  });
1228  } else {
1229  // Not splitting. Union the bases. Keep the hoist point.
1230  PrevConditionValues.insert(ConditionValues.begin(), ConditionValues.end());
1231  }
1232  }
1233  }
1234  Splits.push_back(Scope);
1235  SplitsSplitFromOuter.push_back(PrevSplitFromOuter);
1236  SplitsConditionValues.push_back(PrevConditionValues);
1237  assert(PrevInsertPoint && "Null PrevInsertPoint");
1238  SplitsInsertPoints.push_back(PrevInsertPoint);
1239  assert(Splits.size() == SplitsConditionValues.size() &&
1240  Splits.size() == SplitsSplitFromOuter.size() &&
1241  Splits.size() == SplitsInsertPoints.size() && "Mismatching sizes");
1242  for (size_t I = 0; I < Splits.size(); ++I) {
1243  CHRScope *Split = Splits[I];
1244  DenseSet<Value *> &SplitConditionValues = SplitsConditionValues[I];
1245  Instruction *SplitInsertPoint = SplitsInsertPoints[I];
1247  DenseSet<Instruction *> SplitUnhoistables;
1248  getSelectsInScope(Split, SplitUnhoistables);
1249  for (CHRScope *Sub : Split->Subs) {
1250  SmallVector<CHRScope *, 8> SubSplits = splitScope(
1251  Sub, Split, &SplitConditionValues, SplitInsertPoint, Output,
1252  SplitUnhoistables);
1253  NewSubs.insert(NewSubs.end(), SubSplits.begin(), SubSplits.end());
1254  }
1255  Split->Subs = NewSubs;
1256  }
1258  for (size_t I = 0; I < Splits.size(); ++I) {
1259  CHRScope *Split = Splits[I];
1260  if (SplitsSplitFromOuter[I]) {
1261  // Split from the outer.
1262  Output.push_back(Split);
1263  Split->BranchInsertPoint = SplitsInsertPoints[I];
1264  CHR_DEBUG(dbgs() << "BranchInsertPoint " << *SplitsInsertPoints[I]
1265  << "\n");
1266  } else {
1267  // Connected to the outer.
1268  Result.push_back(Split);
1269  }
1270  }
1271  if (!Outer)
1272  assert(Result.empty() &&
1273  "If no outer (top-level), must return no nested ones");
1274  return Result;
1275 }
1276 
1277 void CHR::classifyBiasedScopes(SmallVectorImpl<CHRScope *> &Scopes) {
1278  for (CHRScope *Scope : Scopes) {
1279  assert(Scope->TrueBiasedRegions.empty() && Scope->FalseBiasedRegions.empty() && "Empty");
1280  classifyBiasedScopes(Scope, Scope);
1281  CHR_DEBUG(
1282  dbgs() << "classifyBiasedScopes " << *Scope << "\n";
1283  dbgs() << "TrueBiasedRegions ";
1284  for (Region *R : Scope->TrueBiasedRegions) {
1285  dbgs() << R->getNameStr() << ", ";
1286  }
1287  dbgs() << "\n";
1288  dbgs() << "FalseBiasedRegions ";
1289  for (Region *R : Scope->FalseBiasedRegions) {
1290  dbgs() << R->getNameStr() << ", ";
1291  }
1292  dbgs() << "\n";
1293  dbgs() << "TrueBiasedSelects ";
1294  for (SelectInst *SI : Scope->TrueBiasedSelects) {
1295  dbgs() << *SI << ", ";
1296  }
1297  dbgs() << "\n";
1298  dbgs() << "FalseBiasedSelects ";
1299  for (SelectInst *SI : Scope->FalseBiasedSelects) {
1300  dbgs() << *SI << ", ";
1301  }
1302  dbgs() << "\n";);
1303  }
1304 }
1305 
1306 void CHR::classifyBiasedScopes(CHRScope *Scope, CHRScope *OutermostScope) {
1307  for (RegInfo &RI : Scope->RegInfos) {
1308  if (RI.HasBranch) {
1309  Region *R = RI.R;
1310  if (TrueBiasedRegionsGlobal.count(R) > 0)
1311  OutermostScope->TrueBiasedRegions.insert(R);
1312  else if (FalseBiasedRegionsGlobal.count(R) > 0)
1313  OutermostScope->FalseBiasedRegions.insert(R);
1314  else
1315  llvm_unreachable("Must be biased");
1316  }
1317  for (SelectInst *SI : RI.Selects) {
1318  if (TrueBiasedSelectsGlobal.count(SI) > 0)
1319  OutermostScope->TrueBiasedSelects.insert(SI);
1320  else if (FalseBiasedSelectsGlobal.count(SI) > 0)
1321  OutermostScope->FalseBiasedSelects.insert(SI);
1322  else
1323  llvm_unreachable("Must be biased");
1324  }
1325  }
1326  for (CHRScope *Sub : Scope->Subs) {
1327  classifyBiasedScopes(Sub, OutermostScope);
1328  }
1329 }
1330 
1331 static bool hasAtLeastTwoBiasedBranches(CHRScope *Scope) {
1332  unsigned NumBiased = Scope->TrueBiasedRegions.size() +
1333  Scope->FalseBiasedRegions.size() +
1334  Scope->TrueBiasedSelects.size() +
1335  Scope->FalseBiasedSelects.size();
1336  return NumBiased >= CHRMergeThreshold;
1337 }
1338 
1339 void CHR::filterScopes(SmallVectorImpl<CHRScope *> &Input,
1340  SmallVectorImpl<CHRScope *> &Output) {
1341  for (CHRScope *Scope : Input) {
1342  // Filter out the ones with only one region and no subs.
1343  if (!hasAtLeastTwoBiasedBranches(Scope)) {
1344  CHR_DEBUG(dbgs() << "Filtered out by biased branches truthy-regions "
1345  << Scope->TrueBiasedRegions.size()
1346  << " falsy-regions " << Scope->FalseBiasedRegions.size()
1347  << " true-selects " << Scope->TrueBiasedSelects.size()
1348  << " false-selects " << Scope->FalseBiasedSelects.size() << "\n");
1349  ORE.emit([&]() {
1350  return OptimizationRemarkMissed(
1351  DEBUG_TYPE,
1352  "DropScopeWithOneBranchOrSelect",
1353  Scope->RegInfos[0].R->getEntry()->getTerminator())
1354  << "Drop scope with < "
1355  << ore::NV("CHRMergeThreshold", CHRMergeThreshold)
1356  << " biased branch(es) or select(s)";
1357  });
1358  continue;
1359  }
1360  Output.push_back(Scope);
1361  }
1362 }
1363 
1364 void CHR::setCHRRegions(SmallVectorImpl<CHRScope *> &Input,
1365  SmallVectorImpl<CHRScope *> &Output) {
1366  for (CHRScope *Scope : Input) {
1367  assert(Scope->HoistStopMap.empty() && Scope->CHRRegions.empty() &&
1368  "Empty");
1369  setCHRRegions(Scope, Scope);
1370  Output.push_back(Scope);
1371  CHR_DEBUG(
1372  dbgs() << "setCHRRegions HoistStopMap " << *Scope << "\n";
1373  for (auto pair : Scope->HoistStopMap) {
1374  Region *R = pair.first;
1375  dbgs() << "Region " << R->getNameStr() << "\n";
1376  for (Instruction *I : pair.second) {
1377  dbgs() << "HoistStop " << *I << "\n";
1378  }
1379  }
1380  dbgs() << "CHRRegions" << "\n";
1381  for (RegInfo &RI : Scope->CHRRegions) {
1382  dbgs() << RI.R->getNameStr() << "\n";
1383  });
1384  }
1385 }
1386 
1387 void CHR::setCHRRegions(CHRScope *Scope, CHRScope *OutermostScope) {
1388  DenseSet<Instruction *> Unhoistables;
1389  // Put the biased selects in Unhoistables because they should stay where they
1390  // are and constant-folded after CHR (in case one biased select or a branch
1391  // can depend on another biased select.)
1392  for (RegInfo &RI : Scope->RegInfos) {
1393  for (SelectInst *SI : RI.Selects) {
1394  Unhoistables.insert(SI);
1395  }
1396  }
1397  Instruction *InsertPoint = OutermostScope->BranchInsertPoint;
1398  for (RegInfo &RI : Scope->RegInfos) {
1399  Region *R = RI.R;
1400  DenseSet<Instruction *> HoistStops;
1401  bool IsHoisted = false;
1402  if (RI.HasBranch) {
1403  assert((OutermostScope->TrueBiasedRegions.count(R) > 0 ||
1404  OutermostScope->FalseBiasedRegions.count(R) > 0) &&
1405  "Must be truthy or falsy");
1406  auto *BI = cast<BranchInst>(R->getEntry()->getTerminator());
1407  // Note checkHoistValue fills in HoistStops.
1409  bool IsHoistable = checkHoistValue(BI->getCondition(), InsertPoint, DT,
1410  Unhoistables, &HoistStops, Visited);
1411  assert(IsHoistable && "Must be hoistable");
1412  (void)(IsHoistable); // Unused in release build
1413  IsHoisted = true;
1414  }
1415  for (SelectInst *SI : RI.Selects) {
1416  assert((OutermostScope->TrueBiasedSelects.count(SI) > 0 ||
1417  OutermostScope->FalseBiasedSelects.count(SI) > 0) &&
1418  "Must be true or false biased");
1419  // Note checkHoistValue fills in HoistStops.
1421  bool IsHoistable = checkHoistValue(SI->getCondition(), InsertPoint, DT,
1422  Unhoistables, &HoistStops, Visited);
1423  assert(IsHoistable && "Must be hoistable");
1424  (void)(IsHoistable); // Unused in release build
1425  IsHoisted = true;
1426  }
1427  if (IsHoisted) {
1428  OutermostScope->CHRRegions.push_back(RI);
1429  OutermostScope->HoistStopMap[R] = HoistStops;
1430  }
1431  }
1432  for (CHRScope *Sub : Scope->Subs)
1433  setCHRRegions(Sub, OutermostScope);
1434 }
1435 
1436 bool CHRScopeSorter(CHRScope *Scope1, CHRScope *Scope2) {
1437  return Scope1->RegInfos[0].R->getDepth() < Scope2->RegInfos[0].R->getDepth();
1438 }
1439 
1440 void CHR::sortScopes(SmallVectorImpl<CHRScope *> &Input,
1441  SmallVectorImpl<CHRScope *> &Output) {
1442  Output.resize(Input.size());
1443  llvm::copy(Input, Output.begin());
1445 }
1446 
1447 // Return true if V is already hoisted or was hoisted (along with its operands)
1448 // to the insert point.
1449 static void hoistValue(Value *V, Instruction *HoistPoint, Region *R,
1450  HoistStopMapTy &HoistStopMap,
1451  DenseSet<Instruction *> &HoistedSet,
1452  DenseSet<PHINode *> &TrivialPHIs,
1453  DominatorTree &DT) {
1454  auto IT = HoistStopMap.find(R);
1455  assert(IT != HoistStopMap.end() && "Region must be in hoist stop map");
1456  DenseSet<Instruction *> &HoistStops = IT->second;
1457  if (auto *I = dyn_cast<Instruction>(V)) {
1458  if (I == HoistPoint)
1459  return;
1460  if (HoistStops.count(I))
1461  return;
1462  if (auto *PN = dyn_cast<PHINode>(I))
1463  if (TrivialPHIs.count(PN))
1464  // The trivial phi inserted by the previous CHR scope could replace a
1465  // non-phi in HoistStops. Note that since this phi is at the exit of a
1466  // previous CHR scope, which dominates this scope, it's safe to stop
1467  // hoisting there.
1468  return;
1469  if (HoistedSet.count(I))
1470  // Already hoisted, return.
1471  return;
1472  assert(isHoistableInstructionType(I) && "Unhoistable instruction type");
1473  assert(DT.getNode(I->getParent()) && "DT must contain I's block");
1474  assert(DT.getNode(HoistPoint->getParent()) &&
1475  "DT must contain HoistPoint block");
1476  if (DT.dominates(I, HoistPoint))
1477  // We are already above the hoist point. Stop here. This may be necessary
1478  // when multiple scopes would independently hoist the same
1479  // instruction. Since an outer (dominating) scope would hoist it to its
1480  // entry before an inner (dominated) scope would to its entry, the inner
1481  // scope may see the instruction already hoisted, in which case it
1482  // potentially wrong for the inner scope to hoist it and could cause bad
1483  // IR (non-dominating def), but safe to skip hoisting it instead because
1484  // it's already in a block that dominates the inner scope.
1485  return;
1486  for (Value *Op : I->operands()) {
1487  hoistValue(Op, HoistPoint, R, HoistStopMap, HoistedSet, TrivialPHIs, DT);
1488  }
1489  I->moveBefore(HoistPoint);
1490  HoistedSet.insert(I);
1491  CHR_DEBUG(dbgs() << "hoistValue " << *I << "\n");
1492  }
1493 }
1494 
1495 // Hoist the dependent condition values of the branches and the selects in the
1496 // scope to the insert point.
1497 static void hoistScopeConditions(CHRScope *Scope, Instruction *HoistPoint,
1498  DenseSet<PHINode *> &TrivialPHIs,
1499  DominatorTree &DT) {
1500  DenseSet<Instruction *> HoistedSet;
1501  for (const RegInfo &RI : Scope->CHRRegions) {
1502  Region *R = RI.R;
1503  bool IsTrueBiased = Scope->TrueBiasedRegions.count(R);
1504  bool IsFalseBiased = Scope->FalseBiasedRegions.count(R);
1505  if (RI.HasBranch && (IsTrueBiased || IsFalseBiased)) {
1506  auto *BI = cast<BranchInst>(R->getEntry()->getTerminator());
1507  hoistValue(BI->getCondition(), HoistPoint, R, Scope->HoistStopMap,
1508  HoistedSet, TrivialPHIs, DT);
1509  }
1510  for (SelectInst *SI : RI.Selects) {
1511  bool IsTrueBiased = Scope->TrueBiasedSelects.count(SI);
1512  bool IsFalseBiased = Scope->FalseBiasedSelects.count(SI);
1513  if (!(IsTrueBiased || IsFalseBiased))
1514  continue;
1515  hoistValue(SI->getCondition(), HoistPoint, R, Scope->HoistStopMap,
1516  HoistedSet, TrivialPHIs, DT);
1517  }
1518  }
1519 }
1520 
1521 // Negate the predicate if an ICmp if it's used only by branches or selects by
1522 // swapping the operands of the branches or the selects. Returns true if success.
1524  Instruction *ExcludedUser,
1525  CHRScope *Scope) {
1526  for (User *U : ICmp->users()) {
1527  if (U == ExcludedUser)
1528  continue;
1529  if (isa<BranchInst>(U) && cast<BranchInst>(U)->isConditional())
1530  continue;
1531  if (isa<SelectInst>(U) && cast<SelectInst>(U)->getCondition() == ICmp)
1532  continue;
1533  return false;
1534  }
1535  for (User *U : ICmp->users()) {
1536  if (U == ExcludedUser)
1537  continue;
1538  if (auto *BI = dyn_cast<BranchInst>(U)) {
1539  assert(BI->isConditional() && "Must be conditional");
1540  BI->swapSuccessors();
1541  // Don't need to swap this in terms of
1542  // TrueBiasedRegions/FalseBiasedRegions because true-based/false-based
1543  // mean whehter the branch is likely go into the if-then rather than
1544  // successor0/successor1 and because we can tell which edge is the then or
1545  // the else one by comparing the destination to the region exit block.
1546  continue;
1547  }
1548  if (auto *SI = dyn_cast<SelectInst>(U)) {
1549  // Swap operands
1550  SI->swapValues();
1551  SI->swapProfMetadata();
1552  if (Scope->TrueBiasedSelects.count(SI)) {
1553  assert(Scope->FalseBiasedSelects.count(SI) == 0 &&
1554  "Must not be already in");
1555  Scope->FalseBiasedSelects.insert(SI);
1556  } else if (Scope->FalseBiasedSelects.count(SI)) {
1557  assert(Scope->TrueBiasedSelects.count(SI) == 0 &&
1558  "Must not be already in");
1559  Scope->TrueBiasedSelects.insert(SI);
1560  }
1561  continue;
1562  }
1563  llvm_unreachable("Must be a branch or a select");
1564  }
1566  return true;
1567 }
1568 
1569 // A helper for transformScopes. Insert a trivial phi at the scope exit block
1570 // for a value that's defined in the scope but used outside it (meaning it's
1571 // alive at the exit block).
1572 static void insertTrivialPHIs(CHRScope *Scope,
1573  BasicBlock *EntryBlock, BasicBlock *ExitBlock,
1574  DenseSet<PHINode *> &TrivialPHIs) {
1575  DenseSet<BasicBlock *> BlocksInScopeSet;
1576  SmallVector<BasicBlock *, 8> BlocksInScopeVec;
1577  for (RegInfo &RI : Scope->RegInfos) {
1578  for (BasicBlock *BB : RI.R->blocks()) { // This includes the blocks in the
1579  // sub-Scopes.
1580  BlocksInScopeSet.insert(BB);
1581  BlocksInScopeVec.push_back(BB);
1582  }
1583  }
1584  CHR_DEBUG(
1585  dbgs() << "Inserting redudant phis\n";
1586  for (BasicBlock *BB : BlocksInScopeVec) {
1587  dbgs() << "BlockInScope " << BB->getName() << "\n";
1588  });
1589  for (BasicBlock *BB : BlocksInScopeVec) {
1590  for (Instruction &I : *BB) {
1592  for (User *U : I.users()) {
1593  if (auto *UI = dyn_cast<Instruction>(U)) {
1594  if (BlocksInScopeSet.count(UI->getParent()) == 0 &&
1595  // Unless there's already a phi for I at the exit block.
1596  !(isa<PHINode>(UI) && UI->getParent() == ExitBlock)) {
1597  CHR_DEBUG(dbgs() << "V " << I << "\n");
1598  CHR_DEBUG(dbgs() << "Used outside scope by user " << *UI << "\n");
1599  Users.push_back(UI);
1600  } else if (UI->getParent() == EntryBlock && isa<PHINode>(UI)) {
1601  // There's a loop backedge from a block that's dominated by this
1602  // scope to the entry block.
1603  CHR_DEBUG(dbgs() << "V " << I << "\n");
1604  CHR_DEBUG(dbgs()
1605  << "Used at entry block (for a back edge) by a phi user "
1606  << *UI << "\n");
1607  Users.push_back(UI);
1608  }
1609  }
1610  }
1611  if (Users.size() > 0) {
1612  // Insert a trivial phi for I (phi [&I, P0], [&I, P1], ...) at
1613  // ExitBlock. Replace I with the new phi in UI unless UI is another
1614  // phi at ExitBlock.
1615  unsigned PredCount = std::distance(pred_begin(ExitBlock),
1616  pred_end(ExitBlock));
1617  PHINode *PN = PHINode::Create(I.getType(), PredCount, "",
1618  &ExitBlock->front());
1619  for (BasicBlock *Pred : predecessors(ExitBlock)) {
1620  PN->addIncoming(&I, Pred);
1621  }
1622  TrivialPHIs.insert(PN);
1623  CHR_DEBUG(dbgs() << "Insert phi " << *PN << "\n");
1624  for (Instruction *UI : Users) {
1625  for (unsigned J = 0, NumOps = UI->getNumOperands(); J < NumOps; ++J) {
1626  if (UI->getOperand(J) == &I) {
1627  UI->setOperand(J, PN);
1628  }
1629  }
1630  CHR_DEBUG(dbgs() << "Updated user " << *UI << "\n");
1631  }
1632  }
1633  }
1634  }
1635 }
1636 
1637 // Assert that all the CHR regions of the scope have a biased branch or select.
1638 static void LLVM_ATTRIBUTE_UNUSED
1640 #ifndef NDEBUG
1641  auto HasBiasedBranchOrSelect = [](RegInfo &RI, CHRScope *Scope) {
1642  if (Scope->TrueBiasedRegions.count(RI.R) ||
1643  Scope->FalseBiasedRegions.count(RI.R))
1644  return true;
1645  for (SelectInst *SI : RI.Selects)
1646  if (Scope->TrueBiasedSelects.count(SI) ||
1647  Scope->FalseBiasedSelects.count(SI))
1648  return true;
1649  return false;
1650  };
1651  for (RegInfo &RI : Scope->CHRRegions) {
1652  assert(HasBiasedBranchOrSelect(RI, Scope) &&
1653  "Must have biased branch or select");
1654  }
1655 #endif
1656 }
1657 
1658 // Assert that all the condition values of the biased branches and selects have
1659 // been hoisted to the pre-entry block or outside of the scope.
1661  CHRScope *Scope, BasicBlock *PreEntryBlock) {
1662  CHR_DEBUG(dbgs() << "Biased regions condition values \n");
1663  for (RegInfo &RI : Scope->CHRRegions) {
1664  Region *R = RI.R;
1665  bool IsTrueBiased = Scope->TrueBiasedRegions.count(R);
1666  bool IsFalseBiased = Scope->FalseBiasedRegions.count(R);
1667  if (RI.HasBranch && (IsTrueBiased || IsFalseBiased)) {
1668  auto *BI = cast<BranchInst>(R->getEntry()->getTerminator());
1669  Value *V = BI->getCondition();
1670  CHR_DEBUG(dbgs() << *V << "\n");
1671  if (auto *I = dyn_cast<Instruction>(V)) {
1672  (void)(I); // Unused in release build.
1673  assert((I->getParent() == PreEntryBlock ||
1674  !Scope->contains(I)) &&
1675  "Must have been hoisted to PreEntryBlock or outside the scope");
1676  }
1677  }
1678  for (SelectInst *SI : RI.Selects) {
1679  bool IsTrueBiased = Scope->TrueBiasedSelects.count(SI);
1680  bool IsFalseBiased = Scope->FalseBiasedSelects.count(SI);
1681  if (!(IsTrueBiased || IsFalseBiased))
1682  continue;
1683  Value *V = SI->getCondition();
1684  CHR_DEBUG(dbgs() << *V << "\n");
1685  if (auto *I = dyn_cast<Instruction>(V)) {
1686  (void)(I); // Unused in release build.
1687  assert((I->getParent() == PreEntryBlock ||
1688  !Scope->contains(I)) &&
1689  "Must have been hoisted to PreEntryBlock or outside the scope");
1690  }
1691  }
1692  }
1693 }
1694 
1695 void CHR::transformScopes(CHRScope *Scope, DenseSet<PHINode *> &TrivialPHIs) {
1696  CHR_DEBUG(dbgs() << "transformScopes " << *Scope << "\n");
1697 
1698  assert(Scope->RegInfos.size() >= 1 && "Should have at least one Region");
1699  Region *FirstRegion = Scope->RegInfos[0].R;
1700  BasicBlock *EntryBlock = FirstRegion->getEntry();
1701  Region *LastRegion = Scope->RegInfos[Scope->RegInfos.size() - 1].R;
1702  BasicBlock *ExitBlock = LastRegion->getExit();
1703  Optional<uint64_t> ProfileCount = BFI.getBlockProfileCount(EntryBlock);
1704 
1705  if (ExitBlock) {
1706  // Insert a trivial phi at the exit block (where the CHR hot path and the
1707  // cold path merges) for a value that's defined in the scope but used
1708  // outside it (meaning it's alive at the exit block). We will add the
1709  // incoming values for the CHR cold paths to it below. Without this, we'd
1710  // miss updating phi's for such values unless there happens to already be a
1711  // phi for that value there.
1712  insertTrivialPHIs(Scope, EntryBlock, ExitBlock, TrivialPHIs);
1713  }
1714 
1715  // Split the entry block of the first region. The new block becomes the new
1716  // entry block of the first region. The old entry block becomes the block to
1717  // insert the CHR branch into. Note DT gets updated. Since DT gets updated
1718  // through the split, we update the entry of the first region after the split,
1719  // and Region only points to the entry and the exit blocks, rather than
1720  // keeping everything in a list or set, the blocks membership and the
1721  // entry/exit blocks of the region are still valid after the split.
1722  CHR_DEBUG(dbgs() << "Splitting entry block " << EntryBlock->getName()
1723  << " at " << *Scope->BranchInsertPoint << "\n");
1724  BasicBlock *NewEntryBlock =
1725  SplitBlock(EntryBlock, Scope->BranchInsertPoint, &DT);
1726  assert(NewEntryBlock->getSinglePredecessor() == EntryBlock &&
1727  "NewEntryBlock's only pred must be EntryBlock");
1728  FirstRegion->replaceEntryRecursive(NewEntryBlock);
1729  BasicBlock *PreEntryBlock = EntryBlock;
1730 
1731  ValueToValueMapTy VMap;
1732  // Clone the blocks in the scope (excluding the PreEntryBlock) to split into a
1733  // hot path (originals) and a cold path (clones) and update the PHIs at the
1734  // exit block.
1735  cloneScopeBlocks(Scope, PreEntryBlock, ExitBlock, LastRegion, VMap);
1736 
1737  // Replace the old (placeholder) branch with the new (merged) conditional
1738  // branch.
1739  BranchInst *MergedBr = createMergedBranch(PreEntryBlock, EntryBlock,
1740  NewEntryBlock, VMap);
1741 
1742 #ifndef NDEBUG
1744 #endif
1745 
1746  // Hoist the conditional values of the branches/selects.
1747  hoistScopeConditions(Scope, PreEntryBlock->getTerminator(), TrivialPHIs, DT);
1748 
1749 #ifndef NDEBUG
1750  assertBranchOrSelectConditionHoisted(Scope, PreEntryBlock);
1751 #endif
1752 
1753  // Create the combined branch condition and constant-fold the branches/selects
1754  // in the hot path.
1755  fixupBranchesAndSelects(Scope, PreEntryBlock, MergedBr,
1756  ProfileCount ? ProfileCount.getValue() : 0);
1757 }
1758 
1759 // A helper for transformScopes. Clone the blocks in the scope (excluding the
1760 // PreEntryBlock) to split into a hot path and a cold path and update the PHIs
1761 // at the exit block.
1762 void CHR::cloneScopeBlocks(CHRScope *Scope,
1763  BasicBlock *PreEntryBlock,
1764  BasicBlock *ExitBlock,
1765  Region *LastRegion,
1766  ValueToValueMapTy &VMap) {
1767  // Clone all the blocks. The original blocks will be the hot-path
1768  // CHR-optimized code and the cloned blocks will be the original unoptimized
1769  // code. This is so that the block pointers from the
1770  // CHRScope/Region/RegionInfo can stay valid in pointing to the hot-path code
1771  // which CHR should apply to.
1772  SmallVector<BasicBlock*, 8> NewBlocks;
1773  for (RegInfo &RI : Scope->RegInfos)
1774  for (BasicBlock *BB : RI.R->blocks()) { // This includes the blocks in the
1775  // sub-Scopes.
1776  assert(BB != PreEntryBlock && "Don't copy the preetntry block");
1777  BasicBlock *NewBB = CloneBasicBlock(BB, VMap, ".nonchr", &F);
1778  NewBlocks.push_back(NewBB);
1779  VMap[BB] = NewBB;
1780  }
1781 
1782  // Place the cloned blocks right after the original blocks (right before the
1783  // exit block of.)
1784  if (ExitBlock)
1785  F.getBasicBlockList().splice(ExitBlock->getIterator(),
1786  F.getBasicBlockList(),
1787  NewBlocks[0]->getIterator(), F.end());
1788 
1789  // Update the cloned blocks/instructions to refer to themselves.
1790  for (unsigned i = 0, e = NewBlocks.size(); i != e; ++i)
1791  for (Instruction &I : *NewBlocks[i])
1792  RemapInstruction(&I, VMap,
1794 
1795  // Add the cloned blocks to the PHIs of the exit blocks. ExitBlock is null for
1796  // the top-level region but we don't need to add PHIs. The trivial PHIs
1797  // inserted above will be updated here.
1798  if (ExitBlock)
1799  for (PHINode &PN : ExitBlock->phis())
1800  for (unsigned I = 0, NumOps = PN.getNumIncomingValues(); I < NumOps;
1801  ++I) {
1802  BasicBlock *Pred = PN.getIncomingBlock(I);
1803  if (LastRegion->contains(Pred)) {
1804  Value *V = PN.getIncomingValue(I);
1805  auto It = VMap.find(V);
1806  if (It != VMap.end()) V = It->second;
1807  assert(VMap.find(Pred) != VMap.end() && "Pred must have been cloned");
1808  PN.addIncoming(V, cast<BasicBlock>(VMap[Pred]));
1809  }
1810  }
1811 }
1812 
1813 // A helper for transformScope. Replace the old (placeholder) branch with the
1814 // new (merged) conditional branch.
1815 BranchInst *CHR::createMergedBranch(BasicBlock *PreEntryBlock,
1816  BasicBlock *EntryBlock,
1817  BasicBlock *NewEntryBlock,
1818  ValueToValueMapTy &VMap) {
1819  BranchInst *OldBR = cast<BranchInst>(PreEntryBlock->getTerminator());
1820  assert(OldBR->isUnconditional() && OldBR->getSuccessor(0) == NewEntryBlock &&
1821  "SplitBlock did not work correctly!");
1822  assert(NewEntryBlock->getSinglePredecessor() == EntryBlock &&
1823  "NewEntryBlock's only pred must be EntryBlock");
1824  assert(VMap.find(NewEntryBlock) != VMap.end() &&
1825  "NewEntryBlock must have been copied");
1826  OldBR->dropAllReferences();
1827  OldBR->eraseFromParent();
1828  // The true predicate is a placeholder. It will be replaced later in
1829  // fixupBranchesAndSelects().
1830  BranchInst *NewBR = BranchInst::Create(NewEntryBlock,
1831  cast<BasicBlock>(VMap[NewEntryBlock]),
1832  ConstantInt::getTrue(F.getContext()));
1833  PreEntryBlock->getInstList().push_back(NewBR);
1834  assert(NewEntryBlock->getSinglePredecessor() == EntryBlock &&
1835  "NewEntryBlock's only pred must be EntryBlock");
1836  return NewBR;
1837 }
1838 
1839 // A helper for transformScopes. Create the combined branch condition and
1840 // constant-fold the branches/selects in the hot path.
1841 void CHR::fixupBranchesAndSelects(CHRScope *Scope,
1842  BasicBlock *PreEntryBlock,
1843  BranchInst *MergedBR,
1844  uint64_t ProfileCount) {
1845  Value *MergedCondition = ConstantInt::getTrue(F.getContext());
1846  BranchProbability CHRBranchBias(1, 1);
1847  uint64_t NumCHRedBranches = 0;
1848  IRBuilder<> IRB(PreEntryBlock->getTerminator());
1849  for (RegInfo &RI : Scope->CHRRegions) {
1850  Region *R = RI.R;
1851  if (RI.HasBranch) {
1852  fixupBranch(R, Scope, IRB, MergedCondition, CHRBranchBias);
1853  ++NumCHRedBranches;
1854  }
1855  for (SelectInst *SI : RI.Selects) {
1856  fixupSelect(SI, Scope, IRB, MergedCondition, CHRBranchBias);
1857  ++NumCHRedBranches;
1858  }
1859  }
1860  Stats.NumBranchesDelta += NumCHRedBranches - 1;
1861  Stats.WeightedNumBranchesDelta += (NumCHRedBranches - 1) * ProfileCount;
1862  ORE.emit([&]() {
1864  "CHR",
1865  // Refer to the hot (original) path
1866  MergedBR->getSuccessor(0)->getTerminator())
1867  << "Merged " << ore::NV("NumCHRedBranches", NumCHRedBranches)
1868  << " branches or selects";
1869  });
1870  MergedBR->setCondition(MergedCondition);
1871  SmallVector<uint32_t, 2> Weights;
1872  Weights.push_back(static_cast<uint32_t>(CHRBranchBias.scale(1000)));
1873  Weights.push_back(static_cast<uint32_t>(CHRBranchBias.getCompl().scale(1000)));
1874  MDBuilder MDB(F.getContext());
1875  MergedBR->setMetadata(LLVMContext::MD_prof, MDB.createBranchWeights(Weights));
1876  CHR_DEBUG(dbgs() << "CHR branch bias " << Weights[0] << ":" << Weights[1]
1877  << "\n");
1878 }
1879 
1880 // A helper for fixupBranchesAndSelects. Add to the combined branch condition
1881 // and constant-fold a branch in the hot path.
1882 void CHR::fixupBranch(Region *R, CHRScope *Scope,
1883  IRBuilder<> &IRB,
1884  Value *&MergedCondition,
1885  BranchProbability &CHRBranchBias) {
1886  bool IsTrueBiased = Scope->TrueBiasedRegions.count(R);
1887  assert((IsTrueBiased || Scope->FalseBiasedRegions.count(R)) &&
1888  "Must be truthy or falsy");
1889  auto *BI = cast<BranchInst>(R->getEntry()->getTerminator());
1890  assert(BranchBiasMap.find(R) != BranchBiasMap.end() &&
1891  "Must be in the bias map");
1892  BranchProbability Bias = BranchBiasMap[R];
1893  assert(Bias >= getCHRBiasThreshold() && "Must be highly biased");
1894  // Take the min.
1895  if (CHRBranchBias > Bias)
1896  CHRBranchBias = Bias;
1897  BasicBlock *IfThen = BI->getSuccessor(1);
1898  BasicBlock *IfElse = BI->getSuccessor(0);
1899  BasicBlock *RegionExitBlock = R->getExit();
1900  assert(RegionExitBlock && "Null ExitBlock");
1901  assert((IfThen == RegionExitBlock || IfElse == RegionExitBlock) &&
1902  IfThen != IfElse && "Invariant from findScopes");
1903  if (IfThen == RegionExitBlock) {
1904  // Swap them so that IfThen means going into it and IfElse means skipping
1905  // it.
1906  std::swap(IfThen, IfElse);
1907  }
1908  CHR_DEBUG(dbgs() << "IfThen " << IfThen->getName()
1909  << " IfElse " << IfElse->getName() << "\n");
1910  Value *Cond = BI->getCondition();
1911  BasicBlock *HotTarget = IsTrueBiased ? IfThen : IfElse;
1912  bool ConditionTrue = HotTarget == BI->getSuccessor(0);
1913  addToMergedCondition(ConditionTrue, Cond, BI, Scope, IRB,
1914  MergedCondition);
1915  // Constant-fold the branch at ClonedEntryBlock.
1916  assert(ConditionTrue == (HotTarget == BI->getSuccessor(0)) &&
1917  "The successor shouldn't change");
1918  Value *NewCondition = ConditionTrue ?
1919  ConstantInt::getTrue(F.getContext()) :
1920  ConstantInt::getFalse(F.getContext());
1921  BI->setCondition(NewCondition);
1922 }
1923 
1924 // A helper for fixupBranchesAndSelects. Add to the combined branch condition
1925 // and constant-fold a select in the hot path.
1926 void CHR::fixupSelect(SelectInst *SI, CHRScope *Scope,
1927  IRBuilder<> &IRB,
1928  Value *&MergedCondition,
1929  BranchProbability &CHRBranchBias) {
1930  bool IsTrueBiased = Scope->TrueBiasedSelects.count(SI);
1931  assert((IsTrueBiased ||
1932  Scope->FalseBiasedSelects.count(SI)) && "Must be biased");
1933  assert(SelectBiasMap.find(SI) != SelectBiasMap.end() &&
1934  "Must be in the bias map");
1935  BranchProbability Bias = SelectBiasMap[SI];
1936  assert(Bias >= getCHRBiasThreshold() && "Must be highly biased");
1937  // Take the min.
1938  if (CHRBranchBias > Bias)
1939  CHRBranchBias = Bias;
1940  Value *Cond = SI->getCondition();
1941  addToMergedCondition(IsTrueBiased, Cond, SI, Scope, IRB,
1942  MergedCondition);
1943  Value *NewCondition = IsTrueBiased ?
1944  ConstantInt::getTrue(F.getContext()) :
1945  ConstantInt::getFalse(F.getContext());
1946  SI->setCondition(NewCondition);
1947 }
1948 
1949 // A helper for fixupBranch/fixupSelect. Add a branch condition to the merged
1950 // condition.
1951 void CHR::addToMergedCondition(bool IsTrueBiased, Value *Cond,
1952  Instruction *BranchOrSelect,
1953  CHRScope *Scope,
1954  IRBuilder<> &IRB,
1955  Value *&MergedCondition) {
1956  if (IsTrueBiased) {
1957  MergedCondition = IRB.CreateAnd(MergedCondition, Cond);
1958  } else {
1959  // If Cond is an icmp and all users of V except for BranchOrSelect is a
1960  // branch, negate the icmp predicate and swap the branch targets and avoid
1961  // inserting an Xor to negate Cond.
1962  bool Done = false;
1963  if (auto *ICmp = dyn_cast<ICmpInst>(Cond))
1964  if (negateICmpIfUsedByBranchOrSelectOnly(ICmp, BranchOrSelect, Scope)) {
1965  MergedCondition = IRB.CreateAnd(MergedCondition, Cond);
1966  Done = true;
1967  }
1968  if (!Done) {
1969  Value *Negate = IRB.CreateXor(
1970  ConstantInt::getTrue(F.getContext()), Cond);
1971  MergedCondition = IRB.CreateAnd(MergedCondition, Negate);
1972  }
1973  }
1974 }
1975 
1976 void CHR::transformScopes(SmallVectorImpl<CHRScope *> &CHRScopes) {
1977  unsigned I = 0;
1978  DenseSet<PHINode *> TrivialPHIs;
1979  for (CHRScope *Scope : CHRScopes) {
1980  transformScopes(Scope, TrivialPHIs);
1981  CHR_DEBUG(
1982  std::ostringstream oss;
1983  oss << " after transformScopes " << I++;
1984  dumpIR(F, oss.str().c_str(), nullptr));
1985  (void)I;
1986  }
1987 }
1988 
1989 static void LLVM_ATTRIBUTE_UNUSED
1990 dumpScopes(SmallVectorImpl<CHRScope *> &Scopes, const char *Label) {
1991  dbgs() << Label << " " << Scopes.size() << "\n";
1992  for (CHRScope *Scope : Scopes) {
1993  dbgs() << *Scope << "\n";
1994  }
1995 }
1996 
1997 bool CHR::run() {
1998  if (!shouldApply(F, PSI))
1999  return false;
2000 
2001  CHR_DEBUG(dumpIR(F, "before", nullptr));
2002 
2003  bool Changed = false;
2004  {
2005  CHR_DEBUG(
2006  dbgs() << "RegionInfo:\n";
2007  RI.print(dbgs()));
2008 
2009  // Recursively traverse the region tree and find regions that have biased
2010  // branches and/or selects and create scopes.
2011  SmallVector<CHRScope *, 8> AllScopes;
2012  findScopes(AllScopes);
2013  CHR_DEBUG(dumpScopes(AllScopes, "All scopes"));
2014 
2015  // Split the scopes if 1) the conditiona values of the biased
2016  // branches/selects of the inner/lower scope can't be hoisted up to the
2017  // outermost/uppermost scope entry, or 2) the condition values of the biased
2018  // branches/selects in a scope (including subscopes) don't share at least
2019  // one common value.
2020  SmallVector<CHRScope *, 8> SplitScopes;
2021  splitScopes(AllScopes, SplitScopes);
2022  CHR_DEBUG(dumpScopes(SplitScopes, "Split scopes"));
2023 
2024  // After splitting, set the biased regions and selects of a scope (a tree
2025  // root) that include those of the subscopes.
2026  classifyBiasedScopes(SplitScopes);
2027  CHR_DEBUG(dbgs() << "Set per-scope bias " << SplitScopes.size() << "\n");
2028 
2029  // Filter out the scopes that has only one biased region or select (CHR
2030  // isn't useful in such a case).
2031  SmallVector<CHRScope *, 8> FilteredScopes;
2032  filterScopes(SplitScopes, FilteredScopes);
2033  CHR_DEBUG(dumpScopes(FilteredScopes, "Filtered scopes"));
2034 
2035  // Set the regions to be CHR'ed and their hoist stops for each scope.
2036  SmallVector<CHRScope *, 8> SetScopes;
2037  setCHRRegions(FilteredScopes, SetScopes);
2038  CHR_DEBUG(dumpScopes(SetScopes, "Set CHR regions"));
2039 
2040  // Sort CHRScopes by the depth so that outer CHRScopes comes before inner
2041  // ones. We need to apply CHR from outer to inner so that we apply CHR only
2042  // to the hot path, rather than both hot and cold paths.
2043  SmallVector<CHRScope *, 8> SortedScopes;
2044  sortScopes(SetScopes, SortedScopes);
2045  CHR_DEBUG(dumpScopes(SortedScopes, "Sorted scopes"));
2046 
2047  CHR_DEBUG(
2048  dbgs() << "RegionInfo:\n";
2049  RI.print(dbgs()));
2050 
2051  // Apply the CHR transformation.
2052  if (!SortedScopes.empty()) {
2053  transformScopes(SortedScopes);
2054  Changed = true;
2055  }
2056  }
2057 
2058  if (Changed) {
2059  CHR_DEBUG(dumpIR(F, "after", &Stats));
2060  ORE.emit([&]() {
2061  return OptimizationRemark(DEBUG_TYPE, "Stats", &F)
2062  << ore::NV("Function", &F) << " "
2063  << "Reduced the number of branches in hot paths by "
2064  << ore::NV("NumBranchesDelta", Stats.NumBranchesDelta)
2065  << " (static) and "
2066  << ore::NV("WeightedNumBranchesDelta", Stats.WeightedNumBranchesDelta)
2067  << " (weighted by PGO count)";
2068  });
2069  }
2070 
2071  return Changed;
2072 }
2073 
2076  getAnalysis<BlockFrequencyInfoWrapperPass>().getBFI();
2077  DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
2078  ProfileSummaryInfo &PSI =
2079  getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();
2080  RegionInfo &RI = getAnalysis<RegionInfoPass>().getRegionInfo();
2081  std::unique_ptr<OptimizationRemarkEmitter> OwnedORE =
2082  std::make_unique<OptimizationRemarkEmitter>(&F);
2083  return CHR(F, BFI, DT, PSI, RI, *OwnedORE.get()).run();
2084 }
2085 
2086 namespace llvm {
2087 
2090 }
2091 
2093  Function &F,
2094  FunctionAnalysisManager &FAM) {
2095  auto &BFI = FAM.getResult<BlockFrequencyAnalysis>(F);
2096  auto &DT = FAM.getResult<DominatorTreeAnalysis>(F);
2097  auto &MAMProxy = FAM.getResult<ModuleAnalysisManagerFunctionProxy>(F);
2098  auto &MAM = MAMProxy.getManager();
2099  auto &PSI = *MAM.getCachedResult<ProfileSummaryAnalysis>(*F.getParent());
2100  auto &RI = FAM.getResult<RegionInfoAnalysis>(F);
2101  auto &ORE = FAM.getResult<OptimizationRemarkEmitterAnalysis>(F);
2102  bool Changed = CHR(F, BFI, DT, PSI, RI, ORE).run();
2103  if (!Changed)
2104  return PreservedAnalyses::all();
2105  auto PA = PreservedAnalyses();
2106  PA.preserve<GlobalsAA>();
2107  return PA;
2108 }
2109 
2110 } // 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:616
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:1571
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:144
iv Induction Variable Users
Definition: IVUsers.cpp:51
BasicBlock * SplitBlock(BasicBlock *Old, Instruction *SplitPt, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="")
Split the specified block at the specified instruction - everything before SplitPt stays in Old and e...
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:4429
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:156
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
Definition: Instruction.h:244
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:240
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:381
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 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:285
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
static std::set< Value * > getBaseValues(Value *V, DominatorTree &DT, DenseMap< Value *, std::set< Value *>> &Visited)
Represent the analysis usage information of a pass.
PreservedAnalyses run(Function &F, FunctionAnalysisManager &FAM)
#define LLVM_ATTRIBUTE_UNUSED
Definition: Compiler.h:180
This instruction compares its operands according to the predicate given to the constructor.
Analysis pass providing a never-invalidated alias analysis result.
constexpr double e
Definition: MathExtras.h:57
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:1193
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:1205
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:136
const InstListType & getInstList() const
Return the underlying instruction list container.
Definition: BasicBlock.h:338
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:710
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:609
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:420
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
Tail - This calling convention attemps to make calls as fast as possible while guaranteeing that tail...
Definition: CallingConv.h:81
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:329
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:2047
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:145
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:1289
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:575
LLVM Value Representation.
Definition: Value.h:74
StringSet - A wrapper for StringMap that provides set-like functionality.
Definition: StringSet.h:27
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
A container for analyses that lazily runs them and caches their results.
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:1217
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