2004/06/20: ic-0.3

The "I" compiler can now perform simple tree-based optimization like constant folding (as long as associativity does not need to be changed) and elimination of constant conditions and their unreachable branches.

2004/06/19: ic-0.2

Initial release of the "I" compiler.

This is version 0.3 of the "I" compiler. It should be a fully functional "I" compiler with some simple tree-based optimization.

I provide the complete source code here.

Source:		IC.tar.gz   [30kb gzipped source tarball]
Version:		ic-0.3, mii-0.4   (2004-06-20)
Author:		Wolfgang Wieser   (report bugs here)
License:		GNU GPL (Version 2)
Requires:		gcc, flex, bison

The archive contains 2 directories, mii which contains the MI interpreter and ic for the I compiler. In order to compile the code, you need flex, bison and gcc. (I am using flex-2.5.31, bison-1.875a, gcc-3.4.1pre.) Note that you must build mii first before compiling ic because the latter depends on the former.
Simply calling make in mii and in ic should do the trick.

The original design proposal by F. Bry was modified slightly: This implementation features:

• Comments. Like in C/C++ and other languages using // and /*...*/.
• More operators: &,|,% for and, or, modulo.
• Verbose assembler comments.

The current implementation does the following optimizations, most of them need to be enabled using option -Ot:

• Leaving away any unused variables and constants and procedures which are called from nowhere, including those which become unused because optimization removed all references to them.
• Constant folding as long as associativity does not need to be changed.
  (I.e. var+1+2 will not get optimized but 1+2+var will get 3+var.)
• Constant condition elimination (including removal of unreachable code).

This compiler is effectively three/four-step:

1. Parsing: First, the file is lexically analyzed and parsed to generate a tree representation from the input. This is done with the help of well-known flex and bison. This step was separated to allow for an alternative LL(1) top-down parser instead of the current LR(1) bottom-up parser.
2. Registration: Performs all identifier lookups (procedure and variable names).
3. Tree-based optimization: Perform optimization on tree representation if enabled with option -Ot.
4. Code generation: Actually generate the assembler code. This is splitted from the previous pass to allow for an tree-based optimization pass in between.

As an example, let us consider the following code (some similar code is part of the source code archive above).

/* test.i: Small I test program. */

program prog;
    var x,y,product,n,fac;
    
    procedure Mul;
        var a;
        begin
            product:=0;
            a:=y;
            while not a<1 do begin
                product:=product+x;
                a:=a-1
            end
        end;
    
    procedure Faculty;
        begin
            if n>1 then begin
                //fac:=fac*n;
                x:=fac;
                y:=n;
                CALL Mul;
                fac:=product;
                n:=n-1;
                call Faculty
            end
        end;
    
    procedure Bar2;
        const a=33,g=99;
        var a,b;
        begin
            x:=1+a;
            b:=a;
            read g
        end;
    
    begin
        read x; read y; call Mul; write product;
        read n; fac:=1; call Faculty; write fac
    end.

Compiling this code will yield a waning and errors:

bash# ./icomp --help
USAGE: icomp [options...] input_file
options:
  --help      print this help
  --version   print version information
  -va         emit verbose assembler code
  -nw         switch off warnings
  -Ot         perform tree-based optimizations
  -o file.mi  set output file
input_file: I-file to compile (max one)

I compiler version 0.3 (c) 2004 by Wolfgang Wieser
Compiler for pretty minimalistic imperative PASCAL-like programming
language called "I" (based on design by F. Bry).
bash# ./icomp test.i
Compiling: test.i -> test.mi:
test.i:32:[20..21]: error: variable "a" already declared
test.i:31:[22..23]: error:   this is the location of the previous declaration
test.i:36:[24..28]: error: assignment to constant value "g"
test.i:30:[8..17]: warning: unused procedure "Bar2"

So, let's correct that (by removing the "a" in the var decl and remove the read operation). Furthermore, I use -va to enable verbose assembler output and -nw do disable all warnings.

bash# ./icomp -va -nw test.i
Compiling: test.i -> test.mi:

The compiled assembler code will look like this:

# Program "prog" compiled by icomp-0.2 (56 insns)
# 000000
    RST
    INC 5
    JMP 41      # to prog (used=0)
    INC 1
    LIT 0
    STO 1 5      # product (0)
    LOD 1 4      # y (0)
    STO 0 3      # a (1)
    JMP 17      # while @11:30 (jump to condition)
    LOD 1 5      # product (0)
# 000010
    LOD 1 3      # x (0)
    OPR +      # @12:48
    STO 1 5      # product (0)
    LOD 0 3      # a (1)
    LIT 1
    OPR -      # @13:36
    STO 0 3      # a (1)
    LOD 0 3      # a (1)
    LIT 1
    OPR <      # @11:35
# 000020
    OPR !      # @11:30
    JOT 9      # while @11:30 (loop jump)
    RET      # from Mul
    INC 0
    LOD 1 6      # n (0)
    LIT 1
    OPR>      # @19:28
    JOF 40      # if @19:27
    LOD 1 7      # fac (0)
    STO 1 3      # x (0)
# 000030
    LOD 1 6      # n (0)
    STO 1 4      # y (0)
    CAL 1 3      # Mul (0)
    LOD 1 5      # product (0)
    STO 1 7      # fac (0)
    LOD 1 6      # n (0)
    LIT 1
    OPR -      # @25:36
    STO 1 6      # n (0)
    CAL 1 23      # Faculty (0)
# 000040
    RET      # from Faculty
    REA      # from x
    STO 0 3      # x (0)
    REA      # from y
    STO 0 4      # y (0)
    CAL 0 3      # Mul (0)
    LOD 0 5      # product (0)
    WRI
    REA      # from n
    STO 0 6      # n (0)
# 000050
    LIT 1
    STO 0 7      # fac (0)
    CAL 0 23      # Faculty (0)
    LOD 0 7      # fac (0)
    WRI
    HLT

This code can now be execured using the MI interpreter:

bash# ../mii/miinterp test.mi
MI Abstract Machine version 0.4 (c) Wolfgang Wieser. Stack size 4096
miinterp: Read 56 instructions from "test.mi".
Read=10
Read=12
Write=120
Read=10
Write=3628800
miinterp: Normal termination after executing 1163 instructions.
miinterp: State: T=7, B=0, P=55

The MI interpreter can also dump the executed commands and the stack if desired:

bash# ../mii/miinterp -it -st test.mi
MI Abstract Machine version 0.4 (c) Wolfgang Wieser. Stack size 4096
miinterp: Read 56 instructions from "test.mi".
Executing: 000000:     RST
Stack content:
   000000:          0  B DL
   000001:          0  RA
   000002: -->      0  T SL
Executing: 000001:     INC 5
Stack content:
   000000:          0  B DL
   000001:          0  RA
   000002:          0  SL
   000003:         -1
   000004:         -1
   000005:         -1
   000006:         -1
   000007: -->     -1  T
Executing: 000002:     JMP 41
Stack content:
   000000:          0  B DL
   000001:          0  RA
   000002:          0  SL
   000003:         -1
   000004:         -1
   000005:         -1
   000006:         -1
   000007: -->     -1  T
Executing: 000041:     REA
Read=1
Stack content:
   000000:          0  B DL
   000001:          0  RA
   000002:          0  SL
   000003:         -1
   000004:         -1
   000005:         -1
   000006:         -1
   000007:         -1
   000008: -->      1  T
(...and so on...)