001/*
002 * Copyright (c) 2011, 2014, Oracle and/or its affiliates. All rights reserved.
003 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
004 *
005 * This code is free software; you can redistribute it and/or modify it
006 * under the terms of the GNU General Public License version 2 only, as
007 * published by the Free Software Foundation.
008 *
009 * This code is distributed in the hope that it will be useful, but WITHOUT
010 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
011 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
012 * version 2 for more details (a copy is included in the LICENSE file that
013 * accompanied this code).
014 *
015 * You should have received a copy of the GNU General Public License version
016 * 2 along with this work; if not, write to the Free Software Foundation,
017 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
018 *
019 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
020 * or visit www.oracle.com if you need additional information or have any
021 * questions.
022 */
023package com.oracle.graal.nodes.calc;
024
025import jdk.internal.jvmci.common.*;
026import jdk.internal.jvmci.meta.*;
027
028import com.oracle.graal.compiler.common.calc.*;
029import com.oracle.graal.compiler.common.type.*;
030import com.oracle.graal.graph.*;
031import com.oracle.graal.graph.spi.*;
032import com.oracle.graal.nodeinfo.*;
033import com.oracle.graal.nodes.*;
034
035/* TODO (thomaswue/gdub) For high-level optimization purpose the compare node should be a boolean *value* (it is currently only a helper node)
036 * 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)
037 *
038 * 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
039 * into variants that do not materialize the value (CompareIf, CompareGuard...)
040 */
041@NodeInfo
042public abstract class CompareNode extends BinaryOpLogicNode implements Canonicalizable.Binary<ValueNode> {
043
044    public static final NodeClass<CompareNode> TYPE = NodeClass.create(CompareNode.class);
045    protected final Condition condition;
046    protected final boolean unorderedIsTrue;
047
048    /**
049     * Constructs a new Compare instruction.
050     *
051     * @param x the instruction producing the first input to the instruction
052     * @param y the instruction that produces the second input to this instruction
053     */
054    protected CompareNode(NodeClass<? extends CompareNode> c, Condition condition, boolean unorderedIsTrue, ValueNode x, ValueNode y) {
055        super(c, x, y);
056        this.condition = condition;
057        this.unorderedIsTrue = unorderedIsTrue;
058    }
059
060    /**
061     * Gets the condition (comparison operation) for this instruction.
062     *
063     * @return the condition
064     */
065    public final Condition condition() {
066        return condition;
067    }
068
069    /**
070     * Checks whether unordered inputs mean true or false (only applies to float operations).
071     *
072     * @return {@code true} if unordered inputs produce true
073     */
074    public final boolean unorderedIsTrue() {
075        return this.unorderedIsTrue;
076    }
077
078    private ValueNode optimizeConditional(Constant constant, ConditionalNode conditionalNode, ConstantReflectionProvider constantReflection, Condition cond) {
079        Constant trueConstant = conditionalNode.trueValue().asConstant();
080        Constant falseConstant = conditionalNode.falseValue().asConstant();
081
082        if (falseConstant != null && trueConstant != null && constantReflection != null) {
083            boolean trueResult = cond.foldCondition(trueConstant, constant, constantReflection, unorderedIsTrue());
084            boolean falseResult = cond.foldCondition(falseConstant, constant, constantReflection, unorderedIsTrue());
085
086            if (trueResult == falseResult) {
087                return LogicConstantNode.forBoolean(trueResult);
088            } else {
089                if (trueResult) {
090                    assert falseResult == false;
091                    return conditionalNode.condition();
092                } else {
093                    assert falseResult == true;
094                    return LogicNegationNode.create(conditionalNode.condition());
095
096                }
097            }
098        }
099        return this;
100    }
101
102    protected ValueNode optimizeNormalizeCmp(Constant constant, NormalizeCompareNode normalizeNode, boolean mirrored) {
103        throw new JVMCIError("NormalizeCompareNode connected to %s (%s %s %s)", this, constant, normalizeNode, mirrored);
104    }
105
106    @Override
107    public ValueNode canonical(CanonicalizerTool tool, ValueNode forX, ValueNode forY) {
108        ConstantReflectionProvider constantReflection = tool.getConstantReflection();
109        LogicNode constantCondition = tryConstantFold(condition(), forX, forY, constantReflection, unorderedIsTrue());
110        if (constantCondition != null) {
111            return constantCondition;
112        }
113        ValueNode result;
114        if (forX.isConstant()) {
115            if ((result = canonicalizeSymmetricConstant(tool, forX.asConstant(), forY, true)) != this) {
116                return result;
117            }
118        } else if (forY.isConstant()) {
119            if ((result = canonicalizeSymmetricConstant(tool, forY.asConstant(), forX, false)) != this) {
120                return result;
121            }
122        } else if (forX instanceof ConvertNode && forY instanceof ConvertNode) {
123            ConvertNode convertX = (ConvertNode) forX;
124            ConvertNode convertY = (ConvertNode) forY;
125            if (convertX.preservesOrder(condition()) && convertY.preservesOrder(condition()) && convertX.getValue().stamp().isCompatible(convertY.getValue().stamp())) {
126                return duplicateModified(convertX.getValue(), convertY.getValue());
127            }
128        }
129        return this;
130    }
131
132    public static LogicNode tryConstantFold(Condition condition, ValueNode forX, ValueNode forY, ConstantReflectionProvider constantReflection, boolean unorderedIsTrue) {
133        if (forX.isConstant() && forY.isConstant() && constantReflection != null) {
134            return LogicConstantNode.forBoolean(condition.foldCondition(forX.asConstant(), forY.asConstant(), constantReflection, unorderedIsTrue));
135        }
136        return null;
137    }
138
139    protected abstract LogicNode duplicateModified(ValueNode newX, ValueNode newY);
140
141    protected ValueNode canonicalizeSymmetricConstant(CanonicalizerTool tool, Constant constant, ValueNode nonConstant, boolean mirrored) {
142        if (nonConstant instanceof ConditionalNode) {
143            return optimizeConditional(constant, (ConditionalNode) nonConstant, tool.getConstantReflection(), mirrored ? condition().mirror() : condition());
144        } else if (nonConstant instanceof NormalizeCompareNode) {
145            return optimizeNormalizeCmp(constant, (NormalizeCompareNode) nonConstant, mirrored);
146        } else if (nonConstant instanceof ConvertNode) {
147            ConvertNode convert = (ConvertNode) nonConstant;
148            ConstantNode newConstant = canonicalConvertConstant(tool, convert, constant);
149            if (newConstant != null) {
150                if (mirrored) {
151                    return duplicateModified(newConstant, convert.getValue());
152                } else {
153                    return duplicateModified(convert.getValue(), newConstant);
154                }
155            }
156        }
157        return this;
158    }
159
160    private ConstantNode canonicalConvertConstant(CanonicalizerTool tool, ConvertNode convert, Constant constant) {
161        ConstantReflectionProvider constantReflection = tool.getConstantReflection();
162        if (convert.preservesOrder(condition(), constant, constantReflection)) {
163            Constant reverseConverted = convert.reverse(constant, constantReflection);
164            if (convert.convert(reverseConverted, constantReflection).equals(constant)) {
165                return ConstantNode.forConstant(convert.getValue().stamp(), reverseConverted, tool.getMetaAccess());
166            }
167        }
168        return null;
169    }
170
171    public static LogicNode createCompareNode(StructuredGraph graph, Condition condition, ValueNode x, ValueNode y, ConstantReflectionProvider constantReflection) {
172        LogicNode result = createCompareNode(condition, x, y, constantReflection);
173        return (result.graph() == null ? graph.unique(result) : result);
174    }
175
176    public static LogicNode createCompareNode(Condition condition, ValueNode x, ValueNode y, ConstantReflectionProvider constantReflection) {
177        assert x.getKind() == y.getKind();
178        assert condition.isCanonical() : "condition is not canonical: " + condition;
179        assert !x.getKind().isNumericFloat();
180
181        LogicNode comparison;
182        if (condition == Condition.EQ) {
183            if (x.stamp() instanceof AbstractObjectStamp) {
184                comparison = ObjectEqualsNode.create(x, y, constantReflection);
185            } else if (x.stamp() instanceof AbstractPointerStamp) {
186                comparison = PointerEqualsNode.create(x, y);
187            } else {
188                assert x.getKind().isNumericInteger();
189                comparison = IntegerEqualsNode.create(x, y, constantReflection);
190            }
191        } else if (condition == Condition.LT) {
192            assert x.getKind().isNumericInteger();
193            comparison = IntegerLessThanNode.create(x, y, constantReflection);
194        } else {
195            assert condition == Condition.BT;
196            assert x.getKind().isNumericInteger();
197            comparison = IntegerBelowNode.create(x, y, constantReflection);
198        }
199
200        return comparison;
201    }
202}