Java example source code file (RangeAnalyzer.java)

This example Java source code file (RangeAnalyzer.java) is included in the alvinalexander.com "Java Source Code Warehouse" project. The intent of this project is to help you "Learn Java by Example" ^TM.

Learn more about this Java project at its project page.

Java - Java tags/keywords

binarynode, debuglogger, expression, fornode, hashset, lexicalcontext, literalnode, loopnode, node, override, range, rangeanalyzer, symbol, unarynode, util

The RangeAnalyzer.java Java example source code

/*
 * Copyright (c) 2010, 2013, Oracle and/or its affiliates. All rights reserved.
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
 *
 * This code is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License version 2 only, as
 * published by the Free Software Foundation.  Oracle designates this
 * particular file as subject to the "Classpath" exception as provided
 * by Oracle in the LICENSE file that accompanied this code.
 *
 * This code is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
 * version 2 for more details (a copy is included in the LICENSE file that
 * accompanied this code).
 *
 * You should have received a copy of the GNU General Public License version
 * 2 along with this work; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
 *
 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
 * or visit www.oracle.com if you need additional information or have any
 * questions.
 */

package jdk.nashorn.internal.codegen;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import jdk.nashorn.internal.codegen.types.Range;
import jdk.nashorn.internal.codegen.types.Type;
import jdk.nashorn.internal.ir.Assignment;
import jdk.nashorn.internal.ir.BinaryNode;
import jdk.nashorn.internal.ir.Expression;
import jdk.nashorn.internal.ir.ForNode;
import jdk.nashorn.internal.ir.IdentNode;
import jdk.nashorn.internal.ir.LexicalContext;
import jdk.nashorn.internal.ir.LiteralNode;
import jdk.nashorn.internal.ir.LiteralNode.ArrayLiteralNode;
import jdk.nashorn.internal.ir.LoopNode;
import jdk.nashorn.internal.ir.Node;
import jdk.nashorn.internal.ir.RuntimeNode;
import jdk.nashorn.internal.ir.Symbol;
import jdk.nashorn.internal.ir.UnaryNode;
import jdk.nashorn.internal.ir.VarNode;
import jdk.nashorn.internal.ir.visitor.NodeOperatorVisitor;
import jdk.nashorn.internal.ir.visitor.NodeVisitor;
import jdk.nashorn.internal.parser.TokenType;
import jdk.nashorn.internal.runtime.DebugLogger;

/**
 * Range analysis and narrowing of type where it can be proven
 * that there is no spillover, e.g.
 *
 *  function func(c) {
 *    var v = c & 0xfff;
 *    var w = c & 0xeee;
 *    var x = v * w;
 *    return x;
 *  }
 *
 *  Proves that the multiplication never exceeds 24 bits and can thus be an int
 */
final class RangeAnalyzer extends NodeOperatorVisitor<LexicalContext> {
    static final DebugLogger LOG = new DebugLogger("ranges");

    private static final Range.Functionality RANGE = new Range.Functionality(LOG);

    private final Map<LoopNode, Symbol> loopCounters = new HashMap<>();

    RangeAnalyzer() {
        super(new LexicalContext());
    }

    @Override
    public boolean enterForNode(final ForNode forNode) {
        //conservatively attempt to identify the loop counter. Null means that it wasn't
        //properly identified and that no optimizations can be made with it - its range is
        //simply unknown in that case, if it is assigned in the loop
        final Symbol counter = findLoopCounter(forNode);
        LOG.fine("Entering forNode " + forNode + " counter = " + counter);
        if (counter != null && !assignedInLoop(forNode,  counter)) {
            loopCounters.put(forNode, counter);
        }
        return true;
    }

    //destination visited
    private Symbol setRange(final Expression dest, final Range range) {
        if (range.isUnknown()) {
            return null;
        }

        final Symbol symbol = dest.getSymbol();
        assert symbol != null : dest + " " + dest.getClass() + " has no symbol";
        assert symbol.getRange() != null : symbol + " has no range";
        final Range symRange = RANGE.join(symbol.getRange(), range);

        //anything assigned in the loop, not being the safe loop counter(s) invalidates its entire range
        if (lc.inLoop() && !isLoopCounter(lc.getCurrentLoop(), symbol)) {
            symbol.setRange(Range.createGenericRange());
            return symbol;
        }

        if (!symRange.equals(symbol.getRange())) {
            LOG.fine("Modify range for " + dest + " " + symbol + " from " + symbol.getRange() + " to " + symRange + " (in node = " + dest + ")" );
            symbol.setRange(symRange);
        }

        return null;
    }

    @Override
    public Node leaveADD(final BinaryNode node) {
        setRange(node, RANGE.add(node.lhs().getSymbol().getRange(), node.rhs().getSymbol().getRange()));
        return node;
    }

    @Override
    public Node leaveSUB(final BinaryNode node) {
        setRange(node, RANGE.sub(node.lhs().getSymbol().getRange(), node.rhs().getSymbol().getRange()));
        return node;
    }

    @Override
    public Node leaveMUL(final BinaryNode node) {
        setRange(node, RANGE.mul(node.lhs().getSymbol().getRange(), node.rhs().getSymbol().getRange()));
        return node;
    }

    @Override
    public Node leaveDIV(final BinaryNode node) {
        setRange(node, RANGE.div(node.lhs().getSymbol().getRange(), node.rhs().getSymbol().getRange()));
        return node;
    }

    @Override
    public Node leaveMOD(final BinaryNode node) {
        setRange(node, RANGE.mod(node.lhs().getSymbol().getRange(), node.rhs().getSymbol().getRange()));
        return node;
    }

    @Override
    public Node leaveBIT_AND(final BinaryNode node) {
        setRange(node, RANGE.and(node.lhs().getSymbol().getRange(), node.rhs().getSymbol().getRange()));
        return node;
    }

    @Override
    public Node leaveBIT_OR(final BinaryNode node) {
        setRange(node, RANGE.or(node.lhs().getSymbol().getRange(), node.rhs().getSymbol().getRange()));
        return node;
    }

    @Override
    public Node leaveBIT_XOR(final BinaryNode node) {
        setRange(node, RANGE.xor(node.lhs().getSymbol().getRange(), node.rhs().getSymbol().getRange()));
        return node;
    }

    @Override
    public Node leaveSAR(final BinaryNode node) {
        setRange(node, RANGE.sar(node.lhs().getSymbol().getRange(), node.rhs().getSymbol().getRange()));
        return node;
    }

    @Override
    public Node leaveSHL(final BinaryNode node) {
        setRange(node, RANGE.shl(node.lhs().getSymbol().getRange(), node.rhs().getSymbol().getRange()));
        return node;
    }

    @Override
    public Node leaveSHR(final BinaryNode node) {
        setRange(node, RANGE.shr(node.lhs().getSymbol().getRange(), node.rhs().getSymbol().getRange()));
        return node;
    }

    private Node leaveCmp(final BinaryNode node) {
        setRange(node, Range.createTypeRange(Type.BOOLEAN));
        return node;
    }

    @Override
    public Node leaveEQ(final BinaryNode node) {
        return leaveCmp(node);
    }

    @Override
    public Node leaveEQ_STRICT(final BinaryNode node) {
        return leaveCmp(node);
    }

    @Override
    public Node leaveNE(final BinaryNode node) {
        return leaveCmp(node);
    }

    @Override
    public Node leaveNE_STRICT(final BinaryNode node) {
        return leaveCmp(node);
    }

    @Override
    public Node leaveLT(final BinaryNode node) {
        return leaveCmp(node);
    }

    @Override
    public Node leaveLE(final BinaryNode node) {
        return leaveCmp(node);
    }

    @Override
    public Node leaveGT(final BinaryNode node) {
        return leaveCmp(node);
    }

    @Override
    public Node leaveGE(final BinaryNode node) {
        return leaveCmp(node);
    }

    @Override
    public Node leaveASSIGN(final BinaryNode node) {
        Range range = node.rhs().getSymbol().getRange();
        if (range.isUnknown()) {
            range = Range.createGenericRange();
        }

        setRange(node.lhs(), range);
        setRange(node, range);

        return node;
    }

    private Node leaveSelfModifyingAssign(final BinaryNode node, final Range range) {
        setRange(node.lhs(), range);
        setRange(node, range);
        return node;
    }

    private Node leaveSelfModifyingAssign(final UnaryNode node, final Range range) {
        setRange(node.rhs(), range);
        setRange(node, range);
        return node;
    }

    @Override
    public Node leaveASSIGN_ADD(final BinaryNode node) {
        return leaveSelfModifyingAssign(node, RANGE.add(node.lhs().getSymbol().getRange(), node.rhs().getSymbol().getRange()));
    }

    @Override
    public Node leaveASSIGN_SUB(final BinaryNode node) {
        return leaveSelfModifyingAssign(node, RANGE.sub(node.lhs().getSymbol().getRange(), node.rhs().getSymbol().getRange()));
    }

    @Override
    public Node leaveASSIGN_MUL(final BinaryNode node) {
        return leaveSelfModifyingAssign(node, RANGE.mul(node.lhs().getSymbol().getRange(), node.rhs().getSymbol().getRange()));
    }

    @Override
    public Node leaveASSIGN_DIV(final BinaryNode node) {
        return leaveSelfModifyingAssign(node, Range.createTypeRange(Type.NUMBER));
    }

    @Override
    public Node leaveASSIGN_MOD(final BinaryNode node) {
        return leaveSelfModifyingAssign(node, Range.createTypeRange(Type.NUMBER));
    }

    @Override
    public Node leaveASSIGN_BIT_AND(final BinaryNode node) {
        return leaveSelfModifyingAssign(node, RANGE.and(node.lhs().getSymbol().getRange(), node.rhs().getSymbol().getRange()));
    }

    @Override
    public Node leaveASSIGN_BIT_OR(final BinaryNode node) {
        return leaveSelfModifyingAssign(node, RANGE.or(node.lhs().getSymbol().getRange(), node.rhs().getSymbol().getRange()));
    }

    @Override
    public Node leaveASSIGN_BIT_XOR(final BinaryNode node) {
        return leaveSelfModifyingAssign(node, RANGE.xor(node.lhs().getSymbol().getRange(), node.rhs().getSymbol().getRange()));
    }

    @Override
    public Node leaveASSIGN_SAR(final BinaryNode node) {
        return leaveSelfModifyingAssign(node, RANGE.sar(node.lhs().getSymbol().getRange(), node.rhs().getSymbol().getRange()));
    }

    @Override
    public Node leaveASSIGN_SHR(final BinaryNode node) {
        return leaveSelfModifyingAssign(node, RANGE.shr(node.lhs().getSymbol().getRange(), node.rhs().getSymbol().getRange()));
    }

    @Override
    public Node leaveASSIGN_SHL(final BinaryNode node) {
        return leaveSelfModifyingAssign(node, RANGE.shl(node.lhs().getSymbol().getRange(), node.rhs().getSymbol().getRange()));
    }

    @Override
    public Node leaveDECINC(final UnaryNode node) {
        switch (node.tokenType()) {
        case DECPREFIX:
        case DECPOSTFIX:
            return leaveSelfModifyingAssign(node, RANGE.sub(node.rhs().getSymbol().getRange(), Range.createRange(1)));
        case INCPREFIX:
        case INCPOSTFIX:
            return leaveSelfModifyingAssign(node, RANGE.add(node.rhs().getSymbol().getRange(), Range.createRange(1)));
        default:
            assert false;
            return node;
        }
    }

    @Override
    public Node leaveADD(final UnaryNode node) {
        Range range = node.rhs().getSymbol().getRange();
        if (!range.getType().isNumeric()) {
           range = Range.createTypeRange(Type.NUMBER);
        }
        setRange(node, range);
        return node;
    }

    @Override
    public Node leaveBIT_NOT(final UnaryNode node) {
        setRange(node, Range.createTypeRange(Type.INT));
        return node;
    }

    @Override
    public Node leaveNOT(final UnaryNode node) {
        setRange(node, Range.createTypeRange(Type.BOOLEAN));
        return node;
    }

    @Override
    public Node leaveSUB(final UnaryNode node) {
        setRange(node, RANGE.neg(node.rhs().getSymbol().getRange()));
        return node;
    }

    @Override
    public Node leaveVarNode(final VarNode node) {
        if (node.isAssignment()) {
            Range range = node.getInit().getSymbol().getRange();
            range = range.isUnknown() ? Range.createGenericRange() : range;

            setRange(node.getName(), range);
        }

        return node;
    }

    @SuppressWarnings("rawtypes")
    @Override
    public boolean enterLiteralNode(final LiteralNode node) {
        // ignore array literals
        return !(node instanceof ArrayLiteralNode);
    }

    @Override
    public Node leaveLiteralNode(@SuppressWarnings("rawtypes") final LiteralNode node) {
        if (node.getType().isInteger()) {
            setRange(node, Range.createRange(node.getInt32()));
        } else if (node.getType().isNumber()) {
            setRange(node, Range.createRange(node.getNumber()));
        } else if (node.getType().isLong()) {
            setRange(node, Range.createRange(node.getLong()));
        } else if (node.getType().isBoolean()) {
            setRange(node, Range.createTypeRange(Type.BOOLEAN));
        } else {
            setRange(node, Range.createGenericRange());
        }
        return node;
    }

    @Override
    public boolean enterRuntimeNode(final RuntimeNode node) {
        // a runtime node that cannot be specialized is no point entering
        return node.getRequest().canSpecialize();
    }

    /**
     * Check whether a symbol is unsafely assigned in a loop - i.e. repeteadly assigned and
     * not being identified as the loop counter. That means we don't really know anything
     * about its range.
     * @param loopNode loop node
     * @param symbol   symbol
     * @return true if assigned in loop
     */
    // TODO - this currently checks for nodes only - needs to be augmented for while nodes
    // assignment analysis is also very conservative
    private static boolean assignedInLoop(final LoopNode loopNode, final Symbol symbol) {
        final HashSet<Node> skip = new HashSet<>();
        final HashSet<Node> assignmentsInLoop = new HashSet<>();

        loopNode.accept(new NodeVisitor<LexicalContext>(new LexicalContext()) {
            private boolean assigns(final Node node, final Symbol s) {
                return node.isAssignment() && ((Assignment<?>)node).getAssignmentDest().getSymbol() == s;
            }

            @Override
            public boolean enterForNode(final ForNode forNode) {
                if (forNode.getInit() != null) {
                    skip.add(forNode.getInit());
                }
                if (forNode.getModify() != null) {
                    skip.add(forNode.getModify());
                }
                return true;
            }

            @Override
            public Node leaveDefault(final Node node) {
                //if this is an assignment to symbol
                if (!skip.contains(node) && assigns(node, symbol)) {
                    assignmentsInLoop.add(node);
                }
                return node;
            }
        });

        return !assignmentsInLoop.isEmpty();
    }

    /**
     * Check for a loop counter. This is currently quite conservative, in that it only handles
     * x <= counter and x < counter.
     *
     * @param node loop node to check
     * @return
     */
    private static Symbol findLoopCounter(final LoopNode node) {
        final Expression test = node.getTest();

        if (test != null && test.isComparison()) {
            final BinaryNode binaryNode = (BinaryNode)test;
            final Expression lhs = binaryNode.lhs();
            final Expression rhs = binaryNode.rhs();

            //detect ident cmp int_literal
            if (lhs instanceof IdentNode && rhs instanceof LiteralNode && ((LiteralNode<?>)rhs).getType().isInteger()) {
                final Symbol    symbol = lhs.getSymbol();
                final int       margin = ((LiteralNode<?>)rhs).getInt32();
                final TokenType op     = test.tokenType();

                switch (op) {
                case LT:
                case LE:
                    symbol.setRange(RANGE.join(symbol.getRange(), Range.createRange(op == TokenType.LT ? margin - 1 : margin)));
                    return symbol;
                case GT:
                case GE:
                    //setRange(lhs, Range.createRange(op == TokenType.GT ? margin + 1 : margin));
                    //return symbol;
                default:
                    break;
                }
            }
        }

        return null;
    }

    private boolean isLoopCounter(final LoopNode loopNode, final Symbol symbol) {
        //this only works if loop nodes aren't replaced by other ones during this transform, but they are not
        return loopCounters.get(loopNode) == symbol;
    }
}