Improved range analysis for bitwise operations.

src/hydrogen-instructions.cc

 // Copyright 2012 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 267 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;
-  }
-  return 0xffffffff;
+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 2032 matching lines @@
 
 void HMathMinMax::InferRepresentation(HInferRepresentation* h_infer) {
   ASSERT(CheckFlag(kFlexibleRepresentation));
   Representation new_rep = RepresentationFromInputs();
   UpdateRepresentation(new_rep, h_infer, "inputs");
   // Do not care about uses.
 }
 
 
 Range* HBitwise::InferRange(Zone* zone) {
+  /*
   if (op() == Token::BIT_XOR) {
     if (left()->HasRange() && right()->HasRange()) {
       // The maximum value has the high bit, and all bits below, set:
       // (1 << high) - 1.
       // If the range can be negative, the minimum int is a negative number with
       // the high bit, and all bits below, unset:
       // -(1 << high).
       // If it cannot be negative, conservatively choose 0 as minimum int.
       int64_t left_upper = left()->range()->upper();
       int64_t left_lower = left()->range()->lower();
@@ skipping 24 matching lines @@
       : kDefaultMask;
   int32_t right_mask = (right()->range() != NULL)
       ? right()->range()->Mask()
       : kDefaultMask;
   int32_t result_mask = (op() == Token::BIT_AND)
       ? left_mask & right_mask
       : left_mask | right_mask;
   return (result_mask >= 0)
       ? new(zone) Range(0, result_mask)
       : HValue::InferRange(zone);
+  */

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

Remove commented code.

[sra1, 2013/06/12 00:12:24]

Done.

+  if (representation().IsInteger32()) {
+    BitRange left_bits, right_bits;
+
+    if (left()->range() != NULL)

[Toon Verwaest, 2013/06/11 12:47:46]

if (left()->HasRange()) {
...
}

[sra1, 2013/06/12 00:12:24]

Done.

+      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);
+    return new(zone) Range(lower, upper);
+  } else {
+    return HValue::InferRange(zone);
+  }
 }
 
 
 Range* HSar::InferRange(Zone* zone) {
   if (right()->IsConstant()) {
     HConstant* c = HConstant::cast(right());
     if (c->HasInteger32Value()) {
       Range* result = (left()->range() != NULL)
           ? left()->range()->Copy(zone)
           : new(zone) Range();
@@ skipping 1435 matching lines @@
     case kBackingStore:
       if (!name_.is_null()) stream->Add(*String::cast(*name_)->ToCString());
       stream->Add("[backing-store]");
       break;
   }
 
   stream->Add("@%d", offset());
 }
 
 } }  // namespace v8::internal