Remove dead phis as soon as they are discovered.

runtime/vm/flow_graph_allocator.cc

 // Copyright (c) 2013, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 #include "vm/flow_graph_allocator.h"
 
 #include "vm/bit_vector.h"
 #include "vm/intermediate_language.h"
 #include "vm/il_printer.h"
 #include "vm/flow_graph.h"
@@ skipping 73 matching lines @@
   }
   blocked_cpu_registers_[SPREG] = true;
   blocked_cpu_registers_[FPREG] = true;
 
   // FpuTMP is used as scratch by optimized code and parallel move resolver.
   blocked_fpu_registers_[FpuTMP] = true;
 }
 
 
 // Remove environments from the instructions which can't deoptimize.
-// Replace dead phis uses with null values in environments.
-void FlowGraphAllocator::EliminateEnvironmentUses() {
-  ConstantInstr* constant_null =
-      postorder_.Last()->AsGraphEntry()->constant_null();
+void FlowGraphAllocator::EliminateEnvironments() {
   for (intptr_t i = 0; i < block_order_.length(); ++i) {
     BlockEntryInstr* block = block_order_[i];
-    if (block->IsJoinEntry()) block->AsJoinEntry()->RemoveDeadPhis();
     for (ForwardInstructionIterator it(block); !it.Done(); it.Advance()) {
       Instruction* current = it.Current();
-      if (current->CanDeoptimize()) {
-        ASSERT(current->env() != NULL);
-        for (Environment::DeepIterator it(current->env());
-             !it.Done();
-             it.Advance()) {
-          Value* use = it.CurrentValue();
-          Definition* def = use->definition();
-          PushArgumentInstr* push_argument = def->AsPushArgument();
-          if ((push_argument != NULL) && push_argument->WasEliminated()) {
-            it.SetCurrentValue(push_argument->value()->Copy());

[Vyacheslav Egorov (Google), 2013/02/27 21:53:02]

What happened to this special PushArgument handling? Are we relying on the fact
that push argument removal does this substitution? Can we assert that
environment contains no PushArguments.

[Kevin Millikin (Google), 2013/02/28 08:12:02]

It was already obsolete after a previous change, where they were removed eagerly
from environments.

We can add an assert, but it seemed to me that it was just asserting a negative
property of the old implementation.  

Presumably, any removed value turning up in an environment would end up with an
unallocated value and an assertion failure later.  So we can actually assert a
stronger property here if we want, or rely on the later assert.

-            continue;
-          }
-
-          PhiInstr* phi = def->AsPhi();
-          if ((phi != NULL) && !phi->is_alive()) {
-            it.SetCurrentValue(new Value(constant_null));
-            continue;
-          }
-        }
-      } else {
-        current->RemoveEnvironment();
-      }
+      if (!current->CanDeoptimize()) current->RemoveEnvironment();
     }
   }
 }
 
 
 void FlowGraphAllocator::ComputeInitialSets() {
   const intptr_t block_count = postorder_.length();
   for (intptr_t i = 0; i < block_count; i++) {
     BlockEntryInstr* block = postorder_[i];
 
@@ skipping 35 matching lines @@
               !value->BindsToConstant()) {
             live_in->Add(value->definition()->ssa_temp_index());
           }
         }
       }
     }
 
     // Handle phis.
     if (block->IsJoinEntry()) {
       JoinEntryInstr* join = block->AsJoinEntry();
-      if (join->phis() != NULL) {
-        for (intptr_t j = 0; j < join->phis()->length(); j++) {
-          PhiInstr* phi = (*join->phis())[j];
-          if (phi == NULL) continue;
+      for (PhiIterator it(join); !it.Done(); it.Advance()) {
+        PhiInstr* phi = it.Current();
+        ASSERT(phi != NULL);
+        kill->Add(phi->ssa_temp_index());
+        live_in->Remove(phi->ssa_temp_index());
 
-          kill->Add(phi->ssa_temp_index());
-          live_in->Remove(phi->ssa_temp_index());
+        // If a phi input is not defined by the corresponding predecessor it
+        // must be marked live-in for that predecessor.
+        for (intptr_t k = 0; k < phi->InputCount(); k++) {
+          Value* val = phi->InputAt(k);
+          if (val->BindsToConstant()) continue;
 
-          // If phi-operand is not defined by a predecessor it must be marked
-          // live-in for a predecessor.
-          for (intptr_t k = 0; k < phi->InputCount(); k++) {
-            Value* val = phi->InputAt(k);
-            if (val->BindsToConstant()) continue;
-
-            BlockEntryInstr* pred = block->PredecessorAt(k);
-            const intptr_t use = val->definition()->ssa_temp_index();
-            if (!kill_[pred->postorder_number()]->Contains(use)) {
-              live_in_[pred->postorder_number()]->Add(use);
-            }
+          BlockEntryInstr* pred = block->PredecessorAt(k);
+          const intptr_t use = val->definition()->ssa_temp_index();
+          if (!kill_[pred->postorder_number()]->Contains(use)) {
+            live_in_[pred->postorder_number()]->Add(use);
           }
         }
       }
     }
   }
 
   // Process initial definitions, ie, constants and incoming parameters.
   GraphEntryInstr* graph_entry = flow_graph_.graph_entry();
   for (intptr_t i = 0; i < graph_entry->initial_definitions()->length(); i++) {
     intptr_t vreg = (*graph_entry->initial_definitions())[i]->ssa_temp_index();
@@ skipping 480 matching lines @@
   const intptr_t pos = goto_instr->lifetime_position();
 
   JoinEntryInstr* join = goto_instr->successor();
   ASSERT(join != NULL);
 
   // Search for the index of the current block in the predecessors of
   // the join.
   const intptr_t pred_idx = join->IndexOfPredecessor(block);
 
   // Record the corresponding phi input use for each phi.
-  ZoneGrowableArray<PhiInstr*>* phis = join->phis();
   intptr_t move_idx = 0;
-  for (intptr_t phi_idx = 0; phi_idx < phis->length(); phi_idx++) {
-    PhiInstr* phi = (*phis)[phi_idx];
-    if (phi == NULL) continue;
-
+  for (PhiIterator it(join); !it.Done(); it.Advance()) {
+    PhiInstr* phi = it.Current();
     Value* val = phi->InputAt(pred_idx);
     MoveOperands* move = parallel_move->MoveOperandsAt(move_idx);
 
     ConstantInstr* constant = val->definition()->AsConstant();
     if (constant != NULL) {
       move->set_src(Location::Constant(constant->value()));
       move_idx++;
       continue;
     }
 
@@ skipping 22 matching lines @@
 
 void FlowGraphAllocator::ConnectIncomingPhiMoves(BlockEntryInstr* block) {
   // If this block is a join we need to add destinations of phi
   // resolution moves to phi's live range so that register allocator will
   // fill them with moves.
   JoinEntryInstr* join = block->AsJoinEntry();
   if (join == NULL) return;
 
   // All uses are recorded at the start position in the block.
   const intptr_t pos = join->start_pos();
-
-  ZoneGrowableArray<PhiInstr*>* phis = join->phis();
-  if (phis == NULL) return;
-
   const bool is_loop_header = BlockInfoAt(join->start_pos())->is_loop_header();
-
   intptr_t move_idx = 0;
-  for (intptr_t phi_idx = 0; phi_idx < phis->length(); phi_idx++) {
-    PhiInstr* phi = (*phis)[phi_idx];
-    if (phi == NULL) continue;
-
+  for (PhiIterator it(join); !it.Done(); it.Advance()) {
+    PhiInstr* phi = it.Current();
+    ASSERT(phi != NULL);
     const intptr_t vreg = phi->ssa_temp_index();
-    ASSERT(vreg != -1);
+    ASSERT(vreg >= 0);
 
     // Expected shape of live range:
     //
     //                 B
     //      phi        [--------
     //
     LiveRange* range = GetLiveRange(vreg);
     range->DefineAt(pos);  // Shorten live range.
 
     if (is_loop_header) range->mark_loop_phi();
@@ skipping 406 matching lines @@
   }
 
   // Create parallel moves in join predecessors.  This must be done after
   // all instructions are numbered.
   for (intptr_t i = block_count - 1; i >= 0; i--) {
     BlockEntryInstr* block = postorder_[i];
 
     // For join entry predecessors create phi resolution moves if
     // necessary. They will be populated by the register allocator.
     JoinEntryInstr* join = block->AsJoinEntry();
-    if ((join != NULL) && (join->phi_count() > 0)) {
-      const intptr_t phi_count = join->phi_count();
+    if ((join != NULL) &&
+        (join->phis() != NULL) &&
+        !join->phis()->is_empty()) {
+      const intptr_t phi_count = join->phis()->length();
       for (intptr_t i = 0; i < block->PredecessorCount(); i++) {
         // Insert the move between the last two instructions of the
         // predecessor block (all such blocks have at least two instructions:
         // the block entry and goto instructions.)
         Instruction* last = block->PredecessorAt(i)->last_instruction();
         ASSERT(last->IsGoto());
 
         ParallelMoveInstr* move = last->AsGoto()->GetParallelMove();
 
         // Populate the ParallelMove with empty moves.
@@ skipping 551 matching lines @@
       (free_until >= loop_header->last_block()->end_pos()) &&
       loop_header->backedge_interference()->Contains(unallocated->vreg())) {
     ASSERT(static_cast<intptr_t>(kNumberOfFpuRegisters) <=
            kNumberOfCpuRegisters);
     bool used_on_backedge[kNumberOfCpuRegisters] = { false };
 
     for (PhiIterator it(loop_header->entry()->AsJoinEntry());
          !it.Done();
          it.Advance()) {
       PhiInstr* phi = it.Current();
-      if (phi->is_alive()) {
-        const intptr_t phi_vreg = phi->ssa_temp_index();
-        LiveRange* range = GetLiveRange(phi_vreg);
-        if (range->assigned_location().kind() == register_kind_) {
-          const intptr_t reg = range->assigned_location().register_code();
+      ASSERT(phi->is_alive());
+      const intptr_t phi_vreg = phi->ssa_temp_index();
+      LiveRange* range = GetLiveRange(phi_vreg);
+      if (range->assigned_location().kind() == register_kind_) {
+        const intptr_t reg = range->assigned_location().register_code();
 
-          if (!reaching_defs_.Get(phi)->Contains(unallocated->vreg())) {
-            used_on_backedge[reg] = true;
-          }
+        if (!reaching_defs_.Get(phi)->Contains(unallocated->vreg())) {
+          used_on_backedge[reg] = true;
         }
       }
     }
 
     if (used_on_backedge[candidate]) {
       TRACE_ALLOC(OS::Print(
           "considering %s for v%"Pd": has interference on the back edge"
           " {loop [%"Pd", %"Pd")}\n",
           MakeRegisterLocation(candidate, Location::kDouble).Name(),
           unallocated->vreg(),
@@ skipping 661 matching lines @@
         mint_values_->Add(defn->ssa_temp_index());
       }
     }
   }
 }
 
 
 void FlowGraphAllocator::AllocateRegisters() {
   CollectRepresentations();
 
-  EliminateEnvironmentUses();
+  EliminateEnvironments();
 
   AnalyzeLiveness();
 
   NumberInstructions();
 
   DiscoverLoops();
 
   BuildLiveRanges();
 
   if (FLAG_print_ssa_liveness) {
@@ skipping 51 matching lines @@
     OS::Print("-- [after ssa allocator] ir [%s] -------------\n",
               function.ToFullyQualifiedCString());
     FlowGraphPrinter printer(flow_graph_, true);
     printer.PrintBlocks();
     OS::Print("----------------------------------------------\n");
   }
 }
 
 
 }  // namespace dart