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