1 |
12 |
jlechner |
/* Forward propagation of expressions for single use variables.
|
2 |
|
|
Copyright (C) 2004, 2005 Free Software Foundation, Inc.
|
3 |
|
|
|
4 |
|
|
This file is part of GCC.
|
5 |
|
|
|
6 |
|
|
GCC is free software; you can redistribute it and/or modify
|
7 |
|
|
it under the terms of the GNU General Public License as published by
|
8 |
|
|
the Free Software Foundation; either version 2, or (at your option)
|
9 |
|
|
any later version.
|
10 |
|
|
|
11 |
|
|
GCC is distributed in the hope that it will be useful,
|
12 |
|
|
but WITHOUT ANY WARRANTY; without even the implied warranty of
|
13 |
|
|
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
14 |
|
|
GNU General Public License for more details.
|
15 |
|
|
|
16 |
|
|
You should have received a copy of the GNU General Public License
|
17 |
|
|
along with GCC; see the file COPYING. If not, write to
|
18 |
|
|
the Free Software Foundation, 51 Franklin Street, Fifth Floor,
|
19 |
|
|
Boston, MA 02110-1301, USA. */
|
20 |
|
|
|
21 |
|
|
#include "config.h"
|
22 |
|
|
#include "system.h"
|
23 |
|
|
#include "coretypes.h"
|
24 |
|
|
#include "tm.h"
|
25 |
|
|
#include "ggc.h"
|
26 |
|
|
#include "tree.h"
|
27 |
|
|
#include "rtl.h"
|
28 |
|
|
#include "tm_p.h"
|
29 |
|
|
#include "basic-block.h"
|
30 |
|
|
#include "timevar.h"
|
31 |
|
|
#include "diagnostic.h"
|
32 |
|
|
#include "tree-flow.h"
|
33 |
|
|
#include "tree-pass.h"
|
34 |
|
|
#include "tree-dump.h"
|
35 |
|
|
#include "langhooks.h"
|
36 |
|
|
|
37 |
|
|
/* This pass propagates the RHS of assignment statements into use
|
38 |
|
|
sites of the LHS of the assignment. It's basically a specialized
|
39 |
|
|
form of tree combination.
|
40 |
|
|
|
41 |
|
|
Note carefully that after propagation the resulting statement
|
42 |
|
|
must still be a proper gimple statement. Right now we simply
|
43 |
|
|
only perform propagations we know will result in valid gimple
|
44 |
|
|
code. One day we'll want to generalize this code.
|
45 |
|
|
|
46 |
|
|
One class of common cases we handle is forward propagating a single use
|
47 |
|
|
variable into a COND_EXPR.
|
48 |
|
|
|
49 |
|
|
bb0:
|
50 |
|
|
x = a COND b;
|
51 |
|
|
if (x) goto ... else goto ...
|
52 |
|
|
|
53 |
|
|
Will be transformed into:
|
54 |
|
|
|
55 |
|
|
bb0:
|
56 |
|
|
if (a COND b) goto ... else goto ...
|
57 |
|
|
|
58 |
|
|
Similarly for the tests (x == 0), (x != 0), (x == 1) and (x != 1).
|
59 |
|
|
|
60 |
|
|
Or (assuming c1 and c2 are constants):
|
61 |
|
|
|
62 |
|
|
bb0:
|
63 |
|
|
x = a + c1;
|
64 |
|
|
if (x EQ/NEQ c2) goto ... else goto ...
|
65 |
|
|
|
66 |
|
|
Will be transformed into:
|
67 |
|
|
|
68 |
|
|
bb0:
|
69 |
|
|
if (a EQ/NEQ (c2 - c1)) goto ... else goto ...
|
70 |
|
|
|
71 |
|
|
Similarly for x = a - c1.
|
72 |
|
|
|
73 |
|
|
Or
|
74 |
|
|
|
75 |
|
|
bb0:
|
76 |
|
|
x = !a
|
77 |
|
|
if (x) goto ... else goto ...
|
78 |
|
|
|
79 |
|
|
Will be transformed into:
|
80 |
|
|
|
81 |
|
|
bb0:
|
82 |
|
|
if (a == 0) goto ... else goto ...
|
83 |
|
|
|
84 |
|
|
Similarly for the tests (x == 0), (x != 0), (x == 1) and (x != 1).
|
85 |
|
|
For these cases, we propagate A into all, possibly more than one,
|
86 |
|
|
COND_EXPRs that use X.
|
87 |
|
|
|
88 |
|
|
Or
|
89 |
|
|
|
90 |
|
|
bb0:
|
91 |
|
|
x = (typecast) a
|
92 |
|
|
if (x) goto ... else goto ...
|
93 |
|
|
|
94 |
|
|
Will be transformed into:
|
95 |
|
|
|
96 |
|
|
bb0:
|
97 |
|
|
if (a != 0) goto ... else goto ...
|
98 |
|
|
|
99 |
|
|
(Assuming a is an integral type and x is a boolean or x is an
|
100 |
|
|
integral and a is a boolean.)
|
101 |
|
|
|
102 |
|
|
Similarly for the tests (x == 0), (x != 0), (x == 1) and (x != 1).
|
103 |
|
|
For these cases, we propagate A into all, possibly more than one,
|
104 |
|
|
COND_EXPRs that use X.
|
105 |
|
|
|
106 |
|
|
In addition to eliminating the variable and the statement which assigns
|
107 |
|
|
a value to the variable, we may be able to later thread the jump without
|
108 |
|
|
adding insane complexity in the dominator optimizer.
|
109 |
|
|
|
110 |
|
|
Also note these transformations can cascade. We handle this by having
|
111 |
|
|
a worklist of COND_EXPR statements to examine. As we make a change to
|
112 |
|
|
a statement, we put it back on the worklist to examine on the next
|
113 |
|
|
iteration of the main loop.
|
114 |
|
|
|
115 |
|
|
A second class of propagation opportunities arises for ADDR_EXPR
|
116 |
|
|
nodes.
|
117 |
|
|
|
118 |
|
|
ptr = &x->y->z;
|
119 |
|
|
res = *ptr;
|
120 |
|
|
|
121 |
|
|
Will get turned into
|
122 |
|
|
|
123 |
|
|
res = x->y->z;
|
124 |
|
|
|
125 |
|
|
Or
|
126 |
|
|
|
127 |
|
|
ptr = &x[0];
|
128 |
|
|
ptr2 = ptr + <constant>;
|
129 |
|
|
|
130 |
|
|
Will get turned into
|
131 |
|
|
|
132 |
|
|
ptr2 = &x[constant/elementsize];
|
133 |
|
|
|
134 |
|
|
Or
|
135 |
|
|
|
136 |
|
|
ptr = &x[0];
|
137 |
|
|
offset = index * element_size;
|
138 |
|
|
offset_p = (pointer) offset;
|
139 |
|
|
ptr2 = ptr + offset_p
|
140 |
|
|
|
141 |
|
|
Will get turned into:
|
142 |
|
|
|
143 |
|
|
ptr2 = &x[index];
|
144 |
|
|
|
145 |
|
|
|
146 |
|
|
This will (of course) be extended as other needs arise. */
|
147 |
|
|
|
148 |
|
|
|
149 |
|
|
/* Set to true if we delete EH edges during the optimization. */
|
150 |
|
|
static bool cfg_changed;
|
151 |
|
|
|
152 |
|
|
|
153 |
|
|
/* Given an SSA_NAME VAR, return true if and only if VAR is defined by
|
154 |
|
|
a comparison. */
|
155 |
|
|
|
156 |
|
|
static bool
|
157 |
|
|
ssa_name_defined_by_comparison_p (tree var)
|
158 |
|
|
{
|
159 |
|
|
tree def = SSA_NAME_DEF_STMT (var);
|
160 |
|
|
|
161 |
|
|
if (TREE_CODE (def) == MODIFY_EXPR)
|
162 |
|
|
{
|
163 |
|
|
tree rhs = TREE_OPERAND (def, 1);
|
164 |
|
|
return COMPARISON_CLASS_P (rhs);
|
165 |
|
|
}
|
166 |
|
|
|
167 |
|
|
return 0;
|
168 |
|
|
}
|
169 |
|
|
|
170 |
|
|
/* Forward propagate a single-use variable into COND once. Return a
|
171 |
|
|
new condition if successful. Return NULL_TREE otherwise. */
|
172 |
|
|
|
173 |
|
|
static tree
|
174 |
|
|
forward_propagate_into_cond_1 (tree cond, tree *test_var_p)
|
175 |
|
|
{
|
176 |
|
|
tree new_cond = NULL_TREE;
|
177 |
|
|
enum tree_code cond_code = TREE_CODE (cond);
|
178 |
|
|
tree test_var = NULL_TREE;
|
179 |
|
|
tree def;
|
180 |
|
|
tree def_rhs;
|
181 |
|
|
|
182 |
|
|
/* If the condition is not a lone variable or an equality test of an
|
183 |
|
|
SSA_NAME against an integral constant, then we do not have an
|
184 |
|
|
optimizable case.
|
185 |
|
|
|
186 |
|
|
Note these conditions also ensure the COND_EXPR has no
|
187 |
|
|
virtual operands or other side effects. */
|
188 |
|
|
if (cond_code != SSA_NAME
|
189 |
|
|
&& !((cond_code == EQ_EXPR || cond_code == NE_EXPR)
|
190 |
|
|
&& TREE_CODE (TREE_OPERAND (cond, 0)) == SSA_NAME
|
191 |
|
|
&& CONSTANT_CLASS_P (TREE_OPERAND (cond, 1))
|
192 |
|
|
&& INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (cond, 1)))))
|
193 |
|
|
return NULL_TREE;
|
194 |
|
|
|
195 |
|
|
/* Extract the single variable used in the test into TEST_VAR. */
|
196 |
|
|
if (cond_code == SSA_NAME)
|
197 |
|
|
test_var = cond;
|
198 |
|
|
else
|
199 |
|
|
test_var = TREE_OPERAND (cond, 0);
|
200 |
|
|
|
201 |
|
|
/* Now get the defining statement for TEST_VAR. Skip this case if
|
202 |
|
|
it's not defined by some MODIFY_EXPR. */
|
203 |
|
|
def = SSA_NAME_DEF_STMT (test_var);
|
204 |
|
|
if (TREE_CODE (def) != MODIFY_EXPR)
|
205 |
|
|
return NULL_TREE;
|
206 |
|
|
|
207 |
|
|
def_rhs = TREE_OPERAND (def, 1);
|
208 |
|
|
|
209 |
|
|
/* If TEST_VAR is set by adding or subtracting a constant
|
210 |
|
|
from an SSA_NAME, then it is interesting to us as we
|
211 |
|
|
can adjust the constant in the conditional and thus
|
212 |
|
|
eliminate the arithmetic operation. */
|
213 |
|
|
if (TREE_CODE (def_rhs) == PLUS_EXPR
|
214 |
|
|
|| TREE_CODE (def_rhs) == MINUS_EXPR)
|
215 |
|
|
{
|
216 |
|
|
tree op0 = TREE_OPERAND (def_rhs, 0);
|
217 |
|
|
tree op1 = TREE_OPERAND (def_rhs, 1);
|
218 |
|
|
|
219 |
|
|
/* The first operand must be an SSA_NAME and the second
|
220 |
|
|
operand must be a constant. */
|
221 |
|
|
if (TREE_CODE (op0) != SSA_NAME
|
222 |
|
|
|| !CONSTANT_CLASS_P (op1)
|
223 |
|
|
|| !INTEGRAL_TYPE_P (TREE_TYPE (op1)))
|
224 |
|
|
return NULL_TREE;
|
225 |
|
|
|
226 |
|
|
/* Don't propagate if the first operand occurs in
|
227 |
|
|
an abnormal PHI. */
|
228 |
|
|
if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0))
|
229 |
|
|
return NULL_TREE;
|
230 |
|
|
|
231 |
|
|
if (has_single_use (test_var))
|
232 |
|
|
{
|
233 |
|
|
enum tree_code new_code;
|
234 |
|
|
tree t;
|
235 |
|
|
|
236 |
|
|
/* If the variable was defined via X + C, then we must
|
237 |
|
|
subtract C from the constant in the conditional.
|
238 |
|
|
Otherwise we add C to the constant in the
|
239 |
|
|
conditional. The result must fold into a valid
|
240 |
|
|
gimple operand to be optimizable. */
|
241 |
|
|
new_code = (TREE_CODE (def_rhs) == PLUS_EXPR
|
242 |
|
|
? MINUS_EXPR : PLUS_EXPR);
|
243 |
|
|
t = int_const_binop (new_code, TREE_OPERAND (cond, 1), op1, 0);
|
244 |
|
|
if (!is_gimple_val (t))
|
245 |
|
|
return NULL_TREE;
|
246 |
|
|
|
247 |
|
|
new_cond = build (cond_code, boolean_type_node, op0, t);
|
248 |
|
|
}
|
249 |
|
|
}
|
250 |
|
|
|
251 |
|
|
/* These cases require comparisons of a naked SSA_NAME or
|
252 |
|
|
comparison of an SSA_NAME against zero or one. */
|
253 |
|
|
else if (TREE_CODE (cond) == SSA_NAME
|
254 |
|
|
|| integer_zerop (TREE_OPERAND (cond, 1))
|
255 |
|
|
|| integer_onep (TREE_OPERAND (cond, 1)))
|
256 |
|
|
{
|
257 |
|
|
/* If TEST_VAR is set from a relational operation
|
258 |
|
|
between two SSA_NAMEs or a combination of an SSA_NAME
|
259 |
|
|
and a constant, then it is interesting. */
|
260 |
|
|
if (COMPARISON_CLASS_P (def_rhs))
|
261 |
|
|
{
|
262 |
|
|
tree op0 = TREE_OPERAND (def_rhs, 0);
|
263 |
|
|
tree op1 = TREE_OPERAND (def_rhs, 1);
|
264 |
|
|
|
265 |
|
|
/* Both operands of DEF_RHS must be SSA_NAMEs or
|
266 |
|
|
constants. */
|
267 |
|
|
if ((TREE_CODE (op0) != SSA_NAME
|
268 |
|
|
&& !is_gimple_min_invariant (op0))
|
269 |
|
|
|| (TREE_CODE (op1) != SSA_NAME
|
270 |
|
|
&& !is_gimple_min_invariant (op1)))
|
271 |
|
|
return NULL_TREE;
|
272 |
|
|
|
273 |
|
|
/* Don't propagate if the first operand occurs in
|
274 |
|
|
an abnormal PHI. */
|
275 |
|
|
if (TREE_CODE (op0) == SSA_NAME
|
276 |
|
|
&& SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0))
|
277 |
|
|
return NULL_TREE;
|
278 |
|
|
|
279 |
|
|
/* Don't propagate if the second operand occurs in
|
280 |
|
|
an abnormal PHI. */
|
281 |
|
|
if (TREE_CODE (op1) == SSA_NAME
|
282 |
|
|
&& SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op1))
|
283 |
|
|
return NULL_TREE;
|
284 |
|
|
|
285 |
|
|
if (has_single_use (test_var))
|
286 |
|
|
{
|
287 |
|
|
/* TEST_VAR was set from a relational operator. */
|
288 |
|
|
new_cond = build (TREE_CODE (def_rhs),
|
289 |
|
|
boolean_type_node, op0, op1);
|
290 |
|
|
|
291 |
|
|
/* Invert the conditional if necessary. */
|
292 |
|
|
if ((cond_code == EQ_EXPR
|
293 |
|
|
&& integer_zerop (TREE_OPERAND (cond, 1)))
|
294 |
|
|
|| (cond_code == NE_EXPR
|
295 |
|
|
&& integer_onep (TREE_OPERAND (cond, 1))))
|
296 |
|
|
{
|
297 |
|
|
new_cond = invert_truthvalue (new_cond);
|
298 |
|
|
|
299 |
|
|
/* If we did not get a simple relational
|
300 |
|
|
expression or bare SSA_NAME, then we can
|
301 |
|
|
not optimize this case. */
|
302 |
|
|
if (!COMPARISON_CLASS_P (new_cond)
|
303 |
|
|
&& TREE_CODE (new_cond) != SSA_NAME)
|
304 |
|
|
new_cond = NULL_TREE;
|
305 |
|
|
}
|
306 |
|
|
}
|
307 |
|
|
}
|
308 |
|
|
|
309 |
|
|
/* If TEST_VAR is set from a TRUTH_NOT_EXPR, then it
|
310 |
|
|
is interesting. */
|
311 |
|
|
else if (TREE_CODE (def_rhs) == TRUTH_NOT_EXPR)
|
312 |
|
|
{
|
313 |
|
|
enum tree_code new_code;
|
314 |
|
|
|
315 |
|
|
def_rhs = TREE_OPERAND (def_rhs, 0);
|
316 |
|
|
|
317 |
|
|
/* DEF_RHS must be an SSA_NAME or constant. */
|
318 |
|
|
if (TREE_CODE (def_rhs) != SSA_NAME
|
319 |
|
|
&& !is_gimple_min_invariant (def_rhs))
|
320 |
|
|
return NULL_TREE;
|
321 |
|
|
|
322 |
|
|
/* Don't propagate if the operand occurs in
|
323 |
|
|
an abnormal PHI. */
|
324 |
|
|
if (TREE_CODE (def_rhs) == SSA_NAME
|
325 |
|
|
&& SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def_rhs))
|
326 |
|
|
return NULL_TREE;
|
327 |
|
|
|
328 |
|
|
if (cond_code == SSA_NAME
|
329 |
|
|
|| (cond_code == NE_EXPR
|
330 |
|
|
&& integer_zerop (TREE_OPERAND (cond, 1)))
|
331 |
|
|
|| (cond_code == EQ_EXPR
|
332 |
|
|
&& integer_onep (TREE_OPERAND (cond, 1))))
|
333 |
|
|
new_code = EQ_EXPR;
|
334 |
|
|
else
|
335 |
|
|
new_code = NE_EXPR;
|
336 |
|
|
|
337 |
|
|
new_cond = build2 (new_code, boolean_type_node, def_rhs,
|
338 |
|
|
fold_convert (TREE_TYPE (def_rhs),
|
339 |
|
|
integer_zero_node));
|
340 |
|
|
}
|
341 |
|
|
|
342 |
|
|
/* If TEST_VAR was set from a cast of an integer type
|
343 |
|
|
to a boolean type or a cast of a boolean to an
|
344 |
|
|
integral, then it is interesting. */
|
345 |
|
|
else if (TREE_CODE (def_rhs) == NOP_EXPR
|
346 |
|
|
|| TREE_CODE (def_rhs) == CONVERT_EXPR)
|
347 |
|
|
{
|
348 |
|
|
tree outer_type;
|
349 |
|
|
tree inner_type;
|
350 |
|
|
|
351 |
|
|
outer_type = TREE_TYPE (def_rhs);
|
352 |
|
|
inner_type = TREE_TYPE (TREE_OPERAND (def_rhs, 0));
|
353 |
|
|
|
354 |
|
|
if ((TREE_CODE (outer_type) == BOOLEAN_TYPE
|
355 |
|
|
&& INTEGRAL_TYPE_P (inner_type))
|
356 |
|
|
|| (TREE_CODE (inner_type) == BOOLEAN_TYPE
|
357 |
|
|
&& INTEGRAL_TYPE_P (outer_type)))
|
358 |
|
|
;
|
359 |
|
|
else if (INTEGRAL_TYPE_P (outer_type)
|
360 |
|
|
&& INTEGRAL_TYPE_P (inner_type)
|
361 |
|
|
&& TREE_CODE (TREE_OPERAND (def_rhs, 0)) == SSA_NAME
|
362 |
|
|
&& ssa_name_defined_by_comparison_p (TREE_OPERAND (def_rhs,
|
363 |
|
|
0)))
|
364 |
|
|
;
|
365 |
|
|
else
|
366 |
|
|
return NULL_TREE;
|
367 |
|
|
|
368 |
|
|
/* Don't propagate if the operand occurs in
|
369 |
|
|
an abnormal PHI. */
|
370 |
|
|
if (TREE_CODE (TREE_OPERAND (def_rhs, 0)) == SSA_NAME
|
371 |
|
|
&& SSA_NAME_OCCURS_IN_ABNORMAL_PHI (TREE_OPERAND
|
372 |
|
|
(def_rhs, 0)))
|
373 |
|
|
return NULL_TREE;
|
374 |
|
|
|
375 |
|
|
if (has_single_use (test_var))
|
376 |
|
|
{
|
377 |
|
|
enum tree_code new_code;
|
378 |
|
|
tree new_arg;
|
379 |
|
|
|
380 |
|
|
if (cond_code == SSA_NAME
|
381 |
|
|
|| (cond_code == NE_EXPR
|
382 |
|
|
&& integer_zerop (TREE_OPERAND (cond, 1)))
|
383 |
|
|
|| (cond_code == EQ_EXPR
|
384 |
|
|
&& integer_onep (TREE_OPERAND (cond, 1))))
|
385 |
|
|
new_code = NE_EXPR;
|
386 |
|
|
else
|
387 |
|
|
new_code = EQ_EXPR;
|
388 |
|
|
|
389 |
|
|
new_arg = TREE_OPERAND (def_rhs, 0);
|
390 |
|
|
new_cond = build2 (new_code, boolean_type_node, new_arg,
|
391 |
|
|
fold_convert (TREE_TYPE (new_arg),
|
392 |
|
|
integer_zero_node));
|
393 |
|
|
}
|
394 |
|
|
}
|
395 |
|
|
}
|
396 |
|
|
|
397 |
|
|
*test_var_p = test_var;
|
398 |
|
|
return new_cond;
|
399 |
|
|
}
|
400 |
|
|
|
401 |
|
|
/* Forward propagate a single-use variable into COND_EXPR as many
|
402 |
|
|
times as possible. */
|
403 |
|
|
|
404 |
|
|
static void
|
405 |
|
|
forward_propagate_into_cond (tree cond_expr)
|
406 |
|
|
{
|
407 |
|
|
gcc_assert (TREE_CODE (cond_expr) == COND_EXPR);
|
408 |
|
|
|
409 |
|
|
while (1)
|
410 |
|
|
{
|
411 |
|
|
tree test_var = NULL_TREE;
|
412 |
|
|
tree cond = COND_EXPR_COND (cond_expr);
|
413 |
|
|
tree new_cond = forward_propagate_into_cond_1 (cond, &test_var);
|
414 |
|
|
|
415 |
|
|
/* Return if unsuccessful. */
|
416 |
|
|
if (new_cond == NULL_TREE)
|
417 |
|
|
break;
|
418 |
|
|
|
419 |
|
|
/* Dump details. */
|
420 |
|
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
421 |
|
|
{
|
422 |
|
|
fprintf (dump_file, " Replaced '");
|
423 |
|
|
print_generic_expr (dump_file, cond, dump_flags);
|
424 |
|
|
fprintf (dump_file, "' with '");
|
425 |
|
|
print_generic_expr (dump_file, new_cond, dump_flags);
|
426 |
|
|
fprintf (dump_file, "'\n");
|
427 |
|
|
}
|
428 |
|
|
|
429 |
|
|
COND_EXPR_COND (cond_expr) = new_cond;
|
430 |
|
|
update_stmt (cond_expr);
|
431 |
|
|
|
432 |
|
|
if (has_zero_uses (test_var))
|
433 |
|
|
{
|
434 |
|
|
tree def = SSA_NAME_DEF_STMT (test_var);
|
435 |
|
|
block_stmt_iterator bsi = bsi_for_stmt (def);
|
436 |
|
|
bsi_remove (&bsi);
|
437 |
|
|
}
|
438 |
|
|
}
|
439 |
|
|
}
|
440 |
|
|
|
441 |
|
|
/* We've just substituted an ADDR_EXPR into stmt. Update all the
|
442 |
|
|
relevant data structures to match. */
|
443 |
|
|
|
444 |
|
|
static void
|
445 |
|
|
tidy_after_forward_propagate_addr (tree stmt)
|
446 |
|
|
{
|
447 |
|
|
mark_new_vars_to_rename (stmt);
|
448 |
|
|
|
449 |
|
|
/* We may have turned a trapping insn into a non-trapping insn. */
|
450 |
|
|
if (maybe_clean_or_replace_eh_stmt (stmt, stmt)
|
451 |
|
|
&& tree_purge_dead_eh_edges (bb_for_stmt (stmt)))
|
452 |
|
|
cfg_changed = true;
|
453 |
|
|
|
454 |
|
|
if (TREE_CODE (TREE_OPERAND (stmt, 1)) == ADDR_EXPR)
|
455 |
|
|
recompute_tree_invarant_for_addr_expr (TREE_OPERAND (stmt, 1));
|
456 |
|
|
|
457 |
|
|
update_stmt (stmt);
|
458 |
|
|
}
|
459 |
|
|
|
460 |
|
|
/* STMT defines LHS which is contains the address of the 0th element
|
461 |
|
|
in an array. USE_STMT uses LHS to compute the address of an
|
462 |
|
|
arbitrary element within the array. The (variable) byte offset
|
463 |
|
|
of the element is contained in OFFSET.
|
464 |
|
|
|
465 |
|
|
We walk back through the use-def chains of OFFSET to verify that
|
466 |
|
|
it is indeed computing the offset of an element within the array
|
467 |
|
|
and extract the index corresponding to the given byte offset.
|
468 |
|
|
|
469 |
|
|
We then try to fold the entire address expression into a form
|
470 |
|
|
&array[index].
|
471 |
|
|
|
472 |
|
|
If we are successful, we replace the right hand side of USE_STMT
|
473 |
|
|
with the new address computation. */
|
474 |
|
|
|
475 |
|
|
static bool
|
476 |
|
|
forward_propagate_addr_into_variable_array_index (tree offset, tree lhs,
|
477 |
|
|
tree stmt, tree use_stmt)
|
478 |
|
|
{
|
479 |
|
|
tree index;
|
480 |
|
|
|
481 |
|
|
/* The offset must be defined by a simple MODIFY_EXPR statement. */
|
482 |
|
|
if (TREE_CODE (offset) != MODIFY_EXPR)
|
483 |
|
|
return false;
|
484 |
|
|
|
485 |
|
|
/* The RHS of the statement which defines OFFSET must be a gimple
|
486 |
|
|
cast of another SSA_NAME. */
|
487 |
|
|
offset = TREE_OPERAND (offset, 1);
|
488 |
|
|
if (!is_gimple_cast (offset))
|
489 |
|
|
return false;
|
490 |
|
|
|
491 |
|
|
offset = TREE_OPERAND (offset, 0);
|
492 |
|
|
if (TREE_CODE (offset) != SSA_NAME)
|
493 |
|
|
return false;
|
494 |
|
|
|
495 |
|
|
/* Get the defining statement of the offset before type
|
496 |
|
|
conversion. */
|
497 |
|
|
offset = SSA_NAME_DEF_STMT (offset);
|
498 |
|
|
|
499 |
|
|
/* The statement which defines OFFSET before type conversion
|
500 |
|
|
must be a simple MODIFY_EXPR. */
|
501 |
|
|
if (TREE_CODE (offset) != MODIFY_EXPR)
|
502 |
|
|
return false;
|
503 |
|
|
|
504 |
|
|
/* The RHS of the statement which defines OFFSET must be a
|
505 |
|
|
multiplication of an object by the size of the array elements.
|
506 |
|
|
This implicitly verifies that the size of the array elements
|
507 |
|
|
is constant. */
|
508 |
|
|
offset = TREE_OPERAND (offset, 1);
|
509 |
|
|
if (TREE_CODE (offset) != MULT_EXPR
|
510 |
|
|
|| TREE_CODE (TREE_OPERAND (offset, 1)) != INTEGER_CST
|
511 |
|
|
|| !simple_cst_equal (TREE_OPERAND (offset, 1),
|
512 |
|
|
TYPE_SIZE_UNIT (TREE_TYPE (TREE_TYPE (lhs)))))
|
513 |
|
|
return false;
|
514 |
|
|
|
515 |
|
|
/* The first operand to the MULT_EXPR is the desired index. */
|
516 |
|
|
index = TREE_OPERAND (offset, 0);
|
517 |
|
|
|
518 |
|
|
/* Replace the pointer addition with array indexing. */
|
519 |
|
|
TREE_OPERAND (use_stmt, 1) = unshare_expr (TREE_OPERAND (stmt, 1));
|
520 |
|
|
TREE_OPERAND (TREE_OPERAND (TREE_OPERAND (use_stmt, 1), 0), 1) = index;
|
521 |
|
|
|
522 |
|
|
/* That should have created gimple, so there is no need to
|
523 |
|
|
record information to undo the propagation. */
|
524 |
|
|
fold_stmt_inplace (use_stmt);
|
525 |
|
|
tidy_after_forward_propagate_addr (use_stmt);
|
526 |
|
|
return true;
|
527 |
|
|
}
|
528 |
|
|
|
529 |
|
|
/* STMT is a statement of the form SSA_NAME = ADDR_EXPR <whatever>.
|
530 |
|
|
|
531 |
|
|
Try to forward propagate the ADDR_EXPR into the uses of the SSA_NAME.
|
532 |
|
|
Often this will allow for removal of an ADDR_EXPR and INDIRECT_REF
|
533 |
|
|
node or for recovery of array indexing from pointer arithmetic. */
|
534 |
|
|
|
535 |
|
|
static bool
|
536 |
|
|
forward_propagate_addr_expr (tree stmt)
|
537 |
|
|
{
|
538 |
|
|
int stmt_loop_depth = bb_for_stmt (stmt)->loop_depth;
|
539 |
|
|
tree name = TREE_OPERAND (stmt, 0);
|
540 |
|
|
use_operand_p imm_use;
|
541 |
|
|
tree use_stmt, lhs, rhs, array_ref;
|
542 |
|
|
|
543 |
|
|
/* We require that the SSA_NAME holding the result of the ADDR_EXPR
|
544 |
|
|
be used only once. That may be overly conservative in that we
|
545 |
|
|
could propagate into multiple uses. However, that would effectively
|
546 |
|
|
be un-cseing the ADDR_EXPR, which is probably not what we want. */
|
547 |
|
|
single_imm_use (name, &imm_use, &use_stmt);
|
548 |
|
|
if (!use_stmt)
|
549 |
|
|
return false;
|
550 |
|
|
|
551 |
|
|
/* If the use is not in a simple assignment statement, then
|
552 |
|
|
there is nothing we can do. */
|
553 |
|
|
if (TREE_CODE (use_stmt) != MODIFY_EXPR)
|
554 |
|
|
return false;
|
555 |
|
|
|
556 |
|
|
/* If the use is in a deeper loop nest, then we do not want
|
557 |
|
|
to propagate the ADDR_EXPR into the loop as that is likely
|
558 |
|
|
adding expression evaluations into the loop. */
|
559 |
|
|
if (bb_for_stmt (use_stmt)->loop_depth > stmt_loop_depth)
|
560 |
|
|
return false;
|
561 |
|
|
|
562 |
|
|
/* Strip away any outer COMPONENT_REF/ARRAY_REF nodes from the LHS.
|
563 |
|
|
ADDR_EXPR will not appear on the LHS. */
|
564 |
|
|
lhs = TREE_OPERAND (use_stmt, 0);
|
565 |
|
|
while (TREE_CODE (lhs) == COMPONENT_REF || TREE_CODE (lhs) == ARRAY_REF)
|
566 |
|
|
lhs = TREE_OPERAND (lhs, 0);
|
567 |
|
|
|
568 |
|
|
/* Now see if the LHS node is an INDIRECT_REF using NAME. If so,
|
569 |
|
|
propagate the ADDR_EXPR into the use of NAME and fold the result. */
|
570 |
|
|
if (TREE_CODE (lhs) == INDIRECT_REF && TREE_OPERAND (lhs, 0) == name)
|
571 |
|
|
{
|
572 |
|
|
/* This should always succeed in creating gimple, so there is
|
573 |
|
|
no need to save enough state to undo this propagation. */
|
574 |
|
|
TREE_OPERAND (lhs, 0) = unshare_expr (TREE_OPERAND (stmt, 1));
|
575 |
|
|
fold_stmt_inplace (use_stmt);
|
576 |
|
|
tidy_after_forward_propagate_addr (use_stmt);
|
577 |
|
|
return true;
|
578 |
|
|
}
|
579 |
|
|
|
580 |
|
|
/* Trivial case. The use statement could be a trivial copy. We
|
581 |
|
|
go ahead and handle that case here since it's trivial and
|
582 |
|
|
removes the need to run copy-prop before this pass to get
|
583 |
|
|
the best results. Also note that by handling this case here
|
584 |
|
|
we can catch some cascading effects, ie the single use is
|
585 |
|
|
in a copy, and the copy is used later by a single INDIRECT_REF
|
586 |
|
|
for example. */
|
587 |
|
|
if (TREE_CODE (lhs) == SSA_NAME && TREE_OPERAND (use_stmt, 1) == name)
|
588 |
|
|
{
|
589 |
|
|
TREE_OPERAND (use_stmt, 1) = unshare_expr (TREE_OPERAND (stmt, 1));
|
590 |
|
|
tidy_after_forward_propagate_addr (use_stmt);
|
591 |
|
|
return true;
|
592 |
|
|
}
|
593 |
|
|
|
594 |
|
|
/* Strip away any outer COMPONENT_REF, ARRAY_REF or ADDR_EXPR
|
595 |
|
|
nodes from the RHS. */
|
596 |
|
|
rhs = TREE_OPERAND (use_stmt, 1);
|
597 |
|
|
while (TREE_CODE (rhs) == COMPONENT_REF
|
598 |
|
|
|| TREE_CODE (rhs) == ARRAY_REF
|
599 |
|
|
|| TREE_CODE (rhs) == ADDR_EXPR)
|
600 |
|
|
rhs = TREE_OPERAND (rhs, 0);
|
601 |
|
|
|
602 |
|
|
/* Now see if the RHS node is an INDIRECT_REF using NAME. If so,
|
603 |
|
|
propagate the ADDR_EXPR into the use of NAME and fold the result. */
|
604 |
|
|
if (TREE_CODE (rhs) == INDIRECT_REF && TREE_OPERAND (rhs, 0) == name)
|
605 |
|
|
{
|
606 |
|
|
/* This should always succeed in creating gimple, so there is
|
607 |
|
|
no need to save enough state to undo this propagation. */
|
608 |
|
|
TREE_OPERAND (rhs, 0) = unshare_expr (TREE_OPERAND (stmt, 1));
|
609 |
|
|
fold_stmt_inplace (use_stmt);
|
610 |
|
|
tidy_after_forward_propagate_addr (use_stmt);
|
611 |
|
|
return true;
|
612 |
|
|
}
|
613 |
|
|
|
614 |
|
|
/* The remaining cases are all for turning pointer arithmetic into
|
615 |
|
|
array indexing. They only apply when we have the address of
|
616 |
|
|
element zero in an array. If that is not the case then there
|
617 |
|
|
is nothing to do. */
|
618 |
|
|
array_ref = TREE_OPERAND (TREE_OPERAND (stmt, 1), 0);
|
619 |
|
|
if (TREE_CODE (array_ref) != ARRAY_REF
|
620 |
|
|
|| TREE_CODE (TREE_TYPE (TREE_OPERAND (array_ref, 0))) != ARRAY_TYPE
|
621 |
|
|
|| !integer_zerop (TREE_OPERAND (array_ref, 1)))
|
622 |
|
|
return false;
|
623 |
|
|
|
624 |
|
|
/* If the use of the ADDR_EXPR must be a PLUS_EXPR, or else there
|
625 |
|
|
is nothing to do. */
|
626 |
|
|
if (TREE_CODE (rhs) != PLUS_EXPR)
|
627 |
|
|
return false;
|
628 |
|
|
|
629 |
|
|
/* Try to optimize &x[0] + C where C is a multiple of the size
|
630 |
|
|
of the elements in X into &x[C/element size]. */
|
631 |
|
|
if (TREE_OPERAND (rhs, 0) == name
|
632 |
|
|
&& TREE_CODE (TREE_OPERAND (rhs, 1)) == INTEGER_CST)
|
633 |
|
|
{
|
634 |
|
|
tree orig = unshare_expr (rhs);
|
635 |
|
|
TREE_OPERAND (rhs, 0) = unshare_expr (TREE_OPERAND (stmt, 1));
|
636 |
|
|
|
637 |
|
|
/* If folding succeeds, then we have just exposed new variables
|
638 |
|
|
in USE_STMT which will need to be renamed. If folding fails,
|
639 |
|
|
then we need to put everything back the way it was. */
|
640 |
|
|
if (fold_stmt_inplace (use_stmt))
|
641 |
|
|
{
|
642 |
|
|
tidy_after_forward_propagate_addr (use_stmt);
|
643 |
|
|
return true;
|
644 |
|
|
}
|
645 |
|
|
else
|
646 |
|
|
{
|
647 |
|
|
TREE_OPERAND (use_stmt, 1) = orig;
|
648 |
|
|
update_stmt (use_stmt);
|
649 |
|
|
return false;
|
650 |
|
|
}
|
651 |
|
|
}
|
652 |
|
|
|
653 |
|
|
/* Try to optimize &x[0] + OFFSET where OFFSET is defined by
|
654 |
|
|
converting a multiplication of an index by the size of the
|
655 |
|
|
array elements, then the result is converted into the proper
|
656 |
|
|
type for the arithmetic. */
|
657 |
|
|
if (TREE_OPERAND (rhs, 0) == name
|
658 |
|
|
&& TREE_CODE (TREE_OPERAND (rhs, 1)) == SSA_NAME
|
659 |
|
|
/* Avoid problems with IVopts creating PLUS_EXPRs with a
|
660 |
|
|
different type than their operands. */
|
661 |
|
|
&& lang_hooks.types_compatible_p (TREE_TYPE (name), TREE_TYPE (rhs)))
|
662 |
|
|
{
|
663 |
|
|
tree offset_stmt = SSA_NAME_DEF_STMT (TREE_OPERAND (rhs, 1));
|
664 |
|
|
return forward_propagate_addr_into_variable_array_index (offset_stmt, lhs,
|
665 |
|
|
stmt, use_stmt);
|
666 |
|
|
}
|
667 |
|
|
|
668 |
|
|
/* Same as the previous case, except the operands of the PLUS_EXPR
|
669 |
|
|
were reversed. */
|
670 |
|
|
if (TREE_OPERAND (rhs, 1) == name
|
671 |
|
|
&& TREE_CODE (TREE_OPERAND (rhs, 0)) == SSA_NAME
|
672 |
|
|
/* Avoid problems with IVopts creating PLUS_EXPRs with a
|
673 |
|
|
different type than their operands. */
|
674 |
|
|
&& lang_hooks.types_compatible_p (TREE_TYPE (name), TREE_TYPE (rhs)))
|
675 |
|
|
{
|
676 |
|
|
tree offset_stmt = SSA_NAME_DEF_STMT (TREE_OPERAND (rhs, 0));
|
677 |
|
|
return forward_propagate_addr_into_variable_array_index (offset_stmt, lhs,
|
678 |
|
|
stmt, use_stmt);
|
679 |
|
|
}
|
680 |
|
|
return false;
|
681 |
|
|
}
|
682 |
|
|
|
683 |
|
|
/* Main entry point for the forward propagation optimizer. */
|
684 |
|
|
|
685 |
|
|
static void
|
686 |
|
|
tree_ssa_forward_propagate_single_use_vars (void)
|
687 |
|
|
{
|
688 |
|
|
basic_block bb;
|
689 |
|
|
|
690 |
|
|
cfg_changed = false;
|
691 |
|
|
|
692 |
|
|
FOR_EACH_BB (bb)
|
693 |
|
|
{
|
694 |
|
|
block_stmt_iterator bsi;
|
695 |
|
|
|
696 |
|
|
/* Note we update BSI within the loop as necessary. */
|
697 |
|
|
for (bsi = bsi_start (bb); !bsi_end_p (bsi); )
|
698 |
|
|
{
|
699 |
|
|
tree stmt = bsi_stmt (bsi);
|
700 |
|
|
|
701 |
|
|
/* If this statement sets an SSA_NAME to an address,
|
702 |
|
|
try to propagate the address into the uses of the SSA_NAME. */
|
703 |
|
|
if (TREE_CODE (stmt) == MODIFY_EXPR
|
704 |
|
|
&& TREE_CODE (TREE_OPERAND (stmt, 1)) == ADDR_EXPR
|
705 |
|
|
&& TREE_CODE (TREE_OPERAND (stmt, 0)) == SSA_NAME)
|
706 |
|
|
{
|
707 |
|
|
if (forward_propagate_addr_expr (stmt))
|
708 |
|
|
bsi_remove (&bsi);
|
709 |
|
|
else
|
710 |
|
|
bsi_next (&bsi);
|
711 |
|
|
}
|
712 |
|
|
else if (TREE_CODE (stmt) == COND_EXPR)
|
713 |
|
|
{
|
714 |
|
|
forward_propagate_into_cond (stmt);
|
715 |
|
|
bsi_next (&bsi);
|
716 |
|
|
}
|
717 |
|
|
else
|
718 |
|
|
bsi_next (&bsi);
|
719 |
|
|
}
|
720 |
|
|
}
|
721 |
|
|
|
722 |
|
|
if (cfg_changed)
|
723 |
|
|
cleanup_tree_cfg ();
|
724 |
|
|
}
|
725 |
|
|
|
726 |
|
|
|
727 |
|
|
static bool
|
728 |
|
|
gate_forwprop (void)
|
729 |
|
|
{
|
730 |
|
|
return 1;
|
731 |
|
|
}
|
732 |
|
|
|
733 |
|
|
struct tree_opt_pass pass_forwprop = {
|
734 |
|
|
"forwprop", /* name */
|
735 |
|
|
gate_forwprop, /* gate */
|
736 |
|
|
tree_ssa_forward_propagate_single_use_vars, /* execute */
|
737 |
|
|
NULL, /* sub */
|
738 |
|
|
NULL, /* next */
|
739 |
|
|
0, /* static_pass_number */
|
740 |
|
|
TV_TREE_FORWPROP, /* tv_id */
|
741 |
|
|
PROP_cfg | PROP_ssa
|
742 |
|
|
| PROP_alias, /* properties_required */
|
743 |
|
|
0, /* properties_provided */
|
744 |
|
|
0, /* properties_destroyed */
|
745 |
|
|
0, /* todo_flags_start */
|
746 |
|
|
TODO_dump_func | TODO_ggc_collect /* todo_flags_finish */
|
747 |
|
|
| TODO_update_ssa | TODO_verify_ssa,
|
748 |
|
|
|
749 |
|
|
};
|