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.Context;
  46 import jdk.nashorn.internal.runtime.logging.DebugLogger;
  47 import jdk.nashorn.internal.runtime.logging.Loggable;
  48 import jdk.nashorn.internal.runtime.logging.Logger;
  49 import jdk.nashorn.internal.runtime.options.Options;
  50 
  51 /**
  52  * Split the IR into smaller compile units.
  53  */
  54 @Logger(name="splitter")
  55 final 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