Sign in Join

Live chat for Free Pascal, Lazarus, Delphi and every Pascal programmer.

Mailing lists / fpc-devel / 2020-05

Different versions of register name search algorithms used

3 messages · 2 people · –

Reply by email Subscribe to this list Your subscription

Read-only archive. Use j and k to move between messages.

Christo Crause

While trying to understand bug 0037121I noticed that the predominant search algorithm used for finding register names is a binary search without a match check. My understanding of this algorithm is that it will always run the maximum iterations for the search space before terminating. To understand how this is supposed to work I looked at other target implementations. I realized that this algorithm is used in all but 2 cases: x86 (in itx86int.pas) which uses (what I consider to be) a conventional binary search, and mips which uses a linear search.

I don't see a need to have different algorithms for performing what appears to be the same function (search for a string in a sorted list of strings), is this correct?

Then, I don't understand why the general search algorithm isn't the one in itx86int.pas. Is there a compelling reason for preferring the 1st algorithm over the conventional binary search?

Thirdly, each target has its own implementation of findreg_by_XXXname, is there a reason not to have a single search function shared by all targets? This may require some renaming of current variable lists such as gas_regname_index and int_regname_index etc. to a common convention.

Your thoughts on these questions would be appreciated.

Christo

Reply by email

Sven Barth
to Christo Crause
Christo Crause wrote 24 lines
While trying to understand bug 0037121I noticed that the predominant search algorithm used for finding register names is a binary search without a match check.  My understanding of this algorithm is that it will always run the maximum iterations for the search space before terminating.  To understand how this is supposed to work I looked at other target implementations.  I realized that this algorithm is used in all but 2 cases: x86 (in itx86int.pas) which uses (what I consider to be) a conventional binary search, and mips which uses a linear search. I don't see a need to have different algorithms for performing what appears to be the same function (search for a string in a sorted list of strings), is this correct? Then, I don't understand why the general search algorithm isn't the one in itx86int.pas.  Is there a compelling reason for preferring the 1st algorithm over the conventional binary search? Thirdly, each target has its own implementation of findreg_by_XXXname, is there a reason not to have a single search function shared by all targets?  This may require some renaming of current variable lists such as gas_regname_index and int_regname_index etc. to a common convention. Your thoughts on these questions would be appreciated.

There is a general implementation of the search algorithm in rgbase which is already used for example by x86/itcpugas.pas as well as z80/cpubase.pas. So in my opinion the way to go would be to switch the other targets (as well as x86/itx86int.pas) to use this as well.

Regards,
Sven

Reply by email

Christo Crause
to Sven Barth
PM Sven Barth wrote 5 lines
There is a general implementation of the search algorithm in rgbase which is already used for example by x86/itcpugas.pas as well as z80/cpubase.pas. So in my opinion the way to go would be to switch the other targets (as well as x86/itx86int.pas) to use this as well.

Thanks for the suggestion Sven. I've changed the patch for xtensa to call the rgbase search method (issue 0037121). If this patch gets accepted I'll do the same for other targets.

Reply by email