CbC/CbC_gcc: gcc/tree-ssa-uncprop.c comparison

comparison gcc/tree-ssa-uncprop.c @ 111:04ced10e8804

gcc 7

author	kono
date	Fri, 27 Oct 2017 22:46:09 +0900
parents	f6334be47118
children	84e7813d76e9

comparison

equal deleted inserted replaced

-:561a7518be6b
+:04ced10e8804
 /* Routines for discovering and unpropagating edge equivalences.
-Copyright (C) 2005, 2007, 2008, 2010
+Copyright (C) 2005-2017 Free Software Foundation, Inc.
-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
 <http://www.gnu.org/licenses/>.  */
 #include "config.h"
 #include "system.h"
 #include "coretypes.h"
-#include "tm.h"
+#include "backend.h"
 #include "tree.h"
-#include "flags.h"
+#include "gimple.h"
-#include "tm_p.h"
+#include "tree-pass.h"
-#include "basic-block.h"
+#include "ssa.h"
-#include "output.h"
+#include "fold-const.h"
-#include "function.h"
+#include "cfganal.h"
-#include "timevar.h"
+#include "gimple-iterator.h"
-#include "tree-dump.h"
+#include "tree-cfg.h"
-#include "tree-flow.h"
 #include "domwalk.h"
-#include "tree-pass.h"
+#include "tree-hash-traits.h"
-#include "tree-ssa-propagate.h"
+#include "tree-ssa-live.h"
-#include "langhooks.h"
+#include "tree-ssa-coalesce.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
 {
 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 (bb)
+FOR_EACH_BB_FN (bb, cfun)
 {
 gimple_stmt_iterator gsi = gsi_last_bb (bb);
-gimple stmt;
+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;
 	      /* 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
+		  && ssa_name_has_boolean_range (op0)
-		  && is_gimple_min_invariant (op1))
+		  && is_gimple_min_invariant (op1)
+		  && (integer_zerop (op1) || integer_onep (op1)))
 		{
+		  tree true_val = constant_boolean_node (true, TREE_TYPE (op0));
+		  tree false_val = constant_boolean_node (false,
+							  TREE_TYPE (op0));
 		  if (code == EQ_EXPR)
 		    {
 		      equivalency = XNEW (struct edge_equivalency);
 		      equivalency->lhs = op0;
 		      equivalency->rhs = (integer_zerop (op1)
-					  ? boolean_false_node
+					  ? false_val
-					  : boolean_true_node);
+					  : true_val);
 		      true_edge->aux = equivalency;
 		      equivalency = XNEW (struct edge_equivalency);
 		      equivalency->lhs = op0;
 		      equivalency->rhs = (integer_zerop (op1)
-					  ? boolean_true_node
+					  ? true_val
-					  : boolean_false_node);
+					  : false_val);
 		      false_edge->aux = equivalency;
 		    }
 		  else
 		    {
 		      equivalency = XNEW (struct edge_equivalency);
 		      equivalency->lhs = op0;
 		      equivalency->rhs = (integer_zerop (op1)
-					  ? boolean_true_node
+					  ? true_val
-					  : boolean_false_node);
+					  : false_val);
 		      true_edge->aux = equivalency;
 		      equivalency = XNEW (struct edge_equivalency);
 		      equivalency->lhs = op0;
 		      equivalency->rhs = (integer_zerop (op1)
-					  ? boolean_false_node
+					  ? false_val
-					  : boolean_true_node);
+					  : true_val);
 		      false_edge->aux = equivalency;
 		    }
 		}
 	      else if (TREE_CODE (op0) == SSA_NAME
 		{
 		  /* 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)))
+		  if (HONOR_SIGNED_ZEROS (op0)
 		      && (TREE_CODE (op1) != REAL_CST
-			  || REAL_VALUES_EQUAL (dconst0, TREE_REAL_CST (op1))))
+			  || real_equal (&dconst0, &TREE_REAL_CST (op1))))
 		    continue;
 		  equivalency = XNEW (struct edge_equivalency);
 		  equivalency->lhs = op0;
 		  equivalency->rhs = op1;
 /* 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);
+	  gswitch *switch_stmt = as_a <gswitch *> (stmt);
+	  tree cond = gimple_switch_index (switch_stmt);
 	  if (TREE_CODE (cond) == SSA_NAME
 	      && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (cond))
 	    {
-	      int i, n_labels = gimple_switch_num_labels (stmt);
+	      int i, n_labels = gimple_switch_num_labels (switch_stmt);
-	      tree *info = XCNEWVEC (tree, last_basic_block);
+	      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);
+		  tree label = gimple_switch_label (switch_stmt, i);
 		  basic_block bb = label_to_block (CASE_LABEL (label));
 		  if (CASE_HIGH (label)
 		      || !CASE_LOW (label)
 		      || info[bb->index])
 		    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; i++)
+	      for (i = 0; i < n_basic_blocks_for_fn (cfun); i++)
 		{
 		  tree node = info[i];
 		  if (node != NULL
 		      && node != error_mark_node)
 		      /* 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 (i))->aux = equivalency;
+		      find_edge (bb, BASIC_BLOCK_FOR_FN (cfun, i))->aux =
+			equivalency;
 		    }
 		}
 	      free (info);
 	    }
 	}
 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.  */
-/* 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
+/* Main structure for recording equivalences into our hash table.  */
-record NULL.  These equivalences are live until we leave the dominator
+struct equiv_hash_elt
-subtree rooted at the block where we record the equivalency.  */
+{
-static VEC(tree,heap) *equiv_stack;
+/* The value/key of this entry.  */
+tree value;
+/* List of SSA_NAMEs which have the same value/key.  */
+vec<tree> equivalences;
+};
 /* 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 htab_t equiv;
+static hash_map<tree, auto_vec<tree> > *val_ssa_equiv;
-/* 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,heap) *equivalences;
-};
-static void uncprop_enter_block (struct dom_walk_data *, basic_block);
-static void uncprop_leave_block (struct dom_walk_data *, basic_block);
 static void uncprop_into_successor_phis (basic_block);
-/* Hashing and equality routines for the hash table.  */
-static hashval_t
-equiv_hash (const void *p)
-{
-tree const value = ((const struct equiv_hash_elt *)p)->value;
-return iterative_hash_expr (value, 0);
-}
-static int
-equiv_eq (const void *p1, const void *p2)
-{
-tree value1 = ((const struct equiv_hash_elt *)p1)->value;
-tree value2 = ((const struct equiv_hash_elt *)p2)->value;
-return operand_equal_p (value1, value2, 0);
-}
-/* Free an instance of equiv_hash_elt.  */
-static void
-equiv_free (void *p)
-{
-struct equiv_hash_elt *elt = (struct equiv_hash_elt *) p;
-VEC_free (tree, heap, elt->equivalences);
-free (elt);
-}
 /* Remove the most recently recorded equivalency for VALUE.  */
 static void
 remove_equivalence (tree value)
 {
-struct equiv_hash_elt equiv_hash_elt, *equiv_hash_elt_p;
+val_ssa_equiv->get (value)->pop ();
-void **slot;
-equiv_hash_elt.value = value;
-equiv_hash_elt.equivalences = NULL;
-slot = htab_find_slot (equiv, &equiv_hash_elt, NO_INSERT);
-equiv_hash_elt_p = (struct equiv_hash_elt *) *slot;
-VEC_pop (tree, equiv_hash_elt_p->equivalences);
 }
 /* Record EQUIVALENCE = VALUE into our hash table.  */
 static void
 record_equiv (tree value, tree equivalence)
 {
-struct equiv_hash_elt *equiv_hash_elt;
+val_ssa_equiv->get_or_insert (value).safe_push (equivalence);
-void **slot;
+}
-equiv_hash_elt = XNEW (struct equiv_hash_elt);
+class uncprop_dom_walker : public dom_walker
-equiv_hash_elt->value = value;
+{
-equiv_hash_elt->equivalences = NULL;
+public:
+uncprop_dom_walker (cdi_direction direction) : dom_walker (direction) {}
-slot = htab_find_slot (equiv, equiv_hash_elt, INSERT);
+virtual edge before_dom_children (basic_block);
-if (*slot == NULL)
+virtual void after_dom_children (basic_block);
-*slot = (void *) equiv_hash_elt;
-else
+private:
-free (equiv_hash_elt);
+/* As we enter each block we record the value for any edge equivalency
-equiv_hash_elt = (struct equiv_hash_elt *) *slot;
+leading to this block.  If no such edge equivalency exists, then we
+record NULL.  These equivalences are live until we leave the dominator
-VEC_safe_push (tree, heap, equiv_hash_elt->equivalences, equivalence);
+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)
-{
-struct dom_walk_data walk_data;
-basic_block bb;
-associate_equivalences_with_edges ();
-/* Create our global data structures.  */
-equiv = htab_create (1024, equiv_hash, equiv_eq, equiv_free);
-equiv_stack = VEC_alloc (tree, heap, 2);
-/* We're going to do a dominator walk, so ensure that we have
-dominance information.  */
-calculate_dominance_info (CDI_DOMINATORS);
-/* Setup callbacks for the generic dominator tree walker.  */
-walk_data.dom_direction = CDI_DOMINATORS;
-walk_data.initialize_block_local_data = NULL;
-walk_data.before_dom_children = uncprop_enter_block;
-walk_data.after_dom_children = uncprop_leave_block;
-walk_data.global_data = NULL;
-walk_data.block_local_data_size = 0;
-/* Now initialize the dominator walker.  */
-init_walk_dominator_tree (&walk_data);
-/* Recursively walk the dominator tree undoing unprofitable
-constant/copy propagations.  */
-walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
-/* Finalize and clean up.  */
-fini_walk_dominator_tree (&walk_data);
-/* EQUIV_STACK should already be empty at this point, so we just
-need to empty elements out of the hash table, free EQUIV_STACK,
-and cleanup the AUX field on the edges.  */
-htab_delete (equiv);
-VEC_free (tree, heap, equiv_stack);
-FOR_EACH_BB (bb)
-{
-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.  */
-static void
+void
-uncprop_leave_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
+uncprop_dom_walker::after_dom_children (basic_block bb ATTRIBUTE_UNUSED)
-		     basic_block bb ATTRIBUTE_UNUSED)
 {
 /* Pop the topmost value off the equiv stack.  */
-tree value = VEC_pop (tree, 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);
 	}
 /* Walk over the PHI nodes, unpropagating values.  */
 for (gsi = gsi_start (phis) ; !gsi_end_p (gsi); gsi_next (&gsi))
 	{
-	  gimple phi = gsi_stmt (gsi);
+	  gimple *phi = gsi_stmt (gsi);
 	  tree arg = PHI_ARG_DEF (phi, e->dest_idx);
-	  struct equiv_hash_elt equiv_hash_elt;
+	  tree res = PHI_RESULT (phi);
-	  void **slot;
+	  /* If the argument is not an invariant and can be potentially
-	  /* If the argument is not an invariant, or refers to the same
+	     coalesced with the result, then there's no point in
-	     underlying variable as the PHI result, then there's no
+	     un-propagating the argument.  */
-	     point in un-propagating the argument.  */
 	  if (!is_gimple_min_invariant (arg)
-	      && SSA_NAME_VAR (arg) != SSA_NAME_VAR (PHI_RESULT (phi)))
+	      && gimple_can_coalesce_p (arg, res))
 	    continue;
 	  /* Lookup this argument's value in the hash table.  */
-	  equiv_hash_elt.value = arg;
+	  vec<tree> *equivalences = val_ssa_equiv->get (arg);
-	  equiv_hash_elt.equivalences = NULL;
+	  if (equivalences)
-	  slot = htab_find_slot (equiv, &equiv_hash_elt, NO_INSERT);
-	  if (slot)
 	    {
-	      struct equiv_hash_elt *elt = (struct equiv_hash_elt *) *slot;
-	      int j;
 	      /* Walk every equivalence with the same value.  If we find
-		 one with the same underlying variable as the PHI result,
+		 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 = VEC_length (tree, elt->equivalences) - 1; j >= 0; j--)
+	      for (int j = equivalences->length () - 1; j >= 0; j--)
 		{
-		  tree equiv = VEC_index (tree, elt->equivalences, j);
+		  tree equiv = (*equivalences)[j];
-		  if (SSA_NAME_VAR (equiv) == SSA_NAME_VAR (PHI_RESULT (phi)))
+		  if (gimple_can_coalesce_p (equiv, res))
 		    {
 		      SET_PHI_ARG_DEF (phi, e->dest_idx, equiv);
 		      break;
 		    }
 		}
 }
 return retval;
 }
-static void
+edge
-uncprop_enter_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
+uncprop_dom_walker::before_dom_children (basic_block bb)
-		     basic_block bb)
 {
 basic_block parent;
 edge e;
 bool recorded = false;
 if (e && e->src == parent && e->aux)
 	{
 	  struct edge_equivalency *equiv = (struct edge_equivalency *) e->aux;
 	  record_equiv (equiv->rhs, equiv->lhs);
-	  VEC_safe_push (tree, heap, equiv_stack, equiv->rhs);
+	  m_equiv_stack.safe_push (equiv->rhs);
 	  recorded = true;
 	}
 }
 if (!recorded)
-VEC_safe_push (tree, heap, equiv_stack, NULL_TREE);
+m_equiv_stack.safe_push (NULL_TREE);
 uncprop_into_successor_phis (bb);
-}
+return NULL;
+}
-static bool
-gate_uncprop (void)
+namespace {
-{
-return flag_tree_dom != 0;
+const pass_data pass_data_uncprop =
-}
+{
+GIMPLE_PASS, /* type */
-struct gimple_opt_pass pass_uncprop =
+"uncprop", /* name */
-{
+OPTGROUP_NONE, /* optinfo_flags */
-{
+TV_TREE_SSA_UNCPROP, /* tv_id */
-GIMPLE_PASS,
+( PROP_cfg | PROP_ssa ), /* properties_required */
-"uncprop",				/* name */
+0, /* properties_provided */
-gate_uncprop,				/* gate */
+0, /* properties_destroyed */
-tree_ssa_uncprop,			/* execute */
+0, /* todo_flags_start */
-NULL,					/* sub */
+0, /* todo_flags_finish */
-NULL,					/* next */
-0,					/* static_pass_number */
-TV_TREE_SSA_UNCPROP,			/* tv_id */
-PROP_cfg | PROP_ssa,			/* properties_required */
-0,					/* properties_provided */
-0,					/* properties_destroyed */
-0,					/* todo_flags_start */
-TODO_dump_func | 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); }
+virtual bool gate (function *) { return flag_tree_dom != 0; }
+virtual unsigned int execute (function *);
+}; // class pass_uncprop
+unsigned int
+pass_uncprop::execute (function *fun)
+{
+basic_block bb;
+associate_equivalences_with_edges ();
+/* Create our global data structures.  */
+val_ssa_equiv = new hash_map<tree, auto_vec<tree> > (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 (fun->cfg->x_entry_block_ptr);
+/* we just need to empty elements out of the hash table, and cleanup the
+AUX field on the edges.  */
+delete val_ssa_equiv;
+val_ssa_equiv = NULL;
+FOR_EACH_BB_FN (bb, fun)
+{
+edge e;
+edge_iterator ei;
+FOR_EACH_EDGE (e, ei, bb->succs)
+	{
+	  if (e->aux)
+	    {
+	      free (e->aux);
+	      e->aux = NULL;
+	    }
+	}
+}
+return 0;
+}
+} // anon namespace
+gimple_opt_pass *
+make_pass_uncprop (gcc::context *ctxt)
+{
+return new pass_uncprop (ctxt);
+}

Mercurial > hg > CbC > CbC_gcc

comparison gcc/tree-ssa-uncprop.c @ 111:04ced10e8804