CompareNode.java revision 12651:6ef01bd40ce2 
1/*
2 * Copyright (c) 2011, 2016, 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.nodes.calc;
24
25import static org.graalvm.compiler.core.common.GraalOptions.GeneratePIC;
26import static org.graalvm.compiler.nodeinfo.NodeCycles.CYCLES_1;
27
28import org.graalvm.compiler.core.common.calc.Condition;
29import org.graalvm.compiler.core.common.type.AbstractObjectStamp;
30import org.graalvm.compiler.core.common.type.AbstractPointerStamp;
31import org.graalvm.compiler.core.common.type.IntegerStamp;
32import org.graalvm.compiler.debug.GraalError;
33import org.graalvm.compiler.graph.NodeClass;
34import org.graalvm.compiler.graph.spi.Canonicalizable;
35import org.graalvm.compiler.graph.spi.CanonicalizerTool;
36import org.graalvm.compiler.nodeinfo.NodeInfo;
37import org.graalvm.compiler.nodes.BinaryOpLogicNode;
38import org.graalvm.compiler.nodes.ConstantNode;
39import org.graalvm.compiler.nodes.LogicConstantNode;
40import org.graalvm.compiler.nodes.LogicNegationNode;
41import org.graalvm.compiler.nodes.LogicNode;
42import org.graalvm.compiler.nodes.StructuredGraph;
43import org.graalvm.compiler.nodes.ValueNode;
44
45import jdk.vm.ci.meta.Constant;
46import jdk.vm.ci.meta.ConstantReflectionProvider;
47
48/* TODO (thomaswue/gdub) For high-level optimization purpose the compare node should be a boolean *value* (it is currently only a helper node)
49 * But in the back-end the comparison should not always be materialized (for example in x86 the comparison result will not be in a register but in a flag)
50 *
51 * Compare should probably be made a value (so that it can be canonicalized for example) and in later stages some Compare usage should be transformed
52 * into variants that do not materialize the value (CompareIf, CompareGuard...)
53 */
54@NodeInfo(cycles = CYCLES_1)
55public abstract class CompareNode extends BinaryOpLogicNode implements Canonicalizable.Binary<ValueNode> {
56
57    public static final NodeClass<CompareNode> TYPE = NodeClass.create(CompareNode.class);
58    protected final Condition condition;
59    protected final boolean unorderedIsTrue;
60
61    /**
62     * Constructs a new Compare instruction.
63     *
64     * @param x the instruction producing the first input to the instruction
65     * @param y the instruction that produces the second input to this instruction
66     */
67    protected CompareNode(NodeClass<? extends CompareNode> c, Condition condition, boolean unorderedIsTrue, ValueNode x, ValueNode y) {
68        super(c, x, y);
69        this.condition = condition;
70        this.unorderedIsTrue = unorderedIsTrue;
71    }
72
73    /**
74     * Gets the condition (comparison operation) for this instruction.
75     *
76     * @return the condition
77     */
78    public final Condition condition() {
79        return condition;
80    }
81
82    /**
83     * Checks whether unordered inputs mean true or false (only applies to float operations).
84     *
85     * @return {@code true} if unordered inputs produce true
86     */
87    public final boolean unorderedIsTrue() {
88        return this.unorderedIsTrue;
89    }
90
91    private ValueNode optimizeConditional(Constant constant, ConditionalNode conditionalNode, ConstantReflectionProvider constantReflection, Condition cond) {
92        Constant trueConstant = conditionalNode.trueValue().asConstant();
93        Constant falseConstant = conditionalNode.falseValue().asConstant();
94
95        if (falseConstant != null && trueConstant != null && constantReflection != null) {
96            boolean trueResult = cond.foldCondition(trueConstant, constant, constantReflection, unorderedIsTrue());
97            boolean falseResult = cond.foldCondition(falseConstant, constant, constantReflection, unorderedIsTrue());
98
99            if (trueResult == falseResult) {
100                return LogicConstantNode.forBoolean(trueResult);
101            } else {
102                if (trueResult) {
103                    assert falseResult == false;
104                    return conditionalNode.condition();
105                } else {
106                    assert falseResult == true;
107                    return LogicNegationNode.create(conditionalNode.condition());
108
109                }
110            }
111        }
112        return this;
113    }
114
115    protected ValueNode optimizeNormalizeCmp(Constant constant, NormalizeCompareNode normalizeNode, boolean mirrored) {
116        throw new GraalError("NormalizeCompareNode connected to %s (%s %s %s)", this, constant, normalizeNode, mirrored);
117    }
118
119    @Override
120    public ValueNode canonical(CanonicalizerTool tool, ValueNode forX, ValueNode forY) {
121        ConstantReflectionProvider constantReflection = tool.getConstantReflection();
122        LogicNode constantCondition = tryConstantFold(condition(), forX, forY, constantReflection, unorderedIsTrue());
123        if (constantCondition != null) {
124            return constantCondition;
125        }
126        ValueNode result;
127        if (forX.isConstant()) {
128            if ((result = canonicalizeSymmetricConstant(tool, forX.asConstant(), forY, true)) != this) {
129                return result;
130            }
131        } else if (forY.isConstant()) {
132            if ((result = canonicalizeSymmetricConstant(tool, forY.asConstant(), forX, false)) != this) {
133                return result;
134            }
135        } else if (forX instanceof ConvertNode && forY instanceof ConvertNode) {
136            ConvertNode convertX = (ConvertNode) forX;
137            ConvertNode convertY = (ConvertNode) forY;
138            if (convertX.preservesOrder(condition()) && convertY.preservesOrder(condition()) && convertX.getValue().stamp().isCompatible(convertY.getValue().stamp())) {
139                boolean supported = true;
140                if (convertX.getValue().stamp() instanceof IntegerStamp) {
141                    IntegerStamp intStamp = (IntegerStamp) convertX.getValue().stamp();
142                    supported = tool.supportSubwordCompare(intStamp.getBits());
143                }
144
145                if (supported) {
146                    boolean multiUsage = (convertX.asNode().getUsageCount() > 1 || convertY.asNode().getUsageCount() > 1);
147                    if ((forX instanceof ZeroExtendNode || forX instanceof SignExtendNode) && multiUsage) {
148                        // Do not perform for zero or sign extend if there are multiple usages of
149                        // the value.
150                        return this;
151                    }
152                    return duplicateModified(convertX.getValue(), convertY.getValue());
153                }
154            }
155        }
156        return this;
157    }
158
159    public static LogicNode tryConstantFold(Condition condition, ValueNode forX, ValueNode forY, ConstantReflectionProvider constantReflection, boolean unorderedIsTrue) {
160        if (forX.isConstant() && forY.isConstant() && constantReflection != null) {
161            return LogicConstantNode.forBoolean(condition.foldCondition(forX.asConstant(), forY.asConstant(), constantReflection, unorderedIsTrue));
162        }
163        return null;
164    }
165
166    /**
167     * Does this operation represent an identity check such that for x == y, x is exactly the same
168     * thing as y. This is generally true except for some floating point comparisons.
169     *
170     * @return true for identity comparisons
171     */
172    public boolean isIdentityComparison() {
173        return condition == Condition.EQ;
174    }
175
176    protected abstract LogicNode duplicateModified(ValueNode newX, ValueNode newY);
177
178    protected ValueNode canonicalizeSymmetricConstant(CanonicalizerTool tool, Constant constant, ValueNode nonConstant, boolean mirrored) {
179        if (nonConstant instanceof ConditionalNode) {
180            return optimizeConditional(constant, (ConditionalNode) nonConstant, tool.getConstantReflection(), mirrored ? condition().mirror() : condition());
181        } else if (nonConstant instanceof NormalizeCompareNode) {
182            return optimizeNormalizeCmp(constant, (NormalizeCompareNode) nonConstant, mirrored);
183        } else if (nonConstant instanceof ConvertNode) {
184            ConvertNode convert = (ConvertNode) nonConstant;
185            boolean multiUsage = (convert.asNode().getUsageCount() > 1 && convert.getValue().getUsageCount() == 1);
186            if ((convert instanceof ZeroExtendNode || convert instanceof SignExtendNode) && multiUsage) {
187                // Do not perform for zero or sign extend if it could introduce
188                // new live values.
189                return this;
190            }
191
192            boolean supported = true;
193            if (convert.getValue().stamp() instanceof IntegerStamp) {
194                IntegerStamp intStamp = (IntegerStamp) convert.getValue().stamp();
195                supported = tool.supportSubwordCompare(intStamp.getBits());
196            }
197
198            if (supported) {
199                ConstantNode newConstant = canonicalConvertConstant(tool, convert, constant);
200                if (newConstant != null) {
201                    if (mirrored) {
202                        return duplicateModified(newConstant, convert.getValue());
203                    } else {
204                        return duplicateModified(convert.getValue(), newConstant);
205                    }
206                }
207            }
208        }
209        return this;
210    }
211
212    private ConstantNode canonicalConvertConstant(CanonicalizerTool tool, ConvertNode convert, Constant constant) {
213        ConstantReflectionProvider constantReflection = tool.getConstantReflection();
214        if (convert.preservesOrder(condition(), constant, constantReflection)) {
215            Constant reverseConverted = convert.reverse(constant, constantReflection);
216            if (reverseConverted != null && convert.convert(reverseConverted, constantReflection).equals(constant)) {
217                if (GeneratePIC.getValue()) {
218                    // We always want uncompressed constants
219                    return null;
220                }
221                return ConstantNode.forConstant(convert.getValue().stamp(), reverseConverted, tool.getMetaAccess());
222            }
223        }
224        return null;
225    }
226
227    public static LogicNode createCompareNode(StructuredGraph graph, Condition condition, ValueNode x, ValueNode y, ConstantReflectionProvider constantReflection) {
228        LogicNode result = createCompareNode(condition, x, y, constantReflection);
229        return (result.graph() == null ? graph.unique(result) : result);
230    }
231
232    public static LogicNode createCompareNode(Condition condition, ValueNode x, ValueNode y, ConstantReflectionProvider constantReflection) {
233        assert x.getStackKind() == y.getStackKind();
234        assert condition.isCanonical() : "condition is not canonical: " + condition;
235        assert !x.getStackKind().isNumericFloat();
236
237        LogicNode comparison;
238        if (condition == Condition.EQ) {
239            if (x.stamp() instanceof AbstractObjectStamp) {
240                comparison = ObjectEqualsNode.create(x, y, constantReflection);
241            } else if (x.stamp() instanceof AbstractPointerStamp) {
242                comparison = PointerEqualsNode.create(x, y);
243            } else {
244                assert x.getStackKind().isNumericInteger();
245                comparison = IntegerEqualsNode.create(x, y, constantReflection);
246            }
247        } else if (condition == Condition.LT) {
248            assert x.getStackKind().isNumericInteger();
249            comparison = IntegerLessThanNode.create(x, y, constantReflection);
250        } else {
251            assert condition == Condition.BT;
252            assert x.getStackKind().isNumericInteger();
253            comparison = IntegerBelowNode.create(x, y, constantReflection);
254        }
255
256        return comparison;
257    }
258}
259