CbC/CbC_gcc: gcc/tree-ssa-loop-ch.c comparison

comparison gcc/tree-ssa-loop-ch.c @ 145:1830386684a0

gcc-9.2.0

author	anatofuz
date	Thu, 13 Feb 2020 11:34:05 +0900
parents	84e7813d76e9
children

comparison

equal deleted inserted replaced

-:84e7813d76e9
+:1830386684a0
 /* 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.
 GCC is free software; you can redistribute it and/or modify it
 under the terms of the GNU General Public License as published by the
 #include "tree-into-ssa.h"
 #include "cfgloop.h"
 #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
 increases effectiveness of code motion optimizations, and reduces the need
 for loop preconditioning.  */
 /* Check whether we should duplicate HEADER of LOOP.  At most *LIMIT
 instructions should be duplicated, limit is decreased by the actual
 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);
 /* Loop header copying usually increases size of the code.  This used not to
 be true, since quite often it is possible to verify that the condition is
 		 "  Not duplicating bb %i: it has mutiple predecestors.\n",
 		 header->index);
 return false;
 }
-last = last_stmt (header);
+gcond *last = safe_dyn_cast <gcond *> (last_stmt (header));
-if (gimple_code (last) != GIMPLE_COND)
+if (!last)
 {
 if (dump_file && (dump_flags & TDF_DETAILS))
 	fprintf (dump_file,
 		 "  Not duplicating bb %i: it does not end by conditional.\n",
 		 header->index);
 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;
 if (is_gimple_debug (last))
 	    fprintf (dump_file,
 		     "  Not duplicating bb %i contains too many insns.\n",
 		     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;
 }
 /* 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);
 /* If the latch of the loop is not empty, it is not a do-while loop.  */
 if (stmt
 /* Copies headers of all loops in FUN for which process_loop_p is true.  */
 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 =
 {
 GIMPLE_PASS, /* type */
 opt_pass * clone () { return new pass_ch (m_ctxt); }
 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 =
 {
 GIMPLE_PASS, /* type */
 /* Just copy headers, no initialization/finalization of loop structures.  */
 virtual unsigned int execute (function *);
 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
 of the loop.  This is beneficial since it increases efficiency of
 code motion optimizations.  It also saves one jump on entry to the loop.  */
 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;
 unsigned n_bbs;
 unsigned bbs_size;
 bool changed = false;
 if (number_of_loops (fun) <= 1)
 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,
 		 "Analyzing loop %i\n", loop->num);
 	  else
 	    exit = EDGE_SUCC (header, 1);
 	  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)
 	continue;
 					 true))
 	{
 	  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
 	 signed overflow to eliminate the preheader condition, because
 	 we assume that "j < j + 10" is true.  We don't want to warn
 		   !gsi_end_p (bsi);
 		   gsi_next (&bsi))
 		{
 		  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);
 		    }
 		}
 	    }
 	}
 changed = true;
 }
 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);
 return changed ? TODO_cleanup_cfg : 0;
 }
 }
 /* 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);
 }
 /* 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;
 if (loop->dont_vectorize)
 return false;
-if (!do_while_loop_p (loop))
+/* The vectorizer won't handle anything with multiple exits, so skip.  */
-return true;
-/* 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,
+if (!do_while_loop_p (loop))
-i.e. the exit block has an edge to another block (besides the latch,
+return true;
-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;
 return false;
 }
 } // anon namespace

Mercurial > hg > CbC > CbC_gcc

comparison gcc/tree-ssa-loop-ch.c @ 145:1830386684a0