Precise bitwise-xor derived result type for all int32 input types.

src/compiler/typer.cc

 // Copyright 2014 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "src/base/flags.h"
 #include "src/bootstrapper.h"
 #include "src/compiler/graph-reducer.h"
 #include "src/compiler/js-operator.h"
 #include "src/compiler/node.h"
 #include "src/compiler/node-properties.h"
@@ skipping 941 matching lines @@
     max = std::min(max, lmax);
   }
   if (rmin >= 0) {
     min = 0;
     max = std::min(max, rmax);
   }
   return Type::Range(min, max, t->zone());
 }
 
 
+static uint32_t BitwiseXorLow(uint32_t lmin, uint32_t lmax,
+                             uint32_t rmin, uint32_t rmax) {

[titzer, 2015/05/13 14:44:37]

Maybe pull these methods into a separate file with a separate header, such as
src/compiler/int-ranges.h, and you can define a small struct for the upper/lower
ranges.

+  uint32_t bit = 0x80000000, mask = 0x7fffffff;
+
+  for (; lmin != lmax || rmin != rmax; bit >>= 1, mask >>= 1) {
+    uint32_t lminb = lmin & bit;
+    uint32_t lmaxb = lmax & bit;
+    uint32_t rminb = rmin & bit;
+    uint32_t rmaxb = rmax & bit;
+    if (lminb != lmaxb || rminb != rmaxb) {
+     if (lminb == lmaxb) {
+       if (lminb) {
+         rmin = (rmin & ~mask) | bit;
+       } else {
+         rmax = (rmax & ~bit) | mask;
+       }
+     } else if (rminb == rmaxb) {
+       if (rminb) {
+         lmin = (lmin & ~mask) | bit;
+       } else {
+         lmax = (lmax & ~bit) | mask;
+       }
+     } else {
+       lmax = (lmax & ~bit) | mask;
+       rmax = (rmax & ~bit) | mask;
+     }
+    }
+  }
+  return lmin ^ rmin;
+}
+
+
+static uint32_t BitwiseXorHigh(uint32_t lmin, uint32_t lmax,
+                               uint32_t rmin, uint32_t rmax) {
+  uint32_t bit = 0x80000000, mask = 0x7fffffff;
+
+  for (; lmin != lmax || rmin != rmax; bit >>= 1, mask >>= 1) {
+    uint32_t lminb = lmin & bit;
+    uint32_t lmaxb = lmax & bit;
+    uint32_t rminb = rmin & bit;
+    uint32_t rmaxb = rmax & bit;
+    if (lminb != lmaxb || rminb != rmaxb) {
+      if (lminb == lmaxb) {
+        if (lminb) {
+          rmax = (rmax & ~bit) | mask;
+        } else {
+          rmin = (rmin & ~mask) | bit;
+        }
+      } else if (rminb == rmaxb) {
+        if (rminb) {
+          lmax = (lmax & ~bit) | mask;
+        } else {
+          lmin = (lmin & ~mask) | bit;
+        }
+      } else {
+        lmax = (lmax & ~bit) | mask;
+        rmin = (rmin & ~mask) | bit;
+      }
+    }
+  }
+  return lmax ^ rmax;
+}
+
+
+IntType JSBitwiseXorIntType(IntType lhs, IntType rhs) {
+  uint32_t lminp = uint32_t(std::max(lhs.min, 0));
+  uint32_t lmaxn = uint32_t(std::min(lhs.max, -1));
+  uint32_t rminp = uint32_t(std::max(rhs.min, 0));
+  uint32_t rmaxn = uint32_t(std::min(rhs.max, -1));
+  int32_t min = kMaxInt, max = kMinInt;
+
+  if (lhs.max >= 0 && rhs.max >= 0) {
+    min = std::min(min, int32_t(BitwiseXorLow(lminp, lhs.max,
+                                              rminp, rhs.max)));
+    max = std::max(max, int32_t(BitwiseXorHigh(lminp, lhs.max,
+                                               rminp, rhs.max)));
+  }
+  if (lhs.max >= 0 && rhs.min < 0) {
+    min = std::min(min, int32_t(BitwiseXorLow(lminp, lhs.max,
+                                              rhs.min, rmaxn)));
+    max = std::max(max, int32_t(BitwiseXorHigh(lminp, lhs.max,
+                                               rhs.min, rmaxn)));
+  }
+  if (lhs.min < 0 && rhs.max >= 0) {
+    min = std::min(min, int32_t(BitwiseXorLow(lhs.min, lmaxn,
+                                              rminp, rhs.max)));
+    max = std::max(max, int32_t(BitwiseXorHigh(lhs.min, lmaxn,
+                                               rminp, rhs.max)));
+  }
+  if (lhs.min < 0 && rhs.min < 0) {
+    min = std::min(min, int32_t(BitwiseXorLow(lhs.min, lmaxn,
+                                              rhs.min, rmaxn)));
+    max = std::max(max, int32_t(BitwiseXorHigh(lhs.min, lmaxn,
+                                               rhs.min, rmaxn)));
+  }
+  DCHECK(max >= min);
+
+  return IntType(min, max);
+}
+
+
 Type* Typer::Visitor::JSBitwiseXorTyper(Type* lhs, Type* rhs, Typer* t) {
   lhs = NumberToInt32(ToNumber(lhs, t), t);
   rhs = NumberToInt32(ToNumber(rhs, t), t);
-  double lmin = lhs->Min();
-  double rmin = rhs->Min();
-  double lmax = lhs->Max();
-  double rmax = rhs->Max();
-  if ((lmin >= 0 && rmin >= 0) || (lmax < 0 && rmax < 0)) {
-    // Xor-ing negative or non-negative values results in a non-negative value.
-    return Type::Unsigned31();
-  }
-  if ((lmax < 0 && rmin >= 0) || (lmin >= 0 && rmax < 0)) {
-    // Xor-ing a negative and a non-negative value results in a negative value.
-    // TODO(jarin) Use a range here.
-    return Type::Negative32();
-  }
-  return Type::Signed32();
+  IntType type = JSBitwiseXorIntType(IntType(lhs->Min(), lhs->Max()),
+                                     IntType(rhs->Min(), rhs->Max()));
+  return Type::Range(type.min, type.max, t->zone());
 }
 
 
 Type* Typer::Visitor::JSShiftLeftTyper(Type* lhs, Type* rhs, Typer* t) {
   return Type::Signed32();
 }
 
 
 Type* Typer::Visitor::JSShiftRightTyper(Type* lhs, Type* rhs, Typer* t) {
   lhs = NumberToInt32(ToNumber(lhs, t), t);
@@ skipping 1377 matching lines @@
       TYPED_ARRAYS(TYPED_ARRAY_CASE)
 #undef TYPED_ARRAY_CASE
     }
   }
   return Type::Constant(value, zone());
 }
 
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8