This is the mail archive of the
mailing list for the GCC project.
Re: [Patch] Factor self-referential size trees into functions
- From: Richard Guenther <richard dot guenther at gmail dot com>
- To: Eric Botcazou <ebotcazou at adacore dot com>
- Cc: gcc-patches at gcc dot gnu dot org
- Date: Mon, 29 Jun 2009 12:09:31 +0200
- Subject: Re: [Patch] Factor self-referential size trees into functions
- References: <email@example.com>
On Mon, Jun 29, 2009 at 10:26 AM, Eric Botcazou<firstname.lastname@example.org> wrote:
> as explained during last year's summit, types with self-referential size exist
> in Ada and can have an arbitrary complexity. ?For these types, an object has
> a size that depends on its contents, i.e. on one or more fields present in
> the object. ?Technically this means that the TYPE_SIZE is an expression that
> contains one or more PLACEHOLDER_EXPRs and the DECL_SIZE for a particular
> object is obtained by substituting the value of fields in the object for the
> PLACEHOLDER_EXPRs in the expression. ?See SUBSTITUTE_PLACEHOLDER_IN_EXPR.
> The complexity can quickly grow with multiple levels of self-referentialness.
> In this case, the TYPE_SIZE can be a huge expression with dozens of nodes that
> cannot be folded before substitution and may even need to be used directly
> when pointers to these types come into play; it gets copied over and over,
> then gimplified and expanded multiple times, leading to long compilation
> times and bloated code.
> The approach proposed in the attached patch (and used for about 3 years in
> AdaCore's compiler) is to factor out these self-referential size trees into
> functions and replace them with call expressions; these expressions are cheap
> to manipulate and copy, and the size functions can be integrated back by the
> inliner if it deems this profitable, otherwise they are emitted or discarded.
> The main points of the patch are:
> ?1. discovery/construction of functions in stor-layout.c:self_referential_size
> invoked through variable_size when PLACEHOLDER_EXPRs are detected, with the
> help of tree.c:find_substitute_in_expr.
> ?2. more aggressive propagation of TREE_READONLY in expressions. ?Expressions
> cannot be factored out if they contain SAVE_EXPRs so superfluous SAVE_EXPRs
> must be eliminated as much as possible by tracking the TREE_READONLYness.
This should be separately tested/committed. The PROCESS_ARG
change, build3_stat and the process_call_operands change are ok.
> ?3. re-integration of size functions into expressions. ?This is necessary in a
> few cases to compute properties of types at compile time and is implemented
> as a limited form of inlining on trees.
Hm, do you really need to avoid unsharing trees or is this an
optimization? I don't like the tree-inline.c dependency you
create for tree.c here - I don't have really a better place, but I
wonder if we can move some of this stuff into gigi via a langhook
(all the substitute-in-placeholder stuff)?
I guess if we would do gimplification unit-at-a-time then the
special-handling of size functions could go.
> This should only affect the Ada compiler (although I presume 2. can marginally
> help the other compilers) and dramatically help for code with multiple levels
> of discriminated types (for our favorite example at -O0: code size divided by
> 2 and compilation time by 4).
> Tested on i586-suse-linux and x86_64-suse-linux, OK for mainline?
> 2009-06-29 ?Eric Botcazou ?<email@example.com>
> ? ? ? ?* cgraphunit.c (cgraph_finalize_compilation_unit): Call
> ? ? ? ?finalize_size_functions before further processing.
> ? ? ? ?* stor-layout.c: Include cgraph.h, tree-inline.h and tree-dump.h.
> ? ? ? ?(variable_size): Call self_referential_size on size expressions
> ? ? ? ?that contain a PLACEHOLDER_EXPR.
> ? ? ? ?(size_functions): New static variable.
> ? ? ? ?(copy_self_referential_tree_r): New static function.
> ? ? ? ?(self_referential_size): Likewise.
> ? ? ? ?(finalize_size_functions): New global function.
> ? ? ? ?* tree.c: Include tree-inline.h.
> ? ? ? ?(process_call_operands): Propagate TREE_READONLY from the operands.
> ? ? ? ?(push_without_duplicate): New static function.
> ? ? ? ?(find_substitute_in_expr): New global function.
> ? ? ? ?(substitute_in_expr) <tcc_declaration>: Return the replacement object
> ? ? ? ?on equality.
> ? ? ? ?<tcc_expression>: Likewise.
> ? ? ? ?<tcc_vl_exp>: If the replacement object is a constant, try to inline
> ? ? ? ?the call in the expression.
> ? ? ? ?(PROCESS_ARG): Do not clear TREE_READONLY if CONSTANT_CLASS_P.
> ? ? ? ?(build3_stat): Propagate TREE_READONLY for COND_EXPR.
> ? ? ? ?* tree.h (finalize_size_functions): Declare.
> ? ? ? ?(find_substitute_in_expr): Likewise.
> ? ? ? ?(FIND_SUBSTITUTE_IN_EXPR): New macro.
> ? ? ? ?(substitute_placeholder_in_expr): Update comment.
> ? ? ? ?* tree-inline.c (remap_decl): Do not unshare trees if do_not_unshare
> ? ? ? ?is true.
> ? ? ? ?(remap_gimple_op_r): Likewise.
> ? ? ? ?(copy_tree_body): New static function.
> ? ? ? ?(maybe_inline_call_in_expr): New global function.
> ? ? ? ?* tree-inline.h (struct copy_body_data): Add do_not_unshare field.
> ? ? ? ?(maybe_inline_call_in_expr): Declare.
> ? ? ? ?* Makefile.in (tree.o): Depend on TREE_INLINE_H.
> ? ? ? ?(stor-layout.o): Depend on CGRAPH_H, TREE_INLINE_H, TREE_DUMP_H and
> ? ? ? ?GIMPLE_H.
> ? ? ? ?* gcc-interface/decl.c: Include tree-inline.h.
> ? ? ? ?(annotate_value) <CALL_EXPR>: Try to inline the call in the expression.
> ? ? ? ?* gcc-interface/utils.c (max_size) <CALL_EXPR>: Likewise.
> ? ? ? ?* gcc-interface/utils2.c: Include tree-inline.h.
> ? ? ? ?(known_alignment) <CALL_EXPR>: Likewise.
> Eric Botcazou