Assignment 3: Pablo to IR Compilation

Your assignment is to compile Pablo statements and expressions to Pablo IR, a simplified intermediate representation based on LLVM IR. Alternatively, you may use the Haskell-LLVM library to produce LLVM IR directly.

Tasks:

1. Define your own PabloIR algebraic data types to represent the required features of Pablo IR.
2. Implement show functions for your new IR types to print out PabloIR in the string representation given.
3. Implement a compiler algorithm to translate Pablo programs into Pablo IR ensuring that the program is in SSA (static single assignment) form.
4. Create a main program pabloc.hs which parses a Pablo program from an input file (using the parser of assignment 2) and generates the corresponding PabloIR file as output.

Notes:

• The Pablo Advance v n operation translates to a shl v n operation.
• The Pablo MatchStar m c operation should be translated to code that implements the following calculation: \((((m\wedge c) + c) \oplus c) \vee m\).

Simplified Version of Assignment

You may choose to submit a simplified solution, ignoring SSA form and phi nodes, for 90% credit.

Example 1

Consider the following Pablo program.

x = a & (b ^ c)
if d | e:
   y = d & x
else:
   y = 000...
.
z = x | y

The following Pablo IR consisting of three basic blocks should be produced by compiling this program.

entry:
  %0 = xor %b, %c
  %x = and %a, %0
  %1 = or %d, %e
  cb %1, %ifbody, %ifend

ifbody:
  %y = and %d, %x
  br ifend

ifend:
  %y1 = phi [%y, %ifbody], [0, %entry]
  %z = or %x, %y1
  ret

Notice that every variable computed in the program is assigned once only. To ensure that %y is not assigned twice in different control paths, a new variable %y1 is introduced and given a unified value by the phi instruction.

More Examples

You can use the program icgrep to produce examples of Pablo source code and corresponding LLVM IR object code. Note that both the Pablo code it produces and the LLVM IR it produces is more complex than required for the assignment.

For example, to generate the code for the regular expression a[bc]d you can use the following commands.

• icgrep 'a[bc]d' -print-pablo
• icgrep 'a[bc]d' -dump-generated-IR

For an example involving while loops, you can use the following commands.

• icgrep 'a(bc)*d' -print-pablo
• icgrep 'a(bc)*d' -dump-generated-IR

You can download and compile the icgrep-1.00a source code (Linux or Mac OS X) using svn check-out.

• svn co http://parabix.costar.sfu.ca/svn/tags/icgrep-1.0

Alternatively, you can try the development version.

• svn co http://parabix.costar.sfu.ca/svn/parabix/icGREP

Reference Material

If you wish to produce LLVM IR rather than Pablo IR, you can consult the following tutorial.

• A Tutorial on Generating LLVM IR with Haskell

Due: Wednesday November 04 2015, 23:59