FoldConstants.java revision 1076:871cd9451896 
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 java.util.ArrayList;
29import java.util.List;
30import jdk.nashorn.internal.codegen.types.Type;
31import jdk.nashorn.internal.ir.BinaryNode;
32import jdk.nashorn.internal.ir.Block;
33import jdk.nashorn.internal.ir.BlockStatement;
34import jdk.nashorn.internal.ir.EmptyNode;
35import jdk.nashorn.internal.ir.FunctionNode;
36import jdk.nashorn.internal.ir.FunctionNode.CompilationState;
37import jdk.nashorn.internal.ir.IfNode;
38import jdk.nashorn.internal.ir.LexicalContext;
39import jdk.nashorn.internal.ir.LiteralNode;
40import jdk.nashorn.internal.ir.LiteralNode.ArrayLiteralNode;
41import jdk.nashorn.internal.ir.Node;
42import jdk.nashorn.internal.ir.Statement;
43import jdk.nashorn.internal.ir.TernaryNode;
44import jdk.nashorn.internal.ir.UnaryNode;
45import jdk.nashorn.internal.ir.VarNode;
46import jdk.nashorn.internal.ir.visitor.NodeVisitor;
47import jdk.nashorn.internal.runtime.Context;
48import jdk.nashorn.internal.runtime.JSType;
49import jdk.nashorn.internal.runtime.ScriptRuntime;
50import jdk.nashorn.internal.runtime.logging.DebugLogger;
51import jdk.nashorn.internal.runtime.logging.Loggable;
52import jdk.nashorn.internal.runtime.logging.Logger;
53
54/**
55 * Simple constant folding pass, executed before IR is starting to be lowered.
56 */
57@Logger(name="fold")
58final class FoldConstants extends NodeVisitor<LexicalContext> implements Loggable {
59
60    private final DebugLogger log;
61
62    FoldConstants(final Compiler compiler) {
63        super(new LexicalContext());
64        this.log = initLogger(compiler.getContext());
65    }
66
67    @Override
68    public DebugLogger getLogger() {
69        return log;
70    }
71
72    @Override
73    public DebugLogger initLogger(final Context context) {
74        return context.getLogger(this.getClass());
75    }
76
77    @Override
78    public Node leaveUnaryNode(final UnaryNode unaryNode) {
79        final LiteralNode<?> literalNode = new UnaryNodeConstantEvaluator(unaryNode).eval();
80        if (literalNode != null) {
81            log.info("Unary constant folded ", unaryNode, " to ", literalNode);
82            return literalNode;
83        }
84        return unaryNode;
85    }
86
87    @Override
88    public Node leaveBinaryNode(final BinaryNode binaryNode) {
89        final LiteralNode<?> literalNode = new BinaryNodeConstantEvaluator(binaryNode).eval();
90        if (literalNode != null) {
91            log.info("Binary constant folded ", binaryNode, " to ", literalNode);
92            return literalNode;
93        }
94        return binaryNode;
95    }
96
97    @Override
98    public Node leaveFunctionNode(final FunctionNode functionNode) {
99        return functionNode.setState(lc, CompilationState.CONSTANT_FOLDED);
100    }
101
102    @Override
103    public Node leaveIfNode(final IfNode ifNode) {
104        final Node test = ifNode.getTest();
105        if (test instanceof LiteralNode.PrimitiveLiteralNode) {
106            final boolean isTrue = ((LiteralNode.PrimitiveLiteralNode<?>)test).isTrue();
107            final Block executed = isTrue ? ifNode.getPass() : ifNode.getFail();
108            final Block dropped  = isTrue ? ifNode.getFail() : ifNode.getPass();
109            final List<Statement> statements = new ArrayList<>();
110
111            if (executed != null) {
112                statements.addAll(executed.getStatements()); // Get statements form executed branch
113            }
114            if (dropped != null) {
115                extractVarNodes(dropped, statements); // Get var-nodes from non-executed branch
116            }
117            if (statements.isEmpty()) {
118                return new EmptyNode(ifNode);
119            }
120            return BlockStatement.createReplacement(ifNode, ifNode.getFinish(), statements);
121        }
122        return ifNode;
123    }
124
125    @Override
126    public Node leaveTernaryNode(final TernaryNode ternaryNode) {
127        final Node test = ternaryNode.getTest();
128        if (test instanceof LiteralNode.PrimitiveLiteralNode) {
129            return ((LiteralNode.PrimitiveLiteralNode<?>)test).isTrue() ? ternaryNode.getTrueExpression() : ternaryNode.getFalseExpression();
130        }
131        return ternaryNode;
132    }
133
134    /**
135     * Helper class to evaluate constant expressions at compile time This is
136     * also a simplifier used by BinaryNode visits, UnaryNode visits and
137     * conversions.
138     */
139    abstract static class ConstantEvaluator<T extends Node> {
140        protected T            parent;
141        protected final long   token;
142        protected final int    finish;
143
144        protected ConstantEvaluator(final T parent) {
145            this.parent = parent;
146            this.token  = parent.getToken();
147            this.finish = parent.getFinish();
148        }
149
150        /**
151         * Returns a literal node that replaces the given parent node, or null if replacement
152         * is impossible
153         * @return the literal node
154         */
155        protected abstract LiteralNode<?> eval();
156    }
157
158    private static void extractVarNodes(final Block block, final List<Statement> statements) {
159        final LexicalContext lc = new LexicalContext();
160        block.accept(lc, new NodeVisitor<LexicalContext>(lc) {
161            @Override
162            public boolean enterVarNode(final VarNode varNode) {
163                statements.add(varNode.setInit(null));
164                return false;
165            }
166        });
167    }
168
169    private static class UnaryNodeConstantEvaluator extends ConstantEvaluator<UnaryNode> {
170        UnaryNodeConstantEvaluator(final UnaryNode parent) {
171            super(parent);
172        }
173
174        @Override
175        protected LiteralNode<?> eval() {
176            final Node rhsNode = parent.getExpression();
177
178            if (!(rhsNode instanceof LiteralNode)) {
179                return null;
180            }
181
182            if (rhsNode instanceof ArrayLiteralNode) {
183                return null;
184            }
185
186            final LiteralNode<?> rhs = (LiteralNode<?>)rhsNode;
187            final Type rhsType = rhs.getType();
188            final boolean rhsInteger = rhsType.isInteger() || rhsType.isBoolean();
189
190            LiteralNode<?> literalNode;
191
192            switch (parent.tokenType()) {
193            case ADD:
194                if (rhsInteger) {
195                    literalNode = LiteralNode.newInstance(token, finish, rhs.getInt32());
196                } else {
197                    literalNode = LiteralNode.newInstance(token, finish, rhs.getNumber());
198                }
199                break;
200            case SUB:
201                if (rhsInteger && rhs.getInt32() != 0) { // @see test/script/basic/minuszero.js
202                    literalNode = LiteralNode.newInstance(token, finish, -rhs.getInt32());
203                } else {
204                    literalNode = LiteralNode.newInstance(token, finish, -rhs.getNumber());
205                }
206                break;
207            case NOT:
208                literalNode = LiteralNode.newInstance(token, finish, !rhs.getBoolean());
209                break;
210            case BIT_NOT:
211                literalNode = LiteralNode.newInstance(token, finish, ~rhs.getInt32());
212                break;
213            default:
214                return null;
215            }
216
217            return literalNode;
218        }
219    }
220
221    //TODO add AND and OR with one constant parameter (bitwise)
222    private static class BinaryNodeConstantEvaluator extends ConstantEvaluator<BinaryNode> {
223        BinaryNodeConstantEvaluator(final BinaryNode parent) {
224            super(parent);
225        }
226
227        @Override
228        protected LiteralNode<?> eval() {
229            LiteralNode<?> result;
230
231            result = reduceTwoLiterals();
232            if (result != null) {
233                return result;
234            }
235
236            result = reduceOneLiteral();
237            if (result != null) {
238                return result;
239            }
240
241            return null;
242        }
243
244        @SuppressWarnings("static-method")
245        private LiteralNode<?> reduceOneLiteral() {
246            //TODO handle patterns like AND, OR, numeric ops that can be strength reduced but not replaced by a single literal node etc
247            return null;
248        }
249
250        private LiteralNode<?> reduceTwoLiterals() {
251            if (!(parent.lhs() instanceof LiteralNode && parent.rhs() instanceof LiteralNode)) {
252                return null;
253            }
254
255            final LiteralNode<?> lhs = (LiteralNode<?>)parent.lhs();
256            final LiteralNode<?> rhs = (LiteralNode<?>)parent.rhs();
257
258            if (lhs instanceof ArrayLiteralNode || rhs instanceof ArrayLiteralNode) {
259                return null;
260            }
261
262            final Type widest = Type.widest(lhs.getType(), rhs.getType());
263
264            boolean isInteger = widest.isInteger();
265            boolean isLong    = widest.isLong();
266
267            double value;
268
269            switch (parent.tokenType()) {
270            case DIV:
271                value = lhs.getNumber() / rhs.getNumber();
272                break;
273            case ADD:
274                if ((lhs.isString() || rhs.isNumeric()) && (rhs.isString() || rhs.isNumeric())) {
275                    final Object res = ScriptRuntime.ADD(lhs.getObject(), rhs.getObject());
276                    if (res instanceof Number) {
277                        value = ((Number)res).doubleValue();
278                        break;
279                    }
280                    assert res instanceof CharSequence : res + " was not a CharSequence, it was a " + res.getClass();
281                    return LiteralNode.newInstance(token, finish, res.toString());
282                }
283                return null;
284            case MUL:
285                value = lhs.getNumber() * rhs.getNumber();
286                break;
287            case MOD:
288                value = lhs.getNumber() % rhs.getNumber();
289                break;
290            case SUB:
291                value = lhs.getNumber() - rhs.getNumber();
292                break;
293            case SHR:
294                return LiteralNode.newInstance(token, finish, JSType.toUint32(lhs.getInt32() >>> rhs.getInt32()));
295            case SAR:
296                return LiteralNode.newInstance(token, finish, lhs.getInt32() >> rhs.getInt32());
297            case SHL:
298                return LiteralNode.newInstance(token, finish, lhs.getInt32() << rhs.getInt32());
299            case BIT_XOR:
300                return LiteralNode.newInstance(token, finish, lhs.getInt32() ^ rhs.getInt32());
301            case BIT_AND:
302                return LiteralNode.newInstance(token, finish, lhs.getInt32() & rhs.getInt32());
303            case BIT_OR:
304                return LiteralNode.newInstance(token, finish, lhs.getInt32() | rhs.getInt32());
305            case GE:
306                return LiteralNode.newInstance(token, finish, ScriptRuntime.GE(lhs.getObject(), rhs.getObject()));
307            case LE:
308                return LiteralNode.newInstance(token, finish, ScriptRuntime.LE(lhs.getObject(), rhs.getObject()));
309            case GT:
310                return LiteralNode.newInstance(token, finish, ScriptRuntime.GT(lhs.getObject(), rhs.getObject()));
311            case LT:
312                return LiteralNode.newInstance(token, finish, ScriptRuntime.LT(lhs.getObject(), rhs.getObject()));
313            case NE:
314                return LiteralNode.newInstance(token, finish, ScriptRuntime.NE(lhs.getObject(), rhs.getObject()));
315            case NE_STRICT:
316                return LiteralNode.newInstance(token, finish, ScriptRuntime.NE_STRICT(lhs.getObject(), rhs.getObject()));
317            case EQ:
318                return LiteralNode.newInstance(token, finish, ScriptRuntime.EQ(lhs.getObject(), rhs.getObject()));
319            case EQ_STRICT:
320                return LiteralNode.newInstance(token, finish, ScriptRuntime.EQ_STRICT(lhs.getObject(), rhs.getObject()));
321            default:
322                return null;
323            }
324
325            isInteger &= JSType.isRepresentableAsInt(value) && !JSType.isNegativeZero(value);
326            isLong    &= JSType.isRepresentableAsLong(value) && !JSType.isNegativeZero(value);
327
328            if (isInteger) {
329                return LiteralNode.newInstance(token, finish, (int)value);
330            } else if (isLong) {
331                return LiteralNode.newInstance(token, finish, (long)value);
332            }
333
334            return LiteralNode.newInstance(token, finish, value);
335        }
336    }
337}
338