1 /*
   2  * Copyright (c) 2012, 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  */
  23 package org.graalvm.compiler.replacements.nodes;
  24 
  25 import static org.graalvm.compiler.nodeinfo.NodeCycles.CYCLES_3;
  26 import static org.graalvm.compiler.nodeinfo.NodeSize.SIZE_1;
  27 
  28 import org.graalvm.compiler.core.common.type.IntegerStamp;
  29 import org.graalvm.compiler.core.common.type.PrimitiveStamp;
  30 import org.graalvm.compiler.core.common.type.Stamp;
  31 import org.graalvm.compiler.core.common.type.StampFactory;
  32 import org.graalvm.compiler.graph.NodeClass;
  33 import org.graalvm.compiler.graph.spi.CanonicalizerTool;
  34 import org.graalvm.compiler.lir.gen.ArithmeticLIRGeneratorTool;
  35 import org.graalvm.compiler.nodeinfo.NodeInfo;
  36 import org.graalvm.compiler.nodes.ConstantNode;
  37 import org.graalvm.compiler.nodes.ValueNode;
  38 import org.graalvm.compiler.nodes.calc.UnaryNode;
  39 import org.graalvm.compiler.nodes.spi.ArithmeticLIRLowerable;
  40 import org.graalvm.compiler.nodes.spi.NodeLIRBuilderTool;
  41 
  42 import jdk.vm.ci.code.CodeUtil;
  43 import jdk.vm.ci.meta.JavaConstant;
  44 import jdk.vm.ci.meta.JavaKind;
  45 
  46 /**
  47  * Determines the index of the least significant "1" bit. Note that the result is undefined if the
  48  * input is zero.
  49  */
  50 @NodeInfo(cycles = CYCLES_3, size = SIZE_1)
  51 public final class BitScanForwardNode extends UnaryNode implements ArithmeticLIRLowerable {
  52 
  53     public static final NodeClass<BitScanForwardNode> TYPE = NodeClass.create(BitScanForwardNode.class);
  54 
  55     public BitScanForwardNode(ValueNode value) {
  56         super(TYPE, StampFactory.forInteger(JavaKind.Int, 0, ((PrimitiveStamp) value.stamp()).getBits()), value);
  57         assert value.getStackKind() == JavaKind.Int || value.getStackKind() == JavaKind.Long;
  58     }
  59 
  60     @Override
  61     public Stamp foldStamp(Stamp newStamp) {
  62         assert newStamp.isCompatible(getValue().stamp());
  63         IntegerStamp valueStamp = (IntegerStamp) newStamp;
  64         int min;
  65         int max;
  66         long mask = CodeUtil.mask(valueStamp.getBits());
  67         int firstAlwaysSetBit = scan(valueStamp.downMask() & mask);
  68         int firstMaybeSetBit = scan(valueStamp.upMask() & mask);
  69         if (firstAlwaysSetBit == -1) {
  70             int lastMaybeSetBit = BitScanReverseNode.scan(valueStamp.upMask() & mask);
  71             min = firstMaybeSetBit;
  72             max = lastMaybeSetBit;
  73         } else {
  74             min = firstMaybeSetBit;
  75             max = firstAlwaysSetBit;
  76         }
  77         return StampFactory.forInteger(JavaKind.Int, min, max);
  78     }
  79 
  80     public static ValueNode tryFold(ValueNode value) {
  81         if (value.isConstant()) {
  82             JavaConstant c = value.asJavaConstant();
  83             if (c.asLong() != 0) {
  84                 return ConstantNode.forInt(value.getStackKind() == JavaKind.Int ? scan(c.asInt()) : scan(c.asLong()));
  85             }
  86         }
  87         return null;
  88     }
  89 
  90     @Override
  91     public ValueNode canonical(CanonicalizerTool tool, ValueNode forValue) {
  92         ValueNode folded = tryFold(forValue);
  93         return folded != null ? folded : this;
  94     }
  95 
  96     /**
  97      * Utility method with defined return value for 0.
  98      *
  99      * @param v
 100      * @return number of trailing zeros or -1 if {@code v} == 0.
 101      */
 102     public static int scan(long v) {
 103         if (v == 0) {
 104             return -1;
 105         }
 106         return Long.numberOfTrailingZeros(v);
 107     }
 108 
 109     /**
 110      * Utility method with defined return value for 0.
 111      *
 112      * @param v
 113      * @return number of trailing zeros or -1 if {@code v} == 0.
 114      */
 115     public static int scan(int v) {
 116         return scan(0xffffffffL & v);
 117     }
 118 
 119     /**
 120      * Raw intrinsic for bsf instruction.
 121      *
 122      * @param v
 123      * @return number of trailing zeros or an undefined value if {@code v} == 0.
 124      */
 125     @NodeIntrinsic
 126     public static native int unsafeScan(long v);
 127 
 128     /**
 129      * Raw intrinsic for bsf instruction.
 130      *
 131      * @param v
 132      * @return number of trailing zeros or an undefined value if {@code v} == 0.
 133      */
 134     @NodeIntrinsic
 135     public static native int unsafeScan(int v);
 136 
 137     @Override
 138     public void generate(NodeLIRBuilderTool builder, ArithmeticLIRGeneratorTool gen) {
 139         builder.setResult(this, gen.emitBitScanForward(builder.operand(getValue())));
 140     }
 141 }