Opened 4 years ago

Last modified 3 weeks ago

#5567 new task

LLVM: Improve alias analysis / performance

Reported by: dterei Owned by: dterei
Priority: normal Milestone: 7.12.1
Component: Compiler (LLVM) Version:
Keywords: Cc: jan.stolarek@…, brooks.brian@…, rwbarton, erikd, michalt
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: Runtime performance bug Test Case:
Blocked By: Blocking:
Related Tickets: Differential Revisions:

Description

  • 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.

Change History (18)

comment:3 Changed 4 years ago by igloo

  • Milestone set to 7.6.1

comment:4 Changed 3 years ago by 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

comment:5 Changed 3 years ago by dterei

Pushed some patches for doing TBAA with LLVM:

0f15f8a76d334becf992a83870d0b327cc3c40b6
71e5ee7d1656444ad23d0610ddaf9fc99a58b190

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

comment:6 Changed 3 years ago by 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.

comment:7 Changed 3 years ago by 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

comment:8 Changed 3 years ago by igloo

  • Milestone changed from 7.6.1 to 7.6.2

comment:9 Changed 2 years ago by carter

heres the commits as linked into github

commit one

commit two

commit three that improves stuff

adding -llvm-tbaa flag

has anyone looked into this topic more recently? Is there any low hanging fruit in this area?

comment:10 Changed 2 years ago by dterei

No, no one has. Depends on how 'low' you want the fruit. I think we have a number of ideas that are worth trying. They are discussed on the wiki page and the tickets it links to: http://hackage.haskell.org/trac/ghc/wiki/Commentary/Compiler/Backends/LLVM/Alias

Those ideas aren't too hard to implement and while we don't know, we do suspect they can be a big win in some situations. Finding someone with the time, knowledge and motivation to tackle them is hard though. It is a solid week or two of work probably to try them out properly.

comment:11 Changed 2 years ago by carter

ok, I'd be interested in spending some time on this ticket sometime in the next month or so. (or more realistically some part of the early summer, given how busy i am with work right now.)

I may try and dig into some simpler related tasks first, as a warm up/ improve my familiarity with some of the relevant bits, such as the task I just proposed in http://hackage.haskell.org/trac/ghc/ticket/7883

comment:12 Changed 2 years ago by jstolarek

  • Cc jan.stolarek@… added

comment:13 Changed 11 months ago by thoughtpolice

  • Milestone changed from 7.6.2 to 7.10.1

Moving to 7.10.1.

comment:14 Changed 10 months ago by brbr

  • Cc brooks.brian@… added
  • difficulty set to Unknown

comment:15 Changed 10 months ago by rwbarton

  • Cc rwbarton added

comment:16 Changed 5 months ago by thoughtpolice

  • Milestone changed from 7.10.1 to 7.12.1

Moving to 7.12.1 milestone; if you feel this is an error and should be addressed sooner, please move it back to the 7.10.1 milestone.

comment:17 Changed 3 months ago by erikd

  • Cc erikd added

comment:18 Changed 3 weeks ago by michalt

  • Cc michalt added
Note: See TracTickets for help on using tickets.