[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 1942 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* oddball_check = NULL;
+  HBasicBlock* oddball_block = NULL;
+
+  int iterations = clause_count;
+
+  // Test switch's tag value if all clauses are string literals
+  if (switch_type == STRING_SWITCH) {
+    // We'll generate two passes of checks
+    iterations = iterations * 2;
+
+    oddball_check = new(zone()) HIsStringAndBranch(tag_value);
+    first_test_block = graph()->CreateBasicBlock();
+    oddball_block = graph()->CreateBasicBlock();
+
+    oddball_check->SetSuccessorAt(0, first_test_block);
+    oddball_check->SetSuccessorAt(1, oddball_block);
+    current_block()->Finish(oddball_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;
+
+    clause->RecordTypeFeedback(oracle());
+
+    // Generate a compare and branch.
+    CHECK_ALIVE(VisitForValue(clause->label()));
+    HValue* label_value = Pop();
+
+    HBasicBlock* next_test_block = graph()->CreateBasicBlock();
+    HBasicBlock* body_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,

[fschneider, 2011/11/01 09:26:19]

Not sure this works: If you pass an object as tag value, we may get a
lazy-deoptimization at this instruction: The generic compare may invoke other JS
code through valueOf method.

The problem is that we can't insert a LLazyBailout instruction for the
lazy-deopt after a branch. That's why we only had CompareGeneric (without
branch).

How about only handling the string-cases, and deoptimize on others? I think the
code would get a lot simpler, too.

[indutny, 2011/11/01 09:31:07]

tag_value can't be object, as we have oddball check above

+                                                       label_value,
+                                                       Token::EQ_STRICT);
+      }
     }
 
-    // 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;
-    }
-
-    // Otherwise 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* body_block = graph()->CreateBasicBlock();
-    HBasicBlock* next_test_block = graph()->CreateBasicBlock();
     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 (oddball_block != NULL) {
+    if (last_block != NULL) {

[fschneider, 2011/11/01 09:26:19]

Can it happen at all that we deoptimize (and last_block == NULL) if there are
only string-literals? last_block should be never NULL in this case, shouldn't
it?

+      last_block = CreateJoin(last_block, oddball_block, stmt->ExitId());
+    } else {
+      oddball_block->Goto(first_test_block);
+    }
+  }
+
+  // 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 4215 matching lines @@
     }
   }
 
 #ifdef DEBUG
   if (graph_ != NULL) graph_->Verify(false);  // No full verify.
   if (allocator_ != NULL) allocator_->Verify();
 #endif
 }
 
 } }  // namespace v8::internal