Further reading
Aho, Sethi, and Ullman [Aho06] wrote a classic text on compilers, and Muchnick [Muc97] describes advanced compiler techniques in detail. A paper on the ATOM system [Sri94] provides a good description of instrumenting programs for gathering traces. Cramer et al. [Cra97] describe the Java JIT compiler. Li and Malik [Li97D] describe a method for statically analyzing program performance. Banerjee [Ban93, Ban94] describes loop transformations. Two books by Beizer, one on fundamental functional and structural testing techniques [Bei90] and the other on system-level testing [Bei84], provide comprehensive introductions to software testing and, as a bonus, are well written. Lyu [Lyu96] provides a good advanced survey of software reliability. Walsh [Wal97] describes a software modem implemented on an ARM processor.
Questions
Q5-1 Write C code for a state machine that implements a four-cycle handshake.
Q5-2 Use the circular buffer functions to write a C function that accepts a new data value, puts it into the circular buffer, and then returns the average value of all the data values in the buffer.
Q5-3 Write C code for a producer/consumer program that takes one value from one input queue, another value from another input queue, and puts the sum of those two values into a separate queue.
Q5-4 For each basic block given below, rewrite it in single-assignment form, and then draw the data flow graph for that form.
a. x = a + b;
y = c + d;
z = x + e;
b. r = a + b − c;
s = 2 * r;
t = b − d;
r = d + e;
c. a = q − r;
b = a + t;
a = r + s;
c = t − u;
d. w = a − b + c;
x = w − d;
y = x − 2;
w = a + b − c;
z = y + d;
y = b * c;
Q5-5 Draw the CDFG for the following code fragments:
a. if (y == 2) {r = a + b; s = c − d;}
else r = a − c
b. x = 1;
if (y == 2) { r = a + b; s = c − d; }
else { r = a − c; }
c. x = 2;
while (x < 40) {
x = foo[x];
}
d. for (i = 0; i < N; i++)
x[i] = a[i]*b[i];
e. for (i = 0; i < N; i++) {
if (a[i] == 0)
x[i] = 5;
else
x[i] = a[i]*b[i];
}
Q5-6 Show the contents of the assembler’s symbol table at the end of code generation for each line of the following programs:
a. ORG 200
p1: ADR r4,a
LDR r0,[r4]
ADR r4,e
LDR r1,[r4]
ADD r0,r0,r1
CMP r0,r1
BNE q1
p2: ADR r4,e
b. ORG 100
p1: CMP r0,r1
BEQ x1
p2: CMP r0,r2
BEQ x2
p3: CMP r0,r3
BEQ x3
c. ORG 200
S1: ADR r2,a
LDR r0,[r2]
S2: ADR r2,b
LDR r2,a
ADD r1,r1,r2
Q5-7 Your linker uses a single pass through the set of given object files to find and resolve external references. Each object file is processed in the order given, all external references are found, and then the previously loaded files are searched for labels that resolve those references. Will this linker be able to successfully load a program with these external references and entry points?
| Object file | Entry points | External references |
| o1 | a, b, c, d | s, t |
| o2 | r, s, t | w, y, d |
| o3 | w, x, y, z | a, c, d |
Q5-8 Determine whether each of these programs is reentrant.
a. int p1(int a, int b) {
retun( a + b);
}
b. int x, y;
int p2(int a) {
return a + x;
}
c. int x, y;
int p3(int a, int b) {
if (a > 0)
x = b;
return a + b;
}
Q5-9 Is the code for the FIR filter of Programming Example 5.3 reentrant? Explain.
Q5-10 Provide the required order of execution of operations in these data flow graphs. If several operations can be performed in arbitrary order, show them as a set: {a + b, c − d}.
Q5-11 Draw the CDFG for the following C code before and after applying dead code elimination to the if statement:
#define DEBUG 0
proc1();
if (DEBUG) debug_stuff();
switch (foo) {
case A: a_case();
case B: b_case();
default: default_case();
}
Q5-12 Unroll the loop below:
Q5-13 Apply loop fusion or loop distribution to these code fragments as appropriate. Identify the technique you use and write the modified code.
a. for (i=0; i<N; i++)
z[i] = a[i] + b[i];
for (i=0; i<N; i++)
w[i] = a[i] − b[i];
b. for (i=0; i<N; i++) {
x[i] = c[i]*d[i];
y[i] = x[i] * e[i];
}
c. for (i=0; i<N; i++) {
for (j=0; j<M; j++) {
c[i][j] = a[i][j] + b[i][j];
x[j] = x[j] * c[i][j];
}
y[i] = a[i] + x[j];
}
Q5-14 Can you apply code motion to the following example? Explain.
for (i = 0; i < N; i++)
for (j = 0; j < M; j++)
z[i][j] = a[i] * b[i][j];
Q5-15 For each of the basic blocks of Q5-4, determine the minimum number of registers required to perform the operations when they are executed in the order shown in the code. (You can assume that all computed values are used outside the basic blocks, so that no assignments can be eliminated.)
Q5-16 For each of the basic blocks of Q5-4, determine the order of execution of operations that gives the smallest number of required registers. Next, state the number of registers required in each case. (You can assume that all computed values are used outside the basic blocks, so that no assignments can be eliminated.)
Q5-17 Draw a data flow graph for the code fragment of Example 5.6. Assign an order of execution to the nodes in the graph so that no more than four registers are required. Explain how you arrived at your solution using the structure of the data flow graph.
Q5-18 Determine the longest path through each code fragment, assuming that all statements can be executed in equal time and that all branch directions are equally probable.
a. if (i < CONST1) { x = a + b; }
else { x = c − d; y = e + f; }
b. for (i = 0; i < 32; i++)
if (a[i] < CONST2)
x[i] = a[i] * c[i];
c. if (a < CONST3) {
if (b < CONST4)
w = r + s;
else {
w = r − s;
x = s + t;
}
} else {
if (c > CONST5) {
w = r + t;
x = r − s;
y = s + u;
}
}
Q5-19 For each code fragment, list the sets of variable values required to execute each assignment statement at least once. Reaching all assignments may require multiple independent executions of the code.
a. if (a > 0)
x = 5;
else {
if (b < 0)
x = 7;
}
b. if (a == b) {
if (c > d)
x = 1;
else
x = 2;
x = x + 1;
}
Q5-20 Determine the shortest path through each code fragment, assuming that all statements can be executed in equal time and that all branch directions are equally probable. The first branch is always taken.
Q5-21 Write the branch tests for each conditional.
Q5-22 The loop appearing below is executed on a machine that has a 1-K-word data cache with four words per cache line.
a. How must x and a be placed relative to each other in memory to produce a conflict miss every time the inner loop’s body is executed?
b. How must x and a be placed relative to each other in memory to produce a conflict miss one out of every four times the inner loop’s body is executed?
c. How must x and a be placed relative to each other in memory to produce no conflict misses?
for (i = 0; i < 50; i++)
for (j = 0; j < 4; j++)
x[i][j] = a[i][j] * c[i];
Q5-23 Explain why the person generating clear-box program tests should not be the person who wrote the code being tested.
Q5-24 Find the cyclomatic complexity of the CDFGs for each of the code fragments given below.
a. if (a < b) {
if (c < d)
x = 1;
else
x = 2;
} else {
if (e < f)
x = 3;
else
x = 4;
}
b. switch (state) {
case A:
if (x = 1) { r = a + b; state = B; }
else { s = a − b; state = C; }
break;
case B:
s = c + d;
state = A;
break;
case C:
if (x < 5) { r = a − f; state = D; }
else if (x == 5) { r = b + d; state = A; }
else { r = c + e; state = D; }
break;
case D:
r = r + 1;
state = D;
break;
}
c. for (i = 0; i < M; i++)
for (j = 0; j < N; j++)
x[i][j] = a[i][j] * c[i];
Q5-25 Use the branch condition testing strategy to determine a set of tests for each of the following statements.
a. if (a < b || ptr1 == NULL) proc1();
else proc2();
b. switch (x) {
case 0: proc1(); break;
case 1: proc2(); break;
case 2: proc3(); break;
case 3: proc4(); break;
default; dproc(); break;
}
c. if (a < 5 && b > 7) proc1();
else if (a < 5) proc2();
else if (b > 7) proc3();
else proc4();
Q5-26 Find all the def-use pairs for each code fragment given below.
a. x = a + b;
if (x < 20) proc1();
else {
y = c + d;
while (y < 10)
y = y + e;
}
b. r = 10;
s = a − b;
for (i = 0; i < 10; i++)
x[i] = a[i] * b[s];
c. x = a − b;
y = c − d;
z = e − f;
if (x < 10) {
q = y + e;
z = e + f;
}
if (z < y) proc1();
Q5-27 For each of the code fragments of Q5-26, determine values for the variables that will cause each def-use pair to be exercised at least once.
Q5-28 Assume you want to use random tests on an FIR filter program. How would you know when the program under test is executing correctly?
Lab exercises
L5-1 Compare the source code and assembly code for a moderate-size program. (Most C compilers will provide an assembly language listing with the -S flag.) Can you trace the high-level language statements in the assembly code? Can you see any optimizations that can be done on the assembly code?
L5-2 Write C code for an FIR filter. Measure the execution time of the filter, either using a simulator or by measuring the time on a running microprocessor. Vary the number of taps in the FIR filter and measure execution time as a function of the filter size.
L5-3 Write C++ code for an FIR filter using a class to implement the filter. Implement as many member functions as possible as inline functions. Measure the execution time of the filter and compare to the C implementation.
L5-4 Generate a trace for a program using software techniques. Use the trace to analyze the program’s cache behavior.
L5-5 Use a cycle-accurate CPU simulator to determine the execution time of a program.
L5-6 Measure the power consumption of your microprocessor on a simple block of code.
L5-7 Use software testing techniques to determine how well your input sequences to the cycle-accurate simulator exercise your program.
L5-8 Generate a set of functional tests for a moderate-size program. Evaluate your test coverage in one of two ways: Have someone else independently identify bugs and see how many of those bugs your tests catch (and how many tests they catch that were not found by the human inspector); or inject bugs into the code and see how many of those are caught by your tests.