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