Re: [PATCH] tree-optimization/106514 - revisit m_import compute in backward threading

[Andrew MacLeod <amacleod@redhat.com>]

On 8/10/22 06:46, Richard Biener wrote:
>
> I see the solver itself adds relations from edges on the path so
> the cruical item here seems to be to add imports for the path
> entry conditional, but those would likely be GORI imports for that
> block?  Unfortunately that fails to add t[012], the GORI exports
> seem to cover all that's needed but then exports might be too much

the GORI export list is the list of names which which GORi thinks might 
be different on the outgoing edges from a block.

The GORI import list is the list of names which GORI thinks can affect 
those ranges from outside the block.  It doesnt try to look at 
individual PHI aguments, so IIRC it treats a PHI def as originating 
outside the block for import purposes.  This should be a subset of the 
export list.

GORI info is only every concerned ONLY with the basic block... all 
external influences are considrered to be in the import list. And all 
GORI calculations utilize a range_of_expr query from a range_query to 
resolve the incoming value of an import in order to calculate an 
outgoing edge.

outgoing_edge_range_p () has some additional smarts in it which allows 
for recomputations. You may have noticed the depend1/depend2 fields in 
the range_def_chain structure.  These are quick and dirty caches which 
represent the first 2 ssa-names encountered on the stmt when it was 
processed.  so for PHIs, the first 2 ssa names encountered, and for 
simple range-op qualifying stmts, the 1 or 2 ssanames in the def stmt 
for an ssa-name.

If you ask for the range of a_32 on an outgoing edge, and it is not in 
the export list, GORI would not be able to provide a range. 
Outgoing_edge_range_p utilizes those 2 depend fields as a quick check to 
see if a recomputation may give us a better range.  if either depend1 or 
depend2 asociated with a_32 IS i the export list, then it performs a 
recompuation of a_32 instead of a GORI calculation.  ie  from the 
example in my previous note:

   a_32 = f_16 + 10
<...>
bb88:
   if (f_16 < 20)
bb89:
      b_8 = a_32 + 8

depend1 for a_32 will be f_16.
during rangers evaluation of b_8 in bb89, it will ask for the range of 
a_32 on the edge 88->89.  a_32 is not an export, but it sees that 
depend1 (f_16) is in the export list, so it does a recalculation of a_32 
on the edge, coming up with f_16 being [0, 19] and returning a_32 as 
[10, 29].

This is why you may see outgoing_edge_range_p coming up with things that 
GORI itself doesnt actually provide...

your example:

void foo (int nest, int print_nest)
{
   _Bool t0 = nest != 0;
   _Bool t1 = nest == print_nest;
   _Bool t2 = t0 & t1;
   if (t2)
     __builtin_puts ("x");
   nest++;
   if (nest > 2)
     __builtin_abort ();
   if (print_nest == nest)
     __builtin_puts ("y");
}


if (nest > 2) , : nest is the only import and export in that block, but 
outgoing_edge_range_p would be able to recompute t1 and t0 on those 
edges as nest is used in defining them. Likewise, print_nest is used in 
defining t1, so it can also be recomputed. on the final edges.     This 
could be why adding some dependencies from outside the block sometimes 
gets a better result.

the recomputation information is not rolled into the GORI exports, as it 
is more dynamic.  we don't know which order this will be seen in, so we 
dont know what ssa_names in advance use 'nest' in their calculations.   
we could add them as they are seen, but then the bitmaps could explode 
in size.. so leaving it in this dynamic quick check seemed more practical.

There is no mapping from a name to the other ssanames that depend on it 
in either..  ie, given 'nest', there is no mechaism to see that t0 and 
t1 use it.   I had considered building this list as well, but at the 
moment didnt have a lot of use for it and thought a use map might get 
large quickly.

I wonder if what might help is to loop thru all the interesting names 
that have been calculated, and adding  the GORI export names from the 
original block which occur in either a depend1 or depend2 field of those 
names..   That would be more concise than the entire gori export list. 
if it is just the entry path exports that are relevant, then perhaps as 
names are added to the interesting list we could check if either of its 
'depend's fields is in the entry blocks export list, and add it then.


> here?  At least that's what the code in compute_imports effectively
> does (also for the entry block).  But I do wonder why compute_ranges
> does not add relations computed by the entry conditional ...
> That's probably because of
>
> void
> path_range_query::compute_outgoing_relations (basic_block bb, basic_block
> next)
> {
>    gimple *stmt = last_stmt (bb);
>
>    if (stmt
>        && gimple_code (stmt) == GIMPLE_COND
>        && (import_p (gimple_cond_lhs (stmt))
>            || import_p (gimple_cond_rhs (stmt))))
>
> where for a condition like above the names in the imports are not
> in the condition itself.  The gori.outgoing_edge_range_p compute
> of the import ranges is appearantly not affected by this
> restriction and picks up nest as ~[0, 0] on the respective path
> even though, while 'nest' is in imports, the temporaries are not.
> That would support the argument to drop the import_p checks in
> path_range_query::compute_outgoing_relations.
>
> I'm not sure it's worth fixing incrementally though, it's fallout
> of r12-5157-gbfa04d0ec958eb that in some way did the reverse of
> my patch.  Interestingly hybrid_jt_simplifier::compute_ranges_from_state
> still computes imports itself before calling compute_ranges.
>
> For comparing thread numbers fixing the current state incrementally
> would be nice I guess, I will test something but not further pursue it
> if not successful.
>
> Richard.