--- a/gcc/tree-chrec.c	Thu Oct 25 07:37:49 2018 +0900
+++ b/gcc/tree-chrec.c	Thu Feb 13 11:34:05 2020 +0900
@@ -1,5 +1,5 @@
 /* Chains of recurrences.
-   Copyright (C) 2003-2018 Free Software Foundation, Inc.
+   Copyright (C) 2003-2020 Free Software Foundation, Inc.
    Contributed by Sebastian Pop <pop@cri.ensmp.fr>
 
 This file is part of GCC.
@@ -35,8 +35,9 @@
 #include "tree-ssa-loop-ivopts.h"
 #include "tree-ssa-loop-niter.h"
 #include "tree-chrec.h"
+#include "gimple.h"
+#include "tree-ssa-loop.h"
 #include "dumpfile.h"
-#include "params.h"
 #include "tree-scalar-evolution.h"
 
 /* Extended folder for chrecs.  */
@@ -50,8 +51,8 @@
 			   tree poly1)
 {
   tree left, right;
-  struct loop *loop0 = get_chrec_loop (poly0);
-  struct loop *loop1 = get_chrec_loop (poly1);
+  class loop *loop0 = get_chrec_loop (poly0);
+  class loop *loop1 = get_chrec_loop (poly1);
   tree rtype = code == POINTER_PLUS_EXPR ? chrec_type (poly1) : type;
 
   gcc_assert (poly0);
@@ -142,8 +143,8 @@
 {
   tree t0, t1, t2;
   int var;
-  struct loop *loop0 = get_chrec_loop (poly0);
-  struct loop *loop1 = get_chrec_loop (poly1);
+  class loop *loop0 = get_chrec_loop (poly0);
+  class loop *loop1 = get_chrec_loop (poly1);
 
   gcc_assert (poly0);
   gcc_assert (poly1);
@@ -331,9 +332,9 @@
 	    int size = 0;
 	    if ((tree_contains_chrecs (op0, &size)
 		 || tree_contains_chrecs (op1, &size))
-		&& size < PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE))
+		&& size < param_scev_max_expr_size)
 	      return build2 (code, type, op0, op1);
-	    else if (size < PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE))
+	    else if (size < param_scev_max_expr_size)
 	      {
 		if (code == POINTER_PLUS_EXPR)
 		  return fold_build_pointer_plus (fold_convert (type, op0),
@@ -537,7 +538,7 @@
 {
   tree arg0, arg1, binomial_n_k;
   tree type = TREE_TYPE (chrec);
-  struct loop *var_loop = get_loop (cfun, var);
+  class loop *var_loop = get_loop (cfun, var);
 
   while (TREE_CODE (chrec) == POLYNOMIAL_CHREC
 	 && flow_loop_nested_p (var_loop, get_chrec_loop (chrec)))
@@ -718,7 +719,7 @@
 hide_evolution_in_other_loops_than_loop (tree chrec,
 					 unsigned loop_num)
 {
-  struct loop *loop = get_loop (cfun, loop_num), *chloop;
+  class loop *loop = get_loop (cfun, loop_num), *chloop;
   if (automatically_generated_chrec_p (chrec))
     return chrec;
 
@@ -759,7 +760,7 @@
 			     bool right)
 {
   tree component;
-  struct loop *loop = get_loop (cfun, loop_num), *chloop;
+  class loop *loop = get_loop (cfun, loop_num), *chloop;
 
   if (automatically_generated_chrec_p (chrec))
     return chrec;
@@ -841,7 +842,7 @@
 			 tree chrec,
 			 tree new_evol)
 {
-  struct loop *loop = get_loop (cfun, loop_num);
+  class loop *loop = get_loop (cfun, loop_num);
 
   if (POINTER_TYPE_P (chrec_type (chrec)))
     gcc_assert (ptrofftype_p (chrec_type (new_evol)));
@@ -932,10 +933,12 @@
     return false;
 }
 
-/* Determines whether the chrec contains symbolic names or not.  */
+/* Determines whether the chrec contains symbolic names or not.  If LOOP isn't
+   NULL, we also consider chrec wrto outer loops of LOOP as symbol.  */
 
-bool
-chrec_contains_symbols (const_tree chrec)
+static bool
+chrec_contains_symbols (const_tree chrec, hash_set<const_tree> &visited,
+			class loop *loop)
 {
   int i, n;
 
@@ -952,17 +955,94 @@
       || TREE_CODE (chrec) == FIELD_DECL)
     return true;
 
+  if (loop != NULL
+      && TREE_CODE (chrec) == POLYNOMIAL_CHREC
+      && flow_loop_nested_p (get_chrec_loop (chrec), loop))
+    return true;
+
+  if (visited.add (chrec))
+    return false;
+
   n = TREE_OPERAND_LENGTH (chrec);
   for (i = 0; i < n; i++)
-    if (chrec_contains_symbols (TREE_OPERAND (chrec, i)))
+    if (chrec_contains_symbols (TREE_OPERAND (chrec, i), visited, loop))
       return true;
   return false;
 }
 
+/* Return true if CHREC contains any symbols.  If LOOP is not NULL, check if
+   CHREC contains any chrec which is invariant wrto the loop (nest), in other
+   words, chrec defined by outer loops of loop, so from LOOP's point of view,
+   the chrec is considered as a SYMBOL.  */
+
+bool
+chrec_contains_symbols (const_tree chrec, class loop* loop)
+{
+  hash_set<const_tree> visited;
+  return chrec_contains_symbols (chrec, visited, loop);
+}
+
+/* Return true when CHREC contains symbolic names defined in
+   LOOP_NB.  */
+
+static bool
+chrec_contains_symbols_defined_in_loop (const_tree chrec, unsigned loop_nb,
+					hash_set<const_tree> &visited)
+{
+  int i, n;
+
+  if (chrec == NULL_TREE)
+    return false;
+
+  if (is_gimple_min_invariant (chrec))
+    return false;
+
+  if (TREE_CODE (chrec) == SSA_NAME)
+    {
+      gimple *def;
+      loop_p def_loop, loop;
+
+      if (SSA_NAME_IS_DEFAULT_DEF (chrec))
+	return false;
+
+      def = SSA_NAME_DEF_STMT (chrec);
+      def_loop = loop_containing_stmt (def);
+      loop = get_loop (cfun, loop_nb);
+
+      if (def_loop == NULL)
+	return false;
+
+      if (loop == def_loop || flow_loop_nested_p (loop, def_loop))
+	return true;
+
+      return false;
+    }
+
+  if (visited.add (chrec))
+    return false;
+
+  n = TREE_OPERAND_LENGTH (chrec);
+  for (i = 0; i < n; i++)
+    if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec, i),
+						loop_nb, visited))
+      return true;
+  return false;
+}
+
+/* Return true when CHREC contains symbolic names defined in
+   LOOP_NB.  */
+
+bool
+chrec_contains_symbols_defined_in_loop (const_tree chrec, unsigned loop_nb)
+{
+  hash_set<const_tree> visited;
+  return chrec_contains_symbols_defined_in_loop (chrec, loop_nb, visited);
+}
+
 /* Determines whether the chrec contains undetermined coefficients.  */
 
-bool
-chrec_contains_undetermined (const_tree chrec)
+static bool
+chrec_contains_undetermined (const_tree chrec, hash_set<const_tree> &visited)
 {
   int i, n;
 
@@ -972,19 +1052,29 @@
   if (chrec == NULL_TREE)
     return false;
 
+  if (visited.add (chrec))
+    return false;
+
   n = TREE_OPERAND_LENGTH (chrec);
   for (i = 0; i < n; i++)
-    if (chrec_contains_undetermined (TREE_OPERAND (chrec, i)))
+    if (chrec_contains_undetermined (TREE_OPERAND (chrec, i), visited))
       return true;
   return false;
 }
 
+bool
+chrec_contains_undetermined (const_tree chrec)
+{
+  hash_set<const_tree> visited;
+  return chrec_contains_undetermined (chrec, visited);
+}
+
 /* Determines whether the tree EXPR contains chrecs, and increment
    SIZE if it is not a NULL pointer by an estimation of the depth of
    the tree.  */
 
-bool
-tree_contains_chrecs (const_tree expr, int *size)
+static bool
+tree_contains_chrecs (const_tree expr, int *size, hash_set<const_tree> &visited)
 {
   int i, n;
 
@@ -997,13 +1087,24 @@
   if (tree_is_chrec (expr))
     return true;
 
+  if (visited.add (expr))
+    return false;
+
   n = TREE_OPERAND_LENGTH (expr);
   for (i = 0; i < n; i++)
-    if (tree_contains_chrecs (TREE_OPERAND (expr, i), size))
+    if (tree_contains_chrecs (TREE_OPERAND (expr, i), size, visited))
       return true;
   return false;
 }
 
+bool
+tree_contains_chrecs (const_tree expr, int *size)
+{
+  hash_set<const_tree> visited;
+  return tree_contains_chrecs (expr, size, visited);
+}
+
+
 /* Recursive helper function.  */
 
 static bool
@@ -1105,23 +1206,30 @@
 }
 
 /* Determine whether the given tree is a function in zero or one
-   variables.  */
+   variables with respect to loop specified by LOOPNUM.  Note only positive
+   LOOPNUM stands for a real loop.  */
 
 bool
-evolution_function_is_univariate_p (const_tree chrec)
+evolution_function_is_univariate_p (const_tree chrec, int loopnum)
 {
   if (chrec == NULL_TREE)
     return true;
 
+  tree sub_chrec;
   switch (TREE_CODE (chrec))
     {
     case POLYNOMIAL_CHREC:
       switch (TREE_CODE (CHREC_LEFT (chrec)))
 	{
 	case POLYNOMIAL_CHREC:
-	  if (CHREC_VARIABLE (chrec) != CHREC_VARIABLE (CHREC_LEFT (chrec)))
+	  sub_chrec = CHREC_LEFT (chrec);
+	  if (CHREC_VARIABLE (chrec) != CHREC_VARIABLE (sub_chrec)
+	      && (loopnum <= 0
+		  || CHREC_VARIABLE (sub_chrec) == (unsigned) loopnum
+		  || flow_loop_nested_p (get_loop (cfun, loopnum),
+					 get_chrec_loop (sub_chrec))))
 	    return false;
-	  if (!evolution_function_is_univariate_p (CHREC_LEFT (chrec)))
+	  if (!evolution_function_is_univariate_p (sub_chrec, loopnum))
 	    return false;
 	  break;
 
@@ -1134,9 +1242,14 @@
       switch (TREE_CODE (CHREC_RIGHT (chrec)))
 	{
 	case POLYNOMIAL_CHREC:
-	  if (CHREC_VARIABLE (chrec) != CHREC_VARIABLE (CHREC_RIGHT (chrec)))
+	  sub_chrec = CHREC_RIGHT (chrec);
+	  if (CHREC_VARIABLE (chrec) != CHREC_VARIABLE (sub_chrec)
+	      && (loopnum <= 0
+		  || CHREC_VARIABLE (sub_chrec) == (unsigned) loopnum
+		  || flow_loop_nested_p (get_loop (cfun, loopnum),
+					 get_chrec_loop (sub_chrec))))
 	    return false;
-	  if (!evolution_function_is_univariate_p (CHREC_RIGHT (chrec)))
+	  if (!evolution_function_is_univariate_p (sub_chrec, loopnum))
 	    return false;
 	  break;
 
@@ -1182,7 +1295,7 @@
    the conversion succeeded, false otherwise.  */
 
 bool
-convert_affine_scev (struct loop *loop, tree type,
+convert_affine_scev (class loop *loop, tree type,
 		     tree *base, tree *step, gimple *at_stmt,
 		     bool use_overflow_semantics, tree from)
 {
@@ -1313,7 +1426,7 @@
 {
   tree ct, res;
   tree base, step;
-  struct loop *loop;
+  class loop *loop;
 
   if (automatically_generated_chrec_p (chrec))
     return chrec;
@@ -1449,7 +1562,7 @@
   if (!*fold_conversions && evolution_function_is_affine_p (chrec))
     {
       tree base, step;
-      struct loop *loop;
+      class loop *loop;
 
       loop = get_chrec_loop (chrec);
       base = CHREC_LEFT (chrec);