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 1335 matching lines @@
 };
 
 
 class HGlobalValueNumberer BASE_EMBEDDED {
  public:
   explicit HGlobalValueNumberer(HGraph* graph, CompilationInfo* info)
       : graph_(graph),
         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() {
     ASSERT(!info_->isolate()->heap()->allow_allocation(true));
   }
 
   // Returns true if values with side effects are removed.
   bool Analyze();
 
  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 conservative_first_time_depends,
+                        GVNFlagSet* accumulated_first_time_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_;
+  ZoneList<GVNFlagSet> block_depends_on_;
 
   // 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;
+    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()) {
       loop_side_effects_[id].Add(side_effects);
     }
 
     // Propagate loop side effects upwards.
     if (block->HasParentLoopHeader()) {
       int header_id = block->parent_loop_header()->block_id();
       loop_side_effects_[header_id].Add(block->IsLoopHeader()
                                         ? loop_side_effects_[id]
                                         : side_effects);
     }
   }
 }
 
 
 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;
       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",
            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) 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 (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.
+      accumulated_first_time_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 827 matching lines @@
 
   // 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();
+      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 5047 matching lines @@
     }
   }
 
 #ifdef DEBUG
   if (graph_ != NULL) graph_->Verify(false);  // No full verify.
   if (allocator_ != NULL) allocator_->Verify();
 #endif
 }
 
 } }  // namespace v8::internal