Compilers Principles, Techniques, & Tools (purple dragon book) second edition exercise answers

Exercises for Section 8.2

8.2.1

Generate code for the following three-address statements assuming all variables are stored in memory locations.

  1. x = 1
  2. x = a
  3. x = a + 1
  4. x = a + b
  5. The two statements
    • x = b * c
    • y = a + x

answer

1.  LD R1, #1
    ST x, R1

2.  LD R1, a
    ST x, R1

3.  LD R1, a
    ADD R1, R1, #1
    ST x, R1

4.  LD R1, a
    LD R2, b
    ADD R1, R1, R2
    ST x, R1

5.  LD R1, b
    LD R2, c
    MUL R1, R1, R2
    LD R3, a
    ADD R3, R3, R1
    ST y, R3

Note：第 5 小题，可以在生成的汇编码第三行后插入 ST x, R1 和 LD R1, x 两句，这两句属于冗余代码（redundant store-load）。使用简易代码生成策略很容易生成这种冗余代码，慢是慢一些但是也是正确的，有专门处理这种问题的优化（redundant store-load elimination），所以生不生成在这题的答案里感觉都行。

8.2.2

Generate code for the following three-address statements assuming a and b are arrays whose elements are 4-byte values.

  1. The four-statement sequence

     x = a[i]
 y = b[j]
 a[i] = y
 b[j] = x

  2. The three-statement sequence

     x = a[i]
 y = b[i]
 z = x * y

  3. The three-statement sequence

     x = a[i]
 y = b[x]
 a[i] = y

answer

1.  LD R1, i
    MUL R1, R1, #4
    LD R2, a(R1)
    LD R3, j
    MUL R3, R3, #4
    LD R4, b(R3)
    ST a(R1), R4
    ST b(R3), R2

2.  LD R1, i
    MUL R1, R1, #4
    LD R2, a(R1)
    LD R1, b(R1)
    MUL R1, R2, R1
    ST z, R1

3.  LD R1, i
    MUL R1, R1, #4
    LD R2, a(R1)
    MUL R2, R2, #4
    LD R2, b(R2)
    ST a(R1), R2

8.2.3

Generate code for the following three-address sequence assuming that p and q are in memory locations:

y = *q
q = q + 4
*p = y
p = p + 4

answer

LD R1, q
LD R2, 0(R1)
ADD R1, R1, #4
ST q, R1
LD R1, p
ST 0(R1), R2
ADD R1, R1, #4
ST p, R1

8.2.4

Generate code for the following sequence assuming that x, y, and z are in memory locations:

    if x < y goto L1
    z = 0
    goto L2
L1: z = 1

answer

    LD R1, x
    LD R2, y
    SUB R1, R1, R2
    BLTZ R1, L1
    LD R1, #0
    ST z, R1
    BR L2
L1: LD R1, #1
    ST z, R1

Note：实际生成代码时会把标签对应到具体的数字地址上，但这小节还没到那一步，把原本题目里的标签名拿来随便写写就好啦。

8.2.5

Generate code for the following sequence assuming that n is in a memory location:

    s = 0
    i = 0
L1: if i > n goto L2
    s = s + i
    i = i + 1
    goto L1
L2:

answer

Long version:

    LD R1, #0
    ST s, R1
    ST i, R1
L1: LD R1, i
    LD R2, n
    SUB R2, R1, R2
    BGTZ R2, L2
    LD R2, s
    ADD R2, R2, R1
    ST s, R2
    ADD R1, R1, #1
    ST i, R1
    BR L1
L2:

Short version:

    LD R2, #0
    LD R1, R2
    LD R3, n
L1: SUB R4, R1, R3
    BGTZ R4, L2
    ADD R2, R2, R1
    ADD R1, R1, #1
    BR L1
L2:

Note：短版本的优化 1）消除冗余存-读 2）循环不变代码外提 3）然后外加寄存器分配

8.2.6

Determine the costs of the following instruction sequences:

1.  LD R0, y
    LD R1, z
    ADD R0, R0, R1
    ST x, R0

2.  LD R0, i
    MUL R0, R0, 8
    LD R1, a(R0)
    ST b, R1

3.  LD R0, c
    LD R1, i
    MUL R1, R1, 8
    ST a(R1),R0

4.  LD R0, p
    LD R1, 0(R0)
    ST x, R1

5.  LD R0, p
    LD R1, x
    ST 0(R0), R1

6.  LD R0, x
    LD R1, y
    SUB R0, R0, R1
    BLTZ *R3, R0

answer

  1. 2 + 2 + 1 + 2 = 7
  2. 2 + 2 + 2 + 2 = 8
  3. 2 + 2 + 2 + 2 = 8
  4. 2 + 2 + 2 = 6
  5. 2 + 2 + 2 = 6
  6. 2 + 2 + 1 + 1 = 6

Note：这本书用的指令集没明确定义所有指令的细节，但看起来所谓用变量名来指定内存地址实际上隐含着这些变量是静态分配的假设，也就是说在真正生成完的指令里这些变量名都会被替换为它们对应的数字形式的地址常量，而地址存在指令后的一个额外的word里，这就算多一单位的开销。

Note

  1. 很明显本节内容写得非常随意，推荐数字常量是应该都加#前缀的，除了放在地址里用。比如 LD R1, #1 和 ADD R1, R1, #1。

  2. 本书中 Ri 表示第 i 号寄存器。

    1. 在翻译成汇编码的过程中，是可以随意指定 i 的值（比如 R3, R4, R1000）呢还是会有某种限制？

      回答：现在暂时随意。等后面说寄存器个数有限制的时候再考虑有限制的情况。

    2. 另外，如果代码中所示的 R1 在后面的代码中用不着了，那么新的值是不是可以被加载到 R1 中？如果可以的话，如何知道之前的 R1 用不着了？

      回答：可以覆盖。至于如何知道前面的值死了就要看 def-use 链。这是优化的重要问题。例如9.2.5小节讲 live variable 就跟这个有关。

  3. b = a[i] 对应的汇编码：

     LD R1, i
 MUL R1, R1, 8
 LD R2, a(R1)
 ...

    其中 a 为什么不需要先 load 到寄存器？

    回答：这里隐含一个假设：变量是静态分配存储的。后面涉及不是静态变量的时候情况会有变化。