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.
