Remove dead phis as soon as they are discovered.

runtime/vm/flow_graph.cc

 // Copyright (c) 2012, 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.h"
 
 #include "vm/bit_vector.h"
 #include "vm/flow_graph_builder.h"
 #include "vm/intermediate_language.h"
 #include "vm/longjump.h"
@@ skipping 127 matching lines @@
       ASSERT(use->definition() != NULL);
       ASSERT((use->definition() != instr) || use->definition()->IsPhi());
       ASSERT(use->instruction() == instr);
       ASSERT(use->use_index() == use_index++);
       ASSERT(!FLAG_verify_compiler ||
              (1 == MembershipCount(use, use->definition()->env_use_list())));
     }
   }
   Definition* defn = instr->AsDefinition();
   if (defn != NULL) {
+    // Used definitions must have an SSA name.  We use the name to index
+    // into bit vectors during analyses.  Some definitions without SSA names
+    // (e.g., PushArgument) have environment uses.
+    ASSERT((defn->input_use_list() == NULL) || defn->HasSSATemp());
     Value* prev = NULL;
     Value* curr = defn->input_use_list();
     while (curr != NULL) {
       ASSERT(prev == curr->previous_use());
       ASSERT(defn == curr->definition());
       Instruction* instr = curr->instruction();
-      // The instruction should not be removed from the graph.  Removed
-      // instructions have a NULL previous link.  Phis are not removed until
-      // register allocation.  Comparisons used only in a branch will have a
-      // NULL previous link though they are still in the graph.
-      ASSERT(instr->IsPhi() ||
-             (instr->IsDefinition() && instr->AsDefinition()->IsComparison()) ||
+      // The instruction should not be removed from the graph.
+      ASSERT((instr->IsPhi() && instr->AsPhi()->is_alive()) ||
              (instr->previous() != NULL));
       ASSERT(curr == instr->InputAt(curr->use_index()));
       prev = curr;
       curr = curr->next_use();
     }
 
     prev = NULL;
     curr = defn->env_use_list();
     while (curr != NULL) {
       ASSERT(prev == curr->previous_use());
       ASSERT(defn == curr->definition());
       Instruction* instr = curr->instruction();
       ASSERT(curr == instr->env()->ValueAtUseIndex(curr->use_index()));
-      ASSERT(instr->IsPhi() ||
-             (instr->IsDefinition() && instr->AsDefinition()->IsComparison()) ||
+      ASSERT((instr->IsPhi() && instr->AsPhi()->is_alive()) ||
              (instr->previous() != NULL));
       prev = curr;
       curr = curr->next_use();
     }
   }
 }
 
 
 bool FlowGraph::VerifyUseLists() {
   // Verify the initial definitions.
   for (intptr_t i = 0; i < graph_entry_->initial_definitions()->length(); ++i) {
     VerifyUseListsInInstruction((*graph_entry_->initial_definitions())[i]);
   }
 
   // Verify phis in join entries and the instructions in each block.
   for (intptr_t i = 0; i < preorder_.length(); ++i) {
     BlockEntryInstr* entry = preorder_[i];
     JoinEntryInstr* join = entry->AsJoinEntry();
-    if (join != NULL && join->phis() != NULL) {
-      for (intptr_t i = 0; i < join->phis()->length(); ++i) {
-        PhiInstr* phi = (*join->phis())[i];
-        if (phi != NULL) VerifyUseListsInInstruction(phi);
+    if (join != NULL) {
+      for (PhiIterator it(join); !it.Done(); it.Advance()) {
+        PhiInstr* phi = it.Current();
+        ASSERT(phi != NULL);
+        VerifyUseListsInInstruction(phi);
       }
     }
     for (ForwardInstructionIterator it(entry); !it.Done(); it.Advance()) {
       VerifyUseListsInInstruction(it.Current());
     }
   }
   return true;  // Return true so we can ASSERT validation.
 }
 #endif  // DEBUG
 
 
 void FlowGraph::ComputeSSA(intptr_t next_virtual_register_number,
                            GrowableArray<Definition*>* inlining_parameters) {
   ASSERT((next_virtual_register_number == 0) || (inlining_parameters != NULL));
   current_ssa_temp_index_ = next_virtual_register_number;
   GrowableArray<BitVector*> dominance_frontier;
   ComputeDominators(&dominance_frontier);
   InsertPhis(preorder_, assigned_vars_, dominance_frontier);
   GrowableArray<PhiInstr*> live_phis;
   // Rename uses to reference inserted phis where appropriate.
   // Collect phis that reach a non-environment use.
   Rename(&live_phis, inlining_parameters);
-  // Propagate alive mark transitively from alive phis.
-  MarkLivePhis(&live_phis);
+  // Propagate alive mark transitively from alive phis and then remove
+  // non-live ones.
+  RemoveDeadPhis(&live_phis);
 }
 
 
 // Compute immediate dominators and the dominance frontier for each basic
 // block.  As a side effect of the algorithm, sets the immediate dominator
 // of each basic block.
 //
 // dominance_frontier: an output parameter encoding the dominance frontier.
 //     The array maps the preorder block number of a block to the set of
 //     (preorder block numbers of) blocks in the dominance frontier.
@@ skipping 340 matching lines @@
         block_entry->last_instruction()->SuccessorAt(0)->AsJoinEntry();
     intptr_t pred_index = successor->IndexOfPredecessor(block_entry);
     ASSERT(pred_index >= 0);
     if (successor->phis() != NULL) {
       for (intptr_t i = 0; i < successor->phis()->length(); ++i) {
         PhiInstr* phi = (*successor->phis())[i];
         if (phi != NULL) {
           // Rename input operand.
           Value* use = new Value((*env)[i]);
           phi->SetInputAt(pred_index, use);
-          use->definition()->AddInputUse(use);
         }
       }
     }
   }
 }
 
 
-void FlowGraph::MarkLivePhis(GrowableArray<PhiInstr*>* live_phis) {
+void FlowGraph::RemoveDeadPhis(GrowableArray<PhiInstr*>* live_phis) {
   while (!live_phis->is_empty()) {
     PhiInstr* phi = live_phis->RemoveLast();
     for (intptr_t i = 0; i < phi->InputCount(); i++) {
       Value* val = phi->InputAt(i);
       PhiInstr* used_phi = val->definition()->AsPhi();
       if ((used_phi != NULL) && !used_phi->is_alive()) {
         used_phi->mark_alive();
         live_phis->Add(used_phi);
       }
     }
   }
+
+  for (BlockIterator it(postorder_iterator()); !it.Done(); it.Advance()) {
+    JoinEntryInstr* join = it.Current()->AsJoinEntry();
+    if (join != NULL) join->RemoveDeadPhis(constant_null());
+  }
 }
 
 
 // Find the natural loop for the back edge m->n and attach loop information
 // to block n (loop header). The algorithm is described in "Advanced Compiler
 // Design & Implementation" (Muchnick) p192.
 static void FindLoop(BlockEntryInstr* m,
                      BlockEntryInstr* n,
                      intptr_t num_blocks) {
   GrowableArray<BlockEntryInstr*> stack;
@@ skipping 74 matching lines @@
          !it.Done();
          it.Advance()) {
       ++size;
     }
   }
   return size;
 }
 
 
 }  // namespace dart