en Copyright 2015 Java http://172.16.0.5:8080/history/llvm-project-15.0.7/llvm/test/CodeGen/X86/code_placement_ext_tsp.ll#f573f686 ext-tsp basic block layoutA new basic block ordering improving existing MachineBlockPlacement.The algorithm tries to find a layout of nodes (basic blocks) of a given CFGoptimizing jump locality and thus processor I-cache utilization. This isachieved via increasing the number of fall-through jumps and co-locatingfrequently executed nodes together. The name follows the underlyingoptimization problem, Extended-TSP, which is a generalization of classical(maximum) Traveling Salesmen Problem.The algorithm is a greedy heuristic that works with chains (ordered lists)of basic blocks. Initially all chains are isolated basic blocks. On everyiteration, we pick a pair of chains whose merging yields the biggest increasein the ExtTSP value, which models how i-cache "friendly" a specific chain is.A pair of chains giving the maximum gain is merged into a new chain. Theprocedure stops when there is only one chain left, or when merging does notincrease ExtTSP. In the latter case, the remaining chains are sorted bydensity in decreasing order.An important aspect is the way two chains are merged. Unlike earlieralgorithms (e.g., based on the approach of Pettis-Hansen), twochains, X and Y, are first split into three, X1, X2, and Y. Then weconsider all possible ways of gluing the three chains (e.g., X1YX2, X1X2Y,X2X1Y, X2YX1, YX1X2, YX2X1) and choose the one producing the largest score.This improves the quality of the final result (the search space is larger)while keeping the implementation sufficiently fast.Differential Revision: https://reviews.llvm.org/D113424 List of files: /llvm-project-15.0.7/llvm/test/CodeGen/X86/code_placement_ext_tsp.ll Mon, 08 Nov 2021 15:02:33 +0000 spupyrev <spupyrev@fb.com> http://172.16.0.5:8080/history/llvm-project-15.0.7/llvm/test/CodeGen/X86/code_placement_ext_tsp.ll#c68f71eb ext-tsp basic block layoutA new basic block ordering improving existing MachineBlockPlacement.The algorithm tries to find a layout of nodes (basic blocks) of a given CFGoptimizing jump locality and thus processor I-cache utilization. This isachieved via increasing the number of fall-through jumps and co-locatingfrequently executed nodes together. The name follows the underlyingoptimization problem, Extended-TSP, which is a generalization of classical(maximum) Traveling Salesmen Problem.The algorithm is a greedy heuristic that works with chains (ordered lists)of basic blocks. Initially all chains are isolated basic blocks. On everyiteration, we pick a pair of chains whose merging yields the biggest increasein the ExtTSP value, which models how i-cache "friendly" a specific chain is.A pair of chains giving the maximum gain is merged into a new chain. Theprocedure stops when there is only one chain left, or when merging does notincrease ExtTSP. In the latter case, the remaining chains are sorted bydensity in decreasing order.An important aspect is the way two chains are merged. Unlike earlieralgorithms (e.g., based on the approach of Pettis-Hansen), twochains, X and Y, are first split into three, X1, X2, and Y. Then weconsider all possible ways of gluing the three chains (e.g., X1YX2, X1X2Y,X2X1Y, X2YX1, YX1X2, YX2X1) and choose the one producing the largest score.This improves the quality of the final result (the search space is larger)while keeping the implementation sufficiently fast.Differential Revision: https://reviews.llvm.org/D113424 List of files: /llvm-project-15.0.7/llvm/test/CodeGen/X86/code_placement_ext_tsp.ll Mon, 08 Nov 2021 15:02:33 +0000 spupyrev <spupyrev@fb.com>