--- a/gcc/graphite.c	Sun Aug 21 07:07:55 2011 +0900
+++ b/gcc/graphite.c	Fri Oct 27 22:46:09 2017 +0900
@@ -1,5 +1,5 @@
 /* Gimple Represented as Polyhedra.
-   Copyright (C) 2006, 2007, 2008, 2009, 2010 Free Software Foundation, Inc.
+   Copyright (C) 2006-2017 Free Software Foundation, Inc.
    Contributed by Sebastian Pop <sebastian.pop@inria.fr>.
 
 This file is part of GCC.
@@ -25,36 +25,39 @@
    An early description of this pass can be found in the GCC Summit'06
    paper "GRAPHITE: Polyhedral Analyses and Optimizations for GCC".
    The wiki page http://gcc.gnu.org/wiki/Graphite contains pointers to
-   the related work.
+   the related work.  */
 
-   One important document to read is CLooG's internal manual:
-   http://repo.or.cz/w/cloog-ppl.git?a=blob_plain;f=doc/cloog.texi;hb=HEAD
-   that describes the data structure of loops used in this file, and
-   the functions that are used for transforming the code.  */
+#define USES_ISL
 
 #include "config.h"
 #include "system.h"
 #include "coretypes.h"
+#include "backend.h"
 #include "diagnostic-core.h"
-#include "tree-flow.h"
-#include "tree-dump.h"
 #include "cfgloop.h"
-#include "tree-chrec.h"
+#include "tree-pass.h"
+#include "params.h"
+#include "pretty-print.h"
+
+#ifdef HAVE_isl
+#include "cfghooks.h"
+#include "tree.h"
+#include "gimple.h"
+#include "ssa.h"
+#include "fold-const.h"
+#include "gimple-iterator.h"
+#include "tree-cfg.h"
+#include "tree-ssa-loop.h"
 #include "tree-data-ref.h"
 #include "tree-scalar-evolution.h"
-#include "sese.h"
 #include "dbgcnt.h"
-
-#ifdef HAVE_cloog
-
-#include "ppl_c.h"
-#include "graphite-ppl.h"
-#include "graphite-poly.h"
-#include "graphite-scop-detection.h"
-#include "graphite-clast-to-gimple.h"
-#include "graphite-sese-to-poly.h"
-
-CloogState *cloog_state;
+#include "tree-parloops.h"
+#include "tree-cfgcleanup.h"
+#include "tree-vectorizer.h"
+#include "tree-ssa-loop-manip.h"
+#include "tree-ssa.h"
+#include "tree-into-ssa.h"
+#include "graphite.h"
 
 /* Print global statistics to FILE.  */
 
@@ -65,19 +68,20 @@
   long n_loops = 0;
   long n_stmts = 0;
   long n_conditions = 0;
-  long n_p_bbs = 0;
-  long n_p_loops = 0;
-  long n_p_stmts = 0;
-  long n_p_conditions = 0;
+  profile_count n_p_bbs = profile_count::zero ();
+  profile_count n_p_loops = profile_count::zero ();
+  profile_count n_p_stmts = profile_count::zero ();
+  profile_count n_p_conditions = profile_count::zero ();
 
   basic_block bb;
 
-  FOR_ALL_BB (bb)
+  FOR_ALL_BB_FN (bb, cfun)
     {
       gimple_stmt_iterator psi;
 
       n_bbs++;
-      n_p_bbs += bb->count;
+      if (bb->count.initialized_p ())
+        n_p_bbs += bb->count;
 
       /* Ignore artificial surrounding loop.  */
       if (bb == bb->loop_father->header
@@ -87,16 +91,18 @@
 	  n_p_loops += bb->count;
 	}
 
-      if (VEC_length (edge, bb->succs) > 1)
+      if (EDGE_COUNT (bb->succs) > 1)
 	{
 	  n_conditions++;
-	  n_p_conditions += bb->count;
+	  if (bb->count.initialized_p ())
+	    n_p_conditions += bb->count;
 	}
 
       for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi))
 	{
 	  n_stmts++;
-	  n_p_stmts += bb->count;
+	  if (bb->count.initialized_p ())
+	    n_p_stmts += bb->count;
 	}
     }
 
@@ -105,11 +111,16 @@
   fprintf (file, "LOOPS:%ld, ", n_loops);
   fprintf (file, "CONDITIONS:%ld, ", n_conditions);
   fprintf (file, "STMTS:%ld)\n", n_stmts);
-  fprintf (file, "\nGlobal profiling statistics (");
-  fprintf (file, "BBS:%ld, ", n_p_bbs);
-  fprintf (file, "LOOPS:%ld, ", n_p_loops);
-  fprintf (file, "CONDITIONS:%ld, ", n_p_conditions);
-  fprintf (file, "STMTS:%ld)\n", n_p_stmts);
+  fprintf (file, "Global profiling statistics (");
+  fprintf (file, "BBS:");
+  n_p_bbs.dump (file);
+  fprintf (file, ", LOOPS:");
+  n_p_loops.dump (file);
+  fprintf (file, ", CONDITIONS:");
+  n_p_conditions.dump (file);
+  fprintf (file, ", STMTS:");
+  n_p_stmts.dump (file);
+  fprintf (file, ")\n\n");
 }
 
 /* Print statistics for SCOP to FILE.  */
@@ -121,25 +132,26 @@
   long n_loops = 0;
   long n_stmts = 0;
   long n_conditions = 0;
-  long n_p_bbs = 0;
-  long n_p_loops = 0;
-  long n_p_stmts = 0;
-  long n_p_conditions = 0;
+  profile_count n_p_bbs = profile_count::zero ();
+  profile_count n_p_loops = profile_count::zero ();
+  profile_count n_p_stmts = profile_count::zero ();
+  profile_count n_p_conditions = profile_count::zero ();
 
   basic_block bb;
 
-  FOR_ALL_BB (bb)
+  FOR_ALL_BB_FN (bb, cfun)
     {
       gimple_stmt_iterator psi;
       loop_p loop = bb->loop_father;
 
-      if (!bb_in_sese_p (bb, SCOP_REGION (scop)))
+      if (!bb_in_sese_p (bb, scop->scop_info->region))
 	continue;
 
       n_bbs++;
-      n_p_bbs += bb->count;
+      if (bb->count.initialized_p ())
+        n_p_bbs += bb->count;
 
-      if (VEC_length (edge, bb->succs) > 1)
+      if (EDGE_COUNT (bb->succs) > 1)
 	{
 	  n_conditions++;
 	  n_p_conditions += bb->count;
@@ -151,95 +163,169 @@
 	  n_p_stmts += bb->count;
 	}
 
-      if (loop->header == bb && loop_in_sese_p (loop, SCOP_REGION (scop)))
+      if (loop->header == bb && loop_in_sese_p (loop, scop->scop_info->region))
 	{
 	  n_loops++;
 	  n_p_loops += bb->count;
 	}
     }
 
+  fprintf (file, "\nFunction Name: %s\n", current_function_name ());
+
+  edge scop_begin = scop->scop_info->region.entry;
+  edge scop_end = scop->scop_info->region.exit;
+
+  fprintf (file, "\nSCoP (entry_edge (bb_%d, bb_%d), ",
+	   scop_begin->src->index, scop_begin->dest->index);
+  fprintf (file, "exit_edge (bb_%d, bb_%d))",
+	   scop_end->src->index, scop_end->dest->index);
+
   fprintf (file, "\nSCoP statistics (");
   fprintf (file, "BBS:%ld, ", n_bbs);
   fprintf (file, "LOOPS:%ld, ", n_loops);
   fprintf (file, "CONDITIONS:%ld, ", n_conditions);
   fprintf (file, "STMTS:%ld)\n", n_stmts);
-  fprintf (file, "\nSCoP profiling statistics (");
-  fprintf (file, "BBS:%ld, ", n_p_bbs);
-  fprintf (file, "LOOPS:%ld, ", n_p_loops);
-  fprintf (file, "CONDITIONS:%ld, ", n_p_conditions);
-  fprintf (file, "STMTS:%ld)\n", n_p_stmts);
+  fprintf (file, "SCoP profiling statistics (");
+  fprintf (file, "BBS:");
+  n_p_bbs.dump (file);
+  fprintf (file, ", LOOPS:");
+  n_p_loops.dump (file);
+  fprintf (file, ", CONDITIONS:");
+  n_p_conditions.dump (file);
+  fprintf (file, ", STMTS:");
+  n_p_stmts.dump (file);
+  fprintf (file, ")\n\n");
 }
 
 /* Print statistics for SCOPS to FILE.  */
 
 static void
-print_graphite_statistics (FILE* file, VEC (scop_p, heap) *scops)
+print_graphite_statistics (FILE* file, vec<scop_p> scops)
 {
   int i;
-
   scop_p scop;
 
-  FOR_EACH_VEC_ELT (scop_p, scops, i, scop)
+  FOR_EACH_VEC_ELT (scops, i, scop)
     print_graphite_scop_statistics (file, scop);
 }
 
-/* Initialize graphite: when there are no loops returns false.  */
+/* Deletes all scops in SCOPS.  */
+
+static void
+free_scops (vec<scop_p> scops)
+{
+  int i;
+  scop_p scop;
+
+  FOR_EACH_VEC_ELT (scops, i, scop)
+    free_scop (scop);
+
+  scops.release ();
+}
 
-static bool
-graphite_initialize (void)
+/* Transforms LOOP to the canonical loop closed SSA form.  */
+
+static void
+canonicalize_loop_closed_ssa (loop_p loop)
 {
-  int ppl_initialized;
+  edge e = single_exit (loop);
+  basic_block bb;
+  gphi_iterator psi;
+
+  if (!e || (e->flags & EDGE_COMPLEX))
+    return;
+
+  bb = e->dest;
 
-  if (number_of_loops () <= 1
-      /* FIXME: This limit on the number of basic blocks of a function
-	 should be removed when the SCOP detection is faster.  */
-      || n_basic_blocks > PARAM_VALUE (PARAM_GRAPHITE_MAX_BBS_PER_FUNCTION))
+  /* Make the loop-close PHI node BB contain only PHIs and have a
+     single predecessor.  */
+  if (single_pred_p (bb))
+    {
+      e = split_block_after_labels (bb);
+      bb = e->src;
+    }
+  else
     {
-      if (dump_file && (dump_flags & TDF_DETAILS))
-	print_global_statistics (dump_file);
+      basic_block close = split_edge (e);
+      e = single_succ_edge (close);
+      for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi))
+	{
+	  gphi *phi = psi.phi ();
+	  use_operand_p use_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, e);
+	  tree arg = USE_FROM_PTR (use_p);
 
-      return false;
+	  /* Only add close phi nodes for SSA_NAMEs defined in LOOP.  */
+	  if (TREE_CODE (arg) != SSA_NAME
+	      || SSA_NAME_IS_DEFAULT_DEF (arg)
+	      || ! flow_bb_inside_loop_p (loop,
+					  gimple_bb (SSA_NAME_DEF_STMT (arg))))
+	    continue;
+
+	  tree res = copy_ssa_name (arg);
+	  gphi *close_phi = create_phi_node (res, close);
+	  add_phi_arg (close_phi, arg, gimple_phi_arg_edge (close_phi, 0),
+		       UNKNOWN_LOCATION);
+	  SET_USE (use_p, res);
+	}
+      bb = close;
     }
 
-  scev_reset ();
-  recompute_all_dominators ();
-  initialize_original_copy_tables ();
+  /* Eliminate duplicates.  This relies on processing loops from
+     innermost to outer.  */
+  for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi))
+    {
+      gphi_iterator gsi = psi;
+      gphi *phi = psi.phi ();
 
-  ppl_initialized = ppl_initialize ();
-  gcc_assert (ppl_initialized == 0);
+      /* At this point, PHI should be a close phi in normal form.  */
+      gcc_assert (gimple_phi_num_args (phi) == 1);
 
-  cloog_state = cloog_state_malloc ();
-  cloog_initialize ();
-
-  if (dump_file && dump_flags)
-    dump_function_to_file (current_function_decl, dump_file, dump_flags);
-
-  return true;
+      /* Iterate over the next phis and remove duplicates.  */
+      gsi_next (&gsi);
+      while (!gsi_end_p (gsi))
+	if (gimple_phi_arg_def (phi, 0) == gimple_phi_arg_def (gsi.phi (), 0))
+	  {
+	    replace_uses_by (gimple_phi_result (gsi.phi ()),
+			     gimple_phi_result (phi));
+	    remove_phi_node (&gsi, true);
+	  }
+	else
+	  gsi_next (&gsi);
+    }
 }
 
-/* Finalize graphite: perform CFG cleanup when NEED_CFG_CLEANUP_P is
-   true.  */
+/* Converts the current loop closed SSA form to a canonical form
+   expected by the Graphite code generation.
+
+   The loop closed SSA form has the following invariant: a variable
+   defined in a loop that is used outside the loop appears only in the
+   phi nodes in the destination of the loop exit.  These phi nodes are
+   called close phi nodes.
+
+   The canonical loop closed SSA form contains the extra invariants:
+
+   - when the loop contains only one exit, the close phi nodes contain
+   only one argument.  That implies that the basic block that contains
+   the close phi nodes has only one predecessor, that is a basic block
+   in the loop.
+
+   - the basic block containing the close phi nodes does not contain
+   other statements.
+
+   - there exist only one phi node per definition in the loop.
+*/
 
 static void
-graphite_finalize (bool need_cfg_cleanup_p)
+canonicalize_loop_closed_ssa_form (void)
 {
-  if (need_cfg_cleanup_p)
-    {
-      scev_reset ();
-      cleanup_tree_cfg ();
-      profile_status = PROFILE_ABSENT;
-      release_recorded_exits ();
-      tree_estimate_probability ();
-    }
+  loop_p loop;
+  FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
+    canonicalize_loop_closed_ssa (loop);
 
-  cloog_state_free (cloog_state);
-  cloog_finalize ();
-  ppl_finalize ();
-  free_original_copy_tables ();
+  checking_verify_loop_closed_ssa (true);
+}
 
-  if (dump_file && dump_flags)
-    print_loops (dump_file, 3);
-}
+isl_ctx *the_isl_ctx;
 
 /* Perform a set of linear transforms on the loops of the current
    function.  */
@@ -249,14 +335,34 @@
 {
   int i;
   scop_p scop;
-  bool need_cfg_cleanup_p = false;
-  VEC (scop_p, heap) *scops = NULL;
-  htab_t bb_pbb_mapping;
+  bool changed = false;
+  vec<scop_p> scops = vNULL;
+  isl_ctx *ctx;
 
-  if (!graphite_initialize ())
+  /* If a function is parallel it was most probably already run through graphite
+     once. No need to run again.  */
+  if (parallelized_function_p (cfun->decl))
     return;
 
+  calculate_dominance_info (CDI_DOMINATORS);
+
+  ctx = isl_ctx_alloc ();
+  isl_options_set_on_error (ctx, ISL_ON_ERROR_ABORT);
+  the_isl_ctx = ctx;
+
+  sort_sibling_loops (cfun);
+  canonicalize_loop_closed_ssa_form ();
+
+  /* Print the loop structure.  */
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    {
+      print_loops (dump_file, 2);
+      print_loops (dump_file, 3);
+    }
+
+  calculate_dominance_info (CDI_POST_DOMINATORS);
   build_scops (&scops);
+  free_dominance_info (CDI_POST_DOMINATORS);
 
   if (dump_file && (dump_flags & TDF_DETAILS))
     {
@@ -264,30 +370,167 @@
       print_global_statistics (dump_file);
     }
 
-  bb_pbb_mapping = htab_create (10, bb_pbb_map_hash, eq_bb_pbb_map, free);
-
-  FOR_EACH_VEC_ELT (scop_p, scops, i, scop)
+  FOR_EACH_VEC_ELT (scops, i, scop)
     if (dbg_cnt (graphite_scop))
       {
-	build_poly_scop (scop);
+	scop->isl_context = ctx;
+	if (!build_poly_scop (scop))
+	  continue;
+
+	if (!apply_poly_transforms (scop))
+	  continue;
 
-	if (POLY_SCOP_P (scop)
-	    && apply_poly_transforms (scop)
-	    && gloog (scop, bb_pbb_mapping))
-	  need_cfg_cleanup_p = true;
+	changed = true;
+	if (graphite_regenerate_ast_isl (scop))
+	  {
+	    location_t loc = find_loop_location
+	      (scops[i]->scop_info->region.entry->dest->loop_father);
+	    dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, loc,
+			     "loop nest optimized\n");
+	  }
       }
 
-  htab_delete (bb_pbb_mapping);
+  if (changed)
+    {
+      mark_virtual_operands_for_renaming (cfun);
+      update_ssa (TODO_update_ssa);
+      checking_verify_ssa (true, true);
+      rewrite_into_loop_closed_ssa (NULL, 0);
+      scev_reset ();
+      checking_verify_loop_structure ();
+    }
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    {
+      loop_p loop;
+      int num_no_dependency = 0;
+
+      FOR_EACH_LOOP (loop, 0)
+	if (loop->can_be_parallel)
+	  num_no_dependency++;
+
+      fprintf (dump_file, "%d loops carried no dependency.\n",
+	       num_no_dependency);
+    }
+
   free_scops (scops);
-  graphite_finalize (need_cfg_cleanup_p);
+  the_isl_ctx = NULL;
+  isl_ctx_free (ctx);
+
+  if (changed)
+    {
+      cleanup_tree_cfg ();
+      profile_status_for_fn (cfun) = PROFILE_ABSENT;
+      release_recorded_exits (cfun);
+      tree_estimate_probability (false);
+    }
+
 }
 
-#else /* If Cloog is not available: #ifndef HAVE_cloog.  */
+#else /* If isl is not available: #ifndef HAVE_isl.  */
 
-void
+static void
 graphite_transform_loops (void)
 {
-  sorry ("Graphite loop optimizations cannot be used");
+  sorry ("Graphite loop optimizations cannot be used (isl is not available).");
 }
 
 #endif
+
+
+static unsigned int
+graphite_transforms (struct function *fun)
+{
+  if (number_of_loops (fun) <= 1)
+    return 0;
+
+  graphite_transform_loops ();
+
+  return 0;
+}
+
+static bool
+gate_graphite_transforms (void)
+{
+  /* Enable -fgraphite pass if any one of the graphite optimization flags
+     is turned on.  */
+  if (flag_graphite_identity
+      || flag_loop_parallelize_all
+      || flag_loop_nest_optimize)
+    flag_graphite = 1;
+
+  return flag_graphite != 0;
+}
+
+namespace {
+
+const pass_data pass_data_graphite =
+{
+  GIMPLE_PASS, /* type */
+  "graphite0", /* name */
+  OPTGROUP_LOOP, /* optinfo_flags */
+  TV_GRAPHITE, /* tv_id */
+  ( PROP_cfg | PROP_ssa ), /* properties_required */
+  0, /* properties_provided */
+  0, /* properties_destroyed */
+  0, /* todo_flags_start */
+  0, /* todo_flags_finish */
+};
+
+class pass_graphite : public gimple_opt_pass
+{
+public:
+  pass_graphite (gcc::context *ctxt)
+    : gimple_opt_pass (pass_data_graphite, ctxt)
+  {}
+
+  /* opt_pass methods: */
+  virtual bool gate (function *) { return gate_graphite_transforms (); }
+
+}; // class pass_graphite
+
+} // anon namespace
+
+gimple_opt_pass *
+make_pass_graphite (gcc::context *ctxt)
+{
+  return new pass_graphite (ctxt);
+}
+
+namespace {
+
+const pass_data pass_data_graphite_transforms =
+{
+  GIMPLE_PASS, /* type */
+  "graphite", /* name */
+  OPTGROUP_LOOP, /* optinfo_flags */
+  TV_GRAPHITE_TRANSFORMS, /* tv_id */
+  ( PROP_cfg | PROP_ssa ), /* properties_required */
+  0, /* properties_provided */
+  0, /* properties_destroyed */
+  0, /* todo_flags_start */
+  0, /* todo_flags_finish */
+};
+
+class pass_graphite_transforms : public gimple_opt_pass
+{
+public:
+  pass_graphite_transforms (gcc::context *ctxt)
+    : gimple_opt_pass (pass_data_graphite_transforms, ctxt)
+  {}
+
+  /* opt_pass methods: */
+  virtual bool gate (function *) { return gate_graphite_transforms (); }
+  virtual unsigned int execute (function *fun) { return graphite_transforms (fun); }
+
+}; // class pass_graphite_transforms
+
+} // anon namespace
+
+gimple_opt_pass *
+make_pass_graphite_transforms (gcc::context *ctxt)
+{
+  return new pass_graphite_transforms (ctxt);
+}
+
+