Message ID | orlio23y73.fsf@livre.localdomain |
---|---|
State | New |
Headers | show |
Alexandre Oliva <aoliva@redhat.com> writes: > On Feb 15, 2012, Richard Sandiford <rdsandiford@googlemail.com> wrote: > >> I'm fine with putting it in and seeing what breaks. But I'd really >> prefer if we knew in theory. :-) > > Ok, I dove into the problem without a testcase, and I managed to trigger > it on other platforms after tweaking get_addr a bit so as use loc lists > form canonical values, and to avoid returning other VALUEs if other > alternatives exist. > >> Like I say, my understanding before this patch series went in was that >> cselib values weren't supposed to be cyclic. Now that they are, what >> should consumers like memrefs_conflict_p do to avoid getting stuck? > > I'm now testing the following heuristic: only use an expr instead of a > value if the expr doesn't reference any value whose uid is greater than > that of the value. This worked for libgcc so far; regstrapping now. > > Here's the revised patch that addresses Jakub's and your comments, that > regstrapped on x86_64-linux-gnu and i686-linux-gnu, followed by the > patch I'm testing now on both platforms. Thanks for tackling this. I agree it looks like the patch should work. I have to admit I still don't like these changes, and it still isn't obvious to me when canonical_cselib_val is supposed to be used. I'd much rather we kept to the original dag. But I realise that probably isn't a useful attitude to take, and I don't know vartracking well enough to understand the constraints, so I'll shut up now. Richard
On Fri, Feb 17, 2012 at 02:01:36AM -0200, Alexandre Oliva wrote: > for gcc/ChangeLog > from Alexandre Oliva <aoliva@redhat.com> > > PR debug/52001 > * cselib.c (preserve_only_constants): Rename to... > (preserve_constants_and_equivs): ... this. Split out... > (invariant_or_equiv_p): ... this. Preserve plus expressions > of other preserved expressions too. > (cselib_reset_table): Adjust. > * var-tracking.c (reverse_op): Use canonical value to build > reverse operation. This patch is ok for the trunk, provided testing was successful. Jakub
On Feb 19, 2012, Richard Sandiford <rdsandiford@googlemail.com> wrote: > I have to admit I still don't like these changes > I'd much rather we kept to the original dag. I'm not sure I mentioned before, but it remains a DAG unless cselib_add_permanent_equiv is called. Only var-tracking calls it, and even then, only when VTA is enabled, so if anyone ever runs into a problem, it's easy enough to disable VTA, var-tracking or even -g altogether to work around the problem. Now, I confess I didn't expect problems in the first place, for I'd missed this use of alias.c by var-tracking. The other use, in find_base_term, had been properly adjusted already. There aren't any other uses of CSELIB_VAL_PTR, so I'm now pretty confident we won't run into any other problems like this. (famous last words ;-) > and it still isn't obvious to me when canonical_cselib_val is supposed > to be used. For comparison of VALUEs, it avoids the need for recursive or combinatorial compares, for all equivalent VALUEs map directly to the single canonical value. For recursive searches and other the like, it's just an optimization to avoid an additional recursion (avoiding recursing into *any* VALUEs is recommended along with it). Other algorithms that iterate over loc lists and recurse should take care to avoid infinite recursion, by marking already-visited nodes (cselib and var-tracking do some of this), temporarily zeroing out their loc lists (like find_base_term), or using other mechanisms to break recursion cycles (like get_addr). Algorithms that didn't expect naked VALUEs in loc lists (like get_addr) may need adjusting to iterate over the loc lists of the canonical value (for non-canonical values have a single loc, the canonical value), and to disregard values in canonical value's lists (unless e.g. we happen to be looking for VALUEs that turn out to be noncanonical). In other cases, the use of canonical values instead of noncanonical ones when filling in data structures (say, building expressions to record in cselib) may save memory by avoiding duplication, but since it causes cselib to compute different hashes, we'd better use whatever is most likely to be searched for by hashing. (We could tweak lookups to use canonical values and to recompute hashes when adding equivalences between values already used in expressions, but this hasn't been done yet). I hope this makes some sense ;-)
Alexandre Oliva <aoliva@redhat.com> writes: > On Feb 19, 2012, Richard Sandiford <rdsandiford@googlemail.com> wrote: >> and it still isn't obvious to me when canonical_cselib_val is supposed >> to be used. > > For comparison of VALUEs, it avoids the need for recursive or > combinatorial compares, for all equivalent VALUEs map directly to the > single canonical value. For recursive searches and other the like, it's just > an optimization to avoid an additional recursion (avoiding recursing > into *any* VALUEs is recommended along with it). > > Other algorithms that iterate over loc lists and recurse should take > care to avoid infinite recursion, by marking already-visited nodes > (cselib and var-tracking do some of this), temporarily zeroing out their > loc lists (like find_base_term), or using other mechanisms to break > recursion cycles (like get_addr). > > Algorithms that didn't expect naked VALUEs in loc lists (like get_addr) > may need adjusting to iterate over the loc lists of the canonical value > (for non-canonical values have a single loc, the canonical value), and > to disregard values in canonical value's lists (unless e.g. we happen to > be looking for VALUEs that turn out to be noncanonical). > > In other cases, the use of canonical values instead of noncanonical ones > when filling in data structures (say, building expressions to record in > cselib) may save memory by avoiding duplication, but since it causes > cselib to compute different hashes, we'd better use whatever is most > likely to be searched for by hashing. (We could tweak lookups to use > canonical values and to recompute hashes when adding equivalences > between values already used in expressions, but this hasn't been done > yet). > > I hope this makes some sense ;-) Yeah, it does, thanks. It seemed that when we recorded two values V1 and V2 were equivalent, we added V1 to V2's location list and V2 to V1's location list. But it sounds from the above like the canonical value is what we want in almost all cases, so if V2 is the one that becomes "noncanonical", is it really worth adding V2 to V1's location list? Richard
On Feb 26, 2012, Richard Sandiford <rdsandiford@googlemail.com> wrote: > It seemed that when we recorded two values V1 and V2 were equivalent, > we added V1 to V2's location list and V2 to V1's location list. But > it sounds from the above like the canonical value is what we want in > almost all cases, so if V2 is the one that becomes "noncanonical", is > it really worth adding V2 to V1's location list? I'd given that some thought and concluded that it wasn't safe to take V2 out of V1's list, in case what we were searching for among V1's locations was precisely V2. Now, maybe there are ways around that that (say, canonicalizing a value before searching for it) that I haven't given much thought. I didn't think it would buy us much, but I could easily be wrong, and I'd be glad to look into this given evidence that I am.
for gcc/ChangeLog from Alexandre Oliva <aoliva@redhat.com> PR debug/52001 * alias.c (refs_newer_value_cb, refs_newer_value_p): New. (get_addr): Walk canonical value's locs. Avoid returning VALUEs and locs that reference values newer than the non-canonical value at hand. Return the canonical value as a worst case. (memrefs_conflict_p): Walk canonical value's locs. Index: gcc/alias.c =================================================================== --- gcc/alias.c.orig 2012-02-17 01:14:43.734347934 -0200 +++ gcc/alias.c 2012-02-17 01:47:33.506632170 -0200 @@ -1773,6 +1773,29 @@ base_alias_check (rtx x, rtx y, enum mac return 1; } +/* Callback for for_each_rtx, that returns 1 upon encountering a VALUE + whose UID is greater than the int uid that D points to. */ + +static int +refs_newer_value_cb (rtx *x, void *d) +{ + if (GET_CODE (*x) == VALUE && CSELIB_VAL_PTR (*x)->uid > *(int *)d) + return 1; + + return 0; +} + +/* Return TRUE if EXPR refers to a VALUE whose uid is greater than + that of V. */ + +static bool +refs_newer_value_p (rtx expr, rtx v) +{ + int minuid = CSELIB_VAL_PTR (v)->uid; + + return for_each_rtx (&expr, refs_newer_value_cb, &minuid); +} + /* Convert the address X into something we can use. This is done by returning it unchanged unless it is a value; in the latter case we call cselib to get a more useful rtx. */ @@ -1788,14 +1811,20 @@ get_addr (rtx x) v = CSELIB_VAL_PTR (x); if (v) { + v = canonical_cselib_val (v); for (l = v->locs; l; l = l->next) if (CONSTANT_P (l->loc)) return l->loc; for (l = v->locs; l; l = l->next) - if (!REG_P (l->loc) && !MEM_P (l->loc)) + if (!REG_P (l->loc) && !MEM_P (l->loc) && GET_CODE (l->loc) != VALUE + && !refs_newer_value_p (l->loc, x)) + return l->loc; + for (l = v->locs; l; l = l->next) + if (REG_P (l->loc) || (GET_CODE (l->loc) != VALUE + && !refs_newer_value_p (l->loc, x))) return l->loc; - if (v->locs) - return v->locs->loc; + /* Return the canonical value. */ + return v->val_rtx; } return x; } @@ -1873,7 +1902,8 @@ memrefs_conflict_p (int xsize, rtx x, in { struct elt_loc_list *l = NULL; if (CSELIB_VAL_PTR (x)) - for (l = CSELIB_VAL_PTR (x)->locs; l; l = l->next) + for (l = canonical_cselib_val (CSELIB_VAL_PTR (x))->locs; + l; l = l->next) if (REG_P (l->loc) && rtx_equal_for_memref_p (l->loc, y)) break; if (l) @@ -1891,7 +1921,8 @@ memrefs_conflict_p (int xsize, rtx x, in { struct elt_loc_list *l = NULL; if (CSELIB_VAL_PTR (y)) - for (l = CSELIB_VAL_PTR (y)->locs; l; l = l->next) + for (l = canonical_cselib_val (CSELIB_VAL_PTR (y))->locs; + l; l = l->next) if (REG_P (l->loc) && rtx_equal_for_memref_p (l->loc, x)) break; if (l)