[PATCH][AArch64][1/3] Expand signed mod by power of 2 using CSNEG
Kyrill Tkachov
kyrylo.tkachov@arm.com
Thu Aug 20 08:24:00 GMT 2015
Ping.
https://gcc.gnu.org/ml/gcc-patches/2015-08/msg00710.html
Thanks,
Kyrill
On 03/08/15 14:01, James Greenhalgh wrote:
> On Fri, Jul 24, 2015 at 11:55:33AM +0100, Kyrill Tkachov wrote:
>> Hi all,
>>
>> This patch implements an aarch64-specific expansion of the signed modulo
by a power of 2.
>> The proposed sequence makes use of the conditional negate instruction
CSNEG.
>> For a power of N, x % N can be calculated with:
>> negs x1, x0
>> and x0, x0, #(N - 1)
>> and x1, x1, #(N - 1)
>> csneg x0, x0, x1, mi
>>
>> So, for N == 256 this would be:
>> negs x1, x0
>> and x0, x0, #255
>> and x1, x1, #255
>> csneg x0, x0, x1, mi
>>
>> For comparison, the existing sequence emitted by expand_smod_pow2 in
expmed.c is:
>> asr x1, x0, 63
>> lsr x1, x1, 56
>> add x0, x0, x1
>> and x0, x0, 255
>> sub x0, x0, x1
>>
>> Note that the CSNEG sequence is one instruction shorter and that the two
and operations
>> are independent, compared to the existing sequence where all instructions
are dependent
>> on the preceeding instructions.
>>
>> For the special case of N == 2 we can do even better:
>> cmp x0, xzr
>> and x0, x0, 1
>> csneg x0, x0, x0, ge
>>
>> I first tried implementing this in the generic code in expmed.c but that
didn't work
>> out for a few reasons:
>>
>> * This relies on having a conditional-negate instruction. We could gate
it on
>> HAVE_conditional_move and the combiner is capable of merging the final
negate into
>> the conditional move if a conditional negate is available (like on
aarch64) but on
>> targets without a conditional negate this would end up emitting a
separate negate.
>>
>> * The first negs has to be a negs for the sequence to be a win i.e.
having a separate
>> negate and compare makes the sequence slower than the existing one (at
least in my
>> microbenchmarking) and I couldn't get subsequent passes to combine the
negate and combine
>> into the negs (presumably due to the use of the negated result in one of
the ands).
>> Doing it in the aarch64 backend where I could just call the exact gen_*
functions that
>> I need worked much more cleanly.
>>
>> The costing logic is updated to reflect this sequence during the
intialisation of
>> expmed.c where it calculates the smod_pow2_cheap metric.
>>
>> The tests will come in patch 3 of the series which are partly shared with
the equivalent
>> arm implementation.
>>
>> Bootstrapped and tested on aarch64.
>> Ok for trunk?
>>
>> diff --git a/gcc/config/aarch64/aarch64.c b/gcc/config/aarch64/aarch64.c
>> index 9d88a60..7bb4a55 100644
>> --- a/gcc/config/aarch64/aarch64.c
>> +++ b/gcc/config/aarch64/aarch64.c
>> @@ -6639,8 +6639,26 @@ cost_plus:
>> if (VECTOR_MODE_P (mode))
>> *cost += extra_cost->vect.alu;
>> else if (GET_MODE_CLASS (mode) == MODE_INT)
>> - *cost += (extra_cost->mult[mode == DImode].add
>> - + extra_cost->mult[mode == DImode].idiv);
>> + {
>> + /* We can expand signed mod by power of 2 using a
>> + NEGS, two parallel ANDs and a CSNEG. Assume here
>> + that CSNEG is COSTS_N_INSNS (1). This case should
>> + only ever be reached through the set_smod_pow2_cheap check
>> + in expmed.c. */
>> + if (code == MOD
>> + && CONST_INT_P (XEXP (x, 1))
>> + && exact_log2 (INTVAL (XEXP (x, 1))) > 0
>> + && (mode == SImode || mode == DImode))
>> + {
>> + *cost += COSTS_N_INSNS (3)
>> + + 2 * extra_cost->alu.logical
>> + + extra_cost->alu.arith;
>> + return true;
>> + }
>> +
>> + *cost += (extra_cost->mult[mode == DImode].add
>> + + extra_cost->mult[mode == DImode].idiv);
>> + }
>> else if (mode == DFmode)
>> *cost += (extra_cost->fp[1].mult
>> + extra_cost->fp[1].div);
> This looks like it calculates the wrong cost for !speed. I think we will
> still expand through mod<mode>3 when compiling for size, so we probably
> still want to cost the multiple instructions.
>
> Have I misunderstood?
You're right, the logic needs a bit of wiggling to do the right
thing. I've moved this case into a separate MOD case and added
a gate on speed for the extra costs addition.
Ok?
Thanks,
Kyrill
2015-08-13 Kyrylo Tkachov <kyrylo.tkachov@arm.com>
* config/aarch64/aarch64.md (mod<mode>3): New define_expand.
(*neg<mode>2_compare0): Rename to...
(neg<mode>2_compare0): ... This.
* config/aarch64/aarch64.c (aarch64_rtx_costs, MOD case):
Move check for speed inside the if-then-elses. Reflect
CSNEG sequence in MOD by power of 2 case.
>
> Thanks,
> James
>
aarch64-mod-2.patch
commit de67e5fba716ce835f595c4167f57ec4faf61607
Author: Kyrylo Tkachov <kyrylo.tkachov@arm.com>
Date: Wed Jul 15 17:01:13 2015 +0100
[AArch64][1/3] Expand signed mod by power of 2 using CSNEG
diff --git a/gcc/config/aarch64/aarch64.c b/gcc/config/aarch64/aarch64.c
index 1394ed7..c8bd8d2 100644
--- a/gcc/config/aarch64/aarch64.c
+++ b/gcc/config/aarch64/aarch64.c
@@ -6652,6 +6652,25 @@ cost_plus:
return true;
case MOD:
+ /* We can expand signed mod by power of 2 using a
+ NEGS, two parallel ANDs and a CSNEG. Assume here
+ that CSNEG is COSTS_N_INSNS (1). This case should
+ only ever be reached through the set_smod_pow2_cheap check
+ in expmed.c. */
+ if (CONST_INT_P (XEXP (x, 1))
+ && exact_log2 (INTVAL (XEXP (x, 1))) > 0
+ && (mode == SImode || mode == DImode))
+ {
+ *cost += COSTS_N_INSNS (3);
+
+ if (speed)
+ *cost += 2 * extra_cost->alu.logical
+ + extra_cost->alu.arith;
+
+ return true;
+ }
+
+ /* Fall-through. */
case UMOD:
if (speed)
{
diff --git a/gcc/config/aarch64/aarch64.md b/gcc/config/aarch64/aarch64.md
index b7b04c4..a515573 100644
--- a/gcc/config/aarch64/aarch64.md
+++ b/gcc/config/aarch64/aarch64.md
@@ -302,6 +302,62 @@ (define_expand "cmp<mode>"
}
)
+;; AArch64-specific expansion of signed mod by power of 2 using CSNEG.
+;; For x0 % n where n is a power of 2 produce:
+;; negs x1, x0
+;; and x0, x0, #(n - 1)
+;; and x1, x1, #(n - 1)
+;; csneg x0, x0, x1, mi
+
+(define_expand "mod<mode>3"
+ [(match_operand:GPI 0 "register_operand" "")
+ (match_operand:GPI 1 "register_operand" "")
+ (match_operand:GPI 2 "const_int_operand" "")]
+ ""
+ {
+ HOST_WIDE_INT val = INTVAL (operands[2]);
+
+ if (val <= 0
+ || exact_log2 (INTVAL (operands[2])) <= 0
+ || !aarch64_bitmask_imm (INTVAL (operands[2]) - 1, <MODE>mode))
+ FAIL;
+
+ rtx mask = GEN_INT (val - 1);
+
+ /* In the special case of x0 % 2 we can do the even shorter:
+ cmp x0, xzr
+ and x0, x0, 1
+ csneg x0, x0, x0, ge. */
+ if (val == 2)
+ {
+ rtx masked = gen_reg_rtx (<MODE>mode);
+ rtx ccreg = aarch64_gen_compare_reg (LT, operands[1], const0_rtx);
+ emit_insn (gen_and<mode>3 (masked, operands[1], mask));
+ rtx x = gen_rtx_LT (VOIDmode, ccreg, const0_rtx);
+ emit_insn (gen_csneg3<mode>_insn (operands[0], x, masked, masked));
+ DONE;
+ }
+
+ rtx neg_op = gen_reg_rtx (<MODE>mode);
+ rtx_insn *insn = emit_insn (gen_neg<mode>2_compare0 (neg_op,
operands[1]));
+
+ /* Extract the condition register and mode. */
+ rtx cmp = XVECEXP (PATTERN (insn), 0, 0);
+ rtx cc_reg = SET_DEST (cmp);
+ rtx cond = gen_rtx_GE (VOIDmode, cc_reg, const0_rtx);
+
+ rtx masked_pos = gen_reg_rtx (<MODE>mode);
+ emit_insn (gen_and<mode>3 (masked_pos, operands[1], mask));
+
+ rtx masked_neg = gen_reg_rtx (<MODE>mode);
+ emit_insn (gen_and<mode>3 (masked_neg, neg_op, mask));
+
+ emit_insn (gen_csneg3<mode>_insn (operands[0], cond,
+ masked_neg, masked_pos));
+ DONE;
+ }
+)
+
(define_insn "*condjump"
[(set (pc) (if_then_else (match_operator 0 "aarch64_comparison_operator"
[(match_operand 1 "cc_register" "") (const_int
0)])
@@ -2392,7 +2448,7 @@ (define_insn "*ngcsi_uxtw"
[(set_attr "type" "adc_reg")]
)
-(define_insn "*neg<mode>2_compare0"
+(define_insn "neg<mode>2_compare0"
[(set (reg:CC_NZ CC_REGNUM)
(compare:CC_NZ (neg:GPI (match_operand:GPI 1 "register_operand"
"r"))
(const_int 0)))
More information about the Gcc-patches
mailing list