re PR debug/66691 (ICE on valid code at -O3 with -g enabled in simplify_subreg, at...
[gcc.git] / gcc / tree-ssa-loop-prefetch.c
index 00f30a1f31b4d631b4ce3a2c660ddfd7c323401e..69968454c46bdf092ec092a0e68380ba5a55b61b 100644 (file)
@@ -1,6 +1,5 @@
 /* Array prefetching.
-   Copyright (C) 2005, 2007, 2008, 2009, 2010, 2011
-   Free Software Foundation, Inc.
+   Copyright (C) 2005-2015 Free Software Foundation, Inc.
 
 This file is part of GCC.
 
@@ -22,19 +21,35 @@ along with GCC; see the file COPYING3.  If not see
 #include "system.h"
 #include "coretypes.h"
 #include "tm.h"
+#include "alias.h"
+#include "symtab.h"
 #include "tree.h"
+#include "fold-const.h"
+#include "stor-layout.h"
 #include "tm_p.h"
+#include "predict.h"
+#include "hard-reg-set.h"
+#include "function.h"
+#include "dominance.h"
+#include "cfg.h"
 #include "basic-block.h"
-#include "output.h"
 #include "tree-pretty-print.h"
-#include "tree-flow.h"
-#include "tree-dump.h"
-#include "timevar.h"
+#include "tree-ssa-alias.h"
+#include "internal-fn.h"
+#include "gimple-expr.h"
+#include "gimple.h"
+#include "gimplify.h"
+#include "gimple-iterator.h"
+#include "gimplify-me.h"
+#include "gimple-ssa.h"
+#include "tree-ssa-loop-ivopts.h"
+#include "tree-ssa-loop-manip.h"
+#include "tree-ssa-loop-niter.h"
+#include "tree-ssa-loop.h"
+#include "tree-into-ssa.h"
 #include "cfgloop.h"
 #include "tree-pass.h"
 #include "insn-config.h"
-#include "recog.h"
-#include "hashtab.h"
 #include "tree-chrec.h"
 #include "tree-scalar-evolution.h"
 #include "diagnostic-core.h"
@@ -46,8 +61,19 @@ along with GCC; see the file COPYING3.  If not see
 
 /* FIXME: Needed for optabs, but this should all be moved to a TBD interface
    between the GIMPLE and RTL worlds.  */
+#include "rtl.h"
+#include "flags.h"
+#include "expmed.h"
+#include "dojump.h"
+#include "explow.h"
+#include "calls.h"
+#include "emit-rtl.h"
+#include "varasm.h"
+#include "stmt.h"
 #include "expr.h"
+#include "insn-codes.h"
 #include "optabs.h"
+#include "recog.h"
 
 /* This pass inserts prefetch instructions to optimize cache usage during
    accesses to arrays in loops.  It processes loops sequentially and:
@@ -281,29 +307,37 @@ struct mem_ref
                                   nontemporal one.  */
 };
 
-/* Dumps information about reference REF to FILE.  */
-
+/* Dumps information about memory reference */
 static void
-dump_mem_ref (FILE *file, struct mem_ref *ref)
+dump_mem_details (FILE *file, tree base, tree step,
+           HOST_WIDE_INT delta, bool write_p) 
 {
-  fprintf (file, "Reference %p:\n", (void *) ref);
-
-  fprintf (file, "  group %p (base ", (void *) ref->group);
-  print_generic_expr (file, ref->group->base, TDF_SLIM);
+  fprintf (file, "(base ");
+  print_generic_expr (file, base, TDF_SLIM);
   fprintf (file, ", step ");
-  if (cst_and_fits_in_hwi (ref->group->step))
-    fprintf (file, HOST_WIDE_INT_PRINT_DEC, int_cst_value (ref->group->step));
+  if (cst_and_fits_in_hwi (step))
+    fprintf (file, HOST_WIDE_INT_PRINT_DEC, int_cst_value (step));
   else
-    print_generic_expr (file, ref->group->step, TDF_TREE);
+    print_generic_expr (file, step, TDF_TREE);
   fprintf (file, ")\n");
-
   fprintf (file, "  delta ");
-  fprintf (file, HOST_WIDE_INT_PRINT_DEC, ref->delta);
+  fprintf (file, HOST_WIDE_INT_PRINT_DEC, delta);
+  fprintf (file, "\n");
+  fprintf (file, "  %s\n", write_p ? "write" : "read");
   fprintf (file, "\n");
+}
 
-  fprintf (file, "  %s\n", ref->write_p ? "write" : "read");
+/* Dumps information about reference REF to FILE.  */
 
-  fprintf (file, "\n");
+static void
+dump_mem_ref (FILE *file, struct mem_ref *ref)
+{
+  fprintf (file, "Reference %p:\n", (void *) ref);
+
+  fprintf (file, "  group %p ", (void *) ref->group);
+
+  dump_mem_details (file, ref->group->base, ref->group->step, ref->delta,
+                   ref->write_p);
 }
 
 /* Finds a group with BASE and STEP in GROUPS, or creates one if it does not
@@ -322,8 +356,8 @@ find_or_create_group (struct mem_ref_group **groups, tree base, tree step)
 
       /* If step is an integer constant, keep the list of groups sorted
          by decreasing step.  */
-        if (cst_and_fits_in_hwi ((*groups)->step) && cst_and_fits_in_hwi (step)
-            && int_cst_value ((*groups)->step) < int_cst_value (step))
+      if (cst_and_fits_in_hwi ((*groups)->step) && cst_and_fits_in_hwi (step)
+         && int_cst_value ((*groups)->step) < int_cst_value (step))
        break;
     }
 
@@ -540,9 +574,44 @@ gather_memory_references_ref (struct loop *loop, struct mem_ref_group **refs,
   if (may_be_nonaddressable_p (base))
     return false;
 
-  /* Limit non-constant step prefetching only to the innermost loops.  */
-  if (!cst_and_fits_in_hwi (step) && loop->inner != NULL)
-    return false;
+  /* Limit non-constant step prefetching only to the innermost loops and 
+     only when the step is loop invariant in the entire loop nest. */
+  if (!cst_and_fits_in_hwi (step))
+    {
+      if (loop->inner != NULL)
+        {
+          if (dump_file && (dump_flags & TDF_DETAILS))
+            {
+              fprintf (dump_file, "Memory expression %p\n",(void *) ref ); 
+              print_generic_expr (dump_file, ref, TDF_TREE); 
+              fprintf (dump_file,":");
+              dump_mem_details (dump_file, base, step, delta, write_p);
+              fprintf (dump_file, 
+                       "Ignoring %p, non-constant step prefetching is "
+                       "limited to inner most loops \n", 
+                       (void *) ref);
+            }
+            return false;    
+         }
+      else
+        {
+          if (!expr_invariant_in_loop_p (loop_outermost (loop), step))
+          {
+            if (dump_file && (dump_flags & TDF_DETAILS))
+              {
+                fprintf (dump_file, "Memory expression %p\n",(void *) ref );
+                print_generic_expr (dump_file, ref, TDF_TREE);
+                fprintf (dump_file,":");
+                dump_mem_details (dump_file, base, step, delta, write_p);
+                fprintf (dump_file, 
+                         "Not prefetching, ignoring %p due to "
+                         "loop variant step\n",
+                         (void *) ref);
+              }
+              return false;                 
+            }
+        }
+    }
 
   /* Now we know that REF = &BASE + STEP * iter + DELTA, where DELTA and STEP
      are integer constants.  */
@@ -1074,7 +1143,7 @@ issue_prefetch_ref (struct mem_ref *ref, unsigned unroll_factor, unsigned ahead)
 {
   HOST_WIDE_INT delta;
   tree addr, addr_base, write_p, local, forward;
-  gimple prefetch;
+  gcall *prefetch;
   gimple_stmt_iterator bsi;
   unsigned n_prefetches, ap;
   bool nontemporal = ref->reuse_distance >= L2_CACHE_SIZE_BYTES;
@@ -1145,7 +1214,7 @@ issue_prefetches (struct mem_ref_group *groups,
 static bool
 nontemporal_store_p (struct mem_ref *ref)
 {
-  enum machine_mode mode;
+  machine_mode mode;
   enum insn_code code;
 
   /* REF must be a write that is not reused.  We require it to be independent
@@ -1189,13 +1258,13 @@ mark_nontemporal_store (struct mem_ref *ref)
 static void
 emit_mfence_after_loop (struct loop *loop)
 {
-  VEC (edge, heap) *exits = get_loop_exit_edges (loop);
+  vec<edge> exits = get_loop_exit_edges (loop);
   edge exit;
-  gimple call;
+  gcall *call;
   gimple_stmt_iterator bsi;
   unsigned i;
 
-  FOR_EACH_VEC_ELT (edge, exits, i, exit)
+  FOR_EACH_VEC_ELT (exits, i, exit)
     {
       call = gimple_build_call (FENCE_FOLLOWING_MOVNT, 0);
 
@@ -1207,10 +1276,9 @@ emit_mfence_after_loop (struct loop *loop)
       bsi = gsi_after_labels (exit->dest);
 
       gsi_insert_before (&bsi, call, GSI_NEW_STMT);
-      mark_virtual_ops_for_renaming (call);
     }
 
-  VEC_free (edge, heap, exits);
+  exits.release ();
   update_ssa (TODO_update_ssa_only_virtuals);
 }
 
@@ -1228,16 +1296,16 @@ may_use_storent_in_loop_p (struct loop *loop)
      is a suitable place for it at each of the loop exits.  */
   if (FENCE_FOLLOWING_MOVNT != NULL_TREE)
     {
-      VEC (edge, heap) *exits = get_loop_exit_edges (loop);
+      vec<edge> exits = get_loop_exit_edges (loop);
       unsigned i;
       edge exit;
 
-      FOR_EACH_VEC_ELT (edge, exits, i, exit)
+      FOR_EACH_VEC_ELT (exits, i, exit)
        if ((exit->flags & EDGE_ABNORMAL)
-           && exit->dest == EXIT_BLOCK_PTR)
+           && exit->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
          ret = false;
 
-      VEC_free (edge, heap, exits);
+      exits.release ();
     }
 
   return ret;
@@ -1411,8 +1479,8 @@ add_subscript_strides (tree access_fn, unsigned stride,
       if ((unsigned) loop_depth (aloop) <= min_depth)
        continue;
 
-      if (host_integerp (step, 0))
-       astep = tree_low_cst (step, 0);
+      if (tree_fits_shwi_p (step))
+       astep = tree_to_shwi (step);
       else
        astep = L1_CACHE_LINE_SIZE;
 
@@ -1432,7 +1500,7 @@ self_reuse_distance (data_reference_p dr, unsigned *loop_sizes, unsigned n,
 {
   tree stride, access_fn;
   HOST_WIDE_INT *strides, astride;
-  VEC (tree, heap) *access_fns;
+  vec<tree> access_fns;
   tree ref = DR_REF (dr);
   unsigned i, ret = ~0u;
 
@@ -1451,7 +1519,7 @@ self_reuse_distance (data_reference_p dr, unsigned *loop_sizes, unsigned n,
   strides = XCNEWVEC (HOST_WIDE_INT, n);
   access_fns = DR_ACCESS_FNS (dr);
 
-  FOR_EACH_VEC_ELT (tree, access_fns, i, access_fn)
+  FOR_EACH_VEC_ELT (access_fns, i, access_fn)
     {
       /* Keep track of the reference corresponding to the subscript, so that we
         know its stride.  */
@@ -1461,8 +1529,8 @@ self_reuse_distance (data_reference_p dr, unsigned *loop_sizes, unsigned n,
       if (TREE_CODE (ref) == ARRAY_REF)
        {
          stride = TYPE_SIZE_UNIT (TREE_TYPE (ref));
-         if (host_integerp (stride, 1))
-           astride = tree_low_cst (stride, 1);
+         if (tree_fits_uhwi_p (stride))
+           astride = tree_to_uhwi (stride);
          else
            astride = L1_CACHE_LINE_SIZE;
 
@@ -1502,11 +1570,11 @@ determine_loop_nest_reuse (struct loop *loop, struct mem_ref_group *refs,
                           bool no_other_refs)
 {
   struct loop *nest, *aloop;
-  VEC (data_reference_p, heap) *datarefs = NULL;
-  VEC (ddr_p, heap) *dependences = NULL;
+  vec<data_reference_p> datarefs = vNULL;
+  vec<ddr_p> dependences = vNULL;
   struct mem_ref_group *gr;
   struct mem_ref *ref, *refb;
-  VEC (loop_p, heap) *vloops = NULL;
+  vec<loop_p> vloops = vNULL;
   unsigned *loop_data_size;
   unsigned i, j, n;
   unsigned volume, dist, adist;
@@ -1535,7 +1603,7 @@ determine_loop_nest_reuse (struct loop *loop, struct mem_ref_group *refs,
      We use this to estimate whether the reference is evicted from the
      cache before its reuse.  */
   find_loop_nest (nest, &vloops);
-  n = VEC_length (loop_p, vloops);
+  n = vloops.length ();
   loop_data_size = XNEWVEC (unsigned, n);
   volume = volume_of_references (refs);
   i = n;
@@ -1547,7 +1615,7 @@ determine_loop_nest_reuse (struct loop *loop, struct mem_ref_group *refs,
       if (volume > L2_CACHE_SIZE_BYTES)
        continue;
 
-      aloop = VEC_index (loop_p, vloops, i);
+      aloop = vloops[i];
       vol = estimated_stmt_executions_int (aloop);
       if (vol == -1)
        vol = expected_loop_iterations (aloop);
@@ -1568,13 +1636,13 @@ determine_loop_nest_reuse (struct loop *loop, struct mem_ref_group *refs,
          {
            ref->reuse_distance = volume;
            dr->aux = ref;
-           VEC_safe_push (data_reference_p, heap, datarefs, dr);
+           datarefs.safe_push (dr);
          }
        else
          no_other_refs = false;
       }
 
-  FOR_EACH_VEC_ELT (data_reference_p, datarefs, i, dr)
+  FOR_EACH_VEC_ELT (datarefs, i, dr)
     {
       dist = self_reuse_distance (dr, loop_data_size, n, loop);
       ref = (struct mem_ref *) dr->aux;
@@ -1588,7 +1656,7 @@ determine_loop_nest_reuse (struct loop *loop, struct mem_ref_group *refs,
   if (!compute_all_dependences (datarefs, &dependences, vloops, true))
     return false;
 
-  FOR_EACH_VEC_ELT (ddr_p, dependences, i, dep)
+  FOR_EACH_VEC_ELT (dependences, i, dep)
     {
       if (DDR_ARE_DEPENDENT (dep) == chrec_known)
        continue;
@@ -1882,7 +1950,6 @@ fail:
 unsigned int
 tree_ssa_prefetch_arrays (void)
 {
-  loop_iterator li;
   struct loop *loop;
   bool unrolled = false;
   int todo_flags = 0;
@@ -1930,7 +1997,7 @@ tree_ssa_prefetch_arrays (void)
      here.  */
   gcc_assert ((PREFETCH_BLOCK & (PREFETCH_BLOCK - 1)) == 0);
 
-  FOR_EACH_LOOP (li, loop, LI_FROM_INNERMOST)
+  FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
     {
       if (dump_file && (dump_flags & TDF_DETAILS))
        fprintf (dump_file, "Processing loop %d:\n", loop->num);
@@ -1950,3 +2017,52 @@ tree_ssa_prefetch_arrays (void)
   free_original_copy_tables ();
   return todo_flags;
 }
+
+/* Prefetching.  */
+
+namespace {
+
+const pass_data pass_data_loop_prefetch =
+{
+  GIMPLE_PASS, /* type */
+  "aprefetch", /* name */
+  OPTGROUP_LOOP, /* optinfo_flags */
+  TV_TREE_PREFETCH, /* tv_id */
+  ( PROP_cfg | PROP_ssa ), /* properties_required */
+  0, /* properties_provided */
+  0, /* properties_destroyed */
+  0, /* todo_flags_start */
+  0, /* todo_flags_finish */
+};
+
+class pass_loop_prefetch : public gimple_opt_pass
+{
+public:
+  pass_loop_prefetch (gcc::context *ctxt)
+    : gimple_opt_pass (pass_data_loop_prefetch, ctxt)
+  {}
+
+  /* opt_pass methods: */
+  virtual bool gate (function *) { return flag_prefetch_loop_arrays > 0; }
+  virtual unsigned int execute (function *);
+
+}; // class pass_loop_prefetch
+
+unsigned int
+pass_loop_prefetch::execute (function *fun)
+{
+  if (number_of_loops (fun) <= 1)
+    return 0;
+
+  return tree_ssa_prefetch_arrays ();
+}
+
+} // anon namespace
+
+gimple_opt_pass *
+make_pass_loop_prefetch (gcc::context *ctxt)
+{
+  return new pass_loop_prefetch (ctxt);
+}
+
+