[PATCH] PR middle-end/100810: Penalize IV candidates with undefined value bases

Roger Sayle roger@nextmovesoftware.com
Tue Aug 31 06:21:35 GMT 2021

Time to hopefully earn some goodwill from the team; this patch fixes
a P1 wrong-code-on-valid regression in ivopts.  Many thanks to Andrew
Pinski for help with the analysis.

Consider the code fragment below:

        int i;
        for (j=0; j<10; j++)

This results in a loop containing two induction variables, i and j,
where j is initialized, but i isn't (typically indicated in tree dumps
by qualified ssa names like i(D).  In PR 100810, the loop optimizers
end up selecting i as the "best" candidate (perhaps because having no
initialization it's cheaper) which leads to problems in later passes
when (the equivalent of) j is considered not to have the value 10 after
the loop, as its definition is now computed from an undefined/uninitialized

The fix below is to add a field to track whether any "iv_group" contains
a use of an iv based on a undefined value, and then prohibit IVs that are
based on undefined values from being candidates for groups that don't use
undefined values.  This may seem lenient, but it allows an IV with an
undefined base to be a candidate for itself, and is a sufficient condition
to avoid the above bug/regression.  A stricter condition might be to only
allow "undefined_value iv"s as candidates for iv_groups where *all*
uses are to "undefined_value ivs"?  My concern was that this might lead
to cases/loops that no longer have suitable candidates (i.e. a possible
performance regression).

Hopefully, the tree-loop optimization experts agree with my analysis/fix.

This patch has been tested on x86_64-pc-linux-gnu with a "make bootstrap"
and "make -k check" with no new failures.  Ok for mainline?

2021-08-31  Roger Sayle  <roger@nextmovesoftware.com>
	    Andrew Pinski  <apinski@marvell.com>

	PR middle-end/100810
	* tree-ssa-loop-ivopts.c (struct iv_group): Add a new
	uses_undefined_value_p field, indicating this group has
	uses of iv's whose base is ssa_undefined_value_p.
	(record_use): Update uses_undefined_value_p as required.
	(record_group): Initialize uses_undefined_value_p to false.
	(determine_group_iv_cost_generic): Consider a candidate with
	a ssa_undefined_value_p base to have infinite_cost for a
	group where uses_undefined_value_p is false.

	PR middle-end/100810
	* gcc.dg/pr100810.c: New test case.


-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: patchl.txt
URL: <https://gcc.gnu.org/pipermail/gcc-patches/attachments/20210831/abfb0673/attachment.txt>
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: pr100810.c
URL: <https://gcc.gnu.org/pipermail/gcc-patches/attachments/20210831/abfb0673/attachment.c>

More information about the Gcc-patches mailing list