Lines Matching defs:Chain
23 // first time it reaches a chain of basic blocks, it schedules them in the
71 /// \brief Type for our function-wide basic block -> block chain mapping.
76 /// \brief A chain of blocks which will be laid out contiguously.
78 /// This is the datastructure representing a chain of consecutive blocks that
80 /// probabilities and code locality. We also can use a block chain to represent
85 /// them. They participate in a block-to-chain mapping, which is updated
88 /// \brief The sequence of blocks belonging to this chain.
90 /// This is the sequence of blocks for a particular chain. These will be laid
94 /// \brief A handle to the function-wide basic block to block chain mapping.
96 /// This is retained in each block chain to simplify the computation of child
105 /// This builds a new block chain representing a single basic block in the
106 /// function. It also registers itself as the chain that block participates
110 assert(BB && "Cannot create a chain with a null basic block");
114 /// \brief Iterator over blocks within the chain.
117 /// \brief Beginning of blocks within the chain.
120 /// \brief End of blocks within the chain.
123 /// \brief Merge a block chain into this one.
125 /// This routine merges a block chain into this one. It takes care of forming
127 /// updating the block -> chain mapping. It does not free or tear down the
128 /// old chain, but the old chain's block list is no longer valid.
129 void merge(MachineBasicBlock *BB, BlockChain *Chain) {
133 // Fast path in case we don't have a chain already.
134 if (!Chain) {
141 assert(BB == *Chain->begin());
142 assert(Chain->begin() != Chain->end());
144 // Update the incoming blocks to point to this chain, and add them to the
145 // chain structure.
146 for (BlockChain::iterator BI = Chain->begin(), BE = Chain->end();
149 assert(BlockToChain[*BI] == Chain && "Incoming blocks not in chain");
155 /// \brief Dump the blocks in this chain.
165 /// in-loop predecessors of this chain.
207 void markChainSuccessors(BlockChain &Chain,
212 BlockChain &Chain,
215 BlockChain &Chain, SmallVectorImpl<MachineBasicBlock *> &WorkList,
222 void buildChain(MachineBasicBlock *BB, BlockChain &Chain,
287 /// \brief Mark a chain's successors as having one fewer preds.
289 /// When a chain is being merged into the "placed" chain, this routine will
290 /// quickly walk the successors of each block in the chain and mark them as
292 /// chain which reach the zero-predecessor state to the worklist passed in.
294 BlockChain &Chain,
298 // Walk all the blocks in this chain, marking their successors as having
300 for (BlockChain::iterator CBI = Chain.begin(), CBE = Chain.end();
312 // Disregard edges within a fixed chain, or edges to the loop header.
313 if (&Chain == &SuccChain || *SI == LoopHeaderBB)
316 // This is a cross-chain edge that is within the loop, so decrement the
317 // loop predecessor count of the destination chain.
334 MachineBasicBlock *BB, BlockChain &Chain,
355 if (&SuccChain == &Chain) {
360 DEBUG(dbgs() << " " << getBlockName(*SI) << " -> Mid chain!\n");
385 BlockToChain[*PI] == &Chain)
424 BlockChain &Chain, SmallVectorImpl<MachineBasicBlock *> &WorkList,
432 return BlockToChain.lookup(BB) == &Chain;
442 if (&SuccChain == &Chain) {
463 /// all of the basic blocks and form a chain due to unnatural loops in the CFG.
477 // Now select the head of the chain to which the unplaced block belongs
478 // as the block to place. This will force the entire chain to be placed,
488 BlockChain &Chain,
492 assert(BlockToChain[BB] == &Chain);
497 markChainSuccessors(Chain, LoopHeaderBB, BlockWorkList, BlockFilter);
498 BB = *std::prev(Chain.end());
501 assert(BlockToChain[BB] == &Chain);
502 assert(*std::prev(Chain.end()) == BB);
506 MachineBasicBlock *BestSucc = selectBestSuccessor(BB, Chain, BlockFilter);
512 BestSucc = selectBestCandidateBlock(Chain, BlockWorkList, BlockFilter);
515 BestSucc = getFirstUnplacedBlock(F, Chain, PrevUnplacedBlockIt,
532 Chain.merge(BestSucc, &SuccChain);
533 BB = *std::prev(Chain.end());
536 DEBUG(dbgs() << "Finished forming chain for header block "
537 << getBlockNum(*Chain.begin()) << "\n");
613 // header has be pre-merged into a chain due to predecessors not having
635 BlockChain &Chain = *BlockToChain[*I];
636 // Ensure that this block is at the end of a chain; otherwise it could be
638 if (*I != *std::prev(Chain.end()))
661 // Don't split chains, either this chain or the successor's chain.
662 if (&Chain == &SuccChain) {
664 << getBlockName(*SI) << " (chain conflict)\n");
728 /// Once we have built a chain, try to rotate it to line up the hot exit block
806 // walk the blocks, and use a set to prevent visiting a particular chain
814 BlockChain &Chain = *BlockToChain[*BI];
815 if (!UpdatedPreds.insert(&Chain))
818 assert(Chain.LoopPredecessors == 0);
819 for (BlockChain::iterator BCI = Chain.begin(), BCE = Chain.end();
821 assert(BlockToChain[*BCI] == &Chain);
825 if (BlockToChain[*PI] == &Chain || !LoopBlockSet.count(*PI))
827 ++Chain.LoopPredecessors;
831 if (Chain.LoopPredecessors == 0)
832 BlockWorkList.push_back(*Chain.begin());
843 dbgs() << "Loop chain contains a block without its preds placed!\n"
845 << " Chain header: " << getBlockName(*LoopChain.begin()) << "\n";
854 dbgs() << "Loop chain contains a block not contained by the loop!\n"
856 << " Chain header: " << getBlockName(*LoopChain.begin()) << "\n"
866 dbgs() << "Loop contains blocks never placed into a chain!\n"
868 << " Chain header: " << getBlockName(*LoopChain.begin()) << "\n"
876 // Ensure that every BB in the function has an associated chain to simplify
881 BlockChain *Chain
899 Chain->merge(NextBB, nullptr);
915 BlockChain &Chain = *BlockToChain[BB];
916 if (!UpdatedPreds.insert(&Chain))
919 assert(Chain.LoopPredecessors == 0);
920 for (BlockChain::iterator BCI = Chain.begin(), BCE = Chain.end();
922 assert(BlockToChain[*BCI] == &Chain);
926 if (BlockToChain[*PI] == &Chain)
928 ++Chain.LoopPredecessors;
932 if (Chain.LoopPredecessors == 0)
933 BlockWorkList.push_back(*Chain.begin());
954 dbgs() << "Function chain contains a block not in the function!\n"
963 dbgs() << "Function contains blocks never placed into a chain!\n"
974 DEBUG(dbgs() << (BI == FunctionChain.begin() ? "Placing chain "
1052 return; // Empty chain.
