none none none
none

Compiler



Papers

Interesting papers on programming languages (under construction)


Books

Good books on compiler construction:

  • Modern Compiler Design, Grune, Bal, Jacobs, Langendoen
  • Advanced Compiler Design Implementation, Steven S. Muchnick
  • High Performance Compilers for Parallel Computing, Michael Wolfe
  • Modern Compiler Implementation in Java Andrew W. Appel

.. and on programming language design in general:

  • Programming Language Design Concepts, David A. Watt

Generated Code

To debunk some myth about sneaky Java optimizations by saving some checks in a loop and instead catch the out-of-bound exception of the array that is iterated over to end the loop: It does not work - not on any tested compiler. I checked Sun's Hotspot on Linux (version 1.4.2 and 1.5.0), on Solaris 8 (version 1.2.2), on Mac OS X (version 1.4.2) and gcj on Linux (version 3.3), on Mac OS X (version 4.0.1). The compilers all succeed in removing the unnecessary 2nd check in the straight forward implementation; this makes the exception-driven loop even slower as the exception itself takes some extra time.
Here is the code so you can check for yourself:

public class Test {
  static int[] k;
  static int size = 10000000;

  public static void main( String args[] ) {
    long time_r = 0;
    long time_e = 0;

    for( int i = 0; i < 100; i++ ) {
      time_r += reasonable();
      k = null; //avoid out of memory exception
      time_e += exception();
      k = null; //avoid out of memory exception
    }
    System.out.println( "reasonable: " + time_r/100 );
    System.out.println( "exception:  " + time_e/100 );
  }

  public static long reasonable() {
    int i[] = new int[size];
    int j = 0;
    
    long time = System.currentTimeMillis();
    
    for( j = 0; j < i.length; j++ ) {
      i[j] = j;
    }

    time = System.currentTimeMillis() - time;

    k = i; //avoid removal of loop by compiler optimizations
    return time;
  }

  public static long exception() {
    int i[] = new int[size];
    int j = 0;

    long time = System.currentTimeMillis();

    try {
      while( true ) {
        i[j++] = j;
      }
    } catch( Exception e ) {}

    time = System.currentTimeMillis() - time;

    k = i; //avoid removal of loop by compiler optimizations
    return time;
  }
}

This C language example shows, that your compiler uses some kind of intermediate language. At least with gcc (3.3, 4.0) this code snippet produces identical binaries for each define (A, B, C, D). Of course everyone familiar with the Church-Turing Thesis shouldn't be too surprised... ;)

#include <stdio.h>

int main( char* args[] ) {
#ifdef A
  while(1) {
    printf( "hello" );
  }
#elif B
  do {
    printf( "hello" );
  } while(1);
#elif C
  mark:
    printf( "hello" );
    goto mark;
#elif D
  for(;;) {
    printf( "hello" );
  }
#endif
  return 0;
}

Optimization

Some links about compiler optimizations (under construction)


Parallelization


Parallel

Though not a parallelizing compiler, there are parallel compilers, too:

  • distcc, the parallel compiler

Tools

  • The LLVM compiler infrastructure, a compiler framework centered around an advanced intermediate language definition
  • flex, very well done scanner generator (flex doc)
  • bison, yacc compatible parser generator (bison doc)
  • treecc, a tool to create abstract syntax trees (integrates with yacc/bison). (treecc docs)
  • byacc, the BSD version of yacc
  • byaccj, extended BSD yacc that can e. g. generate Java code
  • lemon, the parser generator in use by sqlite
  • Java Cup, Java LALR parser generator
  • JLex, scanner generator for use with Java
  • gcc frontend howto, create your very own gcc frontend

Grammars

none
none none none
none none none
none Last touched on Thursday, 08-Nov-2007 13:03:49 CET, © Markus W. Weissmann none
none none none