[m-rev.] for review: call-dependent structure reuse analysis

[Peter Wang]

On 2008-05-27, Julien Fischer <juliensf at csse.unimelb.edu.au> wrote:
>
> On Mon, 26 May 2008, Peter Wang wrote:
>>
>> 	When looking up reuse information for a procedure, if we don't have
>> 	that information we should take that assumed result is `optimal'.
>> 	Otherwise, the analysis results of mutually recursive procedures will
>> 	never get out of the `suboptimal' state.  (Other analyses make the
>> 	same mistake.)
>
> Which analyses?  (other than structure sharing below, or is that it?)

All the ones which use the analysis framework.

In case it wasn't clear, the problem is this.  Say M.P and N.Q are mutually
recursive procedures in different modules.  When we first analyse P it looks up
a result for Q.  If we guess some result for Q and assume that it's
`suboptimal' then the final result for P will probably have to be `suboptimal'.
When we analyse Q it will look up the result for P, and since it's marked
`suboptimal', the result for Q probably be `suboptimal' again.

I think the right way to use the analysis framework is to initially assume
that the guessed result for Q is `optimal'.  When we do analyse Q, if we end
up with a more precise result than what's in the analysis registry then the
whole of M will be marked as `suboptimal', so P would be reanalysed eventually.
That's assuming when analysing M that we recorded the assumed result for Q,
and that M depends on the result for Q.

>>
>> No speedtest yet as the analysis is too slow.  Here are some run times
>> for icfp2000 (--intermodule-analysis, asm_fast.gc).  The first float is
>> user time in seconds with CTGC enabled; the second is without CTGC.
>>
>> dice:       1 - 7.41 / 7.78 = 0.05
>> golf:       1 - 0.95 / 1.05 = 0.09
>> mtest7:     1 - 2.40 / 2.70 = 0.11
>> snowgoon:   1 - 4.97 / 5.05 = 0.02
>>
>> These memory calculations are based on GC_PRINT_STATS output as I
>> couldn't be bothered recompiling in .memprof.  The first number is total
>> allocated memory in bytes (up to the last GC) with CTGC; the second is
>> without CTGC.
>>
>> dice:       1 - 1496674496 / 1726076880 = 0.133
>> golf:       1 -  227425536 /  276405008 = 0.177
>> mtest7:     1 -  558735136 /  733795728 = 0.239
>> snowgoon:   1 -  971669520 / 1026713552 = 0.054
>
> What are the sizes of the executable?

4524960 bytes, ctgc
3973216 bytes, no ctgc
(stripped)

They're both linked to the same standard library (with some reuse procedures)
so the difference should be greater.

Peter

--------------------------------------------------------------------------
mercury-reviews mailing list
Post messages to:       mercury-reviews at csse.unimelb.edu.au
Administrative Queries: owner-mercury-reviews at csse.unimelb.edu.au
Subscriptions:          mercury-reviews-request at csse.unimelb.edu.au
--------------------------------------------------------------------------