Semantic hint for the standard library

[kyouko-taiga]

One problem we have to write optimization passes on Hylo IR that it is hard to know what an operation is trying to achieve, even on "compiler-known" types. Part of the problem is that the user is free to redefine conformances everywhere, thereby shadowing the semantics of the standard library.

The compiler might be allowed to skip some operations (e.g., necessary moves or copies), but I don't think that is an approach we can apply to all operations. There are some conformances that are legit to shadow on standard library types, like hashing when the user has extra knowledge about the instances that can be hashed in some particular scope. Further, even without conformance shadowing, it is still not obvious to figure out the semantics of a particular operation once we're deep in the IR.

To address this issue, I propose to add semantic hints on the definition of some operations. These hints would be stored in the declaration of the function/method implementing the operation and so during IR processing we would be able to check whether the function being called implements an operation that the compiler knows about.

In code it would look like this:

public conformance Int: AdditiveArithmetic {
  @_semantics("integer_addition")
  public fun infix+ (_ other: Self) -> Self {
    // ...
  }
}

Now when the compiler sees a call to this specific implementation of Int.infix+, it can emit different code or even evaluate the result of the operation at compile time.

This feature wouldn't be necessary if we were already able to run any function at compile time, which is a goal we have on our roadmap. Implementing generalized compile-time evaluation is a big project, though, so these semantics hint might help fill the gap before we get there.

[dabrahams]

I am really really wary of this. In Swift, the back-end team added these hints and as a standard library author I had no way to know what they meant nor whether I was going to break them by any particular refactor. So I've been burnt by a feature exactly like this one.

Before we go any further with this discussion though, it's important that you explain the problem this is actually solving. What optimization pass are you trying to write and how is it hampered by not having these hints?

This feature wouldn't be necessary if we were already able to run any function at compile time

Really, all optimizations to be enabled by this feature boil down to constant-folding? If that were the case, a much more targeted annotation like Swift's @transparent should probably be sufficient.

[kyouko-taiga]

So I've been burnt by a feature exactly like this one.

Okay, I think that is enough for me to retract my proposal.

What optimization pass are you trying to write and how is it hampered by not having these hints?

There are two things I'm trying to achieve:

1. Help the emitter know what a function is doing without having to read its contents.
2. Enable compile-time computation for some simple operations whose semantics are known.

Really, all optimizations to be enabled by this feature boil down to constant-folding?

It would speedup inlining a little but yes, it is mostly about constant-folding.

@transparent is a better long-time solution. It's just that ideally I'd like a simple way to let the emitter do something differently if it knows it's lowering an operation whose semantics are known. Otherwise inlining has much more work to do later on.

[dabrahams]

Help the emitter know what a function is doing without having to read its contents

Sure; I was hoping you could tell me specifically what optimization you want to write for which such a hint is needed.

[kyouko-taiga]

I would like to eliminate the allocas required to call arithmetic operators on integers. Currently when the emitter sees 40 + n it writes this, more or less:

var t0: Int
&t0 = 40
var t1: Int
plus(t0, n, &t1)

The local variables will be allocas which LLVM has a hard time removing. I suspect part of the issue is that it doesn't understand that plus doesn't really care about addresses, only about the values stored at these addresses. Anyway, my current plan is to address this issue by inlining plus. But it would be simpler to know that really I only want to do something like sadd.with.overflow.i64(...) so that I could teach code generation how to emit LLVM IR directly, without even having an inline pass on our IR.