BorlandTalk.com Borland discussion newsgroups   Archives   FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in to check your private messages   Log in  Superoptimizer          BorlandTalk.com Forum Index -> Delphi Language BASM View previous topic :: View next topic   Author Message Nicholas Sherlock Guest Posted: Fri Jan 27, 2006 6:28 am    Post subject: Superoptimizer Hey all, I'm much of the way through writing a SuperOptimizer in Delphi. A SO writes code by brute force - it finds code to do a job by enumerating and validating all possible combinations of opcodes. My SO currently writes a tiny subset of X86 instructions (AND, OR, XOR, NOT, MOV, ADD, SUB, MUL, CMP, SETcc, CMOVcc). Do any of you have any suggestions for functions that I should test my SuperOptimizer against? It's good for generating code lengths up to about 5 instructions. I've succeeded in generating code for functions like "Return 0", "Return sum of 2 parameters", "Compare two parameters, return 1 if they are equal, otherwise 0", "Compare two parameters, return the first parameter plus 2 if both are equal, otherwise return the first parameter unchanged". Cheers, Nicholas Sherlock Back to top Per Larsen Guest Posted: Fri Jan 27, 2006 11:40 am    Post subject: Re: Superoptimizer "Nicholas Sherlock" <N.sherlock (AT) gmail (DOT) com> wrote Quote: I'm much of the way through writing a SuperOptimizer in Delphi. A SO writes code by brute force - it finds code to do a job by enumerating and validating all possible combinations of opcodes. My SO currently writes a tiny subset of X86 instructions (AND, OR, XOR, NOT, MOV, ADD, SUB, MUL, CMP, SETcc, CMOVcc). Very cool Quote: Do any of you have any suggestions for functions that I should test my SuperOptimizer against? Well, obvious candidates would be attempts at creating branchless functions that compare two arguments and return -1, 0, 1 for less, equal, greater. I have one somewhere (though I can't actually locate it right now) for signed 32-bit integers, which uses only the optimized RISC-type instructions (no SETcc, CMOVcc, etc) - supposedly written by an SO. It's very efficient. I would like to see as many such functions as possible for scalar argument types. Will you be making your tool available to the public at some point? It doesn't necessarily have to be in source form - I have a couple of experimental compilers here, and I might use such a tool for improving their code-gen. - Per Back to top Nicholas Sherlock Guest Posted: Sat Jan 28, 2006 4:13 am    Post subject: Re: Superoptimizer Per Larsen wrote: Quote: "Nicholas Sherlock" <N.sherlock (AT) gmail (DOT) com> wrote Do any of you have any suggestions for functions that I should test my SuperOptimizer against? Well, obvious candidates would be attempts at creating branchless functions that compare two arguments and return -1, 0, 1 for less, equal, greater An excellent target! My computer is busy keeping my room warm working on it right now. After testing 7.5 billion routines (And keeping my CPU at 75 degrees celcius), it has decided that it can't manage it in 4 instructions, so it's moving on to 5. Do you know how many instructions your routine uses? Anything exotic that I should add to my supported instruction set? Quote: Will you be making your tool available to the public at some point? It doesn't necessarily have to be in source form - I have a couple of experimental compilers here, and I might use such a tool for improving their code-gen. Sounds like an excellent idea. I'll put some thought into how that could be arranged and eventually post back with details... Cheers, Nicholas Sherlock Back to top Thorsten Engler [NexusDB] Guest Posted: Sat Jan 28, 2006 9:56 am    Post subject: Re: Superoptimizer Quote: An excellent target! My computer is busy keeping my room warm working on it right now. After testing 7.5 billion routines (And keeping my CPU at 75 degrees celcius), it has decided that it can't manage it in 4 instructions, so it's moving on to 5. Do you know how many instructions your routine uses? Anything exotic that I should add to my supported instruction set? I've seen that code somewhere... I think it made use of th carry flag... so SBC / ADC would be good candidates to add. Cheers, Thorsten Back to top John O'Harrow Guest Posted: Sat Jan 28, 2006 12:58 pm    Post subject: Re: Superoptimizer "Nicholas Sherlock" <N.sherlock (AT) gmail (DOT) com> wrote Quote: An excellent target! My computer is busy keeping my room warm working on it right now. After testing 7.5 billion routines (And keeping my CPU at 75 degrees celcius), it has decided that it can't manage it in 4 instructions, so it's moving on to 5. Do you know how many instructions your routine uses? Anything exotic that I should add to my supported instruction set? The following (untested) code should perform the comparison and return -1, 0 or +1 function Compare(A, B: Integer): Integer; asm mov ecx, 1 sub eax, edx cdq cmovg eax, ecx or eax, edx end; -- regards, John The Fastcode Project: http://www.fastcodeproject.org/ Back to top Per Larsen Guest Posted: Sat Jan 28, 2006 4:38 pm    Post subject: Re: Superoptimizer "John O'Harrow" <john (AT) elmcrest (DOT) demon.co.uk> wrote Quote: The following (untested) code should perform the comparison and return -1, 0 or +1 function Compare(A, B: Integer): Integer; asm mov ecx, 1 sub eax, edx cdq cmovg eax, ecx or eax, edx end; Okay, you made me go look for it some more :) Here it is: function Compare(A, B: Integer): Integer; asm sub eax,edx cdq neg eax adc edx, edx mov eax, edx end; - Per Back to top Nicholas Sherlock Guest Posted: Sun Jan 29, 2006 1:15 am    Post subject: Re: Superoptimizer Per Larsen wrote: Quote: Here it is: function Compare(A, B: Integer): Integer; asm sub eax,edx cdq neg eax adc edx, edx mov eax, edx end; Argh... I spent ages trying to work out why my SO wouldn't validate this sequence (Wrote a little "debugger" in the process, and compared it with Delphi's CPU view for the same routine). Finally tracked it down to, wait for it... The sub instruction: fRegs[i^.operands[0].location] := op1 + op2; Yes, a plus sign, sigh. This is a great project for learning assembler, I've never even written something as complex as a loop in assembly language, now I can learn simple things by example! My SO generates this solution, 1 instruction shorter: function mycompare(a,b:integer):integer; asm SUB EAX, EDX CDQ SUB EDX, EAX ADC EAX, EDX end; Is this a better solution to the problem? Cheers, Nicholas Sherlock Back to top Avatar Zondertau Guest Posted: Sun Jan 29, 2006 8:30 am    Post subject: Re: Superoptimizer Quote: My SO generates this solution, 1 instruction shorter: function mycompare(a,b:integer):integer; asm SUB EAX, EDX CDQ SUB EDX, EAX ADC EAX, EDX end; Is this a better solution to the problem? It is not a valid solution. Try the code below: mycompare(-2, High(Integer)) Since -2 < High(Integer) it should return -1, but it returns 1. The same goes for Per's version BTW. JOH's version returns a large positive number in this case (probably somewhere near $7FFFFFFF), which is even more wrong. -- The Fastcode Project: http://www.fastcodeproject.org/ Back to top Avatar Zondertau Guest Posted: Sun Jan 29, 2006 8:43 am    Post subject: Re: Superoptimizer Quote: It is not a valid solution. Try the code below: mycompare(-2, High(Integer)) Since -2 < High(Integer) it should return -1, but it returns 1. The same goes for Per's version BTW. JOH's version returns a large positive number in this case (probably somewhere near $7FFFFFFF), which is even more wrong. It may be somewhat lame, but this branchless implementation does seem to work: function CompareInt(A, B: LongInt): LongInt; register; asm mov ecx, -1 sub eax, edx mov edx, 1 cmovl eax, ecx cmovg eax, edx end; It is most likely not optimal though. -- The Fastcode Project: http://www.fastcodeproject.org/ Back to top Per Larsen Guest Posted: Sun Jan 29, 2006 11:40 am    Post subject: Re: Superoptimizer "Avatar Zondertau" wrote Quote: It is not a valid solution. Try the code below: mycompare(-2, High(Integer)) Since -2 < High(Integer) it should return -1, but it returns 1. The same goes for Per's version BTW. Oh my! You're right - it has issues with extreme values (where a-b over/underflows). That's no good. Fortunately, I don't believe I ever put this in production anywhere. - Per Back to top Ain Valtin Guest Posted: Fri Feb 03, 2006 7:00 pm    Post subject: Re: Superoptimizer On Sun, 29 Jan 2006 09:43:56 +0100, "Avatar Zondertau" <avatarzt (AT) gmail (DOT) com (please reply to newsgroup)> wrote: Quote: It may be somewhat lame, but this branchless implementation does seem to work: function CompareInt(A, B: LongInt): LongInt; register; asm mov ecx, -1 sub eax, edx mov edx, 1 cmovl eax, ecx cmovg eax, edx end; I would have a use for such a function but it has to be method, ie right now I use function TObjektiKuuGraafik.CompareNodes(const AKey1, AKey2: Integer): Integer; begin if(AKey1 = AKey2)then Result:= 0 else if(AKey1 > AKey2)then Result:= 1 else Result:= -1; end; How would your solution look like if it is method? This method is called many times in my code, so any optimization would be welcome... Quote: It is most likely not optimal though. Nicholas, how your superoptimizer is progressing? <g> TIA ain Back to top John Herbster Guest Posted: Fri Feb 03, 2006 7:22 pm    Post subject: Re: Superoptimizer "Ain Valtin" wrote Quote: I would have a use for such a function but it has to be method, ie right now I use Why? Quote: function TObjektiKuuGraafik.CompareNodes (const AKey1, AKey2: Integer): Integer; begin if(AKey1 = AKey2)then Result:= 0 else if(AKey1 > AKey2)then Result:= 1 else Result:= -1; end; I do not see anything in your method that would depend on anything else in the object! Regards, JohnH Back to top Avatar Zondertau Guest Posted: Fri Feb 03, 2006 8:56 pm    Post subject: Re: Superoptimizer Quote: It may be somewhat lame, but this branchless implementation does seem to work: function CompareInt(A, B: LongInt): LongInt; register; asm mov ecx, -1 sub eax, edx mov edx, 1 cmovl eax, ecx cmovg eax, edx end; I would have a use for such a function but it has to be method, ie right now I use That would make it something like this: function TMyObject.CompareInt(A, B: LongInt): LongInt; register; asm xchg eax, edx mov edx, -1 sub eax, ecx mov ecx, 1 cmovl eax, edx cmovg eax, ecx end; Note that if only the sign of the result matters (which is often the case) this might work as well (untested): function TMyObject.CompareInt(A, B: LongInt): LongInt; register; asm mov eax, edx sub eax, ecx jo @Overflow ret @Overflow: neg eax end; This function uses a branch, but in practical situations it will be predicted correctly every time. You should test to see if it really is faster. -- The Fastcode Project: http://www.fastcodeproject.org/ Back to top Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First         BorlandTalk.com Forum Index -> Delphi Language BASM All times are GMT Page 1 of 1   Jump to: Select a forum C++ Builder Newsgroups----------------C++ BuilderC++ Builder (ActiveX)C++ Builder (Announcements)C++ Builder (Command Line Tools)C++ Builder DatabasesC++ Builder Databases (ADO)C++ Builder Databases (Desktop)C++ Builder Databases (InterBase Express)C++ Builder Databases (Multi-Tier)C++ Builder Databases (SQL Servers)C++ Builder (Graphics)C++ Builder (IDE)C++ Builder (Internet)C++ Builder (Internet Socket)C++ Builder (Internet Web)C++ Builder (Jobs)C++ Builder (Language)C++ Builder (Language C++)C++ Builder (Compatibility with MFC)C++ Builder (Native API)C++ Builder (Non-Technical)C++ Builder (Students)C++ Builder (Third Party Tools)C++ Builder (Upgrade)C++ Builder (VCL)C++ Builder (VCL Components Usage)C++ Builder (VCL Components Development)C++ Builder (VCL Usage)C++ Builder (WinAPI)C++ Builder Installation Delphi Newsgroups----------------Delphi (General)Delphi ActiveX Controls UsageDelphi ActiveX Controls DevelopmentDelphi As400Delphi DatabasesDelphi Databases (ADO)Delphi Databases (dbExpress)Delphi Databases (Desktop)Delphi Databases (InterBase Express)Delphi Databases (Multi-Tier)Delphi Databases (SQL Servers)Delphi DeploymentDelphi GraphicsDelphi IDEDelphi InternationalizationDelphi InternetDelphi Internet Isapi-WebBrokerDelphi Internet WebSnapDelphi Internet WinsockDelphi JobsDelphi Language BASMDelphi Language ObjectPascalDelphi Model Driven Architecture (General)Delphi Model Driven Architecture (Third Party)Delphi MultimediaDelphi Native APIDelphi Non-TechnicalDelphi ObjectPascalDelphi OLE AutomationDelphi OO designDelphi OpenToolsAPIDelphi Reporting-ChartingDelphi RTLDelphi StudentsDelphi TeamSourceDelphi Thirdparty ToolsDelphi Thirdparty Tools (General)Delphi Thirdparty Tools (IntraWeb)Delphi Thirdparty Tools (RaveReports)Delphi UpgradeDelphi VCLDelphi VCL ComponentsDelphi VCL Components UsingDelphi VCL Components WritingDelphi WebServices SOAPDelphi WinAPIDelphi XMLDelphi Installationcomp.lang.pascal.delphi.components.misccomp.lang.pascal.delphi.components.usagecomp.lang.pascal.delphi.components.writingcomp.lang.pascal.delphi.databasescomp.lang.pascal.delphi.misccomp.sources.delphi JBuilder Newsgroups----------------JBuilderJBuilder AnnouncementsJBuilder Applet IssuesJBuilder As400JBuilder CompilerJBuilder CORBA/RMIJBuilder DatabasesJBuilder DB SwingJBuilder DebuggerJBuilder DeploymentJBuilder DocumentationJBuilder EnterpriseJBuilder HandheldJBuilder IDEJBuilder JavaJBuilder JavaAPIJBuilder Java LanguageJBuilder Java SwingJBuilder Java BeansJBuilder Java Beans UsageJBuilder Java Beans DevelopmentJBuilder JBCLJBuilder JDataStoreJBuilder JobsJBuilder LinuxJBuilder MacintoshJBuilder & MobileSetJBuilder MultiLingual AppsJBuilder Non-TechnicalJBuilder OpenToolsJBuilder Servlets (JSP)JBuilder StudentsJBuilder Team DevelopmentJBuilder Thirdparty ToolsJBuilder UpgradeJBuilder Installation InterBase Newsgroups----------------InterBaseInterBase Bug DiscussionInterBase GeneralInterBase IBConsoleInterBase OpenSourceInterBase ReplicationInterBase SQLInterBase ThirdpartyInterBase Installation Miscellaneous Borland Newsgroups----------------AppCenterAppServerEnteraVisiBroker  You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot vote in polls in this forum Powered by phpBB © 2001, 2006 phpBB Group SEO toolkit © 2004-2006 webmedic.