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 52 matching lines @@
       predecessors_(2),
       dominator_(NULL),
       dominated_blocks_(4),
       last_environment_(NULL),
       argument_count_(-1),
       first_instruction_index_(-1),
       last_instruction_index_(-1),
       deleted_phis_(4),
       parent_loop_header_(NULL),
       is_inline_return_target_(false),
-      is_deoptimizing_(false) { }
+      is_deoptimizing_(false),
+      dominates_loop_successors_(false) { }
 
 
 void HBasicBlock::AttachLoopInformation() {
   ASSERT(!IsLoopHeader());
   loop_information_ = new(zone()) HLoopInformation(this);
 }
 
 
 void HBasicBlock::DetachLoopInformation() {
   ASSERT(IsLoopHeader());
@@ skipping 224 matching lines @@
     if (dominator_ != first) {
       ASSERT(dominator_->dominated_blocks_.Contains(this));
       dominator_->dominated_blocks_.RemoveElement(this);
       dominator_ = first;
       first->AddDominatedBlock(this);
     }
   }
 }
 
 
+void HBasicBlock::AssignLoopSuccessorDominators() {
+  // Mark blocks that dominate all subsequent reachable blocks inside their
+  // loop. Exploit the fact that blocks are sorted in reverse post order. When
+  // the loop is visited in increasing block id order, if the number of
+  // non-loop-exiting successor edges at the dominator_candidate block doesn't
+  // exceed the number of previously encountered predecessor edges, there is no
+  // path from the loop header to any block with higher id that doesn't go
+  // through the dominator_candidate block. In this case, the
+  // dominator_candidate block is guaranteed to dominate all blocks reachable
+  // from it with higher ids.
+  HBasicBlock* last = loop_information()->GetLastBackEdge();
+  int outstanding_sucsessors = 1;  // one edge from the pre-header

[fschneider, 2012/02/02 14:59:50]

s/sucsessors/successors/g

[danno, 2012/02/06 16:54:57]

Done.

+  // Header always dominates everything.
+  MarkAsLoopSuccessorDominator();
+  for (int j = block_id(); j <= last->block_id(); ++j) {

[fschneider, 2012/02/02 14:59:50]

Maybe this be simplified: The header is always marked, so there is no need to
include it in the iteration:

Would it work to initialize outstanding_successors to 0 and  start at block_id()
+ 1 instead?

Then you could also save detecting back edges below.

[danno, 2012/02/06 16:54:57]

You have to iterate over every block's successors, even the header, so the
header must be included in the iteration over the loop.
On 2012/02/02 14:59:50, fschneider wrote:

+    HBasicBlock* dominator_candidate = graph_->blocks()->at(j);
+    const ZoneList<HBasicBlock*>* predecessor_list =
+        dominator_candidate->predecessors();
+    int predecessor_count = predecessor_list->length();
+    for (int i = 0; i < predecessor_count; ++i) {

[fschneider, 2012/02/02 14:59:50]

Maybe it would make sense to introduce a HPredecessorIterator, similar to
HSuccessorIterator for more concise code.

[danno, 2012/02/06 16:54:57]

Done.

+      HBasicBlock* predecessor = predecessor_list->at(i);
+      // Don't count back edges.
+      if (predecessor->block_id() < dominator_candidate->block_id()) {
+        outstanding_sucsessors--;
+      }
+    }
+
+    // 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. Also be careful to record
+    // dominator information about the current loop that's being processed,
+    // and not nested loops, which will be processed when
+    // AssignLoopSuccessorDominators gets called on their header.
+    ASSERT(outstanding_sucsessors >= 0);
+    HBasicBlock* parent_loop_header = dominator_candidate->parent_loop_header();
+    if (outstanding_sucsessors == 0 &&
+        (parent_loop_header == this && !dominator_candidate->IsLoopHeader())) {
+      MarkAsLoopSuccessorDominator();

[fschneider, 2012/02/02 14:59:50]

I guess this should be:

candidate_dominator->MarkAsLoopSuccessorDominator();

otherwise no other block will be marked.

[danno, 2012/02/06 16:54:57]

Done.

+    }
+    HControlInstruction* end_instr = dominator_candidate->end();
+    int successor_count = end_instr->SuccessorCount();
+    for (int current = 0; current < successor_count; ++current) {

[fschneider, 2012/02/02 14:59:50]

You can use HSuccessorIterator here.

[danno, 2012/02/06 16:54:57]

Done.

+      HBasicBlock* successor = end_instr->SuccessorAt(current);
+      // Only count successors that remain inside the loop and don't loop back
+      // to a loop header.
+      if (successor->block_id() > dominator_candidate->block_id() &&
+          successor->block_id() <= last->block_id()) {
+        // Backwards edges must land on loop headers.
+        ASSERT(successor->block_id() > dominator_candidate->block_id() ||
+               successor->IsLoopHeader());
+        outstanding_sucsessors++;
+      }
+    }
+  }
+}
+
+
 int HBasicBlock::PredecessorIndexOf(HBasicBlock* predecessor) const {
   for (int i = 0; i < predecessors_.length(); ++i) {
     if (predecessors_[i] == predecessor) return i;
   }
   UNREACHABLE();
   return -1;
 }
 
 
 #ifdef DEBUG
@@ skipping 419 matching lines @@
   ASSERT(block->end()->SecondSuccessor() == NULL ||
          order->Contains(block->end()->SecondSuccessor()) ||
          block->end()->SecondSuccessor()->IsLoopHeader());
   order->Add(block);
 }
 
 
 void HGraph::AssignDominators() {
   HPhase phase("Assign dominators", this);
   for (int i = 0; i < blocks_.length(); ++i) {
-    if (blocks_[i]->IsLoopHeader()) {
+    HBasicBlock* block = blocks_[i];
+    if (block->IsLoopHeader()) {
       // Only the first predecessor of a loop header is from outside the loop.
       // All others are back edges, and thus cannot dominate the loop header.
-      blocks_[i]->AssignCommonDominator(blocks_[i]->predecessors()->first());
+      block->AssignCommonDominator(block->predecessors()->first());
+      block->AssignLoopSuccessorDominators();
     } else {
       for (int j = blocks_[i]->predecessors()->length() - 1; j >= 0; --j) {
         blocks_[i]->AssignCommonDominator(blocks_[i]->predecessors()->at(j));
       }
     }
   }
 }
 
 // Mark all blocks that are dominated by an unconditional soft deoptimize to
 // prevent code motion across those blocks.
@@ skipping 597 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* 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_;
 
   // 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) {

[fschneider, 2012/02/02 14:59:50]

Comment on why resetting the loop side effect sets.

[danno, 2012/02/06 16:54:57]

Done.

+    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 accumulated_first_time_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,
+                         &accumulated_first_time_depends);
       }
     }
   }
 }
 
 
-void HGlobalValueNumberer::ProcessLoopBlock(HBasicBlock* block,
-                                            HBasicBlock* loop_header,
-                                            GVNFlagSet loop_kills) {
+void HGlobalValueNumberer::ProcessLoopBlock(
+    HBasicBlock* block,
+    HBasicBlock* loop_header,
+    GVNFlagSet loop_kills,
+    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, "
+               "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(),
+               depends_flags.ToIntegral());
+      bool can_hoist = !instr->gvn_flags().ContainsAnyOf(depends_flags);
+      if (!can_hoist &&
+          !instr->HasObservableSideEffects() &&

[fschneider, 2012/02/02 14:59:50]

maybe just say: 

if (!can_hoist && instr->IsTransitionElementsKind())

I think this should be generalized as necessary in the future.

[danno, 2012/02/06 16:54:57]

Done.

+          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, accumulated depends 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.
+        bool not_in_nested_loop = block == loop_header ||
+            (block->parent_loop_header() ==
+             loop_header && !block->IsLoopHeader());
+        can_hoist = !not_in_nested_loop &&

[fschneider, 2012/02/02 14:59:50]

The double negation !not... should be avoided for readability.

[danno, 2012/02/06 16:54:57]

Done.

+            block->IsLoopSuccessorDominator() &&
+            !accumulated_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("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 (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 or
+      // SideEffects flags to not prevent hosting OneTimeSideEffecct

[fschneider, 2012/02/02 14:59:50]

I find the double negation in the comment confusing. How about the following:

If an instruction is not hoisted, we have to account for its side effects when
hoisting later HTransitionElementsKind instructions.

[danno, 2012/02/06 16:54:57]

Done.

+      // instructions.
+      accumulated_first_time_depends->Add(instr->DependsOnFlags());
+      GVNFlagSet converted_changes =
+          HValue::ConvertChangesToDependsFlags(instr->SideEffectFlags());
+      accumulated_first_time_depends->Add(converted_changes);
     }
     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