[turbofan] compress live_in bitvectors

src/compiler/register-allocator.cc

Index: src/compiler/register-allocator.cc
diff --git a/src/compiler/register-allocator.cc b/src/compiler/register-allocator.cc
index ff196eaa910a1204e83f3f366fdf27543b05498b..188b011c793430f80e49ffc7d94fd75ad5ec7c0d 100644
--- a/src/compiler/register-allocator.cc
+++ b/src/compiler/register-allocator.cc
@@ -500,10 +500,143 @@ LifetimePosition LiveRange::FirstIntersection(LiveRange* other) {
 }
 
 
+namespace {
+
+class VregMapping {
+ public:
+  explicit VregMapping(Zone* zone)
+      : zone_(zone), vregs_(zone), mapping_(zone) {}
+
+  int GetVreg(size_t mapped) {
+    DCHECK_LT(mapped, vregs_.size());
+    return vregs_[mapped];
+  }
+  size_t GetMapping(int vreg) {
+    int mapped = mapping_[vreg];
+    if (mapped != -1) return static_cast<size_t>(mapped);
+    // Insert.
+    size_t new_mapping = vregs_.size();
+    vregs_.push_back(vreg);
+    mapping_[vreg] = static_cast<int>(new_mapping);
+    return new_mapping;
+  }
+  void Initialize(size_t expected_size, size_t max_vregs) {
+    DCHECK(vregs_.empty());
+    DCHECK(mapping_.empty());
+    vregs_.reserve(expected_size);
+    mapping_.insert(mapping_.begin(), max_vregs, -1);
+  }
+
+ private:
+  Zone* zone_;
+  IntVector vregs_;
+  IntVector mapping_;
+  DISALLOW_COPY_AND_ASSIGN(VregMapping);
+};
+
+
+class LiveInSet : public ZoneObject {
+ public:
+  LiveInSet(Zone* zone, VregMapping* mapping, size_t initial_size)
+      : bits_(initial_size, false, zone), mapping_(mapping) {}
+
+  void Add(int vreg) {
+    size_t mapped = mapping_->GetMapping(vreg);
+    if (mapped >= bits_.size()) {
+      // TODO(dcarney): need a better resizing heuristic.
+      size_t new_size = mapped + 10;
+      bits_.resize(new_size, false);
+    }
+    bits_[mapped] = true;
+  }
+
+  void Remove(int vreg) {
+    size_t mapped = mapping_->GetMapping(vreg);
+    if (mapped >= bits_.size()) return;
+    bits_[mapped] = false;
+  }
+
+  bool Contains(int vreg) {
+    size_t mapped = mapping_->GetMapping(vreg);
+    if (mapped >= bits_.size()) return false;
+    return bits_[mapped];
+  }
+
+  void Union(LiveInSet* other) {
+    if (other->bits_.size() > this->bits_.size()) {
+      bits_.resize(other->bits_.size(), false);
+    }
+    BoolVector::iterator j = bits_.begin();
+    for (BoolVector::iterator i = other->bits_.begin(); i != other->bits_.end();
+         ++i, ++j) {
+      if (!*i) continue;
+      *j = true;
+    }
+  }
+
+  class Iterator {
+   public:
+    explicit Iterator(LiveInSet* set) : set_(set), offset_(0) { Advance(); }
+
+    bool Done() { return offset_ > set_->bits_.size(); }
+    void Advance() {
+      for (BoolVector::iterator i = set_->bits_.begin() + offset_;
+           i != set_->bits_.end(); ++i, ++offset_) {
+        if (*i) break;
+      }
+      ++offset_;  // Advance one past match.
+    }
+    int Current() {
+      DCHECK(!Done());
+      return set_->mapping_->GetVreg(offset_ - 1);
+    }
+
+   private:
+    LiveInSet* set_;
+    size_t offset_;
+  };
+
+ private:
+  BoolVector bits_;
+  VregMapping* mapping_;
+};
+
+}  // namespace
+
+
+class RegisterAllocator::LiveInSets : public ZoneObject {
+ public:
+  LiveInSets(size_t basic_block_count, Zone* zone)
+      : zone_(zone),
+        live_ins_(basic_block_count, NULL, LiveIns::allocator_type(zone)),
+        mapping_(zone) {}
+  ~LiveInSets() {}
+
+  LiveInSet* For(BasicBlock* block) { return live_ins_[block->rpo_number()]; }
+  LiveInSet* For(int rpo_number) { return live_ins_[rpo_number]; }
+
+  void Initialize(size_t max_vregs) {
+    // Assume some level of compression.
+    size_t expected_size = std::min(static_cast<size_t>(500), max_vregs);
+    mapping_.Initialize(expected_size, max_vregs);
+    for (LiveIns::iterator i = live_ins_.begin(); i != live_ins_.end(); ++i) {
+      (*i) = new (zone_) LiveInSet(zone_, &mapping_, expected_size);
+    }
+  }
+
+ private:
+  typedef std::vector<LiveInSet*, zone_allocator<LiveInSet*> > LiveIns;
+
+  Zone* zone_;
+  LiveIns live_ins_;
+  VregMapping mapping_;
+};
+
+
 RegisterAllocator::RegisterAllocator(InstructionSequence* code)
     : zone_(code->isolate()),
       code_(code),
-      live_in_sets_(code->BasicBlockCount(), zone()),
+      live_in_sets_(new (zone()) LiveInSets(code->BasicBlockCount(), zone())),
       live_ranges_(code->VirtualRegisterCount() * 2, zone()),
       fixed_live_ranges_(NULL),
       fixed_double_live_ranges_(NULL),
@@ -516,28 +649,18 @@ RegisterAllocator::RegisterAllocator(InstructionSequence* code)
       allocation_ok_(true) {}
 
 
-void RegisterAllocator::InitializeLivenessAnalysis() {
-  // Initialize the live_in sets for each block to NULL.
-  int block_count = code()->BasicBlockCount();
-  live_in_sets_.Initialize(block_count, zone());
-  live_in_sets_.AddBlock(NULL, block_count, zone());
-}
-
-
-BitVector* RegisterAllocator::ComputeLiveOut(BasicBlock* block) {
+void RegisterAllocator::ComputeLiveOut(BasicBlock* block) {
   // Compute live out for the given block, except not including backward
   // successor edges.
-  BitVector* live_out =
-      new (zone()) BitVector(code()->VirtualRegisterCount(), zone());
-
+  LiveInSet* live_out = live_in_sets_->For(block);
   // Process all successor blocks.
   for (BasicBlock::Successors::iterator i = block->successors_begin();
        i != block->successors_end(); ++i) {
     // Add values live on entry to the successor. Note the successor's
     // live_in will not be computed yet for backwards edges.
     BasicBlock* successor = *i;
-    BitVector* live_in = live_in_sets_[successor->rpo_number()];
-    if (live_in != NULL) live_out->Union(*live_in);
+    LiveInSet* live_in = live_in_sets_->For(successor);
+    if (live_in != NULL) live_out->Union(live_in);
 
     // All phi input operands corresponding to this successor edge are live
     // out from this block.
@@ -551,20 +674,17 @@ BitVector* RegisterAllocator::ComputeLiveOut(BasicBlock* block) {
       live_out->Add(input->id());
     }
   }
-
-  return live_out;
 }
 
 
-void RegisterAllocator::AddInitialIntervals(BasicBlock* block,
-                                            BitVector* live_out) {
+void RegisterAllocator::AddInitialIntervals(BasicBlock* block) {
   // Add an interval that includes the entire block to the live range for
   // each live_out value.
   LifetimePosition start =
       LifetimePosition::FromInstructionIndex(block->first_instruction_index());
   LifetimePosition end = LifetimePosition::FromInstructionIndex(
                              block->last_instruction_index()).NextInstruction();
-  BitVector::Iterator iterator(live_out);
+  LiveInSet::Iterator iterator(live_in_sets_->For(block));
   while (!iterator.Done()) {
     int operand_index = iterator.Current();
     LiveRange* range = LiveRangeFor(operand_index);
@@ -936,8 +1056,8 @@ bool RegisterAllocator::IsOutputDoubleRegisterOf(Instruction* instr,
 }
 
 
-void RegisterAllocator::ProcessInstructions(BasicBlock* block,
-                                            BitVector* live) {
+void RegisterAllocator::ProcessInstructions(BasicBlock* block) {
+  LiveInSet* live = live_in_sets_->For(block);
   int block_start = block->first_instruction_index();
 
   LifetimePosition block_start_position =
@@ -1259,8 +1379,8 @@ void RegisterAllocator::ResolveControlFlow() {
   for (int block_id = 1; block_id < code()->BasicBlockCount(); ++block_id) {
     BasicBlock* block = code()->BlockAt(block_id);
     if (CanEagerlyResolveControlFlow(block)) continue;
-    BitVector* live = live_in_sets_[block->rpo_number()];
-    BitVector::Iterator iterator(live);
+    LiveInSet* live = live_in_sets_->For(block);
+    LiveInSet::Iterator iterator(live);
     while (!iterator.Done()) {
       int operand_index = iterator.Current();
       for (BasicBlock::Predecessors::iterator i = block->predecessors_begin();
@@ -1277,19 +1397,23 @@ void RegisterAllocator::ResolveControlFlow() {
 
 void RegisterAllocator::BuildLiveRanges() {
   RegisterAllocatorPhase phase("L_Build live ranges", this);
-  InitializeLivenessAnalysis();
+
+  live_in_sets_->Initialize(code()->VirtualRegisterCount());
+
   // Process the blocks in reverse order.
   for (int block_id = code()->BasicBlockCount() - 1; block_id >= 0;
        --block_id) {
     BasicBlock* block = code()->BlockAt(block_id);
-    BitVector* live = ComputeLiveOut(block);
+    ComputeLiveOut(block);
     // Initially consider all live_out values live for the entire block. We
     // will shorten these intervals if necessary.
-    AddInitialIntervals(block, live);
+    AddInitialIntervals(block);
 
     // Process the instructions in reverse order, generating and killing
     // live values.
-    ProcessInstructions(block, live);
+    ProcessInstructions(block);
+
+    LiveInSet* live = live_in_sets_->For(block);
     // All phi output operands are killed by this block.
     for (BasicBlock::const_iterator i = block->begin(); i != block->end();
          ++i) {
@@ -1325,12 +1449,10 @@ void RegisterAllocator::BuildLiveRanges() {
 
     // Now live is live_in for this block except not including values live
     // out on backward successor edges.
-    live_in_sets_[block_id] = live;
-
     if (block->IsLoopHeader()) {
       // Add a live range stretching from the first loop instruction to the last
       // for each value live on entry to the header.
-      BitVector::Iterator iterator(live);
+      LiveInSet::Iterator iterator(live);
       LifetimePosition start = LifetimePosition::FromInstructionIndex(
           block->first_instruction_index());
       int end_index =
@@ -1346,13 +1468,13 @@ void RegisterAllocator::BuildLiveRanges() {
 
       // Insert all values into the live in sets of all blocks in the loop.
       for (int i = block->rpo_number() + 1; i < block->loop_end(); ++i) {
-        live_in_sets_[i]->Union(*live);
+        live_in_sets_->For(i)->Union(live);
       }
     }
 
 #ifdef DEBUG
     if (block_id == 0) {
-      BitVector::Iterator iterator(live);
+      LiveInSet::Iterator iterator(live);
       bool found = false;
       while (!iterator.Done()) {
         found = true;