[PATCH] ifcvt: Account for parallelism when costing noce sequences

From: juewang <[email protected]>

seq_cost treats every instruction in a replacement sequence as serial.
This can overestimate simple register-only sequences on superscalar
targets and reject profitable if-conversion.

Build dependency levels for simple, single-cycle register operations.
Cost each level using the target reassociation widths for integer,
floating-point and vector operations, with the issue rate as a global
limit.  Fall back to the serial cost for unsupported sequences and size
optimization.

gcc/ChangeLog:

	* ifcvt.cc (noce_parallel_cost_node): New.
	(noce_parallel_cost_class): New.
	(noce_parallel_cost_level): New.
	(noce_reassociation_code): New.
	(noce_parallel_operand_class_p): New.
	(noce_parallel_cost_info): New.
	(noce_parallel_seq_cost): New.
	(default_noce_conversion_profitable_p): Use it.
---
 gcc/ifcvt.cc | 251 ++++++++++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 250 insertions(+), 1 deletion(-)

diff --git a/gcc/ifcvt.cc b/gcc/ifcvt.cc
index 5ea25f8fbe7..33120a30e7d 100644
--- a/gcc/ifcvt.cc
+++ b/gcc/ifcvt.cc
@@ -803,6 +803,255 @@ noce_reversed_cond_code (struct noce_if_info *if_info)
   return reversed_comparison_code (if_info->cond, if_info->jump);
 }
 
+/* A destination and its dependency level in a noce sequence.  */
+
+struct noce_parallel_cost_node
+{
+  rtx dest;
+  unsigned int level;
+};
+
+enum noce_parallel_cost_class
+{
+  NOCE_PARALLEL_INT,
+  NOCE_PARALLEL_FP,
+  NOCE_PARALLEL_VECTOR,
+  NOCE_PARALLEL_NUM_CLASSES
+};
+
+/* Instruction counts and widths for one dependency level.  */
+
+struct noce_parallel_cost_level
+{
+  unsigned int insns[NOCE_PARALLEL_NUM_CLASSES];
+  unsigned int widths[NOCE_PARALLEL_NUM_CLASSES];
+};
+
+/* Return a tree code corresponding to the operation in SRC.  */
+
+static enum tree_code
+noce_reassociation_code (rtx src)
+{
+  switch (GET_CODE (src))
+    {
+    case PLUS:
+      return PLUS_EXPR;
+    case MINUS:
+      return MINUS_EXPR;
+    case MULT:
+      return MULT_EXPR;
+    case AND:
+      return BIT_AND_EXPR;
+    case IOR:
+      return BIT_IOR_EXPR;
+    case XOR:
+      return BIT_XOR_EXPR;
+    case ASHIFT:
+      return LSHIFT_EXPR;
+    case ASHIFTRT:
+    case LSHIFTRT:
+      return RSHIFT_EXPR;
+    case NEG:
+      return NEGATE_EXPR;
+    case IF_THEN_ELSE:
+      return COND_EXPR;
+    case EQ:
+      return EQ_EXPR;
+    case NE:
+      return NE_EXPR;
+    case LT:
+    case LTU:
+      return LT_EXPR;
+    case LE:
+    case LEU:
+      return LE_EXPR;
+    case GT:
+    case GTU:
+      return GT_EXPR;
+    case GE:
+    case GEU:
+      return GE_EXPR;
+    case SMIN:
+    case UMIN:
+      return MIN_EXPR;
+    case SMAX:
+    case UMAX:
+      return MAX_EXPR;
+    default:
+      return NOP_EXPR;
+    }
+}
+
+/* Return true if the modes in X belong to COST_CLASS.  */
+
+static bool
+noce_parallel_operand_class_p (rtx x,
+			       noce_parallel_cost_class cost_class)
+{
+  subrtx_iterator::array_type array;
+  FOR_EACH_SUBRTX (iter, array, x, ALL)
+    {
+      machine_mode mode = GET_MODE (*iter);
+      if (mode == VOIDmode || GET_MODE_CLASS (mode) == MODE_CC)
+	continue;
+
+      noce_parallel_cost_class operand_class;
+      if (VECTOR_MODE_P (mode))
+	operand_class = NOCE_PARALLEL_VECTOR;
+      else if (FLOAT_MODE_P (mode))
+	operand_class = NOCE_PARALLEL_FP;
+      else if (SCALAR_INT_MODE_P (mode))
+	operand_class = NOCE_PARALLEL_INT;
+      else
+	return false;
+
+      if (operand_class != cost_class)
+	return false;
+    }
+
+  return true;
+}
+
+/* Classify SET for the parallel cost estimate.  */
+
+static bool
+noce_parallel_cost_info (rtx set, noce_parallel_cost_class *cost_class,
+			 machine_mode *mode, enum tree_code *opcode)
+{
+  rtx dest = SET_DEST (set);
+  rtx src = SET_SRC (set);
+  machine_mode operation_mode = GET_MODE (dest);
+  bool comparison_p = COMPARISON_P (src) || GET_CODE (src) == COMPARE;
+
+  /* Classify comparisons by their input mode.  Store-flag operations use
+     the result mode.  */
+  if (comparison_p)
+    {
+      machine_mode input_mode = GET_MODE (XEXP (src, 0));
+      if (input_mode != VOIDmode
+	  && GET_MODE_CLASS (input_mode) != MODE_CC)
+	operation_mode = input_mode;
+    }
+
+  if (VECTOR_MODE_P (operation_mode))
+    *cost_class = NOCE_PARALLEL_VECTOR;
+  else if (FLOAT_MODE_P (operation_mode))
+    *cost_class = NOCE_PARALLEL_FP;
+  else if (SCALAR_INT_MODE_P (operation_mode))
+    *cost_class = NOCE_PARALLEL_INT;
+  else
+    return false;
+
+  /* Check only the selected values of a conditional select.  Reject other
+     operations that cross execution classes.  */
+  if (!comparison_p && GET_CODE (src) == IF_THEN_ELSE)
+    {
+      if (!noce_parallel_operand_class_p (XEXP (src, 1), *cost_class)
+	  || !noce_parallel_operand_class_p (XEXP (src, 2), *cost_class))
+	return false;
+    }
+  else if (!comparison_p
+	   && !noce_parallel_operand_class_p (src, *cost_class))
+    return false;
+
+  *mode = operation_mode;
+  *opcode = noce_reassociation_code (src);
+  return true;
+}
+
+/* Estimate the cost of independent, single-cycle register operations in
+   SEQ using target reassociation widths.  */
+
+static unsigned int
+noce_parallel_seq_cost (rtx_insn *seq, bool speed_p)
+{
+  unsigned int serial_cost = seq_cost (seq, speed_p);
+
+  if (!speed_p)
+    return serial_cost;
+
+  auto_vec<noce_parallel_cost_node> nodes;
+  auto_vec<noce_parallel_cost_level> levels;
+
+  /* Build register dependency levels.  Place an instruction after its
+     deepest producer; independent instructions remain at the same level.  */
+
+  for (rtx_insn *insn = seq; insn; insn = NEXT_INSN (insn))
+    {
+      if (!NONDEBUG_INSN_P (insn))
+	continue;
+
+      rtx set = single_set (insn);
+      if (!set)
+	return serial_cost;
+
+      rtx dest = SET_DEST (set);
+      rtx src = SET_SRC (set);
+
+      if (!REG_P (dest)
+	  || contains_mem_rtx_p (src)
+	  || side_effects_p (src)
+	  || may_trap_p (src)
+	  || set_rtx_cost (set, speed_p) != COSTS_N_INSNS (1))
+	return serial_cost;
+
+      unsigned int level = 0;
+      for (unsigned int i = 0; i < nodes.length (); ++i)
+	if (reg_overlap_mentioned_p (nodes[i].dest, src))
+	  level = MAX (level, nodes[i].level + 1);
+
+      noce_parallel_cost_class cost_class;
+      machine_mode mode;
+      enum tree_code opcode;
+      if (!noce_parallel_cost_info (set, &cost_class, &mode, &opcode))
+	return serial_cost;
+
+      int width = targetm.sched.reassociation_width (opcode, mode);
+      if (width <= 0)
+	return serial_cost;
+
+      if (levels.length () <= level)
+	levels.safe_grow_cleared (level + 1, true);
+      noce_parallel_cost_level &level_info = levels[level];
+      ++level_info.insns[cost_class];
+      if (level_info.widths[cost_class] == 0)
+	level_info.widths[cost_class] = width;
+      else
+	level_info.widths[cost_class]
+	  = MIN (level_info.widths[cost_class], (unsigned int) width);
+
+      noce_parallel_cost_node node = { dest, level };
+      nodes.safe_push (node);
+    }
+
+  unsigned int issue_rate = 1;
+  if (targetm.sched.issue_rate)
+    issue_rate = MAX (targetm.sched.issue_rate (), 1);
+
+  /* Sum the issue cycles needed for each dependency level.  */
+
+  unsigned int parallel_cost = 0;
+  for (unsigned int i = 0; i < levels.length (); ++i)
+    {
+      unsigned int total_insns = 0;
+      unsigned int level_cycles = 0;
+
+      for (unsigned int j = 0; j < NOCE_PARALLEL_NUM_CLASSES; ++j)
+	if (levels[i].insns[j] != 0)
+	  {
+	    total_insns += levels[i].insns[j];
+	    level_cycles
+	      = MAX (level_cycles,
+		     CEIL (levels[i].insns[j], levels[i].widths[j]));
+	  }
+
+      level_cycles = MAX (level_cycles, CEIL (total_insns, issue_rate));
+      parallel_cost += COSTS_N_INSNS (level_cycles);
+    }
+
+  return MIN (serial_cost, parallel_cost);
+}
+
 /* Return true if SEQ is a good candidate as a replacement for the
    if-convertible sequence described in IF_INFO.
    This is the default implementation that targets can override
@@ -815,7 +1064,7 @@ default_noce_conversion_profitable_p (rtx_insn *seq,
   bool speed_p = if_info->speed_p;
 
   /* Cost up the new sequence.  */
-  unsigned int cost = seq_cost (seq, speed_p);
+  unsigned int cost = noce_parallel_seq_cost (seq, speed_p);
 
   if (cost <= if_info->original_cost)
     return true;
-- 
2.34.1