48#define DEBUG_TYPE "chr"
50#define CHR_DEBUG(X) LLVM_DEBUG(X)
53 cl::desc(
"Disable CHR for all functions"));
56 cl::desc(
"Apply CHR for all functions"));
60 cl::desc(
"CHR considers a branch bias greater than this ratio as biased"));
64 cl::desc(
"CHR merges a group of N branches/selects where N >= this value"));
68 cl::desc(
"Specify file to retrieve the list of modules to apply CHR to"));
72 cl::desc(
"Specify file to retrieve the list of functions to apply CHR to"));
76 cl::desc(
"Max number of duplications by CHR for a region"));
85 errs() <<
"Error: Couldn't read the chr-module-list file " <<
CHRModuleList <<
"\n";
88 StringRef Buf = FileOrErr->get()->getBuffer();
90 Buf.
split(Lines,
'\n');
103 StringRef Buf = FileOrErr->get()->getBuffer();
105 Buf.
split(Lines,
'\n');
117 CHRStats() =
default;
119 OS <<
"CHRStats: NumBranches " << NumBranches
120 <<
" NumBranchesDelta " << NumBranchesDelta
121 <<
" WeightedNumBranchesDelta " << WeightedNumBranchesDelta;
129 uint64_t WeightedNumBranchesDelta = 0;
137 bool HasBranch =
false;
148 CHRScope(
RegInfo RI) : BranchInsertPoint(nullptr) {
149 assert(RI.R &&
"Null RegionIn");
150 RegInfos.push_back(RI);
153 Region *getParentRegion() {
154 assert(RegInfos.size() > 0 &&
"Empty CHRScope");
156 assert(Parent &&
"Unexpected to call this on the top-level region");
161 assert(RegInfos.size() > 0 &&
"Empty CHRScope");
162 return RegInfos.front().R->getEntry();
166 assert(RegInfos.size() > 0 &&
"Empty CHRScope");
167 return RegInfos.back().R->getExit();
170 bool appendable(CHRScope *Next) {
174 BasicBlock *NextEntry = Next->getEntryBlock();
175 if (getExitBlock() != NextEntry)
178 Region *LastRegion = RegInfos.back().R;
187 void append(CHRScope *Next) {
188 assert(RegInfos.size() > 0 &&
"Empty CHRScope");
189 assert(Next->RegInfos.size() > 0 &&
"Empty CHRScope");
190 assert(getParentRegion() == Next->getParentRegion() &&
192 assert(getExitBlock() == Next->getEntryBlock() &&
194 RegInfos.append(Next->RegInfos.begin(), Next->RegInfos.end());
195 Subs.append(Next->Subs.begin(), Next->Subs.end());
198 void addSub(CHRScope *SubIn) {
200 bool IsChild =
false;
202 if (RI.R == SubIn->getParentRegion()) {
206 assert(IsChild &&
"Must be a child");
208 Subs.push_back(SubIn);
214 assert(Boundary &&
"Boundary null");
215 assert(RegInfos.begin()->R != Boundary &&
216 "Can't be split at beginning");
218 RegInfos, [&Boundary](
const RegInfo &RI) {
return Boundary == RI.R; });
219 if (BoundaryIt == RegInfos.end())
223 for (
const RegInfo &RI : TailRegInfos)
224 TailRegionSet.
insert(RI.R);
227 std::stable_partition(Subs.begin(), Subs.end(), [&](CHRScope *Sub) {
228 assert(Sub &&
"null Sub");
229 Region *Parent = Sub->getParentRegion();
230 if (TailRegionSet.count(Parent))
235 [&Parent](const RegInfo &RI) { return Parent == RI.R; }) &&
241 assert(HoistStopMap.empty() &&
"MapHoistStops must be empty");
242 auto *
Scope =
new CHRScope(TailRegInfos, TailSubs);
243 RegInfos.erase(BoundaryIt, RegInfos.end());
244 Subs.erase(TailIt, Subs.end());
250 for (
const RegInfo &RI : RegInfos)
251 if (RI.R->contains(Parent))
280 HoistStopMapTy HoistStopMap;
284 : RegInfos(RegInfosIn.
begin(), RegInfosIn.
end()),
285 Subs(SubsIn.
begin(), SubsIn.
end()), BranchInsertPoint(nullptr) {}
293 :
F(Fin),
BFI(BFIin), DT(DTin), PSI(PSIin), RI(RIin), ORE(OREin) {}
296 for (CHRScope *Scope : Scopes) {
308 Region *
R = RI.getTopLevelRegion();
309 if (CHRScope *Scope = findScopes(R,
nullptr,
nullptr, Output)) {
315 CHRScope *findScope(
Region *R);
316 void checkScopeHoistable(CHRScope *Scope);
328 void classifyBiasedScopes(CHRScope *Scope, CHRScope *OutermostScope);
335 void setCHRRegions(CHRScope *Scope, CHRScope *OutermostScope);
342 void cloneScopeBlocks(CHRScope *Scope,
351 void fixupBranchesAndSelects(CHRScope *Scope,
BasicBlock *PreEntryBlock,
357 void addToMergedCondition(
bool IsTrueBiased,
Value *
Cond,
360 unsigned getRegionDuplicationCount(
const Region *R) {
367 Count += DuplicationCount[
R];
403 const CHRStats &
Stats) {
445 assert(RegInfos.size() > 0 &&
"Empty CHRScope");
447 OS << RegInfos.size() <<
", Regions[";
448 for (
const RegInfo &RI : RegInfos) {
449 OS << RI.R->getNameStr();
452 if (RI.Selects.size() > 0)
453 OS <<
" S" << RI.Selects.size();
456 if (RegInfos[0].
R->getParent()) {
457 OS <<
"], Parent " << RegInfos[0].R->getParent()->getNameStr();
463 for (CHRScope *Sub : Subs) {
471 return isa<BinaryOperator>(
I) || isa<CastInst>(
I) || isa<SelectInst>(
I) ||
472 isa<GetElementPtrInst>(
I) || isa<CmpInst>(
I) ||
473 isa<InsertElementInst>(
I) || isa<ExtractElementInst>(
I) ||
474 isa<ShuffleVectorInst>(
I) || isa<ExtractValueInst>(
I) ||
475 isa<InsertValueInst>(
I);
490static const std::set<Value *> &
493 auto It = Visited.find(V);
494 if (It != Visited.end()) {
497 std::set<Value *> Result;
498 if (
auto *
I = dyn_cast<Instruction>(V)) {
504 return Visited.insert(std::make_pair(V, std::move(Result))).first->second;
507 for (
Value *Op :
I->operands()) {
508 const std::set<Value *> &OpResult =
getBaseValues(Op, DT, Visited);
509 Result.insert(OpResult.begin(), OpResult.end());
511 return Visited.insert(std::make_pair(V, std::move(Result))).first->second;
513 if (isa<Argument>(V)) {
519 return Visited.insert(std::make_pair(V, std::move(Result))).first->second;
531 assert(InsertPoint &&
"Null InsertPoint");
532 if (
auto *
I = dyn_cast<Instruction>(V)) {
533 auto It = Visited.
find(
I);
534 if (It != Visited.
end()) {
537 assert(DT.
getNode(
I->getParent()) &&
"DT must contain I's parent block");
539 if (Unhoistables.
count(
I)) {
556 bool AllOpsHoisted =
true;
557 for (
Value *Op :
I->operands()) {
558 if (!
checkHoistValue(Op, InsertPoint, DT, Unhoistables, &OpsHoistStops,
560 AllOpsHoisted =
false;
588 uint64_t SumWeight = TrueWeight + FalseWeight;
590 assert(SumWeight >= TrueWeight && SumWeight >= FalseWeight &&
591 "Overflow calculating branch probabilities.");
611template <
typename K,
typename S,
typename M>
616 if (TrueProb >= Threshold) {
618 BiasMap[Key] = TrueProb;
620 }
else if (FalseProb >= Threshold) {
621 FalseSet.insert(Key);
622 BiasMap[Key] = FalseProb;
641 assert((IfThen == R->getExit() || IfElse == R->getExit()) &&
643 "Invariant from findScopes");
644 if (IfThen == R->getExit()) {
654 TrueBiasedRegionsGlobal, FalseBiasedRegionsGlobal,
672 TrueBiasedSelectsGlobal, FalseBiasedSelectsGlobal,
686 if (
SI->getParent() == EntryBB) {
693 assert(HoistPoint &&
"Null HoistPoint");
699 if (
SI->getParent() == EntryBB) {
706 "HoistPoint must be the first one in Selects");
715CHRScope * CHR::findScope(
Region *R) {
716 CHRScope *
Result =
nullptr;
719 assert(Entry &&
"Entry must not be null");
720 assert((Exit ==
nullptr) == (
R->isTopLevelRegion()) &&
721 "Only top level region has a null exit");
732 bool EntryInSubregion = RI.getRegionFor(Entry) !=
R;
733 if (EntryInSubregion)
737 if (
R->contains(Pred))
742 if (BB->hasAddressTaken())
751 if (
auto *II = dyn_cast<IntrinsicInst>(&
I))
752 if (II->getIntrinsicID() == Intrinsic::coro_id)
761 auto *BI = dyn_cast<BranchInst>(Entry->getTerminator());
763 CHR_DEBUG(
dbgs() <<
"BI.isConditional " << BI->isConditional() <<
"\n");
766 if (BI && BI->isConditional()) {
771 if (S0 != S1 && (S0 == Exit || S1 == Exit)) {
774 BI, R, TrueBiasedRegionsGlobal, FalseBiasedRegionsGlobal,
776 Result =
new CHRScope(RI);
783 <<
"Branch not biased";
804 if (
E->isSubRegion())
812 if (
auto *SI = dyn_cast<SelectInst>(&
I)) {
818 if (Selects.
size() > 0) {
819 auto AddSelects = [&](
RegInfo &RI) {
820 for (
auto *SI : Selects)
822 TrueBiasedSelectsGlobal,
823 FalseBiasedSelectsGlobal,
825 RI.Selects.push_back(SI);
829 <<
"Select not biased";
836 Result =
new CHRScope(RI);
839 CHR_DEBUG(
dbgs() <<
"Found select(s) in a region with a branch\n");
840 AddSelects(
Result->RegInfos[0]);
846 checkScopeHoistable(Result);
873void CHR::checkScopeHoistable(CHRScope *Scope) {
877 auto *
Branch = RI.HasBranch ?
880 if (RI.HasBranch || !Selects.
empty()) {
892 for (
auto it = Selects.begin(); it != Selects.end(); ) {
894 if (SI == InsertPoint) {
900 DT, Unhoistables,
nullptr, Visited);
905 "DropUnhoistableSelect", SI)
906 <<
"Dropped unhoistable select";
908 it = Selects.erase(it);
911 Unhoistables.
erase(SI);
918 if (RI.HasBranch && InsertPoint != Branch) {
921 DT, Unhoistables,
nullptr, Visited);
926 assert(InsertPoint != Branch &&
"Branch must not be the hoist point");
930 dbgs() <<
"SI " << *
SI <<
"\n";
935 "DropSelectUnhoistableBranch", SI)
936 <<
"Dropped select due to unhoistable branch";
940 return SI->getParent() == EntryBB;
942 Unhoistables.
clear();
949 assert(!DT.dominates(Branch, InsertPoint) &&
950 "Branch can't be already above the hoist point");
953 DT, Unhoistables,
nullptr, Visited) &&
954 "checkHoistValue for branch");
956 for (
auto *SI : Selects) {
957 assert(!DT.dominates(SI, InsertPoint) &&
958 "SI can't be already above the hoist point");
961 Unhoistables,
nullptr, Visited) &&
962 "checkHoistValue for selects");
968 for (
auto *SI : Selects) {
979 CHRScope *
Result = findScope(R);
981 CHRScope *ConsecutiveSubscope =
nullptr;
983 for (
auto It =
R->begin(); It !=
R->end(); ++It) {
984 const std::unique_ptr<Region> &SubR = *It;
985 auto NextIt = std::next(It);
986 Region *NextSubR = NextIt !=
R->end() ? NextIt->get() :
nullptr;
987 CHR_DEBUG(
dbgs() <<
"Looking at subregion " << SubR.get()->getNameStr()
989 CHRScope *SubCHRScope = findScopes(SubR.get(), NextSubR, R, Scopes);
991 CHR_DEBUG(
dbgs() <<
"Subregion Scope " << *SubCHRScope <<
"\n");
996 if (!ConsecutiveSubscope)
997 ConsecutiveSubscope = SubCHRScope;
998 else if (!ConsecutiveSubscope->appendable(SubCHRScope)) {
999 Subscopes.
push_back(ConsecutiveSubscope);
1000 ConsecutiveSubscope = SubCHRScope;
1002 ConsecutiveSubscope->append(SubCHRScope);
1004 if (ConsecutiveSubscope) {
1005 Subscopes.
push_back(ConsecutiveSubscope);
1007 ConsecutiveSubscope =
nullptr;
1010 if (ConsecutiveSubscope) {
1011 Subscopes.
push_back(ConsecutiveSubscope);
1013 for (CHRScope *Sub : Subscopes) {
1028 auto *BI = cast<BranchInst>(RI.R->getEntry()->getTerminator());
1029 ConditionValues.
insert(BI->getCondition());
1032 ConditionValues.
insert(
SI->getCondition());
1034 return ConditionValues;
1049 assert(InsertPoint &&
"Null InsertPoint");
1051 dbgs() <<
"shouldSplit " << *InsertPoint <<
" PrevConditionValues ";
1052 for (
Value *V : PrevConditionValues) {
1053 dbgs() << *V <<
", ";
1055 dbgs() <<
" ConditionValues ";
1056 for (
Value *V : ConditionValues) {
1057 dbgs() << *V <<
", ";
1061 for (
Value *V : ConditionValues) {
1063 if (!
checkHoistValue(V, InsertPoint, DT, Unhoistables,
nullptr, Visited)) {
1064 CHR_DEBUG(
dbgs() <<
"Split. checkHoistValue false " << *V <<
"\n");
1071 if (!PrevConditionValues.
empty() && !ConditionValues.
empty()) {
1073 std::set<Value *> PrevBases, Bases;
1075 for (
Value *V : PrevConditionValues) {
1076 const std::set<Value *> &BaseValues =
getBaseValues(V, DT, Visited);
1077 PrevBases.insert(BaseValues.begin(), BaseValues.end());
1079 for (
Value *V : ConditionValues) {
1080 const std::set<Value *> &BaseValues =
getBaseValues(V, DT, Visited);
1081 Bases.insert(BaseValues.begin(), BaseValues.end());
1084 dbgs() <<
"PrevBases ";
1085 for (
Value *V : PrevBases) {
1086 dbgs() << *V <<
", ";
1088 dbgs() <<
" Bases ";
1089 for (
Value *V : Bases) {
1090 dbgs() << *V <<
", ";
1093 std::vector<Value *> Intersection;
1094 std::set_intersection(PrevBases.begin(), PrevBases.end(), Bases.begin(),
1095 Bases.end(), std::back_inserter(Intersection));
1096 if (Intersection.empty()) {
1108 for (
RegInfo &RI : Scope->RegInfos)
1111 for (CHRScope *Sub : Scope->Subs)
1117 for (CHRScope *Scope : Input) {
1119 "BranchInsertPoint must not be set");
1122 splitScope(Scope,
nullptr,
nullptr,
nullptr, Output, Unhoistables);
1125 for (CHRScope *Scope : Output) {
1126 assert(
Scope->BranchInsertPoint &&
"BranchInsertPoint must be set");
1139 assert(OuterConditionValues &&
"Null OuterConditionValues");
1140 assert(OuterInsertPoint &&
"Null OuterInsertPoint");
1142 bool PrevSplitFromOuter =
true;
1150 for (
RegInfo &RI : RegInfos) {
1154 dbgs() <<
"ConditionValues ";
1155 for (
Value *V : ConditionValues) {
1156 dbgs() << *
V <<
", ";
1159 if (RI.R == RegInfos[0].R) {
1164 << RI.R->getNameStr() <<
"\n");
1165 if (
shouldSplit(OuterInsertPoint, *OuterConditionValues,
1166 ConditionValues, DT, Unhoistables)) {
1167 PrevConditionValues = ConditionValues;
1168 PrevInsertPoint = InsertPoint;
1171 "SplitScopeFromOuter",
1172 RI.R->getEntry()->getTerminator())
1173 <<
"Split scope from outer due to unhoistable branch/select "
1174 <<
"and/or lack of common condition values";
1179 PrevSplitFromOuter =
false;
1180 PrevConditionValues = *OuterConditionValues;
1181 PrevConditionValues.
insert(ConditionValues.begin(),
1182 ConditionValues.end());
1183 PrevInsertPoint = OuterInsertPoint;
1187 PrevConditionValues = ConditionValues;
1188 PrevInsertPoint = InsertPoint;
1192 << RI.R->getNameStr() <<
"\n");
1193 if (
shouldSplit(PrevInsertPoint, PrevConditionValues, ConditionValues,
1194 DT, Unhoistables)) {
1198 SplitsSplitFromOuter.
push_back(PrevSplitFromOuter);
1199 SplitsConditionValues.
push_back(PrevConditionValues);
1200 SplitsInsertPoints.
push_back(PrevInsertPoint);
1202 PrevConditionValues = ConditionValues;
1203 PrevInsertPoint = InsertPoint;
1204 PrevSplitFromOuter =
true;
1207 "SplitScopeFromPrev",
1208 RI.R->getEntry()->getTerminator())
1209 <<
"Split scope from previous due to unhoistable branch/select "
1210 <<
"and/or lack of common condition values";
1214 PrevConditionValues.
insert(ConditionValues.begin(), ConditionValues.end());
1219 SplitsSplitFromOuter.
push_back(PrevSplitFromOuter);
1220 SplitsConditionValues.
push_back(PrevConditionValues);
1221 assert(PrevInsertPoint &&
"Null PrevInsertPoint");
1222 SplitsInsertPoints.
push_back(PrevInsertPoint);
1224 Splits.
size() == SplitsSplitFromOuter.
size() &&
1225 Splits.
size() == SplitsInsertPoints.
size() &&
"Mismatching sizes");
1226 for (
size_t I = 0;
I < Splits.
size(); ++
I) {
1227 CHRScope *
Split = Splits[
I];
1233 for (CHRScope *Sub :
Split->Subs) {
1235 Sub, Split, &SplitConditionValues, SplitInsertPoint, Output,
1239 Split->Subs = NewSubs;
1242 for (
size_t I = 0;
I < Splits.
size(); ++
I) {
1243 CHRScope *
Split = Splits[
I];
1244 if (SplitsSplitFromOuter[
I]) {
1247 Split->BranchInsertPoint = SplitsInsertPoints[
I];
1248 CHR_DEBUG(
dbgs() <<
"BranchInsertPoint " << *SplitsInsertPoints[
I]
1257 "If no outer (top-level), must return no nested ones");
1262 for (CHRScope *Scope : Scopes) {
1263 assert(
Scope->TrueBiasedRegions.empty() &&
Scope->FalseBiasedRegions.empty() &&
"Empty");
1264 classifyBiasedScopes(Scope, Scope);
1266 dbgs() <<
"classifyBiasedScopes " << *Scope <<
"\n";
1267 dbgs() <<
"TrueBiasedRegions ";
1269 dbgs() <<
R->getNameStr() <<
", ";
1272 dbgs() <<
"FalseBiasedRegions ";
1274 dbgs() <<
R->getNameStr() <<
", ";
1277 dbgs() <<
"TrueBiasedSelects ";
1282 dbgs() <<
"FalseBiasedSelects ";
1290void CHR::classifyBiasedScopes(CHRScope *Scope, CHRScope *OutermostScope) {
1294 if (TrueBiasedRegionsGlobal.contains(R))
1295 OutermostScope->TrueBiasedRegions.insert(R);
1296 else if (FalseBiasedRegionsGlobal.contains(R))
1297 OutermostScope->FalseBiasedRegions.insert(R);
1302 if (TrueBiasedSelectsGlobal.contains(SI))
1303 OutermostScope->TrueBiasedSelects.insert(SI);
1304 else if (FalseBiasedSelectsGlobal.contains(SI))
1305 OutermostScope->FalseBiasedSelects.insert(SI);
1310 for (CHRScope *Sub :
Scope->Subs) {
1311 classifyBiasedScopes(Sub, OutermostScope);
1316 unsigned NumBiased = Scope->TrueBiasedRegions.size() +
1317 Scope->FalseBiasedRegions.size() +
1318 Scope->TrueBiasedSelects.size() +
1319 Scope->FalseBiasedSelects.size();
1325 for (CHRScope *Scope : Input) {
1328 CHR_DEBUG(
dbgs() <<
"Filtered out by biased branches truthy-regions "
1329 <<
Scope->TrueBiasedRegions.size()
1330 <<
" falsy-regions " <<
Scope->FalseBiasedRegions.size()
1331 <<
" true-selects " <<
Scope->TrueBiasedSelects.size()
1332 <<
" false-selects " <<
Scope->FalseBiasedSelects.size() <<
"\n");
1336 "DropScopeWithOneBranchOrSelect",
1337 Scope->RegInfos[0].R->getEntry()->getTerminator())
1338 <<
"Drop scope with < "
1340 <<
" biased branch(es) or select(s)";
1350 for (CHRScope *Scope : Input) {
1353 setCHRRegions(Scope, Scope);
1356 dbgs() <<
"setCHRRegions HoistStopMap " << *Scope <<
"\n";
1357 for (
auto pair :
Scope->HoistStopMap) {
1358 Region *R = pair.first;
1359 dbgs() <<
"Region " << R->getNameStr() <<
"\n";
1360 for (Instruction *I : pair.second) {
1361 dbgs() <<
"HoistStop " << *I <<
"\n";
1364 dbgs() <<
"CHRRegions" <<
"\n";
1366 dbgs() << RI.R->getNameStr() <<
"\n";
1371void CHR::setCHRRegions(CHRScope *Scope, CHRScope *OutermostScope) {
1381 Instruction *InsertPoint = OutermostScope->BranchInsertPoint;
1385 bool IsHoisted =
false;
1387 assert((OutermostScope->TrueBiasedRegions.contains(R) ||
1388 OutermostScope->FalseBiasedRegions.contains(R)) &&
1389 "Must be truthy or falsy");
1390 auto *BI = cast<BranchInst>(
R->getEntry()->getTerminator());
1393 bool IsHoistable =
checkHoistValue(BI->getCondition(), InsertPoint, DT,
1394 Unhoistables, &HoistStops, Visited);
1395 assert(IsHoistable &&
"Must be hoistable");
1396 (void)(IsHoistable);
1400 assert((OutermostScope->TrueBiasedSelects.contains(SI) ||
1401 OutermostScope->FalseBiasedSelects.contains(SI)) &&
1402 "Must be true or false biased");
1406 Unhoistables, &HoistStops, Visited);
1407 assert(IsHoistable &&
"Must be hoistable");
1408 (void)(IsHoistable);
1412 OutermostScope->CHRRegions.push_back(RI);
1413 OutermostScope->HoistStopMap[
R] = HoistStops;
1416 for (CHRScope *Sub :
Scope->Subs)
1417 setCHRRegions(Sub, OutermostScope);
1421 return Scope1->RegInfos[0].R->getDepth() < Scope2->RegInfos[0].R->getDepth();
1434 HoistStopMapTy &HoistStopMap,
1438 auto IT = HoistStopMap.find(R);
1439 assert(
IT != HoistStopMap.end() &&
"Region must be in hoist stop map");
1441 if (
auto *
I = dyn_cast<Instruction>(V)) {
1442 if (
I == HoistPoint)
1446 if (
auto *PN = dyn_cast<PHINode>(
I))
1447 if (TrivialPHIs.
count(PN))
1457 assert(DT.
getNode(
I->getParent()) &&
"DT must contain I's block");
1459 "DT must contain HoistPoint block");
1470 for (
Value *Op :
I->operands()) {
1471 hoistValue(Op, HoistPoint, R, HoistStopMap, HoistedSet, TrivialPHIs, DT);
1473 I->moveBefore(HoistPoint);
1485 for (
const RegInfo &RI : Scope->CHRRegions) {
1487 bool IsTrueBiased = Scope->TrueBiasedRegions.count(R);
1488 bool IsFalseBiased = Scope->FalseBiasedRegions.count(R);
1489 if (RI.HasBranch && (IsTrueBiased || IsFalseBiased)) {
1490 auto *BI = cast<BranchInst>(R->getEntry()->getTerminator());
1491 hoistValue(BI->getCondition(), HoistPoint, R, Scope->HoistStopMap,
1492 HoistedSet, TrivialPHIs, DT);
1495 bool IsTrueBiased = Scope->TrueBiasedSelects.count(
SI);
1496 bool IsFalseBiased = Scope->FalseBiasedSelects.count(
SI);
1497 if (!(IsTrueBiased || IsFalseBiased))
1499 hoistValue(
SI->getCondition(), HoistPoint, R, Scope->HoistStopMap,
1500 HoistedSet, TrivialPHIs, DT);
1511 if (U == ExcludedUser)
1513 if (isa<BranchInst>(U) && cast<BranchInst>(U)->isConditional())
1515 if (isa<SelectInst>(U) && cast<SelectInst>(U)->getCondition() == ICmp)
1520 if (U == ExcludedUser)
1522 if (
auto *BI = dyn_cast<BranchInst>(U)) {
1523 assert(BI->isConditional() &&
"Must be conditional");
1524 BI->swapSuccessors();
1532 if (
auto *
SI = dyn_cast<SelectInst>(U)) {
1535 SI->swapProfMetadata();
1536 if (Scope->TrueBiasedSelects.count(
SI)) {
1537 assert(!Scope->FalseBiasedSelects.contains(
SI) &&
1538 "Must not be already in");
1539 Scope->FalseBiasedSelects.insert(
SI);
1540 }
else if (Scope->FalseBiasedSelects.count(
SI)) {
1541 assert(!Scope->TrueBiasedSelects.contains(
SI) &&
1542 "Must not be already in");
1543 Scope->TrueBiasedSelects.insert(
SI);
1560 for (
RegInfo &RI : Scope->RegInfos) {
1563 BlocksInScope.
insert(BB);
1567 dbgs() <<
"Inserting redundant phis\n";
1569 dbgs() <<
"BlockInScope " << BB->getName() <<
"\n";
1574 for (
User *U :
I.users()) {
1575 if (
auto *UI = dyn_cast<Instruction>(U)) {
1576 if (!BlocksInScope.
contains(UI->getParent()) &&
1578 !(isa<PHINode>(UI) && UI->getParent() == ExitBlock)) {
1580 CHR_DEBUG(
dbgs() <<
"Used outside scope by user " << *UI <<
"\n");
1581 Users.push_back(UI);
1582 }
else if (UI->getParent() == EntryBlock && isa<PHINode>(UI)) {
1587 <<
"Used at entry block (for a back edge) by a phi user "
1589 Users.push_back(UI);
1593 if (
Users.size() > 0) {
1598 &ExitBlock->
front());
1605 for (
unsigned J = 0, NumOps = UI->getNumOperands(); J < NumOps; ++J) {
1606 if (UI->getOperand(J) == &
I) {
1607 UI->setOperand(J, PN);
1621 auto HasBiasedBranchOrSelect = [](
RegInfo &RI, CHRScope *Scope) {
1622 if (Scope->TrueBiasedRegions.count(RI.R) ||
1623 Scope->FalseBiasedRegions.count(RI.R))
1626 if (Scope->TrueBiasedSelects.count(
SI) ||
1627 Scope->FalseBiasedSelects.count(
SI))
1631 for (
RegInfo &RI : Scope->CHRRegions) {
1632 assert(HasBiasedBranchOrSelect(RI, Scope) &&
1633 "Must have biased branch or select");
1641 CHRScope *Scope,
BasicBlock *PreEntryBlock) {
1643 for (
RegInfo &RI : Scope->CHRRegions) {
1645 bool IsTrueBiased = Scope->TrueBiasedRegions.count(R);
1646 bool IsFalseBiased = Scope->FalseBiasedRegions.count(R);
1647 if (RI.HasBranch && (IsTrueBiased || IsFalseBiased)) {
1648 auto *BI = cast<BranchInst>(R->getEntry()->getTerminator());
1649 Value *V = BI->getCondition();
1651 if (
auto *
I = dyn_cast<Instruction>(V)) {
1653 assert((
I->getParent() == PreEntryBlock ||
1654 !Scope->contains(
I)) &&
1655 "Must have been hoisted to PreEntryBlock or outside the scope");
1659 bool IsTrueBiased = Scope->TrueBiasedSelects.count(
SI);
1660 bool IsFalseBiased = Scope->FalseBiasedSelects.count(
SI);
1661 if (!(IsTrueBiased || IsFalseBiased))
1663 Value *V =
SI->getCondition();
1665 if (
auto *
I = dyn_cast<Instruction>(V)) {
1667 assert((
I->getParent() == PreEntryBlock ||
1668 !Scope->contains(
I)) &&
1669 "Must have been hoisted to PreEntryBlock or outside the scope");
1678 assert(
Scope->RegInfos.size() >= 1 &&
"Should have at least one Region");
1682 unsigned Duplication = getRegionDuplicationCount(R);
1683 CHR_DEBUG(
dbgs() <<
"Dup count for R=" << R <<
" is " << Duplication
1686 CHR_DEBUG(
dbgs() <<
"Reached the dup threshold of " << Duplication
1687 <<
" for this region");
1690 R->getEntry()->getTerminator())
1691 <<
"Reached the duplication threshold for the region";
1697 DuplicationCount[RI.R]++;
1704 std::optional<uint64_t>
ProfileCount =
BFI.getBlockProfileCount(EntryBlock);
1724 <<
" at " << *
Scope->BranchInsertPoint <<
"\n");
1728 "NewEntryBlock's only pred must be EntryBlock");
1736 cloneScopeBlocks(Scope, PreEntryBlock, ExitBlock, LastRegion, VMap);
1740 BranchInst *MergedBr = createMergedBranch(PreEntryBlock, EntryBlock,
1741 NewEntryBlock, VMap);
1756 fixupBranchesAndSelects(Scope, PreEntryBlock, MergedBr,
1763void CHR::cloneScopeBlocks(CHRScope *Scope,
1777 assert(BB != PreEntryBlock &&
"Don't copy the preetntry block");
1786 F.splice(ExitBlock->
getIterator(), &
F, NewBlocks[0]->getIterator(),
1800 for (
unsigned I = 0, NumOps = PN.getNumIncomingValues();
I < NumOps;
1804 Value *
V = PN.getIncomingValue(
I);
1805 auto It = VMap.
find(V);
1806 if (It != VMap.
end())
V = It->second;
1807 assert(VMap.
find(Pred) != VMap.
end() &&
"Pred must have been cloned");
1808 PN.addIncoming(V, cast<BasicBlock>(VMap[Pred]));
1821 "SplitBlock did not work correctly!");
1823 "NewEntryBlock's only pred must be EntryBlock");
1825 "NewEntryBlock must have been copied");
1831 cast<BasicBlock>(VMap[NewEntryBlock]),
1834 assert(NewEntryBlock->getSinglePredecessor() == EntryBlock &&
1835 "NewEntryBlock's only pred must be EntryBlock");
1841void CHR::fixupBranchesAndSelects(CHRScope *Scope,
1852 fixupBranch(R, Scope, IRB, MergedCondition, CHRBranchBias);
1856 fixupSelect(SI, Scope, IRB, MergedCondition, CHRBranchBias);
1860 Stats.NumBranchesDelta += NumCHRedBranches - 1;
1867 <<
"Merged " <<
ore::NV(
"NumCHRedBranches", NumCHRedBranches)
1868 <<
" branches or selects";
1872 static_cast<uint32_t>(CHRBranchBias.scale(1000)),
1873 static_cast<uint32_t>(CHRBranchBias.getCompl().scale(1000)),
1876 MergedBR->
setMetadata(LLVMContext::MD_prof, MDB.createBranchWeights(Weights));
1877 CHR_DEBUG(
dbgs() <<
"CHR branch bias " << Weights[0] <<
":" << Weights[1]
1883void CHR::fixupBranch(
Region *R, CHRScope *Scope,
1885 Value *&MergedCondition,
1887 bool IsTrueBiased =
Scope->TrueBiasedRegions.count(R);
1888 assert((IsTrueBiased ||
Scope->FalseBiasedRegions.count(R)) &&
1889 "Must be truthy or falsy");
1890 auto *BI = cast<BranchInst>(
R->getEntry()->getTerminator());
1891 assert(BranchBiasMap.contains(R) &&
"Must be in the bias map");
1895 if (CHRBranchBias > Bias)
1896 CHRBranchBias = Bias;
1900 assert(RegionExitBlock &&
"Null ExitBlock");
1901 assert((IfThen == RegionExitBlock || IfElse == RegionExitBlock) &&
1902 IfThen != IfElse &&
"Invariant from findScopes");
1903 if (IfThen == RegionExitBlock) {
1909 <<
" IfElse " << IfElse->
getName() <<
"\n");
1911 BasicBlock *HotTarget = IsTrueBiased ? IfThen : IfElse;
1912 bool ConditionTrue = HotTarget == BI->getSuccessor(0);
1913 addToMergedCondition(ConditionTrue,
Cond, BI, Scope, IRB,
1916 assert(ConditionTrue == (HotTarget == BI->getSuccessor(0)) &&
1917 "The successor shouldn't change");
1918 Value *NewCondition = ConditionTrue ?
1921 BI->setCondition(NewCondition);
1926void CHR::fixupSelect(
SelectInst *SI, CHRScope *Scope,
1928 Value *&MergedCondition,
1930 bool IsTrueBiased =
Scope->TrueBiasedSelects.count(SI);
1932 Scope->FalseBiasedSelects.count(SI)) &&
"Must be biased");
1933 assert(SelectBiasMap.contains(SI) &&
"Must be in the bias map");
1937 if (CHRBranchBias > Bias)
1938 CHRBranchBias = Bias;
1940 addToMergedCondition(IsTrueBiased,
Cond, SI, Scope, IRB,
1942 Value *NewCondition = IsTrueBiased ?
1945 SI->setCondition(NewCondition);
1950void CHR::addToMergedCondition(
bool IsTrueBiased,
Value *
Cond,
1953 if (!IsTrueBiased) {
1957 auto *ICmp = dyn_cast<ICmpInst>(
Cond);
1974 for (CHRScope *Scope : CHRScopes) {
1975 transformScopes(Scope, TrivialPHIs);
1977 std::ostringstream oss;
1978 oss <<
" after transformScopes " <<
I++;
1979 dumpIR(
F, oss.str().c_str(),
nullptr));
1986 dbgs() << Label <<
" " << Scopes.size() <<
"\n";
1987 for (CHRScope *Scope : Scopes) {
1988 dbgs() << *Scope <<
"\n";
1998 bool Changed =
false;
2001 dbgs() <<
"RegionInfo:\n";
2007 findScopes(AllScopes);
2016 splitScopes(AllScopes, SplitScopes);
2021 classifyBiasedScopes(SplitScopes);
2027 filterScopes(SplitScopes, FilteredScopes);
2032 setCHRRegions(FilteredScopes, SetScopes);
2039 sortScopes(SetScopes, SortedScopes);
2043 dbgs() <<
"RegionInfo:\n";
2047 if (!SortedScopes.
empty()) {
2048 transformScopes(SortedScopes);
2058 <<
"Reduced the number of branches in hot paths by "
2061 <<
ore::NV(
"WeightedNumBranchesDelta",
Stats.WeightedNumBranchesDelta)
2062 <<
" (weighted by PGO count)";
2081 if (!PPSI || !PPSI->hasProfileSummary())
2088 bool Changed = CHR(
F, BFI, DT, PSI, RI, ORE).run();
static cl::opt< ITMode > IT(cl::desc("IT block support"), cl::Hidden, cl::init(DefaultIT), cl::values(clEnumValN(DefaultIT, "arm-default-it", "Generate any type of IT block"), clEnumValN(RestrictedIT, "arm-restrict-it", "Disallow complex IT blocks")))
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
SmallVector< MachineOperand, 4 > Cond
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
#define LLVM_ATTRIBUTE_UNUSED
static void insertTrivialPHIs(CHRScope *Scope, BasicBlock *EntryBlock, BasicBlock *ExitBlock, DenseSet< PHINode * > &TrivialPHIs)
static raw_ostream LLVM_ATTRIBUTE_UNUSED & operator<<(raw_ostream &OS, const CHRStats &Stats)
static cl::opt< bool > DisableCHR("disable-chr", cl::init(false), cl::Hidden, cl::desc("Disable CHR for all functions"))
static StringSet CHRFunctions
static bool CHRScopeSorter(CHRScope *Scope1, CHRScope *Scope2)
static bool checkHoistValue(Value *V, Instruction *InsertPoint, DominatorTree &DT, DenseSet< Instruction * > &Unhoistables, DenseSet< Instruction * > *HoistStops, DenseMap< Instruction *, bool > &Visited)
static cl::opt< unsigned > CHRMergeThreshold("chr-merge-threshold", cl::init(2), cl::Hidden, cl::desc("CHR merges a group of N branches/selects where N >= this value"))
static bool isHoistable(Instruction *I, DominatorTree &DT)
static cl::opt< unsigned > CHRDupThreshsold("chr-dup-threshold", cl::init(3), cl::Hidden, cl::desc("Max number of duplications by CHR for a region"))
static bool shouldSplit(Instruction *InsertPoint, DenseSet< Value * > &PrevConditionValues, DenseSet< Value * > &ConditionValues, DominatorTree &DT, DenseSet< Instruction * > &Unhoistables)
static bool checkBias(K *Key, BranchProbability TrueProb, BranchProbability FalseProb, S &TrueSet, S &FalseSet, M &BiasMap)
static StringSet CHRModules
static bool checkBiasedSelect(SelectInst *SI, Region *R, DenseSet< SelectInst * > &TrueBiasedSelectsGlobal, DenseSet< SelectInst * > &FalseBiasedSelectsGlobal, DenseMap< SelectInst *, BranchProbability > &SelectBiasMap)
static void hoistValue(Value *V, Instruction *HoistPoint, Region *R, HoistStopMapTy &HoistStopMap, DenseSet< Instruction * > &HoistedSet, DenseSet< PHINode * > &TrivialPHIs, DominatorTree &DT)
static bool hasAtLeastTwoBiasedBranches(CHRScope *Scope)
static bool shouldApply(Function &F, ProfileSummaryInfo &PSI)
static void LLVM_ATTRIBUTE_UNUSED dumpIR(Function &F, const char *Label, CHRStats *Stats)
static void getSelectsInScope(CHRScope *Scope, DenseSet< Instruction * > &Output)
static void hoistScopeConditions(CHRScope *Scope, Instruction *HoistPoint, DenseSet< PHINode * > &TrivialPHIs, DominatorTree &DT)
static bool isHoistableInstructionType(Instruction *I)
static DenseSet< Value * > getCHRConditionValuesForRegion(RegInfo &RI)
static bool negateICmpIfUsedByBranchOrSelectOnly(ICmpInst *ICmp, Instruction *ExcludedUser, CHRScope *Scope)
static Instruction * getBranchInsertPoint(RegInfo &RI)
static void LLVM_ATTRIBUTE_UNUSED assertBranchOrSelectConditionHoisted(CHRScope *Scope, BasicBlock *PreEntryBlock)
static cl::opt< std::string > CHRModuleList("chr-module-list", cl::init(""), cl::Hidden, cl::desc("Specify file to retrieve the list of modules to apply CHR to"))
static void LLVM_ATTRIBUTE_UNUSED assertCHRRegionsHaveBiasedBranchOrSelect(CHRScope *Scope)
static cl::opt< double > CHRBiasThreshold("chr-bias-threshold", cl::init(0.99), cl::Hidden, cl::desc("CHR considers a branch bias greater than this ratio as biased"))
static void LLVM_ATTRIBUTE_UNUSED dumpScopes(SmallVectorImpl< CHRScope * > &Scopes, const char *Label)
static BranchProbability getCHRBiasThreshold()
static cl::opt< std::string > CHRFunctionList("chr-function-list", cl::init(""), cl::Hidden, cl::desc("Specify file to retrieve the list of functions to apply CHR to"))
static cl::opt< bool > ForceCHR("force-chr", cl::init(false), cl::Hidden, cl::desc("Apply CHR for all functions"))
static bool checkBiasedBranch(BranchInst *BI, Region *R, DenseSet< Region * > &TrueBiasedRegionsGlobal, DenseSet< Region * > &FalseBiasedRegionsGlobal, DenseMap< Region *, BranchProbability > &BranchBiasMap)
static const std::set< Value * > & getBaseValues(Value *V, DominatorTree &DT, DenseMap< Value *, std::set< Value * > > &Visited)
static bool extractBranchProbabilities(Instruction *I, BranchProbability &TrueProb, BranchProbability &FalseProb)
static void parseCHRFilterFiles()
static Error split(StringRef Str, char Separator, std::pair< StringRef, StringRef > &Split)
Checked version of split, to ensure mandatory subparts.
This file defines the DenseMap class.
This file defines the DenseSet and SmallDenseSet classes.
This is the interface for a simple mod/ref and alias analysis over globals.
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
iv Induction Variable Users
static Constant * getFalse(Type *Ty)
For a boolean type or a vector of boolean type, return false or a vector with every element false.
block placement Basic Block Placement Stats
FunctionAnalysisManager FAM
This header defines various interfaces for pass management in LLVM.
This file contains the declarations for profiling metadata utility functions.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallVector class.
StringSet - A set-like wrapper for the StringMap.
static bool contains(SmallPtrSetImpl< ConstantExpr * > &Cache, ConstantExpr *Expr, Constant *C)
A container for analyses that lazily runs them and caches their results.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
LLVM Basic Block Representation.
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
const Instruction & front() const
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Analysis pass which computes BlockFrequencyInfo.
BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...
Conditional or Unconditional Branch instruction.
void setCondition(Value *V)
bool isConditional() const
static BranchInst * Create(BasicBlock *IfTrue, Instruction *InsertBefore=nullptr)
BasicBlock * getSuccessor(unsigned i) const
bool isUnconditional() const
static BranchProbability getBranchProbability(uint64_t Numerator, uint64_t Denominator)
void setPredicate(Predicate P)
Set the predicate for this instruction to the specified value.
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE,...
Predicate getPredicate() const
Return the predicate for this instruction.
This is the shared class of boolean and integer constants.
static ConstantInt * getTrue(LLVMContext &Context)
ControlHeightReductionPass()
PreservedAnalyses run(Function &F, FunctionAnalysisManager &FAM)
iterator find(const_arg_type_t< KeyT > Val)
Implements a dense probed hash-table based set.
Analysis pass which computes a DominatorTree.
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
Class to represent profile counts.
This instruction compares its operands according to the predicate given to the constructor.
Value * CreateFreeze(Value *V, const Twine &Name="")
Value * CreateLogicalAnd(Value *Cond1, Value *Cond2, const Twine &Name="")
Value * CreateXor(Value *LHS, Value *RHS, const Twine &Name="")
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
const BasicBlock * getParent() const
void setMetadata(unsigned KindID, MDNode *Node)
Set the metadata of the specified kind to the specified node.
SymbolTableList< Instruction >::iterator insertInto(BasicBlock *ParentBB, SymbolTableList< Instruction >::iterator It)
Inserts an unlinked instruction into ParentBB at position It and returns the iterator of the inserted...
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
static ErrorOr< std::unique_ptr< MemoryBuffer > > getFile(const Twine &Filename, bool IsText=false, bool RequiresNullTerminator=true, bool IsVolatile=false, std::optional< Align > Alignment=std::nullopt)
Open the specified file as a MemoryBuffer, returning a new MemoryBuffer if successful,...
An analysis over an "inner" IR unit that provides access to an analysis manager over a "outer" IR uni...
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
A set of analyses that are preserved following a run of a transformation pass.
static PreservedAnalyses none()
Convenience factory function for the empty preserved set.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
An analysis pass based on the new PM to deliver ProfileSummaryInfo.
Analysis providing profile information.
bool isFunctionEntryHot(const Function *F) const
Returns true if F has hot function entry.
BlockT * getExit() const
Get the exit BasicBlock of the Region.
void replaceEntryRecursive(BlockT *NewEntry)
Recursively replace the entry basic block of the region.
bool contains(const BlockT *BB) const
Check if the region contains a BasicBlock.
RegionT * getParent() const
Get the parent of the Region.
BlockT * getEntry() const
Get the entry BasicBlock of the Region.
Analysis pass that exposes the RegionInfo for a function.
This class represents the LLVM 'select' instruction.
bool contains(const key_type &key) const
Check if the SetVector contains the given key.
bool insert(const value_type &X)
Insert a new element into the SetVector.
A SetVector that performs no allocations if smaller than a certain size.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
size_type count(StringRef Key) const
count - Return 1 if the element is in the map, 0 otherwise.
StringRef - Represent a constant reference to a string, i.e.
std::pair< StringRef, StringRef > split(char Separator) const
Split into two substrings around the first occurrence of a separator character.
StringSet - A wrapper for StringMap that provides set-like functionality.
std::pair< typename Base::iterator, bool > insert(StringRef key)
void dropAllReferences()
Drop all references to operands.
iterator find(const KeyT &Val)
LLVM Value Representation.
iterator_range< user_iterator > users()
StringRef getName() const
Return a constant reference to the value's name.
std::pair< iterator, bool > insert(const ValueT &V)
bool contains(const_arg_type_t< ValueT > V) const
Check if the set contains the given element.
bool erase(const ValueT &V)
size_type count(const_arg_type_t< ValueT > V) const
Return 1 if the specified key is in the set, 0 otherwise.
self_iterator getIterator()
This class implements an extremely fast bulk output stream that can only output to a stream.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
@ Tail
Attemps to make calls as fast as possible while guaranteeing that tail call optimization can always b...
initializer< Ty > init(const Ty &Val)
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
Scope
Defines the scope in which this symbol should be visible: Default – Visible in the public interface o...
DiagnosticInfoOptimizationBase::Argument NV
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
const_iterator end(StringRef path)
Get end iterator over path.
void append(SmallVectorImpl< char > &path, const Twine &a, const Twine &b="", const Twine &c="", const Twine &d="")
Append to path.
This is an optimization pass for GlobalISel generic memory operations.
void stable_sort(R &&Range)
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
BasicBlock * CloneBasicBlock(const BasicBlock *BB, ValueToValueMapTy &VMap, const Twine &NameSuffix="", Function *F=nullptr, ClonedCodeInfo *CodeInfo=nullptr, DebugInfoFinder *DIFinder=nullptr)
Return a copy of the specified basic block, but without embedding the block into a particular functio...
@ RF_IgnoreMissingLocals
If this flag is set, the remapper ignores missing function-local entries (Argument,...
@ RF_NoModuleLevelChanges
If this flag is set, the remapper knows that only local values within a function (such as an instruct...
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
void RemapInstruction(Instruction *I, ValueToValueMapTy &VM, RemapFlags Flags=RF_None, ValueMapTypeRemapper *TypeMapper=nullptr, ValueMaterializer *Materializer=nullptr)
Convert the instruction operands from referencing the current values into those specified by VM.
raw_fd_ostream & errs()
This returns a reference to a raw_ostream for standard error.
bool isGuaranteedNotToBeUndefOrPoison(const Value *V, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Return true if this function can prove that V does not have undef bits and is never poison.
OutputIt copy(R &&Range, OutputIt Out)
bool isSafeToSpeculativelyExecute(const Instruction *I, const Instruction *CtxI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr)
Return true if the instruction does not have any effects besides calculating the result and does not ...
bool extractBranchWeights(const MDNode *ProfileData, SmallVectorImpl< uint32_t > &Weights)
Extract branch weights from MD_prof metadata.
auto find_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly.
void erase_if(Container &C, UnaryPredicate P)
Provide a container algorithm similar to C++ Library Fundamentals v2's erase_if which is equivalent t...
auto predecessors(const MachineBasicBlock *BB)
BasicBlock * SplitBlock(BasicBlock *Old, Instruction *SplitPt, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="", bool Before=false)
Split the specified block at the specified instruction.
unsigned pred_size(const MachineBasicBlock *BB)
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.