Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c > #106252
| Newsgroups | comp.lang.c |
|---|---|
| Date | 2017-03-16 09:22 -0700 |
| References | (5 earlier) <ibWxA.69903$k61.43609@fx05.iad> <c117efc1-24a2-40cb-bc44-0c8833dff448@googlegroups.com> <oaa93r$obp$1@z-news.wcss.wroc.pl> <ed6e2220-879c-4c33-a3e4-fbefc9376fcb@googlegroups.com> <oacq5n$5vs$1@z-news.wcss.wroc.pl> |
| Message-ID | <bc4e795e-07d3-47d2-9e77-21fde4e7eeb2@googlegroups.com> (permalink) |
| Subject | Re: C Compilers QoI |
| From | supercat@casperkitty.com |
On Wednesday, March 15, 2017 at 8:36:00 PM UTC-5, anti...@math.uni.wroc.pl wrote:
> supercat wrote:
> > Going after low-hanging fruit is cheap and doesn't require much extra
> > memory. For example, instead of having a function to generate code to
> > put an effective address into EBX, one could pass a pointer to a structure
> > that describes the effective address as one of several forms, and have
> > code that would perform operations on [EBX] accept that structure and
> > generate code for the effective address indicated therein. If one does
> > likewise for code which would place value operands in EAX, then something
> > like:
> >
> > p->member += 3;
> >
> > would be improved from:
> >
> > mov ebx,&p
> > mov ebx,[ebx]
> > add ebx,4 ; member offset
> > mov eax,3
> > add [dword ebx],eax
> >
> > to
> >
> > mov ebx,[p]
> > add [dword ebx],3
> >
> > A huge improvement in code quality, but relatively cheap.
>
> Well, it would take substantial work to get your first form.
> As I wrote currently the compiler is a toy, it has 1458 lines
> total from which 896 is code generator. And that is wc count,
> including blank lines, comments and a lot of whitespace.
Peephole optimizing isn't completely trivial, but it's low-hanging fruit
compared with the kinds of optimizations gcc goes after.
> In pseudo Pascal single line version of Bart's routine is:
>
> procedure foo;
> var a, b, c, d;
> begin
> a := b + c*d;
> end;
>
> which generates:
>
> .globl foo
> .type foo, @function
> foo:
> subq $64, %rsp
> movq 48(%rsp), %rax
> movq %rax, 56(%rsp)
> movq 32(%rsp), %rax
> movq %rax, 40(%rsp)
> movq 16(%rsp), %rax
> movq %rax, 24(%rsp)
> movq 40(%rsp), %rax
> imulq 24(%rsp), %rax
> movq %rax, 8(%rsp)
> movq 56(%rsp), %rax
> addq 8(%rsp), %rax
> movq %rax, 0(%rsp)
> addq $64, %rsp
> ret
>
> Let me explain how this code is created. First, compiler performs
> tree walk of parse tree of the whole program. During tree walk
> compiler introduces temporary variable for each inner node of an
> expression, effectively transforming:
>
> a = b + c*d
>
> into
>
> t1 = b
> t3 = c
> t4 = d
> t2 = t3 + t4
> a = t1 + t2
> In principle simple piphole optimizer
> could eliminate some useless stores of temporaries
> to memory. But thate would be an additional pass
> and AFAICS in the example above it would lead to
> no improvement. It is tempting to keep temporaries
> in registers and generate intermediate results
> directly to registers. But AMD64 instruction set
> still has various irregularities and some arguments
> and/or results need to be in specific registers.
> So generators for primitive operations would have
> to cope with arguments or results in "wrong" registers.
> Also, when compiler runs out of registers it has to
> spill something, so there is need to generate spill
> code and manage info about current location of variables.
> All doable in serious compiler, but would significantly
> complicate my toy.
Having a compiler look for cases where one operand of "+" or "*" is a
simple variable and the other is an expression, and evaluate the expression
first, is pretty easy, and would result in the only load and store of a
temporary being consecutive, which would be precisely the kind of thing that
peephole optimizers are good at handling.
> Let me add that one of goals for me was compiler that
> is obviously correct -- the naive tactic is reasonably
> close to this. Also, while this compiler is a toy
> I used similar approach prototyping compiler for
> higher level language using C as a target. Now,
> gcc nicely elliminates all bloat due to unnecessary
> temporaries and extra copies. In fact, somewhat
> bloated C code compiled by gcc leads to very good
> machine code. OTOH trying to produce tighter C
> may lead to worse machine code. Namely, temporaries
> in generated C code cannot alias anything and gcc
> can easily deduce dependencies. Reusing temporaries
> and especially directly using variables from
> higher level obscures information and may force
> gcc to generate more conservative code. My
> conclusion from this is that for purpose of
> translating higher level language I can outsource
> low level optimisations to gcc, instead concetrating
> on higher level aspects. My current estimate is
> that gcc generates about 10 times faster code
> that my generator. So it would be nice to have
> fast generator of good code, but at least for me
> it is long way to go...
Variable-lifetime graph coloring is a useful thing for compilers to be able
to do. While doing it perfectly may require exponential time, doing a fairly
basic job can be pretty easy. Having directives to indicate when a variable
could safely be set to an unspecified value might make graph coloring even
more effective, but there are no standards for such things. While some
compilers may use reserved identifiers to indicate unspecified values, an
intrinsic which took an lvalue would IMHO be better. If one has code like
someVariable = __UNSPECIFIED__;
one could make it work on compilers that don't recognize the intrinsic by
saying
#define __UNSPECIFIED__ 0
but that would in many cases compel such compilers to generate actual code
for it, defeating the entire purpose. By contrast, if there were an
intrinsic:
__ERASE_UNSPECIFIED(someVariable);
then a compiler which didn't know how to optimize usefully could be made
to simply ignore it.
> Well, currently assembler takes more time then my compiler, so it
> would make sense to generate code directly. The point is that
> we need to store various intermediate information at least at
> scale of a function. In old tradition one could store intermedate
> data in files. However, correctly handling intermediate files
> add complexity (think about deleting intermediate files when
> compiler receives a signal). And on some filesystems limit
> on the file size may be smaller than available RAM. Or
> temporary filesystem may be in a ramdisk. So cost/benefits
> ratio of various tricks to handle large functions looks low.
Older tools managed to have functions that would use ram buffers when space
allowed, and spool to disk when it didn't. On systems which handle virtual
memory effectively I could see justification for simply relying upon that
if available virtual space would be expected to be large enough to accommodate
any kind of program one would be called upon to process. On the other hand,
a simple and straightforward (but big) "do all these actions in sequence"
program should not require orders of magnitude more storage to compile than
it would to execute.
> > A compiler will generally need to see an entire loop before deciding upon
> > the optimal register allocation of variables at the start, but the larger
> > a loop is the less relative cost there will be for guessing wrong. At worst,
> > the compiler will have to shuffle some variables around before branching back
> > to the start of the loop. If a compiler can hold off on generating the code
> > for the start of the loop until it knows the best arrangement, that will allow
> > better code than if it has to start generating code before it knows what's
> > best, but if the compiler defaults to "safe" choices when generating code in
> > such circumstances, it will be able to work around those choices later on.
>
> Well, if you have a loop around a switch with many cases, then average
> executed sequence of instructions may be moderate despite enormous
> size of the whole loop. In similar spirit one can consider code
> obtained via Boehm-Jacopini theorem. In this case one converts
> aribtrary spagetti of gotos into a big loop with a chain of ifs.
> Naively compiling obtained code leads to one loop iteration per
> jump in orignal spagetti program. This basically leads to slowdown
> proportional to number of labels in orignal program. But using known
> optimization techniques one can essentially reconstruct original
> spagetti from structured form. Main point is that structural
> code assign to variable information about destination of jump
> in spaggetti version. Optimizer can use known value of this
> variable to find out next computational statement that will
> be executed essentially bypassing long chain of ifs performing
> dispatch in naive version. ATM I know of no compiler which
> can do this on practical code, but gcc was quite close (it
> implements all needed steps but was unable/unwilling to combine
> them).
It's certainly possible to have a loop with a huge amount of code in it
that ends up executing only a small amount of the code in most iterations.
On the other hand, a programmer who knows that some cases will be more
common than others should be able to arrange the code, or perhaps add
annotations, to help a compiler exploit that. Having a programmer do
such work once may make more sense than requiring a compiler to do extra
work every time a program is built.
Also, if I write something like:
... assume "x" is some integer type
if (x == 23)
...
else switch(x)
{
}
should a compiler absorb the code that handles a value of 23 into the switch
statement or leave it as-is? My feeling is that when I write code like that
it is--likely as not--because I expect performance to be dominated by cases
where x is 23 and any slowdown on those cases would degrade performance even
if it improved performance in all other cases. If a compiler can't see the
program's source of input, it would have no basis for assuming it knows more
than I do about its distribution.
> In a bit different spirit, frequently error handling
> code is more complicated than actial computation. To
> ensure correctness C source will have a lot of checks
> (either coming from macros or inserted by generator unable
> to deduce if check can fail). In big loop compiler can
> fing invariants and use them to prove that checks can not
> fail and due to this substantially simplify the code.
> As a realistic example consider bound checking array
> accessor macro. IME gcc can eliminate most checks
> inserted by such macros.
Having a compiler eliminate checks that are actually redundant can be good.
On the other hand, in cases where a program could meet requirements without
certain checks in the machine code, optimization will not be helped by
requiring that a programmer include those checks in the source code. If
the behavior of a the machine code would be affected by the presence or
absence of such checks, but both behaviors would be equally acceptable, there
may be no way to convince a compiler to omit those checks without it also
omitting checks which are crucial to correct operation.
> Anyway the point is that there are codes when large scale
> optimization can give significant speedup. And some
> folks write code assuming that quality compiler will perform
> certain optimizations.
Compilers should not expect to be suitable for all purposes if programmers
don't use options or directives to indicate what they actually need. There
are some situations where where high-end optimizations might yield orders-
of-magnitude performance increases which could not be achieved any other way.
There are many others where even a 1990s compiler would yield code whose
performance is within 10% of the best that could be achieved by any means
on the target platform.
My personal philosophy is that compilers should, by default, try to be fast
enough that programmers won't have to spend much time waiting for the
compiler, and should try to be compatible with a wide range of programs that
need to use features of the underlying platform but don't jump through hoops
in an effort to do so. If code generated with default settings runs slowly
enough that a programmer would want to make it faster, then a programmer can
see about enabling more optimizations. If cheap and safe optimizations would
suffice to meet requirements, however, any attempt to add others would be
"premature" (and, per the axiom, viewed as "evil").
> > Of course, but such things have a certain cost. For some kinds of code, the
> > payoffs may be huge, making such optimizations clearly worthwhile. For other
> > kinds of code, the payoffs may be much smaller.
>
> I know how to write C source so that even naive compiler will
> give resonably fast machine code. But assuming that
> C compiler will do reasonable job at optimization I
> can write clearer and safer code. For example instead
> of error prone reasoning which checks are needed I just
> write redundant checks and let compiler remove useless
> one. Putting checks in macros leads to compact code
> which is obviously correct (because every operation
> is checked).
There are a number of directives that could be added to the language to
reduce the need for compilers to include error-checking code that won't
help a program meet requirements. At present, there's no way by which
code can say e.g. "I'll need to know if an overflow happens anywhere in
this stretch of code, but I won't care exactly when", nor even "Set the
overflow flag if this calculation would overflow and its result would be
used, but if the result of the calculation isn't used feel free to omit
the overflow check". Letting programmers indicate what kinds of checking
are actually needed would help eliminate the need for redundant checks.
Using UB-based optimization, however, has the opposite effect, since it
compels programmers to include checks which would not need to be present
in the machine code for a program to meet requirements.
> Indeed, but splitting code into sensible pieces which can be
> handled without trouble by C compiler is part of generator job.
> And splitting is clearly related ot global optimization: when
> all interesting dependecies were handled splitting should be
> easy. As an example I have a code generator which can produce
> potentially large expressions and convert them to code.
> Generator introduces temporaries to split expression into
> parts of managable size. And it performs common subexpresssion
> elimination. In effect, if needed generator could split
> expression into several functions without significant loss
> of efficiency compared to putting expression in a single
> function.
If there would be a natural split in the source domain, it makes sense to
carry through such a split and generate multiple distinct functions. If,
however, something is simply a large blob in the source domain and doesn't
have any logical subdivisions, I see no reason to expect that a code
generator should partition a large function into pieces of some arbitrary
size unless it is expected to be used with a target that would impose some
limit (e.g. a segmented architecture where each function is required to fit
in a single segment).
Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
C Compilers QoI BartC <bc@freeuk.com> - 2017-03-14 13:01 +0000
Re: C Compilers QoI mark.bluemel@gmail.com - 2017-03-14 06:16 -0700
Re: C Compilers QoI already5chosen@yahoo.com - 2017-03-14 06:42 -0700
Re: C Compilers QoI "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2017-03-14 06:56 -0700
Re: C Compilers QoI BartC <bc@freeuk.com> - 2017-03-14 15:58 +0000
Re: C Compilers QoI "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2017-03-14 09:22 -0700
Re: C Compilers QoI scott@slp53.sl.home (Scott Lurndal) - 2017-03-14 16:54 +0000
Re: C Compilers QoI supercat@casperkitty.com - 2017-03-14 10:24 -0700
Re: C Compilers QoI scott@slp53.sl.home (Scott Lurndal) - 2017-03-14 17:58 +0000
Re: C Compilers QoI supercat@casperkitty.com - 2017-03-14 14:12 -0700
Re: C Compilers QoI Robert Wessel <robertwessel2@yahoo.com> - 2017-03-14 16:34 -0500
Re: C Compilers QoI Robert Wessel <robertwessel2@yahoo.com> - 2017-03-14 17:36 -0500
Re: C Compilers QoI BartC <bc@freeuk.com> - 2017-03-14 23:06 +0000
Re: C Compilers QoI supercat@casperkitty.com - 2017-03-14 16:20 -0700
Re: C Compilers QoI antispam@math.uni.wroc.pl - 2017-03-15 02:32 +0000
Re: C Compilers QoI BartC <bc@freeuk.com> - 2017-03-15 12:49 +0000
Re: C Compilers QoI supercat@casperkitty.com - 2017-03-15 11:56 -0700
Re: C Compilers QoI BartC <bc@freeuk.com> - 2017-03-15 23:09 +0000
Re: C Compilers QoI scott@slp53.sl.home (Scott Lurndal) - 2017-03-16 18:17 +0000
Re: C Compilers QoI supercat@casperkitty.com - 2017-03-16 11:47 -0700
Re: C Compilers QoI Ian Collins <ian-news@hotmail.com> - 2017-03-17 07:50 +1300
Re: C Compilers QoI supercat@casperkitty.com - 2017-03-16 12:59 -0700
Re: C Compilers QoI David Brown <david.brown@hesbynett.no> - 2017-03-16 21:24 +0100
Re: C Compilers QoI supercat@casperkitty.com - 2017-03-16 14:23 -0700
Re: C Compilers QoI Ian Collins <ian-news@hotmail.com> - 2017-03-17 11:30 +1300
Re: C Compilers QoI Ian Collins <ian-news@hotmail.com> - 2017-03-17 11:38 +1300
Re: C Compilers QoI Gareth Owen <gwowen@gmail.com> - 2017-03-17 05:07 +0000
Re: C Compilers QoI Ian Collins <ian-news@hotmail.com> - 2017-03-17 20:26 +1300
Re: C Compilers QoI Gareth Owen <gwowen@gmail.com> - 2017-03-17 07:59 +0000
Re: C Compilers QoI supercat@casperkitty.com - 2017-03-16 16:14 -0700
Re: C Compilers QoI Robert Wessel <robertwessel2@yahoo.com> - 2017-03-16 22:54 -0500
Re: C Compilers QoI supercat@casperkitty.com - 2017-03-17 09:01 -0700
Re: C Compilers QoI Ian Collins <ian-news@hotmail.com> - 2017-03-26 14:16 +1300
Re: C Compilers QoI supercat@casperkitty.com - 2017-03-26 14:19 -0700
Re: C Compilers QoI BartC <bc@freeuk.com> - 2017-03-26 22:43 +0100
Re: C Compilers QoI GOTHIER Nathan <nathan.gothier@gmail.com> - 2017-03-27 01:28 +0200
Re: C Compilers QoI supercat@casperkitty.com - 2017-03-26 22:07 -0700
Re: C Compilers QoI BartC <bc@freeuk.com> - 2017-03-27 11:28 +0100
Re: C Compilers QoI supercat@casperkitty.com - 2017-03-27 07:38 -0700
Re: C Compilers QoI BartC <bc@freeuk.com> - 2017-03-27 16:23 +0100
Re: C Compilers QoI supercat@casperkitty.com - 2017-03-27 08:55 -0700
Re: C Compilers QoI BartC <bc@freeuk.com> - 2017-03-27 17:01 +0100
Re: C Compilers QoI supercat@casperkitty.com - 2017-03-27 10:03 -0700
Re: C Compilers QoI GOTHIER Nathan <nathan.gothier@gmail.com> - 2017-03-27 17:58 +0200
Re: C Compilers QoI already5chosen@yahoo.com - 2017-03-27 03:54 -0700
Re: C Compilers QoI supercat@casperkitty.com - 2017-03-27 08:46 -0700
Re: C Compilers QoI scott@slp53.sl.home (Scott Lurndal) - 2017-03-27 17:47 +0000
Re: C Compilers QoI supercat@casperkitty.com - 2017-03-27 11:48 -0700
Re: C Compilers QoI Robert Wessel <robertwessel2@yahoo.com> - 2017-03-27 15:37 -0500
Re: C Compilers QoI supercat@casperkitty.com - 2017-03-27 14:46 -0700
Re: C Compilers QoI Robert Wessel <robertwessel2@yahoo.com> - 2017-03-27 20:28 -0500
Re: C Compilers QoI supercat@casperkitty.com - 2017-03-28 01:18 -0700
Re: C Compilers QoI Robert Wessel <robertwessel2@yahoo.com> - 2017-03-28 18:24 -0500
Re: C Compilers QoI supercat@casperkitty.com - 2017-03-29 07:40 -0700
Re: C Compilers QoI David Brown <david.brown@hesbynett.no> - 2017-03-29 17:05 +0200
Re: C Compilers QoI supercat@casperkitty.com - 2017-03-29 11:07 -0700
Re: C Compilers QoI antispam@math.uni.wroc.pl - 2017-03-31 04:04 +0000
Re: C Compilers QoI bartc <bc@freeuk.com> - 2017-03-31 10:53 +0100
Re: C Compilers QoI Malcolm McLean <malcolm.mclean5@btinternet.com> - 2017-03-31 07:35 -0700
Re: C Compilers QoI supercat@casperkitty.com - 2017-03-31 08:07 -0700
Re: C Compilers QoI supercat@casperkitty.com - 2017-03-31 07:54 -0700
Re: C Compilers QoI supercat@casperkitty.com - 2017-03-31 07:43 -0700
Re: C Compilers QoI Ian Collins <ian-news@hotmail.com> - 2017-03-17 11:21 +1300
Re: C Compilers QoI Ian Collins <ian-news@hotmail.com> - 2017-03-17 11:24 +1300
Re: C Compilers QoI BartC <bc@freeuk.com> - 2017-03-16 22:15 +0000
Re: C Compilers QoI scott@slp53.sl.home (Scott Lurndal) - 2017-03-17 12:31 +0000
Re: C Compilers QoI already5chosen@yahoo.com - 2017-03-16 15:24 -0700
Re: C Compilers QoI supercat@casperkitty.com - 2017-03-16 16:03 -0700
Re: C Compilers QoI scott@slp53.sl.home (Scott Lurndal) - 2017-03-17 12:39 +0000
Re: C Compilers QoI already5chosen@yahoo.com - 2017-03-17 08:27 -0700
Re: C Compilers QoI antispam@math.uni.wroc.pl - 2017-03-16 01:35 +0000
Re: C Compilers QoI BartC <bc@freeuk.com> - 2017-03-16 02:18 +0000
Re: C Compilers QoI antispam@math.uni.wroc.pl - 2017-03-18 00:45 +0000
Re: C Compilers QoI BartC <bc@freeuk.com> - 2017-03-18 13:12 +0000
Re: C Compilers QoI antispam@math.uni.wroc.pl - 2017-03-18 20:31 +0000
Re: C Compilers QoI supercat@casperkitty.com - 2017-03-18 17:31 -0700
Re: C Compilers QoI supercat@casperkitty.com - 2017-03-16 09:22 -0700
Re: C Compilers QoI Nick Bowler <nbowler@draconx.ca> - 2017-03-24 16:13 +0000
Re: C Compilers QoI supercat@casperkitty.com - 2017-03-24 12:32 -0700
Re: C Compilers QoI Robert Wessel <robertwessel2@yahoo.com> - 2017-03-24 22:13 -0500
Re: C Compilers QoI supercat@casperkitty.com - 2017-03-25 13:05 -0700
Re: C Compilers QoI Robert Wessel <robertwessel2@yahoo.com> - 2017-03-27 15:44 -0500
Re: C Compilers QoI supercat@casperkitty.com - 2017-03-27 14:51 -0700
Re: C Compilers QoI Robert Wessel <robertwessel2@yahoo.com> - 2017-03-27 20:31 -0500
Re: C Compilers QoI BartC <bc@freeuk.com> - 2017-03-14 17:26 +0000
Re: C Compilers QoI Andrew Haley <andrew29@littlepinkcloud.invalid> - 2017-03-15 12:02 -0500
Re: C Compilers QoI David Brown <david.brown@hesbynett.no> - 2017-03-14 15:00 +0100
Re: C Compilers QoI already5chosen@yahoo.com - 2017-03-14 07:36 -0700
Re: C Compilers QoI David Brown <david.brown@hesbynett.no> - 2017-03-14 15:57 +0100
Re: C Compilers QoI Andrey Tarasevich <andreytarasevich@hotmail.com> - 2017-03-14 08:11 -0700
Re: C Compilers QoI BGB <cr88192@hotmail.com> - 2017-03-29 23:51 -0500
Re: C Compilers QoI BartC <bc@freeuk.com> - 2017-03-14 15:28 +0000
Re: C Compilers QoI David Brown <david.brown@hesbynett.no> - 2017-03-14 21:41 +0100
Re: C Compilers QoI Keith Thompson <kst-u@mib.org> - 2017-03-14 09:26 -0700
Re: C Compilers QoI BartC <bc@freeuk.com> - 2017-03-14 18:23 +0000
Re: C Compilers QoI Keith Thompson <kst-u@mib.org> - 2017-03-14 12:05 -0700
Re: C Compilers QoI already5chosen@yahoo.com - 2017-03-14 09:35 -0700
Re: C Compilers QoI BartC <bc@freeuk.com> - 2017-03-14 17:08 +0000
Re: C Compilers QoI already5chosen@yahoo.com - 2017-03-14 10:24 -0700
Re: C Compilers QoI BartC <bc@freeuk.com> - 2017-03-14 17:34 +0000
Re: C Compilers QoI already5chosen@yahoo.com - 2017-03-14 11:55 -0700
Re: C Compilers QoI BartC <bc@freeuk.com> - 2017-03-14 19:03 +0000
Re: C Compilers QoI BartC <bc@freeuk.com> - 2017-03-14 19:06 +0000
Re: C Compilers QoI already5chosen@yahoo.com - 2017-03-14 12:10 -0700
Re: C Compilers QoI BartC <bc@freeuk.com> - 2017-03-14 21:14 +0000
Re: C Compilers QoI already5chosen@yahoo.com - 2017-03-14 14:42 -0700
Re: C Compilers QoI supercat@casperkitty.com - 2017-03-14 14:53 -0700
Re: C Compilers QoI BartC <bc@freeuk.com> - 2017-03-14 23:20 +0000
Re: C Compilers QoI antispam@math.uni.wroc.pl - 2017-03-15 02:43 +0000
Re: C Compilers QoI jacobnavia <jacob@jacob.remcomp.fr> - 2017-03-14 19:39 +0100
Re: C Compilers QoI BartC <bc@freeuk.com> - 2017-03-14 19:10 +0000
Re: C Compilers QoI antispam@math.uni.wroc.pl - 2017-03-14 19:29 +0000
Re: C Compilers QoI Noob <root@127.0.0.1> - 2017-03-15 09:27 +0100
Re: C Compilers QoI ed_davis2@yahoo.com - 2017-03-16 15:10 -0700
Re: C Compilers QoI BartC <bc@freeuk.com> - 2017-03-16 23:19 +0000
csiph-web