Optimizations for boolean comparisons

[NDos Dannyu]

Please read the following Q&A I posted on Stack Overflow: http://stackoverflow.com/questions/40069217/comparison-operators-on-booleans-trick

As the answer "hvd" posted states, P < Q won't perform better than !P && Q, as well as the other comparison operators. So I think an optimization should be there.

More specifically, the right operand of a comparison operator shouldn't be evaluated if:

1. The left operand of < is evaluated to true, where the result will be always false,
2. The left operand of > is evaluated to false, where the result will be always false,
   
3. The left operand of <= is evaluated to false, where the result will be always true,
4. The left operand of >= is evaluated to true, where the result will be always true.

[D. B.]

AFAICT comparing booleans using < et al is possible because of implicit conversion to int, but should not be encouraged as a good means of comparing bools, which adding special-case optimisations would encourage.

[Thiago Macieira]

Em domingo, 16 de outubro de 2016, às 04:02:54 PDT, NDos Dannyu escreveu:
> 1. The left operand of *< *is evaluated to *true*, where the result will
> be always *false*,

K-map:
P\Q 0 1
0 0 1
1 0 0

Therefore, P<Q is the same as !P && Q, except that the current boolean
expression already has your short-circuiting request.

> 2. The left operand of *> *is evaluated to *false*, where the result
> will be always *false*,

P\Q 0 1
0 0 0
1 1 0

Therefore, this is the same as P && !Q.

> 3. The left operand of *<=* is evaluated to *false*, where the result
> will be always *true*,

P\Q 0 1
0 1 1
1 0 1

This is the same as !P || Q.

> 4. The left operand of *>=* is evaluated to *true*, where the result
> will be always *true*.

P\Q 0 1
0 1 0
1 1 1

This is the same as P || !Q.

--
Thiago Macieira - thiago (AT) macieira.info - thiago (AT) kde.org
Software Architect - Intel Open Source Technology Center

[John Yates]

Replying to the OP.

There are 16 function of 2 Boolean variable A and B.  Let us considered the cases:

• Some depend neither on A nor on B (false, and true).
• Some depend on only a single variable (A, !A, B, !B).
  
• Some can never be resolved by looking at a single variable (A==B, A!=B).
• The remaining 8 functions can sometimes be resolved by looking at only one variable.

In the case of the two most common functions (AND: & and OR: |) C++ provides direct support for explicit short-circuit semantics (&& and || respectively).  These come up frequently in situations where the expression need not be materialized because it is being used only as a control expression (e.g. verifying that a pointer is non-null before dereferencing it).  Unlike EXCLUSIVE-OR (A!=B) which has a inverse operator (==) AND and OR do not, neither in their fully applicative form nor in their short circuit form.  In such cases a programmer is reduced to applying DeMorgan.

Having accounted for 12 Boolean functions 4 remain (A<B, A<=B, A>B and A>=B).  I do write these occasionally but I never think of these in terms of short circuiting for correctness.  Instead I trust my compiler to optimize their evaluation.  That may involve not only choosing short-circuit evaluation but also potentially evaluating B before A.  As long as it achieves the correct result why should I care?

/john

[Nicol Bolas]

Actually, short-circuit evaluation is not allowed. Or at least, so long as B is something which the compiler cannot guarantee will have visible side effects, the compiler cannot choose not to evaluate it.

SCE is something people frequently rely on in boolean expressions. It's used to do things like `if(ptr && ptr->foo())`. That only works if `ptr` being NULL guarantees that `ptr->foo()` is never evaluated.

Now to be fair, I think the OP's idea is wrong for precisely that reason. Namely... how often can you actually structure your code where SCE can work with A < B, where both `A` and `B` are boolean expressions? I'd like to see an example where SCE is needed. That is, show me a condition where you legitimately would use `A < B`, and the evaluation of `B` will lead to a runtime error/UB if `A` is not true.

And remember: both `A` and `B` must be actual boolean expressions (note that `ptr` in my above example is not a boolean expression).