llvm dev - Nov 2017 - RFC: Adding 'no-overflow' keyword to 'sdiv'\'udiv' instructions

Introduction:



We would like to add new keyword to 'sdiv'\'udiv' instructions
i.e. 'no-overflow'.

This is the updated solution devised in the discussion:
http://lists.llvm.org/pipermail/llvm-dev/2017-October/118257.html



The proposed keywords:



    "nof" stands for 'no-overflow'



Syntax:



    <result> = sdiv nof <ty> <op1>, <op2> ; yields
ty:result

    <result> = udiv nof <ty> <op1>, <op2> ; yields
ty:result



Overview:



If the keyword is present, the compiler can assume no zero values in the
denominator. Moreover, for sdiv the division MIN_INT / -1 is prohibited.
Otherwise, undefined behavior.



Poison value is returned, in case of division by zero or MIN_INT/-1 if the
keyword not present.



Motivation:



In the current state if the loop-vectorizer decides that it should vectorize a
loop which contains a predicated integer division -  it will vectorize the loop
body and scalarize the predicated division instruction into a sequence of
branches that guard scalar division operations. In some cases the generated code
for this will not be very efficient. Speculating the divides using current
vector sdiv instruction is not an option due to the danger of integer
divide-by-zero.



There are two ways for ensuring the safety of "vector div under
condition", One way is to use the same condition as the scalar execution.
Current serialization approach and previous masked integer div intrinsic
proposal (http://lists.llvm.org/pipermail/llvm-dev/2017-October/118257.html)
follows this idea. Second way is to check the actual divisor, regardless of the
original condition. The 'no-overflow' keyword follows this idea. If the
original code has possible div-by-zero behavior, for example, the latter
approach will end up hiding it -- by taking advantage of the undefined behavior.



With the addition of 'nof' keyword Clang will lower C\C++ division to
'nof' div IR since it will keep the same semantics.

In case the vectorizer decided to vectorize one of the predicated div it can be
done by widening the datatype of the div and the 'nof' keyword will not
hold anymore (because of the risk that one of the predicated lanes may have
zero).

Keeping that with the widened datatype will allow codegen to lower that
instruction as a vector instruction while ensuring lanes that may have zero
values do not trigger a trap.



Implementation considerations:



Initially all the targets can scalarize vector sdiv\udiv instructions to one
with 'nof' by using guards for each lane:



%r = sdiv <4 x i32> %a, %b can be lowered to:



(assuimg %a = <i32 %a.0, i32 %a.1, i32 %a.2, i32 %a.3>, %b = <i32 %b.0,
i32 %b.1, i32 %b.2, i32 %b.3> and %r = <i32 %r.0, i32 %r.1, i32 %r.2, i32
%r.3>)



If CheckSafety(%a.0,%b.0):

  %r.0 = sdiv nof i32 %a.0, %b.0

If CheckSafety(%a.1,%b.1):

  %r.1 = sdiv nof i32 %a.1, %b.1

If CheckSafety(%a.2,%b.2):

  %r.2 = sdiv nof i32 %a.2, %b.2

If CheckSafety(%a.3,%b.3):

  %r.3 = sdiv nof i32 %a.3, %b.3



CheckSafety(a,b): (of sdiv)

  b != 0 || (b != -1 && a != MIN_INT)



CheckSafety(a,b): (of udiv)

  b != 0





Changes in LangRef.rst of udiv/sdiv Instructions:

-----------------------------------------------------------


'``udiv``' Instruction
^^^^^^^^^^^^^^^

Syntax:
"""""""

::

       <result> = udiv <ty> <op1>, <op2>         ;
yields ty:result
       <result> = udiv exact <ty> <op1>, <op2>   ;
yields ty:result
+       <result> = udiv nof <ty> <op1>, <op2>   ; yields
ty:result

Overview:
"""""""""

The '``udiv``' instruction returns the quotient of its two operands.

Arguments:
""""""""""

The two arguments to the '``udiv``' instruction must be
:ref:`integer <t_integer>` or :ref:`vector <t_vector>` of integer
values. Both
arguments must have identical types.

Semantics:
""""""""""

The value produced is the unsigned integer quotient of the two operands.

Note that unsigned integer division and signed integer division are
distinct operations; for signed integer division, use '``sdiv``'.

Division by zero is undefined behavior. For vectors, if any element
of the divisor is zero, the operation has undefined behavior.
See the description of the ``nof`` keyword below for division by zero.

If the ``exact`` keyword is present, the result value of the ``udiv`` is
a :ref:`poison value <poisonvalues>` if %op1 is not a multiple of %op2 (as
such, "((a udiv exact b) mul b) == a").

``nof``stands for "No Overflow". If the ``nof`` keyword is present,
the result is undefined behavior for division by zero.
If the ``nof`` keyword is not present, division by zero results in poison value.
For vectors, if any element of the divisor is zero, the behavior is same as for
scalar division by zero.


'``sdiv``' Instruction
^^^^^^^^^^^^^^^

Syntax:
"""""""

::

       <result> = sdiv <ty> <op1>, <op2>         ;
yields ty:result
       <result> = sdiv exact <ty> <op1>, <op2>   ;
yields ty:result
+       <result> = sdiv nof <ty> <op1>, <op2>   ; yields
ty:result

Overview
"""""""""

The '``sdiv``' instruction returns the quotient of its two operands.

Arguments:
""""""""""

The two arguments to the '``sdiv``' instruction must be
:ref:`integer <t_integer>` or :ref:`vector <t_vector>` of integer
values. Both
arguments must have identical types.

Semantics:
""""""""""

The value produced is the signed integer quotient of the two operands
rounded towards zero.

Note that signed integer division and unsigned integer division are
distinct operations; for unsigned integer division, use '``udiv``'.

Division by zero is undefined behavior. For vectors, if any element
of the divisor is zero, the operation has undefined behavior.
Overflow also leads to undefined behavior; this is a rare case, but can
occur, for example, by doing a 32-bit division of -2147483648 by -1.
See the description of the ``nof`` keyword below for division by zero and
overflow.


If the ``exact`` keyword is present, the result value of the ``sdiv`` is
a :ref:`poison value <poisonvalues>` if the result would be rounded.

``nof``stands for "No Overflow". If the ``nof`` keyword is present,
the result is undefined behavior if overflow occurs. This may be result of
division by zero or dividing the smallest representable integer of the type by
-1.
If the ``nof`` keyword is not present, the overflow cases described above result
in poison value.
For vectors, if any element of the division causes overflow, the behavior is
same as for scalar division with overflow.


Example:
""""""""

.. code-block:: text

       <result> = sdiv i32 4, %var          ; yields i32:result = 4 / %var


---------------------------------------------------------------------
Intel Israel (74) Limited

This e-mail and any attachments may contain confidential material for
the sole use of the intended recipient(s). Any review or distribution
by others is strictly prohibited. If you are not the intended
recipient, please contact the sender and delete all copies.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20171129/ff8a6343/attachment.html>

Your proposal is essentially to introduce division instructions that cannot 
trigger UB, but return poison instead. On ISAs like x86 that means that 
these instructions have to be lowered with guards around them.
You also propose to change clang to always emit these non-UB-triggering 
instructions.  Is this only for vector operations or also for scalar ones? 
What's the performance impact of all those extra guards?

Also, if your ISA has vector instructions that don't trigger UB on e.g. 
division by zero, why don't you rely on this target-specific information in 
the vectorizer instead?  I mean, you would still need to add the attribute 
you are proposing, but you wouldn't change clang.

Nuno


-----Original Message----- 
From: Agabaria, Mohammed via llvm-dev
Sent: Wednesday, November 29, 2017 9:23 AM
To: llvm-dev at lists.llvm.org
Subject: [llvm-dev] RFC: Adding 'no-overflow' keyword to 
'sdiv'\'udiv'instructions



Introduction:



We would like to add new keyword to 'sdiv'\'udiv' instructions
i.e.
'no-overflow'.

This is the updated solution devised in the discussion: 
http://lists.llvm.org/pipermail/llvm-dev/2017-October/118257.html



The proposed keywords:



    "nof" stands for 'no-overflow'



Syntax:



    <result> = sdiv nof <ty> <op1>, <op2> ; yields
ty:result

    <result> = udiv nof <ty> <op1>, <op2> ; yields
ty:result



Overview:



If the keyword is present, the compiler can assume no zero values in the 
denominator. Moreover, for sdiv the division MIN_INT / -1 is prohibited. 
Otherwise, undefined behavior.



Poison value is returned, in case of division by zero or MIN_INT/-1 if the 
keyword not present.



Motivation:



In the current state if the loop-vectorizer decides that it should vectorize 
a loop which contains a predicated integer division -  it will vectorize the 
loop body and scalarize the predicated division instruction into a sequence 
of branches that guard scalar division operations. In some cases the 
generated code for this will not be very efficient. Speculating the divides 
using current vector sdiv instruction is not an option due to the danger of 
integer divide-by-zero.



There are two ways for ensuring the safety of "vector div under
condition",
One way is to use the same condition as the scalar execution. Current 
serialization approach and previous masked integer div intrinsic proposal 
(http://lists.llvm.org/pipermail/llvm-dev/2017-October/118257.html) follows 
this idea. Second way is to check the actual divisor, regardless of the 
original condition. The 'no-overflow' keyword follows this idea. If the 
original code has possible div-by-zero behavior, for example, the latter 
approach will end up hiding it -- by taking advantage of the undefined 
behavior.



With the addition of 'nof' keyword Clang will lower C\C++ division to
'nof'
div IR since it will keep the same semantics.

In case the vectorizer decided to vectorize one of the predicated div it can 
be done by widening the datatype of the div and the 'nof' keyword will
not
hold anymore (because of the risk that one of the predicated lanes may have 
zero).

Keeping that with the widened datatype will allow codegen to lower that 
instruction as a vector instruction while ensuring lanes that may have zero 
values do not trigger a trap.



Implementation considerations:



Initially all the targets can scalarize vector sdiv\udiv instructions to one 
with 'nof' by using guards for each lane:



%r = sdiv <4 x i32> %a, %b can be lowered to:



(assuimg %a = <i32 %a.0, i32 %a.1, i32 %a.2, i32 %a.3>, %b = <i32 %b.0,
i32
%b.1, i32 %b.2, i32 %b.3> and %r = <i32 %r.0, i32 %r.1, i32 %r.2, i32
%r.3>)



If CheckSafety(%a.0,%b.0):

  %r.0 = sdiv nof i32 %a.0, %b.0

If CheckSafety(%a.1,%b.1):

  %r.1 = sdiv nof i32 %a.1, %b.1

If CheckSafety(%a.2,%b.2):

  %r.2 = sdiv nof i32 %a.2, %b.2

If CheckSafety(%a.3,%b.3):

  %r.3 = sdiv nof i32 %a.3, %b.3



CheckSafety(a,b): (of sdiv)

  b != 0 || (b != -1 && a != MIN_INT)



CheckSafety(a,b): (of udiv)

  b != 0





Changes in LangRef.rst of udiv/sdiv Instructions:

-----------------------------------------------------------



'``udiv``' Instruction

^^^^^^^^^^^^^^^



Syntax:

"""""""



::



       <result> = udiv <ty> <op1>, <op2>         ;
yields ty:result

       <result> = udiv exact <ty> <op1>, <op2>   ;
yields ty:result

+       <result> = udiv nof <ty> <op1>, <op2>   ; yields
ty:result



Overview:

"""""""""



The '``udiv``' instruction returns the quotient of its two operands.



Arguments:

""""""""""



The two arguments to the '``udiv``' instruction must be

:ref:`integer <t_integer>` or :ref:`vector <t_vector>` of integer
values.
Both

arguments must have identical types.



Semantics:

""""""""""



The value produced is the unsigned integer quotient of the two operands.



Note that unsigned integer division and signed integer division are

distinct operations; for signed integer division, use '``sdiv``'.



Division by zero is undefined behavior. For vectors, if any element

of the divisor is zero, the operation has undefined behavior.

See the description of the ``nof`` keyword below for division by zero.



If the ``exact`` keyword is present, the result value of the ``udiv`` is

a :ref:`poison value <poisonvalues>` if %op1 is not a multiple of %op2 (as

such, "((a udiv exact b) mul b) == a").



``nof``stands for “No Overflow”. If the ``nof`` keyword is present, the 
result is undefined behavior for division by zero.

If the ``nof`` keyword is not present, division by zero results in poison 
value.

For vectors, if any element of the divisor is zero, the behavior is same as 
for scalar division by zero.





'``sdiv``' Instruction

^^^^^^^^^^^^^^^



Syntax:

"""""""



::



       <result> = sdiv <ty> <op1>, <op2>         ;
yields ty:result

       <result> = sdiv exact <ty> <op1>, <op2>   ;
yields ty:result

+       <result> = sdiv nof <ty> <op1>, <op2>   ; yields
ty:result



Overview

"""""""""



The '``sdiv``' instruction returns the quotient of its two operands.



Arguments:

""""""""""



The two arguments to the '``sdiv``' instruction must be

:ref:`integer <t_integer>` or :ref:`vector <t_vector>` of integer
values.
Both

arguments must have identical types.



Semantics:

""""""""""



The value produced is the signed integer quotient of the two operands

rounded towards zero.



Note that signed integer division and unsigned integer division are

distinct operations; for unsigned integer division, use '``udiv``'.



Division by zero is undefined behavior. For vectors, if any element

of the divisor is zero, the operation has undefined behavior.

Overflow also leads to undefined behavior; this is a rare case, but can

occur, for example, by doing a 32-bit division of -2147483648 by -1.

See the description of the ``nof`` keyword below for division by zero and 
overflow.





If the ``exact`` keyword is present, the result value of the ``sdiv`` is

a :ref:`poison value <poisonvalues>` if the result would be rounded.



``nof``stands for “No Overflow”. If the ``nof`` keyword is present, the 
result is undefined behavior if overflow occurs. This may be result of 
division by zero or dividing the smallest representable integer of the type 
by -1.

If the ``nof`` keyword is not present, the overflow cases described above 
result in poison value.

For vectors, if any element of the division causes overflow, the behavior is 
same as for scalar division with overflow.





Example:

""""""""



.. code-block:: text



       <result> = sdiv i32 4, %var          ; yields i32:result = 4 / %var







---------------------------------------------------------------------
Intel Israel (74) Limited

This e-mail and any attachments may contain confidential material for
the sole use of the intended recipient(s). Any review or distribution
by others is strictly prohibited. If you are not the intended
recipient, please contact the sender and delete all copies.





_______________________________________________
LLVM Developers mailing list
llvm-dev at lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

On 12/03/2017 06:57 AM, Nuno Lopes via llvm-dev wrote:
> Your proposal is essentially to introduce division instructions that 
> cannot trigger UB, but return poison instead. On ISAs like x86 that 
> means that these instructions have to be lowered with guards around them.
> You also propose to change clang to always emit these 
> non-UB-triggering instructions.  Is this only for vector operations or 
> also for scalar ones? What's the performance impact of all those extra 
> guards?
Just to comment here, I think this really is worth measuring.  The 
results aren't easy to predict.  Given the optimizer may be able to 
frequently discharge the guard via known-bits or constant-ranges, 
machine-licm can move the divide to the use (thus removing the need for 
the guard), and the vector forms can be done as a ptest/br, the results 
might be nowhere as bad as it might first seem. Particularly not after 
some targeted tuning work.

If someone  wanted to get really fancy, there's also room for implicit 
fault detection and code patching based healing schemes here that I 
don't think have been well explored.  (Or at least, I'm not aware of
it.)
>
> Also, if your ISA has vector instructions that don't trigger UB on 
> e.g. division by zero, why don't you rely on this target-specific 
> information in the vectorizer instead?  I mean, you would still need 
> to add the attribute you are proposing, but you wouldn't change clang.
I thought we generally tried to avoiding emitting target specific 
intrinsics in the vectorizer?
>
> Nuno
>
>
> -----Original Message----- From: Agabaria, Mohammed via llvm-dev
> Sent: Wednesday, November 29, 2017 9:23 AM
> To: llvm-dev at lists.llvm.org
> Subject: [llvm-dev] RFC: Adding 'no-overflow' keyword to 
> 'sdiv'\'udiv'instructions
>
>
>
> Introduction:
>
>
>
> We would like to add new keyword to 'sdiv'\'udiv'
instructions i.e.
> 'no-overflow'.
>
> This is the updated solution devised in the discussion: 
> http://lists.llvm.org/pipermail/llvm-dev/2017-October/118257.html
>
>
>
> The proposed keywords:
>
>
>
>    "nof" stands for 'no-overflow'
>
>
>
> Syntax:
>
>
>
>    <result> = sdiv nof <ty> <op1>, <op2> ; yields
ty:result
>
>    <result> = udiv nof <ty> <op1>, <op2> ; yields
ty:result
>
>
>
> Overview:
>
>
>
> If the keyword is present, the compiler can assume no zero values in 
> the denominator. Moreover, for sdiv the division MIN_INT / -1 is 
> prohibited. Otherwise, undefined behavior.
>
>
>
> Poison value is returned, in case of division by zero or MIN_INT/-1 if 
> the keyword not present.
>
>
>
> Motivation:
>
>
>
> In the current state if the loop-vectorizer decides that it should 
> vectorize a loop which contains a predicated integer division - it 
> will vectorize the loop body and scalarize the predicated division 
> instruction into a sequence of branches that guard scalar division 
> operations. In some cases the generated code for this will not be very 
> efficient. Speculating the divides using current vector sdiv 
> instruction is not an option due to the danger of integer divide-by-zero.
>
>
>
> There are two ways for ensuring the safety of "vector div under 
> condition", One way is to use the same condition as the scalar 
> execution. Current serialization approach and previous masked integer 
> div intrinsic proposal 
> (http://lists.llvm.org/pipermail/llvm-dev/2017-October/118257.html) 
> follows this idea. Second way is to check the actual divisor, 
> regardless of the original condition. The 'no-overflow' keyword 
> follows this idea. If the original code has possible div-by-zero 
> behavior, for example, the latter approach will end up hiding it -- by 
> taking advantage of the undefined behavior.
>
>
>
> With the addition of 'nof' keyword Clang will lower C\C++ division
to
> 'nof' div IR since it will keep the same semantics.
>
> In case the vectorizer decided to vectorize one of the predicated div 
> it can be done by widening the datatype of the div and the 'nof' 
> keyword will not hold anymore (because of the risk that one of the 
> predicated lanes may have zero).
>
> Keeping that with the widened datatype will allow codegen to lower 
> that instruction as a vector instruction while ensuring lanes that may 
> have zero values do not trigger a trap.
>
>
>
> Implementation considerations:
>
>
>
> Initially all the targets can scalarize vector sdiv\udiv instructions 
> to one with 'nof' by using guards for each lane:
>
>
>
> %r = sdiv <4 x i32> %a, %b can be lowered to:
>
>
>
> (assuimg %a = <i32 %a.0, i32 %a.1, i32 %a.2, i32 %a.3>, %b = <i32 
> %b.0, i32 %b.1, i32 %b.2, i32 %b.3> and %r = <i32 %r.0, i32 %r.1, i32
> %r.2, i32 %r.3>)
>
>
>
> If CheckSafety(%a.0,%b.0):
>
>  %r.0 = sdiv nof i32 %a.0, %b.0
>
> If CheckSafety(%a.1,%b.1):
>
>  %r.1 = sdiv nof i32 %a.1, %b.1
>
> If CheckSafety(%a.2,%b.2):
>
>  %r.2 = sdiv nof i32 %a.2, %b.2
>
> If CheckSafety(%a.3,%b.3):
>
>  %r.3 = sdiv nof i32 %a.3, %b.3
>
>
>
> CheckSafety(a,b): (of sdiv)
>
>  b != 0 || (b != -1 && a != MIN_INT)
>
>
>
> CheckSafety(a,b): (of udiv)
>
>  b != 0
>
>
>
>
>
> Changes in LangRef.rst of udiv/sdiv Instructions:
>
> -----------------------------------------------------------
>
>
>
> '``udiv``' Instruction
>
> ^^^^^^^^^^^^^^^
>
>
>
> Syntax:
>
> """""""
>
>
>
> ::
>
>
>
>       <result> = udiv <ty> <op1>, <op2>         ;
yields ty:result
>
>       <result> = udiv exact <ty> <op1>, <op2>   ;
yields ty:result
>
> +       <result> = udiv nof <ty> <op1>, <op2>   ;
yields ty:result
>
>
>
> Overview:
>
> """""""""
>
>
>
> The '``udiv``' instruction returns the quotient of its two
operands.
>
>
>
> Arguments:
>
> """"""""""
>
>
>
> The two arguments to the '``udiv``' instruction must be
>
> :ref:`integer <t_integer>` or :ref:`vector <t_vector>` of
integer
> values. Both
>
> arguments must have identical types.
>
>
>
> Semantics:
>
> """"""""""
>
>
>
> The value produced is the unsigned integer quotient of the two operands.
>
>
>
> Note that unsigned integer division and signed integer division are
>
> distinct operations; for signed integer division, use '``sdiv``'.
>
>
>
> Division by zero is undefined behavior. For vectors, if any element
>
> of the divisor is zero, the operation has undefined behavior.
>
> See the description of the ``nof`` keyword below for division by zero.
>
>
>
> If the ``exact`` keyword is present, the result value of the ``udiv`` is
>
> a :ref:`poison value <poisonvalues>` if %op1 is not a multiple of
%op2
> (as
>
> such, "((a udiv exact b) mul b) == a").
>
>
>
> ``nof``stands for “No Overflow”. If the ``nof`` keyword is present, 
> the result is undefined behavior for division by zero.
>
> If the ``nof`` keyword is not present, division by zero results in 
> poison value.
>
> For vectors, if any element of the divisor is zero, the behavior is 
> same as for scalar division by zero.
>
>
>
>
>
> '``sdiv``' Instruction
>
> ^^^^^^^^^^^^^^^
>
>
>
> Syntax:
>
> """""""
>
>
>
> ::
>
>
>
>       <result> = sdiv <ty> <op1>, <op2>         ;
yields ty:result
>
>       <result> = sdiv exact <ty> <op1>, <op2>   ;
yields ty:result
>
> +       <result> = sdiv nof <ty> <op1>, <op2>   ;
yields ty:result
>
>
>
> Overview
>
> """""""""
>
>
>
> The '``sdiv``' instruction returns the quotient of its two
operands.
>
>
>
> Arguments:
>
> """"""""""
>
>
>
> The two arguments to the '``sdiv``' instruction must be
>
> :ref:`integer <t_integer>` or :ref:`vector <t_vector>` of
integer
> values. Both
>
> arguments must have identical types.
>
>
>
> Semantics:
>
> """"""""""
>
>
>
> The value produced is the signed integer quotient of the two operands
>
> rounded towards zero.
>
>
>
> Note that signed integer division and unsigned integer division are
>
> distinct operations; for unsigned integer division, use '``udiv``'.
>
>
>
> Division by zero is undefined behavior. For vectors, if any element
>
> of the divisor is zero, the operation has undefined behavior.
>
> Overflow also leads to undefined behavior; this is a rare case, but can
>
> occur, for example, by doing a 32-bit division of -2147483648 by -1.
>
> See the description of the ``nof`` keyword below for division by zero 
> and overflow.
>
>
>
>
>
> If the ``exact`` keyword is present, the result value of the ``sdiv`` is
>
> a :ref:`poison value <poisonvalues>` if the result would be rounded.
>
>
>
> ``nof``stands for “No Overflow”. If the ``nof`` keyword is present, 
> the result is undefined behavior if overflow occurs. This may be 
> result of division by zero or dividing the smallest representable 
> integer of the type by -1.
>
> If the ``nof`` keyword is not present, the overflow cases described 
> above result in poison value.
>
> For vectors, if any element of the division causes overflow, the 
> behavior is same as for scalar division with overflow.
>
>
>
>
>
> Example:
>
> """"""""
>
>
>
> .. code-block:: text
>
>
>
>       <result> = sdiv i32 4, %var          ; yields i32:result = 4 /
%var
>
>
>
>
>
>
>
> ---------------------------------------------------------------------
> Intel Israel (74) Limited
>
> This e-mail and any attachments may contain confidential material for
> the sole use of the intended recipient(s). Any review or distribution
> by others is strictly prohibited. If you are not the intended
> recipient, please contact the sender and delete all copies.
>
>
>
>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

>Your proposal is essentially to introduce division instructions that cannot
trigger UB, but return poison instead. On ISAs like x86 that means that these
instructions have to be >lowered with guards around them.
We return a poison value when this flag is not present. And yes in X86 we can
simulate this by having a guard around div instruction (to make sure no trap can
be raised) but there is another way to implement that using fp div in x86 once
it becomes profitable.
>You also propose to change clang to always emit these non-UB-triggering
instructions.
Clang behavior should be the same like the current behavior which means
undefined behavior in case of divide-by-zero/overflow (currently this raise a
trap on X86) so to keep this behavior clang should generate div instruction with
the flag set by default (i.e. div nof ...).
> Is this only for vector operations or also for scalar ones? 
>What's the performance impact of all those extra guards?
The keyword is for both scalar and vector div instructions.
Of course these guards may hit the performance but this will allow the compiler
to hoist\speculate div instructions which can be profitable in case of
vectorization in some cases for example.
> Also, if your ISA has vector instructions that don't trigger UB on e.g.
>division by zero, why don't you rely on this target-specific information
in the vectorizer instead?  I mean, you would still need to add the attribute
you are proposing, but you wouldn't change clang.
I am not sure that I got your point here, but we need this in order to know that
the code may have div-by-zero which didn't come from the original code
(speculation) so once the vectorizer tries to
Widen predicated div instruction it should delete the 'nof' flag if
exist. Each target should choose how to lower this instruction and generating
this widened div still will be controlled by the vectorizer cost-model.

-----Original Message-----
From: Nuno Lopes [mailto:nunoplopes at sapo.pt] 
Sent: Sunday, December 03, 2017 16:57
To: Agabaria, Mohammed <mohammed.agabaria at intel.com>; llvm-dev at
lists.llvm.org
Subject: Re: [llvm-dev] RFC: Adding 'no-overflow' keyword to
'sdiv'\'udiv'instructions

Your proposal is essentially to introduce division instructions that cannot
trigger UB, but return poison instead. On ISAs like x86 that means that these
instructions have to be lowered with guards around them.
You also propose to change clang to always emit these non-UB-triggering
instructions.  Is this only for vector operations or also for scalar ones?
What's the performance impact of all those extra guards?

Also, if your ISA has vector instructions that don't trigger UB on e.g. 
division by zero, why don't you rely on this target-specific information in
the vectorizer instead?  I mean, you would still need to add the attribute you
are proposing, but you wouldn't change clang.

Nuno


-----Original Message-----
From: Agabaria, Mohammed via llvm-dev
Sent: Wednesday, November 29, 2017 9:23 AM
To: llvm-dev at lists.llvm.org
Subject: [llvm-dev] RFC: Adding 'no-overflow' keyword to
'sdiv'\'udiv'instructions



Introduction:



We would like to add new keyword to 'sdiv'\'udiv' instructions
i.e.
'no-overflow'.

This is the updated solution devised in the discussion: 
http://lists.llvm.org/pipermail/llvm-dev/2017-October/118257.html



The proposed keywords:



    "nof" stands for 'no-overflow'



Syntax:



    <result> = sdiv nof <ty> <op1>, <op2> ; yields
ty:result

    <result> = udiv nof <ty> <op1>, <op2> ; yields
ty:result



Overview:



If the keyword is present, the compiler can assume no zero values in the
denominator. Moreover, for sdiv the division MIN_INT / -1 is prohibited.
Otherwise, undefined behavior.



Poison value is returned, in case of division by zero or MIN_INT/-1 if the 
keyword not present.



Motivation:



In the current state if the loop-vectorizer decides that it should vectorize 
a loop which contains a predicated integer division -  it will vectorize the 
loop body and scalarize the predicated division instruction into a sequence 
of branches that guard scalar division operations. In some cases the 
generated code for this will not be very efficient. Speculating the divides 
using current vector sdiv instruction is not an option due to the danger of 
integer divide-by-zero.



There are two ways for ensuring the safety of "vector div under
condition",
One way is to use the same condition as the scalar execution. Current 
serialization approach and previous masked integer div intrinsic proposal 
(http://lists.llvm.org/pipermail/llvm-dev/2017-October/118257.html) follows 
this idea. Second way is to check the actual divisor, regardless of the 
original condition. The 'no-overflow' keyword follows this idea. If the 
original code has possible div-by-zero behavior, for example, the latter 
approach will end up hiding it -- by taking advantage of the undefined 
behavior.



With the addition of 'nof' keyword Clang will lower C\C++ division to
'nof'
div IR since it will keep the same semantics.

In case the vectorizer decided to vectorize one of the predicated div it can 
be done by widening the datatype of the div and the 'nof' keyword will
not
hold anymore (because of the risk that one of the predicated lanes may have 
zero).

Keeping that with the widened datatype will allow codegen to lower that 
instruction as a vector instruction while ensuring lanes that may have zero 
values do not trigger a trap.



Implementation considerations:



Initially all the targets can scalarize vector sdiv\udiv instructions to one 
with 'nof' by using guards for each lane:



%r = sdiv <4 x i32> %a, %b can be lowered to:



(assuimg %a = <i32 %a.0, i32 %a.1, i32 %a.2, i32 %a.3>, %b = <i32 %b.0,
i32
%b.1, i32 %b.2, i32 %b.3> and %r = <i32 %r.0, i32 %r.1, i32 %r.2, i32
%r.3>)



If CheckSafety(%a.0,%b.0):

  %r.0 = sdiv nof i32 %a.0, %b.0

If CheckSafety(%a.1,%b.1):

  %r.1 = sdiv nof i32 %a.1, %b.1

If CheckSafety(%a.2,%b.2):

  %r.2 = sdiv nof i32 %a.2, %b.2

If CheckSafety(%a.3,%b.3):

  %r.3 = sdiv nof i32 %a.3, %b.3



CheckSafety(a,b): (of sdiv)

  b != 0 || (b != -1 && a != MIN_INT)



CheckSafety(a,b): (of udiv)

  b != 0





Changes in LangRef.rst of udiv/sdiv Instructions:

-----------------------------------------------------------



'``udiv``' Instruction

^^^^^^^^^^^^^^^



Syntax:

"""""""



::



       <result> = udiv <ty> <op1>, <op2>         ;
yields ty:result

       <result> = udiv exact <ty> <op1>, <op2>   ;
yields ty:result

+       <result> = udiv nof <ty> <op1>, <op2>   ; yields
ty:result



Overview:

"""""""""



The '``udiv``' instruction returns the quotient of its two operands.



Arguments:

""""""""""



The two arguments to the '``udiv``' instruction must be

:ref:`integer <t_integer>` or :ref:`vector <t_vector>` of integer
values.
Both

arguments must have identical types.



Semantics:

""""""""""



The value produced is the unsigned integer quotient of the two operands.



Note that unsigned integer division and signed integer division are

distinct operations; for signed integer division, use '``sdiv``'.



Division by zero is undefined behavior. For vectors, if any element

of the divisor is zero, the operation has undefined behavior.

See the description of the ``nof`` keyword below for division by zero.



If the ``exact`` keyword is present, the result value of the ``udiv`` is

a :ref:`poison value <poisonvalues>` if %op1 is not a multiple of %op2 (as

such, "((a udiv exact b) mul b) == a").



``nof``stands for “No Overflow”. If the ``nof`` keyword is present, the 
result is undefined behavior for division by zero.

If the ``nof`` keyword is not present, division by zero results in poison 
value.

For vectors, if any element of the divisor is zero, the behavior is same as 
for scalar division by zero.





'``sdiv``' Instruction

^^^^^^^^^^^^^^^



Syntax:

"""""""



::



       <result> = sdiv <ty> <op1>, <op2>         ;
yields ty:result

       <result> = sdiv exact <ty> <op1>, <op2>   ;
yields ty:result

+       <result> = sdiv nof <ty> <op1>, <op2>   ; yields
ty:result



Overview

"""""""""



The '``sdiv``' instruction returns the quotient of its two operands.



Arguments:

""""""""""



The two arguments to the '``sdiv``' instruction must be

:ref:`integer <t_integer>` or :ref:`vector <t_vector>` of integer
values.
Both

arguments must have identical types.



Semantics:

""""""""""



The value produced is the signed integer quotient of the two operands

rounded towards zero.



Note that signed integer division and unsigned integer division are

distinct operations; for unsigned integer division, use '``udiv``'.



Division by zero is undefined behavior. For vectors, if any element

of the divisor is zero, the operation has undefined behavior.

Overflow also leads to undefined behavior; this is a rare case, but can

occur, for example, by doing a 32-bit division of -2147483648 by -1.

See the description of the ``nof`` keyword below for division by zero and 
overflow.





If the ``exact`` keyword is present, the result value of the ``sdiv`` is

a :ref:`poison value <poisonvalues>` if the result would be rounded.



``nof``stands for “No Overflow”. If the ``nof`` keyword is present, the 
result is undefined behavior if overflow occurs. This may be result of 
division by zero or dividing the smallest representable integer of the type 
by -1.

If the ``nof`` keyword is not present, the overflow cases described above 
result in poison value.

For vectors, if any element of the division causes overflow, the behavior is 
same as for scalar division with overflow.





Example:

""""""""



.. code-block:: text



       <result> = sdiv i32 4, %var          ; yields i32:result = 4 / %var







---------------------------------------------------------------------
Intel Israel (74) Limited

This e-mail and any attachments may contain confidential material for
the sole use of the intended recipient(s). Any review or distribution
by others is strictly prohibited. If you are not the intended
recipient, please contact the sender and delete all copies.





_______________________________________________
LLVM Developers mailing list
llvm-dev at lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev 

---------------------------------------------------------------------
Intel Israel (74) Limited

This e-mail and any attachments may contain confidential material for
the sole use of the intended recipient(s). Any review or distribution
by others is strictly prohibited. If you are not the intended
recipient, please contact the sender and delete all copies.