https://gcc.gnu.org/bugzilla/show_bug.cgi?id=125040
--- Comment #8 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to Richard Biener from comment #7)
> Created attachment 64864 [details]
> debugging patch
>
> Debugging patch that shows we do not have a cycle in values or expressions
> but instead the issue is the toplevel iteration in
> sorted_array_from_bitmap_set:
>
> FOR_EACH_VALUE_ID_IN_SET (set, i, bi)
> if (bitmap_set_bit (val_visited, i))
> pre_expr_DFS (i, set, exclusions, val_visited, result);
>
> as that can enter the expression graph at random places and thus while
> each sub-graph we visit produces a properly sorted set the overall
> set isn't appropriately sorted.
OK, but we _do_ have cycles, the debug patch doesn't see those with the entry.
Fixing the enter issue with the following patch does not resolve that part.
I'll note that apart from optimality this whole sorting is done so that we
do _not_ need to iterate or at least not as much. We still iterate PRE
insertion:
/* Sorting is not perfect, iterate locally. */
while (do_pre_regular_insertion (block, dom, exprs))
;
but we do not iterate hoist insertion. I think there's room for improvement
(possibly with the patch below), but then for clean () we probably have to
revert back to iterating. Unless we do full SCC processing so we can wipe
value cycles at whole (we then still have to iterate I think).
diff --git a/gcc/tree-ssa-pre.cc b/gcc/tree-ssa-pre.cc
index b41c7364c96..cc182f6fe36 100644
--- a/gcc/tree-ssa-pre.cc
+++ b/gcc/tree-ssa-pre.cc
@@ -1076,11 +1076,43 @@ sorted_array_from_bitmap_set (bitmap_set_t set, bool
for_insertion)
result.truncate (0);
}
+ bool single_p = true;
auto_bitmap val_visited (&grand_bitmap_obstack);
bitmap_tree_view (val_visited);
FOR_EACH_VALUE_ID_IN_SET (set, i, bi)
if (bitmap_set_bit (val_visited, i))
- pre_expr_DFS (i, set, exclusions, val_visited, result);
+ {
+ if (!result.is_empty ())
+ {
+ single_p = false;
+ result.truncate (0);
+ }
+ pre_expr_DFS (i, set, exclusions, val_visited, result);
+ /* Mark i as entry that is not forward reachable. Note we do
+ have cycles in the value graph so eventually i reaches itself. */
+ bitmap_clear_bit (val_visited, i);
+ }
+ /* If we didn't by luck visit only a single entry to the value
+ graph visit now all not forward reachable values. */
+ if (!single_p)
+ {
+ result.truncate (0);
+ auto_bitmap val_visited2 (&grand_bitmap_obstack);
+ bitmap_tree_view (val_visited2);
+ FOR_EACH_VALUE_ID_IN_SET (set, i, bi)
+ if (!bitmap_bit_p (val_visited, i))
+ {
+ if (bitmap_set_bit (val_visited2, i))
+ pre_expr_DFS (i, set, exclusions, val_visited2, result);
+ else
+ gcc_unreachable ();
+ }
+ if (flag_checking)
+ {
+ bitmap_list_view (val_visited2);
+ gcc_assert (bitmap_equal_p (&set->values, val_visited2));
+ }
+ }
return result;
}
