Re: compiler bugs

Chris F Clark <cfc@shell01.TheWorld.com>
Thu, 07 May 2009 12:55:17 -0400

          From comp.compilers

Related articles
[20 earlier articles]
Re: compiler bugs cdg@nullstone.com (Christopher Glaeser) (2009-05-04)
Re: compiler bugs anton@mips.complang.tuwien.ac.at (2009-05-05)
Re: compiler bugs gah@ugcs.caltech.edu (glen herrmannsfeldt) (2009-05-05)
Re: compiler bugs gah@ugcs.caltech.edu (glen herrmannsfeldt) (2009-05-05)
Re: compiler bugs cdg@nullstone.com (Christopher Glaeser) (2009-05-06)
Re: compiler bugs anton@mips.complang.tuwien.ac.at (2009-05-06)
Re: compiler bugs cfc@shell01.TheWorld.com (Chris F Clark) (2009-05-07)
Re: compiler bugs barry.j.kelly@gmail.com (Barry Kelly) (2009-05-10)
Re: compiler bugs anton@mips.complang.tuwien.ac.at (2009-05-10)
Re: behavior-preserving optimization in C, was compiler bugs cdg@nullstone.com (Christopher Glaeser) (2009-05-12)
Re: behavior-preserving optimization in C, was compiler bugs anton@mips.complang.tuwien.ac.at (2009-05-13)
Re: behavior-preserving optimization in C, was compiler bugs dnovillo@acm.org (Diego Novillo) (2009-05-15)
Re: behavior-preserving optimization in C, was compiler bugs cdg@nullstone.com (Christopher Glaeser) (2009-05-15)
[21 later articles]
| List of all articles for this month |

From: Chris F Clark <cfc@shell01.TheWorld.com>
Newsgroups: comp.compilers
Date: Thu, 07 May 2009 12:55:17 -0400
Organization: The World Public Access UNIX, Brookline, MA
References: 09-04-072 09-04-086 09-05-010 09-05-022 09-05-028 09-05-038 09-05-039
Keywords: optimize, debug
Posted-Date: 09 May 2009 18:52:30 EDT

While I hate disagreeing with you Anton, what you suggest here isn't
necessarily practical, at least not in all cases.


anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:


> "Christopher Glaeser" <cdg@nullstone.com> writes:
> [Anton Ertl:]
>>> the optimizer should preserve the behaviour of the non-optimizing
>>> compiler.
>>
>>In a language like C, the behavior of programs that reference
>>uninitialized variables can be affected by the slightest change to
>>register assignments.
>
> Not if the unoptimizing compiler initializes all variables to some
> known value.


The problem with this solution is that there is at least 1 well-known
algorithmic trick that doesn't work in this case. It is a way to
initialize a large unbounded array efficiently, when you only use a
portion of the array in your algorithhm. However, it depends upon
being able to not actually initialize the array for the unused
sections. You find a way to map the array such that you can track the
"highest" element used and when accessing the array, you compare the
element you are about to use with the highest element initialized so
far, and if it is beyond the bound, you initialize enough elements to
cover the element you are accessing and update your tracker.


I don't know of any optimizers that will insert that kind of trick in
ones code. I don't know of optimizers that will replace bubble-sort
with quick-sort either.


So, if you have an algorithm that needs a trick like the above to meet
its performance promises, then the unoptimizing compiler breaks your
algorithm (and we don't have a well-known optimization technique that
fixes that breakage).


Now, your point about stability is well taken. Most programmers would
prefer that they can be blindly cavalier about memory usage and
uninitialized values would simply always be zero. It makes a lot of
off-by-one errors benign. However, that freedom comes at a price, one
that is often unacceptable. Yes, you can zero stack frames on every
procedure entry, but if someone starts putting large auotmatic arrays
on the stack, the performance can drop steeply.


I don't know of (nor believe there even is) a general solution to the
problem. That's why we have both C and SML and Lisp and ..., which
are all very different solutions to the problem, with different
tradeoffs.


Yes, one can design a language that is safe, but every attempt to do
so, has restricted the language such that certain short-cuts that may
be generally unsafe, but can be safe in certain instances, are
prohibited. The question then is whether those short-cuts are
required in ones application.


-Chris


******************************************************************************
Chris Clark Internet: christopher.f.clark@compiler-resources.com
Compiler Resources, Inc. or: compres@world.std.com
23 Bailey Rd Web Site: http://world.std.com/~compres
Berlin, MA 01503 voice: (508) 435-5016
USA fax: (978) 838-0263 (24 hours)


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.