don't short-circuit chained comparisons

[StefanKarpinski]

It's harder to lower, more surprising and usually less efficient. We should just lower a < b < c to (a < b) & (b < c).

[stevengj]

I wasn't even aware that these short-circuit, but I see that it is documented in the manual. (I guess it comes from Python?) Somehow I doubt that many programs rely on this, but I don't know how to go about doing a survey.

[stevengj]

The manual says "However, the order of evaluations in a chained comparison is undefined". This makes the short-circuit behavior useless anyway, so you might as well get rid of it. Any code that relies on the short-circuit behavior is probably broken anyway, thanks to the undefined order.

[ArchRobison]

I'm not sure about the efficiency trade-off. Assuming short-circuit (lazy) semantics, several cases come to mind for a() < b() < c():

• Evaluation of c() is expensive, and therefore short-circuiting wins.
• Evaluation of c() is cheap, and therefore the extra branch is the overriding cost. But if c() is that cheap, it's probably all inline and the compiler can estimate its cost fairly well, leading to two subcases of concern:
  • c() is provably safe to evaluate unnecessarily. Then the compiler can convert short-circuit to eager evaluation. (I've worked on a compiler that did this, but I'm not sure about LLVM.)
  • c() is not provably safe to evaluate unnecessarily. Common examples are indirect load off a possibly null pointer or possible divide by zero. Not being able to evaluate c() unnecessarily can hurt vectorization on machines without predication (e.g. won't be a problem for AVX-512, but can be a problem for SSE/AVX.).

For the last case, there is also a flow-analysis loss for lazy evaluation: with evaluation of c() uncertain, subsequent evaluations "downstream" cannot be proven to be redundant. But modern partial-redundancy elimination (PRE) techniques deal with that. (I'm not sure what the state of PRE is in LLVM. It seemed to be missing from LLVM 3.3 from what I recall.)

Maybe we could add a switch to control lazy versus eager evaluation of chained comparisons and see what the impact is on current benchmarks of interest?

[ArchRobison]

With respect to "order of evaluations in a chained comparison is undefined", I'd be in favor nailing down the order, regardless of whether we decide on eager or lazy evaluation, because having the order differ in different implementations can cause a lot of pain. The optimization advantages of undefined order, useful on ye olde PDP 11 seem to have evaporated with modern compilers. Even the C++ committee is seriously considering nailing down the order.

[StefanKarpinski]

Then the compiler can convert short-circuit to eager evaluation.

@ArchRobison: if LLVM was better at doing this, I would agree with your analysis, but it seems to either never do this or be very bad at it. Perhaps that's effectively agreement since LLVM could be improved to make this argument go through. Similarly for the second subcase.

I wholeheartedly agree about making the order of evaluation defined.

[stevengj]

I would think that a lot of chained comparisons in practice are safe to evaluate unnecessarily, e.g. 0 < i ≤ n and similar are probably very common. I just checked, and LLVM 3.7.1 in Julia 0.5 is not able to convert short-circuit to eager evaluation in 0 < i ≤ n for Int types.

In the case where one of the operands is very expensive to evaluate unnecessarily, one can always write && explicitly. Of course, in the current situation you could always write & explicitly, but eager evaluation seems like a better default to me since "cheap" operands are probably more common if I had to guess (assuming eager is faster in that case) . Of course, it would be even better if LLVM were just smarter.