llvm dev - Aug 2015 - [RFC] Improving integer divide optimization (related to D12082)

> On Aug 19, 2015, at 3:48 PM, escha via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
> 
> 
>> On Aug 19, 2015, at 1:45 PM, Steve King via llvm-dev <llvm-dev at
lists.llvm.org <mailto:llvm-dev at lists.llvm.org>> wrote:
>> 
>> In the targets I know, shifts are
>> cheaper than divides in both speed and size.
> 
> From what I remember, udiv by power of 2 already gets turned into a shift
in instcombine; the tricky case is sdiv by power of 2, which takes significantly
more than one instruction. The generic implementation is this:
> 
>     // Splat the sign bit into the register
>     SDValue SGN >         DAG.getNode(ISD::SRA, DL, VT, N0,
>                     DAG.getConstant(VT.getScalarSizeInBits() - 1, DL,
>                                     getShiftAmountTy(N0.getValueType())));
>     AddToWorklist(SGN.getNode());
> 
>     // Add (N0 < 0) ? abs2 - 1 : 0;
>     SDValue SRL >         DAG.getNode(ISD::SRL, DL, VT, SGN,
>                     DAG.getConstant(VT.getScalarSizeInBits() - lg2, DL,
>                                     getShiftAmountTy(SGN.getValueType())));
>     SDValue ADD = DAG.getNode(ISD::ADD, DL, VT, N0, SRL);
>     AddToWorklist(SRL.getNode());
>     AddToWorklist(ADD.getNode());    // Divide by pow2
>     SDValue SRA = DAG.getNode(ISD::SRA, DL, VT, ADD,
>                   DAG.getConstant(lg2, DL,
>                                   getShiftAmountTy(ADD.getValueType())));
> 
> And there’s already a target-specific hook to add a custom implementation
(e.g. on PowerPC):
> 
>     // Target-specific implementation of sdiv x, pow2.
>     if (SDValue Res = BuildSDIVPow2(N))
>       return Res;

Isn’t the problem the fact that the patch makes it harder for a target to get
the generic code to reach its custom hook?
Now the "cheap pow2 sdiv” is merged with the generic “cheap div” you can’t
distinguish anymore.

— 
Mehdi

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150819/aaca66f4/attachment.html>

On Wed, Aug 19, 2015 at 10:58 PM, Mehdi Amini <mehdi.amini at apple.com>
wrote:
>
> Isn’t the problem the fact that the patch makes it harder for a target to
> get the generic code to reach its custom hook?
> Now the "cheap pow2 sdiv” is merged with the generic “cheap div” you
can’t
> distinguish anymore.
>
Yes and also the issue of needing more information to make a smart
isIntDivCheap() decision.

In visitSDIV(), checking looks like this when the denominator is a power of 2.

    if (TLI.isIntDivCheap(N->getValueType(0), MinSize))
      return SDValue();

    // Target-specific implementation of sdiv x, pow2.
    if (SDValue Res = BuildSDIVPow2(N))
      return Res;

How about this for isIntDivCheap?
1) pass Function* to allow the target to decide for itself which
attributes matter, and
2) pass a boolean indicating a power-of-2 denominator.

    const Function* Fn = DAG.getMachineFunction().getFunction();
    if (TLI.isIntDivCheap(N->getValueType(0), Fn, true))
      return SDValue();

    // Target-specific implementation of sdiv x, pow2.
    if (SDValue Res = BuildSDIVPow2(N))
      return Res;

> On Aug 20, 2015, at 9:46 AM, Steve King <steve at metrokings.com>
wrote:
> 
> On Wed, Aug 19, 2015 at 10:58 PM, Mehdi Amini <mehdi.amini at
apple.com> wrote:
>> 
>> Isn’t the problem the fact that the patch makes it harder for a target
to
>> get the generic code to reach its custom hook?
>> Now the "cheap pow2 sdiv” is merged with the generic “cheap div”
you can’t
>> distinguish anymore.
>> 
> 
> Yes and also the issue of needing more information to make a smart
> isIntDivCheap() decision.
> 
> In visitSDIV(), checking looks like this when the denominator is a power of
2.
> 
>    if (TLI.isIntDivCheap(N->getValueType(0), MinSize))
>      return SDValue();
> 
>    // Target-specific implementation of sdiv x, pow2.
>    if (SDValue Res = BuildSDIVPow2(N))
>      return Res;
> 
> How about this for isIntDivCheap?
> 1) pass Function* to allow the target to decide for itself which
> attributes matter, and
If you want the attributes, I think you should pass the attributes and not the
whole Function.

I’m not sure why MinSize does not trigger with -Os by default, Michael is it
intended?
> 2) pass a boolean indicating a power-of-2 denominator.
> 
>    const Function* Fn = DAG.getMachineFunction().getFunction();
>    if (TLI.isIntDivCheap(N->getValueType(0), Fn, true))
>      return SDValue();
> 
>    // Target-specific implementation of sdiv x, pow2.
>    if (SDValue Res = BuildSDIVPow2(N))
>      return Res;
Did you consider what I suggested, i.e. inverting the order of the two tests?

Thinking about it more, I even think than removing the first test entirely would
even be nicer here.
The default implementation for BuildSDIVPow2() would be:

virtual SDValue BuildSDIVPow2(SDValue N) {
   bool MinSize = …. // choose a default, target can override anyway
   if (TLI.isIntDivCheap(N->getValueType(0), MinSize))
     return N;
   return SDValue();  
}

I believe this would preserve the current default behavior and leave targets the
ability to override as much as they want.

— 
Mehdi