FindScopeDepths.java revision 1245:c55ce3738888
1/* 2 * Copyright (c) 2014, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. Oracle designates this 8 * particular file as subject to the "Classpath" exception as provided 9 * by Oracle in the LICENSE file that accompanied this code. 10 * 11 * This code is distributed in the hope that it will be useful, but WITHOUT 12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14 * version 2 for more details (a copy is included in the LICENSE file that 15 * accompanied this code). 16 * 17 * You should have received a copy of the GNU General Public License version 18 * 2 along with this work; if not, write to the Free Software Foundation, 19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 20 * 21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 22 * or visit www.oracle.com if you need additional information or have any 23 * questions. 24 */ 25 26package jdk.nashorn.internal.codegen; 27 28import static jdk.nashorn.internal.runtime.logging.DebugLogger.quote; 29 30import java.util.HashMap; 31import java.util.HashSet; 32import java.util.Iterator; 33import java.util.Map; 34import java.util.Set; 35import jdk.nashorn.internal.ir.Block; 36import jdk.nashorn.internal.ir.FunctionNode; 37import jdk.nashorn.internal.ir.FunctionNode.CompilationState; 38import jdk.nashorn.internal.ir.IdentNode; 39import jdk.nashorn.internal.ir.LexicalContext; 40import jdk.nashorn.internal.ir.Node; 41import jdk.nashorn.internal.ir.Symbol; 42import jdk.nashorn.internal.ir.WithNode; 43import jdk.nashorn.internal.ir.visitor.NodeVisitor; 44import jdk.nashorn.internal.runtime.Context; 45import jdk.nashorn.internal.runtime.RecompilableScriptFunctionData; 46import jdk.nashorn.internal.runtime.logging.DebugLogger; 47import jdk.nashorn.internal.runtime.logging.Loggable; 48import jdk.nashorn.internal.runtime.logging.Logger; 49 50/** 51 * Establishes depth of scope for non local symbols at the start of method. 52 * If this is a recompilation, the previous data from eager compilation is 53 * stored in the RecompilableScriptFunctionData and is transferred to the 54 * FunctionNode being compiled 55 */ 56@Logger(name="scopedepths") 57final class FindScopeDepths extends NodeVisitor<LexicalContext> implements Loggable { 58 59 private final Compiler compiler; 60 private final Map<Integer, Map<Integer, RecompilableScriptFunctionData>> fnIdToNestedFunctions = new HashMap<>(); 61 private final Map<Integer, Map<String, Integer>> externalSymbolDepths = new HashMap<>(); 62 private final Map<Integer, Set<String>> internalSymbols = new HashMap<>(); 63 private final Set<Block> withBodies = new HashSet<>(); 64 65 private final DebugLogger log; 66 67 private int dynamicScopeCount; 68 69 FindScopeDepths(final Compiler compiler) { 70 super(new LexicalContext()); 71 this.compiler = compiler; 72 this.log = initLogger(compiler.getContext()); 73 } 74 75 @Override 76 public DebugLogger getLogger() { 77 return log; 78 } 79 80 @Override 81 public DebugLogger initLogger(final Context context) { 82 return context.getLogger(this.getClass()); 83 } 84 85 static int findScopesToStart(final LexicalContext lc, final FunctionNode fn, final Block block) { 86 final Block bodyBlock = findBodyBlock(lc, fn, block); 87 final Iterator<Block> iter = lc.getBlocks(block); 88 Block b = iter.next(); 89 int scopesToStart = 0; 90 while (true) { 91 if (b.needsScope()) { 92 scopesToStart++; 93 } 94 if (b == bodyBlock) { 95 break; 96 } 97 b = iter.next(); 98 } 99 return scopesToStart; 100 } 101 102 static int findInternalDepth(final LexicalContext lc, final FunctionNode fn, final Block block, final Symbol symbol) { 103 final Block bodyBlock = findBodyBlock(lc, fn, block); 104 final Iterator<Block> iter = lc.getBlocks(block); 105 Block b = iter.next(); 106 int scopesToStart = 0; 107 while (true) { 108 if (definedInBlock(b, symbol)) { 109 return scopesToStart; 110 } 111 if (b.needsScope()) { 112 scopesToStart++; 113 } 114 if (b == bodyBlock) { 115 break; //don't go past body block, but process it 116 } 117 b = iter.next(); 118 } 119 return -1; 120 } 121 122 private static boolean definedInBlock(final Block block, final Symbol symbol) { 123 if (symbol.isGlobal()) { 124 if (block.isGlobalScope()) { 125 return true; 126 } 127 //globals cannot be defined anywhere else 128 return false; 129 } 130 return block.getExistingSymbol(symbol.getName()) == symbol; 131 } 132 133 static Block findBodyBlock(final LexicalContext lc, final FunctionNode fn, final Block block) { 134 final Iterator<Block> iter = lc.getBlocks(block); 135 while (iter.hasNext()) { 136 final Block next = iter.next(); 137 if (fn.getBody() == next) { 138 return next; 139 } 140 } 141 return null; 142 } 143 144 private static Block findGlobalBlock(final LexicalContext lc, final Block block) { 145 final Iterator<Block> iter = lc.getBlocks(block); 146 Block globalBlock = null; 147 while (iter.hasNext()) { 148 globalBlock = iter.next(); 149 } 150 return globalBlock; 151 } 152 153 private static boolean isDynamicScopeBoundary(final FunctionNode fn) { 154 return fn.needsDynamicScope(); 155 } 156 157 private boolean isDynamicScopeBoundary(final Block block) { 158 return withBodies.contains(block); 159 } 160 161 @Override 162 public boolean enterFunctionNode(final FunctionNode functionNode) { 163 if (compiler.isOnDemandCompilation()) { 164 return true; 165 } 166 167 if (isDynamicScopeBoundary(functionNode)) { 168 increaseDynamicScopeCount(functionNode); 169 } 170 171 final int fnId = functionNode.getId(); 172 Map<Integer, RecompilableScriptFunctionData> nestedFunctions = fnIdToNestedFunctions.get(fnId); 173 if (nestedFunctions == null) { 174 nestedFunctions = new HashMap<>(); 175 fnIdToNestedFunctions.put(fnId, nestedFunctions); 176 } 177 178 return true; 179 } 180 181 //external symbols hold the scope depth of sc11 from global at the start of the method 182 @Override 183 public Node leaveFunctionNode(final FunctionNode functionNode) { 184 final String name = functionNode.getName(); 185 FunctionNode newFunctionNode = functionNode.setState(lc, CompilationState.SCOPE_DEPTHS_COMPUTED); 186 187 if (compiler.isOnDemandCompilation()) { 188 final RecompilableScriptFunctionData data = compiler.getScriptFunctionData(newFunctionNode.getId()); 189 if (data.inDynamicContext()) { 190 log.fine("Reviving scriptfunction ", quote(name), " as defined in previous (now lost) dynamic scope."); 191 newFunctionNode = newFunctionNode.setInDynamicContext(lc); 192 } 193 return newFunctionNode; 194 } 195 196 if (inDynamicScope()) { 197 log.fine("Tagging ", quote(name), " as defined in dynamic scope"); 198 newFunctionNode = newFunctionNode.setInDynamicContext(lc); 199 } 200 201 //create recompilable scriptfunctiondata 202 final int fnId = newFunctionNode.getId(); 203 final Map<Integer, RecompilableScriptFunctionData> nestedFunctions = fnIdToNestedFunctions.remove(fnId); 204 205 assert nestedFunctions != null; 206 // Generate the object class and property map in case this function is ever used as constructor 207 final RecompilableScriptFunctionData data = new RecompilableScriptFunctionData( 208 newFunctionNode, 209 compiler.getCodeInstaller(), 210 ObjectClassGenerator.createAllocationStrategy(newFunctionNode.getThisProperties(), compiler.getContext().useDualFields()), 211 nestedFunctions, 212 externalSymbolDepths.get(fnId), 213 internalSymbols.get(fnId), 214 compiler.removeSerializedAst(fnId)); 215 216 if (lc.getOutermostFunction() != newFunctionNode) { 217 final FunctionNode parentFn = lc.getParentFunction(newFunctionNode); 218 if (parentFn != null) { 219 fnIdToNestedFunctions.get(parentFn.getId()).put(fnId, data); 220 } 221 } else { 222 compiler.setData(data); 223 } 224 225 if (isDynamicScopeBoundary(functionNode)) { 226 decreaseDynamicScopeCount(functionNode); 227 } 228 229 return newFunctionNode; 230 } 231 232 private boolean inDynamicScope() { 233 return dynamicScopeCount > 0; 234 } 235 236 private void increaseDynamicScopeCount(final Node node) { 237 assert dynamicScopeCount >= 0; 238 ++dynamicScopeCount; 239 if (log.isEnabled()) { 240 log.finest(quote(lc.getCurrentFunction().getName()), " ++dynamicScopeCount = ", dynamicScopeCount, " at: ", node, node.getClass()); 241 } 242 } 243 244 private void decreaseDynamicScopeCount(final Node node) { 245 --dynamicScopeCount; 246 assert dynamicScopeCount >= 0; 247 if (log.isEnabled()) { 248 log.finest(quote(lc.getCurrentFunction().getName()), " --dynamicScopeCount = ", dynamicScopeCount, " at: ", node, node.getClass()); 249 } 250 } 251 252 @Override 253 public boolean enterWithNode(final WithNode node) { 254 withBodies.add(node.getBody()); 255 return true; 256 } 257 258 @Override 259 public boolean enterBlock(final Block block) { 260 if (compiler.isOnDemandCompilation()) { 261 return true; 262 } 263 264 if (isDynamicScopeBoundary(block)) { 265 increaseDynamicScopeCount(block); 266 } 267 268 if (!lc.isFunctionBody()) { 269 return true; 270 } 271 272 //the below part only happens on eager compilation when we have the entire hierarchy 273 //block is a function body 274 final FunctionNode fn = lc.getCurrentFunction(); 275 276 //get all symbols that are referenced inside this function body 277 final Set<Symbol> symbols = new HashSet<>(); 278 block.accept(new NodeVisitor<LexicalContext>(new LexicalContext()) { 279 @Override 280 public final boolean enterDefault(final Node node) { 281 if (!compiler.isOnDemandCompilation()) { 282 if (node instanceof IdentNode) { 283 final Symbol symbol = ((IdentNode)node).getSymbol(); 284 if (symbol != null && symbol.isScope()) { 285 //if this is an internal symbol, skip it. 286 symbols.add(symbol); 287 } 288 } 289 } 290 return true; 291 } 292 }); 293 294 final Map<String, Integer> internals = new HashMap<>(); 295 296 final Block globalBlock = findGlobalBlock(lc, block); 297 final Block bodyBlock = findBodyBlock(lc, fn, block); 298 299 assert globalBlock != null; 300 assert bodyBlock != null; 301 302 for (final Symbol symbol : symbols) { 303 Iterator<Block> iter; 304 305 final int internalDepth = findInternalDepth(lc, fn, block, symbol); 306 final boolean internal = internalDepth >= 0; 307 if (internal) { 308 internals.put(symbol.getName(), internalDepth); 309 } 310 311 // if not internal, we have to continue walking until we reach the top. We 312 // start outside the body and each new scope adds a depth count. When we 313 // find the symbol, we store its depth count 314 if (!internal) { 315 int depthAtStart = 0; 316 //not internal - keep looking. 317 iter = lc.getAncestorBlocks(bodyBlock); 318 while (iter.hasNext()) { 319 final Block b2 = iter.next(); 320 if (definedInBlock(b2, symbol)) { 321 addExternalSymbol(fn, symbol, depthAtStart); 322 break; 323 } 324 if (b2.needsScope()) { 325 depthAtStart++; 326 } 327 } 328 } 329 } 330 331 addInternalSymbols(fn, internals.keySet()); 332 333 if (log.isEnabled()) { 334 log.info(fn.getName() + " internals=" + internals + " externals=" + externalSymbolDepths.get(fn.getId())); 335 } 336 337 return true; 338 } 339 340 @Override 341 public Node leaveBlock(final Block block) { 342 if (compiler.isOnDemandCompilation()) { 343 return block; 344 } 345 if (isDynamicScopeBoundary(block)) { 346 decreaseDynamicScopeCount(block); 347 } 348 return block; 349 } 350 351 private void addInternalSymbols(final FunctionNode functionNode, final Set<String> symbols) { 352 final int fnId = functionNode.getId(); 353 assert internalSymbols.get(fnId) == null || internalSymbols.get(fnId).equals(symbols); //e.g. cloned finally block 354 internalSymbols.put(fnId, symbols); 355 } 356 357 private void addExternalSymbol(final FunctionNode functionNode, final Symbol symbol, final int depthAtStart) { 358 final int fnId = functionNode.getId(); 359 Map<String, Integer> depths = externalSymbolDepths.get(fnId); 360 if (depths == null) { 361 depths = new HashMap<>(); 362 externalSymbolDepths.put(fnId, depths); 363 } 364 depths.put(symbol.getName(), depthAtStart); 365 } 366 367} 368