This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[PATCH] Avoid spending exponential time in contain_placeholder_p()
- From: Geert Bosch <bosch at adacore dot com>
- To: gcc-patches Patches <gcc-patches at gcc dot gnu dot org>
- Cc: Ian Lance Taylor <iant at google dot com>, Eric Botcazou <ebotcazou at adacore dot com>
- Date: Tue, 30 Sep 2008 14:08:16 -0400
- Subject: [PATCH] Avoid spending exponential time in contain_placeholder_p()
My recent work on a scheme for signed integer overflow checking,
intended
to eventually serve as replacement for -ftrapv, exposes some huge
(exponential?)
compile time blowup as a result of mutual recursion between
contain_placeholder_p()
and save_expr().
Here, save_expr needs to check if the expression contains a
placeholder, as those
may not be wrapped in a save_expr. However, contains_placeholder_p
recurses through
SAVE_EXPRs as well. This results in every node doing a tree walk, with
every SAVE_EXPR
also doing complete tree walk. I believe this is exponential in the
number of levels
SAVE_EXPRs are nested in a single expression.
Example of "infinite" compile time:
function sum (a, b, c, d, e, f, g, h, i, j, k, l, m,
n, o, p, q, r, s, t, u, v, w, x, y, z : Integer) return
Integer
is
pragma Unsuppress (Overflow_Check);
begin
return a + b + c + d + e + f + g + h + i + j + k + l + m
+ n + o + p + q + r + s + t + u + v + w + x + y + z;
end;
The easiest way of fixing this is observing that a SAVE_EXPR can never
contain
a placeholder, so contains_placeholder_p() can return 0 on
encountering a SAVE_EXPR.
OK to commit?
-Geert
2008-09-29 Geert Bosch <bosch@adacore.com>
* tree.c (contains_placeholder_p): Return 0 for a SAVE_EXPR
--- tree.c~ Wed Sep 17 17:39:13 2008
+++ tree.c Mon Sep 29 15:50:10 2008
@@ -2492,6 +2492,10 @@
|| CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 1))
|| CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 2)));
+ case SAVE_EXPR:
+ /* save_expr () never wraps anything containing a
placeholder */
+ return 0;
+
default:
break;
}
--- /dev/null
+++ gnat.dg/test_overflow_sum.adb
@@ -0,0 +1,45 @@
+-- { dg-do run }
+-- { dg-options "-gnato" }
+
+procedure test_overflow_sum is
+ pragma Unsuppress (Overflow_Check);
+ function sum (a, b, c, d, e, f, g, h, i, j, k, l, m,
+ n, o, p, q, r, s, t, u, v, w, x, y, z : Integer)
+ return Integer
+ is
+ begin
+ return a + b + c + d + e + f + g + h + i + j + k + l + m
+ + n + o + p + q + r + s + t + u + v + w + x + y + z;
+ end;
+
+ f : integer;
+begin
+ f := sum (a => -2**31, b => 1, c => 2**31 - 1, -- 0
+ d => 1, e => -2**31, f => 2**31 - 1, -- 0
+ g => 2**0, h => 2, i => 4, -- 2**3 - 1
+ j => 2**3, k => 2**4, l => 2**5, -- 2**6 - 1
+ m => 2**6, n => 2**7, o => 2**8, -- 2**9 - 1
+ p => 2**9, q => 2**10, r => 2**11, -- 2**12 - 1
+ s => 2**12, t => 2**13, u => 2**14, -- 2**15 - 1
+ v => 2**15, w => 2**16, x => 2**17, -- 2**18 - 1
+ y => 2**31 - 2**18, z => 0); -- 2**31 - 1
+
+ if f /= 2**31 - 1 then
+ raise Program_Error;
+ end if;
+
+ begin
+ f := sum (a => f, b => -2**31, c => 1, -- 0
+ d => -2**31, e => 1, f => f, -- 0
+ g => 2**0, h => 2, i => 4, -- 2**3 - 1
+ j => 2**3, k => 2**4, l => 2**5, -- 2**6 - 1
+ m => 2**6, n => 2**7, o => 2**8, -- 2**9 - 1
+ p => 2**9, q => 2**10, r => 2**11, -- 2**12
- 1
+ s => 2**12, t => 2**13, u => 2**14, -- 2**15
- 1
+ v => 2**15, w => 2**16, x => 2**17, -- 2**18
- 1
+ y => 2**31 - 2**18, z => 1); -- 2**31
(overflow)
+ raise Program_Error;
+ exception
+ when Constraint_Error => null;
+ end;
+end test_overflow_sum;