Message ID | 20190506122828.3dxgpidbssnn3qjp@kam.mff.cuni.cz |
---|---|
State | New |
Headers | show |
Series | aliasing_component_refs_p tweek | expand |
On Mon, 6 May 2019, Jan Hubicka wrote: > Hi, > this patch makes aliasing_component_refs_p little bit stronger, especially > with LTO increasing number of disambiguations on tramp3d by 2%. > > It took me a while to uderstand that function so a bit summary what it > does. > > Function analyzes chains of nested references like > > ref1: a.b.c.d.e > ref2: c.d.f > > (Here I assume that type of a is a and type of b is b etc.) > > On such chains it looks for outermost common type (c) and then compares > accesss c.d.e and c.d.f for range overlap. This is safe because we know > that both copies of type c are either overlaping or completely > different. > > Walk is done in both directions so > > ref1: c.d.f > ref2: a.b.c.d.e > > Gives the same answer. > > In the final step it is assumed that the reference chains do not have > common type and may reference one to another only if one is continuation > of the other (with some intermediate steps omitted). > > So function is organized as follows > > 1) perform walk of ref1 looking for type of base of ref2. > If we sucessful use base+offset oracle. > 2) perform walk of ref2 looking for type of base of ref1 > If we sucessful use base+offset oracle. > 3) assume that chains are disjoiont and see of base type of one is subset > of ref type of the other (i.e. one can be can be a continuation of the > chain). > > Now same_type_for_tbaa can return -1 for some odd cases which include the case > where TYPE_CANONICAL==NULL the function gives up. This is quite common with > LTO because TYPE_CANONICAL is NULL for pointers, vectors and arrays and thus we > often give up after the innermost reference. > > If the first walk in 1) terminates with -1 then it still makes sense to do the > walk in 2) and see if the common type is found. If there is no common type we > need to give up on the final test. > > I wonder if as an optimization we do not want to terminate the walk when one > type is too small to hold the second. > > Bootstrapped/regtested x86_64-linux, OK? > > * tree-ssa-alias.c (aliasing_component_refs_p): Walk references > both directions even if first walk fails. > Index: tree-ssa-alias.c > =================================================================== > --- tree-ssa-alias.c (revision 270877) > +++ tree-ssa-alias.c (working copy) > @@ -814,10 +841,7 @@ aliasing_component_refs_p (tree ref1, > && same_type_for_tbaa (TREE_TYPE (*refp), type1) == 0) > refp = &TREE_OPERAND (*refp, 0); > same_p = same_type_for_tbaa (TREE_TYPE (*refp), type1); > - /* If we couldn't compare types we have to bail out. */ > - if (same_p == -1) > - return true; > - else if (same_p == 1) > + if (same_p == 1) > { > poly_int64 offadj, sztmp, msztmp; > bool reverse; > @@ -827,24 +851,31 @@ aliasing_component_refs_p (tree ref1, > offset1 -= offadj; > return ranges_maybe_overlap_p (offset1, max_size1, offset2, max_size2); > } > - /* If we didn't find a common base, try the other way around. */ > - refp = &ref1; > - while (handled_component_p (*refp) > - && same_type_for_tbaa (TREE_TYPE (*refp), type2) == 0) > - refp = &TREE_OPERAND (*refp, 0); > - same_p = same_type_for_tbaa (TREE_TYPE (*refp), type2); > - /* If we couldn't compare types we have to bail out. */ > - if (same_p == -1) > - return true; > - else if (same_p == 1) > + else > { No need for the else {} and thus indenting the rest since the if () arm always returns from the function. OK with eliding this else { } wrapping. Thanks, Richard. > - poly_int64 offadj, sztmp, msztmp; > - bool reverse; > - get_ref_base_and_extent (*refp, &offadj, &sztmp, &msztmp, &reverse); > - offset1 -= offadj; > - get_ref_base_and_extent (base2, &offadj, &sztmp, &msztmp, &reverse); > - offset2 -= offadj; > - return ranges_maybe_overlap_p (offset1, max_size1, offset2, max_size2); > + int same_p2; > + > + /* If we didn't find a common base, try the other way around. */ > + refp = &ref1; > + while (handled_component_p (*refp) > + && same_type_for_tbaa (TREE_TYPE (*refp), type2) == 0) > + refp = &TREE_OPERAND (*refp, 0); > + same_p2 = same_type_for_tbaa (TREE_TYPE (*refp), type2); > + if (same_p2 == 1) > + { > + poly_int64 offadj, sztmp, msztmp; > + bool reverse; > + get_ref_base_and_extent (*refp, &offadj, &sztmp, &msztmp, &reverse); > + offset1 -= offadj; > + get_ref_base_and_extent (base2, &offadj, &sztmp, &msztmp, &reverse); > + offset2 -= offadj; > + return ranges_maybe_overlap_p (offset1, max_size1, > + offset2, max_size2); > + } > + /* In the remaining test we assume that there is no overlapping type > + at all. So if we are unsure, we need to give up. */ > + else if (same_p == -1 || same_p2 == -1) > + return true; > } > > /* If we have two type access paths B1.path1 and B2.path2 they may >
> > No need for the else {} and thus indenting the rest since the if () > arm always returns from the function. > > OK with eliding this else { } wrapping. Ah, right, I changed the function bit too many times :) Here is updated patch I re-tested and comitted. * tree-ssa-alias.c (aliasing_component_refs_p): Continue looking for comparaible types in the second direction even if first one hits incomparable type. Index: tree-ssa-alias.c =================================================================== --- tree-ssa-alias.c (revision 270877) +++ tree-ssa-alias.c (working copy) @@ -795,7 +795,7 @@ aliasing_component_refs_p (tree ref1, tree base1, base2; tree type1, type2; tree *refp; - int same_p; + int same_p, same_p2; /* Choose bases and base types to search for. */ base1 = ref1; @@ -814,10 +814,7 @@ aliasing_component_refs_p (tree ref1, && same_type_for_tbaa (TREE_TYPE (*refp), type1) == 0) refp = &TREE_OPERAND (*refp, 0); same_p = same_type_for_tbaa (TREE_TYPE (*refp), type1); - /* If we couldn't compare types we have to bail out. */ - if (same_p == -1) - return true; - else if (same_p == 1) + if (same_p == 1) { poly_int64 offadj, sztmp, msztmp; bool reverse; @@ -827,26 +824,31 @@ aliasing_component_refs_p (tree ref1, offset1 -= offadj; return ranges_maybe_overlap_p (offset1, max_size1, offset2, max_size2); } + /* If we didn't find a common base, try the other way around. */ refp = &ref1; while (handled_component_p (*refp) && same_type_for_tbaa (TREE_TYPE (*refp), type2) == 0) refp = &TREE_OPERAND (*refp, 0); - same_p = same_type_for_tbaa (TREE_TYPE (*refp), type2); - /* If we couldn't compare types we have to bail out. */ - if (same_p == -1) - return true; - else if (same_p == 1) + same_p2 = same_type_for_tbaa (TREE_TYPE (*refp), type2); + if (same_p2 == 1) { poly_int64 offadj, sztmp, msztmp; bool reverse; get_ref_base_and_extent (*refp, &offadj, &sztmp, &msztmp, &reverse); offset1 -= offadj; get_ref_base_and_extent (base2, &offadj, &sztmp, &msztmp, &reverse); offset2 -= offadj; - return ranges_maybe_overlap_p (offset1, max_size1, offset2, max_size2); + return ranges_maybe_overlap_p (offset1, max_size1, + offset2, max_size2); } + /* In the remaining test we assume that there is no overlapping type + at all. So if we are unsure, we need to give up. */ + if (same_p == -1 || same_p2 == -1) + return true; + /* If we have two type access paths B1.path1 and B2.path2 they may only alias if either B1 is in B2.path2 or B2 is in B1.path1. But we can still have a path that goes B1.path1...B2.path2 with
Index: tree-ssa-alias.c =================================================================== --- tree-ssa-alias.c (revision 270877) +++ tree-ssa-alias.c (working copy) @@ -814,10 +841,7 @@ aliasing_component_refs_p (tree ref1, && same_type_for_tbaa (TREE_TYPE (*refp), type1) == 0) refp = &TREE_OPERAND (*refp, 0); same_p = same_type_for_tbaa (TREE_TYPE (*refp), type1); - /* If we couldn't compare types we have to bail out. */ - if (same_p == -1) - return true; - else if (same_p == 1) + if (same_p == 1) { poly_int64 offadj, sztmp, msztmp; bool reverse; @@ -827,24 +851,31 @@ aliasing_component_refs_p (tree ref1, offset1 -= offadj; return ranges_maybe_overlap_p (offset1, max_size1, offset2, max_size2); } - /* If we didn't find a common base, try the other way around. */ - refp = &ref1; - while (handled_component_p (*refp) - && same_type_for_tbaa (TREE_TYPE (*refp), type2) == 0) - refp = &TREE_OPERAND (*refp, 0); - same_p = same_type_for_tbaa (TREE_TYPE (*refp), type2); - /* If we couldn't compare types we have to bail out. */ - if (same_p == -1) - return true; - else if (same_p == 1) + else { - poly_int64 offadj, sztmp, msztmp; - bool reverse; - get_ref_base_and_extent (*refp, &offadj, &sztmp, &msztmp, &reverse); - offset1 -= offadj; - get_ref_base_and_extent (base2, &offadj, &sztmp, &msztmp, &reverse); - offset2 -= offadj; - return ranges_maybe_overlap_p (offset1, max_size1, offset2, max_size2); + int same_p2; + + /* If we didn't find a common base, try the other way around. */ + refp = &ref1; + while (handled_component_p (*refp) + && same_type_for_tbaa (TREE_TYPE (*refp), type2) == 0) + refp = &TREE_OPERAND (*refp, 0); + same_p2 = same_type_for_tbaa (TREE_TYPE (*refp), type2); + if (same_p2 == 1) + { + poly_int64 offadj, sztmp, msztmp; + bool reverse; + get_ref_base_and_extent (*refp, &offadj, &sztmp, &msztmp, &reverse); + offset1 -= offadj; + get_ref_base_and_extent (base2, &offadj, &sztmp, &msztmp, &reverse); + offset2 -= offadj; + return ranges_maybe_overlap_p (offset1, max_size1, + offset2, max_size2); + } + /* In the remaining test we assume that there is no overlapping type + at all. So if we are unsure, we need to give up. */ + else if (same_p == -1 || same_p2 == -1) + return true; } /* If we have two type access paths B1.path1 and B2.path2 they may