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