Reorder switch clauses using newly-introduced execution counters in

src/hydrogen.cc

 // Copyright 2012 the V8 project authors. All rights reserved.
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
@@ skipping 1922 matching lines @@
 }
 
 
 HOptimizedGraphBuilder::HOptimizedGraphBuilder(CompilationInfo* info)
     : HGraphBuilder(info),
       function_state_(NULL),
       initial_function_state_(this, info, NORMAL_RETURN),
       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
   // constructor for the initial state relies on function_state_ == NULL
   // to know it's the initial state.
   function_state_= &initial_function_state_;
   InitializeAstVisitor();
 }
 
 
@@ skipping 2681 matching lines @@
 
 void HOptimizedGraphBuilder::AddSoftDeoptimize() {
   if (FLAG_always_opt) return;
   if (current_block()->IsDeoptimizing()) return;
   AddInstruction(new(zone()) HSoftDeoptimize());
   current_block()->MarkAsDeoptimizing();
   graph()->set_has_soft_deoptimize(true);
 }
 
 
+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();
   ZoneList<HValue*> arguments(count, zone());
   for (int i = 0; i < count; ++i) {
     arguments.Add(Pop(), zone());
   }
 
   while (!arguments.is_empty()) {
     AddInstruction(new(zone()) HPushArgument(arguments.RemoveLast()));
@@ skipping 266 matching lines @@
 
 
 void HOptimizedGraphBuilder::VisitWithStatement(WithStatement* stmt) {
   ASSERT(!HasStackOverflow());
   ASSERT(current_block() != NULL);
   ASSERT(current_block()->HasPredecessor());
   return Bailout("WithStatement");
 }
 
 
+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) {
   ASSERT(!HasStackOverflow());
   ASSERT(current_block() != NULL);
   ASSERT(current_block()->HasPredecessor());
 
   // We only optimize switch statements with smi-literal smi comparisons,
   // with a bounded number of clauses.
   const int kCaseClauseLimit = 128;
   ZoneList<CaseClause*>* clauses = stmt->cases();
   int clause_count = clauses->length();
@@ skipping 22 matching lines @@
     first_test_block = graph()->CreateBasicBlock();
     not_string_block = graph()->CreateBasicBlock();
 
     string_check->SetSuccessorAt(0, first_test_block);
     string_check->SetSuccessorAt(1, not_string_block);
     current_block()->Finish(string_check);
 
     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;
     }
 
     // Generate a compare and branch.
     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 ? 2 : -3));
+      }
+    }
+
     if (stmt->switch_type() == SwitchStatement::SMI_SWITCH) {
       if (!clause->IsSmiCompare()) {
         // Finish with deoptimize and add uses of enviroment values to
         // account for invisible uses.
         current_block()->FinishExitWithDeoptimization(HDeoptimize::kUseAll);
         set_current_block(NULL);
         break;
       }
 
       HCompareIDAndBranch* compare_ =
@@ skipping 20 matching lines @@
   // exit.  This block is NULL if we deoptimized.
   HBasicBlock* last_block = current_block();
 
   if (not_string_block != NULL) {
     BailoutId join_id = !default_id.IsNone() ? default_id : stmt->ExitId();
     last_block = CreateJoin(last_block, not_string_block, join_id);
   }
 
   // 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
       // goes to.
       HBasicBlock* normal_block = NULL;
       if (clause->is_default()) {
         if (last_block != NULL) {
           normal_block = last_block;
           last_block = NULL;  // Cleared to indicate we've handled it.
         }
       } 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.
       if (normal_block == NULL) {
         if (fall_through_block == NULL) {
           // (a) Unreachable.
           if (clause->is_default()) {
             continue;  // Might still be reachable clause bodies.
           } else {
             break;
@@ skipping 6439 matching lines @@
     }
   }
 
 #ifdef DEBUG
   if (graph_ != NULL) graph_->Verify(false);  // No full verify.
   if (allocator_ != NULL) allocator_->Verify();
 #endif
 }
 
 } }  // namespace v8::internal