noloopalias: Add new pass to optimise loops.gcc-8_2_0-amp3gcc-8_2_0-amp3-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, 549 insertions, 0 deletions

diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index 42adaef66213..be0f2c90a863 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -1415,6 +1415,7 @@ OBJS = \
 	mode-switching.o \
 	modulo-sched.o \
 	multiple_target.o \
+	noloopalias.o \
 	omp-offload.o \
 	omp-expand.o \
 	omp-general.o \
diff --git a/gcc/common.opt b/gcc/common.opt
index 6f43ef937e95..86d0d02d8d72 100644
--- a/gcc/common.opt
+++ b/gcc/common.opt
@@ -2721,6 +2721,11 @@ fnoalias
 Common Report Var(flag_noalias) Optimization
 Assume no aliasing in the whole program.
 
+fnoloopalias
+Common Report Var(flag_noloopalias) Optimization
+Restrict pointer aliasing for 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/noloopalias.c b/gcc/noloopalias.c
new file mode 100644
index 000000000000..329dee4e0edb
--- /dev/null
+++ b/gcc/noloopalias.c
@@ -0,0 +1,540 @@
+#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;
+
+static const char *uninlined_function_postfix = "loop";
+
+/* If a callback returns a negative number,
+ * then we immediately bail out and return the
+ * return value from the callback.  */
+typedef int (*stmt_callback) (gimple *stmt, void *g);
+typedef int (*op_callback) (gimple *stmt, tree op, unsigned index, void *g);
+
+
+/* Iterator helper, which can be used to iterate over all basic blocks,
+ * their statements and the statement's operands in a loop.
+ * For each statement and operator a callback will be invoked.
+ * If any callback invocation returns a non-null return code,
+ * the iteration will be stopped immediately and the non-null
+ * return code will be returned.  */
+
+static int
+for_each_operand_in_loop (const struct loop *loop, stmt_callback stmt_cb, op_callback op_cb, void *g)
+{
+  basic_block *bbs;
+  unsigned num_nodes;
+  unsigned i;
+  int ret = 0;
+
+  /* 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);
+
+	  if (stmt_cb)
+	    {
+	      ret = stmt_cb(stmt, g);
+	      if (ret)
+		goto end;
+	    }
+
+	  /* Iterate over operands in stmt.  */
+	  for (j = 0; j < gimple_num_ops (stmt); j++)
+	    {
+	      tree op;
+	      op = gimple_op (stmt, j);
+	      if (op)
+		{
+		  if (op_cb)
+		    {
+		      ret = op_cb (stmt, op, j, g);
+		      if (ret)
+			goto end;
+		    }
+		}
+	    }
+	}
+    }
+
+end:
+  /* Free the bb list.  */
+  free (bbs);
+
+  return ret;
+}
+
+/* Given stmt is an assign statement and given op is its LHS.  */
+
+static bool
+is_defined_in_stmt (const gimple *stmt, const tree op)
+{
+  if (gimple_code (stmt) == GIMPLE_ASSIGN)
+    {
+      tree 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)
+{
+  /* Get a gsi for the bb stmt belongs to (pointing to stmt).  */
+  gimple_stmt_iterator 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;
+}
+
+static int
+is_gimple_call (gimple *stmt, void *g)
+{
+  (void)g;
+  return (gimple_code (stmt) == GIMPLE_CALL);
+}
+
+/* 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 int
+collect_cb (gimple *stmt, tree op, unsigned index, void *g)
+{
+  expr_vec *v = (expr_vec *) g;
+  enum tree_code code;
+
+  /* Whitelist LHS of assignments.  */
+  if (gimple_code (stmt) == GIMPLE_ASSIGN && index == 0)
+    return 0;
+
+  code = TREE_CODE (op);
+
+  /* Whitelist of supported codes */
+  if (code == INTEGER_CST ||
+      code == SSA_NAME ||
+      code == MEM_REF)
+    return 0;
+
+  /* Filter out op, which are not VAR_DECL or PARM_DECL.  */
+  if (code != VAR_DECL && code != PARM_DECL)
+    return -1;
+
+  /* Filter out op without DECL_NAME. */
+  if (!DECL_NAME (op))
+    return -1;
+
+  /* Filter out if op already included.  */
+  if (v->contains (op))
+    return 0;
+
+  /* Filter out ops, which are defined inside bb. */
+  if (is_defined_inside (stmt, op))
+    return 0;
+
+  if (dump_file)
+    {
+    fprintf (dump_file, "Found new element for arguments list: ");
+      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 0;
+}
+
+/* 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;
+  int ret = for_each_operand_in_loop (loop, NULL, collect_cb, (void *) &v);
+  if (ret)
+    return vNULL;
+
+  return v;
+}
+
+/* Return non-null if loop contains a call statement with operands.  */
+
+static int
+contains_call (struct loop *loop)
+{
+  return for_each_operand_in_loop (loop, is_gimple_call, NULL, NULL);
+}
+
+struct var_to_parm_cb_p
+{
+  tree d;
+  tree d_parm;
+};
+
+/* Replace op in stmt by p->d_parm if op == p->d.  */
+
+static int
+var_to_parm_cb (gimple *stmt, tree op, unsigned index, void *g)
+{
+  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);
+    }
+  return 0;
+}
+
+/* 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, NULL, 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)) && TREE_CODE (d) == VAR_DECL)
+	TYPE_RESTRICT (TREE_TYPE (d_parm)) = 1;
+
+      /* 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
+outline_loop (struct loop *loop, expr_vec parameter_vector)
+{
+  /* Build function declaration.  */
+  char postfix[strlen(uninlined_function_postfix)+12];
+  snprintf (postfix, sizeof (postfix), "%s%i", uninlined_function_postfix, loop->num);
+  tree name = clone_function_name (cfun->decl, 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);
+
+  edge out = single_exit (loop);
+
+  gcc_assert (out != NULL);
+
+  basic_block out_bb = split_edge (out);
+
+  /* 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);
+
+  /* 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 ();
+
+  push_cfun (child_cfun);
+  update_max_bb_count ();
+  cgraph_edge::rebuild_edges ();
+
+  pop_cfun ();
+}
+
+static unsigned int
+extract_loop_to_function ()
+{
+  struct loop *loop;
+  expr_vec v = vNULL;
+
+  /* First create the list of loop exits of cfun
+     (searches all edges of all bb in cfun).  */
+  record_loop_exits ();
+
+  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;
+
+      /* Assure the loop is not the entire function.  */
+      if ((loop->num_nodes + 5) >= n_basic_blocks_for_fn (cfun))
+	continue;
+
+      /* We can't deal with calls inside of loops.  */
+      if (contains_call (loop))
+	continue;
+
+      /* First we get a unique list of operands in the loop,
+         which are defined outside of the loop.  */
+      v = collect_def_outside (loop);
+      if (v == vNULL)
+	continue;
+
+      /* Ignore small loop, which don't offer optimisation potential. */
+      if (v.length () < 10)
+	continue;
+
+      if (dump_file)
+	fprintf (dump_file, "Outlining loop %d\n", loop);
+
+      /* Now we create a new function with the given list of arguments.  */
+      outline_loop (loop, v);
+    }
+
+  /* Free the list of loop exits of cfun. */
+  release_recorded_exits (cfun);
+
+  return 0;
+}
+
+namespace {
+
+const pass_data pass_data_noloopalias =
+{
+  GIMPLE_PASS, /* type */
+  "noloopalias", /* name */
+  OPTGROUP_NONE, /* optinfo_flags */
+  TV_NOLOOPALIAS, /* tv_id */
+  PROP_gimple_any, /* properties_required */
+  0, /* properties_provided */
+  0, /* properties_destroyed */
+  0, /* todo_flags_start */
+  0, /* todo_flags_finish */
+};
+
+class pass_noloopalias: public gimple_opt_pass
+{
+public:
+  pass_noloopalias (gcc::context *ctxt)
+    : gimple_opt_pass (pass_data_noloopalias, ctxt)
+  {}
+
+  /* opt_pass methods: */
+  virtual bool gate (function *fun)
+    {
+      return flag_noloopalias;
+    }
+
+  virtual unsigned int execute (function *)
+    {
+      return extract_loop_to_function ();
+    }
+};
+
+} // anon namespace
+
+gimple_opt_pass *
+make_pass_noloopalias (gcc::context *ctxt)
+{
+  return new pass_noloopalias (ctxt);
+}
diff --git a/gcc/passes.def b/gcc/passes.def
index fe81b405f140..3dd743236dfb 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_noloopalias);
   TERMINATE_PASS_LIST (all_lowering_passes)
 
   /* Interprocedural optimization passes.  */
diff --git a/gcc/timevar.def b/gcc/timevar.def
index 1e56e5014870..5b1e34e6ad2d 100644
--- a/gcc/timevar.def
+++ b/gcc/timevar.def
@@ -145,6 +145,7 @@ DEFTIMEVAR (TV_FLATTEN_INLINING      , "flatten inlining")
 DEFTIMEVAR (TV_EARLY_INLINING        , "early inlining heuristics")
 DEFTIMEVAR (TV_INLINE_PARAMETERS     , "inline parameters")
 DEFTIMEVAR (TV_INTEGRATION           , "integration")
+DEFTIMEVAR (TV_NOLOOPALIAS           , "noloopalias")
 DEFTIMEVAR (TV_TREE_GIMPLIFY	     , "tree gimplify")
 DEFTIMEVAR (TV_TREE_EH		     , "tree eh")
 DEFTIMEVAR (TV_TREE_CFG		     , "tree CFG construction")
diff --git a/gcc/tree-pass.h b/gcc/tree-pass.h
index abf6c4cfe3c3..05fcf1dcce6b 100644
--- a/gcc/tree-pass.h
+++ b/gcc/tree-pass.h
@@ -355,6 +355,7 @@ extern gimple_opt_pass *make_pass_refactor_eh (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_lower_eh (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_lower_eh_dispatch (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_lower_resx (gcc::context *ctxt);
+extern gimple_opt_pass *make_pass_noloopalias (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_build_cfg (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_early_tree_profile (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_cleanup_eh (gcc::context *ctxt);