1/*
2 * Copyright (c) 2013, 2015, 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.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 */
23package org.graalvm.compiler.replacements.nodes.arithmetic;
24
25import static org.graalvm.compiler.core.common.type.IntegerStamp.addOverflowsNegatively;
26import static org.graalvm.compiler.core.common.type.IntegerStamp.addOverflowsPositively;
27import static org.graalvm.compiler.core.common.type.IntegerStamp.carryBits;
28import static org.graalvm.compiler.nodeinfo.NodeCycles.CYCLES_2;
29import static org.graalvm.compiler.nodeinfo.NodeSize.SIZE_2;
30
31import org.graalvm.compiler.core.common.type.IntegerStamp;
32import org.graalvm.compiler.core.common.type.Stamp;
33import org.graalvm.compiler.core.common.type.StampFactory;
34import org.graalvm.compiler.graph.NodeClass;
35import org.graalvm.compiler.graph.spi.CanonicalizerTool;
36import org.graalvm.compiler.nodeinfo.NodeInfo;
37import org.graalvm.compiler.nodes.AbstractBeginNode;
38import org.graalvm.compiler.nodes.ConstantNode;
39import org.graalvm.compiler.nodes.ValueNode;
40import org.graalvm.compiler.nodes.calc.AddNode;
41import org.graalvm.compiler.nodes.spi.LoweringTool;
42
43import jdk.vm.ci.code.CodeUtil;
44import jdk.vm.ci.meta.JavaConstant;
45import jdk.vm.ci.meta.JavaKind;
46
47/**
48 * Node representing an exact integer addition that will throw an {@link ArithmeticException} in
49 * case the addition would overflow the 32 bit range.
50 */
51@NodeInfo(cycles = CYCLES_2, size = SIZE_2)
52public final class IntegerAddExactNode extends AddNode implements IntegerExactArithmeticNode {
53    public static final NodeClass<IntegerAddExactNode> TYPE = NodeClass.create(IntegerAddExactNode.class);
54
55    public IntegerAddExactNode(ValueNode x, ValueNode y) {
56        super(TYPE, x, y);
57        setStamp(x.stamp().unrestricted());
58        assert x.stamp().isCompatible(y.stamp()) && x.stamp() instanceof IntegerStamp;
59    }
60
61    @Override
62    public boolean inferStamp() {
63        /*
64         * Note: it is not allowed to use the foldStamp method of the regular add node as we do not
65         * know the result stamp of this node if we do not know whether we may deopt. If we know we
66         * can never overflow we will replace this node with its non overflow checking counterpart
67         * anyway.
68         */
69        return false;
70    }
71
72    @Override
73    public Stamp foldStamp(Stamp stampX, Stamp stampY) {
74        IntegerStamp a = (IntegerStamp) stampX;
75        IntegerStamp b = (IntegerStamp) stampY;
76
77        int bits = a.getBits();
78        assert bits == b.getBits();
79
80        long defaultMask = CodeUtil.mask(bits);
81        long variableBits = (a.downMask() ^ a.upMask()) | (b.downMask() ^ b.upMask());
82        long variableBitsWithCarry = variableBits | (carryBits(a.downMask(), b.downMask()) ^ carryBits(a.upMask(), b.upMask()));
83        long newDownMask = (a.downMask() + b.downMask()) & ~variableBitsWithCarry;
84        long newUpMask = (a.downMask() + b.downMask()) | variableBitsWithCarry;
85
86        newDownMask &= defaultMask;
87        newUpMask &= defaultMask;
88
89        long newLowerBound;
90        long newUpperBound;
91        boolean lowerOverflowsPositively = addOverflowsPositively(a.lowerBound(), b.lowerBound(), bits);
92        boolean upperOverflowsPositively = addOverflowsPositively(a.upperBound(), b.upperBound(), bits);
93        boolean lowerOverflowsNegatively = addOverflowsNegatively(a.lowerBound(), b.lowerBound(), bits);
94        boolean upperOverflowsNegatively = addOverflowsNegatively(a.upperBound(), b.upperBound(), bits);
95        if (lowerOverflowsPositively) {
96            newLowerBound = CodeUtil.maxValue(bits);
97        } else if (lowerOverflowsNegatively) {
98            newLowerBound = CodeUtil.minValue(bits);
99        } else {
100            newLowerBound = CodeUtil.signExtend((a.lowerBound() + b.lowerBound()) & defaultMask, bits);
101        }
102
103        if (upperOverflowsPositively) {
104            newUpperBound = CodeUtil.maxValue(bits);
105        } else if (upperOverflowsNegatively) {
106            newUpperBound = CodeUtil.minValue(bits);
107        } else {
108            newUpperBound = CodeUtil.signExtend((a.upperBound() + b.upperBound()) & defaultMask, bits);
109        }
110
111        IntegerStamp limit = StampFactory.forInteger(bits, newLowerBound, newUpperBound);
112        newUpMask &= limit.upMask();
113        newUpperBound = CodeUtil.signExtend(newUpperBound & newUpMask, bits);
114        newDownMask |= limit.downMask();
115        newLowerBound |= newDownMask;
116        return IntegerStamp.create(bits, newLowerBound, newUpperBound, newDownMask, newUpMask);
117    }
118
119    @Override
120    public ValueNode canonical(CanonicalizerTool tool, ValueNode forX, ValueNode forY) {
121        if (forX.isConstant() && !forY.isConstant()) {
122            return new IntegerAddExactNode(forY, forX).canonical(tool);
123        }
124        if (forX.isConstant()) {
125            ConstantNode constantNode = canonicalXconstant(forX, forY);
126            if (constantNode != null) {
127                return constantNode;
128            }
129        } else if (forY.isConstant()) {
130            long c = forY.asJavaConstant().asLong();
131            if (c == 0) {
132                return forX;
133            }
134        }
135        if (!IntegerStamp.addCanOverflow((IntegerStamp) forX.stamp(), (IntegerStamp) forY.stamp())) {
136            return new AddNode(forX, forY).canonical(tool);
137        }
138        return this;
139    }
140
141    private static ConstantNode canonicalXconstant(ValueNode forX, ValueNode forY) {
142        JavaConstant xConst = forX.asJavaConstant();
143        JavaConstant yConst = forY.asJavaConstant();
144        if (xConst != null && yConst != null) {
145            assert xConst.getJavaKind() == yConst.getJavaKind();
146            try {
147                if (xConst.getJavaKind() == JavaKind.Int) {
148                    return ConstantNode.forInt(Math.addExact(xConst.asInt(), yConst.asInt()));
149                } else {
150                    assert xConst.getJavaKind() == JavaKind.Long;
151                    return ConstantNode.forLong(Math.addExact(xConst.asLong(), yConst.asLong()));
152                }
153            } catch (ArithmeticException ex) {
154                // The operation will result in an overflow exception, so do not canonicalize.
155            }
156        }
157        return null;
158    }
159
160    @Override
161    public IntegerExactArithmeticSplitNode createSplit(AbstractBeginNode next, AbstractBeginNode deopt) {
162        return graph().add(new IntegerAddExactSplitNode(stamp(), getX(), getY(), next, deopt));
163    }
164
165    @Override
166    public void lower(LoweringTool tool) {
167        IntegerExactArithmeticSplitNode.lower(tool, this);
168    }
169}
170