Initial checkin of GCC 4.9.0 from trunk (r208799).

Change-Id: I48a3c08bb98542aa215912a75f03c0890e497dba

1 files changed, 627 insertions, 0 deletions

diff --git a/gcc-4.9/gcc/tree-ssa-uncprop.c b/gcc-4.9/gcc/tree-ssa-uncprop.c
new file mode 100644
index 000000000..a43dd1a84
--- /dev/null
+++ b/gcc-4.9/gcc/tree-ssa-uncprop.c
@@ -0,0 +1,627 @@
+/* Routines for discovering and unpropagating edge equivalences.
+   Copyright (C) 2005-2014 Free Software Foundation, Inc.
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify
+it under the terms of the GNU General Public License as published by
+the Free Software Foundation; either version 3, or (at your option)
+any later version.
+
+GCC is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3.  If not see
+<http://www.gnu.org/licenses/>.  */
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "tm.h"
+#include "tree.h"
+#include "stor-layout.h"
+#include "flags.h"
+#include "tm_p.h"
+#include "basic-block.h"
+#include "function.h"
+#include "hash-table.h"
+#include "tree-ssa-alias.h"
+#include "internal-fn.h"
+#include "gimple-expr.h"
+#include "is-a.h"
+#include "gimple.h"
+#include "gimple-iterator.h"
+#include "gimple-ssa.h"
+#include "tree-cfg.h"
+#include "tree-phinodes.h"
+#include "ssa-iterators.h"
+#include "domwalk.h"
+#include "tree-pass.h"
+#include "tree-ssa-propagate.h"
+
+/* The basic structure describing an equivalency created by traversing
+   an edge.  Traversing the edge effectively means that we can assume
+   that we've seen an assignment LHS = RHS.  */
+struct edge_equivalency
+{
+  tree rhs;
+  tree lhs;
+};
+
+/* This routine finds and records edge equivalences for every edge
+   in the CFG.
+
+   When complete, each edge that creates an equivalency will have an
+   EDGE_EQUIVALENCY structure hanging off the edge's AUX field.
+   The caller is responsible for freeing the AUX fields.  */
+
+static void
+associate_equivalences_with_edges (void)
+{
+  basic_block bb;
+
+  /* Walk over each block.  If the block ends with a control statement,
+     then it might create a useful equivalence.  */
+  FOR_EACH_BB_FN (bb, cfun)
+    {
+      gimple_stmt_iterator gsi = gsi_last_bb (bb);
+      gimple stmt;
+
+      /* If the block does not end with a COND_EXPR or SWITCH_EXPR
+	 then there is nothing to do.  */
+      if (gsi_end_p (gsi))
+	continue;
+
+      stmt = gsi_stmt (gsi);
+
+      if (!stmt)
+	continue;
+
+      /* A COND_EXPR may create an equivalency in a variety of different
+	 ways.  */
+      if (gimple_code (stmt) == GIMPLE_COND)
+	{
+	  edge true_edge;
+	  edge false_edge;
+	  struct edge_equivalency *equivalency;
+	  enum tree_code code = gimple_cond_code (stmt);
+
+	  extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
+
+	  /* Equality tests may create one or two equivalences.  */
+	  if (code == EQ_EXPR || code == NE_EXPR)
+	    {
+	      tree op0 = gimple_cond_lhs (stmt);
+	      tree op1 = gimple_cond_rhs (stmt);
+
+	      /* Special case comparing booleans against a constant as we
+		 know the value of OP0 on both arms of the branch.  i.e., we
+		 can record an equivalence for OP0 rather than COND.  */
+	      if (TREE_CODE (op0) == SSA_NAME
+		  && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0)
+		  && TREE_CODE (TREE_TYPE (op0)) == BOOLEAN_TYPE
+		  && is_gimple_min_invariant (op1))
+		{
+		  if (code == EQ_EXPR)
+		    {
+		      equivalency = XNEW (struct edge_equivalency);
+		      equivalency->lhs = op0;
+		      equivalency->rhs = (integer_zerop (op1)
+					  ? boolean_false_node
+					  : boolean_true_node);
+		      true_edge->aux = equivalency;
+
+		      equivalency = XNEW (struct edge_equivalency);
+		      equivalency->lhs = op0;
+		      equivalency->rhs = (integer_zerop (op1)
+					  ? boolean_true_node
+					  : boolean_false_node);
+		      false_edge->aux = equivalency;
+		    }
+		  else
+		    {
+		      equivalency = XNEW (struct edge_equivalency);
+		      equivalency->lhs = op0;
+		      equivalency->rhs = (integer_zerop (op1)
+					  ? boolean_true_node
+					  : boolean_false_node);
+		      true_edge->aux = equivalency;
+
+		      equivalency = XNEW (struct edge_equivalency);
+		      equivalency->lhs = op0;
+		      equivalency->rhs = (integer_zerop (op1)
+					  ? boolean_false_node
+					  : boolean_true_node);
+		      false_edge->aux = equivalency;
+		    }
+		}
+
+	      else if (TREE_CODE (op0) == SSA_NAME
+		       && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0)
+		       && (is_gimple_min_invariant (op1)
+			   || (TREE_CODE (op1) == SSA_NAME
+			       && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op1))))
+		{
+		  /* For IEEE, -0.0 == 0.0, so we don't necessarily know
+		     the sign of a variable compared against zero.  If
+		     we're honoring signed zeros, then we cannot record
+		     this value unless we know that the value is nonzero.  */
+		  if (HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (op0)))
+		      && (TREE_CODE (op1) != REAL_CST
+			  || REAL_VALUES_EQUAL (dconst0, TREE_REAL_CST (op1))))
+		    continue;
+
+		  equivalency = XNEW (struct edge_equivalency);
+		  equivalency->lhs = op0;
+		  equivalency->rhs = op1;
+		  if (code == EQ_EXPR)
+		    true_edge->aux = equivalency;
+		  else
+		    false_edge->aux = equivalency;
+
+		}
+	    }
+
+	  /* ??? TRUTH_NOT_EXPR can create an equivalence too.  */
+	}
+
+      /* For a SWITCH_EXPR, a case label which represents a single
+	 value and which is the only case label which reaches the
+	 target block creates an equivalence.  */
+      else if (gimple_code (stmt) == GIMPLE_SWITCH)
+	{
+	  tree cond = gimple_switch_index (stmt);
+
+	  if (TREE_CODE (cond) == SSA_NAME
+	      && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (cond))
+	    {
+	      int i, n_labels = gimple_switch_num_labels (stmt);
+	      tree *info = XCNEWVEC (tree, last_basic_block_for_fn (cfun));
+
+	      /* Walk over the case label vector.  Record blocks
+		 which are reached by a single case label which represents
+		 a single value.  */
+	      for (i = 0; i < n_labels; i++)
+		{
+		  tree label = gimple_switch_label (stmt, i);
+		  basic_block bb = label_to_block (CASE_LABEL (label));
+
+		  if (CASE_HIGH (label)
+		      || !CASE_LOW (label)
+		      || info[bb->index])
+		    info[bb->index] = error_mark_node;
+		  else
+		    info[bb->index] = label;
+		}
+
+	      /* Now walk over the blocks to determine which ones were
+		 marked as being reached by a useful case label.  */
+	      for (i = 0; i < n_basic_blocks_for_fn (cfun); i++)
+		{
+		  tree node = info[i];
+
+		  if (node != NULL
+		      && node != error_mark_node)
+		    {
+		      tree x = fold_convert (TREE_TYPE (cond), CASE_LOW (node));
+		      struct edge_equivalency *equivalency;
+
+		      /* Record an equivalency on the edge from BB to basic
+			 block I.  */
+		      equivalency = XNEW (struct edge_equivalency);
+		      equivalency->rhs = x;
+		      equivalency->lhs = cond;
+		      find_edge (bb, BASIC_BLOCK_FOR_FN (cfun, i))->aux =
+			equivalency;
+		    }
+		}
+	      free (info);
+	    }
+	}
+
+    }
+}
+
+
+/* Translating out of SSA sometimes requires inserting copies and
+   constant initializations on edges to eliminate PHI nodes.
+
+   In some cases those copies and constant initializations are
+   redundant because the target already has the value on the
+   RHS of the assignment.
+
+   We previously tried to catch these cases after translating
+   out of SSA form.  However, that code often missed cases.  Worse
+   yet, the cases it missed were also often missed by the RTL
+   optimizers.  Thus the resulting code had redundant instructions.
+
+   This pass attempts to detect these situations before translating
+   out of SSA form.
+
+   The key concept that this pass is built upon is that these
+   redundant copies and constant initializations often occur
+   due to constant/copy propagating equivalences resulting from
+   COND_EXPRs and SWITCH_EXPRs.
+
+   We want to do those propagations as they can sometimes allow
+   the SSA optimizers to do a better job.  However, in the cases
+   where such propagations do not result in further optimization,
+   we would like to "undo" the propagation to avoid the redundant
+   copies and constant initializations.
+
+   This pass works by first associating equivalences with edges in
+   the CFG.  For example, the edge leading from a SWITCH_EXPR to
+   its associated CASE_LABEL will have an equivalency between
+   SWITCH_COND and the value in the case label.
+
+   Once we have found the edge equivalences, we proceed to walk
+   the CFG in dominator order.  As we traverse edges we record
+   equivalences associated with those edges we traverse.
+
+   When we encounter a PHI node, we walk its arguments to see if we
+   have an equivalence for the PHI argument.  If so, then we replace
+   the argument.
+
+   Equivalences are looked up based on their value (think of it as
+   the RHS of an assignment).   A value may be an SSA_NAME or an
+   invariant.  We may have several SSA_NAMEs with the same value,
+   so with each value we have a list of SSA_NAMEs that have the
+   same value.  */
+
+
+/* Main structure for recording equivalences into our hash table.  */
+struct equiv_hash_elt
+{
+  /* The value/key of this entry.  */
+  tree value;
+
+  /* List of SSA_NAMEs which have the same value/key.  */
+  vec<tree> equivalences;
+};
+
+/* Value to ssa name equivalence hashtable helpers.  */
+
+struct val_ssa_equiv_hasher
+{
+  typedef equiv_hash_elt value_type;
+  typedef equiv_hash_elt compare_type;
+  static inline hashval_t hash (const value_type *);
+  static inline bool equal (const value_type *, const compare_type *);
+  static inline void remove (value_type *);
+};
+
+inline hashval_t
+val_ssa_equiv_hasher::hash (const value_type *p)
+{
+  tree const value = p->value;
+  return iterative_hash_expr (value, 0);
+}
+
+inline bool
+val_ssa_equiv_hasher::equal (const value_type *p1, const compare_type *p2)
+{
+  tree value1 = p1->value;
+  tree value2 = p2->value;
+
+  return operand_equal_p (value1, value2, 0);
+}
+
+/* Free an instance of equiv_hash_elt.  */
+
+inline void
+val_ssa_equiv_hasher::remove (value_type *elt)
+{
+  elt->equivalences.release ();
+  free (elt);
+}
+
+/* Global hash table implementing a mapping from invariant values
+   to a list of SSA_NAMEs which have the same value.  We might be
+   able to reuse tree-vn for this code.  */
+static hash_table <val_ssa_equiv_hasher> val_ssa_equiv;
+
+static void uncprop_into_successor_phis (basic_block);
+
+/* Remove the most recently recorded equivalency for VALUE.  */
+
+static void
+remove_equivalence (tree value)
+{
+  struct equiv_hash_elt an_equiv_elt, *an_equiv_elt_p;
+  equiv_hash_elt **slot;
+
+  an_equiv_elt.value = value;
+  an_equiv_elt.equivalences.create (0);
+
+  slot = val_ssa_equiv.find_slot (&an_equiv_elt, NO_INSERT);
+
+  an_equiv_elt_p = *slot;
+  an_equiv_elt_p->equivalences.pop ();
+}
+
+/* Record EQUIVALENCE = VALUE into our hash table.  */
+
+static void
+record_equiv (tree value, tree equivalence)
+{
+  equiv_hash_elt *an_equiv_elt_p;
+  equiv_hash_elt **slot;
+
+  an_equiv_elt_p = XNEW (struct equiv_hash_elt);
+  an_equiv_elt_p->value = value;
+  an_equiv_elt_p->equivalences.create (0);
+
+  slot = val_ssa_equiv.find_slot (an_equiv_elt_p, INSERT);
+
+  if (*slot == NULL)
+    *slot = an_equiv_elt_p;
+  else
+     free (an_equiv_elt_p);
+
+  an_equiv_elt_p = *slot;
+
+  an_equiv_elt_p->equivalences.safe_push (equivalence);
+}
+
+class uncprop_dom_walker : public dom_walker
+{
+public:
+  uncprop_dom_walker (cdi_direction direction) : dom_walker (direction) {}
+
+  virtual void before_dom_children (basic_block);
+  virtual void after_dom_children (basic_block);
+
+private:
+
+  /* As we enter each block we record the value for any edge equivalency
+     leading to this block.  If no such edge equivalency exists, then we
+     record NULL.  These equivalences are live until we leave the dominator
+     subtree rooted at the block where we record the equivalency.  */
+  auto_vec<tree, 2> m_equiv_stack;
+};
+
+/* Main driver for un-cprop.  */
+
+static unsigned int
+tree_ssa_uncprop (void)
+{
+  basic_block bb;
+
+  associate_equivalences_with_edges ();
+
+  /* Create our global data structures.  */
+  val_ssa_equiv.create (1024);
+
+  /* We're going to do a dominator walk, so ensure that we have
+     dominance information.  */
+  calculate_dominance_info (CDI_DOMINATORS);
+
+  /* Recursively walk the dominator tree undoing unprofitable
+     constant/copy propagations.  */
+  uncprop_dom_walker (CDI_DOMINATORS).walk (cfun->cfg->x_entry_block_ptr);
+
+  /* we just need to empty elements out of the hash table, and cleanup the
+    AUX field on the edges.  */
+  val_ssa_equiv.dispose ();
+  FOR_EACH_BB_FN (bb, cfun)
+    {
+      edge e;
+      edge_iterator ei;
+
+      FOR_EACH_EDGE (e, ei, bb->succs)
+	{
+	  if (e->aux)
+	    {
+	      free (e->aux);
+	      e->aux = NULL;
+	    }
+	}
+    }
+  return 0;
+}
+
+
+/* We have finished processing the dominator children of BB, perform
+   any finalization actions in preparation for leaving this node in
+   the dominator tree.  */
+
+void
+uncprop_dom_walker::after_dom_children (basic_block bb ATTRIBUTE_UNUSED)
+{
+  /* Pop the topmost value off the equiv stack.  */
+  tree value = m_equiv_stack.pop ();
+
+  /* If that value was non-null, then pop the topmost equivalency off
+     its equivalency stack.  */
+  if (value != NULL)
+    remove_equivalence (value);
+}
+
+/* Unpropagate values from PHI nodes in successor blocks of BB.  */
+
+static void
+uncprop_into_successor_phis (basic_block bb)
+{
+  edge e;
+  edge_iterator ei;
+
+  /* For each successor edge, first temporarily record any equivalence
+     on that edge.  Then unpropagate values in any PHI nodes at the
+     destination of the edge.  Then remove the temporary equivalence.  */
+  FOR_EACH_EDGE (e, ei, bb->succs)
+    {
+      gimple_seq phis = phi_nodes (e->dest);
+      gimple_stmt_iterator gsi;
+
+      /* If there are no PHI nodes in this destination, then there is
+	 no sense in recording any equivalences.  */
+      if (gimple_seq_empty_p (phis))
+	continue;
+
+      /* Record any equivalency associated with E.  */
+      if (e->aux)
+	{
+	  struct edge_equivalency *equiv = (struct edge_equivalency *) e->aux;
+	  record_equiv (equiv->rhs, equiv->lhs);
+	}
+
+      /* Walk over the PHI nodes, unpropagating values.  */
+      for (gsi = gsi_start (phis) ; !gsi_end_p (gsi); gsi_next (&gsi))
+	{
+	  gimple phi = gsi_stmt (gsi);
+	  tree arg = PHI_ARG_DEF (phi, e->dest_idx);
+	  tree res = PHI_RESULT (phi);
+	  equiv_hash_elt an_equiv_elt;
+	  equiv_hash_elt **slot;
+
+	  /* If the argument is not an invariant and can be potentially
+	     coalesced with the result, then there's no point in
+	     un-propagating the argument.  */
+	  if (!is_gimple_min_invariant (arg)
+	      && gimple_can_coalesce_p (arg, res))
+	    continue;
+
+	  /* Lookup this argument's value in the hash table.  */
+	  an_equiv_elt.value = arg;
+	  an_equiv_elt.equivalences.create (0);
+	  slot = val_ssa_equiv.find_slot (&an_equiv_elt, NO_INSERT);
+
+	  if (slot)
+	    {
+	      struct equiv_hash_elt *elt = *slot;
+	      int j;
+
+	      /* Walk every equivalence with the same value.  If we find
+		 one that can potentially coalesce with the PHI rsult,
+		 then replace the value in the argument with its equivalent
+		 SSA_NAME.  Use the most recent equivalence as hopefully
+		 that results in shortest lifetimes.  */
+	      for (j = elt->equivalences.length () - 1; j >= 0; j--)
+		{
+		  tree equiv = elt->equivalences[j];
+
+		  if (gimple_can_coalesce_p (equiv, res))
+		    {
+		      SET_PHI_ARG_DEF (phi, e->dest_idx, equiv);
+		      break;
+		    }
+		}
+	    }
+	}
+
+      /* If we had an equivalence associated with this edge, remove it.  */
+      if (e->aux)
+	{
+	  struct edge_equivalency *equiv = (struct edge_equivalency *) e->aux;
+	  remove_equivalence (equiv->rhs);
+	}
+    }
+}
+
+/* Ignoring loop backedges, if BB has precisely one incoming edge then
+   return that edge.  Otherwise return NULL.  */
+static edge
+single_incoming_edge_ignoring_loop_edges (basic_block bb)
+{
+  edge retval = NULL;
+  edge e;
+  edge_iterator ei;
+
+  FOR_EACH_EDGE (e, ei, bb->preds)
+    {
+      /* A loop back edge can be identified by the destination of
+	 the edge dominating the source of the edge.  */
+      if (dominated_by_p (CDI_DOMINATORS, e->src, e->dest))
+	continue;
+
+      /* If we have already seen a non-loop edge, then we must have
+	 multiple incoming non-loop edges and thus we return NULL.  */
+      if (retval)
+	return NULL;
+
+      /* This is the first non-loop incoming edge we have found.  Record
+	 it.  */
+      retval = e;
+    }
+
+  return retval;
+}
+
+void
+uncprop_dom_walker::before_dom_children (basic_block bb)
+{
+  basic_block parent;
+  edge e;
+  bool recorded = false;
+
+  /* If this block is dominated by a single incoming edge and that edge
+     has an equivalency, then record the equivalency and push the
+     VALUE onto EQUIV_STACK.  Else push a NULL entry on EQUIV_STACK.  */
+  parent = get_immediate_dominator (CDI_DOMINATORS, bb);
+  if (parent)
+    {
+      e = single_incoming_edge_ignoring_loop_edges (bb);
+
+      if (e && e->src == parent && e->aux)
+	{
+	  struct edge_equivalency *equiv = (struct edge_equivalency *) e->aux;
+
+	  record_equiv (equiv->rhs, equiv->lhs);
+	  m_equiv_stack.safe_push (equiv->rhs);
+	  recorded = true;
+	}
+    }
+
+  if (!recorded)
+    m_equiv_stack.safe_push (NULL_TREE);
+
+  uncprop_into_successor_phis (bb);
+}
+
+static bool
+gate_uncprop (void)
+{
+  return flag_tree_dom != 0;
+}
+
+namespace {
+
+const pass_data pass_data_uncprop =
+{
+  GIMPLE_PASS, /* type */
+  "uncprop", /* name */
+  OPTGROUP_NONE, /* optinfo_flags */
+  true, /* has_gate */
+  true, /* has_execute */
+  TV_TREE_SSA_UNCPROP, /* tv_id */
+  ( PROP_cfg | PROP_ssa ), /* properties_required */
+  0, /* properties_provided */
+  0, /* properties_destroyed */
+  0, /* todo_flags_start */
+  TODO_verify_ssa, /* todo_flags_finish */
+};
+
+class pass_uncprop : public gimple_opt_pass
+{
+public:
+  pass_uncprop (gcc::context *ctxt)
+    : gimple_opt_pass (pass_data_uncprop, ctxt)
+  {}
+
+  /* opt_pass methods: */
+  opt_pass * clone () { return new pass_uncprop (m_ctxt); }
+  bool gate () { return gate_uncprop (); }
+  unsigned int execute () { return tree_ssa_uncprop (); }
+
+}; // class pass_uncprop
+
+} // anon namespace
+
+gimple_opt_pass *
+make_pass_uncprop (gcc::context *ctxt)
+{
+  return new pass_uncprop (ctxt);
+}