Simplifying Gimple Generation

Simplifying Gimple Generation

[Lawrence Crowl]

Diego and I seek your comments on the following (loose) proposal.


Generating gimple and tree expressions require lots of detail,
which is hard to remember and easy to get wrong.  There is some
amount of boilerplate code that can, in most cases, be reduced and
managed automatically.

We will add a set of helper classes to be used as local variables
to manage the details of handling the existing types.  That is,
a layer over 'gimple_build_*'. We intend to provide helpers for
those facilities that are both commonly used and have room for
significant simplification.


Generating an Expression

Suppose one wants to generate the expression (shadow != 0) &
(((base_addr & 7) + offset) >= shadow), where offset is a value and
the other identifiers are variables.  The current code to generate
this expression is as follows.

/* t = shadow != 0 */
g = gimple_build_assign_with_ops (NE_EXPR,
            make_ssa_name (boolean_type_node, NULL),
            shadow,
            build_int_cst (shadow_type, 0));
gimple_set_location (g, location);
gsi_insert_after (&gsi, g, GSI_NEW_STMT);
t = gimple_assign_lhs (g);

/* a = base_addr & 7 */
g = gimple_build_assign_with_ops (BIT_AND_EXPR,
            make_ssa_name (uintptr_type, NULL),
            base_addr,
            build_int_cst (uintptr_type, 7));
gimple_set_location (g, location);
gsi_insert_after (&gsi, g, GSI_NEW_STMT);

/* b = (shadow_type)a */
g = gimple_build_assign_with_ops (NOP_EXPR,
            make_ssa_name (shadow_type, NULL),
            gimple_assign_lhs (g),
            NULL_TREE);
gimple_set_location (g, location);
gsi_insert_after (&gsi, g, GSI_NEW_STMT);

/* c = b + offset */
g = gimple_build_assign_with_ops (PLUS_EXPR,
            make_ssa_name (shadow_type, NULL),
            gimple_assign_lhs (g),
            build_int_cst (shadow_type, offset));
gimple_set_location (g, location);
gsi_insert_after (&gsi, g, GSI_NEW_STMT);

/* d = c >= shadow */
g = gimple_build_assign_with_ops (GE_EXPR,
            make_ssa_name (boolean_type_node, NULL),
            gimple_assign_lhs (g),
            shadow);
gimple_set_location (g, location);
gsi_insert_after (&gsi, g, GSI_NEW_STMT);

/* r = t & d */
g = gimple_build_assign_with_ops (BIT_AND_EXPR,
            make_ssa_name (boolean_type_node, NULL),
            t,
            gimple_assign_lhs (g));
gimple_set_location (g, location);
gsi_insert_after (&gsi, g, GSI_NEW_STMT);
r = gimple_assign_lhs (g);

We propose a simplified form using new build helper classes ssa_seq
and ssa_stmt that would allow the above code to be written as
follows.

ssa_seq q;
ssa_stmt t = q.stmt (NE_EXPR, shadow, 0);
ssa_stmt a = q.stmt (BIT_AND_EXPR, base_addr, 7);
ssa_stmt b = q.stmt (shadow_type, a);
ssa_stmt c = q.stmt (PLUS_EXPR, b, offset);
ssa_stmt d = q.stmt (GE_EXPR, c, shadow);
ssa_stmt e = q.stmt (BIT_AND_EXPR, t, d);
q.set_location (location);
r = e.lhs ();

There are a few important things to note about this example.

.. We have a new class (ssa_seq) that knows how to sequence
statements automatically and can build expressions out of types.

.. Every statement created produces an SSA name.  Referencing an
ssa_stmt instance in a an argument to ssa_seq::stmt retrieves the
SSA name generated by that statement.

.. The statement result type is that of the arguments.

.. The type of integral constant arguments is that of the other
argument.  (Which implies that only one argument can be constant.)

.. The 'stmt' method handles linking the statement into the sequence.

.. The 'set_location' method iterates over all statements.

There will be another class of builders for generating GIMPLE
in normal form (gimple_stmt).  We expect that this will mostly
affect all transformations that need to generate new expressions
and statements, like instrumentation passes.

We also expect to reduce calls to tree expression builders by
allowing the use of numeric and string constants to be converted
to the appropriate tree _CST node.  This will only work when the
type of the constant can be deduced from the other argument in some
expressions, of course.


Generating a Type

Consider the generation of the following type.

struct __asan_global {
  const_ptr_type_node __beg;
  inttype __size;
  inttype __size_with_redzone;
  const_ptr_type_node __name;
  inttype __has_dynamic_init;
};

The current code to generate it is as follows.

tree inttype = build_nonstandard_integer_type (POINTER_SIZE, 1);
tree ret = make_node (RECORD_TYPE);
TYPE_NAME (ret) = get_identifier ("__asan_global");
tree beg = build_decl (UNKNOWN_LOCATION, FIELD_DECL,
                       get_identifier ("__beg"), const_ptr_type_node);
DECL_CONTEXT (beg) = ret;
TYPE_FIELDS (ret) = beg;
tree size = build_decl (UNKNOWN_LOCATION, FIELD_DECL,
                        get_identifier ("__size"), inttype);
DECL_CONTEXT (size) = ret;
DECL_CHAIN (beg) = size;
tree red = build_decl (UNKNOWN_LOCATION, FIELD_DECL,
                       get_identifier ("__size_with_redzone"), inttype);
DECL_CONTEXT (red) = ret;
DECL_CHAIN (size) = red;
tree name = build_decl (UNKNOWN_LOCATION, FIELD_DECL,
                        get_identifier ("__name"), const_ptr_type_node);
DECL_CONTEXT (name) = ret;
DECL_CHAIN (red) = name;
tree init = build_decl (UNKNOWN_LOCATION, FIELD_DECL,
                        get_identifier ("__has_dynamic_init"), inttype);
DECL_CONTEXT (init) = ret;
DECL_CHAIN (name) = init;
layout_type (ret);

We propose a form as follows.

tree inttype = build_nonstandard_integer_type (POINTER_SIZE, 1);
record_builder rec ("__asan_global");
rec.field ("__beg", const_ptr_type_node);
rec.field ("__size", inttype);
rec.field ("__size_with_redzone", inttype);
rec.field ("__name", const_ptr_type_node);
rec.field ("__has_dynamic_init", inttype);
rec.finish ();
tree ret = rec.as_tree ();

There are a few important things to note about this example.

.. The 'field' method will add context and chain links.

.. The 'field' method is overloaded on both strings and identifiers.

.. The 'finish' method lays out the struct.


Proposal

Create a set of IL builder classes that provide a simplified IL
building interface.  Essentially, these builder classes will abstract
most of the bookkeeping code required by the current interfaces.

These classes will not replace the existing interfaces.  We do not
expect that all the IL generation done in current transformations
will be able to use the simplified interfaces.  The goal is to
simplify most of them, however.

-- 
Lawrence Crowl

Re: Simplifying Gimple Generation

[Basile Starynkevitch]

On Wed, Nov 14, 2012 at 05:13:12PM -0800, Lawrence Crowl wrote:
> Diego and I seek your comments on the following (loose) proposal.
> 
> 
> Generating gimple and tree expressions require lots of detail,
> which is hard to remember and easy to get wrong.  There is some
> amount of boilerplate code that can, in most cases, be reduced and
> managed automatically.
> 
> We will add a set of helper classes to be used as local variables
> to manage the details of handling the existing types.  That is,
> a layer over 'gimple_build_*'. We intend to provide helpers for
> those facilities that are both commonly used and have room for
> significant simplification.

I do agree (in principle) on this and the previous (debugging-like) proposal, but:

  do you target the 4.8 release? (I believe not, since its stage 1 is ending)

  do you intend to remove the current way of doing?

Cheers.
-- 
Basile STARYNKEVITCH         http://starynkevitch.net/Basile/
email: basile<at>starynkevitch<dot>net mobile: +33 6 8501 2359
8, rue de la Faiencerie, 92340 Bourg La Reine, France
*** opinions {are only mines, sont seulement les miennes} ***

Re: Simplifying Gimple Generation

[Xinliang David Li]

On Wed, Nov 14, 2012 at 5:13 PM, Lawrence Crowl <crowl@googlers.com> wrote:
> Diego and I seek your comments on the following (loose) proposal.
>
>
> Generating gimple and tree expressions require lots of detail,
> which is hard to remember and easy to get wrong.  There is some
> amount of boilerplate code that can, in most cases, be reduced and
> managed automatically.
>
> We will add a set of helper classes to be used as local variables
> to manage the details of handling the existing types.  That is,
> a layer over 'gimple_build_*'. We intend to provide helpers for
> those facilities that are both commonly used and have room for
> significant simplification.
>
>
> Generating an Expression
>
> Suppose one wants to generate the expression (shadow != 0) &
> (((base_addr & 7) + offset) >= shadow), where offset is a value and
> the other identifiers are variables.  The current code to generate
> this expression is as follows.
>
> /* t = shadow != 0 */
> g = gimple_build_assign_with_ops (NE_EXPR,
>             make_ssa_name (boolean_type_node, NULL),
>             shadow,
>             build_int_cst (shadow_type, 0));
> gimple_set_location (g, location);
> gsi_insert_after (&gsi, g, GSI_NEW_STMT);
> t = gimple_assign_lhs (g);
>
> /* a = base_addr & 7 */
> g = gimple_build_assign_with_ops (BIT_AND_EXPR,
>             make_ssa_name (uintptr_type, NULL),
>             base_addr,
>             build_int_cst (uintptr_type, 7));
> gimple_set_location (g, location);
> gsi_insert_after (&gsi, g, GSI_NEW_STMT);
>
> /* b = (shadow_type)a */
> g = gimple_build_assign_with_ops (NOP_EXPR,
>             make_ssa_name (shadow_type, NULL),
>             gimple_assign_lhs (g),
>             NULL_TREE);
> gimple_set_location (g, location);
> gsi_insert_after (&gsi, g, GSI_NEW_STMT);
>
> /* c = b + offset */
> g = gimple_build_assign_with_ops (PLUS_EXPR,
>             make_ssa_name (shadow_type, NULL),
>             gimple_assign_lhs (g),
>             build_int_cst (shadow_type, offset));
> gimple_set_location (g, location);
> gsi_insert_after (&gsi, g, GSI_NEW_STMT);
>
> /* d = c >= shadow */
> g = gimple_build_assign_with_ops (GE_EXPR,
>             make_ssa_name (boolean_type_node, NULL),
>             gimple_assign_lhs (g),
>             shadow);
> gimple_set_location (g, location);
> gsi_insert_after (&gsi, g, GSI_NEW_STMT);
>
> /* r = t & d */
> g = gimple_build_assign_with_ops (BIT_AND_EXPR,
>             make_ssa_name (boolean_type_node, NULL),
>             t,
>             gimple_assign_lhs (g));
> gimple_set_location (g, location);
> gsi_insert_after (&gsi, g, GSI_NEW_STMT);
> r = gimple_assign_lhs (g);
>
> We propose a simplified form using new build helper classes ssa_seq
> and ssa_stmt that would allow the above code to be written as
> follows.
>
> ssa_seq q;

Can it be more abstract, such as stmt_builder?


> ssa_stmt t = q.stmt (NE_EXPR, shadow, 0);
> ssa_stmt a = q.stmt (BIT_AND_EXPR, base_addr, 7);
> ssa_stmt b = q.stmt (shadow_type, a);
> ssa_stmt c = q.stmt (PLUS_EXPR, b, offset);
> ssa_stmt d = q.stmt (GE_EXPR, c, shadow);
> ssa_stmt e = q.stmt (BIT_AND_EXPR, t, d);


seq_seq::stmt(...) sounds like a getter interface, not a creator.

x = q.new_assignment (...);
x = q.new_call (..);
x.add_arg(..);
x = q.new_icall (..);

l1 = q.new_label ("xx");
l2 = q.new_label ("xxx");
join_l = q.new_label ("...");

x = new_if_then_else (cond, l1, l2, join_l);
q.insert_label (l1);
q.new_assignment (...);
q.insert_label(l2);
...
q.insert_label(join_l);
q.close_if_then_else(x);


> q.set_location (location);
> r = e.lhs ();
>
> There are a few important things to note about this example.
>
> .. We have a new class (ssa_seq) that knows how to sequence
> statements automatically and can build expressions out of types.
>
> .. Every statement created produces an SSA name.  Referencing an
> ssa_stmt instance in a an argument to ssa_seq::stmt retrieves the
> SSA name generated by that statement.

>
> .. The statement result type is that of the arguments.
>
> .. The type of integral constant arguments is that of the other
> argument.  (Which implies that only one argument can be constant.)
>
> .. The 'stmt' method handles linking the statement into the sequence.
>
> .. The 'set_location' method iterates over all statements.
>
> There will be another class of builders for generating GIMPLE
> in normal form (gimple_stmt).  We expect that this will mostly
> affect all transformations that need to generate new expressions
> and statements, like instrumentation passes.

What are the uses of the raw forms?

>
> We also expect to reduce calls to tree expression builders by
> allowing the use of numeric and string constants to be converted
> to the appropriate tree _CST node.  This will only work when the
> type of the constant can be deduced from the other argument in some
> expressions, of course.
>
>
> Generating a Type
>
> Consider the generation of the following type.
>
> struct __asan_global {
>   const_ptr_type_node __beg;
>   inttype __size;
>   inttype __size_with_redzone;
>   const_ptr_type_node __name;
>   inttype __has_dynamic_init;
> };
>
> The current code to generate it is as follows.
>
> tree inttype = build_nonstandard_integer_type (POINTER_SIZE, 1);
> tree ret = make_node (RECORD_TYPE);
> TYPE_NAME (ret) = get_identifier ("__asan_global");
> tree beg = build_decl (UNKNOWN_LOCATION, FIELD_DECL,
>                        get_identifier ("__beg"), const_ptr_type_node);
> DECL_CONTEXT (beg) = ret;
> TYPE_FIELDS (ret) = beg;
> tree size = build_decl (UNKNOWN_LOCATION, FIELD_DECL,
>                         get_identifier ("__size"), inttype);
> DECL_CONTEXT (size) = ret;
> DECL_CHAIN (beg) = size;
> tree red = build_decl (UNKNOWN_LOCATION, FIELD_DECL,
>                        get_identifier ("__size_with_redzone"), inttype);
> DECL_CONTEXT (red) = ret;
> DECL_CHAIN (size) = red;
> tree name = build_decl (UNKNOWN_LOCATION, FIELD_DECL,
>                         get_identifier ("__name"), const_ptr_type_node);
> DECL_CONTEXT (name) = ret;
> DECL_CHAIN (red) = name;
> tree init = build_decl (UNKNOWN_LOCATION, FIELD_DECL,
>                         get_identifier ("__has_dynamic_init"), inttype);
> DECL_CONTEXT (init) = ret;
> DECL_CHAIN (name) = init;
> layout_type (ret);
>
> We propose a form as follows.
>
> tree inttype = build_nonstandard_integer_type (POINTER_SIZE, 1);
> record_builder rec ("__asan_global");
> rec.field ("__beg", const_ptr_type_node);
> rec.field ("__size", inttype);
> rec.field ("__size_with_redzone", inttype);
> rec.field ("__name", const_ptr_type_node);
> rec.field ("__has_dynamic_init", inttype);
> rec.finish ();
> tree ret = rec.as_tree ();

Again, something like new_field or add_field is more intuitive.

>
> There are a few important things to note about this example.
>
> .. The 'field' method will add context and chain links.
>
> .. The 'field' method is overloaded on both strings and identifiers.
>
> .. The 'finish' method lays out the struct.
>
>
> Proposal
>
> Create a set of IL builder classes that provide a simplified IL
> building interface.  Essentially, these builder classes will abstract
> most of the bookkeeping code required by the current interfaces.
>
> These classes will not replace the existing interfaces.  We do not
> expect that all the IL generation done in current transformations
> will be able to use the simplified interfaces.  The goal is to
> simplify most of them, however.


Looks like a good direction to go.

thanks,

David


>
> --
> Lawrence Crowl

Re: Simplifying Gimple Generation

[Michael Matz]

Hi Lawrence,

On Wed, 14 Nov 2012, Lawrence Crowl wrote:

> Diego and I seek your comments on the following (loose) proposal.

In principle I agree with the goal, I'm not sure I like the specific way 
yet, and even if I do I have some suggestions:

> We will add a set of helper classes to be used as local variables
> to manage the details of handling the existing types.

I think one goal should be to minimize the number of those helper classes 
if we can.  And use clear names, for the statement builder e.g. 
stmt_builder, or the like, not just ssa_seq.

> We propose a simplified form using new build helper classes ssa_seq
> and ssa_stmt that would allow the above code to be written as
> follows.
> 
> ssa_seq q;
> ssa_stmt t = q.stmt (NE_EXPR, shadow, 0);
> ssa_stmt a = q.stmt (BIT_AND_EXPR, base_addr, 7);
> ssa_stmt b = q.stmt (shadow_type, a);

I think consistency should trump brevity here, so also add a tree code for 
the converter, i.e.
  ssa_stmt b = q.stmt (NOP_EXPR, shadow_type, a);

The method name should imply the action, e.g. 'add_stmt' or append_stmt 
or the like.  I'm not sure if we need the ssa_stmt class.  We could use 
overloading to accept 'gimple' as operands, with the understanding that 
those will be implicitely converted to 'tree' by accessing the LHS:

gimple append_stmt (gimple g, tree_code code, gimple op1, tree op2)
{
  return append_stmt (g, code, gimple_lhs (op1), op2);
}

(where gimple_lhs would ICE when the stmt in question doesn't have 
one).  As gimple statements are their own iterators meanwhile I'm not even 
sure if you need the ssa_seq (or ssa_stmt_builder) class.  The above 
append_stmt would simply add the newly created statement to after 'g'.

That is, I'm not yet convinced that you really need any local data for 
which you'd have to add helper classes.

So, you solve multiple problems (and I agree that they are problems), and 
these are:

> There are a few important things to note about this example.
> 
> .. We have a new class (ssa_seq) that knows how to sequence
> statements automatically and can build expressions out of types.

1) automatic sequencing; I think we don't need a helper class for that, 
   just new helper functions.

> .. Every statement created produces an SSA name.  Referencing an
> ssa_stmt instance in a an argument to ssa_seq::stmt retrieves the
> SSA name generated by that statement.

2) gimple with LHS and their LHS are isomorphic; I think overloads will 
   solve this as well without a wrapper class.
> 
> .. The statement result type is that of the arguments.

3) easy stmt building
3a) type inference; I agree with all your rules

> .. The type of integral constant arguments is that of the other 
> argument.  (Which implies that only one argument can be constant.)
> 
> .. The 'stmt' method handles linking the statement into the sequence.

See 1)

> .. The 'set_location' method iterates over all statements.

So it iterates from the starting point of the ssa_seq to its end 
(presumably only overriding locations that don't yet have one).  This can 
also be implemented by remembering the starting point of the gimple 
sequence (I'd remember a gimple stmt, you have to remember the ssa_seq 
object, so it's the same there).

All in all I think we can severely improve on building gimple statements 
without introduction of any helper class.  Basically, whenever a helper 
class merely contains one member of a different type, then I think that 
other type should be improved so that the wrapper class isn't necessary 
anymore.  Fewer types -> good :)

> Generating a Type

Apart from naming of some methods to imply the action done, I don't have 
any opinion about this at this point.  Though I agree that again the 
boilerplate sequencing (_CONTEXT and _CHAIN) should be improved.


Ciao,
Michael.

Re: Simplifying Gimple Generation

[Gabriel Dos Reis]

On Thu, Nov 15, 2012 at 8:48 AM, Michael Matz <matz@suse.de> wrote:
[...]
> The method name should imply the action, e.g. 'add_stmt' or append_stmt
> or the like.

strongly agreed.
[...]

> All in all I think we can severely improve on building gimple statements
> without introduction of any helper class.  Basically, whenever a helper
> class merely contains one member of a different type, then I think that
> other type should be improved so that the wrapper class isn't necessary
> anymore.  Fewer types -> good :)

no, it is the opposite.  Distinct abstractions should be materialized
by distinct types.  => less opportunities for bugs.

-- Gaby

Re: Simplifying Gimple Generation

[Michael Matz]

Hi,

On Thu, 15 Nov 2012, Gabriel Dos Reis wrote:

> On Thu, Nov 15, 2012 at 8:48 AM, Michael Matz <matz@suse.de> wrote:
> [...]
> > The method name should imply the action, e.g. 'add_stmt' or append_stmt
> > or the like.
> 
> strongly agreed.
> [...]
> 
> > All in all I think we can severely improve on building gimple statements
> > without introduction of any helper class.  Basically, whenever a helper
> > class merely contains one member of a different type, then I think that
> > other type should be improved so that the wrapper class isn't necessary
> > anymore.  Fewer types -> good :)
> 
> no, it is the opposite.  Distinct abstractions should be materialized

But the proposed improvements aren't distinct abstractions at all, they 
are interface cleanups and idiom shortenings.  That's my point, those 
improvements should be made to the interface of the gimple type, so that 
working with that one becomes nicer, instead of adding an 
abstractiong with which working is easier than with gimple directly.

It's not that our gimple interface is cast in stone so that we have to 
wrap it to improve it.  We can _directly_ improve it.

> by distinct types.  => less opportunities for bugs.


Ciao,
Michael.

Re: Simplifying Gimple Generation

[Xinliang David Li]

On Thu, Nov 15, 2012 at 9:01 AM, Michael Matz <matz@suse.de> wrote:
> Hi,
>
> On Thu, 15 Nov 2012, Gabriel Dos Reis wrote:
>
>> On Thu, Nov 15, 2012 at 8:48 AM, Michael Matz <matz@suse.de> wrote:
>> [...]
>> > The method name should imply the action, e.g. 'add_stmt' or append_stmt
>> > or the like.
>>
>> strongly agreed.
>> [...]
>>
>> > All in all I think we can severely improve on building gimple statements
>> > without introduction of any helper class.  Basically, whenever a helper
>> > class merely contains one member of a different type, then I think that
>> > other type should be improved so that the wrapper class isn't necessary
>> > anymore.  Fewer types -> good :)
>>
>> no, it is the opposite.  Distinct abstractions should be materialized
>
> But the proposed improvements aren't distinct abstractions at all, they
> are interface cleanups and idiom shortenings.  That's my point, those
> improvements should be made to the interface of the gimple type, so that
> working with that one becomes nicer, instead of adding an
> abstractiong with which working is easier than with gimple directly.
>
> It's not that our gimple interface is cast in stone so that we have to
> wrap it to improve it.  We can _directly_ improve it.

Without examples to show otherwise, I tend to agree with your point.

David


>
>> by distinct types.  => less opportunities for bugs.
>
>
> Ciao,
> Michael.

Re: Simplifying Gimple Generation

[Lawrence Crowl]

On 11/14/12, Basile Starynkevitch <basile@starynkevitch.net> wrote:
> On Wed, Nov 14, 2012 at 05:13:12PM -0800, Lawrence Crowl wrote:
>> Diego and I seek your comments on the following (loose) proposal.
>>
>>
>> Generating gimple and tree expressions require lots of detail,
>> which is hard to remember and easy to get wrong.  There is some
>> amount of boilerplate code that can, in most cases, be reduced and
>> managed automatically.
>>
>> We will add a set of helper classes to be used as local variables
>> to manage the details of handling the existing types.  That is,
>> a layer over 'gimple_build_*'. We intend to provide helpers for
>> those facilities that are both commonly used and have room for
>> significant simplification.
>
> I do agree (in principle) on this and the previous (debugging-like)
> proposal, but:
>
>   do you target the 4.8 release? (I believe not, since its stage 1 is
>   ending)

Not 4.8.

>   do you intend to remove the current way of doing?

Definitely not.  Our intent is to provide an easier tool that
accomplishes the common tasks.  We expect that tricky stuff will
use the existing interfaces.

-- 
Lawrence Crowl

Re: Simplifying Gimple Generation

[Lawrence Crowl]

On 11/15/12, Michael Matz <matz@suse.de> wrote:
> On Wed, 14 Nov 2012, Lawrence Crowl wrote:
> > Diego and I seek your comments on the following (loose) proposal.
>
> In principle I agree with the goal, I'm not sure I like the
> specific way yet, and even if I do I have some suggestions:
>
> > We will add a set of helper classes to be used as local variables
> > to manage the details of handling the existing types.
>
> I think one goal should be to minimize the number of those
> helper classes if we can.  And use clear names, for the statement
> builder e.g.  stmt_builder, or the like, not just ssa_seq.

The helper classes provide benefits.

They allow us to keep state needed to tie actions together.
Without that state, we would either require the user to create their
own extra variables, or require extending the representation of
the primary data structures.  The former is a programming burden,
the latter is a space problem.

They allow us to use the same name for the same actions in two
different contexts.  In particular, distinguishing between statement
construction in SSA and non-SSA.

> > We propose a simplified form using new build helper classes
> > ssa_seq and ssa_stmt that would allow the above code to be
> > written as follows.
> >
> > ssa_seq q;
> > ssa_stmt t = q.stmt (NE_EXPR, shadow, 0);
> > ssa_stmt a = q.stmt (BIT_AND_EXPR, base_addr, 7);
> > ssa_stmt b = q.stmt (shadow_type, a);
>
> I think consistency should trump brevity here, so also add a tree
> code for the converter, i.e.
>
> ssa_stmt b = q.stmt (NOP_EXPR, shadow_type, a);

Personally, I found that "NOP_EXPR" was confusing, because I was
expecting a cast operation.  My expectation is that folks learning
GCC would have a lower hurdle without the misdirection.  However,
I don't have strong feelings here.

> The method name should imply the action, e.g. 'add_stmt' or
> append_stmt or the like.

I was thinking more declaratively, but making it a verb is okay
with me.

> I'm not sure if we need the ssa_stmt class.  We could use
> overloading to accept 'gimple' as operands, with the understanding
> that those will be implicitely converted to 'tree' by accessing
> the LHS:
>
> gimple append_stmt (gimple g, tree_code code, gimple op1, tree op2)
> {
>  return append_stmt (g, code, gimple_lhs (op1), op2);
> }
>
> (where gimple_lhs would ICE when the stmt in question doesn't have
> one).  As gimple statements are their own iterators meanwhile I'm
> not even sure if you need the ssa_seq (or ssa_stmt_builder) class.
> The above append_stmt would simply add the newly created statement
> to after 'g'.

Yes, simplifications like that were the intent.

> That is, I'm not yet convinced that you really need any local
> data for which you'd have to add helper classes.

We also need to ask if we will ever need local data.  If we plan
for it now, future changes might be possible without affecting
existing code.  Otherwise, we might require more substantial patches.

> So, you solve multiple problems (and I agree that they are
> problems), and these are:
>
> > There are a few important things to note about this example.
> >
> > .. We have a new class (ssa_seq) that knows how to sequence
> > statements automatically and can build expressions out of types.
>
> 1) automatic sequencing; I think we don't need a helper class
> for that, just new helper functions.
>
> > .. Every statement created produces an SSA name.  Referencing an
> > ssa_stmt instance in a an argument to ssa_seq::stmt retrieves
> > the SSA name generated by that statement.
>
> 2) gimple with LHS and their LHS are isomorphic; I think overloads
> will solve this as well without a wrapper class.
>
> > .. The statement result type is that of the arguments.
>
> 3) easy stmt building
> 3a) type inference; I agree with all your rules
>
> > .. The type of integral constant arguments is that of the
> > other argument.  (Which implies that only one argument can
> > be constant.)
> >
> > .. The 'stmt' method handles linking the statement into the
> > sequence.
>
> See 1)
>
> > .. The 'set_location' method iterates over all statements.
>
> So it iterates from the starting point of the ssa_seq to its end
> (presumably only overriding locations that don't yet have one).
> This can also be implemented by remembering the starting point
> of the gimple sequence (I'd remember a gimple stmt, you have to
> remember the ssa_seq object, so it's the same there).
>
> All in all I think we can severely improve on building gimple
> statements without introduction of any helper class.  Basically,
> whenever a helper class merely contains one member of a different
> type, then I think that other type should be improved so that
> the wrapper class isn't necessary anymore.  Fewer types -> good :)

While I would agree that unnecessary types are bad, I have found
that having types to represent distinct concepts is a good way to
structure my thinking and catch my errors.

> > Generating a Type
>
> Apart from naming of some methods to imply the action done,
> I don't have any opinion about this at this point.  Though I
> agree that again the boilerplate sequencing (_CONTEXT and _CHAIN)
> should be improved.

-- 
Lawrence Crowl

Re: Simplifying Gimple Generation

[Michael Matz]

Hi,

On Thu, 15 Nov 2012, Lawrence Crowl wrote:

> They allow us to use the same name for the same actions in two
> different contexts.  In particular, distinguishing between statement
> construction in SSA and non-SSA.

I don't see the difference, and I don't see where you need context data to 
distinguis that, in case you really need to.

> > That is, I'm not yet convinced that you really need any local
> > data for which you'd have to add helper classes.
> 
> We also need to ask if we will ever need local data.  If we plan
> for it now, future changes might be possible without affecting
> existing code.  Otherwise, we might require more substantial patches.

But so it _now_ requires substantial patches without it being clear that 
we ever need the complications.  Please don't optimize prematurely.

> > statements without introduction of any helper class.  Basically, 
> > whenever a helper class merely contains one member of a different 
> > type, then I think that other type should be improved so that the 
> > wrapper class isn't necessary anymore.  Fewer types -> good :)
> 
> While I would agree that unnecessary types are bad, I have found that 
> having types to represent distinct concepts is a good way to structure 
> my thinking and catch my errors.

But where exactly are your concepts different?  We have gimple_seq, we can 
append to it.  You had ssa_seq, you could append to it (nicer).  We can 
construct new statements already (boilerplaty), you can construct new 
statements (nicer).  It just the same with a leaner interface.


Ciao,
Michael.

Re: Simplifying Gimple Generation

[Diego Novillo]

On Thu, Nov 15, 2012 at 2:31 AM, Xinliang David Li <davidxl@google.com> wrote:

>> ssa_stmt t = q.stmt (NE_EXPR, shadow, 0);
>> ssa_stmt a = q.stmt (BIT_AND_EXPR, base_addr, 7);
>> ssa_stmt b = q.stmt (shadow_type, a);
>> ssa_stmt c = q.stmt (PLUS_EXPR, b, offset);
>> ssa_stmt d = q.stmt (GE_EXPR, c, shadow);
>> ssa_stmt e = q.stmt (BIT_AND_EXPR, t, d);
>
>
> seq_seq::stmt(...) sounds like a getter interface, not a creator.

Sure. They could be named new_stmt() or build_stmt() or something similar.

> x = q.new_assignment (...);
> x = q.new_call (..);
> x.add_arg(..);
> x = q.new_icall (..);
>
> l1 = q.new_label ("xx");
> l2 = q.new_label ("xxx");
> join_l = q.new_label ("...");
>
> x = new_if_then_else (cond, l1, l2, join_l);
> q.insert_label (l1);
> q.new_assignment (...);
> q.insert_label(l2);
> ...
> q.insert_label(join_l);
> q.close_if_then_else(x);

What I was thinking for if_then_else constructs was something along
the lines of:

stmt_seq then_body(s1);
then_body.add_stmt(s2);

stmt_seq else_body(r1);
else_body.add_stmt(r2);
stmt if_then_else(cond, then_body, else_body);

You can then take 'if_then_else' and insert it inside a basic block or
an edge.  When that happens, the builder takes care of the block/edge
splitting for you.

>> .. The statement result type is that of the arguments.
>>
>> .. The type of integral constant arguments is that of the other
>> argument.  (Which implies that only one argument can be constant.)
>>
>> .. The 'stmt' method handles linking the statement into the sequence.
>>
>> .. The 'set_location' method iterates over all statements.
>>
>> There will be another class of builders for generating GIMPLE
>> in normal form (gimple_stmt).  We expect that this will mostly
>> affect all transformations that need to generate new expressions
>> and statements, like instrumentation passes.
>
> What are the uses of the raw forms?

Sorry, what are these "raw forms" that you refer to?

>> tree inttype = build_nonstandard_integer_type (POINTER_SIZE, 1);
>> record_builder rec ("__asan_global");
>> rec.field ("__beg", const_ptr_type_node);
>> rec.field ("__size", inttype);
>> rec.field ("__size_with_redzone", inttype);
>> rec.field ("__name", const_ptr_type_node);
>> rec.field ("__has_dynamic_init", inttype);
>> rec.finish ();
>> tree ret = rec.as_tree ();
>
> Again, something like new_field or add_field is more intuitive.

Sure.


Diego.

Re: Simplifying Gimple Generation

[Diego Novillo]

On Thu, Nov 15, 2012 at 1:06 AM, Basile Starynkevitch
<basile@starynkevitch.net> wrote:
> On Wed, Nov 14, 2012 at 05:13:12PM -0800, Lawrence Crowl wrote:
>> Diego and I seek your comments on the following (loose) proposal.
>>
>>
>> Generating gimple and tree expressions require lots of detail,
>> which is hard to remember and easy to get wrong.  There is some
>> amount of boilerplate code that can, in most cases, be reduced and
>> managed automatically.
>>
>> We will add a set of helper classes to be used as local variables
>> to manage the details of handling the existing types.  That is,
>> a layer over 'gimple_build_*'. We intend to provide helpers for
>> those facilities that are both commonly used and have room for
>> significant simplification.
>
> I do agree (in principle) on this and the previous (debugging-like) proposal, but:
>
>   do you target the 4.8 release? (I believe not, since its stage 1 is ending)

No, this would be a 4.9 feature.

>   do you intend to remove the current way of doing?

No.  The simplified interface will necessarily not be able to handle
all kinds of IL creation.  It is a layer over the low-level routines
that helps with the common cases.


Diego.

Re: Simplifying Gimple Generation

[Diego Novillo]

On Thu, Nov 15, 2012 at 9:48 AM, Michael Matz <matz@suse.de> wrote:
> Hi Lawrence,
>
> On Wed, 14 Nov 2012, Lawrence Crowl wrote:
>
>> Diego and I seek your comments on the following (loose) proposal.
>
> In principle I agree with the goal, I'm not sure I like the specific way
> yet, and even if I do I have some suggestions:

Sure.  We do not have very firm notions yet.  We have only started
exploring this recently.  We wanted to discuss our ideas early on to
make sure we are going in the right direction.

>> We will add a set of helper classes to be used as local variables
>> to manage the details of handling the existing types.
>
> I think one goal should be to minimize the number of those helper classes
> if we can.  And use clear names, for the statement builder e.g.
> stmt_builder, or the like, not just ssa_seq.

Sure.

>
>> We propose a simplified form using new build helper classes ssa_seq
>> and ssa_stmt that would allow the above code to be written as
>> follows.
>>
>> ssa_seq q;
>> ssa_stmt t = q.stmt (NE_EXPR, shadow, 0);
>> ssa_stmt a = q.stmt (BIT_AND_EXPR, base_addr, 7);
>> ssa_stmt b = q.stmt (shadow_type, a);
>
> I think consistency should trump brevity here, so also add a tree code for
> the converter, i.e.
>   ssa_stmt b = q.stmt (NOP_EXPR, shadow_type, a);

Ah, yes.  This one was amusing.  When we were drafting the proposal,
Lawrence kept wondering what this NOP_EXPR thing is.  I've been
suffering this name for so long, that it no longer irritates me.  Had
it been named CAST_EXPR, or even NOP_CAST_EXPR, he would have probably
kept it in the example code :)

> The method name should imply the action, e.g. 'add_stmt' or append_stmt
> or the like.  I'm not sure if we need the ssa_stmt class.  We could use
> overloading to accept 'gimple' as operands, with the understanding that
> those will be implicitely converted to 'tree' by accessing the LHS:

Hm, maybe you are right.  The main goal was reduce all the ssa name
and temporary creation needed to glue the statements together.

> gimple append_stmt (gimple g, tree_code code, gimple op1, tree op2)
> {
>   return append_stmt (g, code, gimple_lhs (op1), op2);
> }
>
> (where gimple_lhs would ICE when the stmt in question doesn't have
> one).  As gimple statements are their own iterators meanwhile I'm not even
> sure if you need the ssa_seq (or ssa_stmt_builder) class.  The above
> append_stmt would simply add the newly created statement to after 'g'.

Yes, I think that could work.  More details will surface as we start
the implementation, of course.

> All in all I think we can severely improve on building gimple statements
> without introduction of any helper class.  Basically, whenever a helper
> class merely contains one member of a different type, then I think that
> other type should be improved so that the wrapper class isn't necessary
> anymore.  Fewer types -> good :)

Sure.  If the helper classes do not contain any significant state that
cannot be gleaned from the operands to the builder, then we won't
introduce them.

>
>> Generating a Type
>
> Apart from naming of some methods to imply the action done, I don't have
> any opinion about this at this point.  Though I agree that again the
> boilerplate sequencing (_CONTEXT and _CHAIN) should be improved.

Right.  I think it's mostly record types that will benefit from this
type of shortening.  Building other types is usually more
straightforward.


Diego.

Re: Simplifying Gimple Generation

[Michael Matz]

Hi,

On Fri, 16 Nov 2012, Diego Novillo wrote:

> > I think consistency should trump brevity here, so also add a tree code for
> > the converter, i.e.
> >   ssa_stmt b = q.stmt (NOP_EXPR, shadow_type, a);
> 
> Ah, yes.  This one was amusing.  When we were drafting the proposal,
> Lawrence kept wondering what this NOP_EXPR thing is.  I've been
> suffering this name for so long, that it no longer irritates me.  Had
> it been named CAST_EXPR, or even NOP_CAST_EXPR, he would have probably
> kept it in the example code :)

We have CONVERT_EXPR, but it currently doesn't do _quite_ the same as 
NOP_EXPR.  I once wanted to merge them (with CONVERT_EXPR surviving), but 
it stalled somewhere, couple years ago.


Ciao,
Michael.

Re: Simplifying Gimple Generation

[Andrew Pinski]

On Fri, Nov 16, 2012 at 6:30 AM, Michael Matz <matz@suse.de> wrote:
> Hi,
>
> On Fri, 16 Nov 2012, Diego Novillo wrote:
>
>> > I think consistency should trump brevity here, so also add a tree code for
>> > the converter, i.e.
>> >   ssa_stmt b = q.stmt (NOP_EXPR, shadow_type, a);
>>
>> Ah, yes.  This one was amusing.  When we were drafting the proposal,
>> Lawrence kept wondering what this NOP_EXPR thing is.  I've been
>> suffering this name for so long, that it no longer irritates me.  Had
>> it been named CAST_EXPR, or even NOP_CAST_EXPR, he would have probably
>> kept it in the example code :)
>
> We have CONVERT_EXPR, but it currently doesn't do _quite_ the same as
> NOP_EXPR.  I once wanted to merge them (with CONVERT_EXPR surviving), but
> it stalled somewhere, couple years ago.

I think the only difference now is in the front-ends IIRC.  Everything
else has been merged with respect to CONVERT_EXPR and NOP_EXPR.  So we
should recommend using CONVERT_EXPR in new code.

Thanks,
Andrew Pinski

Re: Simplifying Gimple Generation

[Xinliang David Li]

On Fri, Nov 16, 2012 at 5:13 AM, Diego Novillo <dnovillo@google.com> wrote:
> On Thu, Nov 15, 2012 at 2:31 AM, Xinliang David Li <davidxl@google.com> wrote:
>
>>> ssa_stmt t = q.stmt (NE_EXPR, shadow, 0);
>>> ssa_stmt a = q.stmt (BIT_AND_EXPR, base_addr, 7);
>>> ssa_stmt b = q.stmt (shadow_type, a);
>>> ssa_stmt c = q.stmt (PLUS_EXPR, b, offset);
>>> ssa_stmt d = q.stmt (GE_EXPR, c, shadow);
>>> ssa_stmt e = q.stmt (BIT_AND_EXPR, t, d);
>>
>>
>> seq_seq::stmt(...) sounds like a getter interface, not a creator.
>
> Sure. They could be named new_stmt() or build_stmt() or something similar.
>
>> x = q.new_assignment (...);
>> x = q.new_call (..);
>> x.add_arg(..);
>> x = q.new_icall (..);
>>
>> l1 = q.new_label ("xx");
>> l2 = q.new_label ("xxx");
>> join_l = q.new_label ("...");
>>
>> x = new_if_then_else (cond, l1, l2, join_l);
>> q.insert_label (l1);
>> q.new_assignment (...);
>> q.insert_label(l2);
>> ...
>> q.insert_label(join_l);
>> q.close_if_then_else(x);
>
> What I was thinking for if_then_else constructs was something along
> the lines of:
>
> stmt_seq then_body(s1);
> then_body.add_stmt(s2);
>
> stmt_seq else_body(r1);
> else_body.add_stmt(r2);
> stmt if_then_else(cond, then_body, else_body);


That looks good. The interface should also allow user to specify
branch prob. It is probably useful to consider support creating
if-then-else with multiple conditions with short circuit  semantics.
The interface should look very similar.

thanks,

David


>
> You can then take 'if_then_else' and insert it inside a basic block or
> an edge.  When that happens, the builder takes care of the block/edge
> splitting for you.
>
>>> .. The statement result type is that of the arguments.
>>>
>>> .. The type of integral constant arguments is that of the other
>>> argument.  (Which implies that only one argument can be constant.)
>>>
>>> .. The 'stmt' method handles linking the statement into the sequence.
>>>
>>> .. The 'set_location' method iterates over all statements.
>>>
>>> There will be another class of builders for generating GIMPLE
>>> in normal form (gimple_stmt).  We expect that this will mostly
>>> affect all transformations that need to generate new expressions
>>> and statements, like instrumentation passes.
>>
>> What are the uses of the raw forms?
>
> Sorry, what are these "raw forms" that you refer to?
>
>>> tree inttype = build_nonstandard_integer_type (POINTER_SIZE, 1);
>>> record_builder rec ("__asan_global");
>>> rec.field ("__beg", const_ptr_type_node);
>>> rec.field ("__size", inttype);
>>> rec.field ("__size_with_redzone", inttype);
>>> rec.field ("__name", const_ptr_type_node);
>>> rec.field ("__has_dynamic_init", inttype);
>>> rec.finish ();
>>> tree ret = rec.as_tree ();
>>
>> Again, something like new_field or add_field is more intuitive.
>
> Sure.
>
>
> Diego.

Re: Simplifying Gimple Generation

[Andrew MacLeod]

On 11/14/2012 08:13 PM, Lawrence Crowl wrote:
> Diego and I seek your comments on the following (loose) proposal.
>
>
>
> We propose a simplified form using new build helper classes ssa_seq
> and ssa_stmt that would allow the above code to be written as
> follows.
>
> ssa_seq q;
> ssa_stmt t = q.stmt (NE_EXPR, shadow, 0);
> ssa_stmt a = q.stmt (BIT_AND_EXPR, base_addr, 7);
> ssa_stmt b = q.stmt (shadow_type, a);
> ssa_stmt c = q.stmt (PLUS_EXPR, b, offset);
> ssa_stmt d = q.stmt (GE_EXPR, c, shadow);
> ssa_stmt e = q.stmt (BIT_AND_EXPR, t, d);
> q.set_location (location);
> r = e.lhs ();
<...>
>
> There will be another class of builders for generating GIMPLE
> in normal form (gimple_stmt).  We expect that this will mostly
> affect all transformations that need to generate new expressions
> and statements, like instrumentation passes.
I certainly like the general idea.

Have you actually sat down and worked out the interface?  Do we really 
need a set of SSA *and* a set of gimple routines? I fooled around with a 
few variations and it doesn't seem like we should.

It seems to me that SSA is just a specialization of gimple, so I would 
think maybe a very small set of SSA specializations could be applied to 
the gimple interface.   All the statement linking, manipulation and 
accessing is identical, so maybe something as simple as making the 
stmt() method have 2 variations on whether you want SSA results or not 
in the gimple expression.

GimpleSeq q;
GimpleStmt t = q.ssa_stmt (NE_EXPR, shadow, 0);
GimpleStmt a = q.ssa_stmt (BIT_AND_EXPR, base_addr, 7);
GimpleStmt b = q.ssa_stmt (shadow_type, a);

Any accesses to 'a' when you are generating code is going to pick up the LHS of the expression, whether its SSA or not. So if you want gimple generated instead of SSA, you do something like
GimpleStmt b = q.gimple_stmt (shadow_type, a);  // result is just a gimple temp insterad of ssa temp

And would the GimpleStmt class give you access to ALL the gimple_YYY access routines?  ie,  b.has_ops() instead of gimple_has_ops (b)

This would certainly help pave the way for replacing the gimple data structure with a proper object eventually.

The GinmpleSeq object which affects everything in the sequence... I presume there is just a subset of the methods which would be available.. ie set_use_ops() would clearly not make sense. Have you enumerated which routines that would be, or just leave that until its actually implemented?

We may find there are other interesting uses of the GimpelSeq object along the way as well.


>
> We also expect to reduce calls to tree expression builders by
> allowing the use of numeric and string constants to be converted
> to the appropriate tree _CST node.  This will only work when the
> type of the constant can be deduced from the other argument in some
> expressions, of course.
>
<...>

I think this would be great.. I find I'm constantly having to look up 
the right thing to do and it annoys me to no end that I cant just say 0 
when I mean 0. or "a string". I have to look up the correct way to get 
everything back as well...
>
> Proposal
>
> Create a set of IL builder classes that provide a simplified IL
> building interface.  Essentially, these builder classes will abstract
> most of the bookkeeping code required by the current interfaces.
>
> These classes will not replace the existing interfaces.  We do not
> expect that all the IL generation done in current transformations
> will be able to use the simplified interfaces.  The goal is to
> simplify most of them, however.
The long term goal *would* be a complete replacement, so as long as that 
is kept in mind and these changes help move in that direction, then I 
think the effort is worthwhile.

Andrew

Re: Simplifying Gimple Generation

[Diego Novillo]

Thanks for all the responses.

I have created a wiki page to track this proposal:
http://gcc.gnu.org/wiki/cxx-conversion/gimple-generation

It is also indexed from the main improvements wiki:
http://gcc.gnu.org/wiki/ImprovementProjects


Thanks.  Diego.