[m-dev.] I want to move and rename the dependency_graph module

Zoltan Somogyi zoltan.somogyi at runbox.com
Wed Feb 15 17:36:09 AEDT 2017

On Wed, 15 Feb 2017 17:13:24 +1100, Paul Bone <paul at bone.id.au> wrote:
> Yeah, I thought so too.  Didn't we talk about this at lunch with Andy King
> once? 

I don't remember.

>  He mentioned supercompilation in passing and I hadn't heard of it.
> Basically you both said that it's something that searches the space of
> possible optimisations (or is it something else) and then picks the best?
> You both said that it only works for very small programs.  That made sense
> to me.

The basic idea is: for each N, there are only a finite number of machine language
programs consisting of N instructions. To supercompile a function in e.g. C, do this:

for N = 0 up to some limit:
  for every possible machine language program with exactly N instructions,
  with some exceptions:
     try to prove that its semantics is exactly the same as the C function
     you are trying to compile
     if the proof attempt is successful

The "some exceptions" part meant that for instructions that contain immediate values,
the supercompiler will typically explore only a fixed small set of immediates, such as
0, 1, -1, 2, -2, up to (say) 16, instead of all 2^16 possible values in a 16 bit field.
Even then, this is feasible only for VERY small values of N.

> > I was thinking about the safety of deleting the code of a C function
> > if all calls to that functions have been inlined. To do this, the C compiler
> > must be sure that noone has taken the address of the function anywhere,
> > which would require an analysis of the whole namespace in which the
> > function name is visible.
> It should know this if the function is static.


> I might be able to automate it, but it's probably equally easy to check each
> SCC by hand and make a tally.

Yes, if the number of SCCs is small enough.

> I have some similar code in the deep profiler that might be able to help.
> The benifit of that is that it can weight each by the number of calls made
> into and within the SCC.

I don't think we are looking for weighted information.


More information about the developers mailing list