CbC/CbC_gcc: gcc/tree-ssa-phiopt.c comparison

comparison gcc/tree-ssa-phiopt.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
 /* Optimization of PHI nodes by converting them into straightline code.
-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 "domwalk.h"
 #include "cfgloop.h"
 #include "tree-data-ref.h"
 #include "tree-scalar-evolution.h"
 #include "tree-inline.h"
-#include "params.h"
 #include "case-cfn-macros.h"
 static unsigned int tree_ssa_phiopt_worker (bool, bool, bool);
+static bool two_value_replacement (basic_block, basic_block, edge, gphi *,
+				   tree, tree);
 static bool conditional_replacement (basic_block, basic_block,
 				     edge, edge, gphi *, tree, tree);
 static gphi *factor_out_conditional_conversion (edge, edge, gphi *, tree, tree,
 						gimple *);
 static int value_replacement (basic_block, basic_block,
 	      arg1 = gimple_phi_arg_def (phi, e2->dest_idx);
 	      gcc_assert (arg0 != NULL_TREE && arg1 != NULL_TREE);
 	    }
 	  /* Do the replacement of conditional if it can be done.  */
-	  if (!early_p
+	  if (two_value_replacement (bb, bb1, e2, phi, arg0, arg1))
-	      && conditional_replacement (bb, bb1, e1, e2, phi, arg0, arg1))
+	    cfgchanged = true;
+	  else if (!early_p
+		   && conditional_replacement (bb, bb1, e1, e2, phi,
+					       arg0, arg1))
 	    cfgchanged = true;
 	  else if (abs_replacement (bb, bb1, e1, e2, phi, arg0, arg1))
 	    cfgchanged = true;
 	  else if (!early_p
 		   && cond_removal_in_popcount_pattern (bb, bb1, e1, e2,
 gimple *arg0_def_stmt = NULL, *arg1_def_stmt = NULL, *new_stmt;
 tree new_arg0 = NULL_TREE, new_arg1 = NULL_TREE;
 tree temp, result;
 gphi *newphi;
 gimple_stmt_iterator gsi, gsi_for_def;
-source_location locus = gimple_location (phi);
+location_t locus = gimple_location (phi);
 enum tree_code convert_code;
 /* Handle only PHI statements with two arguments.  TODO: If all
 other arguments to PHI are INTEGER_CST or if their defining
 statement have the same unary operation, we can handle more
 		  && gimple_bb (arg0_def_stmt) == e0->src)
 		{
 		  gsi = gsi_for_stmt (arg0_def_stmt);
 		  gsi_prev_nondebug (&gsi);
 		  if (!gsi_end_p (gsi))
-		    return NULL;
+		    {
+		      if (gassign *assign
+			    = dyn_cast <gassign *> (gsi_stmt (gsi)))
+			{
+			  tree lhs = gimple_assign_lhs (assign);
+			  enum tree_code ass_code
+			    = gimple_assign_rhs_code (assign);
+			  if (ass_code != MAX_EXPR && ass_code != MIN_EXPR)
+			    return NULL;
+			  if (lhs != gimple_assign_rhs1 (arg0_def_stmt))
+			    return NULL;
+			  gsi_prev_nondebug (&gsi);
+			  if (!gsi_end_p (gsi))
+			    return NULL;
+			}
+		      else
+			return NULL;
+		    }
 		  gsi = gsi_for_stmt (arg0_def_stmt);
 		  gsi_next_nondebug (&gsi);
 		  if (!gsi_end_p (gsi))
 		    return NULL;
 		}
 gsi = gsi_for_stmt (phi);
 gsi_remove (&gsi, true);
 return newphi;
 }
+/* Optimize
+# x_5 in range [cst1, cst2] where cst2 = cst1 + 1
+if (x_5 op cstN) # where op is == or != and N is 1 or 2
+goto bb3;
+else
+goto bb4;
+bb3:
+bb4:
+# r_6 = PHI<cst3(2), cst4(3)> # where cst3 == cst4 + 1 or cst4 == cst3 + 1
+to r_6 = x_5 + (min (cst3, cst4) - cst1) or
+r_6 = (min (cst3, cst4) + cst1) - x_5 depending on op, N and which
+of cst3 and cst4 is smaller.  */
+static bool
+two_value_replacement (basic_block cond_bb, basic_block middle_bb,
+		       edge e1, gphi *phi, tree arg0, tree arg1)
+{
+/* Only look for adjacent integer constants.  */
+if (!INTEGRAL_TYPE_P (TREE_TYPE (arg0))
+|| !INTEGRAL_TYPE_P (TREE_TYPE (arg1))
+|| TREE_CODE (arg0) != INTEGER_CST
+|| TREE_CODE (arg1) != INTEGER_CST
+|| (tree_int_cst_lt (arg0, arg1)
+	  ? wi::to_widest (arg0) + 1 != wi::to_widest (arg1)
+	  : wi::to_widest (arg1) + 1 != wi::to_widest (arg0)))
+return false;
+if (!empty_block_p (middle_bb))
+return false;
+gimple *stmt = last_stmt (cond_bb);
+tree lhs = gimple_cond_lhs (stmt);
+tree rhs = gimple_cond_rhs (stmt);
+if (TREE_CODE (lhs) != SSA_NAME
+|| !INTEGRAL_TYPE_P (TREE_TYPE (lhs))
+|| TREE_CODE (TREE_TYPE (lhs)) == BOOLEAN_TYPE
+|| TREE_CODE (rhs) != INTEGER_CST)
+return false;
+switch (gimple_cond_code (stmt))
+{
+case EQ_EXPR:
+case NE_EXPR:
+break;
+default:
+return false;
+}
+wide_int min, max;
+if (get_range_info (lhs, &min, &max) != VR_RANGE
+|| min + 1 != max
+|| (wi::to_wide (rhs) != min
+	  && wi::to_wide (rhs) != max))
+return false;
+/* We need to know which is the true edge and which is the false
+edge so that we know when to invert the condition below.  */
+edge true_edge, false_edge;
+extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
+if ((gimple_cond_code (stmt) == EQ_EXPR)
+^ (wi::to_wide (rhs) == max)
+^ (e1 == false_edge))
+std::swap (arg0, arg1);
+tree type;
+if (TYPE_PRECISION (TREE_TYPE (lhs)) == TYPE_PRECISION (TREE_TYPE (arg0)))
+{
+/* Avoid performing the arithmetics in bool type which has different
+	 semantics, otherwise prefer unsigned types from the two with
+	 the same precision.  */
+if (TREE_CODE (TREE_TYPE (arg0)) == BOOLEAN_TYPE
+	  || !TYPE_UNSIGNED (TREE_TYPE (arg0)))
+	type = TREE_TYPE (lhs);
+else
+	type = TREE_TYPE (arg0);
+}
+else if (TYPE_PRECISION (TREE_TYPE (lhs)) > TYPE_PRECISION (TREE_TYPE (arg0)))
+type = TREE_TYPE (lhs);
+else
+type = TREE_TYPE (arg0);
+min = wide_int::from (min, TYPE_PRECISION (type),
+			TYPE_SIGN (TREE_TYPE (lhs)));
+wide_int a = wide_int::from (wi::to_wide (arg0), TYPE_PRECISION (type),
+			       TYPE_SIGN (TREE_TYPE (arg0)));
+enum tree_code code;
+wi::overflow_type ovf;
+if (tree_int_cst_lt (arg0, arg1))
+{
+code = PLUS_EXPR;
+a -= min;
+if (!TYPE_UNSIGNED (type))
+	{
+	  /* lhs is known to be in range [min, min+1] and we want to add a
+	     to it.  Check if that operation can overflow for those 2 values
+	     and if yes, force unsigned type.  */
+	  wi::add (min + (wi::neg_p (a) ? 0 : 1), a, SIGNED, &ovf);
+	  if (ovf)
+	    type = unsigned_type_for (type);
+	}
+}
+else
+{
+code = MINUS_EXPR;
+a += min;
+if (!TYPE_UNSIGNED (type))
+	{
+	  /* lhs is known to be in range [min, min+1] and we want to subtract
+	     it from a.  Check if that operation can overflow for those 2
+	     values and if yes, force unsigned type.  */
+	  wi::sub (a, min + (wi::neg_p (min) ? 0 : 1), SIGNED, &ovf);
+	  if (ovf)
+	    type = unsigned_type_for (type);
+	}
+}
+tree arg = wide_int_to_tree (type, a);
+gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
+if (!useless_type_conversion_p (type, TREE_TYPE (lhs)))
+lhs = gimplify_build1 (&gsi, NOP_EXPR, type, lhs);
+tree new_rhs;
+if (code == PLUS_EXPR)
+new_rhs = gimplify_build2 (&gsi, PLUS_EXPR, type, lhs, arg);
+else
+new_rhs = gimplify_build2 (&gsi, MINUS_EXPR, type, arg, lhs);
+if (!useless_type_conversion_p (TREE_TYPE (arg0), type))
+new_rhs = gimplify_build1 (&gsi, NOP_EXPR, TREE_TYPE (arg0), new_rhs);
+replace_phi_edge_with_variable (cond_bb, e1, phi, new_rhs);
+/* Note that we optimized this PHI.  */
+return true;
+}
 /*  The function conditional_replacement does the main work of doing the
 conditional replacement.  Return true if the replacement is done.
 Otherwise return false.
 BB is the basic block where the replacement is going to be done on.  ARG0
 is argument 0 from PHI.  Likewise for ARG1.  */
 new_var = force_gimple_operand_gsi (&gsi, cond, true, NULL, true,
 				      GSI_SAME_STMT);
 if (!useless_type_conversion_p (TREE_TYPE (result), TREE_TYPE (new_var)))
 {
-source_location locus_0, locus_1;
+location_t locus_0, locus_1;
 new_var2 = make_ssa_name (TREE_TYPE (result));
 new_stmt = gimple_build_assign (new_var2, CONVERT_EXPR, new_var);
 gsi_insert_before (&gsi, new_stmt, GSI_SAME_STMT);
 new_var = new_var2;
 static bool
 minmax_replacement (basic_block cond_bb, basic_block middle_bb,
 		    edge e0, edge e1, gimple *phi,
 		    tree arg0, tree arg1)
 {
-tree result, type;
+tree result, type, rhs;
 gcond *cond;
 gassign *new_stmt;
 edge true_edge, false_edge;
 enum tree_code cmp, minmax, ass_code;
 tree smaller, alt_smaller, larger, alt_larger, arg_true, arg_false;
 if (HONOR_NANS (type) || HONOR_SIGNED_ZEROS (type))
 return false;
 cond = as_a <gcond *> (last_stmt (cond_bb));
 cmp = gimple_cond_code (cond);
+rhs = gimple_cond_rhs (cond);
+/* Turn EQ/NE of extreme values to order comparisons.  */
+if ((cmp == NE_EXPR || cmp == EQ_EXPR)
+&& TREE_CODE (rhs) == INTEGER_CST
+&& INTEGRAL_TYPE_P (TREE_TYPE (rhs)))
+{
+if (wi::eq_p (wi::to_wide (rhs), wi::min_value (TREE_TYPE (rhs))))
+	{
+	  cmp = (cmp == EQ_EXPR) ? LT_EXPR : GE_EXPR;
+	  rhs = wide_int_to_tree (TREE_TYPE (rhs),
+				  wi::min_value (TREE_TYPE (rhs)) + 1);
+	}
+else if (wi::eq_p (wi::to_wide (rhs), wi::max_value (TREE_TYPE (rhs))))
+	{
+	  cmp = (cmp == EQ_EXPR) ? GT_EXPR : LE_EXPR;
+	  rhs = wide_int_to_tree (TREE_TYPE (rhs),
+				  wi::max_value (TREE_TYPE (rhs)) - 1);
+	}
+}
 /* This transformation is only valid for order comparisons.  Record which
 operand is smaller/larger if the result of the comparison is true.  */
 alt_smaller = NULL_TREE;
 alt_larger = NULL_TREE;
 if (cmp == LT_EXPR || cmp == LE_EXPR)
 {
 smaller = gimple_cond_lhs (cond);
-larger = gimple_cond_rhs (cond);
+larger = rhs;
 /* If we have smaller < CST it is equivalent to smaller <= CST-1.
 	 Likewise smaller <= CST is equivalent to smaller < CST+1.  */
-if (TREE_CODE (larger) == INTEGER_CST)
+if (TREE_CODE (larger) == INTEGER_CST
+	  && INTEGRAL_TYPE_P (TREE_TYPE (larger)))
 	{
 	  if (cmp == LT_EXPR)
 	    {
 	      wi::overflow_type overflow;
 	      wide_int alt = wi::sub (wi::to_wide (larger), 1,
 	    }
 	}
 }
 else if (cmp == GT_EXPR || cmp == GE_EXPR)
 {
-smaller = gimple_cond_rhs (cond);
+smaller = rhs;
 larger = gimple_cond_lhs (cond);
 /* If we have larger > CST it is equivalent to larger >= CST+1.
 	 Likewise larger >= CST is equivalent to larger > CST-1.  */
-if (TREE_CODE (smaller) == INTEGER_CST)
+if (TREE_CODE (smaller) == INTEGER_CST
+	  && INTEGRAL_TYPE_P (TREE_TYPE (smaller)))
 	{
 	  wi::overflow_type overflow;
 	  if (cmp == GT_EXPR)
 	    {
 	      wide_int alt = wi::add (wi::to_wide (smaller), 1,
 /* OTHER_BLOCK must have only one executable statement which must have the
 form arg0 = -arg1 or arg1 = -arg0.  */
 assign = last_and_only_stmt (middle_bb);
-/* If we did not find the proper negation assignment, then we can not
+/* If we did not find the proper negation assignment, then we cannot
 optimize.  */
 if (assign == NULL)
 return false;
 /* If we got here, then we have found the only executable statement
 in OTHER_BLOCK.  If it is anything other than arg = -arg1 or
-arg1 = -arg0, then we can not optimize.  */
+arg1 = -arg0, then we cannot optimize.  */
 if (gimple_code (assign) != GIMPLE_ASSIGN)
 return false;
 lhs = gimple_assign_lhs (assign);
 JOIN_BB:
 some more
 We check that MIDDLE_BB contains only one store, that that store
 doesn't trap (not via NOTRAP, but via checking if an access to the same
-memory location dominates us) and that the store has a "simple" RHS.  */
+memory location dominates us, or the store is to a local addressable
+object) and that the store has a "simple" RHS.  */
 static bool
 cond_store_replacement (basic_block middle_bb, basic_block join_bb,
 			edge e0, edge e1, hash_set<tree> *nontrap)
 {
 gimple *assign = last_and_only_stmt (middle_bb);
 tree lhs, rhs, name, name2;
 gphi *newphi;
 gassign *new_stmt;
 gimple_stmt_iterator gsi;
-source_location locus;
+location_t locus;
 /* Check if middle_bb contains of only one store.  */
 if (!assign
 || !gimple_assign_single_p (assign)
 || gimple_has_volatile_ops (assign))
 return false;
+/* And no PHI nodes so all uses in the single stmt are also
+available where we insert to.  */
+if (!gimple_seq_empty_p (phi_nodes (middle_bb)))
+return false;
 locus = gimple_location (assign);
 lhs = gimple_assign_lhs (assign);
 rhs = gimple_assign_rhs1 (assign);
-if (TREE_CODE (lhs) != MEM_REF
+if ((TREE_CODE (lhs) != MEM_REF
-|| TREE_CODE (TREE_OPERAND (lhs, 0)) != SSA_NAME
+&& TREE_CODE (lhs) != ARRAY_REF
+&& TREE_CODE (lhs) != COMPONENT_REF)
 || !is_gimple_reg_type (TREE_TYPE (lhs)))
 return false;
 /* Prove that we can move the store down.  We could also check
 TREE_THIS_NOTRAP here, but in that case we also could move stores,
 whose value is not available readily, which we want to avoid.  */
 if (!nontrap->contains (lhs))
-return false;
+{
+/* If LHS is a local variable without address-taken, we could
+	 always safely move down the store.  */
+tree base = get_base_address (lhs);
+if (!auto_var_p (base) || TREE_ADDRESSABLE (base))
+	return false;
+}
 /* Now we've checked the constraints, so do the transformation:
 1) Remove the single store.  */
 gsi = gsi_for_stmt (assign);
 unlink_stmt_vdef (assign);
 /* 2) Insert a load from the memory of the store to the temporary
 on the edge which did not contain the store.  */
 name = make_temp_ssa_name (TREE_TYPE (lhs), NULL, "cstore");
 new_stmt = gimple_build_assign (name, lhs);
 gimple_set_location (new_stmt, locus);
+lhs = unshare_expr (lhs);
+/* Set TREE_NO_WARNING on the rhs of the load to avoid uninit
+warnings.  */
+TREE_NO_WARNING (gimple_assign_rhs1 (new_stmt)) = 1;
 gsi_insert_on_edge (e1, new_stmt);
 /* 3) Create a PHI node at the join block, with one argument
 holding the old RHS, and the other holding the temporary
 where we stored the old memory contents.  */
 name2 = make_temp_ssa_name (TREE_TYPE (lhs), NULL, "cstore");
 newphi = create_phi_node (name2, join_bb);
 add_phi_arg (newphi, rhs, e0, locus);
 add_phi_arg (newphi, name, e1, locus);
-lhs = unshare_expr (lhs);
 new_stmt = gimple_build_assign (lhs, PHI_RESULT (newphi));
 /* 4) Insert that PHI node.  */
 gsi = gsi_after_labels (join_bb);
 if (gsi_end_p (gsi))
 gsi = gsi_last_bb (join_bb);
 gsi_insert_after (&gsi, new_stmt, GSI_NEW_STMT);
 }
 else
 gsi_insert_before (&gsi, new_stmt, GSI_NEW_STMT);
+if (dump_file && (dump_flags & TDF_DETAILS))
+{
+fprintf (dump_file, "\nConditional store replacement happened!");
+fprintf (dump_file, "\nReplaced the store with a load.");
+fprintf (dump_file, "\nInserted a new PHI statement in joint block:\n");
+print_gimple_stmt (dump_file, new_stmt, 0, TDF_VOPS|TDF_MEMSYMS);
+}
 return true;
 }
 /* Do the main work of conditional store replacement.  */
 cond_if_else_store_replacement_1 (basic_block then_bb, basic_block else_bb,
 				  basic_block join_bb, gimple *then_assign,
 				  gimple *else_assign)
 {
 tree lhs_base, lhs, then_rhs, else_rhs, name;
-source_location then_locus, else_locus;
+location_t then_locus, else_locus;
 gimple_stmt_iterator gsi;
 gphi *newphi;
 gassign *new_stmt;
 if (then_assign == NULL
 if (else_assign)
 	return cond_if_else_store_replacement_1 (then_bb, else_bb, join_bb,
 						 then_assign, else_assign);
 }
-if (MAX_STORES_TO_SINK == 0)
+/* If either vectorization or if-conversion is disabled then do
+not sink any stores.  */
+if (param_max_stores_to_sink == 0
+|| (!flag_tree_loop_vectorize && !flag_tree_slp_vectorize)
+|| !flag_tree_loop_if_convert)
 return false;
 /* Find data references.  */
 then_datarefs.create (1);
 else_datarefs.create (1);
 else_stores.safe_push (else_store);
 }
 /* No pairs of stores found.  */
 if (!then_stores.length ()
-|| then_stores.length () > (unsigned) MAX_STORES_TO_SINK)
+|| then_stores.length () > (unsigned) param_max_stores_to_sink)
 {
 free_data_refs (then_datarefs);
 free_data_refs (else_datarefs);
 return false;
 }
 static void
 hoist_adjacent_loads (basic_block bb0, basic_block bb1,
 		      basic_block bb2, basic_block bb3)
 {
-int param_align = PARAM_VALUE (PARAM_L1_CACHE_LINE_SIZE);
+int param_align = param_l1_cache_line_size;
 unsigned param_align_bits = (unsigned) (param_align * BITS_PER_UNIT);
 gphi_iterator gsi;
 /* Walk the phis in bb3 looking for an opportunity.  We are looking
 for phis of two SSA names, one each of which is defined in bb1 and
 static bool
 gate_hoist_loads (void)
 {
 return (flag_hoist_adjacent_loads == 1
-	  && PARAM_VALUE (PARAM_L1_CACHE_LINE_SIZE)
+	  && param_l1_cache_line_size
 	  && HAVE_conditional_move);
 }
 /* This pass tries to replaces an if-then-else block with an
 assignment.  We have four kinds of transformations.  Some of these

Mercurial > hg > CbC > CbC_gcc

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