[gcc r14-9174] fold-const: Avoid infinite recursion in +-*&|^minmax reassociation [PR114084]

[gcc r14-9174] fold-const: Avoid infinite recursion in +-*&|^minmax reassociation [PR114084]

[Jakub Jelinek]

https://gcc.gnu.org/g:f9d2a95be5680e04f53141c2675798b06d23f409

commit r14-9174-gf9d2a95be5680e04f53141c2675798b06d23f409
Author: Jakub Jelinek <jakub@redhat.com>
Date:   Mon Feb 26 10:07:39 2024 +0100

    fold-const: Avoid infinite recursion in +-*&|^minmax reassociation [PR114084]
    
    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.
    
    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.

Diff:
---
 gcc/fold-const.cc                | 51 ++++++++++++++++++++++++++++++++--------
 gcc/testsuite/gcc.dg/bitint-94.c | 12 ++++++++++
 2 files changed, 53 insertions(+), 10 deletions(-)

diff --git a/gcc/fold-const.cc b/gcc/fold-const.cc
index 80e211e18c0e..43105d20be35 100644
--- a/gcc/fold-const.cc
+++ b/gcc/fold-const.cc
@@ -11779,6 +11779,15 @@ fold_binary_loc (location_t loc, enum tree_code code, tree type,
 		  + (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 tree_code code, tree type,
 
 	      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 tree_code code, tree type,
 		      /* 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 tree_code code, tree type,
 		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));
diff --git a/gcc/testsuite/gcc.dg/bitint-94.c b/gcc/testsuite/gcc.dg/bitint-94.c
new file mode 100644
index 000000000000..ca32043a095d
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/bitint-94.c
@@ -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);
+}