Relax TransitionElementsKind DependsOn/Changes dependencies.

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 1413 matching lines @@
  private:
   GVNFlagSet CollectSideEffectsOnPathsToDominatedBlock(
       HBasicBlock* dominator,
       HBasicBlock* dominated);
   void AnalyzeBlock(HBasicBlock* block, HValueMap* map);
   void ComputeBlockSideEffects();
   void LoopInvariantCodeMotion();
   void ProcessLoopBlock(HBasicBlock* block,
                         HBasicBlock* before_loop,
                         GVNFlagSet loop_kills,
-                        GVNFlagSet* accumulated_first_time_depends);
+                        GVNFlagSet* accumulated_first_time_depends,
+                        GVNFlagSet* accumulated_first_time_changes);
   bool AllowCodeMotion();
   bool ShouldMove(HInstruction* instr, HBasicBlock* loop_header);
 
   HGraph* graph() { return graph_; }
   CompilationInfo* info() { return info_; }
   Zone* zone() { return graph_->zone(); }
 
   HGraph* graph_;
   CompilationInfo* info_;
   bool removed_side_effects_;
@@ skipping 60 matching lines @@
 void HGlobalValueNumberer::LoopInvariantCodeMotion() {
   for (int i = graph_->blocks()->length() - 1; i >= 0; --i) {
     HBasicBlock* block = graph_->blocks()->at(i);
     if (block->IsLoopHeader()) {
       GVNFlagSet side_effects = loop_side_effects_[block->block_id()];
       TraceGVN("Try loop invariant motion for block B%d effects=0x%x\n",
                block->block_id(),
                side_effects.ToIntegral());
 
       GVNFlagSet accumulated_first_time_depends;
+      GVNFlagSet accumulated_first_time_changes;
       HBasicBlock* last = block->loop_information()->GetLastBackEdge();
       for (int j = block->block_id(); j <= last->block_id(); ++j) {
         ProcessLoopBlock(graph_->blocks()->at(j), block, side_effects,
-                         &accumulated_first_time_depends);
+                         &accumulated_first_time_depends,
+                         &accumulated_first_time_changes);
       }
     }
   }
 }
 
 
 void HGlobalValueNumberer::ProcessLoopBlock(
     HBasicBlock* block,
     HBasicBlock* loop_header,
     GVNFlagSet loop_kills,
-    GVNFlagSet* accumulated_first_time_depends) {
+    GVNFlagSet* first_time_depends,
+    GVNFlagSet* first_time_changes) {
   HBasicBlock* pre_header = loop_header->predecessors()->at(0);
   GVNFlagSet depends_flags = HValue::ConvertChangesToDependsFlags(loop_kills);
   TraceGVN("Loop invariant motion for B%d depends_flags=0x%x\n",
            block->block_id(),
            depends_flags.ToIntegral());
   HInstruction* instr = block->first();
   while (instr != NULL) {
     HInstruction* next = instr->next();
     bool hoisted = false;
     if (instr->CheckFlag(HValue::kUseGVN)) {
       TraceGVN("Checking instruction %d (%s) instruction GVN flags 0x%X, "
                "loop kills 0x%X\n",
                instr->id(),
                instr->Mnemonic(),
                instr->gvn_flags().ToIntegral(),
                depends_flags.ToIntegral());
       bool can_hoist = !instr->gvn_flags().ContainsAnyOf(depends_flags);
-      if (!can_hoist && instr->IsTransitionElementsKind()) {
-        // It's only possible to hoist one time side effects if there are no
-        // dependencies on their changes from the loop header to the current
-        // instruction.
-        GVNFlagSet converted_changes =
-            HValue::ConvertChangesToDependsFlags(instr->ChangesFlags());
-        TraceGVN("Checking dependencies on one-time instruction %d (%s) "
-                 "converted changes 0x%X, accumulated depends 0x%X\n",
+      if (instr->IsTransitionElementsKind()) {
+        // It's possible to hoist transitions out of a loop as long as the
+        // hoisting wouldn't move the transition past a DependsOn of one of it's
+        // changes or any instructions that might change an objects map or
+        // elements contents.
+        GVNFlagSet changes = instr->ChangesFlags();
+        GVNFlagSet hoist_depends_blockers =
+            HValue::ConvertChangesToDependsFlags(changes);
+        // In addition to not hoisting transitions above other instructions that
+        // change dependencies that the transition changes, it must not be
+        // hoisted above map changes and stores to an elements backing store
+        // that the transition might change.
+        GVNFlagSet hoist_change_blockers = changes;
+        hoist_change_blockers.Add(kChangesMaps);
+        HTransitionElementsKind* trans = HTransitionElementsKind::cast(instr);
+        if (trans->original_map()->has_fast_double_elements()) {
+          hoist_change_blockers.Add(kChangesDoubleArrayElements);
+        }
+        if (trans->transitioned_map()->has_fast_double_elements()) {
+          hoist_change_blockers.Add(kChangesArrayElements);
+        }
+        TraceGVN("Checking dependencies on HTransitionElementsKind %d (%s) "
+                 "hoist depends blockers 0x%X, hoist change blockers 0x%X, "
+                 "accumulated depends 0x%X, accumulated changes 0x%X\n",
                  instr->id(),
                  instr->Mnemonic(),
-                 converted_changes.ToIntegral(),
-                 accumulated_first_time_depends->ToIntegral());
-        // It's possible to hoist one-time side effects from the current loop
-        // loop only if they dominate all of the successor blocks in the same
-        // loop and there are not any instructions that have Changes/DependsOn
-        // that intervene between it and the beginning of the loop header.
+                 hoist_depends_blockers.ToIntegral(),
+                 hoist_change_blockers.ToIntegral(),
+                 first_time_depends->ToIntegral(),
+                 first_time_changes->ToIntegral());
+        // It's possible to hoist transition from the current loop loop only if
+        // they dominate all of the successor blocks in the same loop and there
+        // are not any instructions that have Changes/DependsOn that intervene
+        // between it and the beginning of the loop header.
         bool in_nested_loop = block != loop_header &&
             ((block->parent_loop_header() != loop_header) ||
              block->IsLoopHeader());
         can_hoist = !in_nested_loop &&
             block->IsLoopSuccessorDominator() &&
-            !accumulated_first_time_depends->ContainsAnyOf(converted_changes);
+            !first_time_depends->ContainsAnyOf(hoist_depends_blockers) &&
+            !first_time_changes->ContainsAnyOf(hoist_change_blockers);
       }
 
       if (can_hoist) {
         bool inputs_loop_invariant = true;
         for (int i = 0; i < instr->OperandCount(); ++i) {
           if (instr->OperandAt(i)->IsDefinedAfter(pre_header)) {
             inputs_loop_invariant = false;
           }
         }
 
         if (inputs_loop_invariant && ShouldMove(instr, loop_header)) {
           TraceGVN("Hoisting loop invariant instruction %d\n", instr->id());
           // Move the instruction out of the loop.
           instr->Unlink();
           instr->InsertBefore(pre_header->end());
           if (instr->HasSideEffects()) removed_side_effects_ = true;
           hoisted = true;
         }
       }
     }
     if (!hoisted) {
       // If an instruction is not hoisted, we have to account for its side
       // effects when hoisting later HTransitionElementsKind instructions.
-      accumulated_first_time_depends->Add(instr->DependsOnFlags());
-      GVNFlagSet converted_changes =
-          HValue::ConvertChangesToDependsFlags(instr->SideEffectFlags());
-      accumulated_first_time_depends->Add(converted_changes);
+      first_time_depends->Add(instr->DependsOnFlags());
+      first_time_changes->Add(instr->ChangesFlags());
     }
     instr = next;
   }
 }
 
 
 bool HGlobalValueNumberer::AllowCodeMotion() {
   return info()->shared_info()->opt_count() + 1 < Compiler::kDefaultMaxOptCount;
 }
 
@@ skipping 2841 matching lines @@
         map->FindTransitionedMap(&possible_transitioned_maps);
     transition_target.Add(transitioned_map);
   }
 
   int num_untransitionable_maps = 0;
   Handle<Map> untransitionable_map;
   for (int i = 0; i < maps->length(); ++i) {
     Handle<Map> map = maps->at(i);
     ASSERT(map->IsMap());
     if (!transition_target.at(i).is_null()) {
-      object = AddInstruction(new(zone()) HTransitionElementsKind(
+      AddInstruction(new(zone()) HTransitionElementsKind(
           object, map, transition_target.at(i)));
     } else {
       type_todo[map->elements_kind()] = true;
       if (map->elements_kind() >= FIRST_EXTERNAL_ARRAY_ELEMENTS_KIND) {
         todo_external_array = true;
       }
       num_untransitionable_maps++;
       untransitionable_map = map;
     }
   }
@@ skipping 3239 matching lines @@
     }
   }
 
 #ifdef DEBUG
   if (graph_ != NULL) graph_->Verify(false);  // No full verify.
   if (allocator_ != NULL) allocator_->Verify();
 #endif
 }
 
 } }  // namespace v8::internal