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 6This file is part of GCC. 7 8GCC is free software; you can redistribute it and/or modify 9it under the terms of the GNU General Public License as published by 10the Free Software Foundation; either version 2, or (at your option) 11any later version. 12 13GCC is distributed in the hope that it will be useful, 14but WITHOUT ANY WARRANTY; without even the implied warranty of 15MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 16GNU General Public License for more details. 17 18You should have received a copy of the GNU General Public License 19along with GCC; see the file COPYING. If not, write to 20the Free Software Foundation, 51 Franklin Street, Fifth Floor, 21Boston, 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. */ 37static 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. */ 43typedef 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 58static void set_value_handle (tree e, tree v); 59 60 61/* Create and return a new value handle node of type TYPE. */ 62 63static tree 64make_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 82hashval_t 83vn_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 98bool 99expressions_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 138static hashval_t 139val_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 150static int 151val_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 178static void 179set_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_common_ann (e)->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 194static VEC (tree, gc) * 195copy_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. */ 211static 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 217static VEC (tree, gc) * 218shared_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 240void 241vn_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 251void 252vn_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 279tree 280vn_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 290tree 291vn_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 314static int 315vuses_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 329static void 330print_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 359tree 360vn_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 386void 387sort_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 401tree 402vn_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 429tree 430get_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_common_t ann = tree_common_ann (expr); 442 return ((ann) ? ann->value_handle : NULL_TREE); 443 } 444 else 445 gcc_unreachable (); 446} 447 448 449/* Initialize data structures used in value numbering. */ 450 451void 452vn_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 462void 463vn_delete (void) 464{ 465 htab_delete (value_table); 466 VEC_free (tree, gc, shared_lookup_vuses); 467 value_table = NULL; 468} 469