Type Inference

I just finished implementing a type inference algorithm based off of FALCON  [1]. I like this algorithm for several reasons

1. The efficiency is O(n): This is important because we should minimize JIT overhead.
2. Decouples type inference from code generation: This will make it easier if we decide to switch from LLVM to a GNU equivalent.
3. Type bounds are good: The algorithm is able to assign different types to the same variable when the variable is used in different contexts.

The algorithm works by introducing a type lattice (also similar to the MaJIC and McVM MATLAB JIT compilers[2][3]). For example, the simple lattice I am currently using

Each variable in the SSA is then assigned a type from our lattice. For example, in the code

b = 1;
for i=0:5
  temp = 5;
  b = b + temp;

  temp = [5 5 5];
  b = b + temp;
endfor

The algorithm is able to differentiate between the two occurrences of temp. The algorithm will also realizes that b is a matrix inside of the loop (once matrices are added to type type lattice). Then before the start of the loop, b, will be converted to a single element matrix. This means we can generate matrix addition operations inside of the loop.

[1] L. D. Rose and D. Padua. Techniques for the Translation of MATLAB Programs into Fortran 90. ACM Transactions on Programming Languages and Systems, 21(2):286–323, Mar. 1999.
[2]George Almási and David Padua. 2002. MaJIC: compiling MATLAB for speed and responsiveness. SIGPLAN Not. 37, 5 (May 2002), 294-303.
[3] M.Sc. Thesis - McVM: an Optimizing Virtual Machine for the MATLAB Programming Language