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
  36 /* The value table that maps expressions to values.  */
  37 static htab_t value_table;
  38
  39 /* Map expressions to values.  These are simple pairs of expressions
  40    and the values they represent.  To find the value represented by
  41    an expression, we use a hash table where the elements are {e,v}
  42    pairs, and the expression is the key.  */
  43 typedef struct val_expr_pair_d
  44 {
  45   /* Value handle.  */
  46   tree v;
  47
  48   /* Associated expression.  */
  49   tree e;
  50
  51   /* For comparing virtual uses in E.  */
  52   VEC (tree, gc) *vuses;
  53
  54   /* E's hash value.  */
  55   hashval_t hashcode;
  56 } *val_expr_pair_t;
  57
  58 static void set_value_handle (tree e, tree v);
  59
  60
  61 /* Create and return a new value handle node of type TYPE.  */
  62
  63 static tree
  64 make_value_handle (tree type)
  65 {
  66   static unsigned int id = 0;
  67   tree vh;
  68
  69   vh = build0 (VALUE_HANDLE, type);
  70   VALUE_HANDLE_ID (vh) = id++;
  71   return vh;
  72 }
  73
  74
  75 /* Given an expression EXPR, compute a hash value number using the
  76    code of the expression, its real operands and virtual operands (if
  77    any).
  78
  79    VAL can be used to iterate by passing previous value numbers (it is
  80    used by iterative_hash_expr).  */
  81
  82 hashval_t
  83 vn_compute (tree expr, hashval_t val)
  84 {
  85   /* EXPR must not be a statement.  We are only interested in value
  86      numbering expressions on the RHS of assignments.  */
  87   gcc_assert (expr);
  88   gcc_assert (!expr->base.ann
  89               || expr->base.ann->common.type != STMT_ANN);
  90
  91   val = iterative_hash_expr (expr, val);
  92   return val;
  93 }
  94
  95 /* Compare two expressions E1 and E2 and return true if they are
  96    equal.  */
  97
  98 bool
  99 expressions_equal_p (tree e1, tree e2)
 100 {
 101   tree te1, te2;
 102
 103   if (e1 == e2)
 104     return true;
 105
 106   te1 = TREE_TYPE (e1);
 107   te2 = TREE_TYPE (e2);
 108
 109   if (TREE_CODE (e1) == TREE_LIST && TREE_CODE (e2) == TREE_LIST)
 110     {
 111       tree lop1 = e1;
 112       tree lop2 = e2;
 113       for (lop1 = e1, lop2 = e2;
 114            lop1 || lop2;
 115            lop1 = TREE_CHAIN (lop1), lop2 = TREE_CHAIN (lop2))
 116         {
 117           if (!lop1 || !lop2)
 118             return false;
 119           if (!expressions_equal_p (TREE_VALUE (lop1), TREE_VALUE (lop2)))
 120             return false;
 121         }
 122       return true;
 123
 124     }
 125   else if (TREE_CODE (e1) == TREE_CODE (e2)
 126            && (te1 == te2 || lang_hooks.types_compatible_p (te1, te2))
 127            && operand_equal_p (e1, e2, OEP_PURE_SAME))
 128     return true;
 129
 130   return false;
 131 }
 132
 133
 134 /* Hash a {v,e} pair that is pointed to by P.
 135    The hashcode is cached in the val_expr_pair, so we just return
 136    that.  */
 137
 138 static hashval_t
 139 val_expr_pair_hash (const void *p)
 140 {
 141   const val_expr_pair_t ve = (val_expr_pair_t) p;
 142   return ve->hashcode;
 143 }
 144
 145
 146 /* Given two val_expr_pair_t's, return true if they represent the same
 147    expression, false otherwise.
 148    P1 and P2 should point to the val_expr_pair_t's to be compared.  */
 149
 150 static int
 151 val_expr_pair_expr_eq (const void *p1, const void *p2)
 152 {
 153   int i;
 154   tree vuse1;
 155   const val_expr_pair_t ve1 = (val_expr_pair_t) p1;
 156   const val_expr_pair_t ve2 = (val_expr_pair_t) p2;
 157
 158   if (! expressions_equal_p (ve1->e, ve2->e))
 159     return false;
 160
 161   if (ve1->vuses == ve2->vuses)
 162     return true;
 163
 164   if (VEC_length (tree, ve1->vuses) != VEC_length (tree, ve2->vuses))
 165     return false;
 166
 167   for (i = 0; VEC_iterate (tree, ve1->vuses, i, vuse1); i++)
 168     {
 169       if (VEC_index (tree, ve2->vuses, i) != vuse1)
 170         return false;
 171     }
 172   return true;
 173 }
 174
 175
 176 /* Set the value handle for expression E to value V.  */
 177
 178 static void
 179 set_value_handle (tree e, tree v)
 180 {
 181   if (TREE_CODE (e) == SSA_NAME)
 182     SSA_NAME_VALUE (e) = v;
 183   else if (EXPR_P (e) || DECL_P (e) || TREE_CODE (e) == TREE_LIST
 184            || GIMPLE_STMT_P (e)
 185            || TREE_CODE (e) == CONSTRUCTOR)
 186     get_tree_common_ann (e)->value_handle = v;
 187   else
 188     /* Do nothing.  Constants are their own value handles.  */
 189     gcc_assert (is_gimple_min_invariant (e));
 190 }
 191
 192 /* Copy the virtual uses from STMT into a newly allocated VEC(tree),
 193    and return the VEC(tree).  */
 194
 195 static VEC (tree, gc) *
 196 copy_vuses_from_stmt (tree stmt)
 197 {
 198   ssa_op_iter iter;
 199   tree vuse;
 200   VEC (tree, gc) *vuses = NULL;
 201
 202   if (!stmt)
 203     return NULL;
 204
 205   FOR_EACH_SSA_TREE_OPERAND (vuse, stmt, iter, SSA_OP_VUSE)
 206     VEC_safe_push (tree, gc, vuses, vuse);
 207
 208   return vuses;
 209 }
 210
 211 /* Place for shared_vuses_from_stmt to shove vuses.  */
 212 static VEC (tree, gc) *shared_lookup_vuses;
 213
 214 /* Copy the virtual uses from STMT into SHARED_LOOKUP_VUSES.
 215    This function will overwrite the current SHARED_LOOKUP_VUSES
 216    variable.  */
 217
 218 static VEC (tree, gc) *
 219 shared_vuses_from_stmt (tree stmt)
 220 {
 221   ssa_op_iter iter;
 222   tree vuse;
 223
 224   if (!stmt)
 225     return NULL;
 226
 227   VEC_truncate (tree, shared_lookup_vuses, 0);
 228
 229   FOR_EACH_SSA_TREE_OPERAND (vuse, stmt, iter, SSA_OP_VUSE)
 230     VEC_safe_push (tree, gc, shared_lookup_vuses, vuse);
 231
 232   if (VEC_length (tree, shared_lookup_vuses) > 1)
 233     sort_vuses (shared_lookup_vuses);
 234
 235   return shared_lookup_vuses;
 236 }
 237
 238 /* Insert EXPR into VALUE_TABLE with value VAL, and add expression
 239    EXPR to the value set for value VAL.  */
 240
 241 void
 242 vn_add (tree expr, tree val)
 243 {
 244   vn_add_with_vuses (expr, val, NULL);
 245 }
 246
 247 /* Insert EXPR into VALUE_TABLE with value VAL, and add expression
 248    EXPR to the value set for value VAL.  VUSES represents the virtual
 249    use operands associated with EXPR.  It is used when computing a
 250    hash value for EXPR.  */
 251
 252 void
 253 vn_add_with_vuses (tree expr, tree val, VEC (tree, gc) *vuses)
 254 {
 255   void **slot;
 256   val_expr_pair_t new_pair;
 257
 258   new_pair = XNEW (struct val_expr_pair_d);
 259   new_pair->e = expr;
 260   new_pair->v = val;
 261   new_pair->vuses = vuses;
 262   new_pair->hashcode = vn_compute (expr, 0);
 263   slot = htab_find_slot_with_hash (value_table, new_pair, new_pair->hashcode,
 264                                    INSERT);
 265   if (*slot)
 266     free (*slot);
 267   *slot = (void *) new_pair;
 268
 269   set_value_handle (expr, val);
 270   if (TREE_CODE (val) == VALUE_HANDLE)
 271     add_to_value (val, expr);
 272 }
 273
 274
 275 /* Search in VALUE_TABLE for an existing instance of expression EXPR,
 276    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.  */
 279
 280 tree
 281 vn_lookup (tree expr, tree stmt)
 282 {
 283   return vn_lookup_with_vuses (expr, shared_vuses_from_stmt (stmt));
 284 }
 285
 286 /* Search in VALUE_TABLE for an existing instance of expression EXPR,
 287    and return its value, or NULL if none has been set.  VUSES is the
 288    list of virtual use operands associated with EXPR.  It is used when
 289    computing the hash value for EXPR.  */
 290
 291 tree
 292 vn_lookup_with_vuses (tree expr, VEC (tree, gc) *vuses)
 293 {
 294   void **slot;
 295   struct val_expr_pair_d vep = {NULL, NULL, NULL, 0};
 296
 297   /* Constants are their own value.  */
 298   if (is_gimple_min_invariant (expr))
 299     return expr;
 300
 301   vep.e = expr;
 302   vep.vuses = vuses;
 303   vep.hashcode = vn_compute (expr, 0);
 304   slot = htab_find_slot_with_hash (value_table, &vep, vep.hashcode, NO_INSERT);
 305   if (!slot)
 306     return NULL_TREE;
 307   else
 308     return ((val_expr_pair_t) *slot)->v;
 309 }
 310
 311
 312 /* A comparison function for use in qsort to compare vuses.  Simply
 313    subtracts version numbers.  */
 314
 315 static int
 316 vuses_compare (const void *pa, const void *pb)
 317 {
 318   const tree vusea = *((const tree *)pa);
 319   const tree vuseb = *((const tree *)pb);
 320   int sn = SSA_NAME_VERSION (vusea) - SSA_NAME_VERSION (vuseb);
 321
 322   return sn;
 323 }
 324
 325 /* Print out the "Created value <x> for <Y>" statement to the
 326    dump_file.
 327    This is factored because both versions of lookup use it, and it
 328    obscures the real work going on in those functions.  */
 329
 330 static void
 331 print_creation_to_file (tree v, tree expr, VEC (tree, gc) *vuses)
 332 {
 333   fprintf (dump_file, "Created value ");
 334   print_generic_expr (dump_file, v, dump_flags);
 335   fprintf (dump_file, " for ");
 336   print_generic_expr (dump_file, expr, dump_flags);
 337
 338   if (vuses && VEC_length (tree, vuses) != 0)
 339     {
 340       size_t i;
 341       tree vuse;
 342
 343       fprintf (dump_file, " vuses: (");
 344       for (i = 0; VEC_iterate (tree, vuses, i, vuse); i++)
 345         {
 346           print_generic_expr (dump_file, vuse, dump_flags);
 347           if (VEC_length (tree, vuses) - 1 != i)
 348             fprintf (dump_file, ",");
 349         }
 350       fprintf (dump_file, ")");
 351     }
 352   fprintf (dump_file, "\n");
 353 }
 354
 355 /* Like vn_lookup, but creates a new value for expression EXPR, if
 356    EXPR doesn't already have a value.  Return the existing/created
 357    value for EXPR.  STMT represents the stmt associated with EXPR.  It
 358    is used when computing the VUSES for EXPR.  */
 359
 360 tree
 361 vn_lookup_or_add (tree expr, tree stmt)
 362 {
 363   tree v = vn_lookup (expr, stmt);
 364   if (v == NULL_TREE)
 365     {
 366       VEC(tree,gc) *vuses;
 367
 368       v = make_value_handle (TREE_TYPE (expr));
 369       vuses = copy_vuses_from_stmt (stmt);
 370       sort_vuses (vuses);
 371
 372       if (dump_file && (dump_flags & TDF_DETAILS))
 373         print_creation_to_file (v, expr, vuses);
 374
 375       VALUE_HANDLE_VUSES (v) = vuses;
 376       vn_add_with_vuses (expr, v, vuses);
 377     }
 378
 379   set_value_handle (expr, v);
 380
 381   return v;
 382 }
 383
 384 /* Sort the VUSE array so that we can do equality comparisons
 385    quicker on two vuse vecs.  */
 386
 387 void
 388 sort_vuses (VEC (tree,gc) *vuses)
 389 {
 390   if (VEC_length (tree, vuses) > 1)
 391     qsort (VEC_address (tree, vuses),
 392            VEC_length (tree, vuses),
 393            sizeof (tree),
 394            vuses_compare);
 395 }
 396
 397 /* Like vn_lookup, but creates a new value for expression EXPR, if
 398    EXPR doesn't already have a value.  Return the existing/created
 399    value for EXPR.  STMT represents the stmt associated with EXPR.  It is used
 400    when computing the hash value for EXPR.  */
 401
 402 tree
 403 vn_lookup_or_add_with_vuses (tree expr, VEC (tree, gc) *vuses)
 404 {
 405   tree v = vn_lookup_with_vuses (expr, vuses);
 406   if (v == NULL_TREE)
 407     {
 408       v = make_value_handle (TREE_TYPE (expr));
 409       sort_vuses (vuses);
 410
 411       if (dump_file && (dump_flags & TDF_DETAILS))
 412         print_creation_to_file (v, expr, vuses);
 413
 414       VALUE_HANDLE_VUSES (v) = vuses;
 415       vn_add_with_vuses (expr, v, vuses);
 416     }
 417
 418   set_value_handle (expr, v);
 419
 420   return v;
 421 }
 422
 423 /* Initialize data structures used in value numbering.  */
 424
 425 void
 426 vn_init (void)
 427 {
 428   value_table = htab_create (511, val_expr_pair_hash,
 429                              val_expr_pair_expr_eq, free);
 430   shared_lookup_vuses = NULL;
 431 }
 432
 433 /* Delete data used for value numbering.  */
 434
 435 void
 436 vn_delete (void)
 437 {
 438   htab_delete (value_table);
 439   VEC_free (tree, gc, shared_lookup_vuses);
 440   value_table = NULL;
 441 }