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]);
+  }
+}
+
+
+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_() { }
+
+  const GrowableArray<BitVector*>& ComputeAssignedVars() {
+    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));

[Kevin Millikin (Google), 2013/03/22 11:57:52]

It seems to me that you could either use a fresh bitvector for each element of
assigned_vars_ and not mutate kill_, or else mutate kill_ and then just return
it.

There doesn't seem much point to doing it this way, though.

[Vyacheslav Egorov (Google), 2013/03/22 12:16:15]

kill_ is in postorder while assigned_vars_ are in preorder. I will add a comment
about that.

+      assigned_vars_.Add(kill);
+    }
+
+    return assigned_vars_;
+  }
+
+  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;
+  }
+
+  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);
-  InsertPhis(preorder_, assigned_vars_, dominance_frontier);
+
+  VariableLivenessAnalysis variable_liveness(this);
+  variable_liveness.Analyze();
+
+  InsertPhis(preorder_,
+             variable_liveness.ComputeAssignedVars(),
+             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);
+  Rename(&live_phis, &variable_liveness, 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);
+  RenameRecursive(normal_entry, &env, live_phis, variable_liveness);
 }
 
 
 void FlowGraph::RenameRecursive(BlockEntryInstr* block_entry,
                                 GrowableArray<Definition*>* env,
-                                GrowableArray<PhiInstr*>* live_phis) {
+                                GrowableArray<PhiInstr*>* live_phis,
+                                VariableLivenessAnalysis* variable_liveness) {
   // 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()) {
+    if (current->CanDeoptimize() ||
+        current->IsGoto() ||
+        (current->IsBranch() &&

[Kevin Millikin (Google), 2013/03/22 11:57:52]

This still seems kind of fiddly.

Could we just make every control instruction that has successors have a deopt
environment?

[Vyacheslav Egorov (Google), 2013/03/22 12:16:15]

Discussed offline. Will postpone it to another change.

+         current->AsBranch()->comparison()->IsStrictCompare())) {
       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) {
+          // Update renaming environment.
           index = store->local().BitIndexIn(num_non_copied_params_);
-          // Update renaming environment.
-          (*env)[index] = store->value()->definition();
+          result = store->value()->definition();
+
+          if (variable_liveness->IsStoreAlive(block_entry, store)) {
+            (*env)[index] = result;
+          } else {
+            (*env)[index] = constant_null();
+          }
         } 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 = (*env)[index]->AsPhi();
+          PhiInstr* phi = result->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((*env)[index]);
+          env->Add(result);
           // 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);
+    RenameRecursive(block, &new_env, live_phis, variable_liveness);
   }
 
   // 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