[m-rev.] for review: conditional structure reuse for LLDS backends

[Julien Fischer]

On Wed, 30 Jan 2008, Peter Wang wrote:

> [Pending bootchecks in more grades.]

Could you please post some benchmarks between conditional structure
reuse / structure reuse without static data / no structure reuse,
at some point.

> Estimated hours taken: 15
> Branches: main
>
> Implement conditional structure reuse for LLDS backends using Boehm GC.
> Verify at run time, just before reusing a dead cell, that the base address of
> the cell was dynamically allocated.  If not, fall back to allocating a new
> object on the heap.  This makes structure reuse safe without having to disable
> static data.
>
> In the simple case, the generated C code looks like this:
>
>    MR_tag_reuse_or_alloc_heap(dest, tag, addr_of_reuse_cell,
> 	MR_tag_alloc_heap(dest, tag, count));
>    ...assign fields...
>
> If some of the fields are known to already have the correct values then we can
> avoid assigning them.  We need to handle both reuse and non-reuse cases:
>
>    MR_tag_reuse_or_alloc_heap_flag(dest, flag_reg, tag, addr_of_reuse_cell,
> 	MR_tag_alloc_heap(dest, tag, count));
>    /* flag_reg is non-zero iff reuse is possible */
>    if (flag_reg) {
> 	goto skip;
>    }
>    ...assign fields which don't need to be assigned in reuse case...
>  skip:
>    ...assign fields which must be assigned in both cases...
>
> It may be that it is not worth the branch to avoid assigning known fields.
> I haven't yet checked.
>
>
> compiler/llds.m:
> 	Extend the `incr_hp' instruction to holds information for structure
> 	reuse.

s/holds/hold/

> compiler/code_info.m:
> 	Generate a label and pass it to `var_locn_assign_cell_to_var'.  The
> 	label is only needed for the type of code shown above.
>
> compiler/var_locn.m:
> 	Change the code generated for cell reuse.  Rather than assigning the
> 	dead cell's address to the target lval unconditionally, generate an
> 	`incr_hp' instruction with the reuse field filled in.
>
> 	Generate code that avoids filling in known fields if possible.
>
> 	Abort if we see `construct_statically(_)' in
> 	`var_locn_assign_dynamic_cell_to_var'.
>
> runtime/mercury_heap.h:
> 	Add a macro to check if an address is between
> 	`GC_least_plausible_heap_addr' and `GC_greatest_plausible_heap_addr',
> 	which are therefore in the heap.
>
> 	Add macros to conditionally reuse a cell or otherwise fall back to
> 	allocating a new object.
>
> compiler/llds_out.m:
> 	Call the new macros in `mercury_heap.h' for `incr_hp' instructions
> 	with reuse information filled in.
>
> compiler/dupelim.m:
> compiler/dupproc.m:
> compiler/exprn_aux.m:
> compiler/global_data.m:
> compiler/jumpopt.m:
> compiler/livemap.m:
> compiler/llds_to_x86_64.m:
> compiler/middle_rec.m:
> compiler/opt_debug.m:
> compiler/opt_util.m:
> compiler/reassign.m:
> compiler/unify_gen.m:
> compiler/use_local_vars.m:
> 	Conform to the changed `incr_hp' instruction.
>
>

...

> Index: runtime/mercury_heap.h
> ===================================================================
> RCS file: /home/mercury/mercury1/repository/mercury/runtime/mercury_heap.h,v
> retrieving revision 1.39
> diff -u -r1.39 mercury_heap.h
> --- runtime/mercury_heap.h	21 Aug 2007 06:22:04 -0000	1.39
> +++ runtime/mercury_heap.h	30 Jan 2008 03:58:00 -0000
> @@ -33,7 +33,7 @@
> #include "mercury_context.h"            /* for min_heap_reclamation_point() */
> #include "mercury_heap_profile.h"       /* for MR_record_allocation() */
> #include "mercury_deep_profiling.h"     /* for MR_current_call_site_dynamic */
> -#include "mercury_std.h"               /* for MR_EXTERN_INLINE */
> +#include "mercury_std.h"                /* for MR_EXTERN_INLINE */
> #include "mercury_reg_workarounds.h"    /* for MR_memcpy */
> #include "mercury_debug.h"              /* for MR_debugtagoffsetincrhp* */
> #ifdef MR_HIGHLEVEL_CODE
> @@ -47,6 +47,8 @@
>   #ifdef MR_BOEHM_GC
>     #define GC_I_HIDE_POINTERS
>     #include "gc.h"
> +    #include "gc_mark.h"                /* for GC_least_plausible_heap_addr */
> +                                        /* GC_greatest_plausible_heap_addr */
>   #endif
> #endif
>
> @@ -396,6 +398,59 @@
> /***************************************************************************/
>
> /*
> +** Macros to implement structure reuse, conditioned on whether the structure

s/conditioned/conditional/

> +** to reuse is really dynamically allocated. If not, fall back to allocating
> +** a new object on the heap.
> +*/
> +
> +#define     MR_reuse_or_alloc_heap(dest, reuse, fallback_alloc)             \
> +            MR_tag_reuse_or_alloc_heap((dest), 0, (reuse), (fallback_alloc))
> +
> +#define     MR_reuse_or_alloc_heap_flag(dest, flag, reuse, fallback_alloc)  \
> +            MR_tag_reuse_or_alloc_heap((dest), 0, (flag), (reuse),          \
> +                (fallback_alloc))
> +
> +#define     MR_tag_reuse_or_alloc_heap(dest, tag, reuse, fallback_alloc)    \
> +            do {                                                            \
> +                MR_bool dummy;                                              \
> +                MR_tag_reuse_or_alloc_heap_flag((dest), (tag), dummy,       \
> +                    (reuse), (fallback_alloc));                             \
> +                (void) dummy;                                               \
> +            } while (0)
> +
> +#ifdef MR_BOEHM_GC
> +
> +  #define   MR_in_heap_range(addr)                                          \
> +            ((void *) (addr) >= GC_least_plausible_heap_addr &&             \
> +             (void *) (addr) < GC_greatest_plausible_heap_addr)             \
> +
> +#else /* ! MR_BOEHM_GC */

Is it still possible to use non-conditional structre reuse with the LLDS
backend?  If so, how do I do it?  If not, there should be a
developer-only option that does that.

The diff looks fine otherwise.

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