Support inlining function containing throw in the optimizer.

runtime/vm/flow_graph_builder.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_builder.h"
 
 #include "lib/invocation_mirror.h"
 #include "vm/ast_printer.h"
 #include "vm/code_descriptors.h"
 #include "vm/dart_entry.h"
@@ skipping 111 matching lines @@
   exits_.Sort(LowestBlockIdFirst);
 }
 
 
 Definition* InlineExitCollector::JoinReturns(BlockEntryInstr** exit_block,
                                              Instruction** last_instruction) {
   // First sort the list of exits by block id (caching return instruction
   // block entries as a side effect).
   SortExits();
   intptr_t num_exits = exits_.length();
-  if (num_exits == 0) {
-    // TODO(zerny): Add support for non-local exits, such as throw.
-    UNREACHABLE();
-    return NULL;
-  } else if (num_exits == 1) {
+  if (num_exits == 1) {
     ReturnAt(0)->UnuseAllInputs();
     *exit_block = ExitBlockAt(0);
     *last_instruction = LastInstructionAt(0);
     return call_->HasUses() ? ValueAt(0)->definition() : NULL;
   } else {
+    ASSERT(num_exits > 1);
     // Create a join of the returns.
     intptr_t join_id = caller_graph_->max_block_id() + 1;
     caller_graph_->set_max_block_id(join_id);
     JoinEntryInstr* join =
         new JoinEntryInstr(join_id, CatchClauseNode::kInvalidTryIndex);
     join->InheritDeoptTargetAfter(call_);
 
     // The dominator set of the join is the intersection of the dominator
     // sets of all the predecessors.  If we keep the dominator sets ordered
     // by height in the dominator tree, we can also get the immediate
@@ skipping 78 matching lines @@
 
 
 void InlineExitCollector::ReplaceCall(TargetEntryInstr* callee_entry) {
   ASSERT(call_->previous() != NULL);
   ASSERT(call_->next() != NULL);
   BlockEntryInstr* call_block = call_->GetBlock();
 
   // Insert the callee graph into the caller graph.
   BlockEntryInstr* callee_exit = NULL;
   Instruction* callee_last_instruction = NULL;
-  Definition* callee_result = JoinReturns(&callee_exit,
-                                          &callee_last_instruction);
-  if (callee_result != NULL) {
-    call_->ReplaceUsesWith(callee_result);
+
+  if (exits_.length() == 0) {
+    // Handle the case when there are no normal return exits from the callee
+    // (i.e. the callee unconditionally throws) by inserting an artificial
+    // branch (true === true).
+    // The true successor is the inlined body, the false successor
+    // goes to the rest of the caller graph. It is removed as unreachable code
+    // by the constant propagation.
+    TargetEntryInstr* false_block =
+        new TargetEntryInstr(caller_graph_->allocate_block_id(),
+                             call_block->try_index());
+    false_block->LinkTo(call_->next());

[Kevin Millikin (Google), 2013/05/22 12:05:11]

I guess it's safe that false_block does not have a deopt target, because we know
it's unreachable code.  For hygiene I would call InheritDeoptTarget for it.  I
think the right target is the deopt target after the call.

[Florian Schneider, 2013/05/24 12:51:56]

Done.

+    call_block->ReplaceAsPredecessorWith(false_block);
+
+    ConstantInstr* true_const = caller_graph_->GetConstant(Bool::True());
+    Value* left = new Value(true_const);
+    Value* right = new Value(true_const);
+    true_const->AddInputUse(left);
+    true_const->AddInputUse(right);
+    BranchInstr* branch =
+        new BranchInstr(new StrictCompareInstr(Token::kEQ_STRICT, left, right));
+    branch->InheritDeoptTarget(call_);
+
+    call_->previous()->LinkTo(branch);

[Kevin Millikin (Google), 2013/05/22 12:05:11]

You can call

AppendInstruction(call_->previous(), branch);

That allows you to skip the AddInputUse calls here for left and right, then they
probably don't need to be named. 

[Florian Schneider, 2013/05/24 12:51:56]

Done. Added AppendInstruction helper to the Instruction class.

+    call_block->set_last_instruction(branch);
+
+    *branch->true_successor_address() = callee_entry;
+    *branch->false_successor_address() = false_block;
+
+    // Update dominator tree.
+    call_block->AddDominatedBlock(callee_entry);
+    call_block->AddDominatedBlock(false_block);
+
+    // The graph entry (if present) is not in the graph anymore.

[Kevin Millikin (Google), 2013/05/22 12:05:11]

This is the same as the last code in the else block.  Move it out of the
if/else?

[Florian Schneider, 2013/05/24 12:51:56]

Done.

+    // Remove it and the original call from use lists.
+    if (callee_entry->PredecessorCount() > 0) {
+      callee_entry->PredecessorAt(0)->AsGraphEntry()->UnuseAllInputs();
+    }
+    call_->UnuseAllInputs();
+  } else {

[Florian Schneider, 2013/05/22 11:40:40]

The diff is confused here. This part of the if-statement is taken unchanged from
the original function.

+    Definition* callee_result = JoinReturns(&callee_exit,
+                                            &callee_last_instruction);
+    if (callee_result != NULL) {
+      call_->ReplaceUsesWith(callee_result);
+    }
+    if (callee_last_instruction == callee_entry) {
+      // There are no instructions in the inlined function (e.g., it might be
+      // a return of a parameter or a return of a constant defined in the
+      // initial definitions).
+      call_->previous()->LinkTo(call_->next());
+    } else {
+      call_->previous()->LinkTo(callee_entry->next());
+      callee_last_instruction->LinkTo(call_->next());
+    }
+    if (callee_exit != callee_entry) {
+      // In case of control flow, locally update the predecessors, phis and
+      // dominator tree.
+      //
+      // Pictorially, the graph structure is:
+      //
+      //   Bc : call_block      Bi : callee_entry
+      //     before_call          inlined_head
+      //     call               ... other blocks ...
+      //     after_call         Be : callee_exit
+      //                          inlined_foot
+      // And becomes:
+      //
+      //   Bc : call_block
+      //     before_call
+      //     inlined_head
+      //   ... other blocks ...
+      //   Be : callee_exit
+      //    inlined_foot
+      //    after_call
+      //
+      // For successors of 'after_call', the call block (Bc) is replaced as a
+      // predecessor by the callee exit (Be).
+      call_block->ReplaceAsPredecessorWith(callee_exit);
+      // For successors of 'inlined_head', the callee entry (Bi) is replaced
+      // as a predecessor by the call block (Bc).
+      callee_entry->ReplaceAsPredecessorWith(call_block);
+
+      // The callee exit is now the immediate dominator of blocks whose
+      // immediate dominator was the call block.
+      ASSERT(callee_exit->dominated_blocks().is_empty());
+      for (intptr_t i = 0; i < call_block->dominated_blocks().length(); ++i) {
+        BlockEntryInstr* block = call_block->dominated_blocks()[i];
+        callee_exit->AddDominatedBlock(block);
+      }
+      // The call block is now the immediate dominator of blocks whose
+      // immediate dominator was the callee entry.
+      call_block->ClearDominatedBlocks();
+      for (intptr_t i = 0; i < callee_entry->dominated_blocks().length(); ++i) {
+        BlockEntryInstr* block = callee_entry->dominated_blocks()[i];
+        call_block->AddDominatedBlock(block);
+      }
+    }
+
+    // Neither call nor callee entry nor the graph entry (if present) are in the
+    // graph at this point. Remove them from use lists.
+    callee_entry->UnuseAllInputs();
+    if (callee_entry->PredecessorCount() > 0) {
+      callee_entry->PredecessorAt(0)->AsGraphEntry()->UnuseAllInputs();
+    }
+    call_->UnuseAllInputs();
   }
-  if (callee_last_instruction == callee_entry) {
-    // There are no instructions in the inlined function (e.g., it might be
-    // a return of a parameter or a return of a constant defined in the
-    // initial definitions).
-    call_->previous()->LinkTo(call_->next());
-  } else {
-    call_->previous()->LinkTo(callee_entry->next());
-    callee_last_instruction->LinkTo(call_->next());
-  }
-  if (callee_exit != callee_entry) {
-    // In case of control flow, locally update the predecessors, phis and
-    // dominator tree.
-    //
-    // Pictorially, the graph structure is:
-    //
-    //   Bc : call_block      Bi : callee_entry
-    //     before_call          inlined_head
-    //     call               ... other blocks ...
-    //     after_call         Be : callee_exit
-    //                          inlined_foot
-    // And becomes:
-    //
-    //   Bc : call_block
-    //     before_call
-    //     inlined_head
-    //   ... other blocks ...
-    //   Be : callee_exit
-    //    inlined_foot
-    //    after_call
-    //
-    // For successors of 'after_call', the call block (Bc) is replaced as a
-    // predecessor by the callee exit (Be).
-    call_block->ReplaceAsPredecessorWith(callee_exit);
-    // For successors of 'inlined_head', the callee entry (Bi) is replaced
-    // as a predecessor by the call block (Bc).
-    callee_entry->ReplaceAsPredecessorWith(call_block);
-
-    // The callee exit is now the immediate dominator of blocks whose
-    // immediate dominator was the call block.
-    ASSERT(callee_exit->dominated_blocks().is_empty());
-    for (intptr_t i = 0; i < call_block->dominated_blocks().length(); ++i) {
-      BlockEntryInstr* block = call_block->dominated_blocks()[i];
-      callee_exit->AddDominatedBlock(block);
-    }
-    // The call block is now the immediate dominator of blocks whose
-    // immediate dominator was the callee entry.
-    call_block->ClearDominatedBlocks();
-    for (intptr_t i = 0; i < callee_entry->dominated_blocks().length(); ++i) {
-      BlockEntryInstr* block = callee_entry->dominated_blocks()[i];
-      call_block->AddDominatedBlock(block);
-    }
-  }
-
-  // Neither call nor callee entry nor the graph entry (if present) are in the
-  // graph at this point. Remove them from use lists.
-  callee_entry->UnuseAllInputs();
-  if (callee_entry->PredecessorCount() > 0) {
-    callee_entry->PredecessorAt(0)->AsGraphEntry()->UnuseAllInputs();
-  }
-  call_->UnuseAllInputs();
 }
 
 
 void EffectGraphVisitor::Append(const EffectGraphVisitor& other_fragment) {
   ASSERT(is_open());
   if (other_fragment.is_empty()) return;
   if (is_empty()) {
     entry_ = other_fragment.entry();
     exit_ = other_fragment.exit();
   } else {
@@ skipping 2971 matching lines @@
                               Resolver::kIsQualified));
   ASSERT(!func.IsNull());
   return new StaticCallInstr(token_pos,
                              func,
                              Array::ZoneHandle(),  // No names.
                              arguments);
 }
 
 
 void EffectGraphVisitor::BuildThrowNode(ThrowNode* node) {
-  // TODO(kmillikin) non-local control flow is not handled correctly
-  // by the inliner.
-  InlineBailout("EffectGraphVisitor::BuildThrowNode (exception)");
   ValueGraphVisitor for_exception(owner(), temp_index());
   node->exception()->Visit(&for_exception);
   Append(for_exception);
   PushArgument(for_exception.value());
   Instruction* instr = NULL;
   if (node->stacktrace() == NULL) {
     instr = new ThrowInstr(node->token_pos());
   } else {
     ValueGraphVisitor for_stack_trace(owner(), temp_index());
     node->stacktrace()->Visit(&for_stack_trace);
@@ skipping 86 matching lines @@
   intptr_t len = OS::SNPrint(NULL, 0, kFormat, function_name, reason) + 1;
   char* chars = Isolate::Current()->current_zone()->Alloc<char>(len);
   OS::SNPrint(chars, len, kFormat, function_name, reason);
   const Error& error = Error::Handle(
       LanguageError::New(String::Handle(String::New(chars))));
   Isolate::Current()->long_jump_base()->Jump(1, error);
 }
 
 
 }  // namespace dart