Lines Matching full:scope
128 // NumBranchesDelta weighted by the profile count at the scope entry.
171 // The next scope is appendable only if this scope is directly connected to in appendable()
172 // it (which implies it post-dominates this scope) and this scope dominates in appendable()
173 // it (no edge to the next scope outside this scope). in appendable()
181 // There's an edge going into the entry of the next scope from outside in appendable()
182 // of this scope. in appendable()
211 // Split this scope at the boundary region into two, which will belong to the
242 auto *Scope = new CHRScope(TailRegInfos, TailSubs); in split() local
245 return Scope; in split()
258 SmallVector<RegInfo, 8> RegInfos; // Regions that belong to this scope
266 // respectively. Used only for the outermost scope and includes regions in
274 // outermost scope and includes ones in subscopes.
296 for (CHRScope *Scope : Scopes) { in ~CHR()
297 delete Scope; in ~CHR()
309 if (CHRScope *Scope = findScopes(R, nullptr, nullptr, Output)) { in findScopes() local
310 Output.push_back(Scope); in findScopes()
316 void checkScopeHoistable(CHRScope *Scope);
320 SmallVector<CHRScope *, 8> splitScope(CHRScope *Scope,
328 void classifyBiasedScopes(CHRScope *Scope, CHRScope *OutermostScope);
335 void setCHRRegions(CHRScope *Scope, CHRScope *OutermostScope);
341 void transformScopes(CHRScope *Scope, DenseSet<PHINode *> &TrivialPHIs);
342 void cloneScopeBlocks(CHRScope *Scope,
351 void fixupBranchesAndSelects(CHRScope *Scope, BasicBlock *PreEntryBlock,
353 void fixupBranch(Region *R, CHRScope *Scope, IRBuilder<> &IRB,
355 void fixupSelect(SelectInst *SI, CHRScope *Scope, IRBuilder<> &IRB,
358 Instruction *BranchOrSelect, CHRScope *Scope,
409 raw_ostream &operator<<(raw_ostream &OS, const CHRScope &Scope) { in operator <<() argument
410 Scope.print(OS); in operator <<()
486 // of the unhoistable base values defined within the scope (excluding the
489 // scope. The returned set doesn't include constants.
499 // We don't stop at a block that's not in the Scope because we would miss in getBaseValues()
506 // I is hoistable above the Scope. in getBaseValues()
714 // Find a CHR scope in the given region.
749 // scope and hoisting more branches. in findScope()
857 // For example, for the following scope/region with selects, we want to insert
873 void CHR::checkScopeHoistable(CHRScope *Scope) { in checkScopeHoistable() argument
874 RegInfo &RI = Scope->RegInfos[0]; in checkScopeHoistable()
991 CHR_DEBUG(dbgs() << "Subregion Scope " << *SubCHRScope << "\n"); in findScopes()
993 CHR_DEBUG(dbgs() << "Subregion Scope null\n"); in findScopes()
1038 // Determine whether to split a scope depending on the sets of the branch
1040 // (return true) it if 1) the condition values of the inner/lower scope can't be
1041 // hoisted up to the outer/upper scope, or 2) the two sets of the condition
1106 static void getSelectsInScope(CHRScope *Scope, in getSelectsInScope() argument
1108 for (RegInfo &RI : Scope->RegInfos) in getSelectsInScope()
1111 for (CHRScope *Sub : Scope->Subs) in getSelectsInScope()
1117 for (CHRScope *Scope : Input) { in splitScopes()
1118 assert(!Scope->BranchInsertPoint && in splitScopes()
1121 getSelectsInScope(Scope, Unhoistables); in splitScopes()
1122 splitScope(Scope, nullptr, nullptr, nullptr, Output, Unhoistables); in splitScopes()
1125 for (CHRScope *Scope : Output) { in splitScopes()
1126 assert(Scope->BranchInsertPoint && "BranchInsertPoint must be set"); in splitScopes()
1132 CHRScope *Scope, in splitScope() argument
1149 SmallVector<RegInfo, 8> RegInfos(Scope->RegInfos); // Copy in splitScope()
1173 << "Split scope from outer due to unhoistable branch/select " in splitScope()
1195 CHRScope *Tail = Scope->split(RI.R); in splitScope()
1197 Splits.push_back(Scope); in splitScope()
1201 Scope = Tail; in splitScope()
1209 << "Split scope from previous due to unhoistable branch/select " in splitScope()
1218 Splits.push_back(Scope); in splitScope()
1262 for (CHRScope *Scope : Scopes) { in classifyBiasedScopes()
1263 assert(Scope->TrueBiasedRegions.empty() && Scope->FalseBiasedRegions.empty() && "Empty"); in classifyBiasedScopes()
1264 classifyBiasedScopes(Scope, Scope); in classifyBiasedScopes()
1266 dbgs() << "classifyBiasedScopes " << *Scope << "\n"; in classifyBiasedScopes()
1268 for (Region *R : Scope->TrueBiasedRegions) { in classifyBiasedScopes()
1273 for (Region *R : Scope->FalseBiasedRegions) { in classifyBiasedScopes()
1278 for (SelectInst *SI : Scope->TrueBiasedSelects) { in classifyBiasedScopes()
1283 for (SelectInst *SI : Scope->FalseBiasedSelects) { in classifyBiasedScopes()
1290 void CHR::classifyBiasedScopes(CHRScope *Scope, CHRScope *OutermostScope) { in classifyBiasedScopes() argument
1291 for (RegInfo &RI : Scope->RegInfos) { in classifyBiasedScopes()
1310 for (CHRScope *Sub : Scope->Subs) { in classifyBiasedScopes()
1315 static bool hasAtLeastTwoBiasedBranches(CHRScope *Scope) { in hasAtLeastTwoBiasedBranches() argument
1316 unsigned NumBiased = Scope->TrueBiasedRegions.size() + in hasAtLeastTwoBiasedBranches()
1317 Scope->FalseBiasedRegions.size() + in hasAtLeastTwoBiasedBranches()
1318 Scope->TrueBiasedSelects.size() + in hasAtLeastTwoBiasedBranches()
1319 Scope->FalseBiasedSelects.size(); in hasAtLeastTwoBiasedBranches()
1325 for (CHRScope *Scope : Input) { in filterScopes()
1327 if (!hasAtLeastTwoBiasedBranches(Scope)) { in filterScopes()
1329 << Scope->TrueBiasedRegions.size() in filterScopes()
1330 << " falsy-regions " << Scope->FalseBiasedRegions.size() in filterScopes()
1331 << " true-selects " << Scope->TrueBiasedSelects.size() in filterScopes()
1332 << " false-selects " << Scope->FalseBiasedSelects.size() << "\n"); in filterScopes()
1337 Scope->RegInfos[0].R->getEntry()->getTerminator()) in filterScopes()
1338 << "Drop scope with < " in filterScopes()
1344 Output.push_back(Scope); in filterScopes()
1350 for (CHRScope *Scope : Input) { in setCHRRegions()
1351 assert(Scope->HoistStopMap.empty() && Scope->CHRRegions.empty() && in setCHRRegions()
1353 setCHRRegions(Scope, Scope); in setCHRRegions()
1354 Output.push_back(Scope); in setCHRRegions()
1356 dbgs() << "setCHRRegions HoistStopMap " << *Scope << "\n"; in setCHRRegions()
1357 for (auto pair : Scope->HoistStopMap) { in setCHRRegions()
1365 for (RegInfo &RI : Scope->CHRRegions) { in setCHRRegions()
1371 void CHR::setCHRRegions(CHRScope *Scope, CHRScope *OutermostScope) { in setCHRRegions() argument
1376 for (RegInfo &RI : Scope->RegInfos) { in setCHRRegions()
1382 for (RegInfo &RI : Scope->RegInfos) { in setCHRRegions()
1416 for (CHRScope *Sub : Scope->Subs) in setCHRRegions()
1448 // The trivial phi inserted by the previous CHR scope could replace a in hoistValue()
1450 // previous CHR scope, which dominates this scope, it's safe to stop in hoistValue()
1463 // instruction. Since an outer (dominating) scope would hoist it to its in hoistValue()
1464 // entry before an inner (dominated) scope would to its entry, the inner in hoistValue()
1465 // scope may see the instruction already hoisted, in which case it in hoistValue()
1466 // potentially wrong for the inner scope to hoist it and could cause bad in hoistValue()
1468 // it's already in a block that dominates the inner scope. in hoistValue()
1480 // scope to the insert point.
1481 static void hoistScopeConditions(CHRScope *Scope, Instruction *HoistPoint, in hoistScopeConditions() argument
1485 for (const RegInfo &RI : Scope->CHRRegions) { in hoistScopeConditions()
1487 bool IsTrueBiased = Scope->TrueBiasedRegions.count(R); in hoistScopeConditions()
1488 bool IsFalseBiased = Scope->FalseBiasedRegions.count(R); in hoistScopeConditions()
1491 hoistValue(BI->getCondition(), HoistPoint, R, Scope->HoistStopMap, in hoistScopeConditions()
1495 bool IsTrueBiased = Scope->TrueBiasedSelects.count(SI); in hoistScopeConditions()
1496 bool IsFalseBiased = Scope->FalseBiasedSelects.count(SI); in hoistScopeConditions()
1499 hoistValue(SI->getCondition(), HoistPoint, R, Scope->HoistStopMap, in hoistScopeConditions()
1509 CHRScope *Scope) { in negateICmpIfUsedByBranchOrSelectOnly() argument
1536 if (Scope->TrueBiasedSelects.count(SI)) { in negateICmpIfUsedByBranchOrSelectOnly()
1537 assert(!Scope->FalseBiasedSelects.contains(SI) && in negateICmpIfUsedByBranchOrSelectOnly()
1539 Scope->FalseBiasedSelects.insert(SI); in negateICmpIfUsedByBranchOrSelectOnly()
1540 } else if (Scope->FalseBiasedSelects.count(SI)) { in negateICmpIfUsedByBranchOrSelectOnly()
1541 assert(!Scope->TrueBiasedSelects.contains(SI) && in negateICmpIfUsedByBranchOrSelectOnly()
1543 Scope->TrueBiasedSelects.insert(SI); in negateICmpIfUsedByBranchOrSelectOnly()
1553 // A helper for transformScopes. Insert a trivial phi at the scope exit block
1554 // for a value that's defined in the scope but used outside it (meaning it's
1556 static void insertTrivialPHIs(CHRScope *Scope, in insertTrivialPHIs() argument
1560 for (RegInfo &RI : Scope->RegInfos) { in insertTrivialPHIs()
1580 CHR_DEBUG(dbgs() << "Used outside scope by user " << *UI << "\n"); in insertTrivialPHIs()
1584 // scope to the entry block. in insertTrivialPHIs()
1617 // Assert that all the CHR regions of the scope have a biased branch or select.
1619 assertCHRRegionsHaveBiasedBranchOrSelect(CHRScope *Scope) { in assertCHRRegionsHaveBiasedBranchOrSelect() argument
1621 auto HasBiasedBranchOrSelect = [](RegInfo &RI, CHRScope *Scope) { in assertCHRRegionsHaveBiasedBranchOrSelect() argument
1622 if (Scope->TrueBiasedRegions.count(RI.R) || in assertCHRRegionsHaveBiasedBranchOrSelect()
1623 Scope->FalseBiasedRegions.count(RI.R)) in assertCHRRegionsHaveBiasedBranchOrSelect()
1626 if (Scope->TrueBiasedSelects.count(SI) || in assertCHRRegionsHaveBiasedBranchOrSelect()
1627 Scope->FalseBiasedSelects.count(SI)) in assertCHRRegionsHaveBiasedBranchOrSelect()
1631 for (RegInfo &RI : Scope->CHRRegions) { in assertCHRRegionsHaveBiasedBranchOrSelect()
1632 assert(HasBiasedBranchOrSelect(RI, Scope) && in assertCHRRegionsHaveBiasedBranchOrSelect()
1639 // been hoisted to the pre-entry block or outside of the scope.
1641 CHRScope *Scope, BasicBlock *PreEntryBlock) { in assertBranchOrSelectConditionHoisted() argument
1643 for (RegInfo &RI : Scope->CHRRegions) { in assertBranchOrSelectConditionHoisted()
1645 bool IsTrueBiased = Scope->TrueBiasedRegions.count(R); in assertBranchOrSelectConditionHoisted()
1646 bool IsFalseBiased = Scope->FalseBiasedRegions.count(R); in assertBranchOrSelectConditionHoisted()
1654 !Scope->contains(I)) && in assertBranchOrSelectConditionHoisted()
1655 "Must have been hoisted to PreEntryBlock or outside the scope"); in assertBranchOrSelectConditionHoisted()
1659 bool IsTrueBiased = Scope->TrueBiasedSelects.count(SI); in assertBranchOrSelectConditionHoisted()
1660 bool IsFalseBiased = Scope->FalseBiasedSelects.count(SI); in assertBranchOrSelectConditionHoisted()
1668 !Scope->contains(I)) && in assertBranchOrSelectConditionHoisted()
1669 "Must have been hoisted to PreEntryBlock or outside the scope"); in assertBranchOrSelectConditionHoisted()
1675 void CHR::transformScopes(CHRScope *Scope, DenseSet<PHINode *> &TrivialPHIs) { in transformScopes() argument
1676 CHR_DEBUG(dbgs() << "transformScopes " << *Scope << "\n"); in transformScopes()
1678 assert(Scope->RegInfos.size() >= 1 && "Should have at least one Region"); in transformScopes()
1680 for (RegInfo &RI : Scope->RegInfos) { in transformScopes()
1696 for (RegInfo &RI : Scope->RegInfos) { in transformScopes()
1700 Region *FirstRegion = Scope->RegInfos[0].R; in transformScopes()
1702 Region *LastRegion = Scope->RegInfos[Scope->RegInfos.size() - 1].R; in transformScopes()
1708 // cold path merges) for a value that's defined in the scope but used in transformScopes()
1713 insertTrivialPHIs(Scope, EntryBlock, ExitBlock, TrivialPHIs); in transformScopes()
1724 << " at " << *Scope->BranchInsertPoint << "\n"); in transformScopes()
1726 SplitBlock(EntryBlock, Scope->BranchInsertPoint, &DT); in transformScopes()
1733 // Clone the blocks in the scope (excluding the PreEntryBlock) to split into a in transformScopes()
1736 cloneScopeBlocks(Scope, PreEntryBlock, ExitBlock, LastRegion, VMap); in transformScopes()
1744 assertCHRRegionsHaveBiasedBranchOrSelect(Scope); in transformScopes()
1748 hoistScopeConditions(Scope, PreEntryBlock->getTerminator(), TrivialPHIs, DT); in transformScopes()
1751 assertBranchOrSelectConditionHoisted(Scope, PreEntryBlock); in transformScopes()
1756 fixupBranchesAndSelects(Scope, PreEntryBlock, MergedBr, in transformScopes()
1760 // A helper for transformScopes. Clone the blocks in the scope (excluding the
1763 void CHR::cloneScopeBlocks(CHRScope *Scope, in cloneScopeBlocks() argument
1774 for (RegInfo &RI : Scope->RegInfos) in cloneScopeBlocks()
1848 void CHR::fixupBranchesAndSelects(CHRScope *Scope, in fixupBranchesAndSelects() argument
1856 for (RegInfo &RI : Scope->CHRRegions) { in fixupBranchesAndSelects()
1859 fixupBranch(R, Scope, IRB, MergedCondition, CHRBranchBias); in fixupBranchesAndSelects()
1863 fixupSelect(SI, Scope, IRB, MergedCondition, CHRBranchBias); in fixupBranchesAndSelects()
1889 void CHR::fixupBranch(Region *R, CHRScope *Scope, in fixupBranch() argument
1893 bool IsTrueBiased = Scope->TrueBiasedRegions.count(R); in fixupBranch()
1894 assert((IsTrueBiased || Scope->FalseBiasedRegions.count(R)) && in fixupBranch()
1919 addToMergedCondition(ConditionTrue, Cond, BI, Scope, IRB, in fixupBranch()
1932 void CHR::fixupSelect(SelectInst *SI, CHRScope *Scope, in fixupSelect() argument
1936 bool IsTrueBiased = Scope->TrueBiasedSelects.count(SI); in fixupSelect()
1938 Scope->FalseBiasedSelects.count(SI)) && "Must be biased"); in fixupSelect()
1946 addToMergedCondition(IsTrueBiased, Cond, SI, Scope, IRB, in fixupSelect()
1957 Instruction *BranchOrSelect, CHRScope *Scope, in addToMergedCondition() argument
1965 !negateICmpIfUsedByBranchOrSelectOnly(ICmp, BranchOrSelect, Scope)) in addToMergedCondition()
1980 for (CHRScope *Scope : CHRScopes) { in transformScopes()
1981 transformScopes(Scope, TrivialPHIs); in transformScopes()
1993 for (CHRScope *Scope : Scopes) { in dumpScopes()
1994 dbgs() << *Scope << "\n"; in dumpScopes()
2017 // branches/selects of the inner/lower scope can't be hoisted up to the in run()
2018 // outermost/uppermost scope entry, or 2) the condition values of the biased in run()
2019 // branches/selects in a scope (including subscopes) don't share at least in run()
2025 // After splitting, set the biased regions and selects of a scope (a tree in run()
2028 CHR_DEBUG(dbgs() << "Set per-scope bias " << SplitScopes.size() << "\n"); in run()
2036 // Set the regions to be CHR'ed and their hoist stops for each scope. in run()