From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-lf1-x12d.google.com (mail-lf1-x12d.google.com [IPv6:2a00:1450:4864:20::12d]) by sourceware.org (Postfix) with ESMTPS id 4D1723858D39 for ; Thu, 10 Nov 2022 21:11:34 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 4D1723858D39 Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=vrull.eu Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=vrull.eu Received: by mail-lf1-x12d.google.com with SMTP id d6so5427638lfs.10 for ; Thu, 10 Nov 2022 13:11:34 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=vrull.eu; s=google; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:from:to:cc:subject:date:message-id:reply-to; bh=YFkJOmNVPGAmADhQiaxoF+VsaoHc0WoSt2SyH0DFvgo=; b=Bod5K/aK0dcGPIlHjumHmPj71niEZhwQ0lHeeqRiIegadl9eKStdUs58OOMQtIdYQn 4pZed4L/Drt762Lo+2b23BBNgciHK09mpF6kQu6OKXtfuJvViUMGaL7uNQIVb143UkMR 51j1EDwE9IwjyK3/BHvPygdpXiFoPvwnnxUF+v8Kjte5rmfH8LPLPwQfNSl3pl5MO7y1 pdk6cAOWEHgqy4ao9fbZflX/VCL83uX7byMM3THza9jrC1W2bGozi5dLtq47pnYY1SmF 7/ACAW9Lo48gNEPasBV++2S8nqQAm4Sajv9YKItfAt7OK2ynN6ZZPFsdmPQXh9F7oXVN foUQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=YFkJOmNVPGAmADhQiaxoF+VsaoHc0WoSt2SyH0DFvgo=; b=HD/piSXyxDxOHmI8cg3th+h+OVcSu0dVcd7pbxLHRcb8oHPU3yZi6q/Gp/c6tuA0k3 bq8UmbAWeIRIGO8h138DWyZSx+bz9YolIGZGLaSfOG0hmUMD2JGjYAvXz0C61pBtVfG5 0ggkQmLLEG8H7r7EFwLiXSYpEMTYDsmvdSiQHguYp88jSHBWXQQJX36X50yMMidWGBmj tn1MkRoHaVHAscb6DaMO/YK1Dmb9OuXZxb9OCzqQaRyDwlHECVwX2YZQMGAg+Pq6XRwG uDKIsxXt87ad51JEMT7orWtZa8R/K3OANQCI7kjZ4wR/C1jTaoK4D+pu3V0F5MoBcubR fArw== X-Gm-Message-State: ACrzQf0RvgDTbxs+BgNpD/mNi8OO9qA/rxYZzZj7l5X6F3v/1yvSOpBf X6QNe93AlWU4giDukPaOR2VANnkKfLWqfUIqgIxmoA== X-Google-Smtp-Source: AMsMyM6+0kUHLhcBaSNeb1UdyR7rbEZs/We8ihCZbmFuMHfqQv2xRyX5iYilhJCPJg6uTE0YSsfm3YzDg7i1jtHO3ao= X-Received: by 2002:a05:6512:25c:b0:4b1:753b:e671 with SMTP id b28-20020a056512025c00b004b1753be671mr1690254lfo.441.1668114692441; Thu, 10 Nov 2022 13:11:32 -0800 (PST) MIME-Version: 1.0 References: In-Reply-To: From: Philipp Tomsich Date: Thu, 10 Nov 2022 22:11:21 +0100 Message-ID: Subject: Re: [PATCH] RISC-V: costs: support shift-and-add in strength-reduction To: Palmer Dabbelt Cc: gcc-patches@gcc.gnu.org, Kito Cheng , Vineet Gupta , christoph.muellner@vrull.eu, jlaw@ventanamicro.com Content-Type: text/plain; charset="UTF-8" X-Spam-Status: No, score=-9.0 required=5.0 tests=BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,GIT_PATCH_0,JMQ_SPF_NEUTRAL,RCVD_IN_DNSWL_NONE,SPF_HELO_NONE,SPF_PASS,TXREP autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org List-Id: On Thu, 10 Nov 2022 at 21:47, Palmer Dabbelt wrote: > > On Thu, 10 Nov 2022 07:09:35 PST (-0800), philipp.tomsich@vrull.eu wrote: > > On Thu, 10 Nov 2022 at 02:46, Palmer Dabbelt wrote: > >> > >> On Tue, 08 Nov 2022 11:54:34 PST (-0800), philipp.tomsich@vrull.eu wrote: > >> > The strength-reduction implementation in expmed.c will assess the > >> > profitability of using shift-and-add using a RTL expression that wraps > >> > a MULT (with a power-of-2) in a PLUS. Unless the RISC-V rtx_costs > >> > function recognizes this as expressing a sh[123]add instruction, we > >> > will return an inflated cost---thus defeating the optimization. > >> > > >> > This change adds the necessary idiom recognition to provide an > >> > accurate cost for this for of expressing sh[123]add. > >> > > >> > Instead on expanding to > >> > li a5,200 > >> > mulw a0,a5,a0 > >> > with this change, the expression 'a * 200' is sythesized as: > >> > sh2add a0,a0,a0 // *5 = a + 4 * a > >> > sh2add a0,a0,a0 // *5 = a + 4 * a > >> > slli a0,a0,3 // *8 > >> > >> That's more instructions, but multiplication is generally expensive. At > >> some point I remember the SiFive cores getting very fast integer > >> multipliers, but I don't see that reflected in the cost model anywhere > >> so maybe I'm just wrong? Andrew or Kito might remember... > >> > >> If the mul-based sequences are still faster on the SiFive cores then we > >> should probably find a way to keep emitting them, which may just be a > >> matter of adjusting those multiply costs. Moving to the shift-based > >> sequences seems reasonable for a generic target, though. > > > > The cost for a regular MULT is COSTS_N_INSNS(4) for the series-7 (see > > the SImode and DImode entries in the int_mul line): > > /* Costs to use when optimizing for Sifive 7 Series. */ > > static const struct riscv_tune_param sifive_7_tune_info = { > > {COSTS_N_INSNS (4), COSTS_N_INSNS (5)}, /* fp_add */ > > {COSTS_N_INSNS (4), COSTS_N_INSNS (5)}, /* fp_mul */ > > {COSTS_N_INSNS (20), COSTS_N_INSNS (20)}, /* fp_div */ > > {COSTS_N_INSNS (4), COSTS_N_INSNS (4)}, /* int_mul */ > > {COSTS_N_INSNS (6), COSTS_N_INSNS (6)}, /* int_div */ > > 2, /* issue_rate */ > > 4, /* branch_cost */ > > 3, /* memory_cost */ > > 8, /* fmv_cost */ > > true, /* slow_unaligned_access */ > > }; > > > > So the break-even is at COSTS_N_INSNS(4) + rtx_cost(immediate). > > > > Testing against series-7, we get up to 5 (4 for the mul + 1 for the > > li) instructions from strength reduction: > > > > val * 783 > > => > > sh1add a5,a0,a0 > > slli a5,a5,4 > > add a5,a5,a0 > > slli a5,a5,4 > > sub a0,a5,a0 > > > > but fall back to a mul, once the cost exceeds this: > > > > val * 1574 > > => > > li a5,1574 > > mul a0,a0,a5 > > That's just the cost model, though, not the hardware. My argument was > essentially that the cost model is wrong, assuming how I remember the > hardware is right. That was a while ago and there's a lot of options, > though, so I'm not sure what these things actually look like. > > IMO that doesn't need to block this patch, though: having one incorrect > cost model so it cancels out another one is a great way to lose our > minds. > > >> Either way, it probably warrants a test case to make sure we don't > >> regress in the future. > > > > Ack. Will be added for v2. > > > >> > >> > > >> > gcc/ChangeLog: > >> > > >> > * config/riscv/riscv.c (riscv_rtx_costs): Recognize shNadd, > >> > if expressed as a plus and multiplication with a power-of-2. > > > > This will still need to be regenerated (it's referring to a '.c' > > extension still). > > > >> > > >> > --- > >> > > >> > gcc/config/riscv/riscv.cc | 13 +++++++++++++ > >> > 1 file changed, 13 insertions(+) > >> > > >> > diff --git a/gcc/config/riscv/riscv.cc b/gcc/config/riscv/riscv.cc > >> > index ab6c745c722..0b2c4b3599d 100644 > >> > --- a/gcc/config/riscv/riscv.cc > >> > +++ b/gcc/config/riscv/riscv.cc > >> > @@ -2451,6 +2451,19 @@ riscv_rtx_costs (rtx x, machine_mode mode, int outer_code, int opno ATTRIBUTE_UN > >> > *total = COSTS_N_INSNS (1); > >> > return true; > >> > } > >> > + /* Before strength-reduction, the shNadd can be expressed as the addition > >> > + of a multiplication with a power-of-two. If this case is not handled, > >> > + the strength-reduction in expmed.c will calculate an inflated cost. */ > >> > + if (TARGET_ZBA > >> > + && mode == word_mode > >> > + && GET_CODE (XEXP (x, 0)) == MULT > >> > + && REG_P (XEXP (XEXP (x, 0), 0)) > >> > + && CONST_INT_P (XEXP (XEXP (x, 0), 1)) > >> > + && IN_RANGE (pow2p_hwi (INTVAL (XEXP (XEXP (x, 0), 1))), 1, 3)) > >> > >> IIUC the fall-through is biting us here and this matches power-of-2 +1 > >> and power-of-2 -1. That looks to be the case for the one below, though, > >> so not sure if I'm just missing something? > > > > The strength-reduction in expmed.cc uses "(PLUS (reg) (MULT (reg) > > ))" to express a shift-then-add. > > Here's one of the relevant snippets (from the internal costing in expmed.cc): > > all.shift_mult = gen_rtx_MULT (mode, all.reg, all.reg); > > all.shift_add = gen_rtx_PLUS (mode, all.shift_mult, all.reg); > > > > So while we normally encounter a "(PLUS (reg) (ASHIFT (reg) > > ))", for the strength-reduction we also need to provide the > > cost for the expression with a MULT). > > The other idioms (those matching above and below the new one) always > > require an ASHIFT for the inner. > > I was trying to say this also matches "(MINUS (REG) (MULT (reg) > ))", the switch statement block it's in has PLUS and MINUS as a > fall through. IIUC we don't have single-instruction patterns for the > minus case, unless I'm missing some sort of trick in ZBA? In fact, this was caught with the test cases being pulled it. If left unchecked, it led to cases with one or 2 extra instructions being generated beyond the breakeven point for multiplication. So this will also be queued up for v2. Thanks for pointing it out! > > That also looks to be the case for some of the other patterns in this > block. > > >> > + { > >> > + *total = COSTS_N_INSNS (1); > >> > + return true; > >> > + } > >> > /* shNadd.uw pattern for zba. > >> > [(set (match_operand:DI 0 "register_operand" "=r") > >> > (plus:DI