LLVM: Improve alias analysis / performance

[dterei]

• LLVM doesn't generate as good as code as we feel it should in many situations
• Why?
  • We've often felt its a alias anlysis issue.
  • I'm a little more doubtful of that than others (I feel its part of the bigger problem, not the whole thing).
  • I think there may be some register allocation / instruction selection / live range splitting issue going on.
• We could also do with looking at what optimisation passes we should run and in what order...

Here is some work Max did on the alias issue, his results for nofib weren't good:

 http://blog.omega-prime.co.uk/?p=135

So this ticket is just a high level ticket about figuring out and improving the performance of LLVM backend.

[dterei]

 http://dterei.blogspot.com/2011/09/ghc-project-for-all.html

[dterei]

 http://llvm.org/bugs/show_bug.cgi?id=1512

[dterei]

Johan and I have started some work on this, wiki page about it is here:

 http://hackage.haskell.org/trac/ghc/wiki/Commentary/Compiler/Backends/LLVM/Alias

[dterei]

Pushed some patches for doing TBAA with LLVM:

0f15f8a76d334becf992a83870d0b327cc3c40b6 71e5ee7d1656444ad23d0610ddaf9fc99a58b190

No improvement to nofib, haven't tried other benchmarks to see.

[dterei]

OK, tried this benchmark:

module Main(main) where

import Data.Array.Base
import Data.Array.IO
import Data.Array.MArray

main :: IO ()
main = do
    arr <- newArray_ (0, 200)
    go arr 2 0 100

go :: IOUArray Int Int -> Int -> Int -> Int -> IO ()
go arr stride x y | x < y     = do unsafeWrite arr (x * stride) 1337
                                   go arr stride (x + 1) y
                             | otherwise = return ()

And not working as I seem to be adding the TBAA info wrong. I think we need an unknown type (for pointers loaded from RX registers) that doesn't alias Sp.

[dterei]

Pushed an improvement: e10589a505b44f4f0394500c6a0d2db5baa7f3f4

This gets the good code generated for the above benchmark improving performance by around 20%! Also added control to enable or disable if TBAA is used with: ba52053b95ccb417ca7ce08e85a45e49b5f49b0a