1/* Routines for discovering and unpropagating edge equivalences.
2 Copyright (C) 2005-2017 Free Software Foundation, Inc.
3
4This file is part of GCC.
5
6GCC is free software; you can redistribute it and/or modify
7it under the terms of the GNU General Public License as published by
8the Free Software Foundation; either version 3, or (at your option)
9any later version.
10
11GCC is distributed in the hope that it will be useful,
12but WITHOUT ANY WARRANTY; without even the implied warranty of
13MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14GNU General Public License for more details.
15
16You should have received a copy of the GNU General Public License
17along 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 "backend.h"
24#include "tree.h"
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"
32#include "domwalk.h"
33#include "tree-hash-traits.h"
34#include "tree-ssa-live.h"
35#include "tree-ssa-coalesce.h"
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. */
40struct 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
50 EDGE_EQUIVALENCY structure hanging off the edge's AUX field.
51 The caller is responsible for freeing the AUX fields. */
52
53static void
54associate_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. */
60 FOR_EACH_BB_FN (bb, cfun)
61 {
62 gimple_stmt_iterator gsi = gsi_last_bb (bb);
63 gimple *stmt;
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)
97 && ssa_name_has_boolean_range (op0)
98 && is_gimple_min_invariant (op1)
99 && (integer_zerop (op1) || integer_onep (op1)))
100 {
101 tree true_val = constant_boolean_node (true, TREE_TYPE (op0));
102 tree false_val = constant_boolean_node (false,
103 TREE_TYPE (op0));
104 if (code == EQ_EXPR)
105 {
106 equivalency = XNEW (struct edge_equivalency);
107 equivalency->lhs = op0;
108 equivalency->rhs = (integer_zerop (op1)
109 ? false_val
110 : true_val);
111 true_edge->aux = equivalency;
112
113 equivalency = XNEW (struct edge_equivalency);
114 equivalency->lhs = op0;
115 equivalency->rhs = (integer_zerop (op1)
116 ? true_val
117 : false_val);
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)
125 ? true_val
126 : false_val);
127 true_edge->aux = equivalency;
128
129 equivalency = XNEW (struct edge_equivalency);
130 equivalency->lhs = op0;
131 equivalency->rhs = (integer_zerop (op1)
132 ? false_val
133 : true_val);
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. */
148 if (HONOR_SIGNED_ZEROS (op0)
149 && (TREE_CODE (op1) != REAL_CST
150 || real_equal (&dconst0, &TREE_REAL_CST (op1))))
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;
158 else
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 {
172 gswitch *switch_stmt = as_a <gswitch *> (stmt);
173 tree cond = gimple_switch_index (switch_stmt);
174
175 if (TREE_CODE (cond) == SSA_NAME
176 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (cond))
177 {
178 int i, n_labels = gimple_switch_num_labels (switch_stmt);
179 tree *info = XCNEWVEC (tree, last_basic_block_for_fn (cfun));
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 {
186 tree label = gimple_switch_label (switch_stmt, i);
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. */
199 for (i = 0; i < n_basic_blocks_for_fn (cfun); i++)
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;
214 find_edge (bb, BASIC_BLOCK_FOR_FN (cfun, i))->aux =
215 equivalency;
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. */
273struct 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. */
279 vec<tree> equivalences;
280};
281
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. */
285static hash_map<tree, auto_vec<tree> > *val_ssa_equiv;
286
287static void uncprop_into_successor_phis (basic_block);
288
289/* Remove the most recently recorded equivalency for VALUE. */
290
291static void
292remove_equivalence (tree value)
293{
294 val_ssa_equiv->get (value)->pop ();
295}
296
297/* Record EQUIVALENCE = VALUE into our hash table. */
298
299static void
300record_equiv (tree value, tree equivalence)
301{
302 val_ssa_equiv->get_or_insert (value).safe_push (equivalence);
303}
304
305class uncprop_dom_walker : public dom_walker
306{
307public:
308 uncprop_dom_walker (cdi_direction direction) : dom_walker (direction) {}
309
310 virtual edge before_dom_children (basic_block);
311 virtual void after_dom_children (basic_block);
312
313private:
314
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};
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
326void
327uncprop_dom_walker::after_dom_children (basic_block bb ATTRIBUTE_UNUSED)
328{
329 /* Pop the topmost value off the equiv stack. */
330 tree value = m_equiv_stack.pop ();
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
340static void
341uncprop_into_successor_phis (basic_block bb)
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. */
356 if (gimple_seq_empty_p (phis))
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 {
369 gimple *phi = gsi_stmt (gsi);
370 tree arg = PHI_ARG_DEF (phi, e->dest_idx);
371 tree res = PHI_RESULT (phi);
372
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. */
376 if (!is_gimple_min_invariant (arg)
377 && gimple_can_coalesce_p (arg, res))
378 continue;
379
380 /* Lookup this argument's value in the hash table. */
381 vec<tree> *equivalences = val_ssa_equiv->get (arg);
382 if (equivalences)
383 {
384 /* Walk every equivalence with the same value. If we find
385 one that can potentially coalesce with the PHI rsult,
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. */
389 for (int j = equivalences->length () - 1; j >= 0; j--)
390 {
391 tree equiv = (*equivalences)[j];
392
393 if (gimple_can_coalesce_p (equiv, res))
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
411edge
412uncprop_dom_walker::before_dom_children (basic_block bb)
413{
414 basic_block parent;
415 bool recorded = false;
416
417 /* If this block is dominated by a single incoming edge and that edge
418 has an equivalency, then record the equivalency and push the
419 VALUE onto EQUIV_STACK. Else push a NULL entry on EQUIV_STACK. */
420 parent = get_immediate_dominator (CDI_DOMINATORS, bb);
421 if (parent)
422 {
423 edge e = single_pred_edge_ignoring_loop_edges (bb, false);
424
425 if (e && e->src == parent && e->aux)
426 {
427 struct edge_equivalency *equiv = (struct edge_equivalency *) e->aux;
428
429 record_equiv (equiv->rhs, equiv->lhs);
430 m_equiv_stack.safe_push (equiv->rhs);
431 recorded = true;
432 }
433 }
434
435 if (!recorded)
436 m_equiv_stack.safe_push (NULL_TREE);
437
438 uncprop_into_successor_phis (bb);
439 return NULL;
440}
441
442namespace {
443
444const pass_data pass_data_uncprop =
445{
446 GIMPLE_PASS, /* type */
447 "uncprop", /* name */
448 OPTGROUP_NONE, /* optinfo_flags */
449 TV_TREE_SSA_UNCPROP, /* tv_id */
450 ( PROP_cfg | PROP_ssa ), /* properties_required */
451 0, /* properties_provided */
452 0, /* properties_destroyed */
453 0, /* todo_flags_start */
454 0, /* todo_flags_finish */
455};
456
457class pass_uncprop : public gimple_opt_pass
458{
459public:
460 pass_uncprop (gcc::context *ctxt)
461 : gimple_opt_pass (pass_data_uncprop, ctxt)
462 {}
463
464 /* opt_pass methods: */
465 opt_pass * clone () { return new pass_uncprop (m_ctxt); }
466 virtual bool gate (function *) { return flag_tree_dom != 0; }
467 virtual unsigned int execute (function *);
468
469}; // class pass_uncprop
470
471unsigned int
472pass_uncprop::execute (function *fun)
473{
474 basic_block bb;
475
476 associate_equivalences_with_edges ();
477
478 /* Create our global data structures. */
479 val_ssa_equiv = new hash_map<tree, auto_vec<tree> > (1024);
480
481 /* We're going to do a dominator walk, so ensure that we have
482 dominance information. */
483 calculate_dominance_info (CDI_DOMINATORS);
484
485 /* Recursively walk the dominator tree undoing unprofitable
486 constant/copy propagations. */
487 uncprop_dom_walker (CDI_DOMINATORS).walk (fun->cfg->x_entry_block_ptr);
488
489 /* we just need to empty elements out of the hash table, and cleanup the
490 AUX field on the edges. */
491 delete val_ssa_equiv;
492 val_ssa_equiv = NULL;
493 FOR_EACH_BB_FN (bb, fun)
494 {
495 edge e;
496 edge_iterator ei;
497
498 FOR_EACH_EDGE (e, ei, bb->succs)
499 {
500 if (e->aux)
501 {
502 free (e->aux);
503 e->aux = NULL;
504 }
505 }
506 }
507 return 0;
508}
509
510} // anon namespace
511
512gimple_opt_pass *
513make_pass_uncprop (gcc::context *ctxt)
514{
515 return new pass_uncprop (ctxt);
516}
517