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"
+#include "vm/il_printer.h"

[srdjan, 2013/05/07 17:34:05]

Remove.

[Florian Schneider, 2013/05/08 08:57:47]

Done.

 
 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_(),
@@ skipping 298 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.
       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 24 matching lines @@
 };
 
 
 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];
 
+

[srdjan, 2013/05/07 17:34:05]

Two lines space seems too match within a function (also some places below).

[Florian Schneider, 2013/05/08 08:57:47]

Done.

     BitVector* kill = kill_[i];
     BitVector* live_in = live_in_[i];
     last_loads->Clear();
 
+    // Inside try-catch all locals are live.
+    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) {
+          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) {
-    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());
 
   // Add parameters to the initial definitions and renaming environment.
   if (inlining_parameters != NULL) {
     // Use known parameters.
@@ skipping 12 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) {
+            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.
+    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()) {
             (*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()) {
             (*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();
         }
       } 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);
   }
 
   // 4. Process successor block. We have edge-split form, so that only blocks
   // with one successor can have a join block as successor.
@@ skipping 243 matching lines @@
 }
 
 
 bool BlockEffects::IsSideEffectFreePath(BlockEntryInstr* from,
                                         BlockEntryInstr* to) const {
   return available_at_[to->postorder_number()]->Contains(
       from->postorder_number());
 }
 
 }  // namespace dart