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