一个编译优化问题：怎么让一段basic block的存储空间使用最优？

水木社区手机版

主题:一个编译优化问题：怎么让一段basic block的存储空间使用最优？
楼主|snnn|2022-01-11 10:25:36|只看此ID
首先我们只考虑简单代码块，就是一段代码片段，它不含有if/else/for/jump等任何跳转指令，不管是条件跳转但是非条件跳转。
比如下面这样的代码：
int a=3,b=4,c=5;
a = b+3;
c = a+1;
...

那么我们可以计算每个变量最后一次被读引用的位置（行号），然后从此之后，该变量所使用的空间（栈或者寄存器）就可以被其它的变量复用。这个算法实现起来也比较简单。

但是，如果我们允许编译器调整语句顺序（re-ordering)，条件是不影响正确性。那么我们怎么找出哪种排序下可以最大化的重用存储空间呢？除了brute force列出所有排序并挨个挨个试，有其它更好的解法吗？我觉得至少可以把原始的代码分成更小的子块来枚举，有的子块只有一种可能性。

有什么paper吗？
--
FROM 107.139.34.*
1楼|BigCarrot|2022-01-11 15:54:34|只看此ID
你这个就是instruction scheduling 对RA的影响
说老实话真的没有非常好的系统化的解决方法

llvm上的做法是在schedule的时候同时跟踪寄存器压力,每次选择下一条指令时,检查
所有待选指令对寄存器压力的影响,尽量避免寄存器压力超过物理寄存器数目

【在 snnn (cm) 的大作中提到: 】
: 首先我们只考虑简单代码块，就是一段代码片段，它不含有if/else/for/jump等任何跳转指令，不管是条件跳转但是非条件跳转。
: 比如下面这样的代码：
: int a=3,b=4,c=5;
: ...................
--
FROM 104.133.8.*
2楼|snnn|2022-01-31 10:20:43|只看此ID
爬上来更新一下：
这个问题可以抽象成点着色问题，用SAT来解决。程序的每个变量对应抽象图中的一个顶点。如果两个变量的声明周期有overlap,我们就用一条边把它们的顶点连起来。然后做点着色，看最少用多少种颜色可以把这个图给涂了（要求每条边的两个顶点的颜色必须不同）。

这个问题的进一步扩展是：如果一个C程序，假设已知malloc/free将如何被调用，如何设计一个内存分配器使得peak memory usage最小。这个时候就需要考虑内存碎片的问题，如何让浪费的内存最少。这个在研究里称为Compile time memory allocation（CMA） problem，或者Dynamic Storage Allocation (DSA) problem。都有成熟但非最优的算法。
--
FROM 107.139.34.*
3楼|BigCarrot|2022-01-31 12:58:06|只看此ID
【在 snnn (cm) 的大作中提到: 】
: 标题: Re: 一个编译优化问题：怎么让一段basic block的存储空间使用最
: 发信站: 水木社区 (Mon Jan 31 10:20:43 2022), 站内
:
: 爬上来更新一下：
: 这个问题可以抽象成点着色问题，用SAT来解决。程序的每个变量对应抽象图中的一个顶点。如果两个变量的声明周期有overlap,我们就用一条边把它们的顶点连起来。然后做点着色，看最少用多少种颜色可以把这个图给涂了（要求每条边的两个顶点的颜色必须不同）。
这个是寄存器分配的问题解法,和你顶楼的问题不太一样,你原来的问题是要考虑指令调度对寄存器分配的影响
:
: 这个问题的进一步扩展是：如果一个C程序，假设已知malloc/free将如何被调用，如何设计一个内存分配器使得peak memory usage最小。这个时候就需要考虑内存碎片的问题，如何让浪费的内存最少。这个在研究里称为Compile time memory allocation（CMA） problem，或者Dynamic Storage Allocation (DSA) problem。都有成熟但非最优的算法。
你这个假设的条件太强了,在这个前提下,大多数程序直接用静态分配的内存就可以了

: --
:
: ※ 来源:·水木社区 http://www.mysmth.net·[FROM: 107.139.34.*]
--
FROM 104.133.8.*