gcc/tree-vn.c

   1 /* Value Numbering routines for tree expressions.
   2    Copyright (C) 2001, 2002, 2003, 2004, 2005 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 2, 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 COPYING.  If not, write to
  20 the Free Software Foundation, 51 Franklin Street, Fifth Floor,
  21 Boston, MA 02110-1301, USA.  */
  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
  55
  56 /* Compare two expressions E1 and E2 and return true if they are
  57    equal.  */
  58
  59 bool
  60 expressions_equal_p (tree e1, tree e2)
  61 {
  62   tree te1, te2;
  63
  64   if (e1 == e2)
  65     return true;
  66
  67   te1 = TREE_TYPE (e1);
  68   te2 = TREE_TYPE (e2);
  69
  70   if (TREE_CODE (e1) == TREE_LIST && TREE_CODE (e2) == TREE_LIST)
  71     {
  72       tree lop1 = e1;
  73       tree lop2 = e2;
  74       for (lop1 = e1, lop2 = e2;
  75            lop1 || lop2;
  76            lop1 = TREE_CHAIN (lop1), lop2 = TREE_CHAIN (lop2))
  77         {
  78           if (!lop1 || !lop2)
  79             return false;
  80           if (!expressions_equal_p (TREE_VALUE (lop1), TREE_VALUE (lop2)))
  81             return false;
  82         }
  83       return true;
  84
  85     }
  86   else if (TREE_CODE (e1) == TREE_CODE (e2)
  87            && (te1 == te2
  88                || types_compatible_p (te1, te2))
  89            && operand_equal_p (e1, e2, OEP_PURE_SAME))
  90     return true;
  91
  92   return false;
  93 }
  94
  95 /* Set the value handle for expression E to value V.  */
  96
  97 void
  98 set_value_handle (tree e, tree v)
  99 {
 100   if (TREE_CODE (e) == SSA_NAME)
 101     SSA_NAME_VALUE (e) = v;
 102   else if (EXPR_P (e) || DECL_P (e) || TREE_CODE (e) == TREE_LIST
 103            || GIMPLE_STMT_P (e)
 104            || TREE_CODE (e) == CONSTRUCTOR)
 105     get_tree_common_ann (e)->value_handle = v;
 106   else
 107     /* Do nothing.  Constants are their own value handles.  */
 108     gcc_assert (is_gimple_min_invariant (e));
 109 }
 110
 111 /* A comparison function for use in qsort to compare vuses.  Simply
 112    subtracts version numbers.  */
 113
 114 static int
 115 vuses_compare (const void *pa, const void *pb)
 116 {
 117   const tree vusea = *((const tree *)pa);
 118   const tree vuseb = *((const tree *)pb);
 119   int sn = SSA_NAME_VERSION (vusea) - SSA_NAME_VERSION (vuseb);
 120
 121   return sn;
 122 }
 123
 124 /* Print out the "Created value <x> for <Y>" statement to the
 125    dump_file.
 126    This is factored because both versions of lookup use it, and it
 127    obscures the real work going on in those functions.  */
 128
 129 static void
 130 print_creation_to_file (tree v, tree expr, VEC (tree, gc) *vuses)
 131 {
 132   fprintf (dump_file, "Created value ");
 133   print_generic_expr (dump_file, v, dump_flags);
 134   fprintf (dump_file, " for ");
 135   print_generic_expr (dump_file, expr, dump_flags);
 136
 137   if (vuses && VEC_length (tree, vuses) != 0)
 138     {
 139       size_t i;
 140       tree vuse;
 141
 142       fprintf (dump_file, " vuses: (");
 143       for (i = 0; VEC_iterate (tree, vuses, i, vuse); i++)
 144         {
 145           print_generic_expr (dump_file, vuse, dump_flags);
 146           if (VEC_length (tree, vuses) - 1 != i)
 147             fprintf (dump_file, ",");
 148         }
 149       fprintf (dump_file, ")");
 150     }
 151   fprintf (dump_file, "\n");
 152 }
 153
 154
 155 /* Sort the VUSE array so that we can do equality comparisons
 156    quicker on two vuse vecs.  */
 157
 158 void
 159 sort_vuses (VEC (tree,gc) *vuses)
 160 {
 161   if (VEC_length (tree, vuses) > 1)
 162     qsort (VEC_address (tree, vuses),
 163            VEC_length (tree, vuses),
 164            sizeof (tree),
 165            vuses_compare);
 166 }
 167
 168 /* Sort the VUSE array so that we can do equality comparisons
 169    quicker on two vuse vecs.  */
 170
 171 void
 172 sort_vuses_heap (VEC (tree,heap) *vuses)
 173 {
 174   if (VEC_length (tree, vuses) > 1)
 175     qsort (VEC_address (tree, vuses),
 176            VEC_length (tree, vuses),
 177            sizeof (tree),
 178            vuses_compare);
 179 }
 180 /* Insert EXPR into VALUE_TABLE with value VAL, and add expression
 181    EXPR to the value set for value VAL.  */
 182
 183 void
 184 vn_add (tree expr, tree val)
 185 {
 186   switch (TREE_CODE_CLASS (TREE_CODE (expr)))
 187     {
 188     case tcc_comparison:
 189     case tcc_binary:
 190       vn_binary_op_insert (expr, val);
 191       break;
 192     case tcc_unary:
 193       vn_unary_op_insert (expr, val);
 194       break;
 195       /* In the case of array-refs of constants, for example, we can
 196          end up with no vuses.  */
 197     case tcc_reference:
 198       vn_reference_insert (expr, val, NULL);
 199       break;
 200       /* The *only* time CALL_EXPR should appear here is
 201          when it has no vuses.  */
 202     case tcc_vl_exp:
 203     case tcc_exceptional:
 204     case tcc_expression:
 205     case tcc_declaration:
 206       if (TREE_CODE (expr) == CALL_EXPR || DECL_P (expr))
 207         {
 208           vn_reference_insert (expr, val, NULL);
 209           break;
 210         }
 211       else if (TREE_CODE (expr) == SSA_NAME)
 212         {
 213           SSA_NAME_VALUE (expr) = val;
 214           break;
 215         }
 216       else if (TREE_CODE (expr) == ADDR_EXPR)
 217         {
 218           vn_unary_op_insert (expr, val);
 219           break;
 220         }
 221       /* FALLTHROUGH */
 222     default:
 223       gcc_unreachable ();
 224     }
 225   set_value_handle (expr, val);
 226   if (TREE_CODE (val) == VALUE_HANDLE)
 227     add_to_value (val, expr);
 228 }
 229
 230 /* Insert EXPR into the value numbering tables.  with value VAL, and
 231    add expression EXPR to the value set for value VAL.  VUSES
 232    represents the virtual use operands associated with EXPR.  It is
 233    used when computing a hash value for EXPR.  */
 234
 235 void
 236 vn_add_with_vuses (tree expr, tree val, VEC (tree, gc) *vuses)
 237 {
 238   if (!vuses)
 239     {
 240       vn_add (expr, val);
 241       return;
 242     }
 243   vn_reference_insert (expr, val, vuses);
 244
 245   set_value_handle (expr, val);
 246   if (TREE_CODE (val) == VALUE_HANDLE)
 247     add_to_value (val, expr);
 248 }
 249
 250
 251 /* Lookup EXPR in the value numbering tables and return the result, if
 252    we have one.  */
 253
 254 tree
 255 vn_lookup (tree expr)
 256 {
 257   /* Constants are their own value.  */
 258   if (is_gimple_min_invariant (expr) || TREE_CODE (expr) == FIELD_DECL)
 259     return expr;
 260
 261   switch (TREE_CODE_CLASS (TREE_CODE (expr)))
 262     {
 263     case tcc_comparison:
 264     case tcc_binary:
 265       return vn_binary_op_lookup (expr);
 266     case tcc_unary:
 267       return vn_unary_op_lookup (expr);
 268       break;
 269       /* In the case of array-refs of constants, for example, we can
 270          end up with no vuses.  */
 271     case tcc_reference:
 272       return vn_reference_lookup (expr, NULL);
 273       break;
 274       /* It is possible to have CALL_EXPR with no vuses for things
 275          like "cos", and these will fall into vn_lookup.   */
 276     case tcc_vl_exp:
 277     case tcc_exceptional:
 278     case tcc_expression:
 279     case tcc_declaration:
 280       if (TREE_CODE (expr) == CALL_EXPR || DECL_P (expr))
 281         return vn_reference_lookup (expr, NULL);
 282       else if (TREE_CODE (expr) == SSA_NAME)
 283         return SSA_NAME_VALUE (expr);
 284       else if (TREE_CODE (expr) == ADDR_EXPR)
 285         return vn_unary_op_lookup (expr);
 286       /* FALLTHROUGH */
 287     default:
 288       gcc_unreachable ();
 289     }
 290   return NULL;
 291 }
 292
 293 /* Search in the value numbering tables for an existing instance of
 294    expression EXPR,  and return its value, or NULL if none has been set.  STMT
 295    represents the stmt associated with EXPR.  It is used when computing the
 296    hash value for EXPR for reference operations.  */
 297
 298 tree
 299 vn_lookup_with_stmt (tree expr, tree stmt)
 300 {
 301   if (stmt == NULL)
 302     return vn_lookup (expr);
 303
 304   /* Constants are their own value.  */
 305   if (is_gimple_min_invariant (expr) || TREE_CODE (expr) == FIELD_DECL)
 306     return expr;
 307
 308   return vn_lookup_with_vuses (expr, shared_vuses_from_stmt (stmt));
 309 }
 310
 311 /* Search in VALUE_TABLE for an existing instance of expression EXPR,
 312    and return its value, or NULL if none has been set.  VUSES is the
 313    list of virtual use operands associated with EXPR.  It is used when
 314    computing the hash value for EXPR.  */
 315
 316 tree
 317 vn_lookup_with_vuses (tree expr, VEC (tree, gc) *vuses)
 318 {
 319   if (!vuses || !VEC_length (tree, vuses))
 320     return vn_lookup (expr);
 321
 322   if (is_gimple_min_invariant (expr) || TREE_CODE (expr) == FIELD_DECL)
 323     return expr;
 324
 325   return vn_reference_lookup (expr, vuses);
 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