Unusual techniques in HLVM and

I just wrote a blog post detailing some of the techniques I adopted in =
HLVM
that appear to be unusual:

http://flyingfrogblog.blogspot.co.uk/2012/03/gc-safe-points-mutator-suspe=
nsi
on-and.html

In particular, HLVM uses many techniques that are much simpler than =
existing
alternatives but appear to be just as efficient.

In the process of writing that I thought of an interesting way to avoid
unnecessary pushes to the shadow stack. A previous benchmark indicated =
that
shadow stack manipulations can account for up to 70% of the total =
running
time of a program:

http://flyingfrogblog.blogspot.co.uk/2009/03/current-shadow-stack-overhea=
ds-
in-hlvm.html

So this theoretically has the potential to dramatically improve HLVM's
performance under certain circumstances (although I don't want to =
exaggerate
the potential advantages because HLVM's current GC is poorly suited for
allocation-intensive programs like that benchmark).

I wanted to avoid both caller and callee pushing the same value onto the
shadow stack. Obviously, there is no harm in just having the caller =
push. I
thought of an interesting solution: add the ability to mark a reference =
type
as "prepushed" and instantiate functions for any combination of =
prepushed
reference arguments as required by callers. This is a conservative
approximation so references default to non-prepushed. Between the push =
and
pop of a reference inside the body of a function it becomes prepushed =
and,
therefore, any callees receive a prepushed reference.

Now, an interesting development of this would be to mark all references
derived from prepushed references via immutable types as also being
prepushed. For example, consider the idiomatic non-tail recursive fold =
right
function over immutable singly-linked lists (OCaml/F# code):

let rec foldr f xs a =3D
  match xs with
  | x::xs -> f x (foldr f xs a)
  | [] -> []

The initial call to this recursive function will push the head of the =
list
onto the stack. As the list is immutable we know that the GC will find =
the
entire list to be reachable for the entire duration of all recursive =
calls.
A na=EFve solution would push references to every single node in the =
list onto
the stack but this new solution would only push the head of the list =
because
all of the other references are derived from the original via values of
immutable types. If the fold is accumulating an O(1) size value (e.g. a =
sum)
then most of the time is probably spent pushing references to list nodes =
and
pushing return addresses. If the VM "unrolls" the recursive calls as =
HLVM
does then pushes of return addresses are amortized and most of the time =
is
spent pushing reference to list nodes, in which case this optimization =
might
dramatically improve performance.

--=20
Dr Jon Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com