Gcc Digest, Vol 5, Issue 52

[Gary Oblock]

Richard,

Thanks, I had no idea about the immediate uses mechanism and
using it will speed things up a bit and make them more reliable.
However, I'll still have to scan the LHS of each assignment unless
there's a mechanism to traverse all the SSAs for a function.
Note, I assume there is also a mechanism to add and remove
immediate use instances. If I can find it I'll post a question to the list.

I do the the patching on a per function basis immediately after
applying the transforms. It was going to be a scan of all the
GIMPLE. What you've told me might make it a bit of a misnomer
to call what I intend to do now, a scan. The default defs problem
happened when the original scan tried to simply modify the type
of a default def. There didn't seem to be a way of doing this and I've
since learned this in fact associates declarations not types but with
a declaration. Note, just modifying the type of normal ssa names
seemed to work but I can't in fact know it actually would have.

I'm not sure I can do justice to the other transformations but
here is one larger example. Note, since I'm currently only
dealing with dynamically allocated array I'll only see "a->f" and
not "a[i].f" so you are getting the former.

 _2 = _1->f

turns into

get_field_arry_addr: new_3 = array_base.f_array_field
get_index               : new_4 = (sizetype)_1
get_offset               : new_5  = new_4 * size_of_f_element
get_field_addr        : new_6 = new_3 + new_5       // uses pointer arith
temp_set                : new_7 = * new_6
final_set                  : _2       = new_7

I hope that's sufficient to satisfy your curiosity because the only other
large transformation currently coded is that for the malloc which would
take me quite a while to put together an example of. Note, these are
shown in the HL design doc which I sent you. Though like battle plans,
no design no matter how good survives coding intact.

Thanks again,

Gary




________________________________
From: Richard Biener <richard.guenther@gmail.com>
Sent: Wednesday, July 29, 2020 5:42 AM
To: Gary Oblock <gary@amperecomputing.com>
Cc: gcc@gcc.gnu.org <gcc@gcc.gnu.org>
Subject: Re: Gcc Digest, Vol 5, Issue 52

[EXTERNAL EMAIL NOTICE: This email originated from an external sender. Please be mindful of safe email handling and proprietary information protection practices.]


On Tue, Jul 28, 2020 at 11:02 PM Gary Oblock <gary@amperecomputing.com> wrote:
>
> Richard,
>
> I wasn't aware of release_defs so I'll add that for certain.
>
> When I do a single transformation as part of the transformation pass
> each transformation uses the correct types internally but on the edges
> emits glue code that will be transformed via a dangling type fixup pass.
>
> For example when adding something to a pointer:
>
> _2 = _1 + k
>
> Where _1 & _2 are the old point types I'll
>  emit
>
> new_3 = (type_convert)_1
> new_4 = (type_convert)k
> new_5 = new_4 / struct_size // truncating divide
> new_6 = new_3 + new_5
> _2       = (type_convert)_new_6
>
> Note, the casting is done with CONVERT_EXPR
> which is harmless when I create new ssa names
> and set the appropriate operands in

OK, so you're funneling the new "index" values through
the original pointer variable _1?  But then I don't see
where the patching up of SSA names and the default
def issue happens.

> new_3 = (type_convert)_1
> _2 = (type_convert)new_6
>
> to
>
> new_3 = new_7
> new_8 = new_6
>
> Now I might actually find via a look up that
> _1 and/or _2 were already mapped to
> new_7 and/or new_8 but that's irrelevant.
>
> To intermix the applications of the transformations and
> the patching of these dangling types seems like I'd
> need to do an insanely ugly recursive walk of each functions
> body.
>
> I'm curious when you mention def-use I'm not aware of
> GCC using def-use chains except at the RTL level.
> Is there a def-use mechanism in GIMPLE because
> in SSA form it's trivial to find the definition of
> a temp variable but non trivial to find the use of
> it. Which I think is a valid reason for fixing up the
> dangling types of temps in a scan.

In GIMPLE SSA we maintain a list of uses for each SSA
def, available via the so called immediate-uses.  You
can grep for uses of FOR_EACH_IMM_USE[_FAST]

>
> Note, I'll maintain a mapping like you suggest but not use
> it at transformation application time. Furthermore,
> I'll initialize the mapping with the default defs from
> the DECLs so I won't have to mess with them on the fly.
> Now at the time in the scan when I find uses and defs of
> a dangling type I'd like to simply modify the associated operands
> of the statement. What is the real advantage creating a new
> statement with the correct types? I'll be using SSA_NAME_DEF_STMT
> if the newly created ssa name is on the left hand side. Also, the
> ssa_name it replaces will no longer be referenced by the end of the
> scan pass.

Since you are replacing a[i].b with array_for_b[i] I am wondering
how you do the transform for non-pointer adjustments.

> Note, I do have a escape mechanism in a qualification
> pre-pass to the transformations. It's not intended as
> catch-all for things I don't understand rather it's an
> aid to find possible new cases. However, there are
> legitimate things at this point in time during development
> of this optimization that I need to spot things this way. Later,
> when points to analysis is integrated falling through to
> the default case behavior will likely cause an internal error.
>
> Thanks,
>
> Gary
>
> ________________________________
> From: Richard Biener <richard.guenther@gmail.com>
> Sent: Tuesday, July 28, 2020 12:07 AM
> To: Gary Oblock <gary@amperecomputing.com>
> Cc: gcc@gcc.gnu.org <gcc@gcc.gnu.org>
> Subject: Re: Gcc Digest, Vol 5, Issue 52
>
> [EXTERNAL EMAIL NOTICE: This email originated from an external sender. Please be mindful of safe email handling and proprietary information protection practices.]
>
>
> On Tue, Jul 28, 2020 at 4:36 AM Gary Oblock via Gcc <gcc@gcc.gnu.org> wrote:
> >
> > Almost all of the makes sense to.
> >
> > I'm not sure what a conditionally initialized pointer is.
>
> {
>   void *p;
>   if (condition)
>     p = ...;
>   if (other condition)
>      ... use p;
>
> will end up with a PHI node after the conditional init with
> one PHI argument being the default definition SSA name
> for 'p'.
>
>
> > You mention VAR_DECL but I assume this is for
> > completeness and not something I'll run across
> > associated with a default def (but then again I don't
> > understand notion of a conditionally initialized
> > pointer.)
> >
> > I'm at the moment only dealing with a single malloced
> > array of structures of the given type (though multiple types could have this property.) I intend to extend this to cover multiple array and static allocations but I need to get the easiest case working first. This means no side pointers are needed and if and when I need them pointer will get transformed into a base and index pair.
> >
> > I intend to do the creation of new ssa names as a separate pass from the gimple transformations. So I will technically be creating for the duration of the pass possibly two defs associated with a single gimple statement. Do I need to delete the old ssa names
> > via some mechanism?
>
> When you remove the old definition do
>
>    gsi_remove (&gsi, true); // gsi points at stmt
>    release_defs (stmt);
>
> note that as far as I understand you need to modify the stmts using
> the former pointer (since its now an index), and I would not recommend
> to make creation of new SSA names a separate pass, instead create
> them when you alter the original definition and maintain a map
> between old and new SSA name.
>
> I haven't dug deep enough into your figure how you identify things
> to modify (well, I fear you're just scanning for "uses" of the changed
> type ...), but in the scheme I think should be implemented you'd
> follow the SSA def->use links for both tracking an objects life
> as well as for modifying the accesses.
>
> With just scanning for types I am quite sure you'll run into
> cases where you discover SSA uses that you did not modify
> because you thought that's not necessary (debug stmts!).  Of
> course you'll simply make more things "type escape points" then.
>
> > By the way this is really helpful information. The only
> > other person on the project, Erick, is a continent away
> > and has about as much experience with gimple as
> > me but a whole heck lot less compiler experience.
> >
> > Thanks,
> >
> > Gary
> >
> > ________________________________
> > From: Gcc <gcc-bounces@gcc.gnu.org> on behalf of gcc-request@gcc.gnu.org <gcc-request@gcc.gnu.org>
> > Sent: Monday, July 27, 2020 1:33 AM
> > To: gcc@gcc.gnu.org <gcc@gcc.gnu.org>
> > Subject: Gcc Digest, Vol 5, Issue 52
> >
> > [EXTERNAL EMAIL NOTICE: This email originated from an external sender. Please be mindful of safe email handling and proprietary information protection practices.]
> >
> >
> > Send Gcc mailing list submissions to
> >         gcc@gcc.gnu.org
> >
> > To subscribe or unsubscribe via the World Wide Web, visit
> >         http://gcc.gnu.org/mailman/listinfo/gcc
> > or, via email, send a message with subject or body 'help' to
> >         gcc-request@gcc.gnu.org
> >
> > You can reach the person managing the list at
> >         gcc-owner@gcc.gnu.org
> >
> > When replying, please edit your Subject line so it is more specific
> > than "Re: Contents of Gcc digest..."