Improve GVN handling of ElementTransitions.

src/hydrogen.cc

Index: src/hydrogen.cc
diff --git a/src/hydrogen.cc b/src/hydrogen.cc
index 4cfd45f53fd785ce29f841d39a4e4abbb7753e18..0330da96f84af0f77f40b3e6c5b6d1a6d68ee326 100644
--- a/src/hydrogen.cc
+++ b/src/hydrogen.cc
@@ -1377,7 +1377,8 @@ class HGlobalValueNumberer BASE_EMBEDDED {
   void LoopInvariantCodeMotion();
   void ProcessLoopBlock(HBasicBlock* block,
                         HBasicBlock* before_loop,
-                        GVNFlagSet loop_kills);
+                        GVNFlagSet loop_kills,
+                        GVNFlagSet* preceeding_loop_depends);
   bool AllowCodeMotion();
   bool ShouldMove(HInstruction* instr, HBasicBlock* loop_header);
 
@@ -1402,6 +1403,7 @@ class HGlobalValueNumberer BASE_EMBEDDED {
 
 
 bool HGlobalValueNumberer::Analyze() {
+  removed_side_effects_ = false;
   ComputeBlockSideEffects();
   if (FLAG_loop_invariant_code_motion) {
     LoopInvariantCodeMotion();
@@ -1413,6 +1415,9 @@ 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);
@@ -1450,9 +1455,11 @@ void HGlobalValueNumberer::LoopInvariantCodeMotion() {
                block->block_id(),
                side_effects.ToIntegral());
 
+      GVNFlagSet preceeding_loop_depends;
       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);
+        ProcessLoopBlock(graph_->blocks()->at(j), block, side_effects,
+                         &preceeding_loop_depends);
       }
     }
   }
@@ -1461,7 +1468,8 @@ void HGlobalValueNumberer::LoopInvariantCodeMotion() {
 
 void HGlobalValueNumberer::ProcessLoopBlock(HBasicBlock* block,
                                             HBasicBlock* loop_header,
-                                            GVNFlagSet loop_kills) {
+                                            GVNFlagSet loop_kills,
+                                            GVNFlagSet* preceeding_loop_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",
@@ -1470,25 +1478,48 @@ 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) instr 0x%X, block 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(),
+               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.

[fschneider, 2012/01/25 00:04:57]

In general a path from the header to the current instruction may involve all
blocks from the loop that are not dominated by the current instruction.
  preceeding_loop_depends accumulates the dependencies of the blocks with an id
less than the current block, and therefore can be missing the ones of blocks
with higher ids that are not dominated by the current instruction.

[danno, 2012/01/31 15:38:26]

I'm not sure that's true. We're careful to order the blocks in reverse post
order, which means that ignoring loops, if there is a path a -> b -> c, then
a.id() < b.id() < c.id(). It's overly conservative, but correct. I talked to
Kevin, and he also agreed that this reasoning is sound, and also pointed out
that liveness analysis relies on this same principle.
On 2012/01/25 00:04:57, fschneider wrote:

+        can_hoist =

[fschneider, 2012/01/25 00:04:57]

Please add a unit test that covers the two cases that can occur here: hoisting
and not hoisting the instruction.

[danno, 2012/01/31 15:38:26]

Done.

+            !preceeding_loop_depends->ContainsAnyOf(
+                HValue::ConvertChangesToDependsFlags(instr->ChangesFlags()));
       }
 
-      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.
+      preceeding_loop_depends->Add(instr->DependsOnFlags());
+    }
     instr = next;
   }
 }
@@ -1549,6 +1580,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));
@@ -2392,8 +2424,11 @@ HGraph* HGraphBuilder::CreateGraph() {
     // 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) {
-      gvn.Analyze();
+    if (FLAG_smi_only_arrays) {
+      if (removed_side_effects) {
+        removed_side_effects = gvn.Analyze();
+      }
+      ASSERT(!removed_side_effects);
     }
   }