46 #define DEBUG_TYPE "chr"
48 #define CHR_DEBUG(X) LLVM_DEBUG(X)
51 cl::desc(
"Apply CHR for all functions"));
55 cl::desc(
"CHR considers a branch bias greater than this ratio as biased"));
59 cl::desc(
"CHR merges a group of N branches/selects where N >= this value"));
63 cl::desc(
"Specify file to retrieve the list of modules to apply CHR to"));
67 cl::desc(
"Specify file to retrieve the list of functions to apply CHR to"));
76 errs() <<
"Error: Couldn't read the chr-module-list file " <<
CHRModuleList <<
"\n";
79 StringRef Buf = FileOrErr->get()->getBuffer();
81 Buf.
split(Lines,
'\n');
94 StringRef Buf = FileOrErr->get()->getBuffer();
96 Buf.
split(Lines,
'\n');
106 class ControlHeightReductionLegacyPass :
public FunctionPass {
131 "Reduce control height in the hot paths",
143 return new ControlHeightReductionLegacyPass();
149 CHRStats() =
default;
151 OS <<
"CHRStats: NumBranches " << NumBranches
152 <<
" NumBranchesDelta " << NumBranchesDelta
153 <<
" WeightedNumBranchesDelta " << WeightedNumBranchesDelta;
161 uint64_t WeightedNumBranchesDelta = 0;
167 RegInfo(
Region *RegionIn) :
R(RegionIn) {}
169 bool HasBranch =
false;
180 CHRScope(RegInfo RI) : BranchInsertPoint(nullptr) {
181 assert(RI.R &&
"Null RegionIn");
182 RegInfos.push_back(RI);
185 Region *getParentRegion() {
186 assert(RegInfos.size() > 0 &&
"Empty CHRScope");
188 assert(Parent &&
"Unexpected to call this on the top-level region");
193 assert(RegInfos.size() > 0 &&
"Empty CHRScope");
194 return RegInfos.front().R->getEntry();
198 assert(RegInfos.size() > 0 &&
"Empty CHRScope");
199 return RegInfos.back().R->getExit();
202 bool appendable(CHRScope *Next) {
206 BasicBlock *NextEntry = Next->getEntryBlock();
207 if (getExitBlock() != NextEntry)
210 Region *LastRegion = RegInfos.back().R;
219 void append(CHRScope *Next) {
220 assert(RegInfos.size() > 0 &&
"Empty CHRScope");
221 assert(Next->RegInfos.size() > 0 &&
"Empty CHRScope");
222 assert(getParentRegion() == Next->getParentRegion() &&
224 assert(getExitBlock() == Next->getEntryBlock() &&
226 RegInfos.append(Next->RegInfos.begin(), Next->RegInfos.end());
227 Subs.append(Next->Subs.begin(), Next->Subs.end());
230 void addSub(CHRScope *SubIn) {
232 bool IsChild =
false;
233 for (RegInfo &RI : RegInfos)
234 if (RI.R == SubIn->getParentRegion()) {
238 assert(IsChild &&
"Must be a child");
240 Subs.push_back(SubIn);
246 assert(Boundary &&
"Boundary null");
247 assert(RegInfos.begin()->R != Boundary &&
248 "Can't be split at beginning");
250 RegInfos, [&Boundary](
const RegInfo &RI) {
return Boundary == RI.R; });
251 if (BoundaryIt == RegInfos.end())
255 for (
const RegInfo &RI : TailRegInfos)
256 TailRegionSet.
insert(RI.R);
259 std::stable_partition(Subs.begin(), Subs.end(), [&](CHRScope *Sub) {
260 assert(Sub &&
"null Sub");
261 Region *Parent = Sub->getParentRegion();
262 if (TailRegionSet.count(Parent))
267 [&Parent](const RegInfo &RI) { return Parent == RI.R; }) &&
273 assert(HoistStopMap.empty() &&
"MapHoistStops must be empty");
274 auto *
Scope =
new CHRScope(TailRegInfos, TailSubs);
275 RegInfos.erase(BoundaryIt, RegInfos.end());
276 Subs.erase(TailIt, Subs.end());
282 for (
const RegInfo &RI : RegInfos)
283 if (RI.R->contains(Parent))
312 HoistStopMapTy HoistStopMap;
316 : RegInfos(RegInfosIn.
begin(), RegInfosIn.
end()),
317 Subs(SubsIn.
begin(), SubsIn.
end()), BranchInsertPoint(nullptr) {}
325 :
F(Fin),
BFI(BFIin), DT(DTin), PSI(PSIin), RI(RIin), ORE(OREin) {}
328 for (CHRScope *
Scope : Scopes) {
340 Region *
R = RI.getTopLevelRegion();
341 if (CHRScope *
Scope = findScopes(R,
nullptr,
nullptr, Output)) {
347 CHRScope *findScope(
Region *R);
348 void checkScopeHoistable(CHRScope *
Scope);
360 void classifyBiasedScopes(CHRScope *
Scope, CHRScope *OutermostScope);
367 void setCHRRegions(CHRScope *
Scope, CHRScope *OutermostScope);
374 void cloneScopeBlocks(CHRScope *
Scope,
383 void fixupBranchesAndSelects(CHRScope *
Scope,
387 void fixupBranch(
Region *R,
395 void addToMergedCondition(
bool IsTrueBiased,
Value *
Cond,
399 Value *&MergedCondition);
429 const CHRStats &
Stats) {
469 assert(RegInfos.size() > 0 &&
"Empty CHRScope");
471 OS << RegInfos.size() <<
", Regions[";
472 for (
const RegInfo &RI : RegInfos) {
473 OS << RI.R->getNameStr();
476 if (RI.Selects.size() > 0)
477 OS <<
" S" << RI.Selects.size();
480 if (RegInfos[0].
R->getParent()) {
481 OS <<
"], Parent " << RegInfos[0].R->getParent()->getNameStr();
487 for (CHRScope *Sub : Subs) {
495 return isa<BinaryOperator>(
I) || isa<CastInst>(
I) || isa<SelectInst>(
I) ||
496 isa<GetElementPtrInst>(
I) || isa<CmpInst>(
I) ||
497 isa<InsertElementInst>(
I) || isa<ExtractElementInst>(
I) ||
498 isa<ShuffleVectorInst>(
I) || isa<ExtractValueInst>(
I) ||
499 isa<InsertValueInst>(
I);
514 static const std::set<Value *> &
517 auto It = Visited.find(V);
518 if (It != Visited.end()) {
521 std::set<Value *> Result;
522 if (
auto *
I = dyn_cast<Instruction>(V)) {
528 return Visited.insert(std::make_pair(V,
std::move(Result))).first->second;
533 Result.insert(OpResult.begin(), OpResult.end());
535 return Visited.insert(std::make_pair(V,
std::move(Result))).first->second;
537 if (isa<Argument>(V)) {
543 return Visited.insert(std::make_pair(V,
std::move(Result))).first->second;
555 assert(InsertPoint &&
"Null InsertPoint");
556 if (
auto *
I = dyn_cast<Instruction>(V)) {
557 auto It = Visited.
find(
I);
558 if (It != Visited.
end()) {
561 assert(DT.
getNode(
I->getParent()) &&
"DT must contain I's parent block");
563 if (Unhoistables.
count(
I)) {
580 bool AllOpsHoisted =
true;
584 AllOpsHoisted =
false;
607 if (!MD)
return false;
609 if (MDName->
getString() !=
"branch_weights" ||
614 if (!TrueWeight || !FalseWeight)
620 assert(SumWt >= TrueWt && SumWt >= FalseWt &&
621 "Overflow calculating branch probabilities.");
627 TrueProb = BranchProbability::getBranchProbability(TrueWt, SumWt);
628 FalseProb = BranchProbability::getBranchProbability(FalseWt, SumWt);
633 return BranchProbability::getBranchProbability(
641 template <
typename K,
typename S,
typename M>
646 if (TrueProb >= Threshold) {
648 BiasMap[
Key] = TrueProb;
650 }
else if (FalseProb >= Threshold) {
651 FalseSet.insert(
Key);
652 BiasMap[
Key] = FalseProb;
672 assert((IfThen ==
R->getExit() || IfElse ==
R->getExit()) &&
674 "Invariant from findScopes");
675 if (IfThen ==
R->getExit()) {
685 TrueBiasedRegionsGlobal, FalseBiasedRegionsGlobal,
698 TrueProb, FalseProb))
704 TrueBiasedSelectsGlobal, FalseBiasedSelectsGlobal,
718 if (
SI->getParent() == EntryBB) {
725 assert(HoistPoint &&
"Null HoistPoint");
731 if (
SI->getParent() == EntryBB) {
738 "HoistPoint must be the first one in Selects");
747 CHRScope * CHR::findScope(
Region *
R) {
748 CHRScope *
Result =
nullptr;
751 assert(Entry &&
"Entry must not be null");
752 assert((Exit ==
nullptr) == (
R->isTopLevelRegion()) &&
753 "Only top level region has a null exit");
764 bool EntryInSubregion = RI.getRegionFor(Entry) !=
R;
765 if (EntryInSubregion)
769 if (
R->contains(Pred))
774 if (
BB->hasAddressTaken())
783 if (
auto *II = dyn_cast<IntrinsicInst>(&
I))
784 if (II->getIntrinsicID() == Intrinsic::coro_id)
793 auto *BI = dyn_cast<BranchInst>(Entry->getTerminator());
795 CHR_DEBUG(
dbgs() <<
"BI.isConditional " << BI->isConditional() <<
"\n");
798 if (BI && BI->isConditional()) {
803 if (S0 != S1 && (S0 == Exit || S1 == Exit)) {
806 BI,
R, TrueBiasedRegionsGlobal, FalseBiasedRegionsGlobal,
808 Result =
new CHRScope(RI);
809 Scopes.insert(Result);
815 <<
"Branch not biased";
836 if (
E->isSubRegion())
844 if (
auto *
SI = dyn_cast<SelectInst>(&
I)) {
845 Selects.push_back(
SI);
850 if (Selects.size() > 0) {
851 auto AddSelects = [&](RegInfo &RI) {
852 for (
auto *
SI : Selects)
854 TrueBiasedSelectsGlobal,
855 FalseBiasedSelectsGlobal,
857 RI.Selects.push_back(
SI);
861 <<
"Select not biased";
868 Result =
new CHRScope(RI);
869 Scopes.insert(Result);
871 CHR_DEBUG(
dbgs() <<
"Found select(s) in a region with a branch\n");
872 AddSelects(
Result->RegInfos[0]);
878 checkScopeHoistable(Result);
905 void CHR::checkScopeHoistable(CHRScope *
Scope) {
906 RegInfo &RI =
Scope->RegInfos[0];
909 auto *
Branch = RI.HasBranch ?
912 if (RI.HasBranch || !Selects.empty()) {
924 for (
auto it = Selects.begin();
it != Selects.end(); ) {
926 if (
SI == InsertPoint) {
932 DT, Unhoistables,
nullptr, Visited);
937 "DropUnhoistableSelect",
SI)
938 <<
"Dropped unhoistable select";
940 it = Selects.erase(
it);
950 if (RI.HasBranch && InsertPoint !=
Branch) {
953 DT, Unhoistables,
nullptr, Visited);
958 assert(InsertPoint !=
Branch &&
"Branch must not be the hoist point");
962 dbgs() <<
"SI " << *
SI <<
"\n";
967 "DropSelectUnhoistableBranch",
SI)
968 <<
"Dropped select due to unhoistable branch";
972 return SI->getParent() == EntryBB;
974 Unhoistables.
clear();
982 "Branch can't be already above the hoist point");
985 DT, Unhoistables,
nullptr, Visited) &&
986 "checkHoistValue for branch");
988 for (
auto *
SI : Selects) {
989 assert(!DT.dominates(
SI, InsertPoint) &&
990 "SI can't be already above the hoist point");
993 Unhoistables,
nullptr, Visited) &&
994 "checkHoistValue for selects");
1000 for (
auto *
SI : Selects) {
1011 CHRScope *
Result = findScope(
R);
1013 CHRScope *ConsecutiveSubscope =
nullptr;
1015 for (
auto It =
R->begin(); It !=
R->end(); ++It) {
1016 const std::unique_ptr<Region> &SubR = *It;
1017 auto NextIt = std::next(It);
1018 Region *NextSubR = NextIt !=
R->end() ? NextIt->get() :
nullptr;
1019 CHR_DEBUG(
dbgs() <<
"Looking at subregion " << SubR.get()->getNameStr()
1021 CHRScope *SubCHRScope = findScopes(SubR.get(), NextSubR,
R, Scopes);
1023 CHR_DEBUG(
dbgs() <<
"Subregion Scope " << *SubCHRScope <<
"\n");
1028 if (!ConsecutiveSubscope)
1029 ConsecutiveSubscope = SubCHRScope;
1030 else if (!ConsecutiveSubscope->appendable(SubCHRScope)) {
1031 Subscopes.push_back(ConsecutiveSubscope);
1032 ConsecutiveSubscope = SubCHRScope;
1034 ConsecutiveSubscope->append(SubCHRScope);
1036 if (ConsecutiveSubscope) {
1037 Subscopes.push_back(ConsecutiveSubscope);
1039 ConsecutiveSubscope =
nullptr;
1042 if (ConsecutiveSubscope) {
1043 Subscopes.push_back(ConsecutiveSubscope);
1045 for (CHRScope *Sub : Subscopes) {
1051 Scopes.push_back(Sub);
1060 auto *BI = cast<BranchInst>(RI.R->getEntry()->getTerminator());
1061 ConditionValues.
insert(BI->getCondition());
1064 ConditionValues.
insert(
SI->getCondition());
1066 return ConditionValues;
1081 assert(InsertPoint &&
"Null InsertPoint");
1083 dbgs() <<
"shouldSplit " << *InsertPoint <<
" PrevConditionValues ";
1084 for (
Value *V : PrevConditionValues) {
1085 dbgs() << *V <<
", ";
1087 dbgs() <<
" ConditionValues ";
1088 for (
Value *V : ConditionValues) {
1089 dbgs() << *V <<
", ";
1093 for (
Value *V : ConditionValues) {
1095 if (!
checkHoistValue(V, InsertPoint, DT, Unhoistables,
nullptr, Visited)) {
1096 CHR_DEBUG(
dbgs() <<
"Split. checkHoistValue false " << *V <<
"\n");
1103 if (!PrevConditionValues.empty() && !ConditionValues.empty()) {
1105 std::set<Value *> PrevBases, Bases;
1107 for (
Value *V : PrevConditionValues) {
1108 const std::set<Value *> &BaseValues =
getBaseValues(V, DT, Visited);
1109 PrevBases.insert(BaseValues.begin(), BaseValues.end());
1111 for (
Value *V : ConditionValues) {
1112 const std::set<Value *> &BaseValues =
getBaseValues(V, DT, Visited);
1113 Bases.insert(BaseValues.begin(), BaseValues.end());
1116 dbgs() <<
"PrevBases ";
1117 for (
Value *V : PrevBases) {
1118 dbgs() << *V <<
", ";
1120 dbgs() <<
" Bases ";
1121 for (
Value *V : Bases) {
1122 dbgs() << *V <<
", ";
1125 std::vector<Value *> Intersection;
1126 std::set_intersection(PrevBases.begin(), PrevBases.end(), Bases.begin(),
1127 Bases.end(), std::back_inserter(Intersection));
1128 if (Intersection.empty()) {
1140 for (RegInfo &RI :
Scope->RegInfos)
1143 for (CHRScope *Sub :
Scope->Subs)
1149 for (CHRScope *
Scope : Input) {
1151 "BranchInsertPoint must not be set");
1154 splitScope(
Scope,
nullptr,
nullptr,
nullptr, Output, Unhoistables);
1157 for (CHRScope *
Scope : Output) {
1158 assert(
Scope->BranchInsertPoint &&
"BranchInsertPoint must be set");
1171 assert(OuterConditionValues &&
"Null OuterConditionValues");
1172 assert(OuterInsertPoint &&
"Null OuterInsertPoint");
1174 bool PrevSplitFromOuter =
true;
1182 for (RegInfo &RI : RegInfos) {
1186 dbgs() <<
"ConditionValues ";
1187 for (
Value *V : ConditionValues) {
1188 dbgs() << *V <<
", ";
1191 if (RI.R == RegInfos[0].R) {
1196 << RI.R->getNameStr() <<
"\n");
1197 if (
shouldSplit(OuterInsertPoint, *OuterConditionValues,
1198 ConditionValues, DT, Unhoistables)) {
1199 PrevConditionValues = ConditionValues;
1200 PrevInsertPoint = InsertPoint;
1203 "SplitScopeFromOuter",
1204 RI.R->getEntry()->getTerminator())
1205 <<
"Split scope from outer due to unhoistable branch/select "
1206 <<
"and/or lack of common condition values";
1211 PrevSplitFromOuter =
false;
1212 PrevConditionValues = *OuterConditionValues;
1213 PrevConditionValues.
insert(ConditionValues.begin(),
1214 ConditionValues.end());
1215 PrevInsertPoint = OuterInsertPoint;
1219 PrevConditionValues = ConditionValues;
1220 PrevInsertPoint = InsertPoint;
1224 << RI.R->getNameStr() <<
"\n");
1225 if (
shouldSplit(PrevInsertPoint, PrevConditionValues, ConditionValues,
1226 DT, Unhoistables)) {
1229 Splits.push_back(
Scope);
1230 SplitsSplitFromOuter.push_back(PrevSplitFromOuter);
1231 SplitsConditionValues.push_back(PrevConditionValues);
1232 SplitsInsertPoints.push_back(PrevInsertPoint);
1234 PrevConditionValues = ConditionValues;
1235 PrevInsertPoint = InsertPoint;
1236 PrevSplitFromOuter =
true;
1239 "SplitScopeFromPrev",
1240 RI.R->getEntry()->getTerminator())
1241 <<
"Split scope from previous due to unhoistable branch/select "
1242 <<
"and/or lack of common condition values";
1246 PrevConditionValues.
insert(ConditionValues.begin(), ConditionValues.end());
1250 Splits.push_back(
Scope);
1251 SplitsSplitFromOuter.push_back(PrevSplitFromOuter);
1252 SplitsConditionValues.push_back(PrevConditionValues);
1253 assert(PrevInsertPoint &&
"Null PrevInsertPoint");
1254 SplitsInsertPoints.push_back(PrevInsertPoint);
1255 assert(Splits.size() == SplitsConditionValues.size() &&
1256 Splits.size() == SplitsSplitFromOuter.size() &&
1257 Splits.size() == SplitsInsertPoints.size() &&
"Mismatching sizes");
1258 for (
size_t I = 0;
I < Splits.size(); ++
I) {
1259 CHRScope *Split = Splits[
I];
1265 for (CHRScope *Sub : Split->Subs) {
1267 Sub, Split, &SplitConditionValues, SplitInsertPoint, Output,
1271 Split->Subs = NewSubs;
1274 for (
size_t I = 0;
I < Splits.size(); ++
I) {
1275 CHRScope *Split = Splits[
I];
1276 if (SplitsSplitFromOuter[
I]) {
1279 Split->BranchInsertPoint = SplitsInsertPoints[
I];
1280 CHR_DEBUG(
dbgs() <<
"BranchInsertPoint " << *SplitsInsertPoints[
I]
1289 "If no outer (top-level), must return no nested ones");
1294 for (CHRScope *
Scope : Scopes) {
1295 assert(
Scope->TrueBiasedRegions.empty() &&
Scope->FalseBiasedRegions.empty() &&
"Empty");
1298 dbgs() <<
"classifyBiasedScopes " << *
Scope <<
"\n";
1299 dbgs() <<
"TrueBiasedRegions ";
1301 dbgs() <<
R->getNameStr() <<
", ";
1304 dbgs() <<
"FalseBiasedRegions ";
1306 dbgs() <<
R->getNameStr() <<
", ";
1309 dbgs() <<
"TrueBiasedSelects ";
1314 dbgs() <<
"FalseBiasedSelects ";
1322 void CHR::classifyBiasedScopes(CHRScope *
Scope, CHRScope *OutermostScope) {
1323 for (RegInfo &RI :
Scope->RegInfos) {
1326 if (TrueBiasedRegionsGlobal.contains(
R))
1327 OutermostScope->TrueBiasedRegions.insert(
R);
1328 else if (FalseBiasedRegionsGlobal.contains(
R))
1329 OutermostScope->FalseBiasedRegions.insert(
R);
1334 if (TrueBiasedSelectsGlobal.contains(
SI))
1335 OutermostScope->TrueBiasedSelects.insert(
SI);
1336 else if (FalseBiasedSelectsGlobal.contains(
SI))
1337 OutermostScope->FalseBiasedSelects.insert(
SI);
1342 for (CHRScope *Sub :
Scope->Subs) {
1343 classifyBiasedScopes(Sub, OutermostScope);
1348 unsigned NumBiased =
Scope->TrueBiasedRegions.size() +
1349 Scope->FalseBiasedRegions.size() +
1350 Scope->TrueBiasedSelects.size() +
1351 Scope->FalseBiasedSelects.size();
1357 for (CHRScope *
Scope : Input) {
1360 CHR_DEBUG(
dbgs() <<
"Filtered out by biased branches truthy-regions "
1361 <<
Scope->TrueBiasedRegions.size()
1362 <<
" falsy-regions " <<
Scope->FalseBiasedRegions.size()
1363 <<
" true-selects " <<
Scope->TrueBiasedSelects.size()
1364 <<
" false-selects " <<
Scope->FalseBiasedSelects.size() <<
"\n");
1368 "DropScopeWithOneBranchOrSelect",
1369 Scope->RegInfos[0].R->getEntry()->getTerminator())
1370 <<
"Drop scope with < "
1372 <<
" biased branch(es) or select(s)";
1382 for (CHRScope *
Scope : Input) {
1388 dbgs() <<
"setCHRRegions HoistStopMap " << *
Scope <<
"\n";
1389 for (
auto pair :
Scope->HoistStopMap) {
1390 Region *R = pair.first;
1391 dbgs() <<
"Region " << R->getNameStr() <<
"\n";
1392 for (Instruction *I : pair.second) {
1393 dbgs() <<
"HoistStop " << *I <<
"\n";
1396 dbgs() <<
"CHRRegions" <<
"\n";
1397 for (RegInfo &RI :
Scope->CHRRegions) {
1398 dbgs() << RI.R->getNameStr() <<
"\n";
1403 void CHR::setCHRRegions(CHRScope *
Scope, CHRScope *OutermostScope) {
1408 for (RegInfo &RI :
Scope->RegInfos) {
1413 Instruction *InsertPoint = OutermostScope->BranchInsertPoint;
1414 for (RegInfo &RI :
Scope->RegInfos) {
1417 bool IsHoisted =
false;
1419 assert((OutermostScope->TrueBiasedRegions.contains(
R) ||
1420 OutermostScope->FalseBiasedRegions.contains(
R)) &&
1421 "Must be truthy or falsy");
1422 auto *BI = cast<BranchInst>(
R->getEntry()->getTerminator());
1425 bool IsHoistable =
checkHoistValue(BI->getCondition(), InsertPoint, DT,
1426 Unhoistables, &HoistStops, Visited);
1427 assert(IsHoistable &&
"Must be hoistable");
1428 (void)(IsHoistable);
1432 assert((OutermostScope->TrueBiasedSelects.contains(
SI) ||
1433 OutermostScope->FalseBiasedSelects.contains(
SI)) &&
1434 "Must be true or false biased");
1438 Unhoistables, &HoistStops, Visited);
1439 assert(IsHoistable &&
"Must be hoistable");
1440 (void)(IsHoistable);
1444 OutermostScope->CHRRegions.push_back(RI);
1445 OutermostScope->HoistStopMap[
R] = HoistStops;
1448 for (CHRScope *Sub :
Scope->Subs)
1449 setCHRRegions(Sub, OutermostScope);
1453 return Scope1->RegInfos[0].R->getDepth() < Scope2->RegInfos[0].R->getDepth();
1466 HoistStopMapTy &HoistStopMap,
1470 auto IT = HoistStopMap.find(
R);
1471 assert(
IT != HoistStopMap.end() &&
"Region must be in hoist stop map");
1473 if (
auto *
I = dyn_cast<Instruction>(V)) {
1474 if (
I == HoistPoint)
1478 if (
auto *PN = dyn_cast<PHINode>(
I))
1479 if (TrivialPHIs.
count(PN))
1489 assert(DT.
getNode(
I->getParent()) &&
"DT must contain I's block");
1491 "DT must contain HoistPoint block");
1503 hoistValue(
Op, HoistPoint,
R, HoistStopMap, HoistedSet, TrivialPHIs, DT);
1505 I->moveBefore(HoistPoint);
1517 for (
const RegInfo &RI :
Scope->CHRRegions) {
1519 bool IsTrueBiased =
Scope->TrueBiasedRegions.count(
R);
1520 bool IsFalseBiased =
Scope->FalseBiasedRegions.count(
R);
1521 if (RI.HasBranch && (IsTrueBiased || IsFalseBiased)) {
1522 auto *BI = cast<BranchInst>(
R->getEntry()->getTerminator());
1524 HoistedSet, TrivialPHIs, DT);
1527 bool IsTrueBiased =
Scope->TrueBiasedSelects.count(
SI);
1528 bool IsFalseBiased =
Scope->FalseBiasedSelects.count(
SI);
1529 if (!(IsTrueBiased || IsFalseBiased))
1532 HoistedSet, TrivialPHIs, DT);
1543 if (U == ExcludedUser)
1545 if (isa<BranchInst>(U) && cast<BranchInst>(U)->isConditional())
1547 if (isa<SelectInst>(U) && cast<SelectInst>(U)->getCondition() == ICmp)
1552 if (U == ExcludedUser)
1554 if (
auto *BI = dyn_cast<BranchInst>(U)) {
1555 assert(BI->isConditional() &&
"Must be conditional");
1556 BI->swapSuccessors();
1564 if (
auto *
SI = dyn_cast<SelectInst>(U)) {
1567 SI->swapProfMetadata();
1568 if (
Scope->TrueBiasedSelects.count(
SI)) {
1570 "Must not be already in");
1571 Scope->FalseBiasedSelects.insert(
SI);
1572 }
else if (
Scope->FalseBiasedSelects.count(
SI)) {
1574 "Must not be already in");
1575 Scope->TrueBiasedSelects.insert(
SI);
1592 for (RegInfo &RI :
Scope->RegInfos) {
1599 dbgs() <<
"Inserting redundant phis\n";
1601 dbgs() <<
"BlockInScope " <<
BB->getName() <<
"\n";
1606 for (
User *U :
I.users()) {
1607 if (
auto *UI = dyn_cast<Instruction>(U)) {
1608 if (!BlocksInScope.contains(UI->getParent()) &&
1610 !(isa<PHINode>(UI) && UI->getParent() == ExitBlock)) {
1612 CHR_DEBUG(
dbgs() <<
"Used outside scope by user " << *UI <<
"\n");
1613 Users.push_back(UI);
1614 }
else if (UI->getParent() == EntryBlock && isa<PHINode>(UI)) {
1619 <<
"Used at entry block (for a back edge) by a phi user "
1621 Users.push_back(UI);
1625 if (
Users.size() > 0) {
1630 &ExitBlock->
front());
1637 for (
unsigned J = 0, NumOps = UI->getNumOperands(); J < NumOps; ++J) {
1638 if (UI->getOperand(J) == &
I) {
1639 UI->setOperand(J, PN);
1653 auto HasBiasedBranchOrSelect = [](RegInfo &RI, CHRScope *
Scope) {
1654 if (
Scope->TrueBiasedRegions.count(RI.R) ||
1655 Scope->FalseBiasedRegions.count(RI.R))
1658 if (
Scope->TrueBiasedSelects.count(
SI) ||
1659 Scope->FalseBiasedSelects.count(
SI))
1663 for (RegInfo &RI :
Scope->CHRRegions) {
1665 "Must have biased branch or select");
1675 for (RegInfo &RI :
Scope->CHRRegions) {
1677 bool IsTrueBiased =
Scope->TrueBiasedRegions.count(
R);
1678 bool IsFalseBiased =
Scope->FalseBiasedRegions.count(
R);
1679 if (RI.HasBranch && (IsTrueBiased || IsFalseBiased)) {
1680 auto *BI = cast<BranchInst>(
R->getEntry()->getTerminator());
1681 Value *V = BI->getCondition();
1683 if (
auto *
I = dyn_cast<Instruction>(V)) {
1685 assert((
I->getParent() == PreEntryBlock ||
1687 "Must have been hoisted to PreEntryBlock or outside the scope");
1691 bool IsTrueBiased =
Scope->TrueBiasedSelects.count(
SI);
1692 bool IsFalseBiased =
Scope->FalseBiasedSelects.count(
SI);
1693 if (!(IsTrueBiased || IsFalseBiased))
1695 Value *V =
SI->getCondition();
1697 if (
auto *
I = dyn_cast<Instruction>(V)) {
1699 assert((
I->getParent() == PreEntryBlock ||
1701 "Must have been hoisted to PreEntryBlock or outside the scope");
1710 assert(
Scope->RegInfos.size() >= 1 &&
"Should have at least one Region");
1735 <<
" at " << *
Scope->BranchInsertPoint <<
"\n");
1739 "NewEntryBlock's only pred must be EntryBlock");
1747 cloneScopeBlocks(
Scope, PreEntryBlock, ExitBlock, LastRegion, VMap);
1751 BranchInst *MergedBr = createMergedBranch(PreEntryBlock, EntryBlock,
1752 NewEntryBlock, VMap);
1767 fixupBranchesAndSelects(
Scope, PreEntryBlock, MergedBr,
1774 void CHR::cloneScopeBlocks(CHRScope *
Scope,
1785 for (RegInfo &RI :
Scope->RegInfos)
1788 assert(
BB != PreEntryBlock &&
"Don't copy the preetntry block");
1790 NewBlocks.push_back(NewBB);
1798 F.getBasicBlockList(),
1799 NewBlocks[0]->getIterator(),
F.end());
1802 for (
unsigned i = 0,
e = NewBlocks.size();
i !=
e; ++
i)
1812 for (
unsigned I = 0, NumOps = PN.getNumIncomingValues();
I < NumOps;
1816 Value *V = PN.getIncomingValue(
I);
1817 auto It = VMap.
find(V);
1818 if (It != VMap.
end()) V = It->second;
1819 assert(VMap.
find(Pred) != VMap.
end() &&
"Pred must have been cloned");
1820 PN.addIncoming(V, cast<BasicBlock>(VMap[Pred]));
1833 "SplitBlock did not work correctly!");
1835 "NewEntryBlock's only pred must be EntryBlock");
1837 "NewEntryBlock must have been copied");
1842 BranchInst *NewBR = BranchInst::Create(NewEntryBlock,
1843 cast<BasicBlock>(VMap[NewEntryBlock]),
1846 assert(NewEntryBlock->getSinglePredecessor() == EntryBlock &&
1847 "NewEntryBlock's only pred must be EntryBlock");
1853 void CHR::fixupBranchesAndSelects(CHRScope *
Scope,
1861 for (RegInfo &RI :
Scope->CHRRegions) {
1864 fixupBranch(
R,
Scope, IRB, MergedCondition, CHRBranchBias);
1868 fixupSelect(
SI,
Scope, IRB, MergedCondition, CHRBranchBias);
1872 Stats.NumBranchesDelta += NumCHRedBranches - 1;
1879 <<
"Merged " <<
ore::NV(
"NumCHRedBranches", NumCHRedBranches)
1880 <<
" branches or selects";
1884 static_cast<uint32_t>(CHRBranchBias.scale(1000)),
1885 static_cast<uint32_t>(CHRBranchBias.getCompl().scale(1000)),
1888 MergedBR->
setMetadata(LLVMContext::MD_prof, MDB.createBranchWeights(Weights));
1889 CHR_DEBUG(
dbgs() <<
"CHR branch bias " << Weights[0] <<
":" << Weights[1]
1897 Value *&MergedCondition,
1899 bool IsTrueBiased =
Scope->TrueBiasedRegions.count(
R);
1900 assert((IsTrueBiased ||
Scope->FalseBiasedRegions.count(
R)) &&
1901 "Must be truthy or falsy");
1902 auto *BI = cast<BranchInst>(
R->getEntry()->getTerminator());
1903 assert(BranchBiasMap.find(
R) != BranchBiasMap.end() &&
1904 "Must be in the bias map");
1908 if (CHRBranchBias > Bias)
1909 CHRBranchBias =
Bias;
1913 assert(RegionExitBlock &&
"Null ExitBlock");
1914 assert((IfThen == RegionExitBlock || IfElse == RegionExitBlock) &&
1915 IfThen != IfElse &&
"Invariant from findScopes");
1916 if (IfThen == RegionExitBlock) {
1922 <<
" IfElse " << IfElse->
getName() <<
"\n");
1924 BasicBlock *HotTarget = IsTrueBiased ? IfThen : IfElse;
1925 bool ConditionTrue = HotTarget == BI->getSuccessor(0);
1926 addToMergedCondition(ConditionTrue,
Cond, BI,
Scope, IRB,
1929 assert(ConditionTrue == (HotTarget == BI->getSuccessor(0)) &&
1930 "The successor shouldn't change");
1931 Value *NewCondition = ConditionTrue ?
1934 BI->setCondition(NewCondition);
1941 Value *&MergedCondition,
1943 bool IsTrueBiased =
Scope->TrueBiasedSelects.count(
SI);
1945 Scope->FalseBiasedSelects.count(
SI)) &&
"Must be biased");
1946 assert(SelectBiasMap.find(
SI) != SelectBiasMap.end() &&
1947 "Must be in the bias map");
1951 if (CHRBranchBias > Bias)
1952 CHRBranchBias =
Bias;
1954 addToMergedCondition(IsTrueBiased,
Cond,
SI,
Scope, IRB,
1956 Value *NewCondition = IsTrueBiased ?
1959 SI->setCondition(NewCondition);
1964 void CHR::addToMergedCondition(
bool IsTrueBiased,
Value *
Cond,
1967 if (!IsTrueBiased) {
1971 auto *ICmp = dyn_cast<ICmpInst>(
Cond);
1980 if (isa<SelectInst>(BranchOrSelect) &&
1991 for (CHRScope *
Scope : CHRScopes) {
1992 transformScopes(
Scope, TrivialPHIs);
1994 std::ostringstream oss;
1995 oss <<
" after transformScopes " <<
I++;
1996 dumpIR(
F, oss.str().c_str(),
nullptr));
2003 dbgs() << Label <<
" " << Scopes.size() <<
"\n";
2004 for (CHRScope *
Scope : Scopes) {
2015 bool Changed =
false;
2018 dbgs() <<
"RegionInfo:\n";
2024 findScopes(AllScopes);
2033 splitScopes(AllScopes, SplitScopes);
2038 classifyBiasedScopes(SplitScopes);
2039 CHR_DEBUG(
dbgs() <<
"Set per-scope bias " << SplitScopes.size() <<
"\n");
2044 filterScopes(SplitScopes, FilteredScopes);
2049 setCHRRegions(FilteredScopes, SetScopes);
2056 sortScopes(SetScopes, SortedScopes);
2060 dbgs() <<
"RegionInfo:\n";
2064 if (!SortedScopes.empty()) {
2065 transformScopes(SortedScopes);
2075 <<
"Reduced the number of branches in hot paths by "
2078 <<
ore::NV(
"WeightedNumBranchesDelta",
Stats.WeightedNumBranchesDelta)
2079 <<
" (weighted by PGO count)";
2088 getAnalysis<BlockFrequencyInfoWrapperPass>().getBFI();
2089 DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
2091 getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();
2092 RegionInfo &RI = getAnalysis<RegionInfoPass>().getRegionInfo();
2093 std::unique_ptr<OptimizationRemarkEmitter> OwnedORE =
2094 std::make_unique<OptimizationRemarkEmitter>(&
F);
2095 return CHR(
F,
BFI, DT, PSI, RI, *OwnedORE).run();
2113 bool Changed = CHR(
F,
BFI, DT, PSI, RI, ORE).
run();