Improve GVN handling of ElementTransitions.

src/hydrogen.cc

Index: src/hydrogen.cc
diff --git a/src/hydrogen.cc b/src/hydrogen.cc
index ec5ea2cab69257d050f0b0f83507051b22dad9b4..f9a0f31d738ec95aedde4d681ed1b7801b9d81ec 100644
--- a/src/hydrogen.cc
+++ b/src/hydrogen.cc
@@ -1353,10 +1353,12 @@ class HGlobalValueNumberer BASE_EMBEDDED {
         info_(info),
         removed_side_effects_(false),
         block_side_effects_(graph->blocks()->length()),
+        block_depends_on_(graph->blocks()->length()),
         loop_side_effects_(graph->blocks()->length()),
         visited_on_paths_(graph->zone(), graph->blocks()->length()) {
     ASSERT(info->isolate()->heap()->allow_allocation(false));
     block_side_effects_.AddBlock(GVNFlagSet(), graph_->blocks()->length());
+    block_depends_on_.AddBlock(GVNFlagSet(), graph_->blocks()->length());
     loop_side_effects_.AddBlock(GVNFlagSet(), graph_->blocks()->length());
   }
   ~HGlobalValueNumberer() {
@@ -1375,7 +1377,9 @@ class HGlobalValueNumberer BASE_EMBEDDED {
   void LoopInvariantCodeMotion();
   void ProcessLoopBlock(HBasicBlock* block,
                         HBasicBlock* before_loop,
-                        GVNFlagSet loop_kills);
+                        GVNFlagSet loop_kills,
+                        GVNFlagSet conservative_first_time_depends,
+                        GVNFlagSet* accumulated_first_time_depends);
   bool AllowCodeMotion();
   bool ShouldMove(HInstruction* instr, HBasicBlock* loop_header);
 
@@ -1389,6 +1393,7 @@ class HGlobalValueNumberer BASE_EMBEDDED {
 
   // A map of block IDs to their side effects.
   ZoneList<GVNFlagSet> block_side_effects_;
+  ZoneList<GVNFlagSet> block_depends_on_;
 
   // A map of loop header block IDs to their loop's side effects.
   ZoneList<GVNFlagSet> loop_side_effects_;
@@ -1400,6 +1405,7 @@ class HGlobalValueNumberer BASE_EMBEDDED {
 
 
 bool HGlobalValueNumberer::Analyze() {
+  removed_side_effects_ = false;
   ComputeBlockSideEffects();
   if (FLAG_loop_invariant_code_motion) {
     LoopInvariantCodeMotion();
@@ -1411,17 +1417,23 @@ bool HGlobalValueNumberer::Analyze() {
 
 
 void HGlobalValueNumberer::ComputeBlockSideEffects() {
+  for (int i = 0; i < loop_side_effects_.length(); ++i) {
+    loop_side_effects_[i].RemoveAll();
+  }
   for (int i = graph_->blocks()->length() - 1; i >= 0; --i) {
     // Compute side effects for the block.
     HBasicBlock* block = graph_->blocks()->at(i);
     HInstruction* instr = block->first();
     int id = block->block_id();
     GVNFlagSet side_effects;
+    GVNFlagSet depends;
     while (instr != NULL) {
       side_effects.Add(instr->ChangesFlags());
+      depends.Add(instr->DependsOnFlags());
       instr = instr->next();
     }
     block_side_effects_[id].Add(side_effects);
+    block_depends_on_[id].Add(depends);
 
     // Loop headers are part of their loop.
     if (block->IsLoopHeader()) {
@@ -1448,18 +1460,41 @@ void HGlobalValueNumberer::LoopInvariantCodeMotion() {
                block->block_id(),
                side_effects.ToIntegral());
 
+      GVNFlagSet accumulated_first_time_depends;
       HBasicBlock* last = block->loop_information()->GetLastBackEdge();
+      int outstanding_sucsessors = 0;
       for (int j = block->block_id(); j <= last->block_id(); ++j) {
-        ProcessLoopBlock(graph_->blocks()->at(j), block, side_effects);
+        GVNFlagSet conservative_first_time_depends =
+            accumulated_first_time_depends;
+        HBasicBlock* analyze_block = graph_->blocks()->at(j);
+        if (analyze_block != block) {
+          outstanding_sucsessors -= analyze_block->predecessors()->length();
+        }
+        if (outstanding_sucsessors != 0) {
+          // If more successors than predecessors have been seen in the loop up
+          // to now, it's not possible to guarantee that the current block
+          // dominates all of the blocks with higher IDs. In this case, assume
+          // conservatively that those paths through loop that don't go through
+          // the current block contain all of the loop's dependencies.

[fschneider, 2012/02/01 10:54:14]

I don't think this works in general: e.g. in a simple while-loop:

P->H
H->A
H->X
A->B
A->C
B->D
C->D
D-->H

If I understand the code correctly, the outstanding count would be > 0 for all
blocks A, B, C, D.

[danno, 2012/02/01 16:53:15]

Done.

+          conservative_first_time_depends.Add(
+              block_depends_on_[analyze_block->block_id()]);
+        }
+        ProcessLoopBlock(analyze_block, block, side_effects,
+                         conservative_first_time_depends,
+                         &accumulated_first_time_depends);
+        outstanding_sucsessors += analyze_block->end()->SuccessorCount();
       }
     }
   }
 }
 
 
-void HGlobalValueNumberer::ProcessLoopBlock(HBasicBlock* block,
-                                            HBasicBlock* loop_header,
-                                            GVNFlagSet loop_kills) {
+void HGlobalValueNumberer::ProcessLoopBlock(
+    HBasicBlock* block,
+    HBasicBlock* loop_header,
+    GVNFlagSet loop_kills,
+    GVNFlagSet conservative_first_time_depends,
+    GVNFlagSet* accumulated_first_time_depends) {
   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",
@@ -1468,25 +1503,57 @@ void HGlobalValueNumberer::ProcessLoopBlock(HBasicBlock* block,
   HInstruction* instr = block->first();
   while (instr != NULL) {
     HInstruction* next = instr->next();
-    if (instr->CheckFlag(HValue::kUseGVN) &&
-        !instr->gvn_flags().ContainsAnyOf(depends_flags)) {
-      TraceGVN("Checking instruction %d (%s)\n",
+    bool hoisted = false;
+    if (instr->CheckFlag(HValue::kUseGVN)) {
+      TraceGVN("Checking instruction %d (%s) instruction GVN flags 0x%X, "
+               "conservative depends 0x%X, loop kills 0x%X\n",
                instr->id(),
-               instr->Mnemonic());
-      bool inputs_loop_invariant = true;
-      for (int i = 0; i < instr->OperandCount(); ++i) {
-        if (instr->OperandAt(i)->IsDefinedAfter(pre_header)) {
-          inputs_loop_invariant = false;
-        }
+               instr->Mnemonic(),
+               instr->gvn_flags().ToIntegral(),
+               (conservative_first_time_depends).ToIntegral(),
+               depends_flags.ToIntegral());
+      bool can_hoist = !instr->gvn_flags().ContainsAnyOf(depends_flags);
+      if (!can_hoist &&
+          !instr->HasObservableSideEffects() &&
+          instr->HasOneTimeSideEffects()) {
+        // 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, conservative depends 0x%X\n",
+                 instr->id(),
+                 instr->Mnemonic(),
+                 converted_changes.ToIntegral(),
+                 (conservative_first_time_depends).ToIntegral());
+        can_hoist =
+            !conservative_first_time_depends.ContainsAnyOf(converted_changes);
       }
 
-      if (inputs_loop_invariant && ShouldMove(instr, loop_header)) {
-        TraceGVN("Found loop invariant instruction %d\n", instr->id());
-        // Move the instruction out of the loop.
-        instr->Unlink();
-        instr->InsertBefore(pre_header->end());
+      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("Found 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) {
+      // Hoisting an instruction to the preheader causes its DependsOn flags to
+      // not prevent hosting OneTimeSideEffecct instructions.
+      accumulated_first_time_depends->Add(instr->DependsOnFlags());
+    }
     instr = next;
   }
 }
@@ -1547,6 +1614,7 @@ void HGlobalValueNumberer::AnalyzeBlock(HBasicBlock* block, HValueMap* map) {
     }
     if (instr->CheckFlag(HValue::kUseGVN)) {
       ASSERT(!instr->HasObservableSideEffects());
+      ASSERT(!instr->HasSideEffects() || instr->HasOneTimeSideEffects());
       HValue* other = map->Lookup(instr);
       if (other != NULL) {
         ASSERT(instr->Equals(other) && other->Equals(instr));
@@ -2394,7 +2462,8 @@ HGraph* HGraphBuilder::CreateGraph() {
     // could only be discovered by removing side-effect-generating instructions
     // during the first pass.
     if (FLAG_smi_only_arrays && removed_side_effects) {
-      gvn.Analyze();
+      removed_side_effects = gvn.Analyze();
+      ASSERT(!removed_side_effects);
     }
   }