Function Merging by Sequence Alignment
Function Merging by Sequence Alignment
复制标题
DOI：
10.5555/3314872.3314892
复制
发表时间：
2019-02
期刊：
影响因子：
--
通讯作者：
Rodrigo C. O. Rocha;Pavlos Petoumenos;Zheng Wang;M. Cole;Hugh Leather
中科院分区：
文献类型：
--
作者：
Rodrigo C. O. Rocha;Pavlos Petoumenos;Zheng Wang;M. Cole;Hugh Leather
嵌入式系统中资源受限的设备正变得越来越重要。在这样的系统中，内存是高度受限的，使得代码大小在大多数情况下比性能更重要。与更传统的平台相比，内存占成本的很大一部分，而代码占据了其中的大部分。尽管如此，编译器很少努力减少代码大小。一项关键技术试图合并功能相似的主体。然而，生产编译器只将这种优化应用于相同的函数，而研究编译器通过合并具有相同控制流图和签名的少数函数来改进这一点。总的来说，现有的解决方案是不够的，我们最终不得不通过增加更多内存来增加成本，或者从程序中删除功能。我们介绍了一种新的技术，可以合并任意功能通过序列比对，生物信息学算法识别序列之间的相似性区域。我们将此技术与智能探索机制相结合，以指导对最有希望的函数对的搜索。我们的方法比最先进的方法好2.4倍以上，将代码大小减少了25%，总体平均减少了6%，而平均编译时间开销仅为15%。在分析信息的帮助下，可以部署这种优化，而不会对生成的代码的性能产生任何重大影响。
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.