12 // The algorithm tries to find a layout of nodes (basic blocks) of a given CFG
15 // frequently executed nodes together. The name follows the underlying
259 /// An arc in the graph, typically corresponding to a jump between two nodes.
281 /// A chain (ordered sequence) of nodes in the graph.
290         Nodes(1, Node) {}  in ChainT()
292   size_t numBlocks() const { return Nodes.size(); }  in numBlocks()
296   bool isEntry() const { return Nodes[0]->Index == 0; }  in isEntry()
299     for (NodeT *Node : Nodes) {  in isCold()
330     Nodes = std::move(MergedBlocks);  in merge()
334     Id = Nodes[0]->Index;  in merge()
336     for (size_t Idx = 0; Idx < Nodes.size(); Idx++) {  in merge()
337       Nodes[Idx]->CurChain = this;  in merge()
338       Nodes[Idx]->CurIndex = Idx;  in merge()
345     Nodes.clear();  in clear()
346     Nodes.shrink_to_fit();  in clear()
360   // Nodes of the chain.
361   std::vector<NodeT *> Nodes;  member
367 /// When nodes are merged into chains, the edges are combined too so that
495 /// A wrapper around three concatenated vectors (chains) of nodes; it is used
556 /// Merge two chains of nodes respecting a given 'type' and 'offset'.
597   /// Run the algorithm and return an optimized ordering of nodes.
599     // Pass 1: Merge nodes with their mutually forced successors  in run()
605     // Pass 3: Merge cold nodes to reduce code size  in run()
608     // Collect nodes from all chains  in run()
617     // Initialize nodes.  in initialize()
628     // Initialize jumps between the nodes.  in initialize()
690   /// For a pair of nodes, A and B, node B is the forced successor of A,
692   /// to B are from A. Such nodes should be adjacent in the optimal ordering;
693   /// the method finds and merges such pairs of nodes.
727     // Merge nodes with their fallthrough successors.  in mergeForcedPairs()
803   /// Merge remaining nodes into chains w/o taking jump counts into
816             SrcChain->Nodes.back()->Index == SrcBB &&  in mergeColdChains()
817             DstChain->Nodes.front()->Index == DstBB &&  in mergeColdChains()
826   double extTSPScore(const MergedNodesT &Nodes,  in extTSPScore()  argument
829     Nodes.forEach([&](const NodeT *Node) {  in extTSPScore()
869       if (Offset == 0 || Offset == ChainPred->Nodes.size())  in getBestMergeGain()
872       NodeT *Node = ChainPred->Nodes[Offset - 1];  in getBestMergeGain()
888     for (JumpT *Jump : ChainSucc->Nodes.front()->InJumps) {  in getBestMergeGain()
897     for (JumpT *Jump : ChainSucc->Nodes.back()->OutJumps) {  in getBestMergeGain()
906     if (ChainPred->Nodes.size() <= ChainSplitThreshold) {  in getBestMergeGain()
907       for (size_t Offset = 1; Offset < ChainPred->Nodes.size(); Offset++) {  in getBestMergeGain()
911         const NodeT *BB = ChainPred->Nodes[Offset - 1];  in getBestMergeGain()
912         const NodeT *BB2 = ChainPred->Nodes[Offset];  in getBestMergeGain()
935         mergeNodes(ChainPred->Nodes, ChainSucc->Nodes, MergeOffset, MergeType);  in computeMergeGain()
954     // Merge the nodes.  in mergeChains()
956         mergeNodes(Into->Nodes, From->Nodes, MergeOffset, MergeType);  in mergeChains()
966       MergedNodes = MergedNodesT(Into->Nodes.begin(), Into->Nodes.end());  in mergeChains()
984       if (!Chain.Nodes.empty())  in concatChains()
1000     // Collect the nodes in the order specified by their chains.  in concatChains()
1004       for (NodeT *Node : Chain->Nodes)  in concatChains()
1010   /// The number of nodes in the graph.
1019   /// All nodes (basic blocks) in the graph.
1022   /// All jumps between the nodes.
1025   /// All chains of nodes.
1051     // Collect nodes from all the chains.  in run()
1061     // Initialize nodes.  in initialize()
1072     // Initialize jumps between the nodes.  in initialize()
1253     // This doesn't depend on the ordering of the nodes  in computeMergeGain()
1259         mergeNodes(ChainPred->Nodes, ChainSucc->Nodes, MergeOffset, MergeType);  in computeMergeGain()
1302   double distBasedLocalityGain(const MergedNodesT &Nodes,  in distBasedLocalityGain()  argument
1305     Nodes.forEach([&](const NodeT *Node) {  in distBasedLocalityGain()
1327     // Merge the nodes.  in mergeChains()
1329         mergeNodes(Into->Nodes, From->Nodes, MergeOffset, MergeType);  in mergeChains()
1343       if (!Chain.Nodes.empty()) {  in concatChains()
1348         for (NodeT *Node : Chain.Nodes) {  in concatChains()
1367     // Collect the nodes in the order specified by their chains.  in concatChains()
1371       for (NodeT *Node : Chain->Nodes)  in concatChains()
1380   /// The number of nodes in the graph.
1389   /// All nodes (functions) in the graph.
1392   /// All jumps (function calls) between the nodes.
1395   /// All chains of nodes.
1404   /// The total size of the nodes in the graph.