Re: Code Generation

Re: Code Generation

[colin]

> > I think we're not agreed that including explicit functionality is
> > necessarily cleaner than including a functional reference.  If there
> > were a number of different applications which might make exclusive
> > use of the compiler's information (and I'm guessing there are) then
> > it seems to me to be semantically cleaner to provide the hook, and
> > decouple the implementation.
> 
> I use 'semantically clean' here to include 'generated code executes
> correctly'. This is a top requirement for compilers, and assembler
> macros certainly break that. If you fix that, you probably find that
> you can't do anything inside the macro except to call a function.

Assembler macros certainly can break that, they don't necessarily break it, of course, any more than adding complexity to a compiler necessarily makes it more labile.  There's a risk in both directions, but only one direction applies even to people who don't choose to use the added functionality.

There's one thing a macro can do that a function call can't, and that's conditionally generate no code at all.

> > I wanted to float the idea of opening up the back-end to people like
> > me, who really +don't+ want to tinker with compilers, or distribute
> > compilers, but who need access to some of the metadata in the
> > compiler.  I think the best way to do it, once and for all, is to
> > define an interface for the backend transfer of the metadata, and I
> > think the least intrusive way is as I've described.

> Well, go ahead. My other concern would be that the day you've
> implemented the macro generation, you find that a certain application
> that falls into the category 'access to compiler metadata' can't be
> implemented on top of your macros.

Yes.  I guess there's always metadata that one could collect and propagate that one has neglected.  Perhaps one way to find out what that might be would be to provide the facility, and see what's missing for a given application.

Given that one would have to find a C-addressable form for compiler metadata, should one choose to treat the generated hooks as function calls, it's more of a headache to add new arguments to a hook than to use the fairly limited but essentially free facilities available through a post-pass, be it m4, PERL, or gas.  So it would seem to me, anyway.

Assuming that the goal of openly supplying metadata to either a post-process, or the application itself, is worthwhile, and given that I'm fairly interested in having and or doing it, what do you really think is the best way to do it?

Colin.

Re: Code generation

[Jim Wilson]

Primrose.Mbanefo@Infineon.com wrote:
> I have seen a lot on the internet saying it is possible to retrieve the
> syntax tree created by gcc.
> I use gcc 2.95.2 on a solaris box and I can't seem to find out how to
> get the tree in a file.

You need a more recent version.  -fdump-translation-unit appeared in 
gcc-3.0.x.

These trees are deliberately incomplete.  This is to prevent people from 
trying to subvert the GPL by feeding the trees into proprietary 
compilers.  This is an inconvenience, but it is FSF policy, and we must 
respect it.

There are additional tree dumping options in more recent gcc versions.
-- 
Jim Wilson, GNU Tools Support, http://www.SpecifixInc.com

Code generation

[Primrose.Mbanefo]

Hello,

I have seen a lot on the internet saying it is possible to retrieve the
syntax tree created by gcc.
I use gcc 2.95.2 on a solaris box and I can't seem to find out how to
get the tree in a file.

I would like to use this tree if it is available for some code
generation from c++ into another language which doesn't look much like
assembler...
Is this possible? Must I update to another version of gcc to do this?

Thank you,
Primrose Mbanefo

Re: Code Generation

[Ken Raeburn]

Colin McCormack <colin@field.medicine.adelaide.edu.au> writes:

> There's a program called Checker ( http://sunsite.unc.edu
> /pub/Linux/devel/c) which acts like Purify, to police references to
> external storage.  It relies, I believe, upon intercepting each such
> reference, and each modification, to ensure that only legal targets may
> be referenced.
> 
> I think it would be a good thing if all such references could be
> (optionally) emitted by the code generator as macros which an assembler
> could expand to support a program like Checker.

Um, why?

If it's done in the assembler, the assembler has to insert calls or
memory references while effectively not changing any register values
the compiler may be depending on.

What's wrong with doing it in the compiler as it is now?

> I think it would be a good thing if all basic blocks were bracketed by a
> pair of assembler macros which an assembler could expand into calls to
> read a high resolution timer and accumulate accurate timings of basic
> block execution times.  Perhaps gcov already does this?

Again with the assembler macros... :-)

In profile.c, output_arc_profiler generates code for incrementing an
execution counter.  You could change that to read a cycle counter or
other fine-grained clock and compute deltas, accumulating totals for
each block.  Or emit a call to some subroutine to do the same thing.

Remember, while in some ways this will give more precise data than
statistical sampling, it alters the effect of the profiling code on
the timing data itself.  The time spent in functions with lots of
small basic blocks will be inflated by a larger factor than the time
spent in functions with a few large basic blocks, even if the original
execution time of the two would have been the same.

> In ColdStore ( http://field.medicine.adelaide.edu.au/coldstore ) we have a
> need to ensure that all constructors call a bit of code to change their
> _vptr.
> 
> I think it would be useful to us if all constructors were bracketed by a
> pair of assembler macros indicating the semantic role of the call.

So add a -fcoldstore option that alters the constructor behavior.  For
anything non-trivial, probably emitting a function call is the best
way to avoid requiring the compiler to know too much about your
system.

> I would like your comments/thoughts on these proposals, as my past
> experience has been that compiler writers are loathe to have their code
> generators spit macros.

I'm not surprised.  Having worked on both gcc and gas, I agree.

The compiler expends rather a lot of effort to try to get good
performance, and many of its aspects (scheduling and register
allocation for example) depend on knowing *exactly* what's going on.
Generating assembler macros whose definitions may vary means the
compiler has less information available to it.  And the macros have to
be written so as to avoid breaking any of those assumptions, or those
assumptions have to be adjusted.

For example, the compiler may think it knows what's in every machine
register before and after a memory access.  If it has to be done with
a macro that *might* clobber register X, then register X cannot be
considered to be available across that memory reference, even if you
don't happen to use a version of the macro that uses that register.

The MIPS back end has to do this sometimes, because of the way older
MIPS assemblers work.  It could undoubtedly generate better code if it
could dictate the literal pool references and relocations directly, as
well as the exact instructions and their order.


I can only see two possible advantages to doing it with assembler
macros: (1) processing the assembly code through a filter, which
complicates the compilation process quite a bit, or (2) hacking the
assembler itself is easier than hacking the compiler, but only because
the assembler is a simpler program, in part because it *doesn't* have
any of this sort of stuff in it.  What is your reason for wanting to
do it here?

Maybe we need an easier way to let the user do generic instrumentation
at certain points of the code generation, expressed in RTL and fully
optimized with the rest of the code....


Per Bothner <bothner@cygnus.com> writes:

> The Checker implementation does not I believe violate any patents.
> However, I don't think it is the right approach.  It uses "fat
> pointers" (i.e. each pointer is represented by a two- or three-word
> set of pointers).  This breaks binary compatibility, which makes
> it very inconvenient.
> 
> A better approach uses "thin" (normal) pointers in function parameters,
> results, globals, and structure fields, but uses "fat" pointers
> *internally* in a function.  Thin pointers are coerced to fat
> pointers as needed by looking them up in a run-time table.

I think you're remembering this backwards from the last time we
discussed it internally at Cygnus.  The Checker code -- at least, last
time I looked at it -- does not use fat pointers in any form in the
compiler.  It does as Colin said, changing each "normal" memory
reference so it's preceded by a check of and/or update to the access
"permissions" for the storage location in question.  Conceptually,
there is a bitmap representing access permissions for storage
locations.  The granularity and indeed the representation used in the
support code are not dictated by the implementation in the compiler,
but the function names were chosen based on some assumptions.

Currently this instrumentation is implemented as ordinary function
calls, though I think for good performance that should eventually
change.  More important though IMHO, and more difficult, is teaching
the compiler how to optimize away or combine some of these calls for
multiple accesses to the same location.

Both of the fat-pointer versions did come up in our discussions
though.  Depending on the details, they may have the disadvantage of
not detecting allocated-but-not-initialized locations.


The Checker package (as opposed to the -fcheck-memory-usage option)
also uses some tricks to rename functions, so that the instrumented
functions call instrumented functions, and link-time errors result if
a function (1) isn't compiled with instrumentation, and (2) doesn't
have a wrapper function supplied.  I haven't played with that aspect
much, so I can't really address it.

Ken

Re: Code Generation

[Ken Raeburn]

Colin McCormack <colin@field.medicine.adelaide.edu.au> writes:

> From where I stand, as a compiler user, a compiler's a big, complicated,
> sensitive, temperamental program.  If I can arrange for a simple
> post-process to do a job, I see no reason to make the compiler any
> bigger or more complex, to make others pay for the facility even though
> they may never need it, or to saddle others with the task of supporting
> the more complex code.

But for most cases, finding the proper places to annotate in the
assembly code would be the hard part, and that has to be done (and
maintained) in either case; emitting the right extra instructions is
usually relatively easy and often machine-independent.

Doing it through assembler macros means not only hacking the compiler
to indicate what gets instrumented, but also writing assembly code for
each processor configuration used, and hacking the build process to
use the right assembly file add-on.

> Decoupling what can be decoupled seems to make sense to me for this
> reason.  The minimally intrusive interface I can envisage is an
> assembler macro.  An assembler macro can be distributed as an add-on,
> it's small, it can be conditionally turned into an identity
> transformation, it can capture all the information the compiler has, and
> selectively use it.

"All the information"?  That will *not* be small.  Consider some of
the information you *might* want for *some* post-processor: user line
numbers; conditional branch or switch locations and destinations at
assembly level; conditional branch or switch locations and
destinations in HLL, including information necessary to distinguish
multiple paths that have been combined by the optimizer; memory reads,
writes, modifies, and block moves, possibly with operand types; basic
block boundaries; HLL block boundaries; variable types, sizes, and
locations (which may change in the course of the function); function
call sites with argument descriptions; incoming argument descriptions;
HLL types of arithmetic operands (e.g., for "see how many complex adds
we do"); beginning and end of code initializing an object.  Also
seemingly random HLL information like C++ vtbl pointer setting during
object initialization -- I don't think there's an equivalent for that
in any of the other languages in the distribution, unless Java has
something similar.  And most of that list is based on things we
already instrument under control of one option or another; for random
post-processing, I'm sure there'd be more.

I would guess "all the information" we might want is going to be
comparable in size to the actual instruction stream plus debugging
info, if not bigger.  If you're willing to analyze the instruction
stream and the debug info themselves, that gets rid of a lot of it,
but still leaves at least (a) HLL info like C++ constructors and
specifically vptr initialization, and types of non-user objects like
intermediate results, and (b) anything the user might want
instrumented but the optimizer has already discarded, which is still
too vague and probably rather large.

I think it's more pragmatic to just have the compiler simply know
about various sorts of instrumentation we want to do, and support them
directly.  If we find one construct tends to get instrumented in lots
of different ways, then perhaps that one should use some user-supplied
parameter do dictate the behavior.  Maybe by naming the assembly macro
to use or giving an option that translates to a file with additional
asm code to include to define the macros as desired; maybe by
describing the rtl or tree structures to generate (and optimize) for
the instrumentation; maybe something else.

> None of the applications I suggested are performance-critical.  Dumping
> the whole register set and reloading it wouldn't (to me) be an
> unacceptable overhead while running a Checker-like check of my code.

Maybe not for you, at the moment, but perhaps for someone else.  Using
Checker with a heavily used network server daemon program could slow
it down enough to cause timeouts, rendering it useless.  I've worked
on some daemons that run full-out and only barely keep up with their
traffic; a factor-of-2 (or 20) slowdown would be completely
unacceptable.

Re: Code Generation

[Martin v. Loewis]

> I think we're not agreed that including explicit functionality is
> necessarily cleaner than including a functional reference.  If there
> were a number of different applications which might make exclusive
> use of the compiler's information (and I'm guessing there are) then
> it seems to me to be semantically cleaner to provide the hook, and
> decouple the implementation.

I use 'semantically clean' here to include 'generated code executes
correctly'. This is a top requirement for compilers, and assembler
macros certainly break that. If you fix that, you probably find that
you can't do anything inside the macro except to call a function.

> I wanted to float the idea of opening up the back-end to people like
> me, who really +don't+ want to tinker with compilers, or distribute
> compilers, but who need access to some of the metadata in the
> compiler.  I think the best way to do it, once and for all, is to
> define an interface for the backend transfer of the metadata, and I
> think the least intrusive way is as I've described.

Well, go ahead. My other concern would be that the day you've
implemented the macro generation, you find that a certain application
that falls into the category 'access to compiler metadata' can't be
implemented on top of your macros.

Regards,
Martin

Re: Code Generation

[Jeffrey A Law]

  In message < 19990103074421.28824.qmail@field.medicine.adelaide.edu.au >you wri
te:

  > I wanted to float the idea of opening up the back-end to people like me,
  > who really +don't+ want to tinker with compilers, or distribute compilers,
  > but who need access to some of the metadata in the compiler.  I think the
  > best way to do it, once and for all, is to define an interface for the
  > backend transfer of the metadata, and I think the least intrusive way is
  > as I've described.
I've been involved in a variety of these kinds of projects in the past; 
purify-like memory checkers,  generation of runtime data to drive function
reordering, instrumentation of code to provide minimal branch histories, and
other things.

In my experience you are best off writing the instrumentation code directly
into the code generator in the compiler.  You get a lot of target independence
that way.  You can also avoid a lot of instrumentation overhead by allowing
the optimizer to chomp on the instrumented code.

The amount of compiler internals you need to learn to emit macro-ized code
are going to be about the same as you would if you hooked directly it the
code generator.  And by hooking into the code generator, you instrumentation
support will be useful by other people on a much wider variety of platforms.

I'm also strongly opposed to emitting any kind of macro-ized assembler by the
the compiler.  My experiences with macro-ized assembler code have been less
than pleasant and we're working towards less reliance of macro-ized assembler
code in the one remaining port which relies heavily on it (mips).


jeff

Re: Code Generation

[Per Bothner]

> Anyway, Purify for free as a side-effect of egcs would be very sweet.

Careful.  Purify has restrive (and enforced) patents.
What we need is array bounds checking - without using the purify
parented techniques.

The Checker implementation does not I believe violate any patents.
However, I don't think it is the right approach.  It uses "fat
pointers" (i.e. each pointer is represented by a two- or three-word
set of pointers).  This breaks binary compatibility, which makes
it very inconvenient.

A better approach uses "thin" (normal) pointers in function parameters,
results, globals, and structure fields, but uses "fat" pointers
*internally* in a function.  Thin pointers are coerced to fat
pointers as needed by looking them up in a run-time table.

This is not a efficient or clean or simple as fat pointers, but
it preserves binary compatibility, without which Checker is little
more than a toy.

If someone want to work on an improved binary-compatible Checker,
I have some ideas.  I'd be happy in sharing these ideas - if there
actually is a chance someone might actually take on such a project.
(Probabaly quite of bit of the Checker code can be re-used, or will
at least help identify the code that needs to be changed.)

	--Per Bothner
Cygnus Solutions     bothner@cygnus.com     http://www.cygnus.com/~bothner

Re: Code Generation

[colin]

> > Having said this, I agree that Checker-like functionality is so
> > intimately wound up with what the compiler's doing that it may be
> > smarter to do it in-compiler.  I just wouldn't +dare+ suggest that
> > anyone else be asked to do it, and I wouldn't be able or prepared to do
> > it myself, where I would be prepared to consider writing the macros
> > mentioned.
> 
> This might be the problem. *Somebody* has to modify the compiler, for
> a seemingly special application. Such a change has to be maintained.
> If it gets used, a detailed specification of what it does and how it
> works is necessary. To the compiler writer, this is insignificantly
> different from putting the desired functionality into the compiler in
> the first place, where this option has the advantage of being
> semantically cleaner.

I think we're not agreed that including explicit functionality is necessarily cleaner than including a functional reference.  If there were a number of different applications which might make exclusive use of the compiler's information (and I'm guessing there are) then it seems to me to be semantically cleaner to provide the hook, and decouple the implementation.

Case in point: the gcov stuff.  I haven't checked, but it appears from this discussion that it emits code to increment a pointer, whereas for semantic/block-level fine-grained profiling, it ought to increment a pointer and store the sum of a delta into a location.

If gcov emitted a macro instead, then the macro definition could selectively be made to handle either function.  If we go the `everything in the compiler' route, then (a) the maintenance load is heavier for compiler writers, (b) there are more switches for the compiler, (c) the compiler's doing more things that a compiler probably doesn't need to do.

Secondly, although I didn't make it clear, I'd be prepared to add the macro stuff to the compiler, too, because I think it's within my capabilities.

I wanted to float the idea of opening up the back-end to people like me, who really +don't+ want to tinker with compilers, or distribute compilers, but who need access to some of the metadata in the compiler.  I think the best way to do it, once and for all, is to define an interface for the backend transfer of the metadata, and I think the least intrusive way is as I've described.

It seemed to me to be necessary to guage the feeling of people who are focused on the larger compiler, rather than an instance of its use, before undertaking what is to me an arduous task.

Colin.

Re: Code Generation

[Horst von Brand]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 1296 bytes --]

Colin McCormack <colin@field.medicine.adelaide.edu.au> said:
> Subject: Code Generation
> 
> Return-Path: colin@cygnus.com 
> Return-Path: <colin@cygnus.com>
> Mailing-List: contact egcs-help@egcs.cygnus.com; run by ezmlm
> Precedence: bulk
> Sender:  owner-egcs@egcs.cygnus.com
> Delivered-To: mailing list egcs@egcs.cygnus.com
> Sender:  colin@cygnus.com
> X-Mailer: Mozilla 4.06 [en] (X11; I; Linux 2.1.132 i686)
> MIME-Version: 1.0
> Content-Type: text/plain; charset=us-ascii
> Content-Transfer-Encoding: 7bit
> X-UIDL:  b323c49f2ccab87bc9857b89e8fd1709
> 
> There's a program called Checker ( http://sunsite.unc.edu
> /pub/Linux/devel/c) which acts like Purify, to police references to
> external storage.  It relies, I believe, upon intercepting each such
> reference, and each modification, to ensure that only legal targets may
> be referenced.

lcc < http://www.cs.princeton.edu/software/lcc > keeps a counter for each
block, and increments it each time it is excecuted. This is cummulative for
runs of the program. A companion program takes the source and the output of
the above and creates an annotated listing. Quite nice.
-- 
Horst von Brand                             vonbrand@sleipnir.valparaiso.cl
Casilla 9G, Viña del Mar, Chile                               +56 32 672616

Re: Code Generation

[Colin McCormack]

Erratum:

Checker's not where I said it was.  It is at

http://metalab.unc.edu/pub/Linux/devel/lang/c/Checker-0.8.tgz
http://metalab.unc.edu/pub/Linux/devel/lang/c/Checker-libs-0.8.1.tgz

There's a newer version at www.debian.org under unstable development, I
think.

http://www.debian.org/Packages/unstable/devel/checker.html

I'm unclear about the relationship between these versions.

Anyway, Purify for free as a side-effect of egcs would be very sweet.

Colin.

Re: Code Generation

[Martin v. Loewis]

> Having said this, I agree that Checker-like functionality is so
> intimately wound up with what the compiler's doing that it may be
> smarter to do it in-compiler.  I just wouldn't +dare+ suggest that
> anyone else be asked to do it, and I wouldn't be able or prepared to do
> it myself, where I would be prepared to consider writing the macros
> mentioned.

This might be the problem. *Somebody* has to modify the compiler, for
a seemingly special application. Such a change has to be maintained.
If it gets used, a detailed specification of what it does and how it
works is necessary. To the compiler writer, this is insignificantly
different from putting the desired functionality into the compiler in
the first place, where this option has the advantage of being
semantically cleaner.

Regards,
Martin

Code Generation

[Colin McCormack]

There's a program called Checker ( http://sunsite.unc.edu
/pub/Linux/devel/c) which acts like Purify, to police references to
external storage.  It relies, I believe, upon intercepting each such
reference, and each modification, to ensure that only legal targets may
be referenced.

I think it would be a good thing if all such references could be
(optionally) emitted by the code generator as macros which an assembler
could expand to support a program like Checker.

There are numerous profilers, they are limited to dividing code into
buckets of arbitrary, usually fixed, equal sizes.  They collect
performance data by a monte carlo method, incrementing a counter per
bucket according to what value the PC has when a tick happens.

I think it would be a good thing if all basic blocks were bracketed by a
pair of assembler macros which an assembler could expand into calls to
read a high resolution timer and accumulate accurate timings of basic
block execution times.  Perhaps gcov already does this?

In ColdStore ( http://field.medicine.adelaide.edu.au/coldstore ) we have a
need to ensure that all constructors call a bit of code to change their
_vptr.

I think it would be useful to us if all constructors were bracketed by a
pair of assembler macros indicating the semantic role of the call.

I would like your comments/thoughts on these proposals, as my past
experience has been that compiler writers are loathe to have their code
generators spit macros.  I could probably pre-process stabs information
to produce the basic block information, and possibly even the
constructor information, but I'm loathe to do this.

I think Checker's an excellent system, a very useful facility, and
deserves to be supported by egcs (or any modern compiler.)

Colin.

Re: Code Generation

[Colin McCormack]

Ken asks:
> I can only see two possible advantages to doing it with assembler
> macros: (1) processing the assembly code through a filter, which
> complicates the compilation process quite a bit, or (2) hacking the
> assembler itself is easier than hacking the compiler, but only because
> the assembler is a simpler program, in part because it *doesn't* have
> any of this sort of stuff in it.  What is your reason for wanting to
> do it here?

From where I stand, as a compiler user, a compiler's a big, complicated,
sensitive, temperamental program.  If I can arrange for a simple
post-process to do a job, I see no reason to make the compiler any
bigger or more complex, to make others pay for the facility even though
they may never need it, or to saddle others with the task of supporting
the more complex code.

Decoupling what can be decoupled seems to make sense to me for this
reason.  The minimally intrusive interface I can envisage is an
assembler macro.  An assembler macro can be distributed as an add-on,
it's small, it can be conditionally turned into an identity
transformation, it can capture all the information the compiler has, and
selectively use it.

None of the applications I suggested are performance-critical.  Dumping
the whole register set and reloading it wouldn't (to me) be an
unacceptable overhead while running a Checker-like check of my code.

It would seem to me that compiling in a function call given a
-fcoldstore option and generating a macro ``call'' for the same purpose
given the same option makes no real difference, except that I can
conditionally assemble-out the macro call, at no runtime performance
cost, and little compile-time cost.

It just seems to me that there's a wealth of information painstakingly
calculated by the compiler which could be propagated to later
post-processes at fairly low cost, and in doing this, the compiler
immediately and adequately supports all the possible post processes
(those I can dream up, those others will dream up.)

I really can't see how it loses if, for example, the gcov code spits a
macro which could additionally server for profiling.

Having said this, I agree that Checker-like functionality is so
intimately wound up with what the compiler's doing that it may be
smarter to do it in-compiler.  I just wouldn't +dare+ suggest that
anyone else be asked to do it, and I wouldn't be able or prepared to do
it myself, where I would be prepared to consider writing the macros
mentioned.

Colin.