Xref: utzoo comp.arch:8457 comp.lang.misc:2695 comp.lang.c:16557
Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!ames!lll-winken!csd4.milw.wisc.edu!leah!rpi!batcomputer!cornell!rochester!pt.cs.cmu.edu!sei!sei.cmu.edu!firth
From: firth@sei.cmu.edu (Robert Firth)
Newsgroups: comp.arch,comp.lang.misc,comp.lang.c
Subject: Peephole optimisation
Message-ID: <8650@aw.sei.cmu.edu>
Date: 27 Feb 89 14:00:22 GMT
References: <740@tetons.UUCP> <76700068@p.cs.uiuc.edu> <671@oracle.oracle.com> <730@microsoft.UUCP> <1153@l.cc.purdue.edu>
Sender: netnews@sei.cmu.edu
Reply-To: firth@bd.sei.cmu.edu (Robert Firth)
Organization: Carnegie-Mellon University, SEI, Pgh, Pa
Lines: 37


	[ NOT (a OR b) => a NOR b ]

csimmons@oracle.UUCP (Charles Simmons) wrote:

   Since the 'nor' instruction doesn't directly map into the C language,
   I didn't really expect the compiler to handle this minor special case.)

w-colinp@microsoft.UUCP (Colin Plumb) writes:

   Really?  I do.  Since the sequence "or $c, $a, $b; not $c, $c" is
   exactly equivalent to "nor $c, $a, $b" and easily recognised by a
   peephole optimiser.

cik@l.cc.purdue.edu (Herman Rubin) writes:

   There is no question that in some cases a peephole optimizer can catch
   things like this.  But this requires that someone has anticipated the
   problem and built it into the optimizer.  And how big is the peephole?

Here's a data point; I rather think it supports everybody's thesis.
When the 'nor' idiom was first posted, I immediately tried it on my
MIPS codegenerator.  The 'nor' was not generated; the less efficient
'or' followed by 'not' came out.  So there's another compiler that
missed the good code.

However, the reason was very simple - I'd completely overlooked the
equivalence when writing the codegenerator.  So the failure was human
error.

Finally, the fix was equally simple: it was necessary to add one
more element to a lookup table in a specific part of the codegenerator,
that basically says [OR;NOT => NOR].

Of course, none of this matters if you have some automated way of
generating the peephole optimisation rules, which seems to me much the
best solution to the problem.