[TurboFan] Calculate precise ranges for bitwise-or with positive input ranges.

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 882 matching lines @@
 
 Type* Typer::Visitor::JSGreaterThanOrEqualTyper(
     Type* lhs, Type* rhs, Typer* t) {
   return FalsifyUndefined(Invert(JSCompareTyper(lhs, rhs, t), t), t);
 }
 
 
 // JS bitwise operators.
 
 
+// Calculate the result minimum. The algorithm considers one bit at a time, from
+// the most significant to least significant, refining a copy of the input
+// ranges and terminating when the ranges are equal.
+static uint32_t BitwiseOrLow(uint32_t lmin, uint32_t lmax,
+                             uint32_t rmin, uint32_t rmax) {
+  uint32_t bit = 0x80000000, mask = 0x7fffffff;
+
+  // Loop, terminating when the ranges are equal, moving down one bit on each
+  // iteration.
+  for (; lmin != lmax || rmin != rmax; bit >>= 1, mask >>= 1) {
+    // Mask off the current bit from each range limit.
+    uint32_t lminb = lmin & bit;
+    uint32_t lmaxb = lmax & bit;
+    uint32_t rminb = rmin & bit;
+    uint32_t rmaxb = rmax & bit;
+    // At this point the higher bits of each range are equal so comparing the
+    // current bit between the upper and lower limit can determine if the bit
+    // changes over the range. If the two input bits are both static across
+    // their ranges then this bit result is known and is the logical OR of each.
+    if (lminb != lmaxb || rminb != rmaxb) {
+     if (lminb == lmaxb) {
+       // The lhs bit is static over its range. The rhs bit changes across it's
+       // range.
+       if (lminb) {
+         // The lhs bit is one forcing the result bit to be one. The rhs bit is
+         // not significant to this bit in the result due to the OR
+         // operation. The rhs minimum of the remaining bits is zero which
+         // occurs when this current bit ticks over to one - which must be
+         // within range because the bit changes. When the lower rhs bits are
+         // zero they do not affect the lower lhs bits and the result is known.
+         rmin &= ~mask;
+         break;
+       } else {
+         // The lhs bit is zero so the result bit equals the rhs bit. The result
+         // minimum occurs when the bit is zero so the rhs range can be culled
+         // to highest input that does not give a one in this bit position. This
+         // is achieved by clearing the bit and setting all the lower bits.
+         rmax = (rmax & ~bit) | mask;
+       }
+     } else if (rminb == rmaxb) {
+       // The rhs bit is static over its range. The lhs bit changes across it's
+       // range. Cull the lhs range as above.
+       if (rminb) {
+         lmin &= ~mask;
+         break;
+       } else {
+         lmax = (lmax & ~bit) | mask;
+       }
+     } else {
+       // Both input bits change across their ranges. The result minimum will
+       // occur then the result bit is zero which demands that both input ranges
+       // be zero in this bit and they are culled as above.
+       lmax = (lmax & ~bit) | mask;
+       rmax = (rmax & ~bit) | mask;
+     }
+    }
+  }
+  return lmin | rmin;
+}
+
+
+// Calculate the result maximum. The algorithm is parallel to the above, but the
+// logic is somewhat reversed because it is calculating the maximum rather than
+// the minimum, and it is possible to exit early if both input bits change
+// across their range.
+static uint32_t BitwiseOrHigh(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 |= mask;
+          break;
+        } else {
+          rmin = (rmin & ~mask) | bit;
+        }
+      } else if (rminb == rmaxb) {
+        if (rminb) {
+          lmax |= mask;
+          break;
+        } else {
+          lmin = (lmin & ~mask) | bit;
+        }
+      } else {
+        // Both input bits change across their ranges. If this bit changes then
+        // all the lower bits also change across both input ranges, and since
+        // the result is one if either is one then the maximum occurs when all
+        // lower bits are one. The lhsUpperBit is already set at this point, so
+        // this bit does not need setting here too, just the lower bits.
+        lmax |= mask;
+        break;
+      }
+    }
+  }
+  return lmax | rmax;
+}
+
+
+IntType JSBitwiseOrIntType(IntType lhs, IntType rhs) {
+  // Or-ing with 0 is essentially a conversion to int32, and or-ing
+  // with -1 returns -1.
+  if (rhs.min == rhs.max) {
+    if (rhs.min == 0) {
+      return IntType(lhs.min, lhs.max);
+    }
+    if (rhs.min == -1) {
+      return IntType(rhs.min, rhs.max);
+    }
+  }
+  if (lhs.min == lhs.max) {
+    if (lhs.min == 0) {
+      return IntType(rhs.min, rhs.max);
+    }
+    if (lhs.min == -1) {
+      return IntType(lhs.min, lhs.max);
+    }
+  }
+
+  // Divide the calculation into sub-ranges that do not change sign.
+  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(BitwiseOrLow(lminp, lhs.max, rminp, rhs.max)));
+    max = std::max(max, int32_t(BitwiseOrHigh(lminp, lhs.max, rminp, rhs.max)));
+  }
+  if (lhs.max >= 0 && rhs.min < 0) {
+    min = std::min(min, int32_t(BitwiseOrLow(lminp, lhs.max, rhs.min, rmaxn)));
+    max = std::max(max, int32_t(BitwiseOrHigh(lminp, lhs.max, rhs.min, rmaxn)));
+  }
+  if (lhs.min < 0 && rhs.max >= 0) {
+    min = std::min(min, int32_t(BitwiseOrLow(lhs.min, lmaxn, rminp, rhs.max)));
+    max = std::max(max, int32_t(BitwiseOrHigh(lhs.min, lmaxn, rminp, rhs.max)));
+  }
+  if (lhs.min < 0 && rhs.min < 0) {
+    min = std::min(min, int32_t(BitwiseOrLow(lhs.min, lmaxn, rhs.min, rmaxn)));
+    max = std::max(max, int32_t(BitwiseOrHigh(lhs.min, lmaxn, rhs.min, rmaxn)));
+  }
+  DCHECK(max >= min);
+
+  return IntType(min, max);
+}
+
+
 Type* Typer::Visitor::JSBitwiseOrTyper(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();
-  // Or-ing any two values results in a value no smaller than their minimum.
-  // Even no smaller than their maximum if both values are non-negative.
-  double min =
-      lmin >= 0 && rmin >= 0 ? std::max(lmin, rmin) : std::min(lmin, rmin);
-  double max = Type::Signed32()->Max();
-
-  // Or-ing with 0 is essentially a conversion to int32.
-  if (rmin == 0 && rmax == 0) {
-    min = lmin;
-    max = lmax;
-  }
-  if (lmin == 0 && lmax == 0) {
-    min = rmin;
-    max = rmax;
-  }
-
-  if (lmax < 0 || rmax < 0) {
-    // Or-ing two values of which at least one is negative results in a negative
-    // value.
-    max = std::min(max, -1.0);
-  }
-  return Type::Range(min, max, t->zone());
-  // TODO(neis): Be precise for singleton inputs, here and elsewhere.
+  IntType type = JSBitwiseOrIntType(IntType(lhs->Min(), lhs->Max()),
+                                    IntType(rhs->Min(), rhs->Max()));
+  return Type::Range(type.min, type.max, t->zone());
 }
 
 
 Type* Typer::Visitor::JSBitwiseAndTyper(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();
@@ skipping 1423 matching lines @@
       TYPED_ARRAYS(TYPED_ARRAY_CASE)
 #undef TYPED_ARRAY_CASE
     }
   }
   return Type::Constant(value, zone());
 }
 
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8