Simple iterative liveness analysis over SSA.

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
index 6faba2d2486a842586192e50ed35a746a13d6f3d..056223f436f4e0a97e73ec074a9db3e46214c75c 100644
--- a/runtime/vm/bit_vector.h
+++ b/runtime/vm/bit_vector.h
@@ -63,6 +63,31 @@ class BitVector: public ZoneAllocated {
     data_[i / kBitsPerWord] |= (static_cast<uword>(1) << (i % kBitsPerWord));
   }
 
+  bool AddAll(BitVector* from) {

[Florian Schneider, 2012/06/25 14:38:29]

Maybe add a test to bit_vector_test.cc that covers the two new functions.

[Vyacheslav Egorov (Google), 2012/06/25 16:58:26]

Done.

[srdjan, 2012/06/25 17:30:05]

The two methods seem to complex for header file, I would move them to .cc file.

+    ASSERT(data_length_ == from->data_length_);
+    bool changed = false;
+    for (intptr_t i = 0; i < data_length_; i++) {
+      const uword before = data_[i];
+      const uword after = data_[i] | from->data_[i];
+      if (before != after) changed = true;
+      data_[i] = after;
+    }
+    return changed;
+  }
+
+  bool KillAndAdd(BitVector* kill, BitVector* gen) {

[Florian Schneider, 2012/06/25 14:38:29]

Add a comment what this computes: sth like

this += (gen \ kill)

[Vyacheslav Egorov (Google), 2012/06/25 16:58:26]

Done.

+    ASSERT(data_length_ == kill->data_length_);
+    ASSERT(data_length_ == gen->data_length_);

[srdjan, 2012/06/25 17:30:05]

It may be clearer to have Kill without Add, do you expect measurable performance
improvement by merging them?

[Vyacheslav Egorov (Google), 2012/06/25 17:42:23]

It's not easy to have Kill without Add because we pass live_out_ as gen, so we
can't kill "in place".

Yes, for big methods with lots of SSA variables.

But in that case it would also be good to have kill pre-negated.

+    bool changed = false;
+    for (intptr_t i = 0; i < data_length_; i++) {
+      const uword before = data_[i];
+      const uword after = data_[i] | (gen->data_[i] & ~kill->data_[i]);
+      if (before != after) changed = true;
+      data_[i] = after;
+    }
+    return changed;
+  }
+
   bool Contains(int i) const {
     ASSERT(i >= 0 && i < length());
     uword block = data_[i / kBitsPerWord];