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

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-dev/] [or1k-gcc/] [gcc/] [tree-ssa-pre.c] - Blame information for rev 733

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

Line No. Rev Author Line
1 684 jeremybenn
/* SSA-PRE for trees.
2
   Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
3
   Free Software Foundation, Inc.
4
   Contributed by Daniel Berlin <dan@dberlin.org> and Steven Bosscher
5
   <stevenb@suse.de>
6
 
7
This file is part of GCC.
8
 
9
GCC is free software; you can redistribute it and/or modify
10
it under the terms of the GNU General Public License as published by
11
the Free Software Foundation; either version 3, or (at your option)
12
any later version.
13
 
14
GCC is distributed in the hope that it will be useful,
15
but WITHOUT ANY WARRANTY; without even the implied warranty of
16
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
17
GNU General Public License for more details.
18
 
19
You should have received a copy of the GNU General Public License
20
along with GCC; see the file COPYING3.  If not see
21
<http://www.gnu.org/licenses/>.  */
22
 
23
#include "config.h"
24
#include "system.h"
25
#include "coretypes.h"
26
#include "tm.h"
27
#include "tree.h"
28
#include "basic-block.h"
29
#include "tree-pretty-print.h"
30
#include "gimple-pretty-print.h"
31
#include "tree-inline.h"
32
#include "tree-flow.h"
33
#include "gimple.h"
34
#include "tree-dump.h"
35
#include "timevar.h"
36
#include "fibheap.h"
37
#include "hashtab.h"
38
#include "tree-iterator.h"
39
#include "alloc-pool.h"
40
#include "obstack.h"
41
#include "tree-pass.h"
42
#include "flags.h"
43
#include "bitmap.h"
44
#include "langhooks.h"
45
#include "cfgloop.h"
46
#include "tree-ssa-sccvn.h"
47
#include "tree-scalar-evolution.h"
48
#include "params.h"
49
#include "dbgcnt.h"
50
 
51
/* TODO:
52
 
53
   1. Avail sets can be shared by making an avail_find_leader that
54
      walks up the dominator tree and looks in those avail sets.
55
      This might affect code optimality, it's unclear right now.
56
   2. Strength reduction can be performed by anticipating expressions
57
      we can repair later on.
58
   3. We can do back-substitution or smarter value numbering to catch
59
      commutative expressions split up over multiple statements.
60
*/
61
 
62
/* For ease of terminology, "expression node" in the below refers to
63
   every expression node but GIMPLE_ASSIGN, because GIMPLE_ASSIGNs
64
   represent the actual statement containing the expressions we care about,
65
   and we cache the value number by putting it in the expression.  */
66
 
67
/* Basic algorithm
68
 
69
   First we walk the statements to generate the AVAIL sets, the
70
   EXP_GEN sets, and the tmp_gen sets.  EXP_GEN sets represent the
71
   generation of values/expressions by a given block.  We use them
72
   when computing the ANTIC sets.  The AVAIL sets consist of
73
   SSA_NAME's that represent values, so we know what values are
74
   available in what blocks.  AVAIL is a forward dataflow problem.  In
75
   SSA, values are never killed, so we don't need a kill set, or a
76
   fixpoint iteration, in order to calculate the AVAIL sets.  In
77
   traditional parlance, AVAIL sets tell us the downsafety of the
78
   expressions/values.
79
 
80
   Next, we generate the ANTIC sets.  These sets represent the
81
   anticipatable expressions.  ANTIC is a backwards dataflow
82
   problem.  An expression is anticipatable in a given block if it could
83
   be generated in that block.  This means that if we had to perform
84
   an insertion in that block, of the value of that expression, we
85
   could.  Calculating the ANTIC sets requires phi translation of
86
   expressions, because the flow goes backwards through phis.  We must
87
   iterate to a fixpoint of the ANTIC sets, because we have a kill
88
   set.  Even in SSA form, values are not live over the entire
89
   function, only from their definition point onwards.  So we have to
90
   remove values from the ANTIC set once we go past the definition
91
   point of the leaders that make them up.
92
   compute_antic/compute_antic_aux performs this computation.
93
 
94
   Third, we perform insertions to make partially redundant
95
   expressions fully redundant.
96
 
97
   An expression is partially redundant (excluding partial
98
   anticipation) if:
99
 
100
   1. It is AVAIL in some, but not all, of the predecessors of a
101
      given block.
102
   2. It is ANTIC in all the predecessors.
103
 
104
   In order to make it fully redundant, we insert the expression into
105
   the predecessors where it is not available, but is ANTIC.
106
 
107
   For the partial anticipation case, we only perform insertion if it
108
   is partially anticipated in some block, and fully available in all
109
   of the predecessors.
110
 
111
   insert/insert_aux/do_regular_insertion/do_partial_partial_insertion
112
   performs these steps.
113
 
114
   Fourth, we eliminate fully redundant expressions.
115
   This is a simple statement walk that replaces redundant
116
   calculations with the now available values.  */
117
 
118
/* Representations of value numbers:
119
 
120
   Value numbers are represented by a representative SSA_NAME.  We
121
   will create fake SSA_NAME's in situations where we need a
122
   representative but do not have one (because it is a complex
123
   expression).  In order to facilitate storing the value numbers in
124
   bitmaps, and keep the number of wasted SSA_NAME's down, we also
125
   associate a value_id with each value number, and create full blown
126
   ssa_name's only where we actually need them (IE in operands of
127
   existing expressions).
128
 
129
   Theoretically you could replace all the value_id's with
130
   SSA_NAME_VERSION, but this would allocate a large number of
131
   SSA_NAME's (which are each > 30 bytes) just to get a 4 byte number.
132
   It would also require an additional indirection at each point we
133
   use the value id.  */
134
 
135
/* Representation of expressions on value numbers:
136
 
137
   Expressions consisting of value numbers are represented the same
138
   way as our VN internally represents them, with an additional
139
   "pre_expr" wrapping around them in order to facilitate storing all
140
   of the expressions in the same sets.  */
141
 
142
/* Representation of sets:
143
 
144
   The dataflow sets do not need to be sorted in any particular order
145
   for the majority of their lifetime, are simply represented as two
146
   bitmaps, one that keeps track of values present in the set, and one
147
   that keeps track of expressions present in the set.
148
 
149
   When we need them in topological order, we produce it on demand by
150
   transforming the bitmap into an array and sorting it into topo
151
   order.  */
152
 
153
/* Type of expression, used to know which member of the PRE_EXPR union
154
   is valid.  */
155
 
156
enum pre_expr_kind
157
{
158
    NAME,
159
    NARY,
160
    REFERENCE,
161
    CONSTANT
162
};
163
 
164
typedef union pre_expr_union_d
165
{
166
  tree name;
167
  tree constant;
168
  vn_nary_op_t nary;
169
  vn_reference_t reference;
170
} pre_expr_union;
171
 
172
typedef struct pre_expr_d
173
{
174
  enum pre_expr_kind kind;
175
  unsigned int id;
176
  pre_expr_union u;
177
} *pre_expr;
178
 
179
#define PRE_EXPR_NAME(e) (e)->u.name
180
#define PRE_EXPR_NARY(e) (e)->u.nary
181
#define PRE_EXPR_REFERENCE(e) (e)->u.reference
182
#define PRE_EXPR_CONSTANT(e) (e)->u.constant
183
 
184
static int
185
pre_expr_eq (const void *p1, const void *p2)
186
{
187
  const struct pre_expr_d *e1 = (const struct pre_expr_d *) p1;
188
  const struct pre_expr_d *e2 = (const struct pre_expr_d *) p2;
189
 
190
  if (e1->kind != e2->kind)
191
    return false;
192
 
193
  switch (e1->kind)
194
    {
195
    case CONSTANT:
196
      return vn_constant_eq_with_type (PRE_EXPR_CONSTANT (e1),
197
                                       PRE_EXPR_CONSTANT (e2));
198
    case NAME:
199
      return PRE_EXPR_NAME (e1) == PRE_EXPR_NAME (e2);
200
    case NARY:
201
      return vn_nary_op_eq (PRE_EXPR_NARY (e1), PRE_EXPR_NARY (e2));
202
    case REFERENCE:
203
      return vn_reference_eq (PRE_EXPR_REFERENCE (e1),
204
                              PRE_EXPR_REFERENCE (e2));
205
    default:
206
      gcc_unreachable ();
207
    }
208
}
209
 
210
static hashval_t
211
pre_expr_hash (const void *p1)
212
{
213
  const struct pre_expr_d *e = (const struct pre_expr_d *) p1;
214
  switch (e->kind)
215
    {
216
    case CONSTANT:
217
      return vn_hash_constant_with_type (PRE_EXPR_CONSTANT (e));
218
    case NAME:
219
      return SSA_NAME_VERSION (PRE_EXPR_NAME (e));
220
    case NARY:
221
      return PRE_EXPR_NARY (e)->hashcode;
222
    case REFERENCE:
223
      return PRE_EXPR_REFERENCE (e)->hashcode;
224
    default:
225
      gcc_unreachable ();
226
    }
227
}
228
 
229
 
230
/* Next global expression id number.  */
231
static unsigned int next_expression_id;
232
 
233
/* Mapping from expression to id number we can use in bitmap sets.  */
234
DEF_VEC_P (pre_expr);
235
DEF_VEC_ALLOC_P (pre_expr, heap);
236
static VEC(pre_expr, heap) *expressions;
237
static htab_t expression_to_id;
238
static VEC(unsigned, heap) *name_to_id;
239
 
240
/* Allocate an expression id for EXPR.  */
241
 
242
static inline unsigned int
243
alloc_expression_id (pre_expr expr)
244
{
245
  void **slot;
246
  /* Make sure we won't overflow. */
247
  gcc_assert (next_expression_id + 1 > next_expression_id);
248
  expr->id = next_expression_id++;
249
  VEC_safe_push (pre_expr, heap, expressions, expr);
250
  if (expr->kind == NAME)
251
    {
252
      unsigned version = SSA_NAME_VERSION (PRE_EXPR_NAME (expr));
253
      /* VEC_safe_grow_cleared allocates no headroom.  Avoid frequent
254
         re-allocations by using VEC_reserve upfront.  There is no
255
         VEC_quick_grow_cleared unfortunately.  */
256
      VEC_reserve (unsigned, heap, name_to_id, num_ssa_names);
257
      VEC_safe_grow_cleared (unsigned, heap, name_to_id, num_ssa_names);
258
      gcc_assert (VEC_index (unsigned, name_to_id, version) == 0);
259
      VEC_replace (unsigned, name_to_id, version, expr->id);
260
    }
261
  else
262
    {
263
      slot = htab_find_slot (expression_to_id, expr, INSERT);
264
      gcc_assert (!*slot);
265
      *slot = expr;
266
    }
267
  return next_expression_id - 1;
268
}
269
 
270
/* Return the expression id for tree EXPR.  */
271
 
272
static inline unsigned int
273
get_expression_id (const pre_expr expr)
274
{
275
  return expr->id;
276
}
277
 
278
static inline unsigned int
279
lookup_expression_id (const pre_expr expr)
280
{
281
  void **slot;
282
 
283
  if (expr->kind == NAME)
284
    {
285
      unsigned version = SSA_NAME_VERSION (PRE_EXPR_NAME (expr));
286
      if (VEC_length (unsigned, name_to_id) <= version)
287
        return 0;
288
      return VEC_index (unsigned, name_to_id, version);
289
    }
290
  else
291
    {
292
      slot = htab_find_slot (expression_to_id, expr, NO_INSERT);
293
      if (!slot)
294
        return 0;
295
      return ((pre_expr)*slot)->id;
296
    }
297
}
298
 
299
/* Return the existing expression id for EXPR, or create one if one
300
   does not exist yet.  */
301
 
302
static inline unsigned int
303
get_or_alloc_expression_id (pre_expr expr)
304
{
305
  unsigned int id = lookup_expression_id (expr);
306
  if (id == 0)
307
    return alloc_expression_id (expr);
308
  return expr->id = id;
309
}
310
 
311
/* Return the expression that has expression id ID */
312
 
313
static inline pre_expr
314
expression_for_id (unsigned int id)
315
{
316
  return VEC_index (pre_expr, expressions, id);
317
}
318
 
319
/* Free the expression id field in all of our expressions,
320
   and then destroy the expressions array.  */
321
 
322
static void
323
clear_expression_ids (void)
324
{
325
  VEC_free (pre_expr, heap, expressions);
326
}
327
 
328
static alloc_pool pre_expr_pool;
329
 
330
/* Given an SSA_NAME NAME, get or create a pre_expr to represent it.  */
331
 
332
static pre_expr
333
get_or_alloc_expr_for_name (tree name)
334
{
335
  struct pre_expr_d expr;
336
  pre_expr result;
337
  unsigned int result_id;
338
 
339
  expr.kind = NAME;
340
  expr.id = 0;
341
  PRE_EXPR_NAME (&expr) = name;
342
  result_id = lookup_expression_id (&expr);
343
  if (result_id != 0)
344
    return expression_for_id (result_id);
345
 
346
  result = (pre_expr) pool_alloc (pre_expr_pool);
347
  result->kind = NAME;
348
  PRE_EXPR_NAME (result) = name;
349
  alloc_expression_id (result);
350
  return result;
351
}
352
 
353
static bool in_fre = false;
354
 
355
/* An unordered bitmap set.  One bitmap tracks values, the other,
356
   expressions.  */
357
typedef struct bitmap_set
358
{
359
  bitmap_head expressions;
360
  bitmap_head values;
361
} *bitmap_set_t;
362
 
363
#define FOR_EACH_EXPR_ID_IN_SET(set, id, bi)            \
364
  EXECUTE_IF_SET_IN_BITMAP(&(set)->expressions, 0, (id), (bi))
365
 
366
#define FOR_EACH_VALUE_ID_IN_SET(set, id, bi)           \
367
  EXECUTE_IF_SET_IN_BITMAP(&(set)->values, 0, (id), (bi))
368
 
369
/* Mapping from value id to expressions with that value_id.  */
370
DEF_VEC_P (bitmap_set_t);
371
DEF_VEC_ALLOC_P (bitmap_set_t, heap);
372
static VEC(bitmap_set_t, heap) *value_expressions;
373
 
374
/* Sets that we need to keep track of.  */
375
typedef struct bb_bitmap_sets
376
{
377
  /* The EXP_GEN set, which represents expressions/values generated in
378
     a basic block.  */
379
  bitmap_set_t exp_gen;
380
 
381
  /* The PHI_GEN set, which represents PHI results generated in a
382
     basic block.  */
383
  bitmap_set_t phi_gen;
384
 
385
  /* The TMP_GEN set, which represents results/temporaries generated
386
     in a basic block. IE the LHS of an expression.  */
387
  bitmap_set_t tmp_gen;
388
 
389
  /* The AVAIL_OUT set, which represents which values are available in
390
     a given basic block.  */
391
  bitmap_set_t avail_out;
392
 
393
  /* The ANTIC_IN set, which represents which values are anticipatable
394
     in a given basic block.  */
395
  bitmap_set_t antic_in;
396
 
397
  /* The PA_IN set, which represents which values are
398
     partially anticipatable in a given basic block.  */
399
  bitmap_set_t pa_in;
400
 
401
  /* The NEW_SETS set, which is used during insertion to augment the
402
     AVAIL_OUT set of blocks with the new insertions performed during
403
     the current iteration.  */
404
  bitmap_set_t new_sets;
405
 
406
  /* A cache for value_dies_in_block_x.  */
407
  bitmap expr_dies;
408
 
409
  /* True if we have visited this block during ANTIC calculation.  */
410
  unsigned int visited : 1;
411
 
412
  /* True we have deferred processing this block during ANTIC
413
     calculation until its successor is processed.  */
414
  unsigned int deferred : 1;
415
 
416
  /* True when the block contains a call that might not return.  */
417
  unsigned int contains_may_not_return_call : 1;
418
} *bb_value_sets_t;
419
 
420
#define EXP_GEN(BB)     ((bb_value_sets_t) ((BB)->aux))->exp_gen
421
#define PHI_GEN(BB)     ((bb_value_sets_t) ((BB)->aux))->phi_gen
422
#define TMP_GEN(BB)     ((bb_value_sets_t) ((BB)->aux))->tmp_gen
423
#define AVAIL_OUT(BB)   ((bb_value_sets_t) ((BB)->aux))->avail_out
424
#define ANTIC_IN(BB)    ((bb_value_sets_t) ((BB)->aux))->antic_in
425
#define PA_IN(BB)       ((bb_value_sets_t) ((BB)->aux))->pa_in
426
#define NEW_SETS(BB)    ((bb_value_sets_t) ((BB)->aux))->new_sets
427
#define EXPR_DIES(BB)   ((bb_value_sets_t) ((BB)->aux))->expr_dies
428
#define BB_VISITED(BB)  ((bb_value_sets_t) ((BB)->aux))->visited
429
#define BB_DEFERRED(BB) ((bb_value_sets_t) ((BB)->aux))->deferred
430
#define BB_MAY_NOTRETURN(BB) ((bb_value_sets_t) ((BB)->aux))->contains_may_not_return_call
431
 
432
 
433
/* Basic block list in postorder.  */
434
static int *postorder;
435
 
436
/* This structure is used to keep track of statistics on what
437
   optimization PRE was able to perform.  */
438
static struct
439
{
440
  /* The number of RHS computations eliminated by PRE.  */
441
  int eliminations;
442
 
443
  /* The number of new expressions/temporaries generated by PRE.  */
444
  int insertions;
445
 
446
  /* The number of inserts found due to partial anticipation  */
447
  int pa_insert;
448
 
449
  /* The number of new PHI nodes added by PRE.  */
450
  int phis;
451
 
452
  /* The number of values found constant.  */
453
  int constified;
454
 
455
} pre_stats;
456
 
457
static bool do_partial_partial;
458
static pre_expr bitmap_find_leader (bitmap_set_t, unsigned int, gimple);
459
static void bitmap_value_insert_into_set (bitmap_set_t, pre_expr);
460
static void bitmap_value_replace_in_set (bitmap_set_t, pre_expr);
461
static void bitmap_set_copy (bitmap_set_t, bitmap_set_t);
462
static bool bitmap_set_contains_value (bitmap_set_t, unsigned int);
463
static void bitmap_insert_into_set (bitmap_set_t, pre_expr);
464
static void bitmap_insert_into_set_1 (bitmap_set_t, pre_expr,
465
                                      unsigned int, bool);
466
static bitmap_set_t bitmap_set_new (void);
467
static tree create_expression_by_pieces (basic_block, pre_expr, gimple_seq *,
468
                                         gimple, tree);
469
static tree find_or_generate_expression (basic_block, pre_expr, gimple_seq *,
470
                                         gimple);
471
static unsigned int get_expr_value_id (pre_expr);
472
 
473
/* We can add and remove elements and entries to and from sets
474
   and hash tables, so we use alloc pools for them.  */
475
 
476
static alloc_pool bitmap_set_pool;
477
static bitmap_obstack grand_bitmap_obstack;
478
 
479
/* To avoid adding 300 temporary variables when we only need one, we
480
   only create one temporary variable, on demand, and build ssa names
481
   off that.  We do have to change the variable if the types don't
482
   match the current variable's type.  */
483
static tree pretemp;
484
static tree storetemp;
485
static tree prephitemp;
486
 
487
/* Set of blocks with statements that have had their EH properties changed.  */
488
static bitmap need_eh_cleanup;
489
 
490
/* Set of blocks with statements that have had their AB properties changed.  */
491
static bitmap need_ab_cleanup;
492
 
493
/* The phi_translate_table caches phi translations for a given
494
   expression and predecessor.  */
495
 
496
static htab_t phi_translate_table;
497
 
498
/* A three tuple {e, pred, v} used to cache phi translations in the
499
   phi_translate_table.  */
500
 
501
typedef struct expr_pred_trans_d
502
{
503
  /* The expression.  */
504
  pre_expr e;
505
 
506
  /* The predecessor block along which we translated the expression.  */
507
  basic_block pred;
508
 
509
  /* The value that resulted from the translation.  */
510
  pre_expr v;
511
 
512
  /* The hashcode for the expression, pred pair. This is cached for
513
     speed reasons.  */
514
  hashval_t hashcode;
515
} *expr_pred_trans_t;
516
typedef const struct expr_pred_trans_d *const_expr_pred_trans_t;
517
 
518
/* Return the hash value for a phi translation table entry.  */
519
 
520
static hashval_t
521
expr_pred_trans_hash (const void *p)
522
{
523
  const_expr_pred_trans_t const ve = (const_expr_pred_trans_t) p;
524
  return ve->hashcode;
525
}
526
 
527
/* Return true if two phi translation table entries are the same.
528
   P1 and P2 should point to the expr_pred_trans_t's to be compared.*/
529
 
530
static int
531
expr_pred_trans_eq (const void *p1, const void *p2)
532
{
533
  const_expr_pred_trans_t const ve1 = (const_expr_pred_trans_t) p1;
534
  const_expr_pred_trans_t const ve2 = (const_expr_pred_trans_t) p2;
535
  basic_block b1 = ve1->pred;
536
  basic_block b2 = ve2->pred;
537
 
538
  /* If they are not translations for the same basic block, they can't
539
     be equal.  */
540
  if (b1 != b2)
541
    return false;
542
  return pre_expr_eq (ve1->e, ve2->e);
543
}
544
 
545
/* Search in the phi translation table for the translation of
546
   expression E in basic block PRED.
547
   Return the translated value, if found, NULL otherwise.  */
548
 
549
static inline pre_expr
550
phi_trans_lookup (pre_expr e, basic_block pred)
551
{
552
  void **slot;
553
  struct expr_pred_trans_d ept;
554
 
555
  ept.e = e;
556
  ept.pred = pred;
557
  ept.hashcode = iterative_hash_hashval_t (pre_expr_hash (e), pred->index);
558
  slot = htab_find_slot_with_hash (phi_translate_table, &ept, ept.hashcode,
559
                                   NO_INSERT);
560
  if (!slot)
561
    return NULL;
562
  else
563
    return ((expr_pred_trans_t) *slot)->v;
564
}
565
 
566
 
567
/* Add the tuple mapping from {expression E, basic block PRED} to
568
   value V, to the phi translation table.  */
569
 
570
static inline void
571
phi_trans_add (pre_expr e, pre_expr v, basic_block pred)
572
{
573
  void **slot;
574
  expr_pred_trans_t new_pair = XNEW (struct expr_pred_trans_d);
575
  new_pair->e = e;
576
  new_pair->pred = pred;
577
  new_pair->v = v;
578
  new_pair->hashcode = iterative_hash_hashval_t (pre_expr_hash (e),
579
                                                 pred->index);
580
 
581
  slot = htab_find_slot_with_hash (phi_translate_table, new_pair,
582
                                   new_pair->hashcode, INSERT);
583
  free (*slot);
584
  *slot = (void *) new_pair;
585
}
586
 
587
 
588
/* Add expression E to the expression set of value id V.  */
589
 
590
void
591
add_to_value (unsigned int v, pre_expr e)
592
{
593
  bitmap_set_t set;
594
 
595
  gcc_assert (get_expr_value_id (e) == v);
596
 
597
  if (v >= VEC_length (bitmap_set_t, value_expressions))
598
    {
599
      VEC_safe_grow_cleared (bitmap_set_t, heap, value_expressions,
600
                             v + 1);
601
    }
602
 
603
  set = VEC_index (bitmap_set_t, value_expressions, v);
604
  if (!set)
605
    {
606
      set = bitmap_set_new ();
607
      VEC_replace (bitmap_set_t, value_expressions, v, set);
608
    }
609
 
610
  bitmap_insert_into_set_1 (set, e, v, true);
611
}
612
 
613
/* Create a new bitmap set and return it.  */
614
 
615
static bitmap_set_t
616
bitmap_set_new (void)
617
{
618
  bitmap_set_t ret = (bitmap_set_t) pool_alloc (bitmap_set_pool);
619
  bitmap_initialize (&ret->expressions, &grand_bitmap_obstack);
620
  bitmap_initialize (&ret->values, &grand_bitmap_obstack);
621
  return ret;
622
}
623
 
624
/* Return the value id for a PRE expression EXPR.  */
625
 
626
static unsigned int
627
get_expr_value_id (pre_expr expr)
628
{
629
  switch (expr->kind)
630
    {
631
    case CONSTANT:
632
      {
633
        unsigned int id;
634
        id = get_constant_value_id (PRE_EXPR_CONSTANT (expr));
635
        if (id == 0)
636
          {
637
            id = get_or_alloc_constant_value_id (PRE_EXPR_CONSTANT (expr));
638
            add_to_value (id, expr);
639
          }
640
        return id;
641
      }
642
    case NAME:
643
      return VN_INFO (PRE_EXPR_NAME (expr))->value_id;
644
    case NARY:
645
      return PRE_EXPR_NARY (expr)->value_id;
646
    case REFERENCE:
647
      return PRE_EXPR_REFERENCE (expr)->value_id;
648
    default:
649
      gcc_unreachable ();
650
    }
651
}
652
 
653
/* Remove an expression EXPR from a bitmapped set.  */
654
 
655
static void
656
bitmap_remove_from_set (bitmap_set_t set, pre_expr expr)
657
{
658
  unsigned int val  = get_expr_value_id (expr);
659
  if (!value_id_constant_p (val))
660
    {
661
      bitmap_clear_bit (&set->values, val);
662
      bitmap_clear_bit (&set->expressions, get_expression_id (expr));
663
    }
664
}
665
 
666
static void
667
bitmap_insert_into_set_1 (bitmap_set_t set, pre_expr expr,
668
                          unsigned int val, bool allow_constants)
669
{
670
  if (allow_constants || !value_id_constant_p (val))
671
    {
672
      /* We specifically expect this and only this function to be able to
673
         insert constants into a set.  */
674
      bitmap_set_bit (&set->values, val);
675
      bitmap_set_bit (&set->expressions, get_or_alloc_expression_id (expr));
676
    }
677
}
678
 
679
/* Insert an expression EXPR into a bitmapped set.  */
680
 
681
static void
682
bitmap_insert_into_set (bitmap_set_t set, pre_expr expr)
683
{
684
  bitmap_insert_into_set_1 (set, expr, get_expr_value_id (expr), false);
685
}
686
 
687
/* Copy a bitmapped set ORIG, into bitmapped set DEST.  */
688
 
689
static void
690
bitmap_set_copy (bitmap_set_t dest, bitmap_set_t orig)
691
{
692
  bitmap_copy (&dest->expressions, &orig->expressions);
693
  bitmap_copy (&dest->values, &orig->values);
694
}
695
 
696
 
697
/* Free memory used up by SET.  */
698
static void
699
bitmap_set_free (bitmap_set_t set)
700
{
701
  bitmap_clear (&set->expressions);
702
  bitmap_clear (&set->values);
703
}
704
 
705
 
706
/* Generate an topological-ordered array of bitmap set SET.  */
707
 
708
static VEC(pre_expr, heap) *
709
sorted_array_from_bitmap_set (bitmap_set_t set)
710
{
711
  unsigned int i, j;
712
  bitmap_iterator bi, bj;
713
  VEC(pre_expr, heap) *result;
714
 
715
  /* Pre-allocate roughly enough space for the array.  */
716
  result = VEC_alloc (pre_expr, heap, bitmap_count_bits (&set->values));
717
 
718
  FOR_EACH_VALUE_ID_IN_SET (set, i, bi)
719
    {
720
      /* The number of expressions having a given value is usually
721
         relatively small.  Thus, rather than making a vector of all
722
         the expressions and sorting it by value-id, we walk the values
723
         and check in the reverse mapping that tells us what expressions
724
         have a given value, to filter those in our set.  As a result,
725
         the expressions are inserted in value-id order, which means
726
         topological order.
727
 
728
         If this is somehow a significant lose for some cases, we can
729
         choose which set to walk based on the set size.  */
730
      bitmap_set_t exprset = VEC_index (bitmap_set_t, value_expressions, i);
731
      FOR_EACH_EXPR_ID_IN_SET (exprset, j, bj)
732
        {
733
          if (bitmap_bit_p (&set->expressions, j))
734
            VEC_safe_push (pre_expr, heap, result, expression_for_id (j));
735
        }
736
    }
737
 
738
  return result;
739
}
740
 
741
/* Perform bitmapped set operation DEST &= ORIG.  */
742
 
743
static void
744
bitmap_set_and (bitmap_set_t dest, bitmap_set_t orig)
745
{
746
  bitmap_iterator bi;
747
  unsigned int i;
748
 
749
  if (dest != orig)
750
    {
751
      bitmap_head temp;
752
      bitmap_initialize (&temp, &grand_bitmap_obstack);
753
 
754
      bitmap_and_into (&dest->values, &orig->values);
755
      bitmap_copy (&temp, &dest->expressions);
756
      EXECUTE_IF_SET_IN_BITMAP (&temp, 0, i, bi)
757
        {
758
          pre_expr expr = expression_for_id (i);
759
          unsigned int value_id = get_expr_value_id (expr);
760
          if (!bitmap_bit_p (&dest->values, value_id))
761
            bitmap_clear_bit (&dest->expressions, i);
762
        }
763
      bitmap_clear (&temp);
764
    }
765
}
766
 
767
/* Subtract all values and expressions contained in ORIG from DEST.  */
768
 
769
static bitmap_set_t
770
bitmap_set_subtract (bitmap_set_t dest, bitmap_set_t orig)
771
{
772
  bitmap_set_t result = bitmap_set_new ();
773
  bitmap_iterator bi;
774
  unsigned int i;
775
 
776
  bitmap_and_compl (&result->expressions, &dest->expressions,
777
                    &orig->expressions);
778
 
779
  FOR_EACH_EXPR_ID_IN_SET (result, i, bi)
780
    {
781
      pre_expr expr = expression_for_id (i);
782
      unsigned int value_id = get_expr_value_id (expr);
783
      bitmap_set_bit (&result->values, value_id);
784
    }
785
 
786
  return result;
787
}
788
 
789
/* Subtract all the values in bitmap set B from bitmap set A.  */
790
 
791
static void
792
bitmap_set_subtract_values (bitmap_set_t a, bitmap_set_t b)
793
{
794
  unsigned int i;
795
  bitmap_iterator bi;
796
  bitmap_head temp;
797
 
798
  bitmap_initialize (&temp, &grand_bitmap_obstack);
799
 
800
  bitmap_copy (&temp, &a->expressions);
801
  EXECUTE_IF_SET_IN_BITMAP (&temp, 0, i, bi)
802
    {
803
      pre_expr expr = expression_for_id (i);
804
      if (bitmap_set_contains_value (b, get_expr_value_id (expr)))
805
        bitmap_remove_from_set (a, expr);
806
    }
807
  bitmap_clear (&temp);
808
}
809
 
810
 
811
/* Return true if bitmapped set SET contains the value VALUE_ID.  */
812
 
813
static bool
814
bitmap_set_contains_value (bitmap_set_t set, unsigned int value_id)
815
{
816
  if (value_id_constant_p (value_id))
817
    return true;
818
 
819
  if (!set || bitmap_empty_p (&set->expressions))
820
    return false;
821
 
822
  return bitmap_bit_p (&set->values, value_id);
823
}
824
 
825
static inline bool
826
bitmap_set_contains_expr (bitmap_set_t set, const pre_expr expr)
827
{
828
  return bitmap_bit_p (&set->expressions, get_expression_id (expr));
829
}
830
 
831
/* Replace an instance of value LOOKFOR with expression EXPR in SET.  */
832
 
833
static void
834
bitmap_set_replace_value (bitmap_set_t set, unsigned int lookfor,
835
                          const pre_expr expr)
836
{
837
  bitmap_set_t exprset;
838
  unsigned int i;
839
  bitmap_iterator bi;
840
 
841
  if (value_id_constant_p (lookfor))
842
    return;
843
 
844
  if (!bitmap_set_contains_value (set, lookfor))
845
    return;
846
 
847
  /* The number of expressions having a given value is usually
848
     significantly less than the total number of expressions in SET.
849
     Thus, rather than check, for each expression in SET, whether it
850
     has the value LOOKFOR, we walk the reverse mapping that tells us
851
     what expressions have a given value, and see if any of those
852
     expressions are in our set.  For large testcases, this is about
853
     5-10x faster than walking the bitmap.  If this is somehow a
854
     significant lose for some cases, we can choose which set to walk
855
     based on the set size.  */
856
  exprset = VEC_index (bitmap_set_t, value_expressions, lookfor);
857
  FOR_EACH_EXPR_ID_IN_SET (exprset, i, bi)
858
    {
859
      if (bitmap_clear_bit (&set->expressions, i))
860
        {
861
          bitmap_set_bit (&set->expressions, get_expression_id (expr));
862
          return;
863
        }
864
    }
865
}
866
 
867
/* Return true if two bitmap sets are equal.  */
868
 
869
static bool
870
bitmap_set_equal (bitmap_set_t a, bitmap_set_t b)
871
{
872
  return bitmap_equal_p (&a->values, &b->values);
873
}
874
 
875
/* Replace an instance of EXPR's VALUE with EXPR in SET if it exists,
876
   and add it otherwise.  */
877
 
878
static void
879
bitmap_value_replace_in_set (bitmap_set_t set, pre_expr expr)
880
{
881
  unsigned int val = get_expr_value_id (expr);
882
 
883
  if (bitmap_set_contains_value (set, val))
884
    bitmap_set_replace_value (set, val, expr);
885
  else
886
    bitmap_insert_into_set (set, expr);
887
}
888
 
889
/* Insert EXPR into SET if EXPR's value is not already present in
890
   SET.  */
891
 
892
static void
893
bitmap_value_insert_into_set (bitmap_set_t set, pre_expr expr)
894
{
895
  unsigned int val = get_expr_value_id (expr);
896
 
897
  gcc_checking_assert (expr->id == get_or_alloc_expression_id (expr));
898
 
899
  /* Constant values are always considered to be part of the set.  */
900
  if (value_id_constant_p (val))
901
    return;
902
 
903
  /* If the value membership changed, add the expression.  */
904
  if (bitmap_set_bit (&set->values, val))
905
    bitmap_set_bit (&set->expressions, expr->id);
906
}
907
 
908
/* Print out EXPR to outfile.  */
909
 
910
static void
911
print_pre_expr (FILE *outfile, const pre_expr expr)
912
{
913
  switch (expr->kind)
914
    {
915
    case CONSTANT:
916
      print_generic_expr (outfile, PRE_EXPR_CONSTANT (expr), 0);
917
      break;
918
    case NAME:
919
      print_generic_expr (outfile, PRE_EXPR_NAME (expr), 0);
920
      break;
921
    case NARY:
922
      {
923
        unsigned int i;
924
        vn_nary_op_t nary = PRE_EXPR_NARY (expr);
925
        fprintf (outfile, "{%s,", tree_code_name [nary->opcode]);
926
        for (i = 0; i < nary->length; i++)
927
          {
928
            print_generic_expr (outfile, nary->op[i], 0);
929
            if (i != (unsigned) nary->length - 1)
930
              fprintf (outfile, ",");
931
          }
932
        fprintf (outfile, "}");
933
      }
934
      break;
935
 
936
    case REFERENCE:
937
      {
938
        vn_reference_op_t vro;
939
        unsigned int i;
940
        vn_reference_t ref = PRE_EXPR_REFERENCE (expr);
941
        fprintf (outfile, "{");
942
        for (i = 0;
943
             VEC_iterate (vn_reference_op_s, ref->operands, i, vro);
944
             i++)
945
          {
946
            bool closebrace = false;
947
            if (vro->opcode != SSA_NAME
948
                && TREE_CODE_CLASS (vro->opcode) != tcc_declaration)
949
              {
950
                fprintf (outfile, "%s", tree_code_name [vro->opcode]);
951
                if (vro->op0)
952
                  {
953
                    fprintf (outfile, "<");
954
                    closebrace = true;
955
                  }
956
              }
957
            if (vro->op0)
958
              {
959
                print_generic_expr (outfile, vro->op0, 0);
960
                if (vro->op1)
961
                  {
962
                    fprintf (outfile, ",");
963
                    print_generic_expr (outfile, vro->op1, 0);
964
                  }
965
                if (vro->op2)
966
                  {
967
                    fprintf (outfile, ",");
968
                    print_generic_expr (outfile, vro->op2, 0);
969
                  }
970
              }
971
            if (closebrace)
972
                fprintf (outfile, ">");
973
            if (i != VEC_length (vn_reference_op_s, ref->operands) - 1)
974
              fprintf (outfile, ",");
975
          }
976
        fprintf (outfile, "}");
977
        if (ref->vuse)
978
          {
979
            fprintf (outfile, "@");
980
            print_generic_expr (outfile, ref->vuse, 0);
981
          }
982
      }
983
      break;
984
    }
985
}
986
void debug_pre_expr (pre_expr);
987
 
988
/* Like print_pre_expr but always prints to stderr.  */
989
DEBUG_FUNCTION void
990
debug_pre_expr (pre_expr e)
991
{
992
  print_pre_expr (stderr, e);
993
  fprintf (stderr, "\n");
994
}
995
 
996
/* Print out SET to OUTFILE.  */
997
 
998
static void
999
print_bitmap_set (FILE *outfile, bitmap_set_t set,
1000
                  const char *setname, int blockindex)
1001
{
1002
  fprintf (outfile, "%s[%d] := { ", setname, blockindex);
1003
  if (set)
1004
    {
1005
      bool first = true;
1006
      unsigned i;
1007
      bitmap_iterator bi;
1008
 
1009
      FOR_EACH_EXPR_ID_IN_SET (set, i, bi)
1010
        {
1011
          const pre_expr expr = expression_for_id (i);
1012
 
1013
          if (!first)
1014
            fprintf (outfile, ", ");
1015
          first = false;
1016
          print_pre_expr (outfile, expr);
1017
 
1018
          fprintf (outfile, " (%04d)", get_expr_value_id (expr));
1019
        }
1020
    }
1021
  fprintf (outfile, " }\n");
1022
}
1023
 
1024
void debug_bitmap_set (bitmap_set_t);
1025
 
1026
DEBUG_FUNCTION void
1027
debug_bitmap_set (bitmap_set_t set)
1028
{
1029
  print_bitmap_set (stderr, set, "debug", 0);
1030
}
1031
 
1032
/* Print out the expressions that have VAL to OUTFILE.  */
1033
 
1034
void
1035
print_value_expressions (FILE *outfile, unsigned int val)
1036
{
1037
  bitmap_set_t set = VEC_index (bitmap_set_t, value_expressions, val);
1038
  if (set)
1039
    {
1040
      char s[10];
1041
      sprintf (s, "%04d", val);
1042
      print_bitmap_set (outfile, set, s, 0);
1043
    }
1044
}
1045
 
1046
 
1047
DEBUG_FUNCTION void
1048
debug_value_expressions (unsigned int val)
1049
{
1050
  print_value_expressions (stderr, val);
1051
}
1052
 
1053
/* Given a CONSTANT, allocate a new CONSTANT type PRE_EXPR to
1054
   represent it.  */
1055
 
1056
static pre_expr
1057
get_or_alloc_expr_for_constant (tree constant)
1058
{
1059
  unsigned int result_id;
1060
  unsigned int value_id;
1061
  struct pre_expr_d expr;
1062
  pre_expr newexpr;
1063
 
1064
  expr.kind = CONSTANT;
1065
  PRE_EXPR_CONSTANT (&expr) = constant;
1066
  result_id = lookup_expression_id (&expr);
1067
  if (result_id != 0)
1068
    return expression_for_id (result_id);
1069
 
1070
  newexpr = (pre_expr) pool_alloc (pre_expr_pool);
1071
  newexpr->kind = CONSTANT;
1072
  PRE_EXPR_CONSTANT (newexpr) = constant;
1073
  alloc_expression_id (newexpr);
1074
  value_id = get_or_alloc_constant_value_id (constant);
1075
  add_to_value (value_id, newexpr);
1076
  return newexpr;
1077
}
1078
 
1079
/* Given a value id V, find the actual tree representing the constant
1080
   value if there is one, and return it. Return NULL if we can't find
1081
   a constant.  */
1082
 
1083
static tree
1084
get_constant_for_value_id (unsigned int v)
1085
{
1086
  if (value_id_constant_p (v))
1087
    {
1088
      unsigned int i;
1089
      bitmap_iterator bi;
1090
      bitmap_set_t exprset = VEC_index (bitmap_set_t, value_expressions, v);
1091
 
1092
      FOR_EACH_EXPR_ID_IN_SET (exprset, i, bi)
1093
        {
1094
          pre_expr expr = expression_for_id (i);
1095
          if (expr->kind == CONSTANT)
1096
            return PRE_EXPR_CONSTANT (expr);
1097
        }
1098
    }
1099
  return NULL;
1100
}
1101
 
1102
/* Get or allocate a pre_expr for a piece of GIMPLE, and return it.
1103
   Currently only supports constants and SSA_NAMES.  */
1104
static pre_expr
1105
get_or_alloc_expr_for (tree t)
1106
{
1107
  if (TREE_CODE (t) == SSA_NAME)
1108
    return get_or_alloc_expr_for_name (t);
1109
  else if (is_gimple_min_invariant (t))
1110
    return get_or_alloc_expr_for_constant (t);
1111
  else
1112
    {
1113
      /* More complex expressions can result from SCCVN expression
1114
         simplification that inserts values for them.  As they all
1115
         do not have VOPs the get handled by the nary ops struct.  */
1116
      vn_nary_op_t result;
1117
      unsigned int result_id;
1118
      vn_nary_op_lookup (t, &result);
1119
      if (result != NULL)
1120
        {
1121
          pre_expr e = (pre_expr) pool_alloc (pre_expr_pool);
1122
          e->kind = NARY;
1123
          PRE_EXPR_NARY (e) = result;
1124
          result_id = lookup_expression_id (e);
1125
          if (result_id != 0)
1126
            {
1127
              pool_free (pre_expr_pool, e);
1128
              e = expression_for_id (result_id);
1129
              return e;
1130
            }
1131
          alloc_expression_id (e);
1132
          return e;
1133
        }
1134
    }
1135
  return NULL;
1136
}
1137
 
1138
/* Return the folded version of T if T, when folded, is a gimple
1139
   min_invariant.  Otherwise, return T.  */
1140
 
1141
static pre_expr
1142
fully_constant_expression (pre_expr e)
1143
{
1144
  switch (e->kind)
1145
    {
1146
    case CONSTANT:
1147
      return e;
1148
    case NARY:
1149
      {
1150
        vn_nary_op_t nary = PRE_EXPR_NARY (e);
1151
        switch (TREE_CODE_CLASS (nary->opcode))
1152
          {
1153
          case tcc_binary:
1154
          case tcc_comparison:
1155
            {
1156
              /* We have to go from trees to pre exprs to value ids to
1157
                 constants.  */
1158
              tree naryop0 = nary->op[0];
1159
              tree naryop1 = nary->op[1];
1160
              tree result;
1161
              if (!is_gimple_min_invariant (naryop0))
1162
                {
1163
                  pre_expr rep0 = get_or_alloc_expr_for (naryop0);
1164
                  unsigned int vrep0 = get_expr_value_id (rep0);
1165
                  tree const0 = get_constant_for_value_id (vrep0);
1166
                  if (const0)
1167
                    naryop0 = fold_convert (TREE_TYPE (naryop0), const0);
1168
                }
1169
              if (!is_gimple_min_invariant (naryop1))
1170
                {
1171
                  pre_expr rep1 = get_or_alloc_expr_for (naryop1);
1172
                  unsigned int vrep1 = get_expr_value_id (rep1);
1173
                  tree const1 = get_constant_for_value_id (vrep1);
1174
                  if (const1)
1175
                    naryop1 = fold_convert (TREE_TYPE (naryop1), const1);
1176
                }
1177
              result = fold_binary (nary->opcode, nary->type,
1178
                                    naryop0, naryop1);
1179
              if (result && is_gimple_min_invariant (result))
1180
                return get_or_alloc_expr_for_constant (result);
1181
              /* We might have simplified the expression to a
1182
                 SSA_NAME for example from x_1 * 1.  But we cannot
1183
                 insert a PHI for x_1 unconditionally as x_1 might
1184
                 not be available readily.  */
1185
              return e;
1186
            }
1187
          case tcc_reference:
1188
            if (nary->opcode != REALPART_EXPR
1189
                && nary->opcode != IMAGPART_EXPR
1190
                && nary->opcode != VIEW_CONVERT_EXPR)
1191
              return e;
1192
            /* Fallthrough.  */
1193
          case tcc_unary:
1194
            {
1195
              /* We have to go from trees to pre exprs to value ids to
1196
                 constants.  */
1197
              tree naryop0 = nary->op[0];
1198
              tree const0, result;
1199
              if (is_gimple_min_invariant (naryop0))
1200
                const0 = naryop0;
1201
              else
1202
                {
1203
                  pre_expr rep0 = get_or_alloc_expr_for (naryop0);
1204
                  unsigned int vrep0 = get_expr_value_id (rep0);
1205
                  const0 = get_constant_for_value_id (vrep0);
1206
                }
1207
              result = NULL;
1208
              if (const0)
1209
                {
1210
                  tree type1 = TREE_TYPE (nary->op[0]);
1211
                  const0 = fold_convert (type1, const0);
1212
                  result = fold_unary (nary->opcode, nary->type, const0);
1213
                }
1214
              if (result && is_gimple_min_invariant (result))
1215
                return get_or_alloc_expr_for_constant (result);
1216
              return e;
1217
            }
1218
          default:
1219
            return e;
1220
          }
1221
      }
1222
    case REFERENCE:
1223
      {
1224
        vn_reference_t ref = PRE_EXPR_REFERENCE (e);
1225
        tree folded;
1226
        if ((folded = fully_constant_vn_reference_p (ref)))
1227
          return get_or_alloc_expr_for_constant (folded);
1228
        return e;
1229
      }
1230
    default:
1231
      return e;
1232
    }
1233
  return e;
1234
}
1235
 
1236
/* Translate the VUSE backwards through phi nodes in PHIBLOCK, so that
1237
   it has the value it would have in BLOCK.  Set *SAME_VALID to true
1238
   in case the new vuse doesn't change the value id of the OPERANDS.  */
1239
 
1240
static tree
1241
translate_vuse_through_block (VEC (vn_reference_op_s, heap) *operands,
1242
                              alias_set_type set, tree type, tree vuse,
1243
                              basic_block phiblock,
1244
                              basic_block block, bool *same_valid)
1245
{
1246
  gimple phi = SSA_NAME_DEF_STMT (vuse);
1247
  ao_ref ref;
1248
  edge e = NULL;
1249
  bool use_oracle;
1250
 
1251
  *same_valid = true;
1252
 
1253
  if (gimple_bb (phi) != phiblock)
1254
    return vuse;
1255
 
1256
  use_oracle = ao_ref_init_from_vn_reference (&ref, set, type, operands);
1257
 
1258
  /* Use the alias-oracle to find either the PHI node in this block,
1259
     the first VUSE used in this block that is equivalent to vuse or
1260
     the first VUSE which definition in this block kills the value.  */
1261
  if (gimple_code (phi) == GIMPLE_PHI)
1262
    e = find_edge (block, phiblock);
1263
  else if (use_oracle)
1264
    while (!stmt_may_clobber_ref_p_1 (phi, &ref))
1265
      {
1266
        vuse = gimple_vuse (phi);
1267
        phi = SSA_NAME_DEF_STMT (vuse);
1268
        if (gimple_bb (phi) != phiblock)
1269
          return vuse;
1270
        if (gimple_code (phi) == GIMPLE_PHI)
1271
          {
1272
            e = find_edge (block, phiblock);
1273
            break;
1274
          }
1275
      }
1276
  else
1277
    return NULL_TREE;
1278
 
1279
  if (e)
1280
    {
1281
      if (use_oracle)
1282
        {
1283
          bitmap visited = NULL;
1284
          /* Try to find a vuse that dominates this phi node by skipping
1285
             non-clobbering statements.  */
1286
          vuse = get_continuation_for_phi (phi, &ref, &visited);
1287
          if (visited)
1288
            BITMAP_FREE (visited);
1289
        }
1290
      else
1291
        vuse = NULL_TREE;
1292
      if (!vuse)
1293
        {
1294
          /* If we didn't find any, the value ID can't stay the same,
1295
             but return the translated vuse.  */
1296
          *same_valid = false;
1297
          vuse = PHI_ARG_DEF (phi, e->dest_idx);
1298
        }
1299
      /* ??? We would like to return vuse here as this is the canonical
1300
         upmost vdef that this reference is associated with.  But during
1301
         insertion of the references into the hash tables we only ever
1302
         directly insert with their direct gimple_vuse, hence returning
1303
         something else would make us not find the other expression.  */
1304
      return PHI_ARG_DEF (phi, e->dest_idx);
1305
    }
1306
 
1307
  return NULL_TREE;
1308
}
1309
 
1310
/* Like bitmap_find_leader, but checks for the value existing in SET1 *or*
1311
   SET2.  This is used to avoid making a set consisting of the union
1312
   of PA_IN and ANTIC_IN during insert.  */
1313
 
1314
static inline pre_expr
1315
find_leader_in_sets (unsigned int val, bitmap_set_t set1, bitmap_set_t set2)
1316
{
1317
  pre_expr result;
1318
 
1319
  result = bitmap_find_leader (set1, val, NULL);
1320
  if (!result && set2)
1321
    result = bitmap_find_leader (set2, val, NULL);
1322
  return result;
1323
}
1324
 
1325
/* Get the tree type for our PRE expression e.  */
1326
 
1327
static tree
1328
get_expr_type (const pre_expr e)
1329
{
1330
  switch (e->kind)
1331
    {
1332
    case NAME:
1333
      return TREE_TYPE (PRE_EXPR_NAME (e));
1334
    case CONSTANT:
1335
      return TREE_TYPE (PRE_EXPR_CONSTANT (e));
1336
    case REFERENCE:
1337
      return PRE_EXPR_REFERENCE (e)->type;
1338
    case NARY:
1339
      return PRE_EXPR_NARY (e)->type;
1340
    }
1341
  gcc_unreachable();
1342
}
1343
 
1344
/* Get a representative SSA_NAME for a given expression.
1345
   Since all of our sub-expressions are treated as values, we require
1346
   them to be SSA_NAME's for simplicity.
1347
   Prior versions of GVNPRE used to use "value handles" here, so that
1348
   an expression would be VH.11 + VH.10 instead of d_3 + e_6.  In
1349
   either case, the operands are really values (IE we do not expect
1350
   them to be usable without finding leaders).  */
1351
 
1352
static tree
1353
get_representative_for (const pre_expr e)
1354
{
1355
  tree exprtype;
1356
  tree name;
1357
  unsigned int value_id = get_expr_value_id (e);
1358
 
1359
  switch (e->kind)
1360
    {
1361
    case NAME:
1362
      return PRE_EXPR_NAME (e);
1363
    case CONSTANT:
1364
      return PRE_EXPR_CONSTANT (e);
1365
    case NARY:
1366
    case REFERENCE:
1367
      {
1368
        /* Go through all of the expressions representing this value
1369
           and pick out an SSA_NAME.  */
1370
        unsigned int i;
1371
        bitmap_iterator bi;
1372
        bitmap_set_t exprs = VEC_index (bitmap_set_t, value_expressions,
1373
                                        value_id);
1374
        FOR_EACH_EXPR_ID_IN_SET (exprs, i, bi)
1375
          {
1376
            pre_expr rep = expression_for_id (i);
1377
            if (rep->kind == NAME)
1378
              return PRE_EXPR_NAME (rep);
1379
          }
1380
      }
1381
      break;
1382
    }
1383
  /* If we reached here we couldn't find an SSA_NAME.  This can
1384
     happen when we've discovered a value that has never appeared in
1385
     the program as set to an SSA_NAME, most likely as the result of
1386
     phi translation.  */
1387
  if (dump_file)
1388
    {
1389
      fprintf (dump_file,
1390
               "Could not find SSA_NAME representative for expression:");
1391
      print_pre_expr (dump_file, e);
1392
      fprintf (dump_file, "\n");
1393
    }
1394
 
1395
  exprtype = get_expr_type (e);
1396
 
1397
  /* Build and insert the assignment of the end result to the temporary
1398
     that we will return.  */
1399
  if (!pretemp || exprtype != TREE_TYPE (pretemp))
1400
    {
1401
      pretemp = create_tmp_reg (exprtype, "pretmp");
1402
      add_referenced_var (pretemp);
1403
    }
1404
 
1405
  name = make_ssa_name (pretemp, gimple_build_nop ());
1406
  VN_INFO_GET (name)->value_id = value_id;
1407
  if (e->kind == CONSTANT)
1408
    VN_INFO (name)->valnum = PRE_EXPR_CONSTANT (e);
1409
  else
1410
    VN_INFO (name)->valnum = name;
1411
 
1412
  add_to_value (value_id, get_or_alloc_expr_for_name (name));
1413
  if (dump_file)
1414
    {
1415
      fprintf (dump_file, "Created SSA_NAME representative ");
1416
      print_generic_expr (dump_file, name, 0);
1417
      fprintf (dump_file, " for expression:");
1418
      print_pre_expr (dump_file, e);
1419
      fprintf (dump_file, "\n");
1420
    }
1421
 
1422
  return name;
1423
}
1424
 
1425
 
1426
 
1427
static pre_expr
1428
phi_translate (pre_expr expr, bitmap_set_t set1, bitmap_set_t set2,
1429
               basic_block pred, basic_block phiblock);
1430
 
1431
/* Translate EXPR using phis in PHIBLOCK, so that it has the values of
1432
   the phis in PRED.  Return NULL if we can't find a leader for each part
1433
   of the translated expression.  */
1434
 
1435
static pre_expr
1436
phi_translate_1 (pre_expr expr, bitmap_set_t set1, bitmap_set_t set2,
1437
                 basic_block pred, basic_block phiblock)
1438
{
1439
  switch (expr->kind)
1440
    {
1441
    case NARY:
1442
      {
1443
        unsigned int i;
1444
        bool changed = false;
1445
        vn_nary_op_t nary = PRE_EXPR_NARY (expr);
1446
        vn_nary_op_t newnary = XALLOCAVAR (struct vn_nary_op_s,
1447
                                           sizeof_vn_nary_op (nary->length));
1448
        memcpy (newnary, nary, sizeof_vn_nary_op (nary->length));
1449
 
1450
        for (i = 0; i < newnary->length; i++)
1451
          {
1452
            if (TREE_CODE (newnary->op[i]) != SSA_NAME)
1453
              continue;
1454
            else
1455
              {
1456
                pre_expr leader, result;
1457
                unsigned int op_val_id = VN_INFO (newnary->op[i])->value_id;
1458
                leader = find_leader_in_sets (op_val_id, set1, set2);
1459
                result = phi_translate (leader, set1, set2, pred, phiblock);
1460
                if (result && result != leader)
1461
                  {
1462
                    tree name = get_representative_for (result);
1463
                    if (!name)
1464
                      return NULL;
1465
                    newnary->op[i] = name;
1466
                  }
1467
                else if (!result)
1468
                  return NULL;
1469
 
1470
                changed |= newnary->op[i] != nary->op[i];
1471
              }
1472
          }
1473
        if (changed)
1474
          {
1475
            pre_expr constant;
1476
            unsigned int new_val_id;
1477
 
1478
            tree result = vn_nary_op_lookup_pieces (newnary->length,
1479
                                                    newnary->opcode,
1480
                                                    newnary->type,
1481
                                                    &newnary->op[0],
1482
                                                    &nary);
1483
            if (result && is_gimple_min_invariant (result))
1484
              return get_or_alloc_expr_for_constant (result);
1485
 
1486
            expr = (pre_expr) pool_alloc (pre_expr_pool);
1487
            expr->kind = NARY;
1488
            expr->id = 0;
1489
            if (nary)
1490
              {
1491
                PRE_EXPR_NARY (expr) = nary;
1492
                constant = fully_constant_expression (expr);
1493
                if (constant != expr)
1494
                  return constant;
1495
 
1496
                new_val_id = nary->value_id;
1497
                get_or_alloc_expression_id (expr);
1498
              }
1499
            else
1500
              {
1501
                new_val_id = get_next_value_id ();
1502
                VEC_safe_grow_cleared (bitmap_set_t, heap,
1503
                                       value_expressions,
1504
                                       get_max_value_id() + 1);
1505
                nary = vn_nary_op_insert_pieces (newnary->length,
1506
                                                 newnary->opcode,
1507
                                                 newnary->type,
1508
                                                 &newnary->op[0],
1509
                                                 result, new_val_id);
1510
                PRE_EXPR_NARY (expr) = nary;
1511
                constant = fully_constant_expression (expr);
1512
                if (constant != expr)
1513
                  return constant;
1514
                get_or_alloc_expression_id (expr);
1515
              }
1516
            add_to_value (new_val_id, expr);
1517
          }
1518
        return expr;
1519
      }
1520
      break;
1521
 
1522
    case REFERENCE:
1523
      {
1524
        vn_reference_t ref = PRE_EXPR_REFERENCE (expr);
1525
        VEC (vn_reference_op_s, heap) *operands = ref->operands;
1526
        tree vuse = ref->vuse;
1527
        tree newvuse = vuse;
1528
        VEC (vn_reference_op_s, heap) *newoperands = NULL;
1529
        bool changed = false, same_valid = true;
1530
        unsigned int i, j, n;
1531
        vn_reference_op_t operand;
1532
        vn_reference_t newref;
1533
 
1534
        for (i = 0, j = 0;
1535
             VEC_iterate (vn_reference_op_s, operands, i, operand); i++, j++)
1536
          {
1537
            pre_expr opresult;
1538
            pre_expr leader;
1539
            tree op[3];
1540
            tree type = operand->type;
1541
            vn_reference_op_s newop = *operand;
1542
            op[0] = operand->op0;
1543
            op[1] = operand->op1;
1544
            op[2] = operand->op2;
1545
            for (n = 0; n < 3; ++n)
1546
              {
1547
                unsigned int op_val_id;
1548
                if (!op[n])
1549
                  continue;
1550
                if (TREE_CODE (op[n]) != SSA_NAME)
1551
                  {
1552
                    /* We can't possibly insert these.  */
1553
                    if (n != 0
1554
                        && !is_gimple_min_invariant (op[n]))
1555
                      break;
1556
                    continue;
1557
                  }
1558
                op_val_id = VN_INFO (op[n])->value_id;
1559
                leader = find_leader_in_sets (op_val_id, set1, set2);
1560
                if (!leader)
1561
                  break;
1562
                /* Make sure we do not recursively translate ourselves
1563
                   like for translating a[n_1] with the leader for
1564
                   n_1 being a[n_1].  */
1565
                if (get_expression_id (leader) != get_expression_id (expr))
1566
                  {
1567
                    opresult = phi_translate (leader, set1, set2,
1568
                                              pred, phiblock);
1569
                    if (!opresult)
1570
                      break;
1571
                    if (opresult != leader)
1572
                      {
1573
                        tree name = get_representative_for (opresult);
1574
                        if (!name)
1575
                          break;
1576
                        changed |= name != op[n];
1577
                        op[n] = name;
1578
                      }
1579
                  }
1580
              }
1581
            if (n != 3)
1582
              {
1583
                if (newoperands)
1584
                  VEC_free (vn_reference_op_s, heap, newoperands);
1585
                return NULL;
1586
              }
1587
            if (!newoperands)
1588
              newoperands = VEC_copy (vn_reference_op_s, heap, operands);
1589
            /* We may have changed from an SSA_NAME to a constant */
1590
            if (newop.opcode == SSA_NAME && TREE_CODE (op[0]) != SSA_NAME)
1591
              newop.opcode = TREE_CODE (op[0]);
1592
            newop.type = type;
1593
            newop.op0 = op[0];
1594
            newop.op1 = op[1];
1595
            newop.op2 = op[2];
1596
            /* If it transforms a non-constant ARRAY_REF into a constant
1597
               one, adjust the constant offset.  */
1598
            if (newop.opcode == ARRAY_REF
1599
                && newop.off == -1
1600
                && TREE_CODE (op[0]) == INTEGER_CST
1601
                && TREE_CODE (op[1]) == INTEGER_CST
1602
                && TREE_CODE (op[2]) == INTEGER_CST)
1603
              {
1604
                double_int off = tree_to_double_int (op[0]);
1605
                off = double_int_add (off,
1606
                                      double_int_neg
1607
                                        (tree_to_double_int (op[1])));
1608
                off = double_int_mul (off, tree_to_double_int (op[2]));
1609
                if (double_int_fits_in_shwi_p (off))
1610
                  newop.off = off.low;
1611
              }
1612
            VEC_replace (vn_reference_op_s, newoperands, j, &newop);
1613
            /* If it transforms from an SSA_NAME to an address, fold with
1614
               a preceding indirect reference.  */
1615
            if (j > 0 && op[0] && TREE_CODE (op[0]) == ADDR_EXPR
1616
                && VEC_index (vn_reference_op_s,
1617
                              newoperands, j - 1)->opcode == MEM_REF)
1618
              vn_reference_fold_indirect (&newoperands, &j);
1619
          }
1620
        if (i != VEC_length (vn_reference_op_s, operands))
1621
          {
1622
            if (newoperands)
1623
              VEC_free (vn_reference_op_s, heap, newoperands);
1624
            return NULL;
1625
          }
1626
 
1627
        if (vuse)
1628
          {
1629
            newvuse = translate_vuse_through_block (newoperands,
1630
                                                    ref->set, ref->type,
1631
                                                    vuse, phiblock, pred,
1632
                                                    &same_valid);
1633
            if (newvuse == NULL_TREE)
1634
              {
1635
                VEC_free (vn_reference_op_s, heap, newoperands);
1636
                return NULL;
1637
              }
1638
          }
1639
 
1640
        if (changed || newvuse != vuse)
1641
          {
1642
            unsigned int new_val_id;
1643
            pre_expr constant;
1644
            bool converted = false;
1645
 
1646
            tree result = vn_reference_lookup_pieces (newvuse, ref->set,
1647
                                                      ref->type,
1648
                                                      newoperands,
1649
                                                      &newref, VN_WALK);
1650
            if (result)
1651
              VEC_free (vn_reference_op_s, heap, newoperands);
1652
 
1653
            if (result
1654
                && !useless_type_conversion_p (ref->type, TREE_TYPE (result)))
1655
              {
1656
                result = fold_build1 (VIEW_CONVERT_EXPR, ref->type, result);
1657
                converted = true;
1658
              }
1659
            else if (!result && newref
1660
                     && !useless_type_conversion_p (ref->type, newref->type))
1661
              {
1662
                VEC_free (vn_reference_op_s, heap, newoperands);
1663
                return NULL;
1664
              }
1665
 
1666
            if (result && is_gimple_min_invariant (result))
1667
              {
1668
                gcc_assert (!newoperands);
1669
                return get_or_alloc_expr_for_constant (result);
1670
              }
1671
 
1672
            expr = (pre_expr) pool_alloc (pre_expr_pool);
1673
            expr->kind = REFERENCE;
1674
            expr->id = 0;
1675
 
1676
            if (converted)
1677
              {
1678
                vn_nary_op_t nary;
1679
                tree nresult;
1680
 
1681
                gcc_assert (CONVERT_EXPR_P (result)
1682
                            || TREE_CODE (result) == VIEW_CONVERT_EXPR);
1683
 
1684
                nresult = vn_nary_op_lookup_pieces (1, TREE_CODE (result),
1685
                                                    TREE_TYPE (result),
1686
                                                    &TREE_OPERAND (result, 0),
1687
                                                    &nary);
1688
                if (nresult && is_gimple_min_invariant (nresult))
1689
                  return get_or_alloc_expr_for_constant (nresult);
1690
 
1691
                expr->kind = NARY;
1692
                if (nary)
1693
                  {
1694
                    PRE_EXPR_NARY (expr) = nary;
1695
                    constant = fully_constant_expression (expr);
1696
                    if (constant != expr)
1697
                      return constant;
1698
 
1699
                    new_val_id = nary->value_id;
1700
                    get_or_alloc_expression_id (expr);
1701
                  }
1702
                else
1703
                  {
1704
                    new_val_id = get_next_value_id ();
1705
                    VEC_safe_grow_cleared (bitmap_set_t, heap,
1706
                                           value_expressions,
1707
                                           get_max_value_id() + 1);
1708
                    nary = vn_nary_op_insert_pieces (1, TREE_CODE (result),
1709
                                                     TREE_TYPE (result),
1710
                                                     &TREE_OPERAND (result, 0),
1711
                                                     NULL_TREE,
1712
                                                     new_val_id);
1713
                    PRE_EXPR_NARY (expr) = nary;
1714
                    constant = fully_constant_expression (expr);
1715
                    if (constant != expr)
1716
                      return constant;
1717
                    get_or_alloc_expression_id (expr);
1718
                  }
1719
              }
1720
            else if (newref)
1721
              {
1722
                PRE_EXPR_REFERENCE (expr) = newref;
1723
                constant = fully_constant_expression (expr);
1724
                if (constant != expr)
1725
                  return constant;
1726
 
1727
                new_val_id = newref->value_id;
1728
                get_or_alloc_expression_id (expr);
1729
              }
1730
            else
1731
              {
1732
                if (changed || !same_valid)
1733
                  {
1734
                    new_val_id = get_next_value_id ();
1735
                    VEC_safe_grow_cleared (bitmap_set_t, heap,
1736
                                           value_expressions,
1737
                                           get_max_value_id() + 1);
1738
                  }
1739
                else
1740
                  new_val_id = ref->value_id;
1741
                newref = vn_reference_insert_pieces (newvuse, ref->set,
1742
                                                     ref->type,
1743
                                                     newoperands,
1744
                                                     result, new_val_id);
1745
                newoperands = NULL;
1746
                PRE_EXPR_REFERENCE (expr) = newref;
1747
                constant = fully_constant_expression (expr);
1748
                if (constant != expr)
1749
                  return constant;
1750
                get_or_alloc_expression_id (expr);
1751
              }
1752
            add_to_value (new_val_id, expr);
1753
          }
1754
        VEC_free (vn_reference_op_s, heap, newoperands);
1755
        return expr;
1756
      }
1757
      break;
1758
 
1759
    case NAME:
1760
      {
1761
        gimple phi = NULL;
1762
        edge e;
1763
        gimple def_stmt;
1764
        tree name = PRE_EXPR_NAME (expr);
1765
 
1766
        def_stmt = SSA_NAME_DEF_STMT (name);
1767
        if (gimple_code (def_stmt) == GIMPLE_PHI
1768
            && gimple_bb (def_stmt) == phiblock)
1769
          phi = def_stmt;
1770
        else
1771
          return expr;
1772
 
1773
        e = find_edge (pred, gimple_bb (phi));
1774
        if (e)
1775
          {
1776
            tree def = PHI_ARG_DEF (phi, e->dest_idx);
1777
            pre_expr newexpr;
1778
 
1779
            if (TREE_CODE (def) == SSA_NAME)
1780
              def = VN_INFO (def)->valnum;
1781
 
1782
            /* Handle constant. */
1783
            if (is_gimple_min_invariant (def))
1784
              return get_or_alloc_expr_for_constant (def);
1785
 
1786
            if (TREE_CODE (def) == SSA_NAME && ssa_undefined_value_p (def))
1787
              return NULL;
1788
 
1789
            newexpr = get_or_alloc_expr_for_name (def);
1790
            return newexpr;
1791
          }
1792
      }
1793
      return expr;
1794
 
1795
    default:
1796
      gcc_unreachable ();
1797
    }
1798
}
1799
 
1800
/* Wrapper around phi_translate_1 providing caching functionality.  */
1801
 
1802
static pre_expr
1803
phi_translate (pre_expr expr, bitmap_set_t set1, bitmap_set_t set2,
1804
               basic_block pred, basic_block phiblock)
1805
{
1806
  pre_expr phitrans;
1807
 
1808
  if (!expr)
1809
    return NULL;
1810
 
1811
  /* Constants contain no values that need translation.  */
1812
  if (expr->kind == CONSTANT)
1813
    return expr;
1814
 
1815
  if (value_id_constant_p (get_expr_value_id (expr)))
1816
    return expr;
1817
 
1818
  if (expr->kind != NAME)
1819
    {
1820
      phitrans = phi_trans_lookup (expr, pred);
1821
      if (phitrans)
1822
        return phitrans;
1823
    }
1824
 
1825
  /* Translate.  */
1826
  phitrans = phi_translate_1 (expr, set1, set2, pred, phiblock);
1827
 
1828
  /* Don't add empty translations to the cache.  Neither add
1829
     translations of NAMEs as those are cheap to translate.  */
1830
  if (phitrans
1831
      && expr->kind != NAME)
1832
    phi_trans_add (expr, phitrans, pred);
1833
 
1834
  return phitrans;
1835
}
1836
 
1837
 
1838
/* For each expression in SET, translate the values through phi nodes
1839
   in PHIBLOCK using edge PHIBLOCK->PRED, and store the resulting
1840
   expressions in DEST.  */
1841
 
1842
static void
1843
phi_translate_set (bitmap_set_t dest, bitmap_set_t set, basic_block pred,
1844
                   basic_block phiblock)
1845
{
1846
  VEC (pre_expr, heap) *exprs;
1847
  pre_expr expr;
1848
  int i;
1849
 
1850
  if (gimple_seq_empty_p (phi_nodes (phiblock)))
1851
    {
1852
      bitmap_set_copy (dest, set);
1853
      return;
1854
    }
1855
 
1856
  exprs = sorted_array_from_bitmap_set (set);
1857
  FOR_EACH_VEC_ELT (pre_expr, exprs, i, expr)
1858
    {
1859
      pre_expr translated;
1860
      translated = phi_translate (expr, set, NULL, pred, phiblock);
1861
      if (!translated)
1862
        continue;
1863
 
1864
      /* We might end up with multiple expressions from SET being
1865
         translated to the same value.  In this case we do not want
1866
         to retain the NARY or REFERENCE expression but prefer a NAME
1867
         which would be the leader.  */
1868
      if (translated->kind == NAME)
1869
        bitmap_value_replace_in_set (dest, translated);
1870
      else
1871
        bitmap_value_insert_into_set (dest, translated);
1872
    }
1873
  VEC_free (pre_expr, heap, exprs);
1874
}
1875
 
1876
/* Find the leader for a value (i.e., the name representing that
1877
   value) in a given set, and return it.  If STMT is non-NULL it
1878
   makes sure the defining statement for the leader dominates it.
1879
   Return NULL if no leader is found.  */
1880
 
1881
static pre_expr
1882
bitmap_find_leader (bitmap_set_t set, unsigned int val, gimple stmt)
1883
{
1884
  if (value_id_constant_p (val))
1885
    {
1886
      unsigned int i;
1887
      bitmap_iterator bi;
1888
      bitmap_set_t exprset = VEC_index (bitmap_set_t, value_expressions, val);
1889
 
1890
      FOR_EACH_EXPR_ID_IN_SET (exprset, i, bi)
1891
        {
1892
          pre_expr expr = expression_for_id (i);
1893
          if (expr->kind == CONSTANT)
1894
            return expr;
1895
        }
1896
    }
1897
  if (bitmap_set_contains_value (set, val))
1898
    {
1899
      /* Rather than walk the entire bitmap of expressions, and see
1900
         whether any of them has the value we are looking for, we look
1901
         at the reverse mapping, which tells us the set of expressions
1902
         that have a given value (IE value->expressions with that
1903
         value) and see if any of those expressions are in our set.
1904
         The number of expressions per value is usually significantly
1905
         less than the number of expressions in the set.  In fact, for
1906
         large testcases, doing it this way is roughly 5-10x faster
1907
         than walking the bitmap.
1908
         If this is somehow a significant lose for some cases, we can
1909
         choose which set to walk based on which set is smaller.  */
1910
      unsigned int i;
1911
      bitmap_iterator bi;
1912
      bitmap_set_t exprset = VEC_index (bitmap_set_t, value_expressions, val);
1913
 
1914
      EXECUTE_IF_AND_IN_BITMAP (&exprset->expressions,
1915
                                &set->expressions, 0, i, bi)
1916
        {
1917
          pre_expr val = expression_for_id (i);
1918
          /* At the point where stmt is not null, there should always
1919
             be an SSA_NAME first in the list of expressions.  */
1920
          if (stmt)
1921
            {
1922
              gimple def_stmt = SSA_NAME_DEF_STMT (PRE_EXPR_NAME (val));
1923
              if (gimple_code (def_stmt) != GIMPLE_PHI
1924
                  && gimple_bb (def_stmt) == gimple_bb (stmt)
1925
                  /* PRE insertions are at the end of the basic-block
1926
                     and have UID 0.  */
1927
                  && (gimple_uid (def_stmt) == 0
1928
                      || gimple_uid (def_stmt) >= gimple_uid (stmt)))
1929
                continue;
1930
            }
1931
          return val;
1932
        }
1933
    }
1934
  return NULL;
1935
}
1936
 
1937
/* Determine if EXPR, a memory expression, is ANTIC_IN at the top of
1938
   BLOCK by seeing if it is not killed in the block.  Note that we are
1939
   only determining whether there is a store that kills it.  Because
1940
   of the order in which clean iterates over values, we are guaranteed
1941
   that altered operands will have caused us to be eliminated from the
1942
   ANTIC_IN set already.  */
1943
 
1944
static bool
1945
value_dies_in_block_x (pre_expr expr, basic_block block)
1946
{
1947
  tree vuse = PRE_EXPR_REFERENCE (expr)->vuse;
1948
  vn_reference_t refx = PRE_EXPR_REFERENCE (expr);
1949
  gimple def;
1950
  gimple_stmt_iterator gsi;
1951
  unsigned id = get_expression_id (expr);
1952
  bool res = false;
1953
  ao_ref ref;
1954
 
1955
  if (!vuse)
1956
    return false;
1957
 
1958
  /* Lookup a previously calculated result.  */
1959
  if (EXPR_DIES (block)
1960
      && bitmap_bit_p (EXPR_DIES (block), id * 2))
1961
    return bitmap_bit_p (EXPR_DIES (block), id * 2 + 1);
1962
 
1963
  /* A memory expression {e, VUSE} dies in the block if there is a
1964
     statement that may clobber e.  If, starting statement walk from the
1965
     top of the basic block, a statement uses VUSE there can be no kill
1966
     inbetween that use and the original statement that loaded {e, VUSE},
1967
     so we can stop walking.  */
1968
  ref.base = NULL_TREE;
1969
  for (gsi = gsi_start_bb (block); !gsi_end_p (gsi); gsi_next (&gsi))
1970
    {
1971
      tree def_vuse, def_vdef;
1972
      def = gsi_stmt (gsi);
1973
      def_vuse = gimple_vuse (def);
1974
      def_vdef = gimple_vdef (def);
1975
 
1976
      /* Not a memory statement.  */
1977
      if (!def_vuse)
1978
        continue;
1979
 
1980
      /* Not a may-def.  */
1981
      if (!def_vdef)
1982
        {
1983
          /* A load with the same VUSE, we're done.  */
1984
          if (def_vuse == vuse)
1985
            break;
1986
 
1987
          continue;
1988
        }
1989
 
1990
      /* Init ref only if we really need it.  */
1991
      if (ref.base == NULL_TREE
1992
          && !ao_ref_init_from_vn_reference (&ref, refx->set, refx->type,
1993
                                             refx->operands))
1994
        {
1995
          res = true;
1996
          break;
1997
        }
1998
      /* If the statement may clobber expr, it dies.  */
1999
      if (stmt_may_clobber_ref_p_1 (def, &ref))
2000
        {
2001
          res = true;
2002
          break;
2003
        }
2004
    }
2005
 
2006
  /* Remember the result.  */
2007
  if (!EXPR_DIES (block))
2008
    EXPR_DIES (block) = BITMAP_ALLOC (&grand_bitmap_obstack);
2009
  bitmap_set_bit (EXPR_DIES (block), id * 2);
2010
  if (res)
2011
    bitmap_set_bit (EXPR_DIES (block), id * 2 + 1);
2012
 
2013
  return res;
2014
}
2015
 
2016
 
2017
#define union_contains_value(SET1, SET2, VAL)                   \
2018
  (bitmap_set_contains_value ((SET1), (VAL))                    \
2019
   || ((SET2) && bitmap_set_contains_value ((SET2), (VAL))))
2020
 
2021
/* Determine if vn_reference_op_t VRO is legal in SET1 U SET2.
2022
 */
2023
static bool
2024
vro_valid_in_sets (bitmap_set_t set1, bitmap_set_t set2,
2025
                   vn_reference_op_t vro)
2026
{
2027
  if (vro->op0 && TREE_CODE (vro->op0) == SSA_NAME)
2028
    {
2029
      struct pre_expr_d temp;
2030
      temp.kind = NAME;
2031
      temp.id = 0;
2032
      PRE_EXPR_NAME (&temp) = vro->op0;
2033
      temp.id = lookup_expression_id (&temp);
2034
      if (temp.id == 0)
2035
        return false;
2036
      if (!union_contains_value (set1, set2,
2037
                                 get_expr_value_id (&temp)))
2038
        return false;
2039
    }
2040
  if (vro->op1 && TREE_CODE (vro->op1) == SSA_NAME)
2041
    {
2042
      struct pre_expr_d temp;
2043
      temp.kind = NAME;
2044
      temp.id = 0;
2045
      PRE_EXPR_NAME (&temp) = vro->op1;
2046
      temp.id = lookup_expression_id (&temp);
2047
      if (temp.id == 0)
2048
        return false;
2049
      if (!union_contains_value (set1, set2,
2050
                                 get_expr_value_id (&temp)))
2051
        return false;
2052
    }
2053
 
2054
  if (vro->op2 && TREE_CODE (vro->op2) == SSA_NAME)
2055
    {
2056
      struct pre_expr_d temp;
2057
      temp.kind = NAME;
2058
      temp.id = 0;
2059
      PRE_EXPR_NAME (&temp) = vro->op2;
2060
      temp.id = lookup_expression_id (&temp);
2061
      if (temp.id == 0)
2062
        return false;
2063
      if (!union_contains_value (set1, set2,
2064
                                 get_expr_value_id (&temp)))
2065
        return false;
2066
    }
2067
 
2068
  return true;
2069
}
2070
 
2071
/* Determine if the expression EXPR is valid in SET1 U SET2.
2072
   ONLY SET2 CAN BE NULL.
2073
   This means that we have a leader for each part of the expression
2074
   (if it consists of values), or the expression is an SSA_NAME.
2075
   For loads/calls, we also see if the vuse is killed in this block.  */
2076
 
2077
static bool
2078
valid_in_sets (bitmap_set_t set1, bitmap_set_t set2, pre_expr expr,
2079
               basic_block block)
2080
{
2081
  switch (expr->kind)
2082
    {
2083
    case NAME:
2084
      return bitmap_set_contains_expr (AVAIL_OUT (block), expr);
2085
    case NARY:
2086
      {
2087
        unsigned int i;
2088
        vn_nary_op_t nary = PRE_EXPR_NARY (expr);
2089
        for (i = 0; i < nary->length; i++)
2090
          {
2091
            if (TREE_CODE (nary->op[i]) == SSA_NAME)
2092
              {
2093
                struct pre_expr_d temp;
2094
                temp.kind = NAME;
2095
                temp.id = 0;
2096
                PRE_EXPR_NAME (&temp) = nary->op[i];
2097
                temp.id = lookup_expression_id (&temp);
2098
                if (temp.id == 0)
2099
                  return false;
2100
                if (!union_contains_value (set1, set2,
2101
                                           get_expr_value_id (&temp)))
2102
                  return false;
2103
              }
2104
          }
2105
        /* If the NARY may trap make sure the block does not contain
2106
           a possible exit point.
2107
           ???  This is overly conservative if we translate AVAIL_OUT
2108
           as the available expression might be after the exit point.  */
2109
        if (BB_MAY_NOTRETURN (block)
2110
            && vn_nary_may_trap (nary))
2111
          return false;
2112
        return true;
2113
      }
2114
      break;
2115
    case REFERENCE:
2116
      {
2117
        vn_reference_t ref = PRE_EXPR_REFERENCE (expr);
2118
        vn_reference_op_t vro;
2119
        unsigned int i;
2120
 
2121
        FOR_EACH_VEC_ELT (vn_reference_op_s, ref->operands, i, vro)
2122
          {
2123
            if (!vro_valid_in_sets (set1, set2, vro))
2124
              return false;
2125
          }
2126
        if (ref->vuse)
2127
          {
2128
            gimple def_stmt = SSA_NAME_DEF_STMT (ref->vuse);
2129
            if (!gimple_nop_p (def_stmt)
2130
                && gimple_bb (def_stmt) != block
2131
                && !dominated_by_p (CDI_DOMINATORS,
2132
                                    block, gimple_bb (def_stmt)))
2133
              return false;
2134
          }
2135
        return !value_dies_in_block_x (expr, block);
2136
      }
2137
    default:
2138
      gcc_unreachable ();
2139
    }
2140
}
2141
 
2142
/* Clean the set of expressions that are no longer valid in SET1 or
2143
   SET2.  This means expressions that are made up of values we have no
2144
   leaders for in SET1 or SET2.  This version is used for partial
2145
   anticipation, which means it is not valid in either ANTIC_IN or
2146
   PA_IN.  */
2147
 
2148
static void
2149
dependent_clean (bitmap_set_t set1, bitmap_set_t set2, basic_block block)
2150
{
2151
  VEC (pre_expr, heap) *exprs = sorted_array_from_bitmap_set (set1);
2152
  pre_expr expr;
2153
  int i;
2154
 
2155
  FOR_EACH_VEC_ELT (pre_expr, exprs, i, expr)
2156
    {
2157
      if (!valid_in_sets (set1, set2, expr, block))
2158
        bitmap_remove_from_set (set1, expr);
2159
    }
2160
  VEC_free (pre_expr, heap, exprs);
2161
}
2162
 
2163
/* Clean the set of expressions that are no longer valid in SET.  This
2164
   means expressions that are made up of values we have no leaders for
2165
   in SET.  */
2166
 
2167
static void
2168
clean (bitmap_set_t set, basic_block block)
2169
{
2170
  VEC (pre_expr, heap) *exprs = sorted_array_from_bitmap_set (set);
2171
  pre_expr expr;
2172
  int i;
2173
 
2174
  FOR_EACH_VEC_ELT (pre_expr, exprs, i, expr)
2175
    {
2176
      if (!valid_in_sets (set, NULL, expr, block))
2177
        bitmap_remove_from_set (set, expr);
2178
    }
2179
  VEC_free (pre_expr, heap, exprs);
2180
}
2181
 
2182
static sbitmap has_abnormal_preds;
2183
 
2184
/* List of blocks that may have changed during ANTIC computation and
2185
   thus need to be iterated over.  */
2186
 
2187
static sbitmap changed_blocks;
2188
 
2189
/* Decide whether to defer a block for a later iteration, or PHI
2190
   translate SOURCE to DEST using phis in PHIBLOCK.  Return false if we
2191
   should defer the block, and true if we processed it.  */
2192
 
2193
static bool
2194
defer_or_phi_translate_block (bitmap_set_t dest, bitmap_set_t source,
2195
                              basic_block block, basic_block phiblock)
2196
{
2197
  if (!BB_VISITED (phiblock))
2198
    {
2199
      SET_BIT (changed_blocks, block->index);
2200
      BB_VISITED (block) = 0;
2201
      BB_DEFERRED (block) = 1;
2202
      return false;
2203
    }
2204
  else
2205
    phi_translate_set (dest, source, block, phiblock);
2206
  return true;
2207
}
2208
 
2209
/* Compute the ANTIC set for BLOCK.
2210
 
2211
   If succs(BLOCK) > 1 then
2212
     ANTIC_OUT[BLOCK] = intersection of ANTIC_IN[b] for all succ(BLOCK)
2213
   else if succs(BLOCK) == 1 then
2214
     ANTIC_OUT[BLOCK] = phi_translate (ANTIC_IN[succ(BLOCK)])
2215
 
2216
   ANTIC_IN[BLOCK] = clean(ANTIC_OUT[BLOCK] U EXP_GEN[BLOCK] - TMP_GEN[BLOCK])
2217
*/
2218
 
2219
static bool
2220
compute_antic_aux (basic_block block, bool block_has_abnormal_pred_edge)
2221
{
2222
  bool changed = false;
2223
  bitmap_set_t S, old, ANTIC_OUT;
2224
  bitmap_iterator bi;
2225
  unsigned int bii;
2226
  edge e;
2227
  edge_iterator ei;
2228
 
2229
  old = ANTIC_OUT = S = NULL;
2230
  BB_VISITED (block) = 1;
2231
 
2232
  /* If any edges from predecessors are abnormal, antic_in is empty,
2233
     so do nothing.  */
2234
  if (block_has_abnormal_pred_edge)
2235
    goto maybe_dump_sets;
2236
 
2237
  old = ANTIC_IN (block);
2238
  ANTIC_OUT = bitmap_set_new ();
2239
 
2240
  /* If the block has no successors, ANTIC_OUT is empty.  */
2241
  if (EDGE_COUNT (block->succs) == 0)
2242
    ;
2243
  /* If we have one successor, we could have some phi nodes to
2244
     translate through.  */
2245
  else if (single_succ_p (block))
2246
    {
2247
      basic_block succ_bb = single_succ (block);
2248
 
2249
      /* We trade iterations of the dataflow equations for having to
2250
         phi translate the maximal set, which is incredibly slow
2251
         (since the maximal set often has 300+ members, even when you
2252
         have a small number of blocks).
2253
         Basically, we defer the computation of ANTIC for this block
2254
         until we have processed it's successor, which will inevitably
2255
         have a *much* smaller set of values to phi translate once
2256
         clean has been run on it.
2257
         The cost of doing this is that we technically perform more
2258
         iterations, however, they are lower cost iterations.
2259
 
2260
         Timings for PRE on tramp3d-v4:
2261
         without maximal set fix: 11 seconds
2262
         with maximal set fix/without deferring: 26 seconds
2263
         with maximal set fix/with deferring: 11 seconds
2264
     */
2265
 
2266
      if (!defer_or_phi_translate_block (ANTIC_OUT, ANTIC_IN (succ_bb),
2267
                                        block, succ_bb))
2268
        {
2269
          changed = true;
2270
          goto maybe_dump_sets;
2271
        }
2272
    }
2273
  /* If we have multiple successors, we take the intersection of all of
2274
     them.  Note that in the case of loop exit phi nodes, we may have
2275
     phis to translate through.  */
2276
  else
2277
    {
2278
      VEC(basic_block, heap) * worklist;
2279
      size_t i;
2280
      basic_block bprime, first = NULL;
2281
 
2282
      worklist = VEC_alloc (basic_block, heap, EDGE_COUNT (block->succs));
2283
      FOR_EACH_EDGE (e, ei, block->succs)
2284
        {
2285
          if (!first
2286
              && BB_VISITED (e->dest))
2287
            first = e->dest;
2288
          else if (BB_VISITED (e->dest))
2289
            VEC_quick_push (basic_block, worklist, e->dest);
2290
        }
2291
 
2292
      /* Of multiple successors we have to have visited one already.  */
2293
      if (!first)
2294
        {
2295
          SET_BIT (changed_blocks, block->index);
2296
          BB_VISITED (block) = 0;
2297
          BB_DEFERRED (block) = 1;
2298
          changed = true;
2299
          VEC_free (basic_block, heap, worklist);
2300
          goto maybe_dump_sets;
2301
        }
2302
 
2303
      if (!gimple_seq_empty_p (phi_nodes (first)))
2304
        phi_translate_set (ANTIC_OUT, ANTIC_IN (first), block, first);
2305
      else
2306
        bitmap_set_copy (ANTIC_OUT, ANTIC_IN (first));
2307
 
2308
      FOR_EACH_VEC_ELT (basic_block, worklist, i, bprime)
2309
        {
2310
          if (!gimple_seq_empty_p (phi_nodes (bprime)))
2311
            {
2312
              bitmap_set_t tmp = bitmap_set_new ();
2313
              phi_translate_set (tmp, ANTIC_IN (bprime), block, bprime);
2314
              bitmap_set_and (ANTIC_OUT, tmp);
2315
              bitmap_set_free (tmp);
2316
            }
2317
          else
2318
            bitmap_set_and (ANTIC_OUT, ANTIC_IN (bprime));
2319
        }
2320
      VEC_free (basic_block, heap, worklist);
2321
    }
2322
 
2323
  /* Generate ANTIC_OUT - TMP_GEN.  */
2324
  S = bitmap_set_subtract (ANTIC_OUT, TMP_GEN (block));
2325
 
2326
  /* Start ANTIC_IN with EXP_GEN - TMP_GEN.  */
2327
  ANTIC_IN (block) = bitmap_set_subtract (EXP_GEN (block),
2328
                                          TMP_GEN (block));
2329
 
2330
  /* Then union in the ANTIC_OUT - TMP_GEN values,
2331
     to get ANTIC_OUT U EXP_GEN - TMP_GEN */
2332
  FOR_EACH_EXPR_ID_IN_SET (S, bii, bi)
2333
    bitmap_value_insert_into_set (ANTIC_IN (block),
2334
                                  expression_for_id (bii));
2335
 
2336
  clean (ANTIC_IN (block), block);
2337
 
2338
  if (!bitmap_set_equal (old, ANTIC_IN (block)))
2339
    {
2340
      changed = true;
2341
      SET_BIT (changed_blocks, block->index);
2342
      FOR_EACH_EDGE (e, ei, block->preds)
2343
        SET_BIT (changed_blocks, e->src->index);
2344
    }
2345
  else
2346
    RESET_BIT (changed_blocks, block->index);
2347
 
2348
 maybe_dump_sets:
2349
  if (dump_file && (dump_flags & TDF_DETAILS))
2350
    {
2351
      if (!BB_DEFERRED (block) || BB_VISITED (block))
2352
        {
2353
          if (ANTIC_OUT)
2354
            print_bitmap_set (dump_file, ANTIC_OUT, "ANTIC_OUT", block->index);
2355
 
2356
          print_bitmap_set (dump_file, ANTIC_IN (block), "ANTIC_IN",
2357
                            block->index);
2358
 
2359
          if (S)
2360
            print_bitmap_set (dump_file, S, "S", block->index);
2361
        }
2362
      else
2363
        {
2364
          fprintf (dump_file,
2365
                   "Block %d was deferred for a future iteration.\n",
2366
                   block->index);
2367
        }
2368
    }
2369
  if (old)
2370
    bitmap_set_free (old);
2371
  if (S)
2372
    bitmap_set_free (S);
2373
  if (ANTIC_OUT)
2374
    bitmap_set_free (ANTIC_OUT);
2375
  return changed;
2376
}
2377
 
2378
/* Compute PARTIAL_ANTIC for BLOCK.
2379
 
2380
   If succs(BLOCK) > 1 then
2381
     PA_OUT[BLOCK] = value wise union of PA_IN[b] + all ANTIC_IN not
2382
     in ANTIC_OUT for all succ(BLOCK)
2383
   else if succs(BLOCK) == 1 then
2384
     PA_OUT[BLOCK] = phi_translate (PA_IN[succ(BLOCK)])
2385
 
2386
   PA_IN[BLOCK] = dependent_clean(PA_OUT[BLOCK] - TMP_GEN[BLOCK]
2387
                                  - ANTIC_IN[BLOCK])
2388
 
2389
*/
2390
static bool
2391
compute_partial_antic_aux (basic_block block,
2392
                           bool block_has_abnormal_pred_edge)
2393
{
2394
  bool changed = false;
2395
  bitmap_set_t old_PA_IN;
2396
  bitmap_set_t PA_OUT;
2397
  edge e;
2398
  edge_iterator ei;
2399
  unsigned long max_pa = PARAM_VALUE (PARAM_MAX_PARTIAL_ANTIC_LENGTH);
2400
 
2401
  old_PA_IN = PA_OUT = NULL;
2402
 
2403
  /* If any edges from predecessors are abnormal, antic_in is empty,
2404
     so do nothing.  */
2405
  if (block_has_abnormal_pred_edge)
2406
    goto maybe_dump_sets;
2407
 
2408
  /* If there are too many partially anticipatable values in the
2409
     block, phi_translate_set can take an exponential time: stop
2410
     before the translation starts.  */
2411
  if (max_pa
2412
      && single_succ_p (block)
2413
      && bitmap_count_bits (&PA_IN (single_succ (block))->values) > max_pa)
2414
    goto maybe_dump_sets;
2415
 
2416
  old_PA_IN = PA_IN (block);
2417
  PA_OUT = bitmap_set_new ();
2418
 
2419
  /* If the block has no successors, ANTIC_OUT is empty.  */
2420
  if (EDGE_COUNT (block->succs) == 0)
2421
    ;
2422
  /* If we have one successor, we could have some phi nodes to
2423
     translate through.  Note that we can't phi translate across DFS
2424
     back edges in partial antic, because it uses a union operation on
2425
     the successors.  For recurrences like IV's, we will end up
2426
     generating a new value in the set on each go around (i + 3 (VH.1)
2427
     VH.1 + 1 (VH.2), VH.2 + 1 (VH.3), etc), forever.  */
2428
  else if (single_succ_p (block))
2429
    {
2430
      basic_block succ = single_succ (block);
2431
      if (!(single_succ_edge (block)->flags & EDGE_DFS_BACK))
2432
        phi_translate_set (PA_OUT, PA_IN (succ), block, succ);
2433
    }
2434
  /* If we have multiple successors, we take the union of all of
2435
     them.  */
2436
  else
2437
    {
2438
      VEC(basic_block, heap) * worklist;
2439
      size_t i;
2440
      basic_block bprime;
2441
 
2442
      worklist = VEC_alloc (basic_block, heap, EDGE_COUNT (block->succs));
2443
      FOR_EACH_EDGE (e, ei, block->succs)
2444
        {
2445
          if (e->flags & EDGE_DFS_BACK)
2446
            continue;
2447
          VEC_quick_push (basic_block, worklist, e->dest);
2448
        }
2449
      if (VEC_length (basic_block, worklist) > 0)
2450
        {
2451
          FOR_EACH_VEC_ELT (basic_block, worklist, i, bprime)
2452
            {
2453
              unsigned int i;
2454
              bitmap_iterator bi;
2455
 
2456
              FOR_EACH_EXPR_ID_IN_SET (ANTIC_IN (bprime), i, bi)
2457
                bitmap_value_insert_into_set (PA_OUT,
2458
                                              expression_for_id (i));
2459
              if (!gimple_seq_empty_p (phi_nodes (bprime)))
2460
                {
2461
                  bitmap_set_t pa_in = bitmap_set_new ();
2462
                  phi_translate_set (pa_in, PA_IN (bprime), block, bprime);
2463
                  FOR_EACH_EXPR_ID_IN_SET (pa_in, i, bi)
2464
                    bitmap_value_insert_into_set (PA_OUT,
2465
                                                  expression_for_id (i));
2466
                  bitmap_set_free (pa_in);
2467
                }
2468
              else
2469
                FOR_EACH_EXPR_ID_IN_SET (PA_IN (bprime), i, bi)
2470
                  bitmap_value_insert_into_set (PA_OUT,
2471
                                                expression_for_id (i));
2472
            }
2473
        }
2474
      VEC_free (basic_block, heap, worklist);
2475
    }
2476
 
2477
  /* PA_IN starts with PA_OUT - TMP_GEN.
2478
     Then we subtract things from ANTIC_IN.  */
2479
  PA_IN (block) = bitmap_set_subtract (PA_OUT, TMP_GEN (block));
2480
 
2481
  /* For partial antic, we want to put back in the phi results, since
2482
     we will properly avoid making them partially antic over backedges.  */
2483
  bitmap_ior_into (&PA_IN (block)->values, &PHI_GEN (block)->values);
2484
  bitmap_ior_into (&PA_IN (block)->expressions, &PHI_GEN (block)->expressions);
2485
 
2486
  /* PA_IN[block] = PA_IN[block] - ANTIC_IN[block] */
2487
  bitmap_set_subtract_values (PA_IN (block), ANTIC_IN (block));
2488
 
2489
  dependent_clean (PA_IN (block), ANTIC_IN (block), block);
2490
 
2491
  if (!bitmap_set_equal (old_PA_IN, PA_IN (block)))
2492
    {
2493
      changed = true;
2494
      SET_BIT (changed_blocks, block->index);
2495
      FOR_EACH_EDGE (e, ei, block->preds)
2496
        SET_BIT (changed_blocks, e->src->index);
2497
    }
2498
  else
2499
    RESET_BIT (changed_blocks, block->index);
2500
 
2501
 maybe_dump_sets:
2502
  if (dump_file && (dump_flags & TDF_DETAILS))
2503
    {
2504
      if (PA_OUT)
2505
        print_bitmap_set (dump_file, PA_OUT, "PA_OUT", block->index);
2506
 
2507
      print_bitmap_set (dump_file, PA_IN (block), "PA_IN", block->index);
2508
    }
2509
  if (old_PA_IN)
2510
    bitmap_set_free (old_PA_IN);
2511
  if (PA_OUT)
2512
    bitmap_set_free (PA_OUT);
2513
  return changed;
2514
}
2515
 
2516
/* Compute ANTIC and partial ANTIC sets.  */
2517
 
2518
static void
2519
compute_antic (void)
2520
{
2521
  bool changed = true;
2522
  int num_iterations = 0;
2523
  basic_block block;
2524
  int i;
2525
 
2526
  /* If any predecessor edges are abnormal, we punt, so antic_in is empty.
2527
     We pre-build the map of blocks with incoming abnormal edges here.  */
2528
  has_abnormal_preds = sbitmap_alloc (last_basic_block);
2529
  sbitmap_zero (has_abnormal_preds);
2530
 
2531
  FOR_EACH_BB (block)
2532
    {
2533
      edge_iterator ei;
2534
      edge e;
2535
 
2536
      FOR_EACH_EDGE (e, ei, block->preds)
2537
        {
2538
          e->flags &= ~EDGE_DFS_BACK;
2539
          if (e->flags & EDGE_ABNORMAL)
2540
            {
2541
              SET_BIT (has_abnormal_preds, block->index);
2542
              break;
2543
            }
2544
        }
2545
 
2546
      BB_VISITED (block) = 0;
2547
      BB_DEFERRED (block) = 0;
2548
 
2549
      /* While we are here, give empty ANTIC_IN sets to each block.  */
2550
      ANTIC_IN (block) = bitmap_set_new ();
2551
      PA_IN (block) = bitmap_set_new ();
2552
    }
2553
 
2554
  /* At the exit block we anticipate nothing.  */
2555
  ANTIC_IN (EXIT_BLOCK_PTR) = bitmap_set_new ();
2556
  BB_VISITED (EXIT_BLOCK_PTR) = 1;
2557
  PA_IN (EXIT_BLOCK_PTR) = bitmap_set_new ();
2558
 
2559
  changed_blocks = sbitmap_alloc (last_basic_block + 1);
2560
  sbitmap_ones (changed_blocks);
2561
  while (changed)
2562
    {
2563
      if (dump_file && (dump_flags & TDF_DETAILS))
2564
        fprintf (dump_file, "Starting iteration %d\n", num_iterations);
2565
      /* ???  We need to clear our PHI translation cache here as the
2566
         ANTIC sets shrink and we restrict valid translations to
2567
         those having operands with leaders in ANTIC.  Same below
2568
         for PA ANTIC computation.  */
2569
      num_iterations++;
2570
      changed = false;
2571
      for (i = n_basic_blocks - NUM_FIXED_BLOCKS - 1; i >= 0; i--)
2572
        {
2573
          if (TEST_BIT (changed_blocks, postorder[i]))
2574
            {
2575
              basic_block block = BASIC_BLOCK (postorder[i]);
2576
              changed |= compute_antic_aux (block,
2577
                                            TEST_BIT (has_abnormal_preds,
2578
                                                      block->index));
2579
            }
2580
        }
2581
      /* Theoretically possible, but *highly* unlikely.  */
2582
      gcc_checking_assert (num_iterations < 500);
2583
    }
2584
 
2585
  statistics_histogram_event (cfun, "compute_antic iterations",
2586
                              num_iterations);
2587
 
2588
  if (do_partial_partial)
2589
    {
2590
      sbitmap_ones (changed_blocks);
2591
      mark_dfs_back_edges ();
2592
      num_iterations = 0;
2593
      changed = true;
2594
      while (changed)
2595
        {
2596
          if (dump_file && (dump_flags & TDF_DETAILS))
2597
            fprintf (dump_file, "Starting iteration %d\n", num_iterations);
2598
          num_iterations++;
2599
          changed = false;
2600
          for (i = n_basic_blocks - NUM_FIXED_BLOCKS - 1 ; i >= 0; i--)
2601
            {
2602
              if (TEST_BIT (changed_blocks, postorder[i]))
2603
                {
2604
                  basic_block block = BASIC_BLOCK (postorder[i]);
2605
                  changed
2606
                    |= compute_partial_antic_aux (block,
2607
                                                  TEST_BIT (has_abnormal_preds,
2608
                                                            block->index));
2609
                }
2610
            }
2611
          /* Theoretically possible, but *highly* unlikely.  */
2612
          gcc_checking_assert (num_iterations < 500);
2613
        }
2614
      statistics_histogram_event (cfun, "compute_partial_antic iterations",
2615
                                  num_iterations);
2616
    }
2617
  sbitmap_free (has_abnormal_preds);
2618
  sbitmap_free (changed_blocks);
2619
}
2620
 
2621
/* Return true if we can value number the call in STMT.  This is true
2622
   if we have a pure or constant call to a real function.  */
2623
 
2624
static bool
2625
can_value_number_call (gimple stmt)
2626
{
2627
  if (gimple_call_internal_p (stmt))
2628
    return false;
2629
  if (gimple_call_flags (stmt) & (ECF_PURE | ECF_CONST))
2630
    return true;
2631
  return false;
2632
}
2633
 
2634
/* Return true if OP is a tree which we can perform PRE on.
2635
   This may not match the operations we can value number, but in
2636
   a perfect world would.  */
2637
 
2638
static bool
2639
can_PRE_operation (tree op)
2640
{
2641
  return UNARY_CLASS_P (op)
2642
    || BINARY_CLASS_P (op)
2643
    || COMPARISON_CLASS_P (op)
2644
    || TREE_CODE (op) == MEM_REF
2645
    || TREE_CODE (op) == COMPONENT_REF
2646
    || TREE_CODE (op) == VIEW_CONVERT_EXPR
2647
    || TREE_CODE (op) == CALL_EXPR
2648
    || TREE_CODE (op) == ARRAY_REF;
2649
}
2650
 
2651
 
2652
/* Inserted expressions are placed onto this worklist, which is used
2653
   for performing quick dead code elimination of insertions we made
2654
   that didn't turn out to be necessary.   */
2655
static bitmap inserted_exprs;
2656
 
2657
/* Pool allocated fake store expressions are placed onto this
2658
   worklist, which, after performing dead code elimination, is walked
2659
   to see which expressions need to be put into GC'able memory  */
2660
static VEC(gimple, heap) *need_creation;
2661
 
2662
/* The actual worker for create_component_ref_by_pieces.  */
2663
 
2664
static tree
2665
create_component_ref_by_pieces_1 (basic_block block, vn_reference_t ref,
2666
                                  unsigned int *operand, gimple_seq *stmts,
2667
                                  gimple domstmt)
2668
{
2669
  vn_reference_op_t currop = VEC_index (vn_reference_op_s, ref->operands,
2670
                                        *operand);
2671
  tree genop;
2672
  ++*operand;
2673
  switch (currop->opcode)
2674
    {
2675
    case CALL_EXPR:
2676
      {
2677
        tree folded, sc = NULL_TREE;
2678
        unsigned int nargs = 0;
2679
        tree fn, *args;
2680
        if (TREE_CODE (currop->op0) == FUNCTION_DECL)
2681
          fn = currop->op0;
2682
        else
2683
          {
2684
            pre_expr op0 = get_or_alloc_expr_for (currop->op0);
2685
            fn = find_or_generate_expression (block, op0, stmts, domstmt);
2686
            if (!fn)
2687
              return NULL_TREE;
2688
          }
2689
        if (currop->op1)
2690
          {
2691
            pre_expr scexpr = get_or_alloc_expr_for (currop->op1);
2692
            sc = find_or_generate_expression (block, scexpr, stmts, domstmt);
2693
            if (!sc)
2694
              return NULL_TREE;
2695
          }
2696
        args = XNEWVEC (tree, VEC_length (vn_reference_op_s,
2697
                                          ref->operands) - 1);
2698
        while (*operand < VEC_length (vn_reference_op_s, ref->operands))
2699
          {
2700
            args[nargs] = create_component_ref_by_pieces_1 (block, ref,
2701
                                                            operand, stmts,
2702
                                                            domstmt);
2703
            if (!args[nargs])
2704
              {
2705
                free (args);
2706
                return NULL_TREE;
2707
              }
2708
            nargs++;
2709
          }
2710
        folded = build_call_array (currop->type,
2711
                                   (TREE_CODE (fn) == FUNCTION_DECL
2712
                                    ? build_fold_addr_expr (fn) : fn),
2713
                                   nargs, args);
2714
        free (args);
2715
        if (sc)
2716
          CALL_EXPR_STATIC_CHAIN (folded) = sc;
2717
        return folded;
2718
      }
2719
      break;
2720
    case MEM_REF:
2721
      {
2722
        tree baseop = create_component_ref_by_pieces_1 (block, ref, operand,
2723
                                                        stmts, domstmt);
2724
        tree offset = currop->op0;
2725
        if (!baseop)
2726
          return NULL_TREE;
2727
        if (TREE_CODE (baseop) == ADDR_EXPR
2728
            && handled_component_p (TREE_OPERAND (baseop, 0)))
2729
          {
2730
            HOST_WIDE_INT off;
2731
            tree base;
2732
            base = get_addr_base_and_unit_offset (TREE_OPERAND (baseop, 0),
2733
                                                  &off);
2734
            gcc_assert (base);
2735
            offset = int_const_binop (PLUS_EXPR, offset,
2736
                                      build_int_cst (TREE_TYPE (offset),
2737
                                                     off));
2738
            baseop = build_fold_addr_expr (base);
2739
          }
2740
        return fold_build2 (MEM_REF, currop->type, baseop, offset);
2741
      }
2742
      break;
2743
    case TARGET_MEM_REF:
2744
      {
2745
        pre_expr op0expr, op1expr;
2746
        tree genop0 = NULL_TREE, genop1 = NULL_TREE;
2747
        vn_reference_op_t nextop = VEC_index (vn_reference_op_s, ref->operands,
2748
                                              ++*operand);
2749
        tree baseop = create_component_ref_by_pieces_1 (block, ref, operand,
2750
                                                        stmts, domstmt);
2751
        if (!baseop)
2752
          return NULL_TREE;
2753
        if (currop->op0)
2754
          {
2755
            op0expr = get_or_alloc_expr_for (currop->op0);
2756
            genop0 = find_or_generate_expression (block, op0expr,
2757
                                                  stmts, domstmt);
2758
            if (!genop0)
2759
              return NULL_TREE;
2760
          }
2761
        if (nextop->op0)
2762
          {
2763
            op1expr = get_or_alloc_expr_for (nextop->op0);
2764
            genop1 = find_or_generate_expression (block, op1expr,
2765
                                                  stmts, domstmt);
2766
            if (!genop1)
2767
              return NULL_TREE;
2768
          }
2769
        return build5 (TARGET_MEM_REF, currop->type,
2770
                       baseop, currop->op2, genop0, currop->op1, genop1);
2771
      }
2772
      break;
2773
    case ADDR_EXPR:
2774
      if (currop->op0)
2775
        {
2776
          gcc_assert (is_gimple_min_invariant (currop->op0));
2777
          return currop->op0;
2778
        }
2779
      /* Fallthrough.  */
2780
    case REALPART_EXPR:
2781
    case IMAGPART_EXPR:
2782
    case VIEW_CONVERT_EXPR:
2783
      {
2784
        tree folded;
2785
        tree genop0 = create_component_ref_by_pieces_1 (block, ref,
2786
                                                        operand,
2787
                                                        stmts, domstmt);
2788
        if (!genop0)
2789
          return NULL_TREE;
2790
        folded = fold_build1 (currop->opcode, currop->type,
2791
                              genop0);
2792
        return folded;
2793
      }
2794
      break;
2795
    case WITH_SIZE_EXPR:
2796
      {
2797
        tree genop0 = create_component_ref_by_pieces_1 (block, ref, operand,
2798
                                                        stmts, domstmt);
2799
        pre_expr op1expr = get_or_alloc_expr_for (currop->op0);
2800
        tree genop1;
2801
 
2802
        if (!genop0)
2803
          return NULL_TREE;
2804
 
2805
        genop1 = find_or_generate_expression (block, op1expr, stmts, domstmt);
2806
        if (!genop1)
2807
          return NULL_TREE;
2808
 
2809
        return fold_build2 (currop->opcode, currop->type, genop0, genop1);
2810
      }
2811
      break;
2812
    case BIT_FIELD_REF:
2813
      {
2814
        tree folded;
2815
        tree genop0 = create_component_ref_by_pieces_1 (block, ref, operand,
2816
                                                        stmts, domstmt);
2817
        pre_expr op1expr = get_or_alloc_expr_for (currop->op0);
2818
        pre_expr op2expr = get_or_alloc_expr_for (currop->op1);
2819
        tree genop1;
2820
        tree genop2;
2821
 
2822
        if (!genop0)
2823
          return NULL_TREE;
2824
        genop1 = find_or_generate_expression (block, op1expr, stmts, domstmt);
2825
        if (!genop1)
2826
          return NULL_TREE;
2827
        genop2 = find_or_generate_expression (block, op2expr, stmts, domstmt);
2828
        if (!genop2)
2829
          return NULL_TREE;
2830
        folded = fold_build3 (BIT_FIELD_REF, currop->type, genop0, genop1,
2831
                              genop2);
2832
        return folded;
2833
      }
2834
 
2835
      /* For array ref vn_reference_op's, operand 1 of the array ref
2836
         is op0 of the reference op and operand 3 of the array ref is
2837
         op1.  */
2838
    case ARRAY_RANGE_REF:
2839
    case ARRAY_REF:
2840
      {
2841
        tree genop0;
2842
        tree genop1 = currop->op0;
2843
        pre_expr op1expr;
2844
        tree genop2 = currop->op1;
2845
        pre_expr op2expr;
2846
        tree genop3 = currop->op2;
2847
        pre_expr op3expr;
2848
        genop0 = create_component_ref_by_pieces_1 (block, ref, operand,
2849
                                                   stmts, domstmt);
2850
        if (!genop0)
2851
          return NULL_TREE;
2852
        op1expr = get_or_alloc_expr_for (genop1);
2853
        genop1 = find_or_generate_expression (block, op1expr, stmts, domstmt);
2854
        if (!genop1)
2855
          return NULL_TREE;
2856
        if (genop2)
2857
          {
2858
            tree domain_type = TYPE_DOMAIN (TREE_TYPE (genop0));
2859
            /* Drop zero minimum index if redundant.  */
2860
            if (integer_zerop (genop2)
2861
                && (!domain_type
2862
                    || integer_zerop (TYPE_MIN_VALUE (domain_type))))
2863
              genop2 = NULL_TREE;
2864
            else
2865
              {
2866
                op2expr = get_or_alloc_expr_for (genop2);
2867
                genop2 = find_or_generate_expression (block, op2expr, stmts,
2868
                                                      domstmt);
2869
                if (!genop2)
2870
                  return NULL_TREE;
2871
              }
2872
          }
2873
        if (genop3)
2874
          {
2875
            tree elmt_type = TREE_TYPE (TREE_TYPE (genop0));
2876
            /* We can't always put a size in units of the element alignment
2877
               here as the element alignment may be not visible.  See
2878
               PR43783.  Simply drop the element size for constant
2879
               sizes.  */
2880
            if (tree_int_cst_equal (genop3, TYPE_SIZE_UNIT (elmt_type)))
2881
              genop3 = NULL_TREE;
2882
            else
2883
              {
2884
                genop3 = size_binop (EXACT_DIV_EXPR, genop3,
2885
                                     size_int (TYPE_ALIGN_UNIT (elmt_type)));
2886
                op3expr = get_or_alloc_expr_for (genop3);
2887
                genop3 = find_or_generate_expression (block, op3expr, stmts,
2888
                                                      domstmt);
2889
                if (!genop3)
2890
                  return NULL_TREE;
2891
              }
2892
          }
2893
        return build4 (currop->opcode, currop->type, genop0, genop1,
2894
                       genop2, genop3);
2895
      }
2896
    case COMPONENT_REF:
2897
      {
2898
        tree op0;
2899
        tree op1;
2900
        tree genop2 = currop->op1;
2901
        pre_expr op2expr;
2902
        op0 = create_component_ref_by_pieces_1 (block, ref, operand,
2903
                                                stmts, domstmt);
2904
        if (!op0)
2905
          return NULL_TREE;
2906
        /* op1 should be a FIELD_DECL, which are represented by
2907
           themselves.  */
2908
        op1 = currop->op0;
2909
        if (genop2)
2910
          {
2911
            op2expr = get_or_alloc_expr_for (genop2);
2912
            genop2 = find_or_generate_expression (block, op2expr, stmts,
2913
                                                  domstmt);
2914
            if (!genop2)
2915
              return NULL_TREE;
2916
          }
2917
 
2918
        return fold_build3 (COMPONENT_REF, TREE_TYPE (op1), op0, op1,
2919
                            genop2);
2920
      }
2921
      break;
2922
    case SSA_NAME:
2923
      {
2924
        pre_expr op0expr = get_or_alloc_expr_for (currop->op0);
2925
        genop = find_or_generate_expression (block, op0expr, stmts, domstmt);
2926
        return genop;
2927
      }
2928
    case STRING_CST:
2929
    case INTEGER_CST:
2930
    case COMPLEX_CST:
2931
    case VECTOR_CST:
2932
    case REAL_CST:
2933
    case CONSTRUCTOR:
2934
    case VAR_DECL:
2935
    case PARM_DECL:
2936
    case CONST_DECL:
2937
    case RESULT_DECL:
2938
    case FUNCTION_DECL:
2939
      return currop->op0;
2940
 
2941
    default:
2942
      gcc_unreachable ();
2943
    }
2944
}
2945
 
2946
/* For COMPONENT_REF's and ARRAY_REF's, we can't have any intermediates for the
2947
   COMPONENT_REF or MEM_REF or ARRAY_REF portion, because we'd end up with
2948
   trying to rename aggregates into ssa form directly, which is a no no.
2949
 
2950
   Thus, this routine doesn't create temporaries, it just builds a
2951
   single access expression for the array, calling
2952
   find_or_generate_expression to build the innermost pieces.
2953
 
2954
   This function is a subroutine of create_expression_by_pieces, and
2955
   should not be called on it's own unless you really know what you
2956
   are doing.  */
2957
 
2958
static tree
2959
create_component_ref_by_pieces (basic_block block, vn_reference_t ref,
2960
                                gimple_seq *stmts, gimple domstmt)
2961
{
2962
  unsigned int op = 0;
2963
  return create_component_ref_by_pieces_1 (block, ref, &op, stmts, domstmt);
2964
}
2965
 
2966
/* Find a leader for an expression, or generate one using
2967
   create_expression_by_pieces if it's ANTIC but
2968
   complex.
2969
   BLOCK is the basic_block we are looking for leaders in.
2970
   EXPR is the expression to find a leader or generate for.
2971
   STMTS is the statement list to put the inserted expressions on.
2972
   Returns the SSA_NAME of the LHS of the generated expression or the
2973
   leader.
2974
   DOMSTMT if non-NULL is a statement that should be dominated by
2975
   all uses in the generated expression.  If DOMSTMT is non-NULL this
2976
   routine can fail and return NULL_TREE.  Otherwise it will assert
2977
   on failure.  */
2978
 
2979
static tree
2980
find_or_generate_expression (basic_block block, pre_expr expr,
2981
                             gimple_seq *stmts, gimple domstmt)
2982
{
2983
  pre_expr leader = bitmap_find_leader (AVAIL_OUT (block),
2984
                                        get_expr_value_id (expr), domstmt);
2985
  tree genop = NULL;
2986
  if (leader)
2987
    {
2988
      if (leader->kind == NAME)
2989
        genop = PRE_EXPR_NAME (leader);
2990
      else if (leader->kind == CONSTANT)
2991
        genop = PRE_EXPR_CONSTANT (leader);
2992
    }
2993
 
2994
  /* If it's still NULL, it must be a complex expression, so generate
2995
     it recursively.  Not so if inserting expressions for values generated
2996
     by SCCVN.  */
2997
  if (genop == NULL
2998
      && !domstmt)
2999
    {
3000
      bitmap_set_t exprset;
3001
      unsigned int lookfor = get_expr_value_id (expr);
3002
      bool handled = false;
3003
      bitmap_iterator bi;
3004
      unsigned int i;
3005
 
3006
      exprset = VEC_index (bitmap_set_t, value_expressions, lookfor);
3007
      FOR_EACH_EXPR_ID_IN_SET (exprset, i, bi)
3008
        {
3009
          pre_expr temp = expression_for_id (i);
3010
          if (temp->kind != NAME)
3011
            {
3012
              handled = true;
3013
              genop = create_expression_by_pieces (block, temp, stmts,
3014
                                                   domstmt,
3015
                                                   get_expr_type (expr));
3016
              break;
3017
            }
3018
        }
3019
      if (!handled && domstmt)
3020
        return NULL_TREE;
3021
 
3022
      gcc_assert (handled);
3023
    }
3024
  return genop;
3025
}
3026
 
3027
#define NECESSARY GF_PLF_1
3028
 
3029
/* Create an expression in pieces, so that we can handle very complex
3030
   expressions that may be ANTIC, but not necessary GIMPLE.
3031
   BLOCK is the basic block the expression will be inserted into,
3032
   EXPR is the expression to insert (in value form)
3033
   STMTS is a statement list to append the necessary insertions into.
3034
 
3035
   This function will die if we hit some value that shouldn't be
3036
   ANTIC but is (IE there is no leader for it, or its components).
3037
   This function may also generate expressions that are themselves
3038
   partially or fully redundant.  Those that are will be either made
3039
   fully redundant during the next iteration of insert (for partially
3040
   redundant ones), or eliminated by eliminate (for fully redundant
3041
   ones).
3042
 
3043
   If DOMSTMT is non-NULL then we make sure that all uses in the
3044
   expressions dominate that statement.  In this case the function
3045
   can return NULL_TREE to signal failure.  */
3046
 
3047
static tree
3048
create_expression_by_pieces (basic_block block, pre_expr expr,
3049
                             gimple_seq *stmts, gimple domstmt, tree type)
3050
{
3051
  tree temp, name;
3052
  tree folded;
3053
  gimple_seq forced_stmts = NULL;
3054
  unsigned int value_id;
3055
  gimple_stmt_iterator gsi;
3056
  tree exprtype = type ? type : get_expr_type (expr);
3057
  pre_expr nameexpr;
3058
  gimple newstmt;
3059
 
3060
  switch (expr->kind)
3061
    {
3062
      /* We may hit the NAME/CONSTANT case if we have to convert types
3063
         that value numbering saw through.  */
3064
    case NAME:
3065
      folded = PRE_EXPR_NAME (expr);
3066
      break;
3067
    case CONSTANT:
3068
      folded = PRE_EXPR_CONSTANT (expr);
3069
      break;
3070
    case REFERENCE:
3071
      {
3072
        vn_reference_t ref = PRE_EXPR_REFERENCE (expr);
3073
        folded = create_component_ref_by_pieces (block, ref, stmts, domstmt);
3074
      }
3075
      break;
3076
    case NARY:
3077
      {
3078
        vn_nary_op_t nary = PRE_EXPR_NARY (expr);
3079
        tree genop[4];
3080
        unsigned i;
3081
        for (i = 0; i < nary->length; ++i)
3082
          {
3083
            pre_expr op = get_or_alloc_expr_for (nary->op[i]);
3084
            genop[i] = find_or_generate_expression (block, op,
3085
                                                    stmts, domstmt);
3086
            if (!genop[i])
3087
              return NULL_TREE;
3088
            /* Ensure genop[] is properly typed for POINTER_PLUS_EXPR.  It
3089
               may have conversions stripped.  */
3090
            if (nary->opcode == POINTER_PLUS_EXPR)
3091
              {
3092
                if (i == 0)
3093
                  genop[i] = fold_convert (nary->type, genop[i]);
3094
                else if (i == 1)
3095
                  genop[i] = convert_to_ptrofftype (genop[i]);
3096
              }
3097
            else
3098
              genop[i] = fold_convert (TREE_TYPE (nary->op[i]), genop[i]);
3099
          }
3100
        if (nary->opcode == CONSTRUCTOR)
3101
          {
3102
            VEC(constructor_elt,gc) *elts = NULL;
3103
            for (i = 0; i < nary->length; ++i)
3104
              CONSTRUCTOR_APPEND_ELT (elts, NULL_TREE, genop[i]);
3105
            folded = build_constructor (nary->type, elts);
3106
          }
3107
        else
3108
          {
3109
            switch (nary->length)
3110
              {
3111
              case 1:
3112
                folded = fold_build1 (nary->opcode, nary->type,
3113
                                      genop[0]);
3114
                break;
3115
              case 2:
3116
                folded = fold_build2 (nary->opcode, nary->type,
3117
                                      genop[0], genop[1]);
3118
                break;
3119
              case 3:
3120
                folded = fold_build3 (nary->opcode, nary->type,
3121
                                      genop[0], genop[1], genop[3]);
3122
                break;
3123
              default:
3124
                gcc_unreachable ();
3125
              }
3126
          }
3127
      }
3128
      break;
3129
    default:
3130
      return NULL_TREE;
3131
    }
3132
 
3133
  if (!useless_type_conversion_p (exprtype, TREE_TYPE (folded)))
3134
    folded = fold_convert (exprtype, folded);
3135
 
3136
  /* Force the generated expression to be a sequence of GIMPLE
3137
     statements.
3138
     We have to call unshare_expr because force_gimple_operand may
3139
     modify the tree we pass to it.  */
3140
  folded = force_gimple_operand (unshare_expr (folded), &forced_stmts,
3141
                                 false, NULL);
3142
 
3143
  /* If we have any intermediate expressions to the value sets, add them
3144
     to the value sets and chain them in the instruction stream.  */
3145
  if (forced_stmts)
3146
    {
3147
      gsi = gsi_start (forced_stmts);
3148
      for (; !gsi_end_p (gsi); gsi_next (&gsi))
3149
        {
3150
          gimple stmt = gsi_stmt (gsi);
3151
          tree forcedname = gimple_get_lhs (stmt);
3152
          pre_expr nameexpr;
3153
 
3154
          if (TREE_CODE (forcedname) == SSA_NAME)
3155
            {
3156
              bitmap_set_bit (inserted_exprs, SSA_NAME_VERSION (forcedname));
3157
              VN_INFO_GET (forcedname)->valnum = forcedname;
3158
              VN_INFO (forcedname)->value_id = get_next_value_id ();
3159
              nameexpr = get_or_alloc_expr_for_name (forcedname);
3160
              add_to_value (VN_INFO (forcedname)->value_id, nameexpr);
3161
              if (!in_fre)
3162
                bitmap_value_replace_in_set (NEW_SETS (block), nameexpr);
3163
              bitmap_value_replace_in_set (AVAIL_OUT (block), nameexpr);
3164
            }
3165
          mark_symbols_for_renaming (stmt);
3166
        }
3167
      gimple_seq_add_seq (stmts, forced_stmts);
3168
    }
3169
 
3170
  /* Build and insert the assignment of the end result to the temporary
3171
     that we will return.  */
3172
  if (!pretemp || exprtype != TREE_TYPE (pretemp))
3173
    pretemp = create_tmp_reg (exprtype, "pretmp");
3174
 
3175
  temp = pretemp;
3176
  add_referenced_var (temp);
3177
 
3178
  newstmt = gimple_build_assign (temp, folded);
3179
  name = make_ssa_name (temp, newstmt);
3180
  gimple_assign_set_lhs (newstmt, name);
3181
  gimple_set_plf (newstmt, NECESSARY, false);
3182
 
3183
  gimple_seq_add_stmt (stmts, newstmt);
3184
  bitmap_set_bit (inserted_exprs, SSA_NAME_VERSION (name));
3185
 
3186
  /* All the symbols in NEWEXPR should be put into SSA form.  */
3187
  mark_symbols_for_renaming (newstmt);
3188
 
3189
  /* Fold the last statement.  */
3190
  gsi = gsi_last (*stmts);
3191
  if (fold_stmt_inplace (&gsi))
3192
    update_stmt (gsi_stmt (gsi));
3193
 
3194
  /* Add a value number to the temporary.
3195
     The value may already exist in either NEW_SETS, or AVAIL_OUT, because
3196
     we are creating the expression by pieces, and this particular piece of
3197
     the expression may have been represented.  There is no harm in replacing
3198
     here.  */
3199
  VN_INFO_GET (name)->valnum = name;
3200
  value_id = get_expr_value_id (expr);
3201
  VN_INFO (name)->value_id = value_id;
3202
  nameexpr = get_or_alloc_expr_for_name (name);
3203
  add_to_value (value_id, nameexpr);
3204
  if (NEW_SETS (block))
3205
    bitmap_value_replace_in_set (NEW_SETS (block), nameexpr);
3206
  bitmap_value_replace_in_set (AVAIL_OUT (block), nameexpr);
3207
 
3208
  pre_stats.insertions++;
3209
  if (dump_file && (dump_flags & TDF_DETAILS))
3210
    {
3211
      fprintf (dump_file, "Inserted ");
3212
      print_gimple_stmt (dump_file, newstmt, 0, 0);
3213
      fprintf (dump_file, " in predecessor %d\n", block->index);
3214
    }
3215
 
3216
  return name;
3217
}
3218
 
3219
 
3220
/* Returns true if we want to inhibit the insertions of PHI nodes
3221
   for the given EXPR for basic block BB (a member of a loop).
3222
   We want to do this, when we fear that the induction variable we
3223
   create might inhibit vectorization.  */
3224
 
3225
static bool
3226
inhibit_phi_insertion (basic_block bb, pre_expr expr)
3227
{
3228
  vn_reference_t vr = PRE_EXPR_REFERENCE (expr);
3229
  VEC (vn_reference_op_s, heap) *ops = vr->operands;
3230
  vn_reference_op_t op;
3231
  unsigned i;
3232
 
3233
  /* If we aren't going to vectorize we don't inhibit anything.  */
3234
  if (!flag_tree_vectorize)
3235
    return false;
3236
 
3237
  /* Otherwise we inhibit the insertion when the address of the
3238
     memory reference is a simple induction variable.  In other
3239
     cases the vectorizer won't do anything anyway (either it's
3240
     loop invariant or a complicated expression).  */
3241
  FOR_EACH_VEC_ELT (vn_reference_op_s, ops, i, op)
3242
    {
3243
      switch (op->opcode)
3244
        {
3245
        case ARRAY_REF:
3246
        case ARRAY_RANGE_REF:
3247
          if (TREE_CODE (op->op0) != SSA_NAME)
3248
            break;
3249
          /* Fallthru.  */
3250
        case SSA_NAME:
3251
          {
3252
            basic_block defbb = gimple_bb (SSA_NAME_DEF_STMT (op->op0));
3253
            affine_iv iv;
3254
            /* Default defs are loop invariant.  */
3255
            if (!defbb)
3256
              break;
3257
            /* Defined outside this loop, also loop invariant.  */
3258
            if (!flow_bb_inside_loop_p (bb->loop_father, defbb))
3259
              break;
3260
            /* If it's a simple induction variable inhibit insertion,
3261
               the vectorizer might be interested in this one.  */
3262
            if (simple_iv (bb->loop_father, bb->loop_father,
3263
                           op->op0, &iv, true))
3264
              return true;
3265
            /* No simple IV, vectorizer can't do anything, hence no
3266
               reason to inhibit the transformation for this operand.  */
3267
            break;
3268
          }
3269
        default:
3270
          break;
3271
        }
3272
    }
3273
  return false;
3274
}
3275
 
3276
/* Insert the to-be-made-available values of expression EXPRNUM for each
3277
   predecessor, stored in AVAIL, into the predecessors of BLOCK, and
3278
   merge the result with a phi node, given the same value number as
3279
   NODE.  Return true if we have inserted new stuff.  */
3280
 
3281
static bool
3282
insert_into_preds_of_block (basic_block block, unsigned int exprnum,
3283
                            pre_expr *avail)
3284
{
3285
  pre_expr expr = expression_for_id (exprnum);
3286
  pre_expr newphi;
3287
  unsigned int val = get_expr_value_id (expr);
3288
  edge pred;
3289
  bool insertions = false;
3290
  bool nophi = false;
3291
  basic_block bprime;
3292
  pre_expr eprime;
3293
  edge_iterator ei;
3294
  tree type = get_expr_type (expr);
3295
  tree temp;
3296
  gimple phi;
3297
 
3298
  if (dump_file && (dump_flags & TDF_DETAILS))
3299
    {
3300
      fprintf (dump_file, "Found partial redundancy for expression ");
3301
      print_pre_expr (dump_file, expr);
3302
      fprintf (dump_file, " (%04d)\n", val);
3303
    }
3304
 
3305
  /* Make sure we aren't creating an induction variable.  */
3306
  if (block->loop_depth > 0 && EDGE_COUNT (block->preds) == 2)
3307
    {
3308
      bool firstinsideloop = false;
3309
      bool secondinsideloop = false;
3310
      firstinsideloop = flow_bb_inside_loop_p (block->loop_father,
3311
                                               EDGE_PRED (block, 0)->src);
3312
      secondinsideloop = flow_bb_inside_loop_p (block->loop_father,
3313
                                                EDGE_PRED (block, 1)->src);
3314
      /* Induction variables only have one edge inside the loop.  */
3315
      if ((firstinsideloop ^ secondinsideloop)
3316
          && (expr->kind != REFERENCE
3317
              || inhibit_phi_insertion (block, expr)))
3318
        {
3319
          if (dump_file && (dump_flags & TDF_DETAILS))
3320
            fprintf (dump_file, "Skipping insertion of phi for partial redundancy: Looks like an induction variable\n");
3321
          nophi = true;
3322
        }
3323
    }
3324
 
3325
  /* Make the necessary insertions.  */
3326
  FOR_EACH_EDGE (pred, ei, block->preds)
3327
    {
3328
      gimple_seq stmts = NULL;
3329
      tree builtexpr;
3330
      bprime = pred->src;
3331
      eprime = avail[bprime->index];
3332
 
3333
      if (eprime->kind != NAME && eprime->kind != CONSTANT)
3334
        {
3335
          builtexpr = create_expression_by_pieces (bprime,
3336
                                                   eprime,
3337
                                                   &stmts, NULL,
3338
                                                   type);
3339
          gcc_assert (!(pred->flags & EDGE_ABNORMAL));
3340
          gsi_insert_seq_on_edge (pred, stmts);
3341
          avail[bprime->index] = get_or_alloc_expr_for_name (builtexpr);
3342
          insertions = true;
3343
        }
3344
      else if (eprime->kind == CONSTANT)
3345
        {
3346
          /* Constants may not have the right type, fold_convert
3347
             should give us back a constant with the right type.
3348
          */
3349
          tree constant = PRE_EXPR_CONSTANT (eprime);
3350
          if (!useless_type_conversion_p (type, TREE_TYPE (constant)))
3351
            {
3352
              tree builtexpr = fold_convert (type, constant);
3353
              if (!is_gimple_min_invariant (builtexpr))
3354
                {
3355
                  tree forcedexpr = force_gimple_operand (builtexpr,
3356
                                                          &stmts, true,
3357
                                                          NULL);
3358
                  if (!is_gimple_min_invariant (forcedexpr))
3359
                    {
3360
                      if (forcedexpr != builtexpr)
3361
                        {
3362
                          VN_INFO_GET (forcedexpr)->valnum = PRE_EXPR_CONSTANT (eprime);
3363
                          VN_INFO (forcedexpr)->value_id = get_expr_value_id (eprime);
3364
                        }
3365
                      if (stmts)
3366
                        {
3367
                          gimple_stmt_iterator gsi;
3368
                          gsi = gsi_start (stmts);
3369
                          for (; !gsi_end_p (gsi); gsi_next (&gsi))
3370
                            {
3371
                              gimple stmt = gsi_stmt (gsi);
3372
                              tree lhs = gimple_get_lhs (stmt);
3373
                              if (TREE_CODE (lhs) == SSA_NAME)
3374
                                bitmap_set_bit (inserted_exprs,
3375
                                                SSA_NAME_VERSION (lhs));
3376
                              gimple_set_plf (stmt, NECESSARY, false);
3377
                            }
3378
                          gsi_insert_seq_on_edge (pred, stmts);
3379
                        }
3380
                      avail[bprime->index] = get_or_alloc_expr_for_name (forcedexpr);
3381
                    }
3382
                }
3383
              else
3384
                avail[bprime->index] = get_or_alloc_expr_for_constant (builtexpr);
3385
            }
3386
        }
3387
      else if (eprime->kind == NAME)
3388
        {
3389
          /* We may have to do a conversion because our value
3390
             numbering can look through types in certain cases, but
3391
             our IL requires all operands of a phi node have the same
3392
             type.  */
3393
          tree name = PRE_EXPR_NAME (eprime);
3394
          if (!useless_type_conversion_p (type, TREE_TYPE (name)))
3395
            {
3396
              tree builtexpr;
3397
              tree forcedexpr;
3398
              builtexpr = fold_convert (type, name);
3399
              forcedexpr = force_gimple_operand (builtexpr,
3400
                                                 &stmts, true,
3401
                                                 NULL);
3402
 
3403
              if (forcedexpr != name)
3404
                {
3405
                  VN_INFO_GET (forcedexpr)->valnum = VN_INFO (name)->valnum;
3406
                  VN_INFO (forcedexpr)->value_id = VN_INFO (name)->value_id;
3407
                }
3408
 
3409
              if (stmts)
3410
                {
3411
                  gimple_stmt_iterator gsi;
3412
                  gsi = gsi_start (stmts);
3413
                  for (; !gsi_end_p (gsi); gsi_next (&gsi))
3414
                    {
3415
                      gimple stmt = gsi_stmt (gsi);
3416
                      tree lhs = gimple_get_lhs (stmt);
3417
                      if (TREE_CODE (lhs) == SSA_NAME)
3418
                        bitmap_set_bit (inserted_exprs, SSA_NAME_VERSION (lhs));
3419
                      gimple_set_plf (stmt, NECESSARY, false);
3420
                    }
3421
                  gsi_insert_seq_on_edge (pred, stmts);
3422
                }
3423
              avail[bprime->index] = get_or_alloc_expr_for_name (forcedexpr);
3424
            }
3425
        }
3426
    }
3427
  /* If we didn't want a phi node, and we made insertions, we still have
3428
     inserted new stuff, and thus return true.  If we didn't want a phi node,
3429
     and didn't make insertions, we haven't added anything new, so return
3430
     false.  */
3431
  if (nophi && insertions)
3432
    return true;
3433
  else if (nophi && !insertions)
3434
    return false;
3435
 
3436
  /* Now build a phi for the new variable.  */
3437
  if (!prephitemp || TREE_TYPE (prephitemp) != type)
3438
    prephitemp = create_tmp_var (type, "prephitmp");
3439
 
3440
  temp = prephitemp;
3441
  add_referenced_var (temp);
3442
 
3443
  if (TREE_CODE (type) == COMPLEX_TYPE
3444
      || TREE_CODE (type) == VECTOR_TYPE)
3445
    DECL_GIMPLE_REG_P (temp) = 1;
3446
  phi = create_phi_node (temp, block);
3447
 
3448
  gimple_set_plf (phi, NECESSARY, false);
3449
  VN_INFO_GET (gimple_phi_result (phi))->valnum = gimple_phi_result (phi);
3450
  VN_INFO (gimple_phi_result (phi))->value_id = val;
3451
  bitmap_set_bit (inserted_exprs, SSA_NAME_VERSION (gimple_phi_result (phi)));
3452
  FOR_EACH_EDGE (pred, ei, block->preds)
3453
    {
3454
      pre_expr ae = avail[pred->src->index];
3455
      gcc_assert (get_expr_type (ae) == type
3456
                  || useless_type_conversion_p (type, get_expr_type (ae)));
3457
      if (ae->kind == CONSTANT)
3458
        add_phi_arg (phi, PRE_EXPR_CONSTANT (ae), pred, UNKNOWN_LOCATION);
3459
      else
3460
        add_phi_arg (phi, PRE_EXPR_NAME (avail[pred->src->index]), pred,
3461
                     UNKNOWN_LOCATION);
3462
    }
3463
 
3464
  newphi = get_or_alloc_expr_for_name (gimple_phi_result (phi));
3465
  add_to_value (val, newphi);
3466
 
3467
  /* The value should *not* exist in PHI_GEN, or else we wouldn't be doing
3468
     this insertion, since we test for the existence of this value in PHI_GEN
3469
     before proceeding with the partial redundancy checks in insert_aux.
3470
 
3471
     The value may exist in AVAIL_OUT, in particular, it could be represented
3472
     by the expression we are trying to eliminate, in which case we want the
3473
     replacement to occur.  If it's not existing in AVAIL_OUT, we want it
3474
     inserted there.
3475
 
3476
     Similarly, to the PHI_GEN case, the value should not exist in NEW_SETS of
3477
     this block, because if it did, it would have existed in our dominator's
3478
     AVAIL_OUT, and would have been skipped due to the full redundancy check.
3479
  */
3480
 
3481
  bitmap_insert_into_set (PHI_GEN (block), newphi);
3482
  bitmap_value_replace_in_set (AVAIL_OUT (block),
3483
                               newphi);
3484
  bitmap_insert_into_set (NEW_SETS (block),
3485
                          newphi);
3486
 
3487
  if (dump_file && (dump_flags & TDF_DETAILS))
3488
    {
3489
      fprintf (dump_file, "Created phi ");
3490
      print_gimple_stmt (dump_file, phi, 0, 0);
3491
      fprintf (dump_file, " in block %d\n", block->index);
3492
    }
3493
  pre_stats.phis++;
3494
  return true;
3495
}
3496
 
3497
 
3498
 
3499
/* Perform insertion of partially redundant values.
3500
   For BLOCK, do the following:
3501
   1.  Propagate the NEW_SETS of the dominator into the current block.
3502
   If the block has multiple predecessors,
3503
       2a. Iterate over the ANTIC expressions for the block to see if
3504
           any of them are partially redundant.
3505
       2b. If so, insert them into the necessary predecessors to make
3506
           the expression fully redundant.
3507
       2c. Insert a new PHI merging the values of the predecessors.
3508
       2d. Insert the new PHI, and the new expressions, into the
3509
           NEW_SETS set.
3510
   3. Recursively call ourselves on the dominator children of BLOCK.
3511
 
3512
   Steps 1, 2a, and 3 are done by insert_aux. 2b, 2c and 2d are done by
3513
   do_regular_insertion and do_partial_insertion.
3514
 
3515
*/
3516
 
3517
static bool
3518
do_regular_insertion (basic_block block, basic_block dom)
3519
{
3520
  bool new_stuff = false;
3521
  VEC (pre_expr, heap) *exprs = sorted_array_from_bitmap_set (ANTIC_IN (block));
3522
  pre_expr expr;
3523
  int i;
3524
 
3525
  FOR_EACH_VEC_ELT (pre_expr, exprs, i, expr)
3526
    {
3527
      if (expr->kind != NAME)
3528
        {
3529
          pre_expr *avail;
3530
          unsigned int val;
3531
          bool by_some = false;
3532
          bool cant_insert = false;
3533
          bool all_same = true;
3534
          pre_expr first_s = NULL;
3535
          edge pred;
3536
          basic_block bprime;
3537
          pre_expr eprime = NULL;
3538
          edge_iterator ei;
3539
          pre_expr edoubleprime = NULL;
3540
          bool do_insertion = false;
3541
 
3542
          val = get_expr_value_id (expr);
3543
          if (bitmap_set_contains_value (PHI_GEN (block), val))
3544
            continue;
3545
          if (bitmap_set_contains_value (AVAIL_OUT (dom), val))
3546
            {
3547
              if (dump_file && (dump_flags & TDF_DETAILS))
3548
                fprintf (dump_file, "Found fully redundant value\n");
3549
              continue;
3550
            }
3551
 
3552
          avail = XCNEWVEC (pre_expr, last_basic_block);
3553
          FOR_EACH_EDGE (pred, ei, block->preds)
3554
            {
3555
              unsigned int vprime;
3556
 
3557
              /* We should never run insertion for the exit block
3558
                 and so not come across fake pred edges.  */
3559
              gcc_assert (!(pred->flags & EDGE_FAKE));
3560
              bprime = pred->src;
3561
              eprime = phi_translate (expr, ANTIC_IN (block), NULL,
3562
                                      bprime, block);
3563
 
3564
              /* eprime will generally only be NULL if the
3565
                 value of the expression, translated
3566
                 through the PHI for this predecessor, is
3567
                 undefined.  If that is the case, we can't
3568
                 make the expression fully redundant,
3569
                 because its value is undefined along a
3570
                 predecessor path.  We can thus break out
3571
                 early because it doesn't matter what the
3572
                 rest of the results are.  */
3573
              if (eprime == NULL)
3574
                {
3575
                  cant_insert = true;
3576
                  break;
3577
                }
3578
 
3579
              eprime = fully_constant_expression (eprime);
3580
              vprime = get_expr_value_id (eprime);
3581
              edoubleprime = bitmap_find_leader (AVAIL_OUT (bprime),
3582
                                                 vprime, NULL);
3583
              if (edoubleprime == NULL)
3584
                {
3585
                  avail[bprime->index] = eprime;
3586
                  all_same = false;
3587
                }
3588
              else
3589
                {
3590
                  avail[bprime->index] = edoubleprime;
3591
                  by_some = true;
3592
                  /* We want to perform insertions to remove a redundancy on
3593
                     a path in the CFG we want to optimize for speed.  */
3594
                  if (optimize_edge_for_speed_p (pred))
3595
                    do_insertion = true;
3596
                  if (first_s == NULL)
3597
                    first_s = edoubleprime;
3598
                  else if (!pre_expr_eq (first_s, edoubleprime))
3599
                    all_same = false;
3600
                }
3601
            }
3602
          /* If we can insert it, it's not the same value
3603
             already existing along every predecessor, and
3604
             it's defined by some predecessor, it is
3605
             partially redundant.  */
3606
          if (!cant_insert && !all_same && by_some)
3607
            {
3608
              if (!do_insertion)
3609
                {
3610
                  if (dump_file && (dump_flags & TDF_DETAILS))
3611
                    {
3612
                      fprintf (dump_file, "Skipping partial redundancy for "
3613
                               "expression ");
3614
                      print_pre_expr (dump_file, expr);
3615
                      fprintf (dump_file, " (%04d), no redundancy on to be "
3616
                               "optimized for speed edge\n", val);
3617
                    }
3618
                }
3619
              else if (dbg_cnt (treepre_insert)
3620
                       && insert_into_preds_of_block (block,
3621
                                                      get_expression_id (expr),
3622
                                                      avail))
3623
                new_stuff = true;
3624
            }
3625
          /* If all edges produce the same value and that value is
3626
             an invariant, then the PHI has the same value on all
3627
             edges.  Note this.  */
3628
          else if (!cant_insert && all_same && eprime
3629
                   && (edoubleprime->kind == CONSTANT
3630
                       || edoubleprime->kind == NAME)
3631
                   && !value_id_constant_p (val))
3632
            {
3633
              unsigned int j;
3634
              bitmap_iterator bi;
3635
              bitmap_set_t exprset = VEC_index (bitmap_set_t,
3636
                                                value_expressions, val);
3637
 
3638
              unsigned int new_val = get_expr_value_id (edoubleprime);
3639
              FOR_EACH_EXPR_ID_IN_SET (exprset, j, bi)
3640
                {
3641
                  pre_expr expr = expression_for_id (j);
3642
 
3643
                  if (expr->kind == NAME)
3644
                    {
3645
                      vn_ssa_aux_t info = VN_INFO (PRE_EXPR_NAME (expr));
3646
                      /* Just reset the value id and valnum so it is
3647
                         the same as the constant we have discovered.  */
3648
                      if (edoubleprime->kind == CONSTANT)
3649
                        {
3650
                          info->valnum = PRE_EXPR_CONSTANT (edoubleprime);
3651
                          pre_stats.constified++;
3652
                        }
3653
                      else
3654
                        info->valnum = VN_INFO (PRE_EXPR_NAME (edoubleprime))->valnum;
3655
                      info->value_id = new_val;
3656
                    }
3657
                }
3658
            }
3659
          free (avail);
3660
        }
3661
    }
3662
 
3663
  VEC_free (pre_expr, heap, exprs);
3664
  return new_stuff;
3665
}
3666
 
3667
 
3668
/* Perform insertion for partially anticipatable expressions.  There
3669
   is only one case we will perform insertion for these.  This case is
3670
   if the expression is partially anticipatable, and fully available.
3671
   In this case, we know that putting it earlier will enable us to
3672
   remove the later computation.  */
3673
 
3674
 
3675
static bool
3676
do_partial_partial_insertion (basic_block block, basic_block dom)
3677
{
3678
  bool new_stuff = false;
3679
  VEC (pre_expr, heap) *exprs = sorted_array_from_bitmap_set (PA_IN (block));
3680
  pre_expr expr;
3681
  int i;
3682
 
3683
  FOR_EACH_VEC_ELT (pre_expr, exprs, i, expr)
3684
    {
3685
      if (expr->kind != NAME)
3686
        {
3687
          pre_expr *avail;
3688
          unsigned int val;
3689
          bool by_all = true;
3690
          bool cant_insert = false;
3691
          edge pred;
3692
          basic_block bprime;
3693
          pre_expr eprime = NULL;
3694
          edge_iterator ei;
3695
 
3696
          val = get_expr_value_id (expr);
3697
          if (bitmap_set_contains_value (PHI_GEN (block), val))
3698
            continue;
3699
          if (bitmap_set_contains_value (AVAIL_OUT (dom), val))
3700
            continue;
3701
 
3702
          avail = XCNEWVEC (pre_expr, last_basic_block);
3703
          FOR_EACH_EDGE (pred, ei, block->preds)
3704
            {
3705
              unsigned int vprime;
3706
              pre_expr edoubleprime;
3707
 
3708
              /* We should never run insertion for the exit block
3709
                 and so not come across fake pred edges.  */
3710
              gcc_assert (!(pred->flags & EDGE_FAKE));
3711
              bprime = pred->src;
3712
              eprime = phi_translate (expr, ANTIC_IN (block),
3713
                                      PA_IN (block),
3714
                                      bprime, block);
3715
 
3716
              /* eprime will generally only be NULL if the
3717
                 value of the expression, translated
3718
                 through the PHI for this predecessor, is
3719
                 undefined.  If that is the case, we can't
3720
                 make the expression fully redundant,
3721
                 because its value is undefined along a
3722
                 predecessor path.  We can thus break out
3723
                 early because it doesn't matter what the
3724
                 rest of the results are.  */
3725
              if (eprime == NULL)
3726
                {
3727
                  cant_insert = true;
3728
                  break;
3729
                }
3730
 
3731
              eprime = fully_constant_expression (eprime);
3732
              vprime = get_expr_value_id (eprime);
3733
              edoubleprime = bitmap_find_leader (AVAIL_OUT (bprime),
3734
                                                 vprime, NULL);
3735
              if (edoubleprime == NULL)
3736
                {
3737
                  by_all = false;
3738
                  break;
3739
                }
3740
              else
3741
                avail[bprime->index] = edoubleprime;
3742
 
3743
            }
3744
 
3745
          /* If we can insert it, it's not the same value
3746
             already existing along every predecessor, and
3747
             it's defined by some predecessor, it is
3748
             partially redundant.  */
3749
          if (!cant_insert && by_all && dbg_cnt (treepre_insert))
3750
            {
3751
              pre_stats.pa_insert++;
3752
              if (insert_into_preds_of_block (block, get_expression_id (expr),
3753
                                              avail))
3754
                new_stuff = true;
3755
            }
3756
          free (avail);
3757
        }
3758
    }
3759
 
3760
  VEC_free (pre_expr, heap, exprs);
3761
  return new_stuff;
3762
}
3763
 
3764
static bool
3765
insert_aux (basic_block block)
3766
{
3767
  basic_block son;
3768
  bool new_stuff = false;
3769
 
3770
  if (block)
3771
    {
3772
      basic_block dom;
3773
      dom = get_immediate_dominator (CDI_DOMINATORS, block);
3774
      if (dom)
3775
        {
3776
          unsigned i;
3777
          bitmap_iterator bi;
3778
          bitmap_set_t newset = NEW_SETS (dom);
3779
          if (newset)
3780
            {
3781
              /* Note that we need to value_replace both NEW_SETS, and
3782
                 AVAIL_OUT. For both the case of NEW_SETS, the value may be
3783
                 represented by some non-simple expression here that we want
3784
                 to replace it with.  */
3785
              FOR_EACH_EXPR_ID_IN_SET (newset, i, bi)
3786
                {
3787
                  pre_expr expr = expression_for_id (i);
3788
                  bitmap_value_replace_in_set (NEW_SETS (block), expr);
3789
                  bitmap_value_replace_in_set (AVAIL_OUT (block), expr);
3790
                }
3791
            }
3792
          if (!single_pred_p (block))
3793
            {
3794
              new_stuff |= do_regular_insertion (block, dom);
3795
              if (do_partial_partial)
3796
                new_stuff |= do_partial_partial_insertion (block, dom);
3797
            }
3798
        }
3799
    }
3800
  for (son = first_dom_son (CDI_DOMINATORS, block);
3801
       son;
3802
       son = next_dom_son (CDI_DOMINATORS, son))
3803
    {
3804
      new_stuff |= insert_aux (son);
3805
    }
3806
 
3807
  return new_stuff;
3808
}
3809
 
3810
/* Perform insertion of partially redundant values.  */
3811
 
3812
static void
3813
insert (void)
3814
{
3815
  bool new_stuff = true;
3816
  basic_block bb;
3817
  int num_iterations = 0;
3818
 
3819
  FOR_ALL_BB (bb)
3820
    NEW_SETS (bb) = bitmap_set_new ();
3821
 
3822
  while (new_stuff)
3823
    {
3824
      num_iterations++;
3825
      new_stuff = insert_aux (ENTRY_BLOCK_PTR);
3826
    }
3827
  statistics_histogram_event (cfun, "insert iterations", num_iterations);
3828
}
3829
 
3830
 
3831
/* Add OP to EXP_GEN (block), and possibly to the maximal set.  */
3832
 
3833
static void
3834
add_to_exp_gen (basic_block block, tree op)
3835
{
3836
  if (!in_fre)
3837
    {
3838
      pre_expr result;
3839
      if (TREE_CODE (op) == SSA_NAME && ssa_undefined_value_p (op))
3840
        return;
3841
      result = get_or_alloc_expr_for_name (op);
3842
      bitmap_value_insert_into_set (EXP_GEN (block), result);
3843
    }
3844
}
3845
 
3846
/* Create value ids for PHI in BLOCK.  */
3847
 
3848
static void
3849
make_values_for_phi (gimple phi, basic_block block)
3850
{
3851
  tree result = gimple_phi_result (phi);
3852
 
3853
  /* We have no need for virtual phis, as they don't represent
3854
     actual computations.  */
3855
  if (is_gimple_reg (result))
3856
    {
3857
      pre_expr e = get_or_alloc_expr_for_name (result);
3858
      add_to_value (get_expr_value_id (e), e);
3859
      bitmap_insert_into_set (PHI_GEN (block), e);
3860
      bitmap_value_insert_into_set (AVAIL_OUT (block), e);
3861
      if (!in_fre)
3862
        {
3863
          unsigned i;
3864
          for (i = 0; i < gimple_phi_num_args (phi); ++i)
3865
            {
3866
              tree arg = gimple_phi_arg_def (phi, i);
3867
              if (TREE_CODE (arg) == SSA_NAME)
3868
                {
3869
                  e = get_or_alloc_expr_for_name (arg);
3870
                  add_to_value (get_expr_value_id (e), e);
3871
                }
3872
            }
3873
        }
3874
    }
3875
}
3876
 
3877
/* Compute the AVAIL set for all basic blocks.
3878
 
3879
   This function performs value numbering of the statements in each basic
3880
   block.  The AVAIL sets are built from information we glean while doing
3881
   this value numbering, since the AVAIL sets contain only one entry per
3882
   value.
3883
 
3884
   AVAIL_IN[BLOCK] = AVAIL_OUT[dom(BLOCK)].
3885
   AVAIL_OUT[BLOCK] = AVAIL_IN[BLOCK] U PHI_GEN[BLOCK] U TMP_GEN[BLOCK].  */
3886
 
3887
static void
3888
compute_avail (void)
3889
{
3890
 
3891
  basic_block block, son;
3892
  basic_block *worklist;
3893
  size_t sp = 0;
3894
  unsigned i;
3895
 
3896
  /* We pretend that default definitions are defined in the entry block.
3897
     This includes function arguments and the static chain decl.  */
3898
  for (i = 1; i < num_ssa_names; ++i)
3899
    {
3900
      tree name = ssa_name (i);
3901
      pre_expr e;
3902
      if (!name
3903
          || !SSA_NAME_IS_DEFAULT_DEF (name)
3904
          || has_zero_uses (name)
3905
          || !is_gimple_reg (name))
3906
        continue;
3907
 
3908
      e = get_or_alloc_expr_for_name (name);
3909
      add_to_value (get_expr_value_id (e), e);
3910
      if (!in_fre)
3911
        bitmap_insert_into_set (TMP_GEN (ENTRY_BLOCK_PTR), e);
3912
      bitmap_value_insert_into_set (AVAIL_OUT (ENTRY_BLOCK_PTR), e);
3913
    }
3914
 
3915
  /* Allocate the worklist.  */
3916
  worklist = XNEWVEC (basic_block, n_basic_blocks);
3917
 
3918
  /* Seed the algorithm by putting the dominator children of the entry
3919
     block on the worklist.  */
3920
  for (son = first_dom_son (CDI_DOMINATORS, ENTRY_BLOCK_PTR);
3921
       son;
3922
       son = next_dom_son (CDI_DOMINATORS, son))
3923
    worklist[sp++] = son;
3924
 
3925
  /* Loop until the worklist is empty.  */
3926
  while (sp)
3927
    {
3928
      gimple_stmt_iterator gsi;
3929
      gimple stmt;
3930
      basic_block dom;
3931
      unsigned int stmt_uid = 1;
3932
 
3933
      /* Pick a block from the worklist.  */
3934
      block = worklist[--sp];
3935
 
3936
      /* Initially, the set of available values in BLOCK is that of
3937
         its immediate dominator.  */
3938
      dom = get_immediate_dominator (CDI_DOMINATORS, block);
3939
      if (dom)
3940
        bitmap_set_copy (AVAIL_OUT (block), AVAIL_OUT (dom));
3941
 
3942
      /* Generate values for PHI nodes.  */
3943
      for (gsi = gsi_start_phis (block); !gsi_end_p (gsi); gsi_next (&gsi))
3944
        make_values_for_phi (gsi_stmt (gsi), block);
3945
 
3946
      BB_MAY_NOTRETURN (block) = 0;
3947
 
3948
      /* Now compute value numbers and populate value sets with all
3949
         the expressions computed in BLOCK.  */
3950
      for (gsi = gsi_start_bb (block); !gsi_end_p (gsi); gsi_next (&gsi))
3951
        {
3952
          ssa_op_iter iter;
3953
          tree op;
3954
 
3955
          stmt = gsi_stmt (gsi);
3956
          gimple_set_uid (stmt, stmt_uid++);
3957
 
3958
          /* Cache whether the basic-block has any non-visible side-effect
3959
             or control flow.
3960
             If this isn't a call or it is the last stmt in the
3961
             basic-block then the CFG represents things correctly.  */
3962
          if (is_gimple_call (stmt)
3963
              && !stmt_ends_bb_p (stmt))
3964
            {
3965
              /* Non-looping const functions always return normally.
3966
                 Otherwise the call might not return or have side-effects
3967
                 that forbids hoisting possibly trapping expressions
3968
                 before it.  */
3969
              int flags = gimple_call_flags (stmt);
3970
              if (!(flags & ECF_CONST)
3971
                  || (flags & ECF_LOOPING_CONST_OR_PURE))
3972
                BB_MAY_NOTRETURN (block) = 1;
3973
            }
3974
 
3975
          FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_DEF)
3976
            {
3977
              pre_expr e = get_or_alloc_expr_for_name (op);
3978
 
3979
              add_to_value (get_expr_value_id (e), e);
3980
              if (!in_fre)
3981
                bitmap_insert_into_set (TMP_GEN (block), e);
3982
              bitmap_value_insert_into_set (AVAIL_OUT (block), e);
3983
            }
3984
 
3985
          if (gimple_has_volatile_ops (stmt)
3986
              || stmt_could_throw_p (stmt))
3987
            continue;
3988
 
3989
          switch (gimple_code (stmt))
3990
            {
3991
            case GIMPLE_RETURN:
3992
              FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_USE)
3993
                add_to_exp_gen (block, op);
3994
              continue;
3995
 
3996
            case GIMPLE_CALL:
3997
              {
3998
                vn_reference_t ref;
3999
                unsigned int i;
4000
                vn_reference_op_t vro;
4001
                pre_expr result = NULL;
4002
                VEC(vn_reference_op_s, heap) *ops = NULL;
4003
 
4004
                if (!can_value_number_call (stmt))
4005
                  continue;
4006
 
4007
                copy_reference_ops_from_call (stmt, &ops);
4008
                vn_reference_lookup_pieces (gimple_vuse (stmt), 0,
4009
                                            gimple_expr_type (stmt),
4010
                                            ops, &ref, VN_NOWALK);
4011
                VEC_free (vn_reference_op_s, heap, ops);
4012
                if (!ref)
4013
                  continue;
4014
 
4015
                for (i = 0; VEC_iterate (vn_reference_op_s,
4016
                                         ref->operands, i,
4017
                                         vro); i++)
4018
                  {
4019
                    if (vro->op0 && TREE_CODE (vro->op0) == SSA_NAME)
4020
                      add_to_exp_gen (block, vro->op0);
4021
                    if (vro->op1 && TREE_CODE (vro->op1) == SSA_NAME)
4022
                      add_to_exp_gen (block, vro->op1);
4023
                    if (vro->op2 && TREE_CODE (vro->op2) == SSA_NAME)
4024
                      add_to_exp_gen (block, vro->op2);
4025
                  }
4026
                result = (pre_expr) pool_alloc (pre_expr_pool);
4027
                result->kind = REFERENCE;
4028
                result->id = 0;
4029
                PRE_EXPR_REFERENCE (result) = ref;
4030
 
4031
                get_or_alloc_expression_id (result);
4032
                add_to_value (get_expr_value_id (result), result);
4033
                if (!in_fre)
4034
                  bitmap_value_insert_into_set (EXP_GEN (block), result);
4035
                continue;
4036
              }
4037
 
4038
            case GIMPLE_ASSIGN:
4039
              {
4040
                pre_expr result = NULL;
4041
                switch (TREE_CODE_CLASS (gimple_assign_rhs_code (stmt)))
4042
                  {
4043
                  case tcc_unary:
4044
                  case tcc_binary:
4045
                  case tcc_comparison:
4046
                    {
4047
                      vn_nary_op_t nary;
4048
                      unsigned int i;
4049
 
4050
                      vn_nary_op_lookup_pieces (gimple_num_ops (stmt) - 1,
4051
                                                gimple_assign_rhs_code (stmt),
4052
                                                gimple_expr_type (stmt),
4053
                                                gimple_assign_rhs1_ptr (stmt),
4054
                                                &nary);
4055
 
4056
                      if (!nary)
4057
                        continue;
4058
 
4059
                      for (i = 0; i < nary->length; i++)
4060
                        if (TREE_CODE (nary->op[i]) == SSA_NAME)
4061
                          add_to_exp_gen (block, nary->op[i]);
4062
 
4063
                      result = (pre_expr) pool_alloc (pre_expr_pool);
4064
                      result->kind = NARY;
4065
                      result->id = 0;
4066
                      PRE_EXPR_NARY (result) = nary;
4067
                      break;
4068
                    }
4069
 
4070
                  case tcc_declaration:
4071
                  case tcc_reference:
4072
                    {
4073
                      vn_reference_t ref;
4074
                      unsigned int i;
4075
                      vn_reference_op_t vro;
4076
 
4077
                      vn_reference_lookup (gimple_assign_rhs1 (stmt),
4078
                                           gimple_vuse (stmt),
4079
                                           VN_WALK, &ref);
4080
                      if (!ref)
4081
                        continue;
4082
 
4083
                      for (i = 0; VEC_iterate (vn_reference_op_s,
4084
                                               ref->operands, i,
4085
                                               vro); i++)
4086
                        {
4087
                          if (vro->op0 && TREE_CODE (vro->op0) == SSA_NAME)
4088
                            add_to_exp_gen (block, vro->op0);
4089
                          if (vro->op1 && TREE_CODE (vro->op1) == SSA_NAME)
4090
                            add_to_exp_gen (block, vro->op1);
4091
                          if (vro->op2 && TREE_CODE (vro->op2) == SSA_NAME)
4092
                            add_to_exp_gen (block, vro->op2);
4093
                        }
4094
                      result = (pre_expr) pool_alloc (pre_expr_pool);
4095
                      result->kind = REFERENCE;
4096
                      result->id = 0;
4097
                      PRE_EXPR_REFERENCE (result) = ref;
4098
                      break;
4099
                    }
4100
 
4101
                  default:
4102
                    /* For any other statement that we don't
4103
                       recognize, simply add all referenced
4104
                       SSA_NAMEs to EXP_GEN.  */
4105
                    FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_USE)
4106
                      add_to_exp_gen (block, op);
4107
                    continue;
4108
                  }
4109
 
4110
                get_or_alloc_expression_id (result);
4111
                add_to_value (get_expr_value_id (result), result);
4112
                if (!in_fre)
4113
                  bitmap_value_insert_into_set (EXP_GEN (block), result);
4114
 
4115
                continue;
4116
              }
4117
            default:
4118
              break;
4119
            }
4120
        }
4121
 
4122
      /* Put the dominator children of BLOCK on the worklist of blocks
4123
         to compute available sets for.  */
4124
      for (son = first_dom_son (CDI_DOMINATORS, block);
4125
           son;
4126
           son = next_dom_son (CDI_DOMINATORS, son))
4127
        worklist[sp++] = son;
4128
    }
4129
 
4130
  free (worklist);
4131
}
4132
 
4133
/* Insert the expression for SSA_VN that SCCVN thought would be simpler
4134
   than the available expressions for it.  The insertion point is
4135
   right before the first use in STMT.  Returns the SSA_NAME that should
4136
   be used for replacement.  */
4137
 
4138
static tree
4139
do_SCCVN_insertion (gimple stmt, tree ssa_vn)
4140
{
4141
  basic_block bb = gimple_bb (stmt);
4142
  gimple_stmt_iterator gsi;
4143
  gimple_seq stmts = NULL;
4144
  tree expr;
4145
  pre_expr e;
4146
 
4147
  /* First create a value expression from the expression we want
4148
     to insert and associate it with the value handle for SSA_VN.  */
4149
  e = get_or_alloc_expr_for (vn_get_expr_for (ssa_vn));
4150
  if (e == NULL)
4151
    return NULL_TREE;
4152
 
4153
  /* Then use create_expression_by_pieces to generate a valid
4154
     expression to insert at this point of the IL stream.  */
4155
  expr = create_expression_by_pieces (bb, e, &stmts, stmt, NULL);
4156
  if (expr == NULL_TREE)
4157
    return NULL_TREE;
4158
  gsi = gsi_for_stmt (stmt);
4159
  gsi_insert_seq_before (&gsi, stmts, GSI_SAME_STMT);
4160
 
4161
  return expr;
4162
}
4163
 
4164
/* Eliminate fully redundant computations.  */
4165
 
4166
static unsigned int
4167
eliminate (void)
4168
{
4169
  VEC (gimple, heap) *to_remove = NULL;
4170
  VEC (gimple, heap) *to_update = NULL;
4171
  basic_block b;
4172
  unsigned int todo = 0;
4173
  gimple_stmt_iterator gsi;
4174
  gimple stmt;
4175
  unsigned i;
4176
 
4177
  FOR_EACH_BB (b)
4178
    {
4179
      for (gsi = gsi_start_bb (b); !gsi_end_p (gsi); gsi_next (&gsi))
4180
        {
4181
          tree lhs = NULL_TREE;
4182
          tree rhs = NULL_TREE;
4183
 
4184
          stmt = gsi_stmt (gsi);
4185
 
4186
          if (gimple_has_lhs (stmt))
4187
            lhs = gimple_get_lhs (stmt);
4188
 
4189
          if (gimple_assign_single_p (stmt))
4190
            rhs = gimple_assign_rhs1 (stmt);
4191
 
4192
          /* Lookup the RHS of the expression, see if we have an
4193
             available computation for it.  If so, replace the RHS with
4194
             the available computation.
4195
 
4196
             See PR43491.
4197
             We don't replace global register variable when it is a the RHS of
4198
             a single assign. We do replace local register variable since gcc
4199
             does not guarantee local variable will be allocated in register.  */
4200
          if (gimple_has_lhs (stmt)
4201
              && TREE_CODE (lhs) == SSA_NAME
4202
              && !gimple_assign_ssa_name_copy_p (stmt)
4203
              && (!gimple_assign_single_p (stmt)
4204
                  || (!is_gimple_min_invariant (rhs)
4205
                      && (gimple_assign_rhs_code (stmt) != VAR_DECL
4206
                          || !is_global_var (rhs)
4207
                          || !DECL_HARD_REGISTER (rhs))))
4208
              && !gimple_has_volatile_ops  (stmt)
4209
              && !has_zero_uses (lhs))
4210
            {
4211
              tree sprime = NULL;
4212
              pre_expr lhsexpr = get_or_alloc_expr_for_name (lhs);
4213
              pre_expr sprimeexpr;
4214
              gimple orig_stmt = stmt;
4215
 
4216
              sprimeexpr = bitmap_find_leader (AVAIL_OUT (b),
4217
                                               get_expr_value_id (lhsexpr),
4218
                                               NULL);
4219
 
4220
              if (sprimeexpr)
4221
                {
4222
                  if (sprimeexpr->kind == CONSTANT)
4223
                    sprime = PRE_EXPR_CONSTANT (sprimeexpr);
4224
                  else if (sprimeexpr->kind == NAME)
4225
                    sprime = PRE_EXPR_NAME (sprimeexpr);
4226
                  else
4227
                    gcc_unreachable ();
4228
                }
4229
 
4230
              /* If there is no existing leader but SCCVN knows this
4231
                 value is constant, use that constant.  */
4232
              if (!sprime && is_gimple_min_invariant (VN_INFO (lhs)->valnum))
4233
                {
4234
                  sprime = VN_INFO (lhs)->valnum;
4235
                  if (!useless_type_conversion_p (TREE_TYPE (lhs),
4236
                                                  TREE_TYPE (sprime)))
4237
                    sprime = fold_convert (TREE_TYPE (lhs), sprime);
4238
 
4239
                  if (dump_file && (dump_flags & TDF_DETAILS))
4240
                    {
4241
                      fprintf (dump_file, "Replaced ");
4242
                      print_gimple_expr (dump_file, stmt, 0, 0);
4243
                      fprintf (dump_file, " with ");
4244
                      print_generic_expr (dump_file, sprime, 0);
4245
                      fprintf (dump_file, " in ");
4246
                      print_gimple_stmt (dump_file, stmt, 0, 0);
4247
                    }
4248
                  pre_stats.eliminations++;
4249
                  propagate_tree_value_into_stmt (&gsi, sprime);
4250
                  stmt = gsi_stmt (gsi);
4251
                  update_stmt (stmt);
4252
 
4253
                  /* If we removed EH side-effects from the statement, clean
4254
                     its EH information.  */
4255
                  if (maybe_clean_or_replace_eh_stmt (orig_stmt, stmt))
4256
                    {
4257
                      bitmap_set_bit (need_eh_cleanup,
4258
                                      gimple_bb (stmt)->index);
4259
                      if (dump_file && (dump_flags & TDF_DETAILS))
4260
                        fprintf (dump_file, "  Removed EH side-effects.\n");
4261
                    }
4262
                  continue;
4263
                }
4264
 
4265
              /* If there is no existing usable leader but SCCVN thinks
4266
                 it has an expression it wants to use as replacement,
4267
                 insert that.  */
4268
              if (!sprime || sprime == lhs)
4269
                {
4270
                  tree val = VN_INFO (lhs)->valnum;
4271
                  if (val != VN_TOP
4272
                      && TREE_CODE (val) == SSA_NAME
4273
                      && VN_INFO (val)->needs_insertion
4274
                      && can_PRE_operation (vn_get_expr_for (val)))
4275
                    sprime = do_SCCVN_insertion (stmt, val);
4276
                }
4277
              if (sprime
4278
                  && sprime != lhs
4279
                  && (rhs == NULL_TREE
4280
                      || TREE_CODE (rhs) != SSA_NAME
4281
                      || may_propagate_copy (rhs, sprime)))
4282
                {
4283
                  bool can_make_abnormal_goto
4284
                    = is_gimple_call (stmt)
4285
                      && stmt_can_make_abnormal_goto (stmt);
4286
 
4287
                  gcc_assert (sprime != rhs);
4288
 
4289
                  if (dump_file && (dump_flags & TDF_DETAILS))
4290
                    {
4291
                      fprintf (dump_file, "Replaced ");
4292
                      print_gimple_expr (dump_file, stmt, 0, 0);
4293
                      fprintf (dump_file, " with ");
4294
                      print_generic_expr (dump_file, sprime, 0);
4295
                      fprintf (dump_file, " in ");
4296
                      print_gimple_stmt (dump_file, stmt, 0, 0);
4297
                    }
4298
 
4299
                  if (TREE_CODE (sprime) == SSA_NAME)
4300
                    gimple_set_plf (SSA_NAME_DEF_STMT (sprime),
4301
                                    NECESSARY, true);
4302
                  /* We need to make sure the new and old types actually match,
4303
                     which may require adding a simple cast, which fold_convert
4304
                     will do for us.  */
4305
                  if ((!rhs || TREE_CODE (rhs) != SSA_NAME)
4306
                      && !useless_type_conversion_p (gimple_expr_type (stmt),
4307
                                                     TREE_TYPE (sprime)))
4308
                    sprime = fold_convert (gimple_expr_type (stmt), sprime);
4309
 
4310
                  pre_stats.eliminations++;
4311
                  propagate_tree_value_into_stmt (&gsi, sprime);
4312
                  stmt = gsi_stmt (gsi);
4313
                  update_stmt (stmt);
4314
 
4315
                  /* If we removed EH side-effects from the statement, clean
4316
                     its EH information.  */
4317
                  if (maybe_clean_or_replace_eh_stmt (orig_stmt, stmt))
4318
                    {
4319
                      bitmap_set_bit (need_eh_cleanup,
4320
                                      gimple_bb (stmt)->index);
4321
                      if (dump_file && (dump_flags & TDF_DETAILS))
4322
                        fprintf (dump_file, "  Removed EH side-effects.\n");
4323
                    }
4324
 
4325
                  /* Likewise for AB side-effects.  */
4326
                  if (can_make_abnormal_goto
4327
                      && !stmt_can_make_abnormal_goto (stmt))
4328
                    {
4329
                      bitmap_set_bit (need_ab_cleanup,
4330
                                      gimple_bb (stmt)->index);
4331
                      if (dump_file && (dump_flags & TDF_DETAILS))
4332
                        fprintf (dump_file, "  Removed AB side-effects.\n");
4333
                    }
4334
                }
4335
            }
4336
          /* If the statement is a scalar store, see if the expression
4337
             has the same value number as its rhs.  If so, the store is
4338
             dead.  */
4339
          else if (gimple_assign_single_p (stmt)
4340
                   && !is_gimple_reg (gimple_assign_lhs (stmt))
4341
                   && (TREE_CODE (rhs) == SSA_NAME
4342
                       || is_gimple_min_invariant (rhs)))
4343
            {
4344
              tree val;
4345
              val = vn_reference_lookup (gimple_assign_lhs (stmt),
4346
                                         gimple_vuse (stmt), VN_WALK, NULL);
4347
              if (TREE_CODE (rhs) == SSA_NAME)
4348
                rhs = VN_INFO (rhs)->valnum;
4349
              if (val
4350
                  && operand_equal_p (val, rhs, 0))
4351
                {
4352
                  if (dump_file && (dump_flags & TDF_DETAILS))
4353
                    {
4354
                      fprintf (dump_file, "Deleted redundant store ");
4355
                      print_gimple_stmt (dump_file, stmt, 0, 0);
4356
                    }
4357
 
4358
                  /* Queue stmt for removal.  */
4359
                  VEC_safe_push (gimple, heap, to_remove, stmt);
4360
                }
4361
            }
4362
          /* Visit COND_EXPRs and fold the comparison with the
4363
             available value-numbers.  */
4364
          else if (gimple_code (stmt) == GIMPLE_COND)
4365
            {
4366
              tree op0 = gimple_cond_lhs (stmt);
4367
              tree op1 = gimple_cond_rhs (stmt);
4368
              tree result;
4369
 
4370
              if (TREE_CODE (op0) == SSA_NAME)
4371
                op0 = VN_INFO (op0)->valnum;
4372
              if (TREE_CODE (op1) == SSA_NAME)
4373
                op1 = VN_INFO (op1)->valnum;
4374
              result = fold_binary (gimple_cond_code (stmt), boolean_type_node,
4375
                                    op0, op1);
4376
              if (result && TREE_CODE (result) == INTEGER_CST)
4377
                {
4378
                  if (integer_zerop (result))
4379
                    gimple_cond_make_false (stmt);
4380
                  else
4381
                    gimple_cond_make_true (stmt);
4382
                  update_stmt (stmt);
4383
                  todo = TODO_cleanup_cfg;
4384
                }
4385
            }
4386
          /* Visit indirect calls and turn them into direct calls if
4387
             possible.  */
4388
          if (is_gimple_call (stmt))
4389
            {
4390
              tree orig_fn = gimple_call_fn (stmt);
4391
              tree fn;
4392
              if (!orig_fn)
4393
                continue;
4394
              if (TREE_CODE (orig_fn) == SSA_NAME)
4395
                fn = VN_INFO (orig_fn)->valnum;
4396
              else if (TREE_CODE (orig_fn) == OBJ_TYPE_REF
4397
                       && TREE_CODE (OBJ_TYPE_REF_EXPR (orig_fn)) == SSA_NAME)
4398
                fn = VN_INFO (OBJ_TYPE_REF_EXPR (orig_fn))->valnum;
4399
              else
4400
                continue;
4401
              if (gimple_call_addr_fndecl (fn) != NULL_TREE
4402
                  && useless_type_conversion_p (TREE_TYPE (orig_fn),
4403
                                                TREE_TYPE (fn)))
4404
                {
4405
                  bool can_make_abnormal_goto
4406
                    = stmt_can_make_abnormal_goto (stmt);
4407
                  bool was_noreturn = gimple_call_noreturn_p (stmt);
4408
 
4409
                  if (dump_file && (dump_flags & TDF_DETAILS))
4410
                    {
4411
                      fprintf (dump_file, "Replacing call target with ");
4412
                      print_generic_expr (dump_file, fn, 0);
4413
                      fprintf (dump_file, " in ");
4414
                      print_gimple_stmt (dump_file, stmt, 0, 0);
4415
                    }
4416
 
4417
                  gimple_call_set_fn (stmt, fn);
4418
                  VEC_safe_push (gimple, heap, to_update, stmt);
4419
 
4420
                  /* When changing a call into a noreturn call, cfg cleanup
4421
                     is needed to fix up the noreturn call.  */
4422
                  if (!was_noreturn && gimple_call_noreturn_p (stmt))
4423
                    todo |= TODO_cleanup_cfg;
4424
 
4425
                  /* If we removed EH side-effects from the statement, clean
4426
                     its EH information.  */
4427
                  if (maybe_clean_or_replace_eh_stmt (stmt, stmt))
4428
                    {
4429
                      bitmap_set_bit (need_eh_cleanup,
4430
                                      gimple_bb (stmt)->index);
4431
                      if (dump_file && (dump_flags & TDF_DETAILS))
4432
                        fprintf (dump_file, "  Removed EH side-effects.\n");
4433
                    }
4434
 
4435
                  /* Likewise for AB side-effects.  */
4436
                  if (can_make_abnormal_goto
4437
                      && !stmt_can_make_abnormal_goto (stmt))
4438
                    {
4439
                      bitmap_set_bit (need_ab_cleanup,
4440
                                      gimple_bb (stmt)->index);
4441
                      if (dump_file && (dump_flags & TDF_DETAILS))
4442
                        fprintf (dump_file, "  Removed AB side-effects.\n");
4443
                    }
4444
 
4445
                  /* Changing an indirect call to a direct call may
4446
                     have exposed different semantics.  This may
4447
                     require an SSA update.  */
4448
                  todo |= TODO_update_ssa_only_virtuals;
4449
                }
4450
            }
4451
        }
4452
 
4453
      for (gsi = gsi_start_phis (b); !gsi_end_p (gsi);)
4454
        {
4455
          gimple stmt, phi = gsi_stmt (gsi);
4456
          tree sprime = NULL_TREE, res = PHI_RESULT (phi);
4457
          pre_expr sprimeexpr, resexpr;
4458
          gimple_stmt_iterator gsi2;
4459
 
4460
          /* We want to perform redundant PHI elimination.  Do so by
4461
             replacing the PHI with a single copy if possible.
4462
             Do not touch inserted, single-argument or virtual PHIs.  */
4463
          if (gimple_phi_num_args (phi) == 1
4464
              || !is_gimple_reg (res))
4465
            {
4466
              gsi_next (&gsi);
4467
              continue;
4468
            }
4469
 
4470
          resexpr = get_or_alloc_expr_for_name (res);
4471
          sprimeexpr = bitmap_find_leader (AVAIL_OUT (b),
4472
                                           get_expr_value_id (resexpr), NULL);
4473
          if (sprimeexpr)
4474
            {
4475
              if (sprimeexpr->kind == CONSTANT)
4476
                sprime = PRE_EXPR_CONSTANT (sprimeexpr);
4477
              else if (sprimeexpr->kind == NAME)
4478
                sprime = PRE_EXPR_NAME (sprimeexpr);
4479
              else
4480
                gcc_unreachable ();
4481
            }
4482
          if (!sprime && is_gimple_min_invariant (VN_INFO (res)->valnum))
4483
            {
4484
              sprime = VN_INFO (res)->valnum;
4485
              if (!useless_type_conversion_p (TREE_TYPE (res),
4486
                                              TREE_TYPE (sprime)))
4487
                sprime = fold_convert (TREE_TYPE (res), sprime);
4488
            }
4489
          if (!sprime
4490
              || sprime == res)
4491
            {
4492
              gsi_next (&gsi);
4493
              continue;
4494
            }
4495
 
4496
          if (dump_file && (dump_flags & TDF_DETAILS))
4497
            {
4498
              fprintf (dump_file, "Replaced redundant PHI node defining ");
4499
              print_generic_expr (dump_file, res, 0);
4500
              fprintf (dump_file, " with ");
4501
              print_generic_expr (dump_file, sprime, 0);
4502
              fprintf (dump_file, "\n");
4503
            }
4504
 
4505
          remove_phi_node (&gsi, false);
4506
 
4507
          if (!bitmap_bit_p (inserted_exprs, SSA_NAME_VERSION (res))
4508
              && TREE_CODE (sprime) == SSA_NAME)
4509
            gimple_set_plf (SSA_NAME_DEF_STMT (sprime), NECESSARY, true);
4510
 
4511
          if (!useless_type_conversion_p (TREE_TYPE (res), TREE_TYPE (sprime)))
4512
            sprime = fold_convert (TREE_TYPE (res), sprime);
4513
          stmt = gimple_build_assign (res, sprime);
4514
          SSA_NAME_DEF_STMT (res) = stmt;
4515
          gimple_set_plf (stmt, NECESSARY, gimple_plf (phi, NECESSARY));
4516
 
4517
          gsi2 = gsi_after_labels (b);
4518
          gsi_insert_before (&gsi2, stmt, GSI_NEW_STMT);
4519
          /* Queue the copy for eventual removal.  */
4520
          VEC_safe_push (gimple, heap, to_remove, stmt);
4521
          /* If we inserted this PHI node ourself, it's not an elimination.  */
4522
          if (bitmap_bit_p (inserted_exprs, SSA_NAME_VERSION (res)))
4523
            pre_stats.phis--;
4524
          else
4525
            pre_stats.eliminations++;
4526
        }
4527
    }
4528
 
4529
  /* We cannot remove stmts during BB walk, especially not release SSA
4530
     names there as this confuses the VN machinery.  The stmts ending
4531
     up in to_remove are either stores or simple copies.  */
4532
  FOR_EACH_VEC_ELT (gimple, to_remove, i, stmt)
4533
    {
4534
      tree lhs = gimple_assign_lhs (stmt);
4535
      tree rhs = gimple_assign_rhs1 (stmt);
4536
      use_operand_p use_p;
4537
      gimple use_stmt;
4538
 
4539
      /* If there is a single use only, propagate the equivalency
4540
         instead of keeping the copy.  */
4541
      if (TREE_CODE (lhs) == SSA_NAME
4542
          && TREE_CODE (rhs) == SSA_NAME
4543
          && single_imm_use (lhs, &use_p, &use_stmt)
4544
          && may_propagate_copy (USE_FROM_PTR (use_p), rhs))
4545
        {
4546
          SET_USE (use_p, rhs);
4547
          update_stmt (use_stmt);
4548
          if (bitmap_bit_p (inserted_exprs, SSA_NAME_VERSION (lhs))
4549
              && TREE_CODE (rhs) == SSA_NAME)
4550
            gimple_set_plf (SSA_NAME_DEF_STMT (rhs), NECESSARY, true);
4551
        }
4552
 
4553
      /* If this is a store or a now unused copy, remove it.  */
4554
      if (TREE_CODE (lhs) != SSA_NAME
4555
          || has_zero_uses (lhs))
4556
        {
4557
          basic_block bb = gimple_bb (stmt);
4558
          gsi = gsi_for_stmt (stmt);
4559
          unlink_stmt_vdef (stmt);
4560
          gsi_remove (&gsi, true);
4561
          /* ???  gsi_remove doesn't tell us whether the stmt was
4562
             in EH tables and thus whether we need to purge EH edges.
4563
             Simply schedule the block for a cleanup.  */
4564
          bitmap_set_bit (need_eh_cleanup, bb->index);
4565
          if (TREE_CODE (lhs) == SSA_NAME)
4566
            bitmap_clear_bit (inserted_exprs, SSA_NAME_VERSION (lhs));
4567
          release_defs (stmt);
4568
        }
4569
    }
4570
  VEC_free (gimple, heap, to_remove);
4571
 
4572
  /* We cannot update call statements with virtual operands during
4573
     SSA walk.  This might remove them which in turn makes our
4574
     VN lattice invalid.  */
4575
  FOR_EACH_VEC_ELT (gimple, to_update, i, stmt)
4576
    update_stmt (stmt);
4577
  VEC_free (gimple, heap, to_update);
4578
 
4579
  return todo;
4580
}
4581
 
4582
/* Borrow a bit of tree-ssa-dce.c for the moment.
4583
   XXX: In 4.1, we should be able to just run a DCE pass after PRE, though
4584
   this may be a bit faster, and we may want critical edges kept split.  */
4585
 
4586
/* If OP's defining statement has not already been determined to be necessary,
4587
   mark that statement necessary. Return the stmt, if it is newly
4588
   necessary.  */
4589
 
4590
static inline gimple
4591
mark_operand_necessary (tree op)
4592
{
4593
  gimple stmt;
4594
 
4595
  gcc_assert (op);
4596
 
4597
  if (TREE_CODE (op) != SSA_NAME)
4598
    return NULL;
4599
 
4600
  stmt = SSA_NAME_DEF_STMT (op);
4601
  gcc_assert (stmt);
4602
 
4603
  if (gimple_plf (stmt, NECESSARY)
4604
      || gimple_nop_p (stmt))
4605
    return NULL;
4606
 
4607
  gimple_set_plf (stmt, NECESSARY, true);
4608
  return stmt;
4609
}
4610
 
4611
/* Because we don't follow exactly the standard PRE algorithm, and decide not
4612
   to insert PHI nodes sometimes, and because value numbering of casts isn't
4613
   perfect, we sometimes end up inserting dead code.   This simple DCE-like
4614
   pass removes any insertions we made that weren't actually used.  */
4615
 
4616
static void
4617
remove_dead_inserted_code (void)
4618
{
4619
  bitmap worklist;
4620
  unsigned i;
4621
  bitmap_iterator bi;
4622
  gimple t;
4623
 
4624
  worklist = BITMAP_ALLOC (NULL);
4625
  EXECUTE_IF_SET_IN_BITMAP (inserted_exprs, 0, i, bi)
4626
    {
4627
      t = SSA_NAME_DEF_STMT (ssa_name (i));
4628
      if (gimple_plf (t, NECESSARY))
4629
        bitmap_set_bit (worklist, i);
4630
    }
4631
  while (!bitmap_empty_p (worklist))
4632
    {
4633
      i = bitmap_first_set_bit (worklist);
4634
      bitmap_clear_bit (worklist, i);
4635
      t = SSA_NAME_DEF_STMT (ssa_name (i));
4636
 
4637
      /* PHI nodes are somewhat special in that each PHI alternative has
4638
         data and control dependencies.  All the statements feeding the
4639
         PHI node's arguments are always necessary. */
4640
      if (gimple_code (t) == GIMPLE_PHI)
4641
        {
4642
          unsigned k;
4643
 
4644
          for (k = 0; k < gimple_phi_num_args (t); k++)
4645
            {
4646
              tree arg = PHI_ARG_DEF (t, k);
4647
              if (TREE_CODE (arg) == SSA_NAME)
4648
                {
4649
                  gimple n = mark_operand_necessary (arg);
4650
                  if (n)
4651
                    bitmap_set_bit (worklist, SSA_NAME_VERSION (arg));
4652
                }
4653
            }
4654
        }
4655
      else
4656
        {
4657
          /* Propagate through the operands.  Examine all the USE, VUSE and
4658
             VDEF operands in this statement.  Mark all the statements
4659
             which feed this statement's uses as necessary.  */
4660
          ssa_op_iter iter;
4661
          tree use;
4662
 
4663
          /* The operands of VDEF expressions are also needed as they
4664
             represent potential definitions that may reach this
4665
             statement (VDEF operands allow us to follow def-def
4666
             links).  */
4667
 
4668
          FOR_EACH_SSA_TREE_OPERAND (use, t, iter, SSA_OP_ALL_USES)
4669
            {
4670
              gimple n = mark_operand_necessary (use);
4671
              if (n)
4672
                bitmap_set_bit (worklist, SSA_NAME_VERSION (use));
4673
            }
4674
        }
4675
    }
4676
 
4677
  EXECUTE_IF_SET_IN_BITMAP (inserted_exprs, 0, i, bi)
4678
    {
4679
      t = SSA_NAME_DEF_STMT (ssa_name (i));
4680
      if (!gimple_plf (t, NECESSARY))
4681
        {
4682
          gimple_stmt_iterator gsi;
4683
 
4684
          if (dump_file && (dump_flags & TDF_DETAILS))
4685
            {
4686
              fprintf (dump_file, "Removing unnecessary insertion:");
4687
              print_gimple_stmt (dump_file, t, 0, 0);
4688
            }
4689
 
4690
          gsi = gsi_for_stmt (t);
4691
          if (gimple_code (t) == GIMPLE_PHI)
4692
            remove_phi_node (&gsi, true);
4693
          else
4694
            {
4695
              gsi_remove (&gsi, true);
4696
              release_defs (t);
4697
            }
4698
        }
4699
    }
4700
  BITMAP_FREE (worklist);
4701
}
4702
 
4703
/* Compute a reverse post-order in *POST_ORDER.  If INCLUDE_ENTRY_EXIT is
4704
   true, then then ENTRY_BLOCK and EXIT_BLOCK are included.  Returns
4705
   the number of visited blocks.  */
4706
 
4707
static int
4708
my_rev_post_order_compute (int *post_order, bool include_entry_exit)
4709
{
4710
  edge_iterator *stack;
4711
  int sp;
4712
  int post_order_num = 0;
4713
  sbitmap visited;
4714
 
4715
  if (include_entry_exit)
4716
    post_order[post_order_num++] = EXIT_BLOCK;
4717
 
4718
  /* Allocate stack for back-tracking up CFG.  */
4719
  stack = XNEWVEC (edge_iterator, n_basic_blocks + 1);
4720
  sp = 0;
4721
 
4722
  /* Allocate bitmap to track nodes that have been visited.  */
4723
  visited = sbitmap_alloc (last_basic_block);
4724
 
4725
  /* None of the nodes in the CFG have been visited yet.  */
4726
  sbitmap_zero (visited);
4727
 
4728
  /* Push the last edge on to the stack.  */
4729
  stack[sp++] = ei_start (EXIT_BLOCK_PTR->preds);
4730
 
4731
  while (sp)
4732
    {
4733
      edge_iterator ei;
4734
      basic_block src;
4735
      basic_block dest;
4736
 
4737
      /* Look at the edge on the top of the stack.  */
4738
      ei = stack[sp - 1];
4739
      src = ei_edge (ei)->src;
4740
      dest = ei_edge (ei)->dest;
4741
 
4742
      /* Check if the edge destination has been visited yet.  */
4743
      if (src != ENTRY_BLOCK_PTR && ! TEST_BIT (visited, src->index))
4744
        {
4745
          /* Mark that we have visited the destination.  */
4746
          SET_BIT (visited, src->index);
4747
 
4748
          if (EDGE_COUNT (src->preds) > 0)
4749
            /* Since the DEST node has been visited for the first
4750
               time, check its successors.  */
4751
            stack[sp++] = ei_start (src->preds);
4752
          else
4753
            post_order[post_order_num++] = src->index;
4754
        }
4755
      else
4756
        {
4757
          if (ei_one_before_end_p (ei) && dest != EXIT_BLOCK_PTR)
4758
            post_order[post_order_num++] = dest->index;
4759
 
4760
          if (!ei_one_before_end_p (ei))
4761
            ei_next (&stack[sp - 1]);
4762
          else
4763
            sp--;
4764
        }
4765
    }
4766
 
4767
  if (include_entry_exit)
4768
    post_order[post_order_num++] = ENTRY_BLOCK;
4769
 
4770
  free (stack);
4771
  sbitmap_free (visited);
4772
  return post_order_num;
4773
}
4774
 
4775
 
4776
/* Initialize data structures used by PRE.  */
4777
 
4778
static void
4779
init_pre (bool do_fre)
4780
{
4781
  basic_block bb;
4782
 
4783
  next_expression_id = 1;
4784
  expressions = NULL;
4785
  VEC_safe_push (pre_expr, heap, expressions, NULL);
4786
  value_expressions = VEC_alloc (bitmap_set_t, heap, get_max_value_id () + 1);
4787
  VEC_safe_grow_cleared (bitmap_set_t, heap, value_expressions,
4788
                         get_max_value_id() + 1);
4789
  name_to_id = NULL;
4790
 
4791
  in_fre = do_fre;
4792
 
4793
  inserted_exprs = BITMAP_ALLOC (NULL);
4794
  need_creation = NULL;
4795
  pretemp = NULL_TREE;
4796
  storetemp = NULL_TREE;
4797
  prephitemp = NULL_TREE;
4798
 
4799
  connect_infinite_loops_to_exit ();
4800
  memset (&pre_stats, 0, sizeof (pre_stats));
4801
 
4802
 
4803
  postorder = XNEWVEC (int, n_basic_blocks - NUM_FIXED_BLOCKS);
4804
  my_rev_post_order_compute (postorder, false);
4805
 
4806
  alloc_aux_for_blocks (sizeof (struct bb_bitmap_sets));
4807
 
4808
  calculate_dominance_info (CDI_POST_DOMINATORS);
4809
  calculate_dominance_info (CDI_DOMINATORS);
4810
 
4811
  bitmap_obstack_initialize (&grand_bitmap_obstack);
4812
  phi_translate_table = htab_create (5110, expr_pred_trans_hash,
4813
                                     expr_pred_trans_eq, free);
4814
  expression_to_id = htab_create (num_ssa_names * 3,
4815
                                  pre_expr_hash,
4816
                                  pre_expr_eq, NULL);
4817
  bitmap_set_pool = create_alloc_pool ("Bitmap sets",
4818
                                       sizeof (struct bitmap_set), 30);
4819
  pre_expr_pool = create_alloc_pool ("pre_expr nodes",
4820
                                     sizeof (struct pre_expr_d), 30);
4821
  FOR_ALL_BB (bb)
4822
    {
4823
      EXP_GEN (bb) = bitmap_set_new ();
4824
      PHI_GEN (bb) = bitmap_set_new ();
4825
      TMP_GEN (bb) = bitmap_set_new ();
4826
      AVAIL_OUT (bb) = bitmap_set_new ();
4827
    }
4828
 
4829
  need_eh_cleanup = BITMAP_ALLOC (NULL);
4830
  need_ab_cleanup = BITMAP_ALLOC (NULL);
4831
}
4832
 
4833
 
4834
/* Deallocate data structures used by PRE.  */
4835
 
4836
static void
4837
fini_pre (bool do_fre)
4838
{
4839
  bool do_eh_cleanup = !bitmap_empty_p (need_eh_cleanup);
4840
  bool do_ab_cleanup = !bitmap_empty_p (need_ab_cleanup);
4841
 
4842
  free (postorder);
4843
  VEC_free (bitmap_set_t, heap, value_expressions);
4844
  BITMAP_FREE (inserted_exprs);
4845
  VEC_free (gimple, heap, need_creation);
4846
  bitmap_obstack_release (&grand_bitmap_obstack);
4847
  free_alloc_pool (bitmap_set_pool);
4848
  free_alloc_pool (pre_expr_pool);
4849
  htab_delete (phi_translate_table);
4850
  htab_delete (expression_to_id);
4851
  VEC_free (unsigned, heap, name_to_id);
4852
 
4853
  free_aux_for_blocks ();
4854
 
4855
  free_dominance_info (CDI_POST_DOMINATORS);
4856
 
4857
  if (do_eh_cleanup)
4858
    gimple_purge_all_dead_eh_edges (need_eh_cleanup);
4859
 
4860
  if (do_ab_cleanup)
4861
    gimple_purge_all_dead_abnormal_call_edges (need_ab_cleanup);
4862
 
4863
  BITMAP_FREE (need_eh_cleanup);
4864
  BITMAP_FREE (need_ab_cleanup);
4865
 
4866
  if (do_eh_cleanup || do_ab_cleanup)
4867
    cleanup_tree_cfg ();
4868
 
4869
  if (!do_fre)
4870
    loop_optimizer_finalize ();
4871
}
4872
 
4873
/* Main entry point to the SSA-PRE pass.  DO_FRE is true if the caller
4874
   only wants to do full redundancy elimination.  */
4875
 
4876
static unsigned int
4877
execute_pre (bool do_fre)
4878
{
4879
  unsigned int todo = 0;
4880
 
4881
  do_partial_partial = optimize > 2 && optimize_function_for_speed_p (cfun);
4882
 
4883
  /* This has to happen before SCCVN runs because
4884
     loop_optimizer_init may create new phis, etc.  */
4885
  if (!do_fre)
4886
    loop_optimizer_init (LOOPS_NORMAL);
4887
 
4888
  if (!run_scc_vn (do_fre ? VN_WALKREWRITE : VN_WALK))
4889
    {
4890
      if (!do_fre)
4891
        loop_optimizer_finalize ();
4892
 
4893
      return 0;
4894
    }
4895
 
4896
  init_pre (do_fre);
4897
  scev_initialize ();
4898
 
4899
  /* Collect and value number expressions computed in each basic block.  */
4900
  compute_avail ();
4901
 
4902
  if (dump_file && (dump_flags & TDF_DETAILS))
4903
    {
4904
      basic_block bb;
4905
 
4906
      FOR_ALL_BB (bb)
4907
        {
4908
          print_bitmap_set (dump_file, EXP_GEN (bb), "exp_gen", bb->index);
4909
          print_bitmap_set (dump_file, PHI_GEN (bb), "phi_gen", bb->index);
4910
          print_bitmap_set (dump_file, TMP_GEN (bb), "tmp_gen", bb->index);
4911
          print_bitmap_set (dump_file, AVAIL_OUT (bb), "avail_out", bb->index);
4912
        }
4913
    }
4914
 
4915
  /* Insert can get quite slow on an incredibly large number of basic
4916
     blocks due to some quadratic behavior.  Until this behavior is
4917
     fixed, don't run it when he have an incredibly large number of
4918
     bb's.  If we aren't going to run insert, there is no point in
4919
     computing ANTIC, either, even though it's plenty fast.  */
4920
  if (!do_fre && n_basic_blocks < 4000)
4921
    {
4922
      compute_antic ();
4923
      insert ();
4924
    }
4925
 
4926
  /* Make sure to remove fake edges before committing our inserts.
4927
     This makes sure we don't end up with extra critical edges that
4928
     we would need to split.  */
4929
  remove_fake_exit_edges ();
4930
  gsi_commit_edge_inserts ();
4931
 
4932
  /* Remove all the redundant expressions.  */
4933
  todo |= eliminate ();
4934
 
4935
  statistics_counter_event (cfun, "Insertions", pre_stats.insertions);
4936
  statistics_counter_event (cfun, "PA inserted", pre_stats.pa_insert);
4937
  statistics_counter_event (cfun, "New PHIs", pre_stats.phis);
4938
  statistics_counter_event (cfun, "Eliminated", pre_stats.eliminations);
4939
  statistics_counter_event (cfun, "Constified", pre_stats.constified);
4940
 
4941
  clear_expression_ids ();
4942
  if (!do_fre)
4943
    {
4944
      remove_dead_inserted_code ();
4945
      todo |= TODO_verify_flow;
4946
    }
4947
 
4948
  scev_finalize ();
4949
  fini_pre (do_fre);
4950
 
4951
  if (!do_fre)
4952
    /* TODO: tail_merge_optimize may merge all predecessors of a block, in which
4953
       case we can merge the block with the remaining predecessor of the block.
4954
       It should either:
4955
       - call merge_blocks after each tail merge iteration
4956
       - call merge_blocks after all tail merge iterations
4957
       - mark TODO_cleanup_cfg when necessary
4958
       - share the cfg cleanup with fini_pre.  */
4959
    todo |= tail_merge_optimize (todo);
4960
  free_scc_vn ();
4961
 
4962
  return todo;
4963
}
4964
 
4965
/* Gate and execute functions for PRE.  */
4966
 
4967
static unsigned int
4968
do_pre (void)
4969
{
4970
  return execute_pre (false);
4971
}
4972
 
4973
static bool
4974
gate_pre (void)
4975
{
4976
  return flag_tree_pre != 0;
4977
}
4978
 
4979
struct gimple_opt_pass pass_pre =
4980
{
4981
 {
4982
  GIMPLE_PASS,
4983
  "pre",                                /* name */
4984
  gate_pre,                             /* gate */
4985
  do_pre,                               /* execute */
4986
  NULL,                                 /* sub */
4987
  NULL,                                 /* next */
4988
  0,                                     /* static_pass_number */
4989
  TV_TREE_PRE,                          /* tv_id */
4990
  PROP_no_crit_edges | PROP_cfg
4991
    | PROP_ssa,                         /* properties_required */
4992
  0,                                     /* properties_provided */
4993
  0,                                     /* properties_destroyed */
4994
  TODO_rebuild_alias,                   /* todo_flags_start */
4995
  TODO_update_ssa_only_virtuals  | TODO_ggc_collect
4996
  | TODO_verify_ssa /* todo_flags_finish */
4997
 }
4998
};
4999
 
5000
 
5001
/* Gate and execute functions for FRE.  */
5002
 
5003
static unsigned int
5004
execute_fre (void)
5005
{
5006
  return execute_pre (true);
5007
}
5008
 
5009
static bool
5010
gate_fre (void)
5011
{
5012
  return flag_tree_fre != 0;
5013
}
5014
 
5015
struct gimple_opt_pass pass_fre =
5016
{
5017
 {
5018
  GIMPLE_PASS,
5019
  "fre",                                /* name */
5020
  gate_fre,                             /* gate */
5021
  execute_fre,                          /* execute */
5022
  NULL,                                 /* sub */
5023
  NULL,                                 /* next */
5024
  0,                                     /* static_pass_number */
5025
  TV_TREE_FRE,                          /* tv_id */
5026
  PROP_cfg | PROP_ssa,                  /* properties_required */
5027
  0,                                     /* properties_provided */
5028
  0,                                     /* properties_destroyed */
5029
  0,                                     /* todo_flags_start */
5030
  TODO_ggc_collect | TODO_verify_ssa /* todo_flags_finish */
5031
 }
5032
};

powered by: WebSVN 2.1.0

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