Re: [fpc-devel] Sorting tests
On Thu, 24 Nov 2022 18:51:12 + "J. Gareth Moreton via fpc-devel" wrote: > Hi everyone, > > I just need to touch on the knowledge base. What tests exist that test > the functionality of rtl/inc/sortbase.pp? As Olly suggested, I'm > looking at creating Introsort for this unit as well, but I need to know > if such a unit already exists or if I need to make my own. Some times ago I wrote a couple of merge sort routines to use in BWT, the project never goes further so they remain at level of numerical values input only. They should have a good worst case scenario. In the merge.pas the parameter nrm has to be false when the dimension of the array is not a power of two. There also is a check head-tail of the blocks to move in a single pass the smaller one. The natural.pas is recursive in the initial division in blocks and allow for adaptation for inputs already sorted. If you find them useful, you are free to made anything you want. Marco -- Simplex sigillum veri PROGRAM Sort; CONST len=20; VAR a:ARRAY[0..2*len-1] OF Byte; i,j:Word; src:Boolean; PROCEDURE MergeSort(VAR src:Boolean;nrm:Boolean); VAR dbl,sub,i,j,k,l,m,n,dst,lim:Word; x,y,z:Integer; BEGIN dbl:=len SHL 1; sub:=1; WHILE subdbl THEN l:=dbl; IF m>dbl THEN m:=dbl; IF lim>len THEN lim:=len; END ELSE BEGIN IF l>len THEN l:=len; IF m>len THEN m:=len; IF lim>dbl THEN lim:=dbl; END; x:=l-i; y:=m-j; z:=m-i; END; IF a[l-1]<=a[j] THEN BEGIN IF z>0 THEN Move(a[i],a[dst],z); i:=l; j:=m; dst:=lim; END (* Solo < per avere un metodo stabile *) ELSE IF a[m-1]0 THEN Move(a[j],a[dst],y) ELSE y:=0; IF x>0 THEN Move(a[i],a[dst+y],x); i:=l; j:=m; dst:=lim; END; WHILE dst=m) OR ((iPROGRAM Sort; CONST len=20; VAR a,b:ARRAY[0..len-1] OF Byte; h,t,idx:Word; PROCEDURE NaturalSort(i,j,k:Word;run:Byte); VAR l,m:Word; BEGIN l:=i; m:=j; IF run<>2 THEN BEGIN t:=a[i]; Inc(i); h:=a[i]; WHILE (i<=m) AND (h>=t) DO BEGIN t:=h; Inc(i); h:=a[i]; END; Dec(i); END ELSE i:=k; IF i1 THEN BEGIN h:=a[j]; Dec(j); t:=a[j]; WHILE (j>=l) AND (h>=t) DO BEGIN h:=t; Dec(j); t:=a[j]; END; Inc(j); END ELSE j:=k; IF i-l>=m-j THEN BEGIN k:=i+1; NaturalSort(k,m,j,1); j:=k; END ELSE BEGIN k:=j-1; NaturalSort(l,k,i,2); i:=k; END; END ELSE k:=len; IF ki) OR (a[l]<=a[j]) THEN Inc(l) ELSE BEGIN b[h]:=a[l]; Inc(h); a[l]:=a[j]; Inc(l); Inc(j); END ELSE BEGIN IF l<=i THEN BEGIN b[h]:=a[l]; Inc(h); END; IF (j>m) OR (b[t]<=a[j]) THEN BEGIN a[l]:=b[t]; Inc(l); Inc(t); END ELSE BEGIN a[l]:=a[j]; Inc(l); Inc(j); END; END; END; END; BEGIN Randomize; FOR idx:=0 TO len-1 DO BEGIN a[idx]:=Random(256); Write(' ',a[idx]); END; WriteLn; NaturalSort(0,len-1,len,0); FOR idx:=0 TO len-1 DO Write(' ',a[idx]); END. ___ fpc-devel maillist - fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
Re: [fpc-devel] Prototype optimisation... Sliding Window
On Fri, 25 Feb 2022 05:08:48 + "J. Gareth Moreton via fpc-devel" wrote: > Almost every source file in the compiler and the RTL shows some kind of > improvement. A lot of them are just redundant pointer deallocations, so > this will help with cache misses and the like - that aside though, here > are a couple of my favourites... one from dbgdwarf - > TDebugInfoDwarf.appendsym_fieldvar_with_name_offset: > > Before: > > ... > .Lj682: > leaq (,%r13,8),%rcx > movq 120(%rdi),%rax > cqto > idivq %rcx > imulq %r13,%rax > movq %rax,%r12 > addq 56(%rbp),%r12 > leaq (,%r13,8),%rcx > movq 120(%rdi),%rax > cqto > idivq %rcx > movq %rdx,%rsi > cmpb $0,U_$SYSTEMS_$$_TARGET_INFO+276(%rip) > > After: > > ... > .Lj682: > leaq (,%r13,8),%rcx > movq 120(%rdi),%rax > cqto > idivq %rcx > imulq %r13,%rax > movq %rax,%r12 > addq 56(%rbp),%r12 > movq %rdx,%rsi > cmpb $0,U_$SYSTEMS_$$_TARGET_INFO+276(%rip) > > This one has successfully removed an IDIV instruction because the > algorithm was able to detect that the subroutine wanted the remainder in > %edx, and it was still available from the first IDIV call because it > hadn't been overwritten, and neither %r13 nor %rdi had changed values so > the references are the same. This is very useful, thank you. I think FPC has an excellent register allocator, but frustrated on 32 bit by scarce resources and by the lack of reloading check. -- Simplex sigillum veri ___ fpc-devel maillist - fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
Re: [fpc-devel] Assembler file option (-a)
Il giorno ven, 31/12/2021 alle 17.32 +0200, Christo Crause ha scritto: > On Fri, Dec 31, 2021 at 4:41 PM Marco Borsari via fpc-devel > wrote: > > Hi, > > on Linux with FPC 3.2.2 the executable size of programs compiled > > with > > fpc -On -a (tried with n 2 or 4) > > is smaller than when the assembler files are deleted (-a omitted). > > Does it is an expected behaviour? > > > > > Using any of the -a options (not sure about -a5?) to output assembly > also automatically switches to an external linker (for targets with > internal linkers). Differences in the executables are thus > attributable to differences in generated output between the internal > and external linkers. Thank you for the clarification ___ fpc-devel maillist - fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
[fpc-devel] Assembler file option (-a)
Hi, on Linux with FPC 3.2.2 the executable size of programs compiled with fpc -On -a (tried with n 2 or 4) is smaller than when the assembler files are deleted (-a omitted). Does it is an expected behaviour? ___ fpc-devel maillist - fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
[fpc-devel] CursorOn/Off on Linux
Hi, I have always thought the procedures for the cursor appearance have intentionally left blank on Linux, but it is not so. In packages/rtl-console/src/unix/crt.pp they make use of ttySendStr, investigating a little I found that variables InCnt, InHead, InTail and OutCnt are not initialized, while they should all start at 0. I am not sure that solves the problem, anyway it is an error. Marco Borsari ___ fpc-devel maillist - fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
Re: [fpc-devel] Capturing addresses
Il 10/11/2019 14:36, Jonas Maebe ha scritto: Hi, Does anyone know what the accepted/excepted behaviour is regarding the capture of addresses of var/out/const-by-address/constref parameters? For example: var g: longint; p: plongint; procedure test(var l: longint); begin p:=@l; end; begin test(g); end. The question is: should the compiler by default assume that such addresses are not captured, or that they are captured? Does anyone know if a lot of code exists that does this? To me p:=@l should be simply refused by the compiler as it happens in case of p:=l. Marco ___ fpc-devel maillist - fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
Re: [fpc-devel] Minor debate with ISO standard on case blocks
Il 31/07/2019 08:37, thaddy ha scritto: On 2019-07-31 08:26, Marco Borsari via fpc-devel wrote: What needs to be detected if all *used* labels are within the confines of the used ordinal, but a selector without label should throw an error. In the case of my patch it behaves like extended pascal mode and throws a run-time error in that case. That is debatable in some cases, because if the selector has no label and the compiler can resolve that at compile time it should in my opinion and how I read ISO 10206 throw a compile-time error. See my remarks and test code. Maybe you can evaluate those conclusions I made. I read your code examples and I have to admit I was a little bit confused about the actual discussion: I was concerned only for the situation in which the value of variable does not match the case statement list, irrespectively of the ordinal type of the variable. For the latter I have no idea about what should be desiderable to do nor knowledge about standards. > I just compiled pascal-s (Moore's iso version, because that's the > relevant one) but did not run it yet with my patch. It fails at > run-time or compile-time? > It is an interpreter/p-code system, so has a greater level of freedom. > Note iso7158 is based on Wirth's but Wirth's version is not > iso compliant. For the situation I intended before, it raises an error when it executes the object code, please consider this code fragment of the procedure interpret: 12: begin (* switch *) h1 := s[t].i; t := t-1; h2 := ir.y; h3 := 0; repeat if code[h2].f <> 13 then begin h3 := 1; ps := caschk end else if code[h2].y = h1 then begin h3 := 1; pc := code[h2+1].y end else h2 := h2 + 2 until h3 <> 0 end; ps is set to caschk when all labels are been processed without a match and the processor reaches code 13, i.e. the end of case. I hope to be more near to the point this time, Marco ___ fpc-devel maillist - fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
Re: [fpc-devel] Minor debate with ISO standard on case blocks
On Wed, 31 Jul 2019 01:26:23 +0200 Martok wrote: > Of course, if you wanted a run-time error you would need to insert a run-time > check, and 'some people' seemed to be hell-bent on saving these 2 cycles at > any > cost. > > The patch to switch from option a1) to a2) would be straightforward, fix 32079 > and insert a default otherwise clause that raises a RunError in -Miso. But the > question is again, does Freepascal actually aim to be compliant with anything, > or just have a compatible syntax and do its own thing from there? It seems to me that the problem of a lack of correspondence in a case statement list should be of the same level of attention of the index limits of an array, except there is no memory corruption risk. The solution could be to insert a run time check in presence of the switch {$R+}, if the latter is allowed in iso mode. Greetings, Marco Borsari -- Simplex sigillum veri ___ fpc-devel maillist - fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
Re: [fpc-devel] Minor debate with ISO standard on case blocks
On Tue, 30 Jul 2019 06:38:56 +0200 thaddy wrote: > According to what I found there is no smoking gun: I could not find any > implementation or reference from any reputable source that implements > the case statement in the way that is implemented in trunk: compile time > error when not all of the ordinal range for the case are processed. It > simply does not exist as far as I am concerned, unless someone can > convince be by a reputable source that such implementation exists > elsewhere. Pascal-S of Wirth does it. Marco Borsari -- Simplex sigillum veri ___ fpc-devel maillist - fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
Re: [fpc-devel] Registers reloading
Il 18/07/2019 21:17, J. Gareth Moreton ha scritto: Hi Marco, That is actually one thing I've been researching myself. Currently the peephole optimiser doesn't have the facilities to detect if a register already contains a value that is being assigned to it, something I call the "Deep Optimizer" but is otherwise just basic data flow analysis. Thank you for your interest and your work, greetings Marco Borsari ___ fpc-devel maillist - fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
[fpc-devel] Registers reloading
Hi all, does the compiler have the optimization to avoid reloading into a register of an address (or a value) whether it is already present? I ask this because of this code fragment compiled with the -O4 option: .Lj380: # Register eax allocated # [726] T := T-1; subw$1,2(%ebx) # Register ax released # Register edx allocated # [727] H6 := @STK^[T]; movlU_$GLOBALS_$$_STK,%edx # Register eax allocated movzwl 2(%ebx),%eax leal-8(%edx,%eax,8),%eax # Register edx released movl%eax,-256(%ebp) # [728] H7 := H6; movl%eax,-260(%ebp) <-(1) # Register eax released # [729] Inc(H7, 1); addl$8,-260(%ebp) # Register eax allocated # [730] H6^.I := H6^.I+H7^.I; movl-256(%ebp),%eax <-(2) # Register ecx allocated movswl 4(%eax),%ecx movl-260(%ebp),%eax # Register edx allocated movswl 4(%eax),%edx leal(%ecx,%edx),%eax # Register ecx released movw%ax,%dx movl-256(%ebp),%eax <-(3) movw%dx,4(%eax) # Register eax,dx released In (1) the compiler assumes that eax has the correct address but in (2) does not omit to reload it (eax released too soon). Both seem to be of the same level of the analysis complexity, more deeper should be takes into account of (3) with the use of a supplementar registers as si or di (they are used in other parts of the code). Thank you for any response, Marco Borsari ___ fpc-devel maillist - fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
Re: [fpc-devel] Unexpected behaviour of bit operators
On Fri, 17 May 2019 18:06:13 +0200 Ondrej Pokorny wrote: > On 17.05.2019 10:47, Marco Borsari via fpc-devel wrote: > > Does this is an effect of some multiplication overflow, or is it a bug? > > Both the bit operations and the arithmetic opretaions return integers as > results and not words: > https://www.freepascal.org/docs-html/ref/refsu46.html > https://www.freepascal.org/docs-html/ref/refsu45.html#x148-1712.8.1 > > The c:=... overflows - you get a range check error: > > c:=(a XOR b)*(a SHL 5+b SHR 2); // range check error > > Just add a couple of word() casts where you need the integer-result to > be casted to word: I tested it (the hash is used for a contest selector in a data compressor), but it seems that the results are bit identical with or without the cast. Do you point it out to suppress false positives in a debug phase? Anyway, thank you. -- Simplex sigillum veri ___ fpc-devel maillist - fpc-devel@lists.freepascal.org http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
Re: [fpc-devel] Unexpected behaviour of bit operators
On Fri, 17 May 2019 16:45:52 +0200 gabor wrote: > Can you provide c source code? > I'm not sure about this: > ...(a SHL 5+b SHR 2)... > Maybe it should look like this: > ((a SHL 5+b) SHR 2) > > Regards, Michał. Please look at https://burtleburtle.net/bob/hash/doobs.html for the Rotating Hash, it is 32 bit but I remember there is the 16 bit version even. Correct implementation is the sum (xoring) of two shifted value (be careful that my hash it is intended for string of length 2). -- Simplex sigillum veri ___ fpc-devel maillist - fpc-devel@lists.freepascal.org http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
Re: [fpc-devel] Unexpected behaviour of bit operators
On Fri, 17 May 2019 14:36:52 +0200 Marco Borsari via fpc-devel wrote: > Thank you, your answer make it clear the nature of the problem, i.e. > operation size extension. > Anyway, if I understand correct, the masking as reported in the code > does not operate over the 16 bit limit, so even h2 should be erroneus. Sorry, it operates as $FFF0. Bye, Marco -- Simplex sigillum veri ___ fpc-devel maillist - fpc-devel@lists.freepascal.org http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
Re: [fpc-devel] Unexpected behaviour of bit operators
On Fri, 17 May 2019 11:55:55 +0100 "J. Gareth Moreton" wrote: > On a slightly different note, I would be careful about only using a > 16-bit hash, because the chance of a collision is only about 1 in 320 > (see "Birthday attack") > > Gareth aka. Kit Thank you, but in my use case collisions are accepted: in fact for every a=b the hash collapses into 0. -- Simplex sigillum veri ___ fpc-devel maillist - fpc-devel@lists.freepascal.org http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
Re: [fpc-devel] Unexpected behaviour of bit operators
On Fri, 17 May 2019 11:51:20 +0100 "J. Gareth Moreton" wrote: > One thing to be aware of is that the compiler will extend intermediate > expressions to the CPU size, so if the multiplication overflows into 32 > bits in h1 (which it does for the given values of a and b), it will > preserve those bits and will end up shifting them to the right instead > of zeroes. > > For h2, the overflowed bits are masked out with the "and ((s - 1) shl > (16 - n))" operation, which in this example is equal to $FFF0. > > I hope this answers your question. > > Gareth aka. Kit Thank you, your answer make it clear the nature of the problem, i.e. operation size extension. Anyway, if I understand correct, the masking as reported in the code does not operate over the 16 bit limit, so even h2 should be erroneus. -- Simplex sigillum veri ___ fpc-devel maillist - fpc-devel@lists.freepascal.org http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
[fpc-devel] Unexpected behaviour of bit operators
In the code below program test; const n=12; s=1 shl n; var a,b,c,h1,h2:word; begin a:=77; b:=0; (*c:=(a XOR b)*(a SHL 5+b SHR 2);*) h1:=((a XOR b)*(a SHL 5+b SHR 2)) SHR (16-n); (*h1:=c SHR (16-n);*) h2:=((a XOR b)*(a SHL 5+b SHR 2)) AND ((s-1) SHL (16-n)) SHR (16-n); (*h2:=c AND ((s-1) SHL (16-n)) SHR (16-n);*) writeln(h1,',',h2); end. the results of h1 and h2 (they are hashes) are different, and only h2 appears to be correct and inside the range. If we precompute the hash value with c, then both h1 and h2 are the same. Does this is an effect of some multiplication overflow, or is it a bug? Regards, Marco Borsari -- Simplex sigillum veri ___ fpc-devel maillist - fpc-devel@lists.freepascal.org http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
Re: [fpc-devel] [Patch/RFC] Warnings for (in/over)complete case statements
Il 01/01/2019 22:10, Martok ha scritto: - If a case statement on an ordinal does not contain labels for all values of the ordinal, and no else statement is given, raise a new warning (W6059). This is actually defined as an error in ISO7185 and a dynamic-violation in IEC10206. * in ISO mode, there are 2 solutions: in Standard Pascal, not covering the entire type is a compile-time error. In Extended Pascal, this is a runtime error. Which one is followed usually? If we agree to check it only at runtime, then the error could be raised everytime it is impossible to find a correspondence in the case statement and there is no an else clause, disregarding the completeness of the ordinal list and so including all types. This way the check can be included in the $R switch. Marco ___ fpc-devel maillist - fpc-devel@lists.freepascal.org http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
Re: [fpc-devel] Case code pattern
Il 14/08/2018 12:37, Martok ha scritto: label label0,label1,label2,{...,}afterend; const table: array [lowestcaselabel..highestcaselabel] of CodePointer = (@label0, @label1, @label2{,...}); if (xhighestcaselabel) then goto @afterend; goto table[x]; label0: code; goto afterend; label1: Morecode; goto afterend; label2: EvenMoreCode; {...} afterend: I did not aware about CodePointer type and its use in conjunction with the goto, it is very useful, thank you. But for compatibility with TP, I could need for a plain branch table, I am writing a new mail in the other list... Marco ___ fpc-devel maillist - fpc-devel@lists.freepascal.org http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
Re: [fpc-devel] Case code pattern
Il 14/08/2018 10:00, Martok ha scritto: array of index = array of pointers, sorry ___ fpc-devel maillist - fpc-devel@lists.freepascal.org http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
Re: [fpc-devel] Case code pattern
Il 14/08/2018 10:00, Martok ha scritto: What Kit said, but a correction: the threshold is not 50, it is 19. And what is generated is not technically a jump table, but a typed dispatch table. From what I can read from Wikipedia, every compound of the case is enclosed in a procedure (or in a function, as you said the table is typed), declared with nostackframe, and called by an array of index, right? ___ fpc-devel maillist - fpc-devel@lists.freepascal.org http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
Re: [fpc-devel] Case code pattern
Il 13/08/2018 16:29, J. Gareth Moreton ha scritto: I haven't explored it too deeply myself, but from what I understand, a jump table is only generated if there are a large number of branches (over 50). If it's just a handful of branches, it simply subtracts values from the input corresponding to the differences between the case labels, and jumping to the next subtraction if there's a mismatch, or to the else block if it goes negative. I'm not sure what it does for strings though. Gareth aka. Kit I see, I suspected the existence of a threshold value. I am not interested in strings, thank you, Marco ___ fpc-devel maillist - fpc-devel@lists.freepascal.org http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
[fpc-devel] Case code pattern
Hello, I would need a clarification about the way the case statement is translated into assembler by FPC. When the list of alternatives is continous, does the compiler generate a jump table? And if yes, there is some conditions for which a fall-through is performed anyway? Thank you, Marco Borsari ___ fpc-devel maillist - fpc-devel@lists.freepascal.org http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
Re: [fpc-devel] no rule to make target pass
On Wed, 9 Aug 2017 11:55:44 +0200 (CEST) mar...@stack.nl (Marco van de Voort) wrote: > I hadn't built FPC for a while on this machine, and the error I get this > morning flabbergasts me. (I also get this error when cycling when it should > start building the compiler after the RTL. I cleaned and distcleaned, no > difference) > > C:\repo\fpc\compiler>make > make: *** No rule to make target `Pass', needed by `ppc386.exe'. Stop. > > Any ideas? Some more info: I hope to remember correctly, but when I have this message it is for an insufficient environment/command processor memory. ___ fpc-devel maillist - fpc-devel@lists.freepascal.org http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
[fpc-devel] LineInfo
Does it is possible that the LineInfo trace (-gl option) are broken (no output) in 3.0.2 version on Linux (at least)? -- Marco Borsari___ fpc-devel maillist - fpc-devel@lists.freepascal.org http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel