6823354: Add intrinsics for {Integer,Long}.{numberOfLeadingZeros,numberOfTrailingZeros}()

Summary: These methods can be instrinsified by using bit scan, bit test, and population count instructions.
Reviewed-by: kvn, never

5 files changed, 201 insertions, 9 deletions

diff --git a/src/share/vm/opto/classes.hpp b/src/share/vm/opto/classes.hpp
index b854447d7..f2320fc7e 100644
--- a/src/share/vm/opto/classes.hpp
+++ b/src/share/vm/opto/classes.hpp
@@ -104,6 +104,10 @@ macro(ConvL2I)
 macro(CosD)
 macro(CountedLoop)
 macro(CountedLoopEnd)
+macro(CountLeadingZerosI)
+macro(CountLeadingZerosL)
+macro(CountTrailingZerosI)
+macro(CountTrailingZerosL)
 macro(CreateEx)
 macro(DecodeN)
 macro(DivD)
diff --git a/src/share/vm/opto/connode.cpp b/src/share/vm/opto/connode.cpp
index 9e82a8e44..4f7036ca9 100644
--- a/src/share/vm/opto/connode.cpp
+++ b/src/share/vm/opto/connode.cpp
@@ -1255,3 +1255,93 @@ const Type *MoveD2LNode::Value( PhaseTransform *phase ) const {
   v.set_jdouble(td->getd());
   return TypeLong::make( v.get_jlong() );
 }
+
+//------------------------------Value------------------------------------------
+const Type* CountLeadingZerosINode::Value(PhaseTransform* phase) const {
+  const Type* t = phase->type(in(1));
+  if (t == Type::TOP) return Type::TOP;
+  const TypeInt* ti = t->isa_int();
+  if (ti && ti->is_con()) {
+    jint i = ti->get_con();
+    // HD, Figure 5-6
+    if (i == 0)
+      return TypeInt::make(BitsPerInt);
+    int n = 1;
+    unsigned int x = i;
+    if (x >> 16 == 0) { n += 16; x <<= 16; }
+    if (x >> 24 == 0) { n +=  8; x <<=  8; }
+    if (x >> 28 == 0) { n +=  4; x <<=  4; }
+    if (x >> 30 == 0) { n +=  2; x <<=  2; }
+    n -= x >> 31;
+    return TypeInt::make(n);
+  }
+  return TypeInt::INT;
+}
+
+//------------------------------Value------------------------------------------
+const Type* CountLeadingZerosLNode::Value(PhaseTransform* phase) const {
+  const Type* t = phase->type(in(1));
+  if (t == Type::TOP) return Type::TOP;
+  const TypeLong* tl = t->isa_long();
+  if (tl && tl->is_con()) {
+    jlong l = tl->get_con();
+    // HD, Figure 5-6
+    if (l == 0)
+      return TypeInt::make(BitsPerLong);
+    int n = 1;
+    unsigned int x = (((julong) l) >> 32);
+    if (x == 0) { n += 32; x = (int) l; }
+    if (x >> 16 == 0) { n += 16; x <<= 16; }
+    if (x >> 24 == 0) { n +=  8; x <<=  8; }
+    if (x >> 28 == 0) { n +=  4; x <<=  4; }
+    if (x >> 30 == 0) { n +=  2; x <<=  2; }
+    n -= x >> 31;
+    return TypeInt::make(n);
+  }
+  return TypeInt::INT;
+}
+
+//------------------------------Value------------------------------------------
+const Type* CountTrailingZerosINode::Value(PhaseTransform* phase) const {
+  const Type* t = phase->type(in(1));
+  if (t == Type::TOP) return Type::TOP;
+  const TypeInt* ti = t->isa_int();
+  if (ti && ti->is_con()) {
+    jint i = ti->get_con();
+    // HD, Figure 5-14
+    int y;
+    if (i == 0)
+      return TypeInt::make(BitsPerInt);
+    int n = 31;
+    y = i << 16; if (y != 0) { n = n - 16; i = y; }
+    y = i <<  8; if (y != 0) { n = n -  8; i = y; }
+    y = i <<  4; if (y != 0) { n = n -  4; i = y; }
+    y = i <<  2; if (y != 0) { n = n -  2; i = y; }
+    y = i <<  1; if (y != 0) { n = n -  1; }
+    return TypeInt::make(n);
+  }
+  return TypeInt::INT;
+}
+
+//------------------------------Value------------------------------------------
+const Type* CountTrailingZerosLNode::Value(PhaseTransform* phase) const {
+  const Type* t = phase->type(in(1));
+  if (t == Type::TOP) return Type::TOP;
+  const TypeLong* tl = t->isa_long();
+  if (tl && tl->is_con()) {
+    jlong l = tl->get_con();
+    // HD, Figure 5-14
+    int x, y;
+    if (l == 0)
+      return TypeInt::make(BitsPerLong);
+    int n = 63;
+    y = (int) l; if (y != 0) { n = n - 32; x = y; } else x = (((julong) l) >> 32);
+    y = x << 16; if (y != 0) { n = n - 16; x = y; }
+    y = x <<  8; if (y != 0) { n = n -  8; x = y; }
+    y = x <<  4; if (y != 0) { n = n -  4; x = y; }
+    y = x <<  2; if (y != 0) { n = n -  2; x = y; }
+    y = x <<  1; if (y != 0) { n = n -  1; }
+    return TypeInt::make(n);
+  }
+  return TypeInt::INT;
+}
diff --git a/src/share/vm/opto/connode.hpp b/src/share/vm/opto/connode.hpp
index 4c078d1b0..382629f90 100644
--- a/src/share/vm/opto/connode.hpp
+++ b/src/share/vm/opto/connode.hpp
@@ -636,22 +636,62 @@ class MoveD2LNode : public Node {
   virtual const Type* Value( PhaseTransform *phase ) const;
 };
 
+//---------- CountBitsNode -----------------------------------------------------
+class CountBitsNode : public Node {
+public:
+  CountBitsNode(Node* in1) : Node(0, in1) {}
+  const Type* bottom_type() const { return TypeInt::INT; }
+  virtual uint ideal_reg() const { return Op_RegI; }
+};
+
+//---------- CountLeadingZerosINode --------------------------------------------
+// Count leading zeros (0-bit count starting from MSB) of an integer.
+class CountLeadingZerosINode : public CountBitsNode {
+public:
+  CountLeadingZerosINode(Node* in1) : CountBitsNode(in1) {}
+  virtual int Opcode() const;
+  virtual const Type* Value(PhaseTransform* phase) const;
+};
+
+//---------- CountLeadingZerosLNode --------------------------------------------
+// Count leading zeros (0-bit count starting from MSB) of a long.
+class CountLeadingZerosLNode : public CountBitsNode {
+public:
+  CountLeadingZerosLNode(Node* in1) : CountBitsNode(in1) {}
+  virtual int Opcode() const;
+  virtual const Type* Value(PhaseTransform* phase) const;
+};
+
+//---------- CountTrailingZerosINode -------------------------------------------
+// Count trailing zeros (0-bit count starting from LSB) of an integer.
+class CountTrailingZerosINode : public CountBitsNode {
+public:
+  CountTrailingZerosINode(Node* in1) : CountBitsNode(in1) {}
+  virtual int Opcode() const;
+  virtual const Type* Value(PhaseTransform* phase) const;
+};
+
+//---------- CountTrailingZerosLNode -------------------------------------------
+// Count trailing zeros (0-bit count starting from LSB) of a long.
+class CountTrailingZerosLNode : public CountBitsNode {
+public:
+  CountTrailingZerosLNode(Node* in1) : CountBitsNode(in1) {}
+  virtual int Opcode() const;
+  virtual const Type* Value(PhaseTransform* phase) const;
+};
+
 //---------- PopCountINode -----------------------------------------------------
 // Population count (bit count) of an integer.
-class PopCountINode : public Node {
+class PopCountINode : public CountBitsNode {
 public:
-  PopCountINode(Node* in1) : Node(0, in1) {}
+  PopCountINode(Node* in1) : CountBitsNode(in1) {}
   virtual int Opcode() const;
-  const Type* bottom_type() const { return TypeInt::INT; }
-  virtual uint ideal_reg() const { return Op_RegI; }
 };
 
 //---------- PopCountLNode -----------------------------------------------------
 // Population count (bit count) of a long.
-class PopCountLNode : public Node {
+class PopCountLNode : public CountBitsNode {
 public:
-  PopCountLNode(Node* in1) : Node(0, in1) {}
+  PopCountLNode(Node* in1) : CountBitsNode(in1) {}
   virtual int Opcode() const;
-  const Type* bottom_type() const { return TypeInt::INT; }
-  virtual uint ideal_reg() const { return Op_RegI; }
 };
diff --git a/src/share/vm/opto/library_call.cpp b/src/share/vm/opto/library_call.cpp
index c51344d4d..a7a2cde82 100644
--- a/src/share/vm/opto/library_call.cpp
+++ b/src/share/vm/opto/library_call.cpp
@@ -222,6 +222,8 @@ class LibraryCallKit : public GraphKit {
   bool inline_unsafe_CAS(BasicType type);
   bool inline_unsafe_ordered_store(BasicType type);
   bool inline_fp_conversions(vmIntrinsics::ID id);
+  bool inline_numberOfLeadingZeros(vmIntrinsics::ID id);
+  bool inline_numberOfTrailingZeros(vmIntrinsics::ID id);
   bool inline_bitCount(vmIntrinsics::ID id);
   bool inline_reverseBytes(vmIntrinsics::ID id);
 };
@@ -630,6 +632,14 @@ bool LibraryCallKit::try_to_inline() {
   case vmIntrinsics::_longBitsToDouble:
     return inline_fp_conversions(intrinsic_id());
 
+  case vmIntrinsics::_numberOfLeadingZeros_i:
+  case vmIntrinsics::_numberOfLeadingZeros_l:
+    return inline_numberOfLeadingZeros(intrinsic_id());
+
+  case vmIntrinsics::_numberOfTrailingZeros_i:
+  case vmIntrinsics::_numberOfTrailingZeros_l:
+    return inline_numberOfTrailingZeros(intrinsic_id());
+
   case vmIntrinsics::_bitCount_i:
   case vmIntrinsics::_bitCount_l:
     return inline_bitCount(intrinsic_id());
@@ -1844,6 +1854,48 @@ inline Node* LibraryCallKit::make_unsafe_address(Node* base, Node* offset) {
   }
 }
 
+//-------------------inline_numberOfLeadingZeros_int/long-----------------------
+// inline int Integer.numberOfLeadingZeros(int)
+// inline int Long.numberOfLeadingZeros(long)
+bool LibraryCallKit::inline_numberOfLeadingZeros(vmIntrinsics::ID id) {
+  assert(id == vmIntrinsics::_numberOfLeadingZeros_i || id == vmIntrinsics::_numberOfLeadingZeros_l, "not numberOfLeadingZeros");
+  if (id == vmIntrinsics::_numberOfLeadingZeros_i && !Matcher::match_rule_supported(Op_CountLeadingZerosI)) return false;
+  if (id == vmIntrinsics::_numberOfLeadingZeros_l && !Matcher::match_rule_supported(Op_CountLeadingZerosL)) return false;
+  _sp += arg_size();  // restore stack pointer
+  switch (id) {
+  case vmIntrinsics::_numberOfLeadingZeros_i:
+    push(_gvn.transform(new (C, 2) CountLeadingZerosINode(pop())));
+    break;
+  case vmIntrinsics::_numberOfLeadingZeros_l:
+    push(_gvn.transform(new (C, 2) CountLeadingZerosLNode(pop_pair())));
+    break;
+  default:
+    ShouldNotReachHere();
+  }
+  return true;
+}
+
+//-------------------inline_numberOfTrailingZeros_int/long----------------------
+// inline int Integer.numberOfTrailingZeros(int)
+// inline int Long.numberOfTrailingZeros(long)
+bool LibraryCallKit::inline_numberOfTrailingZeros(vmIntrinsics::ID id) {
+  assert(id == vmIntrinsics::_numberOfTrailingZeros_i || id == vmIntrinsics::_numberOfTrailingZeros_l, "not numberOfTrailingZeros");
+  if (id == vmIntrinsics::_numberOfTrailingZeros_i && !Matcher::match_rule_supported(Op_CountTrailingZerosI)) return false;
+  if (id == vmIntrinsics::_numberOfTrailingZeros_l && !Matcher::match_rule_supported(Op_CountTrailingZerosL)) return false;
+  _sp += arg_size();  // restore stack pointer
+  switch (id) {
+  case vmIntrinsics::_numberOfTrailingZeros_i:
+    push(_gvn.transform(new (C, 2) CountTrailingZerosINode(pop())));
+    break;
+  case vmIntrinsics::_numberOfTrailingZeros_l:
+    push(_gvn.transform(new (C, 2) CountTrailingZerosLNode(pop_pair())));
+    break;
+  default:
+    ShouldNotReachHere();
+  }
+  return true;
+}
+
 //----------------------------inline_bitCount_int/long-----------------------
 // inline int Integer.bitCount(int)
 // inline int Long.bitCount(long)
diff --git a/src/share/vm/opto/matcher.hpp b/src/share/vm/opto/matcher.hpp
index 9f79dc372..0067e2163 100644
--- a/src/share/vm/opto/matcher.hpp
+++ b/src/share/vm/opto/matcher.hpp
@@ -225,10 +225,16 @@ public:
   OptoRegPair *_parm_regs;        // Array of machine registers per argument
   RegMask *_calling_convention_mask; // Array of RegMasks per argument
 
-  // Does matcher support this ideal node?
+  // Does matcher have a match rule for this ideal node?
   static const bool has_match_rule(int opcode);
   static const bool _hasMatchRule[_last_opcode];
 
+  // Does matcher have a match rule for this ideal node and is the
+  // predicate (if there is one) true?
+  // NOTE: If this function is used more commonly in the future, ADLC
+  // should generate this one.
+  static const bool match_rule_supported(int opcode);
+
   // Used to determine if we have fast l2f conversion
   // USII has it, USIII doesn't
   static const bool convL2FSupported(void);