[antlr-interest] philosophy about translation

Nagesh, Harsha harsha.nagesh at credit-suisse.com
Thu Oct 12 07:41:08 PDT 2006



Andy,

    In one of the previous mails you mentioned about using Collections.Sort routine of java to replace an equivalent piece of code in C. I am really curious how would you go about doing this ? There can be any number of ways one could write a sorting algorithm and I am wondering if you really try to do some fancy token matching to determine that "Aha this is indeed the xyz sorting algorithm" and then replace it with one function call

Harsha

-----Original Message-----
From: antlr-interest-bounces at antlr.org [mailto:antlr-interest-bounces at antlr.org] On Behalf Of Andy Tripp
Sent: Thursday, October 12, 2006 10:25 AM
Cc: ANTLR Interest
Subject: Re: [antlr-interest] philosophy about translation

Loring Craymer wrote:

>--- Andy Tripp <antlr at jazillian.com> wrote:
>
>
>  
>
>>>Check out memcpy for gcc targeting an x86 for an example of a 
>>>compiler-translated library call.
>>>
>>>      
>>>
>>I don't need to check what gcc does for memcpy() calls. I know it does 
>>the same thing that it does for all function calls:
>>generates low-level code
>>to call a function. You're missing my point
>>
>>    
>>
>
>Right.  You "know".  gcc actually translates memcpy into a short 
>sequence of assembler instructions that optimally copy.  There are a 
>few other builtin functions supported by gcc.
>  
>
Geez. You think I don't know that compilers do optimizations like this?
*sigh* Yes, I'm taking a shortcut when I say memcpy() translates to a function call.
And yes, I'm going to just say "a function call" rather than "a push operation on the stack frame". When I'm imprecise like that, you can take that to mean I don't know what I'm talking about, or you can try to see my real point: that gcc, and no other compiler, looks at the memcpy() call, and then looks at the arguments, and then goes back and looks at the argument type and other usages, and then sees that, in fact, this
memcpy() call is doing nothing more than re-initializing memory to zeros, and is operating on an entire object, and so can be replaced by a Java new call. And, by the way, then also go and create a no-arg constructor for the object if it doesn't already have one.

Yes, I do think I "know" that gcc doesn't do that.

Sheesh. There really is a point there.

>  
>
>>entirely: I don't "compile"
>>a memcpy() and all other calls down to a lower level
>>- I treat each
>>one individually. For memcpy(), for example, I do all that checking to 
>>see what a reasonable replacement is.
>>
>>    
>>
>>>As for
>>>the assignment, I see nothing wrong; you have added the restrictions 
>>>that all strings are read-only.
>>>      
>>>
>>That
>>    
>>
>>>would cause errors if naively translated statements like "v1[5] = ' 
>>>';", but I assume that you do the right thing.
>>> 
>>>
>>>      
>>>
>>strcpy() actually makes a copy, while assignment does not. That can 
>>introduce a bug. A compiler would never do that type of replacement 
>>because it may introduce a bug. Yet a person doing a rewrite would.
>>    
>>
>
>Compilers tend to do very interesting things with registers, bypass 
>assignments (intermediate values are not stored to memory), reuse 
>registers that are no longer "live", etc.  As long as input and output 
>semantics are equivalent, the intermediate values "don't matter".  
>Without that freedom, optimization would be impossible.
>  
>
I know compilers do interesting things. Generating incorrect code on purpose is not one of them.

>  
>
>>And no, don't assume that I do "the right thing".
>>Your idea of the
>>"right thing" is, I'm
>>sure, to generate code that always works. And that's not what I do. If 
>>I did that, I would end up with Ephedra, allocating a huge array in 
>>memory, and having every variable reference go through that array.
>>
>>    
>>
>>> 
>>>
>>>      
>>>
>>>>I rename files, methods, and variables based on user-specified 
>>>>mappings.
>>>>Compilers don't do that.
>>>>I could go on.
>>>>   
>>>>
>>>>        
>>>>
>>>Most of the translations are not user-specified,
>>>      
>>>
>>true.
>>    
>>
>>>But any C/C++ compiler renames methods and
>>>      
>>>
>>variables
>>    
>>
>>>according to user specifications (macros), and supports file renaming 
>>>for output.
>>>
>>>      
>>>
>>Yea, but that's different. If you convert 1000 files from C to Java, 
>>you want to specify a mapping from each input file name to the package 
>>that the Java class should go into.
>>    
>>
>
>And you made the particular design decision not to use an external 
>build system ...
>  
>
Yes. I don't see how that relates. I don't see how an external build system would help. And I think this is a valid example of things that I do and compilers do not do.

>
>  
>
>>>This is a user group, not a theory group, so it is
>>>      
>>>
>>not
>>    
>>
>>>the ideal forum for this sort of sanity check (although it is 
>>>certainly better than none).  I do have to think that dragging Monty 
>>>out of  the
>>>      
>>>
>>woodwork
>>    
>>
>>>for this discussion was a significant achievement!
>>>      
>>>
>I
>  
>
>>>only jumped in after I thought that sanity had prevailed to make the 
>>>point that "it's really not
>>>      
>>>
>the
>  
>
>>>methodology that's at issue, it's the level of tool support".
>>>
>>>--Loring
>>>=== message truncated ===
>>> 
>>>
>>>      
>>>
>>Thanks for the discussion. If you can suggest a
>>    
>>
>better >place for me to bring
>  
>
>>stuff like this up, let me know and I'll take it elsewhere.
>>    
>>
>
>My point wasn't "go somewhere else", it was more "don't necessarily 
>expect definitive answers".
>  
>

OK.

>--Loring
>
>  
>
>>Andy
>>    
>>
>
>
>
>__________________________________________________
>Do You Yahoo!?
>Tired of spam?  Yahoo! Mail has the best spam protection around 
>http://mail.yahoo.com
>
>  
>


==============================================================================
Please access the attached hyperlink for an important electronic communications disclaimer: 

http://www.credit-suisse.com/legal/en/disclaimer_email_ib.html
==============================================================================



More information about the antlr-interest mailing list