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