Optimize functions containing try-catch.

runtime/vm/flow_graph_allocator.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_allocator.h"
 
 #include "vm/bit_vector.h"
 #include "vm/intermediate_language.h"
 #include "vm/il_printer.h"
 #include "vm/flow_graph.h"
@@ skipping 165 matching lines @@
           Value* val = phi->InputAt(k);
           if (val->BindsToConstant()) continue;
 
           BlockEntryInstr* pred = block->PredecessorAt(k);
           const intptr_t use = val->definition()->ssa_temp_index();
           if (!kill_[pred->postorder_number()]->Contains(use)) {
             live_in_[pred->postorder_number()]->Add(use);
           }
         }
       }
+    } else if (block->IsCatchBlockEntry()) {
+      // Process initial definitions.

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

It's disconcerting that locals are treated so differently in the two different
liveness analyses.  In the other one, upwards exposed uses of variables in the
catch body add those variables to the live_in set.  In this one, the live_in set
is empty?

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

This deals with SSA values, similar to the initial definitions of the graph
entry.

The other one is changed to correctly deal with local variables inside try{}. I
simplified the changes to the variable liveness analysis.

+      CatchBlockEntryInstr* catch_entry = block->AsCatchBlockEntry();
+      for (intptr_t i = 0;
+           i < catch_entry->initial_definitions()->length();
+           i++) {
+        intptr_t vreg =
+            (*catch_entry->initial_definitions())[i]->ssa_temp_index();
+        kill_[catch_entry->postorder_number()]->Add(vreg);
+        live_in_[catch_entry->postorder_number()]->Remove(vreg);
+      }
     }
   }
 
   // Process initial definitions, ie, constants and incoming parameters.
   for (intptr_t i = 0; i < graph_entry_->initial_definitions()->length(); i++) {
     intptr_t vreg = (*graph_entry_->initial_definitions())[i]->ssa_temp_index();
     kill_[graph_entry_->postorder_number()]->Add(vreg);
     live_in_[graph_entry_->postorder_number()]->Remove(vreg);
   }
 
@@ skipping 43 matching lines @@
   ASSERT(hint != NULL);
   AddUse(pos, location_slot);
   uses_->set_hint(hint);
 }
 
 
 void LiveRange::AddUseInterval(intptr_t start, intptr_t end) {
   ASSERT(start < end);
 
   // Live ranges are being build by visiting instructions in post-order.
-  // This implies that use intervals will be perpended in a monotonically
+  // This implies that use intervals will be prepended in a monotonically
   // decreasing order.
   if (first_use_interval() != NULL) {
     // If the first use interval and the use interval we are adding
     // touch then we can just extend the first interval to cover their
     // union.
     if (start >= first_use_interval()->start()) {
       // The only case when we can add intervals with start greater than
       // start of an already created interval is BlockLocation.
       ASSERT((start == first_use_interval()->start()) ||
              (vreg() == kNoVirtualRegister));
@@ skipping 226 matching lines @@
       for (BitVector::Iterator it(liveness_.GetLiveInSetAt(i));
            !it.Done();
            it.Advance()) {
         LiveRange* range = GetLiveRange(it.Current());
         if (HasOnlyUnconstrainedUsesInLoop(range, block_info)) {
           range->MarkHasOnlyUnconstrainedUsesInLoop(block_info->loop_id());
         }
       }
     }
 
-    ConnectIncomingPhiMoves(block);
+    if (block->IsJoinEntry()) {
+      ConnectIncomingPhiMoves(block->AsJoinEntry());
+    } else if (block->IsCatchBlockEntry()) {
+      // Process initial definitions.
+      CatchBlockEntryInstr* catch_entry = block->AsCatchBlockEntry();
+      for (intptr_t i = 0;
+           i < catch_entry->initial_definitions()->length();
+           i++) {
+        Definition* defn = (*catch_entry->initial_definitions())[i];

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

All this code that is duplicated below should be moved into a function
ProcessInitialDefinition or the like.

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

Done.

+        LiveRange* range = GetLiveRange(defn->ssa_temp_index());
+        range->DefineAt(catch_entry->start_pos());  // Defined at block entry.
+        if (defn->IsParameter()) {
+          ParameterInstr* param = defn->AsParameter();
+          // Assert that copied and non-copied parameters are mutually
+          // exclusive. This might change in the future and, if so, the
+          // index will be wrong.
+          ASSERT((flow_graph_.num_copied_params() == 0) ||
+                 (flow_graph_.num_non_copied_params() == 0));
+          // Slot index for the leftmost copied parameter is 0.
+          intptr_t slot_index = param->index();
+          // Slot index for the rightmost fixed parameter is -1.
+          slot_index -= flow_graph_.num_non_copied_params();
+          range->set_assigned_location(Location::StackSlot(slot_index));
+          range->set_spill_slot(Location::StackSlot(slot_index));
+        } else {
+          ConstantInstr* constant = defn->AsConstant();
+          ASSERT(constant != NULL);
+          range->set_assigned_location(Location::Constant(constant->value()));
+          range->set_spill_slot(Location::Constant(constant->value()));
+        }
+        spill_slots_.Add(range->End());
+        quad_spill_slots_.Add(false);
+        AssignSafepoints(range);
+        range->finger()->Initialize(range);
+        UsePosition* use = range->finger()->FirstRegisterBeneficialUse(
+            catch_entry->start_pos());
+        if (use != NULL) {
+          LiveRange* tail =
+              SplitBetween(range, catch_entry->start_pos(), use->pos());
+          // Parameters and constants are tagged, so allocated to CPU registers.
+          CompleteRange(tail, Location::kRegister);
+        }
+        ConvertAllUses(range);
+        if (defn->IsParameter() && range->spill_slot().stack_index() >= 0) {
+          MarkAsObjectAtSafepoints(range);
+        }
+      }
+    }
   }
 
   // Process incoming parameters and constants.  Do this after all other
   // instructions so that safepoints for all calls have already been found.
   GraphEntryInstr* graph_entry = flow_graph_.graph_entry();
   for (intptr_t i = 0; i < graph_entry->initial_definitions()->length(); i++) {
     Definition* defn = (*graph_entry->initial_definitions())[i];
     LiveRange* range = GetLiveRange(defn->ssa_temp_index());
     range->AddUseInterval(graph_entry->start_pos(), graph_entry->end_pos());
     range->DefineAt(graph_entry->start_pos());
     if (defn->IsParameter()) {
       ParameterInstr* param = defn->AsParameter();
       // Assert that copied and non-copied parameters are mutually exclusive.
       // This might change in the future and, if so, the index will be wrong.
       ASSERT((flow_graph_.num_copied_params() == 0) ||
              (flow_graph_.num_non_copied_params() == 0));
       // Slot index for the leftmost copied parameter is 0.
       intptr_t slot_index = param->index();
       // Slot index for the rightmost fixed parameter is -1.
       slot_index -= flow_graph_.num_non_copied_params();
 
       range->set_assigned_location(Location::StackSlot(slot_index));
       range->set_spill_slot(Location::StackSlot(slot_index));
       if (flow_graph_.num_copied_params() > 0) {
-        ASSERT(spill_slots_.length() == slot_index);
         spill_slots_.Add(range->End());
         quad_spill_slots_.Add(false);
       }
     } else {
       ConstantInstr* constant = defn->AsConstant();
       ASSERT(constant != NULL);
       range->set_assigned_location(Location::Constant(constant->value()));
       range->set_spill_slot(Location::Constant(constant->value()));
     }
     AssignSafepoints(range);
@@ skipping 114 matching lines @@
     move->set_src(Location::PrefersRegister());
     move_idx++;
   }
 
   // Begin backward iteration with the instruction before the parallel
   // move.
   return goto_instr->previous();
 }
 
 
-void FlowGraphAllocator::ConnectIncomingPhiMoves(BlockEntryInstr* block) {
-  // If this block is a join we need to add destinations of phi
-  // resolution moves to phi's live range so that register allocator will
-  // fill them with moves.
-  JoinEntryInstr* join = block->AsJoinEntry();
-  if (join == NULL) return;
+void FlowGraphAllocator::ConnectIncomingPhiMoves(JoinEntryInstr* join) {
+  // For join blocks we need to add destinations of phi resolution moves
+  // to phi's live range so that register allocator will fill them with moves.
 
   // All uses are recorded at the start position in the block.
   const intptr_t pos = join->start_pos();
   const bool is_loop_header = BlockInfoAt(join->start_pos())->is_loop_header();
   intptr_t move_idx = 0;
   for (PhiIterator it(join); !it.Done(); it.Advance()) {
     PhiInstr* phi = it.Current();
     ASSERT(phi != NULL);
     const intptr_t vreg = phi->ssa_temp_index();
     ASSERT(vreg >= 0);
 
     // Expected shape of live range:
     //
     //                 B
     //      phi        [--------
     //
     LiveRange* range = GetLiveRange(vreg);
     range->DefineAt(pos);  // Shorten live range.
 
     if (is_loop_header) range->mark_loop_phi();
 
     for (intptr_t pred_idx = 0; pred_idx < phi->InputCount(); pred_idx++) {
-      BlockEntryInstr* pred = block->PredecessorAt(pred_idx);
+      BlockEntryInstr* pred = join->PredecessorAt(pred_idx);
       GotoInstr* goto_instr = pred->last_instruction()->AsGoto();
       ASSERT((goto_instr != NULL) && (goto_instr->HasParallelMove()));
       MoveOperands* move =
           goto_instr->parallel_move()->MoveOperandsAt(move_idx);
       move->set_dest(Location::PrefersRegister());
       range->AddUse(pos, move->dest_slot());
     }
 
     // All phi resolution moves are connected. Phi's live range is
     // complete.
@@ skipping 815 matching lines @@
   // Special care is taken to never allocate the same index to both
   // double and quad spill slots as it complicates disambiguation during
   // parallel move resolution.
   const bool need_quad = (register_kind_ == Location::kFpuRegister) &&
       ((range->representation() == kUnboxedFloat32x4) ||
        (range->representation() == kUnboxedUint32x4));
 
   // Search for a free spill slot among allocated: the value in it should be
   // dead and its type should match (e.g. it should not be a part of the quad if
   // we are allocating normal double slot).
-  intptr_t idx = 0;
+  // For CPU registers we need to take reserved slots for try-catch into
+  // account.
+  intptr_t idx = register_kind_ == Location::kRegister
+      ? flow_graph_.graph_entry()->fixed_slot_count()
+      : 0;
   for (; idx < spill_slots_.length(); idx++) {
     if ((need_quad == quad_spill_slots_[idx]) &&
         (spill_slots_[idx] <= start)) {
       break;
     }
   }
 
   if (idx == spill_slots_.length()) {
     // No free spill slot found. Allocate a new one.
     spill_slots_.Add(0);
@@ skipping 871 matching lines @@
   GraphEntryInstr* graph_entry = flow_graph_.graph_entry();
   for (intptr_t i = 0; i < graph_entry->initial_definitions()->length(); ++i) {
     Definition* def = (*graph_entry->initial_definitions())[i];
     value_representations_[def->ssa_temp_index()] = def->representation();
   }
 
   for (BlockIterator it = flow_graph_.reverse_postorder_iterator();
        !it.Done();
        it.Advance()) {
     BlockEntryInstr* block = it.Current();
+
+    // Catch entry.
+    if (block->IsCatchBlockEntry()) {
+      CatchBlockEntryInstr* catch_entry = block->AsCatchBlockEntry();
+      for (intptr_t i = 0;
+           i < catch_entry->initial_definitions()->length();
+           ++i) {
+        Definition* def = (*catch_entry->initial_definitions())[i];
+        value_representations_[def->ssa_temp_index()] = def->representation();
+      }
+    }
     // Phis.
     if (block->IsJoinEntry()) {
       JoinEntryInstr* join = block->AsJoinEntry();
       for (PhiIterator it(join); !it.Done(); it.Advance()) {
         PhiInstr* phi = it.Current();
         if ((phi != NULL) && (phi->ssa_temp_index() >= 0)) {
           value_representations_[phi->ssa_temp_index()] = phi->representation();
         }
       }
     }
@@ skipping 78 matching lines @@
     OS::Print("-- [after ssa allocator] ir [%s] -------------\n",
               function.ToFullyQualifiedCString());
     FlowGraphPrinter printer(flow_graph_, true);
     printer.PrintBlocks();
     OS::Print("----------------------------------------------\n");
   }
 }
 
 
 }  // namespace dart