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