Message ID | Zdw1MIKIS343WGqB@tucnak |
---|---|
State | New |
Headers | show |
Series | fold-const: Avoid infinite recursion in +-*&|^minmax reassociation [PR114084] | expand |
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 <jakub@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 > >
--- 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); +}