gcc/tree-vn.c

   1 /* Value Numbering routines for tree expressions.
   2    Copyright (C) 2001, 2002, 2003, 2004, 2005, 2007 Free Software Foundation, Inc.
   3    Contributed by Daniel Berlin <dan@dberlin.org>, Steven Bosscher
   4    <stevenb@suse.de> and Diego Novillo <dnovillo@redhat.com>
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify
   9 it under the terms of the GNU General Public License as published by
  10 the Free Software Foundation; either version 3, or (at your option)
  11 any later version.
  12
  13 GCC is distributed in the hope that it will be useful,
  14 but WITHOUT ANY WARRANTY; without even the implied warranty of
  15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16 GNU General Public License for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GCC; see the file COPYING3.  If not see
  20 <http://www.gnu.org/licenses/>.  */
  21
  22 #include "config.h"
  23 #include "system.h"
  24 #include "coretypes.h"
  25 #include "tm.h"
  26 #include "ggc.h"
  27 #include "tree.h"
  28 #include "tree-flow.h"
  29 #include "hashtab.h"
  30 #include "langhooks.h"
  31 #include "tree-pass.h"
  32 #include "tree-dump.h"
  33 #include "diagnostic.h"
  34 #include "tree-ssa-sccvn.h"
  35
  36 /* Most of this is PRE specific.  The real grunt work is done in
  37    tree-ssa-sccvn.c.  This is where the lookup and insertion
  38    functions, etc, can be found */
  39
  40 /* Create and return a new value handle node of type TYPE.  */
  41
  42 tree
  43 make_value_handle (tree type)
  44 {
  45   static unsigned int id = 0;
  46   tree vh;
  47
  48   vh = build0 (VALUE_HANDLE, type);
  49   VALUE_HANDLE_ID (vh) = id++;
  50   return vh;
  51 }
  52
  53
  54
  55 /* Compare two expressions E1 and E2 and return true if they are
  56    equal.  */
  57
  58 bool
  59 expressions_equal_p (tree e1, tree e2)
  60 {
  61   tree te1, te2;
  62
  63   if (e1 == e2)
  64     return true;
  65
  66   te1 = TREE_TYPE (e1);
  67   te2 = TREE_TYPE (e2);
  68
  69   if (TREE_CODE (e1) == TREE_LIST && TREE_CODE (e2) == TREE_LIST)
  70     {
  71       tree lop1 = e1;
  72       tree lop2 = e2;
  73       for (lop1 = e1, lop2 = e2;
  74            lop1 || lop2;
  75            lop1 = TREE_CHAIN (lop1), lop2 = TREE_CHAIN (lop2))
  76         {
  77           if (!lop1 || !lop2)
  78             return false;
  79           if (!expressions_equal_p (TREE_VALUE (lop1), TREE_VALUE (lop2)))
  80             return false;
  81         }
  82       return true;
  83
  84     }
  85   else if (TREE_CODE (e1) == TREE_CODE (e2)
  86            && (te1 == te2
  87                || types_compatible_p (te1, te2))
  88            && operand_equal_p (e1, e2, OEP_PURE_SAME))
  89     return true;
  90
  91   return false;
  92 }
  93
  94 /* Set the value handle for expression E to value V.  */
  95
  96 void
  97 set_value_handle (tree e, tree v)
  98 {
  99   if (TREE_CODE (e) == SSA_NAME)
 100     SSA_NAME_VALUE (e) = v;
 101   else if (EXPR_P (e) || DECL_P (e) || TREE_CODE (e) == TREE_LIST
 102            || GIMPLE_STMT_P (e)
 103            || TREE_CODE (e) == CONSTRUCTOR)
 104     get_tree_common_ann (e)->value_handle = v;
 105   else
 106     /* Do nothing.  Constants are their own value handles.  */
 107     gcc_assert (is_gimple_min_invariant (e));
 108 }
 109
 110 /* Print out the "Created value <x> for <Y>" statement to the
 111    dump_file.
 112    This is factored because both versions of lookup use it, and it
 113    obscures the real work going on in those functions.  */
 114
 115 static void
 116 print_creation_to_file (tree v, tree expr, VEC (tree, gc) *vuses)
 117 {
 118   fprintf (dump_file, "Created value ");
 119   print_generic_expr (dump_file, v, dump_flags);
 120   fprintf (dump_file, " for ");
 121   print_generic_expr (dump_file, expr, dump_flags);
 122
 123   if (vuses && VEC_length (tree, vuses) != 0)
 124     {
 125       size_t i;
 126       tree vuse;
 127
 128       fprintf (dump_file, " vuses: (");
 129       for (i = 0; VEC_iterate (tree, vuses, i, vuse); i++)
 130         {
 131           print_generic_expr (dump_file, vuse, dump_flags);
 132           if (VEC_length (tree, vuses) - 1 != i)
 133             fprintf (dump_file, ",");
 134         }
 135       fprintf (dump_file, ")");
 136     }
 137   fprintf (dump_file, "\n");
 138 }
 139
 140
 141 /* Sort the VUSE array so that we can do equality comparisons
 142    quicker on two vuse vecs.  */
 143
 144 void
 145 sort_vuses (VEC (tree,gc) *vuses)
 146 {
 147   if (VEC_length (tree, vuses) > 1)
 148     qsort (VEC_address (tree, vuses),
 149            VEC_length (tree, vuses),
 150            sizeof (tree),
 151            operand_build_cmp);
 152 }
 153
 154 /* Sort the VUSE array so that we can do equality comparisons
 155    quicker on two vuse vecs.  */
 156
 157 void
 158 sort_vuses_heap (VEC (tree,heap) *vuses)
 159 {
 160   if (VEC_length (tree, vuses) > 1)
 161     qsort (VEC_address (tree, vuses),
 162            VEC_length (tree, vuses),
 163            sizeof (tree),
 164            operand_build_cmp);
 165 }
 166 /* Insert EXPR into VALUE_TABLE with value VAL, and add expression
 167    EXPR to the value set for value VAL.  */
 168
 169 void
 170 vn_add (tree expr, tree val)
 171 {
 172   switch (TREE_CODE_CLASS (TREE_CODE (expr)))
 173     {
 174     case tcc_comparison:
 175     case tcc_binary:
 176       vn_binary_op_insert (expr, val);
 177       break;
 178     case tcc_unary:
 179       vn_unary_op_insert (expr, val);
 180       break;
 181       /* In the case of array-refs of constants, for example, we can
 182          end up with no vuses.  */
 183     case tcc_reference:
 184       vn_reference_insert (expr, val, NULL);
 185       break;
 186       /* The *only* time CALL_EXPR should appear here is
 187          when it has no vuses.  */
 188     case tcc_vl_exp:
 189     case tcc_exceptional:
 190     case tcc_expression:
 191     case tcc_declaration:
 192       if (TREE_CODE (expr) == CALL_EXPR || DECL_P (expr))
 193         {
 194           vn_reference_insert (expr, val, NULL);
 195           break;
 196         }
 197       else if (TREE_CODE (expr) == SSA_NAME)
 198         {
 199           SSA_NAME_VALUE (expr) = val;
 200           break;
 201         }
 202       else if (TREE_CODE (expr) == ADDR_EXPR)
 203         {
 204           vn_unary_op_insert (expr, val);
 205           break;
 206         }
 207       /* FALLTHROUGH */
 208     default:
 209       gcc_unreachable ();
 210     }
 211   set_value_handle (expr, val);
 212   if (TREE_CODE (val) == VALUE_HANDLE)
 213     add_to_value (val, expr);
 214 }
 215
 216 /* Insert EXPR into the value numbering tables.  with value VAL, and
 217    add expression EXPR to the value set for value VAL.  VUSES
 218    represents the virtual use operands associated with EXPR.  It is
 219    used when computing a hash value for EXPR.  */
 220
 221 void
 222 vn_add_with_vuses (tree expr, tree val, VEC (tree, gc) *vuses)
 223 {
 224   if (!vuses)
 225     {
 226       vn_add (expr, val);
 227       return;
 228     }
 229   vn_reference_insert (expr, val, vuses);
 230
 231   set_value_handle (expr, val);
 232   if (TREE_CODE (val) == VALUE_HANDLE)
 233     add_to_value (val, expr);
 234 }
 235
 236
 237 /* Lookup EXPR in the value numbering tables and return the result, if
 238    we have one.  */
 239
 240 tree
 241 vn_lookup (tree expr)
 242 {
 243   /* Constants are their own value.  */
 244   if (is_gimple_min_invariant (expr) || TREE_CODE (expr) == FIELD_DECL)
 245     return expr;
 246
 247   switch (TREE_CODE_CLASS (TREE_CODE (expr)))
 248     {
 249     case tcc_comparison:
 250     case tcc_binary:
 251       return vn_binary_op_lookup (expr);
 252     case tcc_unary:
 253       return vn_unary_op_lookup (expr);
 254       break;
 255       /* In the case of array-refs of constants, for example, we can
 256          end up with no vuses.  */
 257     case tcc_reference:
 258       return vn_reference_lookup (expr, NULL);
 259       break;
 260       /* It is possible to have CALL_EXPR with no vuses for things
 261          like "cos", and these will fall into vn_lookup.   */
 262     case tcc_vl_exp:
 263     case tcc_exceptional:
 264     case tcc_expression:
 265     case tcc_declaration:
 266       if (TREE_CODE (expr) == CALL_EXPR || DECL_P (expr))
 267         return vn_reference_lookup (expr, NULL);
 268       else if (TREE_CODE (expr) == SSA_NAME)
 269         return SSA_NAME_VALUE (expr);
 270       else if (TREE_CODE (expr) == ADDR_EXPR)
 271         return vn_unary_op_lookup (expr);
 272       /* FALLTHROUGH */
 273     default:
 274       gcc_unreachable ();
 275     }
 276   return NULL;
 277 }
 278
 279 /* Search in the value numbering tables for an existing instance of
 280    expression EXPR,  and return its value, or NULL if none has been set.  STMT
 281    represents the stmt associated with EXPR.  It is used when computing the
 282    hash value for EXPR for reference operations.  */
 283
 284 tree
 285 vn_lookup_with_stmt (tree expr, tree stmt)
 286 {
 287   if (stmt == NULL)
 288     return vn_lookup (expr);
 289
 290   /* Constants are their own value.  */
 291   if (is_gimple_min_invariant (expr) || TREE_CODE (expr) == FIELD_DECL)
 292     return expr;
 293
 294   return vn_lookup_with_vuses (expr, shared_vuses_from_stmt (stmt));
 295 }
 296
 297 /* Search in VALUE_TABLE for an existing instance of expression EXPR,
 298    and return its value, or NULL if none has been set.  VUSES is the
 299    list of virtual use operands associated with EXPR.  It is used when
 300    computing the hash value for EXPR.  */
 301
 302 tree
 303 vn_lookup_with_vuses (tree expr, VEC (tree, gc) *vuses)
 304 {
 305   if (!vuses || !VEC_length (tree, vuses))
 306     return vn_lookup (expr);
 307
 308   if (is_gimple_min_invariant (expr) || TREE_CODE (expr) == FIELD_DECL)
 309     return expr;
 310
 311   return vn_reference_lookup (expr, vuses);
 312 }
 313
 314 static tree
 315 create_value_handle_for_expr (tree expr, VEC(tree, gc) *vuses)
 316 {
 317   tree v;
 318
 319   v = make_value_handle (TREE_TYPE (expr));
 320
 321   if (dump_file && (dump_flags & TDF_DETAILS))
 322     print_creation_to_file (v, expr, vuses);
 323   return v;
 324 }
 325
 326 /* Like vn_lookup, but creates a new value for the operation if one
 327    does not exist.  */
 328
 329 tree
 330 vn_lookup_or_add (tree expr)
 331 {
 332   tree v = vn_lookup (expr);
 333
 334   if (v == NULL_TREE)
 335     {
 336       v = create_value_handle_for_expr (expr, NULL);
 337       vn_add (expr, v);
 338     }
 339   else
 340     set_value_handle (expr, v);
 341
 342   return v;
 343 }
 344
 345 /* Like vn_lookup, but handles reference operations as well by using
 346    STMT to get the set of vuses.  */
 347
 348 tree
 349 vn_lookup_or_add_with_stmt (tree expr, tree stmt)
 350 {
 351   tree v;
 352   if (!stmt)
 353     return vn_lookup_or_add (expr);
 354
 355   v = vn_lookup_with_stmt (expr, stmt);
 356   if (v == NULL_TREE)
 357     {
 358       VEC (tree, gc) *vuses = copy_vuses_from_stmt (stmt);
 359       v = create_value_handle_for_expr (expr, vuses);
 360       vn_add_with_vuses (expr, v, vuses);
 361     }
 362   else
 363     set_value_handle (expr, v);
 364
 365   return v;
 366 }
 367
 368 /* Like vn_lookup, but creates a new value for expression EXPR, if
 369    EXPR doesn't already have a value.  Return the existing/created
 370    value for EXPR.  STMT represents the stmt associated with EXPR.  It is used
 371    when computing the hash value for EXPR.  */
 372
 373 tree
 374 vn_lookup_or_add_with_vuses (tree expr, VEC (tree, gc) *vuses)
 375 {
 376   tree v;
 377
 378   if (!vuses || VEC_length (tree, vuses) == 0)
 379     return vn_lookup_or_add (expr);
 380
 381   v = vn_lookup_with_vuses (expr, vuses);
 382   if (v == NULL_TREE)
 383     {
 384       v = create_value_handle_for_expr (expr, vuses);
 385       vn_add_with_vuses (expr, v, vuses);
 386     }
 387   else
 388     set_value_handle (expr, v);
 389
 390   return v;
 391 }
 392