RFC: cgraph/lowering vs. finish_file for GCC/UPC rewrites?

RFC: cgraph/lowering vs. finish_file for GCC/UPC rewrites?

[Gary Funck]

Recently, we have been working on upgrading GCC/UPC (see
http://gccupc.org) to the GCC trunk.  Previously,
we've sync'ed with the latest stable release, but
now we want to stay more current.

When built with GCC versions 4.0 through 4.3, we used
the gimplify language hook, LANG_HOOKS_GIMPLIFY_EXPR,
to rewrite trees that refer to UPC constructs and UPC
shared variable references - converting them into
non-UPC, gimplified, tree structures.  This worked
well, though we did need to extend the language hook
to include a gimplify test predicate and fallback
so that we can rewrite modify_expr's involving UPC
shared variables as the target:

int
upc_gimplify_expr (tree *expr_p,
   gimple_seq *pre_p, gimple_seq *post_p,
   bool (* gimple_test_f) (tree),
   int fallback)

Working with the latest GCC 4.5 snapshot, we have run
into a problem that leads me to believe that the current
approach will no longer work with the 4.5/trunk
version of GCC.

In prior GCC versions, the gimplify pass was called
before the call graph pass.  This meant that we could
safely employ the gimplify language hook to perform
the rewrites, which may emit inlined runtime calls.

An example UPC-related rewrite is to transform
UPC shared variable references into runtime calls.
This program:

shared int x;
shared int y;

int main()
{
  x = y;
}

might be translated into something like:

int main()
{
  int y_tmp = upc_get_int(upc_shared_addr(&y));
  upc_put_int(upc_shared_addr(&x), &y_tmp);
}

The definitions of the runtime functions upc_put_int()
and upc_get_int() are found in a pre-included header
file (the UPC driver adds a -include switch on the
command line).

Depending upon optimization level and compile time
switches - calls to the UPC runtime functions can
be implemented as either inlined function calls or
conventional calls to pre-compiled library routines.
At optimization levels above -O0, most of the UPC
runtime is inlined, by default.

With the new/current organization of the
compilation/call graph passes, we end up with the
surprising result that the inlined runtime function
definitions "disappear" before UPC's gimplify pass
can refer to them.  That's because the call graph
pass noticed that the inline runtime functions were
declared, but not referenced (yet).  The gimplify pass
is then run against the remaining function bodies,
but the UPC runtime functions are no longer available.

One workaround for this issue might be to mark the
runtime functions, in a fashion similar to ctors/dtors
so that the call graph pass won't eliminate them.
I'm unsure if that will get the inlining aspects of
those routines right, and it might retain unused
function definitions in the form of compiled
non-inlined code.

GOMP appears to use a "lowering" pass that runs after
the call graph and gimplify passes.  It calls runtime
routines via builtin function definitions, ensuring
that the function definitions won't go away.  However,
it looks to me as if GOMP does not inline those
runtime functions?

OBJC implements some post-processing in the
finish_file() hook routine, which in turn calls
objc_finish_file().  That may be a reasonable place
to relocate UPC's tree rewrites, but that leads to
a few questions:

Can gimplify_expr() be safely called on the same tree
more than once?  The question comes up because the
simplest thing is to retain the current infrastructure
where UPC rewrites occur in the gimplify language
hook.  The second gimplify pass will redo some
work, calling out to the UPC language hook again,
but since all UPC constructs have been rewritten and
gimplified, there will be no additional work done,
besides the traversal.

How about an alternative approach that implements a
custom tree-walk inside finish_file() (that is similar
in structure to that implemented in omp-low.c).
Is this rewrite routine allowed to selectively
gimplify parts of the tree and/or to create temp
variables managed by the code in gimplify.c?

Is the description above, of the interactions
between the cgraph, gimplify and lowering passes
correct?

What approach would you recommend for the
implementation of UPC tree re-writes that will
support calls to the runtime (that are inlined,
if applicable)?

thanks,

- Gary

Re: RFC: cgraph/lowering vs. finish_file for GCC/UPC rewrites?

[Richard Guenther]

On Mon, Sep 14, 2009 at 3:18 AM, Gary Funck <gary@intrepid.com> wrote:
>
> Recently, we have been working on upgrading GCC/UPC (see
> http://gccupc.org) to the GCC trunk.  Previously,
> we've sync'ed with the latest stable release, but
> now we want to stay more current.
>
> When built with GCC versions 4.0 through 4.3, we used
> the gimplify language hook, LANG_HOOKS_GIMPLIFY_EXPR,
> to rewrite trees that refer to UPC constructs and UPC
> shared variable references - converting them into
> non-UPC, gimplified, tree structures.  This worked
> well, though we did need to extend the language hook
> to include a gimplify test predicate and fallback
> so that we can rewrite modify_expr's involving UPC
> shared variables as the target:
>
> int
> upc_gimplify_expr (tree *expr_p,
>   gimple_seq *pre_p, gimple_seq *post_p,
>   bool (* gimple_test_f) (tree),
>   int fallback)
>
> Working with the latest GCC 4.5 snapshot, we have run
> into a problem that leads me to believe that the current
> approach will no longer work with the 4.5/trunk
> version of GCC.
>
> In prior GCC versions, the gimplify pass was called
> before the call graph pass.  This meant that we could
> safely employ the gimplify language hook to perform
> the rewrites, which may emit inlined runtime calls.
>
> An example UPC-related rewrite is to transform
> UPC shared variable references into runtime calls.
> This program:
>
> shared int x;
> shared int y;
>
> int main()
> {
>  x = y;
> }
>
> might be translated into something like:
>
> int main()
> {
>  int y_tmp = upc_get_int(upc_shared_addr(&y));
>  upc_put_int(upc_shared_addr(&x), &y_tmp);
> }
>
> The definitions of the runtime functions upc_put_int()
> and upc_get_int() are found in a pre-included header
> file (the UPC driver adds a -include switch on the
> command line).
>
> Depending upon optimization level and compile time
> switches - calls to the UPC runtime functions can
> be implemented as either inlined function calls or
> conventional calls to pre-compiled library routines.
> At optimization levels above -O0, most of the UPC
> runtime is inlined, by default.
>
> With the new/current organization of the
> compilation/call graph passes, we end up with the
> surprising result that the inlined runtime function
> definitions "disappear" before UPC's gimplify pass
> can refer to them.  That's because the call graph
> pass noticed that the inline runtime functions were
> declared, but not referenced (yet).  The gimplify pass
> is then run against the remaining function bodies,
> but the UPC runtime functions are no longer available.
>
> One workaround for this issue might be to mark the
> runtime functions, in a fashion similar to ctors/dtors
> so that the call graph pass won't eliminate them.
> I'm unsure if that will get the inlining aspects of
> those routines right, and it might retain unused
> function definitions in the form of compiled
> non-inlined code.
>
> GOMP appears to use a "lowering" pass that runs after
> the call graph and gimplify passes.  It calls runtime
> routines via builtin function definitions, ensuring
> that the function definitions won't go away.  However,
> it looks to me as if GOMP does not inline those
> runtime functions?
>
> OBJC implements some post-processing in the
> finish_file() hook routine, which in turn calls
> objc_finish_file().  That may be a reasonable place
> to relocate UPC's tree rewrites, but that leads to
> a few questions:
>
> Can gimplify_expr() be safely called on the same tree
> more than once?  The question comes up because the
> simplest thing is to retain the current infrastructure
> where UPC rewrites occur in the gimplify language
> hook.  The second gimplify pass will redo some
> work, calling out to the UPC language hook again,
> but since all UPC constructs have been rewritten and
> gimplified, there will be no additional work done,
> besides the traversal.
>
> How about an alternative approach that implements a
> custom tree-walk inside finish_file() (that is similar
> in structure to that implemented in omp-low.c).
> Is this rewrite routine allowed to selectively
> gimplify parts of the tree and/or to create temp
> variables managed by the code in gimplify.c?
>
> Is the description above, of the interactions
> between the cgraph, gimplify and lowering passes
> correct?
>
> What approach would you recommend for the
> implementation of UPC tree re-writes that will
> support calls to the runtime (that are inlined,
> if applicable)?

Without reading all the details of your mail I suggest that you
perform a custom walk over the function bodies right before
the frontend calls cgraph_finalize_compilation_unit () that
performs the necessary lowering (and function creation) to
GENERIC.  The C++ frontend already does this during its
genericize phase to transform frontend specific trees to
middle-end GENERIC trees.

Richard.

> thanks,
>
> - Gary
>

Re: RFC: cgraph/lowering vs. finish_file for GCC/UPC rewrites?

[Gary Funck]

On 09/14/09 11:52:11, Richard Guenther wrote:
> Without reading all the details of your mail I suggest that you
> perform a custom walk over the function bodies right before
> the frontend calls cgraph_finalize_compilation_unit () that
> performs the necessary lowering (and function creation) to
> GENERIC.  The C++ frontend already does this during its
> genericize phase to transform frontend specific trees to
> middle-end GENERIC trees.

Richard, thanks.  Will take a look at how C++ handles things.

- Gary

Re: RFC: cgraph/lowering vs. finish_file for GCC/UPC rewrites?

[Gary Funck]

On 09/14/09 11:52:11, Richard Guenther wrote:
> > What approach would you recommend for the
> > implementation of UPC tree re-writes that will
> > support calls to the runtime (that are inlined,
> > if applicable)?
> 
> Without reading all the details of your mail I suggest that you
> perform a custom walk over the function bodies right before
> the frontend calls cgraph_finalize_compilation_unit () that
> performs the necessary lowering (and function creation) to
> GENERIC.  The C++ frontend already does this during its
> genericize phase to transform frontend specific trees to
> middle-end GENERIC trees.

I tried the custom tree walk approach, but decided that it
will require some of the infrastructure already present in
the gimplify pass (e. g., the creation of temp. variables),
and that it is more expedient to utilize the current
language dependent gimplify hook, but to move it earlier
in the processing of the function body.

To that end, I defined a language dependent genericize hook:

   /* Determine if a tree is a function parameter pack.  */
   bool (*function_parameter_pack_p) (const_tree);

+  /* Genericize before finalization (called from finish_function()).
+     Perform lowering of function bodies from language dependent form
+     to language independent (GENERIC) form.  */
+  void (*genericize) (tree);
+

which is called from finish_function (instead of calling c_genericize):

       if (!decl_function_context (fndecl))
         {
           invoke_plugin_callbacks (PLUGIN_PRE_GENERICIZE, fndecl);
-          c_genericize (fndecl);
+          /* Lower to GENERIC form before finalization. */
+          lang_hooks.genericize (fndecl);

The UPC genericize hook is implemented as:

/* Convert the tree representation of FNDECL from UPC frontend trees
   to GENERIC.  */
void
upc_genericize (tree fndecl)
{
  /* Take care of C-specific actions first.
     Normally, we'd do this after the language-specific
     actions, but c_genericize is only a dumping pass
     now, and should be renamed.  */
  c_genericize (fndecl);
  /* Perform a full gimplify pass, because the UPC lowering rewrites
     are implemented using the gimplify framework.  */
  gimplify_function_tree (fndecl);
}

Although this may not be the best fit with the current
framework, it lets us re-use the gimplify pass
that we have been using with previous GCC 4.x
implementations.  At some point, we'll need to develop
a ground-up tree-walk rewrite pass.