Solved-A Compiler and Optimizer for tinyL- Solution

Description

THIS IS NOT A GROUP PROJECT! You may talk about the project and possible solutions in general terms, but must not share code. In this project, you will be asked to write a recursive descent LL(1) parser and code generator for the tinyL language as discussed in class. Your compiler will generate RISC machine instructions called ILOC (Intermediate Language for Optimizing Compilers). You will also write a code optimizer that takes ILOC instructions as input and implements di erent peephole optimizations. The output of the optimzer is a sequence of ILOC instructions which produces the same results as the original input sequence. To test your generated programs, you can use a virtual machine (simulator) that can \run” your ILOC programs. The project will require you to manipulate linked lists of instructions. In order to avoid memory leaks, explicit deallocation of \eliminated” instructions is necessary.

This document is not a complete speci cation of the project. You will encounter impor-tant design and implementation issues that need to be addressed in your project solution. Identifying these issues is part of the project. As a result, you need to start early, allowing time for possible revisions of your solution.

<program>

::=

<stmt

list> .

<stmt

list>

::=

<stmt> <morestmts>

<morestmts>

::=

; <stmt

list> j

<stmt>

::=

<assign> j <print>

<assign>

::=

<variable> = <expr>

<print>

::= ! <variable>

<expr>

::=

+ <expr> <expr> j

− <expr> <expr> j

<expr> <expr> j

= <expr> <expr> j

<variable> j

<digit>

j

j

e j

j g

j

j

i j

j k j x j y j z

<variable>

::=

a

j

b

j

c

d

f

h

j

<digit>

::=

0

j

1

j

2

j

3

j

4 j

5

j

6

j 7

j

8

j

9

Figure 1: The tinyL language as speci ed by a context-free grammar

• Background

1.1 The tinyL language

tinyL is a simple expression language that allows assignments, and print as its only I/O operation. Every token is a single character of the input. This makes scanning rather easy, but does not allow integer constants of more than one digit, or variable names of more than one character. The language speci cation in Backus-Naur from is given in Figure . The following are examples of two valid tinyL programs:

1. a=3;b=5;c=/3*ab;d=+c1;!d.

2. a=7;b=-*+1+2a58;!b.

1.2 Target Architecture

instr. format			description			semantics
			memory instructions
loadI c ) rx		) ry	load constant value cinto register rx		rx	c
loadAI rx, c			load value of MEM(rx + c) into ry		ry	MEM(rx + c)
storeAI rx	) ry , c		store value in rxinto MEM(ry + c)		MEM(ry + c)		rx
			bit-shift operations
lshiftI rx, c		) rz	shift contents of registers rxby c	positions to the left	rz	rx<< c
		) rz	store result into register rz
rshiftI rx, c			shift contents of registers rxby c	positions to the right	rz	rx>> c
			store result into register rz
			arithmetic instructions
add rx, ry	) rz		add contents of registers rxand ry , and		rz	rx+ ry
	) rz		store result into register rz			rx− ry
sub rx, ry			subtract contents of register ry from register		rz
	) rz		rx, and store result into register rz			rx ry
mult rx, ry			multiply contents of registers rxand ry , and		rz
	) rz		store result into register rz
div rx, ry			divide contents of registers rxand ry , and		rz	rx/ ry
			store result into register rz
			I/O instruction
outputAI rx, c			write value of MEM(rx + c) to standard output		print( MEM(rx + c)

The target architecture is a RISC machine with 4096 registers. All registers can only store integer values. A RISC architecture is a load/store architecture where arithmetic instructions operate on registers rather than memory operands (memory addresses). This means that for each access to a memory location, a load or store instruction has to be generated. Here is the machine instruction set of our RISC target architecture. You are only allowed to use these ILOC instructions. ILOC instructions are case sensitive. r_x, r_y , and r_z represent three registers.

1.3 Code Shape

Your compiler should generate code of a speci c form with respect to how variables are accessed. All variables accesses use an address that consists of a base pointer and an o set relative to this base pointer. The base pointer address is stored in a special register, in our case r₀. All memory references are therefore of the form MEM(r₀ + o set). This is what the instructions loadI, loadAI, storeAI and outputAI use. All addresses are byte addresses. Your compiler should assign the address 1024 to r₀ at the beginning of the program. For our example language, variable o sets are non-negative byte addresses. Your compiler should map variable \a” to o set 0, variable \b” to o set 4, variable \c” to o set 8, etc. Other mappings are also possible, so we are really talking about \code shape” here, which is a particular coding style.

Your compiler should generate code that does not \reuse” registers. If you assign a value to a register by a loadI, loadAI, add, sub, mult or div instruction, you will always use a fresh, i.e., new register. Your target machine has many registers, so do not worry about running out of registers. For example, this means that the code generated for + 1 1 will generate two loadI instructions with two distinct target registers and one add instruction. This coding style is also called the register-register model, where each computed value gets its own register. In a real compiler, an additional optimization pass maps (virtual) registers to the limited number of physical registers of a machine. This step is typically called register allocation. We do not deal with register allocation here.

Our tinyL language does not contain any control flow constructs (e.g.: jumps, if-then-else, while). This means that every generated instruction in the instruction sequence will be executed.

• Project Description

The project consists of two main parts:

1. Complete the partially implemented recursive descent LL(1) parser that generates ILOC instructions.

2. Write a peephole optimizer for constant folding and operator strength reduction.

In addition, you are asked to write the PrintInstructionList routine. The project represents an entire programming environment consisting of a compiler, an optimizer, and a simulator (virtual machine) for ILOC. The ILOC simulator is called sim and will be made available to you as an executable on the ilab machines. This will allow you to check for correctness of your generated and optimized code.

2.1 Compiler

The recursive descent LL(1) parser implements a simple code generator. You should follow the main structure of the code as given to you in le Compiler.c. As given to you, the le contains code for function digit, variable, and partial code for function expr. As is,

the compiler is able to generate code only for expressions that contain \+” operations on operands that are digits or the variable \f”. You will need to add code in the provided stubs to generate correct RISC machine code for the entire program. Do not change the signatures of the recursive functions. Note: The left-hand and right-hand occurrences of variables are treated di erently.

2.2 I/O Instruction Utility

Within the Optimizer, a sequence of ILOC instructions is represented as a doubly-linked list. You are asked to implement the following utility function in le InstrUtils.c.

void PrintInstructionList(FILE *outfile, Instruction *instr);

Function PrintInstructionList traverses the instruction list beginning with instruction “instr”. The list is written into le “out le”. The implementation of this function must be based on the utility function

void PrintInstruction(FILE *outfile, Instruction *instr);

The implementation of the latter function is provided to you in le InstrUtils.c. This is also the le that will contain your implementation of PrintInstructionList

2.3 Peephole Optimization

There are two types of peephole optimizations that you will need to implement: constant folding and operator strength reduction. Peephole optimizations look for particular instruc-tion subsequences that can be replaced by a more e cient instruction sequence.

The peephole optimizer uses a sliding window of three RISC machine instructions. It looks for code patterns as described below. If no pattern is detected, the window is moved one instruction down the list of instructions. In the case of a successful match and code replacement, the rst instruction of the new window is set to the instruction that immediately follows the instructions that have been replaced, i.e., is set to the instruction immediately after the pattern in the unoptimized code.

A peephole optimization pass (constfolding or strengthreduct) expects the ILOC input le to be provided at the standard input (stdin), and will write the generated code back to standard output (stdout). This allows the speci cation of multiple passes of the same optimization or di erent sequences of optimization passes using the UNIX pipe feature. For example, to apply optimization constfolding twice, followed by a strengthreduction pass strengthreduct with le “tinyL.out” as input, and le “optimized.out” as output, we would specify

./constfolding < tinyL.out | ./constfolding | ./strengthreduct > optimized.out

Instructions that are deleted as part of the optimization process have to be explicitly deallocated using the C free command in order to avoid memory leaks. You will implement your two peephole optimization passes in le ConstFolding.c and StrengthReduction.c.

2.3.1 Constant folding

Patterns are consecutive instructions in your ILOC program. The pattern for constant folding is a follows:

loadI c₁ ) r_a

loadI c₂ ) r_b

OP r_a, r_b ) r_c

where c₁ and c₂ are integer constant, and OP is an arithmetic operation (add, sub, mult). Note: We do not apply this optimization for the division operator. The above pattern can be replaced by the code sequence

loadI c₃ ) r_c

where c₃ is the integer constant that represents the result of the computation (c₁ OP c₂), which is done at compile time. Due to the code shape assumption, register values in r_a and r_b are not used after the optimized pattern, allowing the two loadI instructions to be deleted.

2.3.2 Operator strength reduction

The patterns for this optimization are as follows:

loadI c₁ ) r_a

OP r_b, r_a ) r_c

where c₁ is an integer constant and a power of 2 (e.g.: 2, 4, 8, 16, …) and OP is the arithmetic operation mult or div. Multiplication and division can be implemented as left-shift or right-shift operations, respectively. For example,

loadI 4 ) r_a

div r_b, r_a ) r_c

can be replaced by

rshiftI r_b, 2 ) r_c

and

loadI 4 ) r_a

mult r_b, r_a ) r_c

can be replaced by

lshiftI r_b, 2 ) r_c

Note: Arithmetic integer operations may result in overflow or underflow conditions due to the nite bit-width of the integer representation. However, this is not a problem for these peephole optimizations since the overflow/underflow would also occur in the unoptimized code.

2.4 ILOC Simulator

The virtual machine executes ILOC program. If a outputAI <id> instruction is executed, the value of the speci ed memory location is written to standard output (stdout). All values are of type integer. An ILOC simulator is provided as an executable (sim). The ILOC simulator reports the overall number of executed instructions for a given input program. This allows you to assess the e ectiveness of your dead code elimination optimization. You also will be able to check for correctness of your optimization pass.

• Grading

You will submit your versions of les ConstFolding.c, StrengthReduction.c, Compiler.c and InstrUtils.c. You may also submit an optional ReadMe le if you want to communicate something about your code to the grader. No other le should be modi ed, and no additional le(s) may be used. The electronic submission procedure will be posted later. Do not submit any executables or any of your test cases.

Your programs will be graded based mainly on functionality. Functionality will be veri ed through automatic testing on a set of syntactically correct test cases. No error handing is required. The original project distribution contains some test cases. Note that during grading we will use additional test cases not known to you in advance. The distribution also contains executables of reference solutions for the compiler (compile.sol) and the optimizers (constfolding.sol, strenghtreduct.sol), and the iloc simulator sim. A simple Make le is also provided in the distribution for your convenience. For example, in order to create the compiler, say make compile at the Linux prompt, which will generate the executable compile.

The provided, initial compiler is able to parse and generate code for very simple programs consisting of a single assignment statement with right-hand side expresssions of only addi-tions of numbers, followed by a single print statement. You will need to be able to accept and compile the full tinyL language.

The Make le also contains rules to create executables of your optimization passes.

• How To Get Started

The code for this project lives on the ilab cluster in directory:

www.cs.rutgers.edu/courses/314/classes/fall 2017 kremer/projects/proj1/students

Create your own directory on the ilab cluster, and copy the entire provided project proj1.tar to your own home directory or any other one of your directories. Say tar -xf proj1.tar to extract the project les. Make sure that the read, write, and execute per-missions for groups and others are disabled (chmod go-rwx <directory name>). IT IS CONSIDERED CHEATING IF YOU DO NOT PROTECT YOUR PROJECT FILES.

Say make compile to generate the compiler. To run the compiler on a test case \test”, say ./compile test. This will generate a RISC machine program in le tinyL.out. To create an optimization pass, say make constfolding or make strengthreduct. The distributed versions of the two optimization passes do not work at all, and the compiler can only handle a single example program structure consisting of a single assignment statement followed by a print statemet. An example test case that the provided compiler can handle is given in le tests/test-dummy.

To call your optimization pass constfolding on a le that contains RISC machine code, for instance le tinyL.out, say ./constfolding < tinyL.out > optimized.out. This will generate a new le optimized.out containing the output of your optimizer. The oper-ators \<” and \>” are Linux redirection operators for standard input (stdin) and standard output (stdout), respectively. The same holds for your strenthreduct optimization pass.

You may want to use valgrind for memory leak detection. We recommend to use the following flags, in this case to test the optimizer for memory leaks:

valgrind –leak-check=full –show-reachable=yes –track-origins=yes ./constfolding < tinyL.out

To run a program on the ILOC simulator, for instance tinyL.out, say ./sim < tinyL.out. Finally, you can de ne a tinyL language interpreter on a single Linux command line as follows:

./compile test; ./strengthreduct < tinyL.out > opt.out; ./sim < opt.out

The \;” operator allows you to specify a sequence of Linux commands on a single com-mand line.

• Questions

All questions regarding this project should be posted on piazza (sakai). Enjoy the project!

7