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