<HTML>
<style> BODY { font-family:Arial, Helvetica, sans-serif;font-size:12px; }</style>Not sure if this was intended for the group mailing list or not, but was only e-mailed to me.<br>
<br>
One quesion though... in your example, what level of your optimisation are you
compiling under? I thought the peephole optimizer already changes things
like "lea (%ecx,%eax),%eax" to "add %ecx,%eax". Nevertheless, my Deep
Optimizer is able to spot the unnecessary assignments to %eax. I did
submit a patch, but because it was a prototype and tied into the post
peephole optimizer, it hasn't received that much attention. It's
something I'm still working on though and something I'd like to submit
as an -O4 option.
<div><br>
</div>Gareth aka Kit<br>
<br>
<span style="font-weight: bold;"> <br>
----- Original Message -----<br>
From: David Pethes public@satd.sk<br>
To: gareth@moreton-family.com<br>
Sent: Tue 04/12/18 19:45<br>
Subject: Fwd: Re: [fpc-devel] Optimization theory<br>
</span>Hi Gareth,
<br>
nice to see that you are still working on compiler improvements. If I
<br>
may, can I ask you to look at the assembly output of this routine (it's
<br>
a link to compiler explorer):
<br>
<br>
<a target="_blank" href="https://godbolt.org/#g:!((g:!((g:!((h:codeEditor,i:(fontScale:0.8957951999999999,j:1,lang:pascal,source:'unit+output%3B%0A%0Ainterface%0A%0Aprocedure+core_4x4(block:+psmallint)%3B%0A%0Aimplementation%0A%0Atype%0A++matrix_t+%3D+array%5B0..3,+0..3%5D+of+smallint%3B+%0A%0Aprocedure+core_4x4(block:+psmallint)%3B%0Avar%0A++m:+matrix_t%3B%0A++e,+f,+g,+h:+array%5B0..3%5D+of+smallint%3B%0A%0Avar%0A++i:+longword%3B%0Abegin%0A++move(block%5E,+m,+16*2)%3B%0A%0A++for+i+:%3D+0+to+3+do+begin%0A++++++e%5Bi%5D+:%3D+m%5Bi%5D%5B0%5D+%2B+m%5Bi%5D%5B3%5D%3B%0A++++++f%5Bi%5D+:%3D+m%5Bi%5D%5B0%5D+-+m%5Bi%5D%5B3%5D%3B%0A++++++g%5Bi%5D+:%3D+m%5Bi%5D%5B1%5D+%2B+m%5Bi%5D%5B2%5D%3B%0A++++++h%5Bi%5D+:%3D+m%5Bi%5D%5B1%5D+-+m%5Bi%5D%5B2%5D%3B%0A++end%3B%0A%0Aend%3B%0A+++++++++%0Aend.%0A'),l:'5',n:'0',o:'Pascal+source+%231',t:'0')),k:51.379872662717624,l:'4',m:100,n:'0',o:'',s:0,t:'0'),(g:!((h:compiler,i:(compiler:fpc304,filters:(b:'0',binary:'1',commentOnly:'0',demangle:'0',directives:'0',execute:'1',intel:'0',trim:'1'),lang:pascal,libs:!(),options:'-O4',source:1),l:'5',n:'0',o:'x86-64+fpc+3.0.4+(Editor+%231,+Compiler+%231)+Pascal',t:'0')),header:(),k:48.6201273372824,l:'4',n:'0',o:'',s:0,t:'0')),l:'2',m:100,n:'0',o:'',t:'0')),version:4"><span style="color: red;">https://godbolt.org/#g:!((g:!((g:!((h:codeEditor,i:(fontScale:0.8957951999999999,j:1,lang:pascal,source:'unit+output%3B%0A%0Ainterface%0A%0Aprocedure+core_4x4(block:+psmallint)%3B%0A%0Aimplementation%0A%0Atype%0A++matrix_t+%3D+array%5B0..3,+0..3%5D+of+smallint%3B+%0A%0Aprocedure+core_4x4(block:+psmallint)%3B%0Avar%0A++m:+matrix_t%3B%0A++e,+f,+g,+h:+array%5B0..3%5D+of+smallint%3B%0A%0Avar%0A++i:+longword%3B%0Abegin%0A++move(block%5E,+m,+16*2)%3B%0A%0A++for+i+:%3D+0+to+3+do+begin%0A++++++e%5Bi%5D+:%3D+m%5Bi%5D%5B0%5D+%2B+m%5Bi%5D%5B3%5D%3B%0A++++++f%5Bi%5D+:%3D+m%5Bi%5D%5B0%5D+-+m%5Bi%5D%5B3%5D%3B%0A++++++g%5Bi%5D+:%3D+m%5Bi%5D%5B1%5D+%2B+m%5Bi%5D%5B2%5D%3B%0A++++++h%5Bi%5D+:%3D+m%5Bi%5D%5B1%5D+-+m%5Bi%5D%5B2%5D%3B%0A++end%3B%0A%0Aend%3B%0A+++++++++%0Aend.%0A'),l:'5',n:'0',o:'Pascal+source+%231',t:'0')),k:51.379872662717624,l:'4',m:100,n:'0',o:'',s:0,t:'0'),(g:!((h:compiler,i:(compiler:fpc304,filters:(b:'0',binary:'1',commentOnly:'0',demangle:'0',directives:'0',execute:'1',intel:'0',trim:'1'),lang:pascal,libs:!(),options:'-O4',source:1),l:'5',n:'0',o:'x86-64+fpc+3.0.4+(Editor+%231,+Compiler+%231)+Pascal',t:'0')),header:(),k:48.6201273372824,l:'4',n:'0',o:'',s:0,t:'0')),l:'2',m:100,n:'0',o:'',t:'0')),version:4</span></a>
<br>
<br>
As you can see, there are a lot of duplicated index/load calculations,
<br>
yet there are only a couple of registers used, so the results could be
<br>
reused. I wonder if this is somehow covered in your optimization passes
<br>
as well, or if you have some idea where would I start if I wanted to
<br>
optimize the code generation for this?
<br>
Thanks again for your efforts,
<br>
<br>
David
<br>
<br>
<br>
<br>
<br>
On 19. 6. 2018 1:51, J. Gareth Moreton wrote:
<br>
<span style="color: rgb(102, 102, 102);">> Hah, thanks. In a strange way, I find it quite fun. The culmination of
</span><br>
<span style="color: rgb(102, 102, 102);">> my efforts has been the first stage of a "Deep Optimizer", which
</span><br>
<span style="color: rgb(102, 102, 102);">> searches around MOV commands to see if it can minimise pipeline stalls
</span><br>
<span style="color: rgb(102, 102, 102);">> and sometimes can remove MOV commands entirely if it determines that the
</span><br>
<span style="color: rgb(102, 102, 102);">> two registers are identical in value at that point.
</span><br>
<span style="color: rgb(102, 102, 102);">>
</span><br>
<span style="color: rgb(102, 102, 102);">> As an example where inlining helped (actually, just copying and pasting
</span><br>
<span style="color: rgb(102, 102, 102);">> the function's contents virtually verbatim because everything was in
</span><br>
<span style="color: rgb(102, 102, 102);">> assembly language) is the new Int and Frac functions on x86-64, where I
</span><br>
<span style="color: rgb(102, 102, 102);">> inserted Int's contents directly into Frac. While Int had a branch and
</span><br>
<span style="color: rgb(102, 102, 102);">> a few safety checks to prevent an integer overflow, it was much faster
</span><br>
<span style="color: rgb(102, 102, 102);">> when inlined compared to fiddling around with register moves and doing a
</span><br>
<span style="color: rgb(102, 102, 102);">> function call, especially as the rest of Frac was very fast already, and
</span><br>
<span style="color: rgb(102, 102, 102);">> it also allowed the entirety of Frac to have no stack frame.
</span><br>
<span style="color: rgb(102, 102, 102);">>
</span><br>
<span style="color: rgb(102, 102, 102);">> It's probably a bit insulting to Free Pascal, but my initial drive was
</span><br>
<span style="color: rgb(102, 102, 102);">> to reduce the size of the compiled binaries, without sacrificing speed.
</span><br>
<span style="color: rgb(102, 102, 102);">> Of course, improving speed is a major focus as well!
</span><br>
<span style="color: rgb(102, 102, 102);">>
</span><br>
<span style="color: rgb(102, 102, 102);">> Gareth
</span><br>
<span style="color: rgb(102, 102, 102);">>
</span><br>
<span style="color: rgb(102, 102, 102);">>
</span><br>
<span style="color: rgb(102, 102, 102);">> On Mon 18/06/18 19:49 , David Pethes <a href="mailto:public@satd.sk">public@satd.sk</a> sent:
</span><br>
<span style="color: rgb(102, 102, 102);">>
</span><br>
<span style="color: rgb(102, 102, 102);">>
</span><br>
<span style="color: rgb(102, 102, 102);">> Hi, one less thing to worry about then :) Unless in a quite tight loop,
</span><br>
<span style="color: rgb(102, 102, 102);">> it shouldn't make much difference - or any at all, due to OoO
</span><br>
<span style="color: rgb(102, 102, 102);">> execution.
</span><br>
<span style="color: rgb(102, 102, 102);">> By the way, this Intel code analyzer could be interesting to you - I
</span><br>
<span style="color: rgb(102, 102, 102);">> only found it recently:
</span><br>
<span style="color: rgb(102, 102, 102);">> <a target="_blank" href="https://software.intel.com/en-us/articles/intel-architecture-code-analyzer/"><span style="color: red;">https://software.intel.com/en-us/articles/intel-architecture-code-analyzer/</span></a>
</span><br>
<span style="color: rgb(102, 102, 102);">>
</span><br>
<span style="color: rgb(102, 102, 102);">>
</span><br>
<span style="color: rgb(102, 102, 102);">> Good luck with you optimizations!
</span><br>
<span style="color: rgb(102, 102, 102);">>
</span><br>
<span style="color: rgb(102, 102, 102);">> David
</span><br>
<span style="color: rgb(102, 102, 102);">>
</span><br>
<span style="color: rgb(102, 102, 102);">>
</span><br>
<span style="color: rgb(102, 102, 102);">> On 17. 6. 2018 19:52, J. Gareth Moreton wrote:
</span><br>
<span style="color: rgb(102, 102, 102);">> > Aah, I was in error. I used agner as my
</span><br>
<span style="color: rgb(102, 102, 102);">> > source, but even that says 5 cycles for a
</span><br>
<span style="color: rgb(102, 102, 102);">> > near call and 17-33 for a far call, so I'm
</span><br>
<span style="color: rgb(102, 102, 102);">> > not sure where I got 50 from. My
</span><br>
<span style="color: rgb(102, 102, 102);">> > apologies. I have probably been avoiding
</span><br>
<span style="color: rgb(102, 102, 102);">> > function calls more than necessary!
</span><br>
<span style="color: rgb(102, 102, 102);">> >
</span><br>
<span style="color: rgb(102, 102, 102);">> > Gareth aka. Kit
</span><br>
<span style="color: rgb(102, 102, 102);">>
</span><br>
<span style="color: rgb(102, 102, 102);">>
</span><br>
<br>
<br>
</HTML>