This is the mail archive of the mailing list for the GCC project.

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[Ada] Avoid exponential complexity gimplifying checks

While ideally it would be fine to have many shared trees, trees are unshared 
during gimplification.  In the case of run time checks on arithmetic 
operations, each check references its arguments multiple times.  Without 
save_expr, the number of trees may grow by a factor of 4 as a result of each 
checked operation.  With N nested expressions, the total number of trees 
becomes 4^N.

Fixed thusly, tested on i586-suse-linux, applied on the mainline.

2008-11-15  Geert Bosch  <>

	* gcc-interface/trans.c (emit_check): Put back a final save_expr
	to prevent exponential expansion during gimplification.

Eric Botcazou
Index: gcc-interface/trans.c
--- gcc-interface/trans.c	(revision 138273)
+++ gcc-interface/trans.c	(revision 138274)
@@ -6289,7 +6289,10 @@ emit_check (tree gnu_cond, tree gnu_expr
      we don't need to evaluate it just for the check.  */
   TREE_SIDE_EFFECTS (gnu_result) = TREE_SIDE_EFFECTS (gnu_expr);
-  return gnu_result;
+  /* ??? Unfortunately, if we don't put a SAVE_EXPR around this whole thing,
+     we will repeatedly do the test and, at compile time, we will repeatedly
+     visit it during unsharing, which leads to an exponential explosion.  */
+  return save_expr (gnu_result);
 /* Return an expression that converts GNU_EXPR to GNAT_TYPE, doing

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]