Improve GVN handling of ElementTransitions.

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 1359 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 loop_kills,
+                        GVNFlagSet* preceeding_loop_depends);
   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_;
 
   // A map of block IDs to their side effects.
   ZoneList<GVNFlagSet> block_side_effects_;
 
   // A map of loop header block IDs to their loop's side effects.
   ZoneList<GVNFlagSet> loop_side_effects_;
 
   // Used when collecting side effects on paths from dominator to
   // dominated.
   SparseSet visited_on_paths_;
 };
 
 
 bool HGlobalValueNumberer::Analyze() {
+  removed_side_effects_ = false;
   ComputeBlockSideEffects();
   if (FLAG_loop_invariant_code_motion) {
     LoopInvariantCodeMotion();
   }
   HValueMap* map = new(zone()) HValueMap();
   AnalyzeBlock(graph_->entry_block(), map);
   return removed_side_effects_;
 }
 
 
 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;
     while (instr != NULL) {
       side_effects.Add(instr->ChangesFlags());
       instr = instr->next();
     }
@@ skipping 17 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 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);
       }
     }
   }
 }
 
 
 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",
            block->block_id(),
            depends_flags.ToIntegral());
   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 (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 (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 (!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;
   }
 }
 
 
 bool HGlobalValueNumberer::AllowCodeMotion() {
   return info()->shared_info()->opt_count() + 1 < Compiler::kDefaultMaxOptCount;
 }
 
@@ skipping 41 matching lines @@
   while (instr != NULL) {
     HInstruction* next = instr->next();
     GVNFlagSet flags = instr->ChangesFlags();
     if (!flags.IsEmpty()) {
       // Clear all instructions in the map that are affected by side effects.
       map->Kill(flags);
       TraceGVN("Instruction %d kills\n", instr->id());
     }
     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));
         TraceGVN("Replacing value %d (%s) with value %d (%s)\n",
                  instr->id(),
                  instr->Mnemonic(),
                  other->id(),
                  other->Mnemonic());
         if (instr->HasSideEffects()) removed_side_effects_ = true;
         instr->DeleteAndReplaceWith(other);
@@ skipping 823 matching lines @@
   graph()->Canonicalize();
 
   // Perform common subexpression elimination and loop-invariant code motion.
   if (FLAG_use_gvn) {
     HPhase phase("Global value numbering", graph());
     HGlobalValueNumberer gvn(graph(), 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) {
-      gvn.Analyze();
+    if (FLAG_smi_only_arrays) {
+      if (removed_side_effects) {
+        removed_side_effects = gvn.Analyze();
+      }
+      ASSERT(!removed_side_effects);
     }
   }
 
   if (FLAG_use_range) {
     HRangeAnalysis rangeAnalysis(graph());
     rangeAnalysis.Analyze();
   }
   graph()->ComputeMinusZeroChecks();
 
   // Eliminate redundant stack checks on backwards branches.
@@ skipping 5005 matching lines @@
     }
   }
 
 #ifdef DEBUG
   if (graph_ != NULL) graph_->Verify(false);  // No full verify.
   if (allocator_ != NULL) allocator_->Verify();
 #endif
 }
 
 } }  // namespace v8::internal