/*
 * Copyright (c) 2011, 2020, 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.
 *
 * 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 org.graalvm.compiler.nodes.calc;

import static org.graalvm.compiler.core.common.GraalOptions.GeneratePIC;
import static org.graalvm.compiler.nodeinfo.NodeCycles.CYCLES_1;

import org.graalvm.compiler.core.common.PermanentBailoutException;
import org.graalvm.compiler.core.common.calc.CanonicalCondition;
import org.graalvm.compiler.core.common.calc.Condition;
import org.graalvm.compiler.core.common.type.AbstractObjectStamp;
import org.graalvm.compiler.core.common.type.AbstractPointerStamp;
import org.graalvm.compiler.core.common.type.IntegerStamp;
import org.graalvm.compiler.graph.Node;
import org.graalvm.compiler.graph.NodeClass;
import org.graalvm.compiler.graph.Position;
import org.graalvm.compiler.graph.spi.Canonicalizable;
import org.graalvm.compiler.nodeinfo.InputType;
import org.graalvm.compiler.nodeinfo.NodeInfo;
import org.graalvm.compiler.nodes.BinaryOpLogicNode;
import org.graalvm.compiler.nodes.ConstantNode;
import org.graalvm.compiler.nodes.LogicConstantNode;
import org.graalvm.compiler.nodes.LogicNegationNode;
import org.graalvm.compiler.nodes.LogicNode;
import org.graalvm.compiler.nodes.NodeView;
import org.graalvm.compiler.nodes.StructuredGraph;
import org.graalvm.compiler.nodes.ValueNode;
import org.graalvm.compiler.nodes.memory.VolatileReadNode;
import org.graalvm.compiler.options.OptionValues;

import jdk.vm.ci.meta.Constant;
import jdk.vm.ci.meta.ConstantReflectionProvider;
import jdk.vm.ci.meta.MetaAccessProvider;
import jdk.vm.ci.meta.PrimitiveConstant;

@NodeInfo(cycles = CYCLES_1)
public abstract class CompareNode extends BinaryOpLogicNode implements Canonicalizable.Binary<ValueNode> {

    public static final NodeClass<CompareNode> TYPE = NodeClass.create(CompareNode.class);
    protected final CanonicalCondition condition;
    protected final boolean unorderedIsTrue;

    
Constructs a new Compare instruction.
Params:
  • x – the instruction producing the first input to the instruction
  • y – the instruction that produces the second input to this instruction
/** * Constructs a new Compare instruction. * * @param x the instruction producing the first input to the instruction * @param y the instruction that produces the second input to this instruction */
protected CompareNode(NodeClass<? extends CompareNode> c, CanonicalCondition condition, boolean unorderedIsTrue, ValueNode x, ValueNode y) { super(c, x, y); this.condition = condition; this.unorderedIsTrue = unorderedIsTrue; }
Gets the condition (comparison operation) for this instruction.
Returns:the condition
/** * Gets the condition (comparison operation) for this instruction. * * @return the condition */
public final CanonicalCondition condition() { return condition; }
Checks whether unordered inputs mean true or false (only applies to float operations).
Returns:true if unordered inputs produce true
/** * Checks whether unordered inputs mean true or false (only applies to float operations). * * @return {@code true} if unordered inputs produce true */
public final boolean unorderedIsTrue() { return this.unorderedIsTrue; } public static LogicNode tryConstantFold(CanonicalCondition condition, ValueNode forX, ValueNode forY, ConstantReflectionProvider constantReflection, boolean unorderedIsTrue) { if (forX.isConstant() && forY.isConstant() && (constantReflection != null || forX.asConstant() instanceof PrimitiveConstant)) { return LogicConstantNode.forBoolean(condition.foldCondition(forX.asConstant(), forY.asConstant(), constantReflection, unorderedIsTrue)); } return null; } @SuppressWarnings("unused") public static LogicNode tryConstantFoldPrimitive(CanonicalCondition condition, ValueNode forX, ValueNode forY, boolean unorderedIsTrue, NodeView view) { if (forX.asConstant() instanceof PrimitiveConstant && forY.asConstant() instanceof PrimitiveConstant) { return LogicConstantNode.forBoolean(condition.foldCondition((PrimitiveConstant) forX.asConstant(), (PrimitiveConstant) forY.asConstant(), unorderedIsTrue)); } return null; }
Does this operation represent an identity check such that for x == y, x is exactly the same thing as y. This is generally true except for some floating point comparisons.
Returns:true for identity comparisons
/** * Does this operation represent an identity check such that for x == y, x is exactly the same * thing as y. This is generally true except for some floating point comparisons. * * @return true for identity comparisons */
public boolean isIdentityComparison() { return condition == CanonicalCondition.EQ; } public abstract static class CompareOp { public LogicNode canonical(ConstantReflectionProvider constantReflection, MetaAccessProvider metaAccess, OptionValues options, Integer smallestCompareWidth, CanonicalCondition condition, boolean unorderedIsTrue, ValueNode forX, ValueNode forY, NodeView view) { LogicNode constantCondition = tryConstantFold(condition, forX, forY, constantReflection, unorderedIsTrue); if (constantCondition != null) { return constantCondition; } LogicNode result; if (forX.isConstant()) { if ((result = canonicalizeSymmetricConstant(constantReflection, metaAccess, options, smallestCompareWidth, condition, forX.asConstant(), forY, true, unorderedIsTrue, view)) != null) { return result; } } else if (forY.isConstant()) { if ((result = canonicalizeSymmetricConstant(constantReflection, metaAccess, options, smallestCompareWidth, condition, forY.asConstant(), forX, false, unorderedIsTrue, view)) != null) { return result; } } else if (forX instanceof ConvertNode && forY instanceof ConvertNode) { ConvertNode convertX = (ConvertNode) forX; ConvertNode convertY = (ConvertNode) forY; if (convertX.preservesOrder(condition) && convertY.preservesOrder(condition) && convertX.getValue().stamp(view).isCompatible(convertY.getValue().stamp(view))) { boolean supported = true; if (convertX.getValue().stamp(view) instanceof IntegerStamp) { IntegerStamp intStamp = (IntegerStamp) convertX.getValue().stamp(view); boolean isConversionCompatible = convertX.getClass() == convertY.getClass(); supported = smallestCompareWidth != null && intStamp.getBits() >= smallestCompareWidth && isConversionCompatible; } if (supported) { ValueNode xValue = convertX.getValue(); ValueNode yValue = convertY.getValue(); if (forX instanceof ZeroExtendNode || forX instanceof SignExtendNode) { int introducedUsages = 0; int eliminatedNodes = 0; if (convertX.asNode().hasExactlyOneUsage()) { eliminatedNodes++; } else if (xValue.hasExactlyOneUsage()) { introducedUsages++; } if (convertY.asNode().hasExactlyOneUsage()) { eliminatedNodes++; } else if (yValue.hasExactlyOneUsage()) { introducedUsages++; } if (introducedUsages > eliminatedNodes) { // Only perform the optimization if there is // a good trade-off between introduced new usages and // eliminated nodes. return null; } } return duplicateModified(convertX.getValue(), convertY.getValue(), unorderedIsTrue, view); } } } return null; } protected LogicNode canonicalizeSymmetricConstant(ConstantReflectionProvider constantReflection, MetaAccessProvider metaAccess, OptionValues options, Integer smallestCompareWidth, CanonicalCondition condition, Constant constant, ValueNode nonConstant, boolean mirrored, boolean unorderedIsTrue, NodeView view) { if (nonConstant instanceof ConditionalNode) { Condition realCondition = condition.asCondition(); if (mirrored) { realCondition = realCondition.mirror(); } return optimizeConditional(constant, (ConditionalNode) nonConstant, constantReflection, realCondition, unorderedIsTrue); } else if (nonConstant instanceof AbstractNormalizeCompareNode) { return optimizeNormalizeCompare(constantReflection, metaAccess, options, smallestCompareWidth, constant, (AbstractNormalizeCompareNode) nonConstant, mirrored, view); } else if (nonConstant instanceof ConvertNode) { ConvertNode convert = (ConvertNode) nonConstant; boolean multiUsage = (convert.asNode().hasMoreThanOneUsage() && convert.getValue().hasExactlyOneUsage()); if (!multiUsage && convert.asNode().hasMoreThanOneUsage() && convert.getValue() instanceof VolatileReadNode) { // Only account for data usages VolatileReadNode read = (VolatileReadNode) convert.getValue(); int nonMemoryEdges = 0; for (Node u : read.usages()) { for (Position pos : u.inputPositions()) { if (pos.get(u) == read && pos.getInputType() != InputType.Memory) { nonMemoryEdges++; } } } multiUsage = nonMemoryEdges == 1; } if (convert instanceof IntegerConvertNode && multiUsage) { // Do not perform for integer convers if it could introduce // new live values. return null; } if (convert instanceof NarrowNode) { NarrowNode narrowNode = (NarrowNode) convert; if (narrowNode.getInputBits() > 32 && !constant.isDefaultForKind()) { // Avoid large integer constants. return null; } } boolean supported = true; if (convert.getValue().stamp(view) instanceof IntegerStamp) { IntegerStamp intStamp = (IntegerStamp) convert.getValue().stamp(view); supported = smallestCompareWidth != null && intStamp.getBits() >= smallestCompareWidth; } if (supported) { ConstantNode newConstant = canonicalConvertConstant(constantReflection, metaAccess, options, condition, convert, constant, view); if (newConstant != null) { if (mirrored) { return duplicateModified(newConstant, convert.getValue(), unorderedIsTrue, view); } else { return duplicateModified(convert.getValue(), newConstant, unorderedIsTrue, view); } } } } return null; } private static ConstantNode canonicalConvertConstant(ConstantReflectionProvider constantReflection, MetaAccessProvider metaAccess, OptionValues options, CanonicalCondition condition, ConvertNode convert, Constant constant, NodeView view) { if (convert.preservesOrder(condition, constant, constantReflection)) { Constant reverseConverted = convert.reverse(constant, constantReflection); if (reverseConverted != null && convert.convert(reverseConverted, constantReflection).equals(constant)) { if (GeneratePIC.getValue(options)) { // We always want uncompressed constants return null; } return ConstantNode.forConstant(convert.getValue().stamp(view), reverseConverted, metaAccess); } } return null; } @SuppressWarnings("unused") protected LogicNode optimizeNormalizeCompare(ConstantReflectionProvider constantReflection, MetaAccessProvider metaAccess, OptionValues options, Integer smallestCompareWidth, Constant constant, AbstractNormalizeCompareNode normalizeNode, boolean mirrored, NodeView view) { throw new PermanentBailoutException("NormalizeCompareNode connected to %s (%s %s %s)", this, constant, normalizeNode, mirrored); } private static LogicNode optimizeConditional(Constant constant, ConditionalNode conditionalNode, ConstantReflectionProvider constantReflection, Condition cond, boolean unorderedIsTrue) { Constant trueConstant = conditionalNode.trueValue().asConstant(); Constant falseConstant = conditionalNode.falseValue().asConstant(); if (falseConstant != null && trueConstant != null && constantReflection != null) { boolean trueResult = cond.foldCondition(trueConstant, constant, constantReflection, unorderedIsTrue); boolean falseResult = cond.foldCondition(falseConstant, constant, constantReflection, unorderedIsTrue); if (trueResult == falseResult) { return LogicConstantNode.forBoolean(trueResult); } else { if (trueResult) { assert falseResult == false; return conditionalNode.condition(); } else { assert falseResult == true; return LogicNegationNode.create(conditionalNode.condition()); } } } return null; } protected abstract LogicNode duplicateModified(ValueNode newW, ValueNode newY, boolean unorderedIsTrue, NodeView view); } public static LogicNode createCompareNode(StructuredGraph graph, CanonicalCondition condition, ValueNode x, ValueNode y, ConstantReflectionProvider constantReflection, NodeView view) { LogicNode result = createCompareNode(condition, x, y, constantReflection, view); return (result.graph() == null ? graph.addOrUniqueWithInputs(result) : result); } public static LogicNode createCompareNode(CanonicalCondition condition, ValueNode x, ValueNode y, ConstantReflectionProvider constantReflection, NodeView view) { assert x.getStackKind() == y.getStackKind(); assert !x.getStackKind().isNumericFloat(); LogicNode comparison; if (condition == CanonicalCondition.EQ) { if (x.stamp(view) instanceof AbstractObjectStamp) { comparison = ObjectEqualsNode.create(x, y, constantReflection, view); } else if (x.stamp(view) instanceof AbstractPointerStamp) { comparison = PointerEqualsNode.create(x, y, view); } else { assert x.getStackKind().isNumericInteger(); comparison = IntegerEqualsNode.create(x, y, view); } } else if (condition == CanonicalCondition.LT) { assert x.getStackKind().isNumericInteger(); comparison = IntegerLessThanNode.create(x, y, view); } else { assert condition == CanonicalCondition.BT; assert x.getStackKind().isNumericInteger(); comparison = IntegerBelowNode.create(x, y, view); } return comparison; } public static LogicNode createCompareNode(StructuredGraph graph, ConstantReflectionProvider constantReflection, MetaAccessProvider metaAccess, OptionValues options, Integer smallestCompareWidth, CanonicalCondition condition, ValueNode x, ValueNode y, NodeView view) { LogicNode result = createCompareNode(constantReflection, metaAccess, options, smallestCompareWidth, condition, x, y, view); return (result.graph() == null ? graph.addOrUniqueWithInputs(result) : result); } public static LogicNode createCompareNode(ConstantReflectionProvider constantReflection, MetaAccessProvider metaAccess, OptionValues options, Integer smallestCompareWidth, CanonicalCondition condition, ValueNode x, ValueNode y, NodeView view) { assert x.getStackKind() == y.getStackKind(); assert !x.getStackKind().isNumericFloat(); LogicNode comparison; if (condition == CanonicalCondition.EQ) { if (x.stamp(view) instanceof AbstractObjectStamp) { assert smallestCompareWidth == null; comparison = ObjectEqualsNode.create(constantReflection, metaAccess, options, x, y, view); } else if (x.stamp(view) instanceof AbstractPointerStamp) { comparison = PointerEqualsNode.create(x, y, view); } else { assert x.getStackKind().isNumericInteger(); comparison = IntegerEqualsNode.create(constantReflection, metaAccess, options, smallestCompareWidth, x, y, view); } } else if (condition == CanonicalCondition.LT) { assert x.getStackKind().isNumericInteger(); comparison = IntegerLessThanNode.create(constantReflection, metaAccess, options, smallestCompareWidth, x, y, view); } else { assert condition == CanonicalCondition.BT; assert x.getStackKind().isNumericInteger(); comparison = IntegerBelowNode.create(constantReflection, metaAccess, options, smallestCompareWidth, x, y, view); } return comparison; } public static LogicNode createFloatCompareNode(StructuredGraph graph, CanonicalCondition condition, ValueNode x, ValueNode y, boolean unorderedIsTrue, NodeView view) { LogicNode result = createFloatCompareNode(condition, x, y, unorderedIsTrue, view); return (result.graph() == null ? graph.addOrUniqueWithInputs(result) : result); } public static LogicNode createFloatCompareNode(CanonicalCondition condition, ValueNode x, ValueNode y, boolean unorderedIsTrue, NodeView view) { assert x.getStackKind() == y.getStackKind(); assert x.getStackKind().isNumericFloat(); LogicNode comparison; if (condition == CanonicalCondition.EQ) { comparison = FloatEqualsNode.create(x, y, view); } else { assert condition == CanonicalCondition.LT; comparison = FloatLessThanNode.create(x, y, unorderedIsTrue, view); } return comparison; } }