extend Expr with inline call information

[krauthaufen]

Hi everyone,

In our project FShade we're making heavy use of quotations and we're totally happy with most of the features available for inspecting and changing them.

However there is one big issue I'd like to share since I could not quite get my head around the compiler-code responsible for that.

Statically resolved parameters

When using functions like

let inline run< ^a, ^b when ^a : (member Invoke : ^b -> unit) > (a : ^a) (b : ^b) = 
    (^a : (member Invoke : ^b -> unit) (a, b))

inside quotations, the resulting Expr will look like Call(runMeth, [a]) and there is (to my knowledge) no way of getting its definition for the concrete instantiation in question.
When adding the [<ReflectedDefinition>] attribute to run the compiler complains with Quotations cannot contain expressions that make member constraint calls, or uses of operators that implicitly resolve to a member constraint call

Motivation

Currently our C99/GLSL compiler maintains a mapping from all known inline functions to their respective backend counterpart which makes it hard to add utility-functions.
Consider the following example:

type Vec2 = 
   // ...
   member x.X : float

type Vec3 = 
   // ...
   member x.X : float

module Vec =
    let x< ^a, ^b when ^a : (member X :  ^b) > (v : ^a) = (^a : (member X :  ^b) (v)

Since x is treated as a call our compiler needs to know about its definition. However if the code was inlined in the Expr it would only need to know about the property X (which it does anyways).

Suggestion

Would it be possible to resolve all inline functions at compile-time and simply inline their (resolved) definition in quotations like that?

let a = System.Action<int>(ignore)
<@ run a 10 @> = <@ a.Invoke(10) @>

I'm aware that this scheme will not work for built-in functions (e.g. op_Addition) since they use inline-IL which cannot be represented in Expr.

Since this change would break the current behaviour of quotations one could (for example) add the inlined Expr to the CustomAttributes list for the expression.

any thoughts on that?

cheers

[dsyme]

@krauthaufen I agree this would increase the utility of quotations substantially. It is implementable but not that easy - I think it could also be made a non-breaking change. by having a special quotation active pattern to look into the inlined/resolved code. I suppose this could also be made to work for op_Addition if we added a quotation node that represents a sequence of simple IL instructions

[krauthaufen]

@dsyme I agree that having IL instructions would make the thing even more powerful.

I'm currently trying to understand the translation scheme in QuotationTranslator.fs and how to get the definition-code for those mustinline ValRefs but it seems to be quite complicated ;-)

I will continue to look into that and maybe I can get something running without needing your help here...

[dsyme]

@krauthaufen Yes, it's not at all simple to implement this. The inlined expressions are determined by the optimizer, but quotation translation is done earlier.

[krauthaufen]

After looking at it for a few hours I finally figured out how these things work together.

All quote expressions get their ExprData in PostInferenceChecks which mutates the ref-cell in Expr.Quote.
Whenever the optimizer sees a Quote expr it optimizes all the splices but keeps the ExprData.

Wouldn't it be valid to recreate the ExprData whenever optimizations are possible directly in the Optimizer code?
No idea how to handle [<ReflectedDefinition>] things though...

[krauthaufen]

I managed to get a very simple test working that way:

type Vec(x : float, y : float) =
    member x.X = x
    member x.Y = y

let inline x< ^a, ^b when ^a : (member X : ^b)> (v : ^a) =
    (^a : (member X : ^b) (v))

let q = <@ fun (v : Vec) -> x v @>
printfn "%s" (string q)

which prints:

Lambda (v, PropertyGet (Some (v), X, []))

[dsyme]

@GeorgeHahn When you're ready please add a link to the branch, I'm interested

[GeorgeHahn]

@dsyme I'm not sure I'm the person you're looking for. Love your work though, cheers!

[krauthaufen]

@dsyme This sketch isn't quite what we wanted since it does not include the original call anymore.
I'll be working on it today and the optimizer could be given to the QuotationTranslator as anonymous function somehow.
A different approach would be to "divide" the optimizer into two parts:

• mustinline processing
• real optimization

since we don't want the quotations to be "really" optimized.
However I'm still figuring out how the optimizer finds the Expr for a given function....

[dsyme]

@GeorgeHahn :) Thanks for stopping by :)

@krauthaufen Thanks for the info, that's what I figured. I'm not opposed to dividing the optimizer - phases don't cost that much in themselves, it's the processing you do in them that matters. We could perhaps alternatively do a separate phase to collect and prepare quotation data - the uses of the reference cell hack has been problematic (it caused come very obscure bugs) and we should maybe just do quotation data preparation as a distinct rewriting phase. That phase could collect up inline information (and reuse the inline information provided cross-assembly)

It's important that we present the original body (and not the optimized one). One issue might be that the inline information saved cross-assembly has already been subject to optimization, I'm not sure. I suppose we could save a separate, unoptimized version of that information in a new pickled resource.

I think we would window-dress this in a similar we did Quotations.WithValue, i.e. a new active pattern Quotations.InlineCall. (Every inline call corresponds to the use of Quotations.Call, so this would be a refinement of that)

[krauthaufen]

@dsyme Doing this in a separate phase would be nice but when doing so, the optimizer would need to optimize quote/reflecteddef things while keeping the original expressions somehow. (since they are needed later on)
The QuotationTranslator would then need to get both representations and traverse them in parallel, etc.

Wouldn't it be easier to translate expressions inside the optimizer-phase where all the needed information exists?
I'm aware that this is not really clean from a semantic point.-of-view but implementing it would be simpler.

The cross-assembly thing is a little complicated. As far as I understand it you mean something like:

a.dll:

let inline f a b = a + b
<@ f 1 2 @> = InlineCall(None, f, [Value 1; Value 2], IL [Add])

b.dll:

let inline g a b = f a b * 2
<@ g 1 2 @> = InlineCall(None, g, [Value 1; Value 2], IL [Add; LdConst 2; Mul])

Here the information that g calls f would be lost, but (at least for my purposes) this would be fine.
This behaviour would imply that the optimized version represents a "grounded" variant of the code, which would (in my opinion) also be a sound definition.

[krauthaufen]

@dsyme i finally got something working.

With the changes from https://github.com/krauthaufen/visualfsharp/commit/ea0bc38244be19d56aeb6122fac25fd15632d8e2 calls are properly inlined (using the extended Expr ctors)

So far i handled single-argument function-calls in direct quotes and ReflectedDefinitions.
current limitations:

• Inline IL cannot be quoted atm (simply emits a Call expr like before)
• multi argument calls may be broken (simply concatenated all args from the Expr list list)
• inline properties are not understood (are those even relevant?)

The calls to the QuotationTranslator are now in

• the Optimizer (for Expr.Quote)
• the IlxGen (for ReflectedDefinitions)

Since the optimizer returns a optimize-function optimizeDuringCodeGen the entire functionality could be done by a separate phase quite easily [ didn't know that function existed before ;-) ].

However the following snippet:

open Microsoft.FSharp.Quotations
open Microsoft.FSharp.Quotations.Patterns

type Vec(x : float, y : float) =
    member __.X = x
    member __.Y = y

let inline x< ^a, ^b when ^a : (member X : ^b)> (v : ^a) =
    (^a : (member X : ^b) (v))

type Foo() =
    static member inline x< ^a, ^b when ^a : (member X : ^b)> (v : ^a) =
        (^a : (member X : ^b) (v))
        
    [<ReflectedDefinition>]
    static member Bar(v : Vec) = x v
    
    [<ReflectedDefinition>]
    member __.Baz(v : Vec) = x v

[<ReflectedDefinition>]
let test (a : Vec) = x a

let run = <@ fun (v : Vec) -> Foo.x v @>
printfn "run: %s" (string run)

match <@ test (Vec(1.0, 2.0)) @> with
    | Call(None, mi, _) ->
        match Expr.TryGetReflectedDefinition mi with
        | Some v -> printfn "test: %s" (string v)
        | None -> printfn "test: NO DEF"
    | _ -> printfn "test: invalid"

let bar = typeof<Foo>.GetMethod("Bar")
match Expr.TryGetReflectedDefinition bar with
    | Some bar -> printfn "bar: %s" (string bar)
    | None -> printfn "bar: invalid"

let baz = typeof<Foo>.GetMethod("Baz")
match Expr.TryGetReflectedDefinition baz with
    | Some baz -> printfn "baz: %s" (string baz)
    | None -> printfn "baz: invalid"

prints the following:

run: Lambda (v, InlineCall (None, x, [v], PropertyGet (Some (v), X, [])))
test: Lambda (a, InlineCall (None, x, [a], PropertyGet (Some (a), X, [])))
bar: Lambda (v, InlineCall (None, x, [v], PropertyGet (Some (v), X, [])))
baz: Lambda (__, Lambda (v, InlineCall (None, x, [v], PropertyGet (Some (v), X, []))))

As you see the last expr in InlineCall is the optimized variant.

[krauthaufen]

@dsyme I managed to simplify everything a little by moving all translations to the IlxGen (which seems like a good place for that)

I also removed the ref-cell from Expr.Quote and adjusted the affected code. I'm not sure whether things actually needed the cache-value and therefore marked all of those uses with // TODO: quote-cache useful?

The changes are in https://github.com/krauthaufen/visualfsharp/commit/d056a5fefe4323a0b7960c405e722cccaf89a8e5

I think I'll leave this for today ;-)
Let me know what you think about it and whether I should continue in that direction.

cheers

[krauthaufen]

@dsyme I was thinking the whole thing over again and came up with some questions:

• I changed the pickle/unpickle code in a way that breaks compatibility (MethodCalls have a different number of arguments now). It could be made a non-breaking change by adding a whole new opcode for those inline calls. What is your general policy for these things?
• Since there is no FSharp.Core representation of IL-instructions yet how should it be implemented? (union-type list, byte[], etc.)?
• Should the inlined expression include its arguments (PropertyGet(Some expr, pi, [])) or should it be a lambda Lambda(v, PropertyGet(Some (Var v), pi, [])). The former would enable optimizations while the latter would reduce redundancy since the arguments are already stored in the Call expression.
• The whole translation process for quotations is now performed twice (once in PostInferenceChecks and once in IlxGen). I understand the motivation since errors should be reported by appropriate compiler phases but maybe a separate function checking these quotations (without actually translating them) would be in order?
• When visiting an expression using ExprShape should the inlined variant be skipped or visited too?

When adding a new IL representation to FSharp.Core we'd have all the things necessary for compiling quotations to DynamicMethods. Wouldn't it be nice to have a utility Expr.Evaluate : Expr<'a> -> 'a which basically resembles the compiler (possibly skipping optimizations for the moment). The lack of this tool motivated a lot of libraries out there (QuotationCompiler, Unquote, etc.) which have several caveats (like CompiledNames, non-public methods, etc.)
Since we need this compiler for our projects I will implement it either way, so the question is whether it should be a core feature or not?

cheers

[dsyme]

I changed the pickle/unpickle code in a way that breaks compatibility (MethodCalls have a different number of arguments now). It could be made a non-breaking change by adding a whole new opcode for those inline calls. What is your general policy for these things?

No breaking changes to the format. Extensions are "OK" but need careful thought about whether old compilers will still read the format successfully. If there's no good story, we have either "plan ahead" by making the compiler future-robust ASAP, or make the feature conditional on FSharp.Core latest being referenced, or something like that.

Since there is no FSharp.Core representation of IL-instructions yet how should it be implemented? (union-type list, byte[], etc.)?

Perhaps just the ASCII for the instructions if ilprint.fs is up to scratch for producing it. Or if not adequate then I suppose exposing the equivalent of Abstract IL in the quotations module is ok for a prorotype

• Should the inlined expression include its arguments (PropertyGet(Some expr, pi, [])) or should it be a lambda Lambda(v, PropertyGet(Some (Var v), pi, [])). The former would enable optimizations while the latter would reduce redundancy since the arguments are already stored in the Call expression.

I assume it should be the latter, and then you beta-reduce against the arguments explicitly

• The whole translation process for quotations is now performed twice (once in PostInferenceChecks and once in IlxGen). I understand the motivation since errors should be reported by appropriate compiler phases but maybe a separate function checking these quotations (without actually translating them) would be in order?

I think that just adds work - it's impossible to check without effectively doing the translation (the F# type checker itself works by the same principle, though we only run it once)

• When visiting an expression using ExprShape should the inlined variant be skipped or visited too?

Skipped. It's optional information logically associated with a MethodInfo somewhat like the ReflectedDefinition info

Since we need this compiler for our projects I will implement it either way, so the question is whether it should be a core feature or not?

It shouldn't be in FSharp.Core. Perhaps in FSharp.Compiler.Service. But I'm ok with it being in QuotationCompiler etc.