noloopalias: Add new pass to optimise loops.gcc-8_2_0-amp2-branch

This pass allows to declare pointer non-aliasing on loop level
within the given function.

If such non-aliasing is given, then we outline the loop into
its own function. The arguments of the new function are all
variables, which are used in the loop, where pointers are
declared as restricted types (non-aliasing).

This allows to optimize the loop more aggressively.

Signed-off-by: Christoph Muellner <christoph.muellner@theobroma-systems.com>

6 files changed, 633 insertions, 0 deletions

diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index 42adaef66213..0a2721ef938e 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -1587,6 +1587,7 @@ OBJS = \
 	tree-vrp.o \
 	tree.o \
 	typed-splay-tree.o \
+        uninline-innermost-loops.o \
 	unique-ptr-tests.o \
 	uncse.o \
 	valtrack.o \
diff --git a/gcc/common.opt b/gcc/common.opt
index c6d92b503c47..f230412db1fa 100644
--- a/gcc/common.opt
+++ b/gcc/common.opt
@@ -2719,6 +2719,11 @@ fvectorize-more
 Common Report Var(flag_vectorize_more) Optimization
 Vectorize a bit more.
 
+fnoloopalias=
+Common Report Joined Var(noloopalias) Init(0)
+Restrict pointer aliasing for given function's loops
+(allows more aggressive optimisations).
+
 funwind-tables
 Common Report Var(flag_unwind_tables) Optimization
 Just generate unwind tables for exception handling.
diff --git a/gcc/passes.def b/gcc/passes.def
index fe81b405f140..1258c442e4e3 100644
--- a/gcc/passes.def
+++ b/gcc/passes.def
@@ -45,6 +45,7 @@ along with GCC; see the file COPYING3.  If not see
   NEXT_PASS (pass_sprintf_length, false);
   NEXT_PASS (pass_walloca, /*strict_mode_p=*/true);
   NEXT_PASS (pass_build_cgraph_edges);
+  NEXT_PASS (pass_uninline_innermost_loops);
   TERMINATE_PASS_LIST (all_lowering_passes)
 
   /* Interprocedural optimization passes.  */
diff --git a/gcc/timevar.def b/gcc/timevar.def
index 1e56e5014870..8e1091670863 100644
--- a/gcc/timevar.def
+++ b/gcc/timevar.def
@@ -193,6 +193,7 @@ DEFTIMEVAR (TV_LOOP_JAM              , "unroll and jam")
 DEFTIMEVAR (TV_COMPLETE_UNROLL       , "complete unrolling")
 DEFTIMEVAR (TV_TREE_PARALLELIZE_LOOPS, "tree parallelize loops")
 DEFTIMEVAR (TV_TREE_VECTORIZATION    , "tree vectorization")
+DEFTIMEVAR (TV_UNINLINE_INNERMOST_LOOPS, "uninline innermost loops")
 DEFTIMEVAR (TV_TREE_SLP_VECTORIZATION, "tree slp vectorization")
 DEFTIMEVAR (TV_GRAPHITE              , "Graphite")
 DEFTIMEVAR (TV_GRAPHITE_TRANSFORMS   , "Graphite loop transforms")
diff --git a/gcc/tree-pass.h b/gcc/tree-pass.h
index abf6c4cfe3c3..aab90403ddba 100644
--- a/gcc/tree-pass.h
+++ b/gcc/tree-pass.h
@@ -382,6 +382,7 @@ extern gimple_opt_pass *make_pass_if_conversion (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_loop_distribution (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_vectorize (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_simduid_cleanup (gcc::context *ctxt);
+extern gimple_opt_pass *make_pass_uninline_innermost_loops (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_slp_vectorize (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_complete_unroll (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_complete_unrolli (gcc::context *ctxt);
diff --git a/gcc/uninline-innermost-loops.c b/gcc/uninline-innermost-loops.c
new file mode 100644
index 000000000000..d81a3307c8a4
--- /dev/null
+++ b/gcc/uninline-innermost-loops.c
@@ -0,0 +1,624 @@
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "hash-set.h"
+#include "machmode.h"
+#include "vec.h"
+#include "double-int.h"
+#include "input.h"
+#include "alias.h"
+#include "symtab.h"
+#include "options.h"
+#include "wide-int.h"
+#include "inchash.h"
+#include "tree.h"
+#include "fold-const.h"
+#include "hashtab.h"
+#include "tm.h"
+#include "hard-reg-set.h"
+#include "function.h"
+#include "rtl.h"
+#include "flags.h"
+#include "statistics.h"
+#include "real.h"
+#include "fixed-value.h"
+#include "insn-config.h"
+#include "expmed.h"
+#include "predict.h"
+#include "dojump.h"
+#include "explow.h"
+#include "calls.h"
+#include "varasm.h"
+#include "stmt.h"
+#include "expr.h"
+#include "gimple-pretty-print.h"
+#include "predict.h"
+#include "dominance.h"
+#include "cfg.h"
+#include "cfgloop.h"
+#include "cfghooks.h"
+#include "basic-block.h"
+#include "tree-ssa-alias.h"
+#include "internal-fn.h"
+#include "gimple-expr.h"
+#include "is-a.h"
+#include "gimple.h"
+#include "gimplify.h"
+#include "gimple-iterator.h"
+#include "tree-cfg.h"
+#include "gimplify-me.h"
+#include "gimple-ssa.h"
+#include "tree-ssa-operands.h"
+#include "tree-phinodes.h"
+#include "ssa-iterators.h"
+#include "dumpfile.h"
+#include "tree-pass.h"
+#include "ipa-ref.h"
+#include "plugin-api.h"
+#include "cgraph.h"
+#include "function.h"
+#include "tree-ssa.h"
+#include "tree-into-ssa.h"
+
+typedef vec<tree> expr_vec;
+
+const char *uninlined_function_postfix = "innermost_loop";
+
+/* Given stmt is an assign statement and given op is its LHS.  */
+
+static bool
+is_defined_in_stmt (const gimple *stmt, const tree op)
+{
+  tree lhs;
+  if (gimple_code (stmt) == GIMPLE_ASSIGN)
+    {
+      lhs = gimple_assign_lhs (stmt);
+      if (lhs == op)
+        return true;
+    }
+  return false;
+}
+
+/* Check if op is LHS of assignment within current bb.  */
+
+static bool
+is_defined_inside (gimple *stmt, const tree op)
+{
+  gimple_stmt_iterator gsi;
+
+  /* Get a gsi for the bb stmt belongs to (pointing to stmt).  */
+  gsi = gsi_for_stmt (stmt);
+
+  /* Start search in previous stmt.  */
+  gsi_prev (&gsi);
+
+  /* Iterate over all previous stmts in bb.  */
+  for (; !gsi_end_p (gsi); gsi_prev (&gsi))
+    {
+      if (is_defined_in_stmt (gsi_stmt (gsi), op))
+        return true;
+    }
+  return false;
+}
+
+typedef void (*op_callback) (void *g, tree op, gimple *stmt, unsigned index);
+
+/* Call cb with arg g for each operand of each statement of each bb of the loop.  */
+
+static void
+for_each_operand_in_loop (const struct loop *loop, op_callback cb, void *g)
+{
+  basic_block *bbs;
+  unsigned num_nodes;
+  unsigned i;
+
+  /* Get the basic blocks.  */
+  bbs = get_loop_body (loop);
+  num_nodes = loop->num_nodes;
+
+  /* Iterate over basic blocks. */
+  for (i = 0; i < num_nodes; i++)
+    {
+      basic_block bb;
+      bb = bbs[i];
+
+      /* Iterate over statements in bb.  */
+      gimple_stmt_iterator iter = gsi_start_bb (bb);
+      for ( ; !gsi_end_p (iter); gsi_next (&iter))
+	{
+	  gimple *stmt;
+	  unsigned j;
+	  stmt = gsi_stmt (iter);
+
+	  /* Iterate over operands in bb.  */
+	  for (j = 0; j < gimple_num_ops (stmt); j++)
+	    {
+	      tree op;
+	      op = gimple_op (stmt, j);
+	      if (op)
+		{
+		  /* Here is the callback. */
+		  cb (g, op, stmt, j);
+		}
+	    }
+	}
+    }
+
+  /* Free the bb list.  */
+  free (bbs);
+}
+
+/* Add operand to vector if:
+    - it is not LHS of assignment, and
+    - op is VAR_DECL or PARM_DECL, and
+    - op is not yet in v, and
+    - op is not defined inside of stmt's bb.  */
+
+static void
+collect_cb (void *g, tree op, gimple *stmt, unsigned index)
+{
+  expr_vec *v = (expr_vec *) g;
+  enum tree_code code;
+
+  if (dump_file)
+    fprintf (dump_file, "%s: Entering.\n", __func__);
+
+  /* Filter out LHS of assignments.  */
+  if (gimple_code (stmt) == GIMPLE_ASSIGN && index == 0)
+    {
+      if (dump_file)
+        fprintf (dump_file, "Filtering out LHS of assignment.\n");
+      return;
+    }
+
+  code = TREE_CODE (op);
+
+  /* Filter out op, which are not VAR_DECL or PARM_DECL.  */
+  if (code != VAR_DECL && code != PARM_DECL)
+    {
+      if (dump_file)
+        fprintf (dump_file, "Filtering out op, which is not (VAR_DECL or PARM_DECL).\n");
+       return;
+    }
+
+  /* Filter out if op already included.  */
+  if (v->contains (op))
+    {
+      if (dump_file)
+        fprintf (dump_file, "Filtering out op, which is arleady included.\n");
+       return;
+    }
+
+  /* Filter out ops, which are defined inside bb. */
+  if (is_defined_inside (stmt, op))
+    {
+      if (dump_file)
+        fprintf (dump_file, "Filtering out op, which is defined inside bb.\n");
+       return;
+    }
+
+  if (dump_file)
+    {
+    fprintf (dump_file, "Calling safe_push() for op ");
+      const char *name = "<unknown name>";
+      if (DECL_NAME(op) && IDENTIFIER_POINTER (DECL_NAME (op)))
+	name = identifier_to_locale (IDENTIFIER_POINTER (DECL_NAME (op)));
+      fprintf (dump_file, "'%s'\n", name);
+    }
+
+  v->safe_push(op);
+}
+
+/* Return unique list of operands in the given loop,
+   which are defined outside of the loop.  */
+
+static expr_vec
+collect_def_outside (struct loop *loop)
+{
+  expr_vec v = vNULL;
+
+  if (dump_file)
+    fprintf (dump_file, "%s: Entering.\n", __func__);
+
+  for_each_operand_in_loop (loop, collect_cb, (void *) &v);
+  return v;
+}
+
+/* Set boolean to true if:
+    - stmt is GIMPLE_CALL.  */
+
+static void
+contains_call_cb (void *r, tree, gimple *stmt, unsigned)
+{
+  bool *ret = (bool *) r;
+  if (gimple_code (stmt) == GIMPLE_CALL)
+    *ret = true;
+}
+
+/* Return true if loop contains a call statement with operands.  */
+
+static bool
+contains_call (struct loop *loop)
+{
+  bool ret = false;
+  for_each_operand_in_loop (loop, contains_call_cb, (void *) &ret);
+  return ret;
+}
+
+struct var_to_parm_cb_p
+{
+  tree d;
+  tree d_parm;
+};
+
+/* Replace op in stmt by p->d_parm if op == p->d.  */
+
+static void
+var_to_parm_cb (void *g, tree op, gimple *stmt, unsigned index)
+{
+  struct var_to_parm_cb_p *p = (struct var_to_parm_cb_p *) g;
+
+  if (p->d == op)
+    {
+      gimple_set_op (stmt, index, p->d_parm);
+    }
+}
+
+/* Replace ops in all stmts of loop by p->d_parm if op == p->d.  */
+
+static void
+convert_var_to_parm_uses (struct loop *loop, tree d, tree d_parm)
+{
+  struct var_to_parm_cb_p c;
+  c.d = d;
+  c.d_parm = d_parm;
+  for_each_operand_in_loop (loop, var_to_parm_cb, (void *) &c);
+}
+
+/* Create a function declaration with void return type.  */
+
+static tree
+build_void_function_declaration (struct loop *loop, tree name, expr_vec parameter_vector, vec<tree> *args)
+{
+  /* We use NULL_TREE as placeholder here.
+     This will be fixed later on.  */
+  tree type = NULL_TREE;
+
+  /* Create the function declaration.  */
+  tree decl = build_decl (input_location, FUNCTION_DECL, name, type);
+
+  TREE_STATIC (decl) = 1;
+  TREE_USED (decl) = 1;
+  DECL_ARTIFICIAL (decl) = 1;
+  DECL_NAMELESS (decl) = 0;
+  DECL_IGNORED_P (decl) = 0;
+  TREE_PUBLIC (decl) = 0;
+  DECL_UNINLINABLE (decl) = 1;
+  DECL_EXTERNAL (decl) = 0;
+  DECL_CONTEXT (decl) = NULL_TREE;
+  DECL_INITIAL (decl) = make_node (BLOCK);
+  BLOCK_SUPERCONTEXT (DECL_INITIAL (decl)) = decl;
+  DECL_ATTRIBUTES (decl) = DECL_ATTRIBUTES (cfun->decl);
+
+  /* Create result declaration.  */
+  tree t = build_decl (DECL_SOURCE_LOCATION (decl),
+		  RESULT_DECL, NULL_TREE, void_type_node);
+
+  DECL_ARTIFICIAL (t) = 1;
+  DECL_IGNORED_P (t) = 1;
+  DECL_CONTEXT (t) = decl;
+  DECL_RESULT (decl) = t;
+
+  /* Now we prepare several collections from the parameter vector.  */
+
+  tree t_first = NULL; /* First element of decl chain.  */
+  tree t_last = NULL; /* Last element of decl chain.  */
+  tree types = NULL_TREE; /* TREE_LIST of types.  */
+  tree *pp = &types; /* Helper to create the TREE_LIST. */
+
+  /* Prepare the arguments collected earlier on.  */
+  int i = -1;
+  tree d = NULL;
+  FOR_EACH_VEC_ELT (parameter_vector, i, d)
+    {
+      /* Append parameter to args vector.  */
+      args->safe_push (d);
+
+      /* Get parameter type.  */
+      tree type_new = copy_node (TREE_TYPE (d));
+
+      /* Append type to tree list.  */
+      *pp = build_tree_list (NULL, type_new);
+      pp = &TREE_CHAIN (*pp);
+
+      /* Allocate and initialize parameter declaration.  */
+      tree d_parm = build_decl (DECL_SOURCE_LOCATION (decl), PARM_DECL,
+                           DECL_NAME (d), type_new);
+      DECL_ARG_TYPE (d_parm) = TREE_TYPE (d);
+      DECL_ARTIFICIAL (d_parm) = 1;
+      DECL_CONTEXT (d_parm) = decl;
+      if (POINTER_TYPE_P (TREE_TYPE (d)))
+	TYPE_RESTRICT (TREE_TYPE (d_parm)) = 1;
+
+      if (dump_file)
+	{
+	  const char *name = "<unknown name>";
+	  tree t TREE_TYPE (d);
+	  int isptr = 0;
+	  if (DECL_NAME(d) && IDENTIFIER_POINTER (DECL_NAME (d)))
+	    {
+	      name = identifier_to_locale (IDENTIFIER_POINTER (DECL_NAME (d)));
+	      isptr = POINTER_TYPE_P (t);
+	    }
+	  fprintf (dump_file, "Parameter %s isptr=%i\n", name, isptr);
+	}
+
+      /* Convert the loop to use the parameters.  */
+      convert_var_to_parm_uses (loop, d, d_parm);
+
+      if (!t_first)
+        {
+          t_first = d_parm;
+          t_last = d_parm;
+        }
+      else
+        {
+          DECL_CHAIN (t_last) = d_parm;
+          t_last = d_parm;
+        }
+    }
+
+  /* Replace the placeholder type by the actual type (void f(args...)).  */
+  type = build_function_type (void_type_node, types);
+  TREE_TYPE (decl) = type;
+  DECL_ARGUMENTS (decl) = t_first;
+
+  /* Allocate memory for the function structure.  The call to
+     allocate_struct_function clobbers CFUN, so we need to restore
+     it afterward.  */
+  push_struct_function (decl);
+  cfun->function_end_locus = DECL_SOURCE_LOCATION (decl);
+  init_tree_ssa (cfun);
+  pop_cfun ();
+
+  return decl;
+}
+
+/* Converts the loop body into its own function
+ * with the given arguments.
+ *
+ * This is inspired by create_omp_child_function and create_loop_fn.  */
+
+static void
+body_to_fun (struct loop *loop, expr_vec parameter_vector)
+{
+  /* Build function declaration.  */
+  tree name = clone_function_name (cfun->decl, uninlined_function_postfix);
+  vec<tree> args = vNULL; /* Vector of parameters. */
+  tree decl = build_void_function_declaration (loop, name, parameter_vector, &args);
+
+  /* Fill the function body.  */
+  gimple_seq body = NULL;
+  gimple *bind = gimple_build_bind (NULL, body, DECL_INITIAL (decl));
+  gimple_seq_add_stmt (&body, bind);
+
+  /* We'll create a CFG for child_fn, so no gimple body is needed.  */
+  gimple_set_body (decl, body);
+
+  struct function *child_cfun = DECL_STRUCT_FUNCTION (decl);
+
+  /* We need a SESE (single entry - single exit) region to ease the outlining.  */
+
+  basic_block in_bb = create_preheader (loop, CP_FORCE_PREHEADERS);
+
+  if (dump_file)
+    {
+      fprintf (dump_file, "%s: in_bb: %i\n", __func__, in_bb->index);
+      fprintf (dump_file, "%s: loop->header: %i\n", __func__, loop->header->index);
+      fprintf (dump_file, "%s: loop->latch: %i\n", __func__, loop->latch->index);
+    }
+
+  edge out = single_exit (loop);
+  if (!out)
+    {
+      if (dump_file)
+        fprintf (dump_file, "Loop does not have a single exit!\n");
+    }
+
+  gcc_assert (out != NULL);
+
+  if (dump_file)
+    {
+      fprintf (dump_file, "%s: Exit edge src: %i.\n", __func__, out->src->index);
+      fprintf (dump_file, "%s: Exit edge dest: %i.\n", __func__, out->dest->index);
+    }
+
+  basic_block out_bb = split_edge (out);
+
+  if (dump_file)
+    {
+      fprintf (dump_file, "%s: out_bb: %i\n", __func__, out_bb->index);
+    }
+
+  /* Move the single-entry-single-exit region into its own function.
+     We get the new BB in the original function (which returns
+     the "factored-out" region.  */
+  basic_block new_bb = move_sese_region_to_fn (child_cfun, in_bb,
+                                   out_bb, NULL_TREE);
+
+  if (dump_file)
+    {
+      fprintf (dump_file, "%s: new_bb: %i\n", __func__, new_bb->index);
+      fprintf (dump_file, "new_bb has %u edges: ", EDGE_COUNT(new_bb->preds));
+      edge p;
+      edge_iterator ei;
+      FOR_EACH_EDGE (p, ei, new_bb->preds)
+        {
+	  basic_block runner = p->src;
+	  fprintf (dump_file, "bb%i, ", runner->index);
+	}
+      fprintf(dump_file, "-\n");
+    }
+
+  /* Add call statement into new bb */
+  gimple *call_stmt = gimple_build_call_vec (decl, args);
+  gimple_stmt_iterator call_iter = gsi_start_bb (new_bb);
+  gsi_insert_after (&call_iter, call_stmt, GSI_NEW_STMT);
+
+  /* Add return statement into new exit bb.  */
+  gimple *stmt = gimple_build_return (NULL);
+  gimple_stmt_iterator gsi = gsi_last_bb(out_bb);
+  gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
+
+  /* Copy function properties */
+  child_cfun->curr_properties = cfun->curr_properties;
+
+  /* Create the new function call graph node */
+  cgraph_node::get_create (decl);
+  /* Make the new function known. */
+  cgraph_node::add_new_function (decl, true);
+
+  /* Edge fixup */
+  update_max_bb_count ();
+  cgraph_edge::rebuild_edges ();
+
+  if (gimple_in_ssa_p (cfun))
+    {
+      if (dump_file)
+	fprintf (dump_file, "gimple_in_ssa_p(cfun) is true\n");
+      update_ssa (TODO_update_ssa);
+    }
+  else
+    {
+      if (dump_file)
+	fprintf (dump_file, "gimple_in_ssa_p(cfun) is false\n");
+    }
+
+
+  push_cfun (child_cfun);
+  update_max_bb_count ();
+  cgraph_edge::rebuild_edges ();
+
+  if (gimple_in_ssa_p (cfun))
+    {
+      if (dump_file)
+	fprintf (dump_file, "gimple_in_ssa_p(child) is true\n");
+      update_ssa (TODO_update_ssa);
+    }
+  else
+    {
+      if (dump_file)
+	fprintf (dump_file, "gimple_in_ssa_p(child) is false\n");
+    }
+
+  pop_cfun ();
+}
+
+static unsigned int
+extract_loop_to_function ()
+{
+  struct loop *loop;
+  struct loop *lu;
+  expr_vec v = vNULL;
+  unsigned n;
+
+  lu = NULL;
+
+  /* First create the list of loop exits of cfun
+     (searches all edges of all bb in cfun).  */
+  record_loop_exits ();
+
+  n = 0;
+  FOR_EACH_LOOP_FN (cfun, loop, LI_ONLY_INNERMOST)
+    {
+      /* We need single-entry single-exit loops.  */
+      if (!single_exit (loop))
+	continue;
+      if (EDGE_COUNT(loop->header->preds) > 2)
+	continue;
+
+      /* We can't deal with calls inside of loops.  */
+      if (contains_call (loop))
+	continue;
+
+      if (n < loop->num_nodes)
+	{
+	  n = loop->num_nodes;
+	  lu = loop;
+	}
+    }
+
+  if (lu)
+    {
+      const char *fun_to_uninline = noloopalias;
+      if (dump_file)
+        fprintf (dump_file,
+                 "%s:%d (%s): uninlining in %s\n",
+                 __FILE__, __LINE__, __func__, fun_to_uninline);
+
+      /* First we get a unique list of operands in the loop,
+         which are defined outside of the loop.  */
+      v = collect_def_outside (lu);
+
+      /* Now we create a new function with the given list of arguments.  */
+      body_to_fun (lu, v);
+    }
+
+  /* Free the list of loop exits of cfun. */
+  release_recorded_exits (cfun);
+
+  return 0;
+}
+
+namespace {
+
+const pass_data pass_data_uninline_innermost_loops =
+{
+  GIMPLE_PASS, /* type */
+  "uninline-innermost-loops", /* name */
+  OPTGROUP_NONE, /* optinfo_flags */
+  TV_UNINLINE_INNERMOST_LOOPS, /* tv_id */
+  PROP_gimple_any, /* properties_required */
+  0, /* properties_provided */
+  0, /* properties_destroyed */
+  0, /* todo_flags_start */
+  0, /* todo_flags_finish */
+};
+
+class pass_uninline_innermost_loops: public gimple_opt_pass
+{
+public:
+  pass_uninline_innermost_loops (gcc::context *ctxt)
+    : gimple_opt_pass (pass_data_uninline_innermost_loops, ctxt)
+  {}
+
+  /* opt_pass methods: */
+  virtual bool gate (function *fun)
+    {
+      const char *fun_to_uninline = noloopalias;
+
+      if (fun_to_uninline == NULL)
+	return false;
+
+      if (strcmp(fun_to_uninline, "*") == 0)
+	return true;
+
+      if (fun == NULL)
+	return false;
+
+      return (strcmp (function_name (fun), fun_to_uninline) == 0);
+    }
+
+  virtual unsigned int execute (function *)
+    {
+      return extract_loop_to_function ();
+    }
+};
+
+} // anon namespace
+
+gimple_opt_pass *
+make_pass_uninline_innermost_loops (gcc::context *ctxt)
+{
+  return new pass_uninline_innermost_loops (ctxt);
+}