[turbofan] optimize hot loop in ResolveControlFlow

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 ced88a83d8fb41091bb750e7d2e2b40679b2b5bf..1f2ea4edc4940bf263e554bf79cde721408a33d6 100644
--- a/src/compiler/register-allocator.cc
+++ b/src/compiler/register-allocator.cc
@@ -200,7 +200,7 @@ bool LiveRange::CanBeSpilled(LifetimePosition pos) {
 }
 
 
-InstructionOperand* LiveRange::CreateAssignedOperand(Zone* zone) {
+InstructionOperand* LiveRange::CreateAssignedOperand(Zone* zone) const {
   InstructionOperand* op = NULL;
   if (HasRegisterAssigned()) {
     DCHECK(!IsSpilled());
@@ -1172,9 +1172,8 @@ bool RegisterAllocator::Allocate(PipelineStatistics* stats) {
 
 
 void RegisterAllocator::MeetRegisterConstraints() {
-  for (int i = 0; i < code()->InstructionBlockCount(); ++i) {
-    MeetRegisterConstraints(
-        code()->InstructionBlockAt(BasicBlock::RpoNumber::FromInt(i)));
+  for (auto block : code()->instruction_blocks()) {
+    MeetRegisterConstraints(block);
     if (!AllocationOk()) return;
   }
 }
@@ -1182,55 +1181,9 @@ void RegisterAllocator::MeetRegisterConstraints() {
 
 void RegisterAllocator::ResolvePhis() {
   // Process the blocks in reverse order.
-  for (int i = code()->InstructionBlockCount() - 1; i >= 0; --i) {
-    ResolvePhis(code()->InstructionBlockAt(BasicBlock::RpoNumber::FromInt(i)));
-  }
-}
-
-
-void RegisterAllocator::ResolveControlFlow(LiveRange* range,
-                                           const InstructionBlock* block,
-                                           const InstructionBlock* pred) {
-  LifetimePosition pred_end =
-      LifetimePosition::FromInstructionIndex(pred->last_instruction_index());
-  LifetimePosition cur_start =
-      LifetimePosition::FromInstructionIndex(block->first_instruction_index());
-  LiveRange* pred_cover = NULL;
-  LiveRange* cur_cover = NULL;
-  LiveRange* cur_range = range;
-  while (cur_range != NULL && (cur_cover == NULL || pred_cover == NULL)) {
-    if (cur_range->CanCover(cur_start)) {
-      DCHECK(cur_cover == NULL);
-      cur_cover = cur_range;
-    }
-    if (cur_range->CanCover(pred_end)) {
-      DCHECK(pred_cover == NULL);
-      pred_cover = cur_range;
-    }
-    cur_range = cur_range->next();
-  }
-
-  if (cur_cover->IsSpilled()) return;
-  DCHECK(pred_cover != NULL && cur_cover != NULL);
-  if (pred_cover != cur_cover) {
-    InstructionOperand* pred_op =
-        pred_cover->CreateAssignedOperand(code_zone());
-    InstructionOperand* cur_op = cur_cover->CreateAssignedOperand(code_zone());
-    if (!pred_op->Equals(cur_op)) {
-      GapInstruction* gap = NULL;
-      if (block->PredecessorCount() == 1) {
-        gap = code()->GapAt(block->first_instruction_index());
-      } else {
-        DCHECK(pred->SuccessorCount() == 1);
-        gap = GetLastGap(pred);
-
-        Instruction* branch = InstructionAt(pred->last_instruction_index());
-        DCHECK(!branch->HasPointerMap());
-        USE(branch);
-      }
-      gap->GetOrCreateParallelMove(GapInstruction::START, code_zone())
-          ->AddMove(pred_op, cur_op, code_zone());
-    }
+  for (auto i = code()->instruction_blocks().rbegin();
+       i != code()->instruction_blocks().rend(); ++i) {
+    ResolvePhis(*i);
   }
 }
 
@@ -1300,20 +1253,161 @@ bool RegisterAllocator::CanEagerlyResolveControlFlow(
 }
 
 
+namespace {
+
+class LiveRangeBound {
+ public:
+  explicit LiveRangeBound(const LiveRange* range)
+      : range_(range), start_(range->Start()), end_(range->End()) {
+    DCHECK(!range->IsEmpty());
+  }
+
+  bool CanCover(LifetimePosition position) {
+    return start_.Value() <= position.Value() &&
+           position.Value() < end_.Value();
+  }
+
+  const LiveRange* const range_;
+  const LifetimePosition start_;
+  const LifetimePosition end_;
+
+ private:
+  DISALLOW_COPY_AND_ASSIGN(LiveRangeBound);
+};
+
+
+struct FindResult {
+  const LiveRange* cur_cover_;
+  const LiveRange* pred_cover_;
+};
+
+
+class LiveRangeBoundArray {
+ public:
+  LiveRangeBoundArray() : length_(0), start_(nullptr) {}
+
+  bool ShouldInitialize() { return start_ == NULL; }
+
+  void Initialize(Zone* zone, const LiveRange* const range) {
+    size_t length = 0;
+    for (const LiveRange* i = range; i != NULL; i = i->next()) length++;
+    start_ = zone->NewArray<LiveRangeBound>(static_cast<int>(length));
+    length_ = length;
+    LiveRangeBound* curr = start_;
+    for (const LiveRange* i = range; i != NULL; i = i->next(), ++curr) {
+      new (curr) LiveRangeBound(i);
+    }
+  }
+
+  LiveRangeBound* Find(const LifetimePosition position) {

[Jarin, 2014/11/04 10:42:08]

Could not we use std::lower_bound for this?

[dcarney, 2014/11/05 09:02:02]

benchmarking says no
i refactored the current code and it drops from 3.5% of the compilation time of
zlib to 3
with lower_bound it's around 4

+    size_t left_index = 0;
+    size_t right_index = length_ - 1;
+    while (true) {
+      size_t current_index = left_index + (right_index - left_index) / 2;
+      LiveRangeBound* bound = &start_[current_index];
+      if (bound->CanCover(position)) return bound;
+      if (position.Value() < bound->start_.Value()) {
+        DCHECK(right_index != current_index);

[Jarin, 2014/11/04 10:42:08]

How about DCHECK(right_index > current_index)?

[dcarney, 2014/11/05 09:02:02]

Done.

+        right_index = current_index;
+      } else {
+        DCHECK(position.Value() >= bound->end_.Value());
+        if (left_index == current_index) {
+          DCHECK(right_index == left_index + 1);
+          left_index = right_index;

[Jarin, 2014/11/04 10:42:09]

I think this degenerate case would not appear if you calculated
current_index = left_index + (right_index + 1 - left_index) / 2;
(or if your right_index was exclusive).

[dcarney, 2014/11/05 09:02:02]

Done.

+        } else {
+          left_index = current_index;
+        }
+      }
+    }
+  }
+
+  void Find(const InstructionBlock* block, const InstructionBlock* pred,
+            FindResult* result) {
+    const LifetimePosition pred_end =
+        LifetimePosition::FromInstructionIndex(pred->last_instruction_index());
+    LiveRangeBound* bound = Find(pred_end);
+    result->pred_cover_ = bound->range_;
+    const LifetimePosition cur_start = LifetimePosition::FromInstructionIndex(
+        block->first_instruction_index());
+    // Common case.
+    if (bound->CanCover(cur_start)) {
+      result->cur_cover_ = bound->range_;
+      return;
+    }
+    result->cur_cover_ = Find(cur_start)->range_;
+    DCHECK(result->pred_cover_ != NULL && result->cur_cover_ != NULL);
+  }
+
+ private:
+  size_t length_;
+  LiveRangeBound* start_;
+
+  DISALLOW_COPY_AND_ASSIGN(LiveRangeBoundArray);
+};
+
+
+class LiveRangeFinder {
+ public:
+  explicit LiveRangeFinder(const RegisterAllocator& allocator)
+      : allocator_(allocator),
+        bounds_length_(allocator.live_ranges().length()),
+        bounds_(
+            allocator.zone()->NewArray<LiveRangeBoundArray>(bounds_length_)) {
+    for (int i = 0; i < bounds_length_; ++i) {
+      new (&bounds_[i]) LiveRangeBoundArray();
+    }
+  }
+
+  bool SetCurrent(int operand_index) {

[Jarin, 2014/11/04 10:42:09]

Maybe this could return the LiveRangeBound pointer so that there is not this
funny 'current_' state in this class (then it is basically just a cache for the
bound arrays).

[dcarney, 2014/11/05 09:02:02]

Done.

+    current_ = NULL;
+    // TODO(dcarney): can this happen at this point?

[Jarin, 2014/11/04 10:42:09]

Yeah, just DCHECK here that the things that should not happen do not happen.

[dcarney, 2014/11/05 09:02:02]

Done.

+    if (operand_index >= bounds_length_) return false;
+    const LiveRange* range = allocator_.live_ranges()[operand_index];
+    // TODO(dcarney): can this happen at this point?
+    if (range == NULL || range->IsEmpty()) return false;
+    LiveRangeBoundArray* array = &bounds_[operand_index];
+    if (array->ShouldInitialize()) {
+      array->Initialize(allocator_.zone(), range);
+    }
+    current_ = array;
+    return true;
+  }
+
+  void Find(const InstructionBlock* block, const InstructionBlock* pred,
+            FindResult* result) {
+    current_->Find(block, pred, result);
+  }
+
+ private:
+  const RegisterAllocator& allocator_;
+  const int bounds_length_;
+  LiveRangeBoundArray* const bounds_;
+  LiveRangeBoundArray* current_;
+
+  DISALLOW_COPY_AND_ASSIGN(LiveRangeFinder);
+};
+
+}  // namespace
+
+
 void RegisterAllocator::ResolveControlFlow() {
-  for (int block_id = 1; block_id < code()->InstructionBlockCount();
-       ++block_id) {
-    const InstructionBlock* block =
-        code()->InstructionBlockAt(BasicBlock::RpoNumber::FromInt(block_id));
+  // Lazily linearize live ranges in memory for fast lookup.
+  LiveRangeFinder finder(*this);
+  for (auto block : code()->instruction_blocks()) {
     if (CanEagerlyResolveControlFlow(block)) continue;
     BitVector* live = live_in_sets_[block->rpo_number().ToInt()];
     BitVector::Iterator iterator(live);
     while (!iterator.Done()) {
-      int operand_index = iterator.Current();
+      if (!finder.SetCurrent(iterator.Current())) continue;
       for (auto pred : block->predecessors()) {
-        const InstructionBlock* cur = code()->InstructionBlockAt(pred);
-        LiveRange* cur_range = LiveRangeFor(operand_index);
-        ResolveControlFlow(cur_range, block, cur);
+        FindResult result;
+        const InstructionBlock* pred_block = code()->InstructionBlockAt(pred);
+        finder.Find(block, pred_block, &result);
+        if (result.cur_cover_ == result.pred_cover_ ||
+            result.cur_cover_->IsSpilled())
+          continue;
+        ResolveControlFlow(block, result.cur_cover_, pred_block,
+                           result.pred_cover_);
       }
       iterator.Advance();
     }
@@ -1321,6 +1415,30 @@ void RegisterAllocator::ResolveControlFlow() {
 }
 
 
+void RegisterAllocator::ResolveControlFlow(const InstructionBlock* block,
+                                           const LiveRange* cur_cover,
+                                           const InstructionBlock* pred,
+                                           const LiveRange* pred_cover) {
+  InstructionOperand* pred_op = pred_cover->CreateAssignedOperand(code_zone());
+  InstructionOperand* cur_op = cur_cover->CreateAssignedOperand(code_zone());
+  if (!pred_op->Equals(cur_op)) {
+    GapInstruction* gap = NULL;
+    if (block->PredecessorCount() == 1) {
+      gap = code()->GapAt(block->first_instruction_index());
+    } else {
+      DCHECK(pred->SuccessorCount() == 1);
+      gap = GetLastGap(pred);
+
+      Instruction* branch = InstructionAt(pred->last_instruction_index());
+      DCHECK(!branch->HasPointerMap());
+      USE(branch);
+    }
+    gap->GetOrCreateParallelMove(GapInstruction::START, code_zone())
+        ->AddMove(pred_op, cur_op, code_zone());
+  }
+}
+
+
 void RegisterAllocator::BuildLiveRanges() {
   InitializeLivenessAnalysis();
   // Process the blocks in reverse order.