Simple iterative liveness analysis over SSA.

runtime/vm/bit_vector.h

 // 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/isolate.h"
 #include "vm/zone.h"
@@ skipping 45 matching lines @@
 
   static intptr_t SizeFor(intptr_t length) {
     return 1 + ((length - 1) / kBitsPerWord);
   }
 
   void Add(intptr_t i) {
     ASSERT(i >= 0 && i < length());
     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];
     return (block & (static_cast<uword>(1) << (i % kBitsPerWord))) != 0;
   }
 
   void Clear() {
     for (intptr_t i = 0; i < data_length_; i++) {
       data_[i] = 0;
     }
   }
 
   intptr_t length() const { return length_; }
 
  private:
   intptr_t length_;
   intptr_t data_length_;
   uword* data_;
 
   DISALLOW_COPY_AND_ASSIGN(BitVector);
 };
 
 }  // namespace dart
 
 #endif  // VM_BIT_VECTOR_H_