generated functions, next generation #23168

JeffBezanson · 2017-08-07T20:21:50Z

~~Updated description: #23168 (comment)~~
Now: #23168 (comment)

This also replaces the stagedfunction expression head with metadata. It's more flexible, there are fewer pieces of code that need to propagate the staged bit, and we won't need to worry about handling stagedfunction expressions anywhere.

Interestingly, stagedfunction was neither an AST form nor an IR form, only returned from the @generated macro and immediately lowered away, so it probably doesn't even need a deprecation.

yuyichao · 2017-08-07T20:25:28Z

Do we have any other meta node that changes the behavior of a program that doesn't have UB?

JeffBezanson · 2017-08-07T20:32:45Z

I think there are basically two kinds of metadata: one that's consumed by the method definition process, and one that persists in the IR. I would allow method-def metadata to change program behavior, but not metadata that stays in the IR. There's no other extensible way to convey information between stages. It would be ok to use a different expression head (instead of meta) for this case though, if we can think of one.

vtjnash · 2017-08-07T21:42:42Z

I'm OK with this only in that I want it to become:

function f(args...)
    $Expr(:meta, :stagedfunction, function(Types...) ... end)
    <unspecialized_implementation>
end

JeffBezanson · 2017-08-07T22:26:48Z

Yep, that's where I'm going with this :)

JeffBezanson · 2017-08-07T23:23:30Z

In fact, we could lower the current @generated foo(x) = body to

function foo(x)
    $Expr(:meta, :stagedfunction, function(x) body end)
    error("No fallback implementation provided.")
end

Then I was thinking of using this syntax in general:

function add1(x)
    @generated begin
        return :(x+1)
    end
    return x+1
end

vtjnash · 2017-08-07T23:47:54Z

I think we might want to bikeshed the name to give a better idea what this does (something like @inliner?). Also, throwing an error in the abstract path gives the compiler permission to assume the function always throws an error.

JeffBezanson · 2017-08-07T23:56:33Z

throwing an error in the abstract path gives the compiler permission to assume the function always throws an error

I was thinking about this, and I believe the compiler should not do this. The compiler should try to remain sound even if the implementations don't match. We can freely pick whether to use the generator or not, but we need to be consistent: we can't infer one implementation if there's a chance the other will be called at run time.

vtjnash · 2017-08-08T01:12:55Z

if there's a chance

We cannot possibly bound that chance (except in trivial cases like guaranteeing the generated function will always be called or never be called for a given system image build), so this would be exactly equivalent to saying "if it's a generated function, we can't infer it", which would be terrible. It's perfectly fine for the fallback implementation to be uninferrable, the generated tfunc just must never violate the monotonicity assumption.

JeffBezanson · 2017-08-08T01:47:52Z

I think for a particular call site, if we want to infer anything other than Any, we need to pick which implementation it will use. This is no worse than what we do now --- if we don't have concrete types for the arguments to a generated function, we infer Any. Or we can also insert a typeassert if we want better type information at a call site that might use either implementation.

JeffBezanson · 2017-08-08T21:39:47Z

OK, here is a more fleshed-out implementation. If a function contains a @generated begin ... end block, it's pulled out to a separate first-class function that gets installed as the generator field of that method. The method will contain (meta generator foo) where foo is the global name of the generator function. This is true metadata since it's only an optimization.

To replicate existing generated-only methods, I add a (very unattractively named) (meta generated_only) expression, which just causes the method->source field to be NULLed. This is of course pretty weird, but it's more metadata-like than what I had before.

Open season for bikeshedding on all the names and such.

As an added bonus, this makes it much easier to change the behavior in #12783 (if we want), since jl_call_staged can control how varargs are passed. It also adds a better error message for #18747, but this might need some more finesse.

StefanKarpinski · 2017-08-08T21:53:44Z

How about renaming this to get rid of the vestigial "staged function" terminology? The symbol could be :generated or :generated_method.

StefanKarpinski · 2017-08-08T21:54:39Z

Oh, sorry, I see that you already did that. Carry on.

vtjnash · 2017-08-09T21:19:20Z

src/method.c

+ memcpy(&gargs[1+spl], args, nargs * sizeof(void*));
+ if (def->isva) {
+ gargs[totargs-1] = jl_f_tuple(NULL, &gargs[1+spl+def->nargs-1], nargs - (def->nargs-1));
+ gargs[1+spl+def->nargs-1] = gargs[totargs-1];


could use a lot more spaces here to help legibility

vtjnash · 2017-08-09T21:19:36Z

src/method.c

- size_t world = generator->def.method->min_world;
- const char *F = jl_compile_linfo(&generator, (jl_code_info_t*)generator->inferred, world, &jl_default_cgparams).functionObject;
- fptr = jl_generate_fptr(generator, F, world);
+ size_t spl = jl_svec_len(sparam_vals);


could use a better variable name

vtjnash · 2017-08-09T21:20:31Z

src/method.c

@@ -275,9 +274,11 @@ JL_DLLEXPORT jl_code_info_t *jl_code_for_staged(jl_method_instance_t *linfo)
 jl_expr_t *ex = NULL;
 jl_value_t *linenum = NULL;
 jl_svec_t *sparam_vals = env;
- jl_method_instance_t *generator = linfo->def.method->generator;
+ jl_value_t *generator = linfo->def.method->generator;
+ jl_method_t *gen_meth = jl_gf_mtable(generator)->defs.leaf->func.method;


this is super ugly

Any suggestions?

Also, some of this kind of complexity will go away if we eventually deprecate generated-only methods.

Seems like the names either need to be a characteristic of the original function being optimized, or the generator should be just a single Method object (rather than a function)

The problem is that it's possible to have a Method with a NULL source field. Instead we could populate it with empty IR, or IR that throws an error, or IR that somehow otherwise indicates it doesn't actually work.

Dealing with an individual Method object is difficult, since the front end can't express it, and we needed to duplicate code from jl_call_method_internal to call it.

Either option there sounds OK. When #14919 is implemented, I expect the MethodTable type to vanish (anyways, that's what happens on my branch that fixes that issue), so I would like to avoid adding spurious dependencies on that type which will just need to be deleted.

JeffBezanson · 2017-08-09T21:51:32Z

Somehow this is causing promote_op(==, Int8, UInt8) to return Any.

JeffBezanson · 2017-08-11T17:06:53Z

I get:

julia> Base.promote_op(==,Int8,UInt8)
Any

julia> code_typed(==, (Int8,UInt8));

julia> Base.promote_op(==,Int8,UInt8)
Bool

JeffBezanson · 2017-09-28T22:41:19Z

Oh goodie, the problem went away...

KristofferC · 2017-09-29T08:23:26Z

Is it possible to see a representative example how this is used?

JeffBezanson · 2017-10-16T21:25:44Z

Here's one example ~~based on the current state of this:~~ EDIT: this is old, see next paragraph.

function fillslots!(A::SpecialArrays, x)
    @generated begin
        ex = :(xT = convert(eltype(A), x))
        for field in _valuefields(A)
            ex = :($ex; fill!(A.$field, xT))
        end
        :($ex;return A)
    end
    xT = convert(eltype(A), x)
    for field in _valuefields(A)
        fill!(getfield(A, field), xT)
    end
    return A
end

There are two complete implementations of this method: a generated one in the @generated block, and normal code after that. What jumps out at me is that there's some duplication. I think this is common: often only part of a function body needs to be generated.

So the design I implemented looks like this:

function fillslots!(A::SpecialArrays, x)
    xT = convert(eltype(A), x)
    if @generated
        exs = [ :(fill!(A.$field, xT)) for field in _valuefields(A) ]
        quote
            $(exs...)
        end
    else
        for field in _valuefields(A)
            fill!(getfield(A, field), xT)
        end
    end
    return A
end

That gives two implementations: a generated one where quote is wrapped around everything, with the @generated block $-interpolated, and a normal one where the else part of the @generated block is selected instead. The front end needs to special case if followed by whatever @generated expands to, but that doesn't seem so bad since this feature needs front end support anyway.

JeffBezanson · 2017-10-20T01:57:40Z

Ok, I think this is basically done. I think it also simplifies the implementation a bit, with less implemented in C.

yuyichao

I would add that this looks really like a local scope eval, except that of course the expression is only allowed to be constructed from compile time info. It does make seeing what the generator can see slightly strange.

yuyichao · 2017-10-20T02:07:58Z

doc/src/manual/metaprogramming.md

+
+In this style of definition, the code generation feature is essentially an optional
+optimization.
+The compiler will use it if convenient, but otherwise may choose to use the normal


So does this mean that if a non-generated version is too complicated to write/rewrite one should/can still use @generated on the whole function, which will add the generated_only metadata, and it'll be required to call the generator?

Correct. You can still use @generated on the whole function, but now we have the option of deprecating that if want, and requiring alternate implementations.

yuyichao · 2017-10-20T02:08:27Z

test/staged.jl

+ y = (2x, typeof(x))
+ end
+ push!(a, 2)
+ return y


Can we have a test/do we support functions with multiple generated blocks?

Yes, multiple generated blocks should work. You just get two versions, one with the then part of each generated block selected, and one with the else parts.

vtjnash · 2017-10-20T03:13:05Z

You just get two versions, one with the then part of each generated block selected, and one with the else parts

One other feature I just noticed of this is that we can probably later make closure-lowering / comprehensions work (for the non-generated parts), which will be quite nice!

vtjnash · 2017-10-20T03:16:21Z

base/multidimensional.jl

+ ΔI = first(Rdest) - first(Rsrc)
+ # TODO: restore when #9080 is fixed
+ # for I in Rsrc
+ # @inbounds dest[I+ΔI] = src[I]


remove comment?

vtjnash · 2017-10-20T03:20:52Z

base/sysimg.jl

+ @ncall $N tuple t
+ end
+ else
+ Tuple(f(i) for i = 1:N)


Why is this attempting to use the Tuple constructor? I realize this is sort of a special-case scenario where we know people won't attempt to copy this function elsewhere, but this is still just a rather surprising "gotcha" in behavior (since we'll need a different definition of this function for other top modules like Core.Inference).

I don't understand the problem. Why will we need to add this definition to Core.Inference?

vtjnash · 2017-10-20T03:22:59Z

base/sysimg.jl

+ M > N && throw(ArgumentError("input tuple of length $M, requested $N"))
+ if @generated
+ quote
+ $(Expr(:meta, :inline))


seems like the wrong place for this meta expression to get placed in the function

vtjnash · 2017-10-20T03:24:10Z

base/sysimg.jl

+ if @generated
+ quote
+ $(Expr(:meta, :inline))
+ (t..., $(fill(:val, N-length(t.parameters))...))


this new expression isn't inferable and defeats the whole point of having @generated in this function

It's the same as before, just using fill instead of a comprehension.

vtjnash · 2017-10-20T03:27:41Z

doc/src/manual/metaprogramming.md

-the allowable constructs.
+When a generated function is called, the expression it returns is compiled and then run.
+To make this efficient, the result is usually cached. And to make this inferable, only a limited
+subset of the language is usable during expression generation. Thus, generated functions provide a


This is also true, but I think the original statement was trying to emphasize that some language features (closures, generators, global, etc. – e.g. anything that causes an additional side-effects) are not valid for use in the returned function body.

vtjnash · 2017-10-20T03:34:39Z

base/reflection.jl

@@ -738,7 +738,8 @@ function length(mt::MethodTable)
 end
 isempty(mt::MethodTable) = (mt.defs === nothing)

-uncompressed_ast(m::Method) = uncompressed_ast(m, isdefined(m, :source) ? m.source : m.generator.inferred)
+uncompressed_ast(m::Method) = isdefined(m,:source) ? uncompressed_ast(m, m.source) :


Conditionally returning the source code from a different semi-related method seems sort of random. I think it would be better to now just use the trivial definition (uncompressed_ast(m::Method) = uncompressed_ast(m, m.source))

vtjnash · 2017-10-20T03:41:38Z

src/method.c

+ m->generator = jl_toplevel_eval(m->module, jl_exprarg(st, 1));
+ }
+ JL_CATCH {
+ }


Why are we actively ensuring the backtrace and error message get lost?

vtjnash · 2017-10-20T03:45:03Z

src/method.c

+ else if (jl_expr_nargs(st) == 2 && jl_exprarg(st, 0) == (jl_value_t*)generator_sym) {
+ m->generator = NULL;
+ JL_TRY {
+ m->generator = jl_toplevel_eval(m->module, jl_exprarg(st, 1));


I feel like our deserialize code might be assuming that this function is effect-free / non-reentrant.

Also, what sorts of code is this expecting to potentially encounter? The method-world-counter code, and the multithreaded-toplevel-lock code also strongly assume / require that this function must be effect-free and non-reentrant (both are currently quite bad at enforcing it, but that's besides the point).

The expression it expects is (new (core GeneratedFunctionStub) globalvar constant constant constant constant), so all it does is read two global vars and allocate a struct. I could do that manually instead of calling eval if you think it's necessary.

c42f

The chosen if @generated syntax seems oddly inconsistent with the feel of normal @generated which (at least conceptually) applies to the function block following it just like a normal macro. How about putting the implementation of code rearrangement for normal-vs-generated parts inside the @generated macro itself? Then perhaps some of the special purpose parser changes could go away?

Then we'd potentially have something like

@generated function foo(a)
    if __generated__
        quote
            a + 1
        end
    else
        a + 1
    end
end

With the presence of if __generated__ signifying that code rearrangement and splicing should be performed by @generated. (In the absence of this we'd have to assume generated_only for compatibility.)

c42f · 2017-10-20T20:25:12Z

src/ast.scm

+ (and (length= e 4) (eq? (car e) 'if) (equal? (cadr e) '(generated))))
+
+(define (generator-meta? e)
+ (and (length= e 3) (eq? (car e) 'meta) (eq? (cadr e) 'generator)))


It seems a little confusing to have Expr(:meta, :generator), which is a completely different and unrelated thing from Expr(:generator, ...)

Fair point. I could use generated instead.

c42f · 2017-10-20T20:29:15Z

doc/src/manual/metaprogramming.md

+the first block in `if @generated` is used, and a normal one where the `else` block is used.
+Notice that we added an error check to the top of the function.
+This code will be common to both versions, and is run-time code in both versions
+(in other words, it will be quoted and returned as an expression from the generated version).


I'm curious: does the implementation allow for multiple such blocks of common code interspersed with optionally generated code?

[Edit: I see that this is already asked & answered elsewhere. Would be worth making it clear in the documentation]

JeffBezanson · 2017-10-20T21:14:30Z

A cool feature of if @generated is that macros can expand to it. That allows a macro like @nloops to turn its caller into a generated function if necessary. I also don't want to have to type generated twice.

c42f · 2017-10-23T06:20:51Z

Cool, having other macros which expand to @generated is a pretty nice idea. Maybe a usable @unroll is within our grasp here for StaticArrays :-)

mauro3 · 2017-10-23T08:08:11Z

doc/src/manual/metaprogramming.md

+In this style of definition, the code generation feature is essentially an optional
+optimization.
+The compiler will use it if convenient, but otherwise may choose to use the normal
+implementation instead.


Some guidance on when to use this style versus the generated-only style would be good.

cstjean · 2017-10-23T12:36:40Z

I love the proposal to generate just part of a function (and associated macro possibilities!), but I'm a bit worried by the debugging/testing fallout from having two definitions of a function. Does it mean that a faulty f might cause f(1) and (x->f(x))(1) to return different results depending on compiler internals? Or is it only static compilation that changes which version is chosen? This is not clear from this paragraph:

Typically, Julia is able to compile "generic" versions of functions that will work for any
arguments, but with generated functions this is impossible.
This means that programs making heavy use of generated functions might be impossible to
statically compile.

JeffBezanson · 2017-10-23T14:00:14Z

It is essential that the two implementations do the same thing. Which version is used is a compiler implementation detail.

mauro3 · 2017-10-23T14:12:00Z

It is essential that the two implementations do the same thing.

Then it would be good to have a tool which can test both code paths.

JeffBezanson · 2017-10-23T14:24:01Z

Very much agreed. Any ideas on what its mechanics should be? One possibility is a command line switch to disable @generated.

c42f · 2017-10-23T20:17:04Z

I feel like I'm going to want to test both generated and non-generated implementations of a given function within the same julia session. For example, to compare numerical results, to get coverage correct, or to just iterate on the code in a reasonably productive way. Is it possible to have a compiler annotation at the call site, in the spirit of @nospecialize? A global flag also seems very useful.

Ideally I hope this new version of @generated gives enough flexibility to build some higher level code generation tools (eg, @unroll?) so that the testing effort can focus on getting those tools correct. Then the generated vs non-generated code paths have a better chance of actually being the same.

…onal optimizers use meta nodes instead of `stagedfunction` expression head

c42f · 2017-10-25T20:04:20Z

Party time! I've got to try this out!

TransGirlCodes · 2018-02-20T22:56:20Z

This looks really cool. In the manual it states in the sub2ind example that the compiler may use the "then" part of the if - the generated part, or may use the "else" part of the if, the default part, and that it is up to the compiler.

In julia I suppose many of us have a good feel from looking at some code whether or not static dispatch, unboxing and other optimisations occur, from looking at the code style and use of types etc (and of course we can check!). Is there any general advice on how to develop this kind of feel for if @generated? In what circumstances can we expect the generated branch to be used over the default branch and vice versa?

JeffBezanson · 2018-02-20T23:03:08Z

Currently the @generated branch is always used. In the future, which branch is used will mostly depend on whether the JIT compiler is enabled and available, and if it's not available, then it will depend on how much we were able to compile before the compiler was taken away. So I think it will mostly be a concern for those that might need static compilation and JIT-less deployment.

JeffBezanson added the compiler:lowering Syntax lowering (compiler front end, 2nd stage) label Aug 7, 2017

JeffBezanson changed the title ~~use a meta node instead of stagedfunction expression head~~ RFC: generated functions as optional optimizations Aug 8, 2017

JeffBezanson added needs docs Documentation for this change is required needs news A NEWS entry is required for this change needs tests Unit tests are required for this change labels Aug 8, 2017

JeffBezanson force-pushed the jb/rm_stagedfunction branch from 85e88f7 to bbb9284 Compare August 9, 2017 20:32

vtjnash reviewed Aug 9, 2017

View reviewed changes

andyferris mentioned this pull request Aug 17, 2017

map is overwritten for non-StaticArrays. JuliaArrays/StaticArrays.jl#282

Closed

JeffBezanson force-pushed the jb/rm_stagedfunction branch from bbb9284 to 9ebcd00 Compare September 11, 2017 19:27

JeffBezanson force-pushed the jb/rm_stagedfunction branch from 9ebcd00 to 944e754 Compare September 28, 2017 20:12

vtjnash mentioned this pull request Oct 17, 2017

add NamedTuples #22194

Merged

JeffBezanson removed the needs tests Unit tests are required for this change label Oct 20, 2017

JeffBezanson changed the title ~~RFC: generated functions as optional optimizations~~ generated functions, next generation Oct 20, 2017

yuyichao reviewed Oct 20, 2017

View reviewed changes

vtjnash reviewed Oct 20, 2017

View reviewed changes

c42f reviewed Oct 20, 2017

View reviewed changes

JeffBezanson force-pushed the jb/rm_stagedfunction branch 2 times, most recently from a8bc71a to a5b540c Compare October 22, 2017 18:39

mauro3 reviewed Oct 23, 2017

View reviewed changes

JeffBezanson force-pushed the jb/rm_stagedfunction branch from a5b540c to e87f487 Compare October 23, 2017 14:46

JeffBezanson force-pushed the jb/rm_stagedfunction branch from e87f487 to d01475b Compare October 24, 2017 19:01

add if @generated ... else ... end inside functions to provide opti…

7168542

…onal optimizers use meta nodes instead of `stagedfunction` expression head

JeffBezanson force-pushed the jb/rm_stagedfunction branch from d01475b to 7168542 Compare October 25, 2017 04:16

JeffBezanson merged commit 80a2c2f into master Oct 25, 2017

JeffBezanson deleted the jb/rm_stagedfunction branch October 25, 2017 13:33

cstjean mentioned this pull request Dec 2, 2017

Loop disappears in Julia v0.7 cstjean/Unrolled.jl#1

Closed

jrevels mentioned this pull request Dec 13, 2017

Optional generator expansion in code_lowered (#22979) broken by #23168 #25059

Closed

maleadt mentioned this pull request Jan 23, 2018

Optional generators swallow errors #25707

Open

ToucheSir mentioned this pull request Mar 15, 2023

generated z2d FluxML/Zygote.jl#1394

Merged

generated functions, next generation #23168

generated functions, next generation #23168

Conversation

JeffBezanson commented Aug 7, 2017 • edited Loading

yuyichao commented Aug 7, 2017

JeffBezanson commented Aug 7, 2017 • edited Loading

vtjnash commented Aug 7, 2017

JeffBezanson commented Aug 7, 2017

JeffBezanson commented Aug 7, 2017

vtjnash commented Aug 7, 2017

JeffBezanson commented Aug 7, 2017

vtjnash commented Aug 8, 2017

JeffBezanson commented Aug 8, 2017

JeffBezanson commented Aug 8, 2017 • edited Loading

StefanKarpinski commented Aug 8, 2017

StefanKarpinski commented Aug 8, 2017

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

JeffBezanson commented Aug 9, 2017

JeffBezanson commented Aug 11, 2017

JeffBezanson commented Sep 28, 2017

KristofferC commented Sep 29, 2017

JeffBezanson commented Oct 16, 2017 • edited Loading

JeffBezanson commented Oct 20, 2017

yuyichao left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

vtjnash commented Oct 20, 2017

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

c42f left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

JeffBezanson commented Oct 20, 2017

c42f commented Oct 23, 2017

Choose a reason for hiding this comment

cstjean commented Oct 23, 2017 • edited Loading

JeffBezanson commented Oct 23, 2017

mauro3 commented Oct 23, 2017

JeffBezanson commented Oct 23, 2017

c42f commented Oct 23, 2017

c42f commented Oct 25, 2017

TransGirlCodes commented Feb 20, 2018 • edited Loading

JeffBezanson commented Feb 20, 2018

JeffBezanson commented Aug 7, 2017 •

edited

Loading

JeffBezanson commented Aug 7, 2017 •

edited

Loading

JeffBezanson commented Aug 8, 2017 •

edited

Loading

JeffBezanson commented Oct 16, 2017 •

edited

Loading

cstjean commented Oct 23, 2017 •

edited

Loading

TransGirlCodes commented Feb 20, 2018 •

edited

Loading