[hydrogen] optimize switch with string clauses

src/hydrogen.cc

 // Copyright 2011 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 716 matching lines @@
                        HBasicBlock* loop_header) {
   if (block == NULL || visited->Contains(block->block_id())) return;
   if (block->parent_loop_header() != loop_header) return;
   visited->Add(block->block_id());
   if (block->IsLoopHeader()) {
     PostorderLoopBlocks(block->loop_information(), visited, order, loop_header);
     for (HSuccessorIterator it(block->end()); !it.Done(); it.Advance()) {
       Postorder(it.Current(), visited, order, block);
     }
   } else {
+    ASSERT(block->IsFinished());
     for (HSuccessorIterator it(block->end()); !it.Done(); it.Advance()) {
       Postorder(it.Current(), visited, order, loop_header);
     }
   }
   ASSERT(block->end()->FirstSuccessor() == NULL ||
          order->Contains(block->end()->FirstSuccessor()) ||
          block->end()->FirstSuccessor()->IsLoopHeader());
   ASSERT(block->end()->SecondSuccessor() == NULL ||
          order->Contains(block->end()->SecondSuccessor()) ||
          block->end()->SecondSuccessor()->IsLoopHeader());
@@ skipping 1954 matching lines @@
   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();
   if (clause_count > kCaseClauseLimit) {
     return Bailout("SwitchStatement: too many clauses");
   }
 
+  HValue* context = environment()->LookupContext();
+
   CHECK_ALIVE(VisitForValue(stmt->tag()));
   AddSimulate(stmt->EntryId());
   HValue* tag_value = Pop();
   HBasicBlock* first_test_block = current_block();
 
-  // 1. Build all the tests, with dangling true branches.  Unconditionally
-  // deoptimize if we encounter a non-smi comparison.
+  SwitchType switch_type = UNKNOWN_SWITCH;
+
+  // 1. Extract clause type
   for (int i = 0; i < clause_count; ++i) {
     CaseClause* clause = clauses->at(i);
     if (clause->is_default()) continue;
-    if (!clause->label()->IsSmiLiteral()) {
-      return Bailout("SwitchStatement: non-literal switch label");
+
+    if (switch_type == UNKNOWN_SWITCH) {
+      if (clause->label()->IsSmiLiteral()) {
+        switch_type = SMI_SWITCH;
+      } else if (clause->label()->IsStringLiteral()) {
+        switch_type = STRING_SWITCH;
+      } else {
+        return Bailout("SwitchStatement: non-literal switch label");
+      }
+    } else if ((switch_type == STRING_SWITCH &&
+                !clause->label()->IsStringLiteral()) ||
+               (switch_type == SMI_SWITCH &&
+                !clause->label()->IsSmiLiteral())) {
+      return Bailout("SwitchStatemnt: mixed label types are not supported");
+    }
+  }
+
+  HUnaryControlInstruction* string_check = NULL;
+  HBasicBlock* not_string_block = NULL;
+
+  int iterations = clause_count;
+
+  // Test switch's tag value if all clauses are string literals
+  if (switch_type == STRING_SWITCH) {
+    // Bailout if we seen string(non-symbol) comparisons here
+    for (int i = 0; i < clause_count; ++i) {
+      CaseClause* clause = clauses->at(i);
+      if (clause->is_default()) continue;
+
+      clause->RecordTypeFeedback(oracle());
+
+      if (clause->IsStringCompare()) {
+        return Bailout("SwitchStatement: no symbol comparisons expected");
+      }
     }
 
-    // Unconditionally deoptimize on the first non-smi compare.
-    clause->RecordTypeFeedback(oracle());
-    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;
+    // We'll generate two passes of checks
+    iterations = iterations * 2;

[fschneider, 2011/11/07 08:27:18]

If it does not yield a big improvement, I'd rather generate 1 pass in any case.
It seems there are 3 cases:
1. only symbols, 2. only strings, 3. generic other stuff (e.g. oddballs)

(1) uses CompareObjectEqAndBranch
(2), (3) use StringCompareAndBranch.

There would need to be imho a strong performance argument to justify generating
2 passes, because it makes the CFG larger and complicates the graph
construction.

[indutny, 2011/11/07 11:17:04]

It yields a big improvement, as we usually don't know any type feedback for some
clauses and therefore can't use any type information here.

We can set clause count limit to 64 to preserve same maximum blocks count if you
want, but from my benchmarks having two passes of checks and oddball check
before them is most optimal solution for mutual switch tag's value.

[fschneider, 2011/11/07 15:34:00]

I'm still worried about quadratic size explosion because clause-blocks are not
shared between the two passes. In case of double-nested switch-statements you
get 4 copies of a clause. We need to share at least the clause bodies (as a
result the code for graph building will get even more complicated)

My suggestion: First land a simpler version that uses only 1 pass with
HStringCompareAndBranch. The graph construction would be much cleaner. Then
maybe try to tune it and improve it with concrete benchmark examples. It is
_much_ easier to review smaller chunks. The problem with huge changes is that it
takes forever to review and turnaround time will be long.

[indutny, 2011/11/07 17:06:08]

I tried implementing graph structure like that:
      |
     /\
    /  \
   o    o
   |\  /|
   o  b o
    \ | /
     \|/
      e

But it was much slower, while not generating bodies twice.

Agreed, done

+
+    string_check = new(zone()) HIsStringAndBranch(tag_value);
+    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);
+  }
+
+  // 2. Build all the tests, with dangling true branches
+  for (int i = 0; i < iterations; ++i) {
+    CaseClause* clause = clauses->at(i % clause_count);
+    if (clause->is_default()) continue;
+
+    if (switch_type == SMI_SWITCH) {
+      clause->RecordTypeFeedback(oracle());
     }
 
-    // Otherwise generate a compare and branch.
+    // Generate a compare and branch.
     CHECK_ALIVE(VisitForValue(clause->label()));
     HValue* label_value = Pop();
-    HCompareIDAndBranch* compare =
-        new(zone()) HCompareIDAndBranch(tag_value,
-                                        label_value,
-                                        Token::EQ_STRICT);
-    compare->SetInputRepresentation(Representation::Integer32());
+
+    HBasicBlock* next_test_block = graph()->CreateBasicBlock();
     HBasicBlock* body_block = graph()->CreateBasicBlock();
-    HBasicBlock* next_test_block = graph()->CreateBasicBlock();
+
+    HControlInstruction* compare;
+
+    if (switch_type == 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_ =
+          new(zone()) HCompareIDAndBranch(tag_value,
+                                          label_value,
+                                          Token::EQ_STRICT);
+      compare_->SetInputRepresentation(Representation::Integer32());
+      compare = compare_;
+    } else {
+      if (i < clause_count) {
+        compare = new(zone()) HCompareObjectEqAndBranch(tag_value, label_value);
+      } else {
+        compare = new(zone()) HCompareGenericAndBranch(context, tag_value,
+                                                       label_value,
+                                                       Token::EQ_STRICT);
+      }
+    }
+
     compare->SetSuccessorAt(0, body_block);
     compare->SetSuccessorAt(1, next_test_block);
     current_block()->Finish(compare);
+
     set_current_block(next_test_block);
   }
 
   // Save the current block to use for the default or to join with the
   // exit.  This block is NULL if we deoptimized.
   HBasicBlock* last_block = current_block();
 
-  // 2. Loop over the clauses and the linked list of tests in lockstep,
+  if (not_string_block != NULL) {
+    last_block = CreateJoin(last_block, not_string_block, stmt->ExitId());
+  }
+
+  // 3. 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;
+  HBasicBlock* fall_through_block_left = NULL;
+
   BreakAndContinueInfo break_info(stmt);
   { BreakAndContinueScope push(&break_info, this);
-    for (int i = 0; i < clause_count; ++i) {
-      CaseClause* clause = clauses->at(i);
+    for (int i = 0; i < iterations; ++i) {
+      // Create shadow last block for second pass
+      if (i == clause_count) {
+        fall_through_block_left = fall_through_block;
+        fall_through_block = NULL;
+      }
+
+      CaseClause* clause = clauses->at(i % clause_count);
 
       // 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()) {
@@ skipping 23 matching lines @@
                                        normal_block,
                                        clause->EntryId());
         set_current_block(join);
       }
 
       CHECK_BAILOUT(VisitStatements(clause->statements()));
       fall_through_block = current_block();
     }
   }
 
+  // Join tails of parallel branches
+  fall_through_block = CreateJoin(fall_through_block, fall_through_block_left,
+                                  stmt->ExitId());
+
   // Create an up-to-3-way join.  Use the break block if it exists since
   // it's already a join block.
   HBasicBlock* break_block = break_info.break_block();
   if (break_block == NULL) {
     set_current_block(CreateJoin(fall_through_block,
                                  last_block,
                                  stmt->ExitId()));
   } else {
     if (fall_through_block != NULL) fall_through_block->Goto(break_block);
     if (last_block != NULL) last_block->Goto(break_block);
@@ skipping 4217 matching lines @@
     }
   }
 
 #ifdef DEBUG
   if (graph_ != NULL) graph_->Verify(false);  // No full verify.
   if (allocator_ != NULL) allocator_->Verify();
 #endif
 }
 
 } }  // namespace v8::internal