Home > Research > Publications & Outputs > Function Merging by Sequence Alignment

Electronic data

  • cgo19

    Accepted author manuscript, 857 KB, PDF document

    Available under license: CC BY: Creative Commons Attribution 4.0 International License

Links

View graph of relations

Function Merging by Sequence Alignment

Research output: Contribution in Book/Report/Proceedings - With ISBN/ISSNConference contribution/Paper

Published

Standard

Function Merging by Sequence Alignment. / Rocha, Rodrigo; Petoumenos, Pavlos ; Wang, Zheng; Cole, Murray; Leather, Hugh.

ACM/IEEE International Symposium on Code Generation and Optimization (CGO) 2019. ACM, 2019. p. 149-163.

Research output: Contribution in Book/Report/Proceedings - With ISBN/ISSNConference contribution/Paper

Harvard

Rocha, R, Petoumenos, P, Wang, Z, Cole, M & Leather, H 2019, Function Merging by Sequence Alignment. in ACM/IEEE International Symposium on Code Generation and Optimization (CGO) 2019. ACM, pp. 149-163, 2019 IEEE/ACM International Symposium on Code Generation and Optimization, Washington, United States, 16/02/19. <https://dl.acm.org/citation.cfm?id=3314892>

APA

Rocha, R., Petoumenos, P., Wang, Z., Cole, M., & Leather, H. (2019). Function Merging by Sequence Alignment. In ACM/IEEE International Symposium on Code Generation and Optimization (CGO) 2019 (pp. 149-163). ACM. https://dl.acm.org/citation.cfm?id=3314892

Vancouver

Rocha R, Petoumenos P, Wang Z, Cole M, Leather H. Function Merging by Sequence Alignment. In ACM/IEEE International Symposium on Code Generation and Optimization (CGO) 2019. ACM. 2019. p. 149-163

Author

Rocha, Rodrigo ; Petoumenos, Pavlos ; Wang, Zheng ; Cole, Murray ; Leather, Hugh. / Function Merging by Sequence Alignment. ACM/IEEE International Symposium on Code Generation and Optimization (CGO) 2019. ACM, 2019. pp. 149-163

Bibtex

@inproceedings{c1260d1489344f5ba1801baa4969c325,
title = "Function Merging by Sequence Alignment",
abstract = "Resource-constrained devices for embedded systems are becoming increasingly important. In such systems, memory is highly restrictive, making code size in most cases even more important than performance. Compared to more traditional platforms, memory is a larger part of the cost and code occupies much of it. Despite that, compilers make little effort to reduce code size. One key technique attempts to merge the bodies of similar functions. However, production compilers only apply this optimization to identical functions, while research compilers improve on that by merging the few functions with identical control-flow graphs and signatures. Overall, existing solutions are insufficient and we end up having to either increase cost by adding more memory or remove functionality from programs.We introduce a novel technique that can merge arbitrary functions through sequence alignment, a bioinformatics algorithm for identifying regions of similarity between sequences. We combine this technique with an intelligent exploration mechanism to direct the search towards the most promising function pairs. Our approach is more than 2.4x better than the state-of-the-art, reducing code size by up to 25%, with an overall average of 6%, while introducing an average compilation-time overhead of only 15%. When aided by profiling information, this optimization can be deployed without any significant impact on the performance of the generated code.",
author = "Rodrigo Rocha and Pavlos Petoumenos and Zheng Wang and Murray Cole and Hugh Leather",
year = "2019",
month = feb,
day = "16",
language = "English",
isbn = "9781728114361",
pages = "149--163",
booktitle = "ACM/IEEE International Symposium on Code Generation and Optimization (CGO) 2019",
publisher = "ACM",
note = "2019 IEEE/ACM International Symposium on Code Generation and Optimization, CGO 2019 ; Conference date: 16-02-2019 Through 20-02-2019",

}

RIS

TY - GEN

T1 - Function Merging by Sequence Alignment

AU - Rocha, Rodrigo

AU - Petoumenos, Pavlos

AU - Wang, Zheng

AU - Cole, Murray

AU - Leather, Hugh

PY - 2019/2/16

Y1 - 2019/2/16

N2 - Resource-constrained devices for embedded systems are becoming increasingly important. In such systems, memory is highly restrictive, making code size in most cases even more important than performance. Compared to more traditional platforms, memory is a larger part of the cost and code occupies much of it. Despite that, compilers make little effort to reduce code size. One key technique attempts to merge the bodies of similar functions. However, production compilers only apply this optimization to identical functions, while research compilers improve on that by merging the few functions with identical control-flow graphs and signatures. Overall, existing solutions are insufficient and we end up having to either increase cost by adding more memory or remove functionality from programs.We introduce a novel technique that can merge arbitrary functions through sequence alignment, a bioinformatics algorithm for identifying regions of similarity between sequences. We combine this technique with an intelligent exploration mechanism to direct the search towards the most promising function pairs. Our approach is more than 2.4x better than the state-of-the-art, reducing code size by up to 25%, with an overall average of 6%, while introducing an average compilation-time overhead of only 15%. When aided by profiling information, this optimization can be deployed without any significant impact on the performance of the generated code.

AB - Resource-constrained devices for embedded systems are becoming increasingly important. In such systems, memory is highly restrictive, making code size in most cases even more important than performance. Compared to more traditional platforms, memory is a larger part of the cost and code occupies much of it. Despite that, compilers make little effort to reduce code size. One key technique attempts to merge the bodies of similar functions. However, production compilers only apply this optimization to identical functions, while research compilers improve on that by merging the few functions with identical control-flow graphs and signatures. Overall, existing solutions are insufficient and we end up having to either increase cost by adding more memory or remove functionality from programs.We introduce a novel technique that can merge arbitrary functions through sequence alignment, a bioinformatics algorithm for identifying regions of similarity between sequences. We combine this technique with an intelligent exploration mechanism to direct the search towards the most promising function pairs. Our approach is more than 2.4x better than the state-of-the-art, reducing code size by up to 25%, with an overall average of 6%, while introducing an average compilation-time overhead of only 15%. When aided by profiling information, this optimization can be deployed without any significant impact on the performance of the generated code.

M3 - Conference contribution/Paper

SN - 9781728114361

SP - 149

EP - 163

BT - ACM/IEEE International Symposium on Code Generation and Optimization (CGO) 2019

PB - ACM

T2 - 2019 IEEE/ACM International Symposium on Code Generation and Optimization

Y2 - 16 February 2019 through 20 February 2019

ER -