xref: /netbsd-src/external/gpl3/gcc/dist/gcc/tree-ssa-pre.cc (revision 0a3071956a3a9fdebdbf7f338cf2d439b45fc728)
1 /* Full and partial redundancy elimination and code hoisting on SSA GIMPLE.
2    Copyright (C) 2001-2022 Free Software Foundation, Inc.
3    Contributed by Daniel Berlin <dan@dberlin.org> and Steven Bosscher
4    <stevenb@suse.de>
5 
6 This file is part of GCC.
7 
8 GCC is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 3, or (at your option)
11 any later version.
12 
13 GCC is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16 GNU General Public License for more details.
17 
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3.  If not see
20 <http://www.gnu.org/licenses/>.  */
21 
22 #include "config.h"
23 #include "system.h"
24 #include "coretypes.h"
25 #include "backend.h"
26 #include "rtl.h"
27 #include "tree.h"
28 #include "gimple.h"
29 #include "predict.h"
30 #include "alloc-pool.h"
31 #include "tree-pass.h"
32 #include "ssa.h"
33 #include "cgraph.h"
34 #include "gimple-pretty-print.h"
35 #include "fold-const.h"
36 #include "cfganal.h"
37 #include "gimple-fold.h"
38 #include "tree-eh.h"
39 #include "gimplify.h"
40 #include "gimple-iterator.h"
41 #include "tree-cfg.h"
42 #include "tree-into-ssa.h"
43 #include "tree-dfa.h"
44 #include "tree-ssa.h"
45 #include "cfgloop.h"
46 #include "tree-ssa-sccvn.h"
47 #include "tree-scalar-evolution.h"
48 #include "dbgcnt.h"
49 #include "domwalk.h"
50 #include "tree-ssa-propagate.h"
51 #include "tree-ssa-dce.h"
52 #include "tree-cfgcleanup.h"
53 #include "alias.h"
54 #include "gimple-range.h"
55 
56 /* Even though this file is called tree-ssa-pre.cc, we actually
57    implement a bit more than just PRE here.  All of them piggy-back
58    on GVN which is implemented in tree-ssa-sccvn.cc.
59 
60      1. Full Redundancy Elimination (FRE)
61 	This is the elimination phase of GVN.
62 
63      2. Partial Redundancy Elimination (PRE)
64 	This is adds computation of AVAIL_OUT and ANTIC_IN and
65 	doing expression insertion to form GVN-PRE.
66 
67      3. Code hoisting
68 	This optimization uses the ANTIC_IN sets computed for PRE
69 	to move expressions further up than PRE would do, to make
70 	multiple computations of the same value fully redundant.
71 	This pass is explained below (after the explanation of the
72 	basic algorithm for PRE).
73 */
74 
75 /* TODO:
76 
77    1. Avail sets can be shared by making an avail_find_leader that
78       walks up the dominator tree and looks in those avail sets.
79       This might affect code optimality, it's unclear right now.
80       Currently the AVAIL_OUT sets are the remaining quadraticness in
81       memory of GVN-PRE.
82    2. Strength reduction can be performed by anticipating expressions
83       we can repair later on.
84    3. We can do back-substitution or smarter value numbering to catch
85       commutative expressions split up over multiple statements.
86 */
87 
88 /* For ease of terminology, "expression node" in the below refers to
89    every expression node but GIMPLE_ASSIGN, because GIMPLE_ASSIGNs
90    represent the actual statement containing the expressions we care about,
91    and we cache the value number by putting it in the expression.  */
92 
93 /* Basic algorithm for Partial Redundancy Elimination:
94 
95    First we walk the statements to generate the AVAIL sets, the
96    EXP_GEN sets, and the tmp_gen sets.  EXP_GEN sets represent the
97    generation of values/expressions by a given block.  We use them
98    when computing the ANTIC sets.  The AVAIL sets consist of
99    SSA_NAME's that represent values, so we know what values are
100    available in what blocks.  AVAIL is a forward dataflow problem.  In
101    SSA, values are never killed, so we don't need a kill set, or a
102    fixpoint iteration, in order to calculate the AVAIL sets.  In
103    traditional parlance, AVAIL sets tell us the downsafety of the
104    expressions/values.
105 
106    Next, we generate the ANTIC sets.  These sets represent the
107    anticipatable expressions.  ANTIC is a backwards dataflow
108    problem.  An expression is anticipatable in a given block if it could
109    be generated in that block.  This means that if we had to perform
110    an insertion in that block, of the value of that expression, we
111    could.  Calculating the ANTIC sets requires phi translation of
112    expressions, because the flow goes backwards through phis.  We must
113    iterate to a fixpoint of the ANTIC sets, because we have a kill
114    set.  Even in SSA form, values are not live over the entire
115    function, only from their definition point onwards.  So we have to
116    remove values from the ANTIC set once we go past the definition
117    point of the leaders that make them up.
118    compute_antic/compute_antic_aux performs this computation.
119 
120    Third, we perform insertions to make partially redundant
121    expressions fully redundant.
122 
123    An expression is partially redundant (excluding partial
124    anticipation) if:
125 
126    1. It is AVAIL in some, but not all, of the predecessors of a
127       given block.
128    2. It is ANTIC in all the predecessors.
129 
130    In order to make it fully redundant, we insert the expression into
131    the predecessors where it is not available, but is ANTIC.
132 
133    When optimizing for size, we only eliminate the partial redundancy
134    if we need to insert in only one predecessor.  This avoids almost
135    completely the code size increase that PRE usually causes.
136 
137    For the partial anticipation case, we only perform insertion if it
138    is partially anticipated in some block, and fully available in all
139    of the predecessors.
140 
141    do_pre_regular_insertion/do_pre_partial_partial_insertion
142    performs these steps, driven by insert/insert_aux.
143 
144    Fourth, we eliminate fully redundant expressions.
145    This is a simple statement walk that replaces redundant
146    calculations with the now available values.  */
147 
148 /* Basic algorithm for Code Hoisting:
149 
150    Code hoisting is: Moving value computations up in the control flow
151    graph to make multiple copies redundant.  Typically this is a size
152    optimization, but there are cases where it also is helpful for speed.
153 
154    A simple code hoisting algorithm is implemented that piggy-backs on
155    the PRE infrastructure.  For code hoisting, we have to know ANTIC_OUT
156    which is effectively ANTIC_IN - AVAIL_OUT.  The latter two have to be
157    computed for PRE, and we can use them to perform a limited version of
158    code hoisting, too.
159 
160    For the purpose of this implementation, a value is hoistable to a basic
161    block B if the following properties are met:
162 
163    1. The value is in ANTIC_IN(B) -- the value will be computed on all
164       paths from B to function exit and it can be computed in B);
165 
166    2. The value is not in AVAIL_OUT(B) -- there would be no need to
167       compute the value again and make it available twice;
168 
169    3. All successors of B are dominated by B -- makes sure that inserting
170       a computation of the value in B will make the remaining
171       computations fully redundant;
172 
173    4. At least one successor has the value in AVAIL_OUT -- to avoid
174       hoisting values up too far;
175 
176    5. There are at least two successors of B -- hoisting in straight
177       line code is pointless.
178 
179    The third condition is not strictly necessary, but it would complicate
180    the hoisting pass a lot.  In fact, I don't know of any code hoisting
181    algorithm that does not have this requirement.  Fortunately, experiments
182    have show that most candidate hoistable values are in regions that meet
183    this condition (e.g. diamond-shape regions).
184 
185    The forth condition is necessary to avoid hoisting things up too far
186    away from the uses of the value.  Nothing else limits the algorithm
187    from hoisting everything up as far as ANTIC_IN allows.  Experiments
188    with SPEC and CSiBE have shown that hoisting up too far results in more
189    spilling, less benefits for code size, and worse benchmark scores.
190    Fortunately, in practice most of the interesting hoisting opportunities
191    are caught despite this limitation.
192 
193    For hoistable values that meet all conditions, expressions are inserted
194    to make the calculation of the hoistable value fully redundant.  We
195    perform code hoisting insertions after each round of PRE insertions,
196    because code hoisting never exposes new PRE opportunities, but PRE can
197    create new code hoisting opportunities.
198 
199    The code hoisting algorithm is implemented in do_hoist_insert, driven
200    by insert/insert_aux.  */
201 
202 /* Representations of value numbers:
203 
204    Value numbers are represented by a representative SSA_NAME.  We
205    will create fake SSA_NAME's in situations where we need a
206    representative but do not have one (because it is a complex
207    expression).  In order to facilitate storing the value numbers in
208    bitmaps, and keep the number of wasted SSA_NAME's down, we also
209    associate a value_id with each value number, and create full blown
210    ssa_name's only where we actually need them (IE in operands of
211    existing expressions).
212 
213    Theoretically you could replace all the value_id's with
214    SSA_NAME_VERSION, but this would allocate a large number of
215    SSA_NAME's (which are each > 30 bytes) just to get a 4 byte number.
216    It would also require an additional indirection at each point we
217    use the value id.  */
218 
219 /* Representation of expressions on value numbers:
220 
221    Expressions consisting of value numbers are represented the same
222    way as our VN internally represents them, with an additional
223    "pre_expr" wrapping around them in order to facilitate storing all
224    of the expressions in the same sets.  */
225 
226 /* Representation of sets:
227 
228    The dataflow sets do not need to be sorted in any particular order
229    for the majority of their lifetime, are simply represented as two
230    bitmaps, one that keeps track of values present in the set, and one
231    that keeps track of expressions present in the set.
232 
233    When we need them in topological order, we produce it on demand by
234    transforming the bitmap into an array and sorting it into topo
235    order.  */
236 
237 /* Type of expression, used to know which member of the PRE_EXPR union
238    is valid.  */
239 
240 enum pre_expr_kind
241 {
242     NAME,
243     NARY,
244     REFERENCE,
245     CONSTANT
246 };
247 
248 union pre_expr_union
249 {
250   tree name;
251   tree constant;
252   vn_nary_op_t nary;
253   vn_reference_t reference;
254 };
255 
256 typedef struct pre_expr_d : nofree_ptr_hash <pre_expr_d>
257 {
258   enum pre_expr_kind kind;
259   unsigned int id;
260   unsigned value_id;
261   location_t loc;
262   pre_expr_union u;
263 
264   /* hash_table support.  */
265   static inline hashval_t hash (const pre_expr_d *);
266   static inline int equal (const pre_expr_d *, const pre_expr_d *);
267 } *pre_expr;
268 
269 #define PRE_EXPR_NAME(e) (e)->u.name
270 #define PRE_EXPR_NARY(e) (e)->u.nary
271 #define PRE_EXPR_REFERENCE(e) (e)->u.reference
272 #define PRE_EXPR_CONSTANT(e) (e)->u.constant
273 
274 /* Compare E1 and E1 for equality.  */
275 
276 inline int
equal(const pre_expr_d * e1,const pre_expr_d * e2)277 pre_expr_d::equal (const pre_expr_d *e1, const pre_expr_d *e2)
278 {
279   if (e1->kind != e2->kind)
280     return false;
281 
282   switch (e1->kind)
283     {
284     case CONSTANT:
285       return vn_constant_eq_with_type (PRE_EXPR_CONSTANT (e1),
286 				       PRE_EXPR_CONSTANT (e2));
287     case NAME:
288       return PRE_EXPR_NAME (e1) == PRE_EXPR_NAME (e2);
289     case NARY:
290       return vn_nary_op_eq (PRE_EXPR_NARY (e1), PRE_EXPR_NARY (e2));
291     case REFERENCE:
292       return vn_reference_eq (PRE_EXPR_REFERENCE (e1),
293 			      PRE_EXPR_REFERENCE (e2));
294     default:
295       gcc_unreachable ();
296     }
297 }
298 
299 /* Hash E.  */
300 
301 inline hashval_t
hash(const pre_expr_d * e)302 pre_expr_d::hash (const pre_expr_d *e)
303 {
304   switch (e->kind)
305     {
306     case CONSTANT:
307       return vn_hash_constant_with_type (PRE_EXPR_CONSTANT (e));
308     case NAME:
309       return SSA_NAME_VERSION (PRE_EXPR_NAME (e));
310     case NARY:
311       return PRE_EXPR_NARY (e)->hashcode;
312     case REFERENCE:
313       return PRE_EXPR_REFERENCE (e)->hashcode;
314     default:
315       gcc_unreachable ();
316     }
317 }
318 
319 /* Next global expression id number.  */
320 static unsigned int next_expression_id;
321 
322 /* Mapping from expression to id number we can use in bitmap sets.  */
323 static vec<pre_expr> expressions;
324 static hash_table<pre_expr_d> *expression_to_id;
325 static vec<unsigned> name_to_id;
326 static obstack pre_expr_obstack;
327 
328 /* Allocate an expression id for EXPR.  */
329 
330 static inline unsigned int
alloc_expression_id(pre_expr expr)331 alloc_expression_id (pre_expr expr)
332 {
333   struct pre_expr_d **slot;
334   /* Make sure we won't overflow. */
335   gcc_assert (next_expression_id + 1 > next_expression_id);
336   expr->id = next_expression_id++;
337   expressions.safe_push (expr);
338   if (expr->kind == NAME)
339     {
340       unsigned version = SSA_NAME_VERSION (PRE_EXPR_NAME (expr));
341       /* vec::safe_grow_cleared allocates no headroom.  Avoid frequent
342 	 re-allocations by using vec::reserve upfront.  */
343       unsigned old_len = name_to_id.length ();
344       name_to_id.reserve (num_ssa_names - old_len);
345       name_to_id.quick_grow_cleared (num_ssa_names);
346       gcc_assert (name_to_id[version] == 0);
347       name_to_id[version] = expr->id;
348     }
349   else
350     {
351       slot = expression_to_id->find_slot (expr, INSERT);
352       gcc_assert (!*slot);
353       *slot = expr;
354     }
355   return next_expression_id - 1;
356 }
357 
358 /* Return the expression id for tree EXPR.  */
359 
360 static inline unsigned int
get_expression_id(const pre_expr expr)361 get_expression_id (const pre_expr expr)
362 {
363   return expr->id;
364 }
365 
366 static inline unsigned int
lookup_expression_id(const pre_expr expr)367 lookup_expression_id (const pre_expr expr)
368 {
369   struct pre_expr_d **slot;
370 
371   if (expr->kind == NAME)
372     {
373       unsigned version = SSA_NAME_VERSION (PRE_EXPR_NAME (expr));
374       if (name_to_id.length () <= version)
375 	return 0;
376       return name_to_id[version];
377     }
378   else
379     {
380       slot = expression_to_id->find_slot (expr, NO_INSERT);
381       if (!slot)
382 	return 0;
383       return ((pre_expr)*slot)->id;
384     }
385 }
386 
387 /* Return the existing expression id for EXPR, or create one if one
388    does not exist yet.  */
389 
390 static inline unsigned int
get_or_alloc_expression_id(pre_expr expr)391 get_or_alloc_expression_id (pre_expr expr)
392 {
393   unsigned int id = lookup_expression_id (expr);
394   if (id == 0)
395     return alloc_expression_id (expr);
396   return expr->id = id;
397 }
398 
399 /* Return the expression that has expression id ID */
400 
401 static inline pre_expr
expression_for_id(unsigned int id)402 expression_for_id (unsigned int id)
403 {
404   return expressions[id];
405 }
406 
407 static object_allocator<pre_expr_d> pre_expr_pool ("pre_expr nodes");
408 
409 /* Given an SSA_NAME NAME, get or create a pre_expr to represent it.  */
410 
411 static pre_expr
get_or_alloc_expr_for_name(tree name)412 get_or_alloc_expr_for_name (tree name)
413 {
414   struct pre_expr_d expr;
415   pre_expr result;
416   unsigned int result_id;
417 
418   expr.kind = NAME;
419   expr.id = 0;
420   PRE_EXPR_NAME (&expr) = name;
421   result_id = lookup_expression_id (&expr);
422   if (result_id != 0)
423     return expression_for_id (result_id);
424 
425   result = pre_expr_pool.allocate ();
426   result->kind = NAME;
427   result->loc = UNKNOWN_LOCATION;
428   result->value_id = VN_INFO (name)->value_id;
429   PRE_EXPR_NAME (result) = name;
430   alloc_expression_id (result);
431   return result;
432 }
433 
434 /* Given an NARY, get or create a pre_expr to represent it.  Assign
435    VALUE_ID to it or allocate a new value-id if it is zero.  Record
436    LOC as the original location of the expression.  */
437 
438 static pre_expr
get_or_alloc_expr_for_nary(vn_nary_op_t nary,unsigned value_id,location_t loc=UNKNOWN_LOCATION)439 get_or_alloc_expr_for_nary (vn_nary_op_t nary, unsigned value_id,
440 			    location_t loc = UNKNOWN_LOCATION)
441 {
442   struct pre_expr_d expr;
443   pre_expr result;
444   unsigned int result_id;
445 
446   gcc_assert (value_id == 0 || !value_id_constant_p (value_id));
447 
448   expr.kind = NARY;
449   expr.id = 0;
450   nary->hashcode = vn_nary_op_compute_hash (nary);
451   PRE_EXPR_NARY (&expr) = nary;
452   result_id = lookup_expression_id (&expr);
453   if (result_id != 0)
454     return expression_for_id (result_id);
455 
456   result = pre_expr_pool.allocate ();
457   result->kind = NARY;
458   result->loc = loc;
459   result->value_id = value_id ? value_id : get_next_value_id ();
460   PRE_EXPR_NARY (result)
461     = alloc_vn_nary_op_noinit (nary->length, &pre_expr_obstack);
462   memcpy (PRE_EXPR_NARY (result), nary, sizeof_vn_nary_op (nary->length));
463   alloc_expression_id (result);
464   return result;
465 }
466 
467 /* Given an REFERENCE, get or create a pre_expr to represent it.  */
468 
469 static pre_expr
get_or_alloc_expr_for_reference(vn_reference_t reference,location_t loc=UNKNOWN_LOCATION)470 get_or_alloc_expr_for_reference (vn_reference_t reference,
471 				 location_t loc = UNKNOWN_LOCATION)
472 {
473   struct pre_expr_d expr;
474   pre_expr result;
475   unsigned int result_id;
476 
477   expr.kind = REFERENCE;
478   expr.id = 0;
479   PRE_EXPR_REFERENCE (&expr) = reference;
480   result_id = lookup_expression_id (&expr);
481   if (result_id != 0)
482     return expression_for_id (result_id);
483 
484   result = pre_expr_pool.allocate ();
485   result->kind = REFERENCE;
486   result->loc = loc;
487   result->value_id = reference->value_id;
488   PRE_EXPR_REFERENCE (result) = reference;
489   alloc_expression_id (result);
490   return result;
491 }
492 
493 
494 /* An unordered bitmap set.  One bitmap tracks values, the other,
495    expressions.  */
496 typedef class bitmap_set
497 {
498 public:
499   bitmap_head expressions;
500   bitmap_head values;
501 } *bitmap_set_t;
502 
503 #define FOR_EACH_EXPR_ID_IN_SET(set, id, bi)		\
504   EXECUTE_IF_SET_IN_BITMAP (&(set)->expressions, 0, (id), (bi))
505 
506 #define FOR_EACH_VALUE_ID_IN_SET(set, id, bi)		\
507   EXECUTE_IF_SET_IN_BITMAP (&(set)->values, 0, (id), (bi))
508 
509 /* Mapping from value id to expressions with that value_id.  */
510 static vec<bitmap> value_expressions;
511 /* We just record a single expression for each constant value,
512    one of kind CONSTANT.  */
513 static vec<pre_expr> constant_value_expressions;
514 
515 
516 /* This structure is used to keep track of statistics on what
517    optimization PRE was able to perform.  */
518 static struct
519 {
520   /* The number of new expressions/temporaries generated by PRE.  */
521   int insertions;
522 
523   /* The number of inserts found due to partial anticipation  */
524   int pa_insert;
525 
526   /* The number of inserts made for code hoisting.  */
527   int hoist_insert;
528 
529   /* The number of new PHI nodes added by PRE.  */
530   int phis;
531 } pre_stats;
532 
533 static bool do_partial_partial;
534 static pre_expr bitmap_find_leader (bitmap_set_t, unsigned int);
535 static void bitmap_value_insert_into_set (bitmap_set_t, pre_expr);
536 static bool bitmap_value_replace_in_set (bitmap_set_t, pre_expr);
537 static void bitmap_set_copy (bitmap_set_t, bitmap_set_t);
538 static bool bitmap_set_contains_value (bitmap_set_t, unsigned int);
539 static void bitmap_insert_into_set (bitmap_set_t, pre_expr);
540 static bitmap_set_t bitmap_set_new (void);
541 static tree create_expression_by_pieces (basic_block, pre_expr, gimple_seq *,
542 					 tree);
543 static tree find_or_generate_expression (basic_block, tree, gimple_seq *);
544 static unsigned int get_expr_value_id (pre_expr);
545 
546 /* We can add and remove elements and entries to and from sets
547    and hash tables, so we use alloc pools for them.  */
548 
549 static object_allocator<bitmap_set> bitmap_set_pool ("Bitmap sets");
550 static bitmap_obstack grand_bitmap_obstack;
551 
552 /* A three tuple {e, pred, v} used to cache phi translations in the
553    phi_translate_table.  */
554 
555 typedef struct expr_pred_trans_d : public typed_noop_remove <expr_pred_trans_d>
556 {
557   typedef expr_pred_trans_d value_type;
558   typedef expr_pred_trans_d compare_type;
559 
560   /* The expression ID.  */
561   unsigned e;
562 
563   /* The value expression ID that resulted from the translation.  */
564   unsigned v;
565 
566   /* hash_table support.  */
567   static inline void mark_empty (expr_pred_trans_d &);
568   static inline bool is_empty (const expr_pred_trans_d &);
569   static inline void mark_deleted (expr_pred_trans_d &);
570   static inline bool is_deleted (const expr_pred_trans_d &);
571   static const bool empty_zero_p = true;
572   static inline hashval_t hash (const expr_pred_trans_d &);
573   static inline int equal (const expr_pred_trans_d &, const expr_pred_trans_d &);
574 } *expr_pred_trans_t;
575 typedef const struct expr_pred_trans_d *const_expr_pred_trans_t;
576 
577 inline bool
is_empty(const expr_pred_trans_d & e)578 expr_pred_trans_d::is_empty (const expr_pred_trans_d &e)
579 {
580   return e.e == 0;
581 }
582 
583 inline bool
is_deleted(const expr_pred_trans_d & e)584 expr_pred_trans_d::is_deleted (const expr_pred_trans_d &e)
585 {
586   return e.e == -1u;
587 }
588 
589 inline void
mark_empty(expr_pred_trans_d & e)590 expr_pred_trans_d::mark_empty (expr_pred_trans_d &e)
591 {
592   e.e = 0;
593 }
594 
595 inline void
mark_deleted(expr_pred_trans_d & e)596 expr_pred_trans_d::mark_deleted (expr_pred_trans_d &e)
597 {
598   e.e = -1u;
599 }
600 
601 inline hashval_t
hash(const expr_pred_trans_d & e)602 expr_pred_trans_d::hash (const expr_pred_trans_d &e)
603 {
604   return e.e;
605 }
606 
607 inline int
equal(const expr_pred_trans_d & ve1,const expr_pred_trans_d & ve2)608 expr_pred_trans_d::equal (const expr_pred_trans_d &ve1,
609 			  const expr_pred_trans_d &ve2)
610 {
611   return ve1.e == ve2.e;
612 }
613 
614 /* Sets that we need to keep track of.  */
615 typedef struct bb_bitmap_sets
616 {
617   /* The EXP_GEN set, which represents expressions/values generated in
618      a basic block.  */
619   bitmap_set_t exp_gen;
620 
621   /* The PHI_GEN set, which represents PHI results generated in a
622      basic block.  */
623   bitmap_set_t phi_gen;
624 
625   /* The TMP_GEN set, which represents results/temporaries generated
626      in a basic block. IE the LHS of an expression.  */
627   bitmap_set_t tmp_gen;
628 
629   /* The AVAIL_OUT set, which represents which values are available in
630      a given basic block.  */
631   bitmap_set_t avail_out;
632 
633   /* The ANTIC_IN set, which represents which values are anticipatable
634      in a given basic block.  */
635   bitmap_set_t antic_in;
636 
637   /* The PA_IN set, which represents which values are
638      partially anticipatable in a given basic block.  */
639   bitmap_set_t pa_in;
640 
641   /* The NEW_SETS set, which is used during insertion to augment the
642      AVAIL_OUT set of blocks with the new insertions performed during
643      the current iteration.  */
644   bitmap_set_t new_sets;
645 
646   /* A cache for value_dies_in_block_x.  */
647   bitmap expr_dies;
648 
649   /* The live virtual operand on successor edges.  */
650   tree vop_on_exit;
651 
652   /* PHI translate cache for the single successor edge.  */
653   hash_table<expr_pred_trans_d> *phi_translate_table;
654 
655   /* True if we have visited this block during ANTIC calculation.  */
656   unsigned int visited : 1;
657 
658   /* True when the block contains a call that might not return.  */
659   unsigned int contains_may_not_return_call : 1;
660 } *bb_value_sets_t;
661 
662 #define EXP_GEN(BB)	((bb_value_sets_t) ((BB)->aux))->exp_gen
663 #define PHI_GEN(BB)	((bb_value_sets_t) ((BB)->aux))->phi_gen
664 #define TMP_GEN(BB)	((bb_value_sets_t) ((BB)->aux))->tmp_gen
665 #define AVAIL_OUT(BB)	((bb_value_sets_t) ((BB)->aux))->avail_out
666 #define ANTIC_IN(BB)	((bb_value_sets_t) ((BB)->aux))->antic_in
667 #define PA_IN(BB)	((bb_value_sets_t) ((BB)->aux))->pa_in
668 #define NEW_SETS(BB)	((bb_value_sets_t) ((BB)->aux))->new_sets
669 #define EXPR_DIES(BB)	((bb_value_sets_t) ((BB)->aux))->expr_dies
670 #define PHI_TRANS_TABLE(BB) ((bb_value_sets_t) ((BB)->aux))->phi_translate_table
671 #define BB_VISITED(BB)	((bb_value_sets_t) ((BB)->aux))->visited
672 #define BB_MAY_NOTRETURN(BB) ((bb_value_sets_t) ((BB)->aux))->contains_may_not_return_call
673 #define BB_LIVE_VOP_ON_EXIT(BB) ((bb_value_sets_t) ((BB)->aux))->vop_on_exit
674 
675 
676 /* Add the tuple mapping from {expression E, basic block PRED} to
677    the phi translation table and return whether it pre-existed.  */
678 
679 static inline bool
phi_trans_add(expr_pred_trans_t * entry,pre_expr e,basic_block pred)680 phi_trans_add (expr_pred_trans_t *entry, pre_expr e, basic_block pred)
681 {
682   if (!PHI_TRANS_TABLE (pred))
683     PHI_TRANS_TABLE (pred) = new hash_table<expr_pred_trans_d> (11);
684 
685   expr_pred_trans_t slot;
686   expr_pred_trans_d tem;
687   unsigned id = get_expression_id (e);
688   tem.e = id;
689   slot = PHI_TRANS_TABLE (pred)->find_slot_with_hash (tem, id, INSERT);
690   if (slot->e)
691     {
692       *entry = slot;
693       return true;
694     }
695 
696   *entry = slot;
697   slot->e = id;
698   return false;
699 }
700 
701 
702 /* Add expression E to the expression set of value id V.  */
703 
704 static void
add_to_value(unsigned int v,pre_expr e)705 add_to_value (unsigned int v, pre_expr e)
706 {
707   gcc_checking_assert (get_expr_value_id (e) == v);
708 
709   if (value_id_constant_p (v))
710     {
711       if (e->kind != CONSTANT)
712 	return;
713 
714       if (-v >= constant_value_expressions.length ())
715 	constant_value_expressions.safe_grow_cleared (-v + 1);
716 
717       pre_expr leader = constant_value_expressions[-v];
718       if (!leader)
719 	constant_value_expressions[-v] = e;
720     }
721   else
722     {
723       if (v >= value_expressions.length ())
724 	value_expressions.safe_grow_cleared (v + 1);
725 
726       bitmap set = value_expressions[v];
727       if (!set)
728 	{
729 	  set = BITMAP_ALLOC (&grand_bitmap_obstack);
730 	  value_expressions[v] = set;
731 	}
732       bitmap_set_bit (set, get_or_alloc_expression_id (e));
733     }
734 }
735 
736 /* Create a new bitmap set and return it.  */
737 
738 static bitmap_set_t
bitmap_set_new(void)739 bitmap_set_new (void)
740 {
741   bitmap_set_t ret = bitmap_set_pool.allocate ();
742   bitmap_initialize (&ret->expressions, &grand_bitmap_obstack);
743   bitmap_initialize (&ret->values, &grand_bitmap_obstack);
744   return ret;
745 }
746 
747 /* Return the value id for a PRE expression EXPR.  */
748 
749 static unsigned int
get_expr_value_id(pre_expr expr)750 get_expr_value_id (pre_expr expr)
751 {
752   /* ???  We cannot assert that expr has a value-id (it can be 0), because
753      we assign value-ids only to expressions that have a result
754      in set_hashtable_value_ids.  */
755   return expr->value_id;
756 }
757 
758 /* Return a VN valnum (SSA name or constant) for the PRE value-id VAL.  */
759 
760 static tree
vn_valnum_from_value_id(unsigned int val)761 vn_valnum_from_value_id (unsigned int val)
762 {
763   if (value_id_constant_p (val))
764     {
765       pre_expr vexpr = constant_value_expressions[-val];
766       if (vexpr)
767 	return PRE_EXPR_CONSTANT (vexpr);
768       return NULL_TREE;
769     }
770 
771   bitmap exprset = value_expressions[val];
772   bitmap_iterator bi;
773   unsigned int i;
774   EXECUTE_IF_SET_IN_BITMAP (exprset, 0, i, bi)
775     {
776       pre_expr vexpr = expression_for_id (i);
777       if (vexpr->kind == NAME)
778 	return VN_INFO (PRE_EXPR_NAME (vexpr))->valnum;
779     }
780   return NULL_TREE;
781 }
782 
783 /* Insert an expression EXPR into a bitmapped set.  */
784 
785 static void
bitmap_insert_into_set(bitmap_set_t set,pre_expr expr)786 bitmap_insert_into_set (bitmap_set_t set, pre_expr expr)
787 {
788   unsigned int val = get_expr_value_id (expr);
789   if (! value_id_constant_p (val))
790     {
791       /* Note this is the only function causing multiple expressions
792          for the same value to appear in a set.  This is needed for
793 	 TMP_GEN, PHI_GEN and NEW_SETs.  */
794       bitmap_set_bit (&set->values, val);
795       bitmap_set_bit (&set->expressions, get_or_alloc_expression_id (expr));
796     }
797 }
798 
799 /* Copy a bitmapped set ORIG, into bitmapped set DEST.  */
800 
801 static void
bitmap_set_copy(bitmap_set_t dest,bitmap_set_t orig)802 bitmap_set_copy (bitmap_set_t dest, bitmap_set_t orig)
803 {
804   bitmap_copy (&dest->expressions, &orig->expressions);
805   bitmap_copy (&dest->values, &orig->values);
806 }
807 
808 
809 /* Free memory used up by SET.  */
810 static void
bitmap_set_free(bitmap_set_t set)811 bitmap_set_free (bitmap_set_t set)
812 {
813   bitmap_clear (&set->expressions);
814   bitmap_clear (&set->values);
815 }
816 
817 static void
818 pre_expr_DFS (pre_expr expr, bitmap_set_t set, bitmap val_visited,
819 	      vec<pre_expr> &post);
820 
821 /* DFS walk leaders of VAL to their operands with leaders in SET, collecting
822    expressions in SET in postorder into POST.  */
823 
824 static void
pre_expr_DFS(unsigned val,bitmap_set_t set,bitmap val_visited,vec<pre_expr> & post)825 pre_expr_DFS (unsigned val, bitmap_set_t set, bitmap val_visited,
826 	      vec<pre_expr> &post)
827 {
828   unsigned int i;
829   bitmap_iterator bi;
830 
831   /* Iterate over all leaders and DFS recurse.  Borrowed from
832      bitmap_find_leader.  */
833   bitmap exprset = value_expressions[val];
834   if (!exprset->first->next)
835     {
836       EXECUTE_IF_SET_IN_BITMAP (exprset, 0, i, bi)
837 	if (bitmap_bit_p (&set->expressions, i))
838 	  pre_expr_DFS (expression_for_id (i), set, val_visited, post);
839       return;
840     }
841 
842   EXECUTE_IF_AND_IN_BITMAP (exprset, &set->expressions, 0, i, bi)
843     pre_expr_DFS (expression_for_id (i), set, val_visited, post);
844 }
845 
846 /* DFS walk EXPR to its operands with leaders in SET, collecting
847    expressions in SET in postorder into POST.  */
848 
849 static void
pre_expr_DFS(pre_expr expr,bitmap_set_t set,bitmap val_visited,vec<pre_expr> & post)850 pre_expr_DFS (pre_expr expr, bitmap_set_t set, bitmap val_visited,
851 	      vec<pre_expr> &post)
852 {
853   switch (expr->kind)
854     {
855     case NARY:
856       {
857 	vn_nary_op_t nary = PRE_EXPR_NARY (expr);
858 	for (unsigned i = 0; i < nary->length; i++)
859 	  {
860 	    if (TREE_CODE (nary->op[i]) != SSA_NAME)
861 	      continue;
862 	    unsigned int op_val_id = VN_INFO (nary->op[i])->value_id;
863 	    /* If we already found a leader for the value we've
864 	       recursed already.  Avoid the costly bitmap_find_leader.  */
865 	    if (bitmap_bit_p (&set->values, op_val_id)
866 		&& bitmap_set_bit (val_visited, op_val_id))
867 	      pre_expr_DFS (op_val_id, set, val_visited, post);
868 	  }
869 	break;
870       }
871     case REFERENCE:
872       {
873 	vn_reference_t ref = PRE_EXPR_REFERENCE (expr);
874 	vec<vn_reference_op_s> operands = ref->operands;
875 	vn_reference_op_t operand;
876 	for (unsigned i = 0; operands.iterate (i, &operand); i++)
877 	  {
878 	    tree op[3];
879 	    op[0] = operand->op0;
880 	    op[1] = operand->op1;
881 	    op[2] = operand->op2;
882 	    for (unsigned n = 0; n < 3; ++n)
883 	      {
884 		if (!op[n] || TREE_CODE (op[n]) != SSA_NAME)
885 		  continue;
886 		unsigned op_val_id = VN_INFO (op[n])->value_id;
887 		if (bitmap_bit_p (&set->values, op_val_id)
888 		    && bitmap_set_bit (val_visited, op_val_id))
889 		  pre_expr_DFS (op_val_id, set, val_visited, post);
890 	      }
891 	  }
892 	break;
893       }
894     default:;
895     }
896   post.quick_push (expr);
897 }
898 
899 /* Generate an topological-ordered array of bitmap set SET.  */
900 
901 static vec<pre_expr>
sorted_array_from_bitmap_set(bitmap_set_t set)902 sorted_array_from_bitmap_set (bitmap_set_t set)
903 {
904   unsigned int i;
905   bitmap_iterator bi;
906   vec<pre_expr> result;
907 
908   /* Pre-allocate enough space for the array.  */
909   result.create (bitmap_count_bits (&set->expressions));
910 
911   auto_bitmap val_visited (&grand_bitmap_obstack);
912   bitmap_tree_view (val_visited);
913   FOR_EACH_VALUE_ID_IN_SET (set, i, bi)
914     if (bitmap_set_bit (val_visited, i))
915       pre_expr_DFS (i, set, val_visited, result);
916 
917   return result;
918 }
919 
920 /* Subtract all expressions contained in ORIG from DEST.  */
921 
922 static bitmap_set_t
bitmap_set_subtract_expressions(bitmap_set_t dest,bitmap_set_t orig)923 bitmap_set_subtract_expressions (bitmap_set_t dest, bitmap_set_t orig)
924 {
925   bitmap_set_t result = bitmap_set_new ();
926   bitmap_iterator bi;
927   unsigned int i;
928 
929   bitmap_and_compl (&result->expressions, &dest->expressions,
930 		    &orig->expressions);
931 
932   FOR_EACH_EXPR_ID_IN_SET (result, i, bi)
933     {
934       pre_expr expr = expression_for_id (i);
935       unsigned int value_id = get_expr_value_id (expr);
936       bitmap_set_bit (&result->values, value_id);
937     }
938 
939   return result;
940 }
941 
942 /* Subtract all values in bitmap set B from bitmap set A.  */
943 
944 static void
bitmap_set_subtract_values(bitmap_set_t a,bitmap_set_t b)945 bitmap_set_subtract_values (bitmap_set_t a, bitmap_set_t b)
946 {
947   unsigned int i;
948   bitmap_iterator bi;
949   unsigned to_remove = -1U;
950   bitmap_and_compl_into (&a->values, &b->values);
951   FOR_EACH_EXPR_ID_IN_SET (a, i, bi)
952     {
953       if (to_remove != -1U)
954 	{
955 	  bitmap_clear_bit (&a->expressions, to_remove);
956 	  to_remove = -1U;
957 	}
958       pre_expr expr = expression_for_id (i);
959       if (! bitmap_bit_p (&a->values, get_expr_value_id (expr)))
960 	to_remove = i;
961     }
962   if (to_remove != -1U)
963     bitmap_clear_bit (&a->expressions, to_remove);
964 }
965 
966 
967 /* Return true if bitmapped set SET contains the value VALUE_ID.  */
968 
969 static bool
bitmap_set_contains_value(bitmap_set_t set,unsigned int value_id)970 bitmap_set_contains_value (bitmap_set_t set, unsigned int value_id)
971 {
972   if (value_id_constant_p (value_id))
973     return true;
974 
975   return bitmap_bit_p (&set->values, value_id);
976 }
977 
978 /* Return true if two bitmap sets are equal.  */
979 
980 static bool
bitmap_set_equal(bitmap_set_t a,bitmap_set_t b)981 bitmap_set_equal (bitmap_set_t a, bitmap_set_t b)
982 {
983   return bitmap_equal_p (&a->values, &b->values);
984 }
985 
986 /* Replace an instance of EXPR's VALUE with EXPR in SET if it exists,
987    and add it otherwise.  Return true if any changes were made.  */
988 
989 static bool
bitmap_value_replace_in_set(bitmap_set_t set,pre_expr expr)990 bitmap_value_replace_in_set (bitmap_set_t set, pre_expr expr)
991 {
992   unsigned int val = get_expr_value_id (expr);
993   if (value_id_constant_p (val))
994     return false;
995 
996   if (bitmap_set_contains_value (set, val))
997     {
998       /* The number of expressions having a given value is usually
999 	 significantly less than the total number of expressions in SET.
1000 	 Thus, rather than check, for each expression in SET, whether it
1001 	 has the value LOOKFOR, we walk the reverse mapping that tells us
1002 	 what expressions have a given value, and see if any of those
1003 	 expressions are in our set.  For large testcases, this is about
1004 	 5-10x faster than walking the bitmap.  If this is somehow a
1005 	 significant lose for some cases, we can choose which set to walk
1006 	 based on the set size.  */
1007       unsigned int i;
1008       bitmap_iterator bi;
1009       bitmap exprset = value_expressions[val];
1010       EXECUTE_IF_SET_IN_BITMAP (exprset, 0, i, bi)
1011 	{
1012 	  if (bitmap_clear_bit (&set->expressions, i))
1013 	    {
1014 	      bitmap_set_bit (&set->expressions, get_expression_id (expr));
1015 	      return i != get_expression_id (expr);
1016 	    }
1017 	}
1018       gcc_unreachable ();
1019     }
1020 
1021   bitmap_insert_into_set (set, expr);
1022   return true;
1023 }
1024 
1025 /* Insert EXPR into SET if EXPR's value is not already present in
1026    SET.  */
1027 
1028 static void
bitmap_value_insert_into_set(bitmap_set_t set,pre_expr expr)1029 bitmap_value_insert_into_set (bitmap_set_t set, pre_expr expr)
1030 {
1031   unsigned int val = get_expr_value_id (expr);
1032 
1033   gcc_checking_assert (expr->id == get_or_alloc_expression_id (expr));
1034 
1035   /* Constant values are always considered to be part of the set.  */
1036   if (value_id_constant_p (val))
1037     return;
1038 
1039   /* If the value membership changed, add the expression.  */
1040   if (bitmap_set_bit (&set->values, val))
1041     bitmap_set_bit (&set->expressions, expr->id);
1042 }
1043 
1044 /* Print out EXPR to outfile.  */
1045 
1046 static void
print_pre_expr(FILE * outfile,const pre_expr expr)1047 print_pre_expr (FILE *outfile, const pre_expr expr)
1048 {
1049   if (! expr)
1050     {
1051       fprintf (outfile, "NULL");
1052       return;
1053     }
1054   switch (expr->kind)
1055     {
1056     case CONSTANT:
1057       print_generic_expr (outfile, PRE_EXPR_CONSTANT (expr));
1058       break;
1059     case NAME:
1060       print_generic_expr (outfile, PRE_EXPR_NAME (expr));
1061       break;
1062     case NARY:
1063       {
1064 	unsigned int i;
1065 	vn_nary_op_t nary = PRE_EXPR_NARY (expr);
1066 	fprintf (outfile, "{%s,", get_tree_code_name (nary->opcode));
1067 	for (i = 0; i < nary->length; i++)
1068 	  {
1069 	    print_generic_expr (outfile, nary->op[i]);
1070 	    if (i != (unsigned) nary->length - 1)
1071 	      fprintf (outfile, ",");
1072 	  }
1073 	fprintf (outfile, "}");
1074       }
1075       break;
1076 
1077     case REFERENCE:
1078       {
1079 	vn_reference_t ref = PRE_EXPR_REFERENCE (expr);
1080 	print_vn_reference_ops (outfile, ref->operands);
1081 	if (ref->vuse)
1082 	  {
1083 	    fprintf (outfile, "@");
1084 	    print_generic_expr (outfile, ref->vuse);
1085 	  }
1086       }
1087       break;
1088     }
1089 }
1090 void debug_pre_expr (pre_expr);
1091 
1092 /* Like print_pre_expr but always prints to stderr.  */
1093 DEBUG_FUNCTION void
debug_pre_expr(pre_expr e)1094 debug_pre_expr (pre_expr e)
1095 {
1096   print_pre_expr (stderr, e);
1097   fprintf (stderr, "\n");
1098 }
1099 
1100 /* Print out SET to OUTFILE.  */
1101 
1102 static void
print_bitmap_set(FILE * outfile,bitmap_set_t set,const char * setname,int blockindex)1103 print_bitmap_set (FILE *outfile, bitmap_set_t set,
1104 		  const char *setname, int blockindex)
1105 {
1106   fprintf (outfile, "%s[%d] := { ", setname, blockindex);
1107   if (set)
1108     {
1109       bool first = true;
1110       unsigned i;
1111       bitmap_iterator bi;
1112 
1113       FOR_EACH_EXPR_ID_IN_SET (set, i, bi)
1114 	{
1115 	  const pre_expr expr = expression_for_id (i);
1116 
1117 	  if (!first)
1118 	    fprintf (outfile, ", ");
1119 	  first = false;
1120 	  print_pre_expr (outfile, expr);
1121 
1122 	  fprintf (outfile, " (%04d)", get_expr_value_id (expr));
1123 	}
1124     }
1125   fprintf (outfile, " }\n");
1126 }
1127 
1128 void debug_bitmap_set (bitmap_set_t);
1129 
1130 DEBUG_FUNCTION void
debug_bitmap_set(bitmap_set_t set)1131 debug_bitmap_set (bitmap_set_t set)
1132 {
1133   print_bitmap_set (stderr, set, "debug", 0);
1134 }
1135 
1136 void debug_bitmap_sets_for (basic_block);
1137 
1138 DEBUG_FUNCTION void
debug_bitmap_sets_for(basic_block bb)1139 debug_bitmap_sets_for (basic_block bb)
1140 {
1141   print_bitmap_set (stderr, AVAIL_OUT (bb), "avail_out", bb->index);
1142   print_bitmap_set (stderr, EXP_GEN (bb), "exp_gen", bb->index);
1143   print_bitmap_set (stderr, PHI_GEN (bb), "phi_gen", bb->index);
1144   print_bitmap_set (stderr, TMP_GEN (bb), "tmp_gen", bb->index);
1145   print_bitmap_set (stderr, ANTIC_IN (bb), "antic_in", bb->index);
1146   if (do_partial_partial)
1147     print_bitmap_set (stderr, PA_IN (bb), "pa_in", bb->index);
1148   print_bitmap_set (stderr, NEW_SETS (bb), "new_sets", bb->index);
1149 }
1150 
1151 /* Print out the expressions that have VAL to OUTFILE.  */
1152 
1153 static void
print_value_expressions(FILE * outfile,unsigned int val)1154 print_value_expressions (FILE *outfile, unsigned int val)
1155 {
1156   bitmap set = value_expressions[val];
1157   if (set)
1158     {
1159       bitmap_set x;
1160       char s[10];
1161       sprintf (s, "%04d", val);
1162       x.expressions = *set;
1163       print_bitmap_set (outfile, &x, s, 0);
1164     }
1165 }
1166 
1167 
1168 DEBUG_FUNCTION void
debug_value_expressions(unsigned int val)1169 debug_value_expressions (unsigned int val)
1170 {
1171   print_value_expressions (stderr, val);
1172 }
1173 
1174 /* Given a CONSTANT, allocate a new CONSTANT type PRE_EXPR to
1175    represent it.  */
1176 
1177 static pre_expr
get_or_alloc_expr_for_constant(tree constant)1178 get_or_alloc_expr_for_constant (tree constant)
1179 {
1180   unsigned int result_id;
1181   struct pre_expr_d expr;
1182   pre_expr newexpr;
1183 
1184   expr.kind = CONSTANT;
1185   PRE_EXPR_CONSTANT (&expr) = constant;
1186   result_id = lookup_expression_id (&expr);
1187   if (result_id != 0)
1188     return expression_for_id (result_id);
1189 
1190   newexpr = pre_expr_pool.allocate ();
1191   newexpr->kind = CONSTANT;
1192   newexpr->loc = UNKNOWN_LOCATION;
1193   PRE_EXPR_CONSTANT (newexpr) = constant;
1194   alloc_expression_id (newexpr);
1195   newexpr->value_id = get_or_alloc_constant_value_id (constant);
1196   add_to_value (newexpr->value_id, newexpr);
1197   return newexpr;
1198 }
1199 
1200 /* Return the folded version of T if T, when folded, is a gimple
1201    min_invariant or an SSA name.  Otherwise, return T.  */
1202 
1203 static pre_expr
fully_constant_expression(pre_expr e)1204 fully_constant_expression (pre_expr e)
1205 {
1206   switch (e->kind)
1207     {
1208     case CONSTANT:
1209       return e;
1210     case NARY:
1211       {
1212 	vn_nary_op_t nary = PRE_EXPR_NARY (e);
1213 	tree res = vn_nary_simplify (nary);
1214 	if (!res)
1215 	  return e;
1216 	if (is_gimple_min_invariant (res))
1217 	  return get_or_alloc_expr_for_constant (res);
1218 	if (TREE_CODE (res) == SSA_NAME)
1219 	  return get_or_alloc_expr_for_name (res);
1220 	return e;
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 }
1234 
1235 /* Translate the VUSE backwards through phi nodes in E->dest, so that
1236    it has the value it would have in E->src.  Set *SAME_VALID to true
1237    in case the new vuse doesn't change the value id of the OPERANDS.  */
1238 
1239 static tree
translate_vuse_through_block(vec<vn_reference_op_s> operands,alias_set_type set,alias_set_type base_set,tree type,tree vuse,edge e,bool * same_valid)1240 translate_vuse_through_block (vec<vn_reference_op_s> operands,
1241 			      alias_set_type set, alias_set_type base_set,
1242 			      tree type, tree vuse, edge e, bool *same_valid)
1243 {
1244   basic_block phiblock = e->dest;
1245   gimple *phi = SSA_NAME_DEF_STMT (vuse);
1246   ao_ref ref;
1247 
1248   if (same_valid)
1249     *same_valid = true;
1250 
1251   /* If value-numbering provided a memory state for this
1252      that dominates PHIBLOCK we can just use that.  */
1253   if (gimple_nop_p (phi)
1254       || (gimple_bb (phi) != phiblock
1255 	  && dominated_by_p (CDI_DOMINATORS, phiblock, gimple_bb (phi))))
1256     return vuse;
1257 
1258   /* We have pruned expressions that are killed in PHIBLOCK via
1259      prune_clobbered_mems but we have not rewritten the VUSE to the one
1260      live at the start of the block.  If there is no virtual PHI to translate
1261      through return the VUSE live at entry.  Otherwise the VUSE to translate
1262      is the def of the virtual PHI node.  */
1263   phi = get_virtual_phi (phiblock);
1264   if (!phi)
1265     return BB_LIVE_VOP_ON_EXIT
1266 	     (get_immediate_dominator (CDI_DOMINATORS, phiblock));
1267 
1268   if (same_valid
1269       && ao_ref_init_from_vn_reference (&ref, set, base_set, type, operands))
1270     {
1271       bitmap visited = NULL;
1272       /* Try to find a vuse that dominates this phi node by skipping
1273 	 non-clobbering statements.  */
1274       unsigned int cnt = param_sccvn_max_alias_queries_per_access;
1275       vuse = get_continuation_for_phi (phi, &ref, true,
1276 				       cnt, &visited, false, NULL, NULL);
1277       if (visited)
1278 	BITMAP_FREE (visited);
1279     }
1280   else
1281     vuse = NULL_TREE;
1282   /* If we didn't find any, the value ID can't stay the same.  */
1283   if (!vuse && same_valid)
1284     *same_valid = false;
1285 
1286   /* ??? We would like to return vuse here as this is the canonical
1287      upmost vdef that this reference is associated with.  But during
1288      insertion of the references into the hash tables we only ever
1289      directly insert with their direct gimple_vuse, hence returning
1290      something else would make us not find the other expression.  */
1291   return PHI_ARG_DEF (phi, e->dest_idx);
1292 }
1293 
1294 /* Like bitmap_find_leader, but checks for the value existing in SET1 *or*
1295    SET2 *or* SET3.  This is used to avoid making a set consisting of the union
1296    of PA_IN and ANTIC_IN during insert and phi-translation.  */
1297 
1298 static inline pre_expr
find_leader_in_sets(unsigned int val,bitmap_set_t set1,bitmap_set_t set2,bitmap_set_t set3=NULL)1299 find_leader_in_sets (unsigned int val, bitmap_set_t set1, bitmap_set_t set2,
1300 		     bitmap_set_t set3 = NULL)
1301 {
1302   pre_expr result = NULL;
1303 
1304   if (set1)
1305     result = bitmap_find_leader (set1, val);
1306   if (!result && set2)
1307     result = bitmap_find_leader (set2, val);
1308   if (!result && set3)
1309     result = bitmap_find_leader (set3, val);
1310   return result;
1311 }
1312 
1313 /* Get the tree type for our PRE expression e.  */
1314 
1315 static tree
get_expr_type(const pre_expr e)1316 get_expr_type (const pre_expr e)
1317 {
1318   switch (e->kind)
1319     {
1320     case NAME:
1321       return TREE_TYPE (PRE_EXPR_NAME (e));
1322     case CONSTANT:
1323       return TREE_TYPE (PRE_EXPR_CONSTANT (e));
1324     case REFERENCE:
1325       return PRE_EXPR_REFERENCE (e)->type;
1326     case NARY:
1327       return PRE_EXPR_NARY (e)->type;
1328     }
1329   gcc_unreachable ();
1330 }
1331 
1332 /* Get a representative SSA_NAME for a given expression that is available in B.
1333    Since all of our sub-expressions are treated as values, we require
1334    them to be SSA_NAME's for simplicity.
1335    Prior versions of GVNPRE used to use "value handles" here, so that
1336    an expression would be VH.11 + VH.10 instead of d_3 + e_6.  In
1337    either case, the operands are really values (IE we do not expect
1338    them to be usable without finding leaders).  */
1339 
1340 static tree
get_representative_for(const pre_expr e,basic_block b=NULL)1341 get_representative_for (const pre_expr e, basic_block b = NULL)
1342 {
1343   tree name, valnum = NULL_TREE;
1344   unsigned int value_id = get_expr_value_id (e);
1345 
1346   switch (e->kind)
1347     {
1348     case NAME:
1349       return PRE_EXPR_NAME (e);
1350     case CONSTANT:
1351       return PRE_EXPR_CONSTANT (e);
1352     case NARY:
1353     case REFERENCE:
1354       {
1355 	/* Go through all of the expressions representing this value
1356 	   and pick out an SSA_NAME.  */
1357 	unsigned int i;
1358 	bitmap_iterator bi;
1359 	bitmap exprs = value_expressions[value_id];
1360 	EXECUTE_IF_SET_IN_BITMAP (exprs, 0, i, bi)
1361 	  {
1362 	    pre_expr rep = expression_for_id (i);
1363 	    if (rep->kind == NAME)
1364 	      {
1365 		tree name = PRE_EXPR_NAME (rep);
1366 		valnum = VN_INFO (name)->valnum;
1367 		gimple *def = SSA_NAME_DEF_STMT (name);
1368 		/* We have to return either a new representative or one
1369 		   that can be used for expression simplification and thus
1370 		   is available in B.  */
1371 		if (! b
1372 		    || gimple_nop_p (def)
1373 		    || dominated_by_p (CDI_DOMINATORS, b, gimple_bb (def)))
1374 		  return name;
1375 	      }
1376 	    else if (rep->kind == CONSTANT)
1377 	      return PRE_EXPR_CONSTANT (rep);
1378 	  }
1379       }
1380       break;
1381     }
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, as the result of phi translation.
1386      Create one here.
1387      ???  We should be able to re-use this when we insert the statement
1388      to compute it.  */
1389   name = make_temp_ssa_name (get_expr_type (e), gimple_build_nop (), "pretmp");
1390   vn_ssa_aux_t vn_info = VN_INFO (name);
1391   vn_info->value_id = value_id;
1392   vn_info->valnum = valnum ? valnum : name;
1393   vn_info->visited = true;
1394   /* ???  For now mark this SSA name for release by VN.  */
1395   vn_info->needs_insertion = true;
1396   add_to_value (value_id, get_or_alloc_expr_for_name (name));
1397   if (dump_file && (dump_flags & TDF_DETAILS))
1398     {
1399       fprintf (dump_file, "Created SSA_NAME representative ");
1400       print_generic_expr (dump_file, name);
1401       fprintf (dump_file, " for expression:");
1402       print_pre_expr (dump_file, e);
1403       fprintf (dump_file, " (%04d)\n", value_id);
1404     }
1405 
1406   return name;
1407 }
1408 
1409 
1410 static pre_expr
1411 phi_translate (bitmap_set_t, pre_expr, bitmap_set_t, bitmap_set_t, edge);
1412 
1413 /* Translate EXPR using phis in PHIBLOCK, so that it has the values of
1414    the phis in PRED.  Return NULL if we can't find a leader for each part
1415    of the translated expression.  */
1416 
1417 static pre_expr
phi_translate_1(bitmap_set_t dest,pre_expr expr,bitmap_set_t set1,bitmap_set_t set2,edge e)1418 phi_translate_1 (bitmap_set_t dest,
1419 		 pre_expr expr, bitmap_set_t set1, bitmap_set_t set2, edge e)
1420 {
1421   basic_block pred = e->src;
1422   basic_block phiblock = e->dest;
1423   location_t expr_loc = expr->loc;
1424   switch (expr->kind)
1425     {
1426     case NARY:
1427       {
1428 	unsigned int i;
1429 	bool changed = false;
1430 	vn_nary_op_t nary = PRE_EXPR_NARY (expr);
1431 	vn_nary_op_t newnary = XALLOCAVAR (struct vn_nary_op_s,
1432 					   sizeof_vn_nary_op (nary->length));
1433 	memcpy (newnary, nary, sizeof_vn_nary_op (nary->length));
1434 
1435 	for (i = 0; i < newnary->length; i++)
1436 	  {
1437 	    if (TREE_CODE (newnary->op[i]) != SSA_NAME)
1438 	      continue;
1439 	    else
1440 	      {
1441                 pre_expr leader, result;
1442 		unsigned int op_val_id = VN_INFO (newnary->op[i])->value_id;
1443 		leader = find_leader_in_sets (op_val_id, set1, set2);
1444 		result = phi_translate (dest, leader, set1, set2, e);
1445 		if (result && result != leader)
1446 		  /* If op has a leader in the sets we translate make
1447 		     sure to use the value of the translated expression.
1448 		     We might need a new representative for that.  */
1449 		  newnary->op[i] = get_representative_for (result, pred);
1450 		else if (!result)
1451 		  return NULL;
1452 
1453 		changed |= newnary->op[i] != nary->op[i];
1454 	      }
1455 	  }
1456 	if (changed)
1457 	  {
1458 	    pre_expr constant;
1459 	    unsigned int new_val_id;
1460 
1461 	    PRE_EXPR_NARY (expr) = newnary;
1462 	    constant = fully_constant_expression (expr);
1463 	    PRE_EXPR_NARY (expr) = nary;
1464 	    if (constant != expr)
1465 	      {
1466 		/* For non-CONSTANTs we have to make sure we can eventually
1467 		   insert the expression.  Which means we need to have a
1468 		   leader for it.  */
1469 		if (constant->kind != CONSTANT)
1470 		  {
1471 		    /* Do not allow simplifications to non-constants over
1472 		       backedges as this will likely result in a loop PHI node
1473 		       to be inserted and increased register pressure.
1474 		       See PR77498 - this avoids doing predcoms work in
1475 		       a less efficient way.  */
1476 		    if (e->flags & EDGE_DFS_BACK)
1477 		      ;
1478 		    else
1479 		      {
1480 			unsigned value_id = get_expr_value_id (constant);
1481 			/* We want a leader in ANTIC_OUT or AVAIL_OUT here.
1482 			   dest has what we computed into ANTIC_OUT sofar
1483 			   so pick from that - since topological sorting
1484 			   by sorted_array_from_bitmap_set isn't perfect
1485 			   we may lose some cases here.  */
1486 			constant = find_leader_in_sets (value_id, dest,
1487 							AVAIL_OUT (pred));
1488 			if (constant)
1489 			  {
1490 			    if (dump_file && (dump_flags & TDF_DETAILS))
1491 			      {
1492 				fprintf (dump_file, "simplifying ");
1493 				print_pre_expr (dump_file, expr);
1494 				fprintf (dump_file, " translated %d -> %d to ",
1495 					 phiblock->index, pred->index);
1496 				PRE_EXPR_NARY (expr) = newnary;
1497 				print_pre_expr (dump_file, expr);
1498 				PRE_EXPR_NARY (expr) = nary;
1499 				fprintf (dump_file, " to ");
1500 				print_pre_expr (dump_file, constant);
1501 				fprintf (dump_file, "\n");
1502 			      }
1503 			    return constant;
1504 			  }
1505 		      }
1506 		  }
1507 		else
1508 		  return constant;
1509 	      }
1510 
1511 	    tree result = vn_nary_op_lookup_pieces (newnary->length,
1512 						    newnary->opcode,
1513 						    newnary->type,
1514 						    &newnary->op[0],
1515 						    &nary);
1516 	    if (result && is_gimple_min_invariant (result))
1517 	      return get_or_alloc_expr_for_constant (result);
1518 
1519 	    if (!nary || nary->predicated_values)
1520 	      new_val_id = 0;
1521 	    else
1522 	      new_val_id = nary->value_id;
1523 	    expr = get_or_alloc_expr_for_nary (newnary, new_val_id, expr_loc);
1524 	    add_to_value (get_expr_value_id (expr), expr);
1525 	  }
1526 	return expr;
1527       }
1528       break;
1529 
1530     case REFERENCE:
1531       {
1532 	vn_reference_t ref = PRE_EXPR_REFERENCE (expr);
1533 	vec<vn_reference_op_s> operands = ref->operands;
1534 	tree vuse = ref->vuse;
1535 	tree newvuse = vuse;
1536 	vec<vn_reference_op_s> newoperands = vNULL;
1537 	bool changed = false, same_valid = true;
1538 	unsigned int i, n;
1539 	vn_reference_op_t operand;
1540 	vn_reference_t newref;
1541 
1542 	for (i = 0; operands.iterate (i, &operand); i++)
1543 	  {
1544 	    pre_expr opresult;
1545 	    pre_expr leader;
1546 	    tree op[3];
1547 	    tree type = operand->type;
1548 	    vn_reference_op_s newop = *operand;
1549 	    op[0] = operand->op0;
1550 	    op[1] = operand->op1;
1551 	    op[2] = operand->op2;
1552 	    for (n = 0; n < 3; ++n)
1553 	      {
1554 		unsigned int op_val_id;
1555 		if (!op[n])
1556 		  continue;
1557 		if (TREE_CODE (op[n]) != SSA_NAME)
1558 		  {
1559 		    /* We can't possibly insert these.  */
1560 		    if (n != 0
1561 			&& !is_gimple_min_invariant (op[n]))
1562 		      break;
1563 		    continue;
1564 		  }
1565 		op_val_id = VN_INFO (op[n])->value_id;
1566 		leader = find_leader_in_sets (op_val_id, set1, set2);
1567 		opresult = phi_translate (dest, leader, set1, set2, e);
1568 		if (opresult && opresult != leader)
1569 		  {
1570 		    tree name = get_representative_for (opresult);
1571 		    changed |= name != op[n];
1572 		    op[n] = name;
1573 		  }
1574 		else if (!opresult)
1575 		  break;
1576 	      }
1577 	    if (n != 3)
1578 	      {
1579 		newoperands.release ();
1580 		return NULL;
1581 	      }
1582 	    /* When we translate a MEM_REF across a backedge and we have
1583 	       restrict info that's not from our functions parameters
1584 	       we have to remap it since we now may deal with a different
1585 	       instance where the dependence info is no longer valid.
1586 	       See PR102970.  Note instead of keeping a remapping table
1587 	       per backedge we simply throw away restrict info.  */
1588 	    if ((newop.opcode == MEM_REF
1589 		 || newop.opcode == TARGET_MEM_REF)
1590 		&& newop.clique > 1
1591 		&& (e->flags & EDGE_DFS_BACK))
1592 	      {
1593 		newop.clique = 0;
1594 		newop.base = 0;
1595 		changed = true;
1596 	      }
1597 	    if (!changed)
1598 	      continue;
1599 	    if (!newoperands.exists ())
1600 	      newoperands = operands.copy ();
1601 	    /* We may have changed from an SSA_NAME to a constant */
1602 	    if (newop.opcode == SSA_NAME && TREE_CODE (op[0]) != SSA_NAME)
1603 	      newop.opcode = TREE_CODE (op[0]);
1604 	    newop.type = type;
1605 	    newop.op0 = op[0];
1606 	    newop.op1 = op[1];
1607 	    newop.op2 = op[2];
1608 	    newoperands[i] = newop;
1609 	  }
1610 	gcc_checking_assert (i == operands.length ());
1611 
1612 	if (vuse)
1613 	  {
1614 	    newvuse = translate_vuse_through_block (newoperands.exists ()
1615 						    ? newoperands : operands,
1616 						    ref->set, ref->base_set,
1617 						    ref->type, vuse, e,
1618 						    changed
1619 						    ? NULL : &same_valid);
1620 	    if (newvuse == NULL_TREE)
1621 	      {
1622 		newoperands.release ();
1623 		return NULL;
1624 	      }
1625 	  }
1626 
1627 	if (changed || newvuse != vuse)
1628 	  {
1629 	    unsigned int new_val_id;
1630 
1631 	    tree result = vn_reference_lookup_pieces (newvuse, ref->set,
1632 						      ref->base_set,
1633 						      ref->type,
1634 						      newoperands.exists ()
1635 						      ? newoperands : operands,
1636 						      &newref, VN_WALK);
1637 	    if (result)
1638 	      newoperands.release ();
1639 
1640 	    /* We can always insert constants, so if we have a partial
1641 	       redundant constant load of another type try to translate it
1642 	       to a constant of appropriate type.  */
1643 	    if (result && is_gimple_min_invariant (result))
1644 	      {
1645 		tree tem = result;
1646 		if (!useless_type_conversion_p (ref->type, TREE_TYPE (result)))
1647 		  {
1648 		    tem = fold_unary (VIEW_CONVERT_EXPR, ref->type, result);
1649 		    if (tem && !is_gimple_min_invariant (tem))
1650 		      tem = NULL_TREE;
1651 		  }
1652 		if (tem)
1653 		  return get_or_alloc_expr_for_constant (tem);
1654 	      }
1655 
1656 	    /* If we'd have to convert things we would need to validate
1657 	       if we can insert the translated expression.  So fail
1658 	       here for now - we cannot insert an alias with a different
1659 	       type in the VN tables either, as that would assert.  */
1660 	    if (result
1661 		&& !useless_type_conversion_p (ref->type, TREE_TYPE (result)))
1662 	      return NULL;
1663 	    else if (!result && newref
1664 		     && !useless_type_conversion_p (ref->type, newref->type))
1665 	      {
1666 		newoperands.release ();
1667 		return NULL;
1668 	      }
1669 
1670 	    if (newref)
1671 	      new_val_id = newref->value_id;
1672 	    else
1673 	      {
1674 		if (changed || !same_valid)
1675 		  new_val_id = get_next_value_id ();
1676 		else
1677 		  new_val_id = ref->value_id;
1678 		if (!newoperands.exists ())
1679 		  newoperands = operands.copy ();
1680 		newref = vn_reference_insert_pieces (newvuse, ref->set,
1681 						     ref->base_set, ref->type,
1682 						     newoperands,
1683 						     result, new_val_id);
1684 		newoperands = vNULL;
1685 	      }
1686 	    expr = get_or_alloc_expr_for_reference (newref, expr_loc);
1687 	    add_to_value (new_val_id, expr);
1688 	  }
1689 	newoperands.release ();
1690 	return expr;
1691       }
1692       break;
1693 
1694     case NAME:
1695       {
1696 	tree name = PRE_EXPR_NAME (expr);
1697 	gimple *def_stmt = SSA_NAME_DEF_STMT (name);
1698 	/* If the SSA name is defined by a PHI node in this block,
1699 	   translate it.  */
1700 	if (gimple_code (def_stmt) == GIMPLE_PHI
1701 	    && gimple_bb (def_stmt) == phiblock)
1702 	  {
1703 	    tree def = PHI_ARG_DEF (def_stmt, e->dest_idx);
1704 
1705 	    /* Handle constant. */
1706 	    if (is_gimple_min_invariant (def))
1707 	      return get_or_alloc_expr_for_constant (def);
1708 
1709 	    return get_or_alloc_expr_for_name (def);
1710 	  }
1711 	/* Otherwise return it unchanged - it will get removed if its
1712 	   value is not available in PREDs AVAIL_OUT set of expressions
1713 	   by the subtraction of TMP_GEN.  */
1714 	return expr;
1715       }
1716 
1717     default:
1718       gcc_unreachable ();
1719     }
1720 }
1721 
1722 /* Wrapper around phi_translate_1 providing caching functionality.  */
1723 
1724 static pre_expr
phi_translate(bitmap_set_t dest,pre_expr expr,bitmap_set_t set1,bitmap_set_t set2,edge e)1725 phi_translate (bitmap_set_t dest, pre_expr expr,
1726 	       bitmap_set_t set1, bitmap_set_t set2, edge e)
1727 {
1728   expr_pred_trans_t slot = NULL;
1729   pre_expr phitrans;
1730 
1731   if (!expr)
1732     return NULL;
1733 
1734   /* Constants contain no values that need translation.  */
1735   if (expr->kind == CONSTANT)
1736     return expr;
1737 
1738   if (value_id_constant_p (get_expr_value_id (expr)))
1739     return expr;
1740 
1741   /* Don't add translations of NAMEs as those are cheap to translate.  */
1742   if (expr->kind != NAME)
1743     {
1744       if (phi_trans_add (&slot, expr, e->src))
1745 	return slot->v == 0 ? NULL : expression_for_id (slot->v);
1746       /* Store NULL for the value we want to return in the case of
1747 	 recursing.  */
1748       slot->v = 0;
1749     }
1750 
1751   /* Translate.  */
1752   basic_block saved_valueize_bb = vn_context_bb;
1753   vn_context_bb = e->src;
1754   phitrans = phi_translate_1 (dest, expr, set1, set2, e);
1755   vn_context_bb = saved_valueize_bb;
1756 
1757   if (slot)
1758     {
1759       /* We may have reallocated.  */
1760       phi_trans_add (&slot, expr, e->src);
1761       if (phitrans)
1762 	slot->v = get_expression_id (phitrans);
1763       else
1764 	/* Remove failed translations again, they cause insert
1765 	   iteration to not pick up new opportunities reliably.  */
1766 	PHI_TRANS_TABLE (e->src)->clear_slot (slot);
1767     }
1768 
1769   return phitrans;
1770 }
1771 
1772 
1773 /* For each expression in SET, translate the values through phi nodes
1774    in PHIBLOCK using edge PHIBLOCK->PRED, and store the resulting
1775    expressions in DEST.  */
1776 
1777 static void
phi_translate_set(bitmap_set_t dest,bitmap_set_t set,edge e)1778 phi_translate_set (bitmap_set_t dest, bitmap_set_t set, edge e)
1779 {
1780   bitmap_iterator bi;
1781   unsigned int i;
1782 
1783   if (gimple_seq_empty_p (phi_nodes (e->dest)))
1784     {
1785       bitmap_set_copy (dest, set);
1786       return;
1787     }
1788 
1789   /* Allocate the phi-translation cache where we have an idea about
1790      its size.  hash-table implementation internals tell us that
1791      allocating the table to fit twice the number of elements will
1792      make sure we do not usually re-allocate.  */
1793   if (!PHI_TRANS_TABLE (e->src))
1794     PHI_TRANS_TABLE (e->src) = new hash_table<expr_pred_trans_d>
1795 				   (2 * bitmap_count_bits (&set->expressions));
1796   FOR_EACH_EXPR_ID_IN_SET (set, i, bi)
1797     {
1798       pre_expr expr = expression_for_id (i);
1799       pre_expr translated = phi_translate (dest, expr, set, NULL, e);
1800       if (!translated)
1801 	continue;
1802 
1803       bitmap_insert_into_set (dest, translated);
1804     }
1805 }
1806 
1807 /* Find the leader for a value (i.e., the name representing that
1808    value) in a given set, and return it.  Return NULL if no leader
1809    is found.  */
1810 
1811 static pre_expr
bitmap_find_leader(bitmap_set_t set,unsigned int val)1812 bitmap_find_leader (bitmap_set_t set, unsigned int val)
1813 {
1814   if (value_id_constant_p (val))
1815     return constant_value_expressions[-val];
1816 
1817   if (bitmap_set_contains_value (set, val))
1818     {
1819       /* Rather than walk the entire bitmap of expressions, and see
1820 	 whether any of them has the value we are looking for, we look
1821 	 at the reverse mapping, which tells us the set of expressions
1822 	 that have a given value (IE value->expressions with that
1823 	 value) and see if any of those expressions are in our set.
1824 	 The number of expressions per value is usually significantly
1825 	 less than the number of expressions in the set.  In fact, for
1826 	 large testcases, doing it this way is roughly 5-10x faster
1827 	 than walking the bitmap.
1828 	 If this is somehow a significant lose for some cases, we can
1829 	 choose which set to walk based on which set is smaller.  */
1830       unsigned int i;
1831       bitmap_iterator bi;
1832       bitmap exprset = value_expressions[val];
1833 
1834       if (!exprset->first->next)
1835 	EXECUTE_IF_SET_IN_BITMAP (exprset, 0, i, bi)
1836 	  if (bitmap_bit_p (&set->expressions, i))
1837 	    return expression_for_id (i);
1838 
1839       EXECUTE_IF_AND_IN_BITMAP (exprset, &set->expressions, 0, i, bi)
1840 	return expression_for_id (i);
1841     }
1842   return NULL;
1843 }
1844 
1845 /* Determine if EXPR, a memory expression, is ANTIC_IN at the top of
1846    BLOCK by seeing if it is not killed in the block.  Note that we are
1847    only determining whether there is a store that kills it.  Because
1848    of the order in which clean iterates over values, we are guaranteed
1849    that altered operands will have caused us to be eliminated from the
1850    ANTIC_IN set already.  */
1851 
1852 static bool
value_dies_in_block_x(pre_expr expr,basic_block block)1853 value_dies_in_block_x (pre_expr expr, basic_block block)
1854 {
1855   tree vuse = PRE_EXPR_REFERENCE (expr)->vuse;
1856   vn_reference_t refx = PRE_EXPR_REFERENCE (expr);
1857   gimple *def;
1858   gimple_stmt_iterator gsi;
1859   unsigned id = get_expression_id (expr);
1860   bool res = false;
1861   ao_ref ref;
1862 
1863   if (!vuse)
1864     return false;
1865 
1866   /* Lookup a previously calculated result.  */
1867   if (EXPR_DIES (block)
1868       && bitmap_bit_p (EXPR_DIES (block), id * 2))
1869     return bitmap_bit_p (EXPR_DIES (block), id * 2 + 1);
1870 
1871   /* A memory expression {e, VUSE} dies in the block if there is a
1872      statement that may clobber e.  If, starting statement walk from the
1873      top of the basic block, a statement uses VUSE there can be no kill
1874      inbetween that use and the original statement that loaded {e, VUSE},
1875      so we can stop walking.  */
1876   ref.base = NULL_TREE;
1877   for (gsi = gsi_start_bb (block); !gsi_end_p (gsi); gsi_next (&gsi))
1878     {
1879       tree def_vuse, def_vdef;
1880       def = gsi_stmt (gsi);
1881       def_vuse = gimple_vuse (def);
1882       def_vdef = gimple_vdef (def);
1883 
1884       /* Not a memory statement.  */
1885       if (!def_vuse)
1886 	continue;
1887 
1888       /* Not a may-def.  */
1889       if (!def_vdef)
1890 	{
1891 	  /* A load with the same VUSE, we're done.  */
1892 	  if (def_vuse == vuse)
1893 	    break;
1894 
1895 	  continue;
1896 	}
1897 
1898       /* Init ref only if we really need it.  */
1899       if (ref.base == NULL_TREE
1900 	  && !ao_ref_init_from_vn_reference (&ref, refx->set, refx->base_set,
1901 					     refx->type, refx->operands))
1902 	{
1903 	  res = true;
1904 	  break;
1905 	}
1906       /* If the statement may clobber expr, it dies.  */
1907       if (stmt_may_clobber_ref_p_1 (def, &ref))
1908 	{
1909 	  res = true;
1910 	  break;
1911 	}
1912     }
1913 
1914   /* Remember the result.  */
1915   if (!EXPR_DIES (block))
1916     EXPR_DIES (block) = BITMAP_ALLOC (&grand_bitmap_obstack);
1917   bitmap_set_bit (EXPR_DIES (block), id * 2);
1918   if (res)
1919     bitmap_set_bit (EXPR_DIES (block), id * 2 + 1);
1920 
1921   return res;
1922 }
1923 
1924 
1925 /* Determine if OP is valid in SET1 U SET2, which it is when the union
1926    contains its value-id.  */
1927 
1928 static bool
op_valid_in_sets(bitmap_set_t set1,bitmap_set_t set2,tree op)1929 op_valid_in_sets (bitmap_set_t set1, bitmap_set_t set2, tree op)
1930 {
1931   if (op && TREE_CODE (op) == SSA_NAME)
1932     {
1933       unsigned int value_id = VN_INFO (op)->value_id;
1934       if (!(bitmap_set_contains_value (set1, value_id)
1935 	    || (set2 && bitmap_set_contains_value  (set2, value_id))))
1936 	return false;
1937     }
1938   return true;
1939 }
1940 
1941 /* Determine if the expression EXPR is valid in SET1 U SET2.
1942    ONLY SET2 CAN BE NULL.
1943    This means that we have a leader for each part of the expression
1944    (if it consists of values), or the expression is an SSA_NAME.
1945    For loads/calls, we also see if the vuse is killed in this block.  */
1946 
1947 static bool
valid_in_sets(bitmap_set_t set1,bitmap_set_t set2,pre_expr expr)1948 valid_in_sets (bitmap_set_t set1, bitmap_set_t set2, pre_expr expr)
1949 {
1950   switch (expr->kind)
1951     {
1952     case NAME:
1953       /* By construction all NAMEs are available.  Non-available
1954 	 NAMEs are removed by subtracting TMP_GEN from the sets.  */
1955       return true;
1956     case NARY:
1957       {
1958 	unsigned int i;
1959 	vn_nary_op_t nary = PRE_EXPR_NARY (expr);
1960 	for (i = 0; i < nary->length; i++)
1961 	  if (!op_valid_in_sets (set1, set2, nary->op[i]))
1962 	    return false;
1963 	return true;
1964       }
1965       break;
1966     case REFERENCE:
1967       {
1968 	vn_reference_t ref = PRE_EXPR_REFERENCE (expr);
1969 	vn_reference_op_t vro;
1970 	unsigned int i;
1971 
1972 	FOR_EACH_VEC_ELT (ref->operands, i, vro)
1973 	  {
1974 	    if (!op_valid_in_sets (set1, set2, vro->op0)
1975 		|| !op_valid_in_sets (set1, set2, vro->op1)
1976 		|| !op_valid_in_sets (set1, set2, vro->op2))
1977 	      return false;
1978 	  }
1979 	return true;
1980       }
1981     default:
1982       gcc_unreachable ();
1983     }
1984 }
1985 
1986 /* Clean the set of expressions SET1 that are no longer valid in SET1 or SET2.
1987    This means expressions that are made up of values we have no leaders for
1988    in SET1 or SET2.  */
1989 
1990 static void
clean(bitmap_set_t set1,bitmap_set_t set2=NULL)1991 clean (bitmap_set_t set1, bitmap_set_t set2 = NULL)
1992 {
1993   vec<pre_expr> exprs = sorted_array_from_bitmap_set (set1);
1994   pre_expr expr;
1995   int i;
1996 
1997   FOR_EACH_VEC_ELT (exprs, i, expr)
1998     {
1999       if (!valid_in_sets (set1, set2, expr))
2000 	{
2001 	  unsigned int val  = get_expr_value_id (expr);
2002 	  bitmap_clear_bit (&set1->expressions, get_expression_id (expr));
2003 	  /* We are entered with possibly multiple expressions for a value
2004 	     so before removing a value from the set see if there's an
2005 	     expression for it left.  */
2006 	  if (! bitmap_find_leader (set1, val))
2007 	    bitmap_clear_bit (&set1->values, val);
2008 	}
2009     }
2010   exprs.release ();
2011 
2012   if (flag_checking)
2013     {
2014       unsigned j;
2015       bitmap_iterator bi;
2016       FOR_EACH_EXPR_ID_IN_SET (set1, j, bi)
2017 	gcc_assert (valid_in_sets (set1, set2, expression_for_id (j)));
2018     }
2019 }
2020 
2021 /* Clean the set of expressions that are no longer valid in SET because
2022    they are clobbered in BLOCK or because they trap and may not be executed.  */
2023 
2024 static void
prune_clobbered_mems(bitmap_set_t set,basic_block block)2025 prune_clobbered_mems (bitmap_set_t set, basic_block block)
2026 {
2027   bitmap_iterator bi;
2028   unsigned i;
2029   unsigned to_remove = -1U;
2030   bool any_removed = false;
2031 
2032   FOR_EACH_EXPR_ID_IN_SET (set, i, bi)
2033     {
2034       /* Remove queued expr.  */
2035       if (to_remove != -1U)
2036 	{
2037 	  bitmap_clear_bit (&set->expressions, to_remove);
2038 	  any_removed = true;
2039 	  to_remove = -1U;
2040 	}
2041 
2042       pre_expr expr = expression_for_id (i);
2043       if (expr->kind == REFERENCE)
2044 	{
2045 	  vn_reference_t ref = PRE_EXPR_REFERENCE (expr);
2046 	  if (ref->vuse)
2047 	    {
2048 	      gimple *def_stmt = SSA_NAME_DEF_STMT (ref->vuse);
2049 	      if (!gimple_nop_p (def_stmt)
2050 		  /* If value-numbering provided a memory state for this
2051 		     that dominates BLOCK we're done, otherwise we have
2052 		     to check if the value dies in BLOCK.  */
2053 		  && !(gimple_bb (def_stmt) != block
2054 		       && dominated_by_p (CDI_DOMINATORS,
2055 					  block, gimple_bb (def_stmt)))
2056 		  && value_dies_in_block_x (expr, block))
2057 		to_remove = i;
2058 	    }
2059 	  /* If the REFERENCE may trap make sure the block does not contain
2060 	     a possible exit point.
2061 	     ???  This is overly conservative if we translate AVAIL_OUT
2062 	     as the available expression might be after the exit point.  */
2063 	  if (BB_MAY_NOTRETURN (block)
2064 	      && vn_reference_may_trap (ref))
2065 	    to_remove = i;
2066 	}
2067       else if (expr->kind == NARY)
2068 	{
2069 	  vn_nary_op_t nary = PRE_EXPR_NARY (expr);
2070 	  /* If the NARY may trap make sure the block does not contain
2071 	     a possible exit point.
2072 	     ???  This is overly conservative if we translate AVAIL_OUT
2073 	     as the available expression might be after the exit point.  */
2074 	  if (BB_MAY_NOTRETURN (block)
2075 	      && vn_nary_may_trap (nary))
2076 	    to_remove = i;
2077 	}
2078     }
2079 
2080   /* Remove queued expr.  */
2081   if (to_remove != -1U)
2082     {
2083       bitmap_clear_bit (&set->expressions, to_remove);
2084       any_removed = true;
2085     }
2086 
2087   /* Above we only removed expressions, now clean the set of values
2088      which no longer have any corresponding expression.  We cannot
2089      clear the value at the time we remove an expression since there
2090      may be multiple expressions per value.
2091      If we'd queue possibly to be removed values we could use
2092      the bitmap_find_leader way to see if there's still an expression
2093      for it.  For some ratio of to be removed values and number of
2094      values/expressions in the set this might be faster than rebuilding
2095      the value-set.  */
2096   if (any_removed)
2097     {
2098       bitmap_clear (&set->values);
2099       FOR_EACH_EXPR_ID_IN_SET (set, i, bi)
2100 	{
2101 	  pre_expr expr = expression_for_id (i);
2102 	  unsigned int value_id = get_expr_value_id (expr);
2103 	  bitmap_set_bit (&set->values, value_id);
2104 	}
2105     }
2106 }
2107 
2108 /* Compute the ANTIC set for BLOCK.
2109 
2110    If succs(BLOCK) > 1 then
2111      ANTIC_OUT[BLOCK] = intersection of ANTIC_IN[b] for all succ(BLOCK)
2112    else if succs(BLOCK) == 1 then
2113      ANTIC_OUT[BLOCK] = phi_translate (ANTIC_IN[succ(BLOCK)])
2114 
2115    ANTIC_IN[BLOCK] = clean(ANTIC_OUT[BLOCK] U EXP_GEN[BLOCK] - TMP_GEN[BLOCK])
2116 
2117    Note that clean() is deferred until after the iteration.  */
2118 
2119 static bool
compute_antic_aux(basic_block block,bool block_has_abnormal_pred_edge)2120 compute_antic_aux (basic_block block, bool block_has_abnormal_pred_edge)
2121 {
2122   bitmap_set_t S, old, ANTIC_OUT;
2123   edge e;
2124   edge_iterator ei;
2125 
2126   bool was_visited = BB_VISITED (block);
2127   bool changed = ! BB_VISITED (block);
2128   BB_VISITED (block) = 1;
2129   old = ANTIC_OUT = S = NULL;
2130 
2131   /* If any edges from predecessors are abnormal, antic_in is empty,
2132      so do nothing.  */
2133   if (block_has_abnormal_pred_edge)
2134     goto maybe_dump_sets;
2135 
2136   old = ANTIC_IN (block);
2137   ANTIC_OUT = bitmap_set_new ();
2138 
2139   /* If the block has no successors, ANTIC_OUT is empty.  */
2140   if (EDGE_COUNT (block->succs) == 0)
2141     ;
2142   /* If we have one successor, we could have some phi nodes to
2143      translate through.  */
2144   else if (single_succ_p (block))
2145     {
2146       e = single_succ_edge (block);
2147       gcc_assert (BB_VISITED (e->dest));
2148       phi_translate_set (ANTIC_OUT, ANTIC_IN (e->dest), e);
2149     }
2150   /* If we have multiple successors, we take the intersection of all of
2151      them.  Note that in the case of loop exit phi nodes, we may have
2152      phis to translate through.  */
2153   else
2154     {
2155       size_t i;
2156       edge first = NULL;
2157 
2158       auto_vec<edge> worklist (EDGE_COUNT (block->succs));
2159       FOR_EACH_EDGE (e, ei, block->succs)
2160 	{
2161 	  if (!first
2162 	      && BB_VISITED (e->dest))
2163 	    first = e;
2164 	  else if (BB_VISITED (e->dest))
2165 	    worklist.quick_push (e);
2166 	  else
2167 	    {
2168 	      /* Unvisited successors get their ANTIC_IN replaced by the
2169 		 maximal set to arrive at a maximum ANTIC_IN solution.
2170 		 We can ignore them in the intersection operation and thus
2171 		 need not explicitely represent that maximum solution.  */
2172 	      if (dump_file && (dump_flags & TDF_DETAILS))
2173 		fprintf (dump_file, "ANTIC_IN is MAX on %d->%d\n",
2174 			 e->src->index, e->dest->index);
2175 	    }
2176 	}
2177 
2178       /* Of multiple successors we have to have visited one already
2179          which is guaranteed by iteration order.  */
2180       gcc_assert (first != NULL);
2181 
2182       phi_translate_set (ANTIC_OUT, ANTIC_IN (first->dest), first);
2183 
2184       /* If we have multiple successors we need to intersect the ANTIC_OUT
2185          sets.  For values that's a simple intersection but for
2186 	 expressions it is a union.  Given we want to have a single
2187 	 expression per value in our sets we have to canonicalize.
2188 	 Avoid randomness and running into cycles like for PR82129 and
2189 	 canonicalize the expression we choose to the one with the
2190 	 lowest id.  This requires we actually compute the union first.  */
2191       FOR_EACH_VEC_ELT (worklist, i, e)
2192 	{
2193 	  if (!gimple_seq_empty_p (phi_nodes (e->dest)))
2194 	    {
2195 	      bitmap_set_t tmp = bitmap_set_new ();
2196 	      phi_translate_set (tmp, ANTIC_IN (e->dest), e);
2197 	      bitmap_and_into (&ANTIC_OUT->values, &tmp->values);
2198 	      bitmap_ior_into (&ANTIC_OUT->expressions, &tmp->expressions);
2199 	      bitmap_set_free (tmp);
2200 	    }
2201 	  else
2202 	    {
2203 	      bitmap_and_into (&ANTIC_OUT->values, &ANTIC_IN (e->dest)->values);
2204 	      bitmap_ior_into (&ANTIC_OUT->expressions,
2205 			       &ANTIC_IN (e->dest)->expressions);
2206 	    }
2207 	}
2208       if (! worklist.is_empty ())
2209 	{
2210 	  /* Prune expressions not in the value set.  */
2211 	  bitmap_iterator bi;
2212 	  unsigned int i;
2213 	  unsigned int to_clear = -1U;
2214 	  FOR_EACH_EXPR_ID_IN_SET (ANTIC_OUT, i, bi)
2215 	    {
2216 	      if (to_clear != -1U)
2217 		{
2218 		  bitmap_clear_bit (&ANTIC_OUT->expressions, to_clear);
2219 		  to_clear = -1U;
2220 		}
2221 	      pre_expr expr = expression_for_id (i);
2222 	      unsigned int value_id = get_expr_value_id (expr);
2223 	      if (!bitmap_bit_p (&ANTIC_OUT->values, value_id))
2224 		to_clear = i;
2225 	    }
2226 	  if (to_clear != -1U)
2227 	    bitmap_clear_bit (&ANTIC_OUT->expressions, to_clear);
2228 	}
2229     }
2230 
2231   /* Prune expressions that are clobbered in block and thus become
2232      invalid if translated from ANTIC_OUT to ANTIC_IN.  */
2233   prune_clobbered_mems (ANTIC_OUT, block);
2234 
2235   /* Generate ANTIC_OUT - TMP_GEN.  */
2236   S = bitmap_set_subtract_expressions (ANTIC_OUT, TMP_GEN (block));
2237 
2238   /* Start ANTIC_IN with EXP_GEN - TMP_GEN.  */
2239   ANTIC_IN (block) = bitmap_set_subtract_expressions (EXP_GEN (block),
2240 						      TMP_GEN (block));
2241 
2242   /* Then union in the ANTIC_OUT - TMP_GEN values,
2243      to get ANTIC_OUT U EXP_GEN - TMP_GEN */
2244   bitmap_ior_into (&ANTIC_IN (block)->values, &S->values);
2245   bitmap_ior_into (&ANTIC_IN (block)->expressions, &S->expressions);
2246 
2247   /* clean (ANTIC_IN (block)) is defered to after the iteration converged
2248      because it can cause non-convergence, see for example PR81181.  */
2249 
2250   /* Intersect ANTIC_IN with the old ANTIC_IN.  This is required until
2251      we properly represent the maximum expression set, thus not prune
2252      values without expressions during the iteration.  */
2253   if (was_visited
2254       && bitmap_and_into (&ANTIC_IN (block)->values, &old->values))
2255     {
2256       if (dump_file && (dump_flags & TDF_DETAILS))
2257 	fprintf (dump_file, "warning: intersecting with old ANTIC_IN "
2258 		 "shrinks the set\n");
2259       /* Prune expressions not in the value set.  */
2260       bitmap_iterator bi;
2261       unsigned int i;
2262       unsigned int to_clear = -1U;
2263       FOR_EACH_EXPR_ID_IN_SET (ANTIC_IN (block), i, bi)
2264 	{
2265 	  if (to_clear != -1U)
2266 	    {
2267 	      bitmap_clear_bit (&ANTIC_IN (block)->expressions, to_clear);
2268 	      to_clear = -1U;
2269 	    }
2270 	  pre_expr expr = expression_for_id (i);
2271 	  unsigned int value_id = get_expr_value_id (expr);
2272 	  if (!bitmap_bit_p (&ANTIC_IN (block)->values, value_id))
2273 	    to_clear = i;
2274 	}
2275       if (to_clear != -1U)
2276 	bitmap_clear_bit (&ANTIC_IN (block)->expressions, to_clear);
2277     }
2278 
2279   if (!bitmap_set_equal (old, ANTIC_IN (block)))
2280     changed = true;
2281 
2282  maybe_dump_sets:
2283   if (dump_file && (dump_flags & TDF_DETAILS))
2284     {
2285       if (ANTIC_OUT)
2286 	print_bitmap_set (dump_file, ANTIC_OUT, "ANTIC_OUT", block->index);
2287 
2288       if (changed)
2289 	fprintf (dump_file, "[changed] ");
2290       print_bitmap_set (dump_file, ANTIC_IN (block), "ANTIC_IN",
2291 			block->index);
2292 
2293       if (S)
2294 	print_bitmap_set (dump_file, S, "S", block->index);
2295     }
2296   if (old)
2297     bitmap_set_free (old);
2298   if (S)
2299     bitmap_set_free (S);
2300   if (ANTIC_OUT)
2301     bitmap_set_free (ANTIC_OUT);
2302   return changed;
2303 }
2304 
2305 /* Compute PARTIAL_ANTIC for BLOCK.
2306 
2307    If succs(BLOCK) > 1 then
2308      PA_OUT[BLOCK] = value wise union of PA_IN[b] + all ANTIC_IN not
2309      in ANTIC_OUT for all succ(BLOCK)
2310    else if succs(BLOCK) == 1 then
2311      PA_OUT[BLOCK] = phi_translate (PA_IN[succ(BLOCK)])
2312 
2313    PA_IN[BLOCK] = clean(PA_OUT[BLOCK] - TMP_GEN[BLOCK] - ANTIC_IN[BLOCK])
2314 
2315 */
2316 static void
compute_partial_antic_aux(basic_block block,bool block_has_abnormal_pred_edge)2317 compute_partial_antic_aux (basic_block block,
2318 			   bool block_has_abnormal_pred_edge)
2319 {
2320   bitmap_set_t old_PA_IN;
2321   bitmap_set_t PA_OUT;
2322   edge e;
2323   edge_iterator ei;
2324   unsigned long max_pa = param_max_partial_antic_length;
2325 
2326   old_PA_IN = PA_OUT = NULL;
2327 
2328   /* If any edges from predecessors are abnormal, antic_in is empty,
2329      so do nothing.  */
2330   if (block_has_abnormal_pred_edge)
2331     goto maybe_dump_sets;
2332 
2333   /* If there are too many partially anticipatable values in the
2334      block, phi_translate_set can take an exponential time: stop
2335      before the translation starts.  */
2336   if (max_pa
2337       && single_succ_p (block)
2338       && bitmap_count_bits (&PA_IN (single_succ (block))->values) > max_pa)
2339     goto maybe_dump_sets;
2340 
2341   old_PA_IN = PA_IN (block);
2342   PA_OUT = bitmap_set_new ();
2343 
2344   /* If the block has no successors, ANTIC_OUT is empty.  */
2345   if (EDGE_COUNT (block->succs) == 0)
2346     ;
2347   /* If we have one successor, we could have some phi nodes to
2348      translate through.  Note that we can't phi translate across DFS
2349      back edges in partial antic, because it uses a union operation on
2350      the successors.  For recurrences like IV's, we will end up
2351      generating a new value in the set on each go around (i + 3 (VH.1)
2352      VH.1 + 1 (VH.2), VH.2 + 1 (VH.3), etc), forever.  */
2353   else if (single_succ_p (block))
2354     {
2355       e = single_succ_edge (block);
2356       if (!(e->flags & EDGE_DFS_BACK))
2357 	phi_translate_set (PA_OUT, PA_IN (e->dest), e);
2358     }
2359   /* If we have multiple successors, we take the union of all of
2360      them.  */
2361   else
2362     {
2363       size_t i;
2364 
2365       auto_vec<edge> worklist (EDGE_COUNT (block->succs));
2366       FOR_EACH_EDGE (e, ei, block->succs)
2367 	{
2368 	  if (e->flags & EDGE_DFS_BACK)
2369 	    continue;
2370 	  worklist.quick_push (e);
2371 	}
2372       if (worklist.length () > 0)
2373 	{
2374 	  FOR_EACH_VEC_ELT (worklist, i, e)
2375 	    {
2376 	      unsigned int i;
2377 	      bitmap_iterator bi;
2378 
2379 	      FOR_EACH_EXPR_ID_IN_SET (ANTIC_IN (e->dest), i, bi)
2380 		bitmap_value_insert_into_set (PA_OUT,
2381 					      expression_for_id (i));
2382 	      if (!gimple_seq_empty_p (phi_nodes (e->dest)))
2383 		{
2384 		  bitmap_set_t pa_in = bitmap_set_new ();
2385 		  phi_translate_set (pa_in, PA_IN (e->dest), e);
2386 		  FOR_EACH_EXPR_ID_IN_SET (pa_in, i, bi)
2387 		    bitmap_value_insert_into_set (PA_OUT,
2388 						  expression_for_id (i));
2389 		  bitmap_set_free (pa_in);
2390 		}
2391 	      else
2392 		FOR_EACH_EXPR_ID_IN_SET (PA_IN (e->dest), i, bi)
2393 		  bitmap_value_insert_into_set (PA_OUT,
2394 						expression_for_id (i));
2395 	    }
2396 	}
2397     }
2398 
2399   /* Prune expressions that are clobbered in block and thus become
2400      invalid if translated from PA_OUT to PA_IN.  */
2401   prune_clobbered_mems (PA_OUT, block);
2402 
2403   /* PA_IN starts with PA_OUT - TMP_GEN.
2404      Then we subtract things from ANTIC_IN.  */
2405   PA_IN (block) = bitmap_set_subtract_expressions (PA_OUT, TMP_GEN (block));
2406 
2407   /* For partial antic, we want to put back in the phi results, since
2408      we will properly avoid making them partially antic over backedges.  */
2409   bitmap_ior_into (&PA_IN (block)->values, &PHI_GEN (block)->values);
2410   bitmap_ior_into (&PA_IN (block)->expressions, &PHI_GEN (block)->expressions);
2411 
2412   /* PA_IN[block] = PA_IN[block] - ANTIC_IN[block] */
2413   bitmap_set_subtract_values (PA_IN (block), ANTIC_IN (block));
2414 
2415   clean (PA_IN (block), ANTIC_IN (block));
2416 
2417  maybe_dump_sets:
2418   if (dump_file && (dump_flags & TDF_DETAILS))
2419     {
2420       if (PA_OUT)
2421 	print_bitmap_set (dump_file, PA_OUT, "PA_OUT", block->index);
2422 
2423       print_bitmap_set (dump_file, PA_IN (block), "PA_IN", block->index);
2424     }
2425   if (old_PA_IN)
2426     bitmap_set_free (old_PA_IN);
2427   if (PA_OUT)
2428     bitmap_set_free (PA_OUT);
2429 }
2430 
2431 /* Compute ANTIC and partial ANTIC sets.  */
2432 
2433 static void
compute_antic(void)2434 compute_antic (void)
2435 {
2436   bool changed = true;
2437   int num_iterations = 0;
2438   basic_block block;
2439   int i;
2440   edge_iterator ei;
2441   edge e;
2442 
2443   /* If any predecessor edges are abnormal, we punt, so antic_in is empty.
2444      We pre-build the map of blocks with incoming abnormal edges here.  */
2445   auto_sbitmap has_abnormal_preds (last_basic_block_for_fn (cfun));
2446   bitmap_clear (has_abnormal_preds);
2447 
2448   FOR_ALL_BB_FN (block, cfun)
2449     {
2450       BB_VISITED (block) = 0;
2451 
2452       FOR_EACH_EDGE (e, ei, block->preds)
2453 	if (e->flags & EDGE_ABNORMAL)
2454 	  {
2455 	    bitmap_set_bit (has_abnormal_preds, block->index);
2456 	    break;
2457 	  }
2458 
2459       /* While we are here, give empty ANTIC_IN sets to each block.  */
2460       ANTIC_IN (block) = bitmap_set_new ();
2461       if (do_partial_partial)
2462 	PA_IN (block) = bitmap_set_new ();
2463     }
2464 
2465   /* At the exit block we anticipate nothing.  */
2466   BB_VISITED (EXIT_BLOCK_PTR_FOR_FN (cfun)) = 1;
2467 
2468   /* For ANTIC computation we need a postorder that also guarantees that
2469      a block with a single successor is visited after its successor.
2470      RPO on the inverted CFG has this property.  */
2471   auto_vec<int, 20> postorder;
2472   inverted_post_order_compute (&postorder);
2473 
2474   auto_sbitmap worklist (last_basic_block_for_fn (cfun) + 1);
2475   bitmap_clear (worklist);
2476   FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds)
2477     bitmap_set_bit (worklist, e->src->index);
2478   while (changed)
2479     {
2480       if (dump_file && (dump_flags & TDF_DETAILS))
2481 	fprintf (dump_file, "Starting iteration %d\n", num_iterations);
2482       /* ???  We need to clear our PHI translation cache here as the
2483          ANTIC sets shrink and we restrict valid translations to
2484 	 those having operands with leaders in ANTIC.  Same below
2485 	 for PA ANTIC computation.  */
2486       num_iterations++;
2487       changed = false;
2488       for (i = postorder.length () - 1; i >= 0; i--)
2489 	{
2490 	  if (bitmap_bit_p (worklist, postorder[i]))
2491 	    {
2492 	      basic_block block = BASIC_BLOCK_FOR_FN (cfun, postorder[i]);
2493 	      bitmap_clear_bit (worklist, block->index);
2494 	      if (compute_antic_aux (block,
2495 				     bitmap_bit_p (has_abnormal_preds,
2496 						   block->index)))
2497 		{
2498 		  FOR_EACH_EDGE (e, ei, block->preds)
2499 		    bitmap_set_bit (worklist, e->src->index);
2500 		  changed = true;
2501 		}
2502 	    }
2503 	}
2504       /* Theoretically possible, but *highly* unlikely.  */
2505       gcc_checking_assert (num_iterations < 500);
2506     }
2507 
2508   /* We have to clean after the dataflow problem converged as cleaning
2509      can cause non-convergence because it is based on expressions
2510      rather than values.  */
2511   FOR_EACH_BB_FN (block, cfun)
2512     clean (ANTIC_IN (block));
2513 
2514   statistics_histogram_event (cfun, "compute_antic iterations",
2515 			      num_iterations);
2516 
2517   if (do_partial_partial)
2518     {
2519       /* For partial antic we ignore backedges and thus we do not need
2520          to perform any iteration when we process blocks in postorder.  */
2521       for (i = postorder.length () - 1; i >= 0; i--)
2522 	{
2523 	  basic_block block = BASIC_BLOCK_FOR_FN (cfun, postorder[i]);
2524 	  compute_partial_antic_aux (block,
2525 				     bitmap_bit_p (has_abnormal_preds,
2526 						   block->index));
2527 	}
2528     }
2529 }
2530 
2531 
2532 /* Inserted expressions are placed onto this worklist, which is used
2533    for performing quick dead code elimination of insertions we made
2534    that didn't turn out to be necessary.   */
2535 static bitmap inserted_exprs;
2536 
2537 /* The actual worker for create_component_ref_by_pieces.  */
2538 
2539 static tree
create_component_ref_by_pieces_1(basic_block block,vn_reference_t ref,unsigned int * operand,gimple_seq * stmts)2540 create_component_ref_by_pieces_1 (basic_block block, vn_reference_t ref,
2541 				  unsigned int *operand, gimple_seq *stmts)
2542 {
2543   vn_reference_op_t currop = &ref->operands[*operand];
2544   tree genop;
2545   ++*operand;
2546   switch (currop->opcode)
2547     {
2548     case CALL_EXPR:
2549       gcc_unreachable ();
2550 
2551     case MEM_REF:
2552       {
2553 	tree baseop = create_component_ref_by_pieces_1 (block, ref, operand,
2554 							stmts);
2555 	if (!baseop)
2556 	  return NULL_TREE;
2557 	tree offset = currop->op0;
2558 	if (TREE_CODE (baseop) == ADDR_EXPR
2559 	    && handled_component_p (TREE_OPERAND (baseop, 0)))
2560 	  {
2561 	    poly_int64 off;
2562 	    tree base;
2563 	    base = get_addr_base_and_unit_offset (TREE_OPERAND (baseop, 0),
2564 						  &off);
2565 	    gcc_assert (base);
2566 	    offset = int_const_binop (PLUS_EXPR, offset,
2567 				      build_int_cst (TREE_TYPE (offset),
2568 						     off));
2569 	    baseop = build_fold_addr_expr (base);
2570 	  }
2571 	genop = build2 (MEM_REF, currop->type, baseop, offset);
2572 	MR_DEPENDENCE_CLIQUE (genop) = currop->clique;
2573 	MR_DEPENDENCE_BASE (genop) = currop->base;
2574 	REF_REVERSE_STORAGE_ORDER (genop) = currop->reverse;
2575 	return genop;
2576       }
2577 
2578     case TARGET_MEM_REF:
2579       {
2580 	tree genop0 = NULL_TREE, genop1 = NULL_TREE;
2581 	vn_reference_op_t nextop = &ref->operands[(*operand)++];
2582 	tree baseop = create_component_ref_by_pieces_1 (block, ref, operand,
2583 							stmts);
2584 	if (!baseop)
2585 	  return NULL_TREE;
2586 	if (currop->op0)
2587 	  {
2588 	    genop0 = find_or_generate_expression (block, currop->op0, stmts);
2589 	    if (!genop0)
2590 	      return NULL_TREE;
2591 	  }
2592 	if (nextop->op0)
2593 	  {
2594 	    genop1 = find_or_generate_expression (block, nextop->op0, stmts);
2595 	    if (!genop1)
2596 	      return NULL_TREE;
2597 	  }
2598 	genop = build5 (TARGET_MEM_REF, currop->type,
2599 			baseop, currop->op2, genop0, currop->op1, genop1);
2600 
2601 	MR_DEPENDENCE_CLIQUE (genop) = currop->clique;
2602 	MR_DEPENDENCE_BASE (genop) = currop->base;
2603 	return genop;
2604       }
2605 
2606     case ADDR_EXPR:
2607       if (currop->op0)
2608 	{
2609 	  gcc_assert (is_gimple_min_invariant (currop->op0));
2610 	  return currop->op0;
2611 	}
2612       /* Fallthrough.  */
2613     case REALPART_EXPR:
2614     case IMAGPART_EXPR:
2615     case VIEW_CONVERT_EXPR:
2616       {
2617 	tree genop0 = create_component_ref_by_pieces_1 (block, ref, operand,
2618 							stmts);
2619 	if (!genop0)
2620 	  return NULL_TREE;
2621 	return fold_build1 (currop->opcode, currop->type, genop0);
2622       }
2623 
2624     case WITH_SIZE_EXPR:
2625       {
2626 	tree genop0 = create_component_ref_by_pieces_1 (block, ref, operand,
2627 							stmts);
2628 	if (!genop0)
2629 	  return NULL_TREE;
2630 	tree genop1 = find_or_generate_expression (block, currop->op0, stmts);
2631 	if (!genop1)
2632 	  return NULL_TREE;
2633 	return fold_build2 (currop->opcode, currop->type, genop0, genop1);
2634       }
2635 
2636     case BIT_FIELD_REF:
2637       {
2638 	tree genop0 = create_component_ref_by_pieces_1 (block, ref, operand,
2639 							stmts);
2640 	if (!genop0)
2641 	  return NULL_TREE;
2642 	tree op1 = currop->op0;
2643 	tree op2 = currop->op1;
2644 	tree t = build3 (BIT_FIELD_REF, currop->type, genop0, op1, op2);
2645 	REF_REVERSE_STORAGE_ORDER (t) = currop->reverse;
2646 	return fold (t);
2647       }
2648 
2649       /* For array ref vn_reference_op's, operand 1 of the array ref
2650 	 is op0 of the reference op and operand 3 of the array ref is
2651 	 op1.  */
2652     case ARRAY_RANGE_REF:
2653     case ARRAY_REF:
2654       {
2655 	tree genop0;
2656 	tree genop1 = currop->op0;
2657 	tree genop2 = currop->op1;
2658 	tree genop3 = currop->op2;
2659 	genop0 = create_component_ref_by_pieces_1 (block, ref, operand,
2660 						   stmts);
2661 	if (!genop0)
2662 	  return NULL_TREE;
2663 	genop1 = find_or_generate_expression (block, genop1, stmts);
2664 	if (!genop1)
2665 	  return NULL_TREE;
2666 	if (genop2)
2667 	  {
2668 	    tree domain_type = TYPE_DOMAIN (TREE_TYPE (genop0));
2669 	    /* Drop zero minimum index if redundant.  */
2670 	    if (integer_zerop (genop2)
2671 		&& (!domain_type
2672 		    || integer_zerop (TYPE_MIN_VALUE (domain_type))))
2673 	      genop2 = NULL_TREE;
2674 	    else
2675 	      {
2676 		genop2 = find_or_generate_expression (block, genop2, stmts);
2677 		if (!genop2)
2678 		  return NULL_TREE;
2679 	      }
2680 	  }
2681 	if (genop3)
2682 	  {
2683 	    tree elmt_type = TREE_TYPE (TREE_TYPE (genop0));
2684 	    /* We can't always put a size in units of the element alignment
2685 	       here as the element alignment may be not visible.  See
2686 	       PR43783.  Simply drop the element size for constant
2687 	       sizes.  */
2688 	    if (TREE_CODE (genop3) == INTEGER_CST
2689 		&& TREE_CODE (TYPE_SIZE_UNIT (elmt_type)) == INTEGER_CST
2690 		&& wi::eq_p (wi::to_offset (TYPE_SIZE_UNIT (elmt_type)),
2691 			     (wi::to_offset (genop3)
2692 			      * vn_ref_op_align_unit (currop))))
2693 	      genop3 = NULL_TREE;
2694 	    else
2695 	      {
2696 		genop3 = find_or_generate_expression (block, genop3, stmts);
2697 		if (!genop3)
2698 		  return NULL_TREE;
2699 	      }
2700 	  }
2701 	return build4 (currop->opcode, currop->type, genop0, genop1,
2702 		       genop2, genop3);
2703       }
2704     case COMPONENT_REF:
2705       {
2706 	tree op0;
2707 	tree op1;
2708 	tree genop2 = currop->op1;
2709 	op0 = create_component_ref_by_pieces_1 (block, ref, operand, stmts);
2710 	if (!op0)
2711 	  return NULL_TREE;
2712 	/* op1 should be a FIELD_DECL, which are represented by themselves.  */
2713 	op1 = currop->op0;
2714 	if (genop2)
2715 	  {
2716 	    genop2 = find_or_generate_expression (block, genop2, stmts);
2717 	    if (!genop2)
2718 	      return NULL_TREE;
2719 	  }
2720 	return fold_build3 (COMPONENT_REF, TREE_TYPE (op1), op0, op1, genop2);
2721       }
2722 
2723     case SSA_NAME:
2724       {
2725 	genop = find_or_generate_expression (block, currop->op0, stmts);
2726 	return genop;
2727       }
2728     case STRING_CST:
2729     case INTEGER_CST:
2730     case POLY_INT_CST:
2731     case COMPLEX_CST:
2732     case VECTOR_CST:
2733     case REAL_CST:
2734     case CONSTRUCTOR:
2735     case VAR_DECL:
2736     case PARM_DECL:
2737     case CONST_DECL:
2738     case RESULT_DECL:
2739     case FUNCTION_DECL:
2740       return currop->op0;
2741 
2742     default:
2743       gcc_unreachable ();
2744     }
2745 }
2746 
2747 /* For COMPONENT_REF's and ARRAY_REF's, we can't have any intermediates for the
2748    COMPONENT_REF or MEM_REF or ARRAY_REF portion, because we'd end up with
2749    trying to rename aggregates into ssa form directly, which is a no no.
2750 
2751    Thus, this routine doesn't create temporaries, it just builds a
2752    single access expression for the array, calling
2753    find_or_generate_expression to build the innermost pieces.
2754 
2755    This function is a subroutine of create_expression_by_pieces, and
2756    should not be called on it's own unless you really know what you
2757    are doing.  */
2758 
2759 static tree
create_component_ref_by_pieces(basic_block block,vn_reference_t ref,gimple_seq * stmts)2760 create_component_ref_by_pieces (basic_block block, vn_reference_t ref,
2761 				gimple_seq *stmts)
2762 {
2763   unsigned int op = 0;
2764   return create_component_ref_by_pieces_1 (block, ref, &op, stmts);
2765 }
2766 
2767 /* Find a simple leader for an expression, or generate one using
2768    create_expression_by_pieces from a NARY expression for the value.
2769    BLOCK is the basic_block we are looking for leaders in.
2770    OP is the tree expression to find a leader for or generate.
2771    Returns the leader or NULL_TREE on failure.  */
2772 
2773 static tree
find_or_generate_expression(basic_block block,tree op,gimple_seq * stmts)2774 find_or_generate_expression (basic_block block, tree op, gimple_seq *stmts)
2775 {
2776   /* Constants are always leaders.  */
2777   if (is_gimple_min_invariant (op))
2778     return op;
2779 
2780   gcc_assert (TREE_CODE (op) == SSA_NAME);
2781   vn_ssa_aux_t info = VN_INFO (op);
2782   unsigned int lookfor = info->value_id;
2783   if (value_id_constant_p (lookfor))
2784     return info->valnum;
2785 
2786   pre_expr leader = bitmap_find_leader (AVAIL_OUT (block), lookfor);
2787   if (leader)
2788     {
2789       if (leader->kind == NAME)
2790 	return PRE_EXPR_NAME (leader);
2791       else if (leader->kind == CONSTANT)
2792 	return PRE_EXPR_CONSTANT (leader);
2793 
2794       /* Defer.  */
2795       return NULL_TREE;
2796     }
2797   gcc_assert (!value_id_constant_p (lookfor));
2798 
2799   /* It must be a complex expression, so generate it recursively.  Note
2800      that this is only necessary to handle gcc.dg/tree-ssa/ssa-pre28.c
2801      where the insert algorithm fails to insert a required expression.  */
2802   bitmap exprset = value_expressions[lookfor];
2803   bitmap_iterator bi;
2804   unsigned int i;
2805   EXECUTE_IF_SET_IN_BITMAP (exprset, 0, i, bi)
2806     {
2807       pre_expr temp = expression_for_id (i);
2808       /* We cannot insert random REFERENCE expressions at arbitrary
2809 	 places.  We can insert NARYs which eventually re-materializes
2810 	 its operand values.  */
2811       if (temp->kind == NARY)
2812 	return create_expression_by_pieces (block, temp, stmts,
2813 					    TREE_TYPE (op));
2814     }
2815 
2816   /* Defer.  */
2817   return NULL_TREE;
2818 }
2819 
2820 /* Create an expression in pieces, so that we can handle very complex
2821    expressions that may be ANTIC, but not necessary GIMPLE.
2822    BLOCK is the basic block the expression will be inserted into,
2823    EXPR is the expression to insert (in value form)
2824    STMTS is a statement list to append the necessary insertions into.
2825 
2826    This function will die if we hit some value that shouldn't be
2827    ANTIC but is (IE there is no leader for it, or its components).
2828    The function returns NULL_TREE in case a different antic expression
2829    has to be inserted first.
2830    This function may also generate expressions that are themselves
2831    partially or fully redundant.  Those that are will be either made
2832    fully redundant during the next iteration of insert (for partially
2833    redundant ones), or eliminated by eliminate (for fully redundant
2834    ones).  */
2835 
2836 static tree
create_expression_by_pieces(basic_block block,pre_expr expr,gimple_seq * stmts,tree type)2837 create_expression_by_pieces (basic_block block, pre_expr expr,
2838 			     gimple_seq *stmts, tree type)
2839 {
2840   tree name;
2841   tree folded;
2842   gimple_seq forced_stmts = NULL;
2843   unsigned int value_id;
2844   gimple_stmt_iterator gsi;
2845   tree exprtype = type ? type : get_expr_type (expr);
2846   pre_expr nameexpr;
2847   gassign *newstmt;
2848 
2849   switch (expr->kind)
2850     {
2851     /* We may hit the NAME/CONSTANT case if we have to convert types
2852        that value numbering saw through.  */
2853     case NAME:
2854       folded = PRE_EXPR_NAME (expr);
2855       if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (folded))
2856 	return NULL_TREE;
2857       if (useless_type_conversion_p (exprtype, TREE_TYPE (folded)))
2858 	return folded;
2859       break;
2860     case CONSTANT:
2861       {
2862 	folded = PRE_EXPR_CONSTANT (expr);
2863 	tree tem = fold_convert (exprtype, folded);
2864 	if (is_gimple_min_invariant (tem))
2865 	  return tem;
2866 	break;
2867       }
2868     case REFERENCE:
2869       if (PRE_EXPR_REFERENCE (expr)->operands[0].opcode == CALL_EXPR)
2870 	{
2871 	  vn_reference_t ref = PRE_EXPR_REFERENCE (expr);
2872 	  unsigned int operand = 1;
2873 	  vn_reference_op_t currop = &ref->operands[0];
2874 	  tree sc = NULL_TREE;
2875 	  tree fn = NULL_TREE;
2876 	  if (currop->op0)
2877 	    {
2878 	      fn = find_or_generate_expression (block, currop->op0, stmts);
2879 	      if (!fn)
2880 		return NULL_TREE;
2881 	    }
2882 	  if (currop->op1)
2883 	    {
2884 	      sc = find_or_generate_expression (block, currop->op1, stmts);
2885 	      if (!sc)
2886 		return NULL_TREE;
2887 	    }
2888 	  auto_vec<tree> args (ref->operands.length () - 1);
2889 	  while (operand < ref->operands.length ())
2890 	    {
2891 	      tree arg = create_component_ref_by_pieces_1 (block, ref,
2892 							   &operand, stmts);
2893 	      if (!arg)
2894 		return NULL_TREE;
2895 	      args.quick_push (arg);
2896 	    }
2897 	  gcall *call;
2898 	  if (currop->op0)
2899 	    {
2900 	      call = gimple_build_call_vec (fn, args);
2901 	      gimple_call_set_fntype (call, currop->type);
2902 	    }
2903 	  else
2904 	    call = gimple_build_call_internal_vec ((internal_fn)currop->clique,
2905 						   args);
2906 	  gimple_set_location (call, expr->loc);
2907 	  if (sc)
2908 	    gimple_call_set_chain (call, sc);
2909 	  tree forcedname = make_ssa_name (ref->type);
2910 	  gimple_call_set_lhs (call, forcedname);
2911 	  /* There's no CCP pass after PRE which would re-compute alignment
2912 	     information so make sure we re-materialize this here.  */
2913 	  if (gimple_call_builtin_p (call, BUILT_IN_ASSUME_ALIGNED)
2914 	      && args.length () - 2 <= 1
2915 	      && tree_fits_uhwi_p (args[1])
2916 	      && (args.length () != 3 || tree_fits_uhwi_p (args[2])))
2917 	    {
2918 	      unsigned HOST_WIDE_INT halign = tree_to_uhwi (args[1]);
2919 	      unsigned HOST_WIDE_INT hmisalign
2920 		= args.length () == 3 ? tree_to_uhwi (args[2]) : 0;
2921 	      if ((halign & (halign - 1)) == 0
2922 		  && (hmisalign & ~(halign - 1)) == 0
2923 		  && (unsigned int)halign != 0)
2924 		set_ptr_info_alignment (get_ptr_info (forcedname),
2925 					halign, hmisalign);
2926 	    }
2927 	  gimple_set_vuse (call, BB_LIVE_VOP_ON_EXIT (block));
2928 	  gimple_seq_add_stmt_without_update (&forced_stmts, call);
2929 	  folded = forcedname;
2930 	}
2931       else
2932 	{
2933 	  folded = create_component_ref_by_pieces (block,
2934 						   PRE_EXPR_REFERENCE (expr),
2935 						   stmts);
2936 	  if (!folded)
2937 	    return NULL_TREE;
2938 	  name = make_temp_ssa_name (exprtype, NULL, "pretmp");
2939 	  newstmt = gimple_build_assign (name, folded);
2940 	  gimple_set_location (newstmt, expr->loc);
2941 	  gimple_seq_add_stmt_without_update (&forced_stmts, newstmt);
2942 	  gimple_set_vuse (newstmt, BB_LIVE_VOP_ON_EXIT (block));
2943 	  folded = name;
2944 	}
2945       break;
2946     case NARY:
2947       {
2948 	vn_nary_op_t nary = PRE_EXPR_NARY (expr);
2949 	tree *genop = XALLOCAVEC (tree, nary->length);
2950 	unsigned i;
2951 	for (i = 0; i < nary->length; ++i)
2952 	  {
2953 	    genop[i] = find_or_generate_expression (block, nary->op[i], stmts);
2954 	    if (!genop[i])
2955 	      return NULL_TREE;
2956 	    /* Ensure genop[] is properly typed for POINTER_PLUS_EXPR.  It
2957 	       may have conversions stripped.  */
2958 	    if (nary->opcode == POINTER_PLUS_EXPR)
2959 	      {
2960 		if (i == 0)
2961 		  genop[i] = gimple_convert (&forced_stmts,
2962 					     nary->type, genop[i]);
2963 		else if (i == 1)
2964 		  genop[i] = gimple_convert (&forced_stmts,
2965 					     sizetype, genop[i]);
2966 	      }
2967 	    else
2968 	      genop[i] = gimple_convert (&forced_stmts,
2969 					 TREE_TYPE (nary->op[i]), genop[i]);
2970 	  }
2971 	if (nary->opcode == CONSTRUCTOR)
2972 	  {
2973 	    vec<constructor_elt, va_gc> *elts = NULL;
2974 	    for (i = 0; i < nary->length; ++i)
2975 	      CONSTRUCTOR_APPEND_ELT (elts, NULL_TREE, genop[i]);
2976 	    folded = build_constructor (nary->type, elts);
2977 	    name = make_temp_ssa_name (exprtype, NULL, "pretmp");
2978 	    newstmt = gimple_build_assign (name, folded);
2979 	    gimple_set_location (newstmt, expr->loc);
2980 	    gimple_seq_add_stmt_without_update (&forced_stmts, newstmt);
2981 	    folded = name;
2982 	  }
2983 	else
2984 	  {
2985 	    switch (nary->length)
2986 	      {
2987 	      case 1:
2988 		folded = gimple_build (&forced_stmts, expr->loc,
2989 				       nary->opcode, nary->type, genop[0]);
2990 		break;
2991 	      case 2:
2992 		folded = gimple_build (&forced_stmts, expr->loc, nary->opcode,
2993 				       nary->type, genop[0], genop[1]);
2994 		break;
2995 	      case 3:
2996 		folded = gimple_build (&forced_stmts, expr->loc, nary->opcode,
2997 				       nary->type, genop[0], genop[1],
2998 				       genop[2]);
2999 		break;
3000 	      default:
3001 		gcc_unreachable ();
3002 	      }
3003 	  }
3004       }
3005       break;
3006     default:
3007       gcc_unreachable ();
3008     }
3009 
3010   folded = gimple_convert (&forced_stmts, exprtype, folded);
3011 
3012   /* If there is nothing to insert, return the simplified result.  */
3013   if (gimple_seq_empty_p (forced_stmts))
3014     return folded;
3015   /* If we simplified to a constant return it and discard eventually
3016      built stmts.  */
3017   if (is_gimple_min_invariant (folded))
3018     {
3019       gimple_seq_discard (forced_stmts);
3020       return folded;
3021     }
3022   /* Likewise if we simplified to sth not queued for insertion.  */
3023   bool found = false;
3024   gsi = gsi_last (forced_stmts);
3025   for (; !gsi_end_p (gsi); gsi_prev (&gsi))
3026     {
3027       gimple *stmt = gsi_stmt (gsi);
3028       tree forcedname = gimple_get_lhs (stmt);
3029       if (forcedname == folded)
3030 	{
3031 	  found = true;
3032 	  break;
3033 	}
3034     }
3035   if (! found)
3036     {
3037       gimple_seq_discard (forced_stmts);
3038       return folded;
3039     }
3040   gcc_assert (TREE_CODE (folded) == SSA_NAME);
3041 
3042   /* If we have any intermediate expressions to the value sets, add them
3043      to the value sets and chain them in the instruction stream.  */
3044   if (forced_stmts)
3045     {
3046       gsi = gsi_start (forced_stmts);
3047       for (; !gsi_end_p (gsi); gsi_next (&gsi))
3048 	{
3049 	  gimple *stmt = gsi_stmt (gsi);
3050 	  tree forcedname = gimple_get_lhs (stmt);
3051 	  pre_expr nameexpr;
3052 
3053 	  if (forcedname != folded)
3054 	    {
3055 	      vn_ssa_aux_t vn_info = VN_INFO (forcedname);
3056 	      vn_info->valnum = forcedname;
3057 	      vn_info->value_id = get_next_value_id ();
3058 	      nameexpr = get_or_alloc_expr_for_name (forcedname);
3059 	      add_to_value (vn_info->value_id, nameexpr);
3060 	      if (NEW_SETS (block))
3061 		bitmap_value_replace_in_set (NEW_SETS (block), nameexpr);
3062 	      bitmap_value_replace_in_set (AVAIL_OUT (block), nameexpr);
3063 	    }
3064 
3065 	  bitmap_set_bit (inserted_exprs, SSA_NAME_VERSION (forcedname));
3066 	}
3067       gimple_seq_add_seq (stmts, forced_stmts);
3068     }
3069 
3070   name = folded;
3071 
3072   /* Fold the last statement.  */
3073   gsi = gsi_last (*stmts);
3074   if (fold_stmt_inplace (&gsi))
3075     update_stmt (gsi_stmt (gsi));
3076 
3077   /* Add a value number to the temporary.
3078      The value may already exist in either NEW_SETS, or AVAIL_OUT, because
3079      we are creating the expression by pieces, and this particular piece of
3080      the expression may have been represented.  There is no harm in replacing
3081      here.  */
3082   value_id = get_expr_value_id (expr);
3083   vn_ssa_aux_t vn_info = VN_INFO (name);
3084   vn_info->value_id = value_id;
3085   vn_info->valnum = vn_valnum_from_value_id (value_id);
3086   if (vn_info->valnum == NULL_TREE)
3087     vn_info->valnum = name;
3088   gcc_assert (vn_info->valnum != NULL_TREE);
3089   nameexpr = get_or_alloc_expr_for_name (name);
3090   add_to_value (value_id, nameexpr);
3091   if (NEW_SETS (block))
3092     bitmap_value_replace_in_set (NEW_SETS (block), nameexpr);
3093   bitmap_value_replace_in_set (AVAIL_OUT (block), nameexpr);
3094 
3095   pre_stats.insertions++;
3096   if (dump_file && (dump_flags & TDF_DETAILS))
3097     {
3098       fprintf (dump_file, "Inserted ");
3099       print_gimple_stmt (dump_file, gsi_stmt (gsi_last (*stmts)), 0);
3100       fprintf (dump_file, " in predecessor %d (%04d)\n",
3101 	       block->index, value_id);
3102     }
3103 
3104   return name;
3105 }
3106 
3107 
3108 /* Insert the to-be-made-available values of expression EXPRNUM for each
3109    predecessor, stored in AVAIL, into the predecessors of BLOCK, and
3110    merge the result with a phi node, given the same value number as
3111    NODE.  Return true if we have inserted new stuff.  */
3112 
3113 static bool
insert_into_preds_of_block(basic_block block,unsigned int exprnum,vec<pre_expr> & avail)3114 insert_into_preds_of_block (basic_block block, unsigned int exprnum,
3115 			    vec<pre_expr> &avail)
3116 {
3117   pre_expr expr = expression_for_id (exprnum);
3118   pre_expr newphi;
3119   unsigned int val = get_expr_value_id (expr);
3120   edge pred;
3121   bool insertions = false;
3122   bool nophi = false;
3123   basic_block bprime;
3124   pre_expr eprime;
3125   edge_iterator ei;
3126   tree type = get_expr_type (expr);
3127   tree temp;
3128   gphi *phi;
3129 
3130   /* Make sure we aren't creating an induction variable.  */
3131   if (bb_loop_depth (block) > 0 && EDGE_COUNT (block->preds) == 2)
3132     {
3133       bool firstinsideloop = false;
3134       bool secondinsideloop = false;
3135       firstinsideloop = flow_bb_inside_loop_p (block->loop_father,
3136 					       EDGE_PRED (block, 0)->src);
3137       secondinsideloop = flow_bb_inside_loop_p (block->loop_father,
3138 						EDGE_PRED (block, 1)->src);
3139       /* Induction variables only have one edge inside the loop.  */
3140       if ((firstinsideloop ^ secondinsideloop)
3141 	  && expr->kind != REFERENCE)
3142 	{
3143 	  if (dump_file && (dump_flags & TDF_DETAILS))
3144 	    fprintf (dump_file, "Skipping insertion of phi for partial "
3145 		     "redundancy: Looks like an induction variable\n");
3146 	  nophi = true;
3147 	}
3148     }
3149 
3150   /* Make the necessary insertions.  */
3151   FOR_EACH_EDGE (pred, ei, block->preds)
3152     {
3153       /* When we are not inserting a PHI node do not bother inserting
3154 	 into places that do not dominate the anticipated computations.  */
3155       if (nophi && !dominated_by_p (CDI_DOMINATORS, block, pred->src))
3156 	continue;
3157       gimple_seq stmts = NULL;
3158       tree builtexpr;
3159       bprime = pred->src;
3160       eprime = avail[pred->dest_idx];
3161       builtexpr = create_expression_by_pieces (bprime, eprime,
3162 					       &stmts, type);
3163       gcc_assert (!(pred->flags & EDGE_ABNORMAL));
3164       if (!gimple_seq_empty_p (stmts))
3165 	{
3166 	  basic_block new_bb = gsi_insert_seq_on_edge_immediate (pred, stmts);
3167 	  gcc_assert (! new_bb);
3168 	  insertions = true;
3169 	}
3170       if (!builtexpr)
3171 	{
3172 	  /* We cannot insert a PHI node if we failed to insert
3173 	     on one edge.  */
3174 	  nophi = true;
3175 	  continue;
3176 	}
3177       if (is_gimple_min_invariant (builtexpr))
3178 	avail[pred->dest_idx] = get_or_alloc_expr_for_constant (builtexpr);
3179       else
3180 	avail[pred->dest_idx] = get_or_alloc_expr_for_name (builtexpr);
3181     }
3182   /* If we didn't want a phi node, and we made insertions, we still have
3183      inserted new stuff, and thus return true.  If we didn't want a phi node,
3184      and didn't make insertions, we haven't added anything new, so return
3185      false.  */
3186   if (nophi && insertions)
3187     return true;
3188   else if (nophi && !insertions)
3189     return false;
3190 
3191   /* Now build a phi for the new variable.  */
3192   temp = make_temp_ssa_name (type, NULL, "prephitmp");
3193   phi = create_phi_node (temp, block);
3194 
3195   vn_ssa_aux_t vn_info = VN_INFO (temp);
3196   vn_info->value_id = val;
3197   vn_info->valnum = vn_valnum_from_value_id (val);
3198   if (vn_info->valnum == NULL_TREE)
3199     vn_info->valnum = temp;
3200   bitmap_set_bit (inserted_exprs, SSA_NAME_VERSION (temp));
3201   FOR_EACH_EDGE (pred, ei, block->preds)
3202     {
3203       pre_expr ae = avail[pred->dest_idx];
3204       gcc_assert (get_expr_type (ae) == type
3205 		  || useless_type_conversion_p (type, get_expr_type (ae)));
3206       if (ae->kind == CONSTANT)
3207 	add_phi_arg (phi, unshare_expr (PRE_EXPR_CONSTANT (ae)),
3208 		     pred, UNKNOWN_LOCATION);
3209       else
3210 	add_phi_arg (phi, PRE_EXPR_NAME (ae), pred, UNKNOWN_LOCATION);
3211     }
3212 
3213   newphi = get_or_alloc_expr_for_name (temp);
3214   add_to_value (val, newphi);
3215 
3216   /* The value should *not* exist in PHI_GEN, or else we wouldn't be doing
3217      this insertion, since we test for the existence of this value in PHI_GEN
3218      before proceeding with the partial redundancy checks in insert_aux.
3219 
3220      The value may exist in AVAIL_OUT, in particular, it could be represented
3221      by the expression we are trying to eliminate, in which case we want the
3222      replacement to occur.  If it's not existing in AVAIL_OUT, we want it
3223      inserted there.
3224 
3225      Similarly, to the PHI_GEN case, the value should not exist in NEW_SETS of
3226      this block, because if it did, it would have existed in our dominator's
3227      AVAIL_OUT, and would have been skipped due to the full redundancy check.
3228   */
3229 
3230   bitmap_insert_into_set (PHI_GEN (block), newphi);
3231   bitmap_value_replace_in_set (AVAIL_OUT (block),
3232 			       newphi);
3233   if (NEW_SETS (block))
3234     bitmap_insert_into_set (NEW_SETS (block), newphi);
3235 
3236   /* If we insert a PHI node for a conversion of another PHI node
3237      in the same basic-block try to preserve range information.
3238      This is important so that followup loop passes receive optimal
3239      number of iteration analysis results.  See PR61743.  */
3240   if (expr->kind == NARY
3241       && CONVERT_EXPR_CODE_P (expr->u.nary->opcode)
3242       && TREE_CODE (expr->u.nary->op[0]) == SSA_NAME
3243       && gimple_bb (SSA_NAME_DEF_STMT (expr->u.nary->op[0])) == block
3244       && INTEGRAL_TYPE_P (type)
3245       && INTEGRAL_TYPE_P (TREE_TYPE (expr->u.nary->op[0]))
3246       && (TYPE_PRECISION (type)
3247 	  >= TYPE_PRECISION (TREE_TYPE (expr->u.nary->op[0])))
3248       && SSA_NAME_RANGE_INFO (expr->u.nary->op[0]))
3249     {
3250       value_range r;
3251       if (get_range_query (cfun)->range_of_expr (r, expr->u.nary->op[0])
3252 	  && r.kind () == VR_RANGE
3253 	  && !wi::neg_p (r.lower_bound (), SIGNED)
3254 	  && !wi::neg_p (r.upper_bound (), SIGNED))
3255 	/* Just handle extension and sign-changes of all-positive ranges.  */
3256 	set_range_info (temp, VR_RANGE,
3257 			wide_int_storage::from (r.lower_bound (),
3258 						TYPE_PRECISION (type),
3259 						TYPE_SIGN (type)),
3260 			wide_int_storage::from (r.upper_bound (),
3261 						TYPE_PRECISION (type),
3262 						TYPE_SIGN (type)));
3263     }
3264 
3265   if (dump_file && (dump_flags & TDF_DETAILS))
3266     {
3267       fprintf (dump_file, "Created phi ");
3268       print_gimple_stmt (dump_file, phi, 0);
3269       fprintf (dump_file, " in block %d (%04d)\n", block->index, val);
3270     }
3271   pre_stats.phis++;
3272   return true;
3273 }
3274 
3275 
3276 
3277 /* Perform insertion of partially redundant or hoistable values.
3278    For BLOCK, do the following:
3279    1.  Propagate the NEW_SETS of the dominator into the current block.
3280    If the block has multiple predecessors,
3281        2a. Iterate over the ANTIC expressions for the block to see if
3282 	   any of them are partially redundant.
3283        2b. If so, insert them into the necessary predecessors to make
3284 	   the expression fully redundant.
3285        2c. Insert a new PHI merging the values of the predecessors.
3286        2d. Insert the new PHI, and the new expressions, into the
3287 	   NEW_SETS set.
3288    If the block has multiple successors,
3289        3a. Iterate over the ANTIC values for the block to see if
3290 	   any of them are good candidates for hoisting.
3291        3b. If so, insert expressions computing the values in BLOCK,
3292 	   and add the new expressions into the NEW_SETS set.
3293    4. Recursively call ourselves on the dominator children of BLOCK.
3294 
3295    Steps 1, 2a, and 4 are done by insert_aux. 2b, 2c and 2d are done by
3296    do_pre_regular_insertion and do_partial_insertion.  3a and 3b are
3297    done in do_hoist_insertion.
3298 */
3299 
3300 static bool
do_pre_regular_insertion(basic_block block,basic_block dom,vec<pre_expr> exprs)3301 do_pre_regular_insertion (basic_block block, basic_block dom,
3302 			  vec<pre_expr> exprs)
3303 {
3304   bool new_stuff = false;
3305   pre_expr expr;
3306   auto_vec<pre_expr, 2> avail;
3307   int i;
3308 
3309   avail.safe_grow (EDGE_COUNT (block->preds), true);
3310 
3311   FOR_EACH_VEC_ELT (exprs, i, expr)
3312     {
3313       if (expr->kind == NARY
3314 	  || expr->kind == REFERENCE)
3315 	{
3316 	  unsigned int val;
3317 	  bool by_some = false;
3318 	  bool cant_insert = false;
3319 	  bool all_same = true;
3320 	  pre_expr first_s = NULL;
3321 	  edge pred;
3322 	  basic_block bprime;
3323 	  pre_expr eprime = NULL;
3324 	  edge_iterator ei;
3325 	  pre_expr edoubleprime = NULL;
3326 	  bool do_insertion = false;
3327 
3328 	  val = get_expr_value_id (expr);
3329 	  if (bitmap_set_contains_value (PHI_GEN (block), val))
3330 	    continue;
3331 	  if (bitmap_set_contains_value (AVAIL_OUT (dom), val))
3332 	    {
3333 	      if (dump_file && (dump_flags & TDF_DETAILS))
3334 		{
3335 		  fprintf (dump_file, "Found fully redundant value: ");
3336 		  print_pre_expr (dump_file, expr);
3337 		  fprintf (dump_file, "\n");
3338 		}
3339 	      continue;
3340 	    }
3341 
3342 	  FOR_EACH_EDGE (pred, ei, block->preds)
3343 	    {
3344 	      unsigned int vprime;
3345 
3346 	      /* We should never run insertion for the exit block
3347 	         and so not come across fake pred edges.  */
3348 	      gcc_assert (!(pred->flags & EDGE_FAKE));
3349 	      bprime = pred->src;
3350 	      /* We are looking at ANTIC_OUT of bprime.  */
3351 	      eprime = phi_translate (NULL, expr, ANTIC_IN (block), NULL, pred);
3352 
3353 	      /* eprime will generally only be NULL if the
3354 		 value of the expression, translated
3355 		 through the PHI for this predecessor, is
3356 		 undefined.  If that is the case, we can't
3357 		 make the expression fully redundant,
3358 		 because its value is undefined along a
3359 		 predecessor path.  We can thus break out
3360 		 early because it doesn't matter what the
3361 		 rest of the results are.  */
3362 	      if (eprime == NULL)
3363 		{
3364 		  avail[pred->dest_idx] = NULL;
3365 		  cant_insert = true;
3366 		  break;
3367 		}
3368 
3369 	      vprime = get_expr_value_id (eprime);
3370 	      edoubleprime = bitmap_find_leader (AVAIL_OUT (bprime),
3371 						 vprime);
3372 	      if (edoubleprime == NULL)
3373 		{
3374 		  avail[pred->dest_idx] = eprime;
3375 		  all_same = false;
3376 		}
3377 	      else
3378 		{
3379 		  avail[pred->dest_idx] = edoubleprime;
3380 		  by_some = true;
3381 		  /* We want to perform insertions to remove a redundancy on
3382 		     a path in the CFG we want to optimize for speed.  */
3383 		  if (optimize_edge_for_speed_p (pred))
3384 		    do_insertion = true;
3385 		  if (first_s == NULL)
3386 		    first_s = edoubleprime;
3387 		  else if (!pre_expr_d::equal (first_s, edoubleprime))
3388 		    all_same = false;
3389 		}
3390 	    }
3391 	  /* If we can insert it, it's not the same value
3392 	     already existing along every predecessor, and
3393 	     it's defined by some predecessor, it is
3394 	     partially redundant.  */
3395 	  if (!cant_insert && !all_same && by_some)
3396 	    {
3397 	      if (!do_insertion)
3398 		{
3399 		  if (dump_file && (dump_flags & TDF_DETAILS))
3400 		    {
3401 		      fprintf (dump_file, "Skipping partial redundancy for "
3402 			       "expression ");
3403 		      print_pre_expr (dump_file, expr);
3404 		      fprintf (dump_file, " (%04d), no redundancy on to be "
3405 			       "optimized for speed edge\n", val);
3406 		    }
3407 		}
3408 	      else if (dbg_cnt (treepre_insert))
3409 		{
3410 		  if (dump_file && (dump_flags & TDF_DETAILS))
3411 		    {
3412 		      fprintf (dump_file, "Found partial redundancy for "
3413 			       "expression ");
3414 		      print_pre_expr (dump_file, expr);
3415 		      fprintf (dump_file, " (%04d)\n",
3416 			       get_expr_value_id (expr));
3417 		    }
3418 		  if (insert_into_preds_of_block (block,
3419 						  get_expression_id (expr),
3420 						  avail))
3421 		    new_stuff = true;
3422 		}
3423 	    }
3424 	  /* If all edges produce the same value and that value is
3425 	     an invariant, then the PHI has the same value on all
3426 	     edges.  Note this.  */
3427 	  else if (!cant_insert
3428 		   && all_same
3429 		   && (edoubleprime->kind != NAME
3430 		       || !SSA_NAME_OCCURS_IN_ABNORMAL_PHI
3431 			     (PRE_EXPR_NAME (edoubleprime))))
3432 	    {
3433 	      gcc_assert (edoubleprime->kind == CONSTANT
3434 			  || edoubleprime->kind == NAME);
3435 
3436 	      tree temp = make_temp_ssa_name (get_expr_type (expr),
3437 					      NULL, "pretmp");
3438 	      gassign *assign
3439 		= gimple_build_assign (temp,
3440 				       edoubleprime->kind == CONSTANT ?
3441 				       PRE_EXPR_CONSTANT (edoubleprime) :
3442 				       PRE_EXPR_NAME (edoubleprime));
3443 	      gimple_stmt_iterator gsi = gsi_after_labels (block);
3444 	      gsi_insert_before (&gsi, assign, GSI_NEW_STMT);
3445 
3446 	      vn_ssa_aux_t vn_info = VN_INFO (temp);
3447 	      vn_info->value_id = val;
3448 	      vn_info->valnum = vn_valnum_from_value_id (val);
3449 	      if (vn_info->valnum == NULL_TREE)
3450 		vn_info->valnum = temp;
3451 	      bitmap_set_bit (inserted_exprs, SSA_NAME_VERSION (temp));
3452 	      pre_expr newe = get_or_alloc_expr_for_name (temp);
3453 	      add_to_value (val, newe);
3454 	      bitmap_value_replace_in_set (AVAIL_OUT (block), newe);
3455 	      bitmap_insert_into_set (NEW_SETS (block), newe);
3456 	      bitmap_insert_into_set (PHI_GEN (block), newe);
3457 	    }
3458 	}
3459     }
3460 
3461   return new_stuff;
3462 }
3463 
3464 
3465 /* Perform insertion for partially anticipatable expressions.  There
3466    is only one case we will perform insertion for these.  This case is
3467    if the expression is partially anticipatable, and fully available.
3468    In this case, we know that putting it earlier will enable us to
3469    remove the later computation.  */
3470 
3471 static bool
do_pre_partial_partial_insertion(basic_block block,basic_block dom,vec<pre_expr> exprs)3472 do_pre_partial_partial_insertion (basic_block block, basic_block dom,
3473 				  vec<pre_expr> exprs)
3474 {
3475   bool new_stuff = false;
3476   pre_expr expr;
3477   auto_vec<pre_expr, 2> avail;
3478   int i;
3479 
3480   avail.safe_grow (EDGE_COUNT (block->preds), true);
3481 
3482   FOR_EACH_VEC_ELT (exprs, i, expr)
3483     {
3484       if (expr->kind == NARY
3485 	  || expr->kind == REFERENCE)
3486 	{
3487 	  unsigned int val;
3488 	  bool by_all = true;
3489 	  bool cant_insert = false;
3490 	  edge pred;
3491 	  basic_block bprime;
3492 	  pre_expr eprime = NULL;
3493 	  edge_iterator ei;
3494 
3495 	  val = get_expr_value_id (expr);
3496 	  if (bitmap_set_contains_value (PHI_GEN (block), val))
3497 	    continue;
3498 	  if (bitmap_set_contains_value (AVAIL_OUT (dom), val))
3499 	    continue;
3500 
3501 	  FOR_EACH_EDGE (pred, ei, block->preds)
3502 	    {
3503 	      unsigned int vprime;
3504 	      pre_expr edoubleprime;
3505 
3506 	      /* We should never run insertion for the exit block
3507 	         and so not come across fake pred edges.  */
3508 	      gcc_assert (!(pred->flags & EDGE_FAKE));
3509 	      bprime = pred->src;
3510 	      eprime = phi_translate (NULL, expr, ANTIC_IN (block),
3511 				      PA_IN (block), pred);
3512 
3513 	      /* eprime will generally only be NULL if the
3514 		 value of the expression, translated
3515 		 through the PHI for this predecessor, is
3516 		 undefined.  If that is the case, we can't
3517 		 make the expression fully redundant,
3518 		 because its value is undefined along a
3519 		 predecessor path.  We can thus break out
3520 		 early because it doesn't matter what the
3521 		 rest of the results are.  */
3522 	      if (eprime == NULL)
3523 		{
3524 		  avail[pred->dest_idx] = NULL;
3525 		  cant_insert = true;
3526 		  break;
3527 		}
3528 
3529 	      vprime = get_expr_value_id (eprime);
3530 	      edoubleprime = bitmap_find_leader (AVAIL_OUT (bprime), vprime);
3531 	      avail[pred->dest_idx] = edoubleprime;
3532 	      if (edoubleprime == NULL)
3533 		{
3534 		  by_all = false;
3535 		  break;
3536 		}
3537 	    }
3538 
3539 	  /* If we can insert it, it's not the same value
3540 	     already existing along every predecessor, and
3541 	     it's defined by some predecessor, it is
3542 	     partially redundant.  */
3543 	  if (!cant_insert && by_all)
3544 	    {
3545 	      edge succ;
3546 	      bool do_insertion = false;
3547 
3548 	      /* Insert only if we can remove a later expression on a path
3549 		 that we want to optimize for speed.
3550 		 The phi node that we will be inserting in BLOCK is not free,
3551 		 and inserting it for the sake of !optimize_for_speed successor
3552 		 may cause regressions on the speed path.  */
3553 	      FOR_EACH_EDGE (succ, ei, block->succs)
3554 		{
3555 		  if (bitmap_set_contains_value (PA_IN (succ->dest), val)
3556 		      || bitmap_set_contains_value (ANTIC_IN (succ->dest), val))
3557 		    {
3558 		      if (optimize_edge_for_speed_p (succ))
3559 			do_insertion = true;
3560 		    }
3561 		}
3562 
3563 	      if (!do_insertion)
3564 		{
3565 		  if (dump_file && (dump_flags & TDF_DETAILS))
3566 		    {
3567 		      fprintf (dump_file, "Skipping partial partial redundancy "
3568 			       "for expression ");
3569 		      print_pre_expr (dump_file, expr);
3570 		      fprintf (dump_file, " (%04d), not (partially) anticipated "
3571 			       "on any to be optimized for speed edges\n", val);
3572 		    }
3573 		}
3574 	      else if (dbg_cnt (treepre_insert))
3575 		{
3576 		  pre_stats.pa_insert++;
3577 		  if (dump_file && (dump_flags & TDF_DETAILS))
3578 		    {
3579 		      fprintf (dump_file, "Found partial partial redundancy "
3580 			       "for expression ");
3581 		      print_pre_expr (dump_file, expr);
3582 		      fprintf (dump_file, " (%04d)\n",
3583 			       get_expr_value_id (expr));
3584 		    }
3585 		  if (insert_into_preds_of_block (block,
3586 						  get_expression_id (expr),
3587 						  avail))
3588 		    new_stuff = true;
3589 		}
3590 	    }
3591 	}
3592     }
3593 
3594   return new_stuff;
3595 }
3596 
3597 /* Insert expressions in BLOCK to compute hoistable values up.
3598    Return TRUE if something was inserted, otherwise return FALSE.
3599    The caller has to make sure that BLOCK has at least two successors.  */
3600 
3601 static bool
do_hoist_insertion(basic_block block)3602 do_hoist_insertion (basic_block block)
3603 {
3604   edge e;
3605   edge_iterator ei;
3606   bool new_stuff = false;
3607   unsigned i;
3608   gimple_stmt_iterator last;
3609 
3610   /* At least two successors, or else...  */
3611   gcc_assert (EDGE_COUNT (block->succs) >= 2);
3612 
3613   /* Check that all successors of BLOCK are dominated by block.
3614      We could use dominated_by_p() for this, but actually there is a much
3615      quicker check: any successor that is dominated by BLOCK can't have
3616      more than one predecessor edge.  */
3617   FOR_EACH_EDGE (e, ei, block->succs)
3618     if (! single_pred_p (e->dest))
3619       return false;
3620 
3621   /* Determine the insertion point.  If we cannot safely insert before
3622      the last stmt if we'd have to, bail out.  */
3623   last = gsi_last_bb (block);
3624   if (!gsi_end_p (last)
3625       && !is_ctrl_stmt (gsi_stmt (last))
3626       && stmt_ends_bb_p (gsi_stmt (last)))
3627     return false;
3628 
3629   /* Compute the set of hoistable expressions from ANTIC_IN.  First compute
3630      hoistable values.  */
3631   bitmap_set hoistable_set;
3632 
3633   /* A hoistable value must be in ANTIC_IN(block)
3634      but not in AVAIL_OUT(BLOCK).  */
3635   bitmap_initialize (&hoistable_set.values, &grand_bitmap_obstack);
3636   bitmap_and_compl (&hoistable_set.values,
3637 		    &ANTIC_IN (block)->values, &AVAIL_OUT (block)->values);
3638 
3639   /* Short-cut for a common case: hoistable_set is empty.  */
3640   if (bitmap_empty_p (&hoistable_set.values))
3641     return false;
3642 
3643   /* Compute which of the hoistable values is in AVAIL_OUT of
3644      at least one of the successors of BLOCK.  */
3645   bitmap_head availout_in_some;
3646   bitmap_initialize (&availout_in_some, &grand_bitmap_obstack);
3647   FOR_EACH_EDGE (e, ei, block->succs)
3648     /* Do not consider expressions solely because their availability
3649        on loop exits.  They'd be ANTIC-IN throughout the whole loop
3650        and thus effectively hoisted across loops by combination of
3651        PRE and hoisting.  */
3652     if (! loop_exit_edge_p (block->loop_father, e))
3653       bitmap_ior_and_into (&availout_in_some, &hoistable_set.values,
3654 			   &AVAIL_OUT (e->dest)->values);
3655   bitmap_clear (&hoistable_set.values);
3656 
3657   /* Short-cut for a common case: availout_in_some is empty.  */
3658   if (bitmap_empty_p (&availout_in_some))
3659     return false;
3660 
3661   /* Hack hoitable_set in-place so we can use sorted_array_from_bitmap_set.  */
3662   bitmap_move (&hoistable_set.values, &availout_in_some);
3663   hoistable_set.expressions = ANTIC_IN (block)->expressions;
3664 
3665   /* Now finally construct the topological-ordered expression set.  */
3666   vec<pre_expr> exprs = sorted_array_from_bitmap_set (&hoistable_set);
3667 
3668   bitmap_clear (&hoistable_set.values);
3669 
3670   /* If there are candidate values for hoisting, insert expressions
3671      strategically to make the hoistable expressions fully redundant.  */
3672   pre_expr expr;
3673   FOR_EACH_VEC_ELT (exprs, i, expr)
3674     {
3675       /* While we try to sort expressions topologically above the
3676          sorting doesn't work out perfectly.  Catch expressions we
3677 	 already inserted.  */
3678       unsigned int value_id = get_expr_value_id (expr);
3679       if (bitmap_set_contains_value (AVAIL_OUT (block), value_id))
3680 	{
3681 	  if (dump_file && (dump_flags & TDF_DETAILS))
3682 	    {
3683 	      fprintf (dump_file,
3684 		       "Already inserted expression for ");
3685 	      print_pre_expr (dump_file, expr);
3686 	      fprintf (dump_file, " (%04d)\n", value_id);
3687 	    }
3688 	  continue;
3689 	}
3690 
3691       /* If we end up with a punned expression representation and this
3692 	 happens to be a float typed one give up - we can't know for
3693 	 sure whether all paths perform the floating-point load we are
3694 	 about to insert and on some targets this can cause correctness
3695 	 issues.  See PR88240.  */
3696       if (expr->kind == REFERENCE
3697 	  && PRE_EXPR_REFERENCE (expr)->punned
3698 	  && FLOAT_TYPE_P (get_expr_type (expr)))
3699 	continue;
3700 
3701       /* OK, we should hoist this value.  Perform the transformation.  */
3702       pre_stats.hoist_insert++;
3703       if (dump_file && (dump_flags & TDF_DETAILS))
3704 	{
3705 	  fprintf (dump_file,
3706 		   "Inserting expression in block %d for code hoisting: ",
3707 		   block->index);
3708 	  print_pre_expr (dump_file, expr);
3709 	  fprintf (dump_file, " (%04d)\n", value_id);
3710 	}
3711 
3712       gimple_seq stmts = NULL;
3713       tree res = create_expression_by_pieces (block, expr, &stmts,
3714 					      get_expr_type (expr));
3715 
3716       /* Do not return true if expression creation ultimately
3717          did not insert any statements.  */
3718       if (gimple_seq_empty_p (stmts))
3719 	res = NULL_TREE;
3720       else
3721 	{
3722 	  if (gsi_end_p (last) || is_ctrl_stmt (gsi_stmt (last)))
3723 	    gsi_insert_seq_before (&last, stmts, GSI_SAME_STMT);
3724 	  else
3725 	    gsi_insert_seq_after (&last, stmts, GSI_NEW_STMT);
3726 	}
3727 
3728       /* Make sure to not return true if expression creation ultimately
3729          failed but also make sure to insert any stmts produced as they
3730 	 are tracked in inserted_exprs.  */
3731       if (! res)
3732 	continue;
3733 
3734       new_stuff = true;
3735     }
3736 
3737   exprs.release ();
3738 
3739   return new_stuff;
3740 }
3741 
3742 /* Perform insertion of partially redundant and hoistable values.  */
3743 
3744 static void
insert(void)3745 insert (void)
3746 {
3747   basic_block bb;
3748 
3749   FOR_ALL_BB_FN (bb, cfun)
3750     NEW_SETS (bb) = bitmap_set_new ();
3751 
3752   int *rpo = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
3753   int *bb_rpo = XNEWVEC (int, last_basic_block_for_fn (cfun) + 1);
3754   int rpo_num = pre_and_rev_post_order_compute (NULL, rpo, false);
3755   for (int i = 0; i < rpo_num; ++i)
3756     bb_rpo[rpo[i]] = i;
3757 
3758   int num_iterations = 0;
3759   bool changed;
3760   do
3761     {
3762       num_iterations++;
3763       if (dump_file && dump_flags & TDF_DETAILS)
3764 	fprintf (dump_file, "Starting insert iteration %d\n", num_iterations);
3765 
3766       changed = false;
3767       for (int idx = 0; idx < rpo_num; ++idx)
3768 	{
3769 	  basic_block block = BASIC_BLOCK_FOR_FN (cfun, rpo[idx]);
3770 	  basic_block dom = get_immediate_dominator (CDI_DOMINATORS, block);
3771 	  if (dom)
3772 	    {
3773 	      unsigned i;
3774 	      bitmap_iterator bi;
3775 	      bitmap_set_t newset;
3776 
3777 	      /* First, update the AVAIL_OUT set with anything we may have
3778 		 inserted higher up in the dominator tree.  */
3779 	      newset = NEW_SETS (dom);
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 	      bool avail_out_changed = false;
3786 	      FOR_EACH_EXPR_ID_IN_SET (newset, i, bi)
3787 		{
3788 		  pre_expr expr = expression_for_id (i);
3789 		  bitmap_value_replace_in_set (NEW_SETS (block), expr);
3790 		  avail_out_changed
3791 		    |= bitmap_value_replace_in_set (AVAIL_OUT (block), expr);
3792 		}
3793 	      /* We need to iterate if AVAIL_OUT of an already processed
3794 		 block source changed.  */
3795 	      if (avail_out_changed && !changed)
3796 		{
3797 		  edge_iterator ei;
3798 		  edge e;
3799 		  FOR_EACH_EDGE (e, ei, block->succs)
3800 		    if (e->dest->index != EXIT_BLOCK
3801 			&& bb_rpo[e->dest->index] < idx)
3802 		      changed = true;
3803 		}
3804 
3805 	      /* Insert expressions for partial redundancies.  */
3806 	      if (flag_tree_pre && !single_pred_p (block))
3807 		{
3808 		  vec<pre_expr> exprs
3809 		    = sorted_array_from_bitmap_set (ANTIC_IN (block));
3810 		  /* Sorting is not perfect, iterate locally.  */
3811 		  while (do_pre_regular_insertion (block, dom, exprs))
3812 		    ;
3813 		  exprs.release ();
3814 		  if (do_partial_partial)
3815 		    {
3816 		      exprs = sorted_array_from_bitmap_set (PA_IN (block));
3817 		      while (do_pre_partial_partial_insertion (block, dom,
3818 							       exprs))
3819 			;
3820 		      exprs.release ();
3821 		    }
3822 		}
3823 	    }
3824 	}
3825 
3826       /* Clear the NEW sets before the next iteration.  We have already
3827 	 fully propagated its contents.  */
3828       if (changed)
3829 	FOR_ALL_BB_FN (bb, cfun)
3830 	  bitmap_set_free (NEW_SETS (bb));
3831     }
3832   while (changed);
3833 
3834   statistics_histogram_event (cfun, "insert iterations", num_iterations);
3835 
3836   /* AVAIL_OUT is not needed after insertion so we don't have to
3837      propagate NEW_SETS from hoist insertion.  */
3838   FOR_ALL_BB_FN (bb, cfun)
3839     {
3840       bitmap_set_free (NEW_SETS (bb));
3841       bitmap_set_pool.remove (NEW_SETS (bb));
3842       NEW_SETS (bb) = NULL;
3843     }
3844 
3845   /* Insert expressions for hoisting.  Do a backward walk here since
3846      inserting into BLOCK exposes new opportunities in its predecessors.
3847      Since PRE and hoist insertions can cause back-to-back iteration
3848      and we are interested in PRE insertion exposed hoisting opportunities
3849      but not in hoisting exposed PRE ones do hoist insertion only after
3850      PRE insertion iteration finished and do not iterate it.  */
3851   if (flag_code_hoisting)
3852     for (int idx = rpo_num - 1; idx >= 0; --idx)
3853       {
3854 	basic_block block = BASIC_BLOCK_FOR_FN (cfun, rpo[idx]);
3855 	if (EDGE_COUNT (block->succs) >= 2)
3856 	  changed |= do_hoist_insertion (block);
3857       }
3858 
3859   free (rpo);
3860   free (bb_rpo);
3861 }
3862 
3863 
3864 /* Compute the AVAIL set for all basic blocks.
3865 
3866    This function performs value numbering of the statements in each basic
3867    block.  The AVAIL sets are built from information we glean while doing
3868    this value numbering, since the AVAIL sets contain only one entry per
3869    value.
3870 
3871    AVAIL_IN[BLOCK] = AVAIL_OUT[dom(BLOCK)].
3872    AVAIL_OUT[BLOCK] = AVAIL_IN[BLOCK] U PHI_GEN[BLOCK] U TMP_GEN[BLOCK].  */
3873 
3874 static void
compute_avail(function * fun)3875 compute_avail (function *fun)
3876 {
3877 
3878   basic_block block, son;
3879   basic_block *worklist;
3880   size_t sp = 0;
3881   unsigned i;
3882   tree name;
3883 
3884   /* We pretend that default definitions are defined in the entry block.
3885      This includes function arguments and the static chain decl.  */
3886   FOR_EACH_SSA_NAME (i, name, fun)
3887     {
3888       pre_expr e;
3889       if (!SSA_NAME_IS_DEFAULT_DEF (name)
3890 	  || has_zero_uses (name)
3891 	  || virtual_operand_p (name))
3892 	continue;
3893 
3894       e = get_or_alloc_expr_for_name (name);
3895       add_to_value (get_expr_value_id (e), e);
3896       bitmap_insert_into_set (TMP_GEN (ENTRY_BLOCK_PTR_FOR_FN (fun)), e);
3897       bitmap_value_insert_into_set (AVAIL_OUT (ENTRY_BLOCK_PTR_FOR_FN (fun)),
3898 				    e);
3899     }
3900 
3901   if (dump_file && (dump_flags & TDF_DETAILS))
3902     {
3903       print_bitmap_set (dump_file, TMP_GEN (ENTRY_BLOCK_PTR_FOR_FN (fun)),
3904 			"tmp_gen", ENTRY_BLOCK);
3905       print_bitmap_set (dump_file, AVAIL_OUT (ENTRY_BLOCK_PTR_FOR_FN (fun)),
3906 			"avail_out", ENTRY_BLOCK);
3907     }
3908 
3909   /* Allocate the worklist.  */
3910   worklist = XNEWVEC (basic_block, n_basic_blocks_for_fn (fun));
3911 
3912   /* Seed the algorithm by putting the dominator children of the entry
3913      block on the worklist.  */
3914   for (son = first_dom_son (CDI_DOMINATORS, ENTRY_BLOCK_PTR_FOR_FN (fun));
3915        son;
3916        son = next_dom_son (CDI_DOMINATORS, son))
3917     worklist[sp++] = son;
3918 
3919   BB_LIVE_VOP_ON_EXIT (ENTRY_BLOCK_PTR_FOR_FN (fun))
3920     = ssa_default_def (fun, gimple_vop (fun));
3921 
3922   /* Loop until the worklist is empty.  */
3923   while (sp)
3924     {
3925       gimple *stmt;
3926       basic_block dom;
3927 
3928       /* Pick a block from the worklist.  */
3929       block = worklist[--sp];
3930       vn_context_bb = block;
3931 
3932       /* Initially, the set of available values in BLOCK is that of
3933 	 its immediate dominator.  */
3934       dom = get_immediate_dominator (CDI_DOMINATORS, block);
3935       if (dom)
3936 	{
3937 	  bitmap_set_copy (AVAIL_OUT (block), AVAIL_OUT (dom));
3938 	  BB_LIVE_VOP_ON_EXIT (block) = BB_LIVE_VOP_ON_EXIT (dom);
3939 	}
3940 
3941       /* Generate values for PHI nodes.  */
3942       for (gphi_iterator gsi = gsi_start_phis (block); !gsi_end_p (gsi);
3943 	   gsi_next (&gsi))
3944 	{
3945 	  tree result = gimple_phi_result (gsi.phi ());
3946 
3947 	  /* We have no need for virtual phis, as they don't represent
3948 	     actual computations.  */
3949 	  if (virtual_operand_p (result))
3950 	    {
3951 	      BB_LIVE_VOP_ON_EXIT (block) = result;
3952 	      continue;
3953 	    }
3954 
3955 	  pre_expr e = get_or_alloc_expr_for_name (result);
3956 	  add_to_value (get_expr_value_id (e), e);
3957 	  bitmap_value_insert_into_set (AVAIL_OUT (block), e);
3958 	  bitmap_insert_into_set (PHI_GEN (block), e);
3959 	}
3960 
3961       BB_MAY_NOTRETURN (block) = 0;
3962 
3963       /* Now compute value numbers and populate value sets with all
3964 	 the expressions computed in BLOCK.  */
3965       bool set_bb_may_notreturn = false;
3966       for (gimple_stmt_iterator gsi = gsi_start_bb (block); !gsi_end_p (gsi);
3967 	   gsi_next (&gsi))
3968 	{
3969 	  ssa_op_iter iter;
3970 	  tree op;
3971 
3972 	  stmt = gsi_stmt (gsi);
3973 
3974 	  if (set_bb_may_notreturn)
3975 	    {
3976 	      BB_MAY_NOTRETURN (block) = 1;
3977 	      set_bb_may_notreturn = false;
3978 	    }
3979 
3980 	  /* Cache whether the basic-block has any non-visible side-effect
3981 	     or control flow.
3982 	     If this isn't a call or it is the last stmt in the
3983 	     basic-block then the CFG represents things correctly.  */
3984 	  if (is_gimple_call (stmt) && !stmt_ends_bb_p (stmt))
3985 	    {
3986 	      /* Non-looping const functions always return normally.
3987 		 Otherwise the call might not return or have side-effects
3988 		 that forbids hoisting possibly trapping expressions
3989 		 before it.  */
3990 	      int flags = gimple_call_flags (stmt);
3991 	      if (!(flags & (ECF_CONST|ECF_PURE))
3992 		  || (flags & ECF_LOOPING_CONST_OR_PURE)
3993 		  || stmt_can_throw_external (fun, stmt))
3994 		/* Defer setting of BB_MAY_NOTRETURN to avoid it
3995 		   influencing the processing of the call itself.  */
3996 		set_bb_may_notreturn = true;
3997 	    }
3998 
3999 	  FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_DEF)
4000 	    {
4001 	      pre_expr e = get_or_alloc_expr_for_name (op);
4002 	      add_to_value (get_expr_value_id (e), e);
4003 	      bitmap_insert_into_set (TMP_GEN (block), e);
4004 	      bitmap_value_insert_into_set (AVAIL_OUT (block), e);
4005 	    }
4006 
4007 	  if (gimple_vdef (stmt))
4008 	    BB_LIVE_VOP_ON_EXIT (block) = gimple_vdef (stmt);
4009 
4010 	  if (gimple_has_side_effects (stmt)
4011 	      || stmt_could_throw_p (fun, stmt)
4012 	      || is_gimple_debug (stmt))
4013 	    continue;
4014 
4015 	  FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_USE)
4016 	    {
4017 	      if (ssa_undefined_value_p (op))
4018 		continue;
4019 	      pre_expr e = get_or_alloc_expr_for_name (op);
4020 	      bitmap_value_insert_into_set (EXP_GEN (block), e);
4021 	    }
4022 
4023 	  switch (gimple_code (stmt))
4024 	    {
4025 	    case GIMPLE_RETURN:
4026 	      continue;
4027 
4028 	    case GIMPLE_CALL:
4029 	      {
4030 		vn_reference_t ref;
4031 		vn_reference_s ref1;
4032 		pre_expr result = NULL;
4033 
4034 		vn_reference_lookup_call (as_a <gcall *> (stmt), &ref, &ref1);
4035 		/* There is no point to PRE a call without a value.  */
4036 		if (!ref || !ref->result)
4037 		  continue;
4038 
4039 		/* If the value of the call is not invalidated in
4040 		   this block until it is computed, add the expression
4041 		   to EXP_GEN.  */
4042 		if ((!gimple_vuse (stmt)
4043 		     || gimple_code
4044 			  (SSA_NAME_DEF_STMT (gimple_vuse (stmt))) == GIMPLE_PHI
4045 		     || gimple_bb (SSA_NAME_DEF_STMT
4046 				   (gimple_vuse (stmt))) != block)
4047 		    /* If the REFERENCE traps and there was a preceding
4048 		       point in the block that might not return avoid
4049 		       adding the reference to EXP_GEN.  */
4050 		    && (!BB_MAY_NOTRETURN (block)
4051 			|| !vn_reference_may_trap (ref)))
4052 		  {
4053 		    result = get_or_alloc_expr_for_reference
4054 			       (ref, gimple_location (stmt));
4055 		    add_to_value (get_expr_value_id (result), result);
4056 		    bitmap_value_insert_into_set (EXP_GEN (block), result);
4057 		  }
4058 		continue;
4059 	      }
4060 
4061 	    case GIMPLE_ASSIGN:
4062 	      {
4063 		pre_expr result = NULL;
4064 		switch (vn_get_stmt_kind (stmt))
4065 		  {
4066 		  case VN_NARY:
4067 		    {
4068 		      enum tree_code code = gimple_assign_rhs_code (stmt);
4069 		      vn_nary_op_t nary;
4070 
4071 		      /* COND_EXPR is awkward in that it contains an
4072 			 embedded complex expression.
4073 			 Don't even try to shove it through PRE.  */
4074 		      if (code == COND_EXPR)
4075 			continue;
4076 
4077 		      vn_nary_op_lookup_stmt (stmt, &nary);
4078 		      if (!nary || nary->predicated_values)
4079 			continue;
4080 
4081 		      unsigned value_id = nary->value_id;
4082 		      if (value_id_constant_p (value_id))
4083 			continue;
4084 
4085 		      /* Record the un-valueized expression for EXP_GEN.  */
4086 		      nary = XALLOCAVAR (struct vn_nary_op_s,
4087 					 sizeof_vn_nary_op
4088 					   (vn_nary_length_from_stmt (stmt)));
4089 		      init_vn_nary_op_from_stmt (nary, as_a <gassign *> (stmt));
4090 
4091 		      /* If the NARY traps and there was a preceding
4092 		         point in the block that might not return avoid
4093 			 adding the nary to EXP_GEN.  */
4094 		      if (BB_MAY_NOTRETURN (block)
4095 			  && vn_nary_may_trap (nary))
4096 			continue;
4097 
4098 		      result = get_or_alloc_expr_for_nary
4099 				 (nary, value_id, gimple_location (stmt));
4100 		      break;
4101 		    }
4102 
4103 		  case VN_REFERENCE:
4104 		    {
4105 		      tree rhs1 = gimple_assign_rhs1 (stmt);
4106 		      ao_ref rhs1_ref;
4107 		      ao_ref_init (&rhs1_ref, rhs1);
4108 		      alias_set_type set = ao_ref_alias_set (&rhs1_ref);
4109 		      alias_set_type base_set
4110 			= ao_ref_base_alias_set (&rhs1_ref);
4111 		      vec<vn_reference_op_s> operands
4112 			= vn_reference_operands_for_lookup (rhs1);
4113 		      vn_reference_t ref;
4114 		      vn_reference_lookup_pieces (gimple_vuse (stmt), set,
4115 						  base_set, TREE_TYPE (rhs1),
4116 						  operands, &ref, VN_WALK);
4117 		      if (!ref)
4118 			{
4119 			  operands.release ();
4120 			  continue;
4121 			}
4122 
4123 		      /* If the REFERENCE traps and there was a preceding
4124 		         point in the block that might not return avoid
4125 			 adding the reference to EXP_GEN.  */
4126 		      if (BB_MAY_NOTRETURN (block)
4127 			  && vn_reference_may_trap (ref))
4128 			{
4129 			  operands.release ();
4130 			  continue;
4131 			}
4132 
4133 		      /* If the value of the reference is not invalidated in
4134 			 this block until it is computed, add the expression
4135 			 to EXP_GEN.  */
4136 		      if (gimple_vuse (stmt))
4137 			{
4138 			  gimple *def_stmt;
4139 			  bool ok = true;
4140 			  def_stmt = SSA_NAME_DEF_STMT (gimple_vuse (stmt));
4141 			  while (!gimple_nop_p (def_stmt)
4142 				 && gimple_code (def_stmt) != GIMPLE_PHI
4143 				 && gimple_bb (def_stmt) == block)
4144 			    {
4145 			      if (stmt_may_clobber_ref_p
4146 				    (def_stmt, gimple_assign_rhs1 (stmt)))
4147 				{
4148 				  ok = false;
4149 				  break;
4150 				}
4151 			      def_stmt
4152 				= SSA_NAME_DEF_STMT (gimple_vuse (def_stmt));
4153 			    }
4154 			  if (!ok)
4155 			    {
4156 			      operands.release ();
4157 			      continue;
4158 			    }
4159 			}
4160 
4161 		      /* If the load was value-numbered to another
4162 			 load make sure we do not use its expression
4163 			 for insertion if it wouldn't be a valid
4164 			 replacement.  */
4165 		      /* At the momemt we have a testcase
4166 			 for hoist insertion of aligned vs. misaligned
4167 			 variants in gcc.dg/torture/pr65270-1.c thus
4168 			 with just alignment to be considered we can
4169 			 simply replace the expression in the hashtable
4170 			 with the most conservative one.  */
4171 		      vn_reference_op_t ref1 = &ref->operands.last ();
4172 		      while (ref1->opcode != TARGET_MEM_REF
4173 			     && ref1->opcode != MEM_REF
4174 			     && ref1 != &ref->operands[0])
4175 			--ref1;
4176 		      vn_reference_op_t ref2 = &operands.last ();
4177 		      while (ref2->opcode != TARGET_MEM_REF
4178 			     && ref2->opcode != MEM_REF
4179 			     && ref2 != &operands[0])
4180 			--ref2;
4181 		      if ((ref1->opcode == TARGET_MEM_REF
4182 			   || ref1->opcode == MEM_REF)
4183 			  && (TYPE_ALIGN (ref1->type)
4184 			      > TYPE_ALIGN (ref2->type)))
4185 			ref1->type
4186 			  = build_aligned_type (ref1->type,
4187 						TYPE_ALIGN (ref2->type));
4188 		      /* TBAA behavior is an obvious part so make sure
4189 		         that the hashtable one covers this as well
4190 			 by adjusting the ref alias set and its base.  */
4191 		      if (ref->set == set
4192 			  || alias_set_subset_of (set, ref->set))
4193 			;
4194 		      else if (ref1->opcode != ref2->opcode
4195 			       || (ref1->opcode != MEM_REF
4196 				   && ref1->opcode != TARGET_MEM_REF))
4197 			{
4198 			  /* With mismatching base opcodes or bases
4199 			     other than MEM_REF or TARGET_MEM_REF we
4200 			     can't do any easy TBAA adjustment.  */
4201 			  operands.release ();
4202 			  continue;
4203 			}
4204 		      else if (alias_set_subset_of (ref->set, set))
4205 			{
4206 			  ref->set = set;
4207 			  if (ref1->opcode == MEM_REF)
4208 			    ref1->op0
4209 			      = wide_int_to_tree (TREE_TYPE (ref2->op0),
4210 						  wi::to_wide (ref1->op0));
4211 			  else
4212 			    ref1->op2
4213 			      = wide_int_to_tree (TREE_TYPE (ref2->op2),
4214 						  wi::to_wide (ref1->op2));
4215 			}
4216 		      else
4217 			{
4218 			  ref->set = 0;
4219 			  ref->base_set = 0;
4220 			  if (ref1->opcode == MEM_REF)
4221 			    ref1->op0
4222 			      = wide_int_to_tree (ptr_type_node,
4223 						  wi::to_wide (ref1->op0));
4224 			  else
4225 			    ref1->op2
4226 			      = wide_int_to_tree (ptr_type_node,
4227 						  wi::to_wide (ref1->op2));
4228 			}
4229 		      operands.release ();
4230 
4231 		      result = get_or_alloc_expr_for_reference
4232 				 (ref, gimple_location (stmt));
4233 		      break;
4234 		    }
4235 
4236 		  default:
4237 		    continue;
4238 		  }
4239 
4240 		add_to_value (get_expr_value_id (result), result);
4241 		bitmap_value_insert_into_set (EXP_GEN (block), result);
4242 		continue;
4243 	      }
4244 	    default:
4245 	      break;
4246 	    }
4247 	}
4248       if (set_bb_may_notreturn)
4249 	{
4250 	  BB_MAY_NOTRETURN (block) = 1;
4251 	  set_bb_may_notreturn = false;
4252 	}
4253 
4254       if (dump_file && (dump_flags & TDF_DETAILS))
4255 	{
4256 	  print_bitmap_set (dump_file, EXP_GEN (block),
4257 			    "exp_gen", block->index);
4258 	  print_bitmap_set (dump_file, PHI_GEN (block),
4259 			    "phi_gen", block->index);
4260 	  print_bitmap_set (dump_file, TMP_GEN (block),
4261 			    "tmp_gen", block->index);
4262 	  print_bitmap_set (dump_file, AVAIL_OUT (block),
4263 			    "avail_out", block->index);
4264 	}
4265 
4266       /* Put the dominator children of BLOCK on the worklist of blocks
4267 	 to compute available sets for.  */
4268       for (son = first_dom_son (CDI_DOMINATORS, block);
4269 	   son;
4270 	   son = next_dom_son (CDI_DOMINATORS, son))
4271 	worklist[sp++] = son;
4272     }
4273   vn_context_bb = NULL;
4274 
4275   free (worklist);
4276 }
4277 
4278 
4279 /* Initialize data structures used by PRE.  */
4280 
4281 static void
init_pre(void)4282 init_pre (void)
4283 {
4284   basic_block bb;
4285 
4286   next_expression_id = 1;
4287   expressions.create (0);
4288   expressions.safe_push (NULL);
4289   value_expressions.create (get_max_value_id () + 1);
4290   value_expressions.quick_grow_cleared (get_max_value_id () + 1);
4291   constant_value_expressions.create (get_max_constant_value_id () + 1);
4292   constant_value_expressions.quick_grow_cleared (get_max_constant_value_id () + 1);
4293   name_to_id.create (0);
4294   gcc_obstack_init (&pre_expr_obstack);
4295 
4296   inserted_exprs = BITMAP_ALLOC (NULL);
4297 
4298   connect_infinite_loops_to_exit ();
4299   memset (&pre_stats, 0, sizeof (pre_stats));
4300 
4301   alloc_aux_for_blocks (sizeof (struct bb_bitmap_sets));
4302 
4303   calculate_dominance_info (CDI_DOMINATORS);
4304 
4305   bitmap_obstack_initialize (&grand_bitmap_obstack);
4306   expression_to_id = new hash_table<pre_expr_d> (num_ssa_names * 3);
4307   FOR_ALL_BB_FN (bb, cfun)
4308     {
4309       EXP_GEN (bb) = bitmap_set_new ();
4310       PHI_GEN (bb) = bitmap_set_new ();
4311       TMP_GEN (bb) = bitmap_set_new ();
4312       AVAIL_OUT (bb) = bitmap_set_new ();
4313       PHI_TRANS_TABLE (bb) = NULL;
4314     }
4315 }
4316 
4317 
4318 /* Deallocate data structures used by PRE.  */
4319 
4320 static void
fini_pre()4321 fini_pre ()
4322 {
4323   value_expressions.release ();
4324   constant_value_expressions.release ();
4325   expressions.release ();
4326   bitmap_obstack_release (&grand_bitmap_obstack);
4327   bitmap_set_pool.release ();
4328   pre_expr_pool.release ();
4329   delete expression_to_id;
4330   expression_to_id = NULL;
4331   name_to_id.release ();
4332   obstack_free (&pre_expr_obstack, NULL);
4333 
4334   basic_block bb;
4335   FOR_ALL_BB_FN (bb, cfun)
4336     if (bb->aux && PHI_TRANS_TABLE (bb))
4337       delete PHI_TRANS_TABLE (bb);
4338   free_aux_for_blocks ();
4339 }
4340 
4341 namespace {
4342 
4343 const pass_data pass_data_pre =
4344 {
4345   GIMPLE_PASS, /* type */
4346   "pre", /* name */
4347   OPTGROUP_NONE, /* optinfo_flags */
4348   TV_TREE_PRE, /* tv_id */
4349   ( PROP_cfg | PROP_ssa ), /* properties_required */
4350   0, /* properties_provided */
4351   0, /* properties_destroyed */
4352   TODO_rebuild_alias, /* todo_flags_start */
4353   0, /* todo_flags_finish */
4354 };
4355 
4356 class pass_pre : public gimple_opt_pass
4357 {
4358 public:
pass_pre(gcc::context * ctxt)4359   pass_pre (gcc::context *ctxt)
4360     : gimple_opt_pass (pass_data_pre, ctxt)
4361   {}
4362 
4363   /* opt_pass methods: */
gate(function *)4364   virtual bool gate (function *)
4365     { return flag_tree_pre != 0 || flag_code_hoisting != 0; }
4366   virtual unsigned int execute (function *);
4367 
4368 }; // class pass_pre
4369 
4370 /* Valueization hook for RPO VN when we are calling back to it
4371    at ANTIC compute time.  */
4372 
4373 static tree
pre_valueize(tree name)4374 pre_valueize (tree name)
4375 {
4376   if (TREE_CODE (name) == SSA_NAME)
4377     {
4378       tree tem = VN_INFO (name)->valnum;
4379       if (tem != VN_TOP && tem != name)
4380 	{
4381 	  if (TREE_CODE (tem) != SSA_NAME
4382 	      || SSA_NAME_IS_DEFAULT_DEF (tem))
4383 	    return tem;
4384 	  /* We create temporary SSA names for representatives that
4385 	     do not have a definition (yet) but are not default defs either
4386 	     assume they are fine to use.  */
4387 	  basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (tem));
4388 	  if (! def_bb
4389 	      || dominated_by_p (CDI_DOMINATORS, vn_context_bb, def_bb))
4390 	    return tem;
4391 	  /* ??? Now we could look for a leader.  Ideally we'd somehow
4392 	     expose RPO VN leaders and get rid of AVAIL_OUT as well...  */
4393 	}
4394     }
4395   return name;
4396 }
4397 
4398 unsigned int
execute(function * fun)4399 pass_pre::execute (function *fun)
4400 {
4401   unsigned int todo = 0;
4402 
4403   do_partial_partial =
4404     flag_tree_partial_pre && optimize_function_for_speed_p (fun);
4405 
4406   /* This has to happen before VN runs because
4407      loop_optimizer_init may create new phis, etc.  */
4408   loop_optimizer_init (LOOPS_NORMAL);
4409   split_edges_for_insertion ();
4410   scev_initialize ();
4411   calculate_dominance_info (CDI_DOMINATORS);
4412 
4413   run_rpo_vn (VN_WALK);
4414 
4415   init_pre ();
4416 
4417   vn_valueize = pre_valueize;
4418 
4419   /* Insert can get quite slow on an incredibly large number of basic
4420      blocks due to some quadratic behavior.  Until this behavior is
4421      fixed, don't run it when he have an incredibly large number of
4422      bb's.  If we aren't going to run insert, there is no point in
4423      computing ANTIC, either, even though it's plenty fast nor do
4424      we require AVAIL.  */
4425   if (n_basic_blocks_for_fn (fun) < 4000)
4426     {
4427       compute_avail (fun);
4428       compute_antic ();
4429       insert ();
4430     }
4431 
4432   /* Make sure to remove fake edges before committing our inserts.
4433      This makes sure we don't end up with extra critical edges that
4434      we would need to split.  */
4435   remove_fake_exit_edges ();
4436   gsi_commit_edge_inserts ();
4437 
4438   /* Eliminate folds statements which might (should not...) end up
4439      not keeping virtual operands up-to-date.  */
4440   gcc_assert (!need_ssa_update_p (fun));
4441 
4442   statistics_counter_event (fun, "Insertions", pre_stats.insertions);
4443   statistics_counter_event (fun, "PA inserted", pre_stats.pa_insert);
4444   statistics_counter_event (fun, "HOIST inserted", pre_stats.hoist_insert);
4445   statistics_counter_event (fun, "New PHIs", pre_stats.phis);
4446 
4447   todo |= eliminate_with_rpo_vn (inserted_exprs);
4448 
4449   vn_valueize = NULL;
4450 
4451   fini_pre ();
4452 
4453   scev_finalize ();
4454   loop_optimizer_finalize ();
4455 
4456   /* Perform a CFG cleanup before we run simple_dce_from_worklist since
4457      unreachable code regions will have not up-to-date SSA form which
4458      confuses it.  */
4459   bool need_crit_edge_split = false;
4460   if (todo & TODO_cleanup_cfg)
4461     {
4462       cleanup_tree_cfg ();
4463       need_crit_edge_split = true;
4464     }
4465 
4466   /* Because we don't follow exactly the standard PRE algorithm, and decide not
4467      to insert PHI nodes sometimes, and because value numbering of casts isn't
4468      perfect, we sometimes end up inserting dead code.   This simple DCE-like
4469      pass removes any insertions we made that weren't actually used.  */
4470   simple_dce_from_worklist (inserted_exprs);
4471   BITMAP_FREE (inserted_exprs);
4472 
4473   /* TODO: tail_merge_optimize may merge all predecessors of a block, in which
4474      case we can merge the block with the remaining predecessor of the block.
4475      It should either:
4476      - call merge_blocks after each tail merge iteration
4477      - call merge_blocks after all tail merge iterations
4478      - mark TODO_cleanup_cfg when necessary.  */
4479   todo |= tail_merge_optimize (need_crit_edge_split);
4480 
4481   free_rpo_vn ();
4482 
4483   /* Tail merging invalidates the virtual SSA web, together with
4484      cfg-cleanup opportunities exposed by PRE this will wreck the
4485      SSA updating machinery.  So make sure to run update-ssa
4486      manually, before eventually scheduling cfg-cleanup as part of
4487      the todo.  */
4488   update_ssa (TODO_update_ssa_only_virtuals);
4489 
4490   return todo;
4491 }
4492 
4493 } // anon namespace
4494 
4495 gimple_opt_pass *
make_pass_pre(gcc::context * ctxt)4496 make_pass_pre (gcc::context *ctxt)
4497 {
4498   return new pass_pre (ctxt);
4499 }
4500