FindScopeDepths.java revision 1203:b4d62e7260a4
192108Sphk/* 292108Sphk * Copyright (c) 2014, Oracle and/or its affiliates. All rights reserved. 392108Sphk * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 492108Sphk * 592108Sphk * This code is free software; you can redistribute it and/or modify it 692108Sphk * under the terms of the GNU General Public License version 2 only, as 792108Sphk * published by the Free Software Foundation. Oracle designates this 892108Sphk * particular file as subject to the "Classpath" exception as provided 992108Sphk * by Oracle in the LICENSE file that accompanied this code. 1092108Sphk * 1192108Sphk * This code is distributed in the hope that it will be useful, but WITHOUT 1292108Sphk * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 1392108Sphk * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 1492108Sphk * version 2 for more details (a copy is included in the LICENSE file that 1592108Sphk * accompanied this code). 1692108Sphk * 1792108Sphk * You should have received a copy of the GNU General Public License version 1892108Sphk * 2 along with this work; if not, write to the Free Software Foundation, 1992108Sphk * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 2092108Sphk * 2192108Sphk * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 2292108Sphk * or visit www.oracle.com if you need additional information or have any 2392108Sphk * questions. 2492108Sphk */ 2592108Sphk 2692108Sphkpackage jdk.nashorn.internal.codegen; 2792108Sphk 2892108Sphkimport static jdk.nashorn.internal.runtime.logging.DebugLogger.quote; 2992108Sphk 3092108Sphkimport java.util.HashMap; 3192108Sphkimport java.util.HashSet; 3292108Sphkimport java.util.Iterator; 3392108Sphkimport java.util.Map; 3492108Sphkimport java.util.Set; 3592108Sphkimport jdk.nashorn.internal.ir.Block; 3692108Sphkimport jdk.nashorn.internal.ir.FunctionNode; 3792108Sphkimport jdk.nashorn.internal.ir.FunctionNode.CompilationState; 3892108Sphkimport jdk.nashorn.internal.ir.IdentNode; 3992108Sphkimport jdk.nashorn.internal.ir.LexicalContext; 4092108Sphkimport jdk.nashorn.internal.ir.Node; 4192108Sphkimport jdk.nashorn.internal.ir.Symbol; 4292108Sphkimport jdk.nashorn.internal.ir.WithNode; 4392108Sphkimport jdk.nashorn.internal.ir.visitor.NodeVisitor; 4492108Sphkimport jdk.nashorn.internal.runtime.Context; 4592108Sphkimport jdk.nashorn.internal.runtime.RecompilableScriptFunctionData; 4692108Sphkimport jdk.nashorn.internal.runtime.logging.DebugLogger; 4792108Sphkimport jdk.nashorn.internal.runtime.logging.Loggable; 4892108Sphkimport jdk.nashorn.internal.runtime.logging.Logger; 4992108Sphk 50114216Skan/** 5192108Sphk * Establishes depth of scope for non local symbols at the start of method. 5295323Sphk * If this is a recompilation, the previous data from eager compilation is 5392108Sphk * stored in the RecompilableScriptFunctionData and is transferred to the 5492108Sphk * FunctionNode being compiled 5592108Sphk */ 5692108Sphk@Logger(name="scopedepths") 5792108Sphkfinal class FindScopeDepths extends NodeVisitor<LexicalContext> implements Loggable { 5892108Sphk 5992108Sphk private final Compiler compiler; 60111815Sphk private final Map<Integer, Map<Integer, RecompilableScriptFunctionData>> fnIdToNestedFunctions = new HashMap<>(); 61111815Sphk private final Map<Integer, Map<String, Integer>> externalSymbolDepths = new HashMap<>(); 62111815Sphk private final Map<Integer, Set<String>> internalSymbols = new HashMap<>(); 63111815Sphk private final Set<Block> withBodies = new HashSet<>(); 64111815Sphk 65111815Sphk private final DebugLogger log; 66111815Sphk 67111815Sphk private int dynamicScopeCount; 68111815Sphk 6992108Sphk FindScopeDepths(final Compiler compiler) { 7092108Sphk super(new LexicalContext()); 7192108Sphk this.compiler = compiler; 7292108Sphk this.log = initLogger(compiler.getContext()); 7392108Sphk } 7493248Sphk 75112552Sphk @Override 76112552Sphk public DebugLogger getLogger() { 7798066Sphk return log; 7892108Sphk } 7992108Sphk 80105947Sphk @Override 81105947Sphk public DebugLogger initLogger(final Context context) { 82105947Sphk return context.getLogger(this.getClass()); 83105947Sphk } 84105947Sphk 85105947Sphk static int findScopesToStart(final LexicalContext lc, final FunctionNode fn, final Block block) { 86105947Sphk final Block bodyBlock = findBodyBlock(lc, fn, block); 87105947Sphk final Iterator<Block> iter = lc.getBlocks(block); 88105947Sphk Block b = iter.next(); 89105947Sphk int scopesToStart = 0; 90105947Sphk while (true) { 91105947Sphk if (b.needsScope()) { 92105947Sphk scopesToStart++; 93105947Sphk } 94108294Sphk if (b == bodyBlock) { 95108294Sphk break; 96108294Sphk } 97108294Sphk b = iter.next(); 98108294Sphk } 99108294Sphk return scopesToStart; 100108294Sphk } 10192108Sphk 102104087Sphk static int findInternalDepth(final LexicalContext lc, final FunctionNode fn, final Block block, final Symbol symbol) { 10392108Sphk final Block bodyBlock = findBodyBlock(lc, fn, block); 10492108Sphk final Iterator<Block> iter = lc.getBlocks(block); 10592108Sphk Block b = iter.next(); 10692108Sphk int scopesToStart = 0; 10792108Sphk while (true) { 10892108Sphk if (definedInBlock(b, symbol)) { 10998066Sphk return scopesToStart; 11092108Sphk } 11192108Sphk if (b.needsScope()) { 11293248Sphk scopesToStart++; 11392108Sphk } 11492108Sphk if (b == bodyBlock) { 11592108Sphk break; //don't go past body block, but process it 11692108Sphk } 11792108Sphk b = iter.next(); 11892108Sphk } 11992108Sphk return -1; 12092108Sphk } 12192108Sphk 12292108Sphk private static boolean definedInBlock(final Block block, final Symbol symbol) { 12392108Sphk if (symbol.isGlobal()) { 12492108Sphk if (block.isGlobalScope()) { 12592108Sphk return true; 12692108Sphk } 12792108Sphk //globals cannot be defined anywhere else 12896987Sphk return false; 12992108Sphk } 13096987Sphk return block.getExistingSymbol(symbol.getName()) == symbol; 13192108Sphk } 13292108Sphk 13392108Sphk static Block findBodyBlock(final LexicalContext lc, final FunctionNode fn, final Block block) { 13492108Sphk final Iterator<Block> iter = lc.getBlocks(block); 13592108Sphk while (iter.hasNext()) { 13692108Sphk final Block next = iter.next(); 13792108Sphk if (fn.getBody() == next) { 13893250Sphk return next; 13992108Sphk } 14092108Sphk } 14192108Sphk return null; 142110540Sphk } 14396987Sphk 14492108Sphk private static Block findGlobalBlock(final LexicalContext lc, final Block block) { 14592108Sphk final Iterator<Block> iter = lc.getBlocks(block); 14692108Sphk Block globalBlock = null; 14792108Sphk while (iter.hasNext()) { 14892108Sphk globalBlock = iter.next(); 14993248Sphk } 15092108Sphk return globalBlock; 15192108Sphk } 15293776Sphk 15392108Sphk private static boolean isDynamicScopeBoundary(final FunctionNode fn) { 15496987Sphk return fn.needsDynamicScope(); 15596987Sphk } 15696987Sphk 15796987Sphk private boolean isDynamicScopeBoundary(final Block block) { 15896987Sphk return withBodies.contains(block); 15996987Sphk } 16096987Sphk 16192108Sphk @Override 16292108Sphk public boolean enterFunctionNode(final FunctionNode functionNode) { 16396987Sphk if (compiler.isOnDemandCompilation()) { 164104316Sphk return true; 165110700Sphk } 166110700Sphk 16796987Sphk if (isDynamicScopeBoundary(functionNode)) { 16896987Sphk increaseDynamicScopeCount(functionNode); 169110728Sphk } 170110710Sphk 171110710Sphk final int fnId = functionNode.getId(); 17292108Sphk Map<Integer, RecompilableScriptFunctionData> nestedFunctions = fnIdToNestedFunctions.get(fnId); 17392108Sphk if (nestedFunctions == null) { 17492108Sphk nestedFunctions = new HashMap<>(); 17592108Sphk fnIdToNestedFunctions.put(fnId, nestedFunctions); 17692108Sphk } 17792108Sphk 17892108Sphk return true; 17992108Sphk } 18092108Sphk 18192108Sphk //external symbols hold the scope depth of sc11 from global at the start of the method 18292108Sphk @Override 18392108Sphk public Node leaveFunctionNode(final FunctionNode functionNode) { 18492108Sphk final String name = functionNode.getName(); 18592108Sphk FunctionNode newFunctionNode = functionNode.setState(lc, CompilationState.SCOPE_DEPTHS_COMPUTED); 18692108Sphk 187112978Sphk if (compiler.isOnDemandCompilation()) { 188112978Sphk final RecompilableScriptFunctionData data = compiler.getScriptFunctionData(newFunctionNode.getId()); 189112978Sphk if (data.inDynamicContext()) { 19092108Sphk log.fine("Reviving scriptfunction ", quote(name), " as defined in previous (now lost) dynamic scope."); 19192108Sphk newFunctionNode = newFunctionNode.setInDynamicContext(lc); 19292108Sphk } 19392108Sphk return newFunctionNode; 194103004Sphk } 19592108Sphk 196103004Sphk if (inDynamicScope()) { 197103004Sphk log.fine("Tagging ", quote(name), " as defined in dynamic scope"); 198103004Sphk newFunctionNode = newFunctionNode.setInDynamicContext(lc); 199112978Sphk } 200112978Sphk 201112978Sphk //create recompilable scriptfunctiondata 202112978Sphk final int fnId = newFunctionNode.getId(); 203112978Sphk final Map<Integer, RecompilableScriptFunctionData> nestedFunctions = fnIdToNestedFunctions.remove(fnId); 204112978Sphk 20592108Sphk assert nestedFunctions != null; 20692479Sphk // Generate the object class and property map in case this function is ever used as constructor 20798066Sphk final RecompilableScriptFunctionData data = new RecompilableScriptFunctionData( 208112978Sphk newFunctionNode, 209112978Sphk compiler.getCodeInstaller(), 21092108Sphk ObjectClassGenerator.createAllocationStrategy(newFunctionNode.getThisProperties()), 21192108Sphk nestedFunctions, 21292108Sphk externalSymbolDepths.get(fnId), 21392108Sphk internalSymbols.get(fnId), 21492108Sphk compiler.removeSerializedAst(fnId)); 21592108Sphk 21692108Sphk if (lc.getOutermostFunction() != newFunctionNode) { 21792108Sphk final FunctionNode parentFn = lc.getParentFunction(newFunctionNode); 21892108Sphk if (parentFn != null) { 21992108Sphk fnIdToNestedFunctions.get(parentFn.getId()).put(fnId, data); 22092108Sphk } 22192108Sphk } else { 22292108Sphk compiler.setData(data); 22392108Sphk } 22492108Sphk 22592108Sphk if (isDynamicScopeBoundary(functionNode)) { 22692108Sphk decreaseDynamicScopeCount(functionNode); 22792108Sphk } 228103004Sphk 22992108Sphk return newFunctionNode; 230103004Sphk } 231103004Sphk 232103004Sphk private boolean inDynamicScope() { 233112978Sphk return dynamicScopeCount > 0; 234112978Sphk } 235112978Sphk 236112978Sphk private void increaseDynamicScopeCount(final Node node) { 237112978Sphk assert dynamicScopeCount >= 0; 238112978Sphk ++dynamicScopeCount; 239112978Sphk if (log.isEnabled()) { 240112978Sphk log.finest(quote(lc.getCurrentFunction().getName()), " ++dynamicScopeCount = ", dynamicScopeCount, " at: ", node, node.getClass()); 24192108Sphk } 24292479Sphk } 24398066Sphk 24492108Sphk private void decreaseDynamicScopeCount(final Node node) { 24592108Sphk --dynamicScopeCount; 24692108Sphk assert dynamicScopeCount >= 0; 247112978Sphk if (log.isEnabled()) { 248112978Sphk log.finest(quote(lc.getCurrentFunction().getName()), " --dynamicScopeCount = ", dynamicScopeCount, " at: ", node, node.getClass()); 249112978Sphk } 250112978Sphk } 251112978Sphk 252112978Sphk @Override 25392108Sphk public boolean enterWithNode(final WithNode node) { 25492108Sphk withBodies.add(node.getBody()); 25592108Sphk return true; 25695323Sphk } 25792108Sphk 25895323Sphk @Override 25995038Sphk public boolean enterBlock(final Block block) { 26092108Sphk if (compiler.isOnDemandCompilation()) { 26195038Sphk return true; 26292403Sphk } 26392108Sphk 26492108Sphk if (isDynamicScopeBoundary(block)) { 26592108Sphk increaseDynamicScopeCount(block); 26695323Sphk } 26795323Sphk 268104602Sphk if (!lc.isFunctionBody()) { 26992108Sphk return true; 27092108Sphk } 271112978Sphk 272112978Sphk //the below part only happens on eager compilation when we have the entire hierarchy 27392479Sphk //block is a function body 27492403Sphk final FunctionNode fn = lc.getCurrentFunction(); 275109253Sphk 27692698Sphk //get all symbols that are referenced inside this function body 27792698Sphk final Set<Symbol> symbols = new HashSet<>(); 27892698Sphk block.accept(new NodeVisitor<LexicalContext>(new LexicalContext()) { 279105551Sphk @Override 280105551Sphk public final boolean enterDefault(final Node node) { 281105180Snjl if (!compiler.isOnDemandCompilation()) { 28292698Sphk if (node instanceof IdentNode) { 28392698Sphk final Symbol symbol = ((IdentNode)node).getSymbol(); 284105551Sphk if (symbol != null && symbol.isScope()) { 285105551Sphk //if this is an internal symbol, skip it. 286105180Snjl symbols.add(symbol); 28792698Sphk } 28892698Sphk } 28993250Sphk } 290105180Snjl return true; 291105180Snjl } 29292698Sphk }); 29392698Sphk 29493250Sphk final Map<String, Integer> internals = new HashMap<>(); 295105180Snjl 296105180Snjl final Block globalBlock = findGlobalBlock(lc, block); 29792698Sphk final Block bodyBlock = findBodyBlock(lc, fn, block); 29894287Sphk 29994287Sphk assert globalBlock != null; 30094287Sphk assert bodyBlock != null; 30195038Sphk 30295038Sphk for (final Symbol symbol : symbols) { 30395038Sphk Iterator<Block> iter; 30495038Sphk 30595038Sphk final int internalDepth = findInternalDepth(lc, fn, block, symbol); 30695038Sphk final boolean internal = internalDepth >= 0; 30795038Sphk if (internal) { 30895038Sphk internals.put(symbol.getName(), internalDepth); 30995038Sphk } 31095038Sphk 31195038Sphk // if not internal, we have to continue walking until we reach the top. We 31295038Sphk // start outside the body and each new scope adds a depth count. When we 31395038Sphk // find the symbol, we store its depth count 31495038Sphk if (!internal) { 315104602Sphk int depthAtStart = 0; 31692698Sphk //not internal - keep looking. 317111119Simp iter = lc.getAncestorBlocks(bodyBlock); 31892698Sphk while (iter.hasNext()) { 31992698Sphk final Block b2 = iter.next(); 32092698Sphk if (definedInBlock(b2, symbol)) { 32192698Sphk addExternalSymbol(fn, symbol, depthAtStart); 32292698Sphk break; 323109176Sphk } 324109176Sphk if (b2.needsScope()) { 325109176Sphk depthAtStart++; 326109176Sphk } 327109176Sphk } 328109176Sphk } 32992698Sphk } 33092698Sphk 33192403Sphk addInternalSymbols(fn, internals.keySet()); 33292479Sphk 333104602Sphk if (log.isEnabled()) { 334104602Sphk log.info(fn.getName() + " internals=" + internals + " externals=" + externalSymbolDepths.get(fn.getId())); 335104602Sphk } 336104602Sphk 337104602Sphk return true; 33898066Sphk } 339109253Sphk 340104357Sphk @Override 341104357Sphk public Node leaveBlock(final Block block) { 342104357Sphk if (compiler.isOnDemandCompilation()) { 343104357Sphk return block; 344104357Sphk } 345104357Sphk if (isDynamicScopeBoundary(block)) { 346104357Sphk decreaseDynamicScopeCount(block); 347104357Sphk } 348104357Sphk return block; 349104357Sphk } 350104357Sphk 351104357Sphk private void addInternalSymbols(final FunctionNode functionNode, final Set<String> symbols) { 352104357Sphk final int fnId = functionNode.getId(); 353104357Sphk assert internalSymbols.get(fnId) == null || internalSymbols.get(fnId).equals(symbols); //e.g. cloned finally block 35492403Sphk internalSymbols.put(fnId, symbols); 35592108Sphk } 356109253Sphk 357109253Sphk private void addExternalSymbol(final FunctionNode functionNode, final Symbol symbol, final int depthAtStart) { 35892108Sphk final int fnId = functionNode.getId(); 35992108Sphk Map<String, Integer> depths = externalSymbolDepths.get(fnId); 36092108Sphk if (depths == null) { 36192108Sphk depths = new HashMap<>(); 36292108Sphk externalSymbolDepths.put(fnId, depths); 36392108Sphk } 36492108Sphk depths.put(symbol.getName(), depthAtStart); 36592108Sphk } 366110517Sphk 36792108Sphk} 36892108Sphk