一句话：提出 Scout，通过约束分配大小与对齐实现单次内存访问的运行时指针消歧，解锁被编译器错过的循环优化。
上下文敏感的过程间别名分析更精确但难以扩展，因此生产编译器常采用过程内别名分析，牺牲精度并损害循环优化。已有动态检查方案开销为 O(log n) 或仅适用于受限循环。本文提出 Scout，通过在内存分配时约束分配大小与对齐，实现用单次内存访问在运行时消歧两个指针，并能处理现有 O(1) 范围检查无法覆盖的循环内数组访问。Scout 还利用静态优化反馈减少动态检查数量。该技术为循环不变量代码外提、死存储消除、循环向量化和加载消除创造机会。评估显示，在已优化代码上 Polybench 提升最高 51.11%，CPU SPEC 2017 最高 0.89%；分配器 CPU/内存开销几何平均分别为 1.05%/7.47% 和 0.21%/0.13%。
Context-sensitive inter-procedural alias analyses are more precise than intra-procedural alias analyses. However, context-sensitive inter-procedural alias analyses are not scalable. As a consequence, most of the production compilers sacrifice precision for scalability and implement intra-procedural alias analysis. The alias analysis is used by many compiler optimizations, including loop transformations. Due to the imprecision of alias analysis, the program’s performance may suffer, especially in the presence of loops. Previous work proposed a general approach based on code-versioning with dynamic checks to disambiguate pointers at runtime. However, the overhead of dynamic checks in this approach is O(log n), which is substantially high to enable interesting optimizations. Other suggested approaches, e.g., polyhedral and symbolic range analysis, have O(1) overheads, but they only work for loops with certain constraints. The production compilers, such as LLVM and GCC, use scalar evolution analysis to compute an O(1) range check for loops to resolve memory dependencies at runtime. However, this approach also can only be applied to loops with certain constraints. In this work, we present our tool, Scout, that can disambiguate two pointers at runtime using single memory access. Scout is based on the key idea to constrain the allocation size and alignment during memory allocations. Scout can also disambiguate array accesses within a loop for which the existing O(1) range checks technique cannot be applied. In addition, Scout uses feedback from static optimizations to reduce the number of dynamic checks needed for optimizations. Our technique enabled new opportunities for loop-invariant code motion, dead store elimination, loop vectorization, and load elimination in an already optimized code. Our performance improvements are up to 51.11% for Polybench and up to 0.89% for CPU SPEC 2017 suites. The geometric means for our allocator’s CPU and memory overheads for CPU SPEC 2017 benchmarks are 1.05%, and 7.47%, respectively. For Polybench benchmarks, the geometric mean of CPU and memory overheads are 0.21% and 0.13%, respectively.
@article{paperbot1455,
title = {The road not taken: exploring alias analysis based optimizations missed by the compiler},
author = {Khushboo Chitre and Piyus Kedia and Rahul Purandare},
journal = {Proceedings of the ACM on Programming Languages},
volume = {6},
number = {OOPSLA2},
year = {2022},
doi = {10.1145/3563316}
}