爬上来更新一下：
这个问题可以抽象成点着色问题，用SAT来解决。程序的每个变量对应抽象图中的一个顶点。如果两个变量的声明周期有overlap,我们就用一条边把它们的顶点连起来。然后做点着色，看最少用多少种颜色可以把这个图给涂了（要求每条边的两个顶点的颜色必须不同）。

这个问题的进一步扩展是：如果一个C程序，假设已知malloc/free将如何被调用，如何设计一个内存分配器使得peak memory usage最小。这个时候就需要考虑内存碎片的问题，如何让浪费的内存最少。这个在研究里称为Compile time memory allocation（CMA） problem，或者Dynamic Storage Allocation (DSA) problem。都有成熟但非最优的算法。
--
FROM 107.139.34.*