Mercurial > hg > CbC > CbC_gcc
annotate gcc/tree-ssa-uncprop.c @ 128:fe568345ddd5
fix CbC-example
author | mir3636 |
---|---|
date | Wed, 11 Apr 2018 19:32:28 +0900 |
parents | 04ced10e8804 |
children | 84e7813d76e9 |
rev | line source |
---|---|
0 | 1 /* Routines for discovering and unpropagating edge equivalences. |
111 | 2 Copyright (C) 2005-2017 Free Software Foundation, Inc. |
0 | 3 |
4 This file is part of GCC. | |
5 | |
6 GCC is free software; you can redistribute it and/or modify | |
7 it under the terms of the GNU General Public License as published by | |
8 the Free Software Foundation; either version 3, or (at your option) | |
9 any later version. | |
10 | |
11 GCC is distributed in the hope that it will be useful, | |
12 but WITHOUT ANY WARRANTY; without even the implied warranty of | |
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
14 GNU General Public License for more details. | |
15 | |
16 You should have received a copy of the GNU General Public License | |
17 along with GCC; see the file COPYING3. If not see | |
18 <http://www.gnu.org/licenses/>. */ | |
19 | |
20 #include "config.h" | |
21 #include "system.h" | |
22 #include "coretypes.h" | |
111 | 23 #include "backend.h" |
0 | 24 #include "tree.h" |
111 | 25 #include "gimple.h" |
26 #include "tree-pass.h" | |
27 #include "ssa.h" | |
28 #include "fold-const.h" | |
29 #include "cfganal.h" | |
30 #include "gimple-iterator.h" | |
31 #include "tree-cfg.h" | |
0 | 32 #include "domwalk.h" |
111 | 33 #include "tree-hash-traits.h" |
34 #include "tree-ssa-live.h" | |
35 #include "tree-ssa-coalesce.h" | |
0 | 36 |
37 /* The basic structure describing an equivalency created by traversing | |
38 an edge. Traversing the edge effectively means that we can assume | |
39 that we've seen an assignment LHS = RHS. */ | |
40 struct edge_equivalency | |
41 { | |
42 tree rhs; | |
43 tree lhs; | |
44 }; | |
45 | |
46 /* This routine finds and records edge equivalences for every edge | |
47 in the CFG. | |
48 | |
49 When complete, each edge that creates an equivalency will have an | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
50 EDGE_EQUIVALENCY structure hanging off the edge's AUX field. |
0 | 51 The caller is responsible for freeing the AUX fields. */ |
52 | |
53 static void | |
54 associate_equivalences_with_edges (void) | |
55 { | |
56 basic_block bb; | |
57 | |
58 /* Walk over each block. If the block ends with a control statement, | |
59 then it might create a useful equivalence. */ | |
111 | 60 FOR_EACH_BB_FN (bb, cfun) |
0 | 61 { |
62 gimple_stmt_iterator gsi = gsi_last_bb (bb); | |
111 | 63 gimple *stmt; |
0 | 64 |
65 /* If the block does not end with a COND_EXPR or SWITCH_EXPR | |
66 then there is nothing to do. */ | |
67 if (gsi_end_p (gsi)) | |
68 continue; | |
69 | |
70 stmt = gsi_stmt (gsi); | |
71 | |
72 if (!stmt) | |
73 continue; | |
74 | |
75 /* A COND_EXPR may create an equivalency in a variety of different | |
76 ways. */ | |
77 if (gimple_code (stmt) == GIMPLE_COND) | |
78 { | |
79 edge true_edge; | |
80 edge false_edge; | |
81 struct edge_equivalency *equivalency; | |
82 enum tree_code code = gimple_cond_code (stmt); | |
83 | |
84 extract_true_false_edges_from_block (bb, &true_edge, &false_edge); | |
85 | |
86 /* Equality tests may create one or two equivalences. */ | |
87 if (code == EQ_EXPR || code == NE_EXPR) | |
88 { | |
89 tree op0 = gimple_cond_lhs (stmt); | |
90 tree op1 = gimple_cond_rhs (stmt); | |
91 | |
92 /* Special case comparing booleans against a constant as we | |
93 know the value of OP0 on both arms of the branch. i.e., we | |
94 can record an equivalence for OP0 rather than COND. */ | |
95 if (TREE_CODE (op0) == SSA_NAME | |
96 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0) | |
111 | 97 && ssa_name_has_boolean_range (op0) |
98 && is_gimple_min_invariant (op1) | |
99 && (integer_zerop (op1) || integer_onep (op1))) | |
0 | 100 { |
111 | 101 tree true_val = constant_boolean_node (true, TREE_TYPE (op0)); |
102 tree false_val = constant_boolean_node (false, | |
103 TREE_TYPE (op0)); | |
0 | 104 if (code == EQ_EXPR) |
105 { | |
106 equivalency = XNEW (struct edge_equivalency); | |
107 equivalency->lhs = op0; | |
108 equivalency->rhs = (integer_zerop (op1) | |
111 | 109 ? false_val |
110 : true_val); | |
0 | 111 true_edge->aux = equivalency; |
112 | |
113 equivalency = XNEW (struct edge_equivalency); | |
114 equivalency->lhs = op0; | |
115 equivalency->rhs = (integer_zerop (op1) | |
111 | 116 ? true_val |
117 : false_val); | |
0 | 118 false_edge->aux = equivalency; |
119 } | |
120 else | |
121 { | |
122 equivalency = XNEW (struct edge_equivalency); | |
123 equivalency->lhs = op0; | |
124 equivalency->rhs = (integer_zerop (op1) | |
111 | 125 ? true_val |
126 : false_val); | |
0 | 127 true_edge->aux = equivalency; |
128 | |
129 equivalency = XNEW (struct edge_equivalency); | |
130 equivalency->lhs = op0; | |
131 equivalency->rhs = (integer_zerop (op1) | |
111 | 132 ? false_val |
133 : true_val); | |
0 | 134 false_edge->aux = equivalency; |
135 } | |
136 } | |
137 | |
138 else if (TREE_CODE (op0) == SSA_NAME | |
139 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0) | |
140 && (is_gimple_min_invariant (op1) | |
141 || (TREE_CODE (op1) == SSA_NAME | |
142 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op1)))) | |
143 { | |
144 /* For IEEE, -0.0 == 0.0, so we don't necessarily know | |
145 the sign of a variable compared against zero. If | |
146 we're honoring signed zeros, then we cannot record | |
147 this value unless we know that the value is nonzero. */ | |
111 | 148 if (HONOR_SIGNED_ZEROS (op0) |
0 | 149 && (TREE_CODE (op1) != REAL_CST |
111 | 150 || real_equal (&dconst0, &TREE_REAL_CST (op1)))) |
0 | 151 continue; |
152 | |
153 equivalency = XNEW (struct edge_equivalency); | |
154 equivalency->lhs = op0; | |
155 equivalency->rhs = op1; | |
156 if (code == EQ_EXPR) | |
157 true_edge->aux = equivalency; | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
158 else |
0 | 159 false_edge->aux = equivalency; |
160 | |
161 } | |
162 } | |
163 | |
164 /* ??? TRUTH_NOT_EXPR can create an equivalence too. */ | |
165 } | |
166 | |
167 /* For a SWITCH_EXPR, a case label which represents a single | |
168 value and which is the only case label which reaches the | |
169 target block creates an equivalence. */ | |
170 else if (gimple_code (stmt) == GIMPLE_SWITCH) | |
171 { | |
111 | 172 gswitch *switch_stmt = as_a <gswitch *> (stmt); |
173 tree cond = gimple_switch_index (switch_stmt); | |
0 | 174 |
175 if (TREE_CODE (cond) == SSA_NAME | |
176 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (cond)) | |
177 { | |
111 | 178 int i, n_labels = gimple_switch_num_labels (switch_stmt); |
179 tree *info = XCNEWVEC (tree, last_basic_block_for_fn (cfun)); | |
0 | 180 |
181 /* Walk over the case label vector. Record blocks | |
182 which are reached by a single case label which represents | |
183 a single value. */ | |
184 for (i = 0; i < n_labels; i++) | |
185 { | |
111 | 186 tree label = gimple_switch_label (switch_stmt, i); |
0 | 187 basic_block bb = label_to_block (CASE_LABEL (label)); |
188 | |
189 if (CASE_HIGH (label) | |
190 || !CASE_LOW (label) | |
191 || info[bb->index]) | |
192 info[bb->index] = error_mark_node; | |
193 else | |
194 info[bb->index] = label; | |
195 } | |
196 | |
197 /* Now walk over the blocks to determine which ones were | |
198 marked as being reached by a useful case label. */ | |
111 | 199 for (i = 0; i < n_basic_blocks_for_fn (cfun); i++) |
0 | 200 { |
201 tree node = info[i]; | |
202 | |
203 if (node != NULL | |
204 && node != error_mark_node) | |
205 { | |
206 tree x = fold_convert (TREE_TYPE (cond), CASE_LOW (node)); | |
207 struct edge_equivalency *equivalency; | |
208 | |
209 /* Record an equivalency on the edge from BB to basic | |
210 block I. */ | |
211 equivalency = XNEW (struct edge_equivalency); | |
212 equivalency->rhs = x; | |
213 equivalency->lhs = cond; | |
111 | 214 find_edge (bb, BASIC_BLOCK_FOR_FN (cfun, i))->aux = |
215 equivalency; | |
0 | 216 } |
217 } | |
218 free (info); | |
219 } | |
220 } | |
221 | |
222 } | |
223 } | |
224 | |
225 | |
226 /* Translating out of SSA sometimes requires inserting copies and | |
227 constant initializations on edges to eliminate PHI nodes. | |
228 | |
229 In some cases those copies and constant initializations are | |
230 redundant because the target already has the value on the | |
231 RHS of the assignment. | |
232 | |
233 We previously tried to catch these cases after translating | |
234 out of SSA form. However, that code often missed cases. Worse | |
235 yet, the cases it missed were also often missed by the RTL | |
236 optimizers. Thus the resulting code had redundant instructions. | |
237 | |
238 This pass attempts to detect these situations before translating | |
239 out of SSA form. | |
240 | |
241 The key concept that this pass is built upon is that these | |
242 redundant copies and constant initializations often occur | |
243 due to constant/copy propagating equivalences resulting from | |
244 COND_EXPRs and SWITCH_EXPRs. | |
245 | |
246 We want to do those propagations as they can sometimes allow | |
247 the SSA optimizers to do a better job. However, in the cases | |
248 where such propagations do not result in further optimization, | |
249 we would like to "undo" the propagation to avoid the redundant | |
250 copies and constant initializations. | |
251 | |
252 This pass works by first associating equivalences with edges in | |
253 the CFG. For example, the edge leading from a SWITCH_EXPR to | |
254 its associated CASE_LABEL will have an equivalency between | |
255 SWITCH_COND and the value in the case label. | |
256 | |
257 Once we have found the edge equivalences, we proceed to walk | |
258 the CFG in dominator order. As we traverse edges we record | |
259 equivalences associated with those edges we traverse. | |
260 | |
261 When we encounter a PHI node, we walk its arguments to see if we | |
262 have an equivalence for the PHI argument. If so, then we replace | |
263 the argument. | |
264 | |
265 Equivalences are looked up based on their value (think of it as | |
266 the RHS of an assignment). A value may be an SSA_NAME or an | |
267 invariant. We may have several SSA_NAMEs with the same value, | |
268 so with each value we have a list of SSA_NAMEs that have the | |
269 same value. */ | |
270 | |
271 | |
272 /* Main structure for recording equivalences into our hash table. */ | |
273 struct equiv_hash_elt | |
274 { | |
275 /* The value/key of this entry. */ | |
276 tree value; | |
277 | |
278 /* List of SSA_NAMEs which have the same value/key. */ | |
111 | 279 vec<tree> equivalences; |
0 | 280 }; |
281 | |
111 | 282 /* Global hash table implementing a mapping from invariant values |
283 to a list of SSA_NAMEs which have the same value. We might be | |
284 able to reuse tree-vn for this code. */ | |
285 static hash_map<tree, auto_vec<tree> > *val_ssa_equiv; | |
0 | 286 |
111 | 287 static void uncprop_into_successor_phis (basic_block); |
0 | 288 |
289 /* Remove the most recently recorded equivalency for VALUE. */ | |
290 | |
291 static void | |
292 remove_equivalence (tree value) | |
293 { | |
111 | 294 val_ssa_equiv->get (value)->pop (); |
0 | 295 } |
296 | |
297 /* Record EQUIVALENCE = VALUE into our hash table. */ | |
298 | |
299 static void | |
300 record_equiv (tree value, tree equivalence) | |
301 { | |
111 | 302 val_ssa_equiv->get_or_insert (value).safe_push (equivalence); |
0 | 303 } |
304 | |
111 | 305 class uncprop_dom_walker : public dom_walker |
0 | 306 { |
111 | 307 public: |
308 uncprop_dom_walker (cdi_direction direction) : dom_walker (direction) {} | |
0 | 309 |
111 | 310 virtual edge before_dom_children (basic_block); |
311 virtual void after_dom_children (basic_block); | |
0 | 312 |
111 | 313 private: |
0 | 314 |
111 | 315 /* As we enter each block we record the value for any edge equivalency |
316 leading to this block. If no such edge equivalency exists, then we | |
317 record NULL. These equivalences are live until we leave the dominator | |
318 subtree rooted at the block where we record the equivalency. */ | |
319 auto_vec<tree, 2> m_equiv_stack; | |
320 }; | |
0 | 321 |
322 /* We have finished processing the dominator children of BB, perform | |
323 any finalization actions in preparation for leaving this node in | |
324 the dominator tree. */ | |
325 | |
111 | 326 void |
327 uncprop_dom_walker::after_dom_children (basic_block bb ATTRIBUTE_UNUSED) | |
0 | 328 { |
329 /* Pop the topmost value off the equiv stack. */ | |
111 | 330 tree value = m_equiv_stack.pop (); |
0 | 331 |
332 /* If that value was non-null, then pop the topmost equivalency off | |
333 its equivalency stack. */ | |
334 if (value != NULL) | |
335 remove_equivalence (value); | |
336 } | |
337 | |
338 /* Unpropagate values from PHI nodes in successor blocks of BB. */ | |
339 | |
340 static void | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
341 uncprop_into_successor_phis (basic_block bb) |
0 | 342 { |
343 edge e; | |
344 edge_iterator ei; | |
345 | |
346 /* For each successor edge, first temporarily record any equivalence | |
347 on that edge. Then unpropagate values in any PHI nodes at the | |
348 destination of the edge. Then remove the temporary equivalence. */ | |
349 FOR_EACH_EDGE (e, ei, bb->succs) | |
350 { | |
351 gimple_seq phis = phi_nodes (e->dest); | |
352 gimple_stmt_iterator gsi; | |
353 | |
354 /* If there are no PHI nodes in this destination, then there is | |
355 no sense in recording any equivalences. */ | |
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
356 if (gimple_seq_empty_p (phis)) |
0 | 357 continue; |
358 | |
359 /* Record any equivalency associated with E. */ | |
360 if (e->aux) | |
361 { | |
362 struct edge_equivalency *equiv = (struct edge_equivalency *) e->aux; | |
363 record_equiv (equiv->rhs, equiv->lhs); | |
364 } | |
365 | |
366 /* Walk over the PHI nodes, unpropagating values. */ | |
367 for (gsi = gsi_start (phis) ; !gsi_end_p (gsi); gsi_next (&gsi)) | |
368 { | |
111 | 369 gimple *phi = gsi_stmt (gsi); |
0 | 370 tree arg = PHI_ARG_DEF (phi, e->dest_idx); |
111 | 371 tree res = PHI_RESULT (phi); |
0 | 372 |
111 | 373 /* If the argument is not an invariant and can be potentially |
374 coalesced with the result, then there's no point in | |
375 un-propagating the argument. */ | |
0 | 376 if (!is_gimple_min_invariant (arg) |
111 | 377 && gimple_can_coalesce_p (arg, res)) |
0 | 378 continue; |
379 | |
380 /* Lookup this argument's value in the hash table. */ | |
111 | 381 vec<tree> *equivalences = val_ssa_equiv->get (arg); |
382 if (equivalences) | |
0 | 383 { |
384 /* Walk every equivalence with the same value. If we find | |
111 | 385 one that can potentially coalesce with the PHI rsult, |
0 | 386 then replace the value in the argument with its equivalent |
387 SSA_NAME. Use the most recent equivalence as hopefully | |
388 that results in shortest lifetimes. */ | |
111 | 389 for (int j = equivalences->length () - 1; j >= 0; j--) |
0 | 390 { |
111 | 391 tree equiv = (*equivalences)[j]; |
0 | 392 |
111 | 393 if (gimple_can_coalesce_p (equiv, res)) |
0 | 394 { |
395 SET_PHI_ARG_DEF (phi, e->dest_idx, equiv); | |
396 break; | |
397 } | |
398 } | |
399 } | |
400 } | |
401 | |
402 /* If we had an equivalence associated with this edge, remove it. */ | |
403 if (e->aux) | |
404 { | |
405 struct edge_equivalency *equiv = (struct edge_equivalency *) e->aux; | |
406 remove_equivalence (equiv->rhs); | |
407 } | |
408 } | |
409 } | |
410 | |
411 /* Ignoring loop backedges, if BB has precisely one incoming edge then | |
412 return that edge. Otherwise return NULL. */ | |
413 static edge | |
414 single_incoming_edge_ignoring_loop_edges (basic_block bb) | |
415 { | |
416 edge retval = NULL; | |
417 edge e; | |
418 edge_iterator ei; | |
419 | |
420 FOR_EACH_EDGE (e, ei, bb->preds) | |
421 { | |
422 /* A loop back edge can be identified by the destination of | |
423 the edge dominating the source of the edge. */ | |
424 if (dominated_by_p (CDI_DOMINATORS, e->src, e->dest)) | |
425 continue; | |
426 | |
427 /* If we have already seen a non-loop edge, then we must have | |
428 multiple incoming non-loop edges and thus we return NULL. */ | |
429 if (retval) | |
430 return NULL; | |
431 | |
432 /* This is the first non-loop incoming edge we have found. Record | |
433 it. */ | |
434 retval = e; | |
435 } | |
436 | |
437 return retval; | |
438 } | |
439 | |
111 | 440 edge |
441 uncprop_dom_walker::before_dom_children (basic_block bb) | |
0 | 442 { |
443 basic_block parent; | |
444 edge e; | |
445 bool recorded = false; | |
446 | |
447 /* If this block is dominated by a single incoming edge and that edge | |
448 has an equivalency, then record the equivalency and push the | |
449 VALUE onto EQUIV_STACK. Else push a NULL entry on EQUIV_STACK. */ | |
450 parent = get_immediate_dominator (CDI_DOMINATORS, bb); | |
451 if (parent) | |
452 { | |
453 e = single_incoming_edge_ignoring_loop_edges (bb); | |
454 | |
455 if (e && e->src == parent && e->aux) | |
456 { | |
457 struct edge_equivalency *equiv = (struct edge_equivalency *) e->aux; | |
458 | |
459 record_equiv (equiv->rhs, equiv->lhs); | |
111 | 460 m_equiv_stack.safe_push (equiv->rhs); |
0 | 461 recorded = true; |
462 } | |
463 } | |
464 | |
465 if (!recorded) | |
111 | 466 m_equiv_stack.safe_push (NULL_TREE); |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
467 |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
468 uncprop_into_successor_phis (bb); |
111 | 469 return NULL; |
0 | 470 } |
471 | |
111 | 472 namespace { |
473 | |
474 const pass_data pass_data_uncprop = | |
0 | 475 { |
111 | 476 GIMPLE_PASS, /* type */ |
477 "uncprop", /* name */ | |
478 OPTGROUP_NONE, /* optinfo_flags */ | |
479 TV_TREE_SSA_UNCPROP, /* tv_id */ | |
480 ( PROP_cfg | PROP_ssa ), /* properties_required */ | |
481 0, /* properties_provided */ | |
482 0, /* properties_destroyed */ | |
483 0, /* todo_flags_start */ | |
484 0, /* todo_flags_finish */ | |
0 | 485 }; |
486 | |
111 | 487 class pass_uncprop : public gimple_opt_pass |
488 { | |
489 public: | |
490 pass_uncprop (gcc::context *ctxt) | |
491 : gimple_opt_pass (pass_data_uncprop, ctxt) | |
492 {} | |
493 | |
494 /* opt_pass methods: */ | |
495 opt_pass * clone () { return new pass_uncprop (m_ctxt); } | |
496 virtual bool gate (function *) { return flag_tree_dom != 0; } | |
497 virtual unsigned int execute (function *); | |
498 | |
499 }; // class pass_uncprop | |
500 | |
501 unsigned int | |
502 pass_uncprop::execute (function *fun) | |
503 { | |
504 basic_block bb; | |
505 | |
506 associate_equivalences_with_edges (); | |
507 | |
508 /* Create our global data structures. */ | |
509 val_ssa_equiv = new hash_map<tree, auto_vec<tree> > (1024); | |
510 | |
511 /* We're going to do a dominator walk, so ensure that we have | |
512 dominance information. */ | |
513 calculate_dominance_info (CDI_DOMINATORS); | |
514 | |
515 /* Recursively walk the dominator tree undoing unprofitable | |
516 constant/copy propagations. */ | |
517 uncprop_dom_walker (CDI_DOMINATORS).walk (fun->cfg->x_entry_block_ptr); | |
518 | |
519 /* we just need to empty elements out of the hash table, and cleanup the | |
520 AUX field on the edges. */ | |
521 delete val_ssa_equiv; | |
522 val_ssa_equiv = NULL; | |
523 FOR_EACH_BB_FN (bb, fun) | |
524 { | |
525 edge e; | |
526 edge_iterator ei; | |
527 | |
528 FOR_EACH_EDGE (e, ei, bb->succs) | |
529 { | |
530 if (e->aux) | |
531 { | |
532 free (e->aux); | |
533 e->aux = NULL; | |
534 } | |
535 } | |
536 } | |
537 return 0; | |
538 } | |
539 | |
540 } // anon namespace | |
541 | |
542 gimple_opt_pass * | |
543 make_pass_uncprop (gcc::context *ctxt) | |
544 { | |
545 return new pass_uncprop (ctxt); | |
546 } |