Generate the TransitionElementsStub using Crankshaft

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 203 matching lines @@
 
 void HBasicBlock::SetJoinId(BailoutId ast_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->end()->previous());
     // We only need to verify the ID once.
     ASSERT(i != 0 ||
-           predecessor->last_environment()->closure()->shared()
-               ->VerifyBailoutId(ast_id));
+           (predecessor->last_environment()->closure().is_null() ||
+            predecessor->last_environment()->closure()->shared()
+              ->VerifyBailoutId(ast_id)));
     simulate->set_ast_id(ast_id);
   }
 }
 
 
 bool HBasicBlock::Dominates(HBasicBlock* other) const {
   HBasicBlock* current = other->dominator();
   while (current != NULL) {
     if (current == this) return true;
     current = current->dominator();
@@ skipping 359 matching lines @@
   if (!pointer->is_set()) {
     HConstant* constant =
         new(zone()) HConstant(value, Representation::Integer32());
     constant->InsertAfter(GetConstantUndefined());
     pointer->set(constant);
   }
   return pointer->get();
 }
 
 
+HConstant* HGraph::GetConstant0() {
+  return GetConstantInt32(&constant_0_, 0);
+}
+
+
 HConstant* HGraph::GetConstant1() {
   return GetConstantInt32(&constant_1_, 1);
 }
 
 
 HConstant* HGraph::GetConstantMinus1() {
   return GetConstantInt32(&constant_minus1_, -1);
 }
 
 
 HConstant* HGraph::GetConstantTrue() {
   return GetConstant(&constant_true_, isolate()->factory()->true_value());
 }
 
 
 HConstant* HGraph::GetConstantFalse() {
   return GetConstant(&constant_false_, isolate()->factory()->false_value());
 }
 
 
 HConstant* HGraph::GetConstantHole() {
   return GetConstant(&constant_hole_, isolate()->factory()->the_hole_value());
 }
 
 
+HGraphBuilder::IfBuilder::IfBuilder(HGraphBuilder* builder, BailoutId id)
+    : builder_(builder),
+      finished_(false),
+      id_(id) {
+  HEnvironment* env = builder->environment();
+  true_env_ = env->Copy();

[Michael Starzinger, 2013/02/01 13:15:08]

I think it is safer not to preserve these environments in instance variables
(see comment about body_env_ below).

[danno, 2013/02/02 17:56:21]

Done.

+  false_env_ = env->Copy();
+  merge_env_ = env->Copy();
+  true_block_ = builder->CreateBasicBlock(true_env_);
+  false_block_ = builder->CreateBasicBlock(false_env_);
+  merge_block_ = builder->CreateBasicBlock(merge_env_);
+}
+
+
+void HGraphBuilder::IfBuilder::BeginTrue(HValue* left,
+                                         HValue* right,
+                                         Token::Value token) {
+  HCompareIDAndBranch* compare =
+      new(zone()) HCompareIDAndBranch(left, right, token);
+  compare->ChangeRepresentation(Representation::Integer32());
+  compare->SetSuccessorAt(0, true_block_);
+  compare->SetSuccessorAt(1, false_block_);
+  builder_->current_block()->Finish(compare);
+  builder_->set_current_block(true_block_);
+}
+
+
+void HGraphBuilder::IfBuilder::BeginFalse() {
+  builder_->current_block()->Goto(merge_block_);
+  builder_->set_current_block(false_block_);
+}
+
+
+void HGraphBuilder::IfBuilder::End() {
+  ASSERT(!finished_);
+  builder_->current_block()->Goto(merge_block_);
+  builder_->set_current_block(merge_block_);
+  merge_block_->SetJoinId(id_);
+  finished_ = true;
+}
+
+
+HGraphBuilder::LoopBuilder::LoopBuilder(HGraphBuilder* builder,
+                                        HValue* context,
+                                        LoopBuilder::Direction direction,
+                                        BailoutId id)
+    : builder_(builder),
+      context_(context),
+      direction_(direction),
+      id_(id),
+      finished_(false) {
+  HEnvironment* env = builder_->environment();
+  body_env_ = env->Copy();

[Michael Starzinger, 2013/02/01 13:15:08]

Likewise.

[danno, 2013/02/02 17:56:21]

Done.

+  exit_env_ = env->Copy();
+  header_block_ = builder->CreateLoopHeaderBlock();
+  body_block_ = builder->CreateBasicBlock(body_env_);
+  exit_block_ = builder->CreateBasicBlock(exit_env_);
+}
+
+
+HValue* HGraphBuilder::LoopBuilder::BeginBody(HValue* initial,
+                                              HValue* terminating,
+                                              Token::Value token) {
+  phi_ = new(zone()) HPhi(0, zone());
+  header_block_->AddPhi(phi_);
+  phi_->AddInput(initial);
+  phi_->ChangeRepresentation(Representation::Integer32());
+  HEnvironment* env = builder_->environment();
+  env->Push(initial);
+  builder_->current_block()->Goto(header_block_);
+  builder_->set_current_block(header_block_);
+
+  builder_->set_current_block(header_block_);
+  HCompareIDAndBranch* compare =
+      new(zone()) HCompareIDAndBranch(phi_, terminating, token);
+  compare->ChangeRepresentation(Representation::Integer32());
+  compare->SetSuccessorAt(0, body_block_);
+  compare->SetSuccessorAt(1, exit_block_);
+  builder_->current_block()->Finish(compare);
+
+  builder_->set_current_block(body_block_);
+  if (direction_ == kPreIncrement || direction_ == kPreDecrement) {
+    HValue* one = builder_->graph()->GetConstant1();
+    if (direction_ == kPreIncrement) {
+      increment_ = new(zone()) HAdd(context_, phi_, one);
+    } else {
+      increment_ = new(zone()) HSub(context_, phi_, one);
+    }
+    increment_->ClearFlag(HValue::kCanOverflow);
+    increment_->ChangeRepresentation(Representation::Integer32());
+    builder_->AddInstruction(increment_);
+    return increment_;
+  } else {
+    return phi_;
+  }
+}
+
+
+void HGraphBuilder::LoopBuilder::EndBody() {
+  ASSERT(!finished_);
+
+  if (direction_ == kPostIncrement || direction_ == kPostDecrement) {
+    HValue* one = builder_->graph()->GetConstant1();
+    if (direction_ == kPostIncrement) {
+      increment_ = new(zone()) HAdd(context_, phi_, one);
+    } else {
+      increment_ = new(zone()) HSub(context_, phi_, one);
+    }
+    increment_->ClearFlag(HValue::kCanOverflow);
+    increment_->ChangeRepresentation(Representation::Integer32());
+    builder_->AddInstruction(increment_);
+  }
+
+  body_env_->Push(increment_);

[Michael Starzinger, 2013/02/01 13:15:08]

The body_env_ might be a stale environment in cases where you have nested loops
or an IfBuilder nested within a loop. I think it is safer to push the increment
to the current environment (i.e. HGraphBuilder::environment) and not preserve
the original body-environment in the LoopBuilder instance.

[danno, 2013/02/02 17:56:21]

Done.

+  builder_->current_block()->Goto(header_block_);
+  header_block_->loop_information()->RegisterBackEdge(body_block_);
+  header_block_->SetJoinId(BailoutId::StubEntry());
+  builder_->set_current_block(exit_block_);
+  finished_ = true;
+}
+
+
 HGraph* HGraphBuilder::CreateGraph() {
   graph_ = new(zone()) HGraph(info_);
   if (FLAG_hydrogen_stats) HStatistics::Instance()->Initialize(info_);
   HPhase phase("H_Block building");
   set_current_block(graph()->entry_block());
   if (!BuildGraph()) return NULL;
   return graph_;
 }
 
 
 HInstruction* HGraphBuilder::AddInstruction(HInstruction* instr) {
   ASSERT(current_block() != NULL);
   current_block()->AddInstruction(instr);
   return instr;
 }
 
 
 void HGraphBuilder::AddSimulate(BailoutId id,
                                 RemovableSimulate removable) {
   ASSERT(current_block() != NULL);
   current_block()->AddSimulate(id, removable);
 }
 
 
+HBasicBlock* HGraphBuilder::CreateBasicBlock(HEnvironment* env) {
+  HBasicBlock* b = graph()->CreateBasicBlock();
+  b->SetInitialEnvironment(env);
+  return b;
+}
+
+
+HBasicBlock* HGraphBuilder::CreateLoopHeaderBlock() {
+  HBasicBlock* header = graph()->CreateBasicBlock();
+  HEnvironment* entry_env = environment()->CopyAsLoopHeader(header);
+  header->SetInitialEnvironment(entry_env);
+  header->AttachLoopInformation();
+  return header;
+}
+
+
 HInstruction* HGraphBuilder::BuildExternalArrayElementAccess(
     HValue* external_elements,
     HValue* checked_key,
     HValue* val,
     HValue* dependency,
     ElementsKind elements_kind,
     bool is_store) {
   Zone* zone = this->zone();
   if (is_store) {
     ASSERT(val != NULL);
@@ skipping 128 matching lines @@
   } else {
     length = AddInstruction(new(zone) HFixedArrayBaseLength(elements));
   }
   checked_key = AddInstruction(new(zone) HBoundsCheck(
       key, length, ALLOW_SMI_KEY, checked_index_representation));
   return BuildFastElementAccess(elements, checked_key, val, mapcheck,
                                 elements_kind, is_store);
 }
 
 
+HValue* HGraphBuilder::BuildAllocateElements(HContext* context,
+                                             ElementsKind kind,
+                                             HValue* capacity) {
+  Zone* zone = this->zone();
+
+  int elements_size = IsFastDoubleElementsKind(kind)
+      ? kDoubleSize : kPointerSize;
+  HConstant* elements_size_value =
+      new(zone) HConstant(elements_size, Representation::Integer32());
+  AddInstruction(elements_size_value);
+  HValue* mul = AddInstruction(
+      new(zone) HMul(context, capacity, elements_size_value));
+  mul->ChangeRepresentation(Representation::Integer32());
+  mul->ClearFlag(HValue::kCanOverflow);
+
+  HConstant* header_size =
+      new(zone) HConstant(FixedArray::kHeaderSize, Representation::Integer32());
+  AddInstruction(header_size);
+  HValue* total_size = AddInstruction(
+      new(zone) HAdd(context, mul, header_size));
+  total_size->ChangeRepresentation(Representation::Integer32());
+  total_size->ClearFlag(HValue::kCanOverflow);
+
+  HAllocate::Flags flags = HAllocate::CAN_ALLOCATE_IN_NEW_SPACE;
+  if (IsFastDoubleElementsKind(kind)) {
+    flags = static_cast<HAllocate::Flags>(
+        flags | HAllocate::ALLOCATE_DOUBLE_ALIGNED);
+  }
+
+  HValue* elements =
+      AddInstruction(new(zone) HAllocate(context, total_size,
+                                         HType::JSArray(), flags));
+  Isolate* isolate = graph()->isolate();
+
+  Factory* factory = isolate->factory();
+  Handle<String> map_field_name = factory->map_field_symbol();
+  Handle<Map> map = IsFastDoubleElementsKind(kind)
+      ? factory->fixed_double_array_map()
+      : factory->fixed_array_map();
+  HValue* map_constant =
+      AddInstruction(new(zone) HConstant(map, Representation::Tagged()));
+  HInstruction* store_map =
+      new(zone) HStoreNamedField(elements, map_field_name, map_constant,

[Michael Starzinger, 2013/02/01 13:15:08]

Strictly speaking this store needs to have the kChangesMaps side-effect. I think
in this case it is safe without that flag, but in general all HStoreNamedField
instructions that target the map-field should have that side-effect set. Maybe
this justifies a separate builder function for HStoreNamedField instructions
that target map-fields.

[danno, 2013/02/02 17:56:21]

Done.

+                                 true, JSObject::kMapOffset);
+  AddInstruction(store_map);
+  AddSimulate(BailoutId::StubEntry(), FIXED_SIMULATE);
+
+  Handle<String> fixed_array_length_field_name =
+      isolate->factory()->length_field_symbol();
+  HInstruction* store_length =
+      new(zone) HStoreNamedField(elements, fixed_array_length_field_name,
+                                 capacity, true, FixedArray::kLengthOffset);
+  AddInstruction(store_length);
+  AddSimulate(BailoutId::StubEntry(), FIXED_SIMULATE);
+
+  return elements;
+}
+
+
+void HGraphBuilder::BuildCopyElements(HContext* context,

[Michael Starzinger, 2013/02/01 13:15:08]

Beautifully simple, me gusta!

[danno, 2013/02/02 17:56:21]

Done.

+                                      HValue* from_elements,
+                                      ElementsKind from_elements_kind,
+                                      HValue* to_elements,
+                                      ElementsKind to_elements_kind,
+                                      HValue* length) {
+  LoopBuilder builder(this, context, LoopBuilder::kPostIncrement);
+
+  HValue* key = builder.BeginBody(graph()->GetConstant0(),
+                                  length, Token::LT);
+
+  HValue* element =
+      AddInstruction(new(zone()) HLoadKeyed(from_elements, key, NULL,
+                                            from_elements_kind,
+                                            ALLOW_RETURN_HOLE));
+
+  AddInstruction(new(zone()) HStoreKeyed(to_elements, key, element,
+                                         to_elements_kind));
+  AddSimulate(BailoutId::StubEntry(), REMOVABLE_SIMULATE);
+
+  builder.EndBody();
+}
+
+
 HOptimizedGraphBuilder::HOptimizedGraphBuilder(CompilationInfo* info,
                                                TypeFeedbackOracle* oracle)
     : HGraphBuilder(info),
       function_state_(NULL),
       initial_function_state_(this, info, oracle, NORMAL_RETURN),
       ast_context_(NULL),
       break_scope_(NULL),
       inlined_count_(0),
       globals_(10, info->zone()),
       inline_bailout_(false) {
@@ skipping 1439 matching lines @@
         TRACE_GVN_1("Updated first-time accumulated %s\n",
                     *GetGVNFlagsString(*first_time_changes));
       }
     }
     instr = next;
   }
 }
 
 
 bool HGlobalValueNumberer::AllowCodeMotion() {
-  return info()->opt_count() + 1 < FLAG_max_opt_count;
+  return info()->IsStub() || info()->opt_count() + 1 < FLAG_max_opt_count;
 }
 
 
 bool HGlobalValueNumberer::ShouldMove(HInstruction* instr,
                                       HBasicBlock* loop_header) {
   // If we've disabled code motion or we're in a block that unconditionally
   // deoptimizes, don't move any instructions.
   return AllowCodeMotion() && !instr->block()->IsDeoptimizing();
 }
 
@@ skipping 1231 matching lines @@
   int checksum = type_info->own_type_change_checksum();
   int composite_checksum = graph()->update_type_change_checksum(checksum);
   graph()->set_use_optimistic_licm(
       !type_info->matches_inlined_type_change_checksum(composite_checksum));
   type_info->set_inlined_type_change_checksum(composite_checksum);
 
   return true;
 }
 
 
+void HGraph::GlobalValueNumbering() {
+  // Perform common subexpression elimination and loop-invariant code motion.
+  if (FLAG_use_gvn) {
+    HPhase phase("H_Global value numbering", this);
+    HGlobalValueNumberer gvn(this, info());
+    bool removed_side_effects = gvn.Analyze();
+    // Trigger a second analysis pass to further eliminate duplicate values that
+    // could only be discovered by removing side-effect-generating instructions
+    // during the first pass.
+    if (FLAG_smi_only_arrays && removed_side_effects) {
+      removed_side_effects = gvn.Analyze();
+      ASSERT(!removed_side_effects);
+    }
+  }
+}
+
+
 bool HGraph::Optimize(SmartArrayPointer<char>* bailout_reason) {
   *bailout_reason = SmartArrayPointer<char>();
   OrderBlocks();
   AssignDominators();
 
 #ifdef DEBUG
   // Do a full verify after building the graph and computing dominators.
   Verify(true);
 #endif
 
@@ skipping 33 matching lines @@
 
   InitializeInferredTypes();
 
   // Must be performed before canonicalization to ensure that Canonicalize
   // will not remove semantically meaningful ToInt32 operations e.g. BIT_OR with
   // zero.
   ComputeSafeUint32Operations();
 
   Canonicalize();
 
-  // Perform common subexpression elimination and loop-invariant code motion.
-  if (FLAG_use_gvn) {
-    HPhase phase("H_Global value numbering", this);
-    HGlobalValueNumberer gvn(this, info());
-    bool removed_side_effects = gvn.Analyze();
-    // Trigger a second analysis pass to further eliminate duplicate values that
-    // could only be discovered by removing side-effect-generating instructions
-    // during the first pass.
-    if (FLAG_smi_only_arrays && removed_side_effects) {
-      removed_side_effects = gvn.Analyze();
-      ASSERT(!removed_side_effects);
-    }
-  }
+  GlobalValueNumbering();
 
   if (FLAG_use_range) {
     HRangeAnalysis rangeAnalysis(this);
     rangeAnalysis.Analyze();
   }
   ComputeMinusZeroChecks();
 
   // Eliminate redundant stack checks on backwards branches.
   HStackCheckEliminator sce(this);
   sce.Process();
@@ skipping 569 matching lines @@
 }
 
 
 void HOptimizedGraphBuilder::VisitStatements(ZoneList<Statement*>* statements) {
   for (int i = 0; i < statements->length(); i++) {
     CHECK_ALIVE(Visit(statements->at(i)));
   }
 }
 
 
-HBasicBlock* HOptimizedGraphBuilder::CreateBasicBlock(HEnvironment* env) {
-  HBasicBlock* b = graph()->CreateBasicBlock();
-  b->SetInitialEnvironment(env);
-  return b;
-}
-
-
-HBasicBlock* HOptimizedGraphBuilder::CreateLoopHeaderBlock() {
-  HBasicBlock* header = graph()->CreateBasicBlock();
-  HEnvironment* entry_env = environment()->CopyAsLoopHeader(header);
-  header->SetInitialEnvironment(entry_env);
-  header->AttachLoopInformation();
-  return header;
-}
-
-
 void HOptimizedGraphBuilder::VisitBlock(Block* stmt) {
   ASSERT(!HasStackOverflow());
   ASSERT(current_block() != NULL);
   ASSERT(current_block()->HasPredecessor());
   if (stmt->scope() != NULL) {
     return Bailout("ScopedBlock");
   }
   BreakAndContinueInfo break_info(stmt);
   { BreakAndContinueScope push(&break_info, this);
     CHECK_BAILOUT(VisitStatements(stmt->statements()));
@@ skipping 2301 matching lines @@
   int num_untransitionable_maps = 0;
   Handle<Map> untransitionable_map;
   HTransitionElementsKind* transition = NULL;
   for (int i = 0; i < maps->length(); ++i) {
     Handle<Map> map = maps->at(i);
     ASSERT(map->IsMap());
     if (!transition_target.at(i).is_null()) {
       ASSERT(Map::IsValidElementsTransition(
           map->elements_kind(),
           transition_target.at(i)->elements_kind()));
+      HValue* context = environment()->LookupContext();
       transition = new(zone()) HTransitionElementsKind(
-          object, map, transition_target.at(i));
+          context, object, map, transition_target.at(i));
       AddInstruction(transition);
     } else {
       type_todo[map->elements_kind()] = true;
       if (IsExternalArrayElementsKind(map->elements_kind())) {
         todo_external_array = true;
       }
       num_untransitionable_maps++;
       untransitionable_map = map;
     }
   }
@@ skipping 3231 matching lines @@
       ast_id_(BailoutId::None()),
       zone_(zone) {
   Initialize(0, 0, 0);
 }
 
 
 HEnvironment::HEnvironment(const HEnvironment* other, Zone* zone)
     : values_(0, zone),
       frame_type_(JS_FUNCTION),
       parameter_count_(0),
-      specials_count_(1),
+      specials_count_(0),
       local_count_(0),
       outer_(NULL),
       entry_(NULL),
       pop_count_(0),
       push_count_(0),
       ast_id_(other->ast_id()),
       zone_(zone) {
   Initialize(other);
 }
 
@@ skipping 34 matching lines @@
   closure_ = other->closure();
   values_.AddAll(other->values_, zone());
   assigned_variables_.Union(other->assigned_variables_, zone());
   frame_type_ = other->frame_type_;
   parameter_count_ = other->parameter_count_;
   local_count_ = other->local_count_;
   if (other->outer_ != NULL) outer_ = other->outer_->Copy();  // Deep copy.
   entry_ = other->entry_;
   pop_count_ = other->pop_count_;
   push_count_ = other->push_count_;
+  specials_count_ = other->specials_count_;
   ast_id_ = other->ast_id_;
 }
 
 
 void HEnvironment::AddIncomingEdge(HBasicBlock* block, HEnvironment* other) {
   ASSERT(!block->IsLoopHeader());
   ASSERT(values_.length() == other->values_.length());
 
   int length = values_.length();
   for (int i = 0; i < length; ++i) {
@@ skipping 525 matching lines @@
     }
   }
 
 #ifdef DEBUG
   if (graph_ != NULL) graph_->Verify(false);  // No full verify.
   if (allocator_ != NULL) allocator_->Verify();
 #endif
 }
 
 } }  // namespace v8::internal