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       else if (TREE_CODE (expr) == ADDR_EXPR)
 200         {
 201           vn_nary_op_insert (expr, val);
 202           break;
 203         }
 204       /* FALLTHROUGH */
 205     default:
 206       gcc_unreachable ();
 207     }
 208   set_value_handle (expr, val);
 209   if (TREE_CODE (val) == VALUE_HANDLE)
 210     add_to_value (val, expr);
 211 }
 212
 213 /* Insert EXPR into the value numbering tables with value VAL, and
 214    add expression EXPR to the value set for value VAL.  VUSES
 215    represents the virtual use operands associated with EXPR.  It is
 216    used when computing a hash value for EXPR.  */
 217
 218 void
 219 vn_add_with_vuses (tree expr, tree val, VEC (tree, gc) *vuses)
 220 {
 221   if (!vuses)
 222     {
 223       vn_add (expr, val);
 224       return;
 225     }
 226   vn_reference_insert (expr, val, vuses);
 227
 228   set_value_handle (expr, val);
 229   if (TREE_CODE (val) == VALUE_HANDLE)
 230     add_to_value (val, expr);
 231 }
 232
 233 /* Lookup EXPR in the value numbering tables and return the result, if
 234    we have one.  */
 235
 236 tree
 237 vn_lookup (tree expr)
 238 {
 239   /* Constants are their own value.  */
 240   if (is_gimple_min_invariant (expr) || TREE_CODE (expr) == FIELD_DECL)
 241     return expr;
 242
 243   switch (TREE_CODE_CLASS (TREE_CODE (expr)))
 244     {
 245     case tcc_comparison:
 246     case tcc_binary:
 247       return vn_nary_op_lookup (expr);
 248     case tcc_unary:
 249       return vn_nary_op_lookup (expr);
 250       break;
 251       /* In the case of array-refs of constants, for example, we can
 252          end up with no vuses.  */
 253     case tcc_reference:
 254       return vn_reference_lookup (expr, NULL, false);
 255       break;
 256       /* It is possible to have CALL_EXPR with no vuses for things
 257          like "cos", and these will fall into vn_lookup.   */
 258     case tcc_vl_exp:
 259     case tcc_exceptional:
 260     case tcc_expression:
 261     case tcc_declaration:
 262       if (TREE_CODE (expr) == CALL_EXPR || DECL_P (expr))
 263         return vn_reference_lookup (expr, NULL, false);
 264       else if (TREE_CODE (expr) == SSA_NAME)
 265         return SSA_NAME_VALUE (expr);
 266       else if (TREE_CODE (expr) == ADDR_EXPR)
 267         return vn_nary_op_lookup (expr);
 268       /* FALLTHROUGH */
 269     default:
 270       gcc_unreachable ();
 271     }
 272   return NULL;
 273 }
 274
 275 /* Search in the value numbering tables for an existing instance of
 276    expression EXPR,  and return its value, or NULL if none has been set.  STMT
 277    represents the stmt associated with EXPR.  It is used when computing the
 278    hash value for EXPR for reference operations.  */
 279
 280 tree
 281 vn_lookup_with_stmt (tree expr, tree stmt)
 282 {
 283   if (stmt == NULL)
 284     return vn_lookup (expr);
 285
 286   /* Constants are their own value.  */
 287   if (is_gimple_min_invariant (expr) || TREE_CODE (expr) == FIELD_DECL)
 288     return expr;
 289
 290   return vn_lookup_with_vuses (expr, shared_vuses_from_stmt (stmt));
 291 }
 292
 293 /* Search in VALUE_TABLE for an existing instance of expression EXPR,
 294    and return its value, or NULL if none has been set.  VUSES is the
 295    list of virtual use operands associated with EXPR.  It is used when
 296    computing the hash value for EXPR.  */
 297
 298 tree
 299 vn_lookup_with_vuses (tree expr, VEC (tree, gc) *vuses)
 300 {
 301   if (!vuses || !VEC_length (tree, vuses))
 302     return vn_lookup (expr);
 303
 304   if (is_gimple_min_invariant (expr) || TREE_CODE (expr) == FIELD_DECL)
 305     return expr;
 306
 307   /* We may not walk the use-def chains here as the alias oracle cannot
 308      properly deal with VALUE_HANDLE tree nodes we feed it here.  */
 309   return vn_reference_lookup (expr, vuses, false);
 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