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.LiteralNode;
37 import jdk.nashorn.internal.ir.LiteralNode.ArrayLiteralNode;
38 import jdk.nashorn.internal.ir.Node;
39 import jdk.nashorn.internal.ir.ObjectNode;
40 import jdk.nashorn.internal.ir.PropertyNode;
41 import jdk.nashorn.internal.ir.SplitNode;
42 import jdk.nashorn.internal.ir.Splittable;
43 import jdk.nashorn.internal.ir.Statement;
44 import jdk.nashorn.internal.ir.VarNode;
45 import jdk.nashorn.internal.ir.visitor.SimpleNodeVisitor;
46 import jdk.nashorn.internal.runtime.Context;
47 import jdk.nashorn.internal.runtime.logging.DebugLogger;
48 import jdk.nashorn.internal.runtime.logging.Loggable;
49 import jdk.nashorn.internal.runtime.logging.Logger;
50 import jdk.nashorn.internal.runtime.options.Options;
51
52 /**
53 * Split the IR into smaller compile units.
54 */
55 @Logger(name="splitter")
56 final class Splitter extends SimpleNodeVisitor implements Loggable {
57 /** Current compiler. */
58 private final Compiler compiler;
59
60 /** IR to be broken down. */
61 private final FunctionNode outermost;
62
63 /** Compile unit for the main script. */
64 private final CompileUnit outermostCompileUnit;
65
66 /** Cache for calculated block weights. */
67 private final Map<Node, Long> weightCache = new HashMap<>();
68
69 /** Weight threshold for when to start a split. */
70 public static final long SPLIT_THRESHOLD = Options.getIntProperty("nashorn.compiler.splitter.threshold", 32 * 1024);
71
72 private final DebugLogger log;
73
74 /**
75 * Constructor.
76 *
77 * @param compiler the compiler
78 * @param functionNode function node to split
79 * @param outermostCompileUnit compile unit for outermost function, if non-lazy this is the script's compile unit
80 */
81 public Splitter(final Compiler compiler, final FunctionNode functionNode, final CompileUnit outermostCompileUnit) {
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 function '", 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 SimpleNodeVisitor() {
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;
162 }
163
164 private static List<FunctionNode> directChildren(final FunctionNode functionNode) {
165 final List<FunctionNode> dc = new ArrayList<>();
166 functionNode.accept(new SimpleNodeVisitor() {
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 final boolean isBlockScopedVarNode = isBlockScopedVarNode(statement);
206
207 if (statementsWeight + weight >= SPLIT_THRESHOLD || statement.isTerminal() || isBlockScopedVarNode) {
208 if (!statements.isEmpty()) {
209 splits.add(createBlockSplitNode(block, function, statements, statementsWeight));
210 statements = new ArrayList<>();
211 statementsWeight = 0;
212 }
213 }
214
215 if (statement.isTerminal() || isBlockScopedVarNode) {
216 splits.add(statement);
217 } else {
218 statements.add(statement);
219 statementsWeight += weight;
220 }
221 }
222
223 if (!statements.isEmpty()) {
224 splits.add(createBlockSplitNode(block, function, statements, statementsWeight));
225 }
226
227 return block.setStatements(lc, splits);
228 }
229
230 /**
231 * Create a new split node from statements contained in a parent block.
232 *
233 * @param parent Parent block.
234 * @param statements Statements to include.
235 *
236 * @return New split node.
237 */
238 private SplitNode createBlockSplitNode(final Block parent, final FunctionNode function, final List<Statement> statements, final long weight) {
239 final long token = parent.getToken();
240 final int finish = parent.getFinish();
241 final String name = function.uniqueName(SPLIT_PREFIX.symbolName());
242
243 final Block newBlock = new Block(token, finish, statements);
244
245 return new SplitNode(name, newBlock, compiler.findUnit(weight + WeighNodes.FUNCTION_WEIGHT));
246 }
247
248 private boolean isBlockScopedVarNode(final Statement statement) {
249 return statement instanceof VarNode && ((VarNode) statement).isBlockScoped();
250 }
251
252 @Override
253 public boolean enterBlock(final Block block) {
254 if (block.isCatchBlock()) {
255 return false;
256 }
257
258 final long weight = WeighNodes.weigh(block, weightCache);
259
260 if (weight < SPLIT_THRESHOLD) {
261 weightCache.put(block, weight);
262 return false;
263 }
264
265 return true;
266 }
267
268 @Override
269 public Node leaveBlock(final Block block) {
270 assert !block.isCatchBlock();
271
272 Block newBlock = block;
273
274 // Block was heavier than SLIT_THRESHOLD in enter, but a sub-block may have
275 // been split already, so weigh again before splitting.
276 long weight = WeighNodes.weigh(block, weightCache);
277 if (weight >= SPLIT_THRESHOLD) {
278 final FunctionNode currentFunction = lc.getCurrentFunction();
279 newBlock = splitBlock(block, currentFunction);
280 weight = WeighNodes.weigh(newBlock, weightCache);
281 lc.setFlag(currentFunction, FunctionNode.IS_SPLIT);
282 }
283 weightCache.put(newBlock, weight);
284 return newBlock;
285 }
286
287 @SuppressWarnings("rawtypes")
288 @Override
289 public Node leaveLiteralNode(final LiteralNode literal) {
290 final long weight = WeighNodes.weigh(literal);
291
292 if (weight < SPLIT_THRESHOLD) {
293 return literal;
294 }
295
296 final FunctionNode functionNode = lc.getCurrentFunction();
297
298 lc.setFlag(functionNode, FunctionNode.IS_SPLIT);
299
300 if (literal instanceof ArrayLiteralNode) {
301 final ArrayLiteralNode arrayLiteralNode = (ArrayLiteralNode) literal;
302 final Node[] value = arrayLiteralNode.getValue();
303 final int[] postsets = arrayLiteralNode.getPostsets();
304 final List<Splittable.SplitRange> ranges = new ArrayList<>();
305
306 long totalWeight = 0;
307 int lo = 0;
308
309 for (int i = 0; i < postsets.length; i++) {
310 final int postset = postsets[i];
311 final Node element = value[postset];
312
313 final long elementWeight = WeighNodes.weigh(element);
314 totalWeight += WeighNodes.AASTORE_WEIGHT + elementWeight;
315
316 if (totalWeight >= SPLIT_THRESHOLD) {
317 final CompileUnit unit = compiler.findUnit(totalWeight - elementWeight);
318 ranges.add(new Splittable.SplitRange(unit, lo, i));
319 lo = i;
320 totalWeight = elementWeight;
321 }
322 }
323
324 if (lo != postsets.length) {
325 final CompileUnit unit = compiler.findUnit(totalWeight);
326 ranges.add(new Splittable.SplitRange(unit, lo, postsets.length));
327 }
328
329 log.info("Splitting array literal in '", functionNode.getName(), "' as its weight ", weight, " exceeds split threshold ", SPLIT_THRESHOLD);
330
331 return arrayLiteralNode.setSplitRanges(lc, ranges);
332 }
333
334 return literal;
335 }
336
337 @Override
338 public Node leaveObjectNode(final ObjectNode objectNode) {
339 final long weight = WeighNodes.weigh(objectNode);
340
341 if (weight < SPLIT_THRESHOLD) {
342 return objectNode;
343 }
344
345 final FunctionNode functionNode = lc.getCurrentFunction();
346 lc.setFlag(functionNode, FunctionNode.IS_SPLIT);
347
348 final List<Splittable.SplitRange> ranges = new ArrayList<>();
349 final List<PropertyNode> properties = objectNode.getElements();
350 final boolean isSpillObject = properties.size() > CodeGenerator.OBJECT_SPILL_THRESHOLD;
351 long totalWeight = 0;
352 int lo = 0;
353
354 for (int i = 0; i < properties.size(); i++) {
355
356 final PropertyNode property = properties.get(i);
357 final boolean isConstant = LiteralNode.isConstant(property.getValue());
358
359 if (!isConstant || !isSpillObject) {
360 final long propertyWeight = isConstant ? 0 : WeighNodes.weigh(property.getValue());
361 totalWeight += WeighNodes.AASTORE_WEIGHT + propertyWeight;
362
363 if (totalWeight >= SPLIT_THRESHOLD) {
364 final CompileUnit unit = compiler.findUnit(totalWeight - propertyWeight);
365 ranges.add(new Splittable.SplitRange(unit, lo, i));
366 lo = i;
367 totalWeight = propertyWeight;
368 }
369 }
370 }
371
372 if (lo != properties.size()) {
373 final CompileUnit unit = compiler.findUnit(totalWeight);
374 ranges.add(new Splittable.SplitRange(unit, lo, properties.size()));
375 }
376
377 log.info("Splitting object node in '", functionNode.getName(), "' as its weight ", weight, " exceeds split threshold ", SPLIT_THRESHOLD);
378
379 return objectNode.setSplitRanges(lc, ranges);
380 }
381
382 @Override
383 public boolean enterFunctionNode(final FunctionNode node) {
384 //only go into the function node for this splitter. any subfunctions are rejected
385 return node == outermost;
386 }
387 }
388