This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: [PATCH] Optimize range tests into bittests (PR tree-optimization/63464)


On Fri, 17 Oct 2014, Jakub Jelinek wrote:

> Hi!
> 
> This patch optimizes some range tests into bit tests, like we
> already do for switches in emit_case_bit_tests, but this time
> for a series of ored equality or anded non-equality comparisons.
> If at least 3 comparisons (after the contiguous range, xor and
> diff + xor optimizations are performed) are needed and range of
> values is at most number of bits in a word, we instead check
> whether the operand is >= smallest and <= highest number in the
> range and if it is, test (word) 1 << operand against a bitmask.
> 
> Bootstrapped/regtested on x86_64-linux and i686-linux (for i686-linux
> I had to go back to r216304 because there are multiple ICF related
> bootstrap issues on i686-linux), ok for trunk?

Ok.

Thanks,
Richard.

> 2014-10-16  Jakub Jelinek  <jakub@redhat.com>
> 
> 	PR tree-optimization/63464
> 	* gimple.h (gimple_seq_discard): New prototype.
> 	* gimple.c: Include stringpool.h and tree-ssanames.h.
> 	(gimple_seq_discard): New function.
> 	* optabs.h (lshift_cheap_p): New prototype.
> 	* optabs.c (lshift_cheap_p): New function, moved from...
> 	* tree-switch-conversion.c (lshift_cheap_p): ... here.
> 	* tree-ssa-reassoc.c: Include gimplify.h and optabs.h.
> 	(reassoc_branch_fixups): New variable.
> 	(update_range_test): Add otherrangep and seq arguments.
> 	Unshare exp.  If otherrange is NULL, use for other ranges
> 	array of pointers pointed by otherrangep instead.
> 	Emit seq before gimplified statements for tem.
> 	(optimize_range_tests_diff): Adjust update_range_test
> 	caller.
> 	(optimize_range_tests_xor): Likewise.  Fix up comment.
> 	(extract_bit_test_mask, optimize_range_tests_to_bit_test): New
> 	functions.
> 	(optimize_range_tests): Adjust update_range_test caller.
> 	Call optimize_range_tests_to_bit_test.
> 	(branch_fixup): New function.
> 	(execute_reassoc): Call branch_fixup.
> 
> 	* gcc.dg/torture/pr63464.c: New test.
> 	* gcc.dg/tree-ssa/reassoc-37.c: New test.
> 	* gcc.dg/tree-ssa/reassoc-38.c: New test.
> 
> --- gcc/gimple.h.jj	2014-10-15 12:28:06.428498079 +0200
> +++ gcc/gimple.h	2014-10-15 13:43:18.967491428 +0200
> @@ -1269,9 +1269,10 @@ extern bool gimple_asm_clobbers_memory_p
>  extern void dump_decl_set (FILE *, bitmap);
>  extern bool nonfreeing_call_p (gimple);
>  extern bool infer_nonnull_range (gimple, tree, bool, bool);
> -extern void sort_case_labels (vec<tree> );
> -extern void preprocess_case_label_vec_for_gimple (vec<tree> , tree, tree *);
> -extern void gimple_seq_set_location (gimple_seq , location_t);
> +extern void sort_case_labels (vec<tree>);
> +extern void preprocess_case_label_vec_for_gimple (vec<tree>, tree, tree *);
> +extern void gimple_seq_set_location (gimple_seq, location_t);
> +extern void gimple_seq_discard (gimple_seq);
>  
>  /* Formal (expression) temporary table handling: multiple occurrences of
>     the same scalar expression are evaluated into the same temporary.  */
> --- gcc/gimple.c.jj	2014-10-15 12:28:19.917235900 +0200
> +++ gcc/gimple.c	2014-10-15 13:43:18.970491368 +0200
> @@ -47,6 +47,8 @@ along with GCC; see the file COPYING3.
>  #include "demangle.h"
>  #include "langhooks.h"
>  #include "bitmap.h"
> +#include "stringpool.h"
> +#include "tree-ssanames.h"
>  
>  
>  /* All the tuples have their operand vector (if present) at the very bottom
> @@ -2826,3 +2828,19 @@ gimple_seq_set_location (gimple_seq seq,
>    for (gimple_stmt_iterator i = gsi_start (seq); !gsi_end_p (i); gsi_next (&i))
>      gimple_set_location (gsi_stmt (i), loc);
>  }
> +
> +/* Release SSA_NAMEs in SEQ as well as the GIMPLE statements.  */
> +
> +void
> +gimple_seq_discard (gimple_seq seq)
> +{
> +  gimple_stmt_iterator gsi;
> +
> +  for (gsi = gsi_start (seq); !gsi_end_p (gsi); )
> +    {
> +      gimple stmt = gsi_stmt (gsi);
> +      gsi_remove (&gsi, true);
> +      release_defs (stmt);
> +      ggc_free (stmt);
> +    }
> +}
> --- gcc/optabs.h.jj	2014-10-15 12:28:06.479497088 +0200
> +++ gcc/optabs.h	2014-10-15 13:43:18.970491368 +0200
> @@ -538,5 +538,6 @@ extern void gen_satfractuns_conv_libfunc
>  					  enum machine_mode,
>  					  enum machine_mode);
>  extern void init_tree_optimization_optabs (tree);
> +extern bool lshift_cheap_p (bool);
>  
>  #endif /* GCC_OPTABS_H */
> --- gcc/optabs.c.jj	2014-10-15 12:28:06.433497982 +0200
> +++ gcc/optabs.c	2014-10-15 13:43:18.969491387 +0200
> @@ -8624,4 +8624,31 @@ get_best_mem_extraction_insn (extraction
>  				   struct_bits, field_mode);
>  }
>  
> +/* Determine whether "1 << x" is relatively cheap in word_mode.  */
> +
> +bool
> +lshift_cheap_p (bool speed_p)
> +{
> +  /* FIXME: This should be made target dependent via this "this_target"
> +     mechanism, similar to e.g. can_copy_init_p in gcse.c.  */
> +  static bool init[2] = { false, false };
> +  static bool cheap[2] = { true, true };
> +
> +  /* If the targer has no lshift in word_mode, the operation will most
> +     probably not be cheap.  ??? Does GCC even work for such targets?  */
> +  if (optab_handler (ashl_optab, word_mode) == CODE_FOR_nothing)
> +    return false;
> +
> +  if (!init[speed_p])
> +    {
> +      rtx reg = gen_raw_REG (word_mode, 10000);
> +      int cost = set_src_cost (gen_rtx_ASHIFT (word_mode, const1_rtx, reg),
> +			       speed_p);
> +      cheap[speed_p] = cost < COSTS_N_INSNS (3);
> +      init[speed_p] = true;
> +    }
> +
> +  return cheap[speed_p];
> +}
> +
>  #include "gt-optabs.h"
> --- gcc/tree-switch-conversion.c.jj	2014-10-15 12:28:06.386498896 +0200
> +++ gcc/tree-switch-conversion.c	2014-10-15 13:43:18.963491510 +0200
> @@ -125,35 +125,6 @@ hoist_edge_and_branch_if_true (gimple_st
>  }
>  
>  
> -/* Determine whether "1 << x" is relatively cheap in word_mode.  */
> -/* FIXME: This is the function that we need rtl.h and optabs.h for.
> -   This function (and similar RTL-related cost code in e.g. IVOPTS) should
> -   be moved to some kind of interface file for GIMPLE/RTL interactions.  */
> -static bool
> -lshift_cheap_p (bool speed_p)
> -{
> -  /* FIXME: This should be made target dependent via this "this_target"
> -     mechanism, similar to e.g. can_copy_init_p in gcse.c.  */
> -  static bool init[2] = {false, false};
> -  static bool cheap[2] = {true, true};
> -
> -  /* If the targer has no lshift in word_mode, the operation will most
> -     probably not be cheap.  ??? Does GCC even work for such targets?  */
> -  if (optab_handler (ashl_optab, word_mode) == CODE_FOR_nothing)
> -    return false;
> -
> -  if (!init[speed_p])
> -    {
> -      rtx reg = gen_raw_REG (word_mode, 10000);
> -      int cost = set_src_cost (gen_rtx_ASHIFT (word_mode, const1_rtx, reg),
> -			       speed_p);
> -      cheap[speed_p] = cost < COSTS_N_INSNS (MAX_CASE_BIT_TESTS);
> -      init[speed_p] = true;
> -    }
> -
> -  return cheap[speed_p];
> -}
> -
>  /* Return true if a switch should be expanded as a bit test.
>     RANGE is the difference between highest and lowest case.
>     UNIQ is number of unique case node targets, not counting the default case.
> --- gcc/tree-ssa-reassoc.c.jj	2014-10-15 13:41:45.145301213 +0200
> +++ gcc/tree-ssa-reassoc.c	2014-10-16 16:44:58.776901531 +0200
> @@ -61,6 +61,8 @@ along with GCC; see the file COPYING3.
>  #include "params.h"
>  #include "diagnostic-core.h"
>  #include "builtins.h"
> +#include "gimplify.h"
> +#include "optabs.h"
>  
>  /*  This is a simple global reassociation pass.  It is, in part, based
>      on the LLVM pass of the same name (They do some things more/less
> @@ -218,6 +220,12 @@ static long *bb_rank;
>  /* Operand->rank hashtable.  */
>  static hash_map<tree, long> *operand_rank;
>  
> +/* Vector of SSA_NAMEs on which after reassociate_bb is done with
> +   all basic blocks the CFG should be adjusted - basic blocks
> +   split right after that SSA_NAME's definition statement and before
> +   the only use, which must be a bit ior.  */
> +static vec<tree> reassoc_branch_fixups;
> +
>  /* Forward decls.  */
>  static long get_rank (tree);
>  static bool reassoc_stmt_dominates_stmt_p (gimple, gimple);
> @@ -2071,7 +2079,9 @@ range_entry_cmp (const void *a, const vo
>  /* Helper routine of optimize_range_test.
>     [EXP, IN_P, LOW, HIGH, STRICT_OVERFLOW_P] is a merged range for
>     RANGE and OTHERRANGE through OTHERRANGE + COUNT - 1 ranges,
> -   OPCODE and OPS are arguments of optimize_range_tests.  Return
> +   OPCODE and OPS are arguments of optimize_range_tests.  If OTHERRANGE
> +   is NULL, OTHERRANGEP should not be and then OTHERRANGEP points to
> +   an array of COUNT pointers to other ranges.  Return
>     true if the range merge has been successful.
>     If OPCODE is ERROR_MARK, this is called from within
>     maybe_optimize_range_tests and is performing inter-bb range optimization.
> @@ -2080,9 +2090,10 @@ range_entry_cmp (const void *a, const vo
>  
>  static bool
>  update_range_test (struct range_entry *range, struct range_entry *otherrange,
> +		   struct range_entry **otherrangep,
>  		   unsigned int count, enum tree_code opcode,
> -		   vec<operand_entry_t> *ops, tree exp, bool in_p,
> -		   tree low, tree high, bool strict_overflow_p)
> +		   vec<operand_entry_t> *ops, tree exp, gimple_seq seq,
> +		   bool in_p, tree low, tree high, bool strict_overflow_p)
>  {
>    operand_entry_t oe = (*ops)[range->idx];
>    tree op = oe->op;
> @@ -2090,9 +2101,11 @@ update_range_test (struct range_entry *r
>      last_stmt (BASIC_BLOCK_FOR_FN (cfun, oe->id));
>    location_t loc = gimple_location (stmt);
>    tree optype = op ? TREE_TYPE (op) : boolean_type_node;
> -  tree tem = build_range_check (loc, optype, exp, in_p, low, high);
> +  tree tem = build_range_check (loc, optype, unshare_expr (exp),
> +				in_p, low, high);
>    enum warn_strict_overflow_code wc = WARN_STRICT_OVERFLOW_COMPARISON;
>    gimple_stmt_iterator gsi;
> +  unsigned int i;
>  
>    if (tem == NULL_TREE)
>      return false;
> @@ -2112,8 +2125,12 @@ update_range_test (struct range_entry *r
>        fprintf (dump_file, ", ");
>        print_generic_expr (dump_file, range->high, 0);
>        fprintf (dump_file, "]");
> -      for (r = otherrange; r < otherrange + count; r++)
> +      for (i = 0; i < count; i++)
>  	{
> +	  if (otherrange)
> +	    r = otherrange + i;
> +	  else
> +	    r = otherrangep[i];
>  	  fprintf (dump_file, " and %c[", r->in_p ? '+' : '-');
>  	  print_generic_expr (dump_file, r->low, 0);
>  	  fprintf (dump_file, ", ");
> @@ -2135,10 +2152,14 @@ update_range_test (struct range_entry *r
>       In that case we have to insert after the stmt rather then before
>       it.  */
>    if (op == range->exp)
> -    tem = force_gimple_operand_gsi (&gsi, tem, true, NULL_TREE, false,
> -				    GSI_CONTINUE_LINKING);
> +    {
> +      gsi_insert_seq_after (&gsi, seq, GSI_CONTINUE_LINKING);
> +      tem = force_gimple_operand_gsi (&gsi, tem, true, NULL_TREE, false,
> +				      GSI_CONTINUE_LINKING);
> +    }
>    else
>      {
> +      gsi_insert_seq_before (&gsi, seq, GSI_SAME_STMT);
>        tem = force_gimple_operand_gsi (&gsi, tem, true, NULL_TREE, true,
>  				      GSI_SAME_STMT);
>        gsi_prev (&gsi);
> @@ -2156,8 +2177,12 @@ update_range_test (struct range_entry *r
>    range->in_p = in_p;
>    range->strict_overflow_p = false;
>  
> -  for (range = otherrange; range < otherrange + count; range++)
> +  for (i = 0; i < count; i++)
>      {
> +      if (otherrange)
> +	range = otherrange + i;
> +      else
> +	range = otherrangep[i];
>        oe = (*ops)[range->idx];
>        /* Now change all the other range test immediate uses, so that
>  	 those tests will be optimized away.  */
> @@ -2195,8 +2220,8 @@ optimize_range_tests_xor (enum tree_code
>  			  struct range_entry *rangej)
>  {
>    tree lowxor, highxor, tem, exp;
> -  /* Check highi ^ lowi == highj ^ lowj and
> -     popcount (highi ^ lowi) == 1.  */
> +  /* Check lowi ^ lowj == highi ^ highj and
> +     popcount (lowi ^ lowj) == 1.  */
>    lowxor = fold_binary (BIT_XOR_EXPR, type, lowi, lowj);
>    if (lowxor == NULL_TREE || TREE_CODE (lowxor) != INTEGER_CST)
>      return false;
> @@ -2210,8 +2235,8 @@ optimize_range_tests_xor (enum tree_code
>    exp = fold_build2 (BIT_AND_EXPR, type, rangei->exp, tem);
>    lowj = fold_build2 (BIT_AND_EXPR, type, lowi, tem);
>    highj = fold_build2 (BIT_AND_EXPR, type, highi, tem);
> -  if (update_range_test (rangei, rangej, 1, opcode, ops, exp,
> -			 rangei->in_p, lowj, highj,
> +  if (update_range_test (rangei, rangej, NULL, 1, opcode, ops, exp,
> +			 NULL, rangei->in_p, lowj, highj,
>  			 rangei->strict_overflow_p
>  			 || rangej->strict_overflow_p))
>      return true;
> @@ -2259,8 +2284,8 @@ optimize_range_tests_diff (enum tree_cod
>  		      fold_convert (type, rangei->exp), lowi);
>    tem1 = fold_build2 (BIT_AND_EXPR, type, tem1, mask);
>    lowj = build_int_cst (type, 0);
> -  if (update_range_test (rangei, rangej, 1, opcode, ops, tem1,
> -			 rangei->in_p, lowj, tem2,
> +  if (update_range_test (rangei, rangej, NULL, 1, opcode, ops, tem1,
> +			 NULL, rangei->in_p, lowj, tem2,
>  			 rangei->strict_overflow_p
>  			 || rangej->strict_overflow_p))
>      return true;
> @@ -2328,6 +2353,255 @@ optimize_range_tests_1 (enum tree_code o
>    return any_changes;
>  }
>  
> +/* Helper function of optimize_range_tests_to_bit_test.  Handle a single
> +   range, EXP, LOW, HIGH, compute bit mask of bits to test and return
> +   EXP on success, NULL otherwise.  */
> +
> +static tree
> +extract_bit_test_mask (tree exp, int prec, tree totallow, tree low, tree high,
> +		       wide_int *mask, tree *totallowp)
> +{
> +  tree tem = int_const_binop (MINUS_EXPR, high, low);
> +  if (tem == NULL_TREE
> +      || TREE_CODE (tem) != INTEGER_CST
> +      || TREE_OVERFLOW (tem)
> +      || tree_int_cst_sgn (tem) == -1
> +      || compare_tree_int (tem, prec) != -1)
> +    return NULL_TREE;
> +
> +  unsigned HOST_WIDE_INT max = tree_to_uhwi (tem) + 1;
> +  *mask = wi::shifted_mask (0, max, false, prec);
> +  if (TREE_CODE (exp) == BIT_AND_EXPR
> +      && TREE_CODE (TREE_OPERAND (exp, 1)) == INTEGER_CST)
> +    {
> +      widest_int msk = wi::to_widest (TREE_OPERAND (exp, 1));
> +      msk = wi::zext (~msk, TYPE_PRECISION (TREE_TYPE (exp)));
> +      if (wi::popcount (msk) == 1
> +	  && wi::ltu_p (msk, prec - max))
> +	{
> +	  *mask |= wi::shifted_mask (msk.to_uhwi (), max, false, prec);
> +	  max += msk.to_uhwi ();
> +	  exp = TREE_OPERAND (exp, 0);
> +	  if (integer_zerop (low)
> +	      && TREE_CODE (exp) == PLUS_EXPR
> +	      && TREE_CODE (TREE_OPERAND (exp, 1)) == INTEGER_CST)
> +	    {
> +	      widest_int bias
> +	        = wi::neg (wi::sext (wi::to_widest (TREE_OPERAND (exp, 1)),
> +				     TYPE_PRECISION (TREE_TYPE (low))));
> +	      tree tbias = wide_int_to_tree (TREE_TYPE (low), bias);
> +	      if (totallowp)
> +		{
> +		  *totallowp = tbias;
> +		  exp = TREE_OPERAND (exp, 0);
> +		  STRIP_NOPS (exp);
> +		  return exp;
> +		}
> +	      else if (!tree_int_cst_lt (totallow, tbias))
> +		return NULL_TREE;
> +	      bias -= wi::to_widest (totallow);
> +	      if (wi::ges_p (bias, 0) && wi::lts_p (bias, prec - max))
> +		{
> +		  *mask = wi::lshift (*mask, bias);
> +		  exp = TREE_OPERAND (exp, 0);
> +		  STRIP_NOPS (exp);
> +		  return exp;
> +		}
> +	    }
> +	}
> +    }
> +  if (totallowp)
> +    return exp;
> +  if (!tree_int_cst_lt (totallow, low))
> +    return exp;
> +  tem = int_const_binop (MINUS_EXPR, low, totallow);
> +  if (tem == NULL_TREE
> +      || TREE_CODE (tem) != INTEGER_CST
> +      || TREE_OVERFLOW (tem)
> +      || compare_tree_int (tem, prec - max) == 1)
> +    return NULL_TREE;
> +
> +  *mask = wi::lshift (*mask, wi::to_widest (tem));
> +  return exp;
> +}
> +
> +/* Attempt to optimize small range tests using bit test.
> +   E.g.
> +   X != 43 && X != 76 && X != 44 && X != 78 && X != 49
> +   && X != 77 && X != 46 && X != 75 && X != 45 && X != 82
> +   has been by earlier optimizations optimized into:
> +   ((X - 43U) & ~32U) > 3U && X != 49 && X != 82
> +   As all the 43 through 82 range is less than 64 numbers,
> +   for 64-bit word targets optimize that into:
> +   (X - 43U) > 40U && ((1 << (X - 43U)) & 0x8F0000004FULL) == 0  */
> +
> +static bool
> +optimize_range_tests_to_bit_test (enum tree_code opcode, int first, int length,
> +				  vec<operand_entry_t> *ops,
> +				  struct range_entry *ranges)
> +{
> +  int i, j;
> +  bool any_changes = false;
> +  int prec = GET_MODE_BITSIZE (word_mode);
> +  auto_vec<struct range_entry *, 64> candidates;
> +
> +  for (i = first; i < length - 2; i++)
> +    {
> +      tree lowi, highi, lowj, highj, type;
> +
> +      if (ranges[i].exp == NULL_TREE || ranges[i].in_p)
> +	continue;
> +      type = TREE_TYPE (ranges[i].exp);
> +      if (!INTEGRAL_TYPE_P (type))
> +	continue;
> +      lowi = ranges[i].low;
> +      if (lowi == NULL_TREE)
> +	lowi = TYPE_MIN_VALUE (type);
> +      highi = ranges[i].high;
> +      if (highi == NULL_TREE)
> +	continue;
> +      wide_int mask;
> +      tree exp = extract_bit_test_mask (ranges[i].exp, prec, lowi, lowi,
> +					highi, &mask, &lowi);
> +      if (exp == NULL_TREE)
> +	continue;
> +      bool strict_overflow_p = ranges[i].strict_overflow_p;
> +      candidates.truncate (0);
> +      int end = MIN (i + 64, length);
> +      for (j = i + 1; j < end; j++)
> +	{
> +	  tree exp2;
> +	  if (ranges[j].exp == NULL_TREE || ranges[j].in_p)
> +	    continue;
> +	  if (ranges[j].exp == exp)
> +	    ;
> +	  else if (TREE_CODE (ranges[j].exp) == BIT_AND_EXPR)
> +	    {
> +	      exp2 = TREE_OPERAND (ranges[j].exp, 0);
> +	      if (exp2 == exp)
> +		;
> +	      else if (TREE_CODE (exp2) == PLUS_EXPR)
> +		{
> +		  exp2 = TREE_OPERAND (exp2, 0);
> +		  STRIP_NOPS (exp2);
> +		  if (exp2 != exp)
> +		    continue;
> +		}
> +	      else
> +		continue;
> +	    }
> +	  else
> +	    continue;
> +	  lowj = ranges[j].low;
> +	  if (lowj == NULL_TREE)
> +	    continue;
> +	  highj = ranges[j].high;
> +	  if (highj == NULL_TREE)
> +	    highj = TYPE_MAX_VALUE (type);
> +	  wide_int mask2;
> +	  exp2 = extract_bit_test_mask (ranges[j].exp, prec, lowi, lowj,
> +					highj, &mask2, NULL);
> +	  if (exp2 != exp)
> +	    continue;
> +	  mask |= mask2;
> +	  strict_overflow_p |= ranges[j].strict_overflow_p;
> +	  candidates.safe_push (&ranges[j]);
> +	}
> +
> +      /* If we need otherwise 3 or more comparisons, use a bit test.  */
> +      if (candidates.length () >= 2)
> +	{
> +	  tree high = wide_int_to_tree (TREE_TYPE (lowi),
> +					wi::to_widest (lowi)
> +					+ prec - wi::clz (mask));
> +	  operand_entry_t oe = (*ops)[ranges[i].idx];
> +	  tree op = oe->op;
> +	  gimple stmt = op ? SSA_NAME_DEF_STMT (op)
> +			   : last_stmt (BASIC_BLOCK_FOR_FN (cfun, oe->id));
> +	  location_t loc = gimple_location (stmt);
> +	  tree optype = op ? TREE_TYPE (op) : boolean_type_node;
> +
> +	  /* See if it isn't cheaper to pretend the minimum value of the
> +	     range is 0, if maximum value is small enough.
> +	     We can avoid then subtraction of the minimum value, but the
> +	     mask constant could be perhaps more expensive.  */
> +	  if (compare_tree_int (lowi, 0) > 0
> +	      && compare_tree_int (high, prec) < 0)
> +	    {
> +	      int cost_diff;
> +	      HOST_WIDE_INT m = tree_to_uhwi (lowi);
> +	      rtx reg = gen_raw_REG (word_mode, 10000);
> +	      bool speed_p = optimize_bb_for_speed_p (gimple_bb (stmt));
> +	      cost_diff = set_rtx_cost (gen_rtx_PLUS (word_mode, reg,
> +						      GEN_INT (-m)), speed_p);
> +	      rtx r = immed_wide_int_const (mask, word_mode);
> +	      cost_diff += set_src_cost (gen_rtx_AND (word_mode, reg, r),
> +					 speed_p);
> +	      r = immed_wide_int_const (wi::lshift (mask, m), word_mode);
> +	      cost_diff -= set_src_cost (gen_rtx_AND (word_mode, reg, r),
> +					 speed_p);
> +	      if (cost_diff > 0)
> +		{
> +		  mask = wi::lshift (mask, m);
> +		  lowi = build_zero_cst (TREE_TYPE (lowi));
> +		}
> +	    }
> +
> +	  tree tem = build_range_check (loc, optype, unshare_expr (exp),
> +					false, lowi, high);
> +	  if (tem == NULL_TREE || is_gimple_val (tem))
> +	    continue;
> +	  tree etype = unsigned_type_for (TREE_TYPE (exp));
> +	  exp = fold_build2_loc (loc, MINUS_EXPR, etype,
> +				 fold_convert_loc (loc, etype, exp),
> +				 fold_convert_loc (loc, etype, lowi));
> +	  exp = fold_convert_loc (loc, integer_type_node, exp);
> +	  tree word_type = lang_hooks.types.type_for_mode (word_mode, 1);
> +	  exp = fold_build2_loc (loc, LSHIFT_EXPR, word_type,
> +				 build_int_cst (word_type, 1), exp);
> +	  exp = fold_build2_loc (loc, BIT_AND_EXPR, word_type, exp,
> +				 wide_int_to_tree (word_type, mask));
> +	  exp = fold_build2_loc (loc, EQ_EXPR, optype, exp,
> +				 build_zero_cst (word_type));
> +	  if (is_gimple_val (exp))
> +	    continue;
> +
> +	  /* The shift might have undefined behavior if TEM is true,
> +	     but reassociate_bb isn't prepared to have basic blocks
> +	     split when it is running.  So, temporarily emit a code
> +	     with BIT_IOR_EXPR instead of &&, and fix it up in
> +	     branch_fixup.  */
> +	  gimple_seq seq;
> +	  tem = force_gimple_operand (tem, &seq, true, NULL_TREE);
> +	  gcc_assert (TREE_CODE (tem) == SSA_NAME);
> +	  gimple_set_visited (SSA_NAME_DEF_STMT (tem), true);
> +	  gimple_seq seq2;
> +	  exp = force_gimple_operand (exp, &seq2, true, NULL_TREE);
> +	  gimple_seq_add_seq_without_update (&seq, seq2);
> +	  gcc_assert (TREE_CODE (exp) == SSA_NAME);
> +	  gimple_set_visited (SSA_NAME_DEF_STMT (exp), true);
> +	  gimple g
> +	    = gimple_build_assign_with_ops (BIT_IOR_EXPR,
> +					    make_ssa_name (optype, NULL),
> +					    tem, exp);
> +	  gimple_set_location (g, loc);
> +	  gimple_seq_add_stmt_without_update (&seq, g);
> +	  exp = gimple_assign_lhs (g);
> +	  tree val = build_zero_cst (optype);
> +	  if (update_range_test (&ranges[i], NULL, candidates.address (),
> +				 candidates.length (), opcode, ops, exp,
> +				 seq, false, val, val, strict_overflow_p))
> +	    {
> +	      any_changes = true;
> +	      reassoc_branch_fixups.safe_push (tem);
> +	    }
> +	  else
> +	    gimple_seq_discard (seq);
> +	}
> +    }
> +  return any_changes;
> +}
> +
>  /* Optimize range tests, similarly how fold_range_test optimizes
>     it on trees.  The tree code for the binary
>     operation between all the operands is OPCODE.
> @@ -2391,9 +2665,9 @@ optimize_range_tests (enum tree_code opc
>        if (j == i + 1)
>  	continue;
>  
> -      if (update_range_test (ranges + i, ranges + i + 1, j - i - 1, opcode,
> -			     ops, ranges[i].exp, in_p, low, high,
> -			     strict_overflow_p))
> +      if (update_range_test (ranges + i, ranges + i + 1, NULL, j - i - 1,
> +			     opcode, ops, ranges[i].exp, NULL, in_p,
> +			     low, high, strict_overflow_p))
>  	{
>  	  i = j - 1;
>  	  any_changes = true;
> @@ -2412,6 +2686,9 @@ optimize_range_tests (enum tree_code opc
>    if (BRANCH_COST (optimize_function_for_speed_p (cfun), false) >= 2)
>      any_changes |= optimize_range_tests_1 (opcode, first, length, false,
>  					   ops, ranges);
> +  if (lshift_cheap_p (optimize_function_for_speed_p (cfun)))
> +    any_changes |= optimize_range_tests_to_bit_test (opcode, first, length,
> +						     ops, ranges);
>  
>    if (any_changes && opcode != ERROR_MARK)
>      {
> @@ -4581,6 +4858,82 @@ reassociate_bb (basic_block bb)
>      reassociate_bb (son);
>  }
>  
> +/* Add jumps around shifts for range tests turned into bit tests.
> +   For each SSA_NAME VAR we have code like:
> +   VAR = ...; // final stmt of range comparison
> +   // bit test here...;
> +   OTHERVAR = ...; // final stmt of the bit test sequence
> +   RES = VAR | OTHERVAR;
> +   Turn the above into:
> +   VAR = ...;
> +   if (VAR != 0)
> +     goto <l3>;
> +   else
> +     goto <l2>;
> +   <l2>:
> +   // bit test here...;
> +   OTHERVAR = ...;
> +   <l3>:
> +   # RES = PHI<1(l1), OTHERVAR(l2)>;  */
> +
> +static void
> +branch_fixup (void)
> +{
> +  tree var;
> +  unsigned int i;
> +
> +  FOR_EACH_VEC_ELT (reassoc_branch_fixups, i, var)
> +    {
> +      gimple def_stmt = SSA_NAME_DEF_STMT (var);
> +      gimple use_stmt;
> +      use_operand_p use;
> +      bool ok = single_imm_use (var, &use, &use_stmt);
> +      gcc_assert (ok
> +		  && is_gimple_assign (use_stmt)
> +		  && gimple_assign_rhs_code (use_stmt) == BIT_IOR_EXPR
> +		  && gimple_bb (def_stmt) == gimple_bb (use_stmt));
> +
> +      basic_block cond_bb = gimple_bb (def_stmt);
> +      basic_block then_bb = split_block (cond_bb, def_stmt)->dest;
> +      basic_block merge_bb = split_block (then_bb, use_stmt)->dest;
> +
> +      gimple_stmt_iterator gsi = gsi_for_stmt (def_stmt);
> +      gimple g = gimple_build_cond (NE_EXPR, var,
> +				    build_zero_cst (TREE_TYPE (var)),
> +				    NULL_TREE, NULL_TREE);
> +      location_t loc = gimple_location (use_stmt);
> +      gimple_set_location (g, loc);
> +      gsi_insert_after (&gsi, g, GSI_NEW_STMT);
> +
> +      edge etrue = make_edge (cond_bb, merge_bb, EDGE_TRUE_VALUE);
> +      etrue->probability = REG_BR_PROB_BASE / 2;
> +      etrue->count = cond_bb->count / 2;
> +      edge efalse = find_edge (cond_bb, then_bb);
> +      efalse->flags = EDGE_FALSE_VALUE;
> +      efalse->probability -= etrue->probability;
> +      efalse->count -= etrue->count;
> +      then_bb->count -= etrue->count;
> +
> +      tree othervar = NULL_TREE;
> +      if (gimple_assign_rhs1 (use_stmt) == var)
> +	othervar = gimple_assign_rhs2 (use_stmt);
> +      else if (gimple_assign_rhs2 (use_stmt) == var)
> +	othervar = gimple_assign_rhs1 (use_stmt);
> +      else
> +	gcc_unreachable ();
> +      tree lhs = gimple_assign_lhs (use_stmt);
> +      gimple phi = create_phi_node (lhs, merge_bb);
> +      add_phi_arg (phi, build_one_cst (TREE_TYPE (lhs)), etrue, loc);
> +      add_phi_arg (phi, othervar, single_succ_edge (then_bb), loc);
> +      gsi = gsi_for_stmt (use_stmt);
> +      gsi_remove (&gsi, true);
> +
> +      set_immediate_dominator (CDI_DOMINATORS, merge_bb, cond_bb);
> +      set_immediate_dominator (CDI_POST_DOMINATORS, cond_bb, merge_bb);
> +    }
> +  reassoc_branch_fixups.release ();
> +}
> +
>  void dump_ops_vector (FILE *file, vec<operand_entry_t> ops);
>  void debug_ops_vector (vec<operand_entry_t> ops);
>  
> @@ -4695,6 +5048,7 @@ execute_reassoc (void)
>  
>    do_reassoc ();
>    repropagate_negates ();
> +  branch_fixup ();
>  
>    fini_reassoc ();
>    return 0;
> --- gcc/testsuite/gcc.dg/torture/pr63464.c.jj	2014-10-15 15:15:27.018725273 +0200
> +++ gcc/testsuite/gcc.dg/torture/pr63464.c	2014-10-15 15:14:58.000000000 +0200
> @@ -0,0 +1,92 @@
> +/* PR tree-optimization/63464 */
> +/* { dg-do run { target int32plus } } */
> +
> +int cnt;
> +
> +__attribute__((noinline, noclone)) void
> +bar (int x, int y)
> +{
> +  cnt++;
> +  switch (y)
> +    {
> +    case 1:
> +      if ((unsigned) x < 24U && ((1U << x) & 0x860c0cU) != 0)
> +        __builtin_abort ();
> +      break;
> +    case 2:
> +      if ((unsigned) x >= 24U || ((1U << x) & 0x860c0cU) == 0)
> +        __builtin_abort ();
> +      break;
> +    case 3:
> +      if ((unsigned) x - 43U < 40U && ((1ULL << (x - 43U)) & 0x8f0000004fULL) != 0)
> +        __builtin_abort ();
> +      break;
> +    case 4:
> +      if ((unsigned) x - 43U >= 40U || ((1ULL << (x - 43U)) & 0x8f0000004fULL) == 0)
> +        __builtin_abort ();
> +      break;
> +    default:
> +      __builtin_abort ();
> +    }
> +}
> +
> +__attribute__((noinline, noclone)) void
> +f1 (int x)
> +{
> +  if (x != 2 && x != 3 && x != 10 && x != 11 && x != 17 && x != 18 && x != 23)
> +    bar (x, 1);
> +}
> +
> +__attribute__((noinline, noclone)) void
> +f2 (int x)
> +{
> +  if (x == 2 || x == 3 || x == 10 || x == 11 || x == 17 || x == 18 || x == 23)
> +    bar (x, 2);
> +}
> +
> +__attribute__((noinline, noclone)) void
> +f3 (int x)
> +{
> +  if (x != 43 && x != 76 && x != 44 && x != 78 && x != 49
> +      && x != 77 && x != 46 && x != 75 && x != 45 && x != 82)
> +    bar (x, 3);
> +}
> +
> +__attribute__((noinline, noclone)) void
> +f4 (int x)
> +{
> +  if (x == 43 || x == 76 || x == 44 || x == 78 || x == 49
> +      || x == 77 || x == 46 || x == 75 || x == 45 || x == 82)
> +    bar (x, 4);
> +}
> +
> +int
> +main ()
> +{
> +  int i;
> +  f1 (-__INT_MAX__ - 1);
> +  for (i = -3; i < 92; i++)
> +    f1 (i);
> +  f1 (__INT_MAX__);
> +  if (cnt != 97 - 7)
> +    __builtin_abort ();
> +  f2 (-__INT_MAX__ - 1);
> +  for (i = -3; i < 92; i++)
> +    f2 (i);
> +  f2 (__INT_MAX__);
> +  if (cnt != 97)
> +    __builtin_abort ();
> +  f3 (-__INT_MAX__ - 1);
> +  for (i = -3; i < 92; i++)
> +    f3 (i);
> +  f3 (__INT_MAX__);
> +  if (cnt != 97 * 2 - 10)
> +    __builtin_abort ();
> +  f4 (-__INT_MAX__ - 1);
> +  for (i = -3; i < 92; i++)
> +    f4 (i);
> +  f4 (__INT_MAX__);
> +  if (cnt != 97 * 2)
> +    __builtin_abort ();
> +  return 0;
> +}
> --- gcc/testsuite/gcc.dg/tree-ssa/reassoc-37.c.jj	2014-10-15 15:22:07.458048561 +0200
> +++ gcc/testsuite/gcc.dg/tree-ssa/reassoc-37.c	2014-10-15 15:29:16.849807253 +0200
> @@ -0,0 +1,17 @@
> +/* PR tree-optimization/63464 */
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-optimized" } */
> +
> +void bar (void);
> +
> +void
> +foo (int x)
> +{
> +  if (x != 2 && x != 3 && x != 10 && x != 11 && x != 17 && x != 18 && x != 23)
> +    bar ();
> +}
> +
> +/* Check if the tests have been folded into a bit test.  */
> +/* { dg-final { scan-tree-dump "(8784908|0x0*860c0c)" "optimized" { target i?86-*-* x86_64-*-* } } } */
> +/* { dg-final { scan-tree-dump "(<<|>>)" "optimized" { target i?86-*-* x86_64-*-* } } } */
> +/* { dg-final { cleanup-tree-dump "optimized" } } */
> --- gcc/testsuite/gcc.dg/tree-ssa/reassoc-38.c.jj	2014-10-15 15:28:04.133216268 +0200
> +++ gcc/testsuite/gcc.dg/tree-ssa/reassoc-38.c	2014-10-15 16:01:47.100534040 +0200
> @@ -0,0 +1,18 @@
> +/* PR tree-optimization/63464 */
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-optimized" } */
> +
> +void bar (void);
> +
> +void
> +foo (int x)
> +{
> +  if (x == 43 || x == 76 || x == 44 || x == 78 || x == 49
> +      || x == 77 || x == 46 || x == 75 || x == 45 || x == 82)
> +    bar ();
> +}
> +
> +/* Check if the tests have been folded into a bit test.  */
> +/* { dg-final { scan-tree-dump "(614180323407|0x0*8f0000004f)" "optimized" { target { { i?86-*-* x86_64-*-* } && { ! { ia32 } } } } } } */
> +/* { dg-final { scan-tree-dump "(<<|>>)" "optimized" { target { { i?86-*-* x86_64-*-* } && { ! { ia32 } } } } } } */
> +/* { dg-final { cleanup-tree-dump "optimized" } } */
> 
> 	Jakub
> 
> 

-- 
Richard Biener <rguenther@suse.de>
SUSE / SUSE Labs
SUSE LINUX Products GmbH - Nuernberg - AG Nuernberg - HRB 16746
GF: Jeff Hawn, Jennifer Guild, Felix Imend"orffer


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]