前面，读者已经了解了存储分配优化的基本概念，本小节将从实现的角度来详细分析相关细节。无论存储优化算法如何激进，变量访问不冲突是不可逾越的底线，这是编译安全性的保证。下面，笔者只讨论一种特殊的情况，即临时变量的存储优化。

临时变量是由编译器自动产生的，因此，编译器对其的控制力度要远胜于普通变量。针对临时变量的特点，讨论存储优化就简单得多了。在Neo Pascal中，为了便于算法实现，算法讨论的临时变量必须满足如下三个条件：

(1)在整个程序范围内，只能存在一次定值和一次引用。

(2)一次定值和一次引用是在同一个基本块内的。

(3)定值点位于引用点之前。

也就是说，只有满足这三个条件的临时变量才可能进行存储优化。当然，这只是优化之前的一项准备工作而己。那么，这三个条件是否可以被大多数临时变量接受呢？虽然三个条件看似都比较苛刻，但对于许多临时变量来说，却是可以接受的。事实上，现行的IR生成机制所创建的临时变量是非常容易达到这一要求的。在例8-2中，不难发现，除了Tl之外，其他的临时变量都是本优化算法的工作对象。实际上，读者可以尝试更多的例程，能满足这三个条件的临时变量应该超过80%，这样的结果是令人兴奋的。因此，基于这三个条件讨论存储分配优化是具有现实意义的。注意，本小节后续篇幅中不作特殊说明的“变量”都是指满足上述条件的临时变量。下面，就来讨论临时变量存储优化的实现细节。

首先，就来谈谈共享存储区的问题。Neo Pascal并没有设置太多的共享存储区，在通常情况下，每个过程只拥有一个共享存储区。而共享存储区的大小是根据实际使用该共享区的变量的类型而定的，即为各个变量实际容量的最大值。事实上，针对临时变量存储优化的问题设置一个共享存储区是可以接受的。虽然未必能得到最优的分配方案，但应该是工程应用领域可以接受的次优解。而设置一个共享存储区的主要优点就是便于算法实现。

其次，就要收集本过程中可以共享存储区的临时变量。由于本小节涉及的临时变量的定值、引用必定位于同一基本块内，因此，位于不同基本块内且满足条件的临时变量是可以共享存储区的。这里，编译器只需要确定在一个基本块内可共享存储区的临时变量集合即可。假设临时变量集合s的所有元素的定值、引用点都位于同一个基本块内，且它们可以共享同一存储区。如果试图将变量v加入集合s，那么，v必须满足两个条件：

(1)变量v的定值、引用点也必须位于该基本块内。

(2)集合s中的任意变量i都与v不冲突。所谓“冲突”就是指两个变量从定值点到引用点之间的IR所构成的集合的交集为空。

最后，选择临时变量的顺序也是值得关注的。这主要与Neo Pascal的实现有关，因为Neo Pascal只考虑为每个过程分配一个临时变量的共享存储区。在这种情况下，优化的效果与选择临时变量的顺序是密切相关的。例如，己知5个临时变量的定值、引用点如下：

假设选择变量的顺序为(_Tl、_T2、_T3、_T4、_T5)，那么，分析过程如下：

1)清空集合s。

2)_Tl与集合s中的变量不冲突，s={_T1}。

3)_T2与集合s中的_Tl冲突，略过_T2。

4)同理，_T3、_T4与_Tl也是冲突的，同样略过。

5)_T5与集合s中的_Tl不冲突，s={_T1，_T5}。

就本例而言，优化算法确定{_Tl，_T5}，是可以共享存储区的，而其他临时变量则必须独立分配存储区。不过，如果选择变量的顺序为(_T2、_T3、_T4、_T5、_Tl)时，那么，最终得到的s就是{_T2、_T3、_T4、_T5}，。由于临时变量的类型都是基本类型，不同变量所需的存储空间的差异并不明显，因此，后者的方案是较优于前者的。换句话说，两个方案的差别主要就在于集合s中的元素个数。

这里，应用了一个特殊的排序方式，即按每个临时变量的use-def得到的差值由小至大排序。实际上，其目的就是优先选择引用点与定值点较接近的临时变量，只有这样才能尽可能使更多变量加入共享集合中。

下面，就来详细看看Neo Pascal相关源代码的实现。

程序8-3 MemShare.cpp

第3行：声明临时变量集合，即该集合内的临时变量是共享同一存储区的。其中，TmpInfo结构用于描述临时变量的相关信息，声明如下：

【声明8-5】

m_iLink:指向临时变量符号信息的指针，即符号在变量信息表中的位序号。

m_iBlock:指向临时变量所属基本块信息的指针。

m_LiveArea:用于描述临时变量的活跃区域，即临时变量的定值点、引用点信息。由定值点到引用点构成的一个IR序列的区域即为活跃区域。如果两个临时变量的活跃区域存在交集，则表明这两个临时变量是冲突的，也就无法共享同一存储区。LiveArea结构的声明形式如下：

【声明8-6】

第4行：声明基本块冲突映射表。由于本算法并不是以基本块为主线遍历的，因此需要考虑应用Conflict映射表来描述整个过程的临时变量冲突信息。其中，Conflict是以基本块的指针作为关键字，而vector<LiveArea>则用来描述该基本块内己占用的活跃区域。当一个临时变量试图加入共享集合时，必须保证该变量的活跃区域与所属基本块的所有活跃区域都不存在冲突（即活跃区域不存在交集）。

第5行：调用函数完成数据流分析。

第6～26行：以过程为单位，分析共享存储区的临时变量集合。

第8行：获取当前过程的变量集合。

第9～11行：初始化相关数据结构。其中，m_TmpMemShare就是用于描述该过程的共享集合。

第12～26行：遍历变量集合，将满足存储优化基本条件的临时变量加入TmpVar中。

第14～15行：判断是否为临时变量。

第16～17行：判断该临时变量是否只存在一次定值与一次引用。

第19～22行：根据临时变量的定值、引用信息，获取定值、引用点所属的基本块号。

第23行：判断定值、引用点是否位于同一基本块内，定值点的位置是否先于引用点。

第24行：满足上述条件的临时变量就是算法的工作对象，将其加入TmpVar集合。(www.daowen.com)

第27行：对TmpVar集合进行排序，按活跃区域由小至大排列。

第28～61行：依次选择TmpVar集合中的临时变量，将其加入Conflict中，当然，前提就是不发生活跃区域的冲突。

第30行：获得当前临时变量所属的基本块的活跃区域集合。

第31行：判断Conflict中是否存在该基本块的活跃区域集合。

第34～45行：遍历基本块的活跃区域集合，判断是否存在冲突。

第46～51行：如果当前临时变量的定值及引用点都不包含在该基本块所有活跃区域中，即表示不存在任何冲突，则可以将其加入该基本块的活跃区域集合。

第50行：将当前临时变量加入过程m_TmpMemShare集合中。

第54～59行：由于Conflict中不存在关于所属基本块的活跃区域集合的描述信息，则需要重新生成一个活跃区域集合，并将当前临时变量的活跃区域加入该集合。同时，将变量本身加入过程的m_TmpMemShare集合中。

至此，已经得到了一个关于过程的可共享存储区的临时变量集合，这个集合是后续存储优化分配的关键所在。编译器将根据这个集合确定哪些变量需要独立分配空间，而哪些变量则是共享同一片存储区域的，以及决策共享存储区的设置与相关的应用策略。下面，就来看看Neo Pascal是如何根据过程的m_TmpMemShare集合实现优化分配的。结合83节存储分配算法的详细分析，可能更有利于深入理解。

程序8-4 MemoryAlloc.cpp

第3～6行：在存储分配之前，重新计算类型的实际占用空间大小。

第7～10行：初始化所有变量符号的m_iMemoryAlloc属性。在8.3节中，读者应该已经了解了m_iMemoryAlloc属性就是用于存储变量符号相对于本过程数据块的偏移。

第11--23行：遍历IR序列，根据操作数的类别，分析常量的引用情况。

第24～101行：遍历过程信息表，计算变量符号的m_iMemoryAlloc属性。

第26、27行：略过未被调用的过程。

第30～64行：遍历变量信息表，收集需要分配存储空间的变量符号。由于全局用户变量是静态分配的，因此，这里只考虑局部变量及全局临时变量的分配即可，并不涉及全局用户变量的分配。

第32～34行：略过非当前过程的变量符号。

第35、36行：略过全局用户变量符号。

第37～44行：略过没有定值点及引用点的变量符号。

第45、46行：将当前变量加入Tmp向量中。Tmp向量是一个存储分配的辅助结构。

第47～64行：当前变量符号属于m_TmpMemShare集合，则表示该变量是可以分配在共享存储区的。

第49行：iMaxTmp变量用于标识m_TmpMemShare集合中所需存储空间最多的变量。iMaxTmp的初始值就是一1。

第50～62行：如果当前变量是到目前为止占用空间最多的临时变量，则将iMaxTmp指向该变量信息，并设置该变量的m_bMaxTmp属性为true。

第65行：按占用存储空间的大小重排Tmp向量中的变量信息。在讨论存储布局时，笔者已经详细解释了重排变量的意义了。

第70～94行：遍历Tmp向量，计算各变量符号的m_iMemoryAlloc属性。

第72、73行：判断当前变量是否需要分配存储空间。需要分配存储空间的变量必定满足如下两个条件之一：

(1)不属于m_iMemoryAlloc集合，即为不可共享存储区的变量。

(2)是占用空间最多的可共享存储区的临时变量。

第76～84行：整字对齐处理，即根据变量占用的空间大小，计算留白的字节。

第85、86行：如果当前变量是占用空间最多的可共享存储区的临时变量，则使用iMaxTmpOffset变量暂存当前的偏移。

第87行：设置变量符号的m_iMemoryAlloc属性，即相对于过程数据块的偏移值。

第92行：处理可共享存储区的临时变量（不是占用空间最多的临时变量），将变量符号的位序号加入TmpAlloc向量中。

第95～98行：遍历TmpAlloc向量，回填共享存储区的变量的m_iMemoryAllic属性。

第99行：设置当前过程的m_TmpLink属性，该属性记录的是占用空间最多的可共享存储区的临时变量的位序。

第100行：设置当前过程的m_ValSize属性，该属性记录的是当前过程数据块占用空间的字节数。

在现代编译器设计中，关于存储优化的算法并不罕见，在并行、嵌入式编译等领域，都有广泛的应用，其理论与实现技术可能是相对复杂的。不过，算法的核心仍然在于检测冲突与描述依赖关系。以怎样的数据结构及算法才能更有效地检测存储空间的访问冲突是一个值得深入研究的话题。