Reorder switch clauses using newly-introduced execution counters in

src/hydrogen.cc

Index: src/hydrogen.cc
diff --git a/src/hydrogen.cc b/src/hydrogen.cc
index 7ee6081026b7c58a786a3e3a5985a69259b1f787..5cf5889a26bac85625773ad2890d0e6b5b299221 100644
--- a/src/hydrogen.cc
+++ b/src/hydrogen.cc
@@ -1940,6 +1940,7 @@ HOptimizedGraphBuilder::HOptimizedGraphBuilder(CompilationInfo* info)
       ast_context_(NULL),
       break_scope_(NULL),
       inlined_count_(0),
+      deopt_counter_count_(0),
       globals_(10, info->zone()),
       inline_bailout_(false) {
   // This is not initialized in the initializer list because the
@@ -4641,6 +4642,16 @@ void HOptimizedGraphBuilder::AddSoftDeoptimize() {
 }
 
 
+HDeoptCounter* HOptimizedGraphBuilder::AddDeoptCounter(int initial_value,
+                                                       int max_value) {
+  HDeoptCounter* res = new(zone()) HDeoptCounter(deopt_counter_count_++,
+                                                 initial_value,
+                                                 max_value);
+  AddInstruction(res);
+  return res;
+}
+
+
 template <class Instruction>
 HInstruction* HOptimizedGraphBuilder::PreProcessCall(Instruction* call) {
   int count = call->argument_count();
@@ -4927,6 +4938,14 @@ void HOptimizedGraphBuilder::VisitWithStatement(WithStatement* stmt) {
 }
 
 
+int HOptimizedGraphBuilder::ClauseMapping::HitCountOrder(
+    ClauseMapping* const* a,
+    ClauseMapping* const* b) {
+  return (*a)->clause()->hit_count() == (*b)->clause()->hit_count() ? 0 :
+         (*a)->clause()->hit_count() > (*b)->clause()->hit_count() ? -1 : 1;
+}
+
+
 void HOptimizedGraphBuilder::VisitSwitchStatement(SwitchStatement* stmt) {

[Sven Panne, 2013/06/03 07:30:44]

We shouldn't grow this monster even more, making it basically non-understandable
and unmaintainable (>200 lines).

[indutny, 2013/06/03 07:50:53]

Surely it can be split in multiple parts.

   ASSERT(!HasStackOverflow());
   ASSERT(current_block() != NULL);
@@ -4969,10 +4988,65 @@ void HOptimizedGraphBuilder::VisitSwitchStatement(SwitchStatement* stmt) {
     set_current_block(first_test_block);
   }
 
+  // 0. Order clauses by hit count
+  ZoneList<ClauseMapping*> ordered_clauses(clause_count, zone());
+  ZoneList<HBasicBlock*> clause_test_blocks(clause_count, zone());
+  int max_hit = 0;
+  int min_hit = clause_count == 0 ? 0 : kMaxInt;
+  for (int i = 0; i < clause_count; ++i) {
+    int hits = clauses->at(i)->hit_count();
+    if (hits > max_hit) max_hit = hits;
+    if (hits < min_hit) min_hit = hits;
+
+    ordered_clauses.Add(new(zone()) ClauseMapping(i, clauses->at(i)), zone());
+    clause_test_blocks.Add(NULL, zone());
+  }
+
+  // Number of top cases that are executing at relatively the same speed.
+  const int kClauseReorderSoftLimit = 5;
+
+  // Maximum percent of `min_hit / max_hit` at which optimization is
+  // still allowed.
+  const int kClauseMinDeltaHit = 50;
+
+  // Reorder clauses only if there's a significant difference between
+  // maximum and minimum hit counts.
+  bool reorder_clauses =
+      max_hit == 0 ? false : ((100 * min_hit / max_hit) < kClauseMinDeltaHit);
+
+  HDeoptCounter* counter = NULL;
+
+  // If hit distribution doesn't change much - counter should always stay
+  // below zero. Check that clauses above te soft mark have more weight than
+  // clauses below the mark, and add CounterAdd instruction at the soft mark
+  // boundary with +1, -1 values to catch distribution change.
+  if (reorder_clauses) {
+    ordered_clauses.Sort(ClauseMapping::HitCountOrder);
+
+    double above = 0;
+    double below = 0;
+    for (int i = 0; i < clause_count; ++i) {
+      double hits =
+          static_cast<double>(ordered_clauses.at(i)->clause()->hit_count());
+      if (i < kClauseReorderSoftLimit) {
+        above += hits;
+      } else {
+        below += hits;
+      }
+    }
+
+    double max = static_cast<double>(max_hit) * kClauseReorderSoftLimit;
+    if (above > below && max < Smi::kMaxValue && Smi::IsValid(max)) {
+      counter = AddDeoptCounter(max_hit, max);
+    }
+  }
+
   // 1. Build all the tests, with dangling true branches
   BailoutId default_id = BailoutId::None();
   for (int i = 0; i < clause_count; ++i) {
-    CaseClause* clause = clauses->at(i);
+    int index = ordered_clauses.at(i)->index();
+    CaseClause* clause = ordered_clauses.at(i)->clause();
+
     if (clause->is_default()) {
       default_id = clause->EntryId();
       continue;
@@ -4982,11 +5056,20 @@ void HOptimizedGraphBuilder::VisitSwitchStatement(SwitchStatement* stmt) {
     CHECK_ALIVE(VisitForValue(clause->label()));
     HValue* label_value = Pop();
 
+    // Save test block for later traversal in AST-order
+    clause_test_blocks[index] = current_block();
     HBasicBlock* next_test_block = graph()->CreateBasicBlock();
     HBasicBlock* body_block = graph()->CreateBasicBlock();
 
     HControlInstruction* compare;
 
+    // Deoptimize when balance shifts from top clauses to bottom ones
+    if (counter != NULL) {
+      if (i == 0 || i == kClauseReorderSoftLimit) {
+        AddInstruction(new(zone()) HDeoptCounterAdd(counter, i == 0 ? 1 : -2));
+      }
+    }
+
     if (stmt->switch_type() == SwitchStatement::SMI_SWITCH) {
       if (!clause->IsSmiCompare()) {
         // Finish with deoptimize and add uses of enviroment values to
@@ -5027,12 +5110,12 @@ void HOptimizedGraphBuilder::VisitSwitchStatement(SwitchStatement* stmt) {
 
   // 2. Loop over the clauses and the linked list of tests in lockstep,
   // translating the clause bodies.
-  HBasicBlock* curr_test_block = first_test_block;
   HBasicBlock* fall_through_block = NULL;
 
   BreakAndContinueInfo break_info(stmt);
   { BreakAndContinueScope push(&break_info, this);
     for (int i = 0; i < clause_count; ++i) {
+      HBasicBlock* curr_test_block = clause_test_blocks.at(i);
       CaseClause* clause = clauses->at(i);
 
       // Identify the block where normal (non-fall-through) control flow
@@ -5045,7 +5128,6 @@ void HOptimizedGraphBuilder::VisitSwitchStatement(SwitchStatement* stmt) {
         }
       } else if (!curr_test_block->end()->IsDeoptimize()) {
         normal_block = curr_test_block->end()->FirstSuccessor();
-        curr_test_block = curr_test_block->end()->SecondSuccessor();
       }
 
       // Identify a block to emit the body into.