Mercurial > hg > CbC > CbC_gcc
annotate gcc/tree-ssa-dom.c @ 140:4e440907fcbf
copy CbC goto flang in cfgexpand
remove some CbC unnecessary code
author | Shinji KONO <kono@ie.u-ryukyu.ac.jp> |
---|---|
date | Wed, 14 Nov 2018 00:24:45 +0900 |
parents | 84e7813d76e9 |
children | 1830386684a0 |
rev | line source |
---|---|
0 | 1 /* SSA Dominator optimizations for trees |
131 | 2 Copyright (C) 2001-2018 Free Software Foundation, Inc. |
0 | 3 Contributed by Diego Novillo <dnovillo@redhat.com> |
4 | |
5 This file is part of GCC. | |
6 | |
7 GCC is free software; you can redistribute it and/or modify | |
8 it under the terms of the GNU General Public License as published by | |
9 the Free Software Foundation; either version 3, or (at your option) | |
10 any later version. | |
11 | |
12 GCC is distributed in the hope that it will be useful, | |
13 but WITHOUT ANY WARRANTY; without even the implied warranty of | |
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
15 GNU General Public License for more details. | |
16 | |
17 You should have received a copy of the GNU General Public License | |
18 along with GCC; see the file COPYING3. If not see | |
19 <http://www.gnu.org/licenses/>. */ | |
20 | |
21 #include "config.h" | |
22 #include "system.h" | |
23 #include "coretypes.h" | |
111 | 24 #include "backend.h" |
0 | 25 #include "tree.h" |
111 | 26 #include "gimple.h" |
27 #include "tree-pass.h" | |
28 #include "ssa.h" | |
29 #include "gimple-pretty-print.h" | |
30 #include "fold-const.h" | |
31 #include "cfganal.h" | |
0 | 32 #include "cfgloop.h" |
111 | 33 #include "gimple-fold.h" |
34 #include "tree-eh.h" | |
35 #include "tree-inline.h" | |
36 #include "gimple-iterator.h" | |
37 #include "tree-cfg.h" | |
38 #include "tree-into-ssa.h" | |
0 | 39 #include "domwalk.h" |
40 #include "tree-ssa-propagate.h" | |
111 | 41 #include "tree-ssa-threadupdate.h" |
0 | 42 #include "params.h" |
111 | 43 #include "tree-ssa-scopedtables.h" |
44 #include "tree-ssa-threadedge.h" | |
45 #include "tree-ssa-dom.h" | |
46 #include "gimplify.h" | |
47 #include "tree-cfgcleanup.h" | |
48 #include "dbgcnt.h" | |
131 | 49 #include "alloc-pool.h" |
50 #include "tree-vrp.h" | |
51 #include "vr-values.h" | |
52 #include "gimple-ssa-evrp-analyze.h" | |
0 | 53 |
54 /* This file implements optimizations on the dominator tree. */ | |
55 | |
111 | 56 /* Structure for recording edge equivalences. |
0 | 57 |
58 Computing and storing the edge equivalences instead of creating | |
59 them on-demand can save significant amounts of time, particularly | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
60 for pathological cases involving switch statements. |
0 | 61 |
62 These structures live for a single iteration of the dominator | |
63 optimizer in the edge's AUX field. At the end of an iteration we | |
111 | 64 free each of these structures. */ |
65 class edge_info | |
66 { | |
67 public: | |
68 typedef std::pair <tree, tree> equiv_pair; | |
69 edge_info (edge); | |
70 ~edge_info (); | |
0 | 71 |
111 | 72 /* Record a simple LHS = RHS equivalence. This may trigger |
73 calls to derive_equivalences. */ | |
74 void record_simple_equiv (tree, tree); | |
75 | |
76 /* If traversing this edge creates simple equivalences, we store | |
77 them as LHS/RHS pairs within this vector. */ | |
78 vec<equiv_pair> simple_equivalences; | |
0 | 79 |
80 /* Traversing an edge may also indicate one or more particular conditions | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
81 are true or false. */ |
111 | 82 vec<cond_equivalence> cond_equivalences; |
0 | 83 |
111 | 84 private: |
85 /* Derive equivalences by walking the use-def chains. */ | |
86 void derive_equivalences (tree, tree, int); | |
0 | 87 }; |
88 | |
89 /* Track whether or not we have changed the control flow graph. */ | |
90 static bool cfg_altered; | |
91 | |
92 /* Bitmap of blocks that have had EH statements cleaned. We should | |
93 remove their dead edges eventually. */ | |
94 static bitmap need_eh_cleanup; | |
111 | 95 static vec<gimple *> need_noreturn_fixup; |
0 | 96 |
97 /* Statistics for dominator optimizations. */ | |
98 struct opt_stats_d | |
99 { | |
100 long num_stmts; | |
101 long num_exprs_considered; | |
102 long num_re; | |
103 long num_const_prop; | |
104 long num_copy_prop; | |
105 }; | |
106 | |
107 static struct opt_stats_d opt_stats; | |
108 | |
109 /* Local functions. */ | |
111 | 110 static void record_equality (tree, tree, class const_and_copies *); |
0 | 111 static void record_equivalences_from_phis (basic_block); |
111 | 112 static void record_equivalences_from_incoming_edge (basic_block, |
113 class const_and_copies *, | |
114 class avail_exprs_stack *); | |
115 static void eliminate_redundant_computations (gimple_stmt_iterator *, | |
116 class const_and_copies *, | |
117 class avail_exprs_stack *); | |
118 static void record_equivalences_from_stmt (gimple *, int, | |
119 class avail_exprs_stack *); | |
120 static void dump_dominator_optimization_stats (FILE *file, | |
121 hash_table<expr_elt_hasher> *); | |
0 | 122 |
111 | 123 /* Constructor for EDGE_INFO. An EDGE_INFO instance is always |
124 associated with an edge E. */ | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
125 |
111 | 126 edge_info::edge_info (edge e) |
127 { | |
128 /* Free the old one associated with E, if it exists and | |
129 associate our new object with E. */ | |
130 free_dom_edge_info (e); | |
131 e->aux = this; | |
0 | 132 |
111 | 133 /* And initialize the embedded vectors. */ |
134 simple_equivalences = vNULL; | |
135 cond_equivalences = vNULL; | |
136 } | |
0 | 137 |
111 | 138 /* Destructor just needs to release the vectors. */ |
0 | 139 |
111 | 140 edge_info::~edge_info (void) |
141 { | |
142 this->cond_equivalences.release (); | |
143 this->simple_equivalences.release (); | |
0 | 144 } |
145 | |
111 | 146 /* NAME is known to have the value VALUE, which must be a constant. |
0 | 147 |
111 | 148 Walk through its use-def chain to see if there are other equivalences |
149 we might be able to derive. | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
150 |
111 | 151 RECURSION_LIMIT controls how far back we recurse through the use-def |
152 chains. */ | |
0 | 153 |
111 | 154 void |
155 edge_info::derive_equivalences (tree name, tree value, int recursion_limit) | |
0 | 156 { |
111 | 157 if (TREE_CODE (name) != SSA_NAME || TREE_CODE (value) != INTEGER_CST) |
158 return; | |
0 | 159 |
111 | 160 /* This records the equivalence for the toplevel object. Do |
161 this before checking the recursion limit. */ | |
162 simple_equivalences.safe_push (equiv_pair (name, value)); | |
0 | 163 |
111 | 164 /* Limit how far up the use-def chains we are willing to walk. */ |
165 if (recursion_limit == 0) | |
166 return; | |
0 | 167 |
111 | 168 /* We can walk up the use-def chains to potentially find more |
169 equivalences. */ | |
170 gimple *def_stmt = SSA_NAME_DEF_STMT (name); | |
171 if (is_gimple_assign (def_stmt)) | |
0 | 172 { |
111 | 173 /* We know the result of DEF_STMT was zero. See if that allows |
174 us to deduce anything about the SSA_NAMEs used on the RHS. */ | |
175 enum tree_code code = gimple_assign_rhs_code (def_stmt); | |
176 switch (code) | |
177 { | |
178 case BIT_IOR_EXPR: | |
179 if (integer_zerop (value)) | |
180 { | |
181 tree rhs1 = gimple_assign_rhs1 (def_stmt); | |
182 tree rhs2 = gimple_assign_rhs2 (def_stmt); | |
0 | 183 |
111 | 184 value = build_zero_cst (TREE_TYPE (rhs1)); |
185 derive_equivalences (rhs1, value, recursion_limit - 1); | |
186 value = build_zero_cst (TREE_TYPE (rhs2)); | |
187 derive_equivalences (rhs2, value, recursion_limit - 1); | |
188 } | |
189 break; | |
0 | 190 |
111 | 191 /* We know the result of DEF_STMT was one. See if that allows |
192 us to deduce anything about the SSA_NAMEs used on the RHS. */ | |
193 case BIT_AND_EXPR: | |
194 if (!integer_zerop (value)) | |
195 { | |
196 tree rhs1 = gimple_assign_rhs1 (def_stmt); | |
197 tree rhs2 = gimple_assign_rhs2 (def_stmt); | |
0 | 198 |
111 | 199 /* If either operand has a boolean range, then we |
200 know its value must be one, otherwise we just know it | |
201 is nonzero. The former is clearly useful, I haven't | |
202 seen cases where the latter is helpful yet. */ | |
203 if (TREE_CODE (rhs1) == SSA_NAME) | |
204 { | |
205 if (ssa_name_has_boolean_range (rhs1)) | |
206 { | |
207 value = build_one_cst (TREE_TYPE (rhs1)); | |
208 derive_equivalences (rhs1, value, recursion_limit - 1); | |
209 } | |
210 } | |
211 if (TREE_CODE (rhs2) == SSA_NAME) | |
212 { | |
213 if (ssa_name_has_boolean_range (rhs2)) | |
214 { | |
215 value = build_one_cst (TREE_TYPE (rhs2)); | |
216 derive_equivalences (rhs2, value, recursion_limit - 1); | |
217 } | |
218 } | |
219 } | |
220 break; | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
221 |
111 | 222 /* If LHS is an SSA_NAME and RHS is a constant integer and LHS was |
223 set via a widening type conversion, then we may be able to record | |
224 additional equivalences. */ | |
225 case NOP_EXPR: | |
226 case CONVERT_EXPR: | |
227 { | |
228 tree rhs = gimple_assign_rhs1 (def_stmt); | |
229 tree rhs_type = TREE_TYPE (rhs); | |
230 if (INTEGRAL_TYPE_P (rhs_type) | |
231 && (TYPE_PRECISION (TREE_TYPE (name)) | |
232 >= TYPE_PRECISION (rhs_type)) | |
233 && int_fits_type_p (value, rhs_type)) | |
234 derive_equivalences (rhs, | |
235 fold_convert (rhs_type, value), | |
236 recursion_limit - 1); | |
237 break; | |
238 } | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
239 |
111 | 240 /* We can invert the operation of these codes trivially if |
241 one of the RHS operands is a constant to produce a known | |
242 value for the other RHS operand. */ | |
243 case POINTER_PLUS_EXPR: | |
244 case PLUS_EXPR: | |
245 { | |
246 tree rhs1 = gimple_assign_rhs1 (def_stmt); | |
247 tree rhs2 = gimple_assign_rhs2 (def_stmt); | |
248 | |
249 /* If either argument is a constant, then we can compute | |
250 a constant value for the nonconstant argument. */ | |
251 if (TREE_CODE (rhs1) == INTEGER_CST | |
252 && TREE_CODE (rhs2) == SSA_NAME) | |
253 derive_equivalences (rhs2, | |
254 fold_binary (MINUS_EXPR, TREE_TYPE (rhs1), | |
255 value, rhs1), | |
256 recursion_limit - 1); | |
257 else if (TREE_CODE (rhs2) == INTEGER_CST | |
258 && TREE_CODE (rhs1) == SSA_NAME) | |
259 derive_equivalences (rhs1, | |
260 fold_binary (MINUS_EXPR, TREE_TYPE (rhs1), | |
261 value, rhs2), | |
262 recursion_limit - 1); | |
263 break; | |
264 } | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
265 |
111 | 266 /* If one of the operands is a constant, then we can compute |
267 the value of the other operand. If both operands are | |
268 SSA_NAMEs, then they must be equal if the result is zero. */ | |
269 case MINUS_EXPR: | |
270 { | |
271 tree rhs1 = gimple_assign_rhs1 (def_stmt); | |
272 tree rhs2 = gimple_assign_rhs2 (def_stmt); | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
273 |
111 | 274 /* If either argument is a constant, then we can compute |
275 a constant value for the nonconstant argument. */ | |
276 if (TREE_CODE (rhs1) == INTEGER_CST | |
277 && TREE_CODE (rhs2) == SSA_NAME) | |
278 derive_equivalences (rhs2, | |
279 fold_binary (MINUS_EXPR, TREE_TYPE (rhs1), | |
280 rhs1, value), | |
281 recursion_limit - 1); | |
282 else if (TREE_CODE (rhs2) == INTEGER_CST | |
283 && TREE_CODE (rhs1) == SSA_NAME) | |
284 derive_equivalences (rhs1, | |
285 fold_binary (PLUS_EXPR, TREE_TYPE (rhs1), | |
286 value, rhs2), | |
287 recursion_limit - 1); | |
288 else if (integer_zerop (value)) | |
289 { | |
290 tree cond = build2 (EQ_EXPR, boolean_type_node, | |
291 gimple_assign_rhs1 (def_stmt), | |
292 gimple_assign_rhs2 (def_stmt)); | |
293 tree inverted = invert_truthvalue (cond); | |
294 record_conditions (&this->cond_equivalences, cond, inverted); | |
295 } | |
296 break; | |
297 } | |
0 | 298 |
111 | 299 |
300 case EQ_EXPR: | |
301 case NE_EXPR: | |
302 { | |
303 if ((code == EQ_EXPR && integer_onep (value)) | |
304 || (code == NE_EXPR && integer_zerop (value))) | |
305 { | |
306 tree rhs1 = gimple_assign_rhs1 (def_stmt); | |
307 tree rhs2 = gimple_assign_rhs2 (def_stmt); | |
308 | |
309 /* If either argument is a constant, then record the | |
310 other argument as being the same as that constant. | |
0 | 311 |
111 | 312 If neither operand is a constant, then we have a |
313 conditional name == name equivalence. */ | |
314 if (TREE_CODE (rhs1) == INTEGER_CST) | |
315 derive_equivalences (rhs2, rhs1, recursion_limit - 1); | |
316 else if (TREE_CODE (rhs2) == INTEGER_CST) | |
317 derive_equivalences (rhs1, rhs2, recursion_limit - 1); | |
318 } | |
319 else | |
320 { | |
321 tree cond = build2 (code, boolean_type_node, | |
322 gimple_assign_rhs1 (def_stmt), | |
323 gimple_assign_rhs2 (def_stmt)); | |
324 tree inverted = invert_truthvalue (cond); | |
325 if (integer_zerop (value)) | |
326 std::swap (cond, inverted); | |
327 record_conditions (&this->cond_equivalences, cond, inverted); | |
328 } | |
329 break; | |
330 } | |
0 | 331 |
111 | 332 /* For BIT_NOT and NEGATE, we can just apply the operation to the |
333 VALUE to get the new equivalence. It will always be a constant | |
334 so we can recurse. */ | |
335 case BIT_NOT_EXPR: | |
336 case NEGATE_EXPR: | |
337 { | |
338 tree rhs = gimple_assign_rhs1 (def_stmt); | |
339 tree res = fold_build1 (code, TREE_TYPE (rhs), value); | |
340 derive_equivalences (rhs, res, recursion_limit - 1); | |
341 break; | |
342 } | |
0 | 343 |
111 | 344 default: |
345 { | |
346 if (TREE_CODE_CLASS (code) == tcc_comparison) | |
347 { | |
348 tree cond = build2 (code, boolean_type_node, | |
349 gimple_assign_rhs1 (def_stmt), | |
350 gimple_assign_rhs2 (def_stmt)); | |
351 tree inverted = invert_truthvalue (cond); | |
352 if (integer_zerop (value)) | |
353 std::swap (cond, inverted); | |
354 record_conditions (&this->cond_equivalences, cond, inverted); | |
355 break; | |
356 } | |
357 break; | |
358 } | |
359 } | |
0 | 360 } |
361 } | |
362 | |
111 | 363 void |
364 edge_info::record_simple_equiv (tree lhs, tree rhs) | |
0 | 365 { |
111 | 366 /* If the RHS is a constant, then we may be able to derive |
367 further equivalences. Else just record the name = name | |
368 equivalence. */ | |
369 if (TREE_CODE (rhs) == INTEGER_CST) | |
370 derive_equivalences (lhs, rhs, 4); | |
371 else | |
372 simple_equivalences.safe_push (equiv_pair (lhs, rhs)); | |
0 | 373 } |
374 | |
111 | 375 /* Free the edge_info data attached to E, if it exists. */ |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
376 |
111 | 377 void |
378 free_dom_edge_info (edge e) | |
379 { | |
380 class edge_info *edge_info = (struct edge_info *)e->aux; | |
0 | 381 |
111 | 382 if (edge_info) |
383 delete edge_info; | |
0 | 384 } |
385 | |
386 /* Free all EDGE_INFO structures associated with edges in the CFG. | |
387 If a particular edge can be threaded, copy the redirection | |
388 target from the EDGE_INFO structure into the edge's AUX field | |
389 as required by code to update the CFG and SSA graph for | |
390 jump threading. */ | |
391 | |
392 static void | |
393 free_all_edge_infos (void) | |
394 { | |
395 basic_block bb; | |
396 edge_iterator ei; | |
397 edge e; | |
398 | |
111 | 399 FOR_EACH_BB_FN (bb, cfun) |
0 | 400 { |
401 FOR_EACH_EDGE (e, ei, bb->preds) | |
402 { | |
111 | 403 free_dom_edge_info (e); |
404 e->aux = NULL; | |
0 | 405 } |
406 } | |
407 } | |
408 | |
111 | 409 /* We have finished optimizing BB, record any information implied by |
410 taking a specific outgoing edge from BB. */ | |
411 | |
412 static void | |
413 record_edge_info (basic_block bb) | |
414 { | |
415 gimple_stmt_iterator gsi = gsi_last_bb (bb); | |
416 class edge_info *edge_info; | |
417 | |
418 if (! gsi_end_p (gsi)) | |
419 { | |
420 gimple *stmt = gsi_stmt (gsi); | |
421 location_t loc = gimple_location (stmt); | |
422 | |
423 if (gimple_code (stmt) == GIMPLE_SWITCH) | |
424 { | |
425 gswitch *switch_stmt = as_a <gswitch *> (stmt); | |
426 tree index = gimple_switch_index (switch_stmt); | |
427 | |
428 if (TREE_CODE (index) == SSA_NAME) | |
429 { | |
430 int i; | |
431 int n_labels = gimple_switch_num_labels (switch_stmt); | |
432 tree *info = XCNEWVEC (tree, last_basic_block_for_fn (cfun)); | |
433 edge e; | |
434 edge_iterator ei; | |
435 | |
436 for (i = 0; i < n_labels; i++) | |
437 { | |
438 tree label = gimple_switch_label (switch_stmt, i); | |
131 | 439 basic_block target_bb |
440 = label_to_block (cfun, CASE_LABEL (label)); | |
111 | 441 if (CASE_HIGH (label) |
442 || !CASE_LOW (label) | |
443 || info[target_bb->index]) | |
444 info[target_bb->index] = error_mark_node; | |
445 else | |
446 info[target_bb->index] = label; | |
447 } | |
448 | |
449 FOR_EACH_EDGE (e, ei, bb->succs) | |
450 { | |
451 basic_block target_bb = e->dest; | |
452 tree label = info[target_bb->index]; | |
453 | |
454 if (label != NULL && label != error_mark_node) | |
455 { | |
456 tree x = fold_convert_loc (loc, TREE_TYPE (index), | |
457 CASE_LOW (label)); | |
458 edge_info = new class edge_info (e); | |
459 edge_info->record_simple_equiv (index, x); | |
460 } | |
461 } | |
462 free (info); | |
463 } | |
464 } | |
465 | |
466 /* A COND_EXPR may create equivalences too. */ | |
467 if (gimple_code (stmt) == GIMPLE_COND) | |
468 { | |
469 edge true_edge; | |
470 edge false_edge; | |
471 | |
472 tree op0 = gimple_cond_lhs (stmt); | |
473 tree op1 = gimple_cond_rhs (stmt); | |
474 enum tree_code code = gimple_cond_code (stmt); | |
475 | |
476 extract_true_false_edges_from_block (bb, &true_edge, &false_edge); | |
477 | |
478 /* Special case comparing booleans against a constant as we | |
479 know the value of OP0 on both arms of the branch. i.e., we | |
480 can record an equivalence for OP0 rather than COND. | |
481 | |
482 However, don't do this if the constant isn't zero or one. | |
483 Such conditionals will get optimized more thoroughly during | |
484 the domwalk. */ | |
485 if ((code == EQ_EXPR || code == NE_EXPR) | |
486 && TREE_CODE (op0) == SSA_NAME | |
487 && ssa_name_has_boolean_range (op0) | |
488 && is_gimple_min_invariant (op1) | |
489 && (integer_zerop (op1) || integer_onep (op1))) | |
490 { | |
491 tree true_val = constant_boolean_node (true, TREE_TYPE (op0)); | |
492 tree false_val = constant_boolean_node (false, TREE_TYPE (op0)); | |
493 | |
494 if (code == EQ_EXPR) | |
495 { | |
496 edge_info = new class edge_info (true_edge); | |
497 edge_info->record_simple_equiv (op0, | |
498 (integer_zerop (op1) | |
499 ? false_val : true_val)); | |
500 edge_info = new class edge_info (false_edge); | |
501 edge_info->record_simple_equiv (op0, | |
502 (integer_zerop (op1) | |
503 ? true_val : false_val)); | |
504 } | |
505 else | |
506 { | |
507 edge_info = new class edge_info (true_edge); | |
508 edge_info->record_simple_equiv (op0, | |
509 (integer_zerop (op1) | |
510 ? true_val : false_val)); | |
511 edge_info = new class edge_info (false_edge); | |
512 edge_info->record_simple_equiv (op0, | |
513 (integer_zerop (op1) | |
514 ? false_val : true_val)); | |
515 } | |
516 } | |
517 /* This can show up in the IL as a result of copy propagation | |
518 it will eventually be canonicalized, but we have to cope | |
519 with this case within the pass. */ | |
520 else if (is_gimple_min_invariant (op0) | |
521 && TREE_CODE (op1) == SSA_NAME) | |
522 { | |
523 tree cond = build2 (code, boolean_type_node, op0, op1); | |
524 tree inverted = invert_truthvalue_loc (loc, cond); | |
525 bool can_infer_simple_equiv | |
526 = !(HONOR_SIGNED_ZEROS (op0) | |
527 && real_zerop (op0)); | |
528 struct edge_info *edge_info; | |
529 | |
530 edge_info = new class edge_info (true_edge); | |
531 record_conditions (&edge_info->cond_equivalences, cond, inverted); | |
532 | |
533 if (can_infer_simple_equiv && code == EQ_EXPR) | |
534 edge_info->record_simple_equiv (op1, op0); | |
535 | |
536 edge_info = new class edge_info (false_edge); | |
537 record_conditions (&edge_info->cond_equivalences, inverted, cond); | |
538 | |
539 if (can_infer_simple_equiv && TREE_CODE (inverted) == EQ_EXPR) | |
540 edge_info->record_simple_equiv (op1, op0); | |
541 } | |
542 | |
543 else if (TREE_CODE (op0) == SSA_NAME | |
544 && (TREE_CODE (op1) == SSA_NAME | |
545 || is_gimple_min_invariant (op1))) | |
546 { | |
547 tree cond = build2 (code, boolean_type_node, op0, op1); | |
548 tree inverted = invert_truthvalue_loc (loc, cond); | |
549 bool can_infer_simple_equiv | |
550 = !(HONOR_SIGNED_ZEROS (op1) | |
551 && (TREE_CODE (op1) == SSA_NAME || real_zerop (op1))); | |
552 struct edge_info *edge_info; | |
553 | |
554 edge_info = new class edge_info (true_edge); | |
555 record_conditions (&edge_info->cond_equivalences, cond, inverted); | |
556 | |
557 if (can_infer_simple_equiv && code == EQ_EXPR) | |
558 edge_info->record_simple_equiv (op0, op1); | |
559 | |
560 edge_info = new class edge_info (false_edge); | |
561 record_conditions (&edge_info->cond_equivalences, inverted, cond); | |
562 | |
563 if (can_infer_simple_equiv && TREE_CODE (inverted) == EQ_EXPR) | |
564 edge_info->record_simple_equiv (op0, op1); | |
565 } | |
566 } | |
567 } | |
568 } | |
569 | |
570 | |
571 class dom_opt_dom_walker : public dom_walker | |
572 { | |
573 public: | |
574 dom_opt_dom_walker (cdi_direction direction, | |
575 class const_and_copies *const_and_copies, | |
576 class avail_exprs_stack *avail_exprs_stack, | |
577 gcond *dummy_cond) | |
131 | 578 : dom_walker (direction, REACHABLE_BLOCKS), |
111 | 579 m_const_and_copies (const_and_copies), |
580 m_avail_exprs_stack (avail_exprs_stack), | |
581 m_dummy_cond (dummy_cond) { } | |
582 | |
583 virtual edge before_dom_children (basic_block); | |
584 virtual void after_dom_children (basic_block); | |
585 | |
586 private: | |
587 | |
588 /* Unwindable equivalences, both const/copy and expression varieties. */ | |
589 class const_and_copies *m_const_and_copies; | |
590 class avail_exprs_stack *m_avail_exprs_stack; | |
591 | |
131 | 592 /* VRP data. */ |
593 class evrp_range_analyzer evrp_range_analyzer; | |
594 | |
111 | 595 /* Dummy condition to avoid creating lots of throw away statements. */ |
596 gcond *m_dummy_cond; | |
597 | |
598 /* Optimize a single statement within a basic block using the | |
599 various tables mantained by DOM. Returns the taken edge if | |
600 the statement is a conditional with a statically determined | |
601 value. */ | |
602 edge optimize_stmt (basic_block, gimple_stmt_iterator); | |
603 }; | |
604 | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
605 /* Jump threading, redundancy elimination and const/copy propagation. |
0 | 606 |
607 This pass may expose new symbols that need to be renamed into SSA. For | |
608 every new symbol exposed, its corresponding bit will be set in | |
609 VARS_TO_RENAME. */ | |
610 | |
111 | 611 namespace { |
612 | |
613 const pass_data pass_data_dominator = | |
614 { | |
615 GIMPLE_PASS, /* type */ | |
616 "dom", /* name */ | |
617 OPTGROUP_NONE, /* optinfo_flags */ | |
618 TV_TREE_SSA_DOMINATOR_OPTS, /* tv_id */ | |
619 ( PROP_cfg | PROP_ssa ), /* properties_required */ | |
620 0, /* properties_provided */ | |
621 0, /* properties_destroyed */ | |
622 0, /* todo_flags_start */ | |
623 ( TODO_cleanup_cfg | TODO_update_ssa ), /* todo_flags_finish */ | |
624 }; | |
625 | |
626 class pass_dominator : public gimple_opt_pass | |
0 | 627 { |
111 | 628 public: |
629 pass_dominator (gcc::context *ctxt) | |
630 : gimple_opt_pass (pass_data_dominator, ctxt), | |
631 may_peel_loop_headers_p (false) | |
632 {} | |
0 | 633 |
111 | 634 /* opt_pass methods: */ |
635 opt_pass * clone () { return new pass_dominator (m_ctxt); } | |
636 void set_pass_param (unsigned int n, bool param) | |
637 { | |
638 gcc_assert (n == 0); | |
639 may_peel_loop_headers_p = param; | |
640 } | |
641 virtual bool gate (function *) { return flag_tree_dom != 0; } | |
642 virtual unsigned int execute (function *); | |
643 | |
644 private: | |
645 /* This flag is used to prevent loops from being peeled repeatedly in jump | |
646 threading; it will be removed once we preserve loop structures throughout | |
647 the compilation -- we will be able to mark the affected loops directly in | |
648 jump threading, and avoid peeling them next time. */ | |
649 bool may_peel_loop_headers_p; | |
650 }; // class pass_dominator | |
651 | |
652 unsigned int | |
653 pass_dominator::execute (function *fun) | |
654 { | |
0 | 655 memset (&opt_stats, 0, sizeof (opt_stats)); |
656 | |
657 /* Create our hash tables. */ | |
111 | 658 hash_table<expr_elt_hasher> *avail_exprs |
659 = new hash_table<expr_elt_hasher> (1024); | |
660 class avail_exprs_stack *avail_exprs_stack | |
661 = new class avail_exprs_stack (avail_exprs); | |
662 class const_and_copies *const_and_copies = new class const_and_copies (); | |
0 | 663 need_eh_cleanup = BITMAP_ALLOC (NULL); |
111 | 664 need_noreturn_fixup.create (0); |
0 | 665 |
666 calculate_dominance_info (CDI_DOMINATORS); | |
667 cfg_altered = false; | |
668 | |
669 /* We need to know loop structures in order to avoid destroying them | |
670 in jump threading. Note that we still can e.g. thread through loop | |
671 headers to an exit edge, or through loop header to the loop body, assuming | |
111 | 672 that we update the loop info. |
673 | |
674 TODO: We don't need to set LOOPS_HAVE_PREHEADERS generally, but due | |
675 to several overly conservative bail-outs in jump threading, case | |
676 gcc.dg/tree-ssa/pr21417.c can't be threaded if loop preheader is | |
677 missing. We should improve jump threading in future then | |
678 LOOPS_HAVE_PREHEADERS won't be needed here. */ | |
679 loop_optimizer_init (LOOPS_HAVE_PREHEADERS | LOOPS_HAVE_SIMPLE_LATCHES); | |
0 | 680 |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
681 /* Initialize the value-handle array. */ |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
682 threadedge_initialize_values (); |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
683 |
0 | 684 /* We need accurate information regarding back edges in the CFG |
685 for jump threading; this may include back edges that are not part of | |
686 a single loop. */ | |
687 mark_dfs_back_edges (); | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
688 |
111 | 689 /* We want to create the edge info structures before the dominator walk |
690 so that they'll be in place for the jump threader, particularly when | |
691 threading through a join block. | |
692 | |
693 The conditions will be lazily updated with global equivalences as | |
694 we reach them during the dominator walk. */ | |
695 basic_block bb; | |
696 FOR_EACH_BB_FN (bb, fun) | |
697 record_edge_info (bb); | |
698 | |
699 gcond *dummy_cond = gimple_build_cond (NE_EXPR, integer_zero_node, | |
700 integer_zero_node, NULL, NULL); | |
701 | |
0 | 702 /* Recursively walk the dominator tree optimizing statements. */ |
111 | 703 dom_opt_dom_walker walker (CDI_DOMINATORS, const_and_copies, |
704 avail_exprs_stack, dummy_cond); | |
705 walker.walk (fun->cfg->x_entry_block_ptr); | |
706 | |
707 /* Look for blocks where we cleared EDGE_EXECUTABLE on an outgoing | |
708 edge. When found, remove jump threads which contain any outgoing | |
709 edge from the affected block. */ | |
710 if (cfg_altered) | |
711 { | |
712 FOR_EACH_BB_FN (bb, fun) | |
713 { | |
714 edge_iterator ei; | |
715 edge e; | |
716 | |
717 /* First see if there are any edges without EDGE_EXECUTABLE | |
718 set. */ | |
719 bool found = false; | |
720 FOR_EACH_EDGE (e, ei, bb->succs) | |
721 { | |
722 if ((e->flags & EDGE_EXECUTABLE) == 0) | |
723 { | |
724 found = true; | |
725 break; | |
726 } | |
727 } | |
728 | |
729 /* If there were any such edges found, then remove jump threads | |
730 containing any edge leaving BB. */ | |
731 if (found) | |
732 FOR_EACH_EDGE (e, ei, bb->succs) | |
733 remove_jump_threads_including (e); | |
734 } | |
735 } | |
0 | 736 |
737 { | |
738 gimple_stmt_iterator gsi; | |
739 basic_block bb; | |
111 | 740 FOR_EACH_BB_FN (bb, fun) |
741 { | |
742 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) | |
0 | 743 update_stmt_if_modified (gsi_stmt (gsi)); |
744 } | |
745 } | |
746 | |
747 /* If we exposed any new variables, go ahead and put them into | |
748 SSA form now, before we handle jump threading. This simplifies | |
749 interactions between rewriting of _DECL nodes into SSA form | |
750 and rewriting SSA_NAME nodes into SSA form after block | |
751 duplication and CFG manipulation. */ | |
752 update_ssa (TODO_update_ssa); | |
753 | |
754 free_all_edge_infos (); | |
755 | |
756 /* Thread jumps, creating duplicate blocks as needed. */ | |
111 | 757 cfg_altered |= thread_through_all_blocks (may_peel_loop_headers_p); |
0 | 758 |
759 if (cfg_altered) | |
760 free_dominance_info (CDI_DOMINATORS); | |
761 | |
762 /* Removal of statements may make some EH edges dead. Purge | |
763 such edges from the CFG as needed. */ | |
764 if (!bitmap_empty_p (need_eh_cleanup)) | |
765 { | |
766 unsigned i; | |
767 bitmap_iterator bi; | |
768 | |
769 /* Jump threading may have created forwarder blocks from blocks | |
770 needing EH cleanup; the new successor of these blocks, which | |
111 | 771 has inherited from the original block, needs the cleanup. |
772 Don't clear bits in the bitmap, as that can break the bitmap | |
773 iterator. */ | |
0 | 774 EXECUTE_IF_SET_IN_BITMAP (need_eh_cleanup, 0, i, bi) |
775 { | |
111 | 776 basic_block bb = BASIC_BLOCK_FOR_FN (fun, i); |
777 if (bb == NULL) | |
778 continue; | |
779 while (single_succ_p (bb) | |
780 && (single_succ_edge (bb)->flags & EDGE_EH) == 0) | |
781 bb = single_succ (bb); | |
782 if (bb == EXIT_BLOCK_PTR_FOR_FN (fun)) | |
783 continue; | |
784 if ((unsigned) bb->index != i) | |
785 bitmap_set_bit (need_eh_cleanup, bb->index); | |
0 | 786 } |
787 | |
788 gimple_purge_all_dead_eh_edges (need_eh_cleanup); | |
111 | 789 bitmap_clear (need_eh_cleanup); |
0 | 790 } |
791 | |
111 | 792 /* Fixup stmts that became noreturn calls. This may require splitting |
793 blocks and thus isn't possible during the dominator walk or before | |
794 jump threading finished. Do this in reverse order so we don't | |
795 inadvertedly remove a stmt we want to fixup by visiting a dominating | |
796 now noreturn call first. */ | |
797 while (!need_noreturn_fixup.is_empty ()) | |
798 { | |
799 gimple *stmt = need_noreturn_fixup.pop (); | |
800 if (dump_file && dump_flags & TDF_DETAILS) | |
801 { | |
802 fprintf (dump_file, "Fixing up noreturn call "); | |
803 print_gimple_stmt (dump_file, stmt, 0); | |
804 fprintf (dump_file, "\n"); | |
805 } | |
806 fixup_noreturn_call (stmt); | |
807 } | |
808 | |
809 statistics_counter_event (fun, "Redundant expressions eliminated", | |
0 | 810 opt_stats.num_re); |
111 | 811 statistics_counter_event (fun, "Constants propagated", |
0 | 812 opt_stats.num_const_prop); |
111 | 813 statistics_counter_event (fun, "Copies propagated", |
0 | 814 opt_stats.num_copy_prop); |
815 | |
816 /* Debugging dumps. */ | |
817 if (dump_file && (dump_flags & TDF_STATS)) | |
111 | 818 dump_dominator_optimization_stats (dump_file, avail_exprs); |
0 | 819 |
820 loop_optimizer_finalize (); | |
821 | |
822 /* Delete our main hashtable. */ | |
111 | 823 delete avail_exprs; |
824 avail_exprs = NULL; | |
0 | 825 |
826 /* Free asserted bitmaps and stacks. */ | |
827 BITMAP_FREE (need_eh_cleanup); | |
111 | 828 need_noreturn_fixup.release (); |
829 delete avail_exprs_stack; | |
830 delete const_and_copies; | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
831 |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
832 /* Free the value-handle array. */ |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
833 threadedge_finalize_values (); |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
834 |
0 | 835 return 0; |
836 } | |
837 | |
111 | 838 } // anon namespace |
839 | |
840 gimple_opt_pass * | |
841 make_pass_dominator (gcc::context *ctxt) | |
0 | 842 { |
111 | 843 return new pass_dominator (ctxt); |
0 | 844 } |
845 | |
131 | 846 /* A hack until we remove threading from tree-vrp.c and bring the |
847 simplification routine into the dom_opt_dom_walker class. */ | |
848 static class vr_values *x_vr_values; | |
0 | 849 |
850 /* A trivial wrapper so that we can present the generic jump | |
851 threading code with a simple API for simplifying statements. */ | |
852 static tree | |
111 | 853 simplify_stmt_for_jump_threading (gimple *stmt, |
854 gimple *within_stmt ATTRIBUTE_UNUSED, | |
855 class avail_exprs_stack *avail_exprs_stack, | |
856 basic_block bb ATTRIBUTE_UNUSED) | |
0 | 857 { |
131 | 858 /* First query our hash table to see if the the expression is available |
859 there. A non-NULL return value will be either a constant or another | |
860 SSA_NAME. */ | |
861 tree cached_lhs = avail_exprs_stack->lookup_avail_expr (stmt, false, true); | |
862 if (cached_lhs) | |
863 return cached_lhs; | |
864 | |
865 /* If the hash table query failed, query VRP information. This is | |
866 essentially the same as tree-vrp's simplification routine. The | |
867 copy in tree-vrp is scheduled for removal in gcc-9. */ | |
868 if (gcond *cond_stmt = dyn_cast <gcond *> (stmt)) | |
869 { | |
870 cached_lhs | |
871 = x_vr_values->vrp_evaluate_conditional (gimple_cond_code (cond_stmt), | |
872 gimple_cond_lhs (cond_stmt), | |
873 gimple_cond_rhs (cond_stmt), | |
874 within_stmt); | |
875 return cached_lhs; | |
876 } | |
877 | |
878 if (gswitch *switch_stmt = dyn_cast <gswitch *> (stmt)) | |
879 { | |
880 tree op = gimple_switch_index (switch_stmt); | |
881 if (TREE_CODE (op) != SSA_NAME) | |
882 return NULL_TREE; | |
883 | |
884 value_range *vr = x_vr_values->get_value_range (op); | |
885 if (vr->undefined_p () | |
886 || vr->varying_p () | |
887 || vr->symbolic_p ()) | |
888 return NULL_TREE; | |
889 | |
890 if (vr->kind () == VR_RANGE) | |
891 { | |
892 size_t i, j; | |
893 | |
894 find_case_label_range (switch_stmt, vr->min (), vr->max (), &i, &j); | |
895 | |
896 if (i == j) | |
897 { | |
898 tree label = gimple_switch_label (switch_stmt, i); | |
899 tree singleton; | |
900 | |
901 if (CASE_HIGH (label) != NULL_TREE | |
902 ? (tree_int_cst_compare (CASE_LOW (label), vr->min ()) <= 0 | |
903 && tree_int_cst_compare (CASE_HIGH (label), vr->max ()) >= 0) | |
904 : (vr->singleton_p (&singleton) | |
905 && tree_int_cst_equal (CASE_LOW (label), singleton))) | |
906 return label; | |
907 | |
908 if (i > j) | |
909 return gimple_switch_label (switch_stmt, 0); | |
910 } | |
911 } | |
912 | |
913 if (vr->kind () == VR_ANTI_RANGE) | |
914 { | |
915 unsigned n = gimple_switch_num_labels (switch_stmt); | |
916 tree min_label = gimple_switch_label (switch_stmt, 1); | |
917 tree max_label = gimple_switch_label (switch_stmt, n - 1); | |
918 | |
919 /* The default label will be taken only if the anti-range of the | |
920 operand is entirely outside the bounds of all the (non-default) | |
921 case labels. */ | |
922 if (tree_int_cst_compare (vr->min (), CASE_LOW (min_label)) <= 0 | |
923 && (CASE_HIGH (max_label) != NULL_TREE | |
924 ? tree_int_cst_compare (vr->max (), CASE_HIGH (max_label)) >= 0 | |
925 : tree_int_cst_compare (vr->max (), CASE_LOW (max_label)) >= 0)) | |
926 return gimple_switch_label (switch_stmt, 0); | |
927 } | |
928 return NULL_TREE; | |
929 } | |
930 | |
931 if (gassign *assign_stmt = dyn_cast <gassign *> (stmt)) | |
932 { | |
933 tree lhs = gimple_assign_lhs (assign_stmt); | |
934 if (TREE_CODE (lhs) == SSA_NAME | |
935 && (INTEGRAL_TYPE_P (TREE_TYPE (lhs)) | |
936 || POINTER_TYPE_P (TREE_TYPE (lhs))) | |
937 && stmt_interesting_for_vrp (stmt)) | |
938 { | |
939 edge dummy_e; | |
940 tree dummy_tree; | |
941 value_range new_vr; | |
942 x_vr_values->extract_range_from_stmt (stmt, &dummy_e, | |
943 &dummy_tree, &new_vr); | |
944 tree singleton; | |
945 if (new_vr.singleton_p (&singleton)) | |
946 return singleton; | |
947 } | |
948 } | |
949 return NULL; | |
111 | 950 } |
951 | |
952 /* Valueize hook for gimple_fold_stmt_to_constant_1. */ | |
953 | |
954 static tree | |
955 dom_valueize (tree t) | |
956 { | |
957 if (TREE_CODE (t) == SSA_NAME) | |
958 { | |
959 tree tem = SSA_NAME_VALUE (t); | |
960 if (tem) | |
961 return tem; | |
962 } | |
963 return t; | |
0 | 964 } |
965 | |
111 | 966 /* We have just found an equivalence for LHS on an edge E. |
967 Look backwards to other uses of LHS and see if we can derive | |
968 additional equivalences that are valid on edge E. */ | |
0 | 969 static void |
111 | 970 back_propagate_equivalences (tree lhs, edge e, |
971 class const_and_copies *const_and_copies) | |
0 | 972 { |
111 | 973 use_operand_p use_p; |
974 imm_use_iterator iter; | |
975 bitmap domby = NULL; | |
976 basic_block dest = e->dest; | |
977 | |
978 /* Iterate over the uses of LHS to see if any dominate E->dest. | |
979 If so, they may create useful equivalences too. | |
980 | |
981 ??? If the code gets re-organized to a worklist to catch more | |
982 indirect opportunities and it is made to handle PHIs then this | |
983 should only consider use_stmts in basic-blocks we have already visited. */ | |
984 FOR_EACH_IMM_USE_FAST (use_p, iter, lhs) | |
985 { | |
986 gimple *use_stmt = USE_STMT (use_p); | |
987 | |
988 /* Often the use is in DEST, which we trivially know we can't use. | |
989 This is cheaper than the dominator set tests below. */ | |
990 if (dest == gimple_bb (use_stmt)) | |
991 continue; | |
992 | |
993 /* Filter out statements that can never produce a useful | |
994 equivalence. */ | |
995 tree lhs2 = gimple_get_lhs (use_stmt); | |
996 if (!lhs2 || TREE_CODE (lhs2) != SSA_NAME) | |
997 continue; | |
998 | |
999 /* Profiling has shown the domination tests here can be fairly | |
1000 expensive. We get significant improvements by building the | |
1001 set of blocks that dominate BB. We can then just test | |
1002 for set membership below. | |
1003 | |
1004 We also initialize the set lazily since often the only uses | |
1005 are going to be in the same block as DEST. */ | |
1006 if (!domby) | |
1007 { | |
1008 domby = BITMAP_ALLOC (NULL); | |
1009 basic_block bb = get_immediate_dominator (CDI_DOMINATORS, dest); | |
1010 while (bb) | |
1011 { | |
1012 bitmap_set_bit (domby, bb->index); | |
1013 bb = get_immediate_dominator (CDI_DOMINATORS, bb); | |
1014 } | |
1015 } | |
1016 | |
1017 /* This tests if USE_STMT does not dominate DEST. */ | |
1018 if (!bitmap_bit_p (domby, gimple_bb (use_stmt)->index)) | |
1019 continue; | |
1020 | |
1021 /* At this point USE_STMT dominates DEST and may result in a | |
1022 useful equivalence. Try to simplify its RHS to a constant | |
1023 or SSA_NAME. */ | |
1024 tree res = gimple_fold_stmt_to_constant_1 (use_stmt, dom_valueize, | |
1025 no_follow_ssa_edges); | |
1026 if (res && (TREE_CODE (res) == SSA_NAME || is_gimple_min_invariant (res))) | |
1027 record_equality (lhs2, res, const_and_copies); | |
1028 } | |
1029 | |
1030 if (domby) | |
1031 BITMAP_FREE (domby); | |
1032 } | |
0 | 1033 |
111 | 1034 /* Record into CONST_AND_COPIES and AVAIL_EXPRS_STACK any equivalences implied |
1035 by traversing edge E (which are cached in E->aux). | |
1036 | |
1037 Callers are responsible for managing the unwinding markers. */ | |
1038 void | |
1039 record_temporary_equivalences (edge e, | |
1040 class const_and_copies *const_and_copies, | |
1041 class avail_exprs_stack *avail_exprs_stack) | |
1042 { | |
1043 int i; | |
1044 class edge_info *edge_info = (class edge_info *) e->aux; | |
1045 | |
1046 /* If we have info associated with this edge, record it into | |
1047 our equivalence tables. */ | |
1048 if (edge_info) | |
1049 { | |
1050 cond_equivalence *eq; | |
1051 /* If we have 0 = COND or 1 = COND equivalences, record them | |
1052 into our expression hash tables. */ | |
1053 for (i = 0; edge_info->cond_equivalences.iterate (i, &eq); ++i) | |
1054 avail_exprs_stack->record_cond (eq); | |
1055 | |
1056 edge_info::equiv_pair *seq; | |
1057 for (i = 0; edge_info->simple_equivalences.iterate (i, &seq); ++i) | |
1058 { | |
1059 tree lhs = seq->first; | |
1060 if (!lhs || TREE_CODE (lhs) != SSA_NAME) | |
1061 continue; | |
1062 | |
1063 /* Record the simple NAME = VALUE equivalence. */ | |
1064 tree rhs = seq->second; | |
1065 | |
1066 /* If this is a SSA_NAME = SSA_NAME equivalence and one operand is | |
1067 cheaper to compute than the other, then set up the equivalence | |
1068 such that we replace the expensive one with the cheap one. | |
1069 | |
1070 If they are the same cost to compute, then do not record | |
1071 anything. */ | |
1072 if (TREE_CODE (lhs) == SSA_NAME && TREE_CODE (rhs) == SSA_NAME) | |
1073 { | |
1074 gimple *rhs_def = SSA_NAME_DEF_STMT (rhs); | |
1075 int rhs_cost = estimate_num_insns (rhs_def, &eni_size_weights); | |
1076 | |
1077 gimple *lhs_def = SSA_NAME_DEF_STMT (lhs); | |
1078 int lhs_cost = estimate_num_insns (lhs_def, &eni_size_weights); | |
1079 | |
1080 if (rhs_cost > lhs_cost) | |
1081 record_equality (rhs, lhs, const_and_copies); | |
1082 else if (rhs_cost < lhs_cost) | |
1083 record_equality (lhs, rhs, const_and_copies); | |
1084 } | |
1085 else | |
1086 record_equality (lhs, rhs, const_and_copies); | |
1087 | |
1088 | |
1089 /* Any equivalence found for LHS may result in additional | |
1090 equivalences for other uses of LHS that we have already | |
1091 processed. */ | |
1092 back_propagate_equivalences (lhs, e, const_and_copies); | |
1093 } | |
1094 } | |
0 | 1095 } |
1096 | |
1097 /* PHI nodes can create equivalences too. | |
1098 | |
1099 Ignoring any alternatives which are the same as the result, if | |
1100 all the alternatives are equal, then the PHI node creates an | |
1101 equivalence. */ | |
1102 | |
1103 static void | |
1104 record_equivalences_from_phis (basic_block bb) | |
1105 { | |
111 | 1106 gphi_iterator gsi; |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1107 |
0 | 1108 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) |
1109 { | |
111 | 1110 gphi *phi = gsi.phi (); |
0 | 1111 |
1112 tree lhs = gimple_phi_result (phi); | |
1113 tree rhs = NULL; | |
1114 size_t i; | |
1115 | |
1116 for (i = 0; i < gimple_phi_num_args (phi); i++) | |
1117 { | |
1118 tree t = gimple_phi_arg_def (phi, i); | |
1119 | |
1120 /* Ignore alternatives which are the same as our LHS. Since | |
1121 LHS is a PHI_RESULT, it is known to be a SSA_NAME, so we | |
1122 can simply compare pointers. */ | |
1123 if (lhs == t) | |
1124 continue; | |
1125 | |
111 | 1126 /* If the associated edge is not marked as executable, then it |
1127 can be ignored. */ | |
1128 if ((gimple_phi_arg_edge (phi, i)->flags & EDGE_EXECUTABLE) == 0) | |
1129 continue; | |
1130 | |
1131 t = dom_valueize (t); | |
1132 | |
131 | 1133 /* If T is an SSA_NAME and its associated edge is a backedge, |
1134 then quit as we can not utilize this equivalence. */ | |
1135 if (TREE_CODE (t) == SSA_NAME | |
1136 && (gimple_phi_arg_edge (phi, i)->flags & EDGE_DFS_BACK)) | |
1137 break; | |
1138 | |
0 | 1139 /* If we have not processed an alternative yet, then set |
1140 RHS to this alternative. */ | |
1141 if (rhs == NULL) | |
1142 rhs = t; | |
1143 /* If we have processed an alternative (stored in RHS), then | |
1144 see if it is equal to this one. If it isn't, then stop | |
1145 the search. */ | |
1146 else if (! operand_equal_for_phi_arg_p (rhs, t)) | |
1147 break; | |
1148 } | |
1149 | |
1150 /* If we had no interesting alternatives, then all the RHS alternatives | |
1151 must have been the same as LHS. */ | |
1152 if (!rhs) | |
1153 rhs = lhs; | |
1154 | |
1155 /* If we managed to iterate through each PHI alternative without | |
1156 breaking out of the loop, then we have a PHI which may create | |
1157 a useful equivalence. We do not need to record unwind data for | |
1158 this, since this is a true assignment and not an equivalence | |
1159 inferred from a comparison. All uses of this ssa name are dominated | |
1160 by this assignment, so unwinding just costs time and space. */ | |
111 | 1161 if (i == gimple_phi_num_args (phi) |
1162 && may_propagate_copy (lhs, rhs)) | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1163 set_ssa_name_value (lhs, rhs); |
0 | 1164 } |
1165 } | |
1166 | |
111 | 1167 /* Record any equivalences created by the incoming edge to BB into |
1168 CONST_AND_COPIES and AVAIL_EXPRS_STACK. If BB has more than one | |
1169 incoming edge, then no equivalence is created. */ | |
0 | 1170 |
1171 static void | |
111 | 1172 record_equivalences_from_incoming_edge (basic_block bb, |
1173 class const_and_copies *const_and_copies, | |
1174 class avail_exprs_stack *avail_exprs_stack) | |
0 | 1175 { |
1176 edge e; | |
1177 basic_block parent; | |
1178 | |
1179 /* If our parent block ended with a control statement, then we may be | |
1180 able to record some equivalences based on which outgoing edge from | |
1181 the parent was followed. */ | |
1182 parent = get_immediate_dominator (CDI_DOMINATORS, bb); | |
1183 | |
131 | 1184 e = single_pred_edge_ignoring_loop_edges (bb, true); |
0 | 1185 |
1186 /* If we had a single incoming edge from our parent block, then enter | |
1187 any data associated with the edge into our tables. */ | |
1188 if (e && e->src == parent) | |
111 | 1189 record_temporary_equivalences (e, const_and_copies, avail_exprs_stack); |
1190 } | |
0 | 1191 |
111 | 1192 /* Dump statistics for the hash table HTAB. */ |
0 | 1193 |
111 | 1194 static void |
1195 htab_statistics (FILE *file, const hash_table<expr_elt_hasher> &htab) | |
1196 { | |
1197 fprintf (file, "size %ld, %ld elements, %f collision/search ratio\n", | |
1198 (long) htab.size (), | |
1199 (long) htab.elements (), | |
1200 htab.collisions ()); | |
0 | 1201 } |
1202 | |
1203 /* Dump SSA statistics on FILE. */ | |
1204 | |
111 | 1205 static void |
1206 dump_dominator_optimization_stats (FILE *file, | |
1207 hash_table<expr_elt_hasher> *avail_exprs) | |
0 | 1208 { |
1209 fprintf (file, "Total number of statements: %6ld\n\n", | |
1210 opt_stats.num_stmts); | |
1211 fprintf (file, "Exprs considered for dominator optimizations: %6ld\n", | |
1212 opt_stats.num_exprs_considered); | |
1213 | |
1214 fprintf (file, "\nHash table statistics:\n"); | |
1215 | |
1216 fprintf (file, " avail_exprs: "); | |
111 | 1217 htab_statistics (file, *avail_exprs); |
0 | 1218 } |
1219 | |
1220 | |
1221 /* Similarly, but assume that X and Y are the two operands of an EQ_EXPR. | |
1222 This constrains the cases in which we may treat this as assignment. */ | |
1223 | |
1224 static void | |
111 | 1225 record_equality (tree x, tree y, class const_and_copies *const_and_copies) |
0 | 1226 { |
1227 tree prev_x = NULL, prev_y = NULL; | |
1228 | |
111 | 1229 if (tree_swap_operands_p (x, y)) |
1230 std::swap (x, y); | |
1231 | |
1232 /* Most of the time tree_swap_operands_p does what we want. But there | |
1233 are cases where we know one operand is better for copy propagation than | |
1234 the other. Given no other code cares about ordering of equality | |
1235 comparison operators for that purpose, we just handle the special cases | |
1236 here. */ | |
1237 if (TREE_CODE (x) == SSA_NAME && TREE_CODE (y) == SSA_NAME) | |
1238 { | |
1239 /* If one operand is a single use operand, then make it | |
1240 X. This will preserve its single use properly and if this | |
1241 conditional is eliminated, the computation of X can be | |
1242 eliminated as well. */ | |
1243 if (has_single_use (y) && ! has_single_use (x)) | |
1244 std::swap (x, y); | |
1245 } | |
0 | 1246 if (TREE_CODE (x) == SSA_NAME) |
1247 prev_x = SSA_NAME_VALUE (x); | |
1248 if (TREE_CODE (y) == SSA_NAME) | |
1249 prev_y = SSA_NAME_VALUE (y); | |
1250 | |
1251 /* If one of the previous values is invariant, or invariant in more loops | |
1252 (by depth), then use that. | |
1253 Otherwise it doesn't matter which value we choose, just so | |
1254 long as we canonicalize on one value. */ | |
1255 if (is_gimple_min_invariant (y)) | |
1256 ; | |
111 | 1257 else if (is_gimple_min_invariant (x)) |
0 | 1258 prev_x = x, x = y, y = prev_x, prev_x = prev_y; |
1259 else if (prev_x && is_gimple_min_invariant (prev_x)) | |
1260 x = y, y = prev_x, prev_x = prev_y; | |
1261 else if (prev_y) | |
1262 y = prev_y; | |
1263 | |
1264 /* After the swapping, we must have one SSA_NAME. */ | |
1265 if (TREE_CODE (x) != SSA_NAME) | |
1266 return; | |
1267 | |
1268 /* For IEEE, -0.0 == 0.0, so we don't necessarily know the sign of a | |
1269 variable compared against zero. If we're honoring signed zeros, | |
1270 then we cannot record this value unless we know that the value is | |
1271 nonzero. */ | |
111 | 1272 if (HONOR_SIGNED_ZEROS (x) |
0 | 1273 && (TREE_CODE (y) != REAL_CST |
111 | 1274 || real_equal (&dconst0, &TREE_REAL_CST (y)))) |
0 | 1275 return; |
1276 | |
111 | 1277 const_and_copies->record_const_or_copy (x, y, prev_x); |
0 | 1278 } |
1279 | |
1280 /* Returns true when STMT is a simple iv increment. It detects the | |
1281 following situation: | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1282 |
131 | 1283 i_1 = phi (..., i_k) |
1284 [...] | |
1285 i_j = i_{j-1} for each j : 2 <= j <= k-1 | |
1286 [...] | |
1287 i_k = i_{k-1} +/- ... */ | |
0 | 1288 |
111 | 1289 bool |
1290 simple_iv_increment_p (gimple *stmt) | |
0 | 1291 { |
111 | 1292 enum tree_code code; |
0 | 1293 tree lhs, preinc; |
111 | 1294 gimple *phi; |
0 | 1295 size_t i; |
1296 | |
1297 if (gimple_code (stmt) != GIMPLE_ASSIGN) | |
1298 return false; | |
1299 | |
1300 lhs = gimple_assign_lhs (stmt); | |
1301 if (TREE_CODE (lhs) != SSA_NAME) | |
1302 return false; | |
1303 | |
111 | 1304 code = gimple_assign_rhs_code (stmt); |
1305 if (code != PLUS_EXPR | |
1306 && code != MINUS_EXPR | |
1307 && code != POINTER_PLUS_EXPR) | |
0 | 1308 return false; |
1309 | |
1310 preinc = gimple_assign_rhs1 (stmt); | |
1311 if (TREE_CODE (preinc) != SSA_NAME) | |
1312 return false; | |
1313 | |
1314 phi = SSA_NAME_DEF_STMT (preinc); | |
131 | 1315 while (gimple_code (phi) != GIMPLE_PHI) |
1316 { | |
1317 /* Follow trivial copies, but not the DEF used in a back edge, | |
1318 so that we don't prevent coalescing. */ | |
1319 if (!gimple_assign_ssa_name_copy_p (phi)) | |
1320 return false; | |
1321 preinc = gimple_assign_rhs1 (phi); | |
1322 phi = SSA_NAME_DEF_STMT (preinc); | |
1323 } | |
0 | 1324 |
1325 for (i = 0; i < gimple_phi_num_args (phi); i++) | |
1326 if (gimple_phi_arg_def (phi, i) == lhs) | |
1327 return true; | |
1328 | |
1329 return false; | |
1330 } | |
1331 | |
111 | 1332 /* Propagate know values from SSA_NAME_VALUE into the PHI nodes of the |
0 | 1333 successors of BB. */ |
1334 | |
1335 static void | |
111 | 1336 cprop_into_successor_phis (basic_block bb, |
1337 class const_and_copies *const_and_copies) | |
0 | 1338 { |
1339 edge e; | |
1340 edge_iterator ei; | |
1341 | |
1342 FOR_EACH_EDGE (e, ei, bb->succs) | |
1343 { | |
1344 int indx; | |
111 | 1345 gphi_iterator gsi; |
0 | 1346 |
1347 /* If this is an abnormal edge, then we do not want to copy propagate | |
1348 into the PHI alternative associated with this edge. */ | |
1349 if (e->flags & EDGE_ABNORMAL) | |
1350 continue; | |
1351 | |
1352 gsi = gsi_start_phis (e->dest); | |
1353 if (gsi_end_p (gsi)) | |
1354 continue; | |
1355 | |
111 | 1356 /* We may have an equivalence associated with this edge. While |
1357 we can not propagate it into non-dominated blocks, we can | |
1358 propagate them into PHIs in non-dominated blocks. */ | |
1359 | |
1360 /* Push the unwind marker so we can reset the const and copies | |
1361 table back to its original state after processing this edge. */ | |
1362 const_and_copies->push_marker (); | |
1363 | |
1364 /* Extract and record any simple NAME = VALUE equivalences. | |
1365 | |
1366 Don't bother with [01] = COND equivalences, they're not useful | |
1367 here. */ | |
1368 class edge_info *edge_info = (class edge_info *) e->aux; | |
1369 | |
1370 if (edge_info) | |
1371 { | |
1372 edge_info::equiv_pair *seq; | |
1373 for (int i = 0; edge_info->simple_equivalences.iterate (i, &seq); ++i) | |
1374 { | |
1375 tree lhs = seq->first; | |
1376 tree rhs = seq->second; | |
1377 | |
1378 if (lhs && TREE_CODE (lhs) == SSA_NAME) | |
1379 const_and_copies->record_const_or_copy (lhs, rhs); | |
1380 } | |
1381 | |
1382 } | |
1383 | |
0 | 1384 indx = e->dest_idx; |
1385 for ( ; !gsi_end_p (gsi); gsi_next (&gsi)) | |
1386 { | |
1387 tree new_val; | |
1388 use_operand_p orig_p; | |
1389 tree orig_val; | |
111 | 1390 gphi *phi = gsi.phi (); |
0 | 1391 |
1392 /* The alternative may be associated with a constant, so verify | |
1393 it is an SSA_NAME before doing anything with it. */ | |
1394 orig_p = gimple_phi_arg_imm_use_ptr (phi, indx); | |
1395 orig_val = get_use_from_ptr (orig_p); | |
1396 if (TREE_CODE (orig_val) != SSA_NAME) | |
1397 continue; | |
1398 | |
1399 /* If we have *ORIG_P in our constant/copy table, then replace | |
1400 ORIG_P with its value in our constant/copy table. */ | |
1401 new_val = SSA_NAME_VALUE (orig_val); | |
1402 if (new_val | |
1403 && new_val != orig_val | |
1404 && may_propagate_copy (orig_val, new_val)) | |
1405 propagate_value (orig_p, new_val); | |
1406 } | |
111 | 1407 |
1408 const_and_copies->pop_to_marker (); | |
0 | 1409 } |
1410 } | |
1411 | |
111 | 1412 edge |
1413 dom_opt_dom_walker::before_dom_children (basic_block bb) | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1414 { |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1415 gimple_stmt_iterator gsi; |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1416 |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1417 if (dump_file && (dump_flags & TDF_DETAILS)) |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1418 fprintf (dump_file, "\n\nOptimizing block #%d\n\n", bb->index); |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1419 |
131 | 1420 evrp_range_analyzer.enter (bb); |
1421 | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1422 /* Push a marker on the stacks of local information so that we know how |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1423 far to unwind when we finalize this block. */ |
111 | 1424 m_avail_exprs_stack->push_marker (); |
1425 m_const_and_copies->push_marker (); | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1426 |
111 | 1427 record_equivalences_from_incoming_edge (bb, m_const_and_copies, |
1428 m_avail_exprs_stack); | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1429 |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1430 /* PHI nodes can create equivalences too. */ |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1431 record_equivalences_from_phis (bb); |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1432 |
111 | 1433 /* Create equivalences from redundant PHIs. PHIs are only truly |
1434 redundant when they exist in the same block, so push another | |
1435 marker and unwind right afterwards. */ | |
1436 m_avail_exprs_stack->push_marker (); | |
1437 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) | |
1438 eliminate_redundant_computations (&gsi, m_const_and_copies, | |
1439 m_avail_exprs_stack); | |
1440 m_avail_exprs_stack->pop_to_marker (); | |
1441 | |
1442 edge taken_edge = NULL; | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1443 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) |
131 | 1444 { |
1445 evrp_range_analyzer.record_ranges_from_stmt (gsi_stmt (gsi), false); | |
1446 taken_edge = this->optimize_stmt (bb, gsi); | |
1447 } | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1448 |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1449 /* Now prepare to process dominated blocks. */ |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1450 record_edge_info (bb); |
111 | 1451 cprop_into_successor_phis (bb, m_const_and_copies); |
1452 if (taken_edge && !dbg_cnt (dom_unreachable_edges)) | |
1453 return NULL; | |
1454 | |
1455 return taken_edge; | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1456 } |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1457 |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1458 /* We have finished processing the dominator children of BB, perform |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1459 any finalization actions in preparation for leaving this node in |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1460 the dominator tree. */ |
0 | 1461 |
111 | 1462 void |
1463 dom_opt_dom_walker::after_dom_children (basic_block bb) | |
0 | 1464 { |
131 | 1465 x_vr_values = evrp_range_analyzer.get_vr_values (); |
111 | 1466 thread_outgoing_edges (bb, m_dummy_cond, m_const_and_copies, |
1467 m_avail_exprs_stack, | |
131 | 1468 &evrp_range_analyzer, |
111 | 1469 simplify_stmt_for_jump_threading); |
131 | 1470 x_vr_values = NULL; |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1471 |
111 | 1472 /* These remove expressions local to BB from the tables. */ |
1473 m_avail_exprs_stack->pop_to_marker (); | |
1474 m_const_and_copies->pop_to_marker (); | |
131 | 1475 evrp_range_analyzer.leave (bb); |
0 | 1476 } |
1477 | |
1478 /* Search for redundant computations in STMT. If any are found, then | |
1479 replace them with the variable holding the result of the computation. | |
1480 | |
111 | 1481 If safe, record this expression into AVAIL_EXPRS_STACK and |
1482 CONST_AND_COPIES. */ | |
0 | 1483 |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1484 static void |
111 | 1485 eliminate_redundant_computations (gimple_stmt_iterator* gsi, |
1486 class const_and_copies *const_and_copies, | |
1487 class avail_exprs_stack *avail_exprs_stack) | |
0 | 1488 { |
1489 tree expr_type; | |
1490 tree cached_lhs; | |
111 | 1491 tree def; |
0 | 1492 bool insert = true; |
1493 bool assigns_var_p = false; | |
1494 | |
111 | 1495 gimple *stmt = gsi_stmt (*gsi); |
0 | 1496 |
111 | 1497 if (gimple_code (stmt) == GIMPLE_PHI) |
1498 def = gimple_phi_result (stmt); | |
1499 else | |
1500 def = gimple_get_lhs (stmt); | |
0 | 1501 |
1502 /* Certain expressions on the RHS can be optimized away, but can not | |
1503 themselves be entered into the hash tables. */ | |
1504 if (! def | |
1505 || TREE_CODE (def) != SSA_NAME | |
1506 || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def) | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1507 || gimple_vdef (stmt) |
0 | 1508 /* Do not record equivalences for increments of ivs. This would create |
1509 overlapping live ranges for a very questionable gain. */ | |
1510 || simple_iv_increment_p (stmt)) | |
1511 insert = false; | |
1512 | |
1513 /* Check if the expression has been computed before. */ | |
111 | 1514 cached_lhs = avail_exprs_stack->lookup_avail_expr (stmt, insert, true); |
0 | 1515 |
1516 opt_stats.num_exprs_considered++; | |
1517 | |
1518 /* Get the type of the expression we are trying to optimize. */ | |
1519 if (is_gimple_assign (stmt)) | |
1520 { | |
1521 expr_type = TREE_TYPE (gimple_assign_lhs (stmt)); | |
1522 assigns_var_p = true; | |
1523 } | |
1524 else if (gimple_code (stmt) == GIMPLE_COND) | |
1525 expr_type = boolean_type_node; | |
1526 else if (is_gimple_call (stmt)) | |
1527 { | |
1528 gcc_assert (gimple_call_lhs (stmt)); | |
1529 expr_type = TREE_TYPE (gimple_call_lhs (stmt)); | |
1530 assigns_var_p = true; | |
1531 } | |
111 | 1532 else if (gswitch *swtch_stmt = dyn_cast <gswitch *> (stmt)) |
1533 expr_type = TREE_TYPE (gimple_switch_index (swtch_stmt)); | |
1534 else if (gimple_code (stmt) == GIMPLE_PHI) | |
1535 /* We can't propagate into a phi, so the logic below doesn't apply. | |
1536 Instead record an equivalence between the cached LHS and the | |
1537 PHI result of this statement, provided they are in the same block. | |
1538 This should be sufficient to kill the redundant phi. */ | |
1539 { | |
1540 if (def && cached_lhs) | |
1541 const_and_copies->record_const_or_copy (def, cached_lhs); | |
1542 return; | |
1543 } | |
0 | 1544 else |
1545 gcc_unreachable (); | |
1546 | |
1547 if (!cached_lhs) | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1548 return; |
0 | 1549 |
1550 /* It is safe to ignore types here since we have already done | |
1551 type checking in the hashing and equality routines. In fact | |
1552 type checking here merely gets in the way of constant | |
1553 propagation. Also, make sure that it is safe to propagate | |
1554 CACHED_LHS into the expression in STMT. */ | |
1555 if ((TREE_CODE (cached_lhs) != SSA_NAME | |
1556 && (assigns_var_p | |
1557 || useless_type_conversion_p (expr_type, TREE_TYPE (cached_lhs)))) | |
1558 || may_propagate_copy_into_stmt (stmt, cached_lhs)) | |
1559 { | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1560 gcc_checking_assert (TREE_CODE (cached_lhs) == SSA_NAME |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1561 || is_gimple_min_invariant (cached_lhs)); |
0 | 1562 |
1563 if (dump_file && (dump_flags & TDF_DETAILS)) | |
1564 { | |
1565 fprintf (dump_file, " Replaced redundant expr '"); | |
1566 print_gimple_expr (dump_file, stmt, 0, dump_flags); | |
1567 fprintf (dump_file, "' with '"); | |
1568 print_generic_expr (dump_file, cached_lhs, dump_flags); | |
1569 fprintf (dump_file, "'\n"); | |
1570 } | |
1571 | |
1572 opt_stats.num_re++; | |
1573 | |
1574 if (assigns_var_p | |
1575 && !useless_type_conversion_p (expr_type, TREE_TYPE (cached_lhs))) | |
1576 cached_lhs = fold_convert (expr_type, cached_lhs); | |
1577 | |
1578 propagate_tree_value_into_stmt (gsi, cached_lhs); | |
1579 | |
1580 /* Since it is always necessary to mark the result as modified, | |
1581 perhaps we should move this into propagate_tree_value_into_stmt | |
1582 itself. */ | |
1583 gimple_set_modified (gsi_stmt (*gsi), true); | |
1584 } | |
1585 } | |
1586 | |
1587 /* STMT, a GIMPLE_ASSIGN, may create certain equivalences, in either | |
1588 the available expressions table or the const_and_copies table. | |
111 | 1589 Detect and record those equivalences into AVAIL_EXPRS_STACK. |
1590 | |
1591 We handle only very simple copy equivalences here. The heavy | |
0 | 1592 lifing is done by eliminate_redundant_computations. */ |
1593 | |
1594 static void | |
111 | 1595 record_equivalences_from_stmt (gimple *stmt, int may_optimize_p, |
1596 class avail_exprs_stack *avail_exprs_stack) | |
0 | 1597 { |
1598 tree lhs; | |
1599 enum tree_code lhs_code; | |
1600 | |
1601 gcc_assert (is_gimple_assign (stmt)); | |
1602 | |
1603 lhs = gimple_assign_lhs (stmt); | |
1604 lhs_code = TREE_CODE (lhs); | |
1605 | |
1606 if (lhs_code == SSA_NAME | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1607 && gimple_assign_single_p (stmt)) |
0 | 1608 { |
1609 tree rhs = gimple_assign_rhs1 (stmt); | |
1610 | |
1611 /* If the RHS of the assignment is a constant or another variable that | |
1612 may be propagated, register it in the CONST_AND_COPIES table. We | |
1613 do not need to record unwind data for this, since this is a true | |
1614 assignment and not an equivalence inferred from a comparison. All | |
1615 uses of this ssa name are dominated by this assignment, so unwinding | |
1616 just costs time and space. */ | |
1617 if (may_optimize_p | |
1618 && (TREE_CODE (rhs) == SSA_NAME | |
1619 || is_gimple_min_invariant (rhs))) | |
111 | 1620 { |
1621 rhs = dom_valueize (rhs); | |
1622 | |
1623 if (dump_file && (dump_flags & TDF_DETAILS)) | |
1624 { | |
1625 fprintf (dump_file, "==== ASGN "); | |
1626 print_generic_expr (dump_file, lhs); | |
1627 fprintf (dump_file, " = "); | |
1628 print_generic_expr (dump_file, rhs); | |
1629 fprintf (dump_file, "\n"); | |
1630 } | |
1631 | |
1632 set_ssa_name_value (lhs, rhs); | |
1633 } | |
1634 } | |
0 | 1635 |
111 | 1636 /* Make sure we can propagate &x + CST. */ |
1637 if (lhs_code == SSA_NAME | |
1638 && gimple_assign_rhs_code (stmt) == POINTER_PLUS_EXPR | |
1639 && TREE_CODE (gimple_assign_rhs1 (stmt)) == ADDR_EXPR | |
1640 && TREE_CODE (gimple_assign_rhs2 (stmt)) == INTEGER_CST) | |
1641 { | |
1642 tree op0 = gimple_assign_rhs1 (stmt); | |
1643 tree op1 = gimple_assign_rhs2 (stmt); | |
1644 tree new_rhs | |
1645 = build_fold_addr_expr (fold_build2 (MEM_REF, | |
1646 TREE_TYPE (TREE_TYPE (op0)), | |
1647 unshare_expr (op0), | |
1648 fold_convert (ptr_type_node, | |
1649 op1))); | |
1650 if (dump_file && (dump_flags & TDF_DETAILS)) | |
1651 { | |
1652 fprintf (dump_file, "==== ASGN "); | |
1653 print_generic_expr (dump_file, lhs); | |
1654 fprintf (dump_file, " = "); | |
1655 print_generic_expr (dump_file, new_rhs); | |
1656 fprintf (dump_file, "\n"); | |
1657 } | |
1658 | |
1659 set_ssa_name_value (lhs, new_rhs); | |
0 | 1660 } |
1661 | |
1662 /* A memory store, even an aliased store, creates a useful | |
1663 equivalence. By exchanging the LHS and RHS, creating suitable | |
1664 vops and recording the result in the available expression table, | |
1665 we may be able to expose more redundant loads. */ | |
1666 if (!gimple_has_volatile_ops (stmt) | |
1667 && gimple_references_memory_p (stmt) | |
1668 && gimple_assign_single_p (stmt) | |
1669 && (TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME | |
1670 || is_gimple_min_invariant (gimple_assign_rhs1 (stmt))) | |
1671 && !is_gimple_reg (lhs)) | |
1672 { | |
1673 tree rhs = gimple_assign_rhs1 (stmt); | |
111 | 1674 gassign *new_stmt; |
0 | 1675 |
1676 /* Build a new statement with the RHS and LHS exchanged. */ | |
1677 if (TREE_CODE (rhs) == SSA_NAME) | |
1678 { | |
1679 /* NOTE tuples. The call to gimple_build_assign below replaced | |
1680 a call to build_gimple_modify_stmt, which did not set the | |
1681 SSA_NAME_DEF_STMT on the LHS of the assignment. Doing so | |
1682 may cause an SSA validation failure, as the LHS may be a | |
1683 default-initialized name and should have no definition. I'm | |
1684 a bit dubious of this, as the artificial statement that we | |
1685 generate here may in fact be ill-formed, but it is simply | |
1686 used as an internal device in this pass, and never becomes | |
1687 part of the CFG. */ | |
111 | 1688 gimple *defstmt = SSA_NAME_DEF_STMT (rhs); |
0 | 1689 new_stmt = gimple_build_assign (rhs, lhs); |
1690 SSA_NAME_DEF_STMT (rhs) = defstmt; | |
1691 } | |
1692 else | |
1693 new_stmt = gimple_build_assign (rhs, lhs); | |
1694 | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1695 gimple_set_vuse (new_stmt, gimple_vdef (stmt)); |
0 | 1696 |
1697 /* Finally enter the statement into the available expression | |
1698 table. */ | |
111 | 1699 avail_exprs_stack->lookup_avail_expr (new_stmt, true, true); |
0 | 1700 } |
1701 } | |
1702 | |
1703 /* Replace *OP_P in STMT with any known equivalent value for *OP_P from | |
1704 CONST_AND_COPIES. */ | |
1705 | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1706 static void |
131 | 1707 cprop_operand (gimple *stmt, use_operand_p op_p, vr_values *vr_values) |
0 | 1708 { |
1709 tree val; | |
1710 tree op = USE_FROM_PTR (op_p); | |
1711 | |
1712 /* If the operand has a known constant value or it is known to be a | |
1713 copy of some other variable, use the value or copy stored in | |
1714 CONST_AND_COPIES. */ | |
1715 val = SSA_NAME_VALUE (op); | |
131 | 1716 if (!val) |
1717 val = vr_values->op_with_constant_singleton_value_range (op); | |
1718 | |
0 | 1719 if (val && val != op) |
1720 { | |
1721 /* Do not replace hard register operands in asm statements. */ | |
1722 if (gimple_code (stmt) == GIMPLE_ASM | |
1723 && !may_propagate_copy_into_asm (op)) | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1724 return; |
0 | 1725 |
1726 /* Certain operands are not allowed to be copy propagated due | |
1727 to their interaction with exception handling and some GCC | |
1728 extensions. */ | |
1729 if (!may_propagate_copy (op, val)) | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1730 return; |
0 | 1731 |
111 | 1732 /* Do not propagate copies into BIVs. |
1733 See PR23821 and PR62217 for how this can disturb IV and | |
1734 number of iteration analysis. */ | |
1735 if (TREE_CODE (val) != INTEGER_CST) | |
1736 { | |
1737 gimple *def = SSA_NAME_DEF_STMT (op); | |
1738 if (gimple_code (def) == GIMPLE_PHI | |
1739 && gimple_bb (def)->loop_father->header == gimple_bb (def)) | |
1740 return; | |
1741 } | |
0 | 1742 |
1743 /* Dump details. */ | |
1744 if (dump_file && (dump_flags & TDF_DETAILS)) | |
1745 { | |
1746 fprintf (dump_file, " Replaced '"); | |
1747 print_generic_expr (dump_file, op, dump_flags); | |
1748 fprintf (dump_file, "' with %s '", | |
1749 (TREE_CODE (val) != SSA_NAME ? "constant" : "variable")); | |
1750 print_generic_expr (dump_file, val, dump_flags); | |
1751 fprintf (dump_file, "'\n"); | |
1752 } | |
1753 | |
1754 if (TREE_CODE (val) != SSA_NAME) | |
1755 opt_stats.num_const_prop++; | |
1756 else | |
1757 opt_stats.num_copy_prop++; | |
1758 | |
1759 propagate_value (op_p, val); | |
1760 | |
1761 /* And note that we modified this statement. This is now | |
1762 safe, even if we changed virtual operands since we will | |
1763 rescan the statement and rewrite its operands again. */ | |
1764 gimple_set_modified (stmt, true); | |
1765 } | |
1766 } | |
1767 | |
1768 /* CONST_AND_COPIES is a table which maps an SSA_NAME to the current | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1769 known value for that SSA_NAME (or NULL if no value is known). |
0 | 1770 |
1771 Propagate values from CONST_AND_COPIES into the uses, vuses and | |
1772 vdef_ops of STMT. */ | |
1773 | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1774 static void |
131 | 1775 cprop_into_stmt (gimple *stmt, vr_values *vr_values) |
0 | 1776 { |
1777 use_operand_p op_p; | |
1778 ssa_op_iter iter; | |
111 | 1779 tree last_copy_propagated_op = NULL; |
0 | 1780 |
111 | 1781 FOR_EACH_SSA_USE_OPERAND (op_p, stmt, iter, SSA_OP_USE) |
0 | 1782 { |
111 | 1783 tree old_op = USE_FROM_PTR (op_p); |
1784 | |
1785 /* If we have A = B and B = A in the copy propagation tables | |
1786 (due to an equality comparison), avoid substituting B for A | |
1787 then A for B in the trivially discovered cases. This allows | |
1788 optimization of statements were A and B appear as input | |
1789 operands. */ | |
1790 if (old_op != last_copy_propagated_op) | |
1791 { | |
131 | 1792 cprop_operand (stmt, op_p, vr_values); |
111 | 1793 |
1794 tree new_op = USE_FROM_PTR (op_p); | |
1795 if (new_op != old_op && TREE_CODE (new_op) == SSA_NAME) | |
1796 last_copy_propagated_op = new_op; | |
1797 } | |
0 | 1798 } |
1799 } | |
1800 | |
111 | 1801 /* If STMT contains a relational test, try to convert it into an |
1802 equality test if there is only a single value which can ever | |
1803 make the test true. | |
1804 | |
1805 For example, if the expression hash table contains: | |
1806 | |
1807 TRUE = (i <= 1) | |
1808 | |
1809 And we have a test within statement of i >= 1, then we can safely | |
1810 rewrite the test as i == 1 since there only a single value where | |
1811 the test is true. | |
1812 | |
1813 This is similar to code in VRP. */ | |
1814 | |
1815 static void | |
1816 test_for_singularity (gimple *stmt, gcond *dummy_cond, | |
1817 avail_exprs_stack *avail_exprs_stack) | |
1818 { | |
1819 /* We want to support gimple conditionals as well as assignments | |
1820 where the RHS contains a conditional. */ | |
1821 if (is_gimple_assign (stmt) || gimple_code (stmt) == GIMPLE_COND) | |
1822 { | |
1823 enum tree_code code = ERROR_MARK; | |
1824 tree lhs, rhs; | |
1825 | |
1826 /* Extract the condition of interest from both forms we support. */ | |
1827 if (is_gimple_assign (stmt)) | |
1828 { | |
1829 code = gimple_assign_rhs_code (stmt); | |
1830 lhs = gimple_assign_rhs1 (stmt); | |
1831 rhs = gimple_assign_rhs2 (stmt); | |
1832 } | |
1833 else if (gimple_code (stmt) == GIMPLE_COND) | |
1834 { | |
1835 code = gimple_cond_code (as_a <gcond *> (stmt)); | |
1836 lhs = gimple_cond_lhs (as_a <gcond *> (stmt)); | |
1837 rhs = gimple_cond_rhs (as_a <gcond *> (stmt)); | |
1838 } | |
1839 | |
1840 /* We're looking for a relational test using LE/GE. Also note we can | |
1841 canonicalize LT/GT tests against constants into LE/GT tests. */ | |
1842 if (code == LE_EXPR || code == GE_EXPR | |
1843 || ((code == LT_EXPR || code == GT_EXPR) | |
1844 && TREE_CODE (rhs) == INTEGER_CST)) | |
1845 { | |
1846 /* For LT_EXPR and GT_EXPR, canonicalize to LE_EXPR and GE_EXPR. */ | |
1847 if (code == LT_EXPR) | |
1848 rhs = fold_build2 (MINUS_EXPR, TREE_TYPE (rhs), | |
1849 rhs, build_int_cst (TREE_TYPE (rhs), 1)); | |
1850 | |
1851 if (code == GT_EXPR) | |
1852 rhs = fold_build2 (PLUS_EXPR, TREE_TYPE (rhs), | |
1853 rhs, build_int_cst (TREE_TYPE (rhs), 1)); | |
1854 | |
1855 /* Determine the code we want to check for in the hash table. */ | |
1856 enum tree_code test_code; | |
1857 if (code == GE_EXPR || code == GT_EXPR) | |
1858 test_code = LE_EXPR; | |
1859 else | |
1860 test_code = GE_EXPR; | |
1861 | |
1862 /* Update the dummy statement so we can query the hash tables. */ | |
1863 gimple_cond_set_code (dummy_cond, test_code); | |
1864 gimple_cond_set_lhs (dummy_cond, lhs); | |
1865 gimple_cond_set_rhs (dummy_cond, rhs); | |
1866 tree cached_lhs | |
1867 = avail_exprs_stack->lookup_avail_expr (dummy_cond, false, false); | |
1868 | |
1869 /* If the lookup returned 1 (true), then the expression we | |
1870 queried was in the hash table. As a result there is only | |
1871 one value that makes the original conditional true. Update | |
1872 STMT accordingly. */ | |
1873 if (cached_lhs && integer_onep (cached_lhs)) | |
1874 { | |
1875 if (is_gimple_assign (stmt)) | |
1876 { | |
1877 gimple_assign_set_rhs_code (stmt, EQ_EXPR); | |
1878 gimple_assign_set_rhs2 (stmt, rhs); | |
1879 gimple_set_modified (stmt, true); | |
1880 } | |
1881 else | |
1882 { | |
1883 gimple_set_modified (stmt, true); | |
1884 gimple_cond_set_code (as_a <gcond *> (stmt), EQ_EXPR); | |
1885 gimple_cond_set_rhs (as_a <gcond *> (stmt), rhs); | |
1886 gimple_set_modified (stmt, true); | |
1887 } | |
1888 } | |
1889 } | |
1890 } | |
1891 } | |
1892 | |
1893 /* Optimize the statement in block BB pointed to by iterator SI. | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1894 |
0 | 1895 We try to perform some simplistic global redundancy elimination and |
1896 constant propagation: | |
1897 | |
1898 1- To detect global redundancy, we keep track of expressions that have | |
1899 been computed in this block and its dominators. If we find that the | |
1900 same expression is computed more than once, we eliminate repeated | |
1901 computations by using the target of the first one. | |
1902 | |
1903 2- Constant values and copy assignments. This is used to do very | |
1904 simplistic constant and copy propagation. When a constant or copy | |
1905 assignment is found, we map the value on the RHS of the assignment to | |
111 | 1906 the variable in the LHS in the CONST_AND_COPIES table. |
1907 | |
1908 3- Very simple redundant store elimination is performed. | |
0 | 1909 |
111 | 1910 4- We can simpify a condition to a constant or from a relational |
1911 condition to an equality condition. */ | |
1912 | |
1913 edge | |
1914 dom_opt_dom_walker::optimize_stmt (basic_block bb, gimple_stmt_iterator si) | |
0 | 1915 { |
111 | 1916 gimple *stmt, *old_stmt; |
0 | 1917 bool may_optimize_p; |
1918 bool modified_p = false; | |
111 | 1919 bool was_noreturn; |
1920 edge retval = NULL; | |
0 | 1921 |
1922 old_stmt = stmt = gsi_stmt (si); | |
111 | 1923 was_noreturn = is_gimple_call (stmt) && gimple_call_noreturn_p (stmt); |
0 | 1924 |
1925 if (dump_file && (dump_flags & TDF_DETAILS)) | |
1926 { | |
1927 fprintf (dump_file, "Optimizing statement "); | |
1928 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); | |
1929 } | |
1930 | |
111 | 1931 update_stmt_if_modified (stmt); |
1932 opt_stats.num_stmts++; | |
1933 | |
0 | 1934 /* Const/copy propagate into USES, VUSES and the RHS of VDEFs. */ |
131 | 1935 cprop_into_stmt (stmt, evrp_range_analyzer.get_vr_values ()); |
0 | 1936 |
1937 /* If the statement has been modified with constant replacements, | |
1938 fold its RHS before checking for redundant computations. */ | |
1939 if (gimple_modified_p (stmt)) | |
1940 { | |
1941 tree rhs = NULL; | |
1942 | |
1943 /* Try to fold the statement making sure that STMT is kept | |
1944 up to date. */ | |
1945 if (fold_stmt (&si)) | |
1946 { | |
1947 stmt = gsi_stmt (si); | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1948 gimple_set_modified (stmt, true); |
0 | 1949 |
1950 if (dump_file && (dump_flags & TDF_DETAILS)) | |
1951 { | |
1952 fprintf (dump_file, " Folded to: "); | |
1953 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); | |
1954 } | |
1955 } | |
1956 | |
1957 /* We only need to consider cases that can yield a gimple operand. */ | |
1958 if (gimple_assign_single_p (stmt)) | |
1959 rhs = gimple_assign_rhs1 (stmt); | |
1960 else if (gimple_code (stmt) == GIMPLE_GOTO) | |
1961 rhs = gimple_goto_dest (stmt); | |
111 | 1962 else if (gswitch *swtch_stmt = dyn_cast <gswitch *> (stmt)) |
0 | 1963 /* This should never be an ADDR_EXPR. */ |
111 | 1964 rhs = gimple_switch_index (swtch_stmt); |
0 | 1965 |
1966 if (rhs && TREE_CODE (rhs) == ADDR_EXPR) | |
1967 recompute_tree_invariant_for_addr_expr (rhs); | |
1968 | |
1969 /* Indicate that maybe_clean_or_replace_eh_stmt needs to be called, | |
1970 even if fold_stmt updated the stmt already and thus cleared | |
1971 gimple_modified_p flag on it. */ | |
1972 modified_p = true; | |
1973 } | |
1974 | |
1975 /* Check for redundant computations. Do this optimization only | |
1976 for assignments that have no volatile ops and conditionals. */ | |
111 | 1977 may_optimize_p = (!gimple_has_side_effects (stmt) |
1978 && (is_gimple_assign (stmt) | |
0 | 1979 || (is_gimple_call (stmt) |
111 | 1980 && gimple_call_lhs (stmt) != NULL_TREE) |
0 | 1981 || gimple_code (stmt) == GIMPLE_COND |
1982 || gimple_code (stmt) == GIMPLE_SWITCH)); | |
1983 | |
1984 if (may_optimize_p) | |
1985 { | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1986 if (gimple_code (stmt) == GIMPLE_CALL) |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1987 { |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1988 /* Resolve __builtin_constant_p. If it hasn't been |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1989 folded to integer_one_node by now, it's fairly |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1990 certain that the value simply isn't constant. */ |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1991 tree callee = gimple_call_fndecl (stmt); |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1992 if (callee |
131 | 1993 && fndecl_built_in_p (callee, BUILT_IN_CONSTANT_P)) |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1994 { |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1995 propagate_tree_value_into_stmt (&si, integer_zero_node); |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1996 stmt = gsi_stmt (si); |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1997 } |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1998 } |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
1999 |
111 | 2000 if (gimple_code (stmt) == GIMPLE_COND) |
2001 { | |
2002 tree lhs = gimple_cond_lhs (stmt); | |
2003 tree rhs = gimple_cond_rhs (stmt); | |
2004 | |
2005 /* If the LHS has a range [0..1] and the RHS has a range ~[0..1], | |
2006 then this conditional is computable at compile time. We can just | |
2007 shove either 0 or 1 into the LHS, mark the statement as modified | |
2008 and all the right things will just happen below. | |
2009 | |
2010 Note this would apply to any case where LHS has a range | |
2011 narrower than its type implies and RHS is outside that | |
2012 narrower range. Future work. */ | |
2013 if (TREE_CODE (lhs) == SSA_NAME | |
2014 && ssa_name_has_boolean_range (lhs) | |
2015 && TREE_CODE (rhs) == INTEGER_CST | |
2016 && ! (integer_zerop (rhs) || integer_onep (rhs))) | |
2017 { | |
2018 gimple_cond_set_lhs (as_a <gcond *> (stmt), | |
2019 fold_convert (TREE_TYPE (lhs), | |
2020 integer_zero_node)); | |
2021 gimple_set_modified (stmt, true); | |
2022 } | |
131 | 2023 else if (TREE_CODE (lhs) == SSA_NAME) |
2024 { | |
2025 /* Exploiting EVRP data is not yet fully integrated into DOM | |
2026 but we need to do something for this case to avoid regressing | |
2027 udr4.f90 and new1.C which have unexecutable blocks with | |
2028 undefined behavior that get diagnosed if they're left in the | |
2029 IL because we've attached range information to new | |
2030 SSA_NAMES. */ | |
2031 update_stmt_if_modified (stmt); | |
2032 edge taken_edge = NULL; | |
2033 evrp_range_analyzer.vrp_visit_cond_stmt (as_a <gcond *> (stmt), | |
2034 &taken_edge); | |
2035 if (taken_edge) | |
2036 { | |
2037 if (taken_edge->flags & EDGE_TRUE_VALUE) | |
2038 gimple_cond_make_true (as_a <gcond *> (stmt)); | |
2039 else if (taken_edge->flags & EDGE_FALSE_VALUE) | |
2040 gimple_cond_make_false (as_a <gcond *> (stmt)); | |
2041 else | |
2042 gcc_unreachable (); | |
2043 gimple_set_modified (stmt, true); | |
2044 update_stmt (stmt); | |
2045 cfg_altered = true; | |
2046 return taken_edge; | |
2047 } | |
2048 } | |
111 | 2049 } |
2050 | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
2051 update_stmt_if_modified (stmt); |
111 | 2052 eliminate_redundant_computations (&si, m_const_and_copies, |
2053 m_avail_exprs_stack); | |
0 | 2054 stmt = gsi_stmt (si); |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2055 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2056 /* Perform simple redundant store elimination. */ |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2057 if (gimple_assign_single_p (stmt) |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2058 && TREE_CODE (gimple_assign_lhs (stmt)) != SSA_NAME) |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2059 { |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2060 tree lhs = gimple_assign_lhs (stmt); |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2061 tree rhs = gimple_assign_rhs1 (stmt); |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2062 tree cached_lhs; |
111 | 2063 gassign *new_stmt; |
2064 rhs = dom_valueize (rhs); | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2065 /* Build a new statement with the RHS and LHS exchanged. */ |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2066 if (TREE_CODE (rhs) == SSA_NAME) |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2067 { |
111 | 2068 gimple *defstmt = SSA_NAME_DEF_STMT (rhs); |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2069 new_stmt = gimple_build_assign (rhs, lhs); |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2070 SSA_NAME_DEF_STMT (rhs) = defstmt; |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2071 } |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2072 else |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2073 new_stmt = gimple_build_assign (rhs, lhs); |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2074 gimple_set_vuse (new_stmt, gimple_vuse (stmt)); |
111 | 2075 cached_lhs = m_avail_exprs_stack->lookup_avail_expr (new_stmt, false, |
2076 false); | |
2077 if (cached_lhs && operand_equal_p (rhs, cached_lhs, 0)) | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2078 { |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2079 basic_block bb = gimple_bb (stmt); |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2080 unlink_stmt_vdef (stmt); |
111 | 2081 if (gsi_remove (&si, true)) |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2082 { |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2083 bitmap_set_bit (need_eh_cleanup, bb->index); |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2084 if (dump_file && (dump_flags & TDF_DETAILS)) |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2085 fprintf (dump_file, " Flagged to clear EH edges.\n"); |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2086 } |
111 | 2087 release_defs (stmt); |
2088 return retval; | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2089 } |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
2090 } |
111 | 2091 |
2092 /* If this statement was not redundant, we may still be able to simplify | |
2093 it, which may in turn allow other part of DOM or other passes to do | |
2094 a better job. */ | |
2095 test_for_singularity (stmt, m_dummy_cond, m_avail_exprs_stack); | |
0 | 2096 } |
2097 | |
2098 /* Record any additional equivalences created by this statement. */ | |
2099 if (is_gimple_assign (stmt)) | |
111 | 2100 record_equivalences_from_stmt (stmt, may_optimize_p, m_avail_exprs_stack); |
0 | 2101 |
111 | 2102 /* If STMT is a COND_EXPR or SWITCH_EXPR and it was modified, then we may |
2103 know where it goes. */ | |
0 | 2104 if (gimple_modified_p (stmt) || modified_p) |
2105 { | |
2106 tree val = NULL; | |
2107 | |
2108 if (gimple_code (stmt) == GIMPLE_COND) | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
47
diff
changeset
|
2109 val = fold_binary_loc (gimple_location (stmt), |
111 | 2110 gimple_cond_code (stmt), boolean_type_node, |
2111 gimple_cond_lhs (stmt), | |
2112 gimple_cond_rhs (stmt)); | |
2113 else if (gswitch *swtch_stmt = dyn_cast <gswitch *> (stmt)) | |
2114 val = gimple_switch_index (swtch_stmt); | |
0 | 2115 |
111 | 2116 if (val && TREE_CODE (val) == INTEGER_CST) |
2117 { | |
2118 retval = find_taken_edge (bb, val); | |
2119 if (retval) | |
2120 { | |
2121 /* Fix the condition to be either true or false. */ | |
2122 if (gimple_code (stmt) == GIMPLE_COND) | |
2123 { | |
2124 if (integer_zerop (val)) | |
2125 gimple_cond_make_false (as_a <gcond *> (stmt)); | |
2126 else if (integer_onep (val)) | |
2127 gimple_cond_make_true (as_a <gcond *> (stmt)); | |
2128 else | |
2129 gcc_unreachable (); | |
2130 | |
2131 gimple_set_modified (stmt, true); | |
2132 } | |
2133 | |
2134 /* Further simplifications may be possible. */ | |
2135 cfg_altered = true; | |
2136 } | |
2137 } | |
2138 | |
2139 update_stmt_if_modified (stmt); | |
0 | 2140 |
2141 /* If we simplified a statement in such a way as to be shown that it | |
2142 cannot trap, update the eh information and the cfg to match. */ | |
2143 if (maybe_clean_or_replace_eh_stmt (old_stmt, stmt)) | |
2144 { | |
2145 bitmap_set_bit (need_eh_cleanup, bb->index); | |
2146 if (dump_file && (dump_flags & TDF_DETAILS)) | |
2147 fprintf (dump_file, " Flagged to clear EH edges.\n"); | |
2148 } | |
2149 | |
111 | 2150 if (!was_noreturn |
2151 && is_gimple_call (stmt) && gimple_call_noreturn_p (stmt)) | |
2152 need_noreturn_fixup.safe_push (stmt); | |
0 | 2153 } |
111 | 2154 return retval; |
0 | 2155 } |