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

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

gcc 7

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

comparison

equal deleted inserted replaced

-:561a7518be6b
+:04ced10e8804
+/* Const/Copy propagation originating from degenerate PHIs
+Copyright (C) 2001-2017 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 "backend.h"
+#include "cfghooks.h"
+#include "tree.h"
+#include "gimple.h"
+#include "ssa.h"
+#include "fold-const.h"
+#include "cfgloop.h"
+#include "gimple-pretty-print.h"
+#include "gimple-fold.h"
+#include "tree-eh.h"
+#include "gimple-iterator.h"
+#include "tree-cfg.h"
+#include "tree-pass.h"
+#include "tree-ssa-propagate.h"
+/* PHI-ONLY copy and constant propagation.  This pass is meant to clean
+up degenerate PHIs created by or exposed by jump threading.  */
+/* Given a statement STMT, which is either a PHI node or an assignment,
+remove it from the IL.  */
+static void
+remove_stmt_or_phi (gimple *stmt)
+{
+gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
+if (gimple_code (stmt) == GIMPLE_PHI)
+remove_phi_node (&gsi, true);
+else
+{
+gsi_remove (&gsi, true);
+release_defs (stmt);
+}
+}
+/* Given a statement STMT, which is either a PHI node or an assignment,
+return the "rhs" of the node, in the case of a non-degenerate
+phi, NULL is returned.  */
+static tree
+get_rhs_or_phi_arg (gimple *stmt)
+{
+if (gimple_code (stmt) == GIMPLE_PHI)
+return degenerate_phi_result (as_a <gphi *> (stmt));
+else if (gimple_assign_single_p (stmt))
+return gimple_assign_rhs1 (stmt);
+else
+gcc_unreachable ();
+}
+/* Given a statement STMT, which is either a PHI node or an assignment,
+return the "lhs" of the node.  */
+static tree
+get_lhs_or_phi_result (gimple *stmt)
+{
+if (gimple_code (stmt) == GIMPLE_PHI)
+return gimple_phi_result (stmt);
+else if (is_gimple_assign (stmt))
+return gimple_assign_lhs (stmt);
+else
+gcc_unreachable ();
+}
+/* Propagate RHS into all uses of LHS (when possible).
+RHS and LHS are derived from STMT, which is passed in solely so
+that we can remove it if propagation is successful.
+When propagating into a PHI node or into a statement which turns
+into a trivial copy or constant initialization, set the
+appropriate bit in INTERESTING_NAMEs so that we will visit those
+nodes as well in an effort to pick up secondary optimization
+opportunities.
+NEED_EH_CLEANUP tracks blocks that need their EH information
+cleaned up after changing EH information on a statement.  */
+static bool
+propagate_rhs_into_lhs (gimple *stmt, tree lhs, tree rhs,
+			bitmap interesting_names, bitmap need_eh_cleanup)
+{
+bool cfg_altered = false;
+/* First verify that propagation is valid.  */
+if (may_propagate_copy (lhs, rhs))
+{
+use_operand_p use_p;
+imm_use_iterator iter;
+gimple *use_stmt;
+bool all = true;
+/* Dump details.  */
+if (dump_file && (dump_flags & TDF_DETAILS))
+	{
+	  fprintf (dump_file, "  Replacing '");
+	  print_generic_expr (dump_file, lhs, dump_flags);
+	  fprintf (dump_file, "' with %s '",
+	           (TREE_CODE (rhs) != SSA_NAME ? "constant" : "variable"));
+		   print_generic_expr (dump_file, rhs, dump_flags);
+	  fprintf (dump_file, "'\n");
+	}
+/* Walk over every use of LHS and try to replace the use with RHS.
+	 At this point the only reason why such a propagation would not
+	 be successful would be if the use occurs in an ASM_EXPR.  */
+FOR_EACH_IMM_USE_STMT (use_stmt, iter, lhs)
+	{
+	  /* Leave debug stmts alone.  If we succeed in propagating
+	     all non-debug uses, we'll drop the DEF, and propagation
+	     into debug stmts will occur then.  */
+	  if (gimple_debug_bind_p (use_stmt))
+	    continue;
+	  /* It's not always safe to propagate into an ASM_EXPR.  */
+	  if (gimple_code (use_stmt) == GIMPLE_ASM
+&& ! may_propagate_copy_into_asm (lhs))
+	    {
+	      all = false;
+	      continue;
+	    }
+	  /* It's not ok to propagate into the definition stmt of RHS.
+		<bb 9>:
+		  # prephitmp.12_36 = PHI <g_67.1_6(9)>
+		  g_67.1_6 = prephitmp.12_36;
+		  goto <bb 9>;
+	     While this is strictly all dead code we do not want to
+	     deal with this here.  */
+	  if (TREE_CODE (rhs) == SSA_NAME
+	      && SSA_NAME_DEF_STMT (rhs) == use_stmt)
+	    {
+	      all = false;
+	      continue;
+	    }
+	  /* Dump details.  */
+	  if (dump_file && (dump_flags & TDF_DETAILS))
+	    {
+	      fprintf (dump_file, "    Original statement:");
+	      print_gimple_stmt (dump_file, use_stmt, 0, dump_flags);
+	    }
+	  /* Propagate the RHS into this use of the LHS.  */
+	  FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
+	    propagate_value (use_p, rhs);
+	  /* Special cases to avoid useless calls into the folding
+	     routines, operand scanning, etc.
+	     Propagation into a PHI may cause the PHI to become
+	     a degenerate, so mark the PHI as interesting.  No other
+	     actions are necessary.  */
+	  if (gimple_code (use_stmt) == GIMPLE_PHI)
+	    {
+	      tree result;
+	      /* Dump details.  */
+	      if (dump_file && (dump_flags & TDF_DETAILS))
+		{
+		  fprintf (dump_file, "    Updated statement:");
+		  print_gimple_stmt (dump_file, use_stmt, 0, dump_flags);
+		}
+	      result = get_lhs_or_phi_result (use_stmt);
+	      bitmap_set_bit (interesting_names, SSA_NAME_VERSION (result));
+	      continue;
+	    }
+	  /* From this point onward we are propagating into a
+	     real statement.  Folding may (or may not) be possible,
+	     we may expose new operands, expose dead EH edges,
+	     etc.  */
+/* NOTE tuples. In the tuples world, fold_stmt_inplace
+cannot fold a call that simplifies to a constant,
+because the GIMPLE_CALL must be replaced by a
+GIMPLE_ASSIGN, and there is no way to effect such a
+transformation in-place.  We might want to consider
+using the more general fold_stmt here.  */
+	    {
+	      gimple_stmt_iterator gsi = gsi_for_stmt (use_stmt);
+	      fold_stmt_inplace (&gsi);
+	    }
+	  /* Sometimes propagation can expose new operands to the
+	     renamer.  */
+	  update_stmt (use_stmt);
+	  /* Dump details.  */
+	  if (dump_file && (dump_flags & TDF_DETAILS))
+	    {
+	      fprintf (dump_file, "    Updated statement:");
+	      print_gimple_stmt (dump_file, use_stmt, 0, dump_flags);
+	    }
+	  /* If we replaced a variable index with a constant, then
+	     we would need to update the invariant flag for ADDR_EXPRs.  */
+if (gimple_assign_single_p (use_stmt)
+&& TREE_CODE (gimple_assign_rhs1 (use_stmt)) == ADDR_EXPR)
+	    recompute_tree_invariant_for_addr_expr
+(gimple_assign_rhs1 (use_stmt));
+	  /* If we cleaned up EH information from the statement,
+	     mark its containing block as needing EH cleanups.  */
+	  if (maybe_clean_or_replace_eh_stmt (use_stmt, use_stmt))
+	    {
+	      bitmap_set_bit (need_eh_cleanup, gimple_bb (use_stmt)->index);
+	      if (dump_file && (dump_flags & TDF_DETAILS))
+		fprintf (dump_file, "  Flagged to clear EH edges.\n");
+	    }
+	  /* Propagation may expose new trivial copy/constant propagation
+	     opportunities.  */
+if (gimple_assign_single_p (use_stmt)
+&& TREE_CODE (gimple_assign_lhs (use_stmt)) == SSA_NAME
+&& (TREE_CODE (gimple_assign_rhs1 (use_stmt)) == SSA_NAME
+|| is_gimple_min_invariant (gimple_assign_rhs1 (use_stmt))))
+{
+	      tree result = get_lhs_or_phi_result (use_stmt);
+	      bitmap_set_bit (interesting_names, SSA_NAME_VERSION (result));
+	    }
+	  /* Propagation into these nodes may make certain edges in
+	     the CFG unexecutable.  We want to identify them as PHI nodes
+	     at the destination of those unexecutable edges may become
+	     degenerates.  */
+	  else if (gimple_code (use_stmt) == GIMPLE_COND
+		   || gimple_code (use_stmt) == GIMPLE_SWITCH
+		   || gimple_code (use_stmt) == GIMPLE_GOTO)
+{
+	      tree val;
+	      if (gimple_code (use_stmt) == GIMPLE_COND)
+val = fold_binary_loc (gimple_location (use_stmt),
+				   gimple_cond_code (use_stmt),
+boolean_type_node,
+gimple_cond_lhs (use_stmt),
+gimple_cond_rhs (use_stmt));
+else if (gimple_code (use_stmt) == GIMPLE_SWITCH)
+		val = gimple_switch_index (as_a <gswitch *> (use_stmt));
+	      else
+		val = gimple_goto_dest  (use_stmt);
+	      if (val && is_gimple_min_invariant (val))
+		{
+		  basic_block bb = gimple_bb (use_stmt);
+		  edge te = find_taken_edge (bb, val);
+		  if (!te)
+		    continue;
+		  edge_iterator ei;
+		  edge e;
+		  gimple_stmt_iterator gsi;
+		  gphi_iterator psi;
+		  /* Remove all outgoing edges except TE.  */
+		  for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei));)
+		    {
+		      if (e != te)
+			{
+			  /* Mark all the PHI nodes at the destination of
+			     the unexecutable edge as interesting.  */
+for (psi = gsi_start_phis (e->dest);
+!gsi_end_p (psi);
+gsi_next (&psi))
+{
+gphi *phi = psi.phi ();
+			      tree result = gimple_phi_result (phi);
+			      int version = SSA_NAME_VERSION (result);
+			      bitmap_set_bit (interesting_names, version);
+			    }
+			  te->probability += e->probability;
+			  remove_edge (e);
+			  cfg_altered = true;
+			}
+		      else
+			ei_next (&ei);
+		    }
+		  gsi = gsi_last_bb (gimple_bb (use_stmt));
+		  gsi_remove (&gsi, true);
+		  /* And fixup the flags on the single remaining edge.  */
+		  te->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
+		  te->flags &= ~EDGE_ABNORMAL;
+		  te->flags |= EDGE_FALLTHRU;
+	        }
+	    }
+	}
+/* Ensure there is nothing else to do. */
+gcc_assert (!all || has_zero_uses (lhs));
+/* If we were able to propagate away all uses of LHS, then
+	 we can remove STMT.  */
+if (all)
+	remove_stmt_or_phi (stmt);
+}
+return cfg_altered;
+}
+/* STMT is either a PHI node (potentially a degenerate PHI node) or
+a statement that is a trivial copy or constant initialization.
+Attempt to eliminate STMT by propagating its RHS into all uses of
+its LHS.  This may in turn set new bits in INTERESTING_NAMES
+for nodes we want to revisit later.
+All exit paths should clear INTERESTING_NAMES for the result
+of STMT.
+NEED_EH_CLEANUP tracks blocks that need their EH information
+cleaned up after changing EH information on a statement.  It is
+not set or queried here, but passed along to children.  */
+static bool
+eliminate_const_or_copy (gimple *stmt, bitmap interesting_names,
+			 bitmap need_eh_cleanup)
+{
+tree lhs = get_lhs_or_phi_result (stmt);
+tree rhs;
+int version = SSA_NAME_VERSION (lhs);
+bool cfg_altered = false;
+/* If the LHS of this statement or PHI has no uses, then we can
+just eliminate it.  This can occur if, for example, the PHI
+was created by block duplication due to threading and its only
+use was in the conditional at the end of the block which was
+deleted.  */
+if (has_zero_uses (lhs))
+{
+bitmap_clear_bit (interesting_names, version);
+remove_stmt_or_phi (stmt);
+return cfg_altered;
+}
+/* Get the RHS of the assignment or PHI node if the PHI is a
+degenerate.  */
+rhs = get_rhs_or_phi_arg (stmt);
+if (!rhs)
+{
+bitmap_clear_bit (interesting_names, version);
+return cfg_altered;
+}
+if (!virtual_operand_p (lhs))
+cfg_altered = propagate_rhs_into_lhs (stmt, lhs, rhs,
+					  interesting_names, need_eh_cleanup);
+else
+{
+gimple *use_stmt;
+imm_use_iterator iter;
+use_operand_p use_p;
+/* For virtual operands we have to propagate into all uses as
+otherwise we will create overlapping life-ranges.  */
+FOR_EACH_IMM_USE_STMT (use_stmt, iter, lhs)
+	FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
+	  SET_USE (use_p, rhs);
+if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
+	SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs) = 1;
+remove_stmt_or_phi (stmt);
+}
+/* Note that STMT may well have been deleted by now, so do
+not access it, instead use the saved version # to clear
+T's entry in the worklist.  */
+bitmap_clear_bit (interesting_names, version);
+return cfg_altered;
+}
+/* The first phase in degenerate PHI elimination.
+Eliminate the degenerate PHIs in BB, then recurse on the
+dominator children of BB.
+INTERESTING_NAMES tracks SSA_NAMEs that we may want to revisit
+in the future.  It is not set or queried here, but passed along
+to children.
+NEED_EH_CLEANUP tracks blocks that need their EH information
+cleaned up after changing EH information on a statement.  It is
+not set or queried here, but passed along to children.  */
+static bool
+eliminate_degenerate_phis_1 (basic_block bb, bitmap interesting_names,
+			     bitmap need_eh_cleanup)
+{
+gphi_iterator gsi;
+basic_block son;
+bool cfg_altered = false;
+for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi);)
+{
+gphi *phi = gsi.phi ();
+/* We might end up removing PHI so advance the iterator now.  */
+gsi_next (&gsi);
+cfg_altered |= eliminate_const_or_copy (phi, interesting_names,
+					      need_eh_cleanup);
+}
+/* Recurse into the dominator children of BB.  */
+for (son = first_dom_son (CDI_DOMINATORS, bb);
+son;
+son = next_dom_son (CDI_DOMINATORS, son))
+cfg_altered |= eliminate_degenerate_phis_1 (son, interesting_names,
+						need_eh_cleanup);
+return cfg_altered;
+}
+/* A very simple pass to eliminate degenerate PHI nodes from the
+IL.  This is meant to be fast enough to be able to be run several
+times in the optimization pipeline.
+Certain optimizations, particularly those which duplicate blocks
+or remove edges from the CFG can create or expose PHIs which are
+trivial copies or constant initializations.
+While we could pick up these optimizations in DOM or with the
+combination of copy-prop and CCP, those solutions are far too
+heavy-weight for our needs.
+This implementation has two phases so that we can efficiently
+eliminate the first order degenerate PHIs and second order
+degenerate PHIs.
+The first phase performs a dominator walk to identify and eliminate
+the vast majority of the degenerate PHIs.  When a degenerate PHI
+is identified and eliminated any affected statements or PHIs
+are put on a worklist.
+The second phase eliminates degenerate PHIs and trivial copies
+or constant initializations using the worklist.  This is how we
+pick up the secondary optimization opportunities with minimal
+cost.  */
+namespace {
+const pass_data pass_data_phi_only_cprop =
+{
+GIMPLE_PASS, /* type */
+"phicprop", /* name */
+OPTGROUP_NONE, /* optinfo_flags */
+TV_TREE_PHI_CPROP, /* tv_id */
+( PROP_cfg | PROP_ssa ), /* properties_required */
+0, /* properties_provided */
+0, /* properties_destroyed */
+0, /* todo_flags_start */
+( TODO_cleanup_cfg | TODO_update_ssa ), /* todo_flags_finish */
+};
+class pass_phi_only_cprop : public gimple_opt_pass
+{
+public:
+pass_phi_only_cprop (gcc::context *ctxt)
+: gimple_opt_pass (pass_data_phi_only_cprop, ctxt)
+{}
+/* opt_pass methods: */
+opt_pass * clone () { return new pass_phi_only_cprop (m_ctxt); }
+virtual bool gate (function *) { return flag_tree_dom != 0; }
+virtual unsigned int execute (function *);
+}; // class pass_phi_only_cprop
+unsigned int
+pass_phi_only_cprop::execute (function *fun)
+{
+bool cfg_altered = false;
+/* Bitmap of blocks which need EH information updated.  We can not
+update it on-the-fly as doing so invalidates the dominator tree.  */
+auto_bitmap need_eh_cleanup;
+/* INTERESTING_NAMES is effectively our worklist, indexed by
+SSA_NAME_VERSION.
+A set bit indicates that the statement or PHI node which
+defines the SSA_NAME should be (re)examined to determine if
+it has become a degenerate PHI or trivial const/copy propagation
+opportunity.
+Experiments have show we generally get better compilation
+time behavior with bitmaps rather than sbitmaps.  */
+auto_bitmap interesting_names;
+auto_bitmap interesting_names1;
+calculate_dominance_info (CDI_DOMINATORS);
+cfg_altered = false;
+/* First phase.  Eliminate degenerate PHIs via a dominator
+walk of the CFG.
+Experiments have indicated that we generally get better
+compile-time behavior by visiting blocks in the first
+phase in dominator order.  Presumably this is because walking
+in dominator order leaves fewer PHIs for later examination
+by the worklist phase.  */
+cfg_altered = eliminate_degenerate_phis_1 (ENTRY_BLOCK_PTR_FOR_FN (fun),
+					     interesting_names,
+					     need_eh_cleanup);
+/* Second phase.  Eliminate second order degenerate PHIs as well
+as trivial copies or constant initializations identified by
+the first phase or this phase.  Basically we keep iterating
+until our set of INTERESTING_NAMEs is empty.   */
+while (!bitmap_empty_p (interesting_names))
+{
+unsigned int i;
+bitmap_iterator bi;
+/* EXECUTE_IF_SET_IN_BITMAP does not like its bitmap
+	 changed during the loop.  Copy it to another bitmap and
+	 use that.  */
+bitmap_copy (interesting_names1, interesting_names);
+EXECUTE_IF_SET_IN_BITMAP (interesting_names1, 0, i, bi)
+	{
+	  tree name = ssa_name (i);
+	  /* Ignore SSA_NAMEs that have been released because
+	     their defining statement was deleted (unreachable).  */
+	  if (name)
+	    cfg_altered
+	      |= eliminate_const_or_copy (SSA_NAME_DEF_STMT (ssa_name (i)),
+					  interesting_names, need_eh_cleanup);
+	}
+}
+if (cfg_altered)
+{
+free_dominance_info (CDI_DOMINATORS);
+/* If we changed the CFG schedule loops for fixup by cfgcleanup.  */
+loops_state_set (LOOPS_NEED_FIXUP);
+}
+/* Propagation of const and copies may make some EH edges dead.  Purge
+such edges from the CFG as needed.  */
+if (!bitmap_empty_p (need_eh_cleanup))
+gimple_purge_all_dead_eh_edges (need_eh_cleanup);
+return 0;
+}
+} // anon namespace
+gimple_opt_pass *
+make_pass_phi_only_cprop (gcc::context *ctxt)
+{
+return new pass_phi_only_cprop (ctxt);
+}

Mercurial > hg > CbC > CbC_gcc

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