Change the SSA construction pass to also construct def-use chains.

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 107 matching lines @@
 static intptr_t MembershipCount(Value* use, Value* list) {
   intptr_t count = 0;
   while (list != NULL) {
     if (list == use) ++count;
     list = list->next_use();
   }
   return count;
 }
 
 
-static void ResetUseListsInInstruction(Instruction* instr) {
-  Definition* defn = instr->AsDefinition();
-  if (defn != NULL) {
-    defn->set_input_use_list(NULL);
-    defn->set_env_use_list(NULL);
-  }
-  for (intptr_t i = 0; i < instr->InputCount(); ++i) {
-    Value* use = instr->InputAt(i);
-    use->set_instruction(NULL);
-    use->set_use_index(-1);
-    use->set_previous_use(NULL);
-    use->set_next_use(NULL);
-  }
-  for (Environment::DeepIterator it(instr->env()); !it.Done(); it.Advance()) {
-    Value* use = it.CurrentValue();
-    use->set_instruction(NULL);
-    use->set_use_index(-1);
-    use->set_previous_use(NULL);
-    use->set_next_use(NULL);
-  }
-}
-
-
-bool FlowGraph::ResetUseLists() {
-  // Reset initial definitions.
-  for (intptr_t i = 0; i < graph_entry_->initial_definitions()->length(); ++i) {
-    ResetUseListsInInstruction((*graph_entry_->initial_definitions())[i]);
-  }
-
-  // Reset 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) ResetUseListsInInstruction(phi);
-      }
-    }
-    for (ForwardInstructionIterator it(entry); !it.Done(); it.Advance()) {
-      ResetUseListsInInstruction(it.Current());
-    }
-  }
-  return true;  // Return true so we can ASSERT the reset code.
-}
-
-
 static void VerifyUseListsInInstruction(Instruction* instr) {
   ASSERT(instr != NULL);
   ASSERT(!instr->IsJoinEntry());
   for (intptr_t i = 0; i < instr->InputCount(); ++i) {
     Value* use = instr->InputAt(i);
     ASSERT(use->definition() != NULL);
     ASSERT(use->definition() != instr);
     ASSERT(use->instruction() == instr);
     ASSERT(use->use_index() == i);
     ASSERT(!FLAG_verify_compiler ||
@@ skipping 66 matching lines @@
     }
     for (ForwardInstructionIterator it(entry); !it.Done(); it.Advance()) {
       VerifyUseListsInInstruction(it.Current());
     }
   }
   return true;  // Return true so we can ASSERT validation.
 }
 #endif  // DEBUG
 
 
-static void ClearUseLists(Definition* defn) {
-  ASSERT(defn != NULL);
-  ASSERT(!defn->HasUses());
-  defn->set_input_use_list(NULL);
-  defn->set_env_use_list(NULL);
-}
-
-
-static void RecordInputUses(Instruction* instr) {
-  ASSERT(instr != NULL);
-  for (intptr_t i = 0; i < instr->InputCount(); ++i) {
-    Value* use = instr->InputAt(i);
-    ASSERT(use->instruction() == NULL);
-    ASSERT(use->use_index() == -1);
-    ASSERT(use->previous_use() == NULL);
-    ASSERT(use->next_use() == NULL);
-    DEBUG_ASSERT(!FLAG_verify_compiler ||
-        (0 == MembershipCount(use, use->definition()->input_use_list())));
-    use->set_instruction(instr);
-    use->set_use_index(i);
-    use->definition()->AddInputUse(use);
-  }
-}
-
-
-static void RecordEnvUses(Instruction* instr) {
-  ASSERT(instr != NULL);
-  if (instr->env() == NULL) return;
-  intptr_t use_index = 0;
-  for (Environment::DeepIterator it(instr->env()); !it.Done(); it.Advance()) {
-    Value* use = it.CurrentValue();
-    ASSERT(use->instruction() == NULL);
-    ASSERT(use->use_index() == -1);
-    ASSERT(use->previous_use() == NULL);
-    ASSERT(use->next_use() == NULL);
-    DEBUG_ASSERT(!FLAG_verify_compiler ||
-        (0 == MembershipCount(use, use->definition()->env_use_list())));
-    use->set_instruction(instr);
-    use->set_use_index(use_index++);
-    use->definition()->AddEnvUse(use);
-  }
-}
-
-
-static void ComputeUseListsRecursive(BlockEntryInstr* block) {
-  // Clear phi definitions.
-  JoinEntryInstr* join = block->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) ClearUseLists(phi);
-    }
-  }
-  // Compute uses on normal instructions.
-  for (ForwardInstructionIterator it(block); !it.Done(); it.Advance()) {
-    Instruction* instr = it.Current();
-    if (instr->IsDefinition()) ClearUseLists(instr->AsDefinition());
-    RecordInputUses(instr);
-    RecordEnvUses(instr);
-  }
-  // Compute recursively on dominated blocks.
-  for (intptr_t i = 0; i < block->dominated_blocks().length(); ++i) {
-    ComputeUseListsRecursive(block->dominated_blocks()[i]);
-  }
-  // Add phi uses on successor edges.
-  if (block->last_instruction()->SuccessorCount() == 1 &&
-      block->last_instruction()->SuccessorAt(0)->IsJoinEntry()) {
-    JoinEntryInstr* join =
-        block->last_instruction()->SuccessorAt(0)->AsJoinEntry();
-    intptr_t pred_index = join->IndexOfPredecessor(block);
-    ASSERT(pred_index >= 0);
-    if (join->phis() != NULL) {
-      for (intptr_t i = 0; i < join->phis()->length(); ++i) {
-        PhiInstr* phi = (*join->phis())[i];
-        if (phi == NULL) continue;
-        Value* use = phi->InputAt(pred_index);
-        ASSERT(use->instruction() == NULL);
-        ASSERT(use->use_index() == -1);
-        ASSERT(use->previous_use() == NULL);
-        ASSERT(use->next_use() == NULL);
-        DEBUG_ASSERT(!FLAG_verify_compiler ||
-            (0 == MembershipCount(use, use->definition()->input_use_list())));
-        use->set_instruction(phi);
-        use->set_use_index(pred_index);
-        use->definition()->AddInputUse(use);
-      }
-    }
-  }
-}
-
-
-void FlowGraph::ComputeUseLists() {
-  DEBUG_ASSERT(ResetUseLists());
-  // Clear initial definitions.
-  for (intptr_t i = 0; i < graph_entry_->initial_definitions()->length(); ++i) {
-    ClearUseLists((*graph_entry_->initial_definitions())[i]);
-  }
-  ComputeUseListsRecursive(graph_entry_);
-  DEBUG_ASSERT(!FLAG_verify_compiler || VerifyUseLists());
-}
-
-
 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.
@@ skipping 239 matching lines @@
     }
   }
 
   // 2. Process normal instructions.
   for (ForwardInstructionIterator it(block_entry); !it.Done(); it.Advance()) {
     Instruction* current = it.Current();
     // Attach current environment to the instructions that can deoptimize and
     // at goto instructions. Optimizations like LICM expect an environment at
     // gotos.
     if (current->CanDeoptimize() || current->IsGoto()) {
-      current->set_env(Environment::From(*env,
-                                         num_non_copied_params_,
-                                         parsed_function_.function()));
+      Environment* deopt_env =
+          Environment::From(*env,
+                            num_non_copied_params_,
+                            parsed_function_.function());
+      current->set_env(deopt_env);
+      intptr_t use_index = 0;
+      for (Environment::DeepIterator it(deopt_env); !it.Done(); it.Advance()) {
+        Value* use = it.CurrentValue();
+        use->set_instruction(current);
+        use->set_use_index(use_index++);
+        use->definition()->AddEnvUse(use);
+      }
     }
     if (current->CanDeoptimize()) {
       current->env()->set_deopt_id(current->deopt_id());
     }
 
     // 2a. Handle uses:
     // Update expression stack environment for each use.
     // For each use of a LoadLocal or StoreLocal: Replace it with the value
     // from the environment.
     for (intptr_t i = current->InputCount() - 1; i >= 0; --i) {
       Value* v = current->InputAt(i);
       // Update expression stack.
       ASSERT(env->length() > variable_count());
 
       Definition* reaching_defn = env->RemoveLast();
 
       Definition* input_defn = v->definition();
       if (input_defn->IsLoadLocal() || input_defn->IsStoreLocal()) {
         // Remove the load/store from the graph.
+        input_defn->UnuseAllInputs();
         input_defn->RemoveFromGraph();
         // Assert we are not referencing nulls in the initial environment.
         ASSERT(reaching_defn->ssa_temp_index() != -1);
-        current->SetInputAt(i, new Value(reaching_defn));
+        v->set_definition(reaching_defn);
+        input_defn = reaching_defn;
       }
+      v->set_instruction(current);
+      v->set_use_index(i);
+      input_defn->AddInputUse(v);
     }
 
     // Drop pushed arguments for calls.
     for (intptr_t j = 0; j < current->ArgumentCount(); j++) {
       env->RemoveLast();
     }
 
     // 2b. Handle LoadLocal and StoreLocal.
     // For each LoadLocal: Remove it from the graph.
     // For each StoreLocal: Remove it from the graph and update the environment.
@@ skipping 17 matching lines @@
           if ((phi != NULL) && !phi->is_alive()) {
             phi->mark_alive();
             live_phis->Add(phi);
           }
         }
         // Update expression stack or remove from graph.
         if (definition->is_used()) {
           env->Add((*env)[index]);
           // We remove load/store instructions when we find their use in 2a.
         } else {
+          definition->UnuseAllInputs();
           it.RemoveCurrentFromGraph();
         }
       } else {
         // Not a load or store.
         if (definition->is_used()) {
           // Assign fresh SSA temporary and update expression stack.
           definition->set_ssa_temp_index(alloc_ssa_temp_index());
           env->Add(definition);
         }
       }
@@ skipping 20 matching lines @@
       block_entry->last_instruction()->SuccessorAt(0)->IsJoinEntry()) {
     JoinEntryInstr* successor =
         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.
-          phi->SetInputAt(pred_index, new Value((*env)[i]));
+          Value* use = new Value((*env)[i]);
+          phi->SetInputAt(pred_index, use);
+          use->set_instruction(phi);
+          use->set_use_index(pred_index);
+          use->definition()->AddInputUse(use);
         }
       }
     }
   }
 }
 
 
 void FlowGraph::MarkLivePhis(GrowableArray<PhiInstr*>* live_phis) {
   while (!live_phis->is_empty()) {
     PhiInstr* phi = live_phis->RemoveLast();
@@ skipping 93 matching lines @@
          !it.Done();
          it.Advance()) {
       ++size;
     }
   }
   return size;
 }
 
 
 }  // namespace dart