Improved range analysis for bitwise operations.

src/hydrogen-instructions.h

 // 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 25 matching lines @@
 #include "small-pointer-list.h"
 #include "string-stream.h"
 #include "v8conversions.h"
 #include "v8utils.h"
 #include "zone.h"
 
 namespace v8 {
 namespace internal {
 
 // Forward declarations.
+class BitRange;
 class HBasicBlock;
 class HEnvironment;
 class HInferRepresentation;
 class HInstruction;
 class HLoopInformation;
 class HValue;
 class LInstruction;
 class LChunkBuilder;
 
 
@@ skipping 196 matching lines @@
     return new(zone) Range(kMinInt, upper_);
   }
   Range* CopyClearUpper(Zone* zone) const {
     return new(zone) Range(lower_, kMaxInt);
   }
   Range* Copy(Zone* zone) const {
     Range* result = new(zone) Range(lower_, upper_);
     result->set_can_be_minus_zero(CanBeMinusZero());
     return result;
   }
-  int32_t Mask() const;
+  void ToBitRange(BitRange* bits) const;
   void set_can_be_minus_zero(bool b) { can_be_minus_zero_ = b; }
   bool CanBeMinusZero() const { return CanBeZero() && can_be_minus_zero_; }
   bool CanBeZero() const { return upper_ >= 0 && lower_ <= 0; }
   bool CanBeNegative() const { return lower_ < 0; }
   bool CanBePositive() const { return upper_ > 0; }
   bool Includes(int value) const { return lower_ <= value && upper_ >= value; }
   bool IsMostGeneric() const {
     return lower_ == kMinInt && upper_ == kMaxInt && CanBeMinusZero();
   }
   bool IsInSmiRange() const {
@@ skipping 26 matching lines @@
   bool MulAndCheckOverflow(Range* other);
 
  private:
   int32_t lower_;
   int32_t upper_;
   Range* next_;
   bool can_be_minus_zero_;
 };
 
 
+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;
+  }
+
+  void ExtendRange(int32_t* lower, int32_t* upper) const {
+    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.
+};
+
+
 class UniqueValueId {
  public:
   UniqueValueId() : raw_address_(NULL) { }
 
   explicit UniqueValueId(Object* object) {
     raw_address_ = reinterpret_cast<Address>(object);
     ASSERT(IsInitialized());
   }
 
   explicit UniqueValueId(Handle<Object> handle) {
@@ skipping 6253 matching lines @@
   virtual bool IsDeletable() const { return true; }
 };
 
 
 #undef DECLARE_INSTRUCTION
 #undef DECLARE_CONCRETE_INSTRUCTION
 
 } }  // namespace v8::internal
 
 #endif  // V8_HYDROGEN_INSTRUCTIONS_H_