大门|大门CS 2010 |问题37

下面的程序使用六个临时变量a、b、c、d、e、f。

 
    a = 1
    b = 10
    c = 20
    d = a+b
    e = c+d
    f = c+e
    b = c+e
    e = b+f
    d = 5+e
    return d+f

假设所有操作的操作数都来自寄存器，那么在不溢出的情况下执行该程序所需的最小寄存器数是多少？ （A） 2 （B） 3. （C） 4. （D） 6. 答复: （B） 说明： 所有给定的表达式最多使用3个变量，因此我们不需要超过3个寄存器。

看见 http://en.wikipedia.org/wiki/Register_allocation

它至少需要3个寄存器。

登记分配原则 ：如果一个变量需要分配给寄存器，系统会检查是否有可用的空闲寄存器，如果找到，则分配。如果没有空闲寄存器，那么它会检查是否有一个寄存器包含一个死变量（该变量的值在将来不会被使用），如果它找到了一个，它就会进行分配。否则就会溢出（它会检查最长时间后需要其值的寄存器，将其值保存到内存中，然后使用该寄存器进行当前分配，稍后当需要寄存器的旧值时，系统会从保存该值的内存中获取该值，并将其分配到任何可用的寄存器中）。

但在这里，我们不应按照问题中的指示应用溢出。

让我们为变量分配寄存器。

a=1 （假设寄存器R1分配给变量“a”）

b=10 （R2表示“b”，因为“a”的值将在将来使用，因此不能用R1中“b”的值替换“a”的变量）

c=20 （R3表示“c”，因为“a”和“b”的值将在将来使用，因此不能分别用R1或R2中的“c”替换变量“a”或“b”）

d=a+b （现在可以将’d’赋值给R1，因为R1包含死变量’a’，之所以称它，是因为将来不会使用它，也就是说，没有后续表达式使用变量’a’的值。）

e=c+d （“e”可以分配给R1，因为当前R1包含变量“d”的值，该值不会在后续表达式中使用。）

笔记 ：变量的已计算值仅由读操作（而非写操作）使用，因此我们只需在后续表达式的RHS端查看是否将使用该变量。

f=c+e （’f’可以分配给R2，因为寄存器R2中’b’的值不会在后续表达式中使用，因此R2可以用来分配’f’而不是’b’）

b=c+e （“b”可以分配给R3，因为R3中的“c”值以后不会使用）

e=b+f （此处“e”已在R1中，因此此处无分配，直接分配）

d=5+e （’d’可以分配给R1或R3，因为这两个值都不会被进一步使用，让我们分配给R1）

返回d+f （这里没有分配，只是添加并返回寄存器R1和R2的内容）

因此，我们只需要3个寄存器，R1 R2和R3。

这个问题的小测验