ipa-cp.c (ipcp_cloning_candidate_p): Use opt_for_fn.
[gcc.git] / gcc / tree-ssa-loop-prefetch.c
index a5b511262f9ed9064ac60359aac4cdf00667af8b..2efa2dd9705d99309728755de0005242cfdb0bea 100644 (file)
@@ -1,5 +1,5 @@
 /* Array prefetching.
-   Copyright (C) 2005, 2007, 2008, 2009, 2010 Free Software Foundation, Inc.
+   Copyright (C) 2005-2014 Free Software Foundation, Inc.
 
 This file is part of GCC.
 
@@ -22,22 +22,40 @@ along with GCC; see the file COPYING3.  If not see
 #include "coretypes.h"
 #include "tm.h"
 #include "tree.h"
+#include "stor-layout.h"
 #include "tm_p.h"
+#include "predict.h"
+#include "vec.h"
+#include "hashtab.h"
+#include "hash-set.h"
+#include "machmode.h"
+#include "hard-reg-set.h"
+#include "input.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 "is-a.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"
-#include "toplev.h"
 #include "params.h"
 #include "langhooks.h"
 #include "tree-inline.h"
@@ -47,7 +65,9 @@ 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 "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:
@@ -80,7 +100,7 @@ along with GCC; see the file COPYING3.  If not see
        (2) has PREFETCH_MOD 64
        (3) has PREFETCH_MOD 4
        (4) has PREFETCH_MOD 1.  We do not set PREFETCH_BEFORE here, since
-           the cache line accessed by (4) is the same with probability only
+           the cache line accessed by (5) is the same with probability only
           7/32.
        (5) has PREFETCH_MOD 1 as well.
 
@@ -281,29 +301,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
@@ -423,9 +451,6 @@ idx_analyze_ref (tree base, tree *index, void *data)
   HOST_WIDE_INT idelta = 0, imult = 1;
   affine_iv iv;
 
-  if (TREE_CODE (base) == MISALIGNED_INDIRECT_REF)
-    return false;
-
   if (!simple_iv (ar_data->loop, loop_containing_stmt (ar_data->stmt),
                  *index, &iv, true))
     return false;
@@ -486,10 +511,18 @@ analyze_ref (struct loop *loop, tree *ref_p, tree *base,
   *step = NULL_TREE;
   *delta = 0;
 
-  /* First strip off the component references.  Ignore bitfields.  */
-  if (TREE_CODE (ref) == COMPONENT_REF
-      && DECL_NONADDRESSABLE_P (TREE_OPERAND (ref, 1)))
-    ref = TREE_OPERAND (ref, 0);
+  /* First strip off the component references.  Ignore bitfields.
+     Also strip off the real and imagine parts of a complex, so that
+     they can have the same base.  */
+  if (TREE_CODE (ref) == REALPART_EXPR
+      || TREE_CODE (ref) == IMAGPART_EXPR
+      || (TREE_CODE (ref) == COMPONENT_REF
+          && DECL_NONADDRESSABLE_P (TREE_OPERAND (ref, 1))))
+    {
+      if (TREE_CODE (ref) == IMAGPART_EXPR)
+        *delta += int_size_in_bytes (TREE_TYPE (ref));
+      ref = TREE_OPERAND (ref, 0);
+    }
 
   *ref_p = ref;
 
@@ -531,10 +564,49 @@ gather_memory_references_ref (struct loop *loop, struct mem_ref_group **refs,
   if (step == NULL_TREE)
     return false;
 
-  /* Limit non-constant step prefetching only to the innermost loops.  */
-  if (!cst_and_fits_in_hwi (step) && loop->inner != NULL)
+  /* Stop if the address of BASE could not be taken.  */
+  if (may_be_nonaddressable_p (base))
     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.  */
   agrp = find_or_create_group (refs, base, step);
@@ -786,7 +858,7 @@ prune_ref_by_group_reuse (struct mem_ref *ref, struct mem_ref *by,
       prefetch_before = (hit_from - delta_r + step - 1) / step;
 
       /* Do not reduce prefetch_before if we meet beyond cache size.  */
-      if (prefetch_before > (unsigned) abs (L2_CACHE_SIZE_BYTES / step))
+      if (prefetch_before > absu_hwi (L2_CACHE_SIZE_BYTES / step))
         prefetch_before = PREFETCH_ALL;
       if (prefetch_before < ref->prefetch_before)
        ref->prefetch_before = prefetch_before;
@@ -1092,8 +1164,7 @@ issue_prefetch_ref (struct mem_ref *ref, unsigned unroll_factor, unsigned ahead)
           /* Determine the address to prefetch.  */
           delta = (ahead + ap * ref->prefetch_mod) *
                   int_cst_value (ref->group->step);
-          addr = fold_build2 (POINTER_PLUS_EXPR, ptr_type_node,
-                              addr_base, size_int (delta));
+          addr = fold_build_pointer_plus_hwi (addr_base, delta);
           addr = force_gimple_operand_gsi (&bsi, unshare_expr (addr), true, NULL,
                                            true, GSI_SAME_STMT);
         }
@@ -1104,13 +1175,12 @@ issue_prefetch_ref (struct mem_ref *ref, unsigned unroll_factor, unsigned ahead)
           forward = fold_build2 (MULT_EXPR, sizetype,
                                  fold_convert (sizetype, ref->group->step),
                                  fold_convert (sizetype, size_int (ahead)));
-          addr = fold_build2 (POINTER_PLUS_EXPR, ptr_type_node, addr_base,
-                             forward);
+          addr = fold_build_pointer_plus (addr_base, forward);
           addr = force_gimple_operand_gsi (&bsi, unshare_expr (addr), true,
                                           NULL, true, GSI_SAME_STMT);
       }
       /* Create the prefetch instruction.  */
-      prefetch = gimple_build_call (built_in_decls[BUILT_IN_PREFETCH],
+      prefetch = gimple_build_call (builtin_decl_explicit (BUILT_IN_PREFETCH),
                                    3, addr, write_p, local);
       gsi_insert_before (&bsi, prefetch, GSI_SAME_STMT);
     }
@@ -1138,7 +1208,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
@@ -1182,13 +1252,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;
   gimple_stmt_iterator bsi;
   unsigned i;
 
-  for (i = 0; VEC_iterate (edge, exits, i, exit); i++)
+  FOR_EACH_VEC_ELT (exits, i, exit)
     {
       call = gimple_build_call (FENCE_FOLLOWING_MOVNT, 0);
 
@@ -1200,10 +1270,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);
 }
 
@@ -1221,16 +1290,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 (i = 0; VEC_iterate (edge, exits, i, exit); i++)
+      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;
@@ -1404,8 +1473,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;
 
@@ -1425,7 +1494,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;
 
@@ -1444,7 +1513,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 (i = 0; VEC_iterate (tree, access_fns, i, access_fn); i++)
+  FOR_EACH_VEC_ELT (access_fns, i, access_fn)
     {
       /* Keep track of the reference corresponding to the subscript, so that we
         know its stride.  */
@@ -1454,8 +1523,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;
 
@@ -1488,18 +1557,18 @@ self_reuse_distance (data_reference_p dr, unsigned *loop_sizes, unsigned n,
 
 /* Determines the distance till the first reuse of each reference in REFS
    in the loop nest of LOOP.  NO_OTHER_REFS is true if there are no other
-   memory references in the loop.  */
+   memory references in the loop.  Return false if the analysis fails.  */
 
-static void
+static bool
 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;
@@ -1508,7 +1577,7 @@ determine_loop_nest_reuse (struct loop *loop, struct mem_ref_group *refs,
   ddr_p dep;
 
   if (loop->inner)
-    return;
+    return true;
 
   /* Find the outermost loop of the loop nest of loop (we require that
      there are no sibling loops inside the nest).  */
@@ -1528,7 +1597,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;
@@ -1540,9 +1609,9 @@ 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);
-      vol = estimated_loop_iterations_int (aloop, false);
-      if (vol < 0)
+      aloop = vloops[i];
+      vol = estimated_stmt_executions_int (aloop);
+      if (vol == -1)
        vol = expected_loop_iterations (aloop);
       volume *= vol;
     }
@@ -1554,19 +1623,20 @@ determine_loop_nest_reuse (struct loop *loop, struct mem_ref_group *refs,
   for (gr = refs; gr; gr = gr->next)
     for (ref = gr->refs; ref; ref = ref->next)
       {
-       dr = create_data_ref (nest, ref->mem, ref->stmt, !ref->write_p);
+       dr = create_data_ref (nest, loop_containing_stmt (ref->stmt),
+                             ref->mem, ref->stmt, !ref->write_p);
 
        if (dr)
          {
            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 (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
+  FOR_EACH_VEC_ELT (datarefs, i, dr)
     {
       dist = self_reuse_distance (dr, loop_data_size, n, loop);
       ref = (struct mem_ref *) dr->aux;
@@ -1577,9 +1647,10 @@ determine_loop_nest_reuse (struct loop *loop, struct mem_ref_group *refs,
        ref->independent_p = true;
     }
 
-  compute_all_dependences (datarefs, &dependences, vloops, true);
+  if (!compute_all_dependences (datarefs, &dependences, vloops, true))
+    return false;
 
-  for (i = 0; VEC_iterate (ddr_p, dependences, i, dep); i++)
+  FOR_EACH_VEC_ELT (dependences, i, dep)
     {
       if (DDR_ARE_DEPENDENT (dep) == chrec_known)
        continue;
@@ -1656,6 +1727,8 @@ determine_loop_nest_reuse (struct loop *loop, struct mem_ref_group *refs,
          fprintf (dump_file, " ref %p distance %u\n",
                   (void *) ref, ref->reuse_distance);
     }
+
+  return true;
 }
 
 /* Determine whether or not the trip count to ahead ratio is too small based
@@ -1792,7 +1865,9 @@ loop_prefetch_arrays (struct loop *loop)
     return false;
 
   ahead = (PREFETCH_LATENCY + time - 1) / time;
-  est_niter = estimated_loop_iterations_int (loop, false);
+  est_niter = estimated_stmt_executions_int (loop);
+  if (est_niter == -1)
+    est_niter = max_stmt_executions_int (loop);
 
   /* Prefetching is not likely to be profitable if the trip count to ahead
      ratio is too small.  */
@@ -1816,7 +1891,8 @@ loop_prefetch_arrays (struct loop *loop)
   if (nothing_to_prefetch_p (refs))
     goto fail;
 
-  determine_loop_nest_reuse (loop, refs, no_other_refs);
+  if (!determine_loop_nest_reuse (loop, refs, no_other_refs))
+    goto fail;
 
   /* Step 3: determine unroll factor.  */
   unroll_factor = determine_unroll_factor (loop, refs, ninsns, &desc,
@@ -1868,7 +1944,6 @@ fail:
 unsigned int
 tree_ssa_prefetch_arrays (void)
 {
-  loop_iterator li;
   struct loop *loop;
   bool unrolled = false;
   int todo_flags = 0;
@@ -1901,24 +1976,22 @@ tree_ssa_prefetch_arrays (void)
 
   initialize_original_copy_tables ();
 
-  if (!built_in_decls[BUILT_IN_PREFETCH])
+  if (!builtin_decl_explicit_p (BUILT_IN_PREFETCH))
     {
-      tree type = build_function_type (void_type_node,
-                                      tree_cons (NULL_TREE,
-                                                 const_ptr_type_node,
-                                                 NULL_TREE));
+      tree type = build_function_type_list (void_type_node,
+                                           const_ptr_type_node, NULL_TREE);
       tree decl = add_builtin_function ("__builtin_prefetch", type,
                                        BUILT_IN_PREFETCH, BUILT_IN_NORMAL,
                                        NULL, NULL_TREE);
       DECL_IS_NOVOPS (decl) = true;
-      built_in_decls[BUILT_IN_PREFETCH] = decl;
+      set_builtin_decl (BUILT_IN_PREFETCH, decl, false);
     }
 
   /* We assume that size of cache line is a power of two, so verify this
      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);
@@ -1938,3 +2011,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);
+}
+
+