gcc/tree-vn.c

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