Refactor construction of polymorphic loads, stores, and calls.

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 88 matching lines @@
 }
 
 
 void HBasicBlock::AddInstruction(HInstruction* instr) {
   ASSERT(!IsStartBlock() || !IsFinished());
   ASSERT(!instr->IsLinked());
   ASSERT(!IsFinished());
   if (first_ == NULL) {
     HBlockEntry* entry = new HBlockEntry();
     entry->InitializeAsFirst(this);
-    first_ = entry;
+    first_ = last_ = entry;
   }
-  instr->InsertAfter(GetLastInstruction());
+  instr->InsertAfter(last_);
+  last_ = instr;
 }
 
 
-HInstruction* HBasicBlock::GetLastInstruction() {
-  if (end_ != NULL) return end_->previous();
-  if (first_ == NULL) return NULL;
-  if (last_ == NULL) last_ = first_;
-  while (last_->next() != NULL) last_ = last_->next();
-  return last_;
-}
-
-
 HSimulate* HBasicBlock::CreateSimulate(int id) {
   ASSERT(HasEnvironment());
   HEnvironment* environment = last_environment();
   ASSERT(id == AstNode::kNoNumber ||
          environment->closure()->shared()->VerifyBailoutId(id));
 
   int push_count = environment->push_count();
   int pop_count = environment->pop_count();
 
   int length = environment->length();
@@ skipping 37 matching lines @@
   UpdateEnvironment(env);
 }
 
 
 void HBasicBlock::SetJoinId(int id) {
   int length = predecessors_.length();
   ASSERT(length > 0);
   for (int i = 0; i < length; i++) {
     HBasicBlock* predecessor = predecessors_[i];
     ASSERT(predecessor->end()->IsGoto());
-    HSimulate* simulate = HSimulate::cast(predecessor->GetLastInstruction());
+    HSimulate* simulate = HSimulate::cast(predecessor->end()->previous());
     // We only need to verify the ID once.
     ASSERT(i != 0 ||
            predecessor->last_environment()->closure()->shared()
                ->VerifyBailoutId(id));
     simulate->set_ast_id(id);
   }
 }
 
 
 bool HBasicBlock::Dominates(HBasicBlock* other) const {
@@ skipping 2887 matching lines @@
   }
   ast_context()->ReturnValue(Pop());
 }
 
 
 void HGraphBuilder::VisitCatchExtensionObject(CatchExtensionObject* expr) {
   BAILOUT("CatchExtensionObject");
 }
 
 
-HBasicBlock* HGraphBuilder::BuildTypeSwitch(ZoneMapList* maps,
-                                            ZoneList<HSubgraph*>* subgraphs,
-                                            HValue* receiver,
+HBasicBlock* HGraphBuilder::BuildTypeSwitch(HValue* receiver,
+                                            ZoneMapList* maps,
+                                            ZoneList<HSubgraph*>* body_graphs,
+                                            HSubgraph* default_graph,
                                             int join_id) {
-  ASSERT(subgraphs->length() == (maps->length() + 1));
+  ASSERT(maps->length() == body_graphs->length());
+  HBasicBlock* join_block = graph()->CreateBasicBlock();
+  AddInstruction(new HCheckNonSmi(receiver));
 
-  // Build map compare subgraphs for all but the first map.
-  ZoneList<HSubgraph*> map_compare_subgraphs(maps->length() - 1);
-  for (int i = maps->length() - 1; i > 0; --i) {
-    HSubgraph* subgraph = CreateBranchSubgraph(environment());
-    SubgraphScope scope(this, subgraph);
-    HSubgraph* else_subgraph =
-        (i == (maps->length() - 1))
-        ? subgraphs->last()
-        : map_compare_subgraphs.last();
-    HCompareMap* compare = new HCompareMap(receiver,
-                                           maps->at(i),
-                                           subgraphs->at(i)->entry_block(),
-                                           else_subgraph->entry_block());
-    current_subgraph_->exit_block()->Finish(compare);
-    map_compare_subgraphs.Add(subgraph);
+  for (int i = 0; i < maps->length(); ++i) {
+    // Build the branches, connect all the target subgraphs to the join
+    // block.  Use the default as a target of the last branch.
+    HSubgraph* if_true = body_graphs->at(i);
+    HSubgraph* if_false = (i == maps->length() - 1)
+        ? default_graph
+        : CreateBranchSubgraph(environment());
+    HCompareMap* compare =
+        new HCompareMap(receiver,
+                        maps->at(i),
+                        if_true->entry_block(),
+                        if_false->entry_block());
+    subgraph()->exit_block()->Finish(compare);
+
+    if (if_true->HasExit()) {
+      // In an effect context the value of the type switch is not needed.
+      // There is no need to merge it at the join block only to discard it.
+      if (ast_context()->IsEffect()) {
+        if_true->exit_block()->last_environment()->Drop(1);
+      }
+      if_true->exit_block()->Goto(join_block);
+    }
+
+    subgraph()->set_exit_block(if_false->exit_block());
   }
 
-  // Generate first map check to end the current block.
-  AddInstruction(new HCheckNonSmi(receiver));
-  HSubgraph* else_subgraph =
-      (maps->length() == 1) ? subgraphs->at(1) : map_compare_subgraphs.last();
-  HCompareMap* compare = new HCompareMap(receiver,
-                                         Handle<Map>(maps->first()),
-                                         subgraphs->first()->entry_block(),
-                                         else_subgraph->entry_block());
-  current_subgraph_->exit_block()->Finish(compare);
-
-  // Join all the call subgraphs in a new basic block and make
-  // this basic block the current basic block.
-  HBasicBlock* join_block = graph_->CreateBasicBlock();
-  for (int i = 0; i < subgraphs->length(); ++i) {
-    HSubgraph* subgraph = subgraphs->at(i);
-    if (subgraph->HasExit()) {
-      // In an effect context the value of the type switch is not needed.
-      // There is no need to merge it at the join block only to discard it.
-      HBasicBlock* subgraph_exit = subgraph->exit_block();
-      if (ast_context()->IsEffect()) {
-        subgraph_exit->last_environment()->Drop(1);
-      }
-      subgraph_exit->Goto(join_block);
+  // Connect the default if necessary.
+  if (subgraph()->HasExit()) {
+    if (ast_context()->IsEffect()) {
+      environment()->Drop(1);
     }
+    subgraph()->exit_block()->Goto(join_block);
   }
 
   if (join_block->predecessors()->is_empty()) return NULL;
   join_block->SetJoinId(join_id);
   return join_block;
 }
 
 
 // Sets the lookup result and returns true if the store can be inlined.
 static bool ComputeStoredField(Handle<Map> type,
@@ skipping 85 matching lines @@
 }
 
 
 void HGraphBuilder::HandlePolymorphicStoreNamedField(Assignment* expr,
                                                      HValue* object,
                                                      HValue* value,
                                                      ZoneMapList* types,
                                                      Handle<String> name) {
   int number_of_types = Min(types->length(), kMaxStorePolymorphism);
   ZoneMapList maps(number_of_types);
-  ZoneList<HSubgraph*> subgraphs(number_of_types + 1);
+  ZoneList<HSubgraph*> subgraphs(number_of_types);
   bool needs_generic = (types->length() > kMaxStorePolymorphism);
 
   // Build subgraphs for each of the specific maps.
   //
   // TODO(ager): We should recognize when the prototype chains for
   // different maps are identical. In that case we can avoid
   // repeatedly generating the same prototype map checks.
   for (int i = 0; i < number_of_types; ++i) {
     Handle<Map> map = types->at(i);
     LookupResult lookup;
     if (ComputeStoredField(map, name, &lookup)) {
-      maps.Add(map);
       HSubgraph* subgraph = CreateBranchSubgraph(environment());
       SubgraphScope scope(this, subgraph);
       HInstruction* instr =
           BuildStoreNamedField(object, name, value, map, &lookup, false);
       Push(value);
       instr->set_position(expr->position());
       AddInstruction(instr);
+      maps.Add(map);
       subgraphs.Add(subgraph);
     } else {
       needs_generic = true;
     }
   }
 
   // If none of the properties were named fields we generate a
   // generic store.
   if (maps.length() == 0) {
     HInstruction* instr = BuildStoreNamedGeneric(object, name, value);
     Push(value);
     instr->set_position(expr->position());
     AddInstruction(instr);
     if (instr->HasSideEffects()) AddSimulate(expr->AssignmentId());
     ast_context()->ReturnValue(Pop());
   } else {
     // Build subgraph for generic store through IC.
-    {
-      HSubgraph* subgraph = CreateBranchSubgraph(environment());
-      SubgraphScope scope(this, subgraph);
+    HSubgraph* default_graph = CreateBranchSubgraph(environment());
+    { SubgraphScope scope(this, default_graph);
       if (!needs_generic && FLAG_deoptimize_uncommon_cases) {
-        subgraph->FinishExit(new HDeoptimize());
+        default_graph->FinishExit(new HDeoptimize());
       } else {
         HInstruction* instr = BuildStoreNamedGeneric(object, name, value);
         Push(value);
         instr->set_position(expr->position());
         AddInstruction(instr);
       }
-      subgraphs.Add(subgraph);
     }
 
     HBasicBlock* new_exit_block =
-        BuildTypeSwitch(&maps, &subgraphs, object, expr->id());
+        BuildTypeSwitch(object, &maps, &subgraphs, default_graph, expr->id());
     subgraph()->set_exit_block(new_exit_block);
     // In an effect context, we did not materialized the value in the
     // predecessor environments so there's no need to handle it here.
     if (subgraph()->HasExit() && !ast_context()->IsEffect()) {
       ast_context()->ReturnValue(Pop());
     }
   }
 }
 
 
@@ skipping 254 matching lines @@
   current_subgraph_->FinishExit(new HAbnormalExit);
 }
 
 
 void HGraphBuilder::HandlePolymorphicLoadNamedField(Property* expr,
                                                     HValue* object,
                                                     ZoneMapList* types,
                                                     Handle<String> name) {
   int number_of_types = Min(types->length(), kMaxLoadPolymorphism);
   ZoneMapList maps(number_of_types);
-  ZoneList<HSubgraph*> subgraphs(number_of_types + 1);
+  ZoneList<HSubgraph*> subgraphs(number_of_types);
   bool needs_generic = (types->length() > kMaxLoadPolymorphism);
 
   // Build subgraphs for each of the specific maps.
   //
   // TODO(ager): We should recognize when the prototype chains for
   // different maps are identical. In that case we can avoid
   // repeatedly generating the same prototype map checks.
   for (int i = 0; i < number_of_types; ++i) {
     Handle<Map> map = types->at(i);
     LookupResult lookup;
     map->LookupInDescriptors(NULL, *name, &lookup);
     if (lookup.IsProperty() && lookup.type() == FIELD) {
-      maps.Add(map);
       HSubgraph* subgraph = CreateBranchSubgraph(environment());
       SubgraphScope scope(this, subgraph);
       HLoadNamedField* instr =
           BuildLoadNamedField(object, expr, map, &lookup, false);
       instr->set_position(expr->position());
       instr->ClearFlag(HValue::kUseGVN);  // Don't do GVN on polymorphic loads.
       PushAndAdd(instr);
+      maps.Add(map);
       subgraphs.Add(subgraph);
     } else {
       needs_generic = true;
     }
   }
 
   // If none of the properties were named fields we generate a
   // generic load.
   if (maps.length() == 0) {
     HInstruction* instr = BuildLoadNamedGeneric(object, expr);
     instr->set_position(expr->position());
     ast_context()->ReturnInstruction(instr, expr->id());
   } else {
     // Build subgraph for generic load through IC.
-    {
-      HSubgraph* subgraph = CreateBranchSubgraph(environment());
-      SubgraphScope scope(this, subgraph);
+    HSubgraph* default_graph = CreateBranchSubgraph(environment());
+    { SubgraphScope scope(this, default_graph);
       if (!needs_generic && FLAG_deoptimize_uncommon_cases) {
-        subgraph->FinishExit(new HDeoptimize());
+        default_graph->FinishExit(new HDeoptimize());
       } else {
         HInstruction* instr = BuildLoadNamedGeneric(object, expr);
         instr->set_position(expr->position());
         PushAndAdd(instr);
       }
-      subgraphs.Add(subgraph);
     }
 
     HBasicBlock* new_exit_block =
-        BuildTypeSwitch(&maps, &subgraphs, object, expr->id());
+        BuildTypeSwitch(object, &maps, &subgraphs, default_graph, expr->id());
     subgraph()->set_exit_block(new_exit_block);
     // In an effect context, we did not materialized the value in the
     // predecessor environments so there's no need to handle it here.
     if (subgraph()->HasExit() && !ast_context()->IsEffect()) {
       ast_context()->ReturnValue(Pop());
     }
   }
 }
 
 
@@ skipping 256 matching lines @@
 }
 
 
 void HGraphBuilder::HandlePolymorphicCallNamed(Call* expr,
                                                HValue* receiver,
                                                ZoneMapList* types,
                                                Handle<String> name) {
   int argument_count = expr->arguments()->length() + 1;  // Plus receiver.
   int number_of_types = Min(types->length(), kMaxCallPolymorphism);
   ZoneMapList maps(number_of_types);
-  ZoneList<HSubgraph*> subgraphs(number_of_types + 1);
+  ZoneList<HSubgraph*> subgraphs(number_of_types);
   bool needs_generic = (types->length() > kMaxCallPolymorphism);
 
   // Build subgraphs for each of the specific maps.
   //
   // TODO(ager): We should recognize when the prototype chains for different
   // maps are identical. In that case we can avoid repeatedly generating the
   // same prototype map checks.
   for (int i = 0; i < number_of_types; ++i) {
     Handle<Map> map = types->at(i);
     if (expr->ComputeTarget(map, name)) {
-      maps.Add(map);
       HSubgraph* subgraph = CreateBranchSubgraph(environment());
       SubgraphScope scope(this, subgraph);
       AddCheckConstantFunction(expr, receiver, map, false);
       if (FLAG_trace_inlining && FLAG_polymorphic_inlining) {
         PrintF("Trying to inline the polymorphic call to %s\n",
                *name->ToCString());
       }
       if (!FLAG_polymorphic_inlining || !TryInline(expr)) {
         // Check for bailout, as trying to inline might fail due to bailout
         // during hydrogen processing.
         CHECK_BAILOUT;
         HCall* call = new HCallConstantFunction(expr->target(), argument_count);
         call->set_position(expr->position());
         PreProcessCall(call);
         PushAndAdd(call);
       }
+      maps.Add(map);
       subgraphs.Add(subgraph);
     } else {
       needs_generic = true;
     }
   }
 
   // If we couldn't compute the target for any of the maps just perform an
   // IC call.
   if (maps.length() == 0) {
     HContext* context = new HContext;
     AddInstruction(context);
     HCall* call = new HCallNamed(context, name, argument_count);
     call->set_position(expr->position());
     PreProcessCall(call);
     ast_context()->ReturnInstruction(call, expr->id());
   } else {
     // Build subgraph for generic call through IC.
-    {
-      HSubgraph* subgraph = CreateBranchSubgraph(environment());
-      SubgraphScope scope(this, subgraph);
+    HSubgraph* default_graph = CreateBranchSubgraph(environment());
+    { SubgraphScope scope(this, default_graph);
       if (!needs_generic && FLAG_deoptimize_uncommon_cases) {
-        subgraph->FinishExit(new HDeoptimize());
+        default_graph->FinishExit(new HDeoptimize());
       } else {
         HContext* context = new HContext;
         AddInstruction(context);
         HCall* call = new HCallNamed(context, name, argument_count);
         call->set_position(expr->position());
         PreProcessCall(call);
         PushAndAdd(call);
       }
-      subgraphs.Add(subgraph);
     }
 
     HBasicBlock* new_exit_block =
-        BuildTypeSwitch(&maps, &subgraphs, receiver, expr->id());
+        BuildTypeSwitch(receiver, &maps, &subgraphs, default_graph, expr->id());
     subgraph()->set_exit_block(new_exit_block);
     // In an effect context, we did not materialized the value in the
     // predecessor environments so there's no need to handle it here.
     if (new_exit_block != NULL && !ast_context()->IsEffect()) {
       ast_context()->ReturnValue(Pop());
     }
   }
 }
 
 
@@ skipping 2025 matching lines @@
     }
   }
 
 #ifdef DEBUG
   if (graph_ != NULL) graph_->Verify();
   if (allocator_ != NULL) allocator_->Verify();
 #endif
 }
 
 } }  // namespace v8::internal