[Bug middle-end/91213] Missed optimization: (sub X Y) -> (xor X Y) when Y <= X and isPowerOf2(X + 1)

["rdapp at gcc dot gnu.org" <gcc-bugzilla@gcc.gnu.org>]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=91213

--- Comment #8 from rdapp at gcc dot gnu.org ---
Hacked something together, inspired by the other cases that try two different
sequences.  Does this go into the right direction?  Works for me on s390. I see
some regressions related to predictive commoning that I will look into.

diff --git a/gcc/expr.cc b/gcc/expr.cc
index c90cde35006b..395b4df2e214 100644
--- a/gcc/expr.cc
+++ b/gcc/expr.cc
@@ -23,6 +23,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "backend.h"
 #include "target.h"
 #include "rtl.h"
+#include "tree-core.h"
 #include "tree.h"
 #include "gimple.h"
 #include "predict.h"
@@ -65,7 +66,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "rtx-vector-builder.h"
 #include "tree-pretty-print.h"
 #include "flags.h"

 /* If this is nonzero, we do not bother generating VOLATILE
    around volatile memory references, and we are willing to
@@ -9358,6 +9359,21 @@ expand_expr_real_2 (sepops ops, rtx target, machine_mode
tmode,
          return simplify_gen_binary (MINUS, mode, op0, op1);
        }

+      /* Convert const - A to A xor const if integer_pow2p (const + 1)
+        and 0 <= A <= const.  */
+      if (code == MINUS_EXPR
+         && TREE_CODE (treeop0) == INTEGER_CST
+         && SCALAR_INT_MODE_P (mode)
+         && unsignedp
+         && wi::exact_log2 (wi::to_wide (treeop0) + 1) != -1)
+       {
+         rtx res = maybe_optimize_cst_sub (code, treeop0, treeop1,
+                                           mode, unsignedp, type,
+                                           target, subtarget);
+         if (res)
+           return res;
+       }
+
       /* No sense saving up arithmetic to be done
         if it's all in the wrong mode to form part of an address.
         And force_operand won't know whether to sign-extend or
@@ -12641,6 +12657,77 @@ maybe_optimize_mod_cmp (enum tree_code code, tree
*arg0, tree *arg1)
   return code == EQ_EXPR ? LE_EXPR : GT_EXPR;
 }

+/* Optimize cst - x if integer_pow2p (cst + 1) and 0 >= x <= cst.  */
+
+rtx
+maybe_optimize_cst_sub (enum tree_code code, tree treeop0, tree treeop1,
+                       machine_mode mode, int unsignedp, tree type,
+                       rtx target, rtx subtarget)
+{
+  gcc_checking_assert (code == MINUS_EXPR);
+  gcc_checking_assert (TREE_CODE (treeop0) == INTEGER_CST);
+  gcc_checking_assert (TREE_CODE (TREE_TYPE (treeop1)) == INTEGER_TYPE);
+  gcc_checking_assert (wi::exact_log2 (wi::to_wide (treeop0) + 1) != -1);
+
+  if (!optimize)
+    return NULL_RTX;
+
+  optab this_optab;
+  rtx op0, op1;
+
+  if (wi::leu_p (tree_nonzero_bits (treeop1), tree_nonzero_bits (treeop0)))
+    {
+      expand_operands (treeop0, treeop1, subtarget, &op0, &op1,
+                      EXPAND_NORMAL);
+      bool speed_p = optimize_insn_for_speed_p ();
+      do_pending_stack_adjust ();
+      start_sequence ();
+      this_optab = optab_for_tree_code (MINUS_EXPR, type,
+                                       optab_default);
+      rtx subi = expand_binop (mode, this_optab, op0, op1, target,
+                              unsignedp, OPTAB_LIB_WIDEN);
+
+      rtx_insn *sub_insns = get_insns ();
+      end_sequence ();
+      start_sequence ();
+      this_optab = optab_for_tree_code (BIT_XOR_EXPR, type,
+                                       optab_default);
+      rtx xori = expand_binop (mode, this_optab, op0, op1, target,
+                              unsignedp, OPTAB_LIB_WIDEN);
+      rtx_insn *xor_insns = get_insns ();
+      end_sequence ();
+      unsigned sub_cost = seq_cost (sub_insns, speed_p);
+      unsigned xor_cost = seq_cost (xor_insns, speed_p);
+      /* If costs are the same then use as tie breaker the other other
+        factor.  */
+      if (sub_cost == xor_cost)
+       {
+         sub_cost = seq_cost (sub_insns, !speed_p);
+         xor_cost = seq_cost (xor_insns, !speed_p);
+       }
+
+      if (sub_cost <= xor_cost)
+       {
+         emit_insn (sub_insns);
+         return subi;
+       }
+
+      emit_insn (xor_insns);
+      return xori;
+    }
+
+  return NULL_RTX;
+}
+
 /* Optimize x - y < 0 into x < 0 if x - y has undefined overflow.  */

 void
diff --git a/gcc/expr.h b/gcc/expr.h
index 035118324057..9c4f2ed02fcb 100644
--- a/gcc/expr.h
+++ b/gcc/expr.h
@@ -317,6 +317,8 @@ extern tree string_constant (tree, tree *, tree *, tree *);
 extern tree byte_representation (tree, tree *, tree *, tree *);

 extern enum tree_code maybe_optimize_mod_cmp (enum tree_code, tree *, tree *);
+extern rtx maybe_optimize_cst_sub (enum tree_code, tree, tree,
+                                  machine_mode, int, tree , rtx, rtx);
 extern void maybe_optimize_sub_cmp_0 (enum tree_code, tree *, tree *);

 /* Two different ways of generating switch statements.  */