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