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

> 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

> On Aug 20, 2015, at 9:59 AM, Mehdi Amini <mehdi.amini at apple.com>
wrote:
> 
>> 
>> 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?
I think -Oz might be MinSize?  -Oz being absolute minimum size at the cost of
significant speed, IIRC.

—escha
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150820/b7c1310c/attachment-0001.html>

> On Aug 20, 2015, at 10:22 AM, escha <escha at apple.com> wrote:
> 
>> 
>> On Aug 20, 2015, at 9:59 AM, Mehdi Amini <mehdi.amini at apple.com
<mailto:mehdi.amini at apple.com>> wrote:
>> 
>>> 
>>> On Aug 20, 2015, at 9:46 AM, Steve King <steve at metrokings.com
<mailto:steve at metrokings.com>> wrote:
>>> 
>>> On Wed, Aug 19, 2015 at 10:58 PM, Mehdi Amini <mehdi.amini at
apple.com <mailto: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?
> 
> I think -Oz might be MinSize?  -Oz being absolute minimum size at the cost
of significant speed, IIRC.
Sure, the question is more what is the tradeoff for -Os.
My remember of -Os is somehow “don’t perform transformation that increases code
size”.
It seems that it is what is done here: converting an (possibly expensive)
division into multiple (less expensive) operations, probably increasing code
size (target dependent admittedly).

— 
Mehdi

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150820/534c1415/attachment-0001.html>

On Thu, Aug 20, 2015 at 9:59 AM, Mehdi Amini <mehdi.amini at apple.com>
wrote:
> If you want the attributes, I think you should pass the attributes and not
the whole Function.
OK.
> Did you consider what I suggested, i.e. inverting the order of the two
tests?
I don't see this suggestion in our thread.

> 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.
>
Nice.  visitSDIV() and visitUDIV() still call isIntDivCheap() for
non-power-of-2 cases.  Passing attributes to isIntDivCheap() to enable
a smart check is still desirable, but you eliminated the need for a
power-of-2 flag.

Today's TargetLowering default:

virtual SDValue BuildSDIVPow2(SDNode *N, const APInt &Divisor,
                              SelectionDAG &DAG,
                              std::vector<SDNode *> *Created) const {
  return SDValue();
}

New default with your approach and Fn attributes:

virtual SDValue BuildSDIVPow2(SDNode *N, const APInt &Divisor,
                              SelectionDAG &DAG,
                              std::vector<SDNode *> *Created) const {

   AttributeSet Attr =
DAG.getMachineFunction().getFunction()->getAttributes();
   if (TLI.isIntDivCheap(N->getValueType(0), Attr))
     return N;
   return SDValue();
}

virtual bool isIntDivCheap(EVT VT, AttributeSet Attr) const {
  return false;
}

X86 is the only in-tree user, so to preserve today's behavior:

bool X86TargetLowering::isIntDivCheap(EVT VT, AttributeSet Attr) const {
  bool OptSize = Attr.hasAttribute(AttributeSet::FunctionIndex,
Attribute::MinSize)
  return OptSize && !VT.isVector();
}