Can FPC optimize: if (s[i]='a') or ...

classic Classic list List threaded Threaded
10 messages Options
Reply | Threaded
Open this post in threaded view
|

Can FPC optimize: if (s[i]='a') or ...

AlexeyT
E.g. i have a loop which test each s[i] char for several cases: 'a',
'b', 'c'.

for i:= 1 to length(s) do

if (s[i]='a') or (s[i]='b') or (s[i]='c') then ...

Can FPC optimize it so it only reads s[i] once (to register), not 3 times?

--
Regards,
Alexey

_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: Can FPC optimize: if (s[i]='a') or ...

Ralf Quint
On 4/13/2019 12:30 PM, Alexey Tor. wrote:

> E.g. i have a loop which test each s[i] char for several cases: 'a',
> 'b', 'c'.
>
> for i:= 1 to length(s) do
>
> if (s[i]='a') or (s[i]='b') or (s[i]='c') then ...
>
> Can FPC optimize it so it only reads s[i] once (to register), not 3
> times?
>
How about writing it in Pascal, something like

if s[i] in ['a'..'c'] then

or in case of no-sequential characters/values

if s[i] in ['a', 'b', 'c'] then...


Ralf


---
This email has been checked for viruses by Avast antivirus software.
https://www.avast.com/antivirus

_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: Can FPC optimize: if (s[i]='a') or ...

Rainer Stratmann
In reply to this post by AlexeyT
On Samstag, 13. April 2019 22:30:55 CEST Alexey Tor. wrote:
> E.g. i have a loop which test each s[i] char for several cases: 'a',
> 'b', 'c'.
>
> for i:= 1 to length(s) do
>
> if (s[i]='a') or (s[i]='b') or (s[i]='c') then ...
>
> Can FPC optimize it so it only reads s[i] once (to register), not 3 times?

You can optimise by yourself.

var
 c : char;
 l : longint;

begin
 l := length( s );
 for i := 1 to l do
  c := s[ i ];
  if ( c = 'a' ) or ( c = 'b' ) or ( c = 'c' ) then ...

_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: Can FPC optimize: if (s[i]='a') or ...

Bernd Oppolzer
In reply to this post by Ralf Quint
Am 13.04.2019 um 21:55 schrieb Ralf Quint:

> On 4/13/2019 12:30 PM, Alexey Tor. wrote:
>> E.g. i have a loop which test each s[i] char for several cases: 'a',
>> 'b', 'c'.
>>
>> for i:= 1 to length(s) do
>>
>> if (s[i]='a') or (s[i]='b') or (s[i]='c') then ...
>>
>> Can FPC optimize it so it only reads s[i] once (to register), not 3
>> times?
>>
> How about writing it in Pascal, something like
>
> if s[i] in ['a'..'c'] then
>
> or in case of no-sequential characters/values
>
> if s[i] in ['a', 'b', 'c'] then...
>
>
> Ralf
>

I'd like to second that ... the benefit that the optimizer may get
when IN is used ...

I would like to show you what my New Stanford Pascal compiler does;
it does not eliminate the common expressions s[i], but evaluates
them 3 times, given the original coding. But when the IN expression is used
(this coding: if s[i] in ['a', 'b', 'c'] then...)
it does a very good job. Because the three constants in the set are a
close range without holes in it, it checks in fact the range.

This is how it looks in IBM 370 ASSEMBLY language:

@@ 01AE:       SR    3,3      -- clear register 3
@@ 01B0:       IC    3,404(13,2)      -- insert character s[i] into
register 3 (register 2 has index i, 404/13 is the address of s)
@@ 01B4:       AH    3,=H'-97'      -- subtract constant 'a' - should be
EBCDIC 'a', but is ASCII 'a', because I tested on the PC :-)
@@ 01B8:       CL    3,=F'2'      -- check, if register 3 is between 0 and 2
@@ 01BC:       BC    2,L12      -- branch, if not

This is the result after the second step of the translation;
the first step is the translation to P-Code. The P-Code looks like this
(the Index I is on top of the stack at the beginning, the address of
S at the second position):

      01AE:           DEC  I,1      -- dec top of stack
      01AE:           IXA  1      -- use top of stack as index for
address at second position
      01AE:           IND  C,0      -- replace top of stack (= address)
with content of type char
      01AE:           ORD      -- convert to integer (does nothing)
      01B4:           LCA  S,C32'abc'      -- load character set constant
      01B4:           SLD  32,432      -- convert to binary set
representation
      01B4:           INN      -- implement IN on elements on stack
      01BC:           FJP  L12      -- jump false

On the IBM mainframe, this P-Code is translated to what you see above.
On the other platforms (Windows, Linux, ...), the P-Code is interpreted -
a version of the compiler which generates native code on these platforms
has still to be done. But anyway: the language is fully portable, the
results
are the same. (The P-Code is portable, the 370 implementation is of course
NOT portable - hence the problem when testing the 370 translation on the
PC).

The optimization (implementing IN as a range check in this case) is
in fact done in stage 2, that is: in the P-Code to 370 translator.
The credits for this very fine compiler technology (which is about
40 years old) does not belong to me, but to many other people who
worked on this in the 1975 to 1990 era. I only did some extensions
to it in the last few years and ported the compiler to Windows and
Linux etc.

More information:

http://bernd-oppolzer.de/job9.htm
https://www.facebook.com/StanfordPascal

Kind regards

Bernd


_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: Can FPC optimize: if (s[i]='a') or ...

wkitty42
In reply to this post by Rainer Stratmann
On 4/14/19 7:28 AM, Rainer Stratmann wrote:

> On Samstag, 13. April 2019 22:30:55 CEST Alexey Tor. wrote:
>> E.g. i have a loop which test each s[i] char for several cases: 'a',
>> 'b', 'c'.
>>
>> for i:= 1 to length(s) do
>>
>> if (s[i]='a') or (s[i]='b') or (s[i]='c') then ...
>>
>> Can FPC optimize it so it only reads s[i] once (to register), not 3 times?
>
> You can optimise by yourself.
>
> var
>   c : char;
>   l : longint;
>
> begin
>   l := length( s );
>   for i := 1 to l do
>    c := s[ i ];
>    if ( c = 'a' ) or ( c = 'b' ) or ( c = 'c' ) then ...


this looks like it will read three times like the original instead of once like
using the IN set operation... it is still stepping through each one of the
comparison steps instead of just doing a set match...


--
  NOTE: No off-list assistance is given without prior approval.
        *Please keep mailing list traffic on the list unless*
        *a signed and pre-paid contract is in effect with us.*
_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: Can FPC optimize: if (s[i]='a') or ...

Bernd Oppolzer
Am 15.04.2019 um 03:35 schrieb [hidden email]:

> On 4/14/19 7:28 AM, Rainer Stratmann wrote:
>> On Samstag, 13. April 2019 22:30:55 CEST Alexey Tor. wrote:
>>> E.g. i have a loop which test each s[i] char for several cases: 'a',
>>> 'b', 'c'.
>>>
>>> for i:= 1 to length(s) do
>>>
>>> if (s[i]='a') or (s[i]='b') or (s[i]='c') then ...
>>>
>>> Can FPC optimize it so it only reads s[i] once (to register), not 3
>>> times?
>>
>> You can optimise by yourself.
>>
>> var
>>   c : char;
>>   l : longint;
>>
>> begin
>>   l := length( s );
>>   for i := 1 to l do
>>    c := s[ i ];
>>    if ( c = 'a' ) or ( c = 'b' ) or ( c = 'c' ) then ...
>
>
> this looks like it will read three times like the original instead of
> once like using the IN set operation... it is still stepping through
> each one of the comparison steps instead of just doing a set match...
>
>

True for New Stanford Pascal:

      23       1N   1)    for I := 1 to LENGTH ( S ) do
      24       2N   1)      begin
      25       2N   1)        C := S [ I ] ;
      26       2N   1)        if ( C = 'a' ) or ( C = 'b' ) or ( C = 'c'
) then
      27       2N   1)          WRITELN ( I , '-tes Zeichen ist a, b
oder c' ) ;
      28       2N   1)      end (* for *)

Lines without @@ = P-Code
Lines with @@ = IBM 370 Machine Code (Assembler notation)
as documented by Stage 2 (PASCAL2.PAS) when the A+ switch is set

-------------------- LOC  26 --------------------------------
      0250:           LOD  C,1,424
      0250:           LDC  C,'a'
      0250:           EQU  C
@@ 0250:       CLI   424(13),97  --- compare storage location with 'a'
      0254:           LOD  C,1,424
@@ 0254:       LA    2,1
@@ 0258:       BC    8,*+6
@@ 025C:       SR    2,2
      025E:           LDC  C,'b'
      025E:           EQU  C
@@ 025E:       CLI   424(13),98  --- compare storage location with 'b'
      0262:           IOR  B
@@ 0262:       LA    3,1
@@ 0266:       BC    8,*+6
@@ 026A:       SR    3,3
@@ 026C:       OR    2,3
      026E:           LOD  C,1,424
      026E:           LDC  C,'c'
      026E:           EQU  C
@@ 026E:       CLI   424(13),99  --- compare storage location with 'c'
      0272:           IOR  B
@@ 0272:       LA    3,1
@@ 0276:       BC    8,*+6
@@ 027A:       SR    3,3
@@ 027C:       OR    2,3
      027E:           FJP  L16
@@ 027E:       BC    8,L16


_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: Can FPC optimize: if (s[i]='a') or ...

Tomas Hajny-2
On Mon, April 15, 2019 07:52, Bernd Oppolzer wrote:
 .
 .
>>> On Samstag, 13. April 2019 22:30:55 CEST Alexey Tor. wrote:
 .
 .
>>>> Can FPC optimize it so it only reads s[i] once (to register), not 3
>>>> times?
 .
 .
> True for New Stanford Pascal:
 .
 .

I fail to see how is this related to FPC or the question of the original
poster (who was explicitly asking about FPC). Could we stay on topic,
please?

Tomas
(one of FPC mailing list moderators)


_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: Can FPC optimize: if (s[i]='a') or ...

Bernd Oppolzer
Am 15.04.2019 um 08:29 schrieb Tomas Hajny:

> On Mon, April 15, 2019 07:52, Bernd Oppolzer wrote:
>   .
>   .
>>>> On Samstag, 13. April 2019 22:30:55 CEST Alexey Tor. wrote:
>   .
>   .
>>>>> Can FPC optimize it so it only reads s[i] once (to register), not 3
>>>>> times?
>   .
>   .
>> True for New Stanford Pascal:
>   .
>   .
>
> I fail to see how is this related to FPC or the question of the original
> poster (who was explicitly asking about FPC). Could we stay on topic,
> please?
>
> Tomas
> (one of FPC mailing list moderators)


well, I was hoping for an answer out of the FPC community
what FPC does to the different codings, so that the users can
get some guidelines out of it (for example: common subexpressions
in locigal expressions are not eliminated, so it is better to use the IN
syntax -
or maybe the other way round). My mails were meant to motivate this :-)

but so far only suggestions how to optimize at the source code level.

(and of course: because FPC is sort of inspiration for my work,
I would like to see what FPC does in this cases and to compare it
with what I have)

Sorry about that ...

Best regards

Bernd


_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: Can FPC optimize: if (s[i]='a') or ...

Free Pascal - General mailing list
Am 15.04.2019 um 09:06 schrieb Bernd Oppolzer:

> Am 15.04.2019 um 08:29 schrieb Tomas Hajny:
>> On Mon, April 15, 2019 07:52, Bernd Oppolzer wrote:
>>   .
>>   .
>>>>> On Samstag, 13. April 2019 22:30:55 CEST Alexey Tor. wrote:
>>   .
>>   .
>>>>>> Can FPC optimize it so it only reads s[i] once (to register), not 3
>>>>>> times?
>>   .
>>   .
>>> True for New Stanford Pascal:
>>   .
>>   .
>>
>> I fail to see how is this related to FPC or the question of the original
>> poster (who was explicitly asking about FPC). Could we stay on topic,
>> please?
>>
>> Tomas
>> (one of FPC mailing list moderators)
>
>
> well, I was hoping for an answer out of the FPC community
> what FPC does to the different codings, so that the users can
> get some guidelines out of it (for example: common subexpressions
> in locigal expressions are not eliminated, so it is better to use the
> IN syntax -
> or maybe the other way round). My mails were meant to motivate this :-)
>
> but so far only suggestions how to optimize at the source code level.
>
> (and of course: because FPC is sort of inspiration for my work,
> I would like to see what FPC does in this cases and to compare it
> with what I have)
>
> Sorry about that ...
And you can't just test yourself? After all FPC is free and provides a
"-al" option that keeps the assembly code around...

Anyway, take this code:

=== code begin ===

var
   c: Char;
begin
   c := 'A';
   if (c = 'a') or (c = 'b') or (c = 'c') then
     c := 'B';
   if c in ['a', 'b', 'c'] then
     c := 'B';
   if c in ['a', 'g', 'l'] then
     c := 'B';
end.

=== code end ===

The result on x86_64 with -O- will be this:

=== code begin ===

# [9] c := 'A';
     movb    $65,U_$P$TMW_$$_C(%rip)
# [10] if (c = 'a') or (c = 'b') or (c = 'c') then
     cmpb    $97,U_$P$TMW_$$_C(%rip)
     je    .Lj3
     jmp    .Lj4
.Lj4:
     cmpb    $98,U_$P$TMW_$$_C(%rip)
     je    .Lj3
     jmp    .Lj5
.Lj5:
     cmpb    $99,U_$P$TMW_$$_C(%rip)
     je    .Lj3
     jmp    .Lj6
.Lj3:
# [11] c := 'B';
     movb    $66,U_$P$TMW_$$_C(%rip)
.Lj6:
# [12] if c in ['a', 'b', 'c'] then
     movzbl    U_$P$TMW_$$_C(%rip),%eax
     subl    $97,%eax
     cmpl    $3,%eax
     jb    .Lj7
.Lj7:
     jc    .Lj8
     jmp    .Lj9
.Lj8:
# [13] c := 'B';
     movb    $66,U_$P$TMW_$$_C(%rip)
.Lj9:
# [14] if c in ['a', 'g', 'l'] then
     movzbl    U_$P$TMW_$$_C(%rip),%eax
     cmpl    $97,%eax
     je    .Lj10
     cmpl    $103,%eax
     je    .Lj10
     cmpl    $108,%eax
     je    .Lj10
.Lj10:
     je    .Lj11
     jmp    .Lj12
.Lj11:
# [15] c := 'B';
     movb    $66,U_$P$TMW_$$_C(%rip)

=== code end ===

With -O2 it will be this:

=== code begin ===

# Var c located in register dl
# [9] c := 'A';
     movb    $65,%dl
# [10] if (c = 'a') or (c = 'b') or (c = 'c') then
     cmpb    $97,%dl
     je    .Lj3
     cmpb    $98,%dl
     je    .Lj3
     cmpb    $99,%dl
     jne    .Lj6
.Lj3:
# [11] c := 'B';
     movb    $66,%dl
.Lj6:
# [12] if c in ['a', 'b', 'c'] then
     movzbl    %dl,%eax
     subl    $97,%eax
     cmpl    $3,%eax
     jnc    .Lj9
# [13] c := 'B';
     movb    $66,%dl
.Lj9:
# [14] if c in ['a', 'g', 'l'] then
     movzbl    %dl,%eax
     cmpl    $97,%eax
     je    .Lj11
     cmpl    $103,%eax
     je    .Lj11
     cmpl    $108,%eax
     je    .Lj11
     jne    .Lj12
.Lj11:
# [15] c := 'B';
     movb    $66,%dl

=== code end ===

So it optimized the variable access into a register, but the first
if-condition is more like the third if-condition than the second.

Regards,
Sven
_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: Can FPC optimize: if (s[i]='a') or ...

Rainer Stratmann
In reply to this post by wkitty42
On Sonntag, 14. April 2019 21:35:43 CEST [hidden email] wrote:

> On 4/14/19 7:28 AM, Rainer Stratmann wrote:
> > On Samstag, 13. April 2019 22:30:55 CEST Alexey Tor. wrote:
> >> E.g. i have a loop which test each s[i] char for several cases: 'a',
> >> 'b', 'c'.
> >>
> >> for i:= 1 to length(s) do
> >>
> >> if (s[i]='a') or (s[i]='b') or (s[i]='c') then ...
> >>
> >> Can FPC optimize it so it only reads s[i] once (to register), not 3
> >> times?
> >
> > You can optimise by yourself.
> >
> > var
> >
> >   c : char;
> >   l : longint;
> >
> > begin
> >
> >   l := length( s );
> >   for i := 1 to l do
> >  
> >    c := s[ i ];
> >    if ( c = 'a' ) or ( c = 'b' ) or ( c = 'c' ) then ...
>
> this looks like it will read three times like the original instead of once
> like using the IN set operation... it is still stepping through each one of
> the comparison steps instead of just doing a set match...

It is at least better than reading s[ i ] at every compare operation.
Feel free to make more optimizations if there is a chance.
For example the IN operation.

if c in ['a', 'b', 'c'] then ...

You have to know the whole code to decide if it makes sense to drop the var c
completely.
_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal