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 /* A comparison function for use in qsort to compare vuses.  Simply
 111    subtracts version numbers.  */
 112
 113 static int
 114 vuses_compare (const void *pa, const void *pb)
 115 {
 116   const tree vusea = *((const tree *)pa);
 117   const tree vuseb = *((const tree *)pb);
 118   int sn = SSA_NAME_VERSION (vusea) - SSA_NAME_VERSION (vuseb);
 119
 120   return sn;
 121 }
 122
 123 /* Print out the "Created value <x> for <Y>" statement to the
 124    dump_file.
 125    This is factored because both versions of lookup use it, and it
 126    obscures the real work going on in those functions.  */
 127
 128 static void
 129 print_creation_to_file (tree v, tree expr, VEC (tree, gc) *vuses)
 130 {
 131   fprintf (dump_file, "Created value ");
 132   print_generic_expr (dump_file, v, dump_flags);
 133   fprintf (dump_file, " for ");
 134   print_generic_expr (dump_file, expr, dump_flags);
 135
 136   if (vuses && VEC_length (tree, vuses) != 0)
 137     {
 138       size_t i;
 139       tree vuse;
 140
 141       fprintf (dump_file, " vuses: (");
 142       for (i = 0; VEC_iterate (tree, vuses, i, vuse); i++)
 143         {
 144           print_generic_expr (dump_file, vuse, dump_flags);
 145           if (VEC_length (tree, vuses) - 1 != i)
 146             fprintf (dump_file, ",");
 147         }
 148       fprintf (dump_file, ")");
 149     }
 150   fprintf (dump_file, "\n");
 151 }
 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 (VEC (tree,gc) *vuses)
 159 {
 160   if (VEC_length (tree, vuses) > 1)
 161     qsort (VEC_address (tree, vuses),
 162            VEC_length (tree, vuses),
 163            sizeof (tree),
 164            vuses_compare);
 165 }
 166
 167 /* Sort the VUSE array so that we can do equality comparisons
 168    quicker on two vuse vecs.  */
 169
 170 void
 171 sort_vuses_heap (VEC (tree,heap) *vuses)
 172 {
 173   if (VEC_length (tree, vuses) > 1)
 174     qsort (VEC_address (tree, vuses),
 175            VEC_length (tree, vuses),
 176            sizeof (tree),
 177            vuses_compare);
 178 }
 179 /* Insert EXPR into VALUE_TABLE with value VAL, and add expression
 180    EXPR to the value set for value VAL.  */
 181
 182 void
 183 vn_add (tree expr, tree val)
 184 {
 185   switch (TREE_CODE_CLASS (TREE_CODE (expr)))
 186     {
 187     case tcc_comparison:
 188     case tcc_binary:
 189       vn_binary_op_insert (expr, val);
 190       break;
 191     case tcc_unary:
 192       vn_unary_op_insert (expr, val);
 193       break;
 194       /* In the case of array-refs of constants, for example, we can
 195          end up with no vuses.  */
 196     case tcc_reference:
 197       vn_reference_insert (expr, val, NULL);
 198       break;
 199       /* The *only* time CALL_EXPR should appear here is
 200          when it has no vuses.  */
 201     case tcc_vl_exp:
 202     case tcc_exceptional:
 203     case tcc_expression:
 204     case tcc_declaration:
 205       if (TREE_CODE (expr) == CALL_EXPR || DECL_P (expr))
 206         {
 207           vn_reference_insert (expr, val, NULL);
 208           break;
 209         }
 210       else if (TREE_CODE (expr) == SSA_NAME)
 211         {
 212           SSA_NAME_VALUE (expr) = val;
 213           break;
 214         }
 215       else if (TREE_CODE (expr) == ADDR_EXPR)
 216         {
 217           vn_unary_op_insert (expr, val);
 218           break;
 219         }
 220       /* FALLTHROUGH */
 221     default:
 222       gcc_unreachable ();
 223     }
 224   set_value_handle (expr, val);
 225   if (TREE_CODE (val) == VALUE_HANDLE)
 226     add_to_value (val, expr);
 227 }
 228
 229 /* Insert EXPR into the value numbering tables.  with value VAL, and
 230    add expression EXPR to the value set for value VAL.  VUSES
 231    represents the virtual use operands associated with EXPR.  It is
 232    used when computing a hash value for EXPR.  */
 233
 234 void
 235 vn_add_with_vuses (tree expr, tree val, VEC (tree, gc) *vuses)
 236 {
 237   if (!vuses)
 238     {
 239       vn_add (expr, val);
 240       return;
 241     }
 242   vn_reference_insert (expr, val, vuses);
 243
 244   set_value_handle (expr, val);
 245   if (TREE_CODE (val) == VALUE_HANDLE)
 246     add_to_value (val, expr);
 247 }
 248
 249
 250 /* Lookup EXPR in the value numbering tables and return the result, if
 251    we have one.  */
 252
 253 tree
 254 vn_lookup (tree expr)
 255 {
 256   /* Constants are their own value.  */
 257   if (is_gimple_min_invariant (expr) || TREE_CODE (expr) == FIELD_DECL)
 258     return expr;
 259
 260   switch (TREE_CODE_CLASS (TREE_CODE (expr)))
 261     {
 262     case tcc_comparison:
 263     case tcc_binary:
 264       return vn_binary_op_lookup (expr);
 265     case tcc_unary:
 266       return vn_unary_op_lookup (expr);
 267       break;
 268       /* In the case of array-refs of constants, for example, we can
 269          end up with no vuses.  */
 270     case tcc_reference:
 271       return vn_reference_lookup (expr, NULL);
 272       break;
 273       /* It is possible to have CALL_EXPR with no vuses for things
 274          like "cos", and these will fall into vn_lookup.   */
 275     case tcc_vl_exp:
 276     case tcc_exceptional:
 277     case tcc_expression:
 278     case tcc_declaration:
 279       if (TREE_CODE (expr) == CALL_EXPR || DECL_P (expr))
 280         return vn_reference_lookup (expr, NULL);
 281       else if (TREE_CODE (expr) == SSA_NAME)
 282         return SSA_NAME_VALUE (expr);
 283       else if (TREE_CODE (expr) == ADDR_EXPR)
 284         return vn_unary_op_lookup (expr);
 285       /* FALLTHROUGH */
 286     default:
 287       gcc_unreachable ();
 288     }
 289   return NULL;
 290 }
 291
 292 /* Search in the value numbering tables for an existing instance of
 293    expression EXPR,  and return its value, or NULL if none has been set.  STMT
 294    represents the stmt associated with EXPR.  It is used when computing the
 295    hash value for EXPR for reference operations.  */
 296
 297 tree
 298 vn_lookup_with_stmt (tree expr, tree stmt)
 299 {
 300   if (stmt == NULL)
 301     return vn_lookup (expr);
 302
 303   /* Constants are their own value.  */
 304   if (is_gimple_min_invariant (expr) || TREE_CODE (expr) == FIELD_DECL)
 305     return expr;
 306
 307   return vn_lookup_with_vuses (expr, shared_vuses_from_stmt (stmt));
 308 }
 309
 310 /* Search in VALUE_TABLE for an existing instance of expression EXPR,
 311    and return its value, or NULL if none has been set.  VUSES is the
 312    list of virtual use operands associated with EXPR.  It is used when
 313    computing the hash value for EXPR.  */
 314
 315 tree
 316 vn_lookup_with_vuses (tree expr, VEC (tree, gc) *vuses)
 317 {
 318   if (!vuses || !VEC_length (tree, vuses))
 319     return vn_lookup (expr);
 320
 321   if (is_gimple_min_invariant (expr) || TREE_CODE (expr) == FIELD_DECL)
 322     return expr;
 323
 324   return vn_reference_lookup (expr, vuses);
 325 }
 326
 327 static tree
 328 create_value_handle_for_expr (tree expr, VEC(tree, gc) *vuses)
 329 {
 330   tree v;
 331
 332   v = make_value_handle (TREE_TYPE (expr));
 333
 334   if (dump_file && (dump_flags & TDF_DETAILS))
 335     print_creation_to_file (v, expr, vuses);
 336   return v;
 337 }
 338
 339 /* Like vn_lookup, but creates a new value for the operation if one
 340    does not exist.  */
 341
 342 tree
 343 vn_lookup_or_add (tree expr)
 344 {
 345   tree v = vn_lookup (expr);
 346
 347   if (v == NULL_TREE)
 348     {
 349       v = create_value_handle_for_expr (expr, NULL);
 350       vn_add (expr, v);
 351     }
 352   else
 353     set_value_handle (expr, v);
 354
 355   return v;
 356 }
 357
 358 /* Like vn_lookup, but handles reference operations as well by using
 359    STMT to get the set of vuses.  */
 360
 361 tree
 362 vn_lookup_or_add_with_stmt (tree expr, tree stmt)
 363 {
 364   tree v;
 365   if (!stmt)
 366     return vn_lookup_or_add (expr);
 367
 368   v = vn_lookup_with_stmt (expr, stmt);
 369   if (v == NULL_TREE)
 370     {
 371       VEC (tree, gc) *vuses = copy_vuses_from_stmt (stmt);
 372       v = create_value_handle_for_expr (expr, vuses);
 373       vn_add_with_vuses (expr, v, vuses);
 374     }
 375   else
 376     set_value_handle (expr, v);
 377
 378   return v;
 379 }
 380
 381 /* Like vn_lookup, but creates a new value for expression EXPR, if
 382    EXPR doesn't already have a value.  Return the existing/created
 383    value for EXPR.  STMT represents the stmt associated with EXPR.  It is used
 384    when computing the hash value for EXPR.  */
 385
 386 tree
 387 vn_lookup_or_add_with_vuses (tree expr, VEC (tree, gc) *vuses)
 388 {
 389   tree v;
 390
 391   if (!vuses || VEC_length (tree, vuses) == 0)
 392     return vn_lookup_or_add (expr);
 393
 394   v = vn_lookup_with_vuses (expr, vuses);
 395   if (v == NULL_TREE)
 396     {
 397       v = create_value_handle_for_expr (expr, vuses);
 398       vn_add_with_vuses (expr, v, vuses);
 399     }
 400   else
 401     set_value_handle (expr, v);
 402
 403   return v;
 404 }
 405