From a9e76ff1bc8b69e23a50d8cdc9556270cf7b269d Mon Sep 17 00:00:00 2001
From: marxin <mliska@suse.cz>
Date: Fri, 21 Oct 2016 13:26:19 +0200
Subject: [PATCH] Introduce loop store motion for UPDATE_COVERAGE_COUNTER

gcc/testsuite/ChangeLog:

2016-10-24  Martin Liska  <mliska@suse.cz>

	* gcc.dg/tree-ssa/ssa-lim-11.c: Update scanned pattern.

gcc/ChangeLog:

2016-10-24  Martin Liska  <mliska@suse.cz>

	* Makefile.in: Add new file profile-expand.c.
	* internal-fn.c (expand_UPDATE_COVERAGE_COUNTER): New IFN.
	* internal-fn.def: Likewise.
	* passes.def: Add new pass profile_expand.
	* profile-expand.c: New file.
	* tree-pass.h (make_pass_profile_expand): Declare a new
	function.
	* tree-profile.c (gimple_gen_edge_profiler): Generate the new
	internal fn.
	* tree-ssa-loop-im.c (loop_suitable_for_sm): Move to header
	file.
	(move_coverage_counter_update): New function.
	(process_sm_for_coverage_counter): Likewise.
	(pass_lim::execute): Call invariant motion for
	UPDATE_COVERAGE_COUNTER internal functions.
	* tree-ssa-loop.h: Move the function here from
	tree-ssa-loop-im.c.
	* value-prof.h: Declare expand_coverage_counter_ifns.
---
 gcc/Makefile.in                            |   1 +
 gcc/internal-fn.c                          |   6 ++
 gcc/internal-fn.def                        |   2 +
 gcc/passes.def                             |   1 +
 gcc/profile-expand.c                       | 143 ++++++++++++++++++++++++++
 gcc/testsuite/gcc.dg/tree-ssa/ssa-lim-11.c |   3 +-
 gcc/tree-pass.h                            |   1 +
 gcc/tree-profile.c                         |  37 +------
 gcc/tree-ssa-loop-im.c                     | 157 +++++++++++++++++++++++++----
 gcc/tree-ssa-loop.h                        |  18 ++++
 gcc/value-prof.h                           |   1 +
 11 files changed, 315 insertions(+), 55 deletions(-)
 create mode 100644 gcc/profile-expand.c

diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index c512cd7..9bdb406 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -1404,6 +1404,7 @@ OBJS = \
 	print-rtl-function.o \
 	print-tree.o \
 	profile.o \
+	profile-expand.o \
 	real.o \
 	realmpfr.o \
 	recog.o \
diff --git a/gcc/internal-fn.c b/gcc/internal-fn.c
index 0b32d5f..557d373 100644
--- a/gcc/internal-fn.c
+++ b/gcc/internal-fn.c
@@ -254,6 +254,12 @@ expand_FALLTHROUGH (internal_fn, gcall *call)
 	    "invalid use of attribute %<fallthrough%>");
 }
 
+static void
+expand_UPDATE_COVERAGE_COUNTER (internal_fn, gcall *)
+{
+  gcc_unreachable ();
+}
+
 /* Helper function for expand_addsub_overflow.  Return 1
    if ARG interpreted as signed in its precision is known to be always
    positive or 2 if ARG is known to be always negative, or 3 if ARG may
diff --git a/gcc/internal-fn.def b/gcc/internal-fn.def
index d4fbdb2..348fc2f 100644
--- a/gcc/internal-fn.def
+++ b/gcc/internal-fn.def
@@ -198,6 +198,8 @@ DEF_INTERNAL_FN (ATOMIC_COMPARE_EXCHANGE, ECF_LEAF | ECF_NOTHROW, NULL)
 /* To implement [[fallthrough]].  */
 DEF_INTERNAL_FN (FALLTHROUGH, ECF_LEAF | ECF_NOTHROW, NULL)
 
+DEF_INTERNAL_FN (UPDATE_COVERAGE_COUNTER, ECF_LEAF | ECF_NOTHROW, NULL)
+
 #undef DEF_INTERNAL_INT_FN
 #undef DEF_INTERNAL_FLT_FN
 #undef DEF_INTERNAL_OPTAB_FN
diff --git a/gcc/passes.def b/gcc/passes.def
index 1375254..4a22860 100644
--- a/gcc/passes.def
+++ b/gcc/passes.def
@@ -386,6 +386,7 @@ along with GCC; see the file COPYING3.  If not see
   NEXT_PASS (pass_asan_O0);
   NEXT_PASS (pass_tsan_O0);
   NEXT_PASS (pass_sanopt);
+  NEXT_PASS (pass_profile_expand);
   NEXT_PASS (pass_cleanup_eh);
   NEXT_PASS (pass_lower_resx);
   NEXT_PASS (pass_nrv);
diff --git a/gcc/profile-expand.c b/gcc/profile-expand.c
new file mode 100644
index 0000000..317fe1f
--- /dev/null
+++ b/gcc/profile-expand.c
@@ -0,0 +1,143 @@
+/* Profile expand pass.
+   Copyright (C) 2003-2016 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 "memmodel.h"
+#include "backend.h"
+#include "target.h"
+#include "tree.h"
+#include "gimple.h"
+#include "cfghooks.h"
+#include "tree-pass.h"
+#include "ssa.h"
+#include "coverage.h"
+#include "varasm.h"
+#include "tree-nested.h"
+#include "gimplify.h"
+#include "gimple-iterator.h"
+#include "gimplify-me.h"
+#include "tree-cfg.h"
+#include "tree-into-ssa.h"
+#include "value-prof.h"
+#include "profile.h"
+#include "tree-cfgcleanup.h"
+#include "params.h"
+
+void
+expand_coverage_counter_ifns (void)
+{
+  basic_block bb;
+  tree f = builtin_decl_explicit (LONG_LONG_TYPE_SIZE > 32
+				  ? BUILT_IN_ATOMIC_FETCH_ADD_8:
+				  BUILT_IN_ATOMIC_FETCH_ADD_4);
+
+  FOR_EACH_BB_FN (bb, cfun)
+    {
+      gimple_stmt_iterator gsi;
+      for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+	{
+	  gimple *stmt = gsi_stmt (gsi);
+	  if (gimple_call_internal_p (stmt, IFN_UPDATE_COVERAGE_COUNTER))
+	    {
+	      tree addr = gimple_call_arg (stmt, 0);
+	      tree value = gimple_call_arg (stmt, 1);
+	      if (flag_profile_update == PROFILE_UPDATE_ATOMIC)
+		{
+		  gcall *stmt
+		    = gimple_build_call (f, 3, addr, value,
+					 build_int_cst (integer_type_node,
+							MEMMODEL_RELAXED));
+		  gsi_replace (&gsi, stmt, true);
+		}
+	      else
+		{
+		  gcc_assert (TREE_CODE (addr) == ADDR_EXPR);
+		  tree ref = TREE_OPERAND (addr, 0);
+		  tree gcov_type_tmp_var
+		    = make_temp_ssa_name (get_gcov_type (), NULL,
+					  "PROF_edge_counter");
+		  gassign *stmt1 = gimple_build_assign (gcov_type_tmp_var, ref);
+		  gcov_type_tmp_var
+		    = make_temp_ssa_name (get_gcov_type (), NULL,
+					  "PROF_edge_counter");
+		  gassign *stmt2
+		    = gimple_build_assign (gcov_type_tmp_var, PLUS_EXPR,
+					   gimple_assign_lhs (stmt1), value);
+		  gassign *stmt3
+		    = gimple_build_assign (unshare_expr (ref),
+					   gimple_assign_lhs (stmt2));
+		  gsi_insert_seq_before (&gsi, stmt1, GSI_SAME_STMT);
+		  gsi_insert_seq_before (&gsi, stmt2, GSI_SAME_STMT);
+		  gsi_replace (&gsi, stmt3, GSI_SAME_STMT);
+		}
+	    }
+	}
+    }
+}
+
+/* Profile expand pass.  */
+
+namespace {
+
+const pass_data pass_data_profile_expand =
+{
+  GIMPLE_PASS, /* type */
+  "profile_expand", /* name */
+  OPTGROUP_LOOP, /* optinfo_flags */
+  TV_LIM, /* tv_id */
+  PROP_cfg, /* properties_required */
+  0, /* properties_provided */
+  0, /* properties_destroyed */
+  0, /* todo_flags_start */
+  TODO_update_ssa, /* todo_flags_finish */
+};
+
+class pass_profile_expand : public gimple_opt_pass
+{
+public:
+  pass_profile_expand (gcc::context *ctxt)
+    : gimple_opt_pass (pass_data_profile_expand, ctxt)
+  {}
+
+  /* opt_pass methods: */
+  opt_pass * clone () { return new pass_profile_expand (m_ctxt); }
+  virtual bool gate (function *) { return true; }
+  virtual unsigned int execute (function *);
+
+}; // class pass_profile_expand
+
+unsigned int
+pass_profile_expand::execute (function *)
+{
+  expand_coverage_counter_ifns ();
+
+  return 0;
+}
+
+} // anon namespace
+
+gimple_opt_pass *
+make_pass_profile_expand (gcc::context *ctxt)
+{
+  return new pass_profile_expand (ctxt);
+}
+
+
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-lim-11.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-lim-11.c
index e4c11aa..4c14e24 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/ssa-lim-11.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-lim-11.c
@@ -22,4 +22,5 @@ void access_buf(struct thread_param* p)
     }
 }
 
-/* { dg-final { scan-tree-dump-times "Executing store motion of __gcov0.access_buf\\\[\[01\]\\\] from loop 1" 2 "lim2" } } */
+/* { dg-final { scan-tree-dump-times "Executing store motion of &__gcov0.access_buf\\\[\[01\]\\\] from loop 1" 1 "lim2" } } */
+/* { dg-final { scan-tree-dump-times "Executing store motion of &__gcov0.access_buf\\\[\[01\]\\\] from loop 2" 1 "lim2" } } */
diff --git a/gcc/tree-pass.h b/gcc/tree-pass.h
index 5903fde..ac919f8 100644
--- a/gcc/tree-pass.h
+++ b/gcc/tree-pass.h
@@ -365,6 +365,7 @@ extern gimple_opt_pass *make_pass_fix_loops (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_tree_loop (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_tree_no_loop (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_tree_loop_init (gcc::context *ctxt);
+extern gimple_opt_pass *make_pass_profile_expand (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_lim (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_tree_unswitch (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_predcom (gcc::context *ctxt);
diff --git a/gcc/tree-profile.c b/gcc/tree-profile.c
index abeee92..288d38c 100644
--- a/gcc/tree-profile.c
+++ b/gcc/tree-profile.c
@@ -252,40 +252,13 @@ gimple_init_edge_profiler (void)
 void
 gimple_gen_edge_profiler (int edgeno, edge e)
 {
-  tree one;
+  tree one = build_int_cst (gcov_type_node, 1);
 
-  one = build_int_cst (gcov_type_node, 1);
-
-  if (flag_profile_update == PROFILE_UPDATE_ATOMIC)
-    {
-      /* __atomic_fetch_add (&counter, 1, MEMMODEL_RELAXED); */
-      tree addr = tree_coverage_counter_addr (GCOV_COUNTER_ARCS, edgeno);
-      tree f = builtin_decl_explicit (LONG_LONG_TYPE_SIZE > 32
-				      ? BUILT_IN_ATOMIC_FETCH_ADD_8:
-				      BUILT_IN_ATOMIC_FETCH_ADD_4);
-      gcall *stmt = gimple_build_call (f, 3, addr, one,
-				       build_int_cst (integer_type_node,
-						      MEMMODEL_RELAXED));
-      gsi_insert_on_edge (e, stmt);
-    }
-  else
-    {
-      tree ref = tree_coverage_counter_ref (GCOV_COUNTER_ARCS, edgeno);
-      tree gcov_type_tmp_var = make_temp_ssa_name (gcov_type_node,
-						   NULL, "PROF_edge_counter");
-      gassign *stmt1 = gimple_build_assign (gcov_type_tmp_var, ref);
-      gcov_type_tmp_var = make_temp_ssa_name (gcov_type_node,
-					      NULL, "PROF_edge_counter");
-      gassign *stmt2 = gimple_build_assign (gcov_type_tmp_var, PLUS_EXPR,
-					    gimple_assign_lhs (stmt1), one);
-      gassign *stmt3 = gimple_build_assign (unshare_expr (ref),
-					    gimple_assign_lhs (stmt2));
-      gsi_insert_on_edge (e, stmt1);
-      gsi_insert_on_edge (e, stmt2);
-      gsi_insert_on_edge (e, stmt3);
-    }
+  tree addr = tree_coverage_counter_addr (GCOV_COUNTER_ARCS, edgeno);
+  gcall *stmt = gimple_build_call_internal (IFN_UPDATE_COVERAGE_COUNTER,
+					    2, addr, one);
+  gsi_insert_on_edge (e, stmt);
 }
-
 /* Emits code to get VALUE to instrument at GSI, and returns the
    variable containing the value.  */
 
diff --git a/gcc/tree-ssa-loop-im.c b/gcc/tree-ssa-loop-im.c
index 463db04..0e04250 100644
--- a/gcc/tree-ssa-loop-im.c
+++ b/gcc/tree-ssa-loop-im.c
@@ -44,6 +44,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "trans-mem.h"
 #include "gimple-fold.h"
 #include "tree-scalar-evolution.h"
+#include "coverage.h"
 
 /* TODO:  Support for predicated code motion.  I.e.
 
@@ -2281,24 +2282,6 @@ find_refs_for_sm (struct loop *loop, bitmap sm_executed, bitmap refs_to_sm)
     }
 }
 
-/* Checks whether LOOP (with exits stored in EXITS array) is suitable
-   for a store motion optimization (i.e. whether we can insert statement
-   on its exits).  */
-
-static bool
-loop_suitable_for_sm (struct loop *loop ATTRIBUTE_UNUSED,
-		      vec<edge> exits)
-{
-  unsigned i;
-  edge ex;
-
-  FOR_EACH_VEC_ELT (exits, i, ex)
-    if (ex->flags & (EDGE_ABNORMAL | EDGE_EH))
-      return false;
-
-  return true;
-}
-
 /* Try to perform store motion for all memory references modified inside
    LOOP.  SM_EXECUTED is the bitmap of the memory references for that
    store motion was executed in one of the outer loops.  */
@@ -2556,6 +2539,132 @@ tree_ssa_lim (void)
   return todo;
 }
 
+/* Move coverage counter update internal function, pointed by GSI iterator,
+   out of a loop LOOP.  */
+
+static void
+move_coverage_counter_update (gimple_stmt_iterator *gsi, struct loop *loop)
+{
+  gimple *call = gsi_stmt (*gsi);
+  tree type = get_gcov_type ();
+
+  vec<edge> exits = get_loop_exit_edges (loop);
+  if (!loop_suitable_for_sm (loop, exits))
+    {
+      exits.release ();
+      return;
+    }
+
+  /* Verify that BB of the CALL statement post-dominates all exits.  */
+  for (unsigned i = 0; i < exits.length (); i++)
+    {
+      edge exit = exits[i];
+      if (!dominated_by_p (CDI_POST_DOMINATORS, call->bb, exit->src))
+	{
+	  exits.release ();
+	  return;
+	}
+    }
+
+  if (exits.is_empty ())
+    return;
+
+  edge preheader = loop_preheader_edge (loop);
+  if (!single_succ_p (preheader->src)
+      || preheader->dest != call->bb)
+    return;
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    {
+      fprintf (dump_file, "Executing store motion of ");
+      print_generic_expr (dump_file, gimple_call_arg (call, 0), 0);
+      fprintf (dump_file, " from loop %d\n", loop->num);
+    }
+
+  tree preheader_var = make_temp_ssa_name (type, NULL, "PROF_edge_counter");
+  gimple *stmt = gimple_build_assign (preheader_var, build_int_cst (type, 0));
+  gimple_stmt_iterator it = gsi_last_bb (preheader->src);
+  gsi_insert_after (&it, stmt, GSI_NEW_STMT);
+
+  tree loop_var1 = make_temp_ssa_name (type, NULL, "PROF_edge_counter");
+  tree loop_var2 = make_temp_ssa_name (type, NULL, "PROF_edge_counter");
+
+  gphi *phi = create_phi_node (loop_var1, call->bb);
+  add_phi_arg (phi, preheader_var, preheader, UNKNOWN_LOCATION);
+
+  stmt = gimple_build_assign (loop_var2, PLUS_EXPR, loop_var1,
+			      build_int_cst (type, 1));
+  gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
+
+  edge e;
+  edge_iterator ei;
+  FOR_EACH_EDGE (e, ei, call->bb->preds)
+    if (e != preheader)
+      add_phi_arg (phi, loop_var2, e, UNKNOWN_LOCATION);
+
+  tree updated_value = make_temp_ssa_name (type, NULL, "PROF_edge_counter");
+
+  for (unsigned i = 0; i < exits.length (); i++)
+    {
+      edge exit = exits[i];
+      if (!dominated_by_p (CDI_DOMINATORS, exit->dest, exit->src))
+	{
+	  basic_block new_bb = split_edge (exit);
+	  set_immediate_dominator (CDI_DOMINATORS, new_bb, exit->src);
+	  e = single_pred_edge (new_bb);
+	}
+      else
+	e = exit;
+
+      basic_block bb = e->dest;
+      phi = create_phi_node (updated_value, e->dest);
+      add_phi_arg (phi, loop_var2, e, UNKNOWN_LOCATION);
+
+      tree addr = unshare_expr (gimple_call_arg (call, 0));
+      call = gimple_build_call_internal (IFN_UPDATE_COVERAGE_COUNTER,
+					 2, addr, gimple_phi_result (phi));
+
+      it = gsi_start_bb (bb);
+      gsi_insert_before (&it, call, GSI_NEW_STMT);
+    }
+
+  exits.release ();
+  gsi_remove (gsi, true);
+}
+
+/* Process store motion for coverage counter update internal function.  */
+
+static void
+process_sm_for_coverage_counter (void)
+{
+  bool has_dom_info = dom_info_available_p (CDI_POST_DOMINATORS);
+  if (!has_dom_info)
+    calculate_dominance_info (CDI_POST_DOMINATORS);
+
+  struct loop *loop;
+  FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
+    {
+      basic_block *body = get_loop_body (loop);
+      for (unsigned i = 0; i < loop->num_nodes; i++)
+	{
+	  gimple_stmt_iterator gsi;
+	  for (gsi = gsi_start_bb (body[i]); !gsi_end_p (gsi);)
+	    {
+	      gimple *stmt = gsi_stmt (gsi);
+	      if (gimple_call_internal_p (stmt, IFN_UPDATE_COVERAGE_COUNTER)
+		  && integer_onep (gimple_call_arg (stmt, 1)))
+		move_coverage_counter_update (&gsi, loop);
+
+	      if (!gsi_end_p (gsi))
+		gsi_next (&gsi);
+	    }
+	}
+    }
+
+  if (!has_dom_info)
+    free_dominance_info (CDI_POST_DOMINATORS);
+}
+
 /* Loop invariant motion pass.  */
 
 namespace {
@@ -2592,11 +2701,15 @@ pass_lim::execute (function *fun)
 {
   bool in_loop_pipeline = scev_initialized_p ();
   if (!in_loop_pipeline)
-    loop_optimizer_init (LOOPS_NORMAL | LOOPS_HAVE_RECORDED_EXITS);
+    loop_optimizer_init (LOOPS_NORMAL | LOOPS_HAVE_RECORDED_EXITS
+			 | LOOPS_HAVE_PREHEADERS);
 
-  if (number_of_loops (fun) <= 1)
-    return 0;
-  unsigned int todo = tree_ssa_lim ();
+  unsigned int todo = 0;
+  if (number_of_loops (fun) > 1)
+    todo = tree_ssa_lim ();
+
+  process_sm_for_coverage_counter ();
+  todo |= TODO_update_ssa;
 
   if (!in_loop_pipeline)
     loop_optimizer_finalize ();
diff --git a/gcc/tree-ssa-loop.h b/gcc/tree-ssa-loop.h
index b2f37ab..88bcad7 100644
--- a/gcc/tree-ssa-loop.h
+++ b/gcc/tree-ssa-loop.h
@@ -79,4 +79,22 @@ loop_containing_stmt (gimple *stmt)
   return bb->loop_father;
 }
 
+/* Checks whether LOOP (with exits stored in EXITS array) is suitable
+   for a store motion optimization (i.e. whether we can insert statement
+   on its exits).  */
+
+static inline bool
+loop_suitable_for_sm (struct loop *loop ATTRIBUTE_UNUSED,
+		      vec<edge> exits)
+{
+  unsigned i;
+  edge ex;
+
+  FOR_EACH_VEC_ELT (exits, i, ex)
+    if (ex->flags & (EDGE_ABNORMAL | EDGE_EH))
+      return false;
+
+  return true;
+}
+
 #endif /* GCC_TREE_SSA_LOOP_H */
diff --git a/gcc/value-prof.h b/gcc/value-prof.h
index 07e2b3b..cb3ae1d 100644
--- a/gcc/value-prof.h
+++ b/gcc/value-prof.h
@@ -98,6 +98,7 @@ bool check_ic_target (gcall *, struct cgraph_node *);
 /* In tree-profile.c.  */
 extern void gimple_init_edge_profiler (void);
 extern void gimple_gen_edge_profiler (int, edge);
+extern void expand_coverage_counter_ifns (void);
 extern void gimple_gen_interval_profiler (histogram_value, unsigned, unsigned);
 extern void gimple_gen_pow2_profiler (histogram_value, unsigned, unsigned);
 extern void gimple_gen_one_value_profiler (histogram_value, unsigned, unsigned);
-- 
2.10.1

