1169689Skan/* Value Numbering routines for tree expressions. 2169689Skan Copyright (C) 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc. 3169689Skan Contributed by Daniel Berlin <dan@dberlin.org>, Steven Bosscher 4169689Skan <stevenb@suse.de> and Diego Novillo <dnovillo@redhat.com> 5169689Skan 6169689SkanThis file is part of GCC. 7169689Skan 8169689SkanGCC is free software; you can redistribute it and/or modify 9169689Skanit under the terms of the GNU General Public License as published by 10169689Skanthe Free Software Foundation; either version 2, or (at your option) 11169689Skanany later version. 12169689Skan 13169689SkanGCC is distributed in the hope that it will be useful, 14169689Skanbut WITHOUT ANY WARRANTY; without even the implied warranty of 15169689SkanMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 16169689SkanGNU General Public License for more details. 17169689Skan 18169689SkanYou should have received a copy of the GNU General Public License 19169689Skanalong with GCC; see the file COPYING. If not, write to 20169689Skanthe Free Software Foundation, 51 Franklin Street, Fifth Floor, 21169689SkanBoston, MA 02110-1301, USA. */ 22169689Skan 23169689Skan#include "config.h" 24169689Skan#include "system.h" 25169689Skan#include "coretypes.h" 26169689Skan#include "tm.h" 27169689Skan#include "ggc.h" 28169689Skan#include "tree.h" 29169689Skan#include "tree-flow.h" 30169689Skan#include "hashtab.h" 31169689Skan#include "langhooks.h" 32169689Skan#include "tree-pass.h" 33169689Skan#include "tree-dump.h" 34169689Skan#include "diagnostic.h" 35169689Skan 36169689Skan/* The value table that maps expressions to values. */ 37169689Skanstatic htab_t value_table; 38169689Skan 39169689Skan/* Map expressions to values. These are simple pairs of expressions 40169689Skan and the values they represent. To find the value represented by 41169689Skan an expression, we use a hash table where the elements are {e,v} 42169689Skan pairs, and the expression is the key. */ 43169689Skantypedef struct val_expr_pair_d 44169689Skan{ 45169689Skan /* Value handle. */ 46169689Skan tree v; 47169689Skan 48169689Skan /* Associated expression. */ 49169689Skan tree e; 50169689Skan 51169689Skan /* For comparing virtual uses in E. */ 52169689Skan VEC (tree, gc) *vuses; 53169689Skan 54169689Skan /* E's hash value. */ 55169689Skan hashval_t hashcode; 56169689Skan} *val_expr_pair_t; 57169689Skan 58169689Skanstatic void set_value_handle (tree e, tree v); 59169689Skan 60169689Skan 61169689Skan/* Create and return a new value handle node of type TYPE. */ 62169689Skan 63169689Skanstatic tree 64169689Skanmake_value_handle (tree type) 65169689Skan{ 66169689Skan static unsigned int id = 0; 67169689Skan tree vh; 68169689Skan 69169689Skan vh = build0 (VALUE_HANDLE, type); 70169689Skan VALUE_HANDLE_ID (vh) = id++; 71169689Skan return vh; 72169689Skan} 73169689Skan 74169689Skan 75169689Skan/* Given an expression EXPR, compute a hash value number using the 76169689Skan code of the expression, its real operands and virtual operands (if 77169689Skan any). 78169689Skan 79169689Skan VAL can be used to iterate by passing previous value numbers (it is 80169689Skan used by iterative_hash_expr). */ 81169689Skan 82169689Skanhashval_t 83169689Skanvn_compute (tree expr, hashval_t val) 84169689Skan{ 85169689Skan /* EXPR must not be a statement. We are only interested in value 86169689Skan numbering expressions on the RHS of assignments. */ 87169689Skan gcc_assert (expr); 88169689Skan gcc_assert (!expr->common.ann 89169689Skan || expr->common.ann->common.type != STMT_ANN); 90169689Skan 91169689Skan val = iterative_hash_expr (expr, val); 92169689Skan return val; 93169689Skan} 94169689Skan 95169689Skan/* Compare two expressions E1 and E2 and return true if they are 96169689Skan equal. */ 97169689Skan 98169689Skanbool 99169689Skanexpressions_equal_p (tree e1, tree e2) 100169689Skan{ 101169689Skan tree te1, te2; 102169689Skan 103169689Skan if (e1 == e2) 104169689Skan return true; 105169689Skan 106169689Skan te1 = TREE_TYPE (e1); 107169689Skan te2 = TREE_TYPE (e2); 108169689Skan 109169689Skan if (TREE_CODE (e1) == TREE_LIST && TREE_CODE (e2) == TREE_LIST) 110169689Skan { 111169689Skan tree lop1 = e1; 112169689Skan tree lop2 = e2; 113169689Skan for (lop1 = e1, lop2 = e2; 114169689Skan lop1 || lop2; 115169689Skan lop1 = TREE_CHAIN (lop1), lop2 = TREE_CHAIN (lop2)) 116169689Skan { 117169689Skan if (!lop1 || !lop2) 118169689Skan return false; 119169689Skan if (!expressions_equal_p (TREE_VALUE (lop1), TREE_VALUE (lop2))) 120169689Skan return false; 121169689Skan } 122169689Skan return true; 123169689Skan 124169689Skan } 125169689Skan else if (TREE_CODE (e1) == TREE_CODE (e2) 126169689Skan && (te1 == te2 || lang_hooks.types_compatible_p (te1, te2)) 127169689Skan && operand_equal_p (e1, e2, OEP_PURE_SAME)) 128169689Skan return true; 129169689Skan 130169689Skan return false; 131169689Skan} 132169689Skan 133169689Skan 134169689Skan/* Hash a {v,e} pair that is pointed to by P. 135169689Skan The hashcode is cached in the val_expr_pair, so we just return 136169689Skan that. */ 137169689Skan 138169689Skanstatic hashval_t 139169689Skanval_expr_pair_hash (const void *p) 140169689Skan{ 141169689Skan const val_expr_pair_t ve = (val_expr_pair_t) p; 142169689Skan return ve->hashcode; 143169689Skan} 144169689Skan 145169689Skan 146169689Skan/* Given two val_expr_pair_t's, return true if they represent the same 147169689Skan expression, false otherwise. 148169689Skan P1 and P2 should point to the val_expr_pair_t's to be compared. */ 149169689Skan 150169689Skanstatic int 151169689Skanval_expr_pair_expr_eq (const void *p1, const void *p2) 152169689Skan{ 153169689Skan int i; 154169689Skan tree vuse1; 155169689Skan const val_expr_pair_t ve1 = (val_expr_pair_t) p1; 156169689Skan const val_expr_pair_t ve2 = (val_expr_pair_t) p2; 157169689Skan 158169689Skan if (! expressions_equal_p (ve1->e, ve2->e)) 159169689Skan return false; 160169689Skan 161169689Skan if (ve1->vuses == ve2->vuses) 162169689Skan return true; 163169689Skan 164169689Skan if (VEC_length (tree, ve1->vuses) != VEC_length (tree, ve2->vuses)) 165169689Skan return false; 166169689Skan 167169689Skan for (i = 0; VEC_iterate (tree, ve1->vuses, i, vuse1); i++) 168169689Skan { 169169689Skan if (VEC_index (tree, ve2->vuses, i) != vuse1) 170169689Skan return false; 171169689Skan } 172169689Skan return true; 173169689Skan} 174169689Skan 175169689Skan 176169689Skan/* Set the value handle for expression E to value V. */ 177169689Skan 178169689Skanstatic void 179169689Skanset_value_handle (tree e, tree v) 180169689Skan{ 181169689Skan if (TREE_CODE (e) == SSA_NAME) 182169689Skan SSA_NAME_VALUE (e) = v; 183169689Skan else if (EXPR_P (e) || DECL_P (e) || TREE_CODE (e) == TREE_LIST 184169689Skan || TREE_CODE (e) == CONSTRUCTOR) 185169689Skan get_tree_common_ann (e)->value_handle = v; 186169689Skan else 187169689Skan /* Do nothing. Constants are their own value handles. */ 188169689Skan gcc_assert (is_gimple_min_invariant (e)); 189169689Skan} 190169689Skan 191169689Skan/* Copy the virtual uses from STMT into a newly allocated VEC(tree), 192169689Skan and return the VEC(tree). */ 193169689Skan 194169689Skanstatic VEC (tree, gc) * 195169689Skancopy_vuses_from_stmt (tree stmt) 196169689Skan{ 197169689Skan ssa_op_iter iter; 198169689Skan tree vuse; 199169689Skan VEC (tree, gc) *vuses = NULL; 200169689Skan 201169689Skan if (!stmt) 202169689Skan return NULL; 203169689Skan 204169689Skan FOR_EACH_SSA_TREE_OPERAND (vuse, stmt, iter, SSA_OP_VUSE) 205169689Skan VEC_safe_push (tree, gc, vuses, vuse); 206169689Skan 207169689Skan return vuses; 208169689Skan} 209169689Skan 210169689Skan/* Place for shared_vuses_from_stmt to shove vuses. */ 211169689Skanstatic VEC (tree, gc) *shared_lookup_vuses; 212169689Skan 213169689Skan/* Copy the virtual uses from STMT into SHARED_LOOKUP_VUSES. 214169689Skan This function will overwrite the current SHARED_LOOKUP_VUSES 215169689Skan variable. */ 216169689Skan 217169689Skanstatic VEC (tree, gc) * 218169689Skanshared_vuses_from_stmt (tree stmt) 219169689Skan{ 220169689Skan ssa_op_iter iter; 221169689Skan tree vuse; 222169689Skan 223169689Skan if (!stmt) 224169689Skan return NULL; 225169689Skan 226169689Skan VEC_truncate (tree, shared_lookup_vuses, 0); 227169689Skan 228169689Skan FOR_EACH_SSA_TREE_OPERAND (vuse, stmt, iter, SSA_OP_VUSE) 229169689Skan VEC_safe_push (tree, gc, shared_lookup_vuses, vuse); 230169689Skan 231169689Skan if (VEC_length (tree, shared_lookup_vuses) > 1) 232169689Skan sort_vuses (shared_lookup_vuses); 233169689Skan 234169689Skan return shared_lookup_vuses; 235169689Skan} 236169689Skan 237169689Skan/* Insert EXPR into VALUE_TABLE with value VAL, and add expression 238169689Skan EXPR to the value set for value VAL. */ 239169689Skan 240169689Skanvoid 241169689Skanvn_add (tree expr, tree val) 242169689Skan{ 243169689Skan vn_add_with_vuses (expr, val, NULL); 244169689Skan} 245169689Skan 246169689Skan/* Insert EXPR into VALUE_TABLE with value VAL, and add expression 247169689Skan EXPR to the value set for value VAL. VUSES represents the virtual 248169689Skan use operands associated with EXPR. It is used when computing a 249169689Skan hash value for EXPR. */ 250169689Skan 251169689Skanvoid 252169689Skanvn_add_with_vuses (tree expr, tree val, VEC (tree, gc) *vuses) 253169689Skan{ 254169689Skan void **slot; 255169689Skan val_expr_pair_t new_pair; 256169689Skan 257169689Skan new_pair = XNEW (struct val_expr_pair_d); 258169689Skan new_pair->e = expr; 259169689Skan new_pair->v = val; 260169689Skan new_pair->vuses = vuses; 261169689Skan new_pair->hashcode = vn_compute (expr, 0); 262169689Skan slot = htab_find_slot_with_hash (value_table, new_pair, new_pair->hashcode, 263169689Skan INSERT); 264169689Skan if (*slot) 265169689Skan free (*slot); 266169689Skan *slot = (void *) new_pair; 267169689Skan 268169689Skan set_value_handle (expr, val); 269169689Skan if (TREE_CODE (val) == VALUE_HANDLE) 270169689Skan add_to_value (val, expr); 271169689Skan} 272169689Skan 273169689Skan 274169689Skan/* Search in VALUE_TABLE for an existing instance of expression EXPR, 275169689Skan and return its value, or NULL if none has been set. STMT 276169689Skan represents the stmt associated with EXPR. It is used when computing the 277169689Skan hash value for EXPR. */ 278169689Skan 279169689Skantree 280169689Skanvn_lookup (tree expr, tree stmt) 281169689Skan{ 282169689Skan return vn_lookup_with_vuses (expr, shared_vuses_from_stmt (stmt)); 283169689Skan} 284169689Skan 285169689Skan/* Search in VALUE_TABLE for an existing instance of expression EXPR, 286169689Skan and return its value, or NULL if none has been set. VUSES is the 287169689Skan list of virtual use operands associated with EXPR. It is used when 288169689Skan computing the hash value for EXPR. */ 289169689Skan 290169689Skantree 291169689Skanvn_lookup_with_vuses (tree expr, VEC (tree, gc) *vuses) 292169689Skan{ 293169689Skan void **slot; 294169689Skan struct val_expr_pair_d vep = {NULL, NULL, NULL, 0}; 295169689Skan 296169689Skan /* Constants are their own value. */ 297169689Skan if (is_gimple_min_invariant (expr)) 298169689Skan return expr; 299169689Skan 300169689Skan vep.e = expr; 301169689Skan vep.vuses = vuses; 302169689Skan vep.hashcode = vn_compute (expr, 0); 303169689Skan slot = htab_find_slot_with_hash (value_table, &vep, vep.hashcode, NO_INSERT); 304169689Skan if (!slot) 305169689Skan return NULL_TREE; 306169689Skan else 307169689Skan return ((val_expr_pair_t) *slot)->v; 308169689Skan} 309169689Skan 310169689Skan 311169689Skan/* A comparison function for use in qsort to compare vuses. Simply 312169689Skan subtracts version numbers. */ 313169689Skan 314169689Skanstatic int 315169689Skanvuses_compare (const void *pa, const void *pb) 316169689Skan{ 317169689Skan const tree vusea = *((const tree *)pa); 318169689Skan const tree vuseb = *((const tree *)pb); 319169689Skan int sn = SSA_NAME_VERSION (vusea) - SSA_NAME_VERSION (vuseb); 320169689Skan 321169689Skan return sn; 322169689Skan} 323169689Skan 324169689Skan/* Print out the "Created value <x> for <Y>" statement to the 325169689Skan dump_file. 326169689Skan This is factored because both versions of lookup use it, and it 327169689Skan obscures the real work going on in those functions. */ 328169689Skan 329169689Skanstatic void 330169689Skanprint_creation_to_file (tree v, tree expr, VEC (tree, gc) *vuses) 331169689Skan{ 332169689Skan fprintf (dump_file, "Created value "); 333169689Skan print_generic_expr (dump_file, v, dump_flags); 334169689Skan fprintf (dump_file, " for "); 335169689Skan print_generic_expr (dump_file, expr, dump_flags); 336169689Skan 337169689Skan if (vuses && VEC_length (tree, vuses) != 0) 338169689Skan { 339169689Skan size_t i; 340169689Skan tree vuse; 341169689Skan 342169689Skan fprintf (dump_file, " vuses: ("); 343169689Skan for (i = 0; VEC_iterate (tree, vuses, i, vuse); i++) 344169689Skan { 345169689Skan print_generic_expr (dump_file, vuse, dump_flags); 346169689Skan if (VEC_length (tree, vuses) - 1 != i) 347169689Skan fprintf (dump_file, ","); 348169689Skan } 349169689Skan fprintf (dump_file, ")"); 350169689Skan } 351169689Skan fprintf (dump_file, "\n"); 352169689Skan} 353169689Skan 354169689Skan/* Like vn_lookup, but creates a new value for expression EXPR, if 355169689Skan EXPR doesn't already have a value. Return the existing/created 356169689Skan value for EXPR. STMT represents the stmt associated with EXPR. It 357169689Skan is used when computing the VUSES for EXPR. */ 358169689Skan 359169689Skantree 360169689Skanvn_lookup_or_add (tree expr, tree stmt) 361169689Skan{ 362169689Skan tree v = vn_lookup (expr, stmt); 363169689Skan if (v == NULL_TREE) 364169689Skan { 365169689Skan VEC(tree,gc) *vuses; 366169689Skan 367169689Skan v = make_value_handle (TREE_TYPE (expr)); 368169689Skan vuses = copy_vuses_from_stmt (stmt); 369169689Skan sort_vuses (vuses); 370169689Skan 371169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 372169689Skan print_creation_to_file (v, expr, vuses); 373169689Skan 374169689Skan VALUE_HANDLE_VUSES (v) = vuses; 375169689Skan vn_add_with_vuses (expr, v, vuses); 376169689Skan } 377169689Skan 378169689Skan set_value_handle (expr, v); 379169689Skan 380169689Skan return v; 381169689Skan} 382169689Skan 383169689Skan/* Sort the VUSE array so that we can do equality comparisons 384169689Skan quicker on two vuse vecs. */ 385169689Skan 386169689Skanvoid 387169689Skansort_vuses (VEC (tree,gc) *vuses) 388169689Skan{ 389169689Skan if (VEC_length (tree, vuses) > 1) 390169689Skan qsort (VEC_address (tree, vuses), 391169689Skan VEC_length (tree, vuses), 392169689Skan sizeof (tree), 393169689Skan vuses_compare); 394169689Skan} 395169689Skan 396169689Skan/* Like vn_lookup, but creates a new value for expression EXPR, if 397169689Skan EXPR doesn't already have a value. Return the existing/created 398169689Skan value for EXPR. STMT represents the stmt associated with EXPR. It is used 399169689Skan when computing the hash value for EXPR. */ 400169689Skan 401169689Skantree 402169689Skanvn_lookup_or_add_with_vuses (tree expr, VEC (tree, gc) *vuses) 403169689Skan{ 404169689Skan tree v = vn_lookup_with_vuses (expr, vuses); 405169689Skan if (v == NULL_TREE) 406169689Skan { 407169689Skan v = make_value_handle (TREE_TYPE (expr)); 408169689Skan sort_vuses (vuses); 409169689Skan 410169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 411169689Skan print_creation_to_file (v, expr, vuses); 412169689Skan 413169689Skan VALUE_HANDLE_VUSES (v) = vuses; 414169689Skan vn_add_with_vuses (expr, v, vuses); 415169689Skan } 416169689Skan 417169689Skan set_value_handle (expr, v); 418169689Skan 419169689Skan return v; 420169689Skan} 421169689Skan 422169689Skan 423169689Skan 424169689Skan/* Get the value handle of EXPR. This is the only correct way to get 425169689Skan the value handle for a "thing". If EXPR does not have a value 426169689Skan handle associated, it returns NULL_TREE. 427169689Skan NB: If EXPR is min_invariant, this function is *required* to return EXPR. */ 428169689Skan 429169689Skantree 430169689Skanget_value_handle (tree expr) 431169689Skan{ 432169689Skan 433169689Skan if (is_gimple_min_invariant (expr)) 434169689Skan return expr; 435169689Skan 436169689Skan if (TREE_CODE (expr) == SSA_NAME) 437169689Skan return SSA_NAME_VALUE (expr); 438169689Skan else if (EXPR_P (expr) || DECL_P (expr) || TREE_CODE (expr) == TREE_LIST 439169689Skan || TREE_CODE (expr) == CONSTRUCTOR) 440169689Skan { 441169689Skan tree_ann_common_t ann = tree_common_ann (expr); 442169689Skan return ((ann) ? ann->value_handle : NULL_TREE); 443169689Skan } 444169689Skan else 445169689Skan gcc_unreachable (); 446169689Skan} 447169689Skan 448169689Skan 449169689Skan/* Initialize data structures used in value numbering. */ 450169689Skan 451169689Skanvoid 452169689Skanvn_init (void) 453169689Skan{ 454169689Skan value_table = htab_create (511, val_expr_pair_hash, 455169689Skan val_expr_pair_expr_eq, free); 456169689Skan shared_lookup_vuses = NULL; 457169689Skan} 458169689Skan 459169689Skan 460169689Skan/* Delete data used for value numbering. */ 461169689Skan 462169689Skanvoid 463169689Skanvn_delete (void) 464169689Skan{ 465169689Skan htab_delete (value_table); 466169689Skan VEC_free (tree, gc, shared_lookup_vuses); 467169689Skan value_table = NULL; 468169689Skan} 469