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

[Julien Fischer]

On Mon, 26 May 2008, Peter Wang wrote:

> Branches: main
>
> Add initial support for performing call-specific structure reuse analysis.
> If a call site violates the conditions for calling the reuse version of a
> procedure, it can request a different reuse version of the procedure with
> possibly laxer reuse conditions.  At least for now, I have chosen call
> patterns to simply be lists of argument positions, the arguments are which
> cannot be clobbered by the callee.

s/are which cannot/which cannot/

> Requests across module boundaries are supported when using the
> `--intermodule-analysis' option.
>
> This initial version does a lot of unnecessary reanalysis so must be switched
> on explicitly with a `--structure-reuse-repeat <n>' option.  This option
> shouldn't be needed in the future.
>
>
> compiler/options.m:
> 	Add a `--structure-reuse-repeat <n>' option.
>
> compiler/analysis.m:
> compiler/mercury_compile.m:
> 	Read in the `.request' file for the current module being analysed
> 	when we're preparing to use the intermodule analysis framework.
>
> 	Don't return duplicates when looking up analysis requests.
>
> compiler/structure_reuse.analysis.m:
> 	Read in old reuse analysis answers and new requests when using
> 	`--intermodule-analysis'.  Make procedures corresponding to old
> 	Answers (as expected by other modules) and new requests (so we
> 	analyse the procedures with the requested call patterns).
>
> 	When `--structure-reuse-repeat' is used, use the requests from the
> 	latest indirect reuse pass to create new reuse procedures with the
> 	extra constraints on some of the head variables (that they must not
> 	be clobbered).  Perform direct reuse analysis on those procedures,
> 	then repeat indirect reuse on the whole module so those new
> 	procedures might be called.
>
> 	Record intermodule requests when using `--intermodule-analysis'.
>
> 	Delete reuse versions of procedures we may have created, which after
> 	analysis turn out to have no reuse opportunities at all.
>
> compiler/structure_reuse.lfu.m:
> 	Add a procedure that adds a set of variables to all the
> 	local-forward-use sets of a procedure.
>
> compiler/structure_reuse.direct.m:
> 	Add code to perform direct reuse on a specific list of procedures
> 	instead of all the procedures in a module.
>
> compiler/structure_reuse.indirect.m:
> 	Add code to re-run indirect reuse analysis which when analysing an
> 	SCC also analyses the reuse versions of procedures that were created
> 	from the procedures in the SCC.
>
> 	Remember and return intra- and inter-module requests when existing
> 	reuse procedures can't be called, for later passes and for later
> 	analyses of other modules.
>
> 	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?)

> compiler/structure_reuse.domain.m:
> 	Extend the `reuse_as_table' with a mapping from an original
> 	(non-reuse) procedure plus call pattern to the procedure which
> 	actually implements that reuse.
>
> 	Make `reuse_as_satisfied' try to return all of the variables at a call
> 	site that violate the reuse conditions.  That is, instead of just
> 	giving one reason that a reuse procedure call can't be made, try to
> 	return all the reasons so we don't waste effort requesting laxer reuse
> 	procedures which wouldn't be lax enough for the call site anyway.
>
> compiler/structure_reuse.versions.m:
> 	Account for multiple reuse versions of procedures.
>
> compiler/prog_util.m:
> 	Use `make_pred_name' to make the names for reuse predicates.
>
> compiler/hlds_goal.m:
> compiler/hlds_out.m:
> 	Record in HLDS goals which reuse version of a procedure to call,
> 	since there can be multiple to choose from.
>
> compiler/hlds_module.m:
> compiler/trans_opt.m:
> 	Replace the `structure_reuse_map' field in the module structure by a
> 	simple set of pred_ids of reuse predicates.  The old map from
> 	procedures to their reuse counterparts is not needed outside of the
> 	structure reuse passes, which has the same information in a separate
> 	table anyway.
>
> compiler/structure_sharing.analysis.m:
> 	Assume guessed structure sharing answers are `optimal' instead of
> 	`suboptimal', as above.
>
> compiler/structure_reuse.direct.choose_reuse.m:
> compiler/structure_reuse.direct.detect_garbage.m:
> 	Module import changes.
>
>
> ===================================================================
>
> 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?

The diff looks okay.

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