diff mbox

[ifcvt] Teach RTL ifcvt to handle multiple simple set instructions

Message ID 1446228218-30943-1-git-send-email-james.greenhalgh@arm.com
State Superseded
Headers show

Commit Message

James Greenhalgh Oct. 30, 2015, 6:03 p.m. UTC
On Thu, Sep 10, 2015 at 07:23:28PM +0100, Bernd Schmidt wrote:
> On 09/08/2015 04:53 PM, James Greenhalgh wrote:

> > One big question I have with this patch is how I ought to write a meaningful

> > cost model I've used. It seems like yet another misuse of RTX costs, and

> > another bit of stuff for targets to carefully balance. Now, if the

> > relative cost of branches and conditional move instructions is not

> > carefully managed, you may enable or disable these optimisations. This is

> > probably acceptable, but I dislike adding more and more gotcha's to

> > target costs, as I get bitten by them hard enough as is!

>

> The code you have seems reasonable, except that for compile time it

> might make sense to not even attempt the optimization if the number of

> sets is too large. I'm not too worried about that, but maybe you could

> bail out early if your cost estimate goes too much above the branch cost.


Thanks all for the review of this patch. I was hoping to look at fixing the
costs model first, but that seems likely to continue to be controversial
and worthy of a more considerable period to work through kinks in the
design rather than rushed in to the closing days of Stage 1. I'll get back
to the list soon with what I'd like to achieve with a costs rework and
how I plan to go about it.

In the interim, I'd like to try to find a route to get this patch accepted
and committed.

The goal after I rewrite the costs should be for us to use whatever
new replacement_cost (or similar) hook we end up building. That will
necessitate building and optimising some RTX which we are going to throw
away, I think that is the proffered direction (though still needs
discussed) and compile time will be a necessary sacrifice I'm afraid.

In the FORNOW cost model, we just count instructions. We can do that
early and avoid creating the extra RTX. That's what I do here.

> > +      /* If we were supposed to read from an earlier write in this block,

> > +	 we've changed the register allocation.  Rewire the read.  While

> > +	 we are looking, also try to catch a swap idiom.  */

>

> So this is one interesting case; do you also have to worry about others

> (such as maybe setting the same register multiple times)?


I'm hoping that cases like that will have either been cleaned up already
or will be cleaned up later. For the particular example you mention, we
would have something like:

    if (a > b)
      x = 1;
      y = 2;
      x = x;
      y = x;

And would if-convert (catching with the existing swap idiom check) to:

  tmp_x = (a > b) ? 1 : x;
  tmp_y = (a > b) ? 2 : y;
  tmp_x2 = (a > b) ? 1 : x;
  tmp_y2 = (a > b) ? 1 : y;
  x = tmp_x
  y = tmp_y
  x = tmp_x2
  y = tmp_y2

Which, while ugly, one would hope would be cleaned to:

  tmp_x2 = (a > b) ? 1 : x;
  tmp_y2 = (a > b) ? 1 : y;
  x = tmp_x2
  y = tmp_y2

I've expanded the comment to talk about this case.

> > +  /* We must have seen some sort of insn to insert, otherwise we were

> > +     given an empty BB to convert, and we can't handle that.  */

> > +  if (unmodified_insns.is_empty ())

> > +    {

> > +      end_sequence ();

> > +      return FALSE;

> > +    }

>

> Looks like some of the error conditions are tested twice across the two

> new functions? I think it would be better to get rid of one copy or turn

> the second one into a gcc_assert.


I've cleaned this up a little, thanks.

>

>  > No testcase provided, as currently I don't know of targets with a high

>  > enough branch cost to actually trigger the optimisation.

>

> Hmm, so the code would not actually be used right now? In that case I'll

> leave it to others to decide whether we want to apply it. Other than the

> points above it looks OK to me.


We have more than a few targets with BRANCH_COST >= 2 for unpredictable
branches, so I've put together a testcase which exercises at least some of
the code. I'll need to rely on target maintainers to XFAIL their target
(or at least to shout at me if a FAIL pops up, and I can XFAIL their
target).

I've boosttrapped this revision on aarch64-none-linux-gnu and
x86_64-none-linux-gnu with no issues.

By inspection of the x86_64 and aarch64 generated code for Spec2006 we
if-convert in a few additional places (though within the defined cost
model) and we end up with inverse condition codes for the cmoves we put
out. Neither of these looked bad to me.

Is this OK to progress as is while I build myself up to wrestle with
costs for GCC 7?

Thanks,
James

---
gcc/

2015-10-30  James Greenhalgh  <james.greenhalgh@arm.com>

	* ifcvt.c (bb_ok_for_noce_convert_multiple_sets): New.
	(noce_convert_multiple_sets): Likewise.
	(noce_process_if_block): Call them.

gcc/testsuite/

2015-10-30  James Greenhalgh  <james.greenhalgh@arm.com>

	* gcc.dg/ifcvt-4.c: New.
diff mbox

Patch

diff --git a/gcc/ifcvt.c b/gcc/ifcvt.c
index 592e86d..4071490 100644
--- a/gcc/ifcvt.c
+++ b/gcc/ifcvt.c
@@ -3025,6 +3025,249 @@  bb_valid_for_noce_process_p (basic_block test_bb, rtx cond,
   return false;
 }
 
+/* We have something like:
+
+     if (x > y)
+       { i = a; j = b; k = c; }
+
+   Make it:
+
+     tmp_i = (x > y) ? a : i;
+     tmp_j = (x > y) ? b : j;
+     tmp_k = (x > y) ? c : k;
+     i = tmp_i; <- Should be cleaned up
+     j = tmp_j; <- Likewise.
+     k = tmp_k; <- Likewise.
+
+   Look for special cases such as writes to one register which are
+   read back in anotyher SET, as might occur in a swap idiom or
+   similar.
+
+   These look like:
+
+   if (x > y)
+     i = a;
+     j = i;
+
+   Which we want to rewrite to:
+
+     tmp_i = (x > y) ? a : i;
+     tmp_j = (x > y) ? tmp_i : j;
+     i = tmp_i;
+     j = tmp_j;
+
+   We can catch these when looking at (SET x y) by keeping a list of the
+   registers we would have targetted before if-conversion and looking back
+   through it for an overlap with Y.  If we find one, we rewire the
+   conditional set to use the temporary we introduced earlier.
+
+   IF_INFO contains the useful information about the block structure and
+   jump instructions.  */
+
+static int
+noce_convert_multiple_sets (struct noce_if_info *if_info)
+{
+  basic_block test_bb = if_info->test_bb;
+  basic_block then_bb = if_info->then_bb;
+  basic_block join_bb = if_info->join_bb;
+  rtx_insn *jump = if_info->jump;
+  rtx_insn *cond_earliest;
+  rtx_insn *insn;
+
+  start_sequence ();
+
+  /* Decompose the condition attached to the jump.  */
+  rtx cond = noce_get_condition (jump, &cond_earliest, false);
+  rtx x = XEXP (cond, 0);
+  rtx y = XEXP (cond, 1);
+  rtx_code cond_code = GET_CODE (cond);
+
+  /* The true targets for a conditional move.  */
+  vec<rtx> targets = vNULL;
+  /* The temporaries introduced to allow us to not consider register
+     overlap.  */
+  vec<rtx> temporaries = vNULL;
+  /* The insns we've emitted.  */
+  vec<rtx_insn *> unmodified_insns = vNULL;
+  int count = 0;
+
+  FOR_BB_INSNS (then_bb, insn)
+    {
+      /* Skip over non-insns.  */
+      if (!active_insn_p (insn))
+	continue;
+
+      rtx set = single_set (insn);
+      gcc_checking_assert (set);
+
+      rtx target = SET_DEST (set);
+      rtx temp = gen_reg_rtx (GET_MODE (target));
+      rtx new_val = SET_SRC (set);
+      rtx old_val = target;
+
+      /* If we were supposed to read from an earlier write in this block,
+	 we've changed the register allocation.  Rewire the read.  While
+	 we are looking, also try to catch a swap idiom.  */
+      for (int i = count - 1; i >= 0; --i)
+	{
+	  if (reg_overlap_mentioned_p (new_val, targets[i]))
+	    {
+	      /* Catch a "swap" style idiom.  */
+	      if (find_reg_note (insn, REG_DEAD, new_val) != NULL_RTX)
+		{
+		  /* The write to targets[i] is only live until the read
+		     here.  As the condition codes match, we can propagate
+		     the set to here.  */
+		   new_val = SET_SRC (single_set (unmodified_insns[i]));
+		}
+	      else
+		new_val = temporaries[i];
+	      break;
+	    }
+	}
+
+      /* If we had a non-canonical conditional jump (i.e. one where
+	 the fallthrough is to the "else" case) we need to reverse
+	 the conditional select.  */
+      if (if_info->then_else_reversed)
+	std::swap (old_val, new_val);
+
+      /* Actually emit the conditional move.  */
+      rtx temp_dest = noce_emit_cmove (if_info, temp, cond_code,
+				       x, y, new_val, old_val);
+
+      /* If we failed to expand the conditional move, drop out and don't
+	 try to continue.  */
+      if (temp_dest == NULL_RTX)
+	{
+	  end_sequence ();
+	  return FALSE;
+	}
+
+      /* Bookkeeping.  */
+      count++;
+      targets.safe_push (target);
+      temporaries.safe_push (temp_dest);
+      unmodified_insns.safe_push (insn);
+    }
+
+  /* We must have seen some sort of insn to insert, otherwise we were
+     given an empty BB to convert, and we can't handle that.  */
+  gcc_assert (!unmodified_insns.is_empty ());
+
+  /* Now fixup the assignments.  */
+  for (int i = 0; i < count; i++)
+    noce_emit_move_insn (targets[i], temporaries[i]);
+
+  /* Actually emit the sequence.  */
+  rtx_insn *seq = get_insns ();
+
+  for (insn = seq; insn; insn = NEXT_INSN (insn))
+    set_used_flags (insn);
+
+  /* Mark all our temporaries and targets as used.  */
+  for (int i = 0; i < count; i++)
+    {
+      set_used_flags (temporaries[i]);
+      set_used_flags (targets[i]);
+    }
+
+  set_used_flags (cond);
+  set_used_flags (x);
+  set_used_flags (y);
+
+  unshare_all_rtl_in_chain (seq);
+  end_sequence ();
+
+  if (!seq)
+    return FALSE;
+
+  for (insn = seq; insn; insn = NEXT_INSN (insn))
+    if (JUMP_P (insn)
+	|| recog_memoized (insn) == -1)
+      return FALSE;
+
+  emit_insn_before_setloc (seq, if_info->jump,
+			   INSN_LOCATION (unmodified_insns.last ()));
+
+  /* Clean up THEN_BB and the edges in and out of it.  */
+  remove_edge (find_edge (test_bb, join_bb));
+  remove_edge (find_edge (then_bb, join_bb));
+  redirect_edge_and_branch_force (single_succ_edge (test_bb), join_bb);
+  delete_basic_block (then_bb);
+  num_true_changes++;
+
+  /* Maybe merge blocks now the jump is simple enough.  */
+  if (can_merge_blocks_p (test_bb, join_bb))
+    {
+      merge_blocks (test_bb, join_bb);
+      num_true_changes++;
+    }
+
+  num_updated_if_blocks++;
+  return TRUE;
+}
+
+/* Return true iff basic block TEST_BB is comprised of only
+   (SET (REG) (REG)) insns suitable for conversion to a series
+   of conditional moves.  FORNOW: Use II to find the expected cost of
+   the branch into/over TEST_BB.
+
+   TODO: This creates an implicit "magic number" for branch_cost.
+   II->branch_cost now guides the maximum number of set instructions in
+   a basic block which is considered profitable to completely
+   if-convert.  */
+
+static bool
+bb_ok_for_noce_convert_multiple_sets (basic_block test_bb,
+				      struct noce_if_info *ii)
+{
+  rtx_insn *insn;
+
+  /* We must have at least one real insn to convert, or there will
+     be trouble!  */
+  unsigned count = 0;
+
+  FOR_BB_INSNS (test_bb, insn)
+    {
+      /* Skip over notes etc.  */
+      if (!active_insn_p (insn))
+	continue;
+
+      /* We only handle SET insns.  */
+      rtx set = single_set (insn);
+      if (set == NULL_RTX)
+	return false;
+
+      rtx dest = SET_DEST (set);
+      rtx src = SET_SRC (set);
+
+      /* We can possibly relax this, but for now only handle REG to REG
+	 moves.  This avoids any issues that might come from introducing
+	 loads/stores that might violate data-race-freedom guarantees.  */
+      if (!(REG_P (src) && REG_P (dest)))
+	return false;
+
+      /* Destination must be appropriate for a conditional write.  */
+      if (!noce_operand_ok (dest))
+	return false;
+
+      /* We must be able to conditionally move in this mode.  */
+      if (!can_conditionally_move_p (GET_MODE (dest)))
+	return false;
+
+      ++count;
+    }
+
+  /* FORNOW: Our cost model is a count of the number of instructions we
+     would if-convert.  This is suboptimal, and should be improved as part
+     of a wider rework of branch_cost.  */
+  if (count > ii->branch_cost)
+    return FALSE;
+
+  return count > 0;
+}
+
 /* Given a simple IF-THEN-JOIN or IF-THEN-ELSE-JOIN block, attempt to convert
    it without using conditional execution.  Return TRUE if we were successful
    at converting the block.  */
@@ -3047,12 +3290,22 @@  noce_process_if_block (struct noce_if_info *if_info)
      (1) if (...) x = a; else x = b;
      (2) x = b; if (...) x = a;
      (3) if (...) x = a;   // as if with an initial x = x.
-
+     (4) if (...) { x = a; y = b; z = c; }  // Like 3, for multiple SETS.
      The later patterns require jumps to be more expensive.
      For the if (...) x = a; else x = b; case we allow multiple insns
      inside the then and else blocks as long as their only effect is
      to calculate a value for x.
-     ??? For future expansion, look for multiple X in such patterns.  */
+     ??? For future expansion, further expand the "multiple X" rules.  */
+
+  /* First look for multiple SETS.  */
+  if (!else_bb
+      && HAVE_conditional_move
+      && !HAVE_cc0
+      && bb_ok_for_noce_convert_multiple_sets (then_bb, if_info))
+    {
+      if (noce_convert_multiple_sets (if_info))
+	return TRUE;
+    }
 
   if (! bb_valid_for_noce_process_p (then_bb, cond, &if_info->then_cost,
 				    &if_info->then_simple))
diff --git a/gcc/testsuite/gcc.dg/ifcvt-4.c b/gcc/testsuite/gcc.dg/ifcvt-4.c
new file mode 100644
index 0000000..16be2b0
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/ifcvt-4.c
@@ -0,0 +1,16 @@ 
+/* { dg-options "-fdump-rtl-ce1 -O2" } */
+int
+foo (int x, int y, int a)
+{
+  int i = x;
+  int j = y;
+  /* Try to make taking the branch likely.  */
+  __builtin_expect (x > y, 1);
+  if (x > y)
+    {
+      i = a;
+      j = i;
+    }
+  return i * j;
+}
+/* { dg-final { scan-rtl-dump "2 true changes made" "ce1" } } */