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