Exercises for Section 8.4

8.4.1

Figure 8.10 is a simple matrix-multiplication program.

  1. Translate the program into three-address statements of the type we have been using in this section. Assume the matrix entries are numbers that require 8 bytes, and that matrices are stored in row-major order.
  2. Construct the flow graph for your code from (a).
  3. Identify the loops in your flow graph from (b).
for (i=O; i<n; i++)
    for (j=O; j<n; j++)
        c[i][j] = 0.0;
for (i=O; i<n; i++)
    for (j=O; j<n; j++)
        for (k=O; k<n; k++)
            c[i][j] = c[i][j] + a[i][k]*b[k][j];

Figure 8.10: A matrix-multiplication algorithm

Answer

  1. three-address statements

     B1       1)  i = 0

 B2       2)  if i >= n goto(13)

 B3       3)  j = 0

 B4       4)  if j >= n goto(11)

 B5       5） t1 = n * i
          6)  t2 = t1 + j
          7)  t3 = t2 * 8
          8)  c[t3] = 0.0
          9)  j = j + 1
         10)  goto(4)

 B6      11)  i = i + 1
         12)  goto(2)

 B7      13)  i = 0

 B8      14)  if i >= n goto(40)

 B9      15)  j = 0

 B10     16)  if j >= n goto(38)

 B11     17)  k = 0

 B12     18)  if k >= n goto(36)

 B13     19)  t4 = n * i
         20)  t5 = t4 + j
         21)  t6 = t5 * 8
         22)  t7 = c[t6]
         23)  t8 = n * i
         24)  t9 = t8 + k
         25)  t10 = t9 * 8
         26)  t11 = a[t10]
         27)  t12 = n * k
         28)  t13 = t12 + j
         29)  t14 = t13 * 8
         30)  t15 = b[t14]
         31)  t16 = t11 * t15
         32)  t17 = t7 + t16
         33)  c[t6] = t17
         34)  k = k + 1
         35)  goto(18)

 B14     36)  j = j + 1
         37)  goto(16)

 B15     38)  i = i + 1
         39)  goto(14)

  2. flow graph

    8 4 1-2

  3. loops

    • {B2, B3, B4, B6}
    • {B4, B5}
    • {B8, B9, B10, B15}
    • {B10, B11, B12, B14}
    • {B12, B13}

8.4.2

Figure 8.11 is code to count the number of primes from 2 to n, using the sieve method on a suitably large array a. That is, a[i] is TRUE at the end only if there is no prime i^0.5 or less that evenly divides i. We initialize all a[i] to TRUE and then set a[j] to FALSE if we find a divisor of j.

  1. Translate the program into three-address statements of the type we have been using in this section. Assume integers require 4 bytes.
  2. Construct the flow graph for your code from (a).
  3. Identify the loops in your flow graph from (b).
for (i=2; i<=n; i++)
    a[i] = TRUE;
count = 0;
s = sqrt(n);
for (i=2; i<=s; i++)
if (a[i]) 1* i has been found to be a prime *1 {
    count++ ;
    for (j=2*i; j<=n; j = j+i)
        a[j] = FALSE; 1* no multiple of i is a prime *1
    }

Figure 8.11: Code to sieve for primes

Answer

  1. three-address statements

     B1       1)  i = 2

 B2       2)  if i > n goto(7)

 B3       3)  t1 = i * 4
          4)  a[t1] = TRUE
          5)  i = i + 1
          6)  goto(2)

 B4       7)  count = 0
          8)  s = sqrt(n)
          9)  i = 2

 B5      10)  if i > s goto(22)

 B6      11)  t2 = i * 4
         12)  ifFalse a[t2] goto(20)

 B7      13)  count = count + 1
         14)  j = 2 * i

 B8      15)  if j > n goto(20)

 B9      16)  t3 = j * 4
         17)  a[t3] = FALSE
         18） j = j + i
         19)  goto(15)

 B10     20)  i = i + 1
         21)  goto(10)

  2. flow graph

    8 4 2-2

  3. loops

    • {B2, B3}
    • {B5, B6, B10}
    • {B5, B6, B7, B8, B10}
    • {B8, B9}

Note

1. A demo for algorithm 8.7: Determining the liveness and next-use information foreach statement in a basic block.

init:

three-address statements                 symbol table

                                         symbol  live   nextuse
    i)  a = b + c                       [a,      true,  null]
    j)  t = a + b                       [b,      true,  null]
                                        [c,      true,  null]
                                        [t,      true,  null]

step1:
Attach to statement j the information currently found in the symbol table

                                         symbol  live   nextuse
    i)  a = b + c                       [a,      true,  null]
    j)  t = a + b  [t, true, null]      [b,      true,  null]
                   [a, true, null]      [c,      true,  null]
                   [b, true, null]      [t,      true,  null]

step2:
In the symbol table, set x.live = false and
                         x.nextuse = null

                                         symbol  live   nextuse
    i)  a = b + c                       [a,      true,  null]
    j)  t = a + b  [t, true, null]      [b,      true,  null]
                   [a, true, null]      [c,      true,  null]
                   [b, true, null]      [t,      false, null]

step3:
In the symbol table, set a.live = true, b.live = true and
                         a.nextuse = j, b.nextuse = j

                                         symbol  live   nextuse
    i)  a = b + c                       [a,      true,  j   ]
    j)  t = a + b  [t, true, null]      [b,      true,  j   ]
                   [a, true, null]      [c,      true,  null]
                   [b, true, null]      [t,      false, null]

step4:


                                         symbol  live   nextuse
    i)  a = b + c  [a, true, j   ]      [a,      true,  j   ]
                   [b, true, j   ]      [b,      true,  j   ]
                   [c, true, null]      [c,      true,  null]
                                        [t,      false, null]
    j)  t = a + b  [t, true, null]
                   [a, true, null]
                   [b, true, null]

step5:

                                         symbol  live   nextuse
    i)  a = b + c  [a, true, j   ]      [a,      false, null]
                   [b, true, j   ]      [b,      true,  j   ]
                   [c, true, null]      [c,      true,  null]
                                        [t,      false, null]
    j)  t = a + b  [t, true, null]
                   [a, true, null]
                   [b, true, null]

step6:

                                         symbol  live   nextuse
    i)  a = b + c  [a, true, j   ]      [a,      false, null]
                   [b, true, j   ]      [b,      true,  i   ]
                   [c, true, null]      [c,      true,  i   ]
                                        [t,      false, null]
    j)  t = a + b  [t, true, null]
                   [a, true, null]
                   [b, true, null]

2. Three ways to generate code for "for(i = 0; i < n ; i++)" statement

 1) i = 0
 2) if i >= n goto(9)
 3)
    ...
 7) i = i + 1
 8) if i < n goto(3)
 9)


 1) i = 0
 2) goto(8)
 3)
    ...
 7) i = i + 1
 8) if i < n goto(3)
 9)


 1) i= 0
 2) if i >= n goto(9)
    ...
 7) i = i + 1
 8) goto(2)
 9)

更多可参考 RednaxelaFX 的 对C语义的for循环的基本代码生成模式

Copyright© 2013-2020

All Rights Reserved 京ICP备2023019179号-8