From 97fd7d5f34744de9327b3f9850bef4b21777263c Mon Sep 17 00:00:00 2001 From: Luuk van Dijk Date: Tue, 10 Jan 2012 21:24:31 +0100 Subject: [PATCH] gc: inlining fixes flag -l means: inlining on, -ll inline with early typecheck -l lazily typechecks imports on use and re-export, nicer for debugging -lm produces output suitable for errchk tests, repeated -mm... increases inl.c's verbosity export processed constants, instead of originals outparams get ->inlvar too, and initialized to zero fix shared rlist bug, that lead to typecheck messing up the patched tree properly handle non-method calls to methods T.meth(t, a...) removed embryonic code to handle closures in inlined bodies also inline calls inside closures (todo: move from phase 6b to 4) Fixes #2579. R=rsc CC=golang-dev https://golang.org/cl/5489106 --- src/cmd/gc/export.c | 30 +++++- src/cmd/gc/fmt.c | 20 +++- src/cmd/gc/go.h | 1 + src/cmd/gc/inl.c | 219 +++++++++++++++++++++++++------------------- src/cmd/gc/lex.c | 27 +++--- 5 files changed, 180 insertions(+), 117 deletions(-) diff --git a/src/cmd/gc/export.c b/src/cmd/gc/export.c index 00bbaf31f1..e1f289200c 100644 --- a/src/cmd/gc/export.c +++ b/src/cmd/gc/export.c @@ -104,18 +104,34 @@ reexportdep(Node *n) if(!n) return; +// print("reexportdep %+hN\n", n); switch(n->op) { case ONAME: switch(n->class&~PHEAP) { case PFUNC: + // methods will be printed along with their type + if(!n->type || n->type->thistuple > 0) + break; + // fallthrough case PEXTERN: if (n->sym && n->sym->pkg != localpkg && n->sym->pkg != builtinpkg) exportlist = list(exportlist, n); } break; - case OTYPE: + case OLITERAL: + t = n->type; + if(t != types[n->type->etype] && t != idealbool && t != idealstring) { + if(isptr[t->etype]) + t = t->type; + if (t && t->sym && t->sym->def && t->sym->pkg != localpkg && t->sym->pkg != builtinpkg) { +// print("reexport literal type %+hN\n", t->sym->def); + exportlist = list(exportlist, t->sym->def); + } + } + // fallthrough + case OTYPE: if (n->sym && n->sym->pkg != localpkg && n->sym->pkg != builtinpkg) exportlist = list(exportlist, n); break; @@ -176,7 +192,7 @@ dumpexportvar(Sym *s) Type *t; n = s->def; - typecheck(&n, Erv); + typecheck(&n, Erv|Ecall); if(n == N || n->type == T) { yyerror("variable exported but not defined: %S", s); return; @@ -187,6 +203,10 @@ dumpexportvar(Sym *s) if(t->etype == TFUNC && n->class == PFUNC) { if (n->inl) { + // when lazily typechecking inlined bodies, some re-exported ones may not have been typechecked yet. + // currently that can leave unresolved ONONAMEs in import-dot-ed packages in the wrong package + if(debug['l'] < 2) + typecheckinl(n); Bprint(bout, "\tfunc %#S%#hT { %#H }\n", s, t, n->inl); reexportdeplist(n->inl); } else @@ -243,6 +263,10 @@ dumpexporttype(Type *t) for(i=0; itype->nname && f->type->nname->inl) { // nname was set by caninl + // when lazily typechecking inlined bodies, some re-exported ones may not have been typechecked yet. + // currently that can leave unresolved ONONAMEs in import-dot-ed packages in the wrong package + if(debug['l'] < 2) + typecheckinl(f->type->nname); Bprint(bout, "\tfunc (%#T) %#hhS%#hT { %#H }\n", getthisx(f->type)->type, f->sym, f->type, f->type->nname->inl); reexportdeplist(f->type->nname->inl); } else @@ -261,7 +285,7 @@ dumpsym(Sym *s) yyerror("unknown export symbol: %S", s); return; } - +// print("dumpsym %O %+S\n", s->def->op, s); dumppkg(s->pkg); switch(s->def->op) { diff --git a/src/cmd/gc/fmt.c b/src/cmd/gc/fmt.c index f3be53c8fb..10bf02130a 100644 --- a/src/cmd/gc/fmt.c +++ b/src/cmd/gc/fmt.c @@ -933,6 +933,7 @@ stmtfmt(Fmt *f, Node *n) static int opprec[] = { [OAPPEND] = 8, [OARRAYBYTESTR] = 8, + [OARRAYLIT] = 8, [OCALLFUNC] = 8, [OCALLINTER] = 8, [OCALLMETH] = 8, @@ -947,6 +948,7 @@ static int opprec[] = { [OLITERAL] = 8, [OMAKESLICE] = 8, [OMAKE] = 8, + [OMAPLIT] = 8, [ONAME] = 8, [ONEW] = 8, [ONONAME] = 8, @@ -957,10 +959,14 @@ static int opprec[] = { [OPRINT] = 8, [ORECV] = 8, [ORUNESTR] = 8, - [OTPAREN] = 8, [OSTRUCTLIT] = 8, - [OMAPLIT] = 8, - [OARRAYLIT] = 8, + [OTARRAY] = 8, + [OTCHAN] = 8, + [OTFUNC] = 8, + [OTINTER] = 8, + [OTMAP] = 8, + [OTPAREN] = 8, + [OTSTRUCT] = 8, [OINDEXMAP] = 8, [OINDEX] = 8, @@ -1291,7 +1297,13 @@ nodefmt(Fmt *f, Node *n) Type *t; t = n->type; - if(n->orig != N) + if(n->orig == N) + fatal("node with no orig %N", n); + + // we almost always want the original, except in export mode for literals + // this saves the importer some work, and avoids us having to redo some + // special casing for package unsafe + if(fmtmode != FExp || n->op != OLITERAL) n = n->orig; if(f->flags&FmtLong && t != T) { diff --git a/src/cmd/gc/go.h b/src/cmd/gc/go.h index 10441a5c3f..57cc94cccb 100644 --- a/src/cmd/gc/go.h +++ b/src/cmd/gc/go.h @@ -996,6 +996,7 @@ Sym* renameinit(void); */ void caninl(Node *fn); void inlcalls(Node *fn); +void typecheckinl(Node *fn); /* * lex.c diff --git a/src/cmd/gc/inl.c b/src/cmd/gc/inl.c index 982013619d..8830f6bb12 100644 --- a/src/cmd/gc/inl.c +++ b/src/cmd/gc/inl.c @@ -7,6 +7,11 @@ // saves a copy of the body. Then inlcalls walks each function body to // expand calls to inlinable functions. // +// TODO: +// - inline functions with ... args +// - handle T.meth(f()) with func f() (t T, arg, arg, ) +// - (limited) recursive inlining +// - it would be nice if func max(x, y int) { if x > y { return x }; return y } would be inlineable #include #include @@ -36,6 +41,22 @@ static Node *inlretlabel; // target of the goto substituted in place of a return static NodeList *inlretvars; // temp out variables +void +typecheckinl(Node *fn) +{ + Node *savefn; + + if (debug['m']>2) + print("typecheck import [%S] %lN { %#H }\n", fn->sym, fn, fn->inl); + + savefn = curfn; + curfn = fn; + importpkg = fn->sym->pkg; + typechecklist(fn->inl, Etop); + importpkg = nil; + curfn = savefn; +} + // Caninl determines whether fn is inlineable. Currently that means: // fn is exactly 1 statement, either a return or an assignment, and // some temporary constraints marked TODO. If fn is inlineable, saves @@ -55,7 +76,7 @@ caninl(Node *fn) if(fn->nbody == nil || fn->nbody->next != nil) return; - // the single statement should be a return or an assignment. + // the single statement should be a return, an assignment or empty. switch(fn->nbody->n->op) { default: return; @@ -85,8 +106,10 @@ caninl(Node *fn) // this is so export can find the body of a method fn->type->nname = fn->nname; - if(debug['l']>1) + if(debug['m'] > 1) print("%L: can inline %#N as: %#T { %#H }\n", fn->lineno, fn->nname, fn->type, fn->nname->inl); + else if(debug['m']) + print("%L: can inline %N\n", fn->lineno, fn->nname); curfn = savefn; } @@ -107,14 +130,21 @@ ishairy(Node *n) if(!n) return 0; + // Some of these are implied by the single-assign-or-return condition in caninl, + // but they may stay even if that one is relaxed. switch(n->op) { - case OPROC: - case ODEFER: case OCALL: case OCALLFUNC: case OCALLINTER: case OCALLMETH: - case OCLOSURE: + case OCLOSURE: // TODO too hard to inlvar the PARAMREFs + case OIF: + case ORANGE: + case OFOR: + case OSELECT: + case OSWITCH: + case OPROC: + case ODEFER: return 1; } @@ -250,8 +280,11 @@ inlnodelist(NodeList *l) // nbody and nelse and use one of the 4 inlconv/glue functions above // to turn the OINLCALL into an expression, a statement, or patch it // in to this nodes list or rlist as appropriate. -// NOTE it makes no sense to pass the glue functions down the recursion to the level where the OINLCALL gets created because they have to edit /this/ n, -// so you'd have to push that one down as well, but then you may as well do it here. so this is cleaner and shorter and less complicated. +// NOTE it makes no sense to pass the glue functions down the +// recursion to the level where the OINLCALL gets created because they +// have to edit /this/ n, so you'd have to push that one down as well, +// but then you may as well do it here. so this is cleaner and +// shorter and less complicated. static void inlnode(Node **np) { @@ -274,7 +307,8 @@ inlnode(Node **np) } case OCLOSURE: - // TODO. do them here rather than in lex.c phase 6b + // TODO do them here instead of in lex.c phase 6b, so escape analysis + // can avoid more heapmoves. return; } @@ -374,19 +408,27 @@ inlnode(Node **np) switch(n->op) { case OCALLFUNC: - if(debug['l']>3) - print("%L:call to func %lN\n", n->lineno, n->left); - mkinlcall(np, n->left); + if(debug['m']>3) + print("%L:call to func %+N\n", n->lineno, n->left); + if(n->left->inl) // normal case + mkinlcall(np, n->left); + else if(n->left->op == ONAME && n->left->left && n->left->left->op == OTYPE && n->left->right && n->left->right->op == ONAME) // methods called as functions + if(n->left->sym->def) + mkinlcall(np, n->left->sym->def); break; case OCALLMETH: - if(debug['l']>3) + if(debug['m']>3) print("%L:call to meth %lN\n", n->lineno, n->left->right); - // typecheck resolved ODOTMETH->type, whose nname points to the actual function. - if(n->left->type->nname) - mkinlcall(np, n->left->type->nname); - else + // typecheck should have resolved ODOTMETH->type, whose nname points to the actual function. + if(n->left->type == T) + fatal("no function type for [%p] %+N\n", n->left, n->left); + + if(n->left->type->nname == N) fatal("no function definition for [%p] %+T\n", n->left->type, n->left->type); + + mkinlcall(np, n->left->type->nname); + break; } } @@ -399,20 +441,25 @@ static void mkinlcall(Node **np, Node *fn) { int i; - Node *n, *call, *saveinlfn, *as; + Node *n, *call, *saveinlfn, *as, *m; NodeList *dcl, *ll, *ninit, *body; Type *t; if (fn->inl == nil) return; + if(debug['l']<2) + typecheckinl(fn); + n = *np; // Bingo, we have a function node, and it has an inlineable body - if(debug['l']>1) + if(debug['m']>1) print("%L: inlining call to %S %#T { %#H }\n", n->lineno, fn->sym, fn->type, fn->inl); + else if(debug['m']) + print("%L: inlining call to %N\n", n->lineno, fn); - if(debug['l']>2) + if(debug['m']>2) print("%L: Before inlining: %+N\n", n->lineno, n); saveinlfn = inlfn; @@ -425,30 +472,56 @@ mkinlcall(Node **np, Node *fn) else // imported function dcl = fn->dcl; - // Make temp names to use instead of the originals for anything but the outparams + inlretvars = nil; + i = 0; + // Make temp names to use instead of the originals for(ll = dcl; ll; ll=ll->next) - if(ll->n->op == ONAME && ll->n->class != PPARAMOUT) { + if(ll->n->op == ONAME) { ll->n->inlvar = inlvar(ll->n); ninit = list(ninit, nod(ODCL, ll->n->inlvar, N)); // otherwise gen won't emit the allocations for heapallocs + if (ll->n->class == PPARAMOUT) // we rely on the order being correct here + inlretvars = list(inlretvars, ll->n->inlvar); + } + + // anonymous return values, synthesize names for use in assignment that replaces return + if(inlretvars == nil && fn->type->outtuple > 0) + for(t = getoutargx(fn->type)->type; t; t = t->down) { + m = retvar(t, i++); + ninit = list(ninit, nod(ODCL, m, N)); + inlretvars = list(inlretvars, m); } // assign arguments to the parameters' temp names + as = N; if(fn->type->thistuple) { - if (!n->left->op == ODOTMETH || !n->left->left) - fatal("method call without receiver: %+N", n); t = getthisx(fn->type)->type; - if(t != T && t->nname) { - if(!t->nname->inlvar) - fatal("missing inlvar for %N\n", t->nname); - as = nod(OAS, t->nname->inlvar, n->left->left); + + if(t != T && t->nname != N && !t->nname->inlvar) + fatal("missing inlvar for %N\n", t->nname); + + if(n->left->op == ODOTMETH) { + if (!n->left->left) + fatal("method call without receiver: %+N", n); + if(t != T && t->nname) + as = nod(OAS, t->nname->inlvar, n->left->left); + // else if !ONAME add to init anyway? + } else { // non-method call to method + if (!n->list) + fatal("non-method call to method without first arg: %+N", n); + if(t != T && t->nname) + as = nod(OAS, t->nname->inlvar, n->list->n); + } + + if(as != N) { typecheck(&as, Etop); ninit = list(ninit, as); - } // else if !ONAME add to init anyway? + } } as = nod(OAS2, N, N); if(fn->type->intuple > 1 && n->list && !n->list->next) { // TODO check that n->list->n is a call? + // TODO: non-method call to T.meth(f()) where f returns t, args... as->rlist = n->list; for(t = getinargx(fn->type)->type; t; t=t->down) { if(t->nname && !isblank(t->nname)) { @@ -461,6 +534,9 @@ mkinlcall(Node **np, Node *fn) } } else { ll = n->list; + if(fn->type->thistuple && n->left->op != ODOTMETH) // non method call to method + ll=ll->next; // was handled above in if(thistuple) + for(t = getinargx(fn->type)->type; t && ll; t=t->down) { if(t->nname && !isblank(t->nname)) { if(!t->nname->inlvar) @@ -479,12 +555,13 @@ mkinlcall(Node **np, Node *fn) ninit = list(ninit, as); } - // make the outparams. No need to declare because currently they'll only be used in the assignment that replaces returns. - inlretvars = nil; - i = 0; - for(t = getoutargx(fn->type)->type; t; t = t->down) - inlretvars = list(inlretvars, retvar(t, i++)); - + // zero the outparams + for(ll = inlretvars; ll; ll=ll->next) { + as = nod(OAS, ll->n, N); + typecheck(&as, Etop); + ninit = list(ninit, as); + } + inlretlabel = newlabel(); body = inlsubstlist(fn->inl); @@ -505,7 +582,7 @@ mkinlcall(Node **np, Node *fn) *np = call; inlfn = saveinlfn; - if(debug['l']>2) + if(debug['m']>2) print("%L: After inlining %+N\n\n", n->lineno, *np); } @@ -518,7 +595,7 @@ inlvar(Node *var) { Node *n; - if(debug['l']>3) + if(debug['m']>3) print("inlvar %+N\n", var); n = newname(var->sym); @@ -530,29 +607,6 @@ inlvar(Node *var) return n; } -// Make a new pparamref -static Node* -inlref(Node *var) -{ - Node *n; - - if (!var->closure) - fatal("No ->closure: %N", var); - - if (!var->closure->inlvar) - fatal("No ->closure->inlref: %N", var); - - n = nod(OXXX, N, N); - *n = *var; - -// if(debug['l']>1) -// print("inlref: %N -> %N\n", var, var->closure->inlvar); - - var = var->closure->inlvar; - - return n; -} - // Synthesize a variable to store the inlined function's results in. static Node* retvar(Type *t, int i) @@ -597,8 +651,6 @@ inlsubstlist(NodeList *ll) return l; } -static int closuredepth; - static Node* inlsubst(Node *n) { @@ -611,12 +663,12 @@ inlsubst(Node *n) switch(n->op) { case ONAME: if(n->inlvar) { // These will be set during inlnode - if (debug['l']>2) - print ("substituting name %N -> %N\n", n, n->inlvar); + if (debug['m']>2) + print ("substituting name %+N -> %+N\n", n, n->inlvar); return n->inlvar; } - if (debug['l']>2) - print ("not substituting name %N\n", n); + if (debug['m']>2) + print ("not substituting name %+N\n", n); return n; case OLITERAL: @@ -624,26 +676,17 @@ inlsubst(Node *n) return n; case ORETURN: - // only rewrite returns belonging to this function, not nested ones. - if (closuredepth > 0) - break; - + // Since we don't handle bodies with closures, this return is guaranteed to belong to the current inlined function. + // dump("Return before substitution", n); m = nod(OGOTO, inlretlabel, N); m->ninit = inlsubstlist(n->ninit); - // rewrite naked return for function with return values to return PPARAMOUTs - if(count(n->list) == 0 && inlfn->type->outtuple > 0) { - for(ll = inlfn->dcl; ll; ll=ll->next) - if(ll->n->op == ONAME && ll->n->class == PPARAMOUT) - n->list = list(n->list, ll->n); - -// dump("Return naked -> dressed ", n); - } - if(inlretvars && n->list) { as = nod(OAS2, N, N); - as->list = inlretvars; + // shallow copy or OINLCALL->rlist will be the same list, and later walk and typecheck may clobber that. + for(ll=inlretvars; ll; ll=ll->next) + as->list = list(as->list, ll->n); as->rlist = inlsubstlist(n->list); typecheck(&as, Etop); m->ninit = list(m->ninit, as); @@ -660,20 +703,9 @@ inlsubst(Node *n) *m = *n; m->ninit = nil; - if(n->op == OCLOSURE) { - closuredepth++; + if(n->op == OCLOSURE) + fatal("cannot inline function containing closure: %+N", n); - for(ll = m->dcl; ll; ll=ll->next) - if(ll->n->op == ONAME) { - ll->n->inlvar = inlvar(ll->n); - m->ninit = list(m->ninit, nod(ODCL, ll->n->inlvar, N)); // otherwise gen won't emit the allocations for heapallocs - } - - for (ll=m->cvars; ll; ll=ll->next) - if (ll->n->op == ONAME) - ll->n->cvars = list(ll->n->cvars, inlref(ll->n)); - } - m->left = inlsubst(n->left); m->right = inlsubst(n->right); m->list = inlsubstlist(n->list); @@ -684,9 +716,6 @@ inlsubst(Node *n) m->nbody = inlsubstlist(n->nbody); m->nelse = inlsubstlist(n->nelse); - if(n->op == OCLOSURE) - closuredepth--; - return m; } diff --git a/src/cmd/gc/lex.c b/src/cmd/gc/lex.c index ba9148726c..f777a7e44e 100644 --- a/src/cmd/gc/lex.c +++ b/src/cmd/gc/lex.c @@ -337,20 +337,14 @@ main(int argc, char *argv[]) errorexit(); // Phase 4: Inlining - if (debug['l']) { // TODO only if debug['l'] > 1, otherwise lazily when used. - // Typecheck imported function bodies - for(l=importlist; l; l=l->next) { - if (l->n->inl == nil) - continue; - curfn = l->n; - saveerrors(); - importpkg = l->n->sym->pkg; - if (debug['l']>2) - print("typecheck import [%S] %lN { %#H }\n", l->n->sym, l->n, l->n->inl); - typechecklist(l->n->inl, Etop); - importpkg = nil; - } - curfn = nil; + if (debug['l'] > 1) { + // Typecheck imported function bodies if debug['l'] > 1, + // otherwise lazily when used or re-exported. + for(l=importlist; l; l=l->next) + if (l->n->inl) { + saveerrors(); + typecheckinl(l->n); + } if(nsavederrors+nerrors) errorexit(); @@ -384,8 +378,11 @@ main(int argc, char *argv[]) while(closures) { l = closures; closures = nil; - for(; l; l=l->next) + for(; l; l=l->next) { + if (debug['l']) + inlcalls(l->n); funccompile(l->n, 1); + } } // Phase 7: check external declarations. -- 2.50.0