On Mon, 26 Feb 2024, Jakub Jelinek wrote:
> Hi!
>
> In the following testcase we infinitely recurse during BIT_IOR_EXPR
> reassociation.
> One operand is (unsigned _BitInt(31)) a << 4 and another operand
> 2147483647 >> 1 | 80 where both the right shift and the | 80
> trees have TREE_CONSTANT set, but weren't folded because of delayed
> folding, where some foldings are apparently done even in that case
> unfortunately.
> Now, the fold_binary_loc reassocation code splits both operands into
> variable part, minus variable part, constant part, minus constant part,
> literal part and minus literal parts, to prevent infinite recursion
> punts if there are just 2 parts altogether from the 2 operands and then goes
> on with reassociation, merges first the corresponding parts from both
> operands and then some further merges.
> The problem with the above expressions is that we get 3 different objects,
> var0 (the left shift), con1 (the right shift) and lit1 (80), so the infinite
> recursion prevention doesn't trigger, and we eventually merge con1 with
> lit1, which effectively reconstructs the original op1 and then associate
> that with var0 which is original op0, and associate_trees for that case
> calls fold_binary. There are some casts involved there too (the T typedef
> type and the underlying _BitInt type which are stripped with STRIP_NOPS).
>
> The following patch attempts to prevent this infinite recursion by tracking
> the origin (if certain var comes from nothing - 0, op0 - 1, op1 - 2 or both -
> 3)
> and propagates it through all the associate_tree calls which merge the vars.
> If near the end we'd try to merge what comes solely from op0 with what comes
> solely from op1 (or vice versa), the patch punts, because then it isn't any
> kind of reassociation between the two operands, if anything it should be
> handled when folding the suboperands.
That sounds like a nice thing to do.
> Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?
OK.
Thanks,
Richard.
> 2024-02-26 Jakub Jelinek <ja...@redhat.com>
>
> PR middle-end/114084
> * fold-const.cc (fold_binary_loc): Avoid the final associate_trees
> if all subtrees of var0 come from one of the op0 or op1 operands
> and all subtrees of con0 come from the other one. Don't clear
> variables which are never used afterwards.
>
> * gcc.dg/bitint-94.c: New test.
>
> --- gcc/fold-const.cc.jj 2024-02-24 09:49:09.098815803 +0100
> +++ gcc/fold-const.cc 2024-02-24 11:08:56.036223491 +0100
> @@ -11779,6 +11779,15 @@ fold_binary_loc (location_t loc, enum tr
> + (lit0 != 0) + (lit1 != 0)
> + (minus_lit0 != 0) + (minus_lit1 != 0)) > 2)
> {
> + int var0_origin = (var0 != 0) + 2 * (var1 != 0);
> + int minus_var0_origin
> + = (minus_var0 != 0) + 2 * (minus_var1 != 0);
> + int con0_origin = (con0 != 0) + 2 * (con1 != 0);
> + int minus_con0_origin
> + = (minus_con0 != 0) + 2 * (minus_con1 != 0);
> + int lit0_origin = (lit0 != 0) + 2 * (lit1 != 0);
> + int minus_lit0_origin
> + = (minus_lit0 != 0) + 2 * (minus_lit1 != 0);
> var0 = associate_trees (loc, var0, var1, code, atype);
> minus_var0 = associate_trees (loc, minus_var0, minus_var1,
> code, atype);
> @@ -11791,15 +11800,19 @@ fold_binary_loc (location_t loc, enum tr
>
> if (minus_var0 && var0)
> {
> + var0_origin |= minus_var0_origin;
> var0 = associate_trees (loc, var0, minus_var0,
> MINUS_EXPR, atype);
> minus_var0 = 0;
> + minus_var0_origin = 0;
> }
> if (minus_con0 && con0)
> {
> + con0_origin |= minus_con0_origin;
> con0 = associate_trees (loc, con0, minus_con0,
> MINUS_EXPR, atype);
> minus_con0 = 0;
> + minus_con0_origin = 0;
> }
>
> /* Preserve the MINUS_EXPR if the negative part of the literal is
> @@ -11815,15 +11828,19 @@ fold_binary_loc (location_t loc, enum tr
> /* But avoid ending up with only negated parts. */
> && (var0 || con0))
> {
> + minus_lit0_origin |= lit0_origin;
> minus_lit0 = associate_trees (loc, minus_lit0, lit0,
> MINUS_EXPR, atype);
> lit0 = 0;
> + lit0_origin = 0;
> }
> else
> {
> + lit0_origin |= minus_lit0_origin;
> lit0 = associate_trees (loc, lit0, minus_lit0,
> MINUS_EXPR, atype);
> minus_lit0 = 0;
> + minus_lit0_origin = 0;
> }
> }
>
> @@ -11833,37 +11850,51 @@ fold_binary_loc (location_t loc, enum tr
> return NULL_TREE;
>
> /* Eliminate lit0 and minus_lit0 to con0 and minus_con0. */
> + con0_origin |= lit0_origin;
> con0 = associate_trees (loc, con0, lit0, code, atype);
> - lit0 = 0;
> + minus_con0_origin |= minus_lit0_origin;
> minus_con0 = associate_trees (loc, minus_con0, minus_lit0,
> code, atype);
> - minus_lit0 = 0;
>
> /* Eliminate minus_con0. */
> if (minus_con0)
> {
> if (con0)
> - con0 = associate_trees (loc, con0, minus_con0,
> - MINUS_EXPR, atype);
> + {
> + con0_origin |= minus_con0_origin;
> + con0 = associate_trees (loc, con0, minus_con0,
> + MINUS_EXPR, atype);
> + }
> else if (var0)
> - var0 = associate_trees (loc, var0, minus_con0,
> - MINUS_EXPR, atype);
> + {
> + var0_origin |= minus_con0_origin;
> + var0 = associate_trees (loc, var0, minus_con0,
> + MINUS_EXPR, atype);
> + }
> else
> gcc_unreachable ();
> - minus_con0 = 0;
> }
>
> /* Eliminate minus_var0. */
> if (minus_var0)
> {
> if (con0)
> - con0 = associate_trees (loc, con0, minus_var0,
> - MINUS_EXPR, atype);
> + {
> + con0_origin |= minus_var0_origin;
> + con0 = associate_trees (loc, con0, minus_var0,
> + MINUS_EXPR, atype);
> + }
> else
> gcc_unreachable ();
> - minus_var0 = 0;
> }
>
> + /* Reassociate only if there has been any actual association
> + between subtrees from op0 and subtrees from op1 in at
> + least one of the operands, otherwise we risk infinite
> + recursion. See PR114084. */
> + if (var0_origin != 3 && con0_origin != 3)
> + return NULL_TREE;
> +
> return
> fold_convert_loc (loc, type, associate_trees (loc, var0, con0,
> code, atype));
> --- gcc/testsuite/gcc.dg/bitint-94.c.jj 2024-02-24 11:18:32.607018363
> +0100
> +++ gcc/testsuite/gcc.dg/bitint-94.c 2024-02-24 11:19:09.023500121 +0100
> @@ -0,0 +1,12 @@
> +/* PR middle-end/114084 */
> +/* { dg-do compile { target bitint } } */
> +/* { dg-options "-std=c23 -pedantic-errors" } */
> +
> +typedef unsigned _BitInt(31) T;
> +T a, b;
> +
> +void
> +foo (void)
> +{
> + b = (T) ((a | (-1U >> 1)) >> 1 | (a | 5) << 4);
> +}
>
> Jakub
>
>
--
Richard Biener <rguent...@suse.de>
SUSE Software Solutions Germany GmbH,
Frankenstrasse 146, 90461 Nuernberg, Germany;
GF: Ivo Totev, Andrew McDonald, Werner Knoblich; (HRB 36809, AG Nuernberg)
