1 |
12 |
jlechner |
/* SSA-PRE for trees.
|
2 |
|
|
Copyright (C) 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
|
3 |
|
|
Contributed by Daniel Berlin <dan@dberlin.org> and Steven Bosscher
|
4 |
|
|
<stevenb@suse.de>
|
5 |
|
|
|
6 |
|
|
This file is part of GCC.
|
7 |
|
|
|
8 |
|
|
GCC is free software; you can redistribute it and/or modify
|
9 |
|
|
it under the terms of the GNU General Public License as published by
|
10 |
|
|
the Free Software Foundation; either version 2, or (at your option)
|
11 |
|
|
any later version.
|
12 |
|
|
|
13 |
|
|
GCC is distributed in the hope that it will be useful,
|
14 |
|
|
but WITHOUT ANY WARRANTY; without even the implied warranty of
|
15 |
|
|
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
16 |
|
|
GNU General Public License for more details.
|
17 |
|
|
|
18 |
|
|
You should have received a copy of the GNU General Public License
|
19 |
|
|
along with GCC; see the file COPYING. If not, write to
|
20 |
|
|
the Free Software Foundation, 51 Franklin Street, Fifth Floor,
|
21 |
|
|
Boston, MA 02110-1301, USA. */
|
22 |
|
|
|
23 |
|
|
#include "config.h"
|
24 |
|
|
#include "system.h"
|
25 |
|
|
#include "coretypes.h"
|
26 |
|
|
#include "tm.h"
|
27 |
|
|
#include "ggc.h"
|
28 |
|
|
#include "tree.h"
|
29 |
|
|
#include "basic-block.h"
|
30 |
|
|
#include "diagnostic.h"
|
31 |
|
|
#include "tree-inline.h"
|
32 |
|
|
#include "tree-flow.h"
|
33 |
|
|
#include "tree-gimple.h"
|
34 |
|
|
#include "tree-dump.h"
|
35 |
|
|
#include "timevar.h"
|
36 |
|
|
#include "fibheap.h"
|
37 |
|
|
#include "hashtab.h"
|
38 |
|
|
#include "tree-iterator.h"
|
39 |
|
|
#include "real.h"
|
40 |
|
|
#include "alloc-pool.h"
|
41 |
|
|
#include "tree-pass.h"
|
42 |
|
|
#include "flags.h"
|
43 |
|
|
#include "bitmap.h"
|
44 |
|
|
#include "langhooks.h"
|
45 |
|
|
#include "cfgloop.h"
|
46 |
|
|
|
47 |
|
|
/* TODO:
|
48 |
|
|
|
49 |
|
|
1. Avail sets can be shared by making an avail_find_leader that
|
50 |
|
|
walks up the dominator tree and looks in those avail sets.
|
51 |
|
|
This might affect code optimality, it's unclear right now.
|
52 |
|
|
2. Load motion can be performed by value numbering the loads the
|
53 |
|
|
same as we do other expressions. This requires iterative
|
54 |
|
|
hashing the vuses into the values. Right now we simply assign
|
55 |
|
|
a new value every time we see a statement with a vuse.
|
56 |
|
|
3. Strength reduction can be performed by anticipating expressions
|
57 |
|
|
we can repair later on.
|
58 |
|
|
4. We can do back-substitution or smarter value numbering to catch
|
59 |
|
|
commutative expressions split up over multiple statements.
|
60 |
|
|
*/
|
61 |
|
|
|
62 |
|
|
/* For ease of terminology, "expression node" in the below refers to
|
63 |
|
|
every expression node but MODIFY_EXPR, because MODIFY_EXPR's represent
|
64 |
|
|
the actual statement containing the expressions we care about, and
|
65 |
|
|
we cache the value number by putting it in the expression. */
|
66 |
|
|
|
67 |
|
|
/* Basic algorithm
|
68 |
|
|
|
69 |
|
|
First we walk the statements to generate the AVAIL sets, the
|
70 |
|
|
EXP_GEN sets, and the tmp_gen sets. EXP_GEN sets represent the
|
71 |
|
|
generation of values/expressions by a given block. We use them
|
72 |
|
|
when computing the ANTIC sets. The AVAIL sets consist of
|
73 |
|
|
SSA_NAME's that represent values, so we know what values are
|
74 |
|
|
available in what blocks. AVAIL is a forward dataflow problem. In
|
75 |
|
|
SSA, values are never killed, so we don't need a kill set, or a
|
76 |
|
|
fixpoint iteration, in order to calculate the AVAIL sets. In
|
77 |
|
|
traditional parlance, AVAIL sets tell us the downsafety of the
|
78 |
|
|
expressions/values.
|
79 |
|
|
|
80 |
|
|
Next, we generate the ANTIC sets. These sets represent the
|
81 |
|
|
anticipatable expressions. ANTIC is a backwards dataflow
|
82 |
|
|
problem.An expression is anticipatable in a given block if it could
|
83 |
|
|
be generated in that block. This means that if we had to perform
|
84 |
|
|
an insertion in that block, of the value of that expression, we
|
85 |
|
|
could. Calculating the ANTIC sets requires phi translation of
|
86 |
|
|
expressions, because the flow goes backwards through phis. We must
|
87 |
|
|
iterate to a fixpoint of the ANTIC sets, because we have a kill
|
88 |
|
|
set. Even in SSA form, values are not live over the entire
|
89 |
|
|
function, only from their definition point onwards. So we have to
|
90 |
|
|
remove values from the ANTIC set once we go past the definition
|
91 |
|
|
point of the leaders that make them up.
|
92 |
|
|
compute_antic/compute_antic_aux performs this computation.
|
93 |
|
|
|
94 |
|
|
Third, we perform insertions to make partially redundant
|
95 |
|
|
expressions fully redundant.
|
96 |
|
|
|
97 |
|
|
An expression is partially redundant (excluding partial
|
98 |
|
|
anticipation) if:
|
99 |
|
|
|
100 |
|
|
1. It is AVAIL in some, but not all, of the predecessors of a
|
101 |
|
|
given block.
|
102 |
|
|
2. It is ANTIC in all the predecessors.
|
103 |
|
|
|
104 |
|
|
In order to make it fully redundant, we insert the expression into
|
105 |
|
|
the predecessors where it is not available, but is ANTIC.
|
106 |
|
|
insert/insert_aux performs this insertion.
|
107 |
|
|
|
108 |
|
|
Fourth, we eliminate fully redundant expressions.
|
109 |
|
|
This is a simple statement walk that replaces redundant
|
110 |
|
|
calculations with the now available values. */
|
111 |
|
|
|
112 |
|
|
/* Representations of value numbers:
|
113 |
|
|
|
114 |
|
|
Value numbers are represented using the "value handle" approach.
|
115 |
|
|
This means that each SSA_NAME (and for other reasons to be
|
116 |
|
|
disclosed in a moment, expression nodes) has a value handle that
|
117 |
|
|
can be retrieved through get_value_handle. This value handle, *is*
|
118 |
|
|
the value number of the SSA_NAME. You can pointer compare the
|
119 |
|
|
value handles for equivalence purposes.
|
120 |
|
|
|
121 |
|
|
For debugging reasons, the value handle is internally more than
|
122 |
|
|
just a number, it is a VAR_DECL named "value.x", where x is a
|
123 |
|
|
unique number for each value number in use. This allows
|
124 |
|
|
expressions with SSA_NAMES replaced by value handles to still be
|
125 |
|
|
pretty printed in a sane way. They simply print as "value.3 *
|
126 |
|
|
value.5", etc.
|
127 |
|
|
|
128 |
|
|
Expression nodes have value handles associated with them as a
|
129 |
|
|
cache. Otherwise, we'd have to look them up again in the hash
|
130 |
|
|
table This makes significant difference (factor of two or more) on
|
131 |
|
|
some test cases. They can be thrown away after the pass is
|
132 |
|
|
finished. */
|
133 |
|
|
|
134 |
|
|
/* Representation of expressions on value numbers:
|
135 |
|
|
|
136 |
|
|
In some portions of this code, you will notice we allocate "fake"
|
137 |
|
|
analogues to the expression we are value numbering, and replace the
|
138 |
|
|
operands with the values of the expression. Since we work on
|
139 |
|
|
values, and not just names, we canonicalize expressions to value
|
140 |
|
|
expressions for use in the ANTIC sets, the EXP_GEN set, etc.
|
141 |
|
|
|
142 |
|
|
This is theoretically unnecessary, it just saves a bunch of
|
143 |
|
|
repeated get_value_handle and find_leader calls in the remainder of
|
144 |
|
|
the code, trading off temporary memory usage for speed. The tree
|
145 |
|
|
nodes aren't actually creating more garbage, since they are
|
146 |
|
|
allocated in a special pools which are thrown away at the end of
|
147 |
|
|
this pass.
|
148 |
|
|
|
149 |
|
|
All of this also means that if you print the EXP_GEN or ANTIC sets,
|
150 |
|
|
you will see "value.5 + value.7" in the set, instead of "a_55 +
|
151 |
|
|
b_66" or something. The only thing that actually cares about
|
152 |
|
|
seeing the value leaders is phi translation, and it needs to be
|
153 |
|
|
able to find the leader for a value in an arbitrary block, so this
|
154 |
|
|
"value expression" form is perfect for it (otherwise you'd do
|
155 |
|
|
get_value_handle->find_leader->translate->get_value_handle->find_leader).*/
|
156 |
|
|
|
157 |
|
|
|
158 |
|
|
/* Representation of sets:
|
159 |
|
|
|
160 |
|
|
There are currently two types of sets used, hopefully to be unified soon.
|
161 |
|
|
The AVAIL sets do not need to be sorted in any particular order,
|
162 |
|
|
and thus, are simply represented as two bitmaps, one that keeps
|
163 |
|
|
track of values present in the set, and one that keeps track of
|
164 |
|
|
expressions present in the set.
|
165 |
|
|
|
166 |
|
|
The other sets are represented as doubly linked lists kept in topological
|
167 |
|
|
order, with an optional supporting bitmap of values present in the
|
168 |
|
|
set. The sets represent values, and the elements can be values or
|
169 |
|
|
expressions. The elements can appear in different sets, but each
|
170 |
|
|
element can only appear once in each set.
|
171 |
|
|
|
172 |
|
|
Since each node in the set represents a value, we also want to be
|
173 |
|
|
able to map expression, set pairs to something that tells us
|
174 |
|
|
whether the value is present is a set. We use a per-set bitmap for
|
175 |
|
|
that. The value handles also point to a linked list of the
|
176 |
|
|
expressions they represent via a tree annotation. This is mainly
|
177 |
|
|
useful only for debugging, since we don't do identity lookups. */
|
178 |
|
|
|
179 |
|
|
|
180 |
|
|
static bool in_fre = false;
|
181 |
|
|
|
182 |
|
|
/* A value set element. Basically a single linked list of
|
183 |
|
|
expressions/values. */
|
184 |
|
|
typedef struct value_set_node
|
185 |
|
|
{
|
186 |
|
|
/* An expression. */
|
187 |
|
|
tree expr;
|
188 |
|
|
|
189 |
|
|
/* A pointer to the next element of the value set. */
|
190 |
|
|
struct value_set_node *next;
|
191 |
|
|
} *value_set_node_t;
|
192 |
|
|
|
193 |
|
|
|
194 |
|
|
/* A value set. This is a singly linked list of value_set_node
|
195 |
|
|
elements with a possible bitmap that tells us what values exist in
|
196 |
|
|
the set. This set must be kept in topologically sorted order. */
|
197 |
|
|
typedef struct value_set
|
198 |
|
|
{
|
199 |
|
|
/* The head of the list. Used for iterating over the list in
|
200 |
|
|
order. */
|
201 |
|
|
value_set_node_t head;
|
202 |
|
|
|
203 |
|
|
/* The tail of the list. Used for tail insertions, which are
|
204 |
|
|
necessary to keep the set in topologically sorted order because
|
205 |
|
|
of how the set is built. */
|
206 |
|
|
value_set_node_t tail;
|
207 |
|
|
|
208 |
|
|
/* The length of the list. */
|
209 |
|
|
size_t length;
|
210 |
|
|
|
211 |
|
|
/* True if the set is indexed, which means it contains a backing
|
212 |
|
|
bitmap for quick determination of whether certain values exist in the
|
213 |
|
|
set. */
|
214 |
|
|
bool indexed;
|
215 |
|
|
|
216 |
|
|
/* The bitmap of values that exist in the set. May be NULL in an
|
217 |
|
|
empty or non-indexed set. */
|
218 |
|
|
bitmap values;
|
219 |
|
|
|
220 |
|
|
} *value_set_t;
|
221 |
|
|
|
222 |
|
|
|
223 |
|
|
/* An unordered bitmap set. One bitmap tracks values, the other,
|
224 |
|
|
expressions. */
|
225 |
|
|
typedef struct bitmap_set
|
226 |
|
|
{
|
227 |
|
|
bitmap expressions;
|
228 |
|
|
bitmap values;
|
229 |
|
|
} *bitmap_set_t;
|
230 |
|
|
|
231 |
|
|
/* Sets that we need to keep track of. */
|
232 |
|
|
typedef struct bb_value_sets
|
233 |
|
|
{
|
234 |
|
|
/* The EXP_GEN set, which represents expressions/values generated in
|
235 |
|
|
a basic block. */
|
236 |
|
|
value_set_t exp_gen;
|
237 |
|
|
|
238 |
|
|
/* The PHI_GEN set, which represents PHI results generated in a
|
239 |
|
|
basic block. */
|
240 |
|
|
bitmap_set_t phi_gen;
|
241 |
|
|
|
242 |
|
|
/* The TMP_GEN set, which represents results/temporaries generated
|
243 |
|
|
in a basic block. IE the LHS of an expression. */
|
244 |
|
|
bitmap_set_t tmp_gen;
|
245 |
|
|
|
246 |
|
|
/* The AVAIL_OUT set, which represents which values are available in
|
247 |
|
|
a given basic block. */
|
248 |
|
|
bitmap_set_t avail_out;
|
249 |
|
|
|
250 |
|
|
/* The ANTIC_IN set, which represents which values are anticiptable
|
251 |
|
|
in a given basic block. */
|
252 |
|
|
value_set_t antic_in;
|
253 |
|
|
|
254 |
|
|
/* The NEW_SETS set, which is used during insertion to augment the
|
255 |
|
|
AVAIL_OUT set of blocks with the new insertions performed during
|
256 |
|
|
the current iteration. */
|
257 |
|
|
bitmap_set_t new_sets;
|
258 |
|
|
} *bb_value_sets_t;
|
259 |
|
|
|
260 |
|
|
#define EXP_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->exp_gen
|
261 |
|
|
#define PHI_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->phi_gen
|
262 |
|
|
#define TMP_GEN(BB) ((bb_value_sets_t) ((BB)->aux))->tmp_gen
|
263 |
|
|
#define AVAIL_OUT(BB) ((bb_value_sets_t) ((BB)->aux))->avail_out
|
264 |
|
|
#define ANTIC_IN(BB) ((bb_value_sets_t) ((BB)->aux))->antic_in
|
265 |
|
|
#define NEW_SETS(BB) ((bb_value_sets_t) ((BB)->aux))->new_sets
|
266 |
|
|
|
267 |
|
|
/* This structure is used to keep track of statistics on what
|
268 |
|
|
optimization PRE was able to perform. */
|
269 |
|
|
static struct
|
270 |
|
|
{
|
271 |
|
|
/* The number of RHS computations eliminated by PRE. */
|
272 |
|
|
int eliminations;
|
273 |
|
|
|
274 |
|
|
/* The number of new expressions/temporaries generated by PRE. */
|
275 |
|
|
int insertions;
|
276 |
|
|
|
277 |
|
|
/* The number of new PHI nodes added by PRE. */
|
278 |
|
|
int phis;
|
279 |
|
|
|
280 |
|
|
/* The number of values found constant. */
|
281 |
|
|
int constified;
|
282 |
|
|
|
283 |
|
|
} pre_stats;
|
284 |
|
|
|
285 |
|
|
|
286 |
|
|
static tree bitmap_find_leader (bitmap_set_t, tree);
|
287 |
|
|
static tree find_leader (value_set_t, tree);
|
288 |
|
|
static void value_insert_into_set (value_set_t, tree);
|
289 |
|
|
static void bitmap_value_insert_into_set (bitmap_set_t, tree);
|
290 |
|
|
static void bitmap_value_replace_in_set (bitmap_set_t, tree);
|
291 |
|
|
static void insert_into_set (value_set_t, tree);
|
292 |
|
|
static void bitmap_set_copy (bitmap_set_t, bitmap_set_t);
|
293 |
|
|
static bool bitmap_set_contains_value (bitmap_set_t, tree);
|
294 |
|
|
static bitmap_set_t bitmap_set_new (void);
|
295 |
|
|
static value_set_t set_new (bool);
|
296 |
|
|
static bool is_undefined_value (tree);
|
297 |
|
|
static tree create_expression_by_pieces (basic_block, tree, tree);
|
298 |
|
|
|
299 |
|
|
|
300 |
|
|
/* We can add and remove elements and entries to and from sets
|
301 |
|
|
and hash tables, so we use alloc pools for them. */
|
302 |
|
|
|
303 |
|
|
static alloc_pool value_set_pool;
|
304 |
|
|
static alloc_pool bitmap_set_pool;
|
305 |
|
|
static alloc_pool value_set_node_pool;
|
306 |
|
|
static alloc_pool binary_node_pool;
|
307 |
|
|
static alloc_pool unary_node_pool;
|
308 |
|
|
static alloc_pool reference_node_pool;
|
309 |
|
|
static alloc_pool comparison_node_pool;
|
310 |
|
|
static alloc_pool expression_node_pool;
|
311 |
|
|
static alloc_pool list_node_pool;
|
312 |
|
|
static bitmap_obstack grand_bitmap_obstack;
|
313 |
|
|
|
314 |
|
|
/* Set of blocks with statements that have had its EH information
|
315 |
|
|
cleaned up. */
|
316 |
|
|
static bitmap need_eh_cleanup;
|
317 |
|
|
|
318 |
|
|
/* The phi_translate_table caches phi translations for a given
|
319 |
|
|
expression and predecessor. */
|
320 |
|
|
|
321 |
|
|
static htab_t phi_translate_table;
|
322 |
|
|
|
323 |
|
|
/* A three tuple {e, pred, v} used to cache phi translations in the
|
324 |
|
|
phi_translate_table. */
|
325 |
|
|
|
326 |
|
|
typedef struct expr_pred_trans_d
|
327 |
|
|
{
|
328 |
|
|
/* The expression. */
|
329 |
|
|
tree e;
|
330 |
|
|
|
331 |
|
|
/* The predecessor block along which we translated the expression. */
|
332 |
|
|
basic_block pred;
|
333 |
|
|
|
334 |
|
|
/* The value that resulted from the translation. */
|
335 |
|
|
tree v;
|
336 |
|
|
|
337 |
|
|
/* The hashcode for the expression, pred pair. This is cached for
|
338 |
|
|
speed reasons. */
|
339 |
|
|
hashval_t hashcode;
|
340 |
|
|
} *expr_pred_trans_t;
|
341 |
|
|
|
342 |
|
|
/* Return the hash value for a phi translation table entry. */
|
343 |
|
|
|
344 |
|
|
static hashval_t
|
345 |
|
|
expr_pred_trans_hash (const void *p)
|
346 |
|
|
{
|
347 |
|
|
const expr_pred_trans_t ve = (expr_pred_trans_t) p;
|
348 |
|
|
return ve->hashcode;
|
349 |
|
|
}
|
350 |
|
|
|
351 |
|
|
/* Return true if two phi translation table entries are the same.
|
352 |
|
|
P1 and P2 should point to the expr_pred_trans_t's to be compared.*/
|
353 |
|
|
|
354 |
|
|
static int
|
355 |
|
|
expr_pred_trans_eq (const void *p1, const void *p2)
|
356 |
|
|
{
|
357 |
|
|
const expr_pred_trans_t ve1 = (expr_pred_trans_t) p1;
|
358 |
|
|
const expr_pred_trans_t ve2 = (expr_pred_trans_t) p2;
|
359 |
|
|
basic_block b1 = ve1->pred;
|
360 |
|
|
basic_block b2 = ve2->pred;
|
361 |
|
|
|
362 |
|
|
|
363 |
|
|
/* If they are not translations for the same basic block, they can't
|
364 |
|
|
be equal. */
|
365 |
|
|
if (b1 != b2)
|
366 |
|
|
return false;
|
367 |
|
|
|
368 |
|
|
/* If they are for the same basic block, determine if the
|
369 |
|
|
expressions are equal. */
|
370 |
|
|
if (expressions_equal_p (ve1->e, ve2->e))
|
371 |
|
|
return true;
|
372 |
|
|
|
373 |
|
|
return false;
|
374 |
|
|
}
|
375 |
|
|
|
376 |
|
|
/* Search in the phi translation table for the translation of
|
377 |
|
|
expression E in basic block PRED. Return the translated value, if
|
378 |
|
|
found, NULL otherwise. */
|
379 |
|
|
|
380 |
|
|
static inline tree
|
381 |
|
|
phi_trans_lookup (tree e, basic_block pred)
|
382 |
|
|
{
|
383 |
|
|
void **slot;
|
384 |
|
|
struct expr_pred_trans_d ept;
|
385 |
|
|
ept.e = e;
|
386 |
|
|
ept.pred = pred;
|
387 |
|
|
ept.hashcode = vn_compute (e, (unsigned long) pred, NULL);
|
388 |
|
|
slot = htab_find_slot_with_hash (phi_translate_table, &ept, ept.hashcode,
|
389 |
|
|
NO_INSERT);
|
390 |
|
|
if (!slot)
|
391 |
|
|
return NULL;
|
392 |
|
|
else
|
393 |
|
|
return ((expr_pred_trans_t) *slot)->v;
|
394 |
|
|
}
|
395 |
|
|
|
396 |
|
|
|
397 |
|
|
/* Add the tuple mapping from {expression E, basic block PRED} to
|
398 |
|
|
value V, to the phi translation table. */
|
399 |
|
|
|
400 |
|
|
static inline void
|
401 |
|
|
phi_trans_add (tree e, tree v, basic_block pred)
|
402 |
|
|
{
|
403 |
|
|
void **slot;
|
404 |
|
|
expr_pred_trans_t new_pair = xmalloc (sizeof (*new_pair));
|
405 |
|
|
new_pair->e = e;
|
406 |
|
|
new_pair->pred = pred;
|
407 |
|
|
new_pair->v = v;
|
408 |
|
|
new_pair->hashcode = vn_compute (e, (unsigned long) pred, NULL);
|
409 |
|
|
slot = htab_find_slot_with_hash (phi_translate_table, new_pair,
|
410 |
|
|
new_pair->hashcode, INSERT);
|
411 |
|
|
if (*slot)
|
412 |
|
|
free (*slot);
|
413 |
|
|
*slot = (void *) new_pair;
|
414 |
|
|
}
|
415 |
|
|
|
416 |
|
|
|
417 |
|
|
/* Add expression E to the expression set of value V. */
|
418 |
|
|
|
419 |
|
|
void
|
420 |
|
|
add_to_value (tree v, tree e)
|
421 |
|
|
{
|
422 |
|
|
/* Constants have no expression sets. */
|
423 |
|
|
if (is_gimple_min_invariant (v))
|
424 |
|
|
return;
|
425 |
|
|
|
426 |
|
|
if (VALUE_HANDLE_EXPR_SET (v) == NULL)
|
427 |
|
|
VALUE_HANDLE_EXPR_SET (v) = set_new (false);
|
428 |
|
|
|
429 |
|
|
insert_into_set (VALUE_HANDLE_EXPR_SET (v), e);
|
430 |
|
|
}
|
431 |
|
|
|
432 |
|
|
|
433 |
|
|
/* Return true if value V exists in the bitmap for SET. */
|
434 |
|
|
|
435 |
|
|
static inline bool
|
436 |
|
|
value_exists_in_set_bitmap (value_set_t set, tree v)
|
437 |
|
|
{
|
438 |
|
|
if (!set->values)
|
439 |
|
|
return false;
|
440 |
|
|
|
441 |
|
|
return bitmap_bit_p (set->values, VALUE_HANDLE_ID (v));
|
442 |
|
|
}
|
443 |
|
|
|
444 |
|
|
|
445 |
|
|
/* Remove value V from the bitmap for SET. */
|
446 |
|
|
|
447 |
|
|
static void
|
448 |
|
|
value_remove_from_set_bitmap (value_set_t set, tree v)
|
449 |
|
|
{
|
450 |
|
|
gcc_assert (set->indexed);
|
451 |
|
|
|
452 |
|
|
if (!set->values)
|
453 |
|
|
return;
|
454 |
|
|
|
455 |
|
|
bitmap_clear_bit (set->values, VALUE_HANDLE_ID (v));
|
456 |
|
|
}
|
457 |
|
|
|
458 |
|
|
|
459 |
|
|
/* Insert the value number V into the bitmap of values existing in
|
460 |
|
|
SET. */
|
461 |
|
|
|
462 |
|
|
static inline void
|
463 |
|
|
value_insert_into_set_bitmap (value_set_t set, tree v)
|
464 |
|
|
{
|
465 |
|
|
gcc_assert (set->indexed);
|
466 |
|
|
|
467 |
|
|
if (set->values == NULL)
|
468 |
|
|
set->values = BITMAP_ALLOC (&grand_bitmap_obstack);
|
469 |
|
|
|
470 |
|
|
bitmap_set_bit (set->values, VALUE_HANDLE_ID (v));
|
471 |
|
|
}
|
472 |
|
|
|
473 |
|
|
|
474 |
|
|
/* Create a new bitmap set and return it. */
|
475 |
|
|
|
476 |
|
|
static bitmap_set_t
|
477 |
|
|
bitmap_set_new (void)
|
478 |
|
|
{
|
479 |
|
|
bitmap_set_t ret = pool_alloc (bitmap_set_pool);
|
480 |
|
|
ret->expressions = BITMAP_ALLOC (&grand_bitmap_obstack);
|
481 |
|
|
ret->values = BITMAP_ALLOC (&grand_bitmap_obstack);
|
482 |
|
|
return ret;
|
483 |
|
|
}
|
484 |
|
|
|
485 |
|
|
/* Create a new set. */
|
486 |
|
|
|
487 |
|
|
static value_set_t
|
488 |
|
|
set_new (bool indexed)
|
489 |
|
|
{
|
490 |
|
|
value_set_t ret;
|
491 |
|
|
ret = pool_alloc (value_set_pool);
|
492 |
|
|
ret->head = ret->tail = NULL;
|
493 |
|
|
ret->length = 0;
|
494 |
|
|
ret->indexed = indexed;
|
495 |
|
|
ret->values = NULL;
|
496 |
|
|
return ret;
|
497 |
|
|
}
|
498 |
|
|
|
499 |
|
|
/* Insert an expression EXPR into a bitmapped set. */
|
500 |
|
|
|
501 |
|
|
static void
|
502 |
|
|
bitmap_insert_into_set (bitmap_set_t set, tree expr)
|
503 |
|
|
{
|
504 |
|
|
tree val;
|
505 |
|
|
/* XXX: For now, we only let SSA_NAMES into the bitmap sets. */
|
506 |
|
|
gcc_assert (TREE_CODE (expr) == SSA_NAME);
|
507 |
|
|
val = get_value_handle (expr);
|
508 |
|
|
|
509 |
|
|
gcc_assert (val);
|
510 |
|
|
if (!is_gimple_min_invariant (val))
|
511 |
|
|
{
|
512 |
|
|
bitmap_set_bit (set->values, VALUE_HANDLE_ID (val));
|
513 |
|
|
bitmap_set_bit (set->expressions, SSA_NAME_VERSION (expr));
|
514 |
|
|
}
|
515 |
|
|
}
|
516 |
|
|
|
517 |
|
|
/* Insert EXPR into SET. */
|
518 |
|
|
|
519 |
|
|
static void
|
520 |
|
|
insert_into_set (value_set_t set, tree expr)
|
521 |
|
|
{
|
522 |
|
|
value_set_node_t newnode = pool_alloc (value_set_node_pool);
|
523 |
|
|
tree val = get_value_handle (expr);
|
524 |
|
|
gcc_assert (val);
|
525 |
|
|
|
526 |
|
|
if (is_gimple_min_invariant (val))
|
527 |
|
|
return;
|
528 |
|
|
|
529 |
|
|
/* For indexed sets, insert the value into the set value bitmap.
|
530 |
|
|
For all sets, add it to the linked list and increment the list
|
531 |
|
|
length. */
|
532 |
|
|
if (set->indexed)
|
533 |
|
|
value_insert_into_set_bitmap (set, val);
|
534 |
|
|
|
535 |
|
|
newnode->next = NULL;
|
536 |
|
|
newnode->expr = expr;
|
537 |
|
|
set->length ++;
|
538 |
|
|
if (set->head == NULL)
|
539 |
|
|
{
|
540 |
|
|
set->head = set->tail = newnode;
|
541 |
|
|
}
|
542 |
|
|
else
|
543 |
|
|
{
|
544 |
|
|
set->tail->next = newnode;
|
545 |
|
|
set->tail = newnode;
|
546 |
|
|
}
|
547 |
|
|
}
|
548 |
|
|
|
549 |
|
|
/* Copy a bitmapped set ORIG, into bitmapped set DEST. */
|
550 |
|
|
|
551 |
|
|
static void
|
552 |
|
|
bitmap_set_copy (bitmap_set_t dest, bitmap_set_t orig)
|
553 |
|
|
{
|
554 |
|
|
bitmap_copy (dest->expressions, orig->expressions);
|
555 |
|
|
bitmap_copy (dest->values, orig->values);
|
556 |
|
|
}
|
557 |
|
|
|
558 |
|
|
/* Copy the set ORIG to the set DEST. */
|
559 |
|
|
|
560 |
|
|
static void
|
561 |
|
|
set_copy (value_set_t dest, value_set_t orig)
|
562 |
|
|
{
|
563 |
|
|
value_set_node_t node;
|
564 |
|
|
|
565 |
|
|
if (!orig || !orig->head)
|
566 |
|
|
return;
|
567 |
|
|
|
568 |
|
|
for (node = orig->head;
|
569 |
|
|
node;
|
570 |
|
|
node = node->next)
|
571 |
|
|
{
|
572 |
|
|
insert_into_set (dest, node->expr);
|
573 |
|
|
}
|
574 |
|
|
}
|
575 |
|
|
|
576 |
|
|
/* Remove EXPR from SET. */
|
577 |
|
|
|
578 |
|
|
static void
|
579 |
|
|
set_remove (value_set_t set, tree expr)
|
580 |
|
|
{
|
581 |
|
|
value_set_node_t node, prev;
|
582 |
|
|
|
583 |
|
|
/* Remove the value of EXPR from the bitmap, decrement the set
|
584 |
|
|
length, and remove it from the actual double linked list. */
|
585 |
|
|
value_remove_from_set_bitmap (set, get_value_handle (expr));
|
586 |
|
|
set->length--;
|
587 |
|
|
prev = NULL;
|
588 |
|
|
for (node = set->head;
|
589 |
|
|
node != NULL;
|
590 |
|
|
prev = node, node = node->next)
|
591 |
|
|
{
|
592 |
|
|
if (node->expr == expr)
|
593 |
|
|
{
|
594 |
|
|
if (prev == NULL)
|
595 |
|
|
set->head = node->next;
|
596 |
|
|
else
|
597 |
|
|
prev->next= node->next;
|
598 |
|
|
|
599 |
|
|
if (node == set->tail)
|
600 |
|
|
set->tail = prev;
|
601 |
|
|
pool_free (value_set_node_pool, node);
|
602 |
|
|
return;
|
603 |
|
|
}
|
604 |
|
|
}
|
605 |
|
|
}
|
606 |
|
|
|
607 |
|
|
/* Return true if SET contains the value VAL. */
|
608 |
|
|
|
609 |
|
|
static bool
|
610 |
|
|
set_contains_value (value_set_t set, tree val)
|
611 |
|
|
{
|
612 |
|
|
/* All constants are in every set. */
|
613 |
|
|
if (is_gimple_min_invariant (val))
|
614 |
|
|
return true;
|
615 |
|
|
|
616 |
|
|
if (set->length == 0)
|
617 |
|
|
return false;
|
618 |
|
|
|
619 |
|
|
return value_exists_in_set_bitmap (set, val);
|
620 |
|
|
}
|
621 |
|
|
|
622 |
|
|
/* Return true if bitmapped set SET contains the expression EXPR. */
|
623 |
|
|
static bool
|
624 |
|
|
bitmap_set_contains (bitmap_set_t set, tree expr)
|
625 |
|
|
{
|
626 |
|
|
/* All constants are in every set. */
|
627 |
|
|
if (is_gimple_min_invariant (get_value_handle (expr)))
|
628 |
|
|
return true;
|
629 |
|
|
|
630 |
|
|
/* XXX: Bitmapped sets only contain SSA_NAME's for now. */
|
631 |
|
|
if (TREE_CODE (expr) != SSA_NAME)
|
632 |
|
|
return false;
|
633 |
|
|
return bitmap_bit_p (set->expressions, SSA_NAME_VERSION (expr));
|
634 |
|
|
}
|
635 |
|
|
|
636 |
|
|
|
637 |
|
|
/* Return true if bitmapped set SET contains the value VAL. */
|
638 |
|
|
|
639 |
|
|
static bool
|
640 |
|
|
bitmap_set_contains_value (bitmap_set_t set, tree val)
|
641 |
|
|
{
|
642 |
|
|
if (is_gimple_min_invariant (val))
|
643 |
|
|
return true;
|
644 |
|
|
return bitmap_bit_p (set->values, VALUE_HANDLE_ID (val));
|
645 |
|
|
}
|
646 |
|
|
|
647 |
|
|
/* Replace an instance of value LOOKFOR with expression EXPR in SET. */
|
648 |
|
|
|
649 |
|
|
static void
|
650 |
|
|
bitmap_set_replace_value (bitmap_set_t set, tree lookfor, tree expr)
|
651 |
|
|
{
|
652 |
|
|
value_set_t exprset;
|
653 |
|
|
value_set_node_t node;
|
654 |
|
|
if (is_gimple_min_invariant (lookfor))
|
655 |
|
|
return;
|
656 |
|
|
if (!bitmap_set_contains_value (set, lookfor))
|
657 |
|
|
return;
|
658 |
|
|
|
659 |
|
|
/* The number of expressions having a given value is usually
|
660 |
|
|
significantly less than the total number of expressions in SET.
|
661 |
|
|
Thus, rather than check, for each expression in SET, whether it
|
662 |
|
|
has the value LOOKFOR, we walk the reverse mapping that tells us
|
663 |
|
|
what expressions have a given value, and see if any of those
|
664 |
|
|
expressions are in our set. For large testcases, this is about
|
665 |
|
|
5-10x faster than walking the bitmap. If this is somehow a
|
666 |
|
|
significant lose for some cases, we can choose which set to walk
|
667 |
|
|
based on the set size. */
|
668 |
|
|
exprset = VALUE_HANDLE_EXPR_SET (lookfor);
|
669 |
|
|
for (node = exprset->head; node; node = node->next)
|
670 |
|
|
{
|
671 |
|
|
if (TREE_CODE (node->expr) == SSA_NAME)
|
672 |
|
|
{
|
673 |
|
|
if (bitmap_bit_p (set->expressions, SSA_NAME_VERSION (node->expr)))
|
674 |
|
|
{
|
675 |
|
|
bitmap_clear_bit (set->expressions, SSA_NAME_VERSION (node->expr));
|
676 |
|
|
bitmap_set_bit (set->expressions, SSA_NAME_VERSION (expr));
|
677 |
|
|
return;
|
678 |
|
|
}
|
679 |
|
|
}
|
680 |
|
|
}
|
681 |
|
|
}
|
682 |
|
|
|
683 |
|
|
/* Subtract bitmapped set B from value set A, and return the new set. */
|
684 |
|
|
|
685 |
|
|
static value_set_t
|
686 |
|
|
bitmap_set_subtract_from_value_set (value_set_t a, bitmap_set_t b,
|
687 |
|
|
bool indexed)
|
688 |
|
|
{
|
689 |
|
|
value_set_t ret = set_new (indexed);
|
690 |
|
|
value_set_node_t node;
|
691 |
|
|
for (node = a->head;
|
692 |
|
|
node;
|
693 |
|
|
node = node->next)
|
694 |
|
|
{
|
695 |
|
|
if (!bitmap_set_contains (b, node->expr))
|
696 |
|
|
insert_into_set (ret, node->expr);
|
697 |
|
|
}
|
698 |
|
|
return ret;
|
699 |
|
|
}
|
700 |
|
|
|
701 |
|
|
/* Return true if two sets are equal. */
|
702 |
|
|
|
703 |
|
|
static bool
|
704 |
|
|
set_equal (value_set_t a, value_set_t b)
|
705 |
|
|
{
|
706 |
|
|
value_set_node_t node;
|
707 |
|
|
|
708 |
|
|
if (a->length != b->length)
|
709 |
|
|
return false;
|
710 |
|
|
for (node = a->head;
|
711 |
|
|
node;
|
712 |
|
|
node = node->next)
|
713 |
|
|
{
|
714 |
|
|
if (!set_contains_value (b, get_value_handle (node->expr)))
|
715 |
|
|
return false;
|
716 |
|
|
}
|
717 |
|
|
return true;
|
718 |
|
|
}
|
719 |
|
|
|
720 |
|
|
/* Replace an instance of EXPR's VALUE with EXPR in SET if it exists,
|
721 |
|
|
and add it otherwise. */
|
722 |
|
|
|
723 |
|
|
static void
|
724 |
|
|
bitmap_value_replace_in_set (bitmap_set_t set, tree expr)
|
725 |
|
|
{
|
726 |
|
|
tree val = get_value_handle (expr);
|
727 |
|
|
if (bitmap_set_contains_value (set, val))
|
728 |
|
|
bitmap_set_replace_value (set, val, expr);
|
729 |
|
|
else
|
730 |
|
|
bitmap_insert_into_set (set, expr);
|
731 |
|
|
}
|
732 |
|
|
|
733 |
|
|
/* Insert EXPR into SET if EXPR's value is not already present in
|
734 |
|
|
SET. */
|
735 |
|
|
|
736 |
|
|
static void
|
737 |
|
|
bitmap_value_insert_into_set (bitmap_set_t set, tree expr)
|
738 |
|
|
{
|
739 |
|
|
tree val = get_value_handle (expr);
|
740 |
|
|
|
741 |
|
|
if (is_gimple_min_invariant (val))
|
742 |
|
|
return;
|
743 |
|
|
|
744 |
|
|
if (!bitmap_set_contains_value (set, val))
|
745 |
|
|
bitmap_insert_into_set (set, expr);
|
746 |
|
|
}
|
747 |
|
|
|
748 |
|
|
/* Insert the value for EXPR into SET, if it doesn't exist already. */
|
749 |
|
|
|
750 |
|
|
static void
|
751 |
|
|
value_insert_into_set (value_set_t set, tree expr)
|
752 |
|
|
{
|
753 |
|
|
tree val = get_value_handle (expr);
|
754 |
|
|
|
755 |
|
|
/* Constant and invariant values exist everywhere, and thus,
|
756 |
|
|
actually keeping them in the sets is pointless. */
|
757 |
|
|
if (is_gimple_min_invariant (val))
|
758 |
|
|
return;
|
759 |
|
|
|
760 |
|
|
if (!set_contains_value (set, val))
|
761 |
|
|
insert_into_set (set, expr);
|
762 |
|
|
}
|
763 |
|
|
|
764 |
|
|
|
765 |
|
|
/* Print out SET to OUTFILE. */
|
766 |
|
|
|
767 |
|
|
static void
|
768 |
|
|
bitmap_print_value_set (FILE *outfile, bitmap_set_t set,
|
769 |
|
|
const char *setname, int blockindex)
|
770 |
|
|
{
|
771 |
|
|
fprintf (outfile, "%s[%d] := { ", setname, blockindex);
|
772 |
|
|
if (set)
|
773 |
|
|
{
|
774 |
|
|
bool first = true;
|
775 |
|
|
unsigned i;
|
776 |
|
|
bitmap_iterator bi;
|
777 |
|
|
|
778 |
|
|
EXECUTE_IF_SET_IN_BITMAP (set->expressions, 0, i, bi)
|
779 |
|
|
{
|
780 |
|
|
if (!first)
|
781 |
|
|
fprintf (outfile, ", ");
|
782 |
|
|
first = false;
|
783 |
|
|
print_generic_expr (outfile, ssa_name (i), 0);
|
784 |
|
|
|
785 |
|
|
fprintf (outfile, " (");
|
786 |
|
|
print_generic_expr (outfile, get_value_handle (ssa_name (i)), 0);
|
787 |
|
|
fprintf (outfile, ") ");
|
788 |
|
|
}
|
789 |
|
|
}
|
790 |
|
|
fprintf (outfile, " }\n");
|
791 |
|
|
}
|
792 |
|
|
/* Print out the value_set SET to OUTFILE. */
|
793 |
|
|
|
794 |
|
|
static void
|
795 |
|
|
print_value_set (FILE *outfile, value_set_t set,
|
796 |
|
|
const char *setname, int blockindex)
|
797 |
|
|
{
|
798 |
|
|
value_set_node_t node;
|
799 |
|
|
fprintf (outfile, "%s[%d] := { ", setname, blockindex);
|
800 |
|
|
if (set)
|
801 |
|
|
{
|
802 |
|
|
for (node = set->head;
|
803 |
|
|
node;
|
804 |
|
|
node = node->next)
|
805 |
|
|
{
|
806 |
|
|
print_generic_expr (outfile, node->expr, 0);
|
807 |
|
|
|
808 |
|
|
fprintf (outfile, " (");
|
809 |
|
|
print_generic_expr (outfile, get_value_handle (node->expr), 0);
|
810 |
|
|
fprintf (outfile, ") ");
|
811 |
|
|
|
812 |
|
|
if (node->next)
|
813 |
|
|
fprintf (outfile, ", ");
|
814 |
|
|
}
|
815 |
|
|
}
|
816 |
|
|
|
817 |
|
|
fprintf (outfile, " }\n");
|
818 |
|
|
}
|
819 |
|
|
|
820 |
|
|
/* Print out the expressions that have VAL to OUTFILE. */
|
821 |
|
|
|
822 |
|
|
void
|
823 |
|
|
print_value_expressions (FILE *outfile, tree val)
|
824 |
|
|
{
|
825 |
|
|
if (VALUE_HANDLE_EXPR_SET (val))
|
826 |
|
|
{
|
827 |
|
|
char s[10];
|
828 |
|
|
sprintf (s, "VH.%04d", VALUE_HANDLE_ID (val));
|
829 |
|
|
print_value_set (outfile, VALUE_HANDLE_EXPR_SET (val), s, 0);
|
830 |
|
|
}
|
831 |
|
|
}
|
832 |
|
|
|
833 |
|
|
|
834 |
|
|
void
|
835 |
|
|
debug_value_expressions (tree val)
|
836 |
|
|
{
|
837 |
|
|
print_value_expressions (stderr, val);
|
838 |
|
|
}
|
839 |
|
|
|
840 |
|
|
|
841 |
|
|
void debug_value_set (value_set_t, const char *, int);
|
842 |
|
|
|
843 |
|
|
void
|
844 |
|
|
debug_value_set (value_set_t set, const char *setname, int blockindex)
|
845 |
|
|
{
|
846 |
|
|
print_value_set (stderr, set, setname, blockindex);
|
847 |
|
|
}
|
848 |
|
|
|
849 |
|
|
/* Return the folded version of T if T, when folded, is a gimple
|
850 |
|
|
min_invariant. Otherwise, return T. */
|
851 |
|
|
|
852 |
|
|
static tree
|
853 |
|
|
fully_constant_expression (tree t)
|
854 |
|
|
{
|
855 |
|
|
tree folded;
|
856 |
|
|
folded = fold (t);
|
857 |
|
|
if (folded && is_gimple_min_invariant (folded))
|
858 |
|
|
return folded;
|
859 |
|
|
return t;
|
860 |
|
|
}
|
861 |
|
|
|
862 |
|
|
/* Return a copy of a chain of nodes, chained through the TREE_CHAIN field.
|
863 |
|
|
For example, this can copy a list made of TREE_LIST nodes.
|
864 |
|
|
Allocates the nodes in list_node_pool*/
|
865 |
|
|
|
866 |
|
|
static tree
|
867 |
|
|
pool_copy_list (tree list)
|
868 |
|
|
{
|
869 |
|
|
tree head;
|
870 |
|
|
tree prev, next;
|
871 |
|
|
|
872 |
|
|
if (list == 0)
|
873 |
|
|
return 0;
|
874 |
|
|
head = pool_alloc (list_node_pool);
|
875 |
|
|
|
876 |
|
|
memcpy (head, list, tree_size (list));
|
877 |
|
|
prev = head;
|
878 |
|
|
|
879 |
|
|
next = TREE_CHAIN (list);
|
880 |
|
|
while (next)
|
881 |
|
|
{
|
882 |
|
|
TREE_CHAIN (prev) = pool_alloc (list_node_pool);
|
883 |
|
|
memcpy (TREE_CHAIN (prev), next, tree_size (next));
|
884 |
|
|
prev = TREE_CHAIN (prev);
|
885 |
|
|
next = TREE_CHAIN (next);
|
886 |
|
|
}
|
887 |
|
|
return head;
|
888 |
|
|
}
|
889 |
|
|
|
890 |
|
|
|
891 |
|
|
/* Translate EXPR using phis in PHIBLOCK, so that it has the values of
|
892 |
|
|
the phis in PRED. Return NULL if we can't find a leader for each
|
893 |
|
|
part of the translated expression. */
|
894 |
|
|
|
895 |
|
|
static tree
|
896 |
|
|
phi_translate (tree expr, value_set_t set, basic_block pred,
|
897 |
|
|
basic_block phiblock)
|
898 |
|
|
{
|
899 |
|
|
tree phitrans = NULL;
|
900 |
|
|
tree oldexpr = expr;
|
901 |
|
|
|
902 |
|
|
if (expr == NULL)
|
903 |
|
|
return NULL;
|
904 |
|
|
|
905 |
|
|
if (is_gimple_min_invariant (expr))
|
906 |
|
|
return expr;
|
907 |
|
|
|
908 |
|
|
/* Phi translations of a given expression don't change. */
|
909 |
|
|
phitrans = phi_trans_lookup (expr, pred);
|
910 |
|
|
if (phitrans)
|
911 |
|
|
return phitrans;
|
912 |
|
|
|
913 |
|
|
switch (TREE_CODE_CLASS (TREE_CODE (expr)))
|
914 |
|
|
{
|
915 |
|
|
case tcc_expression:
|
916 |
|
|
{
|
917 |
|
|
if (TREE_CODE (expr) != CALL_EXPR)
|
918 |
|
|
return NULL;
|
919 |
|
|
else
|
920 |
|
|
{
|
921 |
|
|
tree oldop0 = TREE_OPERAND (expr, 0);
|
922 |
|
|
tree oldarglist = TREE_OPERAND (expr, 1);
|
923 |
|
|
tree oldop2 = TREE_OPERAND (expr, 2);
|
924 |
|
|
tree newop0;
|
925 |
|
|
tree newarglist;
|
926 |
|
|
tree newop2 = NULL;
|
927 |
|
|
tree oldwalker;
|
928 |
|
|
tree newwalker;
|
929 |
|
|
tree newexpr;
|
930 |
|
|
bool listchanged = false;
|
931 |
|
|
|
932 |
|
|
/* Call expressions are kind of weird because they have an
|
933 |
|
|
argument list. We don't want to value number the list
|
934 |
|
|
as one value number, because that doesn't make much
|
935 |
|
|
sense, and just breaks the support functions we call,
|
936 |
|
|
which expect TREE_OPERAND (call_expr, 2) to be a
|
937 |
|
|
TREE_LIST. */
|
938 |
|
|
|
939 |
|
|
newop0 = phi_translate (find_leader (set, oldop0),
|
940 |
|
|
set, pred, phiblock);
|
941 |
|
|
if (newop0 == NULL)
|
942 |
|
|
return NULL;
|
943 |
|
|
if (oldop2)
|
944 |
|
|
{
|
945 |
|
|
newop2 = phi_translate (find_leader (set, oldop2),
|
946 |
|
|
set, pred, phiblock);
|
947 |
|
|
if (newop2 == NULL)
|
948 |
|
|
return NULL;
|
949 |
|
|
}
|
950 |
|
|
|
951 |
|
|
/* phi translate the argument list piece by piece.
|
952 |
|
|
|
953 |
|
|
We could actually build the list piece by piece here,
|
954 |
|
|
but it's likely to not be worth the memory we will save,
|
955 |
|
|
unless you have millions of call arguments. */
|
956 |
|
|
|
957 |
|
|
newarglist = pool_copy_list (oldarglist);
|
958 |
|
|
for (oldwalker = oldarglist, newwalker = newarglist;
|
959 |
|
|
oldwalker && newwalker;
|
960 |
|
|
oldwalker = TREE_CHAIN (oldwalker),
|
961 |
|
|
newwalker = TREE_CHAIN (newwalker))
|
962 |
|
|
{
|
963 |
|
|
|
964 |
|
|
tree oldval = TREE_VALUE (oldwalker);
|
965 |
|
|
tree newval;
|
966 |
|
|
if (oldval)
|
967 |
|
|
{
|
968 |
|
|
newval = phi_translate (find_leader (set, oldval),
|
969 |
|
|
set, pred, phiblock);
|
970 |
|
|
if (newval == NULL)
|
971 |
|
|
return NULL;
|
972 |
|
|
if (newval != oldval)
|
973 |
|
|
{
|
974 |
|
|
listchanged = true;
|
975 |
|
|
TREE_VALUE (newwalker) = get_value_handle (newval);
|
976 |
|
|
}
|
977 |
|
|
}
|
978 |
|
|
}
|
979 |
|
|
if (listchanged)
|
980 |
|
|
vn_lookup_or_add (newarglist, NULL);
|
981 |
|
|
|
982 |
|
|
if (listchanged || (newop0 != oldop0) || (oldop2 != newop2))
|
983 |
|
|
{
|
984 |
|
|
newexpr = pool_alloc (expression_node_pool);
|
985 |
|
|
memcpy (newexpr, expr, tree_size (expr));
|
986 |
|
|
TREE_OPERAND (newexpr, 0) = newop0 == oldop0 ? oldop0 : get_value_handle (newop0);
|
987 |
|
|
TREE_OPERAND (newexpr, 1) = listchanged ? newarglist : oldarglist;
|
988 |
|
|
TREE_OPERAND (newexpr, 2) = newop2 == oldop2 ? oldop2 : get_value_handle (newop2);
|
989 |
|
|
create_tree_ann (newexpr);
|
990 |
|
|
vn_lookup_or_add (newexpr, NULL);
|
991 |
|
|
expr = newexpr;
|
992 |
|
|
phi_trans_add (oldexpr, newexpr, pred);
|
993 |
|
|
}
|
994 |
|
|
}
|
995 |
|
|
}
|
996 |
|
|
return expr;
|
997 |
|
|
|
998 |
|
|
case tcc_reference:
|
999 |
|
|
/* XXX: Until we have PRE of loads working, none will be ANTIC. */
|
1000 |
|
|
return NULL;
|
1001 |
|
|
|
1002 |
|
|
case tcc_binary:
|
1003 |
|
|
case tcc_comparison:
|
1004 |
|
|
{
|
1005 |
|
|
tree oldop1 = TREE_OPERAND (expr, 0);
|
1006 |
|
|
tree oldop2 = TREE_OPERAND (expr, 1);
|
1007 |
|
|
tree newop1;
|
1008 |
|
|
tree newop2;
|
1009 |
|
|
tree newexpr;
|
1010 |
|
|
|
1011 |
|
|
newop1 = phi_translate (find_leader (set, oldop1),
|
1012 |
|
|
set, pred, phiblock);
|
1013 |
|
|
if (newop1 == NULL)
|
1014 |
|
|
return NULL;
|
1015 |
|
|
newop2 = phi_translate (find_leader (set, oldop2),
|
1016 |
|
|
set, pred, phiblock);
|
1017 |
|
|
if (newop2 == NULL)
|
1018 |
|
|
return NULL;
|
1019 |
|
|
if (newop1 != oldop1 || newop2 != oldop2)
|
1020 |
|
|
{
|
1021 |
|
|
tree t;
|
1022 |
|
|
newexpr = pool_alloc (binary_node_pool);
|
1023 |
|
|
memcpy (newexpr, expr, tree_size (expr));
|
1024 |
|
|
TREE_OPERAND (newexpr, 0) = newop1 == oldop1 ? oldop1 : get_value_handle (newop1);
|
1025 |
|
|
TREE_OPERAND (newexpr, 1) = newop2 == oldop2 ? oldop2 : get_value_handle (newop2);
|
1026 |
|
|
t = fully_constant_expression (newexpr);
|
1027 |
|
|
if (t != newexpr)
|
1028 |
|
|
{
|
1029 |
|
|
pool_free (binary_node_pool, newexpr);
|
1030 |
|
|
newexpr = t;
|
1031 |
|
|
}
|
1032 |
|
|
else
|
1033 |
|
|
{
|
1034 |
|
|
create_tree_ann (newexpr);
|
1035 |
|
|
vn_lookup_or_add (newexpr, NULL);
|
1036 |
|
|
}
|
1037 |
|
|
expr = newexpr;
|
1038 |
|
|
phi_trans_add (oldexpr, newexpr, pred);
|
1039 |
|
|
}
|
1040 |
|
|
}
|
1041 |
|
|
return expr;
|
1042 |
|
|
|
1043 |
|
|
case tcc_unary:
|
1044 |
|
|
{
|
1045 |
|
|
tree oldop1 = TREE_OPERAND (expr, 0);
|
1046 |
|
|
tree newop1;
|
1047 |
|
|
tree newexpr;
|
1048 |
|
|
|
1049 |
|
|
newop1 = phi_translate (find_leader (set, oldop1),
|
1050 |
|
|
set, pred, phiblock);
|
1051 |
|
|
if (newop1 == NULL)
|
1052 |
|
|
return NULL;
|
1053 |
|
|
if (newop1 != oldop1)
|
1054 |
|
|
{
|
1055 |
|
|
tree t;
|
1056 |
|
|
newexpr = pool_alloc (unary_node_pool);
|
1057 |
|
|
memcpy (newexpr, expr, tree_size (expr));
|
1058 |
|
|
TREE_OPERAND (newexpr, 0) = get_value_handle (newop1);
|
1059 |
|
|
t = fully_constant_expression (newexpr);
|
1060 |
|
|
if (t != newexpr)
|
1061 |
|
|
{
|
1062 |
|
|
pool_free (unary_node_pool, newexpr);
|
1063 |
|
|
newexpr = t;
|
1064 |
|
|
}
|
1065 |
|
|
else
|
1066 |
|
|
{
|
1067 |
|
|
create_tree_ann (newexpr);
|
1068 |
|
|
vn_lookup_or_add (newexpr, NULL);
|
1069 |
|
|
}
|
1070 |
|
|
expr = newexpr;
|
1071 |
|
|
phi_trans_add (oldexpr, newexpr, pred);
|
1072 |
|
|
}
|
1073 |
|
|
}
|
1074 |
|
|
return expr;
|
1075 |
|
|
|
1076 |
|
|
case tcc_exceptional:
|
1077 |
|
|
{
|
1078 |
|
|
tree phi = NULL;
|
1079 |
|
|
edge e;
|
1080 |
|
|
gcc_assert (TREE_CODE (expr) == SSA_NAME);
|
1081 |
|
|
if (TREE_CODE (SSA_NAME_DEF_STMT (expr)) == PHI_NODE)
|
1082 |
|
|
phi = SSA_NAME_DEF_STMT (expr);
|
1083 |
|
|
else
|
1084 |
|
|
return expr;
|
1085 |
|
|
|
1086 |
|
|
e = find_edge (pred, bb_for_stmt (phi));
|
1087 |
|
|
if (e)
|
1088 |
|
|
{
|
1089 |
|
|
if (is_undefined_value (PHI_ARG_DEF (phi, e->dest_idx)))
|
1090 |
|
|
return NULL;
|
1091 |
|
|
vn_lookup_or_add (PHI_ARG_DEF (phi, e->dest_idx), NULL);
|
1092 |
|
|
return PHI_ARG_DEF (phi, e->dest_idx);
|
1093 |
|
|
}
|
1094 |
|
|
}
|
1095 |
|
|
return expr;
|
1096 |
|
|
|
1097 |
|
|
default:
|
1098 |
|
|
gcc_unreachable ();
|
1099 |
|
|
}
|
1100 |
|
|
}
|
1101 |
|
|
|
1102 |
|
|
/* For each expression in SET, translate the value handles through phi nodes
|
1103 |
|
|
in PHIBLOCK using edge PHIBLOCK->PRED, and store the resulting
|
1104 |
|
|
expressions in DEST. */
|
1105 |
|
|
|
1106 |
|
|
static void
|
1107 |
|
|
phi_translate_set (value_set_t dest, value_set_t set, basic_block pred,
|
1108 |
|
|
basic_block phiblock)
|
1109 |
|
|
{
|
1110 |
|
|
value_set_node_t node;
|
1111 |
|
|
for (node = set->head;
|
1112 |
|
|
node;
|
1113 |
|
|
node = node->next)
|
1114 |
|
|
{
|
1115 |
|
|
tree translated;
|
1116 |
|
|
translated = phi_translate (node->expr, set, pred, phiblock);
|
1117 |
|
|
phi_trans_add (node->expr, translated, pred);
|
1118 |
|
|
|
1119 |
|
|
if (translated != NULL)
|
1120 |
|
|
value_insert_into_set (dest, translated);
|
1121 |
|
|
}
|
1122 |
|
|
}
|
1123 |
|
|
|
1124 |
|
|
/* Find the leader for a value (i.e., the name representing that
|
1125 |
|
|
value) in a given set, and return it. Return NULL if no leader is
|
1126 |
|
|
found. */
|
1127 |
|
|
|
1128 |
|
|
static tree
|
1129 |
|
|
bitmap_find_leader (bitmap_set_t set, tree val)
|
1130 |
|
|
{
|
1131 |
|
|
if (val == NULL)
|
1132 |
|
|
return NULL;
|
1133 |
|
|
|
1134 |
|
|
if (is_gimple_min_invariant (val))
|
1135 |
|
|
return val;
|
1136 |
|
|
if (bitmap_set_contains_value (set, val))
|
1137 |
|
|
{
|
1138 |
|
|
/* Rather than walk the entire bitmap of expressions, and see
|
1139 |
|
|
whether any of them has the value we are looking for, we look
|
1140 |
|
|
at the reverse mapping, which tells us the set of expressions
|
1141 |
|
|
that have a given value (IE value->expressions with that
|
1142 |
|
|
value) and see if any of those expressions are in our set.
|
1143 |
|
|
The number of expressions per value is usually significantly
|
1144 |
|
|
less than the number of expressions in the set. In fact, for
|
1145 |
|
|
large testcases, doing it this way is roughly 5-10x faster
|
1146 |
|
|
than walking the bitmap.
|
1147 |
|
|
If this is somehow a significant lose for some cases, we can
|
1148 |
|
|
choose which set to walk based on which set is smaller. */
|
1149 |
|
|
value_set_t exprset;
|
1150 |
|
|
value_set_node_t node;
|
1151 |
|
|
exprset = VALUE_HANDLE_EXPR_SET (val);
|
1152 |
|
|
for (node = exprset->head; node; node = node->next)
|
1153 |
|
|
{
|
1154 |
|
|
if (TREE_CODE (node->expr) == SSA_NAME)
|
1155 |
|
|
{
|
1156 |
|
|
if (bitmap_bit_p (set->expressions,
|
1157 |
|
|
SSA_NAME_VERSION (node->expr)))
|
1158 |
|
|
return node->expr;
|
1159 |
|
|
}
|
1160 |
|
|
}
|
1161 |
|
|
}
|
1162 |
|
|
return NULL;
|
1163 |
|
|
}
|
1164 |
|
|
|
1165 |
|
|
|
1166 |
|
|
/* Find the leader for a value (i.e., the name representing that
|
1167 |
|
|
value) in a given set, and return it. Return NULL if no leader is
|
1168 |
|
|
found. */
|
1169 |
|
|
|
1170 |
|
|
static tree
|
1171 |
|
|
find_leader (value_set_t set, tree val)
|
1172 |
|
|
{
|
1173 |
|
|
value_set_node_t node;
|
1174 |
|
|
|
1175 |
|
|
if (val == NULL)
|
1176 |
|
|
return NULL;
|
1177 |
|
|
|
1178 |
|
|
/* Constants represent themselves. */
|
1179 |
|
|
if (is_gimple_min_invariant (val))
|
1180 |
|
|
return val;
|
1181 |
|
|
|
1182 |
|
|
if (set->length == 0)
|
1183 |
|
|
return NULL;
|
1184 |
|
|
|
1185 |
|
|
if (value_exists_in_set_bitmap (set, val))
|
1186 |
|
|
{
|
1187 |
|
|
for (node = set->head;
|
1188 |
|
|
node;
|
1189 |
|
|
node = node->next)
|
1190 |
|
|
{
|
1191 |
|
|
if (get_value_handle (node->expr) == val)
|
1192 |
|
|
return node->expr;
|
1193 |
|
|
}
|
1194 |
|
|
}
|
1195 |
|
|
|
1196 |
|
|
return NULL;
|
1197 |
|
|
}
|
1198 |
|
|
|
1199 |
|
|
/* Determine if the expression EXPR is valid in SET. This means that
|
1200 |
|
|
we have a leader for each part of the expression (if it consists of
|
1201 |
|
|
values), or the expression is an SSA_NAME.
|
1202 |
|
|
|
1203 |
|
|
NB: We never should run into a case where we have SSA_NAME +
|
1204 |
|
|
SSA_NAME or SSA_NAME + value. The sets valid_in_set is called on,
|
1205 |
|
|
the ANTIC sets, will only ever have SSA_NAME's or value expressions
|
1206 |
|
|
(IE VALUE1 + VALUE2, *VALUE1, VALUE1 < VALUE2) */
|
1207 |
|
|
|
1208 |
|
|
static bool
|
1209 |
|
|
valid_in_set (value_set_t set, tree expr)
|
1210 |
|
|
{
|
1211 |
|
|
switch (TREE_CODE_CLASS (TREE_CODE (expr)))
|
1212 |
|
|
{
|
1213 |
|
|
case tcc_binary:
|
1214 |
|
|
case tcc_comparison:
|
1215 |
|
|
{
|
1216 |
|
|
tree op1 = TREE_OPERAND (expr, 0);
|
1217 |
|
|
tree op2 = TREE_OPERAND (expr, 1);
|
1218 |
|
|
return set_contains_value (set, op1) && set_contains_value (set, op2);
|
1219 |
|
|
}
|
1220 |
|
|
|
1221 |
|
|
case tcc_unary:
|
1222 |
|
|
{
|
1223 |
|
|
tree op1 = TREE_OPERAND (expr, 0);
|
1224 |
|
|
return set_contains_value (set, op1);
|
1225 |
|
|
}
|
1226 |
|
|
|
1227 |
|
|
case tcc_expression:
|
1228 |
|
|
{
|
1229 |
|
|
if (TREE_CODE (expr) == CALL_EXPR)
|
1230 |
|
|
{
|
1231 |
|
|
tree op0 = TREE_OPERAND (expr, 0);
|
1232 |
|
|
tree arglist = TREE_OPERAND (expr, 1);
|
1233 |
|
|
tree op2 = TREE_OPERAND (expr, 2);
|
1234 |
|
|
|
1235 |
|
|
/* Check the non-list operands first. */
|
1236 |
|
|
if (!set_contains_value (set, op0)
|
1237 |
|
|
|| (op2 && !set_contains_value (set, op2)))
|
1238 |
|
|
return false;
|
1239 |
|
|
|
1240 |
|
|
/* Now check the operands. */
|
1241 |
|
|
for (; arglist; arglist = TREE_CHAIN (arglist))
|
1242 |
|
|
{
|
1243 |
|
|
if (!set_contains_value (set, TREE_VALUE (arglist)))
|
1244 |
|
|
return false;
|
1245 |
|
|
}
|
1246 |
|
|
return true;
|
1247 |
|
|
}
|
1248 |
|
|
return false;
|
1249 |
|
|
}
|
1250 |
|
|
|
1251 |
|
|
case tcc_reference:
|
1252 |
|
|
/* XXX: Until PRE of loads works, no reference nodes are ANTIC. */
|
1253 |
|
|
return false;
|
1254 |
|
|
|
1255 |
|
|
case tcc_exceptional:
|
1256 |
|
|
gcc_assert (TREE_CODE (expr) == SSA_NAME);
|
1257 |
|
|
return true;
|
1258 |
|
|
|
1259 |
|
|
case tcc_declaration:
|
1260 |
|
|
/* VAR_DECL and PARM_DECL are never anticipatable. */
|
1261 |
|
|
return false;
|
1262 |
|
|
|
1263 |
|
|
default:
|
1264 |
|
|
/* No other cases should be encountered. */
|
1265 |
|
|
gcc_unreachable ();
|
1266 |
|
|
}
|
1267 |
|
|
}
|
1268 |
|
|
|
1269 |
|
|
/* Clean the set of expressions that are no longer valid in SET. This
|
1270 |
|
|
means expressions that are made up of values we have no leaders for
|
1271 |
|
|
in SET. */
|
1272 |
|
|
|
1273 |
|
|
static void
|
1274 |
|
|
clean (value_set_t set)
|
1275 |
|
|
{
|
1276 |
|
|
value_set_node_t node;
|
1277 |
|
|
value_set_node_t next;
|
1278 |
|
|
node = set->head;
|
1279 |
|
|
while (node)
|
1280 |
|
|
{
|
1281 |
|
|
next = node->next;
|
1282 |
|
|
if (!valid_in_set (set, node->expr))
|
1283 |
|
|
set_remove (set, node->expr);
|
1284 |
|
|
node = next;
|
1285 |
|
|
}
|
1286 |
|
|
}
|
1287 |
|
|
|
1288 |
|
|
DEF_VEC_P (basic_block);
|
1289 |
|
|
DEF_VEC_ALLOC_P (basic_block, heap);
|
1290 |
|
|
static sbitmap has_abnormal_preds;
|
1291 |
|
|
|
1292 |
|
|
/* Compute the ANTIC set for BLOCK.
|
1293 |
|
|
|
1294 |
|
|
If succs(BLOCK) > 1 then
|
1295 |
|
|
ANTIC_OUT[BLOCK] = intersection of ANTIC_IN[b] for all succ(BLOCK)
|
1296 |
|
|
else if succs(BLOCK) == 1 then
|
1297 |
|
|
ANTIC_OUT[BLOCK] = phi_translate (ANTIC_IN[succ(BLOCK)])
|
1298 |
|
|
|
1299 |
|
|
ANTIC_IN[BLOCK] = clean(ANTIC_OUT[BLOCK] U EXP_GEN[BLOCK] - TMP_GEN[BLOCK])
|
1300 |
|
|
|
1301 |
|
|
XXX: It would be nice to either write a set_clear, and use it for
|
1302 |
|
|
ANTIC_OUT, or to mark the antic_out set as deleted at the end
|
1303 |
|
|
of this routine, so that the pool can hand the same memory back out
|
1304 |
|
|
again for the next ANTIC_OUT. */
|
1305 |
|
|
|
1306 |
|
|
static bool
|
1307 |
|
|
compute_antic_aux (basic_block block, bool block_has_abnormal_pred_edge)
|
1308 |
|
|
{
|
1309 |
|
|
basic_block son;
|
1310 |
|
|
bool changed = false;
|
1311 |
|
|
value_set_t S, old, ANTIC_OUT;
|
1312 |
|
|
value_set_node_t node;
|
1313 |
|
|
|
1314 |
|
|
ANTIC_OUT = S = NULL;
|
1315 |
|
|
|
1316 |
|
|
/* If any edges from predecessors are abnormal, antic_in is empty,
|
1317 |
|
|
so do nothing. */
|
1318 |
|
|
if (block_has_abnormal_pred_edge)
|
1319 |
|
|
goto maybe_dump_sets;
|
1320 |
|
|
|
1321 |
|
|
old = set_new (false);
|
1322 |
|
|
set_copy (old, ANTIC_IN (block));
|
1323 |
|
|
ANTIC_OUT = set_new (true);
|
1324 |
|
|
|
1325 |
|
|
/* If the block has no successors, ANTIC_OUT is empty. */
|
1326 |
|
|
if (EDGE_COUNT (block->succs) == 0)
|
1327 |
|
|
;
|
1328 |
|
|
/* If we have one successor, we could have some phi nodes to
|
1329 |
|
|
translate through. */
|
1330 |
|
|
else if (single_succ_p (block))
|
1331 |
|
|
{
|
1332 |
|
|
phi_translate_set (ANTIC_OUT, ANTIC_IN (single_succ (block)),
|
1333 |
|
|
block, single_succ (block));
|
1334 |
|
|
}
|
1335 |
|
|
/* If we have multiple successors, we take the intersection of all of
|
1336 |
|
|
them. */
|
1337 |
|
|
else
|
1338 |
|
|
{
|
1339 |
|
|
VEC(basic_block, heap) * worklist;
|
1340 |
|
|
edge e;
|
1341 |
|
|
size_t i;
|
1342 |
|
|
basic_block bprime, first;
|
1343 |
|
|
edge_iterator ei;
|
1344 |
|
|
|
1345 |
|
|
worklist = VEC_alloc (basic_block, heap, EDGE_COUNT (block->succs));
|
1346 |
|
|
FOR_EACH_EDGE (e, ei, block->succs)
|
1347 |
|
|
VEC_quick_push (basic_block, worklist, e->dest);
|
1348 |
|
|
first = VEC_index (basic_block, worklist, 0);
|
1349 |
|
|
set_copy (ANTIC_OUT, ANTIC_IN (first));
|
1350 |
|
|
|
1351 |
|
|
for (i = 1; VEC_iterate (basic_block, worklist, i, bprime); i++)
|
1352 |
|
|
{
|
1353 |
|
|
node = ANTIC_OUT->head;
|
1354 |
|
|
while (node)
|
1355 |
|
|
{
|
1356 |
|
|
tree val;
|
1357 |
|
|
value_set_node_t next = node->next;
|
1358 |
|
|
val = get_value_handle (node->expr);
|
1359 |
|
|
if (!set_contains_value (ANTIC_IN (bprime), val))
|
1360 |
|
|
set_remove (ANTIC_OUT, node->expr);
|
1361 |
|
|
node = next;
|
1362 |
|
|
}
|
1363 |
|
|
}
|
1364 |
|
|
VEC_free (basic_block, heap, worklist);
|
1365 |
|
|
}
|
1366 |
|
|
|
1367 |
|
|
/* Generate ANTIC_OUT - TMP_GEN. */
|
1368 |
|
|
S = bitmap_set_subtract_from_value_set (ANTIC_OUT, TMP_GEN (block), false);
|
1369 |
|
|
|
1370 |
|
|
/* Start ANTIC_IN with EXP_GEN - TMP_GEN */
|
1371 |
|
|
ANTIC_IN (block) = bitmap_set_subtract_from_value_set (EXP_GEN (block),
|
1372 |
|
|
TMP_GEN (block),
|
1373 |
|
|
true);
|
1374 |
|
|
|
1375 |
|
|
/* Then union in the ANTIC_OUT - TMP_GEN values,
|
1376 |
|
|
to get ANTIC_OUT U EXP_GEN - TMP_GEN */
|
1377 |
|
|
for (node = S->head; node; node = node->next)
|
1378 |
|
|
value_insert_into_set (ANTIC_IN (block), node->expr);
|
1379 |
|
|
|
1380 |
|
|
clean (ANTIC_IN (block));
|
1381 |
|
|
if (!set_equal (old, ANTIC_IN (block)))
|
1382 |
|
|
changed = true;
|
1383 |
|
|
|
1384 |
|
|
maybe_dump_sets:
|
1385 |
|
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
1386 |
|
|
{
|
1387 |
|
|
if (ANTIC_OUT)
|
1388 |
|
|
print_value_set (dump_file, ANTIC_OUT, "ANTIC_OUT", block->index);
|
1389 |
|
|
print_value_set (dump_file, ANTIC_IN (block), "ANTIC_IN", block->index);
|
1390 |
|
|
if (S)
|
1391 |
|
|
print_value_set (dump_file, S, "S", block->index);
|
1392 |
|
|
}
|
1393 |
|
|
|
1394 |
|
|
for (son = first_dom_son (CDI_POST_DOMINATORS, block);
|
1395 |
|
|
son;
|
1396 |
|
|
son = next_dom_son (CDI_POST_DOMINATORS, son))
|
1397 |
|
|
{
|
1398 |
|
|
changed |= compute_antic_aux (son,
|
1399 |
|
|
TEST_BIT (has_abnormal_preds, son->index));
|
1400 |
|
|
}
|
1401 |
|
|
return changed;
|
1402 |
|
|
}
|
1403 |
|
|
|
1404 |
|
|
/* Compute ANTIC sets. */
|
1405 |
|
|
|
1406 |
|
|
static void
|
1407 |
|
|
compute_antic (void)
|
1408 |
|
|
{
|
1409 |
|
|
bool changed = true;
|
1410 |
|
|
int num_iterations = 0;
|
1411 |
|
|
basic_block block;
|
1412 |
|
|
|
1413 |
|
|
/* If any predecessor edges are abnormal, we punt, so antic_in is empty.
|
1414 |
|
|
We pre-build the map of blocks with incoming abnormal edges here. */
|
1415 |
|
|
has_abnormal_preds = sbitmap_alloc (last_basic_block);
|
1416 |
|
|
sbitmap_zero (has_abnormal_preds);
|
1417 |
|
|
FOR_EACH_BB (block)
|
1418 |
|
|
{
|
1419 |
|
|
edge_iterator ei;
|
1420 |
|
|
edge e;
|
1421 |
|
|
|
1422 |
|
|
FOR_EACH_EDGE (e, ei, block->preds)
|
1423 |
|
|
if (e->flags & EDGE_ABNORMAL)
|
1424 |
|
|
{
|
1425 |
|
|
SET_BIT (has_abnormal_preds, block->index);
|
1426 |
|
|
break;
|
1427 |
|
|
}
|
1428 |
|
|
|
1429 |
|
|
/* While we are here, give empty ANTIC_IN sets to each block. */
|
1430 |
|
|
ANTIC_IN (block) = set_new (true);
|
1431 |
|
|
}
|
1432 |
|
|
/* At the exit block we anticipate nothing. */
|
1433 |
|
|
ANTIC_IN (EXIT_BLOCK_PTR) = set_new (true);
|
1434 |
|
|
|
1435 |
|
|
while (changed)
|
1436 |
|
|
{
|
1437 |
|
|
num_iterations++;
|
1438 |
|
|
changed = false;
|
1439 |
|
|
changed = compute_antic_aux (EXIT_BLOCK_PTR, false);
|
1440 |
|
|
}
|
1441 |
|
|
|
1442 |
|
|
sbitmap_free (has_abnormal_preds);
|
1443 |
|
|
|
1444 |
|
|
if (dump_file && (dump_flags & TDF_STATS))
|
1445 |
|
|
fprintf (dump_file, "compute_antic required %d iterations\n", num_iterations);
|
1446 |
|
|
}
|
1447 |
|
|
|
1448 |
|
|
static VEC(tree,heap) *inserted_exprs;
|
1449 |
|
|
/* Find a leader for an expression, or generate one using
|
1450 |
|
|
create_expression_by_pieces if it's ANTIC but
|
1451 |
|
|
complex.
|
1452 |
|
|
BLOCK is the basic_block we are looking for leaders in.
|
1453 |
|
|
EXPR is the expression to find a leader or generate for.
|
1454 |
|
|
STMTS is the statement list to put the inserted expressions on.
|
1455 |
|
|
Returns the SSA_NAME of the LHS of the generated expression or the
|
1456 |
|
|
leader. */
|
1457 |
|
|
|
1458 |
|
|
static tree
|
1459 |
|
|
find_or_generate_expression (basic_block block, tree expr, tree stmts)
|
1460 |
|
|
{
|
1461 |
|
|
tree genop = bitmap_find_leader (AVAIL_OUT (block), expr);
|
1462 |
|
|
|
1463 |
|
|
/* If it's still NULL, it must be a complex expression, so generate
|
1464 |
|
|
it recursively. */
|
1465 |
|
|
if (genop == NULL)
|
1466 |
|
|
{
|
1467 |
|
|
genop = VALUE_HANDLE_EXPR_SET (expr)->head->expr;
|
1468 |
|
|
gcc_assert (UNARY_CLASS_P (genop)
|
1469 |
|
|
|| BINARY_CLASS_P (genop)
|
1470 |
|
|
|| COMPARISON_CLASS_P (genop)
|
1471 |
|
|
|| REFERENCE_CLASS_P (genop)
|
1472 |
|
|
|| TREE_CODE (genop) == CALL_EXPR);
|
1473 |
|
|
genop = create_expression_by_pieces (block, genop, stmts);
|
1474 |
|
|
}
|
1475 |
|
|
return genop;
|
1476 |
|
|
}
|
1477 |
|
|
|
1478 |
|
|
#define NECESSARY(stmt) stmt->common.asm_written_flag
|
1479 |
|
|
/* Create an expression in pieces, so that we can handle very complex
|
1480 |
|
|
expressions that may be ANTIC, but not necessary GIMPLE.
|
1481 |
|
|
BLOCK is the basic block the expression will be inserted into,
|
1482 |
|
|
EXPR is the expression to insert (in value form)
|
1483 |
|
|
STMTS is a statement list to append the necessary insertions into.
|
1484 |
|
|
|
1485 |
|
|
This function will die if we hit some value that shouldn't be
|
1486 |
|
|
ANTIC but is (IE there is no leader for it, or its components).
|
1487 |
|
|
This function may also generate expressions that are themselves
|
1488 |
|
|
partially or fully redundant. Those that are will be either made
|
1489 |
|
|
fully redundant during the next iteration of insert (for partially
|
1490 |
|
|
redundant ones), or eliminated by eliminate (for fully redundant
|
1491 |
|
|
ones). */
|
1492 |
|
|
|
1493 |
|
|
static tree
|
1494 |
|
|
create_expression_by_pieces (basic_block block, tree expr, tree stmts)
|
1495 |
|
|
{
|
1496 |
|
|
tree temp, name;
|
1497 |
|
|
tree folded, forced_stmts, newexpr;
|
1498 |
|
|
tree v;
|
1499 |
|
|
tree_stmt_iterator tsi;
|
1500 |
|
|
|
1501 |
|
|
switch (TREE_CODE_CLASS (TREE_CODE (expr)))
|
1502 |
|
|
{
|
1503 |
|
|
case tcc_expression:
|
1504 |
|
|
{
|
1505 |
|
|
tree op0, op2;
|
1506 |
|
|
tree arglist;
|
1507 |
|
|
tree genop0, genop2;
|
1508 |
|
|
tree genarglist;
|
1509 |
|
|
tree walker, genwalker;
|
1510 |
|
|
|
1511 |
|
|
gcc_assert (TREE_CODE (expr) == CALL_EXPR);
|
1512 |
|
|
genop2 = NULL;
|
1513 |
|
|
|
1514 |
|
|
op0 = TREE_OPERAND (expr, 0);
|
1515 |
|
|
arglist = TREE_OPERAND (expr, 1);
|
1516 |
|
|
op2 = TREE_OPERAND (expr, 2);
|
1517 |
|
|
|
1518 |
|
|
genop0 = find_or_generate_expression (block, op0, stmts);
|
1519 |
|
|
genarglist = copy_list (arglist);
|
1520 |
|
|
for (walker = arglist, genwalker = genarglist;
|
1521 |
|
|
genwalker && walker;
|
1522 |
|
|
genwalker = TREE_CHAIN (genwalker), walker = TREE_CHAIN (walker))
|
1523 |
|
|
{
|
1524 |
|
|
TREE_VALUE (genwalker) = find_or_generate_expression (block,
|
1525 |
|
|
TREE_VALUE (walker),
|
1526 |
|
|
stmts);
|
1527 |
|
|
}
|
1528 |
|
|
|
1529 |
|
|
if (op2)
|
1530 |
|
|
genop2 = find_or_generate_expression (block, op2, stmts);
|
1531 |
|
|
folded = fold_build3 (TREE_CODE (expr), TREE_TYPE (expr),
|
1532 |
|
|
genop0, genarglist, genop2);
|
1533 |
|
|
break;
|
1534 |
|
|
|
1535 |
|
|
|
1536 |
|
|
}
|
1537 |
|
|
break;
|
1538 |
|
|
|
1539 |
|
|
case tcc_binary:
|
1540 |
|
|
case tcc_comparison:
|
1541 |
|
|
{
|
1542 |
|
|
tree op1 = TREE_OPERAND (expr, 0);
|
1543 |
|
|
tree op2 = TREE_OPERAND (expr, 1);
|
1544 |
|
|
tree genop1 = find_or_generate_expression (block, op1, stmts);
|
1545 |
|
|
tree genop2 = find_or_generate_expression (block, op2, stmts);
|
1546 |
|
|
folded = fold_build2 (TREE_CODE (expr), TREE_TYPE (expr),
|
1547 |
|
|
genop1, genop2);
|
1548 |
|
|
break;
|
1549 |
|
|
}
|
1550 |
|
|
|
1551 |
|
|
case tcc_unary:
|
1552 |
|
|
{
|
1553 |
|
|
tree op1 = TREE_OPERAND (expr, 0);
|
1554 |
|
|
tree genop1 = find_or_generate_expression (block, op1, stmts);
|
1555 |
|
|
folded = fold_build1 (TREE_CODE (expr), TREE_TYPE (expr),
|
1556 |
|
|
genop1);
|
1557 |
|
|
break;
|
1558 |
|
|
}
|
1559 |
|
|
|
1560 |
|
|
default:
|
1561 |
|
|
gcc_unreachable ();
|
1562 |
|
|
}
|
1563 |
|
|
|
1564 |
|
|
/* Force the generated expression to be a sequence of GIMPLE
|
1565 |
|
|
statements.
|
1566 |
|
|
We have to call unshare_expr because force_gimple_operand may
|
1567 |
|
|
modify the tree we pass to it. */
|
1568 |
|
|
newexpr = force_gimple_operand (unshare_expr (folded), &forced_stmts,
|
1569 |
|
|
false, NULL);
|
1570 |
|
|
|
1571 |
|
|
/* If we have any intermediate expressions to the value sets, add them
|
1572 |
|
|
to the value sets and chain them on in the instruction stream. */
|
1573 |
|
|
if (forced_stmts)
|
1574 |
|
|
{
|
1575 |
|
|
tsi = tsi_start (forced_stmts);
|
1576 |
|
|
for (; !tsi_end_p (tsi); tsi_next (&tsi))
|
1577 |
|
|
{
|
1578 |
|
|
tree stmt = tsi_stmt (tsi);
|
1579 |
|
|
tree forcedname = TREE_OPERAND (stmt, 0);
|
1580 |
|
|
tree forcedexpr = TREE_OPERAND (stmt, 1);
|
1581 |
|
|
tree val = vn_lookup_or_add (forcedexpr, NULL);
|
1582 |
|
|
|
1583 |
|
|
VEC_safe_push (tree, heap, inserted_exprs, stmt);
|
1584 |
|
|
vn_add (forcedname, val, NULL);
|
1585 |
|
|
bitmap_value_replace_in_set (NEW_SETS (block), forcedname);
|
1586 |
|
|
bitmap_value_replace_in_set (AVAIL_OUT (block), forcedname);
|
1587 |
|
|
}
|
1588 |
|
|
tsi = tsi_last (stmts);
|
1589 |
|
|
tsi_link_after (&tsi, forced_stmts, TSI_CONTINUE_LINKING);
|
1590 |
|
|
}
|
1591 |
|
|
|
1592 |
|
|
/* Build and insert the assignment of the end result to the temporary
|
1593 |
|
|
that we will return. */
|
1594 |
|
|
temp = create_tmp_var (TREE_TYPE (expr), "pretmp");
|
1595 |
|
|
add_referenced_tmp_var (temp);
|
1596 |
|
|
if (TREE_CODE (TREE_TYPE (expr)) == COMPLEX_TYPE)
|
1597 |
|
|
DECL_COMPLEX_GIMPLE_REG_P (temp) = 1;
|
1598 |
|
|
newexpr = build (MODIFY_EXPR, TREE_TYPE (expr), temp, newexpr);
|
1599 |
|
|
name = make_ssa_name (temp, newexpr);
|
1600 |
|
|
TREE_OPERAND (newexpr, 0) = name;
|
1601 |
|
|
NECESSARY (newexpr) = 0;
|
1602 |
|
|
tsi = tsi_last (stmts);
|
1603 |
|
|
tsi_link_after (&tsi, newexpr, TSI_CONTINUE_LINKING);
|
1604 |
|
|
VEC_safe_push (tree, heap, inserted_exprs, newexpr);
|
1605 |
|
|
|
1606 |
|
|
/* Add a value handle to the temporary.
|
1607 |
|
|
The value may already exist in either NEW_SETS, or AVAIL_OUT, because
|
1608 |
|
|
we are creating the expression by pieces, and this particular piece of
|
1609 |
|
|
the expression may have been represented. There is no harm in replacing
|
1610 |
|
|
here. */
|
1611 |
|
|
v = get_value_handle (expr);
|
1612 |
|
|
vn_add (name, v, NULL);
|
1613 |
|
|
bitmap_value_replace_in_set (NEW_SETS (block), name);
|
1614 |
|
|
bitmap_value_replace_in_set (AVAIL_OUT (block), name);
|
1615 |
|
|
|
1616 |
|
|
pre_stats.insertions++;
|
1617 |
|
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
1618 |
|
|
{
|
1619 |
|
|
fprintf (dump_file, "Inserted ");
|
1620 |
|
|
print_generic_expr (dump_file, newexpr, 0);
|
1621 |
|
|
fprintf (dump_file, " in predecessor %d\n", block->index);
|
1622 |
|
|
}
|
1623 |
|
|
|
1624 |
|
|
return name;
|
1625 |
|
|
}
|
1626 |
|
|
|
1627 |
|
|
/* Insert the to-be-made-available values of NODE for each predecessor, stored
|
1628 |
|
|
in AVAIL, into the predecessors of BLOCK, and merge the result with a phi
|
1629 |
|
|
node, given the same value handle as NODE. The prefix of the phi node is
|
1630 |
|
|
given with TMPNAME. Return true if we have inserted new stuff. */
|
1631 |
|
|
|
1632 |
|
|
static bool
|
1633 |
|
|
insert_into_preds_of_block (basic_block block, value_set_node_t node,
|
1634 |
|
|
tree *avail, const char *tmpname)
|
1635 |
|
|
{
|
1636 |
|
|
tree val = get_value_handle (node->expr);
|
1637 |
|
|
edge pred;
|
1638 |
|
|
bool insertions = false;
|
1639 |
|
|
bool nophi = false;
|
1640 |
|
|
basic_block bprime;
|
1641 |
|
|
tree eprime;
|
1642 |
|
|
edge_iterator ei;
|
1643 |
|
|
tree type = TREE_TYPE (avail[EDGE_PRED (block, 0)->src->index]);
|
1644 |
|
|
tree temp;
|
1645 |
|
|
|
1646 |
|
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
1647 |
|
|
{
|
1648 |
|
|
fprintf (dump_file, "Found partial redundancy for expression ");
|
1649 |
|
|
print_generic_expr (dump_file, node->expr, 0);
|
1650 |
|
|
fprintf (dump_file, "\n");
|
1651 |
|
|
}
|
1652 |
|
|
|
1653 |
|
|
/* Make sure we aren't creating an induction variable. */
|
1654 |
|
|
if (block->loop_depth > 0 && EDGE_COUNT (block->preds) == 2)
|
1655 |
|
|
{
|
1656 |
|
|
bool firstinsideloop = false;
|
1657 |
|
|
bool secondinsideloop = false;
|
1658 |
|
|
firstinsideloop = flow_bb_inside_loop_p (block->loop_father,
|
1659 |
|
|
EDGE_PRED (block, 0)->src);
|
1660 |
|
|
secondinsideloop = flow_bb_inside_loop_p (block->loop_father,
|
1661 |
|
|
EDGE_PRED (block, 1)->src);
|
1662 |
|
|
/* Induction variables only have one edge inside the loop. */
|
1663 |
|
|
if (firstinsideloop ^ secondinsideloop)
|
1664 |
|
|
{
|
1665 |
|
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
1666 |
|
|
fprintf (dump_file, "Skipping insertion of phi for partial redundancy: Looks like an induction variable\n");
|
1667 |
|
|
nophi = true;
|
1668 |
|
|
}
|
1669 |
|
|
}
|
1670 |
|
|
|
1671 |
|
|
|
1672 |
|
|
/* Make the necessary insertions. */
|
1673 |
|
|
FOR_EACH_EDGE (pred, ei, block->preds)
|
1674 |
|
|
{
|
1675 |
|
|
tree stmts = alloc_stmt_list ();
|
1676 |
|
|
tree builtexpr;
|
1677 |
|
|
bprime = pred->src;
|
1678 |
|
|
eprime = avail[bprime->index];
|
1679 |
|
|
if (BINARY_CLASS_P (eprime)
|
1680 |
|
|
|| COMPARISON_CLASS_P (eprime)
|
1681 |
|
|
|| UNARY_CLASS_P (eprime)
|
1682 |
|
|
|| TREE_CODE (eprime) == CALL_EXPR)
|
1683 |
|
|
{
|
1684 |
|
|
builtexpr = create_expression_by_pieces (bprime,
|
1685 |
|
|
eprime,
|
1686 |
|
|
stmts);
|
1687 |
|
|
bsi_insert_on_edge (pred, stmts);
|
1688 |
|
|
avail[bprime->index] = builtexpr;
|
1689 |
|
|
insertions = true;
|
1690 |
|
|
}
|
1691 |
|
|
}
|
1692 |
|
|
/* If we didn't want a phi node, and we made insertions, we still have
|
1693 |
|
|
inserted new stuff, and thus return true. If we didn't want a phi node,
|
1694 |
|
|
and didn't make insertions, we haven't added anything new, so return
|
1695 |
|
|
false. */
|
1696 |
|
|
if (nophi && insertions)
|
1697 |
|
|
return true;
|
1698 |
|
|
else if (nophi && !insertions)
|
1699 |
|
|
return false;
|
1700 |
|
|
|
1701 |
|
|
/* Now build a phi for the new variable. */
|
1702 |
|
|
temp = create_tmp_var (type, tmpname);
|
1703 |
|
|
add_referenced_tmp_var (temp);
|
1704 |
|
|
if (TREE_CODE (type) == COMPLEX_TYPE)
|
1705 |
|
|
DECL_COMPLEX_GIMPLE_REG_P (temp) = 1;
|
1706 |
|
|
temp = create_phi_node (temp, block);
|
1707 |
|
|
NECESSARY (temp) = 0;
|
1708 |
|
|
VEC_safe_push (tree, heap, inserted_exprs, temp);
|
1709 |
|
|
FOR_EACH_EDGE (pred, ei, block->preds)
|
1710 |
|
|
add_phi_arg (temp, avail[pred->src->index], pred);
|
1711 |
|
|
|
1712 |
|
|
vn_add (PHI_RESULT (temp), val, NULL);
|
1713 |
|
|
|
1714 |
|
|
/* The value should *not* exist in PHI_GEN, or else we wouldn't be doing
|
1715 |
|
|
this insertion, since we test for the existence of this value in PHI_GEN
|
1716 |
|
|
before proceeding with the partial redundancy checks in insert_aux.
|
1717 |
|
|
|
1718 |
|
|
The value may exist in AVAIL_OUT, in particular, it could be represented
|
1719 |
|
|
by the expression we are trying to eliminate, in which case we want the
|
1720 |
|
|
replacement to occur. If it's not existing in AVAIL_OUT, we want it
|
1721 |
|
|
inserted there.
|
1722 |
|
|
|
1723 |
|
|
Similarly, to the PHI_GEN case, the value should not exist in NEW_SETS of
|
1724 |
|
|
this block, because if it did, it would have existed in our dominator's
|
1725 |
|
|
AVAIL_OUT, and would have been skipped due to the full redundancy check.
|
1726 |
|
|
*/
|
1727 |
|
|
|
1728 |
|
|
bitmap_insert_into_set (PHI_GEN (block),
|
1729 |
|
|
PHI_RESULT (temp));
|
1730 |
|
|
bitmap_value_replace_in_set (AVAIL_OUT (block),
|
1731 |
|
|
PHI_RESULT (temp));
|
1732 |
|
|
bitmap_insert_into_set (NEW_SETS (block),
|
1733 |
|
|
PHI_RESULT (temp));
|
1734 |
|
|
|
1735 |
|
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
1736 |
|
|
{
|
1737 |
|
|
fprintf (dump_file, "Created phi ");
|
1738 |
|
|
print_generic_expr (dump_file, temp, 0);
|
1739 |
|
|
fprintf (dump_file, " in block %d\n", block->index);
|
1740 |
|
|
}
|
1741 |
|
|
pre_stats.phis++;
|
1742 |
|
|
return true;
|
1743 |
|
|
}
|
1744 |
|
|
|
1745 |
|
|
|
1746 |
|
|
|
1747 |
|
|
/* Perform insertion of partially redundant values.
|
1748 |
|
|
For BLOCK, do the following:
|
1749 |
|
|
1. Propagate the NEW_SETS of the dominator into the current block.
|
1750 |
|
|
If the block has multiple predecessors,
|
1751 |
|
|
2a. Iterate over the ANTIC expressions for the block to see if
|
1752 |
|
|
any of them are partially redundant.
|
1753 |
|
|
2b. If so, insert them into the necessary predecessors to make
|
1754 |
|
|
the expression fully redundant.
|
1755 |
|
|
2c. Insert a new PHI merging the values of the predecessors.
|
1756 |
|
|
2d. Insert the new PHI, and the new expressions, into the
|
1757 |
|
|
NEW_SETS set.
|
1758 |
|
|
3. Recursively call ourselves on the dominator children of BLOCK.
|
1759 |
|
|
|
1760 |
|
|
*/
|
1761 |
|
|
|
1762 |
|
|
static bool
|
1763 |
|
|
insert_aux (basic_block block)
|
1764 |
|
|
{
|
1765 |
|
|
basic_block son;
|
1766 |
|
|
bool new_stuff = false;
|
1767 |
|
|
|
1768 |
|
|
if (block)
|
1769 |
|
|
{
|
1770 |
|
|
basic_block dom;
|
1771 |
|
|
dom = get_immediate_dominator (CDI_DOMINATORS, block);
|
1772 |
|
|
if (dom)
|
1773 |
|
|
{
|
1774 |
|
|
unsigned i;
|
1775 |
|
|
bitmap_iterator bi;
|
1776 |
|
|
bitmap_set_t newset = NEW_SETS (dom);
|
1777 |
|
|
if (newset)
|
1778 |
|
|
{
|
1779 |
|
|
/* Note that we need to value_replace both NEW_SETS, and
|
1780 |
|
|
AVAIL_OUT. For both the case of NEW_SETS, the value may be
|
1781 |
|
|
represented by some non-simple expression here that we want
|
1782 |
|
|
to replace it with. */
|
1783 |
|
|
EXECUTE_IF_SET_IN_BITMAP (newset->expressions, 0, i, bi)
|
1784 |
|
|
{
|
1785 |
|
|
bitmap_value_replace_in_set (NEW_SETS (block), ssa_name (i));
|
1786 |
|
|
bitmap_value_replace_in_set (AVAIL_OUT (block), ssa_name (i));
|
1787 |
|
|
}
|
1788 |
|
|
}
|
1789 |
|
|
if (!single_pred_p (block))
|
1790 |
|
|
{
|
1791 |
|
|
value_set_node_t node;
|
1792 |
|
|
for (node = ANTIC_IN (block)->head;
|
1793 |
|
|
node;
|
1794 |
|
|
node = node->next)
|
1795 |
|
|
{
|
1796 |
|
|
if (BINARY_CLASS_P (node->expr)
|
1797 |
|
|
|| COMPARISON_CLASS_P (node->expr)
|
1798 |
|
|
|| UNARY_CLASS_P (node->expr)
|
1799 |
|
|
|| TREE_CODE (node->expr) == CALL_EXPR)
|
1800 |
|
|
{
|
1801 |
|
|
tree *avail;
|
1802 |
|
|
tree val;
|
1803 |
|
|
bool by_some = false;
|
1804 |
|
|
bool cant_insert = false;
|
1805 |
|
|
bool all_same = true;
|
1806 |
|
|
tree first_s = NULL;
|
1807 |
|
|
edge pred;
|
1808 |
|
|
basic_block bprime;
|
1809 |
|
|
tree eprime = NULL_TREE;
|
1810 |
|
|
edge_iterator ei;
|
1811 |
|
|
|
1812 |
|
|
val = get_value_handle (node->expr);
|
1813 |
|
|
if (bitmap_set_contains_value (PHI_GEN (block), val))
|
1814 |
|
|
continue;
|
1815 |
|
|
if (bitmap_set_contains_value (AVAIL_OUT (dom), val))
|
1816 |
|
|
{
|
1817 |
|
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
1818 |
|
|
fprintf (dump_file, "Found fully redundant value\n");
|
1819 |
|
|
continue;
|
1820 |
|
|
}
|
1821 |
|
|
|
1822 |
|
|
avail = xcalloc (last_basic_block, sizeof (tree));
|
1823 |
|
|
FOR_EACH_EDGE (pred, ei, block->preds)
|
1824 |
|
|
{
|
1825 |
|
|
tree vprime;
|
1826 |
|
|
tree edoubleprime;
|
1827 |
|
|
|
1828 |
|
|
/* This can happen in the very weird case
|
1829 |
|
|
that our fake infinite loop edges have caused a
|
1830 |
|
|
critical edge to appear. */
|
1831 |
|
|
if (EDGE_CRITICAL_P (pred))
|
1832 |
|
|
{
|
1833 |
|
|
cant_insert = true;
|
1834 |
|
|
break;
|
1835 |
|
|
}
|
1836 |
|
|
bprime = pred->src;
|
1837 |
|
|
eprime = phi_translate (node->expr,
|
1838 |
|
|
ANTIC_IN (block),
|
1839 |
|
|
bprime, block);
|
1840 |
|
|
|
1841 |
|
|
/* eprime will generally only be NULL if the
|
1842 |
|
|
value of the expression, translated
|
1843 |
|
|
through the PHI for this predecessor, is
|
1844 |
|
|
undefined. If that is the case, we can't
|
1845 |
|
|
make the expression fully redundant,
|
1846 |
|
|
because its value is undefined along a
|
1847 |
|
|
predecessor path. We can thus break out
|
1848 |
|
|
early because it doesn't matter what the
|
1849 |
|
|
rest of the results are. */
|
1850 |
|
|
if (eprime == NULL)
|
1851 |
|
|
{
|
1852 |
|
|
cant_insert = true;
|
1853 |
|
|
break;
|
1854 |
|
|
}
|
1855 |
|
|
|
1856 |
|
|
eprime = fully_constant_expression (eprime);
|
1857 |
|
|
vprime = get_value_handle (eprime);
|
1858 |
|
|
gcc_assert (vprime);
|
1859 |
|
|
edoubleprime = bitmap_find_leader (AVAIL_OUT (bprime),
|
1860 |
|
|
vprime);
|
1861 |
|
|
if (edoubleprime == NULL)
|
1862 |
|
|
{
|
1863 |
|
|
avail[bprime->index] = eprime;
|
1864 |
|
|
all_same = false;
|
1865 |
|
|
}
|
1866 |
|
|
else
|
1867 |
|
|
{
|
1868 |
|
|
avail[bprime->index] = edoubleprime;
|
1869 |
|
|
by_some = true;
|
1870 |
|
|
if (first_s == NULL)
|
1871 |
|
|
first_s = edoubleprime;
|
1872 |
|
|
else if (!operand_equal_p (first_s, edoubleprime,
|
1873 |
|
|
0))
|
1874 |
|
|
all_same = false;
|
1875 |
|
|
}
|
1876 |
|
|
}
|
1877 |
|
|
/* If we can insert it, it's not the same value
|
1878 |
|
|
already existing along every predecessor, and
|
1879 |
|
|
it's defined by some predecessor, it is
|
1880 |
|
|
partially redundant. */
|
1881 |
|
|
if (!cant_insert && !all_same && by_some)
|
1882 |
|
|
{
|
1883 |
|
|
if (insert_into_preds_of_block (block, node, avail,
|
1884 |
|
|
"prephitmp"))
|
1885 |
|
|
new_stuff = true;
|
1886 |
|
|
}
|
1887 |
|
|
/* If all edges produce the same value and that value is
|
1888 |
|
|
an invariant, then the PHI has the same value on all
|
1889 |
|
|
edges. Note this. */
|
1890 |
|
|
else if (!cant_insert && all_same && eprime
|
1891 |
|
|
&& is_gimple_min_invariant (eprime)
|
1892 |
|
|
&& !is_gimple_min_invariant (val))
|
1893 |
|
|
{
|
1894 |
|
|
value_set_t exprset = VALUE_HANDLE_EXPR_SET (val);
|
1895 |
|
|
value_set_node_t node;
|
1896 |
|
|
for (node = exprset->head; node; node = node->next)
|
1897 |
|
|
{
|
1898 |
|
|
if (TREE_CODE (node->expr) == SSA_NAME)
|
1899 |
|
|
{
|
1900 |
|
|
vn_add (node->expr, eprime, NULL);
|
1901 |
|
|
pre_stats.constified++;
|
1902 |
|
|
}
|
1903 |
|
|
}
|
1904 |
|
|
}
|
1905 |
|
|
free (avail);
|
1906 |
|
|
}
|
1907 |
|
|
}
|
1908 |
|
|
}
|
1909 |
|
|
}
|
1910 |
|
|
}
|
1911 |
|
|
for (son = first_dom_son (CDI_DOMINATORS, block);
|
1912 |
|
|
son;
|
1913 |
|
|
son = next_dom_son (CDI_DOMINATORS, son))
|
1914 |
|
|
{
|
1915 |
|
|
new_stuff |= insert_aux (son);
|
1916 |
|
|
}
|
1917 |
|
|
|
1918 |
|
|
return new_stuff;
|
1919 |
|
|
}
|
1920 |
|
|
|
1921 |
|
|
/* Perform insertion of partially redundant values. */
|
1922 |
|
|
|
1923 |
|
|
static void
|
1924 |
|
|
insert (void)
|
1925 |
|
|
{
|
1926 |
|
|
bool new_stuff = true;
|
1927 |
|
|
basic_block bb;
|
1928 |
|
|
int num_iterations = 0;
|
1929 |
|
|
|
1930 |
|
|
FOR_ALL_BB (bb)
|
1931 |
|
|
NEW_SETS (bb) = bitmap_set_new ();
|
1932 |
|
|
|
1933 |
|
|
while (new_stuff)
|
1934 |
|
|
{
|
1935 |
|
|
num_iterations++;
|
1936 |
|
|
new_stuff = false;
|
1937 |
|
|
new_stuff = insert_aux (ENTRY_BLOCK_PTR);
|
1938 |
|
|
}
|
1939 |
|
|
if (num_iterations > 2 && dump_file && (dump_flags & TDF_STATS))
|
1940 |
|
|
fprintf (dump_file, "insert required %d iterations\n", num_iterations);
|
1941 |
|
|
}
|
1942 |
|
|
|
1943 |
|
|
|
1944 |
|
|
/* Return true if VAR is an SSA variable with no defining statement in
|
1945 |
|
|
this procedure, *AND* isn't a live-on-entry parameter. */
|
1946 |
|
|
|
1947 |
|
|
static bool
|
1948 |
|
|
is_undefined_value (tree expr)
|
1949 |
|
|
{
|
1950 |
|
|
return (TREE_CODE (expr) == SSA_NAME
|
1951 |
|
|
&& IS_EMPTY_STMT (SSA_NAME_DEF_STMT (expr))
|
1952 |
|
|
/* PARM_DECLs and hard registers are always defined. */
|
1953 |
|
|
&& TREE_CODE (SSA_NAME_VAR (expr)) != PARM_DECL);
|
1954 |
|
|
}
|
1955 |
|
|
|
1956 |
|
|
|
1957 |
|
|
/* Given an SSA variable VAR and an expression EXPR, compute the value
|
1958 |
|
|
number for EXPR and create a value handle (VAL) for it. If VAR and
|
1959 |
|
|
EXPR are not the same, associate VAL with VAR. Finally, add VAR to
|
1960 |
|
|
S1 and its value handle to S2.
|
1961 |
|
|
|
1962 |
|
|
VUSES represent the virtual use operands associated with EXPR (if
|
1963 |
|
|
any). They are used when computing the hash value for EXPR. */
|
1964 |
|
|
|
1965 |
|
|
static inline void
|
1966 |
|
|
add_to_sets (tree var, tree expr, tree stmt, bitmap_set_t s1,
|
1967 |
|
|
bitmap_set_t s2)
|
1968 |
|
|
{
|
1969 |
|
|
tree val = vn_lookup_or_add (expr, stmt);
|
1970 |
|
|
|
1971 |
|
|
/* VAR and EXPR may be the same when processing statements for which
|
1972 |
|
|
we are not computing value numbers (e.g., non-assignments, or
|
1973 |
|
|
statements that make aliased stores). In those cases, we are
|
1974 |
|
|
only interested in making VAR available as its own value. */
|
1975 |
|
|
if (var != expr)
|
1976 |
|
|
vn_add (var, val, NULL_TREE);
|
1977 |
|
|
|
1978 |
|
|
if (s1)
|
1979 |
|
|
bitmap_insert_into_set (s1, var);
|
1980 |
|
|
bitmap_value_insert_into_set (s2, var);
|
1981 |
|
|
}
|
1982 |
|
|
|
1983 |
|
|
|
1984 |
|
|
/* Given a unary or binary expression EXPR, create and return a new
|
1985 |
|
|
expression with the same structure as EXPR but with its operands
|
1986 |
|
|
replaced with the value handles of each of the operands of EXPR.
|
1987 |
|
|
|
1988 |
|
|
VUSES represent the virtual use operands associated with EXPR (if
|
1989 |
|
|
any). They are used when computing the hash value for EXPR.
|
1990 |
|
|
Insert EXPR's operands into the EXP_GEN set for BLOCK. */
|
1991 |
|
|
|
1992 |
|
|
static inline tree
|
1993 |
|
|
create_value_expr_from (tree expr, basic_block block, tree stmt)
|
1994 |
|
|
{
|
1995 |
|
|
int i;
|
1996 |
|
|
enum tree_code code = TREE_CODE (expr);
|
1997 |
|
|
tree vexpr;
|
1998 |
|
|
alloc_pool pool;
|
1999 |
|
|
|
2000 |
|
|
gcc_assert (TREE_CODE_CLASS (code) == tcc_unary
|
2001 |
|
|
|| TREE_CODE_CLASS (code) == tcc_binary
|
2002 |
|
|
|| TREE_CODE_CLASS (code) == tcc_comparison
|
2003 |
|
|
|| TREE_CODE_CLASS (code) == tcc_reference
|
2004 |
|
|
|| TREE_CODE_CLASS (code) == tcc_expression
|
2005 |
|
|
|| TREE_CODE_CLASS (code) == tcc_exceptional);
|
2006 |
|
|
|
2007 |
|
|
if (TREE_CODE_CLASS (code) == tcc_unary)
|
2008 |
|
|
pool = unary_node_pool;
|
2009 |
|
|
else if (TREE_CODE_CLASS (code) == tcc_reference)
|
2010 |
|
|
pool = reference_node_pool;
|
2011 |
|
|
else if (TREE_CODE_CLASS (code) == tcc_binary)
|
2012 |
|
|
pool = binary_node_pool;
|
2013 |
|
|
else if (TREE_CODE_CLASS (code) == tcc_comparison)
|
2014 |
|
|
pool = comparison_node_pool;
|
2015 |
|
|
else if (TREE_CODE_CLASS (code) == tcc_exceptional)
|
2016 |
|
|
{
|
2017 |
|
|
gcc_assert (code == TREE_LIST);
|
2018 |
|
|
pool = list_node_pool;
|
2019 |
|
|
}
|
2020 |
|
|
else
|
2021 |
|
|
{
|
2022 |
|
|
gcc_assert (code == CALL_EXPR);
|
2023 |
|
|
pool = expression_node_pool;
|
2024 |
|
|
}
|
2025 |
|
|
|
2026 |
|
|
vexpr = pool_alloc (pool);
|
2027 |
|
|
memcpy (vexpr, expr, tree_size (expr));
|
2028 |
|
|
|
2029 |
|
|
/* This case is only for TREE_LIST's that appear as part of
|
2030 |
|
|
CALL_EXPR's. Anything else is a bug, but we can't easily verify
|
2031 |
|
|
this, hence this comment. TREE_LIST is not handled by the
|
2032 |
|
|
general case below is because they don't have a fixed length, or
|
2033 |
|
|
operands, so you can't access purpose/value/chain through
|
2034 |
|
|
TREE_OPERAND macros. */
|
2035 |
|
|
|
2036 |
|
|
if (code == TREE_LIST)
|
2037 |
|
|
{
|
2038 |
|
|
tree op = NULL_TREE;
|
2039 |
|
|
tree temp = NULL_TREE;
|
2040 |
|
|
if (TREE_CHAIN (vexpr))
|
2041 |
|
|
temp = create_value_expr_from (TREE_CHAIN (vexpr), block, stmt);
|
2042 |
|
|
TREE_CHAIN (vexpr) = temp ? temp : TREE_CHAIN (vexpr);
|
2043 |
|
|
|
2044 |
|
|
|
2045 |
|
|
/* Recursively value-numberize reference ops. */
|
2046 |
|
|
if (REFERENCE_CLASS_P (TREE_VALUE (vexpr)))
|
2047 |
|
|
{
|
2048 |
|
|
tree tempop;
|
2049 |
|
|
op = TREE_VALUE (vexpr);
|
2050 |
|
|
tempop = create_value_expr_from (op, block, stmt);
|
2051 |
|
|
op = tempop ? tempop : op;
|
2052 |
|
|
|
2053 |
|
|
TREE_VALUE (vexpr) = vn_lookup_or_add (op, stmt);
|
2054 |
|
|
}
|
2055 |
|
|
else
|
2056 |
|
|
{
|
2057 |
|
|
op = TREE_VALUE (vexpr);
|
2058 |
|
|
TREE_VALUE (vexpr) = vn_lookup_or_add (TREE_VALUE (vexpr), NULL);
|
2059 |
|
|
}
|
2060 |
|
|
/* This is the equivalent of inserting op into EXP_GEN like we
|
2061 |
|
|
do below */
|
2062 |
|
|
if (!is_undefined_value (op))
|
2063 |
|
|
value_insert_into_set (EXP_GEN (block), op);
|
2064 |
|
|
|
2065 |
|
|
return vexpr;
|
2066 |
|
|
}
|
2067 |
|
|
|
2068 |
|
|
for (i = 0; i < TREE_CODE_LENGTH (code); i++)
|
2069 |
|
|
{
|
2070 |
|
|
tree val, op;
|
2071 |
|
|
|
2072 |
|
|
op = TREE_OPERAND (expr, i);
|
2073 |
|
|
if (op == NULL_TREE)
|
2074 |
|
|
continue;
|
2075 |
|
|
|
2076 |
|
|
/* If OP is a constant that has overflowed, do not value number
|
2077 |
|
|
this expression. */
|
2078 |
|
|
if (CONSTANT_CLASS_P (op)
|
2079 |
|
|
&& TREE_OVERFLOW (op))
|
2080 |
|
|
{
|
2081 |
|
|
pool_free (pool, vexpr);
|
2082 |
|
|
return NULL;
|
2083 |
|
|
}
|
2084 |
|
|
|
2085 |
|
|
/* Recursively value-numberize reference ops and tree lists. */
|
2086 |
|
|
if (REFERENCE_CLASS_P (op))
|
2087 |
|
|
{
|
2088 |
|
|
tree tempop = create_value_expr_from (op, block, stmt);
|
2089 |
|
|
op = tempop ? tempop : op;
|
2090 |
|
|
val = vn_lookup_or_add (op, stmt);
|
2091 |
|
|
}
|
2092 |
|
|
else if (TREE_CODE (op) == TREE_LIST)
|
2093 |
|
|
{
|
2094 |
|
|
tree tempop;
|
2095 |
|
|
|
2096 |
|
|
gcc_assert (TREE_CODE (expr) == CALL_EXPR);
|
2097 |
|
|
tempop = create_value_expr_from (op, block, stmt);
|
2098 |
|
|
|
2099 |
|
|
op = tempop ? tempop : op;
|
2100 |
|
|
vn_lookup_or_add (op, NULL);
|
2101 |
|
|
/* Unlike everywhere else, we do *not* want to replace the
|
2102 |
|
|
TREE_LIST itself with a value number, because support
|
2103 |
|
|
functions we call will blow up. */
|
2104 |
|
|
val = op;
|
2105 |
|
|
}
|
2106 |
|
|
else
|
2107 |
|
|
/* Create a value handle for OP and add it to VEXPR. */
|
2108 |
|
|
val = vn_lookup_or_add (op, NULL);
|
2109 |
|
|
|
2110 |
|
|
if (!is_undefined_value (op) && TREE_CODE (op) != TREE_LIST)
|
2111 |
|
|
value_insert_into_set (EXP_GEN (block), op);
|
2112 |
|
|
|
2113 |
|
|
if (TREE_CODE (val) == VALUE_HANDLE)
|
2114 |
|
|
TREE_TYPE (val) = TREE_TYPE (TREE_OPERAND (vexpr, i));
|
2115 |
|
|
|
2116 |
|
|
TREE_OPERAND (vexpr, i) = val;
|
2117 |
|
|
}
|
2118 |
|
|
|
2119 |
|
|
return vexpr;
|
2120 |
|
|
}
|
2121 |
|
|
|
2122 |
|
|
|
2123 |
|
|
/* Return true if we can value number a call. This is true if we have
|
2124 |
|
|
a pure or constant call. */
|
2125 |
|
|
static bool
|
2126 |
|
|
can_value_number_call (tree stmt)
|
2127 |
|
|
{
|
2128 |
|
|
tree call = get_call_expr_in (stmt);
|
2129 |
|
|
|
2130 |
|
|
/* This is a temporary restriction until we translate vuses through
|
2131 |
|
|
phi nodes. This is only needed for PRE, of course. */
|
2132 |
|
|
if (!in_fre && !ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
|
2133 |
|
|
return false;
|
2134 |
|
|
if (call_expr_flags (call) & (ECF_PURE | ECF_CONST))
|
2135 |
|
|
return true;
|
2136 |
|
|
return false;
|
2137 |
|
|
}
|
2138 |
|
|
|
2139 |
|
|
/* Given a statement STMT and its right hand side which is a load, try
|
2140 |
|
|
to look for the expression stored in the location for the load, and
|
2141 |
|
|
return true if a useful equivalence was recorded for LHS. */
|
2142 |
|
|
|
2143 |
|
|
static bool
|
2144 |
|
|
try_look_through_load (tree lhs, tree mem_ref, tree stmt, basic_block block)
|
2145 |
|
|
{
|
2146 |
|
|
tree store_stmt = NULL;
|
2147 |
|
|
tree rhs;
|
2148 |
|
|
ssa_op_iter i;
|
2149 |
|
|
tree vuse;
|
2150 |
|
|
|
2151 |
|
|
FOR_EACH_SSA_TREE_OPERAND (vuse, stmt, i, SSA_OP_VIRTUAL_USES)
|
2152 |
|
|
{
|
2153 |
|
|
tree def_stmt;
|
2154 |
|
|
|
2155 |
|
|
gcc_assert (TREE_CODE (vuse) == SSA_NAME);
|
2156 |
|
|
def_stmt = SSA_NAME_DEF_STMT (vuse);
|
2157 |
|
|
|
2158 |
|
|
/* If there is no useful statement for this VUSE, we'll not find a
|
2159 |
|
|
useful expression to return either. Likewise, if there is a
|
2160 |
|
|
statement but it is not a simple assignment or it has virtual
|
2161 |
|
|
uses, we can stop right here. Note that this means we do
|
2162 |
|
|
not look through PHI nodes, which is intentional. */
|
2163 |
|
|
if (!def_stmt
|
2164 |
|
|
|| TREE_CODE (def_stmt) != MODIFY_EXPR
|
2165 |
|
|
|| !ZERO_SSA_OPERANDS (def_stmt, SSA_OP_VIRTUAL_USES))
|
2166 |
|
|
return false;
|
2167 |
|
|
|
2168 |
|
|
/* If this is not the same statement as one we have looked at for
|
2169 |
|
|
another VUSE of STMT already, we have two statements producing
|
2170 |
|
|
something that reaches our STMT. */
|
2171 |
|
|
if (store_stmt && store_stmt != def_stmt)
|
2172 |
|
|
return false;
|
2173 |
|
|
else
|
2174 |
|
|
{
|
2175 |
|
|
/* Is this a store to the exact same location as the one we are
|
2176 |
|
|
loading from in STMT? */
|
2177 |
|
|
if (!operand_equal_p (TREE_OPERAND (def_stmt, 0), mem_ref, 0))
|
2178 |
|
|
return false;
|
2179 |
|
|
|
2180 |
|
|
/* Otherwise remember this statement and see if all other VUSEs
|
2181 |
|
|
come from the same statement. */
|
2182 |
|
|
store_stmt = def_stmt;
|
2183 |
|
|
}
|
2184 |
|
|
}
|
2185 |
|
|
|
2186 |
|
|
/* Alright then, we have visited all VUSEs of STMT and we've determined
|
2187 |
|
|
that all of them come from the same statement STORE_STMT. See if there
|
2188 |
|
|
is a useful expression we can deduce from STORE_STMT. */
|
2189 |
|
|
rhs = TREE_OPERAND (store_stmt, 1);
|
2190 |
|
|
if ((TREE_CODE (rhs) == SSA_NAME
|
2191 |
|
|
&& !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs))
|
2192 |
|
|
|| is_gimple_min_invariant (rhs)
|
2193 |
|
|
|| TREE_CODE (rhs) == ADDR_EXPR
|
2194 |
|
|
|| TREE_INVARIANT (rhs))
|
2195 |
|
|
{
|
2196 |
|
|
|
2197 |
|
|
/* Yay! Compute a value number for the RHS of the statement and
|
2198 |
|
|
add its value to the AVAIL_OUT set for the block. Add the LHS
|
2199 |
|
|
to TMP_GEN. */
|
2200 |
|
|
add_to_sets (lhs, rhs, store_stmt, TMP_GEN (block), AVAIL_OUT (block));
|
2201 |
|
|
if (TREE_CODE (rhs) == SSA_NAME
|
2202 |
|
|
&& !is_undefined_value (rhs))
|
2203 |
|
|
value_insert_into_set (EXP_GEN (block), rhs);
|
2204 |
|
|
return true;
|
2205 |
|
|
}
|
2206 |
|
|
|
2207 |
|
|
return false;
|
2208 |
|
|
}
|
2209 |
|
|
|
2210 |
|
|
/* Compute the AVAIL set for all basic blocks.
|
2211 |
|
|
|
2212 |
|
|
This function performs value numbering of the statements in each basic
|
2213 |
|
|
block. The AVAIL sets are built from information we glean while doing
|
2214 |
|
|
this value numbering, since the AVAIL sets contain only one entry per
|
2215 |
|
|
value.
|
2216 |
|
|
|
2217 |
|
|
AVAIL_IN[BLOCK] = AVAIL_OUT[dom(BLOCK)].
|
2218 |
|
|
AVAIL_OUT[BLOCK] = AVAIL_IN[BLOCK] U PHI_GEN[BLOCK] U TMP_GEN[BLOCK]. */
|
2219 |
|
|
|
2220 |
|
|
static void
|
2221 |
|
|
compute_avail (void)
|
2222 |
|
|
{
|
2223 |
|
|
basic_block block, son;
|
2224 |
|
|
basic_block *worklist;
|
2225 |
|
|
size_t sp = 0;
|
2226 |
|
|
tree param;
|
2227 |
|
|
|
2228 |
|
|
/* For arguments with default definitions, we pretend they are
|
2229 |
|
|
defined in the entry block. */
|
2230 |
|
|
for (param = DECL_ARGUMENTS (current_function_decl);
|
2231 |
|
|
param;
|
2232 |
|
|
param = TREE_CHAIN (param))
|
2233 |
|
|
{
|
2234 |
|
|
if (default_def (param) != NULL)
|
2235 |
|
|
{
|
2236 |
|
|
tree def = default_def (param);
|
2237 |
|
|
vn_lookup_or_add (def, NULL);
|
2238 |
|
|
bitmap_insert_into_set (TMP_GEN (ENTRY_BLOCK_PTR), def);
|
2239 |
|
|
bitmap_value_insert_into_set (AVAIL_OUT (ENTRY_BLOCK_PTR), def);
|
2240 |
|
|
}
|
2241 |
|
|
}
|
2242 |
|
|
|
2243 |
|
|
/* Allocate the worklist. */
|
2244 |
|
|
worklist = xmalloc (sizeof (basic_block) * n_basic_blocks);
|
2245 |
|
|
|
2246 |
|
|
/* Seed the algorithm by putting the dominator children of the entry
|
2247 |
|
|
block on the worklist. */
|
2248 |
|
|
for (son = first_dom_son (CDI_DOMINATORS, ENTRY_BLOCK_PTR);
|
2249 |
|
|
son;
|
2250 |
|
|
son = next_dom_son (CDI_DOMINATORS, son))
|
2251 |
|
|
worklist[sp++] = son;
|
2252 |
|
|
|
2253 |
|
|
/* Loop until the worklist is empty. */
|
2254 |
|
|
while (sp)
|
2255 |
|
|
{
|
2256 |
|
|
block_stmt_iterator bsi;
|
2257 |
|
|
tree stmt, phi;
|
2258 |
|
|
basic_block dom;
|
2259 |
|
|
|
2260 |
|
|
/* Pick a block from the worklist. */
|
2261 |
|
|
block = worklist[--sp];
|
2262 |
|
|
|
2263 |
|
|
/* Initially, the set of available values in BLOCK is that of
|
2264 |
|
|
its immediate dominator. */
|
2265 |
|
|
dom = get_immediate_dominator (CDI_DOMINATORS, block);
|
2266 |
|
|
if (dom)
|
2267 |
|
|
bitmap_set_copy (AVAIL_OUT (block), AVAIL_OUT (dom));
|
2268 |
|
|
|
2269 |
|
|
/* Generate values for PHI nodes. */
|
2270 |
|
|
for (phi = phi_nodes (block); phi; phi = PHI_CHAIN (phi))
|
2271 |
|
|
/* We have no need for virtual phis, as they don't represent
|
2272 |
|
|
actual computations. */
|
2273 |
|
|
if (is_gimple_reg (PHI_RESULT (phi)))
|
2274 |
|
|
add_to_sets (PHI_RESULT (phi), PHI_RESULT (phi), NULL,
|
2275 |
|
|
PHI_GEN (block), AVAIL_OUT (block));
|
2276 |
|
|
|
2277 |
|
|
/* Now compute value numbers and populate value sets with all
|
2278 |
|
|
the expressions computed in BLOCK. */
|
2279 |
|
|
for (bsi = bsi_start (block); !bsi_end_p (bsi); bsi_next (&bsi))
|
2280 |
|
|
{
|
2281 |
|
|
stmt_ann_t ann;
|
2282 |
|
|
ssa_op_iter iter;
|
2283 |
|
|
tree op;
|
2284 |
|
|
|
2285 |
|
|
stmt = bsi_stmt (bsi);
|
2286 |
|
|
ann = stmt_ann (stmt);
|
2287 |
|
|
|
2288 |
|
|
/* We are only interested in assignments of the form
|
2289 |
|
|
X_i = EXPR, where EXPR represents an "interesting"
|
2290 |
|
|
computation, it has no volatile operands and X_i
|
2291 |
|
|
doesn't flow through an abnormal edge. */
|
2292 |
|
|
if (TREE_CODE (stmt) == MODIFY_EXPR
|
2293 |
|
|
&& !ann->has_volatile_ops
|
2294 |
|
|
&& TREE_CODE (TREE_OPERAND (stmt, 0)) == SSA_NAME
|
2295 |
|
|
&& !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (TREE_OPERAND (stmt, 0)))
|
2296 |
|
|
{
|
2297 |
|
|
tree lhs = TREE_OPERAND (stmt, 0);
|
2298 |
|
|
tree rhs = TREE_OPERAND (stmt, 1);
|
2299 |
|
|
|
2300 |
|
|
/* Try to look through loads. */
|
2301 |
|
|
if (TREE_CODE (lhs) == SSA_NAME
|
2302 |
|
|
&& !ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_USES)
|
2303 |
|
|
&& try_look_through_load (lhs, rhs, stmt, block))
|
2304 |
|
|
continue;
|
2305 |
|
|
|
2306 |
|
|
STRIP_USELESS_TYPE_CONVERSION (rhs);
|
2307 |
|
|
if (UNARY_CLASS_P (rhs)
|
2308 |
|
|
|| BINARY_CLASS_P (rhs)
|
2309 |
|
|
|| COMPARISON_CLASS_P (rhs)
|
2310 |
|
|
|| REFERENCE_CLASS_P (rhs)
|
2311 |
|
|
|| (TREE_CODE (rhs) == CALL_EXPR
|
2312 |
|
|
&& can_value_number_call (stmt)))
|
2313 |
|
|
{
|
2314 |
|
|
/* For binary, unary, and reference expressions,
|
2315 |
|
|
create a duplicate expression with the operands
|
2316 |
|
|
replaced with the value handles of the original
|
2317 |
|
|
RHS. */
|
2318 |
|
|
tree newt = create_value_expr_from (rhs, block, stmt);
|
2319 |
|
|
if (newt)
|
2320 |
|
|
{
|
2321 |
|
|
add_to_sets (lhs, newt, stmt, TMP_GEN (block),
|
2322 |
|
|
AVAIL_OUT (block));
|
2323 |
|
|
value_insert_into_set (EXP_GEN (block), newt);
|
2324 |
|
|
continue;
|
2325 |
|
|
}
|
2326 |
|
|
}
|
2327 |
|
|
else if ((TREE_CODE (rhs) == SSA_NAME
|
2328 |
|
|
&& !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs))
|
2329 |
|
|
|| is_gimple_min_invariant (rhs)
|
2330 |
|
|
|| TREE_CODE (rhs) == ADDR_EXPR
|
2331 |
|
|
|| TREE_INVARIANT (rhs)
|
2332 |
|
|
|| DECL_P (rhs))
|
2333 |
|
|
{
|
2334 |
|
|
/* Compute a value number for the RHS of the statement
|
2335 |
|
|
and add its value to the AVAIL_OUT set for the block.
|
2336 |
|
|
Add the LHS to TMP_GEN. */
|
2337 |
|
|
add_to_sets (lhs, rhs, stmt, TMP_GEN (block),
|
2338 |
|
|
AVAIL_OUT (block));
|
2339 |
|
|
|
2340 |
|
|
if (TREE_CODE (rhs) == SSA_NAME
|
2341 |
|
|
&& !is_undefined_value (rhs))
|
2342 |
|
|
value_insert_into_set (EXP_GEN (block), rhs);
|
2343 |
|
|
continue;
|
2344 |
|
|
}
|
2345 |
|
|
}
|
2346 |
|
|
|
2347 |
|
|
/* For any other statement that we don't recognize, simply
|
2348 |
|
|
make the names generated by the statement available in
|
2349 |
|
|
AVAIL_OUT and TMP_GEN. */
|
2350 |
|
|
FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_DEF)
|
2351 |
|
|
add_to_sets (op, op, NULL, TMP_GEN (block), AVAIL_OUT (block));
|
2352 |
|
|
|
2353 |
|
|
FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_USE)
|
2354 |
|
|
add_to_sets (op, op, NULL, NULL , AVAIL_OUT (block));
|
2355 |
|
|
}
|
2356 |
|
|
|
2357 |
|
|
/* Put the dominator children of BLOCK on the worklist of blocks
|
2358 |
|
|
to compute available sets for. */
|
2359 |
|
|
for (son = first_dom_son (CDI_DOMINATORS, block);
|
2360 |
|
|
son;
|
2361 |
|
|
son = next_dom_son (CDI_DOMINATORS, son))
|
2362 |
|
|
worklist[sp++] = son;
|
2363 |
|
|
}
|
2364 |
|
|
|
2365 |
|
|
free (worklist);
|
2366 |
|
|
}
|
2367 |
|
|
|
2368 |
|
|
|
2369 |
|
|
/* Eliminate fully redundant computations. */
|
2370 |
|
|
|
2371 |
|
|
static void
|
2372 |
|
|
eliminate (void)
|
2373 |
|
|
{
|
2374 |
|
|
basic_block b;
|
2375 |
|
|
|
2376 |
|
|
FOR_EACH_BB (b)
|
2377 |
|
|
{
|
2378 |
|
|
block_stmt_iterator i;
|
2379 |
|
|
|
2380 |
|
|
for (i = bsi_start (b); !bsi_end_p (i); bsi_next (&i))
|
2381 |
|
|
{
|
2382 |
|
|
tree stmt = bsi_stmt (i);
|
2383 |
|
|
|
2384 |
|
|
/* Lookup the RHS of the expression, see if we have an
|
2385 |
|
|
available computation for it. If so, replace the RHS with
|
2386 |
|
|
the available computation. */
|
2387 |
|
|
if (TREE_CODE (stmt) == MODIFY_EXPR
|
2388 |
|
|
&& TREE_CODE (TREE_OPERAND (stmt, 0)) == SSA_NAME
|
2389 |
|
|
&& TREE_CODE (TREE_OPERAND (stmt ,1)) != SSA_NAME
|
2390 |
|
|
&& !is_gimple_min_invariant (TREE_OPERAND (stmt, 1))
|
2391 |
|
|
&& !stmt_ann (stmt)->has_volatile_ops)
|
2392 |
|
|
{
|
2393 |
|
|
tree lhs = TREE_OPERAND (stmt, 0);
|
2394 |
|
|
tree *rhs_p = &TREE_OPERAND (stmt, 1);
|
2395 |
|
|
tree sprime;
|
2396 |
|
|
|
2397 |
|
|
sprime = bitmap_find_leader (AVAIL_OUT (b),
|
2398 |
|
|
vn_lookup (lhs, NULL));
|
2399 |
|
|
if (sprime
|
2400 |
|
|
&& sprime != lhs
|
2401 |
|
|
&& (TREE_CODE (*rhs_p) != SSA_NAME
|
2402 |
|
|
|| may_propagate_copy (*rhs_p, sprime)))
|
2403 |
|
|
{
|
2404 |
|
|
gcc_assert (sprime != *rhs_p);
|
2405 |
|
|
|
2406 |
|
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
2407 |
|
|
{
|
2408 |
|
|
fprintf (dump_file, "Replaced ");
|
2409 |
|
|
print_generic_expr (dump_file, *rhs_p, 0);
|
2410 |
|
|
fprintf (dump_file, " with ");
|
2411 |
|
|
print_generic_expr (dump_file, sprime, 0);
|
2412 |
|
|
fprintf (dump_file, " in ");
|
2413 |
|
|
print_generic_stmt (dump_file, stmt, 0);
|
2414 |
|
|
}
|
2415 |
|
|
|
2416 |
|
|
if (TREE_CODE (sprime) == SSA_NAME)
|
2417 |
|
|
NECESSARY (SSA_NAME_DEF_STMT (sprime)) = 1;
|
2418 |
|
|
/* We need to make sure the new and old types actually match,
|
2419 |
|
|
which may require adding a simple cast, which fold_convert
|
2420 |
|
|
will do for us. */
|
2421 |
|
|
if (TREE_CODE (*rhs_p) != SSA_NAME
|
2422 |
|
|
&& !tree_ssa_useless_type_conversion_1 (TREE_TYPE (*rhs_p),
|
2423 |
|
|
TREE_TYPE (sprime)))
|
2424 |
|
|
sprime = fold_convert (TREE_TYPE (*rhs_p), sprime);
|
2425 |
|
|
|
2426 |
|
|
pre_stats.eliminations++;
|
2427 |
|
|
propagate_tree_value (rhs_p, sprime);
|
2428 |
|
|
update_stmt (stmt);
|
2429 |
|
|
|
2430 |
|
|
/* If we removed EH side effects from the statement, clean
|
2431 |
|
|
its EH information. */
|
2432 |
|
|
if (maybe_clean_or_replace_eh_stmt (stmt, stmt))
|
2433 |
|
|
{
|
2434 |
|
|
bitmap_set_bit (need_eh_cleanup,
|
2435 |
|
|
bb_for_stmt (stmt)->index);
|
2436 |
|
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
2437 |
|
|
fprintf (dump_file, " Removed EH side effects.\n");
|
2438 |
|
|
}
|
2439 |
|
|
}
|
2440 |
|
|
}
|
2441 |
|
|
}
|
2442 |
|
|
}
|
2443 |
|
|
}
|
2444 |
|
|
|
2445 |
|
|
/* Borrow a bit of tree-ssa-dce.c for the moment.
|
2446 |
|
|
XXX: In 4.1, we should be able to just run a DCE pass after PRE, though
|
2447 |
|
|
this may be a bit faster, and we may want critical edges kept split. */
|
2448 |
|
|
|
2449 |
|
|
/* If OP's defining statement has not already been determined to be necessary,
|
2450 |
|
|
mark that statement necessary. Return the stmt, if it is newly
|
2451 |
|
|
necessary. */
|
2452 |
|
|
|
2453 |
|
|
static inline tree
|
2454 |
|
|
mark_operand_necessary (tree op)
|
2455 |
|
|
{
|
2456 |
|
|
tree stmt;
|
2457 |
|
|
|
2458 |
|
|
gcc_assert (op);
|
2459 |
|
|
|
2460 |
|
|
stmt = SSA_NAME_DEF_STMT (op);
|
2461 |
|
|
gcc_assert (stmt);
|
2462 |
|
|
|
2463 |
|
|
if (NECESSARY (stmt)
|
2464 |
|
|
|| IS_EMPTY_STMT (stmt))
|
2465 |
|
|
return NULL;
|
2466 |
|
|
|
2467 |
|
|
NECESSARY (stmt) = 1;
|
2468 |
|
|
return stmt;
|
2469 |
|
|
}
|
2470 |
|
|
|
2471 |
|
|
/* Because we don't follow exactly the standard PRE algorithm, and decide not
|
2472 |
|
|
to insert PHI nodes sometimes, and because value numbering of casts isn't
|
2473 |
|
|
perfect, we sometimes end up inserting dead code. This simple DCE-like
|
2474 |
|
|
pass removes any insertions we made that weren't actually used. */
|
2475 |
|
|
|
2476 |
|
|
static void
|
2477 |
|
|
remove_dead_inserted_code (void)
|
2478 |
|
|
{
|
2479 |
|
|
VEC(tree,heap) *worklist = NULL;
|
2480 |
|
|
int i;
|
2481 |
|
|
tree t;
|
2482 |
|
|
|
2483 |
|
|
worklist = VEC_alloc (tree, heap, VEC_length (tree, inserted_exprs));
|
2484 |
|
|
for (i = 0; VEC_iterate (tree, inserted_exprs, i, t); i++)
|
2485 |
|
|
{
|
2486 |
|
|
if (NECESSARY (t))
|
2487 |
|
|
VEC_quick_push (tree, worklist, t);
|
2488 |
|
|
}
|
2489 |
|
|
while (VEC_length (tree, worklist) > 0)
|
2490 |
|
|
{
|
2491 |
|
|
t = VEC_pop (tree, worklist);
|
2492 |
|
|
if (TREE_CODE (t) == PHI_NODE)
|
2493 |
|
|
{
|
2494 |
|
|
/* PHI nodes are somewhat special in that each PHI alternative has
|
2495 |
|
|
data and control dependencies. All the statements feeding the
|
2496 |
|
|
PHI node's arguments are always necessary. In aggressive mode,
|
2497 |
|
|
we also consider the control dependent edges leading to the
|
2498 |
|
|
predecessor block associated with each PHI alternative as
|
2499 |
|
|
necessary. */
|
2500 |
|
|
int k;
|
2501 |
|
|
|
2502 |
|
|
VEC_reserve (tree, heap, worklist, PHI_NUM_ARGS (t));
|
2503 |
|
|
for (k = 0; k < PHI_NUM_ARGS (t); k++)
|
2504 |
|
|
{
|
2505 |
|
|
tree arg = PHI_ARG_DEF (t, k);
|
2506 |
|
|
if (TREE_CODE (arg) == SSA_NAME)
|
2507 |
|
|
{
|
2508 |
|
|
arg = mark_operand_necessary (arg);
|
2509 |
|
|
if (arg)
|
2510 |
|
|
VEC_quick_push (tree, worklist, arg);
|
2511 |
|
|
}
|
2512 |
|
|
}
|
2513 |
|
|
}
|
2514 |
|
|
else
|
2515 |
|
|
{
|
2516 |
|
|
/* Propagate through the operands. Examine all the USE, VUSE and
|
2517 |
|
|
V_MAY_DEF operands in this statement. Mark all the statements
|
2518 |
|
|
which feed this statement's uses as necessary. */
|
2519 |
|
|
ssa_op_iter iter;
|
2520 |
|
|
tree use;
|
2521 |
|
|
|
2522 |
|
|
/* The operands of V_MAY_DEF expressions are also needed as they
|
2523 |
|
|
represent potential definitions that may reach this
|
2524 |
|
|
statement (V_MAY_DEF operands allow us to follow def-def
|
2525 |
|
|
links). */
|
2526 |
|
|
|
2527 |
|
|
FOR_EACH_SSA_TREE_OPERAND (use, t, iter, SSA_OP_ALL_USES)
|
2528 |
|
|
{
|
2529 |
|
|
tree n = mark_operand_necessary (use);
|
2530 |
|
|
if (n)
|
2531 |
|
|
VEC_safe_push (tree, heap, worklist, n);
|
2532 |
|
|
}
|
2533 |
|
|
}
|
2534 |
|
|
}
|
2535 |
|
|
for (i = 0; VEC_iterate (tree, inserted_exprs, i, t); i++)
|
2536 |
|
|
{
|
2537 |
|
|
if (!NECESSARY (t))
|
2538 |
|
|
{
|
2539 |
|
|
block_stmt_iterator bsi;
|
2540 |
|
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
2541 |
|
|
{
|
2542 |
|
|
fprintf (dump_file, "Removing unnecessary insertion:");
|
2543 |
|
|
print_generic_stmt (dump_file, t, 0);
|
2544 |
|
|
}
|
2545 |
|
|
if (TREE_CODE (t) == PHI_NODE)
|
2546 |
|
|
{
|
2547 |
|
|
remove_phi_node (t, NULL);
|
2548 |
|
|
}
|
2549 |
|
|
else
|
2550 |
|
|
{
|
2551 |
|
|
bsi = bsi_for_stmt (t);
|
2552 |
|
|
bsi_remove (&bsi);
|
2553 |
|
|
}
|
2554 |
|
|
}
|
2555 |
|
|
}
|
2556 |
|
|
VEC_free (tree, heap, worklist);
|
2557 |
|
|
}
|
2558 |
|
|
/* Initialize data structures used by PRE. */
|
2559 |
|
|
|
2560 |
|
|
static void
|
2561 |
|
|
init_pre (bool do_fre)
|
2562 |
|
|
{
|
2563 |
|
|
basic_block bb;
|
2564 |
|
|
|
2565 |
|
|
in_fre = do_fre;
|
2566 |
|
|
|
2567 |
|
|
inserted_exprs = NULL;
|
2568 |
|
|
vn_init ();
|
2569 |
|
|
if (!do_fre)
|
2570 |
|
|
current_loops = loop_optimizer_init (dump_file);
|
2571 |
|
|
connect_infinite_loops_to_exit ();
|
2572 |
|
|
memset (&pre_stats, 0, sizeof (pre_stats));
|
2573 |
|
|
|
2574 |
|
|
/* If block 0 has more than one predecessor, it means that its PHI
|
2575 |
|
|
nodes will have arguments coming from block -1. This creates
|
2576 |
|
|
problems for several places in PRE that keep local arrays indexed
|
2577 |
|
|
by block number. To prevent this, we split the edge coming from
|
2578 |
|
|
ENTRY_BLOCK_PTR (FIXME, if ENTRY_BLOCK_PTR had an index number
|
2579 |
|
|
different than -1 we wouldn't have to hack this. tree-ssa-dce.c
|
2580 |
|
|
needs a similar change). */
|
2581 |
|
|
if (!single_pred_p (single_succ (ENTRY_BLOCK_PTR)))
|
2582 |
|
|
if (!(single_succ_edge (ENTRY_BLOCK_PTR)->flags & EDGE_ABNORMAL))
|
2583 |
|
|
split_edge (single_succ_edge (ENTRY_BLOCK_PTR));
|
2584 |
|
|
|
2585 |
|
|
FOR_ALL_BB (bb)
|
2586 |
|
|
bb->aux = xcalloc (1, sizeof (struct bb_value_sets));
|
2587 |
|
|
|
2588 |
|
|
bitmap_obstack_initialize (&grand_bitmap_obstack);
|
2589 |
|
|
phi_translate_table = htab_create (511, expr_pred_trans_hash,
|
2590 |
|
|
expr_pred_trans_eq, free);
|
2591 |
|
|
value_set_pool = create_alloc_pool ("Value sets",
|
2592 |
|
|
sizeof (struct value_set), 30);
|
2593 |
|
|
bitmap_set_pool = create_alloc_pool ("Bitmap sets",
|
2594 |
|
|
sizeof (struct bitmap_set), 30);
|
2595 |
|
|
value_set_node_pool = create_alloc_pool ("Value set nodes",
|
2596 |
|
|
sizeof (struct value_set_node), 30);
|
2597 |
|
|
calculate_dominance_info (CDI_POST_DOMINATORS);
|
2598 |
|
|
calculate_dominance_info (CDI_DOMINATORS);
|
2599 |
|
|
binary_node_pool = create_alloc_pool ("Binary tree nodes",
|
2600 |
|
|
tree_code_size (PLUS_EXPR), 30);
|
2601 |
|
|
unary_node_pool = create_alloc_pool ("Unary tree nodes",
|
2602 |
|
|
tree_code_size (NEGATE_EXPR), 30);
|
2603 |
|
|
reference_node_pool = create_alloc_pool ("Reference tree nodes",
|
2604 |
|
|
tree_code_size (ARRAY_REF), 30);
|
2605 |
|
|
expression_node_pool = create_alloc_pool ("Expression tree nodes",
|
2606 |
|
|
tree_code_size (CALL_EXPR), 30);
|
2607 |
|
|
list_node_pool = create_alloc_pool ("List tree nodes",
|
2608 |
|
|
tree_code_size (TREE_LIST), 30);
|
2609 |
|
|
comparison_node_pool = create_alloc_pool ("Comparison tree nodes",
|
2610 |
|
|
tree_code_size (EQ_EXPR), 30);
|
2611 |
|
|
FOR_ALL_BB (bb)
|
2612 |
|
|
{
|
2613 |
|
|
EXP_GEN (bb) = set_new (true);
|
2614 |
|
|
PHI_GEN (bb) = bitmap_set_new ();
|
2615 |
|
|
TMP_GEN (bb) = bitmap_set_new ();
|
2616 |
|
|
AVAIL_OUT (bb) = bitmap_set_new ();
|
2617 |
|
|
}
|
2618 |
|
|
|
2619 |
|
|
need_eh_cleanup = BITMAP_ALLOC (NULL);
|
2620 |
|
|
}
|
2621 |
|
|
|
2622 |
|
|
|
2623 |
|
|
/* Deallocate data structures used by PRE. */
|
2624 |
|
|
|
2625 |
|
|
static void
|
2626 |
|
|
fini_pre (bool do_fre)
|
2627 |
|
|
{
|
2628 |
|
|
basic_block bb;
|
2629 |
|
|
unsigned int i;
|
2630 |
|
|
|
2631 |
|
|
VEC_free (tree, heap, inserted_exprs);
|
2632 |
|
|
bitmap_obstack_release (&grand_bitmap_obstack);
|
2633 |
|
|
free_alloc_pool (value_set_pool);
|
2634 |
|
|
free_alloc_pool (bitmap_set_pool);
|
2635 |
|
|
free_alloc_pool (value_set_node_pool);
|
2636 |
|
|
free_alloc_pool (binary_node_pool);
|
2637 |
|
|
free_alloc_pool (reference_node_pool);
|
2638 |
|
|
free_alloc_pool (unary_node_pool);
|
2639 |
|
|
free_alloc_pool (list_node_pool);
|
2640 |
|
|
free_alloc_pool (expression_node_pool);
|
2641 |
|
|
free_alloc_pool (comparison_node_pool);
|
2642 |
|
|
htab_delete (phi_translate_table);
|
2643 |
|
|
remove_fake_exit_edges ();
|
2644 |
|
|
|
2645 |
|
|
FOR_ALL_BB (bb)
|
2646 |
|
|
{
|
2647 |
|
|
free (bb->aux);
|
2648 |
|
|
bb->aux = NULL;
|
2649 |
|
|
}
|
2650 |
|
|
|
2651 |
|
|
free_dominance_info (CDI_POST_DOMINATORS);
|
2652 |
|
|
vn_delete ();
|
2653 |
|
|
|
2654 |
|
|
if (!bitmap_empty_p (need_eh_cleanup))
|
2655 |
|
|
{
|
2656 |
|
|
tree_purge_all_dead_eh_edges (need_eh_cleanup);
|
2657 |
|
|
cleanup_tree_cfg ();
|
2658 |
|
|
}
|
2659 |
|
|
|
2660 |
|
|
BITMAP_FREE (need_eh_cleanup);
|
2661 |
|
|
|
2662 |
|
|
/* Wipe out pointers to VALUE_HANDLEs. In the not terribly distant
|
2663 |
|
|
future we will want them to be persistent though. */
|
2664 |
|
|
for (i = 0; i < num_ssa_names; i++)
|
2665 |
|
|
{
|
2666 |
|
|
tree name = ssa_name (i);
|
2667 |
|
|
|
2668 |
|
|
if (!name)
|
2669 |
|
|
continue;
|
2670 |
|
|
|
2671 |
|
|
if (SSA_NAME_VALUE (name)
|
2672 |
|
|
&& TREE_CODE (SSA_NAME_VALUE (name)) == VALUE_HANDLE)
|
2673 |
|
|
SSA_NAME_VALUE (name) = NULL;
|
2674 |
|
|
}
|
2675 |
|
|
if (!do_fre && current_loops)
|
2676 |
|
|
{
|
2677 |
|
|
loop_optimizer_finalize (current_loops, dump_file);
|
2678 |
|
|
current_loops = NULL;
|
2679 |
|
|
}
|
2680 |
|
|
}
|
2681 |
|
|
|
2682 |
|
|
|
2683 |
|
|
/* Main entry point to the SSA-PRE pass. DO_FRE is true if the caller
|
2684 |
|
|
only wants to do full redundancy elimination. */
|
2685 |
|
|
|
2686 |
|
|
static void
|
2687 |
|
|
execute_pre (bool do_fre)
|
2688 |
|
|
{
|
2689 |
|
|
init_pre (do_fre);
|
2690 |
|
|
|
2691 |
|
|
/* Collect and value number expressions computed in each basic block. */
|
2692 |
|
|
compute_avail ();
|
2693 |
|
|
|
2694 |
|
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
2695 |
|
|
{
|
2696 |
|
|
basic_block bb;
|
2697 |
|
|
|
2698 |
|
|
FOR_ALL_BB (bb)
|
2699 |
|
|
{
|
2700 |
|
|
print_value_set (dump_file, EXP_GEN (bb), "exp_gen", bb->index);
|
2701 |
|
|
bitmap_print_value_set (dump_file, TMP_GEN (bb), "tmp_gen",
|
2702 |
|
|
bb->index);
|
2703 |
|
|
bitmap_print_value_set (dump_file, AVAIL_OUT (bb), "avail_out",
|
2704 |
|
|
bb->index);
|
2705 |
|
|
}
|
2706 |
|
|
}
|
2707 |
|
|
|
2708 |
|
|
/* Insert can get quite slow on an incredibly large number of basic
|
2709 |
|
|
blocks due to some quadratic behavior. Until this behavior is
|
2710 |
|
|
fixed, don't run it when he have an incredibly large number of
|
2711 |
|
|
bb's. If we aren't going to run insert, there is no point in
|
2712 |
|
|
computing ANTIC, either, even though it's plenty fast. */
|
2713 |
|
|
if (!do_fre && n_basic_blocks < 4000)
|
2714 |
|
|
{
|
2715 |
|
|
compute_antic ();
|
2716 |
|
|
insert ();
|
2717 |
|
|
}
|
2718 |
|
|
|
2719 |
|
|
/* Remove all the redundant expressions. */
|
2720 |
|
|
eliminate ();
|
2721 |
|
|
|
2722 |
|
|
|
2723 |
|
|
if (dump_file && (dump_flags & TDF_STATS))
|
2724 |
|
|
{
|
2725 |
|
|
fprintf (dump_file, "Insertions: %d\n", pre_stats.insertions);
|
2726 |
|
|
fprintf (dump_file, "New PHIs: %d\n", pre_stats.phis);
|
2727 |
|
|
fprintf (dump_file, "Eliminated: %d\n", pre_stats.eliminations);
|
2728 |
|
|
fprintf (dump_file, "Constified: %d\n", pre_stats.constified);
|
2729 |
|
|
}
|
2730 |
|
|
|
2731 |
|
|
bsi_commit_edge_inserts ();
|
2732 |
|
|
if (!do_fre)
|
2733 |
|
|
remove_dead_inserted_code ();
|
2734 |
|
|
fini_pre (do_fre);
|
2735 |
|
|
|
2736 |
|
|
}
|
2737 |
|
|
|
2738 |
|
|
|
2739 |
|
|
/* Gate and execute functions for PRE. */
|
2740 |
|
|
|
2741 |
|
|
static void
|
2742 |
|
|
do_pre (void)
|
2743 |
|
|
{
|
2744 |
|
|
execute_pre (false);
|
2745 |
|
|
}
|
2746 |
|
|
|
2747 |
|
|
static bool
|
2748 |
|
|
gate_pre (void)
|
2749 |
|
|
{
|
2750 |
|
|
return flag_tree_pre != 0;
|
2751 |
|
|
}
|
2752 |
|
|
|
2753 |
|
|
struct tree_opt_pass pass_pre =
|
2754 |
|
|
{
|
2755 |
|
|
"pre", /* name */
|
2756 |
|
|
gate_pre, /* gate */
|
2757 |
|
|
do_pre, /* execute */
|
2758 |
|
|
NULL, /* sub */
|
2759 |
|
|
NULL, /* next */
|
2760 |
|
|
0, /* static_pass_number */
|
2761 |
|
|
TV_TREE_PRE, /* tv_id */
|
2762 |
|
|
PROP_no_crit_edges | PROP_cfg
|
2763 |
|
|
| PROP_ssa | PROP_alias, /* properties_required */
|
2764 |
|
|
0, /* properties_provided */
|
2765 |
|
|
0, /* properties_destroyed */
|
2766 |
|
|
0, /* todo_flags_start */
|
2767 |
|
|
TODO_update_ssa | TODO_dump_func | TODO_ggc_collect
|
2768 |
|
|
| TODO_verify_ssa, /* todo_flags_finish */
|
2769 |
|
|
|
2770 |
|
|
};
|
2771 |
|
|
|
2772 |
|
|
|
2773 |
|
|
/* Gate and execute functions for FRE. */
|
2774 |
|
|
|
2775 |
|
|
static void
|
2776 |
|
|
execute_fre (void)
|
2777 |
|
|
{
|
2778 |
|
|
execute_pre (true);
|
2779 |
|
|
}
|
2780 |
|
|
|
2781 |
|
|
static bool
|
2782 |
|
|
gate_fre (void)
|
2783 |
|
|
{
|
2784 |
|
|
return flag_tree_fre != 0;
|
2785 |
|
|
}
|
2786 |
|
|
|
2787 |
|
|
struct tree_opt_pass pass_fre =
|
2788 |
|
|
{
|
2789 |
|
|
"fre", /* name */
|
2790 |
|
|
gate_fre, /* gate */
|
2791 |
|
|
execute_fre, /* execute */
|
2792 |
|
|
NULL, /* sub */
|
2793 |
|
|
NULL, /* next */
|
2794 |
|
|
0, /* static_pass_number */
|
2795 |
|
|
TV_TREE_FRE, /* tv_id */
|
2796 |
|
|
PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */
|
2797 |
|
|
0, /* properties_provided */
|
2798 |
|
|
0, /* properties_destroyed */
|
2799 |
|
|
0, /* todo_flags_start */
|
2800 |
|
|
TODO_dump_func | TODO_ggc_collect | TODO_verify_ssa, /* todo_flags_finish */
|
2801 |
|
|
|
2802 |
|
|
};
|
2803 |
|
|
|
2804 |
|
|
/* Return true if T is a copy statement between two ssa names. */
|
2805 |
|
|
|
2806 |
|
|
static bool
|
2807 |
|
|
is_copy_stmt (tree t)
|
2808 |
|
|
{
|
2809 |
|
|
if (!t || TREE_CODE (t) != MODIFY_EXPR)
|
2810 |
|
|
return false;
|
2811 |
|
|
if (TREE_CODE (TREE_OPERAND (t, 0)) == SSA_NAME
|
2812 |
|
|
&& TREE_CODE (TREE_OPERAND (t, 1)) == SSA_NAME)
|
2813 |
|
|
return true;
|
2814 |
|
|
return false;
|
2815 |
|
|
}
|
2816 |
|
|
|
2817 |
|
|
/* Starting from START, walk copy statements till we hit a statement with a
|
2818 |
|
|
VUSE or a non-copy statement. */
|
2819 |
|
|
|
2820 |
|
|
static tree
|
2821 |
|
|
follow_copies_till_vuse (tree start)
|
2822 |
|
|
{
|
2823 |
|
|
if (is_copy_stmt (start) && ZERO_SSA_OPERANDS (start, SSA_OP_VIRTUAL_USES))
|
2824 |
|
|
{
|
2825 |
|
|
tree rhs, defstmt;
|
2826 |
|
|
|
2827 |
|
|
rhs = TREE_OPERAND (start, 1);
|
2828 |
|
|
defstmt = SSA_NAME_DEF_STMT (rhs);
|
2829 |
|
|
return follow_copies_till_vuse (defstmt);
|
2830 |
|
|
}
|
2831 |
|
|
return start;
|
2832 |
|
|
}
|
2833 |
|
|
|
2834 |
|
|
/* Gate and execute functions for eliminate useless stores.
|
2835 |
|
|
The goal here is to recognize the pattern *x = ... *x, and eliminate the
|
2836 |
|
|
store because the value hasn't changed. Store copy/const prop won't
|
2837 |
|
|
do this because making *more* loads (IE propagating *x) is not a win, so it
|
2838 |
|
|
ignores them.
|
2839 |
|
|
This pass is currently geared completely towards static variable store
|
2840 |
|
|
elimination. */
|
2841 |
|
|
|
2842 |
|
|
static void
|
2843 |
|
|
do_eustores (void)
|
2844 |
|
|
{
|
2845 |
|
|
basic_block bb;
|
2846 |
|
|
/* For each basic block
|
2847 |
|
|
For each statement (STMT) in the block
|
2848 |
|
|
if STMT is a stores of the pattern *x = y
|
2849 |
|
|
follow the chain of definitions for y, until we hit a non-copy
|
2850 |
|
|
statement or a statement with a vuse.
|
2851 |
|
|
if the statement we arrive at is a vuse of the operand we killed,
|
2852 |
|
|
accessed through the same memory operation, then we have a
|
2853 |
|
|
useless store (because it is *x = ... = *x). */
|
2854 |
|
|
|
2855 |
|
|
FOR_EACH_BB (bb)
|
2856 |
|
|
{
|
2857 |
|
|
block_stmt_iterator bsi;
|
2858 |
|
|
|
2859 |
|
|
for (bsi = bsi_start (bb);
|
2860 |
|
|
!bsi_end_p (bsi);)
|
2861 |
|
|
{
|
2862 |
|
|
tree stmt = bsi_stmt (bsi);
|
2863 |
|
|
tree startat;
|
2864 |
|
|
tree kill;
|
2865 |
|
|
tree found;
|
2866 |
|
|
|
2867 |
|
|
if (NUM_SSA_OPERANDS (stmt, SSA_OP_VMUSTDEF) != 1
|
2868 |
|
|
|| TREE_CODE (stmt) != MODIFY_EXPR
|
2869 |
|
|
|| TREE_CODE (TREE_OPERAND (stmt, 1)) != SSA_NAME)
|
2870 |
|
|
{
|
2871 |
|
|
bsi_next (&bsi);
|
2872 |
|
|
continue;
|
2873 |
|
|
}
|
2874 |
|
|
|
2875 |
|
|
kill = MUSTDEF_KILL (MUSTDEF_OPS (stmt));
|
2876 |
|
|
startat = TREE_OPERAND (stmt, 1);
|
2877 |
|
|
startat = SSA_NAME_DEF_STMT (startat);
|
2878 |
|
|
found = follow_copies_till_vuse (startat);
|
2879 |
|
|
|
2880 |
|
|
if (found && TREE_CODE (found) == MODIFY_EXPR)
|
2881 |
|
|
{
|
2882 |
|
|
|
2883 |
|
|
/* We want exactly one virtual use, and it should match up with
|
2884 |
|
|
the use being killed. */
|
2885 |
|
|
|
2886 |
|
|
if (NUM_SSA_OPERANDS (found, SSA_OP_VUSE) != 1
|
2887 |
|
|
|| VUSE_OP (VUSE_OPS (found)) != kill
|
2888 |
|
|
|| !DECL_P (TREE_OPERAND (stmt, 0))
|
2889 |
|
|
|| !operand_equal_p (TREE_OPERAND (found, 1),
|
2890 |
|
|
TREE_OPERAND (stmt, 0), 0))
|
2891 |
|
|
{
|
2892 |
|
|
bsi_next (&bsi);
|
2893 |
|
|
continue;
|
2894 |
|
|
}
|
2895 |
|
|
|
2896 |
|
|
if (dump_file)
|
2897 |
|
|
{
|
2898 |
|
|
fprintf (dump_file, "Eliminating useless store ");
|
2899 |
|
|
print_generic_stmt (dump_file, stmt, 0);
|
2900 |
|
|
}
|
2901 |
|
|
mark_sym_for_renaming (TREE_OPERAND (stmt, 0));
|
2902 |
|
|
bsi_remove (&bsi);
|
2903 |
|
|
}
|
2904 |
|
|
else
|
2905 |
|
|
{
|
2906 |
|
|
bsi_next (&bsi);
|
2907 |
|
|
continue;
|
2908 |
|
|
}
|
2909 |
|
|
}
|
2910 |
|
|
}
|
2911 |
|
|
}
|
2912 |
|
|
|
2913 |
|
|
static bool
|
2914 |
|
|
gate_eustores(void)
|
2915 |
|
|
{
|
2916 |
|
|
return flag_unit_at_a_time != 0;
|
2917 |
|
|
}
|
2918 |
|
|
|
2919 |
|
|
struct tree_opt_pass pass_eliminate_useless_stores =
|
2920 |
|
|
{
|
2921 |
|
|
"eustores", /* name */
|
2922 |
|
|
gate_eustores, /* gate */
|
2923 |
|
|
do_eustores, /* execute */
|
2924 |
|
|
NULL, /* sub */
|
2925 |
|
|
NULL, /* next */
|
2926 |
|
|
0, /* static_pass_number */
|
2927 |
|
|
0, /* tv_id */
|
2928 |
|
|
PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */
|
2929 |
|
|
0, /* properties_provided */
|
2930 |
|
|
0, /* properties_destroyed */
|
2931 |
|
|
0, /* todo_flags_start */
|
2932 |
|
|
TODO_update_ssa | TODO_dump_func
|
2933 |
|
|
| TODO_ggc_collect | TODO_verify_ssa, /* todo_flags_finish */
|
2934 |
|
|
|
2935 |
|
|
};
|