Improving performance by branch reordering Export

@inproceedings{citeulike:6077778, abstract = {The conditional branch has long been considered an expensive operation. The relative cost of conditional branches has increased as recently designed machines are now relying on deeper pipelines and higher multiple issue. Reducing the number of conditional branches executed can often result in a substantial performance benefit. This paper describes a code-improving transformation to reorder sequences of conditional branches. First, sequences of branches that can be reordered are detected in the control flow. Second, profiling information is collected to predict the probability that each branch will transfer control out of the sequence. Third, the cost of performing each conditional branch is estimated. Fourth, the most beneficial ordering of the branches based on the estimated probability and cost is selected. The most beneficial ordering often included the insertion of additional conditional branches that did not previously exist in the sequence. Finally, the control flow is restructured to refflect the new ordering. The results of applying the transformation were significant reductions in the dynamic number of instructions and branches, as well as decreases in execution time.}, address = {New York, NY, USA}, author = {Yang, Minghui and Uh, Gang R. and Whalley, David B.}, booktitle = {PLDI '98: Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation}, citeulike-article-id = {6077778}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=277650.277711}, citeulike-linkout-1 = {http://dx.doi.org/10.1145/277650.277711}, comment = {PLDIr\#2で読んだ。}, doi = {10.1145/277650.277711}, isbn = {0-89791-987-4}, keywords = {optimization}, location = {Montreal, Quebec, Canada}, pages = {130--141}, posted-at = {2009-11-06 00:01:22}, priority = {0}, publisher = {ACM}, title = {Improving performance by branch reordering}, url = {http://dx.doi.org/10.1145/277650.277711}, year = {1998} }

TY - CONF ID - citeulike:6077778 L3 - citeulike-article-id:6077778 N2 - The conditional branch has long been considered an expensive operation. The relative cost of conditional branches has increased as recently designed machines are now relying on deeper pipelines and higher multiple issue. Reducing the number of conditional branches executed can often result in a substantial performance benefit. This paper describes a code-improving transformation to reorder sequences of conditional branches. First, sequences of branches that can be reordered are detected in the control flow. Second, profiling information is collected to predict the probability that each branch will transfer control out of the sequence. Third, the cost of performing each conditional branch is estimated. Fourth, the most beneficial ordering of the branches based on the estimated probability and cost is selected. The most beneficial ordering often included the insertion of additional conditional branches that did not previously exist in the sequence. Finally, the control flow is restructured to refflect the new ordering. The results of applying the transformation were significant reductions in the dynamic number of instructions and branches, as well as decreases in execution time. CY - Montreal, Quebec, Canada SN - 0-89791-987-4 AD - New York, NY, USA EP - 141 TI - Improving performance by branch reordering PB - ACM T2 - PLDI '98: Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation SP - 130 KW - optimization N1 - PLDIr#2で読んだ。 AU - Yang, Minghui AU - Uh, Gang AU - Whalley, David PY - 1998/// UR - http://dx.doi.org/10.1145/277650.277711 ER -