--- a/gcc/tree-ssa-loop-ch.c	Thu Oct 25 07:37:49 2018 +0900
+++ b/gcc/tree-ssa-loop-ch.c	Thu Feb 13 11:34:05 2020 +0900
@@ -1,5 +1,5 @@
 /* Loop header copying on trees.
-   Copyright (C) 2004-2018 Free Software Foundation, Inc.
+   Copyright (C) 2004-2020 Free Software Foundation, Inc.
 
 This file is part of GCC.
 
@@ -33,7 +33,9 @@
 #include "tree-inline.h"
 #include "tree-ssa-scopedtables.h"
 #include "tree-ssa-threadedge.h"
-#include "params.h"
+#include "tree-ssa-sccvn.h"
+#include "tree-phinodes.h"
+#include "ssa-iterators.h"
 
 /* Duplicates headers of loops if they are small enough, so that the statements
    in the loop body are always executed when the loop is entered.  This
@@ -45,11 +47,10 @@
    amount.  */
 
 static bool
-should_duplicate_loop_header_p (basic_block header, struct loop *loop,
+should_duplicate_loop_header_p (basic_block header, class loop *loop,
 				int *limit)
 {
   gimple_stmt_iterator bsi;
-  gimple *last;
 
   gcc_assert (!header->aux);
 
@@ -98,8 +99,8 @@
       return false;
     }
 
-  last = last_stmt (header);
-  if (gimple_code (last) != GIMPLE_COND)
+  gcond *last = safe_dyn_cast <gcond *> (last_stmt (header));
+  if (!last)
     {
       if (dump_file && (dump_flags & TDF_DETAILS))
 	fprintf (dump_file,
@@ -108,10 +109,24 @@
       return false;
     }
 
-  /* Count number of instructions and punt on calls.  */
+  for (gphi_iterator psi = gsi_start_phis (header); !gsi_end_p (psi);
+       gsi_next (&psi))
+    {
+      gphi *phi = psi.phi ();
+      tree res = gimple_phi_result (phi);
+      if (INTEGRAL_TYPE_P (TREE_TYPE (res))
+	  || POINTER_TYPE_P (TREE_TYPE (res)))
+	gimple_set_uid (phi, 1 /* IV */);
+      else
+	gimple_set_uid (phi, 0);
+    }
+
+  /* Count number of instructions and punt on calls.
+     Populate stmts INV/IV flag to later apply heuristics to the
+     kind of conditions we want to copy.  */
   for (bsi = gsi_start_bb (header); !gsi_end_p (bsi); gsi_next (&bsi))
     {
-      last = gsi_stmt (bsi);
+      gimple *last = gsi_stmt (bsi);
 
       if (gimple_code (last) == GIMPLE_LABEL)
 	continue;
@@ -141,7 +156,52 @@
 		     header->index);
 	  return false;
 	}
+
+      /* Classify the stmt based on whether its computation is based
+         on a IV or whether it is invariant in the loop.  */
+      gimple_set_uid (last, 0);
+      if (!gimple_vuse (last))
+	{
+	  bool inv = true;
+	  bool iv = false;
+	  ssa_op_iter i;
+	  tree op;
+	  FOR_EACH_SSA_TREE_OPERAND (op, last, i, SSA_OP_USE)
+	    if (!SSA_NAME_IS_DEFAULT_DEF (op)
+		&& flow_bb_inside_loop_p (loop,
+					  gimple_bb (SSA_NAME_DEF_STMT (op))))
+	      {
+		if (!(gimple_uid (SSA_NAME_DEF_STMT (op)) & 2 /* INV */))
+		  inv = false;
+		if (gimple_uid (SSA_NAME_DEF_STMT (op)) & 1 /* IV */)
+		  iv = true;
+	      }
+	  gimple_set_uid (last, (iv ? 1 : 0) | (inv ? 2 : 0));
+	}
     }
+
+  /* If the condition tests a non-IV loop variant we do not want to rotate
+     the loop further.  Unless this is the original loop header.  */
+  tree lhs = gimple_cond_lhs (last);
+  tree rhs = gimple_cond_rhs (last);
+  if (header != loop->header
+      && ((TREE_CODE (lhs) == SSA_NAME
+	   && !SSA_NAME_IS_DEFAULT_DEF (lhs)
+	   && flow_bb_inside_loop_p (loop, gimple_bb (SSA_NAME_DEF_STMT (lhs)))
+	   && gimple_uid (SSA_NAME_DEF_STMT (lhs)) == 0)
+	  || (TREE_CODE (rhs) == SSA_NAME
+	      && !SSA_NAME_IS_DEFAULT_DEF (rhs)
+	      && flow_bb_inside_loop_p (loop,
+					gimple_bb (SSA_NAME_DEF_STMT (rhs)))
+	      && gimple_uid (SSA_NAME_DEF_STMT (rhs)) == 0)))
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file,
+		 "  Not duplicating bb %i: condition based on non-IV loop"
+		 " variant.\n", header->index);
+      return false;
+    }
+
   if (dump_file && (dump_flags & TDF_DETAILS))
     fprintf (dump_file, "    Will duplicate bb %i\n", header->index); 
   return true;
@@ -150,7 +210,7 @@
 /* Checks whether LOOP is a do-while style loop.  */
 
 static bool
-do_while_loop_p (struct loop *loop)
+do_while_loop_p (class loop *loop)
 {
   gimple *stmt = last_stmt (loop->latch);
 
@@ -207,7 +267,7 @@
   unsigned int copy_headers (function *fun);
 
   /* Return true to copy headers of LOOP or false to skip.  */
-  virtual bool process_loop_p (struct loop *loop) = 0;
+  virtual bool process_loop_p (class loop *loop) = 0;
 };
 
 const pass_data pass_data_ch =
@@ -240,7 +300,7 @@
 
 protected:
   /* ch_base method: */
-  virtual bool process_loop_p (struct loop *loop);
+  virtual bool process_loop_p (class loop *loop);
 }; // class pass_ch
 
 const pass_data pass_data_ch_vect =
@@ -278,7 +338,7 @@
 
 protected:
   /* ch_base method: */
-  virtual bool process_loop_p (struct loop *loop);
+  virtual bool process_loop_p (class loop *loop);
 }; // class pass_ch_vect
 
 /* For all loops, copy the condition at the end of the loop body in front
@@ -288,7 +348,7 @@
 unsigned int
 ch_base::copy_headers (function *fun)
 {
-  struct loop *loop;
+  class loop *loop;
   basic_block header;
   edge exit, entry;
   basic_block *bbs, *copied_bbs;
@@ -297,15 +357,17 @@
   bool changed = false;
 
   if (number_of_loops (fun) <= 1)
-      return 0;
+    return 0;
 
   bbs = XNEWVEC (basic_block, n_basic_blocks_for_fn (fun));
   copied_bbs = XNEWVEC (basic_block, n_basic_blocks_for_fn (fun));
   bbs_size = n_basic_blocks_for_fn (fun);
 
+  auto_vec<std::pair<edge, loop_p> > copied;
+
   FOR_EACH_LOOP (loop, 0)
     {
-      int initial_limit = PARAM_VALUE (PARAM_MAX_LOOP_HEADER_INSNS);
+      int initial_limit = param_max_loop_header_insns;
       int remaining_limit = initial_limit;
       if (dump_file && (dump_flags & TDF_DETAILS))
 	fprintf (dump_file,
@@ -340,11 +402,6 @@
 	  bbs[n_bbs++] = header;
 	  gcc_assert (bbs_size > n_bbs);
 	  header = exit->dest;
-	  /* Make sure to stop copying after we copied the first exit test.
-	     Without further heuristics we do not want to rotate the loop
-	     any further.  */
-	  if (loop_exits_from_bb_p (loop, exit->src))
-	    break;
 	}
 
       if (!exit)
@@ -371,6 +428,7 @@
 	  fprintf (dump_file, "Duplication failed.\n");
 	  continue;
 	}
+      copied.safe_push (std::make_pair (entry, loop));
 
       /* If the loop has the form "for (i = j; i < j + 10; i++)" then
 	 this copying can introduce a case where we rely on undefined
@@ -393,11 +451,23 @@
 		{
 		  gimple *stmt = gsi_stmt (bsi);
 		  if (gimple_code (stmt) == GIMPLE_COND)
-		    gimple_set_no_warning (stmt, true);
+		    {
+		      tree lhs = gimple_cond_lhs (stmt);
+		      if (gimple_cond_code (stmt) != EQ_EXPR
+			  && gimple_cond_code (stmt) != NE_EXPR
+			  && INTEGRAL_TYPE_P (TREE_TYPE (lhs))
+			  && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (lhs)))
+			gimple_set_no_warning (stmt, true);
+		    }
 		  else if (is_gimple_assign (stmt))
 		    {
 		      enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
-		      if (TREE_CODE_CLASS (rhs_code) == tcc_comparison)
+		      tree rhs1 = gimple_assign_rhs1 (stmt);
+		      if (TREE_CODE_CLASS (rhs_code) == tcc_comparison
+			  && rhs_code != EQ_EXPR
+			  && rhs_code != NE_EXPR
+			  && INTEGRAL_TYPE_P (TREE_TYPE (rhs1))
+			  && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (rhs1)))
 			gimple_set_no_warning (stmt, true);
 		    }
 		}
@@ -422,7 +492,28 @@
     }
 
   if (changed)
-    update_ssa (TODO_update_ssa);
+    {
+      update_ssa (TODO_update_ssa);
+      /* After updating SSA form perform CSE on the loop header
+	 copies.  This is esp. required for the pass before
+	 vectorization since nothing cleans up copied exit tests
+	 that can now be simplified.  CSE from the entry of the
+	 region we copied till all loop exit blocks but not
+	 entering the loop itself.  */
+      for (unsigned i = 0; i < copied.length (); ++i)
+	{
+	  edge entry = copied[i].first;
+	  loop_p loop = copied[i].second;
+	  vec<edge> exit_edges = get_loop_exit_edges (loop);
+	  bitmap exit_bbs = BITMAP_ALLOC (NULL);
+	  for (unsigned j = 0; j < exit_edges.length (); ++j)
+	    bitmap_set_bit (exit_bbs, exit_edges[j]->dest->index);
+	  bitmap_set_bit (exit_bbs, loop->header->index);
+	  do_rpo_vn (cfun, entry, exit_bbs);
+	  BITMAP_FREE (exit_bbs);
+	  exit_edges.release ();
+	}
+    }
   free (bbs);
   free (copied_bbs);
 
@@ -457,7 +548,7 @@
 /* Apply header copying according to a very simple test of do-while shape.  */
 
 bool
-pass_ch::process_loop_p (struct loop *loop)
+pass_ch::process_loop_p (class loop *loop)
 {
   return !do_while_loop_p (loop);
 }
@@ -465,7 +556,7 @@
 /* Apply header-copying to loops where we might enable vectorization.  */
 
 bool
-pass_ch_vect::process_loop_p (struct loop *loop)
+pass_ch_vect::process_loop_p (class loop *loop)
 {
   if (!flag_tree_loop_vectorize && !loop->force_vectorize)
     return false;
@@ -473,24 +564,13 @@
   if (loop->dont_vectorize)
     return false;
 
-  if (!do_while_loop_p (loop))
-    return true;
-
- /* The vectorizer won't handle anything with multiple exits, so skip.  */
+  /* The vectorizer won't handle anything with multiple exits, so skip.  */
   edge exit = single_exit (loop);
   if (!exit)
     return false;
 
-  /* Copy headers iff there looks to be code in the loop after the exit block,
-     i.e. the exit block has an edge to another block (besides the latch,
-     which should be empty).  */
-  edge_iterator ei;
-  edge e;
-  FOR_EACH_EDGE (e, ei, exit->src->succs)
-    if (!loop_exit_edge_p (loop, e)
-	&& e->dest != loop->header
-	&& e->dest != loop->latch)
-      return true;
+  if (!do_while_loop_p (loop))
+    return true;
 
   return false;
 }