constant-propagation for @pure functions

[stevengj]

This is a followup to #414 and #13555. Thanks to @vtjnash, we now have an (undocumented) @pure annotation that is an (unchecked) assertion that a function is "pure". However, we don't have the constant-propagation/folding compiler passes to actually exploit this.

As @JeffBezanson suggested in #414, a pure function f(x) in Julia is one for which x===y ⟹ f(x)===f(y). Note that this is technically per-method rather than per-function, because e.g. sin(x) is pure if x is an immutable scalar, but not if x is an array or bigfloat.

Once constant-propagation is implemented, careful use of the @pure tag should allow expressions like log(2.0)^2, sin(3+4im), and convert(Float64, 1//2) to be evaluated at compile-time.

[jwmerrill]

Does Julia still have dynamic rounding modes? Is there a plan to deal with them somehow during constant propagation?

[stevengj]

@jwmerrill, other languages (C and Fortran) have dynamic control over the rounding mode, and I think they just do constant propagation in the default rounding mode. That is probably the only sane choice.

[StefanKarpinski]

Since we're not checking that @pure functions are actually pure, it would seem that's not really what it means. Instead, I think that a "pure" function is one which the compiler is free to call whenever it wants to. In particular, x === y ⟹ f(x) === f(y) isn't really sufficiently strict even if the compiler can prove it since the function might also have side effects. I think we need a few things:

1. If a function is "pure" what does that mean the compiler is free to do with it? I've proposed that this should mean that the compiler is free to call the function whenever it wants to, including never (or multiple times).
2. Conditions when the compiler can automatically infer that the a function can safely be considered "pure". If x === y ⟹ f(x) === f(y) and f has no side effects, that seems sufficient.

To me, the @pure annotation is a way of saying either "trust me, this function is pure in the latter sense" or "even if this function isn't really pure, I don't care when you call it" – both of which are useful.

[JeffBezanson]

Dup of #5560.

Like green-fairy, we should have a Const lattice element used by type inference. It would actually clean up a lot of the code at this point.

[elextr]

If the compiler does any automatic constant folding an annotation to tell it not to do so is going to be needed to allow changing rounding modes to have any effect.

[simonbyrne]

re: rounding modes, LLVM already does constant folding for basic arithmetic ops (e.g. define f() = 0.1 + 0.2), so I don't think we can really worry about this until LLVM #6050 is sorted out (I wouldn't hold my breath).

[simonbyrne]

Note also that LLVM offers other properties such as CannotBeOrderedLessThanZero: it would be useful if there was a way we could hook into those as well.

[stevengj]

@StefanKarpinski, I agree that in practice a @pure annotation should mean that the compiler can call the function as many times as it wants, whenever it wants. However, in most cases people should probably only use it if x===y ⟹ f(x)===f(y) and f has no side-effects, as otherwise the compiler results could be unpredictable.

[StefanKarpinski]

I agree that you probably only want to use the @pure annotation in those circumstances, but we often make it possible to poke around and see what the compiler does – e.g. by putting print statements in macros and generated functions. I think this should be no different and the clearest way to explain what the @pure macro means is to define what it gives the compiler liberty to do. Then if you put a print statement in there and see the output before you call the function, you can see when it's actually getting called.

[bramtayl]

It seems as if Base.select_value isn't know to be pure, or else isn't propagating constants correctly:

test(x, y) = ifelse(true, x, y)
@code_warntype test(1, "a")

[bramtayl]

test() = true & false
@code_warntype test()