Question about exporting omputing alias sets

Question about exporting omputing alias sets

[Erick Ochoa]

Hello,

I am trying to find out all pointers which alias a pointer and place 
them in a set.

I am using `ptr_derefs_may_alias_p` to find out if two pointers may 
point to the same memory location. I think this yields conservative 
results (i.e., when it cannot be proven that to pointers may alias, it 
will give the result "true"). This is what I need.

To collect all pointers which alias pointer "p", this means is that I 
have to collect all pointer variables and all pointer expressions in the 
program and then call `ptr_derefs_may_alias_p` O(n) times to find the 
set of pointers which alias pointer "p". If I have to do this for all 
pointers in the program, that would mean O(n^2).

This also implies that in order for my sets to be correct I need to 
collect all pointer variables and all pointer expressions. I think that 
a better idea would be to have a list of all bitmap solutions and for 
every variable with a bitmap if position j is set, assigned to alias set 
j. In pseudocode:

compute_alias_sets(bitmap set)
{
   // create array of sets of same length as varmap
   // call it alias_map
   for (i = 0; i < varmap.length (); i++)
   {
     bitmap set = get_varinfo(i)->solution;
     EXECUTE_IF_SET_IN_BITMAP (set, 0, j, bi)
     {
       varinfo_t v = get_varinfo (j);
       alias_map[j].insert(v);
     }
   }
}

I think this is a better implementation. I don't need to worry about 
collecting all pointer expressions and I think varmap also contains 
declarations. (I think IPA-PTA already has "collected" all pointer 
expressions/declarations in varmap and created constraint variables for 
them.) *Would there be an issue with exporting varmap and delaying its 
deletion to this pass I'm working on?* This pass is intended to be run 
immediately after IPA-PTA. After this, I think I would still need to do 
some refining on the "alias_map" since (I think) there are more 
constraint variables than gimple variables in the partition, but the 
information I look for should be able to be derived from here.

Thanks!

Re: Question about exporting omputing alias sets

[Richard Biener]

On Wed, Sep 2, 2020 at 10:04 AM Erick Ochoa
<erick.ochoa@theobroma-systems.com> wrote:
>
> Hello,
>
> I am trying to find out all pointers which alias a pointer and place
> them in a set.
>
> I am using `ptr_derefs_may_alias_p` to find out if two pointers may
> point to the same memory location. I think this yields conservative
> results (i.e., when it cannot be proven that to pointers may alias, it
> will give the result "true"). This is what I need.
>
> To collect all pointers which alias pointer "p", this means is that I
> have to collect all pointer variables and all pointer expressions in the
> program and then call `ptr_derefs_may_alias_p` O(n) times to find the
> set of pointers which alias pointer "p". If I have to do this for all
> pointers in the program, that would mean O(n^2).
>
> This also implies that in order for my sets to be correct I need to
> collect all pointer variables and all pointer expressions. I think that
> a better idea would be to have a list of all bitmap solutions and for
> every variable with a bitmap if position j is set, assigned to alias set
> j. In pseudocode:
>
> compute_alias_sets(bitmap set)
> {
>    // create array of sets of same length as varmap
>    // call it alias_map
>    for (i = 0; i < varmap.length (); i++)
>    {
>      bitmap set = get_varinfo(i)->solution;
>      EXECUTE_IF_SET_IN_BITMAP (set, 0, j, bi)
>      {
>        varinfo_t v = get_varinfo (j);
>        alias_map[j].insert(v);
>      }
>    }
> }
>
> I think this is a better implementation. I don't need to worry about
> collecting all pointer expressions and I think varmap also contains
> declarations. (I think IPA-PTA already has "collected" all pointer
> expressions/declarations in varmap and created constraint variables for
> them.) *Would there be an issue with exporting varmap and delaying its
> deletion to this pass I'm working on?* This pass is intended to be run
> immediately after IPA-PTA. After this, I think I would still need to do
> some refining on the "alias_map" since (I think) there are more
> constraint variables than gimple variables in the partition, but the
> information I look for should be able to be derived from here.

I think you should add the code to compute your "alias sets" to
IPA-PTA if struct-reorg is enabled and export those like
we "export" the IPA escaped set (ipa_escaped_pt) to later
passes.

I agree that you want to work on the points-to solutions rather
than start from pointers and expressions in GIMPLE.

Richard.

> Thanks!