OpenCores
URL https://opencores.org/ocsvn/openrisc_me/openrisc_me/trunk

Subversion Repositories openrisc_me

[/] [openrisc/] [trunk/] [gnu-src/] [gcc-4.2.2/] [gcc/] [tree-vn.c] - Blame information for rev 304

Go to most recent revision | Details | Compare with Previous | View Log

Line No. Rev Author Line
1 38 julius
/* Value Numbering routines for tree expressions.
2
   Copyright (C) 2001, 2002, 2003, 2004, 2005, 2007 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 3, 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 COPYING3.  If not see
20
<http://www.gnu.org/licenses/>.  */
21
 
22
#include "config.h"
23
#include "system.h"
24
#include "coretypes.h"
25
#include "tm.h"
26
#include "ggc.h"
27
#include "tree.h"
28
#include "tree-flow.h"
29
#include "hashtab.h"
30
#include "langhooks.h"
31
#include "tree-pass.h"
32
#include "tree-dump.h"
33
#include "diagnostic.h"
34
 
35
/* The value table that maps expressions to values.  */
36
static htab_t value_table;
37
 
38
/* Map expressions to values.  These are simple pairs of expressions
39
   and the values they represent.  To find the value represented by
40
   an expression, we use a hash table where the elements are {e,v}
41
   pairs, and the expression is the key.  */
42
typedef struct val_expr_pair_d
43
{
44
  /* Value handle.  */
45
  tree v;
46
 
47
  /* Associated expression.  */
48
  tree e;
49
 
50
  /* For comparing virtual uses in E.  */
51
  VEC (tree, gc) *vuses;
52
 
53
  /* E's hash value.  */
54
  hashval_t hashcode;
55
} *val_expr_pair_t;
56
 
57
static void set_value_handle (tree e, tree v);
58
 
59
 
60
/* Create and return a new value handle node of type TYPE.  */
61
 
62
static tree
63
make_value_handle (tree type)
64
{
65
  static unsigned int id = 0;
66
  tree vh;
67
 
68
  vh = build0 (VALUE_HANDLE, type);
69
  VALUE_HANDLE_ID (vh) = id++;
70
  return vh;
71
}
72
 
73
 
74
/* Given an expression EXPR, compute a hash value number using the
75
   code of the expression, its real operands and virtual operands (if
76
   any).
77
 
78
   VAL can be used to iterate by passing previous value numbers (it is
79
   used by iterative_hash_expr).  */
80
 
81
hashval_t
82
vn_compute (tree expr, hashval_t val)
83
{
84
  /* EXPR must not be a statement.  We are only interested in value
85
     numbering expressions on the RHS of assignments.  */
86
  gcc_assert (expr);
87
  gcc_assert (!expr->common.ann
88
              || expr->common.ann->common.type != STMT_ANN);
89
 
90
  val = iterative_hash_expr (expr, val);
91
  return val;
92
}
93
 
94
/* Compare two expressions E1 and E2 and return true if they are
95
   equal.  */
96
 
97
bool
98
expressions_equal_p (tree e1, tree e2)
99
{
100
  tree te1, te2;
101
 
102
  if (e1 == e2)
103
    return true;
104
 
105
  te1 = TREE_TYPE (e1);
106
  te2 = TREE_TYPE (e2);
107
 
108
  if (TREE_CODE (e1) == TREE_LIST && TREE_CODE (e2) == TREE_LIST)
109
    {
110
      tree lop1 = e1;
111
      tree lop2 = e2;
112
      for (lop1 = e1, lop2 = e2;
113
           lop1 || lop2;
114
           lop1 = TREE_CHAIN (lop1), lop2 = TREE_CHAIN (lop2))
115
        {
116
          if (!lop1 || !lop2)
117
            return false;
118
          if (!expressions_equal_p (TREE_VALUE (lop1), TREE_VALUE (lop2)))
119
            return false;
120
        }
121
      return true;
122
 
123
    }
124
  else if (TREE_CODE (e1) == TREE_CODE (e2)
125
           && (te1 == te2 || lang_hooks.types_compatible_p (te1, te2))
126
           && operand_equal_p (e1, e2, OEP_PURE_SAME))
127
    return true;
128
 
129
  return false;
130
}
131
 
132
 
133
/* Hash a {v,e} pair that is pointed to by P.
134
   The hashcode is cached in the val_expr_pair, so we just return
135
   that.  */
136
 
137
static hashval_t
138
val_expr_pair_hash (const void *p)
139
{
140
  const val_expr_pair_t ve = (val_expr_pair_t) p;
141
  return ve->hashcode;
142
}
143
 
144
 
145
/* Given two val_expr_pair_t's, return true if they represent the same
146
   expression, false otherwise.
147
   P1 and P2 should point to the val_expr_pair_t's to be compared.  */
148
 
149
static int
150
val_expr_pair_expr_eq (const void *p1, const void *p2)
151
{
152
  int i;
153
  tree vuse1;
154
  const val_expr_pair_t ve1 = (val_expr_pair_t) p1;
155
  const val_expr_pair_t ve2 = (val_expr_pair_t) p2;
156
 
157
  if (! expressions_equal_p (ve1->e, ve2->e))
158
    return false;
159
 
160
  if (ve1->vuses == ve2->vuses)
161
    return true;
162
 
163
  if (VEC_length (tree, ve1->vuses) != VEC_length (tree, ve2->vuses))
164
    return false;
165
 
166
  for (i = 0; VEC_iterate (tree, ve1->vuses, i, vuse1); i++)
167
    {
168
      if (VEC_index (tree, ve2->vuses, i) != vuse1)
169
        return false;
170
    }
171
  return true;
172
}
173
 
174
 
175
/* Set the value handle for expression E to value V.  */
176
 
177
static void
178
set_value_handle (tree e, tree v)
179
{
180
  if (TREE_CODE (e) == SSA_NAME)
181
    SSA_NAME_VALUE (e) = v;
182
  else if (EXPR_P (e) || DECL_P (e) || TREE_CODE (e) == TREE_LIST
183
           || TREE_CODE (e) == CONSTRUCTOR)
184
    get_tree_common_ann (e)->value_handle = v;
185
  else
186
    /* Do nothing.  Constants are their own value handles.  */
187
    gcc_assert (is_gimple_min_invariant (e));
188
}
189
 
190
/* Copy the virtual uses from STMT into a newly allocated VEC(tree),
191
   and return the VEC(tree).  */
192
 
193
static VEC (tree, gc) *
194
copy_vuses_from_stmt (tree stmt)
195
{
196
  ssa_op_iter iter;
197
  tree vuse;
198
  VEC (tree, gc) *vuses = NULL;
199
 
200
  if (!stmt)
201
    return NULL;
202
 
203
  FOR_EACH_SSA_TREE_OPERAND (vuse, stmt, iter, SSA_OP_VUSE)
204
    VEC_safe_push (tree, gc, vuses, vuse);
205
 
206
  return vuses;
207
}
208
 
209
/* Place for shared_vuses_from_stmt to shove vuses.  */
210
static VEC (tree, gc) *shared_lookup_vuses;
211
 
212
/* Copy the virtual uses from STMT into SHARED_LOOKUP_VUSES.
213
   This function will overwrite the current SHARED_LOOKUP_VUSES
214
   variable.  */
215
 
216
static VEC (tree, gc) *
217
shared_vuses_from_stmt (tree stmt)
218
{
219
  ssa_op_iter iter;
220
  tree vuse;
221
 
222
  if (!stmt)
223
    return NULL;
224
 
225
  VEC_truncate (tree, shared_lookup_vuses, 0);
226
 
227
  FOR_EACH_SSA_TREE_OPERAND (vuse, stmt, iter, SSA_OP_VUSE)
228
    VEC_safe_push (tree, gc, shared_lookup_vuses, vuse);
229
 
230
  if (VEC_length (tree, shared_lookup_vuses) > 1)
231
    sort_vuses (shared_lookup_vuses);
232
 
233
  return shared_lookup_vuses;
234
}
235
 
236
/* Insert EXPR into VALUE_TABLE with value VAL, and add expression
237
   EXPR to the value set for value VAL.  */
238
 
239
void
240
vn_add (tree expr, tree val)
241
{
242
  vn_add_with_vuses (expr, val, NULL);
243
}
244
 
245
/* Insert EXPR into VALUE_TABLE with value VAL, and add expression
246
   EXPR to the value set for value VAL.  VUSES represents the virtual
247
   use operands associated with EXPR.  It is used when computing a
248
   hash value for EXPR.  */
249
 
250
void
251
vn_add_with_vuses (tree expr, tree val, VEC (tree, gc) *vuses)
252
{
253
  void **slot;
254
  val_expr_pair_t new_pair;
255
 
256
  new_pair = XNEW (struct val_expr_pair_d);
257
  new_pair->e = expr;
258
  new_pair->v = val;
259
  new_pair->vuses = vuses;
260
  new_pair->hashcode = vn_compute (expr, 0);
261
  slot = htab_find_slot_with_hash (value_table, new_pair, new_pair->hashcode,
262
                                   INSERT);
263
  if (*slot)
264
    free (*slot);
265
  *slot = (void *) new_pair;
266
 
267
  set_value_handle (expr, val);
268
  if (TREE_CODE (val) == VALUE_HANDLE)
269
    add_to_value (val, expr);
270
}
271
 
272
 
273
/* Search in VALUE_TABLE for an existing instance of expression EXPR,
274
   and return its value, or NULL if none has been set.  STMT
275
   represents the stmt associated with EXPR.  It is used when computing the
276
   hash value for EXPR.  */
277
 
278
tree
279
vn_lookup (tree expr, tree stmt)
280
{
281
  return vn_lookup_with_vuses (expr, shared_vuses_from_stmt (stmt));
282
}
283
 
284
/* Search in VALUE_TABLE for an existing instance of expression EXPR,
285
   and return its value, or NULL if none has been set.  VUSES is the
286
   list of virtual use operands associated with EXPR.  It is used when
287
   computing the hash value for EXPR.  */
288
 
289
tree
290
vn_lookup_with_vuses (tree expr, VEC (tree, gc) *vuses)
291
{
292
  void **slot;
293
  struct val_expr_pair_d vep = {NULL, NULL, NULL, 0};
294
 
295
  /* Constants are their own value.  */
296
  if (is_gimple_min_invariant (expr))
297
    return expr;
298
 
299
  vep.e = expr;
300
  vep.vuses = vuses;
301
  vep.hashcode = vn_compute (expr, 0);
302
  slot = htab_find_slot_with_hash (value_table, &vep, vep.hashcode, NO_INSERT);
303
  if (!slot)
304
    return NULL_TREE;
305
  else
306
    return ((val_expr_pair_t) *slot)->v;
307
}
308
 
309
 
310
/* A comparison function for use in qsort to compare vuses.  Simply
311
   subtracts version numbers.  */
312
 
313
static int
314
vuses_compare (const void *pa, const void *pb)
315
{
316
  const tree vusea = *((const tree *)pa);
317
  const tree vuseb = *((const tree *)pb);
318
  int sn = SSA_NAME_VERSION (vusea) - SSA_NAME_VERSION (vuseb);
319
 
320
  return sn;
321
}
322
 
323
/* Print out the "Created value <x> for <Y>" statement to the
324
   dump_file.
325
   This is factored because both versions of lookup use it, and it
326
   obscures the real work going on in those functions.  */
327
 
328
static void
329
print_creation_to_file (tree v, tree expr, VEC (tree, gc) *vuses)
330
{
331
  fprintf (dump_file, "Created value ");
332
  print_generic_expr (dump_file, v, dump_flags);
333
  fprintf (dump_file, " for ");
334
  print_generic_expr (dump_file, expr, dump_flags);
335
 
336
  if (vuses && VEC_length (tree, vuses) != 0)
337
    {
338
      size_t i;
339
      tree vuse;
340
 
341
      fprintf (dump_file, " vuses: (");
342
      for (i = 0; VEC_iterate (tree, vuses, i, vuse); i++)
343
        {
344
          print_generic_expr (dump_file, vuse, dump_flags);
345
          if (VEC_length (tree, vuses) - 1 != i)
346
            fprintf (dump_file, ",");
347
        }
348
      fprintf (dump_file, ")");
349
    }
350
  fprintf (dump_file, "\n");
351
}
352
 
353
/* Like vn_lookup, but creates a new value for expression EXPR, if
354
   EXPR doesn't already have a value.  Return the existing/created
355
   value for EXPR.  STMT represents the stmt associated with EXPR.  It
356
   is used when computing the VUSES for EXPR.  */
357
 
358
tree
359
vn_lookup_or_add (tree expr, tree stmt)
360
{
361
  tree v = vn_lookup (expr, stmt);
362
  if (v == NULL_TREE)
363
    {
364
      VEC(tree,gc) *vuses;
365
 
366
      v = make_value_handle (TREE_TYPE (expr));
367
      vuses = copy_vuses_from_stmt (stmt);
368
      sort_vuses (vuses);
369
 
370
      if (dump_file && (dump_flags & TDF_DETAILS))
371
        print_creation_to_file (v, expr, vuses);
372
 
373
      VALUE_HANDLE_VUSES (v) = vuses;
374
      vn_add_with_vuses (expr, v, vuses);
375
    }
376
 
377
  set_value_handle (expr, v);
378
 
379
  return v;
380
}
381
 
382
/* Sort the VUSE array so that we can do equality comparisons
383
   quicker on two vuse vecs.  */
384
 
385
void
386
sort_vuses (VEC (tree,gc) *vuses)
387
{
388
  if (VEC_length (tree, vuses) > 1)
389
    qsort (VEC_address (tree, vuses),
390
           VEC_length (tree, vuses),
391
           sizeof (tree),
392
           vuses_compare);
393
}
394
 
395
/* Like vn_lookup, but creates a new value for expression EXPR, if
396
   EXPR doesn't already have a value.  Return the existing/created
397
   value for EXPR.  STMT represents the stmt associated with EXPR.  It is used
398
   when computing the hash value for EXPR.  */
399
 
400
tree
401
vn_lookup_or_add_with_vuses (tree expr, VEC (tree, gc) *vuses)
402
{
403
  tree v = vn_lookup_with_vuses (expr, vuses);
404
  if (v == NULL_TREE)
405
    {
406
      v = make_value_handle (TREE_TYPE (expr));
407
      sort_vuses (vuses);
408
 
409
      if (dump_file && (dump_flags & TDF_DETAILS))
410
        print_creation_to_file (v, expr, vuses);
411
 
412
      VALUE_HANDLE_VUSES (v) = vuses;
413
      vn_add_with_vuses (expr, v, vuses);
414
    }
415
 
416
  set_value_handle (expr, v);
417
 
418
  return v;
419
}
420
 
421
 
422
 
423
/* Get the value handle of EXPR.  This is the only correct way to get
424
   the value handle for a "thing".  If EXPR does not have a value
425
   handle associated, it returns NULL_TREE.
426
   NB: If EXPR is min_invariant, this function is *required* to return EXPR.  */
427
 
428
tree
429
get_value_handle (tree expr)
430
{
431
 
432
  if (is_gimple_min_invariant (expr))
433
    return expr;
434
 
435
  if (TREE_CODE (expr) == SSA_NAME)
436
    return SSA_NAME_VALUE (expr);
437
  else if (EXPR_P (expr) || DECL_P (expr) || TREE_CODE (expr) == TREE_LIST
438
           || TREE_CODE (expr) == CONSTRUCTOR)
439
    {
440
      tree_ann_common_t ann = tree_common_ann (expr);
441
      return ((ann) ? ann->value_handle : NULL_TREE);
442
    }
443
  else
444
    gcc_unreachable ();
445
}
446
 
447
 
448
/* Initialize data structures used in value numbering.  */
449
 
450
void
451
vn_init (void)
452
{
453
  value_table = htab_create (511, val_expr_pair_hash,
454
                             val_expr_pair_expr_eq, free);
455
  shared_lookup_vuses = NULL;
456
}
457
 
458
 
459
/* Delete data used for value numbering.  */
460
 
461
void
462
vn_delete (void)
463
{
464
  htab_delete (value_table);
465
  VEC_free (tree, gc, shared_lookup_vuses);
466
  value_table = NULL;
467
}

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.