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

[Zoltan Somogyi]

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
        exit

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.

Yes.

> 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.

Zoltan.