Remove dead phis as soon as they are discovered.

runtime/vm/flow_graph_optimizer.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_optimizer.h"
 
 #include "vm/bit_vector.h"
 #include "vm/cha.h"
 #include "vm/flow_graph_builder.h"
 #include "vm/flow_graph_compiler.h"
@@ skipping 365 matching lines @@
     const Representation to_rep =
         use->instruction()->RequiredInputRepresentation(use->use_index());
     if (from_rep == to_rep) {
       continue;
     }
 
     Instruction* insert_before;
     Instruction* deopt_target;
     PhiInstr* phi = use->instruction()->AsPhi();
     if (phi != NULL) {
-      if (!phi->is_alive()) continue;
-
+      ASSERT(phi->is_alive());
       // For phis conversions have to be inserted in the predecessor.
       insert_before =
           phi->block()->PredecessorAt(use->use_index())->last_instruction();
       deopt_target = NULL;
     } else {
       deopt_target = insert_before = use->instruction();
     }
 
     InsertConversion(from_rep, to_rep, use, insert_before, deopt_target);
   }
 }
 
 
 void FlowGraphOptimizer::SelectRepresentations() {
   // Convervatively unbox all phis that were proven to be of type Double.
   for (intptr_t i = 0; i < block_order_.length(); ++i) {
     JoinEntryInstr* join_entry = block_order_[i]->AsJoinEntry();
-    if (join_entry == NULL) continue;
-
-    if (join_entry->phis() != NULL) {
-      for (intptr_t i = 0; i < join_entry->phis()->length(); ++i) {
-        PhiInstr* phi = (*join_entry->phis())[i];
-        if (phi == NULL) continue;
+    if (join_entry != NULL) {
+      for (PhiIterator it(join_entry); !it.Done(); it.Advance()) {
+        PhiInstr* phi = it.Current();
+        ASSERT(phi != NULL);
         if (phi->Type()->ToCid() == kDoubleCid) {
           phi->set_representation(kUnboxedDouble);
         }
       }
     }
   }
 
   // Process all instructions and insert conversions where needed.
   GraphEntryInstr* graph_entry = block_order_[0]->AsGraphEntry();
 
   // Visit incoming parameters and constants.
   for (intptr_t i = 0; i < graph_entry->initial_definitions()->length(); i++) {
     InsertConversionsFor((*graph_entry->initial_definitions())[i]);
   }
 
   for (intptr_t i = 0; i < block_order_.length(); ++i) {
     BlockEntryInstr* entry = block_order_[i];
-
     JoinEntryInstr* join_entry = entry->AsJoinEntry();
-    if ((join_entry != NULL) && (join_entry->phis() != NULL)) {
-      for (intptr_t i = 0; i < join_entry->phis()->length(); ++i) {
-        PhiInstr* phi = (*join_entry->phis())[i];
-        if ((phi != NULL) && (phi->is_alive())) {
-          InsertConversionsFor(phi);
-        }
+    if (join_entry != NULL) {
+      for (PhiIterator it(join_entry); !it.Done(); it.Advance()) {
+        PhiInstr* phi = it.Current();
+        ASSERT(phi != NULL);
+        ASSERT(phi->is_alive());
+        InsertConversionsFor(phi);
       }
     }
-
     for (ForwardInstructionIterator it(entry); !it.Done(); it.Advance()) {
       Definition* def = it.Current()->AsDefinition();
       if (def != NULL) {
         InsertConversionsFor(def);
       }
     }
   }
 }
 
 
@@ skipping 1800 matching lines @@
 void RangeAnalysis::RenameDominatedUses(Definition* def,
                                         Instruction* dom,
                                         Definition* other) {
   for (Value::Iterator it(def->input_use_list());
        !it.Done();
        it.Advance()) {
     Value* use = it.Current();
 
     // Skip dead phis.
     PhiInstr* phi = use->instruction()->AsPhi();
-    if ((phi != NULL) && !phi->is_alive()) continue;
-
+    ASSERT((phi == NULL) || phi->is_alive());
     if (IsDominatedUse(dom, use)) {
       use->BindTo(other);
     }
   }
 }
 
 
 // For a comparison operation return an operation for the equivalent flipped
 // comparison: a (op) b === b (op') a.
 static Token::Kind FlipComparison(Token::Kind op) {
@@ skipping 1098 matching lines @@
     // All phis in the worklist are redundant and have the same computed
     // value on all code paths.
     ASSERT(value != NULL);
     for (intptr_t i = 0; i < worklist_.length(); i++) {
       worklist_[i]->ReplaceUsesWith(value);
     }
 
     return true;
   }
 
-  // Emit non-redundant phis created during ComputeOutValues and ForwardLoads.
+  // Phis have not yet been inserted into the graph but they have uses of
+  // their inputs.  Insert the non-redundant ones and clear the input uses
+  // of the redundant ones.
   void EmitPhis() {
     for (intptr_t i = 0; i < phis_.length(); i++) {
       PhiInstr* phi = phis_[i];
       if ((phi->input_use_list() != NULL) && !EliminateRedundantPhi(phi)) {
         phi->mark_alive();
         phi->block()->InsertPhi(phi);
+      } else {
+        for (intptr_t j = phi->InputCount() - 1; j >= 0; --j) {
+          phi->InputAt(j)->RemoveFromUseList();
+        }
       }
     }
   }
 
   ZoneGrowableArray<Definition*>* CreateBlockOutValues() {
     ZoneGrowableArray<Definition*>* out =
         new ZoneGrowableArray<Definition*>(max_expr_id_);
     for (intptr_t i = 0; i < max_expr_id_; i++) {
       out->Add(NULL);
     }
@@ skipping 848 matching lines @@
         it.Current()->UnuseAllInputs();
       }
       continue;
     }
 
     if (join != NULL) {
       // Remove phi inputs corresponding to unreachable predecessor blocks.
       // Predecessors will be recomputed (in block id order) after removing
       // unreachable code so we merely have to keep the phi inputs in order.
       ZoneGrowableArray<PhiInstr*>* phis = join->phis();
-      if (phis != NULL) {
+      if ((phis != NULL) && !phis->is_empty()) {
         intptr_t pred_count = join->PredecessorCount();
         intptr_t live_count = 0;
         for (intptr_t pred_idx = 0; pred_idx < pred_count; ++pred_idx) {
           if (reachable_->Contains(
                   join->PredecessorAt(pred_idx)->preorder_number())) {
             if (live_count < pred_idx) {
-              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);
                 phi->SetInputAt(live_count, phi->InputAt(pred_idx));
               }
             }
             ++live_count;
           } else {
-            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);
               phi->InputAt(pred_idx)->RemoveFromUseList();
             }
           }
         }
         if (live_count < pred_count) {
-          for (intptr_t phi_idx = 0; phi_idx < phis->length(); ++phi_idx) {
-            PhiInstr* phi = (*phis)[phi_idx];
-            if (phi == NULL) continue;
+          intptr_t to_idx = 0;
+          for (intptr_t from_idx = 0; from_idx < phis->length(); ++from_idx) {
+            PhiInstr* phi = (*phis)[from_idx];
+            ASSERT(phi != NULL);
             if (FLAG_remove_redundant_phis && (live_count == 1)) {

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

Do we have any code that kills truly redundant phis of form phi(x,x)?

(not related to this CL but might be a good follow up)

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

I don't think so.  I wonder, do they arise?

               Value* input = phi->InputAt(0);
               phi->ReplaceUsesWith(input->definition());
               input->RemoveFromUseList();
-              (*phis)[phi_idx] = NULL;
             } else {
               phi->inputs_.TruncateTo(live_count);
+              (*phis)[to_idx++] = phi;
             }
           }
+          if (to_idx == 0) {
+            join->phis_ = NULL;
+          } else {
+            phis->TruncateTo(to_idx);
+          }
         }
       }
     }
 
     for (ForwardInstructionIterator i(block); !i.Done(); i.Advance()) {
       Definition* defn = i.Current()->AsDefinition();
       // Replace constant-valued instructions without observable side
       // effects.  Do this for smis only to avoid having to copy other
       // objects into the heap's old generation.
       if ((defn != NULL) &&
@@ skipping 58 matching lines @@
 
   if (FLAG_trace_constant_propagation) {
     OS::Print("\n==== After constant propagation ====\n");
     FlowGraphPrinter printer(*graph_);
     printer.PrintBlocks();
   }
 }
 
 
 }  // namespace dart