Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compilers > #2188 > unrolled thread

Optimization techniques

Back to article view | Back to comp.compilers

Contents

  Optimization techniques "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2019-04-17 09:42 -0400
    Re: Optimization techniques Hans Aberg <haberg-news@telia.com> - 2019-04-17 18:11 +0200
    Re: Optimization techniques George Neuner <gneuner2@comcast.net> - 2019-04-18 04:07 -0400
      Re: Optimization techniques "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2019-04-18 11:22 -0400
        Re: Optimization techniques George Neuner <gneuner2@comcast.net> - 2019-04-19 15:48 -0400
      Re: Optimization techniques Hans Aberg <haberg-news@telia.com> - 2019-04-19 00:52 +0200
    Re: Optimization techniques Kaz Kylheku <847-115-0292@kylheku.com> - 2019-04-19 08:49 +0000
      Re: Optimization techniques "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2019-04-19 11:48 -0400
        Re: Optimization techniques David Brown <david.brown@hesbynett.no> - 2019-04-23 09:38 +0200
      Re: Optimization techniques David Brown <david.brown@hesbynett.no> - 2019-04-23 09:18 +0200
    Re: Optimization techniques Hans-Peter Diettrich <DrDiettrich1@netscape.net> - 2019-04-20 00:27 +0200
      Re: Optimization techniques "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2019-04-19 16:11 -0700
        Re: Optimization techniques Hans-Peter Diettrich <DrDiettrich1@netscape.net> - 2019-04-20 19:47 +0200
          Re: Optimization techniques "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2019-04-24 10:16 -0400
      Re: Optimization techniques George Neuner <gneuner2@comcast.net> - 2019-04-20 18:59 -0400
      Re: Optimization techniques David Brown <david.brown@hesbynett.no> - 2019-04-23 09:43 +0200
        Re: Optimization techniques Martin Ward <martin@gkc.org.uk> - 2019-04-26 20:10 +0100
          Re: Optimization techniques Kaz Kylheku <847-115-0292@kylheku.com> - 2019-04-26 21:11 +0000
          Re: Optimization techniques David Brown <david.brown@hesbynett.no> - 2019-04-28 17:22 +0200
            Re: Optimization techniques Gene Wirchenko <genew@telus.net> - 2019-04-30 18:07 -0700
              Re: Optimization techniques David Brown <david.brown@hesbynett.no> - 2019-05-01 09:03 +0200
      Re: Optimization techniques "Derek M. Jones" <derek@_NOSPAM_knosof.co.uk> - 2019-04-26 13:39 +0100
    Re: Optimization techniques rockbrentwood@gmail.com - 2019-09-26 20:35 -0700

Page 1 of 2  [1] 2  Next page →

#2188 — Optimization techniques

Are there resources someone can point me to for learning more about
time-honored, long-established, safely applied, optimization
techniques for a C/C++ like language?

I'm walking the abstract syntax tree and am able to find many kinds of
optimizations, but I would like to learn some theory or pitfalls of
various types of optimizations applied.

Thank you in advance.

--
Rick C. Hodgin
[I'd think this would be in all the usual textbooks.  The
wikipedia article on Optimizing Compiler has a fairly good
discussion of them. -John]

[toc] | [next] | [standalone]

#2189

On 2019-04-17 15:42, Rick C. Hodgin wrote:
> Are there resources someone can point me to for learning more about
> time-honored, long-established, safely applied, optimization
> techniques for a C/C++ like language?

You might pick down LLVM and check its passes.
   https://llvm.org/docs/WritingAnLLVMPass.html

[toc] | [prev] | [next] | [standalone]

#2190

On Wed, 17 Apr 2019 09:42:21 -0400 (EDT), "Rick C. Hodgin"
<rick.c.hodgin@gmail.com> wrote:

>Are there resources someone can point me to for learning more about
>time-honored, long-established, safely applied, optimization
>techniques for a C/C++ like language?

There really aren't many "safe" optimizations you can do before you
run into pointer aliasing problems in C.  Almost any modern compiler
text will cover the bulk of them.

The "Dragon" books by Aho & Sethi (and others) are very good ... I
have a couple of them ... but my favorite intro book is:

  Cooper & Torczon, "Engineering a Compiler", Morgan Kaufman

I have the 1st edition. There is a 2nd edition now.  Very well written
and quite advanced for an introduction.


There are a lot of good intro level compiler texts.  I suggest you
find one that you think is easy to read.  The writing style is as
important to your learning as what information is presented.


>I'm walking the abstract syntax tree and am able to find many kinds of
>optimizations, but I would like to learn some theory or pitfalls of
>various types of optimizations applied.
>
>Thank you in advance.

If you are seriously interested, I'd like to suggest:

  Allen & Kennedy, "Optimizing Compilers for Modern Architectures",
    Academic Press, 2002.

Be aware that this book may be rough sledding.  Most performance
optimizations have their roots in *Fortran* - not C - and this book
deals with high performance Fortran.  Once you understand what they
are doing, it's not terribly hard to figure out how you'd handle it
with C, but it won't be spelled out for you.  This book is graduate
level, and I am not aware of anything similar that is C oriented.


Looking into an existing C compiler to see what it does may be more
confusing than enlightening if you are lacking some prerequisites. You
should understand the "single static assignment" (SSA) code
transformation.  You should know some graph theory - particularly
domination, matching and fusion.  You should understand how to
identify location aliasing (not just by pointers directly, but also
aliasing within memory blocks they refer to).  You need a good
understanding of C's aliasing rules, which take into account not just
data location but also data type(s).

And you need to understand what *shoudn't* be done with floating
point. Floating point operations do not commute, so in general you
can't reorder operations or spill register temporaries without
affecting the result.  Some understanding of numerical analysis is
recommended.


Any modern compiler text should cover SSA.  Alias identification is
touched on in some texts, but I personally have not seen a really
thorough treatment outside of Allen & Kennedy.  If you can interpolate
from the Fortran based discussion, everything you need to know is
there.

C's aliasing rules: you really need to get a copy of the standard
document - they aren't in any other text that I am aware of.

Floating point: if you can get a copy of IEEE-754 (2008), it talks
about what optimizations are possible.  Again, this is not light
reading.  Some further reading is suggested at:
https://en.wikipedia.org/wiki/IEEE_754


Hope this helps.
George
[Great reading list, thanks.  Floating add and multiply commute but
they don't associate.  a+b should be the sams as b+a, but (a+b)+c not
the same as a+(b+c).  -John]

[toc] | [prev] | [next] | [standalone]

#2191

On 4/18/2019 4:07 AM, George Neuner wrote:
> On Wed, 17 Apr 2019 09:42:21 -0400 (EDT), "Rick C. Hodgin"
> <rick.c.hodgin@gmail.com> wrote:
>
>> Are there resources someone can point me to for learning more about
>> time-honored, long-established, safely applied, optimization
>> techniques for a C/C++ like language?
>
> There really aren't many "safe" optimizations you can do before you
> run into pointer aliasing problems in C.  Almost any modern compiler
> text will cover the bulk of them.

I'm not sure what that is by its name, but I'll start there.  Thank
you, George.

> [Great reading list, thanks.  Floating add and multiply commute but
> they don't associate.  a+b should be the sams as b+a, but (a+b)+c not
> the same as a+(b+c).  -John]

I think the goal for floating point engines in moving forward is no
longer to only be exceeding fast under IEEE-754 or its relatives, but
there should be a new model introduced into silicon which carries out
computations that are truly accurate, which either an arbitrary pre-
cision engine which will admittedly be slower and be accurate out only
to some finite degree and inaccurate beyond that, or some kind of sym-
bolic tree-based algorithm which doesn't actually conduct the final
computation until the tree has been updated to its final form, and is
then, and only then, computed, allowing for cancellations and reduc-
tions to be made, which I believe is what happens in apps like Maple
and Mathematica.

--
Rick C. Hodgin
[I think you're conflating different things in the FP stuff.  The
sorts of analysis that Maple and Mathematica do require looking
at potentially large amounts of data and deciding on the fly how
to do the calculations.  It might be reasonable to do some of that
in hardware, but I think most of it is too complicated.  -John]

[toc] | [prev] | [next] | [standalone]

#2195

Our esteemed moderator wrote:

>> [Great reading list, thanks.  Floating add and multiply commute but
>> they don't associate.  a+b should be the sams as b+a, but (a+b)+c not
>> the same as a+(b+c).  -John]

Yes, I was mistaken. Thanks for posting the clarification.

George

[toc] | [prev] | [next] | [standalone]

#2192

On 2019-04-18 10:07, John Levine wrote:
> [Great reading list, thanks.  Floating add and multiply commute but
> they don't associate.  a+b should be the sams as b+a, but (a+b)+c not
> the same as a+(b+c).  -John]

Actually, LLVM has an optimization assuming associativity, which is
legit with sufficiently high precision.

[toc] | [prev] | [next] | [standalone]

#2193

On 2019-04-17, R. C. Hodgin <rick.c.hodgin@gmail.com> wrote:
> Are there resources someone can point me to for learning more about
> time-honored, long-established, safely applied, optimization
> techniques for a C/C++ like language?

Optimization only preserves the meaning of the program to the extent
that the program has a defined meaning, as far as the compiler is
concerned.

Thus, there is one huge pitfall in optimizing C or C++: there is a large
space of possible programs that have unspecified or undefined semantics,
and that programmers actually write.

If you can make your language "C/C++ like" without all the undefined
behavior looming at every corner (i.e. not actually "C/C++ like" at all
in a significant regard), then you've dodged what is probably the number one
optimization pitfall.

For instance, don't have it so that the order of evaluation of
function or operator arguments is unspecified. If you allow side-effects
in expressions, specify when those effects take place in relation to
everything else in the expression.

If you have clear ordering rules, then you honor them when optimizing:
you rearrange the user's calculation order only when it can't possibly
make a difference to the result that is required by the defined
order.

Reordering arithmetic calculations has pitfalls. There are n! orders
for adding together n numbers. Under floating-point, these all
potentially return different results even if nothing overflows.
You can't blindly rely on arithmetic identities to hold.

[toc] | [prev] | [next] | [standalone]

#2194

On 4/19/2019 4:49 AM, Kaz Kylheku wrote:
> If you can make your language "C/C++ like" without all the undefined
> behavior looming at every corner (i.e. not actually "C/C++ like" at all
> in a significant regard), then you've dodged what is probably the number one
> optimization pitfall.

I think UB is unavoidable in any C/C++ language.  It is too low-level
for speed purposes to be bogged down with things that would prevent UB.
Even something simple like pointer use after free.  It can be difficult
to catch statically.

> For instance, don't have it so that the order of evaluation of
> function or operator arguments is unspecified. If you allow side-effects
> in expressions, specify when those effects take place in relation to
> everything else in the expression.
>
> If you have clear ordering rules, then you honor them when optimizing:
> you rearrange the user's calculation order only when it can't possibly
> make a difference to the result that is required by the defined
> order.

I do have very clear ordering rules.  I'm actually surprised to learn
that other systems do not.  I would've thought it would be absolutely
essential.

> Reordering arithmetic calculations has pitfalls. There are n! orders
> for adding together n numbers. Under floating-point, these all
> potentially return different results even if nothing overflows.
> You can't blindly rely on arithmetic identities to hold.

I think people who use floating point recognize it is not an exact
numbering system.

I have introduced native support for arbitrary precision integers
(bi) and floating point (bfp) to address this, but even then it's
still limited precision and not exact.

--
Rick C. Hodgin

[toc] | [prev] | [next] | [standalone]

#2201

On 19/04/2019 17:48, Rick C. Hodgin wrote:
> On 4/19/2019 4:49 AM, Kaz Kylheku wrote:
>> If you can make your language "C/C++ like" without all the undefined
>> behavior looming at every corner (i.e. not actually "C/C++ like" at all
>> in a significant regard), then you've dodged what is probably the
>> number one
>> optimization pitfall.
>
> I think UB is unavoidable in any C/C++ language.  It is too low-level
> for speed purposes to be bogged down with things that would prevent UB.
> Even something simple like pointer use after free.  It can be difficult
> to catch statically.
>
>> For instance, don't have it so that the order of evaluation of
>> function or operator arguments is unspecified. If you allow side-effects
>> in expressions, specify when those effects take place in relation to
>> everything else in the expression.
>>
>> If you have clear ordering rules, then you honor them when optimizing:
>> you rearrange the user's calculation order only when it can't possibly
>> make a difference to the result that is required by the defined
>> order.
>
> I do have very clear ordering rules.  I'm actually surprised to learn
> that other systems do not.  I would've thought it would be absolutely
> essential.
>

No, it is not.  In C, there is the concept of "sequence points".  This
has got more complicated in C11 with the handling of multiple threads,
but in C99 (and single-threaded C11) these are points which define the
order of operations.  (Just the logical order - the actual generated
code order can vary, according to the "as if" rule.)

But between sequence points, operations can be carried out in any order
that suits the compiler.  Given "x = A + B;", the expressions "A" and
"B" can be evaluated in any order.

If you have this code:

int x = 0;
int nextX(void) {
	x++;
	return x;
}

void foo(void) {
	printf("%i, %i, %i\n", nextX(), nextX(), nextX());
}

then the compile can give "1, 2, 3", or "3, 2, 1", or (less likely, but
legal) other orders such as "1, 3, 2".

(C++ has recently fixed the ordering of evaluation of function
arguments, but that does not apply to C.  And it does not apply to other
orderings between sequence points.)

Of course, a language following the same basic principles as C could
simply say that the comma between arguments in a function call act as
sequence points - then their evaluation order will be fixed.


>> Reordering arithmetic calculations has pitfalls. There are n! orders
>> for adding together n numbers. Under floating-point, these all
>> potentially return different results even if nothing overflows.
>> You can't blindly rely on arithmetic identities to hold.
>
> I think people who use floating point recognize it is not an exact
> numbering system.

You'd be surprised - many who take floating point seriously are looking
for absolutely repeatable results, consistent across different systems.
 There is a difference between knowing the results are not perfect
matches for mathematical "real" numbers, and wanting the floating point
calculations to follow the IEEE rules precisely.  People do take care to
write "a + (b + c)" or "(a + b) + c" because they know that one version
gives more precision in their results.  Compilers can't (usually) get
that same knowledge - they have to trust the programmer.

(Or you can have a "fast fp mode" which allows freer optimisation and
re-arrangements.)

>
> I have introduced native support for arbitrary precision integers
> (bi) and floating point (bfp) to address this, but even then it's
> still limited precision and not exact.

[toc] | [prev] | [next] | [standalone]

#2200

On 19/04/2019 10:49, Kaz Kylheku wrote:
> On 2019-04-17, R. C. Hodgin <rick.c.hodgin@gmail.com> wrote:
>> Are there resources someone can point me to for learning more about
>> time-honored, long-established, safely applied, optimization
>> techniques for a C/C++ like language?
>
> Optimization only preserves the meaning of the program to the extent
> that the program has a defined meaning, as far as the compiler is
> concerned.

Yes.

>
> Thus, there is one huge pitfall in optimizing C or C++: there is a large
> space of possible programs that have unspecified or undefined semantics,
> and that programmers actually write.

Here you face the balance between giving good optimisation to people
that write correct code (i.e., no undefined behaviour) and giving "what
people probably expect" behaviour to people who don't follow those
rules.  It is not an easy balance.

Most compilers solve this with flags - the programmer can choose between
"I know what I am doing - trust me and give me efficient code" and "I
don't know how C works, and think it does naïve translations - don't
optimise".  Most also give flags for "Let me know if you see me doing
something silly, even if it is legal".  And some good ones give you
flags for "I know how C works, but I'd like to change it slightly".

There is no way to please all users with a compiler for C or C++.
Flags, and possibly pragmas, are the only way to do it.  Some people
will still complain, of course - they want C to work they way /they/
imagine it should, they want the compiler to guess what their code means
even when it is undefined behaviour (i.e., has no meaning in C), and
they want the compiler to optimise perfectly based on that mind-reading.
 But most should be happy enough if you give them choices.

I'd personally prefer if compilers had more warnings enabled by default.
 That can be hard to change for an existing tool that needs
compatibility, but new tools could be freer here.

>
> If you can make your language "C/C++ like" without all the undefined
> behavior looming at every corner (i.e. not actually "C/C++ like" at all
> in a significant regard), then you've dodged what is probably the number one
> optimization pitfall.

And if you think that is possible, then I have a bridge to sell you.

There are some undefined behaviours in C that should be eliminated, as
they could be detected strictly at compile time with more sophisticated
tools and more advanced sharing of information between separate
translation units.  For example, it should be possible to eliminate
mixups of parameter types and numbers for functions defined in one unit
and called in another.  (It would help if old-style unprototyped calls
were banned, as they are in C++.)

There are some undefined behaviours in C that cannot be eliminated.
Accessing data via an invalid pointer, such as running over the end of a
buffer, is always going to be undefined.  With enough effort and
inefficiencies, run-time checking can reduce these a bit, but not remove
them.  You can't ever get all cases, no matter how inefficient you are
willing to be.

There are some things (mostly unspecified or implementation dependent,
rather than undefined behaviour) that could be tightened if you are
happy to restrict the targets for the language.  C is used on many odd
systems, but a new C-like language could easily fix the sizes of integer
types and that sort of thing.

And there are undefined behaviours which could be given definitions, but
doing so is not actually a positive thing.  The prime example is signed
integer overflow.  Since overflowing your integers is almost always an
error in the code anyway, there are no benefits in giving it defined
behaviour.  On the other hand, defining its behaviour restricts many
optimisations (especially simplification of expressions) and hinders the
compiler from warning you about said errors.  A possible middle ground
would be to say that signed integer overflow gives unspecified results -
operations will always give you an integer, but if there is no correct
result, then any integer will do.  This will allow many optimisations to
be done while blocking the most surprising ones (like time-travelling
optimisations).

Note also that just as executing undefined behaviours is always a bug in
the user code, bugs in the user code are also undefined behaviours when
you take a wider view - and good luck designing a programming language
in which no one has bugs in their code.


>
> For instance, don't have it so that the order of evaluation of
> function or operator arguments is unspecified. If you allow side-effects
> in expressions, specify when those effects take place in relation to
> everything else in the expression.

That is unspecified behaviour, not undefined behaviour.  It could be
specified in the language, but that might limit certain optimisations -
you'd have to be careful.

>
> If you have clear ordering rules, then you honor them when optimizing:
> you rearrange the user's calculation order only when it can't possibly
> make a difference to the result that is required by the defined
> order.

Certainly.  Optimisations should not change the meaning of correct code.

>
> Reordering arithmetic calculations has pitfalls. There are n! orders
> for adding together n numbers. Under floating-point, these all
> potentially return different results even if nothing overflows.
> You can't blindly rely on arithmetic identities to hold.
>

One of the advantages of signed integer arithmetic being undefined in C
is that for those types, you /can/ blindly rely on arithmetic
identities.  It is a lot harder if you have defined behaviour.

IEEE floating point has complicated rules for rounding and ordering,
severely restricting optimisations.  Many compilers have switches to
enable a "looser" mode for floating point which can give massive
speed-ups in fp-heavy code.

[toc] | [prev] | [next] | [standalone]

#2196

Am 17.04.2019 um 15:42 schrieb Rick C. Hodgin:
> Are there resources someone can point me to for learning more about
> time-honored, long-established, safely applied, optimization
> techniques for a C/C++ like language?

I'm always a bit sceptic when C/C++ and "safe" occur in the same
sentence. AFAIR a C compiler is allowed to ignore parentheses when
reordering expressions, what can lead to numeric instabilities.

DoDi

[toc] | [prev] | [next] | [standalone]

#2197

On Friday, April 19, 2019 at 7:04:51 PM UTC-4, Hans-Peter Diettrich wrote:
> Am 17.04.2019 um 15:42 schrieb Rick C. Hodgin:
> > Are there resources someone can point me to for learning more about
> > time-honored, long-established, safely applied, optimization
> > techniques for a C/C++ like language?
>
> I'm always a bit sceptic when C/C++ and "safe" occur in the same
> sentence. AFAIR a C compiler is allowed to ignore parentheses when
> reordering expressions, what can lead to numeric instabilities.

In my language that is not allowed.  The order of operations,
as dictated by the developer, are honored.  A feature has to
be enabled to allow that kind of reordering.

My language focuses on data correctness, not speed.  Computers
today are fast enough for 99% of general purpose apps.  It's
time for them to mature into data correctness in all areas.

--
Rick C. Hodgin

[toc] | [prev] | [next] | [standalone]

#2198

Am 20.04.2019 um 01:11 schrieb Rick C. Hodgin:

> My language focuses on data correctness, not speed.  Computers
> today are fast enough for 99% of general purpose apps.  It's
> time for them to mature into data correctness in all areas.

Did you have a look at Ada and Pascal implementations?

I also have been told that certified Java compilers (for µC) are
guaranteed to produce bit-identical results on all supported platforms.

DoDi

[toc] | [prev] | [next] | [standalone]

#2203

On 4/20/2019 1:47 PM, Hans-Peter Diettrich wrote:
> Am 20.04.2019 um 01:11 schrieb Rick C. Hodgin:
>
>> My language focuses on data correctness, not speed.  Computers
>> today are fast enough for 99% of general purpose apps.  It's
>> time for them to mature into data correctness in all areas.
>
> Did you have a look at Ada and Pascal implementations?

I've looked at Pascal, but never Ada.  My own language actually takes
some cues from Pascal's way of maintaining data integrity in the
presence of errant code, but still relaxes everything so you can still
truly shoot your program in its figurative foot.

> I also have been told that certified Java compilers (for µC) are
> guaranteed to produce bit-identical results on all supported platforms.

C and C++ can often do this as well as the CPUs that exist are often
either truly IEEE-754 compliant, or have the ability to be so (such as
with x86 where you must do an intermediate store and re-load to have
appropriate (legal IEEE-754) rounding).

--
Rick C. Hodgin

[toc] | [prev] | [next] | [standalone]

#2199

On Sat, 20 Apr 2019 00:27:11 +0200, Hans-Peter Diettrich
<DrDiettrich1@netscape.net> wrote:

>I'm always a bit sceptic when C/C++ and "safe" occur in the same
>sentence. AFAIR a C compiler is allowed to ignore parentheses when
>reordering expressions, what can lead to numeric instabilities.

By the standard, a C compiler IS required to respect parentheses
within an arithmetic expression. But even fully parenthesized
expressions contain subexpressions whose evaluations can be reordered.

e.g., (a + (b + c)) has to be equivalent to

  t1 = b + c
  t2 = a + t1

but if any of a, b, or c is an expression itself - e.g., a pointer
dereference - the parenthesized expression does not imply any ordering
of *their* individual evaluations.

George

[toc] | [prev] | [next] | [standalone]

#2202

On 20/04/2019 00:27, Hans-Peter Diettrich wrote:
> Am 17.04.2019 um 15:42 schrieb Rick C. Hodgin:
>> Are there resources someone can point me to for learning more about
>> time-honored, long-established, safely applied, optimization
>> techniques for a C/C++ like language?
>
> I'm always a bit sceptic when C/C++ and "safe" occur in the same
> sentence.

C and C++ can certainly be used safely.  But the programmer needs to
know what they are doing, and want to write safe code.

> AFAIR a C compiler is allowed to ignore parentheses when
> reordering expressions, what can lead to numeric instabilities.

For floating point operations, such re-arrangements could lead to
numeric instabilities - and they are not allowed.

For signed integer operations, brackets that affect calculations can't
be removed.  The compiler can't change "(a * b) / c" into "a * (b / c)".
 But mathematical identities such as associativity and commutativity are
valid because signed integer overflow does not happen - thus "a * (b +
c)" can be changed to "(a * b) + (a * c)".

And of course the evaluation of sub-expressions can be done in any order.

[toc] | [prev] | [next] | [standalone]

#2212

On 23/04/19 08:43, David Brown wrote:
> But mathematical identities such as associativity and commutativity are
> valid because signed integer overflow does not happen - thus "a * (b +
> c)" can be changed to "(a * b) + (a * c)".

If b is large and c has a value close to -b then a * (b + c)
might be OK while (a * b) will overflow and cause undefined
behaviour.

--
			Martin

Dr Martin Ward | Email: martin@gkc.org.uk | http://www.gkc.org.uk
G.K.Chesterton site: http://www.gkc.org.uk/gkc | Erdos number: 4

[toc] | [prev] | [next] | [standalone]

#2214

On 2019-04-26, Martin Ward <martin@gkc.org.uk> wrote:
> On 23/04/19 08:43, David Brown wrote:
>> But mathematical identities such as associativity and commutativity are
>> valid because signed integer overflow does not happen - thus "a * (b +
>> c)" can be changed to "(a * b) + (a * c)".
>
> If b is large and c has a value close to -b then a * (b + c)
> might be OK while (a * b) will overflow and cause undefined
> behaviour.

I.e. careless application of arithmetic identities can introduce
overflows that don't exist in the original form.

--
TXR Programming Lanuage: http://nongnu.org/txr
Music DIY Mailing List:  http://www.kylheku.com/diy
ADA MP-1 Mailing List:   http://www.kylheku.com/mp1

[toc] | [prev] | [next] | [standalone]

#2220

On 26/04/2019 21:10, Martin Ward wrote:
> On 23/04/19 08:43, David Brown wrote:
>> But mathematical identities such as associativity and commutativity are
>> valid because signed integer overflow does not happen - thus "a * (b +
>> c)" can be changed to "(a * b) + (a * c)".
>
> If b is large and c has a value close to -b then a * (b + c)
> might be OK while (a * b) will overflow and cause undefined
> behaviour.
>

You are right.  The compiler can go the other way, but not that way.  It
can ignore the possibility of overflows or other errors (like divide by
zero) in the expression you give it, but it can't manipulate things in a
way that might introduce new errors.

Obviously compiler writers are expected to pay more attention to these
details than someone making a Usenet post!

[toc] | [prev] | [next] | [standalone]

#2234

On Sun, 28 Apr 2019 17:22:26 +0200, David Brown
<david.brown@hesbynett.no> wrote:

[snip]

>Obviously compiler writers are expected to pay more attention to these
>details than someone making a Usenet post!

     What?  I can not trust the godlings in comp.compilers?

Sincerely,

Gene Wirchenko

[toc] | [prev] | [next] | [standalone]

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | comp.compilers

csiph-web