De Morgan's Law optimization with overloaded operators

Every programmer should know that:

(De Morgan's Laws)

Under some circumstances, in order to optimize the program, it may happen that compiler modifies (!p && !q) to (!(p || q)).

The two expressions are equivalent, and it makes no difference evaluating the first or the second.
But in C++ it is possible to overload operators, and the overloaded operator may not always respect this property. So transforming the code this way will actually modify the code.

Should the compiler use De Morgan's Laws when !, || and && are overloaded?

Note that:

> Builtin operators && and || perform short-circuit evaluation (do not evaluate the second operand if the result is known after evaluating the first), but overloaded operators behave like regular function calls and always evaluate both operands. > > ... > Because the short-circuiting properties of operator&& and operator|| do not apply to overloads, and because types with boolean semantics are uncommon, only two standard library classes overload these operators ... > > Source: http://en.cppreference.com/w/cpp/language/operator_logical > (emphasis mine)

And that:

> If there is a user-written candidate with the same name and parameter types as a built-in candidate operator function, the built-in operator function is hidden and is not included in the set of candidate functions. > > Source: n4431 13.6 Built-in operators [over.built] (emphasis mine)

To summarize: overloaded operators behave like regular, user-written functions.

NO, the compiler will not replace a call of a user-written function with a call of another user-written function. Doing otherwise would potentially violate the "as if" rule.

I think that you have answered your own question: no, a compiler can not do this. Not only the operators can be overloaded, some can not be even defined. For example, you can have operator && and operator ! defined, and operator || not defined at all.

Note that there are many other laws that the compiler can not follow. For example, it can not change p||q to q||p, as well as x+y to y+x.

(All of the above applies to overloaded operators, as this is what the question asks for.)

No, in that case the transformation would be invalid. The permission to transform !p && !q into !(p || q) is implicit, by the as-if rule. The as-if rule allows any transformation that, roughly speaking, cannot be observed by a correct program. When overloaded operators are used and would detect the transformation, that automatically means the transformation is no longer allowed.

Overloaded operators per se are just syntactic sugar for function calls; the compiler itself is not allowed to make any assumption about the properties that may or may not hold for such calls. Optimizations that exploit properties of some specific operator (say, De Morgan's for boolean operators, commutativity for sums, distributivity for sum/product, transformation of integral division in an appropriate multiplication, ...) can be employed only when the "real operators" are used.

Notice instead that some parts of the standard library may associate some specific semantic meaning to overloaded operators - for example, std::sort by default expects an operator< that complies to a strict weak ordering between the elements - but this is of course listed in the prerequisites of each algorithm/container.

(incidentally, overloading && and || should probably be avoided anyway since they lose their short-circuiting properties when overloaded, so their behavior becomes surprising and thus potentially dangerous)

You are asking whether the compiler can arbitrarily rewrite your program to do something you did not write it to do.

The answer is: of course not!

• Where De Morgan's laws apply, they may be applied.
• Where they don't, they may not.

It's really that simple.

Not directly.

If p and q are expressions so that p does not have overloaded operators, short circuit evaluation is in effect: expression q is going to be evaluated only if p is false.

If p is of non-primitive type, there is no short circuit evaluation and overloaded function could be anything - even not related to the conventional usage.

Compiler will do its optimizations in its own way. Perhaps it might result de Morgan identities, but not on the level of if condition replacement.

DeMorgan's laws apply to the semantics of those operators. Overloading applies to the syntax of those operators. There is no guarantee that an overloaded operator implements the semantics that are needed for DeMorgan's laws to apply.

> But in C++ it is possible to overload operators, and the overloaded operator may not always respect this property.

Overloaded operator is no longer an operator, it is a function call.

class Boolean
{
  bool value;

  ..

  Boolean operator||(const Boolean& b)
  {
      Boolean c;
      c.value = this->value || b.value;
      return c;
  }

  Boolean logical_or(const Boolean& b)
  {
      Boolean c;
      c.value = this->value || b.value;
      return c;
  }
}

So this line of code

Boolean a (true);
Boolean b (false);

Boolean c = a || b;

is equivalent to this

Boolean c = a.logical_or(b);