This is the mail archive of the mailing list for the GCC project.

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[PATCH] PR middle-end/15239: Artificial limit in expand_mult

The following is my proposed solution to PR middle-end/15239.  Since
the start of current CVS, GCC's middle-end has placed an artificial
restriction on the maximum cost of the sequence of additions and
shifts used to implement multiplication by constant.  This meant that
a synthetic multiply would only be used, even if it was cheaper than
using a multiply, if it was also cheaper than 12 additions.

I believe that the original motivations for this limit may no longer
apply, and its undesirable for the middle-end to prevent a well-tuned
backend from generating "optimal" code.  The original authors may not
have forseen advances in superscalar dispatch that allows modern CPUs
to issue multiple additions and shifts per cycle, or complex scheduling
and pairing constraints that result in integer multiplication instructions
being more than 20 times more expensive than an addition.

This limitation is not required from an algorithmic perspective as
synthetic multiply is able to produce a sequence of less than "word
bits" number of shifts and adds.  Even without the presence of combined
shift-and-add instructions this places an upper bound on 32 or 64
instructions on most platforms.

There's also the possibility that this constraint was originally
introduced to avoid excessive compile-time for "tricky" operands.
However, the usual "Hennessy and Patterson" analysis of distribution of
operands indicates that large co-efficients are expected to be extremely
rare (expect perhaps for division-by-multiplication) and the importance of
synthetic multiplication vs. total compile-time has remained constant over
the last ten years whilst processing power has improved considerably.

Finally, both above points are made moot by the fact that backends
have the ability to adjust the rtx_cost of multiplications themselves.
I suspect that nowadays the middle-end can expect the backend to return
reasonable estimates of instruction costs, rather than additionally
impose a fragile "reasonableness" constraint, that's likely to become
less relevant with time.  Certainly this limitation should no longer
apply to modern IA-32 processors, and probably most architectures.

I was considering applying this patch as "obvious",  but in the bugzilla
and gcc-list discussions, nobody has supported the proposal for removing
this limit althogether.  Hence I thought I'd open it for discussion in
case anybody feels strongly that my reasoning above is fataly flawed.

The following patch has been tested on i686-pc-linux-gnu with a full
"make bootstrap", all languages except treelang, and regression tested
with a top-level "make -k check" with no new failures.

Ok for mainline?

2004-05-09  Roger Sayle  <>

	PR middle-end/15239
	* expmed.c (expand_mult): Remove artificial restriction on the
	maximum cost of a synthetic multiplication sequence.

Index: expmed.c
RCS file: /cvs/gcc/gcc/gcc/expmed.c,v
retrieving revision 1.158
diff -c -3 -p -r1.158 expmed.c
*** expmed.c	24 Apr 2004 01:03:11 -0000	1.158
--- expmed.c	9 May 2004 22:54:04 -0000
*************** expand_mult (enum machine_mode mode, rtx
*** 2639,2645 ****
        && (unsignedp || !flag_trapv))
        int mult_cost = rtx_cost (gen_rtx_MULT (mode, op0, op1), SET);
-       mult_cost = MIN (12 * add_cost, mult_cost);

        if (choose_mult_variant (mode, INTVAL (const_op1), &algorithm, &variant,
--- 2639,2644 ----

Roger Sayle,                         E-mail:
OpenEye Scientific Software,         WWW:
Suite 1107, 3600 Cerrillos Road,     Tel: (+1) 505-473-7385
Santa Fe, New Mexico, 87507.         Fax: (+1) 505-473-0833

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]