Improved range analysis for bitwise operations.

src/hydrogen-instructions.cc

 // Copyright 2011 the V8 project authors. All rights reserved.
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
@@ skipping 90 matching lines @@
   return ConvertAndSetOverflow(result, overflow);
 }
 
 
 static int32_t MulWithoutOverflow(int32_t a, int32_t b, bool* overflow) {
   int64_t result = static_cast<int64_t>(a) * static_cast<int64_t>(b);
   return ConvertAndSetOverflow(result, overflow);
 }
 
 
-int32_t Range::Mask() const {
-  if (lower_ == upper_) return lower_;
-  if (lower_ >= 0) {
-    int32_t res = 1;
-    while (res < upper_) {
-      res = (res << 1) | 1;
-    }
-    return res;
+class BitRange {
+ public:
+  BitRange() : known_(0), bits_(0) { }
+  BitRange(int32_t known, int32_t bits)
+      : known_(known), bits_(bits & known) { }
+
+  static void SetFromRange(BitRange* bits, int32_t lower, int32_t upper) {
+    // Find a mask for the most significant bits that are the same for all
+    // values in the range.
+    int32_t same = ~(lower ^ upper);
+    // Flood zeros to any bits lower than the most significant zero.
+    same &= (same >> 1);
+    same &= (same >> 2);
+    same &= (same >> 4);
+    same &= (same >> 8);
+    same &= (same >> 16);
+
+    bits->known_ = same;
+    bits->bits_ = lower & same;
   }
-  return 0xffffffff;
+
+  void ExtendRange(int32_t* lower, int32_t* upper) {
+    int32_t limit1 = (~known_ & 0x80000000) | bits_;
+    int32_t limit2 = (~known_ & 0x7fffffff) | bits_;
+    *lower = Min(*lower, Min(limit1, limit2));
+    *upper = Max(*upper, Max(limit1, limit2));
+  }
+
+  static BitRange And(BitRange a, BitRange b) {
+    int32_t known = a.known_ & b.known_;
+    // Zeros in either operand become known.
+    known |= (a.known_ & ~a.bits_);
+    known |= (b.known_ & ~b.bits_);
+    return BitRange(known, a.bits_ & b.bits_);
+  }
+
+  static BitRange Or(BitRange a, BitRange b) {
+    int32_t known = a.known_ & b.known_;
+    // Ones in either operand become known.
+    known |= (a.known_ & a.bits_);
+    known |= (b.known_ & b.bits_);
+    return BitRange(known, a.bits_ | b.bits_);
+  }
+
+  static BitRange Xor(BitRange a, BitRange b) {
+    return BitRange(a.known_ & b.known_, a.bits_ ^ b.bits_);
+  }
+
+ private:
+  int32_t known_;  // A mask of known bits.
+  int32_t bits_;   // Values of known bits, zero elsewhere.
+};
+
+
+void Range::ToBitRange(BitRange* bits) const {
+  BitRange::SetFromRange(bits, lower_, upper_);
 }
 
 
 void Range::AddConstant(int32_t value) {
   if (value == 0) return;
   bool may_overflow = false;  // Overflow is ignored here.
   lower_ = AddWithoutOverflow(lower_, value, &may_overflow);
   upper_ = AddWithoutOverflow(upper_, value, &may_overflow);
 #ifdef DEBUG
   Verify();
@@ skipping 1105 matching lines @@
 void HBinaryOperation::PrintDataTo(StringStream* stream) {
   left()->PrintNameTo(stream);
   stream->Add(" ");
   right()->PrintNameTo(stream);
   if (CheckFlag(kCanOverflow)) stream->Add(" !");
   if (CheckFlag(kBailoutOnMinusZero)) stream->Add(" -0?");
 }
 
 
 Range* HBitwise::InferRange() {
-  if (op() == Token::BIT_XOR) return HValue::InferRange();
-  int32_t left_mask = (left()->range() != NULL)
-      ? left()->range()->Mask()
-      : 0xffffffff;
-  int32_t right_mask = (right()->range() != NULL)
-      ? right()->range()->Mask()
-      : 0xffffffff;
-  int32_t result_mask = (op() == Token::BIT_AND)
-      ? left_mask & right_mask
-      : left_mask | right_mask;
-  return (result_mask >= 0)
-      ? new Range(0, result_mask)
-      : HValue::InferRange();
+  if (representation().IsInteger32()) {
+    BitRange left_bits, right_bits;
+
+    if (left()->range() != NULL)
+      left()->range()->ToBitRange(&left_bits);
+
+    if (right()->range() != NULL)
+      right()->range()->ToBitRange(&right_bits);
+
+    BitRange result;
+    switch (op()) {
+      case Token::BIT_AND:
+        result = BitRange::And(left_bits, right_bits);
+        break;
+      case Token::BIT_OR:
+        result = BitRange::Or(left_bits, right_bits);
+        break;
+      case Token::BIT_XOR:
+        result = BitRange::Xor(left_bits, right_bits);
+        break;
+      default:
+        UNREACHABLE();
+    }
+
+    int32_t lower = kMaxInt, upper = kMinInt;  // 'empty' range.
+    result.ExtendRange(&lower, &upper);

[fschneider, 2012/02/28 13:26:52]

I'd simplify this by propagating the inputs kMaxInt and kMinInt into ExtendRange
and change it to return a Range object directy:

return result.ExtendRange();

[sra1, 2013/06/11 05:19:15]

This looks a little strange but let me explain.

The code above is the 1x1 decomposition.
Each input range is 'decomposed' into 1 BitRange.
It is possible to do a more precise decompostion into several BitRanges.
2 BitRanges might be the sweet-spot since it prevents change-of-sign polluting
the result.
E.g.  [-2,3] = {xxxxxxxx} as one BitRange, but is {1111111x, 000000xx} as two.

If you have a 2x2 decomposition, then you have 4 intermediate results.

[-2,3] ^ [-1,5] = {xxxxxxxx} ^ {xxxxxxxx} = xxxxxxxx

but 

[-2,3] ^ [-1,5] = {1111111x, 000000xx} ^ {11111111,00000xxx}
  result11 = 1111111x ^ 11111111 = 0000000x
  result12 = 1111111x ^ 00000xxx = 11111xxx
  result21 = 000000xx ^ 11111111 = 111111xx
  result22 = 000000xx ^ 00000xxx = 00000xxx

These can be accumulated into a range as follows:

  result11.ExtendRange(&lower, &upper);  // 0, 1
  result12.ExtendRange(&lower, &upper);  // -8, 1
  result21.ExtendRange(&lower, &upper);  // -8, 1
  result22.ExtendRange(&lower, &upper);  // -8, 7
= [-8,7]

Do you think I should implement the 2x2 decomposition? It is more complex but
does ensure that small signed integers are known to be smi.

[fschneider, 2013/06/11 10:22:37]

Thanks for the explanation. The code just looked strange to me for the 1x1 case.
It makes sense for the 2x2 case to write it this way.

+    return new Range(lower, upper);
+  } else {
+    return HValue::InferRange();
+  }
 }
 
 
 Range* HSar::InferRange() {
   if (right()->IsConstant()) {
     HConstant* c = HConstant::cast(right());
     if (c->HasInteger32Value()) {
       Range* result = (left()->range() != NULL)
           ? left()->range()->Copy()
           : new Range();
@@ skipping 837 matching lines @@
 
 
 void HCheckPrototypeMaps::Verify() {
   HInstruction::Verify();
   ASSERT(HasNoUses());
 }
 
 #endif
 
 } }  // namespace v8::internal