FindScopeDepths.java revision 1350:3cb11f4d617e
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 //globals cannot be defined anywhere else 125 126 return block.isGlobalScope(); 127 } 128 return block.getExistingSymbol(symbol.getName()) == symbol; 129 } 130 131 static Block findBodyBlock(final LexicalContext lc, final FunctionNode fn, final Block block) { 132 final Iterator<Block> iter = lc.getBlocks(block); 133 while (iter.hasNext()) { 134 final Block next = iter.next(); 135 if (fn.getBody() == next) { 136 return next; 137 } 138 } 139 return null; 140 } 141 142 private static Block findGlobalBlock(final LexicalContext lc, final Block block) { 143 final Iterator<Block> iter = lc.getBlocks(block); 144 Block globalBlock = null; 145 while (iter.hasNext()) { 146 globalBlock = iter.next(); 147 } 148 return globalBlock; 149 } 150 151 private static boolean isDynamicScopeBoundary(final FunctionNode fn) { 152 return fn.needsDynamicScope(); 153 } 154 155 private boolean isDynamicScopeBoundary(final Block block) { 156 return withBodies.contains(block); 157 } 158 159 @Override 160 public boolean enterFunctionNode(final FunctionNode functionNode) { 161 if (compiler.isOnDemandCompilation()) { 162 return true; 163 } 164 165 if (isDynamicScopeBoundary(functionNode)) { 166 increaseDynamicScopeCount(functionNode); 167 } 168 169 final int fnId = functionNode.getId(); 170 Map<Integer, RecompilableScriptFunctionData> nestedFunctions = fnIdToNestedFunctions.get(fnId); 171 if (nestedFunctions == null) { 172 nestedFunctions = new HashMap<>(); 173 fnIdToNestedFunctions.put(fnId, nestedFunctions); 174 } 175 176 return true; 177 } 178 179 //external symbols hold the scope depth of sc11 from global at the start of the method 180 @Override 181 public Node leaveFunctionNode(final FunctionNode functionNode) { 182 final String name = functionNode.getName(); 183 FunctionNode newFunctionNode = functionNode.setState(lc, CompilationState.SCOPE_DEPTHS_COMPUTED); 184 185 if (compiler.isOnDemandCompilation()) { 186 final RecompilableScriptFunctionData data = compiler.getScriptFunctionData(newFunctionNode.getId()); 187 if (data.inDynamicContext()) { 188 log.fine("Reviving scriptfunction ", quote(name), " as defined in previous (now lost) dynamic scope."); 189 newFunctionNode = newFunctionNode.setInDynamicContext(lc); 190 } 191 return newFunctionNode; 192 } 193 194 if (inDynamicScope()) { 195 log.fine("Tagging ", quote(name), " as defined in dynamic scope"); 196 newFunctionNode = newFunctionNode.setInDynamicContext(lc); 197 } 198 199 //create recompilable scriptfunctiondata 200 final int fnId = newFunctionNode.getId(); 201 final Map<Integer, RecompilableScriptFunctionData> nestedFunctions = fnIdToNestedFunctions.remove(fnId); 202 203 assert nestedFunctions != null; 204 // Generate the object class and property map in case this function is ever used as constructor 205 final RecompilableScriptFunctionData data = new RecompilableScriptFunctionData( 206 newFunctionNode, 207 compiler.getCodeInstaller(), 208 ObjectClassGenerator.createAllocationStrategy(newFunctionNode.getThisProperties(), compiler.getContext().useDualFields()), 209 nestedFunctions, 210 externalSymbolDepths.get(fnId), 211 internalSymbols.get(fnId), 212 compiler.removeSerializedAst(fnId)); 213 214 if (lc.getOutermostFunction() != newFunctionNode) { 215 final FunctionNode parentFn = lc.getParentFunction(newFunctionNode); 216 if (parentFn != null) { 217 fnIdToNestedFunctions.get(parentFn.getId()).put(fnId, data); 218 } 219 } else { 220 compiler.setData(data); 221 } 222 223 if (isDynamicScopeBoundary(functionNode)) { 224 decreaseDynamicScopeCount(functionNode); 225 } 226 227 return newFunctionNode; 228 } 229 230 private boolean inDynamicScope() { 231 return dynamicScopeCount > 0; 232 } 233 234 private void increaseDynamicScopeCount(final Node node) { 235 assert dynamicScopeCount >= 0; 236 ++dynamicScopeCount; 237 if (log.isEnabled()) { 238 log.finest(quote(lc.getCurrentFunction().getName()), " ++dynamicScopeCount = ", dynamicScopeCount, " at: ", node, node.getClass()); 239 } 240 } 241 242 private void decreaseDynamicScopeCount(final Node node) { 243 --dynamicScopeCount; 244 assert dynamicScopeCount >= 0; 245 if (log.isEnabled()) { 246 log.finest(quote(lc.getCurrentFunction().getName()), " --dynamicScopeCount = ", dynamicScopeCount, " at: ", node, node.getClass()); 247 } 248 } 249 250 @Override 251 public boolean enterWithNode(final WithNode node) { 252 withBodies.add(node.getBody()); 253 return true; 254 } 255 256 @Override 257 public boolean enterBlock(final Block block) { 258 if (compiler.isOnDemandCompilation()) { 259 return true; 260 } 261 262 if (isDynamicScopeBoundary(block)) { 263 increaseDynamicScopeCount(block); 264 } 265 266 if (!lc.isFunctionBody()) { 267 return true; 268 } 269 270 //the below part only happens on eager compilation when we have the entire hierarchy 271 //block is a function body 272 final FunctionNode fn = lc.getCurrentFunction(); 273 274 //get all symbols that are referenced inside this function body 275 final Set<Symbol> symbols = new HashSet<>(); 276 block.accept(new NodeVisitor<LexicalContext>(new LexicalContext()) { 277 @Override 278 public final boolean enterDefault(final Node node) { 279 if (!compiler.isOnDemandCompilation()) { 280 if (node instanceof IdentNode) { 281 final Symbol symbol = ((IdentNode)node).getSymbol(); 282 if (symbol != null && symbol.isScope()) { 283 //if this is an internal symbol, skip it. 284 symbols.add(symbol); 285 } 286 } 287 } 288 return true; 289 } 290 }); 291 292 final Map<String, Integer> internals = new HashMap<>(); 293 294 final Block globalBlock = findGlobalBlock(lc, block); 295 final Block bodyBlock = findBodyBlock(lc, fn, block); 296 297 assert globalBlock != null; 298 assert bodyBlock != null; 299 300 for (final Symbol symbol : symbols) { 301 Iterator<Block> iter; 302 303 final int internalDepth = findInternalDepth(lc, fn, block, symbol); 304 final boolean internal = internalDepth >= 0; 305 if (internal) { 306 internals.put(symbol.getName(), internalDepth); 307 } 308 309 // if not internal, we have to continue walking until we reach the top. We 310 // start outside the body and each new scope adds a depth count. When we 311 // find the symbol, we store its depth count 312 if (!internal) { 313 int depthAtStart = 0; 314 //not internal - keep looking. 315 iter = lc.getAncestorBlocks(bodyBlock); 316 while (iter.hasNext()) { 317 final Block b2 = iter.next(); 318 if (definedInBlock(b2, symbol)) { 319 addExternalSymbol(fn, symbol, depthAtStart); 320 break; 321 } 322 if (b2.needsScope()) { 323 depthAtStart++; 324 } 325 } 326 } 327 } 328 329 addInternalSymbols(fn, internals.keySet()); 330 331 if (log.isEnabled()) { 332 log.info(fn.getName() + " internals=" + internals + " externals=" + externalSymbolDepths.get(fn.getId())); 333 } 334 335 return true; 336 } 337 338 @Override 339 public Node leaveBlock(final Block block) { 340 if (compiler.isOnDemandCompilation()) { 341 return block; 342 } 343 if (isDynamicScopeBoundary(block)) { 344 decreaseDynamicScopeCount(block); 345 } 346 return block; 347 } 348 349 private void addInternalSymbols(final FunctionNode functionNode, final Set<String> symbols) { 350 final int fnId = functionNode.getId(); 351 assert internalSymbols.get(fnId) == null || internalSymbols.get(fnId).equals(symbols); //e.g. cloned finally block 352 internalSymbols.put(fnId, symbols); 353 } 354 355 private void addExternalSymbol(final FunctionNode functionNode, final Symbol symbol, final int depthAtStart) { 356 final int fnId = functionNode.getId(); 357 Map<String, Integer> depths = externalSymbolDepths.get(fnId); 358 if (depths == null) { 359 depths = new HashMap<>(); 360 externalSymbolDepths.put(fnId, depths); 361 } 362 depths.put(symbol.getName(), depthAtStart); 363 } 364 365} 366