1/* 2 * Copyright (c) 2010, 2013, 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.codegen.CompilerConstants.SPLIT_PREFIX; 29 30import java.util.ArrayList; 31import java.util.HashMap; 32import java.util.List; 33import java.util.Map; 34import jdk.nashorn.internal.ir.Block; 35import jdk.nashorn.internal.ir.FunctionNode; 36import jdk.nashorn.internal.ir.LiteralNode; 37import jdk.nashorn.internal.ir.LiteralNode.ArrayLiteralNode; 38import jdk.nashorn.internal.ir.Node; 39import jdk.nashorn.internal.ir.ObjectNode; 40import jdk.nashorn.internal.ir.PropertyNode; 41import jdk.nashorn.internal.ir.SplitNode; 42import jdk.nashorn.internal.ir.Splittable; 43import jdk.nashorn.internal.ir.Statement; 44import jdk.nashorn.internal.ir.visitor.SimpleNodeVisitor; 45import jdk.nashorn.internal.runtime.Context; 46import jdk.nashorn.internal.runtime.logging.DebugLogger; 47import jdk.nashorn.internal.runtime.logging.Loggable; 48import jdk.nashorn.internal.runtime.logging.Logger; 49import jdk.nashorn.internal.runtime.options.Options; 50 51/** 52 * Split the IR into smaller compile units. 53 */ 54@Logger(name="splitter") 55final class Splitter extends SimpleNodeVisitor implements Loggable { 56 /** Current compiler. */ 57 private final Compiler compiler; 58 59 /** IR to be broken down. */ 60 private final FunctionNode outermost; 61 62 /** Compile unit for the main script. */ 63 private final CompileUnit outermostCompileUnit; 64 65 /** Cache for calculated block weights. */ 66 private final Map<Node, Long> weightCache = new HashMap<>(); 67 68 /** Weight threshold for when to start a split. */ 69 public static final long SPLIT_THRESHOLD = Options.getIntProperty("nashorn.compiler.splitter.threshold", 32 * 1024); 70 71 private final DebugLogger log; 72 73 /** 74 * Constructor. 75 * 76 * @param compiler the compiler 77 * @param functionNode function node to split 78 * @param outermostCompileUnit compile unit for outermost function, if non-lazy this is the script's compile unit 79 */ 80 public Splitter(final Compiler compiler, final FunctionNode functionNode, final CompileUnit outermostCompileUnit) { 81 this.compiler = compiler; 82 this.outermost = functionNode; 83 this.outermostCompileUnit = outermostCompileUnit; 84 this.log = initLogger(compiler.getContext()); 85 } 86 87 @Override 88 public DebugLogger initLogger(final Context context) { 89 return context.getLogger(this.getClass()); 90 } 91 92 @Override 93 public DebugLogger getLogger() { 94 return log; 95 } 96 97 /** 98 * Execute the split. 99 * @param fn the function to split 100 * @param top whether this is the topmost compiled function (it's either a program, or we're doing a recompilation). 101 */ 102 FunctionNode split(final FunctionNode fn, final boolean top) { 103 FunctionNode functionNode = fn; 104 105 log.fine("Initiating split of '", functionNode.getName(), "'"); 106 107 long weight = WeighNodes.weigh(functionNode); 108 109 // We know that our LexicalContext is empty outside the call to functionNode.accept(this) below, 110 // so we can pass null to all methods expecting a LexicalContext parameter. 111 assert lc.isEmpty() : "LexicalContext not empty"; 112 113 if (weight >= SPLIT_THRESHOLD) { 114 log.info("Splitting '", functionNode.getName(), "' as its weight ", weight, " exceeds split threshold ", SPLIT_THRESHOLD); 115 functionNode = (FunctionNode)functionNode.accept(this); 116 117 if (functionNode.isSplit()) { 118 // Weight has changed so weigh again, this time using block weight cache 119 weight = WeighNodes.weigh(functionNode, weightCache); 120 functionNode = functionNode.setBody(null, functionNode.getBody().setNeedsScope(null)); 121 } 122 123 if (weight >= SPLIT_THRESHOLD) { 124 functionNode = functionNode.setBody(null, splitBlock(functionNode.getBody(), functionNode)); 125 functionNode = functionNode.setFlag(null, FunctionNode.IS_SPLIT); 126 weight = WeighNodes.weigh(functionNode.getBody(), weightCache); 127 } 128 } 129 130 assert functionNode.getCompileUnit() == null : "compile unit already set for " + functionNode.getName(); 131 132 if (top) { 133 assert outermostCompileUnit != null : "outermost compile unit is null"; 134 functionNode = functionNode.setCompileUnit(null, outermostCompileUnit); 135 outermostCompileUnit.addWeight(weight + WeighNodes.FUNCTION_WEIGHT); 136 } else { 137 functionNode = functionNode.setCompileUnit(null, findUnit(weight)); 138 } 139 140 final Block body = functionNode.getBody(); 141 final List<FunctionNode> dc = directChildren(functionNode); 142 143 final Block newBody = (Block)body.accept(new SimpleNodeVisitor() { 144 @Override 145 public boolean enterFunctionNode(final FunctionNode nestedFunction) { 146 return dc.contains(nestedFunction); 147 } 148 149 @Override 150 public Node leaveFunctionNode(final FunctionNode nestedFunction) { 151 final FunctionNode split = new Splitter(compiler, nestedFunction, outermostCompileUnit).split(nestedFunction, false); 152 lc.replace(nestedFunction, split); 153 return split; 154 } 155 }); 156 functionNode = functionNode.setBody(null, newBody); 157 158 assert functionNode.getCompileUnit() != null; 159 160 return functionNode; 161 } 162 163 private static List<FunctionNode> directChildren(final FunctionNode functionNode) { 164 final List<FunctionNode> dc = new ArrayList<>(); 165 functionNode.accept(new SimpleNodeVisitor() { 166 @Override 167 public boolean enterFunctionNode(final FunctionNode child) { 168 if (child == functionNode) { 169 return true; 170 } 171 if (lc.getParentFunction(child) == functionNode) { 172 dc.add(child); 173 } 174 return false; 175 } 176 }); 177 return dc; 178 } 179 180 /** 181 * Override this logic to look up compile units in a different way 182 * @param weight weight needed 183 * @return compile unit 184 */ 185 protected CompileUnit findUnit(final long weight) { 186 return compiler.findUnit(weight); 187 } 188 189 /** 190 * Split a block into sub methods. 191 * 192 * @param block Block or function to split. 193 * 194 * @return new weight for the resulting block. 195 */ 196 private Block splitBlock(final Block block, final FunctionNode function) { 197 198 final List<Statement> splits = new ArrayList<>(); 199 List<Statement> statements = new ArrayList<>(); 200 long statementsWeight = 0; 201 202 for (final Statement statement : block.getStatements()) { 203 final long weight = WeighNodes.weigh(statement, weightCache); 204 205 if (statementsWeight + weight >= SPLIT_THRESHOLD || statement.isTerminal()) { 206 if (!statements.isEmpty()) { 207 splits.add(createBlockSplitNode(block, function, statements, statementsWeight)); 208 statements = new ArrayList<>(); 209 statementsWeight = 0; 210 } 211 } 212 213 if (statement.isTerminal()) { 214 splits.add(statement); 215 } else { 216 statements.add(statement); 217 statementsWeight += weight; 218 } 219 } 220 221 if (!statements.isEmpty()) { 222 splits.add(createBlockSplitNode(block, function, statements, statementsWeight)); 223 } 224 225 return block.setStatements(lc, splits); 226 } 227 228 /** 229 * Create a new split node from statements contained in a parent block. 230 * 231 * @param parent Parent block. 232 * @param statements Statements to include. 233 * 234 * @return New split node. 235 */ 236 private SplitNode createBlockSplitNode(final Block parent, final FunctionNode function, final List<Statement> statements, final long weight) { 237 final long token = parent.getToken(); 238 final int finish = parent.getFinish(); 239 final String name = function.uniqueName(SPLIT_PREFIX.symbolName()); 240 241 final Block newBlock = new Block(token, finish, statements); 242 243 return new SplitNode(name, newBlock, compiler.findUnit(weight + WeighNodes.FUNCTION_WEIGHT)); 244 } 245 246 @Override 247 public boolean enterBlock(final Block block) { 248 if (block.isCatchBlock()) { 249 return false; 250 } 251 252 final long weight = WeighNodes.weigh(block, weightCache); 253 254 if (weight < SPLIT_THRESHOLD) { 255 weightCache.put(block, weight); 256 return false; 257 } 258 259 return true; 260 } 261 262 @Override 263 public Node leaveBlock(final Block block) { 264 assert !block.isCatchBlock(); 265 266 Block newBlock = block; 267 268 // Block was heavier than SLIT_THRESHOLD in enter, but a sub-block may have 269 // been split already, so weigh again before splitting. 270 long weight = WeighNodes.weigh(block, weightCache); 271 if (weight >= SPLIT_THRESHOLD) { 272 final FunctionNode currentFunction = lc.getCurrentFunction(); 273 newBlock = splitBlock(block, currentFunction); 274 weight = WeighNodes.weigh(newBlock, weightCache); 275 lc.setFlag(currentFunction, FunctionNode.IS_SPLIT); 276 } 277 weightCache.put(newBlock, weight); 278 return newBlock; 279 } 280 281 @SuppressWarnings("rawtypes") 282 @Override 283 public Node leaveLiteralNode(final LiteralNode literal) { 284 long weight = WeighNodes.weigh(literal); 285 286 if (weight < SPLIT_THRESHOLD) { 287 return literal; 288 } 289 290 final FunctionNode functionNode = lc.getCurrentFunction(); 291 292 lc.setFlag(functionNode, FunctionNode.IS_SPLIT); 293 294 if (literal instanceof ArrayLiteralNode) { 295 final ArrayLiteralNode arrayLiteralNode = (ArrayLiteralNode) literal; 296 final Node[] value = arrayLiteralNode.getValue(); 297 final int[] postsets = arrayLiteralNode.getPostsets(); 298 final List<Splittable.SplitRange> ranges = new ArrayList<>(); 299 300 long totalWeight = 0; 301 int lo = 0; 302 303 for (int i = 0; i < postsets.length; i++) { 304 final int postset = postsets[i]; 305 final Node element = value[postset]; 306 307 weight = WeighNodes.weigh(element); 308 totalWeight += WeighNodes.AASTORE_WEIGHT + weight; 309 310 if (totalWeight >= SPLIT_THRESHOLD) { 311 final CompileUnit unit = compiler.findUnit(totalWeight - weight); 312 ranges.add(new Splittable.SplitRange(unit, lo, i)); 313 lo = i; 314 totalWeight = weight; 315 } 316 } 317 318 if (lo != postsets.length) { 319 final CompileUnit unit = compiler.findUnit(totalWeight); 320 ranges.add(new Splittable.SplitRange(unit, lo, postsets.length)); 321 } 322 323 return arrayLiteralNode.setSplitRanges(lc, ranges); 324 } 325 326 return literal; 327 } 328 329 @Override 330 public Node leaveObjectNode(final ObjectNode objectNode) { 331 long weight = WeighNodes.weigh(objectNode); 332 333 if (weight < SPLIT_THRESHOLD) { 334 return objectNode; 335 } 336 337 final FunctionNode functionNode = lc.getCurrentFunction(); 338 lc.setFlag(functionNode, FunctionNode.IS_SPLIT); 339 340 final List<Splittable.SplitRange> ranges = new ArrayList<>(); 341 final List<PropertyNode> properties = objectNode.getElements(); 342 final boolean isSpillObject = properties.size() > CodeGenerator.OBJECT_SPILL_THRESHOLD; 343 long totalWeight = 0; 344 int lo = 0; 345 346 for (int i = 0; i < properties.size(); i++) { 347 348 final PropertyNode property = properties.get(i); 349 final boolean isConstant = LiteralNode.isConstant(property.getValue()); 350 351 if (!isConstant || !isSpillObject) { 352 weight = isConstant ? 0 : WeighNodes.weigh(property.getValue()); 353 totalWeight += WeighNodes.AASTORE_WEIGHT + weight; 354 355 if (totalWeight >= SPLIT_THRESHOLD) { 356 final CompileUnit unit = compiler.findUnit(totalWeight - weight); 357 ranges.add(new Splittable.SplitRange(unit, lo, i)); 358 lo = i; 359 totalWeight = weight; 360 } 361 } 362 } 363 364 if (lo != properties.size()) { 365 final CompileUnit unit = compiler.findUnit(totalWeight); 366 ranges.add(new Splittable.SplitRange(unit, lo, properties.size())); 367 } 368 369 return objectNode.setSplitRanges(lc, ranges); 370 } 371 372 @Override 373 public boolean enterFunctionNode(final FunctionNode node) { 374 //only go into the function node for this splitter. any subfunctions are rejected 375 return node == outermost; 376 } 377} 378 379