OSDN Git Service

* targhooks.c (default_unwind_emit, default_scalar_mode_supported_p):
[pf3gnuchains/gcc-fork.git] / gcc / tree-vn.c
1 /* Value Numbering routines for tree expressions.
2    Copyright (C) 2001, 2002, 2003, 2004 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, 59 Temple Place - Suite 330,
21 Boston, MA 02111-1307, 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   /* Virtual uses in E.  */
52   vuse_optype 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    VUSES is the set of virtual use operands associated with EXPR.  It
83    may be NULL if EXPR has no virtual operands.  */
84
85 hashval_t
86 vn_compute (tree expr, hashval_t val, vuse_optype vuses)
87 {
88   size_t i;
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   for (i = 0; i < NUM_VUSES (vuses); i++)
101     val = iterative_hash_expr (VUSE_OP (vuses, i), val);
102
103   return val;
104 }
105
106
107 /* Compare two expressions E1 and E2 and return true if they are
108    equal.  */
109
110 bool
111 expressions_equal_p (tree e1, tree e2)
112 {
113   tree te1, te2;
114   
115   if (e1 == e2)
116     return true;
117
118   te1 = TREE_TYPE (e1);
119   te2 = TREE_TYPE (e2);
120
121   if (TREE_CODE (e1) == TREE_CODE (e2) 
122       && (te1 == te2 || lang_hooks.types_compatible_p (te1, te2))
123       && operand_equal_p (e1, e2, OEP_PURE_SAME))
124     return true;
125
126   return false;
127 }
128
129
130 /* Hash a {v,e} pair that is pointed to by P.
131    The hashcode is cached in the val_expr_pair, so we just return
132    that.  */
133
134 static hashval_t
135 val_expr_pair_hash (const void *p)
136 {
137   const val_expr_pair_t ve = (val_expr_pair_t) p;
138   return ve->hashcode;
139 }
140
141
142 /* Given two val_expr_pair_t's, return true if they represent the same
143    expression, false otherwise.
144    P1 and P2 should point to the val_expr_pair_t's to be compared.  */
145
146 static int
147 val_expr_pair_expr_eq (const void *p1, const void *p2)
148 {
149   const val_expr_pair_t ve1 = (val_expr_pair_t) p1;
150   const val_expr_pair_t ve2 = (val_expr_pair_t) p2;
151   size_t i;
152
153   if (! expressions_equal_p (ve1->e, ve2->e))
154     return false;
155
156   if (NUM_VUSES (ve1->vuses) != NUM_VUSES (ve2->vuses))
157     return false;
158   
159   for (i = 0; i < NUM_VUSES (ve1->vuses); i++)
160     if (! expressions_equal_p (VUSE_OP (ve1->vuses, i),
161                                VUSE_OP (ve2->vuses, i)))
162       return false;
163   
164   return true;
165 }
166
167
168 /* Set the value handle for expression E to value V */
169    
170 static void
171 set_value_handle (tree e, tree v)
172 {
173   if (TREE_CODE (e) == SSA_NAME)
174     SSA_NAME_VALUE (e) = v;
175   else if (EXPR_P (e) || DECL_P (e))
176     get_tree_ann (e)->common.value_handle = v;
177   else
178     /* Do nothing.  Constants are their own value handles.  */
179     gcc_assert (is_gimple_min_invariant (e));
180 }
181
182
183 /* Insert EXPR into VALUE_TABLE with value VAL, and add expression
184    EXPR to the value set for value VAL.  VUSES represent the virtual
185    use operands associated with EXPR (if any).  They are used when
186    computing the hash value for EXPR.  */
187
188 void
189 vn_add (tree expr, tree val, vuse_optype vuses)
190 {
191   void **slot;
192   val_expr_pair_t new_pair;
193   
194   new_pair = xmalloc (sizeof (struct val_expr_pair_d));
195   new_pair->e = expr;
196   new_pair->v = val;
197   new_pair->vuses = vuses;
198   new_pair->hashcode = vn_compute (expr, 0, vuses);
199   slot = htab_find_slot_with_hash (value_table, new_pair, new_pair->hashcode,
200                                    INSERT);
201   if (*slot)
202     free (*slot);
203   *slot = (void *) new_pair;
204
205   set_value_handle (expr, val);
206   add_to_value (val, expr);
207 }
208
209
210 /* Search in VALUE_TABLE for an existing instance of expression EXPR,
211    and return its value, or NULL if none has been set.  VUSES
212    represent the virtual use operands associated with EXPR (if any).
213    They are used when computing the hash value for EXPR.  */
214
215 tree
216 vn_lookup (tree expr, vuse_optype vuses)
217 {
218   void **slot;
219   struct val_expr_pair_d vep = {NULL, NULL, NULL, 0};
220
221   /* Constants are their own value.  */
222   if (is_gimple_min_invariant (expr))
223     return expr;
224
225   vep.e = expr;
226   vep.vuses = vuses;
227   vep.hashcode = vn_compute (expr, 0, vuses); 
228   slot = htab_find_slot_with_hash (value_table, &vep, vep.hashcode, NO_INSERT);
229   if (!slot)
230     return NULL_TREE;
231   else
232     return ((val_expr_pair_t) *slot)->v;
233 }
234
235
236 /* Like vn_lookup, but creates a new value for expression EXPR, if
237    EXPR doesn't already have a value.  Return the existing/created
238    value for EXPR.  VUSES represent the virtual use operands
239    associated with EXPR (if any).  They are used when computing the
240    hash value for EXPR.  */
241
242 tree
243 vn_lookup_or_add (tree expr, vuse_optype vuses)
244 {
245   tree v = vn_lookup (expr, vuses);
246   if (v == NULL_TREE)
247     {
248       v = make_value_handle (TREE_TYPE (expr));
249
250       if (dump_file && (dump_flags & TDF_DETAILS))
251         {     
252           fprintf (dump_file, "Created value ");
253           print_generic_expr (dump_file, v, dump_flags);
254           fprintf (dump_file, " for ");
255           print_generic_expr (dump_file, expr, dump_flags);
256           fprintf (dump_file, "\n");
257         }
258
259       vn_add (expr, v, vuses);
260     }
261
262   set_value_handle (expr, v);
263
264   return v;
265 }
266
267
268 /* Get the value handle of EXPR.  This is the only correct way to get
269    the value handle for a "thing".  If EXPR does not have a value
270    handle associated, it returns NULL_TREE.  */
271
272 tree
273 get_value_handle (tree expr)
274 {
275   if (TREE_CODE (expr) == SSA_NAME)
276     return SSA_NAME_VALUE (expr);
277   else if (EXPR_P (expr) || DECL_P (expr))
278     {
279       tree_ann_t ann = tree_ann (expr);
280       return ((ann) ? ann->common.value_handle : NULL_TREE);
281     }
282   else
283     {
284       gcc_assert (is_gimple_min_invariant (expr));
285       return expr;
286     }
287 }
288
289
290 /* Initialize data structures used in value numbering.  */
291
292 void
293 vn_init (void)
294 {
295   value_table = htab_create (511, val_expr_pair_hash,
296                              val_expr_pair_expr_eq, free);
297 }
298
299
300 /* Delete data used for value numbering.  */
301
302 void
303 vn_delete (void)
304 {
305   htab_delete (value_table);
306   value_table = NULL;
307 }