<html>
<head>
<style><!--
.hmmessage P
{
margin:0px;
padding:0px
}
body.hmmessage
{
font-size: 10pt;
font-family:Verdana
}
--></style>
</head>
<body class='hmmessage'>
Good points.<BR>
<BR>
<BR>
I forgot to clarify that to some extent I just want to make<BR>multiple passes over functions, not files.<BR> => even less memory and slow down<BR>
<BR> <BR>
In particular, I want to know if a frame size is < 256, or < 4K or >= 4K.<BR>The >= 4K case isn't handled correctly today I believe, though will generally work.<BR>< 256 affords one byte of savings.<BR>
<BR> <BR>
I'd also like to know what registers are used, for 1, 2, or 3 bytes saved.<BR>
<BR> <BR>
While these are small, they are very broadly applicable.<BR><BR>
Consider that even the smallest of functions:<BR> PROCEDURE F(): INTEGER = BEGIN RETURN 1 END F;<BR>
compiles/compiled to something like:<BR> push ebp<BR> mov ebp, esp<BR> sub esp, 0 ; yes, we are willing to put zero here, and it takes 2 bytes<BR> push esi ; I nop this out now.<BR> push edi ; I nop this out now.<BR> push ebx ; I nop this out now.<BR> mov eax, 1<BR> pop ebx ; I optimize this out now.<BR> pop edi ; I optimize this out now.<BR> pop esi ; I optimize this out now.<BR> leave 0 ; I think<BR> ret<BR>
<BR>
<BR>
when, if you punt the point of frame point omission, it could be:<BR> push ebp<BR> mov ebp, esp<BR> mov eax, 1<BR> leave 0 ; I think.<BR> ret<BR>
<BR> <BR>
or if you allow for frame pointer omission: <BR> mov eax, 1 <BR> ret<BR>
<BR>
<BR>(Let's assume the address is taken, therefore it can't always easily be inlined.)<BR>
<BR>"imagine if all code was multiplied out like this"<BR>
<BR>
<BR>Omitting the frame pointer hurts stack walk and debugging, however<BR>I think there is a midddle ground that people don't discuss:<BR> if a function takes no parameters and has no locals, then omit the frame pointer<BR>
<BR>
<BR>Possibly also if it has no locals and/or makes no function calls.<BR> Like, if it never uses esp or ebp.<BR>
<BR> <BR>
Actually this is encoded in PowerPC and AMD64 calling conventions, leaf<BR>
functions can optimize their prologue/epilogue. But it doesn't seem come up<BR>
with regarding x86.<BR>
<BR>
<BR>
There again, multiple passes help.<BR>
<BR>
<BR>Multiple passes over a function would also offer things like<BR> eliminating dead stores, and cascading elimination of dead code, e.g:<BR>
a := b + 1; (* eliminate this whole line *)<BR> a := b + 2;<BR>
<BR> <BR>
Granted, I am interested in multiple passes over a file too, for inlining.<BR>
<BR>
<BR>What I'm really going to do though is try to provide ObjFile.Move so that<BR>at the end of the function, I can "move" the entire function up or down<BR>a few bytes, or maybe only up. You can imagine "down" to fix the >= 4K case,<BR>but you might as well model that as reserving room for the worst case<BR>in first pass, and then move down usually.<BR>
<BR>
<BR>I think it just requires that I understand relocs much better,<BR>which is a good goal anyway for working with the code.<BR>You know -- perform a not well motivated change to some code, for<BR>purposes of exercise -- understanding the code and how to change it,<BR>so that when a better motivated change comes along, we aren't stuck.<BR>
<BR>
<BR>Also, I only recently realized/learned the high value of "sequential access"<BR>as it relates to "working set".<BR>Let's say you really have more data than memory?<BR> In a compiler we don't, but some applications do (plain text indexing of large data).<BR>
<BR>
<BR>Then what you do is:<BR> To whatever extent you can, break the data down into smaller pieces.<BR> At some level, random access is unavoidable, say, to sort small data.<BR> When you can't break the data down:<BR> Access it linearly, not randomly: mergesort instead of quicksort.<BR> Minimize the number of passes, but there is tradeoff between number of<BR> passes and working set size.<BR>
Linear access keeps working set "constant", even if you are slowed down<BR> by having to reread data from disk.<BR>
<BR>
<BR>
Yes I do see that message from the front end.<BR>I haven't looked into what it means, but yeah presumably something<BR>like a pessimistic first pass, followed by discovery of layout information,<BR>followed by more optimistic second pass.<BR>You might imagine, for example, knowing the sizes of opaque or object types.<BR>The front end makes multiple passes. I suspect for significant simplicity<BR>or "possibility" -- it might be darn difficult to implement in fewer passes,<BR>without contorting the code a lot.<BR>
<BR> <BR>
If you look how how "patching" and "labels" work in the backend, that's probably<BR>an example of where multiple passes would be more general and simpler,<BR>but where the "contortions" are well known and not too bad.<BR>
<BR> <BR>
It uses "patching" to fill in the frame size for example, and I now use<BR>that to nop out unnecessary prolog instructions (on the theory that<BR>nop it is a small optimization).<BR>
<BR> <BR>
Though, again, patching isn't sufficient for >4K frames.<BR>Very long standing bug there, I have to confirm and fix soon.<BR>
<BR> <BR>
Good points about whole program optimization.<BR>
<BR>
<BR>I think there are ways to address this. Not any time soon.<BR>Doing optimization and codegen at "link time" I think is somewhat of a hack<BR>in these systems. One we can't easily play into, as you point out.<BR>However, where we use the gcc backend and linker, we probably can, easily.<BR> That is many platforms.<BR> gcc does have this option.<BR>
<BR>
<BR>Also we could optimize "among" all the *.m3 files, just lose out on any M3<=>C optimizations.<BR>
<BR>
<BR>In reality, let me first think about NTObjFile.Move as a way to do some small optimizations,<BR>NTObjFile CodeView generation, maybe inlining, maybe LLVM.<BR>Testing/optimizing the atomics (add,sub,xor can improve, also store and probably load).<BR>Everything else is too much for the time being.<BR>
<BR>
<BR>Maybe we can do some target independent optimizations in m3front or m3front/cg or m3middle as well.<BR>Inlining could be done there, but the metrics of when to do it aren't really available.<BR>Only for *extremely* cheap seeming functions could the front end make a reliable target-independent choice.<BR>
Oh wait -- that is interesting.<BR>
<BR>
<BR>If you consider just the case of inlining functions whose definitions precede use,<BR>the backend could "measure" a function, after generating it, and report back to the frontend<BR>if it should strongly consider inlining it. Then upon subsequent calls, the frontend could<BR>do the inlining.<BR>
Such measurement is always going to be heuristic, but you can imagine stuff like<BR> number of cg calls<BR> number of parameters<BR> does it return a value<BR>
<BR>
<BR>
<BR>As well, if had a <* FORCEINLINE *> pragma, the frontend could implement that.<BR>I'm pretty sure.<BR>Not clear if better to leave the decision to the compiler or not.<BR>After all, C and C++ have "inline" and "__inline" that are just hints<BR>that modern compilers ignore, and Visual C++ has "__forceinline", which<BR>generates a warning when not honored. Seems to be a bit of an arms race<BR>in terms of who things he knows better, programmer or compiler.<BR>Used to always be the programmer, then shifted to compiler, now not clear.<BR>
<BR> <BR>
<BR>
- Jay<BR><BR><BR><BR><BR><BR><BR> <BR>> Date: Sat, 3 Apr 2010 21:20:57 -0400<BR>> From: hendrik@topoi.pooq.com<BR>> To: m3devel@elegosoft.com<BR>> Subject: Re: [M3devel] changing m3middle/m3back to have multiple passes?<BR>> <BR>> On Thu, Apr 01, 2010 at 03:10:04PM +0000, Jay K wrote:<BR>> > <BR>> > However memory capacity has increased tremendously.<BR>> > <BR>> > <BR>> > <BR>> > <BR>> > <BR>> > Whereas I'm only thinking about multiple passes, while still compiling <BR>> > one file at a time,<BR>> > <BR>> > other compilation systems have capitalized on larger memories and now <BR>> > compile entire programs at once, including multiple passes.<BR>> > <BR>> > This goes by multiple names -- "whole program optimization", "link <BR>> > time codegen (LTCG)".<BR>> <BR>> Link-time code generation was already involved in Mark Rain's Mary 2 <BR>> compiler in the early 80's. It didn't actually require today's huge <BR>> memories.<BR>> <BR>> Every now and then the Modula 3 compiler seems to decide to recompile <BR>> something because new source had been discovered, or soething like that. <BR>> I suspect this is because a new .m3 file changes the memory layout that <BR>> was assumed in aanother source file, so that other one needs to be <BR>> reconsidered. Is the complexity of tracking that simpler or more <BR>> complex than doing whole-program compilation?<BR>> <BR>> It's possible that file-by-file compilation is a simpler match for <BR>> interacting with foreign-language compilations, theough. It two <BR>> languages insist on only compiling whole programs, it makes <BR>> mixed-language programming difficult.<BR>> <BR>> -- hendrik<BR> </body>
</html>