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