Optimize functions containing try-catch.

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);
 
+#if defined(TARGET_ARCH_ARM) || defined(TARGET_ARCH_MIPS)
+DEFINE_FLAG(bool, optimize_try_catch, false, "Optimization of try-catch");
+#else
+DEFINE_FLAG(bool, optimize_try_catch, true, "Optimization of try-catch");
+#endif
+
 FlowGraph::FlowGraph(const FlowGraphBuilder& builder,
                      GraphEntryInstr* graph_entry,
                      intptr_t max_block_id)
   : parent_(),
     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()),
@@ skipping 292 matching lines @@
   // 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];
+      // All locals are assigned inside try-catch.

[Kevin Millikin (Google), 2013/05/08 11:42:00]

Comment needs to say why.  I don't understand why it must be the case that all
locals are assigned in every block inside a try.

Also: be precise in the comments about the difference between blocks inside the
try, blocks inside the catch, the try entry, and the catch entry.  It can be
ambiguous to say simply 'inside try-catch'.

[Florian Schneider, 2013/05/08 17:10:55]

Done.

       BitVector* kill = GetKillSet(block);
-      kill->Intersect(GetLiveOutSet(block));
+      if (block->try_index() != CatchClauseNode::kInvalidTryIndex) {
+        kill->SetAll();
+      } else {
+        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()) {
@@ skipping 28 matching lines @@
   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();
 
+    // Inside try-catch all locals are live.

[Kevin Millikin (Google), 2013/05/08 11:42:00]

Again, I don't understand why.  This is just for all the blocks occurring inside
the try, right?

Is this an approximation because we don't have edges from the calls to the catch
block?

[Florian Schneider, 2013/05/08 17:10:55]

Done.

+    if (block->try_index() != CatchClauseNode::kInvalidTryIndex) {
+      live_in->SetAll();
+      continue;
+    }
+
     // 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)) {
+        if (!last_loads->Contains(index) && !load->local().always_live()) {
           last_loads->Add(index);
           load->mark_last();
         }
         continue;
       }
 
       StoreLocalInstr* store = current->AsStoreLocal();
-      if (store != NULL) {
+      if (store != NULL && !store->local().always_live()) {
         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);
+        if (block->try_index() == CatchClauseNode::kInvalidTryIndex) {

[Kevin Millikin (Google), 2013/05/08 11:42:00]

This comparison is always true.  The loop is not entered in the case that the
condition is false.

[Florian Schneider, 2013/05/08 17:10:55]

Done.

+          live_in->Remove(index);
+        }
         continue;
       }
     }
   }
 }
 
 
 void FlowGraph::ComputeSSA(
     intptr_t next_virtual_register_number,
     ZoneGrowableArray<Definition*>* inlining_parameters) {
@@ skipping 189 matching lines @@
         }
       }
     }
   }
 }
 
 
 void FlowGraph::Rename(GrowableArray<PhiInstr*>* live_phis,
                        VariableLivenessAnalysis* variable_liveness,
                        ZoneGrowableArray<Definition*>* inlining_parameters) {
-  // TODO(fschneider): Support catch-entry.
-  if (graph_entry_->SuccessorCount() > 1) {
+  if (!FLAG_optimize_try_catch && (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.
   constant_null_ =
       AddConstantToInitialDefinitions(Object::ZoneHandle());
 
@@ skipping 15 matching lines @@
       AddToInitialDefinitions(param);
       env.Add(param);
     }
   }
 
   // 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);
+  if (graph_entry_->SuccessorCount() > 1) {
+    // Functions with try-catch have a fixed area of stack slots reserved
+    // so that all local variables are stored at a known location when
+    // on entry to the catch.
+    graph_entry_->set_fixed_slot_count(
+        num_stack_locals() + num_copied_params());
+  }
+  RenameRecursive(graph_entry_, &env, live_phis, variable_liveness);
 }
 
 
 void FlowGraph::AttachEnvironment(Instruction* instr,
                                   GrowableArray<Definition*>* env) {
   Environment* deopt_env =
       Environment::From(*env,
                         num_non_copied_params_,
                         parsed_function_.function());
   instr->SetEnvironment(deopt_env);
@@ skipping 13 matching lines @@
                                 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.
+          if (block_entry->try_index() != CatchClauseNode::kInvalidTryIndex) {

[Kevin Millikin (Google), 2013/05/08 11:42:00]

This comparison is repeated a lot in this change.  It's more readable to
introduce a predicate on blocks IsInsideTry, or NestedInsideTry, or the like.

We also need the comment to record why all phis inside blocks inside the try are
always live, even if not otherwise.

[Florian Schneider, 2013/05/08 17:10:55]

Done.

+            phi->mark_alive();
+            live_phis->Add(phi);
+          }
         }
       }
     }
+  } else if (block_entry->IsCatchBlockEntry()) {
+    // Add real definitions for all locals and parameters. The location of the
+    // parameters and locals is the same as at function entry.

[Kevin Millikin (Google), 2013/05/08 11:42:00]

I don't think this comment is quite correct.  The locals are all uninitialized
at function entry and do not have distinct locations, do they?

I think you mean that the location is the same as in the unoptimized stack
frame, though I'm not sure that's important here.  Nothing about this place has
anything to do with locations anyway.

[Florian Schneider, 2013/05/08 17:10:55]

Done.

+    for (intptr_t i = 0; i < env->length(); ++i) {
+      ParameterInstr* param = new ParameterInstr(i, block_entry);
+      param->set_ssa_temp_index(alloc_ssa_temp_index());  // New SSA temp.
+      (*env)[i] = param;
+      block_entry->AsCatchBlockEntry()->initial_definitions()->Add(param);
+    }
   }
 
   // Attach environment to the block entry.
   AttachEnvironment(block_entry, env);
 
   // 2. Process normal instructions.
 
   for (ForwardInstructionIterator it(block_entry); !it.Done(); it.Advance()) {
     Instruction* current = it.Current();
 
@@ skipping 38 matching lines @@
       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_);
           result = store->value()->definition();
 
-          if (variable_liveness->IsStoreAlive(block_entry, store)) {
+          if (variable_liveness->IsStoreAlive(block_entry, store) ||
+              store->local().always_live()) {

[Kevin Millikin (Google), 2013/05/08 11:42:00]

Need to know why, also below.

These are for the the three special catch variables, right?  Do we have stores
to them that have implicit loads (so they aren't reflected in liveness analysis)
and should not be eliminated?

[Florian Schneider, 2013/05/08 17:10:55]

Done. Not needed anymore.

             (*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 = result->AsPhi();
           if ((phi != NULL) && !phi->is_alive()) {
             phi->mark_alive();
             live_phis->Add(phi);
           }
 
-          if (variable_liveness->IsLastLoad(block_entry, load)) {
+          if (variable_liveness->IsLastLoad(block_entry, load) &&
+              !load->local().always_live()) {

[Kevin Millikin (Google), 2013/05/08 11:42:00]

Is this because there are implicit loads from the special catch variables, so
this might not really be the last load?

[Florian Schneider, 2013/05/08 17:10:55]

Done. Not needed anymore.

             (*env)[index] = constant_null();
           }
         }
         // Update expression stack or remove from graph.
         if (definition->is_used()) {
           env->Add(result);
           // We remove load/store instructions when we find their use in 2a.
         } else {
           it.RemoveCurrentFromGraph();
         }
@@ skipping 270 matching lines @@
 }
 
 
 bool BlockEffects::IsSideEffectFreePath(BlockEntryInstr* from,
                                         BlockEntryInstr* to) const {
   return available_at_[to->postorder_number()]->Contains(
       from->postorder_number());
 }
 
 }  // namespace dart