[Caml-list] compiler storage allocation choices

[Caml-list] compiler storage allocation choices

[Charles Martin]

I am recasting an earlier query about storage allocation choices made by
the compiler.  Please consider the following excerpt from a complex number
package:

type t = { mutable r : float; mutable i : float }
let make r i = { r = r; i = i }
let ncopy a b = a.r <- b.r; a.i <- b.i
let add a b = make (a.r +. b.r) (a.i +. b.i)

The idea is that "destructive" operations will be coded using "pure"
functions such as add, only ncopying the result at the conclusion of what
might be a complex expression, eg, z = (z + z')^2 / z'', or whatever.

As an example, consider a destructive add, coded two possible ways:

let nadd1 a b c = ncopy a (add b c)
let nadd2 a b c = let r = b.r +. c.r and i = b.i +. c.i in a.r <- r; a.i <- i

The first, nadd1, is an example of the desired coding style, only doing the
ncopy at the end, and built out of pure building blocks like add.  The
second, nadd2, is a hand-coded version that just does the job.

Now check out the dump of the "C--" generated by the compiler:

532 $ ocamlopt -c -S -inline 3 -dcmm complex.ml 

(function Complex_nadd1_63 (a/64: addr b/65: addr c/66: addr)
 (let
   b/82
     (let
       (r/86 (+f (load float64u b/65) (load float64u c/66))
        i/87 (+f (load float64u (+a b/65 8)) (load float64u (+a c/66 8))))
       (alloc 4350 r/86 i/87))
   (store float64u a/64 (load float64u b/82))
   (store float64u (+a a/64 8) (load float64u (+a b/82 8))) 1a))

(function Complex_nadd2_67 (a/68: addr b/69: addr c/70: addr)
 (let
   (r/84 (+f (load float64u b/69) (load float64u c/70))
    i/85 (+f (load float64u (+a b/69 8)) (load float64u (+a c/70 8))))
   (store float64u a/68 r/84) (store float64u (+a a/68 8) i/85) 1a))

The C-- code is identical, except that the first version stores the results
in an intermediate allocated block.  Note that this allocated block does
not escape.

The native code for nadd1 includes a heap allocation and gc check, while
the native code for nadd2 does everything on the stack.

It seems like some escape analysis here would allow nadd1 to generate the
same code as nadd2.  So now my questions are:

(1) Would this in fact be a useful addition to the compiler?

(2) Is something like this already in the works?

(3) If not, perhaps the team has some pointers as to where in the compiler
    flow (in terms of specific functions) such analysis would be best
    inserted, which representation it should consume and produce, and any
    known gotchas that would stand in the way of trying to add such an
    analysis?

Thanks!

Charles

__________________________________________________
Do You Yahoo!?
Get personalized email addresses from Yahoo! Mail
http://personal.mail.yahoo.com/
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr