Programming Assignment 3 - VLIW Packing

Advanced Programming II, Fall 2002

Due Date

This assignment is due by 2:00 p.m. on Friday, 18 October.

See the assignment turn-in page (last modified on 4 March 2002) for instructions on turning in your assignment.

A Very-Long Instruction Word (VLIW) CPU architecture is like a regular CPU architecture except that it has two of all its functional units: two adders, two multipliers, and so on. The functional units share access to the same set of CPU registers and to primary store. The architecture has eight CPU registers named r0 through r7; addresses in primary store are referenced by the names of the associated variables (which are assumed to be different from the register names).

A simple VLIW instruction is either a move instruction or an operator instructions. All simple instructions execute in one clock tick. A move instruction has the form

move dst src

and moves the value stored in src to the location given by dst. Both src and dst can be either memory addresses or registers, with the restriction that both cannot be memory addresses; that is at least one must be a register.

An operator instruction has the form

opr dst src

where opr is one of the usual operators add, sub and so on and both src and dst are registers. The effect of an operator instruction is to compute

dst = dst op src

Each operator has its own functional unit; that is, the add operator uses the addition functional unit, the division operator uses the division functional unit and so on. The translation from high-level language statements to simple VLIW instructions is straightforward. For example, the high-level statement

a = b + c

can be translated into the sequence of simple VLIW instructions

move r0  b
move r1  c
add  r1 r0
move  a r1

A sequence of VLIW instructions can be optimized by packing several simple instructions into a single composite instruction. A composite instruction is formed from a set of simple instructions by listing the simple instructions on a line separated by semicolons; the order of the simple instructions in the line doesn't matter. For example, the two simple-instruction sequence

move r0  b
move r1  c

can be packed into the single composite instruction

move r0  b ; move r1  c

A composite instruction also executes in one clock tick, but it executes all its component simple instructions in parallel because of the many functional units available in the CPU.

The Problem

Write a VLIW packer that inputs from std-in a sequence of simple instructions and outputs to std-out the shortest possible sequence of composite instructions that perform the same computation as the input sequence.

Your program should optimize code subject to the following constraints:

A composite instruction can consists of no more than five simple instructions.
A composite instruction can have no more than two of the same operator instructions, because the CPU has at most two functional units for each operator. A composite instruction can contain up to five move instructions.
The optomized instruction sequence should produce exactly the same results in memory as the unoptomized instruction sequence for all possible executions. The initial and final values of registers are not important.

Input

The input will be a sequence of zero or more simple-instruction blocks; adjacent simple-statement blocks are separated by at least one blank line (that is, a line containing zero or more space characters as defined by std::isspace(), excluding the line-ending newline).

A block consists of one or more simple statements. Each simple statement appears in a single line, and a single line contains exactly one simple statement.

Operators can be any of the standard C++ binary operators except for the short-circuit operators && and ||; see Appendix A of Deitel and Deitel for details.

Output

Ouput should be a sequence of zero or more instruction blocks corresponding to the input blocks. Each output block should be an optimized version of the corresponding input block (note that it may not be possible to optimize an input block, in which case the output block is the same as the input block). The operators name appearing in the output should match the operator names appearing in the input.

If your program detects an error in an input block, it should produce an informative error message as the corresponding output block and go on to the next input block.