Optimize functions containing try-catch.

runtime/vm/flow_graph_optimizer.cc

 // Copyright (c) 2013, 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_optimizer.h"
 
 #include "vm/bit_vector.h"
 #include "vm/cha.h"
 #include "vm/flow_graph_builder.h"
 #include "vm/flow_graph_compiler.h"
 #include "vm/hash_map.h"
 #include "vm/il_printer.h"
 #include "vm/intermediate_language.h"
 #include "vm/object_store.h"
 #include "vm/parser.h"
 #include "vm/resolver.h"
 #include "vm/scopes.h"
+#include "vm/stack_frame.h"
 #include "vm/symbols.h"
 
 namespace dart {
 
 DEFINE_FLAG(bool, array_bounds_check_elimination, true,
     "Eliminate redundant bounds checks.");
 DEFINE_FLAG(bool, load_cse, true, "Use redundant load elimination.");
 DEFINE_FLAG(int, max_polymorphic_checks, 4,
     "Maximum number of polymorphic check, otherwise it is megamorphic.");
 DEFINE_FLAG(bool, remove_redundant_phis, true, "Remove redundant phis.");
@@ skipping 422 matching lines @@
     BlockEntryInstr* entry = block_order_[i];
     JoinEntryInstr* join_entry = entry->AsJoinEntry();
     if (join_entry != NULL) {
       for (PhiIterator it(join_entry); !it.Done(); it.Advance()) {
         PhiInstr* phi = it.Current();
         ASSERT(phi != NULL);
         ASSERT(phi->is_alive());
         InsertConversionsFor(phi);
       }
     }
+    CatchBlockEntryInstr* catch_entry = entry->AsCatchBlockEntry();
+    if (catch_entry != NULL) {
+      for (intptr_t i = 0;
+           i < catch_entry->initial_definitions()->length();
+           i++) {
+        InsertConversionsFor((*catch_entry->initial_definitions())[i]);
+      }
+    }
     for (ForwardInstructionIterator it(entry); !it.Done(); it.Advance()) {
       Definition* def = it.Current()->AsDefinition();
       if (def != NULL) {
         InsertConversionsFor(def);
       }
     }
   }
 }
 
 
@@ skipping 2201 matching lines @@
 
 
 void RangeAnalysis::Analyze() {
   CollectSmiValues();
   InsertConstraints();
   InferRanges();
   RemoveConstraints();
 }
 
 
 void RangeAnalysis::CollectSmiValues() {

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

Note that this function does not handle smi constant in the catch block initial
definitions.

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

Good catch. Done.

   for (BlockIterator block_it = flow_graph_->reverse_postorder_iterator();
        !block_it.Done();
        block_it.Advance()) {
     BlockEntryInstr* block = block_it.Current();
     for (ForwardInstructionIterator instr_it(block);
          !instr_it.Done();
          instr_it.Advance()) {
       Instruction* current = instr_it.Current();
       Definition* defn = current->AsDefinition();
       if (defn != NULL) {
@@ skipping 350 matching lines @@
     case kUnknown:
     case kBoth:
       return Range::Unknown();
   }
 
   UNREACHABLE();
   return NULL;
 }
 
 
 void RangeAnalysis::InferRangesRecursive(BlockEntryInstr* block) {

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

Note that this function does not infer ranges for constants in the catch entry's
initial definitions.

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

Done.

   JoinEntryInstr* join = block->AsJoinEntry();
   if (join != NULL) {
     const bool is_loop_header = (join->loop_info() != NULL);
     for (PhiIterator it(join); !it.Done(); it.Advance()) {
       PhiInstr* phi = it.Current();
       if (smi_definitions_->Contains(phi->ssa_temp_index())) {
         if (is_loop_header) {
           // Try recognizing simple induction variables.
           Range* range = InferInductionVariableRange(join, phi);
           if (range != NULL) {
@@ skipping 66 matching lines @@
   }
 }
 
 
 void FlowGraphOptimizer::InferSmiRanges() {
   RangeAnalysis range_analysis(flow_graph_);
   range_analysis.Analyze();
 }
 
 
+void FlowGraphOptimizer::AnalyzeTryCatch() {

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

Doesn't need to be in the FlowGraphOptimizer, which is a visitor that does
ApplyICData.

I think it's confusing to put too many unrelated passes into that same visitor
class.

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

Done.

+  // For every catch-block: Iterate over all call instructions inside the
+  // corresponding try-block and figure out for each environment value if it
+  // is the same constant at all calls. If yes, replace the initial definition
+  // at the catch-entry with this constant.
+  const GrowableArray<CatchBlockEntryInstr*>& catch_entries =
+      flow_graph_->graph_entry()->catch_entries();
+  intptr_t nncp = flow_graph_->num_non_copied_params();

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

intptr_t base = kFirstLocalSlotIndex + flow_graph_->num_non_copied_params();

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

Done.

+  for (intptr_t catch_idx = 0;
+       catch_idx < catch_entries.length();
+       ++catch_idx) {
+    CatchBlockEntryInstr* cb = catch_entries[catch_idx];
+    CatchEntryInstr* catch_entry = cb->next()->AsCatchEntry();
+    intptr_t ex_idx =

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

intptr_t ex_idx = base - catch_entry->exception_var().index();
intptr_t st_idx = base - catch_entry->stacktrace_var().index();

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

Done.

+        kFirstLocalSlotIndex - catch_entry->exception_var().index() + nncp;
+    intptr_t st_idx =
+        kFirstLocalSlotIndex - catch_entry->stacktrace_var().index() + nncp;
+    GrowableArray<Definition*>* idefs = cb->initial_definitions();
+    GrowableArray<Definition*> cdefs(idefs->length());
+    cdefs.AddArray(*idefs);
+
+    for (BlockIterator block_it = flow_graph_->reverse_postorder_iterator();

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

This is doing constant analysis with the lattice:

known to be non-constant (rep: NULL)
  |
known constant (rep: ConstantInstr)
  |
unknown constant (rep: Parameter Instr)

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

Done.

+         !block_it.Done();
+         block_it.Advance()) {
+      BlockEntryInstr* block = block_it.Current();
+      if (block->try_index() == cb->catch_try_index()) {
+        for (ForwardInstructionIterator instr_it(block);
+             !instr_it.Done();
+             instr_it.Advance()) {
+          Instruction* current = instr_it.Current();
+          if (current->MayThrow()) {
+            Environment* env = current->env();
+            for (intptr_t env_idx = 0; env_idx < cdefs.length(); ++env_idx) {
+              if (cdefs[env_idx] != NULL &&
+                  cdefs[env_idx]->IsParameter() &&
+                  cdefs[env_idx]->AsParameter()->index() != ex_idx &&

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

The intent is that ex_idx and st_idx are not constant.  I think it's simpler to
set them to NULL before performing the analysis and have no special treatment in
the loop.

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

Done.

+                  cdefs[env_idx]->AsParameter()->index() != st_idx &&
+                  env->ValueAt(env_idx)->definition()->IsConstant()) {

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

I guess you can write this as env->ValueAt(env_idx)->BindsToConstant();

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

Done.

+                cdefs[env_idx] = env->ValueAt(env_idx)->definition();
+              }
+              if (cdefs[env_idx] != env->ValueAt(env_idx)->definition()) {
+                cdefs[env_idx] = NULL;
+              }
+            }
+          }
+        }
+      }
+    }
+    for (intptr_t j = 0; j < idefs->length(); ++j) {
+      if (cdefs[j] != NULL && cdefs[j]->IsConstant()) {
+        Definition* old = (*idefs)[j];
+        ConstantInstr* orig = cdefs[j]->AsConstant();
+        ConstantInstr* copy = new ConstantInstr(orig->value());

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

Note that all constants are pooled now.  I think you can simply replaces uses
with the one from the pool and remove this definition from the catch block's
initial definitions.  Will that work?

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

Yes. It should and make the code much simpler here. Added a TODO for now.

+        copy->set_ssa_temp_index(flow_graph_->alloc_ssa_temp_index());
+        old->ReplaceUsesWith(copy);
+        (*idefs)[j] = copy;
+      }
+    }
+  }
+}
+
+
 static BlockEntryInstr* FindPreHeader(BlockEntryInstr* header) {
   for (intptr_t j = 0; j < header->PredecessorCount(); ++j) {
     BlockEntryInstr* candidate = header->PredecessorAt(j);
     if (header->dominator() == candidate) {
       return candidate;
     }
   }
   return NULL;
 }
 
@@ skipping 1242 matching lines @@
 // --------------------------------------------------------------------------
 // Analysis of blocks.  Called at most once per block.  The block is already
 // marked as reachable.  All instructions in the block are analyzed.
 void ConstantPropagator::VisitGraphEntry(GraphEntryInstr* block) {
   const GrowableArray<Definition*>& defs = *block->initial_definitions();
   for (intptr_t i = 0; i < defs.length(); ++i) {
     defs[i]->Accept(this);
   }
   ASSERT(ForwardInstructionIterator(block).Done());
 
-  SetReachable(block->normal_entry());
+  for (intptr_t i = 0; i < block->SuccessorCount(); ++i) {
+    SetReachable(block->SuccessorAt(i));

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

Hmm, this is a poor approximation.  Can you add a comment that a better one is
that the catch is reachable if the try entry is (actually, if a call inside the
try is).

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

Done.

+  }
 }
 
 
 void ConstantPropagator::VisitJoinEntry(JoinEntryInstr* block) {
   // Phis are visited when visiting Goto at a predecessor. See VisitGoto.
   for (ForwardInstructionIterator it(block); !it.Done(); it.Advance()) {
     it.Current()->Accept(this);
   }
 }
 
 
 void ConstantPropagator::VisitTargetEntry(TargetEntryInstr* block) {
   for (ForwardInstructionIterator it(block); !it.Done(); it.Advance()) {
     it.Current()->Accept(this);
   }
 }
 
 
 void ConstantPropagator::VisitCatchBlockEntry(CatchBlockEntryInstr* block) {
+  const GrowableArray<Definition*>& defs = *block->initial_definitions();
+  for (intptr_t i = 0; i < defs.length(); ++i) {
+    defs[i]->Accept(this);
+  }
   for (ForwardInstructionIterator it(block); !it.Done(); it.Advance()) {
     it.Current()->Accept(this);
   }
 }
 
 
 void ConstantPropagator::VisitParallelMove(ParallelMoveInstr* instr) {
   // Parallel moves have not yet been inserted in the graph.
   UNREACHABLE();
 }
@@ skipping 786 matching lines @@
       BlockEntryInstr* block = block_worklist_.RemoveLast();
       block->Accept(this);
     }
   }
 }
 
 
 void ConstantPropagator::VisitBranches() {
   GraphEntryInstr* entry = graph_->graph_entry();
   reachable_->Add(entry->preorder_number());
-  // TODO(fschneider): Handle CatchEntry.
-  reachable_->Add(entry->normal_entry()->preorder_number());
-  block_worklist_.Add(entry->normal_entry());
+  block_worklist_.Add(entry);
 
   while (!block_worklist_.is_empty()) {
     BlockEntryInstr* block = block_worklist_.RemoveLast();
+    if (block->IsGraphEntry()) {
+      for (intptr_t i = 0; i < block->SuccessorCount(); ++i) {
+        SetReachable(block->SuccessorAt(i));
+      }
+      continue;
+    }
     Instruction* last = block->last_instruction();
     if (last->IsGoto()) {
       SetReachable(last->AsGoto()->successor());
     } else if (last->IsBranch()) {
       BranchInstr* branch = last->AsBranch();
       // The current block must be reachable.
       ASSERT(reachable_->Contains(branch->GetBlock()->preorder_number()));
       if (branch->constant_target() != NULL) {
         // Found constant target computed by range analysis.
         if (branch->constant_target() == branch->true_successor()) {
@@ skipping 547 matching lines @@
   if (changed) {
     // We may have changed the block order and the dominator tree.
     flow_graph->DiscoverBlocks();
     GrowableArray<BitVector*> dominance_frontier;
     flow_graph->ComputeDominators(&dominance_frontier);
   }
 }
 
 
 }  // namespace dart