Revert "Compute local variable liveness before translation to SSA."

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"
 #include "vm/growable_array.h"
 
 namespace dart {
 
 DECLARE_FLAG(bool, trace_optimization);
 DECLARE_FLAG(bool, verify_compiler);
 
 FlowGraph::FlowGraph(const FlowGraphBuilder& builder,
                      GraphEntryInstr* graph_entry,
                      intptr_t max_block_id)
   : parent_(),
+    assigned_vars_(),
     current_ssa_temp_index_(0),
     max_block_id_(max_block_id),
     parsed_function_(builder.parsed_function()),
     num_copied_params_(builder.num_copied_params()),
     num_non_copied_params_(builder.num_non_copied_params()),
     num_stack_locals_(builder.num_stack_locals()),
     graph_entry_(graph_entry),
     preorder_(),
     postorder_(),
     reverse_postorder_(),
@@ skipping 48 matching lines @@
   if (env != NULL) env->DeepCopyTo(instr);
 }
 
 
 void FlowGraph::DiscoverBlocks() {
   // Initialize state.
   preorder_.Clear();
   postorder_.Clear();
   reverse_postorder_.Clear();
   parent_.Clear();
+  assigned_vars_.Clear();
   // Perform a depth-first traversal of the graph to build preorder and
   // postorder block orders.
   graph_entry_->DiscoverBlocks(NULL,  // Entry block predecessor.
                                &preorder_,
                                &postorder_,
                                &parent_,
+                               &assigned_vars_,
                                variable_count(),
                                num_non_copied_params());
   // Create an array of blocks in reverse postorder.
   intptr_t block_count = postorder_.length();
   for (intptr_t i = 0; i < block_count; ++i) {
     reverse_postorder_.Add(postorder_[block_count - i - 1]);
   }
 }
 
 
@@ skipping 89 matching lines @@
     }
     for (ForwardInstructionIterator it(entry); !it.Done(); it.Advance()) {
       VerifyUseListsInInstruction(it.Current());
     }
   }
   return true;  // Return true so we can ASSERT validation.
 }
 #endif  // DEBUG
 
 
-LivenessAnalysis::LivenessAnalysis(
-  intptr_t variable_count,
-  const GrowableArray<BlockEntryInstr*>& postorder)
-    : variable_count_(variable_count),
-      postorder_(postorder),
-      live_out_(postorder.length()),
-      kill_(postorder.length()),
-      live_in_(postorder.length()) {
-}
-
-
-bool LivenessAnalysis::UpdateLiveOut(const BlockEntryInstr& block) {
-  BitVector* live_out = live_out_[block.postorder_number()];
-  bool changed = false;
-  Instruction* last = block.last_instruction();
-  ASSERT(last != NULL);
-  for (intptr_t i = 0; i < last->SuccessorCount(); i++) {
-    BlockEntryInstr* succ = last->SuccessorAt(i);
-    ASSERT(succ != NULL);
-    if (live_out->AddAll(live_in_[succ->postorder_number()])) {
-      changed = true;
-    }
-  }
-  return changed;
-}
-
-
-bool LivenessAnalysis::UpdateLiveIn(const BlockEntryInstr& block) {
-  BitVector* live_out = live_out_[block.postorder_number()];
-  BitVector* kill = kill_[block.postorder_number()];
-  BitVector* live_in = live_in_[block.postorder_number()];
-  return live_in->KillAndAdd(kill, live_out);
-}
-
-
-void LivenessAnalysis::ComputeLiveInAndLiveOutSets() {
-  const intptr_t block_count = postorder_.length();
-  bool changed;
-  do {
-    changed = false;
-
-    for (intptr_t i = 0; i < block_count; i++) {
-      const BlockEntryInstr& block = *postorder_[i];
-
-      // Live-in set depends only on kill set which does not
-      // change in this loop and live-out set.  If live-out
-      // set does not change there is no need to recompute
-      // live-in set.
-      if (UpdateLiveOut(block) && UpdateLiveIn(block)) {
-        changed = true;
-      }
-    }
-  } while (changed);
-}
-
-
-void LivenessAnalysis::Analyze() {
-  const intptr_t block_count = postorder_.length();
-  for (intptr_t i = 0; i < block_count; i++) {
-    live_out_.Add(new BitVector(variable_count_));
-    kill_.Add(new BitVector(variable_count_));
-    live_in_.Add(new BitVector(variable_count_));
-  }
-
-  ComputeInitialSets();
-  ComputeLiveInAndLiveOutSets();
-}
-
-
-static void PrintBitVector(const char* tag, BitVector* v) {
-  OS::Print("%s:", tag);
-  for (BitVector::Iterator it(v); !it.Done(); it.Advance()) {
-    OS::Print(" %"Pd"", it.Current());
-  }
-  OS::Print("\n");
-}
-
-
-void LivenessAnalysis::Dump() {
-  const intptr_t block_count = postorder_.length();
-  for (intptr_t i = 0; i < block_count; i++) {
-    BlockEntryInstr* block = postorder_[i];
-    OS::Print("block @%"Pd" -> ", block->block_id());
-
-    Instruction* last = block->last_instruction();
-    for (intptr_t j = 0; j < last->SuccessorCount(); j++) {
-      BlockEntryInstr* succ = last->SuccessorAt(j);
-      OS::Print(" @%"Pd"", succ->block_id());
-    }
-    OS::Print("\n");
-
-    PrintBitVector("  live out", live_out_[i]);
-    PrintBitVector("  kill", kill_[i]);
-    PrintBitVector("  live in", live_in_[i]);
-  }
-}
-
-
-// Computes liveness information for local variables.
-class VariableLivenessAnalysis : public LivenessAnalysis {
- public:
-  explicit VariableLivenessAnalysis(FlowGraph* flow_graph)
-      : LivenessAnalysis(flow_graph->variable_count(), flow_graph->postorder()),
-        flow_graph_(flow_graph),
-        num_non_copied_params_(flow_graph->num_non_copied_params()),
-        assigned_vars_() { }
-
-  // For every block (in preorder) compute and return set of variables that
-  // have new assigned values flowing out of that block.
-  const GrowableArray<BitVector*>& ComputeAssignedVars() {
-    // We can't directly return kill_ because it uses postorder numbering while
-    // SSA construction uses preorder numbering internally.
-    // We have to permute postorder into preorder.
-    assigned_vars_.Clear();
-
-    const intptr_t block_count = flow_graph_->preorder().length();
-    for (intptr_t i = 0; i < block_count; i++) {
-      BlockEntryInstr* block = flow_graph_->preorder()[i];
-      BitVector* kill = GetKillSet(block);
-      kill->Intersect(GetLiveOutSet(block));
-      assigned_vars_.Add(kill);
-    }
-
-    return assigned_vars_;
-  }
-
-  // Returns true if the value set by the given store reaches any load from the
-  // same local variable.
-  bool IsStoreAlive(BlockEntryInstr* block, StoreLocalInstr* store) {
-    if (store->is_dead()) {
-      return false;
-    }
-
-    if (store->is_last()) {
-      const intptr_t index = store->local().BitIndexIn(num_non_copied_params_);
-      return GetLiveOutSet(block)->Contains(index);
-    }
-
-    return true;
-  }
-
-  // Returns true if the given load is the last for the local and the value
-  // of the local will not flow into another one.
-  bool IsLastLoad(BlockEntryInstr* block, LoadLocalInstr* load) {
-    const intptr_t index = load->local().BitIndexIn(num_non_copied_params_);
-    return load->is_last() && !GetLiveOutSet(block)->Contains(index);
-  }
-
- private:
-  virtual void ComputeInitialSets();
-
-  const FlowGraph* flow_graph_;
-  const intptr_t num_non_copied_params_;
-  GrowableArray<BitVector*> assigned_vars_;
-};
-
-
-void VariableLivenessAnalysis::ComputeInitialSets() {
-  const intptr_t block_count = postorder_.length();
-
-  BitVector* last_loads = new BitVector(variable_count_);
-  for (intptr_t i = 0; i < block_count; i++) {
-    BlockEntryInstr* block = postorder_[i];
-
-    BitVector* kill = kill_[i];
-    BitVector* live_in = live_in_[i];
-    last_loads->Clear();
-
-    // Iterate backwards starting at the last instruction.
-    for (BackwardInstructionIterator it(block); !it.Done(); it.Advance()) {
-      Instruction* current = it.Current();
-
-      LoadLocalInstr* load = current->AsLoadLocal();
-      if (load != NULL) {
-        const intptr_t index = load->local().BitIndexIn(num_non_copied_params_);
-        live_in->Add(index);
-
-        if (!last_loads->Contains(index)) {
-          last_loads->Add(index);
-          load->mark_last();
-        }
-
-        continue;
-      }
-
-      StoreLocalInstr* store = current->AsStoreLocal();
-      if (store != NULL) {
-        const intptr_t index =
-            store->local().BitIndexIn(num_non_copied_params_);
-        if (kill->Contains(index)) {
-          if (!live_in->Contains(index)) {
-            store->mark_dead();
-          }
-        } else {
-          if (!live_in->Contains(index)) {
-            store->mark_last();
-          }
-          kill->Add(index);
-        }
-        live_in->Remove(index);
-        continue;
-      }
-    }
-  }
-}
-
-
 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);
-
-  VariableLivenessAnalysis variable_liveness(this);
-  variable_liveness.Analyze();
-
-  InsertPhis(preorder_,
-             variable_liveness.ComputeAssignedVars(),
-             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, &variable_liveness, inlining_parameters);
-
+  Rename(&live_phis, inlining_parameters);
   // 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.
 //
@@ skipping 161 matching lines @@
             worklist.Add(block);
           }
         }
       }
     }
   }
 }
 
 
 void FlowGraph::Rename(GrowableArray<PhiInstr*>* live_phis,
-                       VariableLivenessAnalysis* variable_liveness,
                        GrowableArray<Definition*>* inlining_parameters) {
   // TODO(fschneider): Support catch-entry.
   if (graph_entry_->SuccessorCount() > 1) {
     Bailout("Catch-entry support in SSA.");
   }
 
   // Initial renaming environment.
   GrowableArray<Definition*> env(variable_count());
 
   // Add global constants to the initial definitions.
@@ skipping 20 matching lines @@
     }
   }
 
   // Initialize all locals with #null in the renaming environment.
   for (intptr_t i = parameter_count(); i < variable_count(); ++i) {
     env.Add(constant_null());
   }
 
   BlockEntryInstr* normal_entry = graph_entry_->SuccessorAt(0);
   ASSERT(normal_entry != NULL);  // Must have entry.
-  RenameRecursive(normal_entry, &env, live_phis, variable_liveness);
+  RenameRecursive(normal_entry, &env, live_phis);
 }
 
 
 void FlowGraph::RenameRecursive(BlockEntryInstr* block_entry,
                                 GrowableArray<Definition*>* env,
-                                GrowableArray<PhiInstr*>* live_phis,
-                                VariableLivenessAnalysis* variable_liveness) {
+                                GrowableArray<PhiInstr*>* live_phis) {
   // 1. Process phis first.
   if (block_entry->IsJoinEntry()) {
     JoinEntryInstr* join = block_entry->AsJoinEntry();
     if (join->phis() != NULL) {
       for (intptr_t i = 0; i < join->phis()->length(); ++i) {
         PhiInstr* phi = (*join->phis())[i];
         if (phi != NULL) {
           (*env)[i] = phi;
           phi->set_ssa_temp_index(alloc_ssa_temp_index());  // New SSA temp.
         }
       }
     }
   }
 
   // 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->IsBranch() &&
-         current->AsBranch()->comparison()->IsStrictCompare())) {
+    if (current->CanDeoptimize() || current->IsGoto()) {
       Environment* deopt_env =
           Environment::From(*env,
                             num_non_copied_params_,
                             parsed_function_.function());
       current->SetEnvironment(deopt_env);
       for (Environment::DeepIterator it(deopt_env); !it.Done(); it.Advance()) {
         Value* use = it.CurrentValue();
         use->definition()->AddEnvUse(use);
       }
     }
@@ skipping 31 matching lines @@
 
     // 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.
     Definition* definition = current->AsDefinition();
     if (definition != NULL) {
       LoadLocalInstr* load = definition->AsLoadLocal();
       StoreLocalInstr* store = definition->AsStoreLocal();
       if ((load != NULL) || (store != NULL)) {
         intptr_t index;
-        Definition* result;
         if (store != NULL) {
+          index = store->local().BitIndexIn(num_non_copied_params_);
           // Update renaming environment.
-          index = store->local().BitIndexIn(num_non_copied_params_);
-          result = store->value()->definition();
-
-          if (variable_liveness->IsStoreAlive(block_entry, store)) {
-            (*env)[index] = result;
-          } else {
-            (*env)[index] = constant_null();
-          }
+          (*env)[index] = store->value()->definition();
         } else {
           // The graph construction ensures we do not have an unused LoadLocal
           // computation.
           ASSERT(definition->is_used());
           index = load->local().BitIndexIn(num_non_copied_params_);
-          result = (*env)[index];
 
-          PhiInstr* phi = result->AsPhi();
+          PhiInstr* phi = (*env)[index]->AsPhi();
           if ((phi != NULL) && !phi->is_alive()) {
             phi->mark_alive();
             live_phis->Add(phi);
           }
-
-          if (variable_liveness->IsLastLoad(block_entry, load)) {
-            (*env)[index] = constant_null();
-          }
         }
         // Update expression stack or remove from graph.
         if (definition->is_used()) {
-          env->Add(result);
+          env->Add((*env)[index]);
           // We remove load/store instructions when we find their use in 2a.
         } else {
           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);
         }
       }
     }
 
     // 2c. Handle pushed argument.
     PushArgumentInstr* push = current->AsPushArgument();
     if (push != NULL) {
       env->Add(push);
     }
   }
 
   // 3. Process dominated blocks.
   for (intptr_t i = 0; i < block_entry->dominated_blocks().length(); ++i) {
     BlockEntryInstr* block = block_entry->dominated_blocks()[i];
     GrowableArray<Definition*> new_env(env->length());
     new_env.AddArray(*env);
-    RenameRecursive(block, &new_env, live_phis, variable_liveness);
+    RenameRecursive(block, &new_env, live_phis);
   }
 
   // 4. Process successor block. We have edge-split form, so that only blocks
   // with one successor can have a join block as successor.
   if ((block_entry->last_instruction()->SuccessorCount() == 1) &&
       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);
@@ skipping 150 matching lines @@
       if (!found) {
         result->Add(field);
       }
     }
   }
 
   return result;
 }
 
 }  // namespace dart