Lines Matching +full:sub +full:- +full:blocks
1 //===-- ControlHeightReduction.cpp - Control Height Reduction -------------===//
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
9 // This pass merges conditional blocks of code and reduces the number of
12 //===----------------------------------------------------------------------===//
52 static cl::opt<bool> DisableCHR("disable-chr", cl::init(false), cl::Hidden,
55 static cl::opt<bool> ForceCHR("force-chr", cl::init(false), cl::Hidden,
59 "chr-bias-threshold", cl::init(0.99), cl::Hidden,
63 "chr-merge-threshold", cl::init(2), cl::Hidden,
67 "chr-module-list", cl::init(""), cl::Hidden,
71 "chr-function-list", cl::init(""), cl::Hidden,
75 "chr-dup-threshold", cl::init(3), cl::Hidden,
85 errs() << "Error: Couldn't read the chr-module-list file " << CHRModuleList << "\n";
88 StringRef Buf = FileOrErr->get()->getBuffer();
100 errs() << "Error: Couldn't read the chr-function-list file " << CHRFunctionList << "\n";
103 StringRef Buf = FileOrErr->get()->getBuffer();
132 // RegInfo - some properties of a Region.
143 // CHRScope - a sequence of regions to CHR together. It corresponds to a
144 // sequence of conditional blocks. It can have subscopes which correspond to
145 // nested conditional blocks. Nested CHRScopes form a tree.
155 Region *Parent = RegInfos[0].R->getParent();
156 assert(Parent && "Unexpected to call this on the top-level region");
162 return RegInfos.front().R->getEntry();
167 return RegInfos.back().R->getExit();
172 // it (which implies it post-dominates this scope) and this scope dominates
174 BasicBlock *NextEntry = Next->getEntryBlock();
180 if (!LastRegion->contains(Pred))
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());
202 if (RI.R == SubIn->getParentRegion()) {
215 assert(RegInfos.begin()->R != Boundary &&
227 std::stable_partition(Subs.begin(), Subs.end(), [&](CHRScope *Sub) {
228 assert(Sub && "null Sub");
229 Region *Parent = Sub->getParentRegion();
249 BasicBlock *Parent = I->getParent();
251 if (RI.R->contains(Parent))
265 // True-biased and false-biased regions (conditional blocks),
273 // True-biased and false-biased selects, respectively. Used only for the
279 // hoisting instructions at through use-def chains.
368 R = R->getParent();
381 // All the true-biased regions in the function
383 // All the false-biased regions in the function
385 // All the true-biased selects in the function
387 // All the false-biased selects in the function
422 if (CHRModules.count(F.getParent()->getName()))
433 StringRef ModuleName = F.getParent()->getName();
449 OS << RI.R->getNameStr();
456 if (RegInfos[0].R->getParent()) {
457 OS << "], Parent " << RegInfos[0].R->getParent()->getNameStr();
463 for (CHRScope *Sub : Subs) {
464 OS << *Sub << ", ";
485 // Recursively traverse the use-def chains of the given value and return a set
487 // first-region entry block) or the (hoistable or unhoistable) base values that
488 // are defined outside (including the first-region entry block) of the
495 return It->second;
504 return Visited.insert(std::make_pair(V, std::move(Result))).first->second;
507 for (Value *Op : I->operands()) {
511 return Visited.insert(std::make_pair(V, std::move(Result))).first->second;
519 return Visited.insert(std::make_pair(V, std::move(Result))).first->second;
524 // non-null, the instructions to stop hoisting at through the use-def chains are
535 return It->second;
537 assert(DT.getNode(I->getParent()) && "DT must contain I's parent block");
538 assert(DT.getNode(InsertPoint->getParent()) && "DT must contain Destination");
547 HoistStops->insert(I);
557 for (Value *Op : I->operands()) {
567 HoistStops->insert(OpsHoistStops.begin(), OpsHoistStops.end());
575 // Non-instructions are considered hoistable.
593 // Guard against 0-to-0 branch weights to avoid a division-by-zero crash.
634 if (!BI->isConditional())
639 BasicBlock *IfThen = BI->getSuccessor(0);
640 BasicBlock *IfElse = BI->getSuccessor(1);
641 assert((IfThen == R->getExit() || IfElse == R->getExit()) &&
644 if (IfThen == R->getExit()) {
681 BasicBlock *EntryBB = R->getEntry();
684 Instruction *HoistPoint = EntryBB->getTerminator();
686 if (SI->getParent() == EntryBB) {
699 if (SI->getParent() == EntryBB) {
717 BasicBlock *Entry = R->getEntry();
718 BasicBlock *Exit = R->getExit(); // null if top level.
720 assert((Exit == nullptr) == (R->isTopLevelRegion()) &&
723 CHR_DEBUG(dbgs() << "Entry " << Entry->getName() << "\n");
727 CHR_DEBUG(dbgs() << "Exit " << Exit->getName() << "\n");
737 if (R->contains(Pred))
739 // If any of the basic blocks have address taken, we must skip this region
740 // because we cannot clone basic blocks that have address taken.
741 for (BasicBlock *BB : R->blocks()) {
742 if (BB->hasAddressTaken())
752 if (II->getIntrinsicID() == Intrinsic::coro_id)
757 // Try to find an if-then block (check if R is an if-then).
761 auto *BI = dyn_cast<BranchInst>(Entry->getTerminator());
763 CHR_DEBUG(dbgs() << "BI.isConditional " << BI->isConditional() << "\n");
766 if (BI && BI->isConditional()) {
767 BasicBlock *S0 = BI->getSuccessor(0);
768 BasicBlock *S1 = BI->getSuccessor(1);
769 CHR_DEBUG(dbgs() << "S0 " << S0->getName() << "\n");
770 CHR_DEBUG(dbgs() << "S1 " << S1->getName() << "\n");
790 // Try to look for selects in the direct child blocks (as opposed to in
803 for (RegionNode *E : R->elements()) {
804 if (E->isSubRegion())
808 BasicBlock *BB = E->getEntry();
833 CHR_DEBUG(dbgs() << "Found a select-only region\n");
840 AddSelects(Result->RegInfos[0]);
855 // selects in the first blocks.
874 RegInfo &RI = Scope->RegInfos[0];
876 BasicBlock *EntryBB = R->getEntry();
878 cast<BranchInst>(EntryBB->getTerminator()) : nullptr;
884 // select. Note no instruction can't data-depend on a branch (a branch
899 bool IsHoistable = checkHoistValue(SI->getCondition(), InsertPoint,
920 bool IsHoistable = checkHoistValue(Branch->getCondition(), InsertPoint,
940 return SI->getParent() == EntryBB;
952 assert(checkHoistValue(Branch->getCondition(), InsertPoint,
960 assert(checkHoistValue(SI->getCondition(), InsertPoint, DT,
978 CHR_DEBUG(dbgs() << "findScopes " << R->getNameStr() << "\n");
983 for (auto It = R->begin(); It != R->end(); ++It) {
986 Region *NextSubR = NextIt != R->end() ? NextIt->get() : nullptr;
987 CHR_DEBUG(dbgs() << "Looking at subregion " << SubR.get()->getNameStr()
998 else if (!ConsecutiveSubscope->appendable(SubCHRScope)) {
1002 ConsecutiveSubscope->append(SubCHRScope);
1013 for (CHRScope *Sub : Subscopes) {
1016 Result->addSub(Sub);
1019 Scopes.push_back(Sub);
1028 auto *BI = cast<BranchInst>(RI.R->getEntry()->getTerminator());
1029 ConditionValues.insert(BI->getCondition());
1032 ConditionValues.insert(SI->getCondition());
1108 for (RegInfo &RI : Scope->RegInfos)
1111 for (CHRScope *Sub : Scope->Subs)
1112 getSelectsInScope(Sub, Output);
1118 assert(!Scope->BranchInsertPoint &&
1126 assert(Scope->BranchInsertPoint && "BranchInsertPoint must be set");
1149 SmallVector<RegInfo, 8> RegInfos(Scope->RegInfos); // Copy
1164 << RI.R->getNameStr() << "\n");
1172 RI.R->getEntry()->getTerminator())
1192 << RI.R->getNameStr() << "\n");
1195 CHRScope *Tail = Scope->split(RI.R);
1208 RI.R->getEntry()->getTerminator())
1233 for (CHRScope *Sub : Split->Subs) {
1235 Sub, Split, &SplitConditionValues, SplitInsertPoint, Output,
1239 Split->Subs = NewSubs;
1247 Split->BranchInsertPoint = SplitsInsertPoints[I];
1257 "If no outer (top-level), must return no nested ones");
1263 assert(Scope->TrueBiasedRegions.empty() && Scope->FalseBiasedRegions.empty() && "Empty");
1268 for (Region *R : Scope->TrueBiasedRegions) {
1269 dbgs() << R->getNameStr() << ", ";
1273 for (Region *R : Scope->FalseBiasedRegions) {
1274 dbgs() << R->getNameStr() << ", ";
1278 for (SelectInst *SI : Scope->TrueBiasedSelects) {
1283 for (SelectInst *SI : Scope->FalseBiasedSelects) {
1291 for (RegInfo &RI : Scope->RegInfos) {
1295 OutermostScope->TrueBiasedRegions.insert(R);
1297 OutermostScope->FalseBiasedRegions.insert(R);
1303 OutermostScope->TrueBiasedSelects.insert(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();
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");
1337 Scope->RegInfos[0].R->getEntry()->getTerminator())
1351 assert(Scope->HoistStopMap.empty() && Scope->CHRRegions.empty() &&
1357 for (auto pair : Scope->HoistStopMap) {
1359 dbgs() << "Region " << R->getNameStr() << "\n";
1365 for (RegInfo &RI : Scope->CHRRegions) {
1366 dbgs() << RI.R->getNameStr() << "\n";
1374 // are and constant-folded after CHR (in case one biased select or a branch
1376 for (RegInfo &RI : Scope->RegInfos) {
1381 Instruction *InsertPoint = OutermostScope->BranchInsertPoint;
1382 for (RegInfo &RI : Scope->RegInfos) {
1387 assert((OutermostScope->TrueBiasedRegions.contains(R) ||
1388 OutermostScope->FalseBiasedRegions.contains(R)) &&
1390 auto *BI = cast<BranchInst>(R->getEntry()->getTerminator());
1393 bool IsHoistable = checkHoistValue(BI->getCondition(), InsertPoint, DT,
1400 assert((OutermostScope->TrueBiasedSelects.contains(SI) ||
1401 OutermostScope->FalseBiasedSelects.contains(SI)) &&
1405 bool IsHoistable = checkHoistValue(SI->getCondition(), InsertPoint, DT,
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();
1440 DenseSet<Instruction *> &HoistStops = IT->second;
1449 // non-phi in HoistStops. Note that since this phi is at the exit of a
1457 assert(DT.getNode(I->getParent()) && "DT must contain I's block");
1458 assert(DT.getNode(HoistPoint->getParent()) &&
1467 // IR (non-dominating def), but safe to skip hoisting it instead because
1470 for (Value *Op : I->operands()) {
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);
1490 auto *BI = cast<BranchInst>(R->getEntry()->getTerminator());
1491 hoistValue(BI->getCondition(), HoistPoint, R, Scope->HoistStopMap,
1495 bool IsTrueBiased = Scope->TrueBiasedSelects.count(SI);
1496 bool IsFalseBiased = Scope->FalseBiasedSelects.count(SI);
1499 hoistValue(SI->getCondition(), HoistPoint, R, Scope->HoistStopMap,
1510 for (User *U : ICmp->users()) {
1513 if (isa<BranchInst>(U) && cast<BranchInst>(U)->isConditional())
1515 if (isa<SelectInst>(U) && cast<SelectInst>(U)->getCondition() == ICmp)
1519 for (User *U : ICmp->users()) {
1523 assert(BI->isConditional() && "Must be conditional");
1524 BI->swapSuccessors();
1526 // TrueBiasedRegions/FalseBiasedRegions because true-based/false-based
1527 // mean whehter the branch is likely go into the if-then rather than
1534 SI->swapValues();
1535 SI->swapProfMetadata();
1536 if (Scope->TrueBiasedSelects.count(SI)) {
1537 assert(!Scope->FalseBiasedSelects.contains(SI) &&
1539 Scope->FalseBiasedSelects.insert(SI);
1540 } else if (Scope->FalseBiasedSelects.count(SI)) {
1541 assert(!Scope->TrueBiasedSelects.contains(SI) &&
1543 Scope->TrueBiasedSelects.insert(SI);
1549 ICmp->setPredicate(CmpInst::getInversePredicate(ICmp->getPredicate()));
1560 for (RegInfo &RI : Scope->RegInfos) {
1561 for (BasicBlock *BB : RI.R->blocks()) { // This includes the blocks in the
1562 // sub-Scopes.
1569 dbgs() << "BlockInScope " << BB->getName() << "\n";
1576 if (!BlocksInScope.contains(UI->getParent()) &&
1578 !(isa<PHINode>(UI) && UI->getParent() == ExitBlock)) {
1582 } else if (UI->getParent() == EntryBlock && isa<PHINode>(UI)) {
1598 PN->insertBefore(ExitBlock->begin());
1600 PN->addIncoming(&I, Pred);
1605 for (unsigned J = 0, NumOps = UI->getNumOperands(); J < NumOps; ++J) {
1606 if (UI->getOperand(J) == &I) {
1607 UI->setOperand(J, PN);
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) {
1639 // been hoisted to the pre-entry block or outside of the scope.
1643 for (RegInfo &RI : Scope->CHRRegions) {
1645 bool IsTrueBiased = Scope->TrueBiasedRegions.count(R);
1646 bool IsFalseBiased = Scope->FalseBiasedRegions.count(R);
1648 auto *BI = cast<BranchInst>(R->getEntry()->getTerminator());
1649 Value *V = BI->getCondition();
1653 assert((I->getParent() == PreEntryBlock ||
1654 !Scope->contains(I)) &&
1659 bool IsTrueBiased = Scope->TrueBiasedSelects.count(SI);
1660 bool IsFalseBiased = Scope->FalseBiasedSelects.count(SI);
1663 Value *V = SI->getCondition();
1667 assert((I->getParent() == PreEntryBlock ||
1668 !Scope->contains(I)) &&
1678 assert(Scope->RegInfos.size() >= 1 && "Should have at least one Region");
1680 for (RegInfo &RI : Scope->RegInfos) {
1690 R->getEntry()->getTerminator())
1696 for (RegInfo &RI : Scope->RegInfos) {
1700 Region *FirstRegion = Scope->RegInfos[0].R;
1701 BasicBlock *EntryBlock = FirstRegion->getEntry();
1702 Region *LastRegion = Scope->RegInfos[Scope->RegInfos.size() - 1].R;
1703 BasicBlock *ExitBlock = LastRegion->getExit();
1720 // and Region only points to the entry and the exit blocks, rather than
1721 // keeping everything in a list or set, the blocks membership and the
1722 // entry/exit blocks of the region are still valid after the split.
1723 CHR_DEBUG(dbgs() << "Splitting entry block " << EntryBlock->getName()
1724 << " at " << *Scope->BranchInsertPoint << "\n");
1726 SplitBlock(EntryBlock, Scope->BranchInsertPoint, &DT);
1727 assert(NewEntryBlock->getSinglePredecessor() == EntryBlock &&
1729 FirstRegion->replaceEntryRecursive(NewEntryBlock);
1733 // Clone the blocks in the scope (excluding the PreEntryBlock) to split into a
1748 hoistScopeConditions(Scope, PreEntryBlock->getTerminator(), TrivialPHIs, DT);
1754 // Create the combined branch condition and constant-fold the branches/selects
1760 // A helper for transformScopes. Clone the blocks in the scope (excluding the
1768 // Clone all the blocks. The original blocks will be the hot-path
1769 // CHR-optimized code and the cloned blocks will be the original unoptimized
1771 // CHRScope/Region/RegionInfo can stay valid in pointing to the hot-path code
1774 for (RegInfo &RI : Scope->RegInfos)
1775 for (BasicBlock *BB : RI.R->blocks()) { // This includes the blocks in the
1776 // sub-Scopes.
1784 for (PHINode &PN : make_early_inc_range(NewBB->phis()))
1790 // Place the cloned blocks right after the original blocks (right before the
1793 F.splice(ExitBlock->getIterator(), &F, NewBlocks[0]->getIterator(),
1796 // Update the cloned blocks/instructions to refer to themselves.
1802 // Add the cloned blocks to the PHIs of the exit blocks. ExitBlock is null for
1803 // the top-level region but we don't need to add PHIs. The trivial PHIs
1806 for (PHINode &PN : ExitBlock->phis())
1810 if (LastRegion->contains(Pred)) {
1813 if (It != VMap.end()) V = It->second;
1826 BranchInst *OldBR = cast<BranchInst>(PreEntryBlock->getTerminator());
1827 assert(OldBR->isUnconditional() && OldBR->getSuccessor(0) == NewEntryBlock &&
1829 assert(NewEntryBlock->getSinglePredecessor() == EntryBlock &&
1833 OldBR->dropAllReferences();
1834 OldBR->eraseFromParent();
1840 NewBR->insertInto(PreEntryBlock, PreEntryBlock->end());
1841 assert(NewEntryBlock->getSinglePredecessor() == EntryBlock &&
1847 // constant-fold the branches/selects in the hot path.
1855 IRBuilder<> IRB(PreEntryBlock->getTerminator());
1856 for (RegInfo &RI : Scope->CHRRegions) {
1867 Stats.NumBranchesDelta += NumCHRedBranches - 1;
1868 Stats.WeightedNumBranchesDelta += (NumCHRedBranches - 1) * ProfileCount;
1873 MergedBR->getSuccessor(0)->getTerminator())
1877 MergedBR->setCondition(MergedCondition);
1888 // and constant-fold a branch in the hot path.
1893 bool IsTrueBiased = Scope->TrueBiasedRegions.count(R);
1894 assert((IsTrueBiased || Scope->FalseBiasedRegions.count(R)) &&
1896 auto *BI = cast<BranchInst>(R->getEntry()->getTerminator());
1903 BasicBlock *IfThen = BI->getSuccessor(1);
1904 BasicBlock *IfElse = BI->getSuccessor(0);
1905 BasicBlock *RegionExitBlock = R->getExit();
1914 CHR_DEBUG(dbgs() << "IfThen " << IfThen->getName()
1915 << " IfElse " << IfElse->getName() << "\n");
1916 Value *Cond = BI->getCondition();
1918 bool ConditionTrue = HotTarget == BI->getSuccessor(0);
1921 // Constant-fold the branch at ClonedEntryBlock.
1922 assert(ConditionTrue == (HotTarget == BI->getSuccessor(0)) &&
1927 BI->setCondition(NewCondition);
1931 // and constant-fold a select in the hot path.
1936 bool IsTrueBiased = Scope->TrueBiasedSelects.count(SI);
1938 Scope->FalseBiasedSelects.count(SI)) && "Must be biased");
1945 Value *Cond = SI->getCondition();
1951 SI->setCondition(NewCondition);
2028 CHR_DEBUG(dbgs() << "Set per-scope bias " << SplitScopes.size() << "\n");
2087 if (!PPSI || !PPSI->hasProfileSummary())