Re: What's wrong with alloca() ?

In article 91-12-081 preston@dawn.cs.rice.edu (Preston Briggs) writes:
>So, we seem to want several sorts of memory allocation, with special case
>allocators tuned to the special cases that arise in code. When I said
>this to a friend (Scott Warren), he pointed out that we actually want
>optimizers that recognize our patterns of usage, and handle the special
>cases specially.
>
>Of course, people have worked on this problem.
>David Chase is a good example. Are there others?


Yes, certainly.


Jack Schwartz (and others at NYU) did work along these lines for SETL
years ago.


Muchnick and Jones did several papers over the years.


Jeff Barth had a paper on this subject in CACM some years ago.


Paul Hudak (and others) have attacked the "aggregate update problem",
which is an important special case for functional languages.


There's been a bunch of work over the years in the "abstract
interpretation" community. Names I recall off-hand are Meira and Mycroft.


Much of the work on Lisp and Scheme compilers has attacked the problems of
efficient allocation of activation records and numbers.


Christina Ruggieri has a thesis and a paper or two on the subject.


Lucy Hederman did a masters thesis on the subject at Rice; you might be
able to lay your hands on a copy of that. It has real live results in it,
too.


Work by Jim Larus and by Laurie Hendren and by Anne Neirynck and by K.
Gopinath, all intended (I think) to attack the problem of discovering
available parallelism (through the detection of aliases and non-aliases)
can be (fairly) easily converted into solving memory use problems.


Phil Pfeiffer has been working on some of the theoretical underpinnings, I
think (i.e., how do we know that our analysis is correct?)


The most recent paper I wrote had two co-authors, Mark Wegman and Ken
Zadeck. The focus there (besides correctness) was heuristics, algorithms,
and speed.


I've probably forgotten some people, and there's almost certainly been
more recent work that I am ignorant of.


The good news is: we're getting there, and for special cases (Lisp
closures) compilers seem to do a good job.


The bad news is: for general solutions, in certain ugly but popular
languages, it is hard. (It's much easier for functional languages than it
is for languages with side-effects.) Three big problems are:


        (1) interprocedural information is mandatory


        (2) if you go very far down linked lists, your lattices can get
                unmanageably large. Much of the work done has involved tricks
                for keeping lattices manageable.


        (3) incomplete information is viral. If you ever fail to know
                what a procedure will do, and you pass a pointer as a
                parameter to that procedure, then you must make worst-case
                assumptions about subsequent use of the pointer.


My current (informal, since right now I'm working more on writing
compilers for ugly lanugages than I am on theory) approaches to the
problem are:


      (1) Whole-program analysis.
      (2) Optimistic analysis (pointers point nowhere, procedures
              never return).
      (3) Try "factoring" the lattices to reduce their size.


If I had more time, I'd post a bibliography. Oh yeah, Olin Shivers'
thesis is worth looking at if you are interested in #1 and #2.


David Chase
Sun
--

Return to the comp.compilers page.
Search the comp.compilers archives again.