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 tree stmt; 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 82 STMT is the stmt associated with EXPR for comparing virtual operands. */ 83 84hashval_t 85vn_compute (tree expr, hashval_t val, tree stmt) 86{ 87 ssa_op_iter iter; 88 tree vuse; 89 90 /* EXPR must not be a statement. We are only interested in value 91 numbering expressions on the RHS of assignments. */ 92 gcc_assert (expr); 93 gcc_assert (!expr->common.ann 94 || expr->common.ann->common.type != STMT_ANN); 95 96 val = iterative_hash_expr (expr, val); 97 98 /* If the expression has virtual uses, incorporate them into the 99 hash value computed for EXPR. */ 100 if (stmt) 101 FOR_EACH_SSA_TREE_OPERAND (vuse, stmt, iter, SSA_OP_VUSE) 102 val = iterative_hash_expr (vuse, val); 103 104 return val; 105} 106 107 108/* Compare two expressions E1 and E2 and return true if they are 109 equal. */ 110 111bool 112expressions_equal_p (tree e1, tree e2) 113{ 114 tree te1, te2; 115 116 if (e1 == e2) 117 return true; 118 119 te1 = TREE_TYPE (e1); 120 te2 = TREE_TYPE (e2); 121 122 if (TREE_CODE (e1) == TREE_LIST && TREE_CODE (e2) == TREE_LIST) 123 { 124 tree lop1 = e1; 125 tree lop2 = e2; 126 for (lop1 = e1, lop2 = e2; 127 lop1 || lop2; 128 lop1 = TREE_CHAIN (lop1), lop2 = TREE_CHAIN (lop2)) 129 { 130 if (!lop1 || !lop2) 131 return false; 132 if (!expressions_equal_p (TREE_VALUE (lop1), TREE_VALUE (lop2))) 133 return false; 134 } 135 return true; 136 137 } 138 else if (TREE_CODE (e1) == TREE_CODE (e2) 139 && (te1 == te2 || lang_hooks.types_compatible_p (te1, te2)) 140 && operand_equal_p (e1, e2, OEP_PURE_SAME)) 141 return true; 142 143 return false; 144} 145 146 147/* Hash a {v,e} pair that is pointed to by P. 148 The hashcode is cached in the val_expr_pair, so we just return 149 that. */ 150 151static hashval_t 152val_expr_pair_hash (const void *p) 153{ 154 const val_expr_pair_t ve = (val_expr_pair_t) p; 155 return ve->hashcode; 156} 157 158 159/* Given two val_expr_pair_t's, return true if they represent the same 160 expression, false otherwise. 161 P1 and P2 should point to the val_expr_pair_t's to be compared. */ 162 163static int 164val_expr_pair_expr_eq (const void *p1, const void *p2) 165{ 166 bool ret; 167 const val_expr_pair_t ve1 = (val_expr_pair_t) p1; 168 const val_expr_pair_t ve2 = (val_expr_pair_t) p2; 169 170 if (! expressions_equal_p (ve1->e, ve2->e)) 171 return false; 172 173 ret = compare_ssa_operands_equal (ve1->stmt, ve2->stmt, SSA_OP_VUSE); 174 return ret; 175} 176 177 178/* Set the value handle for expression E to value V. */ 179 180static void 181set_value_handle (tree e, tree v) 182{ 183 if (TREE_CODE (e) == SSA_NAME) 184 SSA_NAME_VALUE (e) = v; 185 else if (EXPR_P (e) || DECL_P (e) || TREE_CODE (e) == TREE_LIST 186 || TREE_CODE (e) == CONSTRUCTOR) 187 get_tree_ann (e)->common.value_handle = v; 188 else 189 /* Do nothing. Constants are their own value handles. */ 190 gcc_assert (is_gimple_min_invariant (e)); 191} 192 193 194/* Insert EXPR into VALUE_TABLE with value VAL, and add expression 195 EXPR to the value set for value VAL. STMT represents the stmt 196 associated with EXPR. It is used when computing a hash value for EXPR. */ 197 198void 199vn_add (tree expr, tree val, tree stmt) 200{ 201 void **slot; 202 val_expr_pair_t new_pair; 203 204 new_pair = xmalloc (sizeof (struct val_expr_pair_d)); 205 new_pair->e = expr; 206 new_pair->v = val; 207 new_pair->stmt = stmt; 208 new_pair->hashcode = vn_compute (expr, 0, stmt); 209 slot = htab_find_slot_with_hash (value_table, new_pair, new_pair->hashcode, 210 INSERT); 211 if (*slot) 212 free (*slot); 213 *slot = (void *) new_pair; 214 215 set_value_handle (expr, val); 216 add_to_value (val, expr); 217} 218 219 220/* Search in VALUE_TABLE for an existing instance of expression EXPR, 221 and return its value, or NULL if none has been set. STMT 222 represents the stmt associated with EXPR. It is used when computing the 223 hash value for EXPR. */ 224 225tree 226vn_lookup (tree expr, tree stmt) 227{ 228 void **slot; 229 struct val_expr_pair_d vep = {NULL, NULL, NULL, 0}; 230 231 /* Constants are their own value. */ 232 if (is_gimple_min_invariant (expr)) 233 return expr; 234 235 vep.e = expr; 236 vep.stmt = stmt; 237 vep.hashcode = vn_compute (expr, 0, stmt); 238 slot = htab_find_slot_with_hash (value_table, &vep, vep.hashcode, NO_INSERT); 239 if (!slot) 240 return NULL_TREE; 241 else 242 return ((val_expr_pair_t) *slot)->v; 243} 244 245 246/* Like vn_lookup, but creates a new value for expression EXPR, if 247 EXPR doesn't already have a value. Return the existing/created 248 value for EXPR. STMT represents the stmt associated with EXPR. It is used 249 when computing the hash value for EXPR. */ 250 251tree 252vn_lookup_or_add (tree expr, tree stmt) 253{ 254 tree v = vn_lookup (expr, stmt); 255 if (v == NULL_TREE) 256 { 257 v = make_value_handle (TREE_TYPE (expr)); 258 259 if (dump_file && (dump_flags & TDF_DETAILS)) 260 { 261 fprintf (dump_file, "Created value "); 262 print_generic_expr (dump_file, v, dump_flags); 263 fprintf (dump_file, " for "); 264 print_generic_expr (dump_file, expr, dump_flags); 265 fprintf (dump_file, "\n"); 266 } 267 268 vn_add (expr, v, stmt); 269 } 270 271 set_value_handle (expr, v); 272 273 return v; 274} 275 276 277/* Get the value handle of EXPR. This is the only correct way to get 278 the value handle for a "thing". If EXPR does not have a value 279 handle associated, it returns NULL_TREE. 280 NB: If EXPR is min_invariant, this function is *required* to return EXPR. */ 281 282tree 283get_value_handle (tree expr) 284{ 285 286 if (is_gimple_min_invariant (expr)) 287 return expr; 288 289 if (TREE_CODE (expr) == SSA_NAME) 290 return SSA_NAME_VALUE (expr); 291 else if (EXPR_P (expr) || DECL_P (expr) || TREE_CODE (expr) == TREE_LIST 292 || TREE_CODE (expr) == CONSTRUCTOR) 293 { 294 tree_ann_t ann = tree_ann (expr); 295 return ((ann) ? ann->common.value_handle : NULL_TREE); 296 } 297 else 298 gcc_unreachable (); 299} 300 301 302/* Initialize data structures used in value numbering. */ 303 304void 305vn_init (void) 306{ 307 value_table = htab_create (511, val_expr_pair_hash, 308 val_expr_pair_expr_eq, free); 309} 310 311 312/* Delete data used for value numbering. */ 313 314void 315vn_delete (void) 316{ 317 htab_delete (value_table); 318 value_table = NULL; 319} 320