[RFC][PATCH][mid-end] Optimize immediate choice in comparisons.

[Vlad Lazar <vlad dot lazar at arm dot com>]

Hi.

This patch optimises the choice of immediates in integer comparisons. Integer
comparisons allow for different choices (e.g. a > b is equivalent to a >= b+1)
and there are cases where an incremented/decremented immediate can be loaded into a
register in fewer instructions. The cases are as follows:
  
i)   a >  b or a >= b + 1
ii)  a <= b or a <  b + 1
iii) a >= b or a >  b - 1
iv)  a <  b or a <= b - 1

For each comparison we check whether the equivalent can be performed in less instructions.
This is done on a statement by statement basis, right before the GIMPLE statement is expanded
to RTL. Therefore, it requires a correct implementation of the TARGET_INSN_COST hook.
The change is general and it applies to any integer comparison, regardless of types or location.

For example, on AArch64 for the following code:

int foo (int x)
{
  return x > 0xfefffffe;
}

it generates:

mov	w1, -16777217
cmp	w0, w1
cset	w0, cs

instead of:

mov	w1, 65534
movk	w1, 0xfeff, lsl 16
cmp	w0, w1
cset	w0, hi

Bootstrapped and regtested on aarch64-none-linux-gnu, x86_64-pc-linux-gnu and there are no regressions.

Thanks,
Vlad

gcc/testsuite/
Changelog for gcc/testsuite/Changelog
2018-07-30  Vlad Lazar  <vlad.lazar@arm.com>

	* gcc.target/aarch64/imm_choice_comparison.c: New.

gcc/
Changelog for gcc/Changelog
2018-07-30  Vlad Lazar  <vlad.lazar@arm.com>

	* cfgexpand.c (optimize_immediate_choice): New.
	(can_optimize_immediate_p): Likewise.
	(validate_immediate_optimization): Likewise.
	(update_immediate): Likewise.
	(immediate_optimized_code): Likewise.

---

diff --git a/gcc/cfgexpand.c b/gcc/cfgexpand.c
index 9b91279282e1c6956c8b3699f13036c401ea1dcd..5b0a2e0cdb23f649336844506c8241428b3e6e7d 100644
--- a/gcc/cfgexpand.c
+++ b/gcc/cfgexpand.c
@@ -5423,6 +5423,157 @@ reorder_operands (basic_block bb)
   XDELETE (lattice);
 }
 
+/* Helper function for update_immediate.  Returns the adjusted conditional
+   code for the immediate choice optimization.  See optimize_immediate_choice
+   for cases.  */
+
+static enum tree_code
+immediate_optimized_code (enum tree_code code)
+{
+  switch (code)
+    {
+    case GT_EXPR:
+      return GE_EXPR;
+    case GE_EXPR:
+      return GT_EXPR;
+    case LT_EXPR:
+      return LE_EXPR;
+    case LE_EXPR:
+      return LT_EXPR;
+    default:
+      return code;
+    }
+}
+
+/* Helper function for optimize_immediate_choice.  It updates the immediate
+   and the subcode of the gimple statement.  At the point of calling
+   the function we know that the optimization leads to fewer instructions.
+   stmt points to the gimple statement containing the comparison we wish to
+   optimize and to_add is the amount by which the immediate needs to be
+   adjusted (1 or -1).  */
+
+static void
+update_immediate (gimple *stmt, int to_add)
+{
+  tree inc_dec = to_add == 1 ? build_one_cst (integer_type_node) :
+			       build_minus_one_cst (integer_type_node);
+
+  enum gimple_code code = gimple_code (stmt);
+  if (code == GIMPLE_COND)
+    {
+      gcond *gc = GIMPLE_CHECK2<gcond *> (stmt);
+      tree rhs = gimple_cond_rhs (gc);
+
+      /* Update the statement.  */
+      tree new_rhs = fold_build2 (PLUS_EXPR, TREE_TYPE (rhs), rhs, inc_dec);
+      gimple_cond_set_rhs (gc, new_rhs);
+      gc->subcode = immediate_optimized_code ((enum tree_code) gc->subcode);
+    }
+  if (code == GIMPLE_ASSIGN)
+    {
+      gassign *ga = GIMPLE_CHECK2<gassign *> (stmt);
+      tree rhs2 = gimple_assign_rhs2 (ga);
+
+      tree new_rhs2 = fold_build2 (PLUS_EXPR, TREE_TYPE (rhs2), rhs2, inc_dec);
+      gimple_assign_set_rhs2 (ga, new_rhs2);
+      ga->subcode = immediate_optimized_code ((enum tree_code) ga->subcode);
+    }
+}
+
+/* Helper function for optimize_immediate_choice.  It checks if the other
+   possible immediate leads to a lower rtx cost.  to_add is the amount by
+   which the immediate needs to be adjusted (1 or -1).  The function
+   returns 0 if there is no improvement and the amount by which the immediate
+   needs to be adjusted (1 or -1) otherwise.  */
+
+static int
+validate_immediate_optimization (gimple *stmt, int to_add)
+{
+  tree tree_imm = gimple_code (stmt) == GIMPLE_COND ? gimple_cond_rhs (stmt)
+						: gimple_assign_rhs2 (stmt);
+  const_tree type = TREE_TYPE (tree_imm);
+  widest_int imm = wi::to_widest (tree_imm);
+  enum signop sgn = TYPE_UNSIGNED (type) ? UNSIGNED : SIGNED;
+
+  /* Check for overflow/underflow in the case of signed values and
+     wrapping around in the case of unsigned values.  If any occur
+     cancel the optimization.  */
+
+  widest_int max_type = wi::to_widest (TYPE_MAX_VALUE (type));
+  widest_int min_type = wi::to_widest (TYPE_MIN_VALUE (type));
+  if ((wi::cmp (imm, max_type, sgn) == 0 && to_add == 1)
+      || (wi::cmp (imm, min_type, sgn) == 0 && to_add == -1))
+    return 0;
+
+  widest_int imm_modif = wi::add (imm, to_add);
+
+  rtx reg = gen_reg_rtx (DImode);
+  rtx old_imm = GEN_INT (imm.to_shwi ());
+  rtx new_imm = GEN_INT (imm_modif.to_shwi ());
+
+  rtx_insn *old_rtx = gen_move_insn (reg, old_imm);
+  rtx_insn *new_rtx = gen_move_insn (reg, new_imm);
+
+  /* If the change is beneficial we can just propagate to_add further,
+     otherwise return 0 to cancel the optimization.  */
+  return insn_cost (old_rtx, true) > insn_cost (new_rtx, true) ? to_add : 0;
+}
+
+/* Helper function for optimize_immediate_choice.  Checks if the gimple
+   statement has the right shape for the optimization.  */
+
+static bool
+can_optimize_immediate_p (const gimple *stmt)
+{
+  enum gimple_code code = gimple_code (stmt);
+  if (code != GIMPLE_ASSIGN && code != GIMPLE_COND)
+    return false;
+
+  if (code == GIMPLE_ASSIGN
+      && (gimple_num_ops (stmt) != 3
+	  || TREE_CODE (gimple_assign_rhs2 (stmt)) != INTEGER_CST))
+    return false;
+  if (code == GIMPLE_COND && TREE_CODE (gimple_cond_rhs (stmt)) != INTEGER_CST)
+    return false;
+
+  return true;
+}
+
+/* Entry point for immediate choice optimization.  It aims to choose
+   the simpler immediate in integer comparisons.  The purpose of this
+   is to end up with an immediate which can be loaded into a register
+   in fewer moves, if possible.
+
+   For each integer comparison there exists an equivalent choice:
+     i)   a >  b or a >= b + 1
+     ii)  a <= b or a <  b + 1
+     iii) a >= b or a >  b - 1
+     iv)  a <  b or a <= b - 1
+
+   Comparisons can only appear on the rhs of a GIMPLE_ASSIGN
+   or in a GIMPLE_COND.  */
+
+static void
+optimize_immediate_choice (gimple *stmt)
+{
+  if (!can_optimize_immediate_p (stmt))
+    return;
+
+  /* Check if the other immediate available is preferable.  */
+  int to_add = 0;
+  if (stmt->subcode == GT_EXPR || stmt->subcode == LE_EXPR)
+    to_add = validate_immediate_optimization (stmt, 1);
+
+  if (stmt->subcode == GE_EXPR || stmt->subcode == LT_EXPR)
+    to_add = validate_immediate_optimization (stmt, -1);
+
+  if (!to_add)
+    return;
+
+  /* Update the current statement.  */
+  update_immediate (stmt, to_add);
+}
+
 /* Expand basic block BB from GIMPLE trees to RTL.  */
 
 static basic_block
@@ -5515,6 +5666,7 @@ expand_gimple_basic_block (basic_block bb, bool disable_tail_calls)
       basic_block new_bb;
 
       stmt = gsi_stmt (gsi);
+      optimize_immediate_choice (stmt);
 
       /* If this statement is a non-debug one, and we generate debug
 	 insns, then this one might be the last real use of a TERed
diff --git a/gcc/testsuite/gcc.target/aarch64/imm_choice_comparison.c b/gcc/testsuite/gcc.target/aarch64/imm_choice_comparison.c
new file mode 100644
index 0000000000000000000000000000000000000000..b30dcca88f44ca73fcb8202ea488888b365400c8
--- /dev/null
+++ b/gcc/testsuite/gcc.target/aarch64/imm_choice_comparison.c
@@ -0,0 +1,53 @@
+/* { dg-do compile } */
+/* { dg-options "-O2" } */
+
+int
+foo (int x)
+{
+  return x >= 0xfff01;
+}
+
+int
+GT (unsigned int x)
+{
+  return x > 0xfefffffe;
+}
+
+/* Go from four moves to two.  */
+
+int
+baz (long long x)
+{
+  return x <= 0x1999999999999998;
+}
+
+int
+LE (unsigned int x)
+{
+  return x <= 0xfefffffe;
+}
+
+int
+GE (long long x)
+{
+  return x >= 0xff000000;
+}
+
+int
+LT (int x)
+{
+  return x < 0xff000000;
+}
+
+/* Optimize the immediate in conditionals.  */
+
+int check (int x, int y)
+{
+  if (x > y && GT (x))
+    return 100;
+
+  return x;
+}
+
+/* baz produces one movk instruction.  */
+/* { dg-final { scan-assembler-times "movk" 1 } } */