diff options
Diffstat (limited to 'compiler/lambdalifting.nim')
| -rw-r--r-- | compiler/lambdalifting.nim | 127 |
1 files changed, 77 insertions, 50 deletions
diff --git a/compiler/lambdalifting.nim b/compiler/lambdalifting.nim index 70db9334e..83885029a 100644 --- a/compiler/lambdalifting.nim +++ b/compiler/lambdalifting.nim @@ -10,8 +10,9 @@ # This include file implements lambda lifting for the transformator. const - procDefs = {nkLambda, nkProcDef, nkMethodDef, nkIteratorDef, nkMacroDef, + declarativeDefs = {nkProcDef, nkMethodDef, nkIteratorDef, nkMacroDef, nkConverterDef} + procDefs = {nkLambda} + declarativeDefs proc indirectAccess(a, b: PSym, info: TLineInfo): PNode = # returns a[].b as a node @@ -47,17 +48,16 @@ proc captureToTuple(cap: TCapture, owner: PSym): PType = addSon(result.n, newSymNode(field)) addSon(result, typ) +proc interestingVar(s: PSym): bool {.inline.} = + result = s.kind in {skVar, skLet, skTemp, skForVar, skParam, skResult} and + sfGlobal notin s.flags + proc gatherVars(c: PTransf, n: PNode, outerProc: PSym, cap: var TCapture) = # gather used vars for closure generation into 'cap' case n.kind of nkSym: var s = n.sym - var found = false - case s.kind - of skVar, skLet: found = sfGlobal notin s.flags - of skTemp, skForVar, skParam, skResult: found = true - else: nil - if found and outerProc.id == s.owner.id: + if interestingVar(s) and outerProc.id == s.owner.id: #echo "captured: ", s.name.s Capture(cap, s) of nkEmpty..pred(nkSym), succ(nkSym)..nkNilLit: nil @@ -70,37 +70,34 @@ proc replaceVars(c: PTransf, n: PNode, outerProc, env: PSym) = let a = n.sons[i] if a.kind == nkSym: let s = a.sym - var found = false - case s.kind - of skVar, skLet: found = sfGlobal notin s.flags - of skTemp, skForVar, skParam, skResult: found = true - else: nil - if found and outerProc.id == s.owner.id: + if interestingVar(s) and outerProc == s.owner: # access through the closure param: n.sons[i] = indirectAccess(env, s, n.info) else: replaceVars(c, a, outerProc, env) -proc addFormalParam(routine: PType, param: PSym) = - addSon(routine, param.typ) - addSon(routine.n, newSymNode(param)) - -proc addFormalParam(routine: PSym, param: PSym) = - #addFormalParam(routine.typ, param) - addSon(routine.ast.sons[paramsPos], newSymNode(param)) +proc addHiddenParam(routine: PSym, param: PSym) = + var params = routine.ast.sons[paramsPos] + let L = params.len-1 + if L >= 0: + # update if we already added a hidden parameter: + if params.sons[L].kind == nkSym and params.sons[L].sym.kind == skTemp: + params.sons[L].sym = param + return + addSon(params, newSymNode(param)) + #echo "produced environment: ", param.id, " for ", routine.name.s proc isInnerProc(s, outerProc: PSym): bool {.inline.} = result = s.kind in {skProc, skMacro, skIterator, skMethod, skConverter} and - s.owner.id == outerProc.id and not isGenericRoutine(s) and - s.typ.callConv == ccClosure + s.owner == outerProc and not isGenericRoutine(s) + #s.typ.callConv == ccClosure proc searchForInnerProcs(c: PTransf, n: PNode, outerProc: PSym, cap: var TCapture) = case n.kind of nkSym: - let s = n.sym - if isInnerProc(s, outerProc): - gatherVars(c, s.getBody, outerProc, cap) + if isInnerProc(n.sym, outerProc): + gatherVars(c, n.sym.getBody, outerProc, cap) of nkEmpty..pred(nkSym), succ(nkSym)..nkNilLit: nil else: for i in 0.. <len(n): @@ -109,29 +106,47 @@ proc searchForInnerProcs(c: PTransf, n: PNode, outerProc: PSym, proc makeClosure(c: PTransf, prc, env: PSym, info: TLineInfo): PNode = result = newNodeIT(nkClosure, info, prc.typ) result.add(newSymNode(prc)) - result.add(newSymNode(env)) + if env == nil: + result.add(newNodeIT(nkNilLit, info, getSysType(tyNil))) + else: + result.add(newSymNode(env)) proc transformInnerProcs(c: PTransf, n: PNode, outerProc, env: PSym) = case n.kind of nkSym: let innerProc = n.sym - if isInnerProc(innerProc, outerProc): - # inner proc could capture outer vars: - var param = newTemp(c, env.typ, n.info) - param.kind = skParam - addFormalParam(innerProc, param) - # 'anon' should be replaced by '(anon, env)': - IdNodeTablePut(c.transCon.mapping, innerProc, - makeClosure(c, innerProc, env, n.info)) - # access all non-local vars through the 'env' param: - var body = innerProc.getBody - # XXX does not work with recursion! - replaceVars(c, body, outerProc, param) - innerProc.ast.sons[bodyPos] = body + if isInnerProc(innerProc, outerProc) and not + containsOrIncl(c.transformedInnerProcs, innerProc.id): + if env == nil: + innerProc.ast.sons[bodyPos] = transform(c, innerProc.getBody).pnode + else: + # inner proc could capture outer vars: + var param = newTemp(c, env.typ, n.info) + + # recursive calls go through (f, hiddenParam): + IdNodeTablePut(c.transCon.mapping, innerProc, + makeClosure(c, innerProc, param, n.info)) + # access all non-local vars through the 'env' param: + replaceVars(c, innerProc.getBody, outerProc, param) + + innerProc.ast.sons[bodyPos] = transform(c, innerProc.getBody).pnode + addHiddenParam(innerProc, param) + + # 'anon' should be replaced by '(anon, env)' in the outer proc: + IdNodeTablePut(c.transCon.mapping, innerProc, + makeClosure(c, innerProc, env, n.info)) of nkEmpty..pred(nkSym), succ(nkSym)..nkNilLit: nil else: for i in 0.. <len(n): transformInnerProcs(c, n.sons[i], outerProc, env) + +template checkInvariant(n: PNode, s: PSym) = + when false: + if s.ast != n: + echo renderTree(s.ast) + echo " -------------- " + echo n.renderTree + assert s.ast == n proc newCall(a, b: PSym): PNode = result = newNodeI(nkCall, a.info) @@ -158,10 +173,13 @@ proc createEnvStmt(c: PTransf, varList: TCapture, env: PSym): PTransNode = IdNodeTablePut(c.transCon.mapping, v, fieldAccess) proc transformProcFin(c: PTransf, n: PNode, s: PSym): PTransNode = - # to be safe: XXX this a mystery how it could ever happen that: s.ast != n. - s.ast.sons[bodyPos] = n.sons[bodyPos] - if n.kind == nkMethodDef: methodDef(s, false) + if n.kind == nkLambda: + # for lambdas we transformed 'n.sons[bodyPos]', but not 'ast.n[bodyPos]'! + s.ast.sons[bodyPos] = n.sons[bodyPos] + else: + assert s.ast == n + if n.kind == nkMethodDef: methodDef(s, false) # should 's' be replaced by a tuple ('s', env)? var tc = c.transCon var repl: PNode = nil @@ -181,26 +199,35 @@ proc transformProc(c: PTransf, n: PNode): PTransNode = var s = n.sons[namePos].sym var body = s.getBody - if body.kind == nkEmpty: - return PTransNode(n) + if body.kind == nkEmpty or n.sons[bodyPos].kind == nkEmpty or + containsOrIncl(c.transformedInnerProcs, s.id): + return PTransNode(n) + + checkInvariant(n, s) - if not containsNode(body, procDefs): + if not containsNode(body, procDefs) and s.typ.callConv != ccClosure: # fast path: no inner procs, so no closure needed: n.sons[bodyPos] = PNode(transform(c, body)) + checkInvariant(n, s) return transformProcFin(c, n, s) # create environment: var cap: TCapture = @[] searchForInnerProcs(c, body, s, cap) + + var envType = newType(tyRef, s) + addSon(envType, captureToTuple(cap, s)) + if s.typ.callConv == ccClosure: + addHiddenParam(s, newTemp(c, envType, n.info)) + IdNodeTablePut(c.transCon.mapping, s, + makeClosure(c, s, nil, n.info)) if cap.len == 0: # fast path: no captured variables, so no closure needed: + transformInnerProcs(c, body, s, nil) n.sons[bodyPos] = PNode(transform(c, body)) return transformProcFin(c, n, s) - var envType = newType(tyRef, s) - addSon(envType, captureToTuple(cap, s)) - # Currently we always do a heap allocation. A simple escape analysis # could turn the closure into a stack allocation. Later versions might # implement that. This would require backend changes too though. @@ -211,11 +238,11 @@ proc transformProc(c: PTransf, n: PNode): PTransNode = # mapping entries that turn (localProc) into (localProc, env): transformInnerProcs(c, body, s, envSym) - # now we can transform 'body' as all rewriting entries have been created. - # Careful this transforms the inner procs too! + # now we can transform 'body' as all rewriting entries have been created: newBody.add(transform(c, body)) n.sons[bodyPos] = newBody.pnode result = transformProcFin(c, n, s) + checkInvariant(n, s) proc generateThunk(c: PTransf, prc: PNode, dest: PType): PNode = ## Converts 'prc' into '(thunk, nil)' so that it's compatible with |