Recent

Author Topic: Likely incorrect 64bit code generation in FPC v3.0.4  (Read 2857 times)

440bx

  • Hero Member
  • *****
  • Posts: 826
Likely incorrect 64bit code generation in FPC v3.0.4
« on: March 13, 2019, 06:07:23 am »
Hello,

In 64bit, when using a negative integer index to index into an array, the index isn't loaded into a 64bit register, instead it is loaded into a 32bit register which is then later used as a 64bit register in a load effective address instruction.  This causes the integer index to always be used as if it were a positive displacement.

for the line:
Code: Pascal  [Select]
  1.   LineIdxPtr^[RowIdx][I + 1] := LineAreaPtr;
  2.  
in 32bit, FPC generates :
Code: Pascal  [Select]
  1. // (from GDB) - 32bit code generated  (this works)
  2.  
  3. SignExtend.lpr:132                LineIdxPtr^[RowIdx][I + 1] := LineAreaPtr;
  4. 0040198F 8b1520804100             mov    0x418020,%edx
  5. 00401995 a130804100               mov    0x418030,%eax
  6. 0040199A 8b0d40804100             mov    0x418040,%ecx
  7. 004019A0 8d0482                   lea    (%edx,%eax,4),%eax
  8. 004019A3 8b1510804100             mov    0x418010,%edx
  9. 004019A9 891488                   mov    %edx,(%eax,%ecx,4)      

which works correctly because there is no need to sign extend the integer index RowIdx.

in 64bit, FPC generates:
Code: Pascal  [Select]
  1. // (from GDB) - 64bit code generated (this does NOT work)
  2.  
  3. SignExtend.lpr:132                        LineIdxPtr^[RowIdx][I + 1] := LineAreaPtr;
  4. 0000000100001B02 488b0517e50100           mov    0x1e517(%rip),%rax        # 0x100020020
  5. 0000000100001B09 8b1521e50100             mov    0x1e521(%rip),%edx        # 0x100020030
  6. 0000000100001B0F 48630d2ae50100           movslq 0x1e52a(%rip),%rcx        # 0x100020040
  7. 0000000100001B16 488d04d0                 lea    (%rax,%rdx,8),%rax
  8. 0000000100001B1A 488b15efe40100           mov    0x1e4ef(%rip),%rdx        # 0x100020010
  9. 0000000100001B21 488914c8                 mov    %rdx,(%rax,%rcx,8)
  10.  
in that sequence of code, RowIdx is being loaded into edx, instead of rdx with sign extension.  This causes the instruction
Code: Pascal  [Select]
  1. 0000000100001B16 488d04d0                 lea    (%rax,%rdx,8),%rax
to compute an address which is incorrect.

The attached program works when compiled for 32bit but causes an access violation when compiled for 64bit.

Changing the line
Code: Pascal  [Select]
  1.   LineIdxPtr^[RowIdx][I + 1] := LineAreaPtr;
  2.  
to include a typecast to ptrint or int64:
Code: Pascal  [Select]
  1.   LineIdxPtr^[ptrint(RowIdx)][I + 1] := LineAreaPtr;
  2.  
causes the correct code to be generated.

Just in case, I thought I'd wait for comments before reporting this on Mantis.







using FPC v3.0.4 and Lazarus 1.8.2 on Windows 7 64bit.

Jonas Maebe

  • Hero Member
  • *****
  • Posts: 635
Re: Likely incorrect 64bit code generation in FPC v3.0.4
« Reply #1 on: March 13, 2019, 09:00:40 am »
The reason the compiler uses a load without sign extension is that your arrays are declared as having only valid unsigned index types (0..0 and 1..1). I know this is a common way to declare variable sized arrays, but it's still hack and these statements are all invalid (they cause range errors, which means the result is undefined).

The correct way to declare such arrays is to either declare them as array[low(ptrint) div sizeof(elementsize)..high(ptrint) div sizeof(elementsize)], or to use a pointer type to the element size (you can index pointer types like arrays both in FPC and in Delphi).

440bx

  • Hero Member
  • *****
  • Posts: 826
Re: Likely incorrect 64bit code generation in FPC v3.0.4
« Reply #2 on: March 13, 2019, 09:06:37 am »
The reason the compiler uses a load without sign extension is that your arrays are declared as having only valid unsigned index types (0..0 and 1..1). I know this is a common way to declare variable sized arrays, but it's still hack and these statements are all invalid (they cause range errors, which means the result is undefined).

The correct way to declare such arrays is to either declare them as array[low(ptrint) div sizeof(elementsize)..high(ptrint) div sizeof(elementsize)], or to use a pointer type to the element size (you can index pointer types like arrays both in FPC and in Delphi).
I don't buy that explanation but, leaving that aside.  The fact that the code behaves differently when compiled for 32bit than in 64bit is clearly a problem.   The result should _not_ depend on the bitness.  Either there is a bug when compiling for 64bit or there is a bug when compiling for 32bit.  You choose.

using FPC v3.0.4 and Lazarus 1.8.2 on Windows 7 64bit.

PascalDragon

  • Sr. Member
  • ****
  • Posts: 348
  • Compiler Developer
Re: Likely incorrect 64bit code generation in FPC v3.0.4
« Reply #3 on: March 13, 2019, 10:05:04 am »
No, it's not a problem, because as Jonas said you've entered the realm of undefined behaviour and it's nowhere written that this undefined behaviour needs to be the same on all platforms.

440bx

  • Hero Member
  • *****
  • Posts: 826
Re: Likely incorrect 64bit code generation in FPC v3.0.4
« Reply #4 on: March 13, 2019, 11:00:51 am »
No, it's not a problem, because as Jonas said you've entered the realm of undefined behaviour and it's nowhere written that this undefined behaviour needs to be the same on all platforms.
RowIdx is an integer.  Specifically, a 32bit integer.  If it is going to be moved into a 64bit register then it _must_ be sign extended.  Anything else is incorrect and cannot be justified.

It is not reasonable to claim that is some kind of "undefined behavior".

That is a bug, a nasty one at that, because the result depends on the target bitness. 



« Last Edit: March 13, 2019, 11:12:30 am by 440bx »
using FPC v3.0.4 and Lazarus 1.8.2 on Windows 7 64bit.

BeniBela

  • Hero Member
  • *****
  • Posts: 678
    • homepage
Re: Likely incorrect 64bit code generation in FPC v3.0.4
« Reply #5 on: March 13, 2019, 12:38:24 pm »
Undefined behaviour? In Pascal??  :o So all the crap is copied from C, and the useful things are left off

440bx

  • Hero Member
  • *****
  • Posts: 826
Re: Likely incorrect 64bit code generation in FPC v3.0.4
« Reply #6 on: March 13, 2019, 12:54:13 pm »
Undefined behaviour? In Pascal??  :o So all the crap is copied from C, and the useful things are left off

In Pascal "undefined behavior" is now even better than in C, C++ and any other language.
Code: Pascal  [Select]
  1. var
  2.   Index32 : int32 = -1;
  3.   Index64 : int64 = -1;
  4. ...
  5. ...
  6. AnArray[Index32] <> AnArray[Index64];
That really takes "undefined behavior" to a new level.   
using FPC v3.0.4 and Lazarus 1.8.2 on Windows 7 64bit.

JernejL

  • New member
  • *
  • Posts: 49
Re: Likely incorrect 64bit code generation in FPC v3.0.4
« Reply #7 on: March 13, 2019, 02:47:51 pm »
For some reason i find this last example absolutely hilarious :) i love it when logic and common sense falls apart.
 
I do think that this should be consistient behavior - and work same on all 64 and 32 bit platforms, at minimum, if this should not be fixed for some reason - this warrants at least a compiler warning that the result is undefined and that either array should be made start with negative range low, or that index variable should be of typecasted to correct (unsigned) type, as such code could be strangely failing on 64 bit platforms and give people porting issues.
 

Thaddy

  • Hero Member
  • *****
  • Posts: 7963
Re: Likely incorrect 64bit code generation in FPC v3.0.4
« Reply #8 on: March 13, 2019, 03:33:25 pm »
Undefined behaviour? In Pascal??  :o So all the crap is copied from C, and the useful things are left off

In Pascal "undefined behavior" is now even better than in C, C++ and any other language.
Code: Pascal  [Select]
  1. var
  2.   Index32 : int32 = -1;
  3.   Index64 : int64 = -1;
  4. ...
  5. ...
  6. AnArray[Index32] <> AnArray[Index64];
That really takes "undefined behavior" to a new level.
Think hex, ffíng idiot. $FFFFFFFFFFFFFFFF<> $FFFFFFFF, of course. In any pattern it is undefined
Also in the GNU compiler suite and -let me guess - Visual studio.
You can add more f's to taste....
$FFFFFFFFFFFFFFFF<> $00000000FFFFFFFF in a well behaved compiler, which al three are...
« Last Edit: March 13, 2019, 03:41:16 pm by Thaddy »
Hamlet 1.4 (nothing wrong with the Danish, btw)

440bx

  • Hero Member
  • *****
  • Posts: 826
Re: Likely incorrect 64bit code generation in FPC v3.0.4
« Reply #9 on: March 13, 2019, 06:53:17 pm »
Think hex, ffíng idiot. $FFFFFFFFFFFFFFFF<> $FFFFFFFF, of course. In any pattern it is undefined
Also in the GNU compiler suite and -let me guess - Visual studio.
You can add more f's to taste....
$FFFFFFFFFFFFFFFF<> $00000000FFFFFFFF in a well behaved compiler, which al three are...
Thaddy, you poor thing, at least try to fake some self control.  I'd ask you to think but, that would really be undefined behavior for you.  Maybe someone close to you can hand hold you to -1 = -1 regardless of how it is represented.  If not, consider applying for government help.

I don't want to traumatize you more than you already are but, Delphi Seattle gives the same result in both, 32 and 64bit.  In your case, it is probably necessary to mention that the result is not the same as FPC's and, that's not all, other compilers, unlike FPC, including C and C++ also produce the same result for 32 and 64bit.  Such a coincidence that time and production tested compilers all have the same "undefined behavior".




using FPC v3.0.4 and Lazarus 1.8.2 on Windows 7 64bit.

Jonas Maebe

  • Hero Member
  • *****
  • Posts: 635
Re: Likely incorrect 64bit code generation in FPC v3.0.4
« Reply #10 on: March 13, 2019, 08:27:41 pm »
No, it's not a problem, because as Jonas said you've entered the realm of undefined behaviour and it's nowhere written that this undefined behaviour needs to be the same on all platforms.
RowIdx is an integer.  Specifically, a 32bit integer.  If it is going to be moved into a 64bit register then it _must_ be sign extended.
When you index an array with any expression, this expression gets type-converted to the range type of the array. This is also the step at which range checking gets performed (if enabled). So what gets loaded in a 64bit registers is not RowIdx, but implicit_cast(RowIdx, array_range_type). And array_range_type cannot have negative values according to its declaration.

Quote
The fact that the code behaves differently when compiled for 32bit than in 64bit is clearly a problem.
The code gets interpreted the same on both platforms by the compiler (index = unsigned). However, because on 32 bit platforms an address register is only 32 bit long, you don't notice a difference there.

In general, when code contains a range error, it can even behave differently when compiled with a different compiler version, with different optimization settings, or for a different architecture (even if it is also 32/64 bit). This is not done "because we can", but simply because compiler uses the type information it got from the program (and that is also the only information it can use). What we could do, is remove the taking into account of the upper/lower bound of subrange types to determine whether a type is signed or not (and always consider them signed unless the upper bound is > high(longint) on 32 bit or > high(int64) on 64 bit -- which may be what Delphi does, and which means the behaviour would still be different on 32 and 64 bit, but in a different way), but that would require a complete audit of places in the compiler that use is_signed() would have to be checked to see whether they need to be changed. E.g. all of the bitpacking code will need to be changed, ssince if you interpret 0..3 as a signed 2-bit type, then 3 will be "sign-extended" to -1 when loaded from a bitpacked location if you just make is_signed() return true for this type. It may also result in additional (unwanted) warnings about mixing signed/unsigned types in expressions.

Finally, as you undoubtedly know, range errors can be caught with {$r+} or by using the -Cr command line option. C and C++ have no concept of range checking (although recent versions of clang are finally introducing some support for it). They don't even have a real concept of arrays. E.g., arrayvar[1] and 1[arrayvar] mean exactly the same in C/C++, because they define arrayvar[arrayindex] as being equivalent to *(arrayvar + arrayindex). If you use the Pascal equivalent of these expressions expression (declare arrayvar as a pointer and use either arrayvar[arrayindex] or (arrayvar + arrayindex)^, you also get that same behaviour.

440bx

  • Hero Member
  • *****
  • Posts: 826
Re: Likely incorrect 64bit code generation in FPC v3.0.4
« Reply #11 on: March 13, 2019, 10:25:42 pm »
@Jonas

The range checking argument you are putting forward, simply does not work and it is not even applicable.   A range checking argument cannot be put forward to justify turning a signed type into an unsigned type.  That is simply incorrect and, the short demo program in this post proves it conclusively.

When you index an array with any expression, this expression gets type-converted to the range type of the array. This is also the step at which range checking gets performed (if enabled). So what gets loaded in a 64bit registers is not RowIdx, but implicit_cast(RowIdx, array_range_type). And array_range_type cannot have negative values according to its declaration.
If FPC was doing range checking the way you describe then it would _not_ compile the example program shown below. (cases 1 and 2.)


The code gets interpreted the same on both platforms by the compiler (index = unsigned). However, because on 32 bit platforms an address register is only 32 bit long, you don't notice a difference there.
That is not a valid argument.  The index variable is a signed integer.  The compiler cannot decide to turn it into an unsigned type because it's being used to access an array which can be indexed with an unsigned type.  If you apply what you are saying then the compiler should not even accept a signed type as an index for such an array.

simply because compiler uses the type information it got from the program (and that is also the only information it can use).
You can't use an argument that the compiler "uses type information it got from the program" when the compiler is dropping the sign of a signed data type.  The compiler has been told the indexing variable is a signed integer, it cannot simply turn that into an unsigned integer behind the programmer's back.  That is incorrect.

Even with range checking enabled, the compiler cannot simply decide to change the data type(s) the programmer declared.   It can give an error, a warning, a hint or whatever but, no compiler can simply choose to turn a signed type into an unsigned type. 

here is a sample program which illustrates some of the problems FPC's incorrect sign extension handling/range checking causes:

Code: Pascal  [Select]
  1. {$APPTYPE CONSOLE}
  2.  
  3. {-----------------------------------------------------------------------------}
  4. { NOTE: this code tested with FPC v3.0.4 and Delphi 10 (Seattle)              }
  5. {-----------------------------------------------------------------------------}
  6.  
  7. program RangeChecks;
  8.  
  9. const
  10.   SPACE = ' ';
  11.  
  12. var
  13.   AnArray : array[0..0] of ansichar;
  14.  
  15.   b       : integer;
  16.   AnInt   : integer;         // 32bit integer
  17.  
  18.   AnInt64 : int64;           // 64bit integer
  19.  
  20. begin
  21.   AnArray[0]  := SPACE;      // no problem here
  22.  
  23.   {$ifdef FPC}
  24.     // -------------------------------------------------------------------------
  25.     // case 1.
  26.     // Delphi emits an error for this expression (as it should)
  27.     // FPC emits a warning but, at least, generates CORRECT code.
  28.  
  29.     AnArray[5]  := SPACE;    // Delphi won't compile this (which is correct)
  30.  
  31.  
  32.     // -------------------------------------------------------------------------
  33.     // case 2.
  34.     // same as above for this case
  35.  
  36.     AnArray[-5] := SPACE;    // nor this but, FPC does. At least, in this case
  37.                              // it generates CORRECT code for it.
  38.   {$endif}
  39.  
  40.   // if FPC did range checking the way it should be done, the above statements
  41.   // would NOT compile.  A warning is not good enough.
  42.   //
  43.   // to FPC's credit, while it compiles those incorrect statements, the code
  44.   // it generates for them is correct. (the compiler did what the programmer
  45.   // told it to do.)
  46.  
  47.   // ---------------------------------------------------------------------------
  48.   // case 3.
  49.   // Delphi emits neither a warning nor an error but, generates correct code.
  50.   // if/when runtime range checking is enabled then the problem will be
  51.   // reported.
  52.  
  53.   // FPC neither emits a warning nor a hint and generates INCORRECT code.
  54.  
  55.   // in this case, range checking should be done at runtime and, only if the
  56.   // programmer requested range checking.
  57.  
  58.   b := 3;
  59.   AnInt := (b * 2) div 3;
  60.  
  61.   AnArray[AnInt] := SPACE;   // FPC generates INCORRECT code (no sign extension)
  62.                              // effectively turning a signed int into an
  63.                              // unsigned int.   That is INCORRECT (64bit) and
  64.                              // cannot be justified with a range-checking
  65.                              // argument.
  66.  
  67.                              // Delphi generates correct code.
  68.  
  69.   // ---------------------------------------------------------------------------
  70.   // case 4
  71.   // same as case 3 but using an int64 instead of an int32
  72.  
  73.   AnInt64 := (b * 2) div 3;  // for this expression FPC generates correct code
  74.   AnArray[AnInt64] := SPACE; // and doesn't complain about it.
  75.  
  76.   // ---------------------------------------------------------------------------
  77.   // CONCLUSION:
  78.  
  79.   // FPC compiles statements that it shouldn't compile (cases 1 and 2)
  80.   // FPC's incorrect handling of sign extension makes
  81.   //
  82.   // AnArray[AnInt] <> AnArray[AnInt64]
  83.   //
  84.   // there is no correct argument that can justify that behavior.
  85.  
  86.  
  87.   writeln('press enter/return to end this program');
  88.   readln;
  89. end.  

I sincerely hope this bug is corrected.  The difference in results between 32bit and 64bit have nothing to do with platform in this case, it has everything to do with the fact that in 64bit, FPC decides to turn a signed type into an unsigned type.

FPC is the only compiler I've run into where the particular type of an integer makes a difference when indexing an array.  For the same ordinal value (in this particular example, obviously limited to the range of an int8), AnArray[int8] should equal AnArray[int16] should equal AnArray[int32] should equal AnArray[int64] and, that has nothing to do with range checking, given the same ordinal value, the result should be the same.

Please, we the users, depend on you guys to fix these bugs.  FPC should do sign extension like every other correct compiler does it.  This FPC bug makes porting C/C++ and Delphi code more difficult, time consuming and riskier than it should be.
« Last Edit: March 13, 2019, 10:28:17 pm by 440bx »
using FPC v3.0.4 and Lazarus 1.8.2 on Windows 7 64bit.

marcov

  • Global Moderator
  • Hero Member
  • *****
  • Posts: 7063
Re: Likely incorrect 64bit code generation in FPC v3.0.4
« Reply #12 on: March 13, 2019, 10:37:27 pm »
@Jonas

The range checking argument you are putting forward, simply does not work and it is not even applicable.   A range checking argument cannot be put forward to justify turning a signed type into an unsigned type. 

He doesn't say that. He says you pass an signed value to a range that is only positive. That should generate a runtime error/exception when range checking is on (and also Delphi does so, e.g. change  b:=3 to b:=-3 and add {$R+} and uses sysutils)

If you turn off range checks, you are in undefined territory, and anything may happen. The exact codegeneration depends on target.



If you

440bx

  • Hero Member
  • *****
  • Posts: 826
Re: Likely incorrect 64bit code generation in FPC v3.0.4
« Reply #13 on: March 13, 2019, 10:59:38 pm »
He doesn't say that. He says you pass an signed value to a range that is only positive. That should generate a runtime error/exception when range checking is on (and also Delphi does so, e.g. change  b:=3 to b:=-3 and add {$R+} and uses sysutils)
He is not saying it as clearly as I have because the range checking argument is obviously not applicable but, it is being used to justify incorrect code generation.

By the way, Delphi does not need range checking enabled to refuse the statements AnArray[5] and AnArray[-5] in the example I provided.   How can range checking be used to justify dropping the sign of a signed data type when it compiles statements where the range is obviously wrong ?, not in a correctly formed argument.

In your own words: when range checking is on , it is totally reasonable and expected to get an error but, not so when range checking is off.  Even when range checking is on, Delphi - nor any other properly functioning compiler - turns a signed type into an unsigned type which is what FPC is doing.

If you turn off range checks, you are in undefined territory, and anything may happen. The exact codegeneration depends on target.
That is not the case at all.  For a value n, whether positive or negative, the memory referenced by array[n] is addressof(array) + (n * sizeof(arrayelement)).  There is no "undefined territory" in any of this. 

The range checking argument is neither here nor there.  FPC is dropping the sign of a signed type.  Even with range checking enabled it should NOT do that.  It could report and error but, only if the programmer enables range checking, not otherwise.


using FPC v3.0.4 and Lazarus 1.8.2 on Windows 7 64bit.

ASBzone

  • Full Member
  • ***
  • Posts: 225
  • Automation leads to relaxation...
    • BrainWaveCC Utilities
Re: Likely incorrect 64bit code generation in FPC v3.0.4
« Reply #14 on: March 13, 2019, 11:05:31 pm »
Question...


Code: Pascal  [Select]
  1.     AnArray[5]  := SPACE;    // Delphi won't compile this (which is correct)
  2.  
  3.     AnArray[-5] := SPACE;    // nor this but, FPC does. At least, in this case
  4.                              // it generates CORRECT code for it.
  5.  
  6.   b := 3;
  7.   AnInt := (b * 2) div 3;
  8.  
  9.   AnArray[AnInt] := SPACE;   // FPC generates INCORRECT code (no sign extension)
  10.  


@440bx

For that construct, why does AnArray[number_index] not work when AnArray[variable_index] does?
-ASB: https://www.BrainWaveCC.com

Lazarus v2.0.3 r61198 / FPC v3.2.0-beta-r42126 (via FpcUpDeluxe) -- Windows 64-bit install w/32-bit cross-compile
Primary System: Windows 10 Pro x64, Version 1903 (Build 18362.116)
Other Systems: Windows 10 Pro x64, Version 1809 or greater