[PATCH] Avoid spending exponential time in contain_placeholder_p()

[Geert Bosch <bosch at adacore dot com>]

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;