Path: utzoo!utgpu!water!watmath!clyde!rutgers!mit-eddie!uw-beaver!tikal!amc!pilchuck!dataio!bright
From: bright@Data-IO.COM (Walter Bright)
Newsgroups: comp.lang.c
Subject: Re: "logical" xor
Message-ID: <1459@dataio.Data-IO.COM>
Date: 13 Jan 88 18:45:20 GMT
References: <2946@zeus.TEK.COM> <195@fxgrp.UUCP> <2800@killer.UUCP> <2237@haddock.ISC.COM>
Reply-To: bright@dataio.UUCP (Walter Bright)
Organization: Data I/O Corporation; Redmond, WA
Lines: 29

In article <2237@haddock.ISC.COM> karl@haddock.ima.isc.com (Karl Heuer) writes:
>Conclusion 2: If the compiler knows that both operands are normalized
>booleans, then "x^y" and "x!=y" can generate the same code.
>Would any compiler-writers out there care to comment on
>whether they've implemented this optimization?

It is not implemented in my compiler, nor in any that I've seen. In general,
flow analysis in optimizers is limited to determining things like:
	. x is/isn't always 3 at this point
	. x is/isn't always the same value as y at this point
I have seen many postings to the effect that the compiler should be able
to determine things like:
	. x is/isn't never the same value as y at this point
	. (x > 3 && x < 74) at this point
	. (some expression of arbitrary complexity) defines the possible
	  values of x at this point
Performing the flow analysis to gather the above types of information about
a variable is a research topic. I saw a paper on it once, but no actually
implemented algorithms. A compiler that implemented such analysis would
probably use an order of magnitude more memory than a conventional optimizer
and would run for an order of magnitude longer time. In other words, it's
not commercially practical currently.

Compilers do, however, make use of range information based on the variable's
type. To implement the optimization (x!=y) => (x^y), a new built-in boolean
type would have to be introduced (I am NOT proposing this). Also, a
conventional compiler could do ((a || b) != !c) => ((a || b) ^ !c), though
the number of cases where this appears is insufficient to warrant the overhead
of the test for it.