[turbofan] compress live_in bitvectors

src/compiler/register-allocator.cc

 // Copyright 2014 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "src/compiler/register-allocator.h"
 
 #include "src/compiler/generic-node-inl.h"
 #include "src/compiler/linkage.h"
 #include "src/hydrogen.h"
 #include "src/string-stream.h"
@@ skipping 482 matching lines @@
       if (a == NULL || a->start().Value() > other->End().Value()) break;
       AdvanceLastProcessedMarker(a, advance_last_processed_up_to);
     } else {
       b = b->next();
     }
   }
   return LifetimePosition::Invalid();
 }
 
 
+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),
       unhandled_live_ranges_(code->VirtualRegisterCount() * 2, zone()),
       active_live_ranges_(8, zone()),
       inactive_live_ranges_(8, zone()),
       reusable_slots_(8, zone()),
       mode_(UNALLOCATED_REGISTERS),
       num_registers_(-1),
       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.
     size_t index = successor->PredecessorIndexOf(block);
     DCHECK(index < successor->PredecessorCount());
     for (BasicBlock::const_iterator j = successor->begin();
          j != successor->end(); ++j) {
       Node* phi = *j;
       if (phi->opcode() != IrOpcode::kPhi) continue;
       Node* input = phi->InputAt(static_cast<int>(index));
       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);
     range->AddUseInterval(start, end, zone());
     iterator.Advance();
   }
 }
 
 
 int RegisterAllocator::FixedDoubleLiveRangeID(int index) {
@@ skipping 351 matching lines @@
 bool RegisterAllocator::IsOutputDoubleRegisterOf(Instruction* instr,
                                                  int index) {
   for (size_t i = 0; i < instr->OutputCount(); i++) {
     InstructionOperand* output = instr->OutputAt(i);
     if (output->IsDoubleRegister() && output->index() == index) return true;
   }
   return false;
 }
 
 
-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 =
       LifetimePosition::FromInstructionIndex(block_start);
 
   for (int index = block->last_instruction_index(); index >= block_start;
        index--) {
     LifetimePosition curr_position =
         LifetimePosition::FromInstructionIndex(index);
 
@@ skipping 301 matching lines @@
   if (block->PredecessorCount() != 1) return false;
   return block->PredecessorAt(0)->rpo_number() == block->rpo_number() - 1;
 }
 
 
 void RegisterAllocator::ResolveControlFlow() {
   RegisterAllocatorPhase phase("L_Resolve control flow", this);
   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();
            i != block->predecessors_end(); ++i) {
         BasicBlock* cur = *i;
         LiveRange* cur_range = LiveRangeFor(operand_index);
         ResolveControlFlow(cur_range, block, cur);
       }
       iterator.Advance();
     }
   }
 }
 
 
 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) {
       Node* phi = *i;
       if (phi->opcode() != IrOpcode::kPhi) continue;
 
       // The live range interval already ends at the first instruction of the
       // block.
       live->Remove(phi->id());
 
@@ skipping 15 matching lines @@
       }
       DCHECK(hint != NULL);
 
       LifetimePosition block_start = LifetimePosition::FromInstructionIndex(
           block->first_instruction_index());
       Define(block_start, phi_operand, hint);
     }
 
     // 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 =
           code()->BlockAt(block->loop_end())->last_instruction_index();
       LifetimePosition end =
           LifetimePosition::FromInstructionIndex(end_index).NextInstruction();
       while (!iterator.Done()) {
         int operand_index = iterator.Current();
         LiveRange* range = LiveRangeFor(operand_index);
         range->EnsureInterval(start, end, zone());
         iterator.Advance();
       }
 
       // 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;
         int operand_index = iterator.Current();
         PrintF("Register allocator error: live v%d reached first block.\n",
                operand_index);
         LiveRange* range = LiveRangeFor(operand_index);
         PrintF("  (first use is at %d)\n", range->first_pos()->pos().Value());
         CompilationInfo* info = code()->linkage()->info();
         if (info->IsStub()) {
@@ skipping 854 matching lines @@
                     allocator_zone_start_allocation_size_;
     isolate()->GetTStatistics()->SaveTiming(name(), base::TimeDelta(), size);
   }
 #ifdef DEBUG
   if (allocator_ != NULL) allocator_->Verify();
 #endif
 }
 }
 }
 }  // namespace v8::internal::compiler