Hi everyone,

I need to ask a question about how division nodes are set up (I'm looking at possible optimisation techniques).  I've written the following procedure:

procedure DoDivMod(N, D: Integer; out Q, R: Integer);
begin
   Q := N div D;
   R := N mod D;
end;

Fairly simple and to the point.  However, even before the first node pass, the following node tree is generated for an integer division operation:

<statementn pos="24,10">
   <ifn resultdef="$void" pos="24,10" flags="nf_internal">       <condition>
         <equaln resultdef="Boolean" pos="24,10" flags="nf_internal">             <loadn resultdef="LongInt" pos="24,14">                <symbol>D</symbol>
            </loadn>
            <ordconstn resultdef="LongInt" pos="24,10" rangecheck="FALSE">                <value>-1</value>
            </ordconstn>
         </equaln>
      </condition>
      <then>
         <assignn resultdef="$void" pos="24,10" flags="nf_internal">             <temprefn resultdef="LongInt" pos="24,10" flags="nf_write" id="$7C585E10">
               <typedef>LongInt</typedef> <tempflags>ti_may_be_in_reg</tempflags>
               <temptype>tt_persistent</temptype>             </temprefn>
            <unaryminusn resultdef="LongInt" pos="24,10">                <loadn resultdef="LongInt" pos="24,8">                   <symbol>N</symbol>                </loadn>
            </unaryminusn>
         </assignn>
      </then>
      <else>
         <assignn resultdef="$void" pos="24,10" flags="nf_internal">             <temprefn resultdef="LongInt" pos="24,10" flags="nf_write" id="$7C585E10">
               <typedef>LongInt</typedef> <tempflags>ti_may_be_in_reg</tempflags>
               <temptype>tt_persistent</temptype>             </temprefn>
            <divn resultdef="LongInt" pos="24,10">                <loadn resultdef="LongInt" pos="24,8">                   <symbol>N</symbol>                </loadn>
               <loadn resultdef="LongInt" pos="24,14">                   <symbol>D</symbol>                </loadn>
            </divn>
         </assignn>
      </else>
   </ifn>
</statementn>

Something similar is made for "mod" as well.  I have to ask though... is it really necessary to check to see if the divisor is -1 and have a distinct assignment for it?  It's a bit of a rare edge case that usually just slows things down since it tends to add a comparison and a conditional jump to the final assembly language.  Is there some anomalous behaviour to a processor's division routine if the divisor is -1?

At the very least, would it be possible to remove the conditional check when compiling under -Os?

(I intend to see if it's possible to merge "N div D" and "N mod D" on x86, and possibly other processors that have a combined DIV/MOD operator).

Kit

Looks like a rather disadvantageous way to avoid the idiv instruction because x div -1 = -x and x mod -1 = 0.

I ran a quick benchmark doing a lot of integer divisions where sometimes (randomly) the divisor was -1. When the occurence was rare enough (~5%) the performance was not impacted, the higher the occurence of -1 was the slower it became to almost half as fast. Only when less than 5% of the divisors were *not* -1 the performance was better up to twice as fast when all divisors were -1. Of couse ymmv as it depends on the CPU and the branch predictor behavior but it shows that this "optimization" is hardly any good.

I cannot think of a realistic case where 95% of your divisors are -1 and you really need to save those few extra cycles of calling idiv.

It does seem odd.  In a practical sense, the only time I can see -1 being a common input among other random numbers is if it's an error value, in which case you would most likely do special handling rather than pass it through a division operation.  With the slowdown that comes from additional branch prediction, it just seems like unnecessary fluff, but I need to double-check to see if there's a very good reason behind their generation (if it's a platform-specific problem, it should be moved to that platform's specific first pass)  Now I just need to find out where those nodes are generated - they're proving elusive!

Note that using constant divisors uses a different optimisation, so this only applies to variable divisors.

Kit

P.S. I found the code that adds the conditional checks; it's "doremoveinttypeconvs" in the ncnv unit.  However, it's very unclear as to WHY it's doing it as there's no comments around the code block.

Kit

This is the code block in question (ncnv.pas, starting at line 3397) - if anyone can explain why it has to be set up this way, or add comments to the code, I will be most grateful (it's run for the following node types: subn, addn, muln, divn, modn, xorn, andn, orn, shln, shrn):

   exclude(n.flags,nf_internal);
   if not forceunsigned and
      is_signed(n.resultdef) then
     begin
       originaldivtree:=nil;
       if n.nodetype in [divn,modn] then
         originaldivtree:=n.getcopy;
doremoveinttypeconvs(level+1,tbinarynode(n).left,signedtype,false,signedtype,unsignedtype);
doremoveinttypeconvs(level+1,tbinarynode(n).right,signedtype,false,signedtype,unsignedtype);
       n.resultdef:=signedtype;
       if n.nodetype in [divn,modn] then
         begin
           newblock:=internalstatements(newstatements);
tempnode:=ctempcreatenode.create(n.resultdef,n.resultdef.size,tt_persistent,true);
           addstatement(newstatements,tempnode);
           addstatement(newstatements,cifnode.create_internal(
caddnode.create_internal(equaln,tbinarynode(n).right.getcopy,cordconstnode.create(-1,n.resultdef,false)),
               cassignmentnode.create_internal(
                 ctemprefnode.create(tempnode),
cmoddivnode.create(n.nodetype,tbinarynode(originaldivtree).left.getcopy,cordconstnode.create(-1,tbinarynode(originaldivtree).right.resultdef,false))
               ),
               cassignmentnode.create_internal(
                 ctemprefnode.create(tempnode),n
               )
             )
           );
addstatement(newstatements,ctempdeletenode.create_normal_temp(tempnode));
addstatement(newstatements,ctemprefnode.create(tempnode));
           n:=newblock;
           do_typecheckpass(n);
           originaldivtree.free;
         end;
     end

(the new division/modulus by -1 is then converted elsewhere)

Kit

This is the code block in question (ncnv.pas, starting at line 3397)

The git "blame" function shows who last made changes: https://gitlab.com/freepascal.org/fpc/source/-/blame/main/compiler/ncnv.pas?page=4#L3396

Most of that code was added 2 years ago in this commit: https://gitlab.com/freepascal.org/fpc/source/-/commit/ea11517d27fa00f40b626e47213f0caa8832d155

Fair enough, but I would like an explanation as to why it's necessary, because the reason for testing -1 in particular is very unclear, and I wonder if there's a known misbehaviour with a particular division function with -1.

Kit

I made a merge request that removes the comparison against -1. x86_64-win64 and i386-win32 pass without any regressions, so the reason behind the change still eludes me.  Maybe my fix for #39646 removes the need for it?

https://gitlab.com/freepascal.org/fpc/source/-/merge_requests/418

Kit

I didn't see a mention of it in this discussion thread, but dividing the largest negative integer by -1 does cause an overflow error of some sort, because of two's complement.

Just to make sure, do (min_int div -1) and (min_int mod -1) behave the same way before and after this proposed change? And, what min_int is of course depends on whether targeting a 32-bit or 64-bit system, so best check both cases.

~Kirinn

On Mon, 15 May 2023 17:21:30 +0100

Thank you!  I knew it must have been something simple like that!

I just did a quick test with x86 assembly language - this is the code that used to run for dividing min_int by -1:

MOV EAX, $80000000
NEG EAX

EAX contains $80000000 as a result.  When using IDIV:

MOV EAX, $80000000
MOV EDX, $FFFFFFFF // Sign extension
MOV ECX, -1
IDIV ECX

Exception SIGFPE raised.

I understand now.  Thanks for pointing out min_int div -1.  I'll experiment a bit more though to see if generating the setup is necessary in all circumstances (e.g. if an unsigned operand is being expanded into a larger signed value, it isn't necessary). At the very least, I'll add a new test for this and also put a comment in the code so it's clear why -1 needs special treatment (the fact I got no regressions means this very specific set-up is not tested properly).

Kit

FWIW in 3.2.2 I don't see the -1 check and the idiv causes an int overflow exception. But silently returning 0 for min_int div -1 feels very wrong imo.

FWIW in 3.2.2 I don't see the -1 check and the idiv causes an int overflow exception. But silently returning 0 for min_int div -1 feels very wrong IMO.

Pardon, debugger fooled me - I was meant to say "silently returning min_int".

Le 16/05/2023 à 01:47, Stefan Glienke via fpc-devel a écrit :

min_int div -1

"min_int div -1"  should give  "- min_int" ?

Logically yes, but using 16-bit as an example, min_int is -32,768, and signed 16-bit integers range from -32,768 to 32,767. So -32,768 ÷ -1 = 32,768, which is out of range.  This is where the problem lies.

Internally, negation involves inverting all of the bits and then adding 1 (essentially how you subtract a number using two's complement), so min_int, which is 1000000000000000, becomes 0111111111111111 and then, after incrementing, 1000000000000000, which is min_int again.

Kit

So I need to ask... should the check for a divisor of -1 still be performed? The case of doing "min_int div -1", even with unsigned-to-signed typecasting, seems very contrived and the programmer should expect problems if "min_int" and "-1" appear as the operands.  Is there a specific example where this implicit check is absolutely necessary?  As others have pointed out, silently returning "min_int" as the answer seems more unexpected (granted this is just the behaviour of an optimisation that converts the nodes equating to "x div -1" to "-x", and Intel's NEG instruction doesn't return an error if min_int is its input operand, but I can't be sure if the same applies to non-Intel processors and their equivalent instructions).

Kit

J. Gareth Moreton wrote

So I need to ask... should the check for a divisor of -1 still be performed?

Yes. This is the result of "down sizing" a division. In case of

longint(int64 div int64) can be converted only into longint(int64) div longint(int64) if this check is carried out. longint($80000000 div $ffffffff) must silently result in $8000000 in this case.

That's useful to know - thanks Florian.  So it's possible to forego the -1 check if no downsizing occurs.

I suppose it makes sense... if we go by the signed 64-bit equivalents, $FFFFFFFF80000000 div $FFFFFFFFFFFFFFFF = $0000000080000000, which when typecast to a LongInt does result in a signed overflow that isn't checked without -Co, so the answer is $80000000.  On the flip side, $0000000080000000 div $FFFFFFFFFFFFFFFF = $FFFFFFFF80000000, which when typecast to a LongInt is also equal to $80000000, this time without an overflow.  Even though the original operand of $0000000080000000 is out of range for a LongInt, it's perfectly fine as an Int64.

If my logic is correct, the -1 check is not needed in the following conditions:

* The division is being upsized.
* There is no change in size and neither source is unsigned (e.g. Cardinal --> LongInt would require the check).

Currently, as given in my original code example, LongInt(LongInt div LongInt) is given the -1 check (assuming Integer = LongInt), and this just seems like a waste.  Would you approve this change Florian? (I'll also add a comment to explain about the downsizing situation)

Kit

----

Hi Florian,

Can I have a specific code example where this is absolutely necessary, and, if applicable, a target where it's known to cause a problem otherwise?  I've tried to create the example listed in the e-mail with the following:

procedure DoDivMod(N, D: Int64; out Q, R: LongInt); noinline;
begin
   Q := N div D;
   R := N mod D;
end;

I'm testing on x86_64-win64.  In this case, the "expanding to 64-bit" is necessary and so "doremoveinttypeconvs" is never called, thus the condition is not inserted.  The "idiv" operation is 64-bit and the result downsized to 32-bit - this also occurs if I do an explicit typecast on the result:

procedure DoDivMod(N, D: Int64; out Q, R: LongInt); noinline;
begin
   Q := LongInt(N div D);
   R := LongInt(N mod D);
end;

However, if I do an explicit typecast on the operands...

procedure DoDivMod(N, D: Int64; out Q, R: LongInt); noinline;
begin
   Q := LongInt(N) div LongInt(D);
   R := LongInt(N) mod LongInt(D);
end;

... then "doremoveinttypeconvs" is called and the condition inserted.  I would argue here though that typecasting a value to a LongInt, where an output of $80000000 is a real possibility, should raise an exception if you try to divide it by -1 since the programmer is asking to downsize values that could potentially be out of range.

Kit

I just repeated the test on i386-win32 and it's the same thing... with one notable exception:

procedure DoDivMod(N, D: Int64; out Q, R: LongInt); noinline;
begin
   Q := LongInt(N) div LongInt(D);
   R := LongInt(N) mod LongInt(D);
end;

This reduces the operation to 32 bits, but does NOT generate a conditional check for a divisor of -1, so LongInt($0000000080000000) div LongInt(-1) will raise an exception, but won't raise an exception on x86_64-win64, thus behaviour between platforms is different.

Can others confirm this?

Kit