Re: More questions on points-to analysis

[Richard Biener via Gcc]

On Wed, Mar 17, 2021 at 4:17 PM Erick Ochoa  wrote:
>
> Hi Richard, I think I misunderstood yesterday's answer and deviated a
> little bit. But now I want to focus on this:
>
> > > * the process in GCC that generates the constraints for NULL works
> > > fine (i.e., feeding the constraints generated by GCC to an external
> > > solver should yield a conservatively correct answer) but the process
> > > that solves the constraints relaxes the solutions for the NULL
> > > constraint variable (i.e., GCC has deviated from the constraint
> > > solving algorithm somehow)
> >
> > No, that part should work OK.
> >
>
> So, let's ignore the other solver for now and instead focus on the
> concrete example I presented on the previous email. If GCC is solving
> these constraints:
>
> ```
> ANYTHING = &ANYTHING
> ESCAPED = *ESCAPED
> ESCAPED = ESCAPED + UNKNOWN
> *ESCAPED = NONLOCAL
> NONLOCAL = &NONLOCAL
> NONLOCAL = &ESCAPED
> INTEGER = &ANYTHING
> ISRA.4 = &NONLOCAL
> derefaddrtmp(9) = &NULL
> *ISRA.4 = derefaddrtmp(9)
> i = NONLOCAL
> i = &NONLOCAL
> ESCAPED = &NONLOCAL
> _2 = *ISRA.4
> ```
>
> What would a hand calculated solution gives us vs what was the
> solution given by GCC?
>
> I am following the algorithm stated on Section 3.3 of Structure
> Aliasing in GCC, and I will be ignoring the ESCAPED = ESCAPED +
> UNKNOWN constraint since there isn't any other field offset that needs
> to be calculated.
>
> First, I want to make some adjustments. I am going to be using "=" to
> signify the \supseteq symbol and I will be adding curly braces to
> specify the element in a set as opposed to the whole set. Therefore
> the constraints will now become (ordered slightly differently):
>
> ```
> direct contraints
> ANYTHING = { ANYTHING }
> ESCAPED = { NONLOCAL }
> NONLOCAL = { NONLOCAL }
> NONLOCAL =  { ESCAPED }
> INTEGER = { ANYTHING }
> ISRA.4 = { NONLOCAL }
> derefaddrtmp(9) = { NULL }
> i = { NONLOCAL }
>
> complex constraints==
> ESCAPED = *ESCAPED
> *ESCAPED = NONLOCAL
> *ISRA.4 = derefaddrtmp(9)
> _2 = *ISRA.4
>
> = copy-constraints==
> ESCAPED = ESCAPED // again ignoring the + UNKNOWN since I don't think
> it will matter...
> i = NONLOCAL
> ```
>
> Solution sets are basically the direct constraints at the moment.
>
> Let's now create the graph
>
> 1. node ESCAPED has an edge going to itself (due to the copy constraint)
> 2. node ISRA.4 has no outgoing copy edges
> 3. node derefaddrtmp(9) has no outgoing edges
> 4. node _2 has no outgoing edges
> 5. node i has an outgoing edge to NONLOCAL (due to the copy constraint)
> 6. node NONLOCAL has no outgoing edge
>
> Now, we can iterate over this set of nodes
>
> 1. Walking over node ESCAPED. Sol(ESCAPED) = {NONLOCAL}. There are no
> edges, but it has complex-constraints. Let's modify the graph.
>   1. Looking at ESCAPED = *ESCAPED we note that we need to add a copy
> edge from ESCAPED to NONLOCAL.
>   2. Looking at *ESCAPED = NONLOCAL we note that we need to add a copy
> edge from NONLOCAL to NONLOCAL
>
> The graph is now transformed to
>
> 1. node ESCAPED has an edge going to ESCAPED and NONLOCAL
> 2. node ISRA.4 has no outgoing copy edges
> 3. node derefaddrtmp(9) has no outgoing edges
> 4. node _2 has no outgoing edges
> 5. node i has an outgoing edge to NONLOCAL (due to the copy constraint)
> 6. node NONLOCAL has an edge going to NONLOCAL
>
> The solution set of escaped is now Sol(ESCAPED) = Sol(ESCAPED) U
> Sol(NONLOCAL) = {NONLOCAL, ESCAPED}
>
> Now we continue walking
>
> 2. Walking over node ISRA.4. It has the solution set { NONLOCAL }.
> There are no edges, but it has complex-constraints. Let's modify the
> graph.
>   1. Looking at *ISRA.4 = derefaddrtmp(9), we note that we need to add
> a copy edge from NONLOCAL to derefaddrtmp(9).
>
> The graph is now transformed to
>
> 1. node ESCAPED has an edge going to ESCAPED and NONLOCAL
> 2. node ISRA.4 has no outgoing copy edges
> 3. node derefaddrtmp(9) has no outgoing edges
> 4. node _2 has no outgoing edges
> 5. node i has an outgoing edge to NONLOCAL (due to the copy constraint)
> 6. node NONLOCAL has an edge going to NONLOCAL, derefaddrtmp(9)
>
> The Sol(NONLOCAL) = Sol(NONLOCAL) U Sol(derefaddrtmp(9)) = {NONLOCAL,
> ESCAPED, NULL}.
>
> Now I could continue, but here is already something that is not shown
> in the points-to sets in the dump. It shows that
>
> NONLOCAL = {NONLOCAL, ESCAPED, NULL}
>
> Looking at the data that I showed yesterday:
>
> ```
> NONLOCAL = { ESCAPED NONLOCAL } same as i
> ```
>
> we see that NULL is not in the solution set of NONLOCAL.
>
> Now, yesterday you said that NULL is not conservatively correctly
> represented in the constraints. You also said today the points-to
> analysis should be solving the constraints fine. What I now understand
> from this is that while NULL may be pointed to by some constraints, it
> doesn't mean that not being on the set means that a pointer will not
> point to NULL. However, it should still be shown in the dumps where
> the points-t

Re: 'walk_stmt_load_store_addr_ops' for non-'gimple_assign_single_p (stmt)'

[Thomas Schwinge]

Hi!

On 2021-03-17T08:46:16+0100, Richard Biener  wrote:
> On Wed, Mar 17, 2021 at 12:25 AM Thomas Schwinge
>  wrote:
>> This is a prototype/"initial hack" for a very simple implementation of
>>  "Avoid unnecessary data transfer out of OMP
>> construct".  (... to be completed and posted later.)  So simple that it
>> will easily fail (gracefully, of course), but yet is effective for a lot
>> of real-world code:
>>
>> subroutine [...]
>> [...]
>> real([...])   xx!temporary variable, for distance calculation
>> [...]
>> !$acc kernels pcopyin(x, zii) reduction(+:eva) ! implicit 'copy(xx)' for 
>> scalar used inside region; established during gimplification
>>   do 100 i=0,n-1
>> evx=0.0d0
>> do 90 j=0,n-1
>>   xx=abs(x(1,i)-x(1,j))
>> [...]
>> !$acc end kernels
>> [...]
>> ['xx' never used here]
>> end subroutine [...]
>>
>> Inside 'kernels', we'd like to automatically parallelize loops (we've
>> basically got that working; analysis by Graphite etc.), but the problem
>> is that given "implicit 'copy(xx)' for scalar used inside region", when
>> Graphite later looks at the outlined 'kernels' region's function, it must
>> assume that 'xx' is still live after the OpenACC 'kernels' construct --
>> and thus cannot treat it as a thread-private temporary, cannot
>> parallelize.
>>
>> Now, walking each function backwards (!), I'm taking note of any
>> variables' uses, and if I reach an 'kernels' construct, but have not seen
>> a use of 'xx', I may then optimize 'copy(xx)' -> 'firstprivate(xx)',
>> enabling Graphite to do its thing.  (Other such optimizations may be
>> added later.)  (This is inspired by Jakub's commit
>> 1a80d6b87d81c3f336ab199a901cf80ae349c335 "re PR tree-optimization/68128
>> (A huge regression in Parboil v2.5 OpenMP CUTCP test (2.5 times lower
>> performance))".)
>>
>> I've now got a simple 'callback_op', which for '!is_lhs' looks at
>> 'get_base_address ([op])', and if that 'var' is contained in the set of
>> current candidates (initialized per containg 'bind's, which we enter
>> first, even if walking a 'gimple_seq' backwards), removes that 'var' as a
>> candidate for such optimization.  (Plus some "details", of couse.)  This
>> seems to work fine, as far as I can tell.  :-)
>
> It might then still fail for x = a[var] when you are interested in 'var'.

That already works as expected:

gimple_assign 

..., and in the debug log ('OP' is 'get_base_address (OPERAND)'), I see:

# LOOKING INTO OPERAND:  
## OP:  
### WASN'T CANDIDATE
# LOOKING INTO OPERAND:  
## OP:  
### WASN'T CANDIDATE
# LOOKING INTO OPERAND:  
## OP:  
### NO LONGER CANDIDATE
# LOOKING INTO OPERAND:  
## IGNORED: IS_LHS

Notice 'var' "NO LONGER CANDIDATE".

Well, I cross-checked, and I'm getting this behavior (deep scanning)
because I'm (intentionally) using (default) '*walk_subtrees = 1' in my
'callback_op'.  Indeed if I specify '*walk_subtrees = 0', the debug log
changes as follows:

 # LOOKING INTO OPERAND:  
 ## OP:  
 ### WASN'T CANDIDATE
-# LOOKING INTO OPERAND:  
-## OP:  
-### WASN'T CANDIDATE
-# LOOKING INTO OPERAND:  
-## OP:  
-### NO LONGER CANDIDATE
 # LOOKING INTO OPERAND:  
 ## IGNORED: IS_LHS

..., and your projected mis-optimization:

+# OPTIMIZING map(force_tofrom:var [len: 4]) -> firstprivate(var)

If I continue to use (default) '*walk_subtrees = 1', then I might not
actually need to use 'get_base_address', because we get all the
individual sub operands visited.

> I think you want to use walk_gimple_stmt and provide walk_tree_fn which
> will recurse into the complex tree operands (also making get_base_address
> unnecessary).

I'm already using 'walk_gimple_stmt' via 'walk_gimple_seq', and I'll
(later) look into removing 'get_base_address', and also look up
'walk_tree_fn'.  Ah, wait, what you suggested with 'walk_tree_fn' is
actually what I've already got; in my last email I said "I've now got a
simple 'callback_op' [...]".  Seems we're converging!  ;-)


Grüße
 Thomas


>> Of course, the eventual IPA-based solution (see PR90591, PR94693, etc.)
>> will be much better -- but we need something now.
>>
>>
>> Grüße
>>  Thomas
-
Mentor Graphics (Deutschland) GmbH, Arnulfstrasse 201, 80634 München 
Registergericht München HRB 106955, Geschäftsführer: Thomas Heurung, Frank 
Thürauf

Re: More questions on points-to analysis

[Erick Ochoa via Gcc]

Perfect, thank you! This is exactly the answer that I was looking for.


On Thu, 18 Mar 2021 at 13:27, Richard Biener  wrote:
>
> On Wed, Mar 17, 2021 at 4:17 PM Erick Ochoa  wrote:
> >
> > Hi Richard, I think I misunderstood yesterday's answer and deviated a
> > little bit. But now I want to focus on this:
> >
> > > > * the process in GCC that generates the constraints for NULL works
> > > > fine (i.e., feeding the constraints generated by GCC to an external
> > > > solver should yield a conservatively correct answer) but the process
> > > > that solves the constraints relaxes the solutions for the NULL
> > > > constraint variable (i.e., GCC has deviated from the constraint
> > > > solving algorithm somehow)
> > >
> > > No, that part should work OK.
> > >
> >
> > So, let's ignore the other solver for now and instead focus on the
> > concrete example I presented on the previous email. If GCC is solving
> > these constraints:
> >
> > ```
> > ANYTHING = &ANYTHING
> > ESCAPED = *ESCAPED
> > ESCAPED = ESCAPED + UNKNOWN
> > *ESCAPED = NONLOCAL
> > NONLOCAL = &NONLOCAL
> > NONLOCAL = &ESCAPED
> > INTEGER = &ANYTHING
> > ISRA.4 = &NONLOCAL
> > derefaddrtmp(9) = &NULL
> > *ISRA.4 = derefaddrtmp(9)
> > i = NONLOCAL
> > i = &NONLOCAL
> > ESCAPED = &NONLOCAL
> > _2 = *ISRA.4
> > ```
> >
> > What would a hand calculated solution gives us vs what was the
> > solution given by GCC?
> >
> > I am following the algorithm stated on Section 3.3 of Structure
> > Aliasing in GCC, and I will be ignoring the ESCAPED = ESCAPED +
> > UNKNOWN constraint since there isn't any other field offset that needs
> > to be calculated.
> >
> > First, I want to make some adjustments. I am going to be using "=" to
> > signify the \supseteq symbol and I will be adding curly braces to
> > specify the element in a set as opposed to the whole set. Therefore
> > the constraints will now become (ordered slightly differently):
> >
> > ```
> > direct contraints
> > ANYTHING = { ANYTHING }
> > ESCAPED = { NONLOCAL }
> > NONLOCAL = { NONLOCAL }
> > NONLOCAL =  { ESCAPED }
> > INTEGER = { ANYTHING }
> > ISRA.4 = { NONLOCAL }
> > derefaddrtmp(9) = { NULL }
> > i = { NONLOCAL }
> >
> > complex constraints==
> > ESCAPED = *ESCAPED
> > *ESCAPED = NONLOCAL
> > *ISRA.4 = derefaddrtmp(9)
> > _2 = *ISRA.4
> >
> > = copy-constraints==
> > ESCAPED = ESCAPED // again ignoring the + UNKNOWN since I don't think
> > it will matter...
> > i = NONLOCAL
> > ```
> >
> > Solution sets are basically the direct constraints at the moment.
> >
> > Let's now create the graph
> >
> > 1. node ESCAPED has an edge going to itself (due to the copy constraint)
> > 2. node ISRA.4 has no outgoing copy edges
> > 3. node derefaddrtmp(9) has no outgoing edges
> > 4. node _2 has no outgoing edges
> > 5. node i has an outgoing edge to NONLOCAL (due to the copy constraint)
> > 6. node NONLOCAL has no outgoing edge
> >
> > Now, we can iterate over this set of nodes
> >
> > 1. Walking over node ESCAPED. Sol(ESCAPED) = {NONLOCAL}. There are no
> > edges, but it has complex-constraints. Let's modify the graph.
> >   1. Looking at ESCAPED = *ESCAPED we note that we need to add a copy
> > edge from ESCAPED to NONLOCAL.
> >   2. Looking at *ESCAPED = NONLOCAL we note that we need to add a copy
> > edge from NONLOCAL to NONLOCAL
> >
> > The graph is now transformed to
> >
> > 1. node ESCAPED has an edge going to ESCAPED and NONLOCAL
> > 2. node ISRA.4 has no outgoing copy edges
> > 3. node derefaddrtmp(9) has no outgoing edges
> > 4. node _2 has no outgoing edges
> > 5. node i has an outgoing edge to NONLOCAL (due to the copy constraint)
> > 6. node NONLOCAL has an edge going to NONLOCAL
> >
> > The solution set of escaped is now Sol(ESCAPED) = Sol(ESCAPED) U
> > Sol(NONLOCAL) = {NONLOCAL, ESCAPED}
> >
> > Now we continue walking
> >
> > 2. Walking over node ISRA.4. It has the solution set { NONLOCAL }.
> > There are no edges, but it has complex-constraints. Let's modify the
> > graph.
> >   1. Looking at *ISRA.4 = derefaddrtmp(9), we note that we need to add
> > a copy edge from NONLOCAL to derefaddrtmp(9).
> >
> > The graph is now transformed to
> >
> > 1. node ESCAPED has an edge going to ESCAPED and NONLOCAL
> > 2. node ISRA.4 has no outgoing copy edges
> > 3. node derefaddrtmp(9) has no outgoing edges
> > 4. node _2 has no outgoing edges
> > 5. node i has an outgoing edge to NONLOCAL (due to the copy constraint)
> > 6. node NONLOCAL has an edge going to NONLOCAL, derefaddrtmp(9)
> >
> > The Sol(NONLOCAL) = Sol(NONLOCAL) U Sol(derefaddrtmp(9)) = {NONLOCAL,
> > ESCAPED, NULL}.
> >
> > Now I could continue, but here is already something that is not shown
> > in the points-to sets in the dump. It shows that
> >
> > NONLOCAL = {NONLOCAL, ESCAPED, NULL}
> >
> > Looking at the data that I showed yesterday:
> >
> > ```
> > NONLOCAL = { ESCAPED NONLOCAL } same as i
> > ```
> >
> > we see that NULL is not in the solution set of NONLOCAL.
> >
> > Now, yesterday you said that NU

gcc-8-20210318 is now available

[GCC Administrator via Gcc]

Snapshot gcc-8-20210318 is now available on
  https://gcc.gnu.org/pub/gcc/snapshots/8-20210318/
and on various mirrors, see http://gcc.gnu.org/mirrors.html for details.

This snapshot has been generated from the GCC 8 git branch
with the following options: git://gcc.gnu.org/git/gcc.git branch releases/gcc-8 
revision 43ab249823d4559d1f1d68e721a8e03d52484121

You'll find:

 gcc-8-20210318.tar.xzComplete GCC

  SHA256=59be72eaf74c852c55304f800580d936c7e8c221193baa3c50570179fd0b7668
  SHA1=33678a49bc49c3d6bb6b0b13b069e27180fcc97c

Diffs from 8-20210311 are available in the diffs/ subdirectory.

When a particular snapshot is ready for public consumption the LATEST-8
link is updated and a message is sent to the gcc list.  Please do not use
a snapshot before it has been announced that way.