Lines Matching full:chain
22 // first time it reaches a chain of basic blocks, it schedules them in the
114 // - Outlining: placement of a basic block outside the chain or hot path.
118 cl::desc("Outline loop blocks from loop chain if (frequency of loop) / "
198 "triangle-chain-count",
246 /// Type for our function-wide basic block -> block chain mapping.
249 /// A chain of blocks which will be laid out contiguously.
251 /// This is the datastructure representing a chain of consecutive blocks that
253 /// probabilities and code locality. We also can use a block chain to represent
258 /// them. They participate in a block-to-chain mapping, which is updated
261 /// The sequence of blocks belonging to this chain.
263 /// This is the sequence of blocks for a particular chain. These will be laid
267 /// A handle to the function-wide basic block to block chain mapping.
269 /// This is retained in each block chain to simplify the computation of child
278 /// This builds a new block chain representing a single basic block in the
279 /// function. It also registers itself as the chain that block participates
283 assert(BB && "Cannot create a chain with a null basic block");
287 /// Iterator over blocks within the chain.
291 /// Beginning of blocks within the chain.
295 /// End of blocks within the chain.
309 /// Merge a block chain into this one.
311 /// This routine merges a block chain into this one. It takes care of forming
313 /// updating the block -> chain mapping. It does not free or tear down the
314 /// old chain, but the old chain's block list is no longer valid.
315 void merge(MachineBasicBlock *BB, BlockChain *Chain) {
317 assert(!Blocks.empty() && "Can't merge into an empty chain.");
319 // Fast path in case we don't have a chain already.
320 if (!Chain) {
322 "Passed chain is null, but BB has entry in BlockToChain.");
328 assert(BB == *Chain->begin() && "Passed BB is not head of Chain.");
329 assert(Chain->begin() != Chain->end());
331 // Update the incoming blocks to point to this chain, and add them to the
332 // chain structure.
333 for (MachineBasicBlock *ChainBB : *Chain) {
335 assert(BlockToChain[ChainBB] == Chain && "Incoming blocks not in chain.");
341 /// Dump the blocks in this chain.
348 /// Count of predecessors of any block within the chain which have not
349 /// yet been scheduled. In general, we will delay scheduling this chain
472 /// Decrease the UnscheduledPredecessors count for all blocks in chain, and
474 void markChainSuccessors(const BlockChain &Chain,
480 void markBlockSuccessors(const BlockChain &Chain, const MachineBasicBlock *BB,
485 collectViableSuccessors(const MachineBasicBlock *BB, const BlockChain &Chain,
495 const MachineBasicBlock *LoopHeaderBB, BlockChain &Chain,
501 BlockChain &Chain, BlockFilterSet *BlockFilter,
510 const BlockChain &Chain,
513 const BlockChain &Chain,
516 selectBestCandidateBlock(const BlockChain &Chain,
535 void buildChain(const MachineBasicBlock *BB, BlockChain &Chain,
571 BranchProbability QProb, const BlockChain &Chain,
577 const BlockChain &Chain, const BlockFilterSet *BlockFilter);
583 BranchProbability AdjustedSumProb, const BlockChain &Chain,
595 const BlockChain &Chain,
608 /// Create a single CFG chain from the current block order.
667 /// Mark a chain's successors as having one fewer preds.
669 /// When a chain is being merged into the "placed" chain, this routine will
670 /// quickly walk the successors of each block in the chain and mark them as
672 /// chain which reach the zero-predecessor state to the appropriate worklist.
674 const BlockChain &Chain, const MachineBasicBlock *LoopHeaderBB,
676 // Walk all the blocks in this chain, marking their successors as having
678 for (MachineBasicBlock *MBB : Chain) {
679 markBlockSuccessors(Chain, MBB, LoopHeaderBB, BlockFilter);
687 /// and was duplicated into the chain end, we need to redo markBlockSuccessors
690 const BlockChain &Chain, const MachineBasicBlock *MBB,
700 // Disregard edges within a fixed chain, or edges to the loop header.
701 if (&Chain == &SuccChain || Succ == LoopHeaderBB)
704 // This is a cross-chain edge that is within the loop, so decrement the
705 // loop predecessor count of the destination chain.
723 const MachineBasicBlock *BB, const BlockChain &Chain,
727 // either not in BlockFilter or is already in the current chain. Consider the
749 if (SuccChain == &Chain) {
753 << " -> Mid chain!\n");
831 BranchProbability QProb, const BlockChain &Chain,
860 collectViableSuccessors(Succ, Chain, BlockFilter, SuccSuccs);
889 BlockToChain[SuccPred] == &Chain ||
964 Chain, BlockFilter))
986 const BlockChain &Chain, const BlockFilterSet *BlockFilter) {
1010 PredChain == &Chain || PredChain == BlockToChain[Succ])
1081 BranchProbability AdjustedSumProb, const BlockChain &Chain,
1102 BlockToChain[SuccPred] == &Chain ||
1134 canTailDuplicateUnplacedPreds(BB, Succ2, Chain, BlockFilter) &&
1136 Chain, BlockFilter)) {
1165 const BlockChain &Chain, const BlockFilterSet *BlockFilter) {
1182 (BlockToChain[Pred] == &Chain && !Succ->succ_empty()))
1277 /// If the branches in a chain are likely to be from the same side of the
1308 // Map from last block to the chain that contains it. This allows us to extend
1350 // existing chain.
1354 // If it is, remove the chain from the map, grow it, and put it back in the
1357 TriangleChain Chain = std::move(Found->second);
1359 Chain.append(PDom);
1360 TriangleChainMap.insert(std::make_pair(Chain.getKey(), std::move(Chain)));
1372 TriangleChain &Chain = ChainPair.second;
1376 if (Chain.count() < TriangleChainCount)
1378 MachineBasicBlock *dst = Chain.Edges.back();
1379 Chain.Edges.pop_back();
1380 for (MachineBasicBlock *src : reverse(Chain.Edges)) {
1425 /// \p Chain: The chain that BB belongs to and Succ is being considered for.
1431 BranchProbability RealSuccProb, const BlockChain &Chain,
1561 (BlockFilter && !BlockFilter->count(Pred)) || PredChain == &Chain ||
1610 const BlockChain &Chain,
1619 collectViableSuccessors(BB, Chain, BlockFilter, Successors);
1632 SuccChain != &Chain && Succ == *SuccChain->begin())
1638 if (isTrellis(BB, Successors, Chain, BlockFilter))
1639 return getBestTrellisSuccessor(BB, Successors, AdjustedSumProb, Chain,
1656 Chain, BlockFilter)) {
1694 if (canTailDuplicateUnplacedPreds(BB, Succ, Chain, BlockFilter) &&
1695 (isProfitableToTailDup(BB, Succ, BestProb, Chain, BlockFilter))) {
1722 const BlockChain &Chain, SmallVectorImpl<MachineBasicBlock *> &WorkList) {
1728 return BlockToChain.lookup(BB) == &Chain;
1743 if (&SuccChain == &Chain)
1785 /// all of the basic blocks and form a chain due to unnatural loops in the CFG.
1797 // Now select the head of the chain to which the unplaced block belongs
1798 // as the block to place. This will force the entire chain to be placed,
1834 BlockChain &Chain = *BlockToChain[MBB];
1835 if (!UpdatedPreds.insert(&Chain).second)
1839 Chain.UnscheduledPredecessors == 0 &&
1841 for (MachineBasicBlock *ChainBB : Chain) {
1842 assert(BlockToChain[ChainBB] == &Chain &&
1843 "Block in chain doesn't match BlockToChain map.");
1847 if (BlockToChain[Pred] == &Chain)
1849 ++Chain.UnscheduledPredecessors;
1853 if (Chain.UnscheduledPredecessors != 0)
1856 MachineBasicBlock *BB = *Chain.begin();
1864 BlockChain &Chain,
1867 assert(BlockToChain[HeadBB] == &Chain && "BlockToChainMap mis-match.\n");
1874 markChainSuccessors(Chain, LoopHeaderBB, BlockFilter);
1875 MachineBasicBlock *BB = *std::prev(Chain.end());
1877 assert(BB && "null block found at end of chain in loop.");
1878 assert(BlockToChain[BB] == &Chain && "BlockToChainMap mis-match in loop.");
1879 assert(*std::prev(Chain.end()) == BB && "BB Not found at end of chain.");
1883 auto Result = selectBestSuccessor(BB, Chain, BlockFilter);
1888 BB, BestSucc, Chain, BlockFilter));
1894 BestSucc = selectBestCandidateBlock(Chain, BlockWorkList);
1896 BestSucc = selectBestCandidateBlock(Chain, EHPadWorkList);
1900 BestSucc = getFirstUnplacedBlock(Chain, PrevUnplacedBlockInFilterIt,
1903 BestSucc = getFirstUnplacedBlock(Chain, PrevUnplacedBlockIt);
1914 repeatedlyTailDuplicateBlock(BestSucc, BB, LoopHeaderBB, Chain,
1918 // it out, just go round the loop again with BB as the chain end.
1931 Chain.merge(BestSucc, &SuccChain);
1932 BB = *std::prev(Chain.end());
1935 LLVM_DEBUG(dbgs() << "Finished forming chain for header block "
1936 << getBlockName(*Chain.begin()) << "\n");
1987 // Succ should not be in any chain, or it is the head of some chain.
2218 // header has be pre-merged into a chain due to predecessors not having
2238 BlockChain &Chain = *BlockToChain[MBB];
2239 // Ensure that this block is at the end of a chain; otherwise it could be
2241 if (MBB != *std::prev(Chain.end()))
2257 // Don't split chains, either this chain or the successor's chain.
2258 if (&Chain == &SuccChain) {
2260 << getBlockName(Succ) << " (chain conflict)\n");
2347 // Succ should not be in any chain, or it is the head of some chain.
2362 /// Once we have built a chain, try to rotate it to line up the hot exit block
2376 // If ExitingBB is already the last one in a chain then nothing to do.
2413 // Let's consider an example. We have a built chain of basic blocks
2444 /// opportunities when rotating a loop chain and select the best rotation.
2451 /// first BB in the loop chain.
2478 // chain head is not the loop header. As we only consider natural loops with
2499 // edge from the tail of the loop chain.
2517 // In this loop we iterate every block in the loop chain and calculate the
2518 // cost assuming the block is the head of the loop chain. When the loop ends,
2519 // we should have found the best candidate as the loop chain's head.
2523 // TailIter is used to track the tail of the loop chain if the block we are
2524 // checking (pointed by Iter) is the head of the chain.
2540 // except the one from the chain tail.
2546 // of the loop chain. Here we need to consider three cases:
2552 // chain is not its CFG successor. Note that the more frequently executed
2555 // of the edge to the chain head, then the cost will be
2612 // don't add it to the loop chain. If there are outer loops, then this block
2613 // will be merged into the first outer loop chain for which this block is not
2629 BlockChain *Chain = BlockToChain[LoopBB];
2630 for (MachineBasicBlock *ChainBB : *Chain)
2688 // walk the blocks, and use a set to prevent visiting a particular chain
2710 dbgs() << "Loop chain contains a block without its preds placed!\n"
2712 << " Chain header: " << getBlockName(*LoopChain.begin()) << "\n";
2720 dbgs() << "Loop chain contains a block not contained by the loop!\n"
2722 << " Chain header: " << getBlockName(*LoopChain.begin()) << "\n"
2730 dbgs() << "Loop contains blocks never placed into a chain!\n"
2732 << " Chain header: " << getBlockName(*LoopChain.begin()) << "\n"
2743 // Ensure that every BB in the function has an associated chain to simplify
2749 BlockChain *Chain =
2767 Chain->merge(NextBB, nullptr);
2782 "BlockWorkList should be empty before building final chain.");
2784 "EHPadWorkList should be empty before building final chain.");
2806 dbgs() << "Function chain contains a block not in the function!\n"
2813 dbgs() << "Function contains blocks never placed into a chain!\n"
2837 LLVM_DEBUG(dbgs() << (ChainBB == *FunctionChain.begin() ? "Placing chain "
2911 // Now that all the basic blocks in the chain have the proper layout,
2959 // Empty chain.
3087 /// it was duplicated into its chain predecessor and removed.
3091 /// Updated to be the chain end if LPred is removed.
3092 /// \p Chain - Chain to which \p LPred belongs, and \p BB will belong.
3103 const MachineBasicBlock *LoopHeaderBB, BlockChain &Chain,
3109 BB, LPred, Chain, BlockFilter, PrevUnplacedBlockIt,
3120 // The removal callback causes Chain.end() to be updated when a block is
3121 // removed. On the first pass through the loop, the chain end should be the
3123 // duplicating the block at the end of the chain, if it is removed the
3124 // chain will have shrunk by one block.
3125 BlockChain::iterator ChainEnd = Chain.end();
3128 if (ChainEnd == Chain.begin())
3132 DupBB, DupPred, Chain, BlockFilter, PrevUnplacedBlockIt,
3136 // removed, markChainSuccessors won't be called for its chain. Instead we
3140 LPred = *std::prev(Chain.end());
3142 markBlockSuccessors(Chain, LPred, LoopHeaderBB, BlockFilter);
3149 /// \p Chain - Chain to which \p LPred belongs, and \p BB will belong.
3160 MachineBasicBlock *BB, MachineBasicBlock *LPred, BlockChain &Chain,
3180 // Remove from the Chain and Chain Map
3182 BlockChain *Chain = It->second;
3183 InWorkList = Chain->UnscheduledPredecessors == 0;
3184 Chain->remove(RemBB);
3258 PredChain == &Chain)
3264 if (NewChain != &Chain && NewChain != PredChain)
3766 continue; // Ignore head of the chain