CS 201

Project Description

1. Global common subexpression elimination: recall that this algorithm is based upon available expressions analysis.
   
2. Partial redundancy elimination: recall that this algorithm requires backward down-safety analysis followed by forward earliestness analysis.
   
3. Instrumentation: instrument the code to compute and output the total number of expression evaluations performed during program execution.

The input will be provided in form of the intermediate language described below. Therefore the first task you must carry out is to read the program written in this intermediate language and construct the program's control flow graph.

You are also provided with an interpreter for this intermediate language using which you can verify the correctness of the optimized code and a translator to generate intermediate code for programs written in a subset of C. By computing the number of expression evaluations performed during execution of a set of programs optimized by each of the above two optimizations, you will be able to compare their relative effectiveness in optimizing the programs.

More details about the languages, tools, and output requirements can be found in the following:

• Mini C language
• Intermediate Representation Language
• Getting the Tools
• Output Requirements

Reporting problems

Mini C language

• Only the int main() function can be defined, and all other definitions/statemetns must be within the function;
• int basic type, and one-dimension int array;
• arithmetic ops: +, -, *, /, %;
• comparison ops: <, <=, ==, !=, >, >=;
• logical ops: &&, ||, !;
• if, for, while, do-while statements;
• read(x) reads an integer from the standard input and puts the value into x, where x can be a[i];
• print(x) write the value of x into the standard output, where x can be a[i];
• C-style comments (i.e. /* comments */ ); and in addition,
• All lines beginning with a # are treated as comments. This means you can insert two macro definitions like

          #define read(x)         scanf("%d", &(x))
          #define print(x)        printf("%d\n", (x))
  

  in the beginning of a C file and use a standard C compiler to compile it. In this way, you can debug the C code using your familiar/favorite tools before using the translator to get an intermediate representation.

#define read(x)         scanf("%d", &(x))
#define print(x)        printf("%d\n", (x))

int main()
{
    int a, n, m, k, j, i, s0, s1, s2, s3, s4;

    read(a);
    n = a;
    m = a;
    k = a;

    while ( n > 0 ) {
        s3 = k + a;
        a = a + 1;

        s1 = a + m;
        if ( n % 2 == 0 ) {
            m = -m;
            s0 = a + m;
        }
        else {
            s0 = a + m;
            m = -m;
        }
        s2 = a + m;
        n = n - 1;

        a = a + 1;
        s4 = k + a;
    }
    s4 = k + a;
    print(s0);
    print(s1);
    print(s2);
    print(s3);
    print(s4);
}

The Intermediate Representation (IR) Language

The following is the IR code for the above example:

	.	_a
	.	_n
	.	_m
	.	_k
	.	_j
	.	_i
	.	_s0
	.	_s1
	.	_s2
	.	_s3
	.	_s4
	.	t0
	.	t1
	.	t2
	.	t3
	.	t4
	.	t5
	.	t6
	.	t7
	.	t8
	.	t9
	.	t10
	.	t11
	.	t12
	.	p0


: START
	.<	_a
	=	_n, _a
	=	_m, _a
	=	_k, _a
: L2
	<=	p0, _n, 0
	?:=	L3, p0
	+	t0, _k, _a
	=	_s3, t0
	+	t1, _a, 1
	=	_a, t1
	+	t2, _a, _m
	=	_s1, t2
	%	t3, _n, 2
	!=	p0, t3, 0
	?:=	L0, p0
	-	t4, 0, _m
	=	_m, t4
	+	t5, _a, _m
	=	_s0, t5
	:=	L1
: L0
	+	t6, _a, _m
	=	_s0, t6
	-	t7, 0, _m
	=	_m, t7
: L1
	+	t8, _a, _m
	=	_s2, t8
	-	t9, _n, 1
	=	_n, t9
	+	t10, _a, 1
	=	_a, t10
	+	t11, _k, _a
	=	_s4, t11
	:=	L2
: L3
	+	t12, _k, _a
	=	_s4, t12
	.>	_s0
	.>	_s1
	.>	_s2
	.>	_s3
	.>	_s4

Specifications of IR language

Getting the Tools

Download the front end (c2ir) which turns Mini C code into IR code.

Download the interpreter (irRun) which executes IR code. The interpreter executes code written in the mini-intermediate-represeantation language. It assumes that

• Each line contains at most one IR instruction;
• Each line is at most 254 characters long;
• All variables are defined before using.

Download test cases in pp_test.tar.gz and use them to test/debug your program.

Output Requirements

• For each test program, you need to generate the instrumented IR code and display what are the basic blocks for the original IR code. The following is the required information for the previous example:

  	.	_a
  	.	_n
  	.	_m
  	.	_k
  	.	_j
  	.	_i
  	.	_s0
  	.	_s1
  	.	_s2
  	.	_s3
  	.	_s4
  	.	t0
  	.	t1
  	.	t2
  	.	t3
  	.	t4
  	.	t5
  	.	t6
  	.	t7
  	.	t8
  	.	t9
  	.	t10
  	.	t11
  	.	t12
  	.	p0
  	.	count
  
  BB1
  : START
  	=	count, 1
  	.<	_a
  	=	_n, _a
  	=	_m, _a
  	=	_k, _a
  	+	t11, _k, _a
  BB2
  : L2
  	+	count, count, 1
  	<=	p0, _n, 0
  	?:=	L3, p0
  BB3
  	+	count, count, 5
  	=	_s3, t11
  	+	t1, _a, 1
  	=	_a, t1
  	+	t2, _a, _m
  	=	_s1, t2
  	-	t4, 0, _m
  	%	t3, _n, 2
  	!=	p0, t3, 0
  	?:=	L0, p0
  BB4
  	+	count, count, 1
  	=	_m, t4
  	+	t5, _a, _m
  	=	_s0, t5
  	:=	L1
  BB5
  : L0
  	+	count, count, 1
  	=	_s0, t2
  	=	_m, t4
  	+	t5, _a, _m
  BB6
  : L1
  	+	count, count, 3
  	=	_s2, t5
  	-	t9, _n, 1
  	=	_n, t9
  	+	t10, _a, 1
  	=	_a, t10
  	+	t11, _k, _a
  	=	_s4, t11
  	:=	L2
  BB7
  : L3
  	=	_s4, t11
  	.>	_s0
  	.>	_s1
  	.>	_s2
  	.>	_s3
  	.>	_s4
  	.>	count
  
  Blue denotes the instrumented code used to calculate the number of performed expression evaluation.
  Red denotes the part of code which is modified due to expression elimination.
  
   The interpreter will execute the instrumented IR and output:
  (a) the output of the original program; and (b) the total number of 
  expression evaluations performed. For example:
  $./irRun sample.mil 
  3 		(input)
  11		(original output)
  11
  5
  10
  12
  32		(total number of expression evaluation performed)