headers
Brett Foster | 2 Jun 2012 19:48

Traversing trees in a plugin...

Hi all,

I'm working on a GCC plugin, having made a lot of progress on that
front. So far running my plugin works 'more or less' on things like
the linux kernel. On the other hand running it on the plugin itself
causes problems. Given that some of the data structures are pretty
complicated in GCC I'm not surprised.

So the question I have (w.r.t. TREE data structures) are:

1) How to marking a node as visited by my algorithm (without screwing
up the compiler!)

2) How to associate additional data (perhaps a pointer to something
else) to a node (like a unique identifier, or a pointer to a data
structure).

Thoughts:

1) The general overview of my current algorithm:
a) When a node can be uniquely identified (has an identifier or
position information) I can use a look up.
b) However with types (especially those that are anonymous) I find it
challenging to do so. I assign such a node an anonymous identifier or
try to assign a general data type (i.e. integer) when the type is
internal.
c) When I arrive at a node and it is identifiable and it is found in
the lookup table I can infer that its children have also been visited.
d) However there may be cases when I cannot identify where a node has
been visited, and processing is duplicated.
(Continue reading)

Permalink | Reply |
headers
Basile Starynkevitch | 2 Jun 2012 20:31

Re: Traversing trees in a plugin...

On Sat, 2 Jun 2012 10:48:47 -0700
Brett Foster <fosterb <at> edgeandvertex.org> wrote:

> Hi all,
> 
> I'm working on a GCC plugin, having made a lot of progress on that
> front. So far running my plugin works 'more or less' on things like
> the linux kernel. On the other hand running it on the plugin itself
> causes problems. Given that some of the data structures are pretty
> complicated in GCC I'm not surprised.
> 
> So the question I have (w.r.t. TREE data structures) are:
> 
> 1) How to marking a node as visited by my algorithm (without screwing
> up the compiler!)
> 
> 2) How to associate additional data (perhaps a pointer to something
> else) to a node (like a unique identifier, or a pointer to a data
> structure).

In the MELT meta-plugin (recall that MELT is a high-level domain specific language to
extend GCC, see http://gcc-melt.org/ for more) we extensively use associative hash-tables
for that. MELT offers homogeneous hash-tables, e.g. hash-table associating tree (i.e.
non-null tree pointers) to arbitrary non-null MELT values (e.g. MELT closures, or MELT
lists, or MELT objects, etc etc), or hash-table associating (non null) gimple to non
null MELT values.

So you can have e.g. an hash-table associating each tree (every tree is in GCC a non-null
pointer to a structure) with data associated to it. Once it has some data you know that
this tree has been visited.
(Continue reading)

Permalink | Reply |
headers
Basile Starynkevitch | 2 Jun 2012 20:40

Re: Traversing trees in a plugin...

On Sat, 2 Jun 2012 20:31:26 +0200
Basile Starynkevitch <basile <at> starynkevitch.net> wrote:
> In a few words, plugins cannot extend existing GCC data structures, but can associate them
> to their own data.

I forgot to mention that gimple-s (but not tree-s) give you a unsigned client number
called a uid, which a single pass can set with gimple_set_uid and retrieve with
gimple_uid, but that uid does not survive the end of a single pass (so you cannot use it
to communicate data between two different passes of your plugin).

Regards

--

-- 
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 mine, sont seulement les miennes} ***
Permalink | Reply |
headers
Brett Foster | 2 Jun 2012 20:47

Re: Traversing trees in a plugin...

On Sat, Jun 2, 2012 at 11:31 AM, Basile Starynkevitch
<basile <at> starynkevitch.net> wrote:
> In the MELT meta-plugin (recall that MELT is a high-level domain specific language to
> extend GCC, see http://gcc-melt.org/ for more) we extensively use associative hash-tables
> for that. MELT offers homogeneous hash-tables, e.g. hash-table associating tree (i.e.
> non-null tree pointers) to arbitrary non-null MELT values (e.g. MELT closures, or MELT
> lists, or MELT objects, etc etc), or hash-table associating (non null) gimple to non
> null MELT values.
>
> So you can have e.g. an hash-table associating each tree (every tree is in GCC a non-null
> pointer to a structure) with data associated to it. Once it has some data you know that
> this tree has been visited.

I'll poke around the MELT source code -

In Melt, where in source code may I have a look to see how trees and
mapped to the hash table? Are you able to summarize the basics? I.e.
the hash for a specific node tree is derived from what data? Pointer
address?

Thanks for the info.
Permalink | Reply |
headers
Basile Starynkevitch | 2 Jun 2012 21:02

Re: Traversing trees in a plugin...

On Sat, 2 Jun 2012 11:47:51 -0700
Brett Foster <fosterb <at> edgeandvertex.org> wrote:

> On Sat, Jun 2, 2012 at 11:31 AM, Basile Starynkevitch
> <basile <at> starynkevitch.net> wrote:
> > In the MELT meta-plugin (recall that MELT is a high-level domain specific language to
> > extend GCC, see http://gcc-melt.org/ for more) we extensively use associative hash-tables
> > for that. MELT offers homogeneous hash-tables, e.g. hash-table associating tree (i.e.
> > non-null tree pointers) to arbitrary non-null MELT values (e.g. MELT closures, or MELT
> > lists, or MELT objects, etc etc), or hash-table associating (non null) gimple to non
> > null MELT values.
> >
> > So you can have e.g. an hash-table associating each tree (every tree is in GCC a non-null
> > pointer to a structure) with data associated to it. Once it has some data you know that
> > this tree has been visited.
> 
> I'll poke around the MELT source code -
> 
> In Melt, where in source code may I have a look to see how trees and
> mapped to the hash table? Are you able to summarize the basics? I.e.
> the hash for a specific node tree is derived from what data? Pointer
> address?

MELT has a generic pointer (using the pointer address as hash function) to MELT value hash
table. In its file melt-runtime.c which you can browse at
http://gcc.gnu.org/viewcvs/branches/melt-branch/gcc/melt-runtime.c
you can find near lines 3795-4020 functions like meltgc_raw_new_mappointers
meltgc_raw_put_mappointers melt_raw_get_mappointers ...

There are used from inline functions in gcc/melt-runtime.h &
(Continue reading)

Permalink | Reply |
headers
Ian Lance Taylor | 4 Jun 2012 07:40
Picon
Favicon
Gravatar

Re: Traversing trees in a plugin...

Brett Foster <fosterb <at> edgeandvertex.org> writes:

> 1) How to marking a node as visited by my algorithm (without screwing
> up the compiler!)

Use a pointer_set.

> 2) How to associate additional data (perhaps a pointer to something
> else) to a node (like a unique identifier, or a pointer to a data
> structure).

Use a pointer_map.

> b) However with types (especially those that are anonymous) I find it
> challenging to do so. I assign such a node an anonymous identifier or
> try to assign a general data type (i.e. integer) when the type is
> internal.

With types, use TYPE_CANONICAL to get the type that you should add to
the pointer_set or pointer_map.  I admit it gets more complicated if
TYPE_CANONICAL is not appropriate for your plugin, e.g., if you need to
distinguish different typedefs for the same type.

> 2) Can memory addresses be used to uniquely identify nodes? I believe
> this may be the case for identifier nodes.

Yes.

Ian
(Continue reading)

Permalink | Reply |

Gmane