A simpler scheme for garbage collection of ureachable phi inputs.

runtime/vm/intermediate_language.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/intermediate_language.h"
 
 #include "vm/bit_vector.h"
 #include "vm/dart_entry.h"
 #include "vm/flow_graph_allocator.h"
 #include "vm/flow_graph_builder.h"
@@ skipping 130 matching lines @@
 
 const Object& Value::BoundConstant() const {
   ASSERT(BindsToConstant());
   ConstantInstr* constant = definition()->AsConstant();
   ASSERT(constant != NULL);
   return constant->value();
 }
 
 
 GraphEntryInstr::GraphEntryInstr(TargetEntryInstr* normal_entry)
-    : BlockEntryInstr(CatchClauseNode::kInvalidTryIndex),
+    : BlockEntryInstr(0, CatchClauseNode::kInvalidTryIndex),
       normal_entry_(normal_entry),
       catch_entries_(),
       initial_definitions_(),
       spill_slot_count_(0) {
 }
 
 
 ConstantInstr* GraphEntryInstr::constant_null() {
   ASSERT(initial_definitions_.length() > 0 &&
          initial_definitions_[0]->IsConstant() &&
@@ skipping 312 matching lines @@
   // always be wrongly eliminated.
   return Type::DynamicType();
 }
 
 
 RawAbstractType* PushArgumentInstr::CompileType() const {
   return AbstractType::null();
 }
 
 
+void JoinEntryInstr::AddPredecessor(BlockEntryInstr* predecessor) {
+  // Require the predecessors to be sorted by block_id to make managing
+  // their corresponding phi inputs simpler.
+  intptr_t pred_id = predecessor->block_id();
+  intptr_t index = 0;
+  while ((index < predecessors_.length()) &&
+         (predecessors_[index]->block_id() < pred_id)) {

[Vyacheslav Egorov (Google), 2012/09/21 12:52:59]

assert here that there is not block with pred_id in the array.

[Kevin Millikin (Google), 2012/09/21 13:08:04]

OK.

+    ++index;
+  }
+  predecessors_.InsertAt(index, predecessor);
+}
+
+
 intptr_t JoinEntryInstr::IndexOfPredecessor(BlockEntryInstr* pred) const {
   for (intptr_t i = 0; i < predecessors_.length(); ++i) {
     if (predecessors_[i] == pred) return i;
   }
   return -1;
 }
 
 
-void JoinEntryInstr::EliminateUnreachablePhiInputs() {
-  if (phis_ == NULL || phis_->is_empty()) return;
-
-  // Loop over the predecessors, reorganize phi inputs.
-  // TODO(kmillikin): Replace phis that have a single remaining input with
-  // the input.  This requires being a bit careful about use lists.
-  intptr_t input_count = predecessors_.length();
-  for (intptr_t new_idx = 0; new_idx < input_count; ++new_idx) {
-    BlockEntryInstr* pred = predecessors_[new_idx];
-    // Linear search for the old predecessor index.  We can't directly
-    // compare block entries, because unreachable code elimination has
-    // replaced some targets with joins.
-    intptr_t old_idx = 0;
-    for (; old_idx < stale_predecessors_.length(); ++old_idx) {
-      if (stale_predecessors_[old_idx]->next() == pred->next()) break;
-    }
-    ASSERT(old_idx < stale_predecessors_.length());
-    // If the index has changed, adjust all phi inputs.
-    if (old_idx != new_idx) {
-      ASSERT(new_idx < old_idx);
-      // Swap each phi's inputs so the input at new_idx is correct.
-      // Preserve the previous value in case it is from a reachable
-      // predecessor.
-      for (intptr_t phi_idx = 0; phi_idx < phis_->length(); ++phi_idx) {
-        PhiInstr* phi = (*phis_)[phi_idx];
-        if (phi == NULL) continue;
-        Value* temp = phi->InputAt(new_idx);
-        phi->SetInputAt(new_idx, phi->InputAt(old_idx));
-        phi->SetInputAt(old_idx, temp);
-      }
-      // The old input at new_idx is now found at old_idx.  It may be a
-      // reachable predecessor so swap the old predecessors too.
-      BlockEntryInstr* temp = stale_predecessors_[new_idx];
-      stale_predecessors_[new_idx] = stale_predecessors_[old_idx];
-      stale_predecessors_[old_idx] = temp;
-    }
-  }
-  // Now truncate each phi if necessary.
-  if (input_count < stale_predecessors_.length()) {
-    for (intptr_t phi_idx = 0; phi_idx < phis_->length(); ++phi_idx) {
-      PhiInstr* phi = (*phis_)[phi_idx];
-      if (phi == NULL) continue;
-      phi->inputs_.TruncateTo(input_count);
-    }
-  }
-}
-
-
 // ==== Recording assigned variables.
 void Definition::RecordAssignedVars(BitVector* assigned_vars,
                                     intptr_t fixed_parameter_count) {
   // Nothing to do for the base class.
 }
 
 
 void StoreLocalInstr::RecordAssignedVars(BitVector* assigned_vars,
                                          intptr_t fixed_parameter_count) {
   if (!local().is_captured()) {
@@ skipping 1289 matching lines @@
     value->set_use_index(use_index++);
     value->AddToEnvUseList();
   }
   instr->env()->outer_ = copy;
 }
 
 
 #undef __
 
 }  // namespace dart