Index: src/hydrogen.cc |
diff --git a/src/hydrogen.cc b/src/hydrogen.cc |
index 7ee6081026b7c58a786a3e3a5985a69259b1f787..93cbe2676a4b350024f69b860c77b1603d74c0da 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) { |
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 ? 2 : -3)); |
+ } |
+ } |
+ |
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. |