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