diff mbox series

- ICE verify_vssa exceeds stack space for big functions [PR124805]

Message ID 2c4ed43b-9787-4c50-b0d9-ee213a3bb896@hexco.de
State New
Headers
Series - ICE verify_vssa exceeds stack space for big functions [PR124805] |

Checks

Context Check Description
linaro-tcwg-bot/tcwg_gcc_build--master-aarch64 success Build passed
linaro-tcwg-bot/tcwg_gcc_build--master-arm success Build passed
linaro-tcwg-bot/tcwg_gcc_check--master-arm success Test passed
linaro-tcwg-bot/tcwg_gcc_check--master-aarch64 fail Test failed

Commit Message

Heiko Eißfeldt April 8, 2026, 9:36 p.m. UTC 
  The source from PR124561 led to an ICE with --enable-checking, caused by a stack overflow.
The recursive verification code verify_vssa in tree-ssa.cc could not handle the extreme
number of basic blocks within the typical limits of stack space.

As for PR124561 the recursive code was transformed into an iterative version, which
avoided the recursive calls.

A worklist is used, which has as entries a pair of a basic_block and a tree (vdef).
The logic of verification steps for each basic_block is unchanged, although the order
of basic_blocks is changed.

This fixes PR124805.

Reg tested OK.

2026-04-07 Heiko Eißfeldt <heiko@hexco.de>

	PR middle-end/124805
	* tree-ssa.cc (verify_vssa):
	replace recursive calls with iteration for lower stack usage

Comments

Richard Biener April 9, 2026, 12:08 p.m. UTC | #1 
On Wed, Apr 8, 2026 at 11:32 PM Heiko Eißfeldt <heiko.Eissfeldt@hexco.de> wrote:
>
> The source from PR124561 led to an ICE with --enable-checking, caused by a stack overflow.
> The recursive verification code verify_vssa in tree-ssa.cc could not handle the extreme
> number of basic blocks within the typical limits of stack space.
>
> As for PR124561 the recursive code was transformed into an iterative version, which
> avoided the recursive calls.
>
> A worklist is used, which has as entries a pair of a basic_block and a tree (vdef).
> The logic of verification steps for each basic_block is unchanged, although the order
> of basic_blocks is changed.
>
> This fixes PR124805.
>
> Reg tested OK.

This is OK for stage1.

Thanks,
Richard.

> 2026-04-07 Heiko Eißfeldt <heiko@hexco.de>
>
> PR middle-end/124805
> * tree-ssa.cc (verify_vssa):
> replace recursive calls with iteration for lower stack usage
diff mbox series

Patch

diff --git a/gcc/tree-ssa.cc b/gcc/tree-ssa.cc
index 3c899eb5979..e110e4acf2b 100644
--- a/gcc/tree-ssa.cc
+++ b/gcc/tree-ssa.cc
@@ -636,96 +636,119 @@  release_defs_bitset (bitmap toremove)
 /* Verify virtual SSA form.  */
 
 bool
-verify_vssa (basic_block bb, tree current_vdef, sbitmap visited)
+verify_vssa (basic_block bb_start, tree current_vdef, sbitmap visited)
 {
   bool err = false;
 
-  if (!bitmap_set_bit (visited, bb->index))
-    return false;
+  struct state_t {
+    basic_block bb;
+    tree	vdef;
+  } state;
+
+  auto_vec<state_t, 3> worklist;
+  state.bb = bb_start;
+  state.vdef = current_vdef;
+  worklist.safe_push (state);
 
-  /* Pick up the single virtual PHI def.  */
-  gphi *phi = NULL;
-  for (gphi_iterator si = gsi_start_phis (bb); !gsi_end_p (si);
-       gsi_next (&si))
+  while (!worklist.is_empty ())
     {
-      tree res = gimple_phi_result (si.phi ());
-      if (virtual_operand_p (res))
+      const auto &state = worklist.pop ();
+      const auto &bb = state.bb;
+      current_vdef = state.vdef;
+
+      if (!bitmap_set_bit (visited, bb->index))
+	continue;
+
+      /* Pick up the single virtual PHI def.  */
+      gphi *phi = NULL;
+      for (gphi_iterator si = gsi_start_phis (bb); !gsi_end_p (si);
+	   gsi_next (&si))
+	{
+	  tree res = gimple_phi_result (si.phi ());
+	  if (virtual_operand_p (res))
+	    {
+	      if (phi)
+		{
+		  error ("multiple virtual PHI nodes in BB %d", bb->index);
+		  print_gimple_stmt (stderr, phi, 0);
+		  print_gimple_stmt (stderr, si.phi (), 0);
+		  err = true;
+		}
+	      else
+		phi = si.phi ();
+	    }
+	}
+      if (phi)
 	{
-	  if (phi)
+	  current_vdef = gimple_phi_result (phi);
+	  if (TREE_CODE (current_vdef) != SSA_NAME)
 	    {
-	      error ("multiple virtual PHI nodes in BB %d", bb->index);
+	      error ("virtual definition is not an SSA name");
 	      print_gimple_stmt (stderr, phi, 0);
-	      print_gimple_stmt (stderr, si.phi (), 0);
 	      err = true;
 	    }
-	  else
-	    phi = si.phi ();
 	}
-    }
-  if (phi)
-    {
-      current_vdef = gimple_phi_result (phi);
-      if (TREE_CODE (current_vdef) != SSA_NAME)
+
+      /* Verify stmts.  */
+      for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
+	   gsi_next (&gsi))
 	{
-	  error ("virtual definition is not an SSA name");
-	  print_gimple_stmt (stderr, phi, 0);
-	  err = true;
+	  gimple *stmt = gsi_stmt (gsi);
+	  tree vuse = gimple_vuse (stmt);
+	  if (vuse)
+	    {
+	      if (vuse != current_vdef)
+		{
+		  error ("stmt with wrong VUSE");
+		  print_gimple_stmt (stderr, stmt, 0, TDF_VOPS);
+		  fprintf (stderr, "expected ");
+		  print_generic_expr (stderr, current_vdef);
+		  fprintf (stderr, "\n");
+		  err = true;
+		}
+	      tree vdef = gimple_vdef (stmt);
+	      if (vdef)
+		{
+		  current_vdef = vdef;
+		  if (TREE_CODE (current_vdef) != SSA_NAME)
+		    {
+		      error ("virtual definition is not an SSA name");
+		      print_gimple_stmt (stderr, phi, 0);
+		      err = true;
+		    }
+		}
+	    }
 	}
-    }
 
-  /* Verify stmts.  */
-  for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
-       gsi_next (&gsi))
-    {
-      gimple *stmt = gsi_stmt (gsi);
-      tree vuse = gimple_vuse (stmt);
-      if (vuse)
+      /* Verify destination PHI uses and add successors to worklist.  */
+      edge_iterator ei;
+      edge e;
+      FOR_EACH_EDGE (e, ei, bb->succs)
 	{
-	  if (vuse != current_vdef)
+	  gphi *phi = get_virtual_phi (e->dest);
+	  if (phi
+	     && PHI_ARG_DEF_FROM_EDGE (phi, e) != current_vdef)
 	    {
-	      error ("stmt with wrong VUSE");
-	      print_gimple_stmt (stderr, stmt, 0, TDF_VOPS);
+	      error ("PHI node with wrong VUSE on edge from BB %d",
+		     e->src->index);
+	      print_gimple_stmt (stderr, phi, 0, TDF_VOPS);
 	      fprintf (stderr, "expected ");
 	      print_generic_expr (stderr, current_vdef);
 	      fprintf (stderr, "\n");
 	      err = true;
 	    }
-	  tree vdef = gimple_vdef (stmt);
-	  if (vdef)
+
+	  /* Add successor BB along with current vdef to worklist.  */
+	  if (!bitmap_bit_p (visited, e->dest->index))
 	    {
-	      current_vdef = vdef;
-	      if (TREE_CODE (current_vdef) != SSA_NAME)
-		{
-		  error ("virtual definition is not an SSA name");
-		  print_gimple_stmt (stderr, phi, 0);
-		  err = true;
-		}
-	    }
-	}
-    }
+	      state_t new_state;
+	      new_state.bb = e->dest;
+	      new_state.vdef = current_vdef;
 
-  /* Verify destination PHI uses and recurse.  */
-  edge_iterator ei;
-  edge e;
-  FOR_EACH_EDGE (e, ei, bb->succs)
-    {
-      gphi *phi = get_virtual_phi (e->dest);
-      if (phi
-	  && PHI_ARG_DEF_FROM_EDGE (phi, e) != current_vdef)
-	{
-	  error ("PHI node with wrong VUSE on edge from BB %d",
-		 e->src->index);
-	  print_gimple_stmt (stderr, phi, 0, TDF_VOPS);
-	  fprintf (stderr, "expected ");
-	  print_generic_expr (stderr, current_vdef);
-	  fprintf (stderr, "\n");
-	  err = true;
+	      worklist.safe_push (new_state);
+	    }
 	}
-
-      /* Recurse.  */
-      err |= verify_vssa (e->dest, current_vdef, visited);
     }
-
   return err;
 }