[patch] ipa-type-escape improvements

[patch] ipa-type-escape improvements

[Olga Golovanevsky]

This patch improve some cases of type-escape analysis.
It was due to gimple that these cases were defined as escaping.
Now, when ipa-type-escape is in tree-ssa, we can extend them to
really utilize this form.

With this patch the following two testcases work correctly,
i.e. str_t is test1 is reported contained, while in test2 it
escapes:

====================================================
#test1
#define N 1000
#include <stdlib.h>
# str_t should not escape by ipa-type-escape analysis

typedef struct
{
  int c;
  double b;
}str_t;


str_t *a_p;
int main (void)
{
  int i;

  a_p = (str_t *)malloc (N*sizeof (str_t));

  for (i=0; i < N; i++)
    {
      a_p[i].c = 5;
      a_p[i].b = 7.2;
    }

  return a_p[i-1].c;
}

====================================================
# test2
#define N 1000
#str_t should escapes by ipa-type-escape analysis

typedef struct
{
  int c;
  double b;
}str_t;

str_t a[N];

str_t * a_p;

int main (void)
{
  int i;
  void * vp;
  vp = (void *) &(a[0].c);

  a_p = (str_t *)vp;

  return a[i-1].c;
}

Formally, the following cases are extended:

1. when array element is accesses by pointer and index (test1)

2. when array element is accesses by pointer and constant
(test1, test2)

3. allow multiplication by pointers (as Jan suggested)

4. fix the support of malloc which was broken by moving from
gimple to tree-ssa (test1)

5. catch casting from pointer type as escaping (test2)

6. two small fixes I came across.

bootstraped and tested on powerpc-suse-linux.

:ADDPATCH ipa ssa:

Any comments?

Ok for mainline?

Olga


Index: tree.h
===================================================================
--- tree.h  (revision 122428)
+++ tree.h  (working copy)
@@ -4454,7 +4454,7 @@ enum operand_equal_flag
 };

 extern int operand_equal_p (tree, tree, unsigned int);
-
+extern int multiple_of_p (tree, tree, tree);
 extern tree omit_one_operand (tree, tree, tree);
 extern tree omit_two_operands (tree, tree, tree, tree);
 extern tree invert_truthvalue (tree);
Index: fold-const.c
===================================================================
--- fold-const.c  (revision 122428)
+++ fold-const.c  (working copy)
@@ -131,7 +131,6 @@ static tree fold_truthop (enum tree_code
 static tree optimize_minmax_comparison (enum tree_code, tree, tree, tree);
 static tree extract_muldiv (tree, tree, enum tree_code, tree, bool *);
 static tree extract_muldiv_1 (tree, tree, enum tree_code, tree, bool *);
-static int multiple_of_p (tree, tree, tree);
 static tree fold_binary_op_with_conditional_arg (enum tree_code, tree,
                                     tree, tree,
                                     tree, tree, int);
@@ -13066,7 +13065,7 @@ fold_build_call_array_initializer (tree
    (where the same SAVE_EXPR (J) is used in the original and the
    transformed version).  */

-static int
+int
 multiple_of_p (tree type, tree top, tree bottom)
 {
   if (operand_equal_p (top, bottom, 0))
Index: ChangeLog
===================================================================
--- ChangeLog     (revision 122428)
+++ ChangeLog     (working copy)
@@ -1,3 +1,21 @@
+
+2007-03-01  Olga Golovanevsky  <olga@il.ibm.com>
+
+     * tree.h : Add multiple_of_p declaration.
+     * fold-const.c (multiple_of_p): Make multiple_of_p public.
+     * ipa-type-escape.c (results_of_malloc): Redundant.
+     (visited_stmts): New. Visited stmt for walk_use_def_chains.
+     (cast_type): Extended with new members.
+     (check_cast): Returns cast_type.
+     (cast): New structure for data of walk_use_def_chains.
+     (is_malloc_result, is_cast_from_non_pointer_1,
+     is_cast_from_non_pointer,
+     is_array_access_through_pointer_and_index): New functions.
+     (look_for_casts): Returns cast types.
+     (check_call): Returns void.
+     (okay_pointer_operation): Use support of pointer plus index,
+     pointer plus constant and allow all multiplications.
+
 2007-03-01  Richard Sandiford  <richard@codesourcery.com>

      * Makefile.in (rtlanal.o): Depend on tree.h.
Index: ipa-type-escape.c
===================================================================
--- ipa-type-escape.c   (revision 122428)
+++ ipa-type-escape.c   (working copy)
@@ -60,13 +60,6 @@ Software Foundation, 51 Franklin Street,
    this phase has been run.  */
 static bool initialized = false;

-/* This bitmap contains the set of local vars that are the lhs of
-   calls to mallocs.  These variables, when seen on the rhs as part of
-   a cast, the cast are not marked as doing bad things to the type
-   even though they are generally of the form
-   "foo = (type_of_foo)void_temp". */
-static bitmap results_of_malloc;
-
 /* Scratch bitmap for avoiding work. */
 static bitmap been_there_done_that;
 static bitmap bitmap_tmp;
@@ -135,8 +128,16 @@ static splay_tree uid_to_subtype_map;
    scan_for_refs.  */
 static struct pointer_set_t *visited_nodes;

+/* Visited stmts by walk_use_def_chains function because it's called
+   recursively.  */
+static struct pointer_set_t *visited_stmts;
+
 static bitmap_obstack ipa_obstack;

+/* Static function from this file that are used before been defined.  */
+static unsigned int look_for_casts (tree lhs __attribute__((unused)),
tree);
+static bool is_cast_from_non_pointer (tree, tree, void *);
+
 /* Get the name of TYPE or return the string "<UNNAMED>".  */
 static char*
 get_name_of_type (tree type)
@@ -622,10 +623,15 @@ count_stars (tree* type_ptr)
 }

 enum cast_type {
-  CT_UP,
-  CT_DOWN,
-  CT_SIDEWAYS,
-  CT_USELESS
+  CT_UP = 0x1,
+  CT_DOWN = 0x2,
+  CT_SIDEWAYS = 0x4,
+  CT_USELESS = 0x8,
+  CT_FROM_P_BAD = 0x10,
+  CT_FROM_NON_P = 0x20,
+  CT_TO_NON_INTER = 0x40,
+  CT_FROM_MALLOC = 0x80,
+  CT_NO_CAST = 0x100
 };

 /* Check the cast FROM_TYPE to TO_TYPE.  This function requires that
@@ -648,17 +654,52 @@ check_cast_type (tree to_type, tree from
   return CT_SIDEWAYS;
 }

+/* This function returns nonzero if VAR is result of malloc call
+   function.  */
+static bool
+is_malloc_result (tree var)
+{
+  tree def_stmt;
+  tree rhs;
+  int flags;
+
+  if (!var)
+    return false;
+
+  if (SSA_NAME_IS_DEFAULT_DEF (var))
+    return false;
+
+  def_stmt = SSA_NAME_DEF_STMT (var);
+
+  if (TREE_CODE (def_stmt) != GIMPLE_MODIFY_STMT)
+    return false;
+
+  if (var != GIMPLE_STMT_OPERAND (def_stmt, 0))
+    return false;
+
+  rhs = GIMPLE_STMT_OPERAND (def_stmt, 1);
+
+  if (TREE_CODE (rhs) != CALL_EXPR)
+    return false;
+
+  flags = call_expr_flags (rhs);
+
+  return ((flags & ECF_MALLOC) != 0);
+
+}
+
 /* Check a cast FROM this variable, TO_TYPE.  Mark the escaping types
-   if appropriate.  */
-static void
+   if appropriate. Returns cast_type as detected.  */
+static enum cast_type
 check_cast (tree to_type, tree from)
 {
   tree from_type = get_canon_type (TREE_TYPE (from), false, false);
   bool to_interesting_type, from_interesting_type;
+  enum cast_type cast = CT_NO_CAST;

   to_type = get_canon_type (to_type, false, false);
   if (!from_type || !to_type || from_type == to_type)
-    return;
+    return cast;

   to_interesting_type =
     ipa_type_escape_star_count_of_interesting_type (to_type) >= 0;
@@ -674,7 +715,8 @@ check_cast (tree to_type, tree from)
         both sides get marked as escaping.  Downcasts are not
         interesting here because if type is marked as escaping, all
         of its subtypes escape.  */
-     switch (check_cast_type (to_type, from_type))
+     cast = check_cast_type (to_type, from_type);
+     switch (cast)
        {
        case CT_UP:
        case CT_USELESS:
@@ -685,17 +727,293 @@ check_cast (tree to_type, tree from)
          mark_type (to_type, FULL_ESCAPE);
          mark_type (from_type, FULL_ESCAPE);
          break;
+
+       default:
+         break;
        }
       }
     else
       {
-     /* If this is a cast from the local that is a result from a
-        call to malloc, do not mark the cast as bad.  */
-     if (DECL_P (from) && !bitmap_bit_p (results_of_malloc, DECL_UID
(from)))
-       mark_type (to_type, FULL_ESCAPE);
+     /* This code excludes two cases from marking as escaped:
+
+     1. if this is a cast of index of array of structures/unions
+     that happens before accessing array element, we should not
+     mark it as escaped.
+     2. if this is a cast from the local that is a result from a
+        call to malloc, do not mark the cast as bad.
+
+     */
+
+     if (POINTER_TYPE_P (to_type) && !POINTER_TYPE_P (from_type))
+       cast = CT_FROM_NON_P;
+     else if (TREE_CODE (from) == SSA_NAME
+            && is_malloc_result (from))
+       cast = CT_FROM_MALLOC;
+     else
+       {
+         cast = CT_FROM_P_BAD;
+         mark_type (to_type, FULL_ESCAPE);
+       }
       }
   else if (from_interesting_type)
-    mark_type (from_type, FULL_ESCAPE);
+    {
+      mark_type (from_type, FULL_ESCAPE);
+      cast = CT_TO_NON_INTER;
+    }
+
+  return cast;
+}
+
+typedef struct cast
+{
+  int type;
+  tree stmt;
+}cast_t;
+
+/* This function data->type is set to be:
+
+  0      - if there is no cast
+  number - the number of casts from non-pointer type
+  -1     - if there is a cast that makes the type to escape
+
+  If number is returned, then data->stmt will contain the
+  last casting stmt met in traversing.  */
+
+static tree
+is_cast_from_non_pointer_1 (tree *tp, int *walk_subtrees, void *data)
+{
+  tree def_stmt = *tp;
+
+
+  if (pointer_set_insert (visited_stmts, def_stmt))
+    {
+      *walk_subtrees = 0;
+      return NULL;
+    }
+
+  switch (TREE_CODE (def_stmt))
+    {
+    case GIMPLE_MODIFY_STMT:
+      {
+     use_operand_p use_p;
+     ssa_op_iter iter;
+     tree lhs = GIMPLE_STMT_OPERAND (def_stmt, 0);
+     tree rhs = GIMPLE_STMT_OPERAND (def_stmt, 1);
+
+        unsigned int cast = look_for_casts (lhs, rhs);
+     /* Check that only one cast happened, and it's of
+        non-pointer type.  */
+     if ((cast & CT_FROM_NON_P) == (CT_FROM_NON_P)
+         && (cast & ~(CT_FROM_NON_P)) == 0)
+       {
+         ((cast_t *)data)->stmt = def_stmt;
+         ((cast_t *)data)->type++;
+
+         FOR_EACH_SSA_USE_OPERAND (use_p, def_stmt, iter, SSA_OP_ALL_USES)
+           {
+           walk_use_def_chains (USE_FROM_PTR (use_p),
is_cast_from_non_pointer,
+                            data, false);
+           if (((cast_t*)data)->type == -1)
+             return def_stmt;
+
+           }
+
+       }
+
+     /* Check that there is no cast, or cast is not harmful. */
+     else if ((cast & CT_NO_CAST) == (CT_NO_CAST)
+            || (cast & CT_DOWN) == (CT_DOWN)
+            || (cast & CT_UP) == (CT_UP)
+            || (cast & CT_USELESS) == (CT_USELESS)
+            || (cast & CT_FROM_MALLOC) == (CT_FROM_MALLOC))
+       {
+         FOR_EACH_SSA_USE_OPERAND (use_p, def_stmt, iter, SSA_OP_ALL_USES)
+           {
+           walk_use_def_chains (USE_FROM_PTR (use_p),
is_cast_from_non_pointer,
+                            data, false);
+           if (((cast_t*)data)->type == -1)
+             return def_stmt;
+           }
+
+       }
+     /* The cast is harmful.  */
+     else
+       {
+         ((cast_t *)data)->type = -1;
+         return def_stmt;
+       }
+
+     *walk_subtrees = 0;
+      }
+      break;
+
+    default:
+      {
+     *walk_subtrees = 0;
+     break;
+      }
+    }
+
+  return NULL;
+}
+
+/* This function is a callback for walk_use_def_chains function called
+   from is_array_access_through_pointer_and_index.  */
+
+static bool
+is_cast_from_non_pointer (tree var, tree def_stmt, void *data)
+{
+
+  if (!def_stmt || !var)
+    return false;
+
+  if (TREE_CODE (def_stmt) == PHI_NODE)
+    return false;
+
+  if (SSA_NAME_IS_DEFAULT_DEF (var))
+      return false;
+
+  walk_tree (&def_stmt, is_cast_from_non_pointer_1, data, NULL);
+  if (((cast_t*)data)->type == -1)
+    return true;
+
+  return false;
+}
+
+/* When array element a_p[i] is accessed through the pointer a_p
+   and index i, it's translated into the following sequence
+   in gimple:
+
+  i.1_5 = (unsigned int) i_1;
+  D.1605_6 = i.1_5 * 16;
+  D.1606_7 = (struct str_t *) D.1605_6;
+  a_p.2_8 = a_p;
+  D.1608_9 = D.1606_7 + a_p.2_8;
+
+  OP0 and OP1 are of the same pointer types and stand for
+  D.1606_7 and a_p.2_8 or vise versa.
+
+  This function checks that:
+
+  1. one of OP0 and OP1 has passed only one cast from
+  non-pointer type (D.1606_7).
+
+  2. one of OP0 and OP1 which has passed the cast from
+  non-pointer type (D.1606_7), is actually generated by multiplication of
+  index by size of type to which OP0 and OP1 are point to
+  (in this case D.1605_6 = i.1_5 * 16; ).
+
+  3. an address of def of the var to which was made cast (D.1605_6)
+  was not taken.(How can it happen?)
+
+  The following items are checked implicitly by the end of algorithm:
+
+  4. one of OP0 and OP1 (a_p.2_8) have never been cast
+  (because if it was cast to pointer type, its type, that is also
+  the type of OP0 and OP1, will be marked as escaped during
+  analysis of casting stmt (when check_cast() is called
+  from scan_for_refs for this stmt)).
+
+  5. defs of OP0 and OP1 are not passed into externally visible function
+  (because if they are passed then their type, that is also the type of
OP0
+  and OP1, will be marked and escaped during check_call function called
from
+  scan_for_refs with call stmt).
+
+  In total, 1-5 guaranty that it's an access to array by pointer and
index.
+
+*/
+
+
+static bool
+is_array_access_through_pointer_and_index (tree op0, tree op1)
+{
+  tree base, offset, offset_cast_stmt;
+  tree before_cast, before_cast_def_stmt;
+  cast_t op0_cast, op1_cast;
+
+  /* Check 1.  */
+
+  /* Init data for walk_use_def_chains function.  */
+  op0_cast.type = op1_cast.type = 0;
+  op0_cast.stmt = op1_cast.stmt = NULL;
+
+  visited_stmts = pointer_set_create ();
+  walk_use_def_chains (op0, is_cast_from_non_pointer,(void *)(&op0_cast),
false);
+  pointer_set_destroy (visited_stmts);
+
+  visited_stmts = pointer_set_create ();
+  walk_use_def_chains (op1, is_cast_from_non_pointer,(void *)(&op1_cast),
false);
+  pointer_set_destroy (visited_stmts);
+
+  if (dump_file)
+    fprintf (dump_file, "\nop0_cast = %d, op1_cast = %d", op0_cast.type,
op1_cast.type);
+
+  if (op0_cast.type == 1 && op1_cast.type == 0)
+    {
+      base = op1;
+      offset = op0;
+      offset_cast_stmt = op0_cast.stmt;
+    }
+  else if (op0_cast.type == 0 && op1_cast.type == 1)
+    {
+      base = op0;
+      offset = op1;
+      offset_cast_stmt = op1_cast.stmt;
+    }
+  else
+    return false;
+
+  /* Check 2.
+     offset_cast_stmt is of the form:
+     D.1606_7 = (struct str_t *) D.1605_6;  */
+
+  before_cast = SINGLE_SSA_TREE_OPERAND (offset_cast_stmt, SSA_OP_USE);
+  if (!before_cast)
+    return false;
+
+  if (SSA_NAME_IS_DEFAULT_DEF(before_cast))
+    return false;
+
+  before_cast_def_stmt = SSA_NAME_DEF_STMT (before_cast);
+  if (!before_cast_def_stmt)
+    return false;
+
+  /* before_cast_def_stmt should be of the form:
+   D.1605_6 = i.1_5 * 16; */
+
+  if (TREE_CODE (before_cast_def_stmt) == GIMPLE_MODIFY_STMT)
+    {
+      tree lhs = GIMPLE_STMT_OPERAND (before_cast_def_stmt,0);
+      tree rhs = GIMPLE_STMT_OPERAND (before_cast_def_stmt,1);
+
+      /* We expect temporary here.  */
+      if (!is_gimple_reg (lhs))
+     return false;
+
+      if (TREE_CODE (rhs) == MULT_EXPR)
+     {
+       tree arg0 = TREE_OPERAND (rhs, 0);
+       tree arg1 = TREE_OPERAND (rhs, 1);
+       tree unit_size =
+         TYPE_SIZE_UNIT (TREE_TYPE (TYPE_MAIN_VARIANT (TREE_TYPE (op0))));
+
+       if (!(CONSTANT_CLASS_P (arg0)
+           && simple_cst_equal (arg0,unit_size))
+           && !(CONSTANT_CLASS_P (arg1)
+           && simple_cst_equal (arg1,unit_size)))
+         return false;
+     }
+      else
+     return false;
+    }
+  else
+    return false;
+
+  /* Check 3.
+     check that address of D.1605_6 was not taken.
+     FIXME: if D.1605_6 is gimple reg than it cannot be addressable.  */
+
+  return true;
 }

 /* Register the parameter and return types of function FN.  The type
@@ -808,9 +1126,9 @@ check_tree (tree t)
   if ((TREE_CODE (t) == EXC_PTR_EXPR) || (TREE_CODE (t) == FILTER_EXPR))
     return;

-  while (TREE_CODE (t) == REALPART_EXPR
-      || TREE_CODE (t) == IMAGPART_EXPR
-      || handled_component_p (t))
+  /* We want to catch here also REALPART_EXPR and IMAGEPART_EXPR,
+     but they already included in handled_component_p.  */
+  while (handled_component_p (t))
     {
       if (TREE_CODE (t) == ARRAY_REF)
      check_operand (TREE_OPERAND (t, 1));
@@ -873,7 +1191,7 @@ mark_interesting_addressof (tree to_type
                   to_uid,
                   (splay_tree_value)type_map);
     }
-  bitmap_set_bit (type_map, TYPE_UID (to_type));
+  bitmap_set_bit (type_map, TYPE_UID (from_type));
 }

 /* Scan tree T to see if there are any addresses taken in within T.  */
@@ -912,29 +1230,41 @@ look_for_address_of (tree t)
 /* Scan tree T to see if there are any casts within it.
    LHS Is the LHS of the expression involving the cast.  */

-static void
+static unsigned int
 look_for_casts (tree lhs __attribute__((unused)), tree t)
 {
+  unsigned int cast = 0;
+
+
   if (is_gimple_cast (t) || TREE_CODE (t) == VIEW_CONVERT_EXPR)
     {
       tree castfromvar = TREE_OPERAND (t, 0);
-      check_cast (TREE_TYPE (t), castfromvar);
+      cast = cast | check_cast (TREE_TYPE (t), castfromvar);
     }
-  else
-    while (handled_component_p (t))
-      {
-     t = TREE_OPERAND (t, 0);
-     if (TREE_CODE (t) == VIEW_CONVERT_EXPR)
-       {
-         /* This may be some part of a component ref.
-            IE it may be a.b.VIEW_CONVERT_EXPR<weird_type>(c).d, AFAIK.
-            castfromref will give you a.b.c, not a. */
-         tree castfromref = TREE_OPERAND (t, 0);
-         check_cast (TREE_TYPE (t), castfromref);
-       }
-     else if (TREE_CODE (t) == COMPONENT_REF)
-       get_canon_type (TREE_TYPE (TREE_OPERAND (t, 1)), false, false);
-      }
+  else if (TREE_CODE (t) == COMPONENT_REF
+        || TREE_CODE (t) == INDIRECT_REF
+        || TREE_CODE (t) == BIT_FIELD_REF)
+    {
+      tree base = get_base_address (t);
+      while (t != base)
+     {
+       t = TREE_OPERAND (t, 0);
+       if (TREE_CODE (t) == VIEW_CONVERT_EXPR)
+         {
+           /* This may be some part of a component ref.
+            IE it may be a.b.VIEW_CONVERT_EXPR<weird_type>(c).d, AFAIK.
+            castfromref will give you a.b.c, not a. */
+           tree castfromref = TREE_OPERAND (t, 0);
+           cast = cast | check_cast (TREE_TYPE (t), castfromref);
+         }
+       else if (TREE_CODE (t) == COMPONENT_REF)
+         get_canon_type (TREE_TYPE (TREE_OPERAND (t, 1)), false, false);
+     }
+    }
+
+  if (!cast)
+    cast = CT_NO_CAST;
+  return cast;
 }

 /* Check to see if T is a read or address of operation on a static var
@@ -1007,10 +1337,9 @@ get_asm_expr_operands (tree stmt)
    this is either an indirect call, a call outside the compilation
    unit.  */

-static bool
+static void
 check_call (tree call_expr)
 {
-  int flags = call_expr_flags(call_expr);
   tree operand;
   tree callee_t = get_callee_fndecl (call_expr);
   struct cgraph_node* callee;
@@ -1118,7 +1447,6 @@ check_call (tree call_expr)
        mark_interesting_type (type, EXPOSED_PARAMETER);
      }
     }
-  return (flags & ECF_MALLOC);
 }

 /* CODE is the operation on OP0 and OP1.  OP0 is the operand that we
@@ -1128,18 +1456,40 @@ okay_pointer_operation (enum tree_code c
 {
   tree op0type = TYPE_MAIN_VARIANT (TREE_TYPE (op0));
   tree op1type = TYPE_MAIN_VARIANT (TREE_TYPE (op1));
-  if (POINTER_TYPE_P (op1type))
-    return false;
+
   switch (code)
     {
     case MULT_EXPR:
-    case PLUS_EXPR:
+      /* Multiplication does not change alignment.  */
+      return true;
+      break;
     case MINUS_EXPR:
-      /* TODO: Handle multiples of op0 size as well */
-      if (operand_equal_p (size_in_bytes (op0type), op1, 0))
-     return true;
-      /* fallthrough */
+    case PLUS_EXPR:
+      {
+     if (POINTER_TYPE_P (op1type)
+         && TREE_CODE (op0) == SSA_NAME
+         && TREE_CODE (op1) == SSA_NAME
+         && is_array_access_through_pointer_and_index (op0, op1))
+       return true;
+     else
+       {
+         tree size_of_op0_points_to = TYPE_SIZE_UNIT (TREE_TYPE
(op0type));
+
+         if (CONSTANT_CLASS_P (op1)
+           && size_of_op0_points_to
+           && multiple_of_p (TREE_TYPE (size_of_op0_points_to),
+                         op1, size_of_op0_points_to))
+           return true;

+         if (CONSTANT_CLASS_P (op0)
+           && size_of_op0_points_to
+           && multiple_of_p (TREE_TYPE (size_of_op0_points_to),
+                         op0, size_of_op0_points_to))
+           return true;
+
+       }
+      }
+      break;
     default:
       return false;
     }
@@ -1256,12 +1606,7 @@ scan_for_refs (tree *tp, int *walk_subtr
            /* If this is a call to malloc, squirrel away the
               result so we do mark the resulting cast as being
               bad.  */
-           if (check_call (rhs))
-             {
-               if (TREE_CODE (lhs) == SSA_NAME)
-                 lhs = SSA_NAME_VAR (lhs);
-               bitmap_set_bit (results_of_malloc, DECL_UID (lhs));
-             }
+           check_call (rhs);
            break;
            default:
            break;
@@ -1307,7 +1652,6 @@ ipa_init (void)
   global_types_exposed_parameter = BITMAP_ALLOC (&ipa_obstack);
   global_types_full_escape = BITMAP_ALLOC (&ipa_obstack);
   global_types_seen = BITMAP_ALLOC (&ipa_obstack);
-  results_of_malloc = BITMAP_ALLOC (&ipa_obstack);

   uid_to_canon_type = splay_tree_new (splay_tree_compare_ints, 0, 0);
   all_canon_types = splay_tree_new (compare_type_brand, 0, 0);
@@ -1810,7 +2154,6 @@ type_escape_execute (void)
   BITMAP_FREE (global_types_exposed_parameter);
   BITMAP_FREE (been_there_done_that);
   BITMAP_FREE (bitmap_tmp);
-  BITMAP_FREE (results_of_malloc);
   return 0;
 }

Re: [patch] ipa-type-escape improvements

[Daniel Berlin]

It looks good to me, but i have no idea who can actually approve it
other than a global write person since we have no IPA pass
maintainers.


On 3/1/07, Olga Golovanevsky <OLGA@il.ibm.com> wrote:
>
> This patch improve some cases of type-escape analysis.
> It was due to gimple that these cases were defined as escaping.
> Now, when ipa-type-escape is in tree-ssa, we can extend them to
> really utilize this form.
>

Re: [patch] ipa-type-escape improvements

[Diego Novillo]

Olga Golovanevsky wrote on 03/01/07 09:57:

> +2007-03-01  Olga Golovanevsky  <olga@il.ibm.com>
> +
> +     * tree.h : Add multiple_of_p declaration.
> +     * fold-const.c (multiple_of_p): Make multiple_of_p public.
> +     * ipa-type-escape.c (results_of_malloc): Redundant.
> +     (visited_stmts): New. Visited stmt for walk_use_def_chains.
> +     (cast_type): Extended with new members.
> +     (check_cast): Returns cast_type.
> +     (cast): New structure for data of walk_use_def_chains.
> +     (is_malloc_result, is_cast_from_non_pointer_1,
> +     is_cast_from_non_pointer,
> +     is_array_access_through_pointer_and_index): New functions.
> +     (look_for_casts): Returns cast types.
> +     (check_call): Returns void.
> +     (okay_pointer_operation): Use support of pointer plus index,
> +     pointer plus constant and allow all multiplications.
> +

OK with a couple minor changes.

> +/* Static function from this file that are used before been defined.  */

s/been/being/  (I think, I'm not actually sure in this case).

> +static unsigned int look_for_casts (tree lhs __attribute__((unused)),
> tree);

No.  ATTRIBUTE_UNUSUED.

> +/* This function returns nonzero if VAR is result of malloc call
> +   function.  */
> +static bool
> +is_malloc_result (tree var)

Blank line after comment.

> +  if (TREE_CODE (def_stmt) != GIMPLE_MODIFY_STMT)
> +    return false;
> +
> +  if (var != GIMPLE_STMT_OPERAND (def_stmt, 0))
> +    return false;
> +
> +  rhs = GIMPLE_STMT_OPERAND (def_stmt, 1);
> +
> +  if (TREE_CODE (rhs) != CALL_EXPR)
> +    return false;
> +

Better use get_call_expr_in.

>  /* Check a cast FROM this variable, TO_TYPE.  Mark the escaping types
> -   if appropriate.  */
> -static void
> +   if appropriate. Returns cast_type as detected.  */
> +static enum cast_type
>  check_cast (tree to_type, tree from)
>  {

Spacing after comment.

> +    case GIMPLE_MODIFY_STMT:
> +      {
> +     use_operand_p use_p;
> +     ssa_op_iter iter;
> +     tree lhs = GIMPLE_STMT_OPERAND (def_stmt, 0);
> +     tree rhs = GIMPLE_STMT_OPERAND (def_stmt, 1);
> +
> +        unsigned int cast = look_for_casts (lhs, rhs);

Watch indentation.


:REVIEWMAIL:

Re: [patch] ipa-type-escape improvements

[Kenneth Zadeck]

Diego Novillo wrote:
> Olga Golovanevsky wrote on 03/01/07 09:57:
>
>> +2007-03-01  Olga Golovanevsky  <olga@il.ibm.com>
>> +
>> +     * tree.h : Add multiple_of_p declaration.
>> +     * fold-const.c (multiple_of_p): Make multiple_of_p public.
>> +     * ipa-type-escape.c (results_of_malloc): Redundant.
>> +     (visited_stmts): New. Visited stmt for walk_use_def_chains.
>> +     (cast_type): Extended with new members.
>> +     (check_cast): Returns cast_type.
>> +     (cast): New structure for data of walk_use_def_chains.
>> +     (is_malloc_result, is_cast_from_non_pointer_1,
>> +     is_cast_from_non_pointer,
>> +     is_array_access_through_pointer_and_index): New functions.
>> +     (look_for_casts): Returns cast types.
>> +     (check_call): Returns void.
>> +     (okay_pointer_operation): Use support of pointer plus index,
>> +     pointer plus constant and allow all multiplications.
>> +
>
> OK with a couple minor changes.
>
>> +/* Static function from this file that are used before been
>> defined.  */
>
> s/been/being/  (I think, I'm not actually sure in this case).
>
Not that I am that good at being the language police but diego is
correct but in addition

s/function/functions/


>> +static unsigned int look_for_casts (tree lhs __attribute__((unused)),
>> tree);
>
> No.  ATTRIBUTE_UNUSUED.
>
>> +/* This function returns nonzero if VAR is result of malloc call
>> +   function.  */
>> +static bool
>> +is_malloc_result (tree var)
>
> Blank line after comment.
>
>> +  if (TREE_CODE (def_stmt) != GIMPLE_MODIFY_STMT)
>> +    return false;
>> +
>> +  if (var != GIMPLE_STMT_OPERAND (def_stmt, 0))
>> +    return false;
>> +
>> +  rhs = GIMPLE_STMT_OPERAND (def_stmt, 1);
>> +
>> +  if (TREE_CODE (rhs) != CALL_EXPR)
>> +    return false;
>> +
>
> Better use get_call_expr_in.
>
>>  /* Check a cast FROM this variable, TO_TYPE.  Mark the escaping types
>> -   if appropriate.  */
>> -static void
>> +   if appropriate. Returns cast_type as detected.  */
>> +static enum cast_type
>>  check_cast (tree to_type, tree from)
>>  {
>
> Spacing after comment.
>
>> +    case GIMPLE_MODIFY_STMT:
>> +      {
>> +     use_operand_p use_p;
>> +     ssa_op_iter iter;
>> +     tree lhs = GIMPLE_STMT_OPERAND (def_stmt, 0);
>> +     tree rhs = GIMPLE_STMT_OPERAND (def_stmt, 1);
>> +
>> +        unsigned int cast = look_for_casts (lhs, rhs);
>
> Watch indentation.
>
>
> :REVIEWMAIL:

Re: [patch] ipa-type-escape improvements

[Olga Golovanevsky]

Kenneth Zadeck <zadeck@naturalbridge.com> wrote on 02/03/2007 02:08:25:

> Diego Novillo wrote:
> > Olga Golovanevsky wrote on 03/01/07 09:57:
> >
> >> +2007-03-01  Olga Golovanevsky  <olga@il.ibm.com>
> >> +
> >> +     * tree.h : Add multiple_of_p declaration.
> >> +     * fold-const.c (multiple_of_p): Make multiple_of_p public.
> >> +     * ipa-type-escape.c (results_of_malloc): Redundant.
> >> +     (visited_stmts): New. Visited stmt for walk_use_def_chains.
> >> +     (cast_type): Extended with new members.
> >> +     (check_cast): Returns cast_type.
> >> +     (cast): New structure for data of walk_use_def_chains.
> >> +     (is_malloc_result, is_cast_from_non_pointer_1,
> >> +     is_cast_from_non_pointer,
> >> +     is_array_access_through_pointer_and_index): New functions.
> >> +     (look_for_casts): Returns cast types.
> >> +     (check_call): Returns void.
> >> +     (okay_pointer_operation): Use support of pointer plus index,
> >> +     pointer plus constant and allow all multiplications.
> >> +
> >
> > OK with a couple minor changes.
> >

Danny, Diego, Kenny,

Thank you for reviewing. I'll make the changes you suggested.

Olga

Re: [patch] ipa-type-escape improvements

[Eric Botcazou]

[-- Attachment #1: Type: text/plain, Size: 1394 bytes --]

> +2007-03-01  Olga Golovanevsky  <olga@il.ibm.com>
> +
> +     * tree.h : Add multiple_of_p declaration.
> +     * fold-const.c (multiple_of_p): Make multiple_of_p public.
> +     * ipa-type-escape.c (results_of_malloc): Redundant.
> +     (visited_stmts): New. Visited stmt for walk_use_def_chains.
> +     (cast_type): Extended with new members.
> +     (check_cast): Returns cast_type.
> +     (cast): New structure for data of walk_use_def_chains.
> +     (is_malloc_result, is_cast_from_non_pointer_1,
> +     is_cast_from_non_pointer,
> +     is_array_access_through_pointer_and_index): New functions.
> +     (look_for_casts): Returns cast types.
> +     (check_call): Returns void.
> +     (okay_pointer_operation): Use support of pointer plus index,
> +     pointer plus constant and allow all multiplications.

This breaks Ada on x86 with tree checking enabled.  To reproduce, compile the 
attached reproducer in the objdir directory with:

gcc/xgcc -Bgcc -S -O2 -gnatpg a-numaux.adb -Igcc/ada/rts

+===========================GNAT BUG DETECTED==============================+
| 4.3.0 20070313 (experimental) (i586-suse-linux-gnu) GCC error:           |
| tree check: expected class 'expression', have 'constant' (real_cst)      |
|     in look_for_casts, at ipa-type-escape.c:1249                         |
| Error detected at a-numaux.adb:37:1                   

-- 
Eric Botcazou

[-- Attachment #2: a-numaux.ads --]
[-- Type: text/x-adasrc, Size: 182 bytes --]

package Ada.Numerics.Aux is

   type Double is new Long_Long_Float;

   function Exp (X : Double) return Double;

   function Tanh (X : Double) return Double;

end Ada.Numerics.Aux;

[-- Attachment #3: a-numaux.adb --]
[-- Type: text/x-adasrc, Size: 1169 bytes --]

with System.Machine_Code; use System.Machine_Code;

package body Ada.Numerics.Aux is

   NL : constant String := ASCII.LF & ASCII.HT;

   function Exp (X : Double) return Double is
      Result : Double;
   begin
      Asm (Template =>
         "fldl2e               " & NL
       & "fmulp   %%st, %%st(1)" & NL -- X * log2 (E)
       & "fld     %%st(0)      " & NL
       & "frndint              " & NL -- Integer (X * Log2 (E))
       & "fsubr   %%st, %%st(1)" & NL -- Fraction (X * Log2 (E))
       & "fxch                 " & NL
       & "f2xm1                " & NL -- 2**(...) - 1
       & "fld1                 " & NL
       & "faddp   %%st, %%st(1)" & NL -- 2**(Fraction (X * Log2 (E)))
       & "fscale               " & NL -- E ** X
       & "fstp    %%st(1)      ",
         Outputs  => Double'Asm_Output ("=t", Result),
         Inputs   => Double'Asm_Input  ("0", X));
      return Result;
   end Exp;

   function Tanh (X : Double) return Double is
   begin

      if abs X > 23.0 then
         return Double'Copy_Sign (1.0, X);
      end if;

      return 1.0 / (1.0 + Exp (-(2.0 * X))) - 1.0 / (1.0 + Exp (2.0 * X));
   end Tanh;

end Ada.Numerics.Aux;

Re: [patch] ipa-type-escape improvements

[Daniel Berlin]

On 3/13/07, Eric Botcazou <ebotcazou@adacore.com> wrote:
> > +2007-03-01  Olga Golovanevsky  <olga@il.ibm.com>
> > +
> > +     * tree.h : Add multiple_of_p declaration.
> > +     * fold-const.c (multiple_of_p): Make multiple_of_p public.
> > +     * ipa-type-escape.c (results_of_malloc): Redundant.
> > +     (visited_stmts): New. Visited stmt for walk_use_def_chains.
> > +     (cast_type): Extended with new members.
> > +     (check_cast): Returns cast_type.
> > +     (cast): New structure for data of walk_use_def_chains.
> > +     (is_malloc_result, is_cast_from_non_pointer_1,
> > +     is_cast_from_non_pointer,
> > +     is_array_access_through_pointer_and_index): New functions.
> > +     (look_for_casts): Returns cast types.
> > +     (check_call): Returns void.
> > +     (okay_pointer_operation): Use support of pointer plus index,
> > +     pointer plus constant and allow all multiplications.
>
> This breaks Ada on x86 with tree checking enabled.  To reproduce, compile the
> attached reproducer in the objdir directory with:

So you have a component_ref or an indirect_ref of a real_cst?
ugh

Re: [patch] ipa-type-escape improvements

[Eric Botcazou]

> So you have a component_ref or an indirect_ref of a real_cst?

Indirectly of course, here is the tree:

 <component_ref 0x5570f488
    type <real_type 0x55754340 long_long_float sizes-gimplified visited XF
        size <integer_cst 0x55709678 constant invariant visited 96>
        unit size <integer_cst 0x55709690 constant invariant visited 12>
        align 32 symtab 0 alias set 7 canonical type 0x55754340 precision 80 
min <real_cst 0x55709c90 
-1.1897314953572317650212638530309702051690633223e+4932> max <real_cst 
0x55709f60 1.1897314953572317650212638530309702051690633223e+4932>>

    arg 0 <view_convert_expr 0x55766444
        type <record_type 0x557543a8 long_long_float___PAD sizes-gimplified 
visited type_5 BLK
            size <integer_cst 0x557094f8 constant invariant visited 128>
            unit size <integer_cst 0x55709510 constant invariant visited 16>
            user align 64 symtab 0 alias set -1 canonical type 0x557543a8 
fields <field_decl 0x55756000 F> Ada size <integer_cst 0x55709678 96>
            chain <type_decl 0x55754478 D.552>>
        invariant
        arg 0 <real_cst 0x55765768 type <real_type 0x5575ef70 
ada__numerics__aux__TdoubleB>
            constant invariant 1.0e+0>>
    arg 1 <field_decl 0x55756000 F type <real_type 0x55754340 long_long_float>
        decl_3 decl_5 XF file a-numaux.adb line 0 size <integer_cst 0x55709678 
96> unit size <integer_cst 0x55709690 12>
        align 32 offset_align 128
        offset <integer_cst 0x55709600 constant invariant visited 0>
        bit offset <integer_cst 0x55709618 constant invariant visited 0> 
context <record_type 0x557543a8 long_long_float___PAD>>>

-- 
Eric Botcazou

Re: [patch] ipa-type-escape improvements

[Andrew Pinski]

On 3/13/07, Daniel Berlin <dberlin@dberlin.org> wrote:
> > This breaks Ada on x86 with tree checking enabled.  To reproduce, compile the
> > attached reproducer in the objdir directory with:
>
> So you have a component_ref or an indirect_ref of a real_cst?

Even though the code in look_for_casts has special code for
VIEW_CONVERT_EXPR, it can never be invoked as it is always an
handled_component_p so get_base_address will return the constant.  The
old code for look_for_casts actually looks at each element seperately.

-- Pinski

Re: [patch] ipa-type-escape improvements

[Olga Golovanevsky]

Eric Botcazou <ebotcazou@adacore.com> wrote on 14/03/2007 01:31:18:

> > +2007-03-01  Olga Golovanevsky  <olga@il.ibm.com>
> > +
> > +     * tree.h : Add multiple_of_p declaration.
> > +     * fold-const.c (multiple_of_p): Make multiple_of_p public.
> > +     * ipa-type-escape.c (results_of_malloc): Redundant.
> > +     (visited_stmts): New. Visited stmt for walk_use_def_chains.
> > +     (cast_type): Extended with new members.
> > +     (check_cast): Returns cast_type.
> > +     (cast): New structure for data of walk_use_def_chains.
> > +     (is_malloc_result, is_cast_from_non_pointer_1,
> > +     is_cast_from_non_pointer,
> > +     is_array_access_through_pointer_and_index): New functions.
> > +     (look_for_casts): Returns cast types.
> > +     (check_call): Returns void.
> > +     (okay_pointer_operation): Use support of pointer plus index,
> > +     pointer plus constant and allow all multiplications.
>
> This breaks Ada on x86 with tree checking enabled.  To reproduce, compile
the
> attached reproducer in the objdir directory with:
>
> gcc/xgcc -Bgcc -S -O2 -gnatpg a-numaux.adb -Igcc/ada/rts
>
> +===========================GNAT BUG
DETECTED==============================+
> | 4.3.0 20070313 (experimental) (i586-suse-linux-gnu) GCC error:
|
> | tree check: expected class 'expression', have 'constant' (real_cst)
|
> |     in look_for_casts, at ipa-type-escape.c:1249
|
> | Error detected at a-numaux.adb:37:1
>

Looking into this problem.

Sorry, I have checked for c, c++ on powerpc and x86, but did not check for
Ada.

Olga

> --
> Eric Botcazou

Re: [patch] ipa-type-escape improvements

[Olga Golovanevsky]

"Andrew Pinski" <pinskia@gmail.com> wrote on 14/03/2007 09:10:03:

> On 3/13/07, Daniel Berlin <dberlin@dberlin.org> wrote:
> > > This breaks Ada on x86 with tree checking enabled.  To
> reproduce, compile the
> > > attached reproducer in the objdir directory with:
> >
> > So you have a component_ref or an indirect_ref of a real_cst?
>
> Even though the code in look_for_casts has special code for
> VIEW_CONVERT_EXPR, it can never be invoked as it is always an
> handled_component_p so get_base_address will return the constant.  The
> old code for look_for_casts actually looks at each element seperately.

right. I reverted the code to use

while (handled_component_p (t))

with this change ada test a-numaux.adb has passed, also as my tests
(test1 and test2).

Testing the patch:

Index: ipa-type-escape.c
===================================================================
--- ipa-type-escape.c   (revision 122835)
+++ ipa-type-escape.c   (working copy)
@@ -1239,26 +1239,21 @@ look_for_casts (tree lhs ATTRIBUTE_UNUSE
       tree castfromvar = TREE_OPERAND (t, 0);
       cast = cast | check_cast (TREE_TYPE (t), castfromvar);
     }
-  else if (TREE_CODE (t) == COMPONENT_REF
-        || TREE_CODE (t) == INDIRECT_REF
-        || TREE_CODE (t) == BIT_FIELD_REF)
-    {
-      tree base = get_base_address (t);
-      while (t != base)
-     {
-       t = TREE_OPERAND (t, 0);
-       if (TREE_CODE (t) == VIEW_CONVERT_EXPR)
-         {
-           /* This may be some part of a component ref.
-            IE it may be a.b.VIEW_CONVERT_EXPR<weird_type>(c).d, AFAIK.
-            castfromref will give you a.b.c, not a. */
-           tree castfromref = TREE_OPERAND (t, 0);
-           cast = cast | check_cast (TREE_TYPE (t), castfromref);
-         }
-       else if (TREE_CODE (t) == COMPONENT_REF)
-         get_canon_type (TREE_TYPE (TREE_OPERAND (t, 1)), false, false);
-     }
-    }
+  else
+    while (handled_component_p (t))
+      {
+       t = TREE_OPERAND (t, 0);
+       if (TREE_CODE (t) == VIEW_CONVERT_EXPR)
+         {
+           /* This may be some part of a component ref.
+              IE it may be a.b.VIEW_CONVERT_EXPR<weird_type>(c).d, AFAIK.
+              castfromref will give you a.b.c, not a. */
+           tree castfromref = TREE_OPERAND (t, 0);
+           cast = cast | check_cast (TREE_TYPE (t), castfromref);
+         }
+       else if (TREE_CODE (t) == COMPONENT_REF)
+         get_canon_type (TREE_TYPE (TREE_OPERAND (t, 1)), false, false);
+      }

   if (!cast)
     cast = CT_NO_CAST;

>
> -- Pinski

Re: [patch] ipa-type-escape improvements

[Eric Botcazou]

> right. I reverted the code to use
>
> while (handled_component_p (t))
>
> with this change ada test a-numaux.adb has passed, also as my tests
> (test1 and test2).
>
> Testing the patch:
>
> Index: ipa-type-escape.c
> ===================================================================
> --- ipa-type-escape.c   (revision 122835)
> +++ ipa-type-escape.c   (working copy)

Did it successfully pass the testing?  If so, please install it.

-- 
Eric Botcazou

Re: [patch] ipa-type-escape improvements

[Olga Golovanevsky]

Eric Botcazou <ebotcazou@adacore.com> wrote on 16/03/2007 08:12:53:

> > right. I reverted the code to use
> >
> > while (handled_component_p (t))
> >
> > with this change ada test a-numaux.adb has passed, also as my tests
> > (test1 and test2).
> >
> > Testing the patch:
> >
> > Index: ipa-type-escape.c
> > ===================================================================
> > --- ipa-type-escape.c   (revision 122835)
> > +++ ipa-type-escape.c   (working copy)
>
> Did it successfully pass the testing?  If so, please install it.

Now it does. committed.

Olga

>
> --
> Eric Botcazou

Re: [patch] ipa-type-escape improvements

[Eric Botcazou]

> Now it does. committed.

I confirm that the Ada compiler is alive again on x86.  Thanks!

-- 
Eric Botcazou