Lines Matching defs:Chain
23 // first time it reaches a chain of basic blocks, it schedules them in the
57 /// \brief Type for our function-wide basic block -> block chain mapping.
62 /// \brief A chain of blocks which will be laid out contiguously.
64 /// This is the datastructure representing a chain of consecutive blocks that
66 /// probabilities and code locality. We also can use a block chain to represent
71 /// them. They participate in a block-to-chain mapping, which is updated
74 /// \brief The sequence of blocks belonging to this chain.
76 /// This is the sequence of blocks for a particular chain. These will be laid
80 /// \brief A handle to the function-wide basic block to block chain mapping.
82 /// This is retained in each block chain to simplify the computation of child
91 /// This builds a new block chain representing a single basic block in the
92 /// function. It also registers itself as the chain that block participates
96 assert(BB && "Cannot create a chain with a null basic block");
100 /// \brief Iterator over blocks within the chain.
103 /// \brief Beginning of blocks within the chain.
106 /// \brief End of blocks within the chain.
109 /// \brief Merge a block chain into this one.
111 /// This routine merges a block chain into this one. It takes care of forming
113 /// updating the block -> chain mapping. It does not free or tear down the
114 /// old chain, but the old chain's block list is no longer valid.
115 void merge(MachineBasicBlock *BB, BlockChain *Chain) {
119 // Fast path in case we don't have a chain already.
120 if (!Chain) {
127 assert(BB == *Chain->begin());
128 assert(Chain->begin() != Chain->end());
130 // Update the incoming blocks to point to this chain, and add them to the
131 // chain structure.
132 for (BlockChain::iterator BI = Chain->begin(), BE = Chain->end();
135 assert(BlockToChain[*BI] == Chain && "Incoming blocks not in chain");
141 /// \brief Dump the blocks in this chain.
151 /// in-loop predecessors of this chain.
193 void markChainSuccessors(BlockChain &Chain,
198 BlockChain &Chain,
201 BlockChain &Chain, SmallVectorImpl<MachineBasicBlock *> &WorkList,
208 void buildChain(MachineBasicBlock *BB, BlockChain &Chain,
273 /// \brief Mark a chain's successors as having one fewer preds.
275 /// When a chain is being merged into the "placed" chain, this routine will
276 /// quickly walk the successors of each block in the chain and mark them as
278 /// chain which reach the zero-predecessor state to the worklist passed in.
280 BlockChain &Chain,
284 // Walk all the blocks in this chain, marking their successors as having
286 for (BlockChain::iterator CBI = Chain.begin(), CBE = Chain.end();
298 // Disregard edges within a fixed chain, or edges to the loop header.
299 if (&Chain == &SuccChain || *SI == LoopHeaderBB)
302 // This is a cross-chain edge that is within the loop, so decrement the
303 // loop predecessor count of the destination chain.
320 MachineBasicBlock *BB, BlockChain &Chain,
341 if (&SuccChain == &Chain) {
346 DEBUG(dbgs() << " " << getBlockName(*SI) << " -> Mid chain!\n");
370 BlockToChain[*PI] == &Chain)
426 BlockChain &Chain, SmallVectorImpl<MachineBasicBlock *> &WorkList,
433 IsBlockPlaced(Chain, BlockToChain)),
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 = *llvm::prior(Chain.end());
501 assert(BlockToChain[BB] == &Chain);
502 assert(*llvm::prior(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 = *llvm::prior(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 != *llvm::prior(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");
725 /// Once we have built a chain, try to rotate it to line up the hot exit block
803 // walk the blocks, and use a set to prevent visiting a particular chain
811 BlockChain &Chain = *BlockToChain[*BI];
812 if (!UpdatedPreds.insert(&Chain))
815 assert(Chain.LoopPredecessors == 0);
816 for (BlockChain::iterator BCI = Chain.begin(), BCE = Chain.end();
818 assert(BlockToChain[*BCI] == &Chain);
822 if (BlockToChain[*PI] == &Chain || !LoopBlockSet.count(*PI))
824 ++Chain.LoopPredecessors;
828 if (Chain.LoopPredecessors == 0)
829 BlockWorkList.push_back(*Chain.begin());
840 dbgs() << "Loop chain contains a block without its preds placed!\n"
842 << " Chain header: " << getBlockName(*LoopChain.begin()) << "\n";
851 dbgs() << "Loop chain contains a block not contained by the loop!\n"
853 << " Chain header: " << getBlockName(*LoopChain.begin()) << "\n"
863 dbgs() << "Loop contains blocks never placed into a chain!\n"
865 << " Chain header: " << getBlockName(*LoopChain.begin()) << "\n"
873 // Ensure that every BB in the function has an associated chain to simplify
878 BlockChain *Chain
896 Chain->merge(NextBB, 0);
912 BlockChain &Chain = *BlockToChain[BB];
913 if (!UpdatedPreds.insert(&Chain))
916 assert(Chain.LoopPredecessors == 0);
917 for (BlockChain::iterator BCI = Chain.begin(), BCE = Chain.end();
919 assert(BlockToChain[*BCI] == &Chain);
923 if (BlockToChain[*PI] == &Chain)
925 ++Chain.LoopPredecessors;
929 if (Chain.LoopPredecessors == 0)
930 BlockWorkList.push_back(*Chain.begin());
949 dbgs() << "Function chain contains a block not in the function!\n"
958 dbgs() << "Function contains blocks never placed into a chain!\n"
969 DEBUG(dbgs() << (BI == FunctionChain.begin() ? "Placing chain "
1023 return; // Empty chain.
