Re: alias and pointers analysis

Re: alias and pointers analysis

[J.C. Pizarro]

On 10/26/07, Diego Novillo <dnovillo@google.com> wrote:
> SSA names of pointers are also pointers, when points-to sets are
> computed for SSA names, what you get is all the symbols that the
> particular SSA name has been found to point to.  Eg,
>
> if (...)
>   p_1 = &a;
> else
>   p_2 = &b;
> endif
> p_3 = phi (p_1, p_2)
>
> points-to (p_1) = { a }
> points-to (p_2) = { b }
> points-to (p_3) = { a b }

What is the matter if the 'b' var. is unused and
optimally removed by the SSA algorithm?

int a;
int b;

a = 2;
p_4 = phi(a)
// b doesn't used here
if (...)
  p_1 = &a;
else
  p_2 = &b;
endif
p_3 = phi (p_1, p_2)

points-to (p_1) = { a }
points-to (p_2) = { b }
points-to (p_3) = { a b }

In this case, should exist hidden p_5 = phi(b) although 'b' is not used
but yes used his reference to phantom cell 'b'. It's weird for me.

I've not idea WHERE put "hidden p_5 = phi(b)"!

Too it's possible to ocurr *p_2 = c where 'b' will be hidden used through
the pointer p_2. It's too weird for me.

    J.C. Pizarro

Re: alias and pointers analysis

[Diego Novillo]

On 10/26/07, J.C. Pizarro <jcpiza@gmail.com> wrote:

> What is the matter if the 'b' var. is unused and
> optimally removed by the SSA algorithm?

In this case, it will not be removed.  If any of the p_i pointers is
ever dereferenced in this code, that will be considered a use of
variable 'b'.


> int a;
> int b;
>
> a = 2;
> p_4 = phi(a)

Is this 'phi' as in a PHI function or a function in your code?  If the
former, then it's wrong, you can never have such a phi function in
this code snippet.

> // b doesn't used here
> if (...)
>   p_1 = &a;
> else
>   p_2 = &b;
> endif
> p_3 = phi (p_1, p_2)
>
> points-to (p_1) = { a }
> points-to (p_2) = { b }
> points-to (p_3) = { a b }
>
> In this case, should exist hidden p_5 = phi(b) although 'b' is not used
> but yes used his reference to phantom cell 'b'. It's weird for me.

I recommend that you read about the SSA form.  PHI nodes are special
constructs that exist only where multiple control flow paths reach a
common join node.  The getting started section of the wiki has links
to books and articles about it.  Morgan's book on compiler
optimization is fairly good.

> I've not idea WHERE put "hidden p_5 = phi(b)"!

No such thing exists.


> Too it's possible to ocurr *p_2 = c where 'b' will be hidden used through
> the pointer p_2. It's too weird for me.

Yes, that is possible, an that is precisely what alias analysis tells
the compiler.  We know from the analysis that reading/writing to
'*p_2' is exactly the same as reading/writing to 'b'.

Re: alias and pointers analysis

[Fran Baena]

Hi again,

i have been studing gcc docs to undestand SSA and steps to take to get
SSA form. In one GCC online document:
http://gcc.gnu.org/projects/tree-ssa/#ssa, the steps to translate to
SSA form are listed. Here, i copy and paste the mentioned text:

[....]
Conversion to SSA form is a three step process driven from tree-optimize.c:

   1. Convert the function into GIMPLE form. Implemented in gimplify.c
and c-simplify.c.
   2. Find variable references in the code. Implemented in tree-dfa.c.
   3. Build a control-flow graph (CFG). Implemented in tree-cfg.c.
This implementation uses the same basic_block structure used by the
RTL optimizers. This allows us to share most of the existing CFG code.
   4. Rewrite the tree in SSA form. Implemented in tree-ssa.c.
[....]

But i still doubt about the process, in some ways:

*  Is the step #2 related to the alias analysis? That is hold with the
def-use chains, and SMT / NMT structures. And, make any sense doing
these step before the SSA variable versioning? If positive answer,
why?

Thanks in advance

Fran.



2007/10/26, Diego Novillo <dnovillo@google.com>:
> On 10/26/07, J.C. Pizarro <jcpiza@gmail.com> wrote:
>
> > What is the matter if the 'b' var. is unused and
> > optimally removed by the SSA algorithm?
>
> In this case, it will not be removed.  If any of the p_i pointers is
> ever dereferenced in this code, that will be considered a use of
> variable 'b'.
>
>
> > int a;
> > int b;
> >
> > a = 2;
> > p_4 = phi(a)
>
> Is this 'phi' as in a PHI function or a function in your code?  If the
> former, then it's wrong, you can never have such a phi function in
> this code snippet.
>
> > // b doesn't used here
> > if (...)
> >   p_1 = &a;
> > else
> >   p_2 = &b;
> > endif
> > p_3 = phi (p_1, p_2)
> >
> > points-to (p_1) = { a }
> > points-to (p_2) = { b }
> > points-to (p_3) = { a b }
> >
> > In this case, should exist hidden p_5 = phi(b) although 'b' is not used
> > but yes used his reference to phantom cell 'b'. It's weird for me.
>
> I recommend that you read about the SSA form.  PHI nodes are special
> constructs that exist only where multiple control flow paths reach a
> common join node.  The getting started section of the wiki has links
> to books and articles about it.  Morgan's book on compiler
> optimization is fairly good.
>
> > I've not idea WHERE put "hidden p_5 = phi(b)"!
>
> No such thing exists.
>
>
> > Too it's possible to ocurr *p_2 = c where 'b' will be hidden used through
> > the pointer p_2. It's too weird for me.
>
> Yes, that is possible, an that is precisely what alias analysis tells
> the compiler.  We know from the analysis that reading/writing to
> '*p_2' is exactly the same as reading/writing to 'b'.
>

Re: alias and pointers analysis

[Diego Novillo]

On Nov 13, 2007 1:38 PM, Fran Baena <franbaena@gmail.com> wrote:

>    1. Convert the function into GIMPLE form. Implemented in gimplify.c
> and c-simplify.c.
>    2. Find variable references in the code. Implemented in tree-dfa.c.
>    3. Build a control-flow graph (CFG). Implemented in tree-cfg.c.
> This implementation uses the same basic_block structure used by the
> RTL optimizers. This allows us to share most of the existing CFG code.
>    4. Rewrite the tree in SSA form. Implemented in tree-ssa.c.
> [....]
>
> But i still doubt about the process, in some ways:
>
> *  Is the step #2 related to the alias analysis?

Yes, though this documentation is fairly old.  Finding referenced
variables is needed to determine what symbols are of interest.

> That is hold with the
> def-use chains, and SMT / NMT structures. And, make any sense doing
> these step before the SSA variable versioning? If positive answer,
> why?

Sorry, I don't understand this question.


Diego.

Re: alias and pointers analysis

[deepak poola]

hi,
 i have a some what similar confusion . i am trying to implement
reference count algo for c. i need to knw how to manupulate pionters
and which file i need to alter.
 for example if i have some statements like
int *p,*q,a;
p=&a;
q=p;

and i need to change the pointer assignments so that i can increment
the assignmnets for reference counting....
can anybody suggest me or guide me regarding this

-- deepak

On 11/14/07, Diego Novillo <dnovillo@google.com> wrote:
> On Nov 13, 2007 1:38 PM, Fran Baena <franbaena@gmail.com> wrote:
>
> >    1. Convert the function into GIMPLE form. Implemented in gimplify.c
> > and c-simplify.c.
> >    2. Find variable references in the code. Implemented in tree-dfa.c.
> >    3. Build a control-flow graph (CFG). Implemented in tree-cfg.c.
> > This implementation uses the same basic_block structure used by the
> > RTL optimizers. This allows us to share most of the existing CFG code.
> >    4. Rewrite the tree in SSA form. Implemented in tree-ssa.c.
> > [....]
> >
> > But i still doubt about the process, in some ways:
> >
> > *  Is the step #2 related to the alias analysis?
>
> Yes, though this documentation is fairly old.  Finding referenced
> variables is needed to determine what symbols are of interest.
>
> > That is hold with the
> > def-use chains, and SMT / NMT structures. And, make any sense doing
> > these step before the SSA variable versioning? If positive answer,
> > why?
>
> Sorry, I don't understand this question.
>
>
> Diego.
>

Re: alias and pointers analysis

[Diego Novillo]

deepak poola wrote:

> and i need to change the pointer assignments so that i can increment
> the assignmnets for reference counting....
> can anybody suggest me or guide me regarding this

You want to instrument every pointer assignment?  You probably want to 
write a GIMPLE pass that looks for pointer assignments.  There is 
information on how to write passes in the getting started section of the 
wiki.  http://gcc.gnu.org/wiki/GettingStarted

Re: alias and pointers analysis

[Fran Baena]

2007/11/13, Diego Novillo <dnovillo@google.com>:
> On Nov 13, 2007 1:38 PM, Fran Baena <franbaena@gmail.com> wrote:
>
> >    1. Convert the function into GIMPLE form. Implemented in gimplify.c
> > and c-simplify.c.
> >    2. Find variable references in the code. Implemented in tree-dfa.c.
> >    3. Build a control-flow graph (CFG). Implemented in tree-cfg.c.
> > This implementation uses the same basic_block structure used by the
> > RTL optimizers. This allows us to share most of the existing CFG code.
> >    4. Rewrite the tree in SSA form. Implemented in tree-ssa.c.
> > [....]
> >
> > But i still doubt about the process, in some ways:
> >
> > *  Is the step #2 related to the alias analysis?
>
> Yes, though this documentation is fairly old.  Finding referenced
> variables is needed to determine what symbols are of interest.
>
> > That is hold with the
> > def-use chains, and SMT / NMT structures. And, make any sense doing
> > these step before the SSA variable versioning? If positive answer,
> > why?
>
> Sorry, I don't understand this question.

I mean that, if that structures (def-use chains, SMT, NMT, etc) are
constructed before the SSA step where the program variables are
versioned, after the variable versioning we will get that these
structures are not congruent with the new variables generated in the
mentioned step.

The issue i dont understand is why alias analysis is done before the
SSA pass, and, if all the structures created within these analysis are
used in next optimization passes (dead code elimination, constant
propagation.........)

Thanks for all

Fran

Re: alias and pointers analysis

[Diego Novillo]

Fran Baena wrote:

> The issue i dont understand is why alias analysis is done before the
> SSA pass

It isn't.  You are reading very stale documentation.  That was the 
status when we were only doing type-based alias analysis.  You should 
read the current implementation and documents.  See 
http://gcc.gnu.org/wiki/GettingStarted.


Diego.

Re: alias and pointers analysis

[Diego Novillo]

On 10/25/07, Fran Baena <franbaena@gmail.com> wrote:

> * Why alias analysis? I mean, the pointers could be versioned like the
> others vars. (I'm not saying it's not usefull, i mean i don't
> understand the alias analisys goals)

SSA names of pointers are also pointers, when points-to sets are
computed for SSA names, what you get is all the symbols that the
particular SSA name has been found to point to.  Eg,

if (...)
  p_1 = &a;
else
  p_2 = &b;
endif
p_3 = phi (p_1, p_2)

points-to (p_1) = { a }
points-to (p_2) = { b }
points-to (p_3) = { a b }



> * What is the significance of Use-Def chains? How are they construct?
> Are related to VDEF/DEF and VUSE/USE?

On GIMPLE they are built with the VDEF/VUSE operators.  The argument
of a VUSE/VDEF operator links to the VDEF operator that created the
argument.  In RTL, the chains are maintained using the DF data
structures.


> Note: i'm beginning i'd need something basic, conceptual docs.

I suggest the tutorials and presentations in the Getting Started
section of the wiki (http://gcc.gnu.org/wiki/GettingStarted).  Also,
some compiler books that may help are listed in that section as well
(IIRC).

alias and pointers analysis

[Fran Baena]

Hi,

once i have been reading lots of documents about SSA computing. I have
a few questions, conceptual ones, that stop me understanding the whole
goal of the method. Here i go:

* Why alias analysis? I mean, the pointers could be versioned like the
others vars. (I'm not saying it's not usefull, i mean i don't
understand the alias analisys goals)

* What is the significance of Use-Def chains? How are they construct?
Are related to VDEF/DEF and VUSE/USE?

Note: i'm beginning i'd need something basic, conceptual docs.

thanks and c u all