SSA alias representation
> Symbols with their address taken are only renamed when they appear as > virtual operands. So, if you have: > > p_3 = (i_5 > 10) ? &a : &b > a = 4 > > notice that 'a' is never renamed in the LHS of the assignment. It's > renamed as a virtual operand: > > p_3 = (i_5 > 10) ? &a : &b > > # a_9 = VDEF > a = 4 I have seen -fdump-tree-salias-all-vops, and i have realized that "a" is never renamed. That means that a previous scan of the tree is needed to know which symbols do not need to be versioned and which do need. I suppose that each definition and use of "a" has associated its virtual operator (as shown in next portion of code), to maintain the FUD chain. After that previous scan the renaming pass is applied. # a_8 = VDEF a = 1; p_3 = (i_5 > 10) ? &a : &b # a_9 = VDEF a = 4 Thanks Fran
Re: SSA alias representation
On Tue, Feb 26, 2008 at 04:44, Fran Baena <[EMAIL PROTECTED]> wrote:
> if ()
> t_1 = & a_1;t_1 points-to { a_1 }
> else
> if ()
> t2_ = & b_1; t_2 points-to { b_1 }
> else
> t_3 = & c_1; t_3 points-to { c_1 }
>
> # t_4 = PHI
> p_1 = t_4; p_1 and t_4 points-to { a_1, b_1, c_1 }
Not quite, points-to sets always have symbols, not SSA names. Use
-fdump-tree-salias-all-vops to see how things are renamed.
Symbols with their address taken are only renamed when they appear as
virtual operands. So, if you have:
p_3 = (i_5 > 10) ? &a : &b
a = 4
notice that 'a' is never renamed in the LHS of the assignment. It's
renamed as a virtual operand:
p_3 = (i_5 > 10) ? &a : &b
# a_9 = VDEF
a = 4
Diego.
Re: SSA alias representation
>
> When there are no symbols in the pointer's points-to set.
>
I am beginning to realize. But there is something it remains:
1) Once the ssa rename has been done, the alias analysis begins
(points-to sets). Each version of a base pointer has associated its
own points-to set? Like
if ()
t_1 = & a_1;t_1 points-to { a_1 }
else
if ()
t2_ = & b_1; t_2 points-to { b_1 }
else
t_3 = & c_1; t_3 points-to { c_1 }
# t_4 = PHI
p_1 = t_4; p_1 and t_4 points-to { a_1, b_1, c_1 }
2) If a virtual operator is inserted for each symbol found in a
points-to set and since the virtual operands are inserted after the
ssa renaming, how virtual operands are versioned to keep a correct
version state between real and virtual operators? For instance, given
the next code
if ()
t_1 = & a_1;t_1 points-to { a_1 }
else
if ()
t2_ = & b_1; t_2 points-to { b_1 }
else
t_3 = & c_1; t_3 points-to { c_1 }
p_1 = t_4; p_1 and t_4 points-to { a_1, b_1, c_1 }
*p_2 = 5; *p_2 -> NMT that is associated to points-to {
a_1, b_1, c_1 }
the virtual operators will be placed and versioned like this:
if ()
t_1 = & a_1;t_1 points-to { a_1 }
else
if ()
t2_ = & b_1; t_2 points-to { b_1 }
else
t_3 = & c_1; t_3 points-to { c_1 }
# t_4 = PHI
# VUSE
# VUSE
# VUSE
p_1 = t_4; p_1 and t_4 points-to { a_1, b_1, c_1 }
# a_2 = VDEF
# b_2 = VDEF
# c_2 = VDEF
*p_2 = 5; *p_2 -> NMT that is associated to points-to {
a_1, b_1, c_1 }
Thank you very much for your help.
Fran
Re: SSA alias representation
On Mon, Feb 25, 2008 at 10:25, Fran Baena <[EMAIL PROTECTED]> wrote: > If a name tag is associated to a ssa name, ¿when does it make sense to > version a name tag? (If it does) When there are no symbols in the pointer's points-to set. Diego.
Re: SSA alias representation
If a name tag is associated to a ssa name, ¿when does it make sense to version a name tag? (If it does) 2008/2/21, Diego Novillo <[EMAIL PROTECTED]>: > On 2/21/08 1:13 PM, Fran Baena wrote: > > 2008/2/21, Diego Novillo <[EMAIL PROTECTED]>: > >> On 2/19/08 2:27 PM, Fran Baena wrote: > >> > Hi everybody, > >> > > >> > i am studing how gcc carries out Alias Representation and some > questions appear. > >> > > >> > For instance, given this code portion: > >> > > >> > if ( ... ) > >> >p = &a; > >> > else > >> >if ( ... ) > >> > p = &b; > >> >else > >> > p = &c; > >> > > >> > a = 5; > >> > b = 3; > >> > d = *p4; > >> > > >> > My questions are: > >> > > >> > - both p like *p need a Name Memory Tag structure? It is enough with > only one? > >> > >> > >> Pointer dereferences do not receive NMTs, only the pointers. So a name > >> tag will be associated with the SSA name resulting from the PHI node > >> created at the end of that if() tree. > > > > And this name tag is versioned too, like this: > > if ( ... ) > > p = &a; (NMTv1 associated to p) > > else > > if ( ... ) > > p = &b;(NMTv2 associated to p) > > else > > p = &c;(NMTv3 associated to p) > > > > No. None of these SSA names are dereferenced so no name tag is created > for them. The only SSA name with a name tag will be the one produced by > the PHI. > > See the output of -fdump-tree-salias-vops-blocks. That will show you > the results of the first alias analysis run. > > > > To organize temporarily the passes. Firstly alias analysis is > > computed, it is followed by ssa form, and after that the memory ssa > > web, aren't they? > > > No. First SSA then alias analysis then the memory SSA > > > > Where could i find all the passes applied and their order? > > > passes.c:init_optimization_passes. > > > > What is register SSA form? Is it the standard SSA form explained in > > "Efficiently computing static single assignment form and the control > > dependence graph (cytron91)"? > > > Yes. It's the traditional rewriting form. The memory SSA web is the > factored use-def chains by Wolfe. > > > See the tutorials in http://gcc.gnu.org/wiki/GettingStarted, all this is > described there. > > > > Diego. >
Re: SSA alias representation
On 2/21/08 1:13 PM, Fran Baena wrote: 2008/2/21, Diego Novillo <[EMAIL PROTECTED]>: On 2/19/08 2:27 PM, Fran Baena wrote: > Hi everybody, > > i am studing how gcc carries out Alias Representation and some questions appear. > > For instance, given this code portion: > > if ( ... ) >p = &a; > else >if ( ... ) > p = &b; >else > p = &c; > > a = 5; > b = 3; > d = *p4; > > My questions are: > > - both p like *p need a Name Memory Tag structure? It is enough with only one? Pointer dereferences do not receive NMTs, only the pointers. So a name tag will be associated with the SSA name resulting from the PHI node created at the end of that if() tree. And this name tag is versioned too, like this: if ( ... ) p = &a; (NMTv1 associated to p) else if ( ... ) p = &b;(NMTv2 associated to p) else p = &c;(NMTv3 associated to p) No. None of these SSA names are dereferenced so no name tag is created for them. The only SSA name with a name tag will be the one produced by the PHI. See the output of -fdump-tree-salias-vops-blocks. That will show you the results of the first alias analysis run. To organize temporarily the passes. Firstly alias analysis is computed, it is followed by ssa form, and after that the memory ssa web, aren't they? No. First SSA then alias analysis then the memory SSA Where could i find all the passes applied and their order? passes.c:init_optimization_passes. What is register SSA form? Is it the standard SSA form explained in "Efficiently computing static single assignment form and the control dependence graph (cytron91)"? Yes. It's the traditional rewriting form. The memory SSA web is the factored use-def chains by Wolfe. See the tutorials in http://gcc.gnu.org/wiki/GettingStarted, all this is described there. Diego.
Re: SSA alias representation
2008/2/21, Diego Novillo <[EMAIL PROTECTED]>: > On 2/19/08 2:27 PM, Fran Baena wrote: > > Hi everybody, > > > > i am studing how gcc carries out Alias Representation and some questions > appear. > > > > For instance, given this code portion: > > > > if ( ... ) > >p = &a; > > else > >if ( ... ) > > p = &b; > >else > > p = &c; > > > > a = 5; > > b = 3; > > d = *p4; > > > > My questions are: > > > > - both p like *p need a Name Memory Tag structure? It is enough with only > one? > > > Pointer dereferences do not receive NMTs, only the pointers. So a name > tag will be associated with the SSA name resulting from the PHI node > created at the end of that if() tree. And this name tag is versioned too, like this: if ( ... ) p = &a; (NMTv1 associated to p) else if ( ... ) p = &b;(NMTv2 associated to p) else p = &c;(NMTv3 associated to p) # p = PHI <> (NMTv4 associated to p) This is, a name tag is constantly being versioned, isnt it? > > - About versioning : every name can be versioned, cannot it? > > > Sorry, I don't understand the question. SSA names have a version > number, yes. Is that what you're asking? Yes, bad formed. Sorry, it is about my english > >- when are virtual operands inserted? Do they have to be versioned > > at same time that real operands? For instance, # a6 = VDEF ; a7 = > > 3;, this implies that alias computation is processed at same time that > > SSA Renaming? > > > No, the memory SSA web is built after the first stage of alias analysis. > First, the program is put in register SSA form, a few passes later the > memory SSA UD web is built on top. > To organize temporarily the passes. Firstly alias analysis is computed, it is followed by ssa form, and after that the memory ssa web, aren't they? Where could i find all the passes applied and their order? What is register SSA form? Is it the standard SSA form explained in "Efficiently computing static single assignment form and the control dependence graph (cytron91)"? > >- Could the others names (TMT, NMT, SFT, etc.) be versioned? > > (every name that is able to be part of a virtual operand could be > > versioned) > > > Yes. When a pointer does not have a specific set of symbols in its > points-to set, its memory tag is used. > My bigger doubt is when are each structure computed: alias set, names tags, UD chains. Thanks very much!! Fran
Re: SSA alias representation
On 2/19/08 2:27 PM, Fran Baena wrote: Hi everybody, i am studing how gcc carries out Alias Representation and some questions appear. For instance, given this code portion: if ( ... ) p = &a; else if ( ... ) p = &b; else p = &c; a = 5; b = 3; d = *p4; My questions are: - both p like *p need a Name Memory Tag structure? It is enough with only one? Pointer dereferences do not receive NMTs, only the pointers. So a name tag will be associated with the SSA name resulting from the PHI node created at the end of that if() tree. - About versioning : every name can be versioned, cannot it? Sorry, I don't understand the question. SSA names have a version number, yes. Is that what you're asking? - when are virtual operands inserted? Do they have to be versioned at same time that real operands? For instance, # a6 = VDEF ; a7 = 3;, this implies that alias computation is processed at same time that SSA Renaming? No, the memory SSA web is built after the first stage of alias analysis. First, the program is put in register SSA form, a few passes later the memory SSA UD web is built on top. - Could the others names (TMT, NMT, SFT, etc.) be versioned? (every name that is able to be part of a virtual operand could be versioned) Yes. When a pointer does not have a specific set of symbols in its points-to set, its memory tag is used. Diego.
SSA alias representation
Hi everybody, i am studing how gcc carries out Alias Representation and some questions appear. For instance, given this code portion: if ( ... ) p = &a; else if ( ... ) p = &b; else p = &c; a = 5; b = 3; d = *p4; My questions are: - both p like *p need a Name Memory Tag structure? It is enough with only one? - About versioning : every name can be versioned, cannot it? - when are virtual operands inserted? Do they have to be versioned at same time that real operands? For instance, # a6 = VDEF ; a7 = 3;, this implies that alias computation is processed at same time that SSA Renaming? - Could the others names (TMT, NMT, SFT, etc.) be versioned? (every name that is able to be part of a virtual operand could be versioned) Thank you in advance, Fran
