LLVM  14.0.0git
ControlHeightReduction.cpp
Go to the documentation of this file.
1 //===-- ControlHeightReduction.cpp - Control Height Reduction -------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This pass merges conditional blocks of code and reduces the number of
10 // conditional branches in the hot paths based on profiles.
11 //
12 //===----------------------------------------------------------------------===//
13 
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"
30 #include "llvm/IR/PassManager.h"
31 #include "llvm/InitializePasses.h"
35 #include "llvm/Transforms/Utils.h"
39 
40 #include <set>
41 #include <sstream>
42 
43 using namespace llvm;
44 
45 #define DEBUG_TYPE "chr"
46 
47 #define CHR_DEBUG(X) LLVM_DEBUG(X)
48 
49 static cl::opt<bool> ForceCHR("force-chr", cl::init(false), cl::Hidden,
50  cl::desc("Apply CHR for all functions"));
51 
53  "chr-bias-threshold", cl::init(0.99), cl::Hidden,
54  cl::desc("CHR considers a branch bias greater than this ratio as biased"));
55 
57  "chr-merge-threshold", cl::init(2), cl::Hidden,
58  cl::desc("CHR merges a group of N branches/selects where N >= this value"));
59 
61  "chr-module-list", cl::init(""), cl::Hidden,
62  cl::desc("Specify file to retrieve the list of modules to apply CHR to"));
63 
65  "chr-function-list", cl::init(""), cl::Hidden,
66  cl::desc("Specify file to retrieve the list of functions to apply CHR to"));
67 
70 
71 static void parseCHRFilterFiles() {
72  if (!CHRModuleList.empty()) {
73  auto FileOrErr = MemoryBuffer::getFile(CHRModuleList);
74  if (!FileOrErr) {
75  errs() << "Error: Couldn't read the chr-module-list file " << CHRModuleList << "\n";
76  std::exit(1);
77  }
78  StringRef Buf = FileOrErr->get()->getBuffer();
80  Buf.split(Lines, '\n');
81  for (StringRef Line : Lines) {
82  Line = Line.trim();
83  if (!Line.empty())
84  CHRModules.insert(Line);
85  }
86  }
87  if (!CHRFunctionList.empty()) {
88  auto FileOrErr = MemoryBuffer::getFile(CHRFunctionList);
89  if (!FileOrErr) {
90  errs() << "Error: Couldn't read the chr-function-list file " << CHRFunctionList << "\n";
91  std::exit(1);
92  }
93  StringRef Buf = FileOrErr->get()->getBuffer();
95  Buf.split(Lines, '\n');
96  for (StringRef Line : Lines) {
97  Line = Line.trim();
98  if (!Line.empty())
99  CHRFunctions.insert(Line);
100  }
101  }
102 }
103 
104 namespace {
105 class ControlHeightReductionLegacyPass : public FunctionPass {
106 public:
107  static char ID;
108 
109  ControlHeightReductionLegacyPass() : FunctionPass(ID) {
113  }
114 
115  bool runOnFunction(Function &F) override;
116  void getAnalysisUsage(AnalysisUsage &AU) const override {
122  }
123 };
124 } // end anonymous namespace
125 
127 
128 INITIALIZE_PASS_BEGIN(ControlHeightReductionLegacyPass,
129  "chr",
130  "Reduce control height in the hot paths",
131  false, false)
136 INITIALIZE_PASS_END(ControlHeightReductionLegacyPass,
137  "chr",
138  "Reduce control height in the hot paths",
140 
142  return new ControlHeightReductionLegacyPass();
143 }
144 
145 namespace {
146 
147 struct CHRStats {
148  CHRStats() : NumBranches(0), NumBranchesDelta(0),
149  WeightedNumBranchesDelta(0) {}
150  void print(raw_ostream &OS) const {
151  OS << "CHRStats: NumBranches " << NumBranches
152  << " NumBranchesDelta " << NumBranchesDelta
153  << " WeightedNumBranchesDelta " << WeightedNumBranchesDelta;
154  }
155  uint64_t NumBranches; // The original number of conditional branches /
156  // selects
157  uint64_t NumBranchesDelta; // The decrease of the number of conditional
158  // branches / selects in the hot paths due to CHR.
159  uint64_t WeightedNumBranchesDelta; // NumBranchesDelta weighted by the profile
160  // count at the scope entry.
161 };
162 
163 // RegInfo - some properties of a Region.
164 struct RegInfo {
165  RegInfo() : R(nullptr), HasBranch(false) {}
166  RegInfo(Region *RegionIn) : R(RegionIn), HasBranch(false) {}
167  Region *R;
168  bool HasBranch;
170 };
171 
172 typedef DenseMap<Region *, DenseSet<Instruction *>> HoistStopMapTy;
173 
174 // CHRScope - a sequence of regions to CHR together. It corresponds to a
175 // sequence of conditional blocks. It can have subscopes which correspond to
176 // nested conditional blocks. Nested CHRScopes form a tree.
177 class CHRScope {
178  public:
179  CHRScope(RegInfo RI) : BranchInsertPoint(nullptr) {
180  assert(RI.R && "Null RegionIn");
181  RegInfos.push_back(RI);
182  }
183 
184  Region *getParentRegion() {
185  assert(RegInfos.size() > 0 && "Empty CHRScope");
186  Region *Parent = RegInfos[0].R->getParent();
187  assert(Parent && "Unexpected to call this on the top-level region");
188  return Parent;
189  }
190 
191  BasicBlock *getEntryBlock() {
192  assert(RegInfos.size() > 0 && "Empty CHRScope");
193  return RegInfos.front().R->getEntry();
194  }
195 
196  BasicBlock *getExitBlock() {
197  assert(RegInfos.size() > 0 && "Empty CHRScope");
198  return RegInfos.back().R->getExit();
199  }
200 
201  bool appendable(CHRScope *Next) {
202  // The next scope is appendable only if this scope is directly connected to
203  // it (which implies it post-dominates this scope) and this scope dominates
204  // it (no edge to the next scope outside this scope).
205  BasicBlock *NextEntry = Next->getEntryBlock();
206  if (getExitBlock() != NextEntry)
207  // Not directly connected.
208  return false;
209  Region *LastRegion = RegInfos.back().R;
210  for (BasicBlock *Pred : predecessors(NextEntry))
211  if (!LastRegion->contains(Pred))
212  // There's an edge going into the entry of the next scope from outside
213  // of this scope.
214  return false;
215  return true;
216  }
217 
218  void append(CHRScope *Next) {
219  assert(RegInfos.size() > 0 && "Empty CHRScope");
220  assert(Next->RegInfos.size() > 0 && "Empty CHRScope");
221  assert(getParentRegion() == Next->getParentRegion() &&
222  "Must be siblings");
223  assert(getExitBlock() == Next->getEntryBlock() &&
224  "Must be adjacent");
225  RegInfos.append(Next->RegInfos.begin(), Next->RegInfos.end());
226  Subs.append(Next->Subs.begin(), Next->Subs.end());
227  }
228 
229  void addSub(CHRScope *SubIn) {
230 #ifndef NDEBUG
231  bool IsChild = false;
232  for (RegInfo &RI : RegInfos)
233  if (RI.R == SubIn->getParentRegion()) {
234  IsChild = true;
235  break;
236  }
237  assert(IsChild && "Must be a child");
238 #endif
239  Subs.push_back(SubIn);
240  }
241 
242  // Split this scope at the boundary region into two, which will belong to the
243  // tail and returns the tail.
244  CHRScope *split(Region *Boundary) {
245  assert(Boundary && "Boundary null");
246  assert(RegInfos.begin()->R != Boundary &&
247  "Can't be split at beginning");
248  auto BoundaryIt = llvm::find_if(
249  RegInfos, [&Boundary](const RegInfo &RI) { return Boundary == RI.R; });
250  if (BoundaryIt == RegInfos.end())
251  return nullptr;
252  ArrayRef<RegInfo> TailRegInfos(BoundaryIt, RegInfos.end());
253  DenseSet<Region *> TailRegionSet;
254  for (const RegInfo &RI : TailRegInfos)
255  TailRegionSet.insert(RI.R);
256 
257  auto TailIt =
258  std::stable_partition(Subs.begin(), Subs.end(), [&](CHRScope *Sub) {
259  assert(Sub && "null Sub");
260  Region *Parent = Sub->getParentRegion();
261  if (TailRegionSet.count(Parent))
262  return false;
263 
264  assert(llvm::any_of(
265  RegInfos,
266  [&Parent](const RegInfo &RI) { return Parent == RI.R; }) &&
267  "Must be in head");
268  return true;
269  });
270  ArrayRef<CHRScope *> TailSubs(TailIt, Subs.end());
271 
272  assert(HoistStopMap.empty() && "MapHoistStops must be empty");
273  auto *Scope = new CHRScope(TailRegInfos, TailSubs);
274  RegInfos.erase(BoundaryIt, RegInfos.end());
275  Subs.erase(TailIt, Subs.end());
276  return Scope;
277  }
278 
279  bool contains(Instruction *I) const {
280  BasicBlock *Parent = I->getParent();
281  for (const RegInfo &RI : RegInfos)
282  if (RI.R->contains(Parent))
283  return true;
284  return false;
285  }
286 
287  void print(raw_ostream &OS) const;
288 
289  SmallVector<RegInfo, 8> RegInfos; // Regions that belong to this scope
290  SmallVector<CHRScope *, 8> Subs; // Subscopes.
291 
292  // The instruction at which to insert the CHR conditional branch (and hoist
293  // the dependent condition values).
294  Instruction *BranchInsertPoint;
295 
296  // True-biased and false-biased regions (conditional blocks),
297  // respectively. Used only for the outermost scope and includes regions in
298  // subscopes. The rest are unbiased.
299  DenseSet<Region *> TrueBiasedRegions;
300  DenseSet<Region *> FalseBiasedRegions;
301  // Among the biased regions, the regions that get CHRed.
302  SmallVector<RegInfo, 8> CHRRegions;
303 
304  // True-biased and false-biased selects, respectively. Used only for the
305  // outermost scope and includes ones in subscopes.
306  DenseSet<SelectInst *> TrueBiasedSelects;
307  DenseSet<SelectInst *> FalseBiasedSelects;
308 
309  // Map from one of the above regions to the instructions to stop
310  // hoisting instructions at through use-def chains.
311  HoistStopMapTy HoistStopMap;
312 
313  private:
314  CHRScope(ArrayRef<RegInfo> RegInfosIn, ArrayRef<CHRScope *> SubsIn)
315  : RegInfos(RegInfosIn.begin(), RegInfosIn.end()),
316  Subs(SubsIn.begin(), SubsIn.end()), BranchInsertPoint(nullptr) {}
317 };
318 
319 class CHR {
320  public:
321  CHR(Function &Fin, BlockFrequencyInfo &BFIin, DominatorTree &DTin,
322  ProfileSummaryInfo &PSIin, RegionInfo &RIin,
324  : F(Fin), BFI(BFIin), DT(DTin), PSI(PSIin), RI(RIin), ORE(OREin) {}
325 
326  ~CHR() {
327  for (CHRScope *Scope : Scopes) {
328  delete Scope;
329  }
330  }
331 
332  bool run();
333 
334  private:
335  // See the comments in CHR::run() for the high level flow of the algorithm and
336  // what the following functions do.
337 
338  void findScopes(SmallVectorImpl<CHRScope *> &Output) {
339  Region *R = RI.getTopLevelRegion();
340  if (CHRScope *Scope = findScopes(R, nullptr, nullptr, Output)) {
341  Output.push_back(Scope);
342  }
343  }
344  CHRScope *findScopes(Region *R, Region *NextRegion, Region *ParentRegion,
346  CHRScope *findScope(Region *R);
347  void checkScopeHoistable(CHRScope *Scope);
348 
349  void splitScopes(SmallVectorImpl<CHRScope *> &Input,
351  SmallVector<CHRScope *, 8> splitScope(CHRScope *Scope,
352  CHRScope *Outer,
353  DenseSet<Value *> *OuterConditionValues,
354  Instruction *OuterInsertPoint,
356  DenseSet<Instruction *> &Unhoistables);
357 
358  void classifyBiasedScopes(SmallVectorImpl<CHRScope *> &Scopes);
359  void classifyBiasedScopes(CHRScope *Scope, CHRScope *OutermostScope);
360 
361  void filterScopes(SmallVectorImpl<CHRScope *> &Input,
363 
364  void setCHRRegions(SmallVectorImpl<CHRScope *> &Input,
366  void setCHRRegions(CHRScope *Scope, CHRScope *OutermostScope);
367 
368  void sortScopes(SmallVectorImpl<CHRScope *> &Input,
370 
371  void transformScopes(SmallVectorImpl<CHRScope *> &CHRScopes);
372  void transformScopes(CHRScope *Scope, DenseSet<PHINode *> &TrivialPHIs);
373  void cloneScopeBlocks(CHRScope *Scope,
374  BasicBlock *PreEntryBlock,
375  BasicBlock *ExitBlock,
376  Region *LastRegion,
377  ValueToValueMapTy &VMap);
378  BranchInst *createMergedBranch(BasicBlock *PreEntryBlock,
379  BasicBlock *EntryBlock,
380  BasicBlock *NewEntryBlock,
381  ValueToValueMapTy &VMap);
382  void fixupBranchesAndSelects(CHRScope *Scope,
383  BasicBlock *PreEntryBlock,
384  BranchInst *MergedBR,
386  void fixupBranch(Region *R,
387  CHRScope *Scope,
388  IRBuilder<> &IRB,
389  Value *&MergedCondition, BranchProbability &CHRBranchBias);
390  void fixupSelect(SelectInst* SI,
391  CHRScope *Scope,
392  IRBuilder<> &IRB,
393  Value *&MergedCondition, BranchProbability &CHRBranchBias);
394  void addToMergedCondition(bool IsTrueBiased, Value *Cond,
395  Instruction *BranchOrSelect,
396  CHRScope *Scope,
397  IRBuilder<> &IRB,
398  Value *&MergedCondition);
399 
400  Function &F;
402  DominatorTree &DT;
403  ProfileSummaryInfo &PSI;
404  RegionInfo &RI;
406  CHRStats Stats;
407 
408  // All the true-biased regions in the function
409  DenseSet<Region *> TrueBiasedRegionsGlobal;
410  // All the false-biased regions in the function
411  DenseSet<Region *> FalseBiasedRegionsGlobal;
412  // All the true-biased selects in the function
413  DenseSet<SelectInst *> TrueBiasedSelectsGlobal;
414  // All the false-biased selects in the function
415  DenseSet<SelectInst *> FalseBiasedSelectsGlobal;
416  // A map from biased regions to their branch bias
418  // A map from biased selects to their branch bias
420  // All the scopes.
421  DenseSet<CHRScope *> Scopes;
422 };
423 
424 } // end anonymous namespace
425 
426 static inline
428  const CHRStats &Stats) {
429  Stats.print(OS);
430  return OS;
431 }
432 
433 static inline
434 raw_ostream &operator<<(raw_ostream &OS, const CHRScope &Scope) {
435  Scope.print(OS);
436  return OS;
437 }
438 
440  if (ForceCHR)
441  return true;
442 
443  if (!CHRModuleList.empty() || !CHRFunctionList.empty()) {
444  if (CHRModules.count(F.getParent()->getName()))
445  return true;
446  return CHRFunctions.count(F.getName());
447  }
448 
449  assert(PSI.hasProfileSummary() && "Empty PSI?");
450  return PSI.isFunctionEntryHot(&F);
451 }
452 
453 static void LLVM_ATTRIBUTE_UNUSED dumpIR(Function &F, const char *Label,
454  CHRStats *Stats) {
455  StringRef FuncName = F.getName();
456  StringRef ModuleName = F.getParent()->getName();
457  (void)(FuncName); // Unused in release build.
458  (void)(ModuleName); // Unused in release build.
459  CHR_DEBUG(dbgs() << "CHR IR dump " << Label << " " << ModuleName << " "
460  << FuncName);
461  if (Stats)
462  CHR_DEBUG(dbgs() << " " << *Stats);
463  CHR_DEBUG(dbgs() << "\n");
464  CHR_DEBUG(F.dump());
465 }
466 
467 void CHRScope::print(raw_ostream &OS) const {
468  assert(RegInfos.size() > 0 && "Empty CHRScope");
469  OS << "CHRScope[";
470  OS << RegInfos.size() << ", Regions[";
471  for (const RegInfo &RI : RegInfos) {
472  OS << RI.R->getNameStr();
473  if (RI.HasBranch)
474  OS << " B";
475  if (RI.Selects.size() > 0)
476  OS << " S" << RI.Selects.size();
477  OS << ", ";
478  }
479  if (RegInfos[0].R->getParent()) {
480  OS << "], Parent " << RegInfos[0].R->getParent()->getNameStr();
481  } else {
482  // top level region
483  OS << "]";
484  }
485  OS << ", Subs[";
486  for (CHRScope *Sub : Subs) {
487  OS << *Sub << ", ";
488  }
489  OS << "]]";
490 }
491 
492 // Return true if the given instruction type can be hoisted by CHR.
494  return isa<BinaryOperator>(I) || isa<CastInst>(I) || isa<SelectInst>(I) ||
495  isa<GetElementPtrInst>(I) || isa<CmpInst>(I) ||
496  isa<InsertElementInst>(I) || isa<ExtractElementInst>(I) ||
497  isa<ShuffleVectorInst>(I) || isa<ExtractValueInst>(I) ||
498  isa<InsertValueInst>(I);
499 }
500 
501 // Return true if the given instruction can be hoisted by CHR.
504  return false;
505  return isSafeToSpeculativelyExecute(I, nullptr, &DT);
506 }
507 
508 // Recursively traverse the use-def chains of the given value and return a set
509 // of the unhoistable base values defined within the scope (excluding the
510 // first-region entry block) or the (hoistable or unhoistable) base values that
511 // are defined outside (including the first-region entry block) of the
512 // scope. The returned set doesn't include constants.
513 static const std::set<Value *> &
515  DenseMap<Value *, std::set<Value *>> &Visited) {
516  auto It = Visited.find(V);
517  if (It != Visited.end()) {
518  return It->second;
519  }
520  std::set<Value *> Result;
521  if (auto *I = dyn_cast<Instruction>(V)) {
522  // We don't stop at a block that's not in the Scope because we would miss
523  // some instructions that are based on the same base values if we stop
524  // there.
525  if (!isHoistable(I, DT)) {
526  Result.insert(I);
527  return Visited.insert(std::make_pair(V, std::move(Result))).first->second;
528  }
529  // I is hoistable above the Scope.
530  for (Value *Op : I->operands()) {
531  const std::set<Value *> &OpResult = getBaseValues(Op, DT, Visited);
532  Result.insert(OpResult.begin(), OpResult.end());
533  }
534  return Visited.insert(std::make_pair(V, std::move(Result))).first->second;
535  }
536  if (isa<Argument>(V)) {
537  Result.insert(V);
538  }
539  // We don't include others like constants because those won't lead to any
540  // chance of folding of conditions (eg two bit checks merged into one check)
541  // after CHR.
542  return Visited.insert(std::make_pair(V, std::move(Result))).first->second;
543 }
544 
545 // Return true if V is already hoisted or can be hoisted (along with its
546 // operands) above the insert point. When it returns true and HoistStops is
547 // non-null, the instructions to stop hoisting at through the use-def chains are
548 // inserted into HoistStops.
549 static bool
551  DenseSet<Instruction *> &Unhoistables,
552  DenseSet<Instruction *> *HoistStops,
554  assert(InsertPoint && "Null InsertPoint");
555  if (auto *I = dyn_cast<Instruction>(V)) {
556  auto It = Visited.find(I);
557  if (It != Visited.end()) {
558  return It->second;
559  }
560  assert(DT.getNode(I->getParent()) && "DT must contain I's parent block");
561  assert(DT.getNode(InsertPoint->getParent()) && "DT must contain Destination");
562  if (Unhoistables.count(I)) {
563  // Don't hoist if they are not to be hoisted.
564  Visited[I] = false;
565  return false;
566  }
567  if (DT.dominates(I, InsertPoint)) {
568  // We are already above the insert point. Stop here.
569  if (HoistStops)
570  HoistStops->insert(I);
571  Visited[I] = true;
572  return true;
573  }
574  // We aren't not above the insert point, check if we can hoist it above the
575  // insert point.
576  if (isHoistable(I, DT)) {
577  // Check operands first.
578  DenseSet<Instruction *> OpsHoistStops;
579  bool AllOpsHoisted = true;
580  for (Value *Op : I->operands()) {
581  if (!checkHoistValue(Op, InsertPoint, DT, Unhoistables, &OpsHoistStops,
582  Visited)) {
583  AllOpsHoisted = false;
584  break;
585  }
586  }
587  if (AllOpsHoisted) {
588  CHR_DEBUG(dbgs() << "checkHoistValue " << *I << "\n");
589  if (HoistStops)
590  HoistStops->insert(OpsHoistStops.begin(), OpsHoistStops.end());
591  Visited[I] = true;
592  return true;
593  }
594  }
595  Visited[I] = false;
596  return false;
597  }
598  // Non-instructions are considered hoistable.
599  return true;
600 }
601 
602 // Returns true and sets the true probability and false probability of an
603 // MD_prof metadata if it's well-formed.
604 static bool checkMDProf(MDNode *MD, BranchProbability &TrueProb,
605  BranchProbability &FalseProb) {
606  if (!MD) return false;
607  MDString *MDName = cast<MDString>(MD->getOperand(0));
608  if (MDName->getString() != "branch_weights" ||
609  MD->getNumOperands() != 3)
610  return false;
611  ConstantInt *TrueWeight = mdconst::extract<ConstantInt>(MD->getOperand(1));
612  ConstantInt *FalseWeight = mdconst::extract<ConstantInt>(MD->getOperand(2));
613  if (!TrueWeight || !FalseWeight)
614  return false;
615  uint64_t TrueWt = TrueWeight->getValue().getZExtValue();
616  uint64_t FalseWt = FalseWeight->getValue().getZExtValue();
617  uint64_t SumWt = TrueWt + FalseWt;
618 
619  assert(SumWt >= TrueWt && SumWt >= FalseWt &&
620  "Overflow calculating branch probabilities.");
621 
622  // Guard against 0-to-0 branch weights to avoid a division-by-zero crash.
623  if (SumWt == 0)
624  return false;
625 
626  TrueProb = BranchProbability::getBranchProbability(TrueWt, SumWt);
627  FalseProb = BranchProbability::getBranchProbability(FalseWt, SumWt);
628  return true;
629 }
630 
632  return BranchProbability::getBranchProbability(
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.
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.contains(&I)) {
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 any of the basic blocks have address taken, we must skip this region
771  // because we cannot clone basic blocks that have address taken.
772  for (BasicBlock *BB : R->blocks())
773  if (BB->hasAddressTaken())
774  return nullptr;
775  if (Exit) {
776  // Try to find an if-then block (check if R is an if-then).
777  // if (cond) {
778  // ...
779  // }
780  auto *BI = dyn_cast<BranchInst>(Entry->getTerminator());
781  if (BI)
782  CHR_DEBUG(dbgs() << "BI.isConditional " << BI->isConditional() << "\n");
783  else
784  CHR_DEBUG(dbgs() << "BI null\n");
785  if (BI && BI->isConditional()) {
786  BasicBlock *S0 = BI->getSuccessor(0);
787  BasicBlock *S1 = BI->getSuccessor(1);
788  CHR_DEBUG(dbgs() << "S0 " << S0->getName() << "\n");
789  CHR_DEBUG(dbgs() << "S1 " << S1->getName() << "\n");
790  if (S0 != S1 && (S0 == Exit || S1 == Exit)) {
791  RegInfo RI(R);
792  RI.HasBranch = checkBiasedBranch(
793  BI, R, TrueBiasedRegionsGlobal, FalseBiasedRegionsGlobal,
794  BranchBiasMap);
795  Result = new CHRScope(RI);
796  Scopes.insert(Result);
797  CHR_DEBUG(dbgs() << "Found a region with a branch\n");
798  ++Stats.NumBranches;
799  if (!RI.HasBranch) {
800  ORE.emit([&]() {
801  return OptimizationRemarkMissed(DEBUG_TYPE, "BranchNotBiased", BI)
802  << "Branch not biased";
803  });
804  }
805  }
806  }
807  }
808  {
809  // Try to look for selects in the direct child blocks (as opposed to in
810  // subregions) of R.
811  // ...
812  // if (..) { // Some subregion
813  // ...
814  // }
815  // if (..) { // Some subregion
816  // ...
817  // }
818  // ...
819  // a = cond ? b : c;
820  // ...
822  for (RegionNode *E : R->elements()) {
823  if (E->isSubRegion())
824  continue;
825  // This returns the basic block of E if E is a direct child of R (not a
826  // subregion.)
827  BasicBlock *BB = E->getEntry();
828  // Need to push in the order to make it easier to find the first Select
829  // later.
830  for (Instruction &I : *BB) {
831  if (auto *SI = dyn_cast<SelectInst>(&I)) {
832  Selects.push_back(SI);
833  ++Stats.NumBranches;
834  }
835  }
836  }
837  if (Selects.size() > 0) {
838  auto AddSelects = [&](RegInfo &RI) {
839  for (auto *SI : Selects)
840  if (checkBiasedSelect(SI, RI.R,
841  TrueBiasedSelectsGlobal,
842  FalseBiasedSelectsGlobal,
843  SelectBiasMap))
844  RI.Selects.push_back(SI);
845  else
846  ORE.emit([&]() {
847  return OptimizationRemarkMissed(DEBUG_TYPE, "SelectNotBiased", SI)
848  << "Select not biased";
849  });
850  };
851  if (!Result) {
852  CHR_DEBUG(dbgs() << "Found a select-only region\n");
853  RegInfo RI(R);
854  AddSelects(RI);
855  Result = new CHRScope(RI);
856  Scopes.insert(Result);
857  } else {
858  CHR_DEBUG(dbgs() << "Found select(s) in a region with a branch\n");
859  AddSelects(Result->RegInfos[0]);
860  }
861  }
862  }
863 
864  if (Result) {
865  checkScopeHoistable(Result);
866  }
867  return Result;
868 }
869 
870 // Check that any of the branch and the selects in the region could be
871 // hoisted above the the CHR branch insert point (the most dominating of
872 // them, either the branch (at the end of the first block) or the first
873 // select in the first block). If the branch can't be hoisted, drop the
874 // selects in the first blocks.
875 //
876 // For example, for the following scope/region with selects, we want to insert
877 // the merged branch right before the first select in the first/entry block by
878 // hoisting c1, c2, c3, and c4.
879 //
880 // // Branch insert point here.
881 // a = c1 ? b : c; // Select 1
882 // d = c2 ? e : f; // Select 2
883 // if (c3) { // Branch
884 // ...
885 // c4 = foo() // A call.
886 // g = c4 ? h : i; // Select 3
887 // }
888 //
889 // But suppose we can't hoist c4 because it's dependent on the preceding
890 // call. Then, we drop Select 3. Furthermore, if we can't hoist c2, we also drop
891 // Select 2. If we can't hoist c3, we drop Selects 1 & 2.
892 void CHR::checkScopeHoistable(CHRScope *Scope) {
893  RegInfo &RI = Scope->RegInfos[0];
894  Region *R = RI.R;
895  BasicBlock *EntryBB = R->getEntry();
896  auto *Branch = RI.HasBranch ?
897  cast<BranchInst>(EntryBB->getTerminator()) : nullptr;
898  SmallVector<SelectInst *, 8> &Selects = RI.Selects;
899  if (RI.HasBranch || !Selects.empty()) {
900  Instruction *InsertPoint = getBranchInsertPoint(RI);
901  CHR_DEBUG(dbgs() << "InsertPoint " << *InsertPoint << "\n");
902  // Avoid a data dependence from a select or a branch to a(nother)
903  // select. Note no instruction can't data-depend on a branch (a branch
904  // instruction doesn't produce a value).
905  DenseSet<Instruction *> Unhoistables;
906  // Initialize Unhoistables with the selects.
907  for (SelectInst *SI : Selects) {
908  Unhoistables.insert(SI);
909  }
910  // Remove Selects that can't be hoisted.
911  for (auto it = Selects.begin(); it != Selects.end(); ) {
912  SelectInst *SI = *it;
913  if (SI == InsertPoint) {
914  ++it;
915  continue;
916  }
918  bool IsHoistable = checkHoistValue(SI->getCondition(), InsertPoint,
919  DT, Unhoistables, nullptr, Visited);
920  if (!IsHoistable) {
921  CHR_DEBUG(dbgs() << "Dropping select " << *SI << "\n");
922  ORE.emit([&]() {
924  "DropUnhoistableSelect", SI)
925  << "Dropped unhoistable select";
926  });
927  it = Selects.erase(it);
928  // Since we are dropping the select here, we also drop it from
929  // Unhoistables.
930  Unhoistables.erase(SI);
931  } else
932  ++it;
933  }
934  // Update InsertPoint after potentially removing selects.
935  InsertPoint = getBranchInsertPoint(RI);
936  CHR_DEBUG(dbgs() << "InsertPoint " << *InsertPoint << "\n");
937  if (RI.HasBranch && InsertPoint != Branch) {
939  bool IsHoistable = checkHoistValue(Branch->getCondition(), InsertPoint,
940  DT, Unhoistables, nullptr, Visited);
941  if (!IsHoistable) {
942  // If the branch isn't hoistable, drop the selects in the entry
943  // block, preferring the branch, which makes the branch the hoist
944  // point.
945  assert(InsertPoint != Branch && "Branch must not be the hoist point");
946  CHR_DEBUG(dbgs() << "Dropping selects in entry block \n");
947  CHR_DEBUG(
948  for (SelectInst *SI : Selects) {
949  dbgs() << "SI " << *SI << "\n";
950  });
951  for (SelectInst *SI : Selects) {
952  ORE.emit([&]() {
954  "DropSelectUnhoistableBranch", SI)
955  << "Dropped select due to unhoistable branch";
956  });
957  }
958  llvm::erase_if(Selects, [EntryBB](SelectInst *SI) {
959  return SI->getParent() == EntryBB;
960  });
961  Unhoistables.clear();
962  InsertPoint = Branch;
963  }
964  }
965  CHR_DEBUG(dbgs() << "InsertPoint " << *InsertPoint << "\n");
966 #ifndef NDEBUG
967  if (RI.HasBranch) {
968  assert(!DT.dominates(Branch, InsertPoint) &&
969  "Branch can't be already above the hoist point");
971  assert(checkHoistValue(Branch->getCondition(), InsertPoint,
972  DT, Unhoistables, nullptr, Visited) &&
973  "checkHoistValue for branch");
974  }
975  for (auto *SI : Selects) {
976  assert(!DT.dominates(SI, InsertPoint) &&
977  "SI can't be already above the hoist point");
979  assert(checkHoistValue(SI->getCondition(), InsertPoint, DT,
980  Unhoistables, nullptr, Visited) &&
981  "checkHoistValue for selects");
982  }
983  CHR_DEBUG(dbgs() << "Result\n");
984  if (RI.HasBranch) {
985  CHR_DEBUG(dbgs() << "BI " << *Branch << "\n");
986  }
987  for (auto *SI : Selects) {
988  CHR_DEBUG(dbgs() << "SI " << *SI << "\n");
989  }
990 #endif
991  }
992 }
993 
994 // Traverse the region tree, find all nested scopes and merge them if possible.
995 CHRScope * CHR::findScopes(Region *R, Region *NextRegion, Region *ParentRegion,
996  SmallVectorImpl<CHRScope *> &Scopes) {
997  CHR_DEBUG(dbgs() << "findScopes " << R->getNameStr() << "\n");
998  CHRScope *Result = findScope(R);
999  // Visit subscopes.
1000  CHRScope *ConsecutiveSubscope = nullptr;
1001  SmallVector<CHRScope *, 8> Subscopes;
1002  for (auto It = R->begin(); It != R->end(); ++It) {
1003  const std::unique_ptr<Region> &SubR = *It;
1004  auto NextIt = std::next(It);
1005  Region *NextSubR = NextIt != R->end() ? NextIt->get() : nullptr;
1006  CHR_DEBUG(dbgs() << "Looking at subregion " << SubR.get()->getNameStr()
1007  << "\n");
1008  CHRScope *SubCHRScope = findScopes(SubR.get(), NextSubR, R, Scopes);
1009  if (SubCHRScope) {
1010  CHR_DEBUG(dbgs() << "Subregion Scope " << *SubCHRScope << "\n");
1011  } else {
1012  CHR_DEBUG(dbgs() << "Subregion Scope null\n");
1013  }
1014  if (SubCHRScope) {
1015  if (!ConsecutiveSubscope)
1016  ConsecutiveSubscope = SubCHRScope;
1017  else if (!ConsecutiveSubscope->appendable(SubCHRScope)) {
1018  Subscopes.push_back(ConsecutiveSubscope);
1019  ConsecutiveSubscope = SubCHRScope;
1020  } else
1021  ConsecutiveSubscope->append(SubCHRScope);
1022  } else {
1023  if (ConsecutiveSubscope) {
1024  Subscopes.push_back(ConsecutiveSubscope);
1025  }
1026  ConsecutiveSubscope = nullptr;
1027  }
1028  }
1029  if (ConsecutiveSubscope) {
1030  Subscopes.push_back(ConsecutiveSubscope);
1031  }
1032  for (CHRScope *Sub : Subscopes) {
1033  if (Result) {
1034  // Combine it with the parent.
1035  Result->addSub(Sub);
1036  } else {
1037  // Push Subscopes as they won't be combined with the parent.
1038  Scopes.push_back(Sub);
1039  }
1040  }
1041  return Result;
1042 }
1043 
1045  DenseSet<Value *> ConditionValues;
1046  if (RI.HasBranch) {
1047  auto *BI = cast<BranchInst>(RI.R->getEntry()->getTerminator());
1048  ConditionValues.insert(BI->getCondition());
1049  }
1050  for (SelectInst *SI : RI.Selects) {
1051  ConditionValues.insert(SI->getCondition());
1052  }
1053  return ConditionValues;
1054 }
1055 
1056 
1057 // Determine whether to split a scope depending on the sets of the branch
1058 // condition values of the previous region and the current region. We split
1059 // (return true) it if 1) the condition values of the inner/lower scope can't be
1060 // hoisted up to the outer/upper scope, or 2) the two sets of the condition
1061 // values have an empty intersection (because the combined branch conditions
1062 // won't probably lead to a simpler combined condition).
1063 static bool shouldSplit(Instruction *InsertPoint,
1064  DenseSet<Value *> &PrevConditionValues,
1065  DenseSet<Value *> &ConditionValues,
1066  DominatorTree &DT,
1067  DenseSet<Instruction *> &Unhoistables) {
1068  assert(InsertPoint && "Null InsertPoint");
1069  CHR_DEBUG(
1070  dbgs() << "shouldSplit " << *InsertPoint << " PrevConditionValues ";
1071  for (Value *V : PrevConditionValues) {
1072  dbgs() << *V << ", ";
1073  }
1074  dbgs() << " ConditionValues ";
1075  for (Value *V : ConditionValues) {
1076  dbgs() << *V << ", ";
1077  }
1078  dbgs() << "\n");
1079  // If any of Bases isn't hoistable to the hoist point, split.
1080  for (Value *V : ConditionValues) {
1082  if (!checkHoistValue(V, InsertPoint, DT, Unhoistables, nullptr, Visited)) {
1083  CHR_DEBUG(dbgs() << "Split. checkHoistValue false " << *V << "\n");
1084  return true; // Not hoistable, split.
1085  }
1086  }
1087  // If PrevConditionValues or ConditionValues is empty, don't split to avoid
1088  // unnecessary splits at scopes with no branch/selects. If
1089  // PrevConditionValues and ConditionValues don't intersect at all, split.
1090  if (!PrevConditionValues.empty() && !ConditionValues.empty()) {
1091  // Use std::set as DenseSet doesn't work with set_intersection.
1092  std::set<Value *> PrevBases, Bases;
1094  for (Value *V : PrevConditionValues) {
1095  const std::set<Value *> &BaseValues = getBaseValues(V, DT, Visited);
1096  PrevBases.insert(BaseValues.begin(), BaseValues.end());
1097  }
1098  for (Value *V : ConditionValues) {
1099  const std::set<Value *> &BaseValues = getBaseValues(V, DT, Visited);
1100  Bases.insert(BaseValues.begin(), BaseValues.end());
1101  }
1102  CHR_DEBUG(
1103  dbgs() << "PrevBases ";
1104  for (Value *V : PrevBases) {
1105  dbgs() << *V << ", ";
1106  }
1107  dbgs() << " Bases ";
1108  for (Value *V : Bases) {
1109  dbgs() << *V << ", ";
1110  }
1111  dbgs() << "\n");
1112  std::vector<Value *> Intersection;
1113  std::set_intersection(PrevBases.begin(), PrevBases.end(), Bases.begin(),
1114  Bases.end(), std::back_inserter(Intersection));
1115  if (Intersection.empty()) {
1116  // Empty intersection, split.
1117  CHR_DEBUG(dbgs() << "Split. Intersection empty\n");
1118  return true;
1119  }
1120  }
1121  CHR_DEBUG(dbgs() << "No split\n");
1122  return false; // Don't split.
1123 }
1124 
1125 static void getSelectsInScope(CHRScope *Scope,
1126  DenseSet<Instruction *> &Output) {
1127  for (RegInfo &RI : Scope->RegInfos)
1128  for (SelectInst *SI : RI.Selects)
1129  Output.insert(SI);
1130  for (CHRScope *Sub : Scope->Subs)
1131  getSelectsInScope(Sub, Output);
1132 }
1133 
1134 void CHR::splitScopes(SmallVectorImpl<CHRScope *> &Input,
1135  SmallVectorImpl<CHRScope *> &Output) {
1136  for (CHRScope *Scope : Input) {
1137  assert(!Scope->BranchInsertPoint &&
1138  "BranchInsertPoint must not be set");
1139  DenseSet<Instruction *> Unhoistables;
1140  getSelectsInScope(Scope, Unhoistables);
1141  splitScope(Scope, nullptr, nullptr, nullptr, Output, Unhoistables);
1142  }
1143 #ifndef NDEBUG
1144  for (CHRScope *Scope : Output) {
1145  assert(Scope->BranchInsertPoint && "BranchInsertPoint must be set");
1146  }
1147 #endif
1148 }
1149 
1150 SmallVector<CHRScope *, 8> CHR::splitScope(
1151  CHRScope *Scope,
1152  CHRScope *Outer,
1153  DenseSet<Value *> *OuterConditionValues,
1154  Instruction *OuterInsertPoint,
1156  DenseSet<Instruction *> &Unhoistables) {
1157  if (Outer) {
1158  assert(OuterConditionValues && "Null OuterConditionValues");
1159  assert(OuterInsertPoint && "Null OuterInsertPoint");
1160  }
1161  bool PrevSplitFromOuter = true;
1162  DenseSet<Value *> PrevConditionValues;
1163  Instruction *PrevInsertPoint = nullptr;
1165  SmallVector<bool, 8> SplitsSplitFromOuter;
1166  SmallVector<DenseSet<Value *>, 8> SplitsConditionValues;
1167  SmallVector<Instruction *, 8> SplitsInsertPoints;
1168  SmallVector<RegInfo, 8> RegInfos(Scope->RegInfos); // Copy
1169  for (RegInfo &RI : RegInfos) {
1170  Instruction *InsertPoint = getBranchInsertPoint(RI);
1171  DenseSet<Value *> ConditionValues = getCHRConditionValuesForRegion(RI);
1172  CHR_DEBUG(
1173  dbgs() << "ConditionValues ";
1174  for (Value *V : ConditionValues) {
1175  dbgs() << *V << ", ";
1176  }
1177  dbgs() << "\n");
1178  if (RI.R == RegInfos[0].R) {
1179  // First iteration. Check to see if we should split from the outer.
1180  if (Outer) {
1181  CHR_DEBUG(dbgs() << "Outer " << *Outer << "\n");
1182  CHR_DEBUG(dbgs() << "Should split from outer at "
1183  << RI.R->getNameStr() << "\n");
1184  if (shouldSplit(OuterInsertPoint, *OuterConditionValues,
1185  ConditionValues, DT, Unhoistables)) {
1186  PrevConditionValues = ConditionValues;
1187  PrevInsertPoint = InsertPoint;
1188  ORE.emit([&]() {
1190  "SplitScopeFromOuter",
1191  RI.R->getEntry()->getTerminator())
1192  << "Split scope from outer due to unhoistable branch/select "
1193  << "and/or lack of common condition values";
1194  });
1195  } else {
1196  // Not splitting from the outer. Use the outer bases and insert
1197  // point. Union the bases.
1198  PrevSplitFromOuter = false;
1199  PrevConditionValues = *OuterConditionValues;
1200  PrevConditionValues.insert(ConditionValues.begin(),
1201  ConditionValues.end());
1202  PrevInsertPoint = OuterInsertPoint;
1203  }
1204  } else {
1205  CHR_DEBUG(dbgs() << "Outer null\n");
1206  PrevConditionValues = ConditionValues;
1207  PrevInsertPoint = InsertPoint;
1208  }
1209  } else {
1210  CHR_DEBUG(dbgs() << "Should split from prev at "
1211  << RI.R->getNameStr() << "\n");
1212  if (shouldSplit(PrevInsertPoint, PrevConditionValues, ConditionValues,
1213  DT, Unhoistables)) {
1214  CHRScope *Tail = Scope->split(RI.R);
1215  Scopes.insert(Tail);
1216  Splits.push_back(Scope);
1217  SplitsSplitFromOuter.push_back(PrevSplitFromOuter);
1218  SplitsConditionValues.push_back(PrevConditionValues);
1219  SplitsInsertPoints.push_back(PrevInsertPoint);
1220  Scope = Tail;
1221  PrevConditionValues = ConditionValues;
1222  PrevInsertPoint = InsertPoint;
1223  PrevSplitFromOuter = true;
1224  ORE.emit([&]() {
1226  "SplitScopeFromPrev",
1227  RI.R->getEntry()->getTerminator())
1228  << "Split scope from previous due to unhoistable branch/select "
1229  << "and/or lack of common condition values";
1230  });
1231  } else {
1232  // Not splitting. Union the bases. Keep the hoist point.
1233  PrevConditionValues.insert(ConditionValues.begin(), ConditionValues.end());
1234  }
1235  }
1236  }
1237  Splits.push_back(Scope);
1238  SplitsSplitFromOuter.push_back(PrevSplitFromOuter);
1239  SplitsConditionValues.push_back(PrevConditionValues);
1240  assert(PrevInsertPoint && "Null PrevInsertPoint");
1241  SplitsInsertPoints.push_back(PrevInsertPoint);
1242  assert(Splits.size() == SplitsConditionValues.size() &&
1243  Splits.size() == SplitsSplitFromOuter.size() &&
1244  Splits.size() == SplitsInsertPoints.size() && "Mismatching sizes");
1245  for (size_t I = 0; I < Splits.size(); ++I) {
1246  CHRScope *Split = Splits[I];
1247  DenseSet<Value *> &SplitConditionValues = SplitsConditionValues[I];
1248  Instruction *SplitInsertPoint = SplitsInsertPoints[I];
1250  DenseSet<Instruction *> SplitUnhoistables;
1251  getSelectsInScope(Split, SplitUnhoistables);
1252  for (CHRScope *Sub : Split->Subs) {
1253  SmallVector<CHRScope *, 8> SubSplits = splitScope(
1254  Sub, Split, &SplitConditionValues, SplitInsertPoint, Output,
1255  SplitUnhoistables);
1256  llvm::append_range(NewSubs, SubSplits);
1257  }
1258  Split->Subs = NewSubs;
1259  }
1261  for (size_t I = 0; I < Splits.size(); ++I) {
1262  CHRScope *Split = Splits[I];
1263  if (SplitsSplitFromOuter[I]) {
1264  // Split from the outer.
1265  Output.push_back(Split);
1266  Split->BranchInsertPoint = SplitsInsertPoints[I];
1267  CHR_DEBUG(dbgs() << "BranchInsertPoint " << *SplitsInsertPoints[I]
1268  << "\n");
1269  } else {
1270  // Connected to the outer.
1271  Result.push_back(Split);
1272  }
1273  }
1274  if (!Outer)
1275  assert(Result.empty() &&
1276  "If no outer (top-level), must return no nested ones");
1277  return Result;
1278 }
1279 
1280 void CHR::classifyBiasedScopes(SmallVectorImpl<CHRScope *> &Scopes) {
1281  for (CHRScope *Scope : Scopes) {
1282  assert(Scope->TrueBiasedRegions.empty() && Scope->FalseBiasedRegions.empty() && "Empty");
1283  classifyBiasedScopes(Scope, Scope);
1284  CHR_DEBUG(
1285  dbgs() << "classifyBiasedScopes " << *Scope << "\n";
1286  dbgs() << "TrueBiasedRegions ";
1287  for (Region *R : Scope->TrueBiasedRegions) {
1288  dbgs() << R->getNameStr() << ", ";
1289  }
1290  dbgs() << "\n";
1291  dbgs() << "FalseBiasedRegions ";
1292  for (Region *R : Scope->FalseBiasedRegions) {
1293  dbgs() << R->getNameStr() << ", ";
1294  }
1295  dbgs() << "\n";
1296  dbgs() << "TrueBiasedSelects ";
1297  for (SelectInst *SI : Scope->TrueBiasedSelects) {
1298  dbgs() << *SI << ", ";
1299  }
1300  dbgs() << "\n";
1301  dbgs() << "FalseBiasedSelects ";
1302  for (SelectInst *SI : Scope->FalseBiasedSelects) {
1303  dbgs() << *SI << ", ";
1304  }
1305  dbgs() << "\n";);
1306  }
1307 }
1308 
1309 void CHR::classifyBiasedScopes(CHRScope *Scope, CHRScope *OutermostScope) {
1310  for (RegInfo &RI : Scope->RegInfos) {
1311  if (RI.HasBranch) {
1312  Region *R = RI.R;
1313  if (TrueBiasedRegionsGlobal.contains(R))
1314  OutermostScope->TrueBiasedRegions.insert(R);
1315  else if (FalseBiasedRegionsGlobal.contains(R))
1316  OutermostScope->FalseBiasedRegions.insert(R);
1317  else
1318  llvm_unreachable("Must be biased");
1319  }
1320  for (SelectInst *SI : RI.Selects) {
1321  if (TrueBiasedSelectsGlobal.contains(SI))
1322  OutermostScope->TrueBiasedSelects.insert(SI);
1323  else if (FalseBiasedSelectsGlobal.contains(SI))
1324  OutermostScope->FalseBiasedSelects.insert(SI);
1325  else
1326  llvm_unreachable("Must be biased");
1327  }
1328  }
1329  for (CHRScope *Sub : Scope->Subs) {
1330  classifyBiasedScopes(Sub, OutermostScope);
1331  }
1332 }
1333 
1334 static bool hasAtLeastTwoBiasedBranches(CHRScope *Scope) {
1335  unsigned NumBiased = Scope->TrueBiasedRegions.size() +
1336  Scope->FalseBiasedRegions.size() +
1337  Scope->TrueBiasedSelects.size() +
1338  Scope->FalseBiasedSelects.size();
1339  return NumBiased >= CHRMergeThreshold;
1340 }
1341 
1342 void CHR::filterScopes(SmallVectorImpl<CHRScope *> &Input,
1343  SmallVectorImpl<CHRScope *> &Output) {
1344  for (CHRScope *Scope : Input) {
1345  // Filter out the ones with only one region and no subs.
1347  CHR_DEBUG(dbgs() << "Filtered out by biased branches truthy-regions "
1348  << Scope->TrueBiasedRegions.size()
1349  << " falsy-regions " << Scope->FalseBiasedRegions.size()
1350  << " true-selects " << Scope->TrueBiasedSelects.size()
1351  << " false-selects " << Scope->FalseBiasedSelects.size() << "\n");
1352  ORE.emit([&]() {
1353  return OptimizationRemarkMissed(
1354  DEBUG_TYPE,
1355  "DropScopeWithOneBranchOrSelect",
1356  Scope->RegInfos[0].R->getEntry()->getTerminator())
1357  << "Drop scope with < "
1358  << ore::NV("CHRMergeThreshold", CHRMergeThreshold)
1359  << " biased branch(es) or select(s)";
1360  });
1361  continue;
1362  }
1363  Output.push_back(Scope);
1364  }
1365 }
1366 
1367 void CHR::setCHRRegions(SmallVectorImpl<CHRScope *> &Input,
1368  SmallVectorImpl<CHRScope *> &Output) {
1369  for (CHRScope *Scope : Input) {
1370  assert(Scope->HoistStopMap.empty() && Scope->CHRRegions.empty() &&
1371  "Empty");
1372  setCHRRegions(Scope, Scope);
1373  Output.push_back(Scope);
1374  CHR_DEBUG(
1375  dbgs() << "setCHRRegions HoistStopMap " << *Scope << "\n";
1376  for (auto pair : Scope->HoistStopMap) {
1377  Region *R = pair.first;
1378  dbgs() << "Region " << R->getNameStr() << "\n";
1379  for (Instruction *I : pair.second) {
1380  dbgs() << "HoistStop " << *I << "\n";
1381  }
1382  }
1383  dbgs() << "CHRRegions" << "\n";
1384  for (RegInfo &RI : Scope->CHRRegions) {
1385  dbgs() << RI.R->getNameStr() << "\n";
1386  });
1387  }
1388 }
1389 
1390 void CHR::setCHRRegions(CHRScope *Scope, CHRScope *OutermostScope) {
1391  DenseSet<Instruction *> Unhoistables;
1392  // Put the biased selects in Unhoistables because they should stay where they
1393  // are and constant-folded after CHR (in case one biased select or a branch
1394  // can depend on another biased select.)
1395  for (RegInfo &RI : Scope->RegInfos) {
1396  for (SelectInst *SI : RI.Selects) {
1397  Unhoistables.insert(SI);
1398  }
1399  }
1400  Instruction *InsertPoint = OutermostScope->BranchInsertPoint;
1401  for (RegInfo &RI : Scope->RegInfos) {
1402  Region *R = RI.R;
1403  DenseSet<Instruction *> HoistStops;
1404  bool IsHoisted = false;
1405  if (RI.HasBranch) {
1406  assert((OutermostScope->TrueBiasedRegions.contains(R) ||
1407  OutermostScope->FalseBiasedRegions.contains(R)) &&
1408  "Must be truthy or falsy");
1409  auto *BI = cast<BranchInst>(R->getEntry()->getTerminator());
1410  // Note checkHoistValue fills in HoistStops.
1412  bool IsHoistable = checkHoistValue(BI->getCondition(), InsertPoint, DT,
1413  Unhoistables, &HoistStops, Visited);
1414  assert(IsHoistable && "Must be hoistable");
1415  (void)(IsHoistable); // Unused in release build
1416  IsHoisted = true;
1417  }
1418  for (SelectInst *SI : RI.Selects) {
1419  assert((OutermostScope->TrueBiasedSelects.contains(SI) ||
1420  OutermostScope->FalseBiasedSelects.contains(SI)) &&
1421  "Must be true or false biased");
1422  // Note checkHoistValue fills in HoistStops.
1424  bool IsHoistable = checkHoistValue(SI->getCondition(), InsertPoint, DT,
1425  Unhoistables, &HoistStops, Visited);
1426  assert(IsHoistable && "Must be hoistable");
1427  (void)(IsHoistable); // Unused in release build
1428  IsHoisted = true;
1429  }
1430  if (IsHoisted) {
1431  OutermostScope->CHRRegions.push_back(RI);
1432  OutermostScope->HoistStopMap[R] = HoistStops;
1433  }
1434  }
1435  for (CHRScope *Sub : Scope->Subs)
1436  setCHRRegions(Sub, OutermostScope);
1437 }
1438 
1439 static bool CHRScopeSorter(CHRScope *Scope1, CHRScope *Scope2) {
1440  return Scope1->RegInfos[0].R->getDepth() < Scope2->RegInfos[0].R->getDepth();
1441 }
1442 
1443 void CHR::sortScopes(SmallVectorImpl<CHRScope *> &Input,
1444  SmallVectorImpl<CHRScope *> &Output) {
1445  Output.resize(Input.size());
1446  llvm::copy(Input, Output.begin());
1448 }
1449 
1450 // Return true if V is already hoisted or was hoisted (along with its operands)
1451 // to the insert point.
1452 static void hoistValue(Value *V, Instruction *HoistPoint, Region *R,
1453  HoistStopMapTy &HoistStopMap,
1454  DenseSet<Instruction *> &HoistedSet,
1455  DenseSet<PHINode *> &TrivialPHIs,
1456  DominatorTree &DT) {
1457  auto IT = HoistStopMap.find(R);
1458  assert(IT != HoistStopMap.end() && "Region must be in hoist stop map");
1459  DenseSet<Instruction *> &HoistStops = IT->second;
1460  if (auto *I = dyn_cast<Instruction>(V)) {
1461  if (I == HoistPoint)
1462  return;
1463  if (HoistStops.count(I))
1464  return;
1465  if (auto *PN = dyn_cast<PHINode>(I))
1466  if (TrivialPHIs.count(PN))
1467  // The trivial phi inserted by the previous CHR scope could replace a
1468  // non-phi in HoistStops. Note that since this phi is at the exit of a
1469  // previous CHR scope, which dominates this scope, it's safe to stop
1470  // hoisting there.
1471  return;
1472  if (HoistedSet.count(I))
1473  // Already hoisted, return.
1474  return;
1475  assert(isHoistableInstructionType(I) && "Unhoistable instruction type");
1476  assert(DT.getNode(I->getParent()) && "DT must contain I's block");
1477  assert(DT.getNode(HoistPoint->getParent()) &&
1478  "DT must contain HoistPoint block");
1479  if (DT.dominates(I, HoistPoint))
1480  // We are already above the hoist point. Stop here. This may be necessary
1481  // when multiple scopes would independently hoist the same
1482  // instruction. Since an outer (dominating) scope would hoist it to its
1483  // entry before an inner (dominated) scope would to its entry, the inner
1484  // scope may see the instruction already hoisted, in which case it
1485  // potentially wrong for the inner scope to hoist it and could cause bad
1486  // IR (non-dominating def), but safe to skip hoisting it instead because
1487  // it's already in a block that dominates the inner scope.
1488  return;
1489  for (Value *Op : I->operands()) {
1490  hoistValue(Op, HoistPoint, R, HoistStopMap, HoistedSet, TrivialPHIs, DT);
1491  }
1492  I->moveBefore(HoistPoint);
1493  HoistedSet.insert(I);
1494  CHR_DEBUG(dbgs() << "hoistValue " << *I << "\n");
1495  }
1496 }
1497 
1498 // Hoist the dependent condition values of the branches and the selects in the
1499 // scope to the insert point.
1500 static void hoistScopeConditions(CHRScope *Scope, Instruction *HoistPoint,
1501  DenseSet<PHINode *> &TrivialPHIs,
1502  DominatorTree &DT) {
1503  DenseSet<Instruction *> HoistedSet;
1504  for (const RegInfo &RI : Scope->CHRRegions) {
1505  Region *R = RI.R;
1506  bool IsTrueBiased = Scope->TrueBiasedRegions.count(R);
1507  bool IsFalseBiased = Scope->FalseBiasedRegions.count(R);
1508  if (RI.HasBranch && (IsTrueBiased || IsFalseBiased)) {
1509  auto *BI = cast<BranchInst>(R->getEntry()->getTerminator());
1510  hoistValue(BI->getCondition(), HoistPoint, R, Scope->HoistStopMap,
1511  HoistedSet, TrivialPHIs, DT);
1512  }
1513  for (SelectInst *SI : RI.Selects) {
1514  bool IsTrueBiased = Scope->TrueBiasedSelects.count(SI);
1515  bool IsFalseBiased = Scope->FalseBiasedSelects.count(SI);
1516  if (!(IsTrueBiased || IsFalseBiased))
1517  continue;
1518  hoistValue(SI->getCondition(), HoistPoint, R, Scope->HoistStopMap,
1519  HoistedSet, TrivialPHIs, DT);
1520  }
1521  }
1522 }
1523 
1524 // Negate the predicate if an ICmp if it's used only by branches or selects by
1525 // swapping the operands of the branches or the selects. Returns true if success.
1527  Instruction *ExcludedUser,
1528  CHRScope *Scope) {
1529  for (User *U : ICmp->users()) {
1530  if (U == ExcludedUser)
1531  continue;
1532  if (isa<BranchInst>(U) && cast<BranchInst>(U)->isConditional())
1533  continue;
1534  if (isa<SelectInst>(U) && cast<SelectInst>(U)->getCondition() == ICmp)
1535  continue;
1536  return false;
1537  }
1538  for (User *U : ICmp->users()) {
1539  if (U == ExcludedUser)
1540  continue;
1541  if (auto *BI = dyn_cast<BranchInst>(U)) {
1542  assert(BI->isConditional() && "Must be conditional");
1543  BI->swapSuccessors();
1544  // Don't need to swap this in terms of
1545  // TrueBiasedRegions/FalseBiasedRegions because true-based/false-based
1546  // mean whehter the branch is likely go into the if-then rather than
1547  // successor0/successor1 and because we can tell which edge is the then or
1548  // the else one by comparing the destination to the region exit block.
1549  continue;
1550  }
1551  if (auto *SI = dyn_cast<SelectInst>(U)) {
1552  // Swap operands
1553  SI->swapValues();
1554  SI->swapProfMetadata();
1555  if (Scope->TrueBiasedSelects.count(SI)) {
1556  assert(Scope->FalseBiasedSelects.count(SI) == 0 &&
1557  "Must not be already in");
1558  Scope->FalseBiasedSelects.insert(SI);
1559  } else if (Scope->FalseBiasedSelects.count(SI)) {
1560  assert(Scope->TrueBiasedSelects.count(SI) == 0 &&
1561  "Must not be already in");
1562  Scope->TrueBiasedSelects.insert(SI);
1563  }
1564  continue;
1565  }
1566  llvm_unreachable("Must be a branch or a select");
1567  }
1568  ICmp->setPredicate(CmpInst::getInversePredicate(ICmp->getPredicate()));
1569  return true;
1570 }
1571 
1572 // A helper for transformScopes. Insert a trivial phi at the scope exit block
1573 // for a value that's defined in the scope but used outside it (meaning it's
1574 // alive at the exit block).
1575 static void insertTrivialPHIs(CHRScope *Scope,
1576  BasicBlock *EntryBlock, BasicBlock *ExitBlock,
1577  DenseSet<PHINode *> &TrivialPHIs) {
1578  SmallSetVector<BasicBlock *, 8> BlocksInScope;
1579  for (RegInfo &RI : Scope->RegInfos) {
1580  for (BasicBlock *BB : RI.R->blocks()) { // This includes the blocks in the
1581  // sub-Scopes.
1582  BlocksInScope.insert(BB);
1583  }
1584  }
1585  CHR_DEBUG({
1586  dbgs() << "Inserting redundant phis\n";
1587  for (BasicBlock *BB : BlocksInScope)
1588  dbgs() << "BlockInScope " << BB->getName() << "\n";
1589  });
1590  for (BasicBlock *BB : BlocksInScope) {
1591  for (Instruction &I : *BB) {
1593  for (User *U : I.users()) {
1594  if (auto *UI = dyn_cast<Instruction>(U)) {
1595  if (BlocksInScope.count(UI->getParent()) == 0 &&
1596  // Unless there's already a phi for I at the exit block.
1597  !(isa<PHINode>(UI) && UI->getParent() == ExitBlock)) {
1598  CHR_DEBUG(dbgs() << "V " << I << "\n");
1599  CHR_DEBUG(dbgs() << "Used outside scope by user " << *UI << "\n");
1600  Users.push_back(UI);
1601  } else if (UI->getParent() == EntryBlock && isa<PHINode>(UI)) {
1602  // There's a loop backedge from a block that's dominated by this
1603  // scope to the entry block.
1604  CHR_DEBUG(dbgs() << "V " << I << "\n");
1605  CHR_DEBUG(dbgs()
1606  << "Used at entry block (for a back edge) by a phi user "
1607  << *UI << "\n");
1608  Users.push_back(UI);
1609  }
1610  }
1611  }
1612  if (Users.size() > 0) {
1613  // Insert a trivial phi for I (phi [&I, P0], [&I, P1], ...) at
1614  // ExitBlock. Replace I with the new phi in UI unless UI is another
1615  // phi at ExitBlock.
1616  PHINode *PN = PHINode::Create(I.getType(), pred_size(ExitBlock), "",
1617  &ExitBlock->front());
1618  for (BasicBlock *Pred : predecessors(ExitBlock)) {
1619  PN->addIncoming(&I, Pred);
1620  }
1621  TrivialPHIs.insert(PN);
1622  CHR_DEBUG(dbgs() << "Insert phi " << *PN << "\n");
1623  for (Instruction *UI : Users) {
1624  for (unsigned J = 0, NumOps = UI->getNumOperands(); J < NumOps; ++J) {
1625  if (UI->getOperand(J) == &I) {
1626  UI->setOperand(J, PN);
1627  }
1628  }
1629  CHR_DEBUG(dbgs() << "Updated user " << *UI << "\n");
1630  }
1631  }
1632  }
1633  }
1634 }
1635 
1636 // Assert that all the CHR regions of the scope have a biased branch or select.
1637 static void LLVM_ATTRIBUTE_UNUSED
1639 #ifndef NDEBUG
1640  auto HasBiasedBranchOrSelect = [](RegInfo &RI, CHRScope *Scope) {
1641  if (Scope->TrueBiasedRegions.count(RI.R) ||
1642  Scope->FalseBiasedRegions.count(RI.R))
1643  return true;
1644  for (SelectInst *SI : RI.Selects)
1645  if (Scope->TrueBiasedSelects.count(SI) ||
1646  Scope->FalseBiasedSelects.count(SI))
1647  return true;
1648  return false;
1649  };
1650  for (RegInfo &RI : Scope->CHRRegions) {
1651  assert(HasBiasedBranchOrSelect(RI, Scope) &&
1652  "Must have biased branch or select");
1653  }
1654 #endif
1655 }
1656 
1657 // Assert that all the condition values of the biased branches and selects have
1658 // been hoisted to the pre-entry block or outside of the scope.
1660  CHRScope *Scope, BasicBlock *PreEntryBlock) {
1661  CHR_DEBUG(dbgs() << "Biased regions condition values \n");
1662  for (RegInfo &RI : Scope->CHRRegions) {
1663  Region *R = RI.R;
1664  bool IsTrueBiased = Scope->TrueBiasedRegions.count(R);
1665  bool IsFalseBiased = Scope->FalseBiasedRegions.count(R);
1666  if (RI.HasBranch && (IsTrueBiased || IsFalseBiased)) {
1667  auto *BI = cast<BranchInst>(R->getEntry()->getTerminator());
1668  Value *V = BI->getCondition();
1669  CHR_DEBUG(dbgs() << *V << "\n");
1670  if (auto *I = dyn_cast<Instruction>(V)) {
1671  (void)(I); // Unused in release build.
1672  assert((I->getParent() == PreEntryBlock ||
1673  !Scope->contains(I)) &&
1674  "Must have been hoisted to PreEntryBlock or outside the scope");
1675  }
1676  }
1677  for (SelectInst *SI : RI.Selects) {
1678  bool IsTrueBiased = Scope->TrueBiasedSelects.count(SI);
1679  bool IsFalseBiased = Scope->FalseBiasedSelects.count(SI);
1680  if (!(IsTrueBiased || IsFalseBiased))
1681  continue;
1682  Value *V = SI->getCondition();
1683  CHR_DEBUG(dbgs() << *V << "\n");
1684  if (auto *I = dyn_cast<Instruction>(V)) {
1685  (void)(I); // Unused in release build.
1686  assert((I->getParent() == PreEntryBlock ||
1687  !Scope->contains(I)) &&
1688  "Must have been hoisted to PreEntryBlock or outside the scope");
1689  }
1690  }
1691  }
1692 }
1693 
1694 void CHR::transformScopes(CHRScope *Scope, DenseSet<PHINode *> &TrivialPHIs) {
1695  CHR_DEBUG(dbgs() << "transformScopes " << *Scope << "\n");
1696 
1697  assert(Scope->RegInfos.size() >= 1 && "Should have at least one Region");
1698  Region *FirstRegion = Scope->RegInfos[0].R;
1699  BasicBlock *EntryBlock = FirstRegion->getEntry();
1700  Region *LastRegion = Scope->RegInfos[Scope->RegInfos.size() - 1].R;
1701  BasicBlock *ExitBlock = LastRegion->getExit();
1702  Optional<uint64_t> ProfileCount = BFI.getBlockProfileCount(EntryBlock);
1703 
1704  if (ExitBlock) {
1705  // Insert a trivial phi at the exit block (where the CHR hot path and the
1706  // cold path merges) for a value that's defined in the scope but used
1707  // outside it (meaning it's alive at the exit block). We will add the
1708  // incoming values for the CHR cold paths to it below. Without this, we'd
1709  // miss updating phi's for such values unless there happens to already be a
1710  // phi for that value there.
1711  insertTrivialPHIs(Scope, EntryBlock, ExitBlock, TrivialPHIs);
1712  }
1713 
1714  // Split the entry block of the first region. The new block becomes the new
1715  // entry block of the first region. The old entry block becomes the block to
1716  // insert the CHR branch into. Note DT gets updated. Since DT gets updated
1717  // through the split, we update the entry of the first region after the split,
1718  // and Region only points to the entry and the exit blocks, rather than
1719  // keeping everything in a list or set, the blocks membership and the
1720  // entry/exit blocks of the region are still valid after the split.
1721  CHR_DEBUG(dbgs() << "Splitting entry block " << EntryBlock->getName()
1722  << " at " << *Scope->BranchInsertPoint << "\n");
1723  BasicBlock *NewEntryBlock =
1724  SplitBlock(EntryBlock, Scope->BranchInsertPoint, &DT);
1725  assert(NewEntryBlock->getSinglePredecessor() == EntryBlock &&
1726  "NewEntryBlock's only pred must be EntryBlock");
1727  FirstRegion->replaceEntryRecursive(NewEntryBlock);
1728  BasicBlock *PreEntryBlock = EntryBlock;
1729 
1730  ValueToValueMapTy VMap;
1731  // Clone the blocks in the scope (excluding the PreEntryBlock) to split into a
1732  // hot path (originals) and a cold path (clones) and update the PHIs at the
1733  // exit block.
1734  cloneScopeBlocks(Scope, PreEntryBlock, ExitBlock, LastRegion, VMap);
1735 
1736  // Replace the old (placeholder) branch with the new (merged) conditional
1737  // branch.
1738  BranchInst *MergedBr = createMergedBranch(PreEntryBlock, EntryBlock,
1739  NewEntryBlock, VMap);
1740 
1741 #ifndef NDEBUG
1743 #endif
1744 
1745  // Hoist the conditional values of the branches/selects.
1746  hoistScopeConditions(Scope, PreEntryBlock->getTerminator(), TrivialPHIs, DT);
1747 
1748 #ifndef NDEBUG
1750 #endif
1751 
1752  // Create the combined branch condition and constant-fold the branches/selects
1753  // in the hot path.
1754  fixupBranchesAndSelects(Scope, PreEntryBlock, MergedBr,
1755  ProfileCount ? ProfileCount.getValue() : 0);
1756 }
1757 
1758 // A helper for transformScopes. Clone the blocks in the scope (excluding the
1759 // PreEntryBlock) to split into a hot path and a cold path and update the PHIs
1760 // at the exit block.
1761 void CHR::cloneScopeBlocks(CHRScope *Scope,
1762  BasicBlock *PreEntryBlock,
1763  BasicBlock *ExitBlock,
1764  Region *LastRegion,
1765  ValueToValueMapTy &VMap) {
1766  // Clone all the blocks. The original blocks will be the hot-path
1767  // CHR-optimized code and the cloned blocks will be the original unoptimized
1768  // code. This is so that the block pointers from the
1769  // CHRScope/Region/RegionInfo can stay valid in pointing to the hot-path code
1770  // which CHR should apply to.
1771  SmallVector<BasicBlock*, 8> NewBlocks;
1772  for (RegInfo &RI : Scope->RegInfos)
1773  for (BasicBlock *BB : RI.R->blocks()) { // This includes the blocks in the
1774  // sub-Scopes.
1775  assert(BB != PreEntryBlock && "Don't copy the preetntry block");
1776  BasicBlock *NewBB = CloneBasicBlock(BB, VMap, ".nonchr", &F);
1777  NewBlocks.push_back(NewBB);
1778  VMap[BB] = NewBB;
1779  }
1780 
1781  // Place the cloned blocks right after the original blocks (right before the
1782  // exit block of.)
1783  if (ExitBlock)
1784  F.getBasicBlockList().splice(ExitBlock->getIterator(),
1785  F.getBasicBlockList(),
1786  NewBlocks[0]->getIterator(), F.end());
1787 
1788  // Update the cloned blocks/instructions to refer to themselves.
1789  for (unsigned i = 0, e = NewBlocks.size(); i != e; ++i)
1790  for (Instruction &I : *NewBlocks[i])
1791  RemapInstruction(&I, VMap,
1793 
1794  // Add the cloned blocks to the PHIs of the exit blocks. ExitBlock is null for
1795  // the top-level region but we don't need to add PHIs. The trivial PHIs
1796  // inserted above will be updated here.
1797  if (ExitBlock)
1798  for (PHINode &PN : ExitBlock->phis())
1799  for (unsigned I = 0, NumOps = PN.getNumIncomingValues(); I < NumOps;
1800  ++I) {
1801  BasicBlock *Pred = PN.getIncomingBlock(I);
1802  if (LastRegion->contains(Pred)) {
1803  Value *V = PN.getIncomingValue(I);
1804  auto It = VMap.find(V);
1805  if (It != VMap.end()) V = It->second;
1806  assert(VMap.find(Pred) != VMap.end() && "Pred must have been cloned");
1807  PN.addIncoming(V, cast<BasicBlock>(VMap[Pred]));
1808  }
1809  }
1810 }
1811 
1812 // A helper for transformScope. Replace the old (placeholder) branch with the
1813 // new (merged) conditional branch.
1814 BranchInst *CHR::createMergedBranch(BasicBlock *PreEntryBlock,
1815  BasicBlock *EntryBlock,
1816  BasicBlock *NewEntryBlock,
1817  ValueToValueMapTy &VMap) {
1818  BranchInst *OldBR = cast<BranchInst>(PreEntryBlock->getTerminator());
1819  assert(OldBR->isUnconditional() && OldBR->getSuccessor(0) == NewEntryBlock &&
1820  "SplitBlock did not work correctly!");
1821  assert(NewEntryBlock->getSinglePredecessor() == EntryBlock &&
1822  "NewEntryBlock's only pred must be EntryBlock");
1823  assert(VMap.find(NewEntryBlock) != VMap.end() &&
1824  "NewEntryBlock must have been copied");
1825  OldBR->dropAllReferences();
1826  OldBR->eraseFromParent();
1827  // The true predicate is a placeholder. It will be replaced later in
1828  // fixupBranchesAndSelects().
1829  BranchInst *NewBR = BranchInst::Create(NewEntryBlock,
1830  cast<BasicBlock>(VMap[NewEntryBlock]),
1831  ConstantInt::getTrue(F.getContext()));
1832  PreEntryBlock->getInstList().push_back(NewBR);
1833  assert(NewEntryBlock->getSinglePredecessor() == EntryBlock &&
1834  "NewEntryBlock's only pred must be EntryBlock");
1835  return NewBR;
1836 }
1837 
1838 // A helper for transformScopes. Create the combined branch condition and
1839 // constant-fold the branches/selects in the hot path.
1840 void CHR::fixupBranchesAndSelects(CHRScope *Scope,
1841  BasicBlock *PreEntryBlock,
1842  BranchInst *MergedBR,
1844  Value *MergedCondition = ConstantInt::getTrue(F.getContext());
1845  BranchProbability CHRBranchBias(1, 1);
1846  uint64_t NumCHRedBranches = 0;
1847  IRBuilder<> IRB(PreEntryBlock->getTerminator());
1848  for (RegInfo &RI : Scope->CHRRegions) {
1849  Region *R = RI.R;
1850  if (RI.HasBranch) {
1851  fixupBranch(R, Scope, IRB, MergedCondition, CHRBranchBias);
1852  ++NumCHRedBranches;
1853  }
1854  for (SelectInst *SI : RI.Selects) {
1855  fixupSelect(SI, Scope, IRB, MergedCondition, CHRBranchBias);
1856  ++NumCHRedBranches;
1857  }
1858  }
1859  Stats.NumBranchesDelta += NumCHRedBranches - 1;
1860  Stats.WeightedNumBranchesDelta += (NumCHRedBranches - 1) * ProfileCount;
1861  ORE.emit([&]() {
1863  "CHR",
1864  // Refer to the hot (original) path
1865  MergedBR->getSuccessor(0)->getTerminator())
1866  << "Merged " << ore::NV("NumCHRedBranches", NumCHRedBranches)
1867  << " branches or selects";
1868  });
1869  MergedBR->setCondition(MergedCondition);
1870  uint32_t Weights[] = {
1871  static_cast<uint32_t>(CHRBranchBias.scale(1000)),
1872  static_cast<uint32_t>(CHRBranchBias.getCompl().scale(1000)),
1873  };
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,
2096  auto &DT = FAM.getResult<DominatorTreeAnalysis>(F);
2098  auto &PSI = *MAMProxy.getCachedResult<ProfileSummaryAnalysis>(*F.getParent());
2099  auto &RI = FAM.getResult<RegionInfoAnalysis>(F);
2101  bool Changed = CHR(F, BFI, DT, PSI, RI, ORE).run();
2102  if (!Changed)
2103  return PreservedAnalyses::all();
2104  return PreservedAnalyses::none();
2105 }
2106 
2107 } // namespace llvm
i
i
Definition: README.txt:29
RegionInfo.h
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
MemoryBuffer.h
llvm::OuterAnalysisManagerProxy
An analysis over an "inner" IR unit that provides access to an analysis manager over a "outer" IR uni...
Definition: PassManager.h:1061
llvm::OptimizationRemarkMissed
Diagnostic information for missed-optimization remarks.
Definition: DiagnosticInfo.h:730
llvm::predecessors
pred_range predecessors(BasicBlock *BB)
Definition: CFG.h:127
getSelectsInScope
static void getSelectsInScope(CHRScope *Scope, DenseSet< Instruction * > &Output)
Definition: ControlHeightReduction.cpp:1125
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
M
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
Definition: README.txt:252
it
into xmm2 addss xmm2 xmm1 xmm3 addss xmm3 movaps xmm0 unpcklps xmm0 ret seems silly when it could just be one addps Expand libm rounding functions main should enable SSE DAZ mode and other fast SSE modes Think about doing i64 math in SSE regs on x86 This testcase should have no SSE instructions in it
Definition: README-SSE.txt:81
CHRMergeThreshold
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"))
ValueMapper.h
print
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
Definition: ArchiveWriter.cpp:147
llvm::isSafeToSpeculativelyExecute
bool isSafeToSpeculativelyExecute(const Value *V, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr)
Return true if the instruction does not have any effects besides calculating the result and does not ...
Definition: ValueTracking.cpp:4589
CHRModules
static StringSet CHRModules
Definition: ControlHeightReduction.cpp:68
llvm::AnalysisManager::getResult
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:779
llvm::ValueMap::end
iterator end()
Definition: ValueMap.h:136
llvm::Function
Definition: Function.h:61
llvm::BlockFrequencyInfoWrapperPass
Legacy analysis pass which computes BlockFrequencyInfo.
Definition: BlockFrequencyInfo.h:138
llvm::ProfileSummaryInfo::hasProfileSummary
bool hasProfileSummary() const
Returns true if profile summary is available.
Definition: ProfileSummaryInfo.h:68
contains
return AArch64::GPR64RegClass contains(Reg)
llvm::IRBuilderBase::CreateXor
Value * CreateXor(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:1414
llvm::ConstantInt::getValue
const APInt & getValue() const
Return the constant as an APInt value reference.
Definition: Constants.h:133
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
llvm::ProfileSummaryInfo::isFunctionEntryHot
bool isFunctionEntryHot(const Function *F) const
Returns true if F has hot function entry.
Definition: ProfileSummaryInfo.cpp:99
llvm::User::dropAllReferences
void dropAllReferences()
Drop all references to operands.
Definition: User.h:299
CHRFunctions
static StringSet CHRFunctions
Definition: ControlHeightReduction.cpp:69
getBaseValues
static const std::set< Value * > & getBaseValues(Value *V, DominatorTree &DT, DenseMap< Value *, std::set< Value * >> &Visited)
Definition: ControlHeightReduction.cpp:514
llvm::IRBuilder<>
llvm::erase_if
void erase_if(Container &C, UnaryPredicate P)
Provide a container algorithm similar to C++ Library Fundamentals v2's erase_if which is equivalent t...
Definition: STLExtras.h:1728
checkBiasedSelect
static bool checkBiasedSelect(SelectInst *SI, Region *R, DenseSet< SelectInst * > &TrueBiasedSelectsGlobal, DenseSet< SelectInst * > &FalseBiasedSelectsGlobal, DenseMap< SelectInst *, BranchProbability > &SelectBiasMap)
Definition: ControlHeightReduction.cpp:690
ValueTracking.h
OptimizationRemarkEmitter.h
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:151
FAM
FunctionAnalysisManager FAM
Definition: PassBuilderBindings.cpp:59
llvm::ControlHeightReductionPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &FAM)
Definition: ControlHeightReduction.cpp:2092
GlobalsModRef.h
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:143
llvm::PreservedAnalyses::none
static PreservedAnalyses none()
Convenience factory function for the empty preserved set.
Definition: PassManager.h:158
hasAtLeastTwoBiasedBranches
static bool hasAtLeastTwoBiasedBranches(CHRScope *Scope)
Definition: ControlHeightReduction.cpp:1334
DenseMap.h
llvm::sys::path::end
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:233
llvm::sys::path::begin
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:224
llvm::copy
OutputIt copy(R &&Range, OutputIt Out)
Definition: STLExtras.h:1598
llvm::DominatorTreeBase::getNode
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
Definition: GenericDomTree.h:351
llvm::Optional< uint64_t >
llvm::ore::NV
DiagnosticInfoOptimizationBase::Argument NV
Definition: OptimizationRemarkEmitter.h:136
llvm::errs
raw_fd_ostream & errs()
This returns a reference to a raw_ostream for standard error.
Definition: raw_ostream.cpp:892
llvm::StringSet::insert
std::pair< typename Base::iterator, bool > insert(StringRef key)
Definition: StringSet.h:33
llvm::BasicBlock::getSinglePredecessor
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
Definition: BasicBlock.cpp:264
LLVM_ATTRIBUTE_UNUSED
#define LLVM_ATTRIBUTE_UNUSED
Definition: Compiler.h:188
getBranchInsertPoint
static Instruction * getBranchInsertPoint(RegInfo &RI)
Definition: ControlHeightReduction.cpp:710
llvm::detail::DenseSetImpl< ValueT, DenseMap< ValueT, detail::DenseSetEmpty, DenseMapInfo< ValueT >, detail::DenseSetPair< ValueT > >, DenseMapInfo< ValueT > >::insert
std::pair< iterator, bool > insert(const ValueT &V)
Definition: DenseSet.h:206
llvm::detail::DenseSetImpl< ValueT, DenseMap< ValueT, detail::DenseSetEmpty, DenseMapInfo< ValueT >, detail::DenseSetPair< ValueT > >, DenseMapInfo< ValueT > >::count
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:97
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::RISCVFenceField::R
@ R
Definition: RISCVBaseInfo.h:193
llvm::Instruction::setMetadata
void setMetadata(unsigned KindID, MDNode *Node)
Set the metadata of the specified kind to the specified node.
Definition: Metadata.cpp:1336
llvm::createControlHeightReductionLegacyPass
FunctionPass * createControlHeightReductionLegacyPass()
Definition: ControlHeightReduction.cpp:141
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
llvm::MDNode::getNumOperands
unsigned getNumOperands() const
Return number of MDNode operands.
Definition: Metadata.h:1113
llvm::sys::path::append
void append(SmallVectorImpl< char > &path, const Twine &a, const Twine &b="", const Twine &c="", const Twine &d="")
Append to path.
Definition: Path.cpp:454
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::DominatorTree::dominates
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
Definition: Dominators.cpp:115
llvm::detail::DenseSetImpl< ValueT, DenseMap< ValueT, detail::DenseSetEmpty, DenseMapInfo< ValueT >, detail::DenseSetPair< ValueT > >, DenseMapInfo< ValueT > >::end
iterator end()
Definition: DenseSet.h:174
hoistValue
static void hoistValue(Value *V, Instruction *HoistPoint, Region *R, HoistStopMapTy &HoistStopMap, DenseSet< Instruction * > &HoistedSet, DenseSet< PHINode * > &TrivialPHIs, DominatorTree &DT)
Definition: ControlHeightReduction.cpp:1452
CommandLine.h
llvm::ConstantInt
This is the shared class of boolean and integer constants.
Definition: Constants.h:79
llvm::BlockFrequencyInfo
BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...
Definition: BlockFrequencyInfo.h:37
llvm::MemoryBuffer::getFile
static ErrorOr< std::unique_ptr< MemoryBuffer > > getFile(const Twine &Filename, bool IsText=false, bool RequiresNullTerminator=true, bool IsVolatile=false)
Open the specified file as a MemoryBuffer, returning a new MemoryBuffer if successful,...
Definition: MemoryBuffer.cpp:246
llvm::RemapInstruction
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:253
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:31
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::RegionInfoAnalysis
Analysis pass that exposes the RegionInfo for a function.
Definition: RegionInfo.h:967
llvm::StringRef::split
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:749
llvm::User
Definition: User.h:44
hoistScopeConditions
static void hoistScopeConditions(CHRScope *Scope, Instruction *HoistPoint, DenseSet< PHINode * > &TrivialPHIs, DominatorTree &DT)
Definition: ControlHeightReduction.cpp:1500
paths
Reduce control height in the hot paths
Definition: ControlHeightReduction.cpp:138
checkBiasedBranch
static bool checkBiasedBranch(BranchInst *BI, Region *R, DenseSet< Region * > &TrueBiasedRegionsGlobal, DenseSet< Region * > &FalseBiasedRegionsGlobal, DenseMap< Region *, BranchProbability > &BranchBiasMap)
Definition: ControlHeightReduction.cpp:659
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
llvm::ms_demangle::QualifierMangleMode::Result
@ Result
llvm::AMDGPU::PALMD::Key
Key
PAL metadata keys.
Definition: AMDGPUMetadata.h:481
DenseSet.h
false
Definition: StackSlotColoring.cpp:142
in
The object format emitted by the WebAssembly backed is documented in
Definition: README.txt:11
llvm::Instruction
Definition: Instruction.h:45
llvm::BranchInst::setCondition
void setCondition(Value *V)
Definition: Instructions.h:3146
llvm::DominatorTreeWrapperPass
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:287
MDBuilder.h
llvm::APInt::getZExtValue
uint64_t getZExtValue() const
Get zero extended value.
Definition: APInt.h:1453
llvm::BasicBlock::phis
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
Definition: BasicBlock.h:354
operator<<
static raw_ostream LLVM_ATTRIBUTE_UNUSED & operator<<(raw_ostream &OS, const CHRStats &Stats)
Definition: ControlHeightReduction.cpp:427
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:53
dumpIR
static void LLVM_ATTRIBUTE_UNUSED dumpIR(Function &F, const char *Label, CHRStats *Stats)
Definition: ControlHeightReduction.cpp:453
llvm::SmallVectorImpl::resize
void resize(size_type N)
Definition: SmallVector.h:606
negateICmpIfUsedByBranchOrSelectOnly
static bool negateICmpIfUsedByBranchOrSelectOnly(ICmpInst *ICmp, Instruction *ExcludedUser, CHRScope *Scope)
Definition: ControlHeightReduction.cpp:1526
Utils.h
llvm::BlockFrequencyAnalysis
Analysis pass which computes BlockFrequencyInfo.
Definition: BlockFrequencyInfo.h:112
parseCHRFilterFiles
static void parseCHRFilterFiles()
Definition: ControlHeightReduction.cpp:71
llvm::RF_NoModuleLevelChanges
@ RF_NoModuleLevelChanges
If this flag is set, the remapper knows that only local values within a function (such as an instruct...
Definition: ValueMapper.h:72
llvm::IRBuilderBase::CreateAnd
Value * CreateAnd(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:1362
BranchProbability.h
ControlHeightReduction.h
llvm::Instruction::getMetadata
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
Definition: Instruction.h:282
isHoistable
static bool isHoistable(Instruction *I, DominatorTree &DT)
Definition: ControlHeightReduction.cpp:502
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
CFG.h
llvm::RegionNode
Definition: RegionInfo.h:879
llvm::ProfileSummaryInfo
Analysis providing profile information.
Definition: ProfileSummaryInfo.h:39
checkBias
static bool checkBias(K *Key, BranchProbability TrueProb, BranchProbability FalseProb, S &TrueSet, S &FalseSet, M &BiasMap)
Definition: ControlHeightReduction.cpp:641
llvm::MDNode::getOperand
const MDOperand & getOperand(unsigned I) const
Definition: Metadata.h:1107
llvm::DenseSet
Implements a dense probed hash-table based set.
Definition: DenseSet.h:268
insertTrivialPHIs
static void insertTrivialPHIs(CHRScope *Scope, BasicBlock *EntryBlock, BasicBlock *ExitBlock, DenseSet< PHINode * > &TrivialPHIs)
Definition: ControlHeightReduction.cpp:1575
llvm::CloneBasicBlock
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...
Definition: CloneFunction.cpp:43
llvm::cl::opt< bool >
llvm::Instruction::eraseFromParent
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:78
llvm::ICmpInst
This instruction compares its operands according to the predicate given to the constructor.
Definition: Instructions.h:1203
uint64_t
ProfileSummaryInfo.h
llvm::RegionBase::getEntry
BlockT * getEntry() const
Get the entry BasicBlock of the Region.
Definition: RegionInfo.h:322
CHRScopeSorter
static bool CHRScopeSorter(CHRScope *Scope1, CHRScope *Scope2)
Definition: ControlHeightReduction.cpp:1439
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
llvm::PHINode::addIncoming
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
Definition: Instructions.h:2775
shouldSplit
static bool shouldSplit(Instruction *InsertPoint, DenseSet< Value * > &PrevConditionValues, DenseSet< Value * > &ConditionValues, DominatorTree &DT, DenseSet< Instruction * > &Unhoistables)
Definition: ControlHeightReduction.cpp:1063
move
compiles ldr LCPI1_0 ldr ldr mov lsr tst moveq r1 ldr LCPI1_1 and r0 bx lr It would be better to do something like to fold the shift into the conditional move
Definition: README.txt:546
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:57
llvm::DenseMap
Definition: DenseMap.h:714
I
#define I(x, y, z)
Definition: MD5.cpp:59
Cloning.h
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:443
checkHoistValue
static bool checkHoistValue(Value *V, Instruction *InsertPoint, DominatorTree &DT, DenseSet< Instruction * > &Unhoistables, DenseSet< Instruction * > *HoistStops, DenseMap< Instruction *, bool > &Visited)
Definition: ControlHeightReduction.cpp:550
llvm::ProfileSummaryInfoWrapperPass
An analysis pass based on legacy pass manager to deliver ProfileSummaryInfo.
Definition: ProfileSummaryInfo.h:185
assertBranchOrSelectConditionHoisted
static void LLVM_ATTRIBUTE_UNUSED assertBranchOrSelectConditionHoisted(CHRScope *Scope, BasicBlock *PreEntryBlock)
Definition: ControlHeightReduction.cpp:1659
llvm::detail::DenseSetImpl< ValueT, DenseMap< ValueT, detail::DenseSetEmpty, DenseMapInfo< ValueT >, detail::DenseSetPair< ValueT > >, DenseMapInfo< ValueT > >::begin
iterator begin()
Definition: DenseSet.h:173
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::find
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:150
IRBuilder.h
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
ForceCHR
static cl::opt< bool > ForceCHR("force-chr", cl::init(false), cl::Hidden, cl::desc("Apply CHR for all functions"))
RegionIterator.h
std::swap
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:840
getFalse
static Constant * getFalse(Type *Ty)
For a boolean type or a vector of boolean type, return false or a vector with every element false.
Definition: InstructionSimplify.cpp:122
SI
StandardInstrumentations SI(Debug, VerifyEach)
llvm::SelectInst
This class represents the LLVM 'select' instruction.
Definition: Instructions.h:1738
llvm::ControlHeightReductionPass::ControlHeightReductionPass
ControlHeightReductionPass()
Definition: ControlHeightReduction.cpp:2088
llvm::MDNode
Metadata node.
Definition: Metadata.h:901
llvm::BranchInst::isUnconditional
bool isUnconditional() const
Definition: Instructions.h:3138
llvm::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::insert
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:141
llvm::detail::DenseSetImpl< ValueT, DenseMap< ValueT, detail::DenseSetEmpty, DenseMapInfo< ValueT >, detail::DenseSetPair< ValueT > >, DenseMapInfo< ValueT > >::clear
void clear()
Definition: DenseSet.h:92
llvm::RegionInfoPass
Definition: RegionInfo.h:942
llvm::ProfileSummaryAnalysis
An analysis pass based on the new PM to deliver ProfileSummaryInfo.
Definition: ProfileSummaryInfo.h:203
llvm::StringSet
StringSet - A wrapper for StringMap that provides set-like functionality.
Definition: StringSet.h:22
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
IT
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")))
llvm::OptimizationRemarkEmitter
The optimization diagnostic interface.
Definition: OptimizationRemarkEmitter.h:33
llvm::OptimizationRemarkEmitterAnalysis::run
Result run(Function &F, FunctionAnalysisManager &AM)
Run the analysis pass over a function and produce BFI.
Definition: OptimizationRemarkEmitter.cpp:127
Cond
SmallVector< MachineOperand, 4 > Cond
Definition: BasicBlockSections.cpp:179
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:58
llvm::CallingConv::Tail
@ Tail
Tail - This calling convention attemps to make calls as fast as possible while guaranteeing that tail...
Definition: CallingConv.h:81
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:136
llvm::pred_size
unsigned pred_size(const BasicBlock *BB)
Get the number of predecessors of BB.
Definition: CFG.h:124
llvm::AnalysisUsage::addPreserved
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
Definition: PassAnalysisSupport.h:98
llvm::detail::DenseSetImpl< ValueT, DenseMap< ValueT, detail::DenseSetEmpty, DenseMapInfo< ValueT >, detail::DenseSetPair< ValueT > >, DenseMapInfo< ValueT > >::contains
bool contains(const_arg_type_t< ValueT > V) const
Check if the set contains the given element.
Definition: DenseSet.h:185
uint32_t
llvm::BranchProbability
Definition: BranchProbability.h:30
llvm::append_range
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
Definition: STLExtras.h:1744
llvm::ilist_node_impl::getIterator
self_iterator getIterator()
Definition: ilist_node.h:81
CHR_DEBUG
#define CHR_DEBUG(X)
Definition: ControlHeightReduction.cpp:47
S
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
Definition: README.txt:210
llvm::RegionInfo
Definition: RegionInfo.h:900
INITIALIZE_PASS_BEGIN
INITIALIZE_PASS_BEGIN(ControlHeightReductionLegacyPass, "chr", "Reduce control height in the hot paths", false, false) INITIALIZE_PASS_END(ControlHeightReductionLegacyPass
chr
chr
Definition: ControlHeightReduction.cpp:137
BlockFrequencyInfo.h
llvm::AMDGPUISD::BFI
@ BFI
Definition: AMDGPUISelLowering.h:421
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:297
llvm::ValueMap< const Value *, WeakTrackingVH >
llvm::BasicBlock::getTerminator
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:148
llvm::find_if
auto find_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1574
llvm::BasicBlock::front
const Instruction & front() const
Definition: BasicBlock.h:308
llvm::RF_IgnoreMissingLocals
@ RF_IgnoreMissingLocals
If this flag is set, the remapper ignores missing function-local entries (Argument,...
Definition: ValueMapper.h:90
StringSet.h
runOnFunction
static bool runOnFunction(Function &F, bool PostInlining)
Definition: EntryExitInstrumenter.cpp:69
llvm::stable_sort
void stable_sort(R &&Range)
Definition: STLExtras.h:1682
getCHRConditionValuesForRegion
static DenseSet< Value * > getCHRConditionValuesForRegion(RegInfo &RI)
Definition: ControlHeightReduction.cpp:1044
split
coro split
Definition: CoroSplit.cpp:2276
CHRModuleList
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"))
Stats
block placement Basic Block Placement Stats
Definition: MachineBlockPlacement.cpp:3465
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::end
iterator end()
Definition: DenseMap.h:83
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:321
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:161
checkMDProf
static bool checkMDProf(MDNode *MD, BranchProbability &TrueProb, BranchProbability &FalseProb)
Definition: ControlHeightReduction.cpp:604
llvm::MCID::Branch
@ Branch
Definition: MCInstrDesc.h:156
PassManager.h
llvm::RegionBase::replaceEntryRecursive
void replaceEntryRecursive(BlockT *NewEntry)
Recursively replace the entry basic block of the region.
Definition: RegionInfoImpl.h:68
CHRBiasThreshold
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"))
llvm::ValueMap::find
iterator find(const KeyT &Val)
Definition: ValueMap.h:156
dumpScopes
static void LLVM_ATTRIBUTE_UNUSED dumpScopes(SmallVectorImpl< CHRScope * > &Scopes, const char *Label)
Definition: ControlHeightReduction.cpp:1990
llvm::RegionBase::contains
bool contains(const BlockT *BB) const
Check if the region contains a BasicBlock.
Definition: RegionInfoImpl.h:104
llvm::StringMap::count
size_type count(StringRef Key) const
count - Return 1 if the element is in the map, 0 otherwise.
Definition: StringMap.h:244
llvm::CmpInst::setPredicate
void setPredicate(Predicate P)
Set the predicate for this instruction to the specified value.
Definition: InstrTypes.h:799
assertCHRRegionsHaveBiasedBranchOrSelect
static void LLVM_ATTRIBUTE_UNUSED assertCHRRegionsHaveBiasedBranchOrSelect(CHRScope *Scope)
Definition: ControlHeightReduction.cpp:1638
llvm::MDBuilder
Definition: MDBuilder.h:35
llvm::DominatorTreeAnalysis
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:252
llvm::BasicBlock::getInstList
const InstListType & getInstList() const
Return the underlying instruction list container.
Definition: BasicBlock.h:363
llvm::OptimizationRemark
Diagnostic information for applied optimization remarks.
Definition: DiagnosticInfo.h:685
getCHRBiasThreshold
static BranchProbability getCHRBiasThreshold()
Definition: ControlHeightReduction.cpp:631
SmallVector.h
exit
declare void exit(i32) noreturn nounwind This compiles into
Definition: README.txt:1072
Dominators.h
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:94
getTrue
static Constant * getTrue(Type *Ty)
For a boolean type or a vector of boolean type, return true or a vector with every element true.
Definition: InstructionSimplify.cpp:128
llvm::CmpInst::getPredicate
Predicate getPredicate() const
Return the predicate for this instruction.
Definition: InstrTypes.h:796
llvm::GlobalsAAWrapperPass
Legacy wrapper pass to provide the GlobalsAAResult object.
Definition: GlobalsModRef.h:143
Users
iv Induction Variable Users
Definition: IVUsers.cpp:52
llvm::PHINode
Definition: Instructions.h:2625
isHoistableInstructionType
static bool isHoistableInstructionType(Instruction *I)
Definition: ControlHeightReduction.cpp:493
Threshold
static cl::opt< unsigned > Threshold("loop-unswitch-threshold", cl::desc("Max loop size to unswitch"), cl::init(100), cl::Hidden)
llvm::detail::DenseSetImpl< ValueT, DenseMap< ValueT, detail::DenseSetEmpty, DenseMapInfo< ValueT >, detail::DenseSetPair< ValueT > >, DenseMapInfo< ValueT > >::erase
bool erase(const ValueT &V)
Definition: DenseSet.h:101
llvm::SmallVectorImpl
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:43
DEBUG_TYPE
#define DEBUG_TYPE
Definition: ControlHeightReduction.cpp:45
llvm::SmallSetVector
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:307
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:44
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:298
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
llvm::Function::ProfileCount
Class to represent profile counts.
Definition: Function.h:254
llvm::cl::desc
Definition: CommandLine.h:414
shouldApply
static bool shouldApply(Function &F, ProfileSummaryInfo &PSI)
Definition: ControlHeightReduction.cpp:439
llvm::Region
Definition: RegionInfo.h:889
llvm::MDString::getString
StringRef getString() const
Definition: Metadata.cpp:483
llvm::BranchInst
Conditional or Unconditional Branch instruction.
Definition: Instructions.h:3060
BasicBlockUtils.h
llvm::MDString
A single uniqued string.
Definition: Metadata.h:611
llvm::SplitBlock
BasicBlock * SplitBlock(BasicBlock *Old, Instruction *SplitPt, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="", bool Before=false)
Split the specified block at the specified instruction.
Definition: BasicBlockUtils.cpp:814
llvm::RegionBase::getExit
BlockT * getExit() const
Get the exit BasicBlock of the Region.
Definition: RegionInfo.h:359
InitializePasses.h
llvm::OptimizationRemarkEmitterAnalysis
Definition: OptimizationRemarkEmitter.h:164
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
llvm::Value::users
iterator_range< user_iterator > users()
Definition: Value.h:422
CHRFunctionList
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"))
llvm::BranchInst::isConditional
bool isConditional() const
Definition: Instructions.h:3139
llvm::BranchInst::getSuccessor
BasicBlock * getSuccessor(unsigned i) const
Definition: Instructions.h:3153
llvm::RegionBase::getParent
RegionT * getParent() const
Get the parent of the Region.
Definition: RegionInfo.h:364
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:37
llvm::SmallVectorImpl::insert
iterator insert(iterator I, T &&Elt)
Definition: SmallVector.h:773
llvm::initializeControlHeightReductionLegacyPassPass
void initializeControlHeightReductionLegacyPassPass(PassRegistry &)