Compute assigned variables and dominance frontiers.

runtime/vm/bit_vector.h

Index: runtime/vm/bit_vector.h
diff --git a/runtime/vm/bit_vector.h b/runtime/vm/bit_vector.h
new file mode 100644
index 0000000000000000000000000000000000000000..d7f7d501e7a3be0c78ed38a16df73fcd703be7ae
--- /dev/null
+++ b/runtime/vm/bit_vector.h
@@ -0,0 +1,162 @@
+// Copyright (c) 2012, the Dart project authors.  Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+#ifndef VM_BIT_VECTOR_H_
+#define VM_BIT_VECTOR_H_
+
+#include "vm/allocation.h"
+#include "vm/zone.h"
+
+namespace dart {
+

[srdjan, 2012/05/12 00:00:55]

This class seems to generic for what you currently need, and we already have
another variation of bitmaps for stackmaps. Maybe we want to merge those two
later, but for now it is OK to add a subset of what is here. All functionality
in BitVector must be tested. Please remove all methods that you do not need, and
add tests to those that survive the pruning. 

[Kevin Millikin (Google), 2012/05/15 11:51:44]

I've added tests.

It's a bit unfortunate to strip out functionality.  (Contains, Remove, Union,
Intersect, Subtract, IsEmpty, Equals, Print, copy constructor, operator=, and
made it DISALLOW_COPY_AND_ASSIGN because it would no longer work correctly).

Most of this will be needed, and now someone who just wants to get work done
will have to stop and reimplement a bunch of BitVector stuff.  (Not to mention
the risk of discarding and reimplementing code that is already well-used in
production.)

[srdjan, 2012/05/15 22:05:32]

Generally we should separate CLs that contribute core libraries to the VM, so
that it can be discussed separately. We should not have dead/unused code in the
VM and its libraries. If you feel confident that you will use it quite soon, I
think it is OK to leave them otherwise they do not belong here (smaller is
better in this case :-).

+// Bit vector implementation.
+class BitVector: public ZoneAllocated {
+ public:
+  // Iterator for the elements of this BitVector.
+  class Iterator : public ValueObject {
+   public:
+    explicit Iterator(BitVector* target)
+        : target_(target),
+          bit_index_(-1),
+          word_index_(0),
+          current_word_(target->data_[0]) {
+      ASSERT(target->data_length_ > 0);
+      Advance();
+    }
+    ~Iterator() { }
+
+    bool Done() const { return word_index_ >= target_->data_length_; }
+    void Advance();
+
+    int Current() const {
+      ASSERT(!Done());
+      return bit_index_;
+    }
+
+   private:
+    BitVector* target_;
+    int bit_index_;
+    int word_index_;
+    uword current_word_;
+
+    friend class BitVector;
+  };
+
+  BitVector(int length, Zone* zone)
+      : length_(length),
+        data_length_(SizeFor(length)),
+        data_(zone->AllocateArray<uword>(data_length_)) {
+    ASSERT(length > 0);
+    Clear();
+  }
+
+  BitVector(const BitVector& other, Zone* zone)
+      : length_(other.length()),
+        data_length_(SizeFor(length_)),
+        data_(zone->AllocateArray<uword>(data_length_)) {

[srdjan, 2012/05/12 00:00:55]

Do not pass in the Zone, instead use
Isolate::Current()->current_zone()->Allocate

[Kevin Millikin (Google), 2012/05/15 11:51:44]

OK, but it seems better without the needing to go to TLS.

[srdjan, 2012/05/15 22:05:32]

The interface is more complex when passing Zone, without clear benefit.
Generally, in the VM and at this stage, we should avoid passing isolates or zone
for performance reasons. This way it looks like we need to allocate BitVector in
varying zones.

+    CopyFrom(other);
+  }
+
+  static int SizeFor(int length) {

[srdjan, 2012/05/12 00:00:55]

intptr_t instead of int (everywhere).

[Kevin Millikin (Google), 2012/05/15 11:51:44]

OK, I've done that here.

This class is currently used with LocalVariable indexes as the elements.  Those
are type int.  When you say "everywhere", do you intend me to change
LocalVariable::index_ to intptr_t and propagate that change to all LocalVariable
clients?  :)

[srdjan, 2012/05/15 22:05:32]

The VM rule is that all memory sizes should be in intptr_t. In case of doubt we
should err toward intptr_t. No need to go fix existing code :-).

+    return 1 + ((length - 1) / sizeof(uword));
+  }
+
+  BitVector& operator=(const BitVector& rhs) {
+    if (this != &rhs) CopyFrom(rhs);
+    return *this;
+  }
+
+  void CopyFrom(const BitVector& other) {
+    ASSERT(other.length() <= length());
+    for (int i = 0; i < other.data_length_; i++) {
+      data_[i] = other.data_[i];
+    }
+    for (int i = other.data_length_; i < data_length_; i++) {
+      data_[i] = 0;
+    }
+  }
+
+  bool Contains(int i) const {
+    ASSERT(i >= 0 && i < length());
+    uword block = data_[i / sizeof(uword)];
+    return (block & (1U << (i % sizeof(uword)))) != 0;
+  }
+
+  void Add(int i) {
+    ASSERT(i >= 0 && i < length());
+    data_[i / sizeof(uword)] |= (1U << (i % sizeof(uword)));
+  }
+
+  void Remove(int i) {
+    ASSERT(i >= 0 && i < length());
+    data_[i / sizeof(uword)] &= ~(1U << (i % sizeof(uword)));
+  }
+
+  void Union(const BitVector& other) {
+    ASSERT(other.length() == length());
+    for (int i = 0; i < data_length_; i++) {
+      data_[i] |= other.data_[i];
+    }
+  }
+
+  bool UnionIsChanged(const BitVector& other) {
+    ASSERT(other.length() == length());
+    bool changed = false;
+    for (int i = 0; i < data_length_; i++) {
+      uword old_data = data_[i];
+      data_[i] |= other.data_[i];
+      if (data_[i] != old_data) changed = true;
+    }
+    return changed;
+  }
+
+  void Intersect(const BitVector& other) {
+    ASSERT(other.length() == length());
+    for (int i = 0; i < data_length_; i++) {
+      data_[i] &= other.data_[i];
+    }
+  }
+
+  void Subtract(const BitVector& other) {
+    ASSERT(other.length() == length());
+    for (int i = 0; i < data_length_; i++) {
+      data_[i] &= ~other.data_[i];
+    }
+  }
+
+  void Clear() {
+    for (int i = 0; i < data_length_; i++) {
+      data_[i] = 0;
+    }
+  }
+
+  bool IsEmpty() const {
+    for (int i = 0; i < data_length_; i++) {
+      if (data_[i] != 0) return false;
+    }
+    return true;
+  }
+
+  bool Equals(const BitVector& other) {
+    for (int i = 0; i < data_length_; i++) {
+      if (data_[i] != other.data_[i]) return false;
+    }
+    return true;
+  }
+
+  int length() const { return length_; }
+
+#ifdef DEBUG
+  void Print();
+#endif
+
+ private:
+  int length_;
+  int data_length_;
+  uword* data_;
+};
+
+}  // namespace dart
+
+#endif  // VM_BIT_VECTOR_H_