Branch on whether a value is known to the compiler

Internals & Design
1

Here’s something that I’ve been thinking about: What if there was a way to write code that works differently depending on whether some value is known to the compiler?

As an example, let’s say I could write:

@inline function ^(x, p::Integer)
    if @known p
       literal_pow(^, x, Val(p))
    else
       power_by_squaring(x, p)
    end
end

where @known would be a special macro that would tell the compiler to first do some amount of inlining and constant-folding, then check whether the value of p is a constant and branch as a function of that. So Val(p) would only be used when it does not result in dynamic dispatch.

Just as with if @generated, the programmer would be responsible for ensuring that both branches do the same thing. The compiler would always be free skip constant propagation and just take the else branch.

Today, the parser does something similar to the above, but only for ^ and only for literal exponents. (For example (-1)^(-1) does not return the same thing as const p = -1; (-1)^p does.) Instead of special-casing the ^ operator in the parser, I think it would make sense to have a built-in feature in the language.

One example of where this feature would be useful is #31138.
That PR deals with type-stable handling of code like t[2:end] where t is a tuple. What makes this hard is the fact that the getindex function gets a tuple and a range, but it does not know that the range is created from the literal 2 and the compile-time constant lastindex(t). With a set of if-statements, like if r.start == 2 && r.stop == length(t) it is possible to handle some common cases. But it’s not possible to cover every possible case with a finite set of if-statements. (For example, even with that PR, t[2:end-1] would not be type-stable.) Being able to run different code depending on whether r.start and r.end are known to the compiler would make it trivial to handle all cases.

I’ve tried to solve some of these problems with the StaticNumbers package. For example, if t is a tuple, then using StaticNumbers; @stat t[2:end-1] will extract a sub-tuple in a type-stable way. But I’ve come to the conclusion that this really needs to be done at the compiler level if it is to be done right.

12 Likes
2

I like ideas like this where I might be able to interact with the compiler in a very simple way. Unfortunately, I have no idea how complex these things are under the hood

3 Likes
3

I would like such a feature.
But because what is known to the compiler is implementation-dependent (e.g., changes to const prop will change whether or not p is known), it would also require the explicit promise that you are not actually changing the behavior in an observable way. Otherwise, your code is likely to break from one version to another.

6 Likes
4

Exactly. Therefore there must exist a documented way to prevent constant propagation, so that unit tests can run through both branches. For example, one might declare that the value stored in a Ref is never considered a constant, and then a unit test could look like:

@test (-1)^(-1) == (-1)^Ref(-1)[]
1 Like
5

Another thing that one could to with this: Inside a @generated function, the if @known x branch could hold the actual value of x (while the else branch would hold the type as usual).

2 Likes
6

The @known magic macro could also be used to get “traits” in a very straightforward manner. For example:

if @known(issymmetric(x)) && issymmetric(x)

This would detect if typeof(x) is known at compile time and is in one of Symmetric, Hermitian{<:Real}, Diagonal, UniformScaling or Number, and it would also detect any symmetric user-defined types (as long as they have a method issymmetric(::MyType) = true) but it would never do dynamic dispatch or evaluate a slow issymetric method at runtime.

1 Like
8

I’ve submitted a feature request for this.

3 Likes