The Glasgow Haskell Compiler and LLVM

What is GHC and Haskell

Existing pipeline

Why an LLVM backend?

• Offload work: Building a high performance compiler backend is a huge amount of work, LLVM for example was started around 10 years ago. Going forward, the LLVM backend should be a lot less work to maintain and extend than either the C backend or NCG. It will also benefit from any future improvements to LLVM.
• Optimisation passes: GHC does a great job of producing fast Haskell programs. However, there are a large number of lower level optimisations (particularly the kind that require machine specific knowledge) that it doesn't currently implement. Using LLVM should give us most of them for free.
• The LLVM Framework: Perhaps the most appealing feature of LLVM is that it has been designed from the start to be a compiler framework. For researchers like the GHC developers, this is a great benefit and makes LLVM a very fun playground. For example, within a couple of days of the public release of the LLVM backend one developer, Don Stewart, wrote a genetic algorithm to find the best LLVM optimisation pipeline to use for various Haskell programs (you can find his blog post about this here).

Show me the speed

• if n is even, the next number is n/2
• if n is odd, the next number is 3n + 1
• if n is 1, stop.

#include <stdio.h>

int main(int argc, char **argv) {
   int longest = 0, terms = 0, this_terms = 1, i;
   unsigned long j;

   for (i = 1; i < 1000000; i++) {
      j = i;
      this_terms = 1;

      while (j != 1) {
         this_terms++;
         j = j % 2 == 0 ? j / 2 : 3 * j + 1;
      }

      if (this_terms > terms) {
         terms = this_terms;
         longest = i;
      }
   }
   printf("longest: %d (%d)\n", longest, terms);
   return 0;
}

--------

import Data.Word

collatzLen :: Int -> Word32 -> Int
collatzLen c 1 = c
collatzLen c n | n `mod` 2 == 0 = collatzLen (c+1) $ n `div` 2
               | otherwise      = collatzLen (c+1) $ 3*n+1

pmax x n = x `max` (collatzLen 1 n, n)

main = print . solve $ 1000000
    where solve xs = foldl pmax (1,1) [2..xs-1]

• GHC-6.13 (NCG): 2.876s
• GHC-6.13 (C): 0.576s
• GHC-6.13 (LLVM): 0.516s
• Clang-1.1: 0.526s
• GCC-4.4.3: 0.335s

import Control.Parallel
import Data.Word

collatzLen :: Int -> Word32 -> Int
collatzLen c 1 = c
collatzLen c n | n `mod` 2 == 0 = collatzLen (c+1) $ n `div` 2
               | otherwise      = collatzLen (c+1) $ 3*n+1

pmax x n = x `max` (collatzLen 1 n, n)
main = print soln
   where
      solve xs = foldl pmax (1,1) xs
      s1 = solve [2..500000]
      s2 = solve [500001..999999]
      soln = s2 `par` (s1 `pseq` max s1 s2)

• GHC-6.13 (Parallel, LLVM): 0.312

• GHC (NCG): 29.499
• GHC (C): 29.043
• GHC (LLVM): 20.774

Backend overview

The new calling convention

Evaluation of the backend

Problems with backend

Success of LLVM?

> [Chris Lattner]: Talking about what you think is good and what you think should be improved in LLVM would also be great. :)

Future