[m-dev.] I want to move and rename the dependency_graph module
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
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