Features Download
From: Filip Pizlo <fpizlo <at> apple.com>
Subject: Re: whole program optimization examples?
Newsgroups: gmane.comp.compilers.llvm.devel
Date: Sunday 12th October 2014 06:37:44 UTC (over 3 years ago)
> On Oct 10, 2014, at 6:24 PM, Hayden Livingston 
> Hello,
> I was wondering if there is an example list somewhere of whole program
optimizations done by LLVM based compilers?
> I'm only familiar with method-level optimizations, and I'm being told wpo
can deliver many great speedups.
> My language is currently staticly typed JIT based and uses the JVM, and I
want to move it over to LLVM so that I can have options where it can be
ahead of time compiled as well.

As Philip kindly pointed out, WebKit uses llvm as part of a JavaScript JIT
optimization pipeline. It works well for WebKit, but this was a large
amount of work. It may not be the path of least resistance depending on
what your requirements are. 

> I'm hearing bad things about LLVM's JIT capabilities -- specifically that
writing your own GC is going to be a pain.

This is a fun topic and you'll probably get some good advice. :-)

Here's my take. GC in llvm is only a pain if you make the tragic mistake of
writing an accurate-on-the-stack GC. Accurate collectors are only known to
be beneficial in niche environments, usually if you have an aversion to
probabilistic algorithms. You might also be stuck requiring accuracy if
your system relies on being able to force *every* object to *immediately*
move to a new location, but this is an uncommon requirement - usually it
happens due to certain speculative optimization strategies in dynamic

My approach is to use a Bartlett-style mostly-copying collector. If you use
a Bartlett-style collector then you don't need any special support in llvm.
It just works, it allows llvm to register-allocate pointers at will, and it
lends itself naturally to high-throughput collector algorithms.
Bartlett-style collectors come in many shapes and sizes - copying or not,
mark-region or not, generational or not, and even a fancy concurrent
copying example exists. 

WebKit used a Bartlett-style parallel generational sticky-mark copying
collector with opportunistic mark-region optimizations. We haven't written
up anything about it yet but it is all open source.

Hosking's paper about the concurrent variant is here: http://dl.acm.org/citation.cfm?doid=1133956.1133963

I highly recommend reading Bartlett's original paper about conservative
copying; it provides an excellent semi space algorithm that would be a
respectable starting point for any VM. You won't regret implementing it -
it'll simplify your interface to any JIT, not just llvm. It'll also make
FFI easy because it allows the C stack to refer directly to GC objects
without any shenanigans. 

Bartlett is probabilistic in the sense that it may, with low probability,
increase object drag. This happens rarely. On 64-bit systems it's
especially rare. It's been pretty well demonstrated that Bartlett
collectors are as fast as accurate ones, insofar as anything in GC land can
be demonstrated (as in it's still a topic of lively debate, though I had
some papers back in the day that showed some comparisons). WebKit often
wins GC benchmarks for example, and we particularly like that our GC never
imposes limitations on llvm optimizations. It's really great to be able to
view the compiler and the collector as orthogonal components!

> Anyways, sort of diverged there, but still looking for WPO examples!
> Hayden.
> _______________________________________________
> LLVM Developers mailing list
> [email protected]         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
CD: 4ms