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->common.ann
  89               || expr->common.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            || TREE_CODE (e) == CONSTRUCTOR)
 185     get_tree_ann (e)->common.value_handle = v;
 186   else
 187     /* Do nothing.  Constants are their own value handles.  */
 188     gcc_assert (is_gimple_min_invariant (e));
 189 }
 190
 191 /* Copy the virtual uses from STMT into a newly allocated VEC(tree),
 192    and return the VEC(tree).  */
 193
 194 static VEC (tree, gc) *
 195 copy_vuses_from_stmt (tree stmt)
 196 {
 197   ssa_op_iter iter;
 198   tree vuse;
 199   VEC (tree, gc) *vuses = NULL;
 200
 201   if (!stmt)
 202     return NULL;
 203
 204   FOR_EACH_SSA_TREE_OPERAND (vuse, stmt, iter, SSA_OP_VUSE)
 205     VEC_safe_push (tree, gc, vuses, vuse);
 206
 207   return vuses;
 208 }
 209
 210 /* Place for shared_vuses_from_stmt to shove vuses.  */
 211 static VEC (tree, gc) *shared_lookup_vuses;
 212
 213 /* Copy the virtual uses from STMT into SHARED_LOOKUP_VUSES.
 214    This function will overwrite the current SHARED_LOOKUP_VUSES
 215    variable.  */
 216
 217 static VEC (tree, gc) *
 218 shared_vuses_from_stmt (tree stmt)
 219 {
 220   ssa_op_iter iter;
 221   tree vuse;
 222
 223   if (!stmt)
 224     return NULL;
 225
 226   VEC_truncate (tree, shared_lookup_vuses, 0);
 227
 228   FOR_EACH_SSA_TREE_OPERAND (vuse, stmt, iter, SSA_OP_VUSE)
 229     VEC_safe_push (tree, gc, shared_lookup_vuses, vuse);
 230
 231   if (VEC_length (tree, shared_lookup_vuses) > 1)
 232     sort_vuses (shared_lookup_vuses);
 233
 234   return shared_lookup_vuses;
 235 }
 236
 237 /* Insert EXPR into VALUE_TABLE with value VAL, and add expression
 238    EXPR to the value set for value VAL.  */
 239
 240 void
 241 vn_add (tree expr, tree val)
 242 {
 243   vn_add_with_vuses (expr, val, NULL);
 244 }
 245
 246 /* Insert EXPR into VALUE_TABLE with value VAL, and add expression
 247    EXPR to the value set for value VAL.  VUSES represents the virtual
 248    use operands associated with EXPR.  It is used when computing a
 249    hash value for EXPR.  */
 250
 251 void
 252 vn_add_with_vuses (tree expr, tree val, VEC (tree, gc) *vuses)
 253 {
 254   void **slot;
 255   val_expr_pair_t new_pair;
 256
 257   new_pair = XNEW (struct val_expr_pair_d);
 258   new_pair->e = expr;
 259   new_pair->v = val;
 260   new_pair->vuses = vuses;
 261   new_pair->hashcode = vn_compute (expr, 0);
 262   slot = htab_find_slot_with_hash (value_table, new_pair, new_pair->hashcode,
 263                                    INSERT);
 264   if (*slot)
 265     free (*slot);
 266   *slot = (void *) new_pair;
 267
 268   set_value_handle (expr, val);
 269   if (TREE_CODE (val) == VALUE_HANDLE)
 270     add_to_value (val, expr);
 271 }
 272
 273
 274 /* Search in VALUE_TABLE for an existing instance of expression EXPR,
 275    and return its value, or NULL if none has been set.  STMT
 276    represents the stmt associated with EXPR.  It is used when computing the
 277    hash value for EXPR.  */
 278
 279 tree
 280 vn_lookup (tree expr, tree stmt)
 281 {
 282   return vn_lookup_with_vuses (expr, shared_vuses_from_stmt (stmt));
 283 }
 284
 285 /* Search in VALUE_TABLE for an existing instance of expression EXPR,
 286    and return its value, or NULL if none has been set.  VUSES is the
 287    list of virtual use operands associated with EXPR.  It is used when
 288    computing the hash value for EXPR.  */
 289
 290 tree
 291 vn_lookup_with_vuses (tree expr, VEC (tree, gc) *vuses)
 292 {
 293   void **slot;
 294   struct val_expr_pair_d vep = {NULL, NULL, NULL, 0};
 295
 296   /* Constants are their own value.  */
 297   if (is_gimple_min_invariant (expr))
 298     return expr;
 299
 300   vep.e = expr;
 301   vep.vuses = vuses;
 302   vep.hashcode = vn_compute (expr, 0);
 303   slot = htab_find_slot_with_hash (value_table, &vep, vep.hashcode, NO_INSERT);
 304   if (!slot)
 305     return NULL_TREE;
 306   else
 307     return ((val_expr_pair_t) *slot)->v;
 308 }
 309
 310
 311 /* A comparison function for use in qsort to compare vuses.  Simply
 312    subtracts version numbers.  */
 313
 314 static int
 315 vuses_compare (const void *pa, const void *pb)
 316 {
 317   const tree vusea = *((const tree *)pa);
 318   const tree vuseb = *((const tree *)pb);
 319   int sn = SSA_NAME_VERSION (vusea) - SSA_NAME_VERSION (vuseb);
 320
 321   return sn;
 322 }
 323
 324 /* Print out the "Created value <x> for <Y>" statement to the
 325    dump_file.
 326    This is factored because both versions of lookup use it, and it
 327    obscures the real work going on in those functions.  */
 328
 329 static void
 330 print_creation_to_file (tree v, tree expr, VEC (tree, gc) *vuses)
 331 {
 332   fprintf (dump_file, "Created value ");
 333   print_generic_expr (dump_file, v, dump_flags);
 334   fprintf (dump_file, " for ");
 335   print_generic_expr (dump_file, expr, dump_flags);
 336
 337   if (vuses && VEC_length (tree, vuses) != 0)
 338     {
 339       size_t i;
 340       tree vuse;
 341
 342       fprintf (dump_file, " vuses: (");
 343       for (i = 0; VEC_iterate (tree, vuses, i, vuse); i++)
 344         {
 345           print_generic_expr (dump_file, vuse, dump_flags);
 346           if (VEC_length (tree, vuses) - 1 != i)
 347             fprintf (dump_file, ",");
 348         }
 349       fprintf (dump_file, ")");
 350     }
 351   fprintf (dump_file, "\n");
 352 }
 353
 354 /* Like vn_lookup, but creates a new value for expression EXPR, if
 355    EXPR doesn't already have a value.  Return the existing/created
 356    value for EXPR.  STMT represents the stmt associated with EXPR.  It
 357    is used when computing the VUSES for EXPR.  */
 358
 359 tree
 360 vn_lookup_or_add (tree expr, tree stmt)
 361 {
 362   tree v = vn_lookup (expr, stmt);
 363   if (v == NULL_TREE)
 364     {
 365       VEC(tree,gc) *vuses;
 366
 367       v = make_value_handle (TREE_TYPE (expr));
 368       vuses = copy_vuses_from_stmt (stmt);
 369       sort_vuses (vuses);
 370
 371       if (dump_file && (dump_flags & TDF_DETAILS))
 372         print_creation_to_file (v, expr, vuses);
 373
 374       VALUE_HANDLE_VUSES (v) = vuses;
 375       vn_add_with_vuses (expr, v, vuses);
 376     }
 377
 378   set_value_handle (expr, v);
 379
 380   return v;
 381 }
 382
 383 /* Sort the VUSE array so that we can do equality comparisons
 384    quicker on two vuse vecs.  */
 385
 386 void
 387 sort_vuses (VEC (tree,gc) *vuses)
 388 {
 389   if (VEC_length (tree, vuses) > 1)
 390     qsort (VEC_address (tree, vuses),
 391            VEC_length (tree, vuses),
 392            sizeof (tree),
 393            vuses_compare);
 394 }
 395
 396 /* Like vn_lookup, but creates a new value for expression EXPR, if
 397    EXPR doesn't already have a value.  Return the existing/created
 398    value for EXPR.  STMT represents the stmt associated with EXPR.  It is used
 399    when computing the hash value for EXPR.  */
 400
 401 tree
 402 vn_lookup_or_add_with_vuses (tree expr, VEC (tree, gc) *vuses)
 403 {
 404   tree v = vn_lookup_with_vuses (expr, vuses);
 405   if (v == NULL_TREE)
 406     {
 407       v = make_value_handle (TREE_TYPE (expr));
 408       sort_vuses (vuses);
 409
 410       if (dump_file && (dump_flags & TDF_DETAILS))
 411         print_creation_to_file (v, expr, vuses);
 412
 413       VALUE_HANDLE_VUSES (v) = vuses;
 414       vn_add_with_vuses (expr, v, vuses);
 415     }
 416
 417   set_value_handle (expr, v);
 418
 419   return v;
 420 }
 421
 422
 423
 424 /* Get the value handle of EXPR.  This is the only correct way to get
 425    the value handle for a "thing".  If EXPR does not have a value
 426    handle associated, it returns NULL_TREE.
 427    NB: If EXPR is min_invariant, this function is *required* to return EXPR.  */
 428
 429 tree
 430 get_value_handle (tree expr)
 431 {
 432
 433   if (is_gimple_min_invariant (expr))
 434     return expr;
 435
 436   if (TREE_CODE (expr) == SSA_NAME)
 437     return SSA_NAME_VALUE (expr);
 438   else if (EXPR_P (expr) || DECL_P (expr) || TREE_CODE (expr) == TREE_LIST
 439            || TREE_CODE (expr) == CONSTRUCTOR)
 440     {
 441       tree_ann_t ann = tree_ann (expr);
 442       return ((ann) ? ann->common.value_handle : NULL_TREE);
 443     }
 444   else
 445     gcc_unreachable ();
 446 }
 447
 448
 449 /* Initialize data structures used in value numbering.  */
 450
 451 void
 452 vn_init (void)
 453 {
 454   value_table = htab_create (511, val_expr_pair_hash,
 455                              val_expr_pair_expr_eq, free);
 456   shared_lookup_vuses = NULL;
 457 }
 458
 459
 460 /* Delete data used for value numbering.  */
 461
 462 void
 463 vn_delete (void)
 464 {
 465   htab_delete (value_table);
 466   VEC_free (tree, gc, shared_lookup_vuses);
 467   value_table = NULL;
 468 }