runtime/vm/compiler/frontend/flow_graph_builder.cc - sdk.git - Git at Google

 // 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/compiler/frontend/flow_graph_builder.h"

 #include "vm/compiler/backend/branch_optimizer.h"
 #include "vm/compiler/backend/flow_graph.h"
 #include "vm/compiler/backend/il.h"
 #include "vm/compiler/compiler_timings.h"
 #include "vm/compiler/frontend/kernel_to_il.h"
 #include "vm/object.h"
 #include "vm/zone.h"

 namespace dart {

 // Quick access to the locally defined zone() method.
 #define Z (zone())

 // TODO(srdjan): Allow compiler to add constants as they are encountered in
 // the compilation.
 const double kCommonDoubleConstants[] = {
     -1.0, -0.5, -0.1, 0.0, 0.1, 0.5, 1.0, 2.0, 4.0, 5.0, 10.0, 20.0, 30.0, 64.0,
     255.0, NAN,
     // From dart:math
     2.718281828459045, 2.302585092994046, 0.6931471805599453,
     1.4426950408889634, 0.4342944819032518, 3.1415926535897932,
     0.7071067811865476, 1.4142135623730951};

 uword FindDoubleConstant(double value) {
   intptr_t len = sizeof(kCommonDoubleConstants) / sizeof(double);  // NOLINT
   for (intptr_t i = 0; i < len; i++) {
     if (Utils::DoublesBitEqual(value, kCommonDoubleConstants[i])) {
       return reinterpret_cast<uword>(&kCommonDoubleConstants[i]);
     }
   }
   return 0;
 }

 void InlineExitCollector::PrepareGraphs(FlowGraph* callee_graph) {
   COMPILER_TIMINGS_TIMER_SCOPE(callee_graph->thread(), PrepareGraphs);
   ASSERT(callee_graph->graph_entry()->SuccessorCount() == 1);
   ASSERT(callee_graph->max_block_id() > caller_graph_->max_block_id());
   ASSERT(callee_graph->max_virtual_register_number() >
          caller_graph_->max_virtual_register_number());

   // Adjust the caller's maximum block id and current SSA temp index.
   caller_graph_->set_max_block_id(callee_graph->max_block_id());
   caller_graph_->set_current_ssa_temp_index(
       callee_graph->max_virtual_register_number());

   // Attach the outer environment on each instruction in the callee graph.
   ASSERT(call_->env() != NULL);
   ASSERT(call_->deopt_id() != DeoptId::kNone);

   auto zone = callee_graph->zone();
   auto env = call_->env();

   const intptr_t outer_deopt_id = call_->deopt_id();
   // Scale the edge weights by the call count for the inlined function.
   double scale_factor = 1.0;
   if (caller_graph_->graph_entry()->entry_count() != 0) {
     scale_factor =
         static_cast<double>(call_->CallCount()) /
         static_cast<double>(caller_graph_->graph_entry()->entry_count());
   }
   for (BlockIterator block_it = callee_graph->postorder_iterator();
        !block_it.Done(); block_it.Advance()) {
     BlockEntryInstr* block = block_it.Current();
     if (block->IsTargetEntry()) {
       block->AsTargetEntry()->adjust_edge_weight(scale_factor);
     }
     Instruction* instr = block;
     if (block->env() != nullptr) {
       env->DeepCopyToOuter(zone, block, outer_deopt_id);
     }
     for (ForwardInstructionIterator it(block); !it.Done(); it.Advance()) {
       instr = it.Current();
       // TODO(zerny): Avoid creating unnecessary environments. Note that some
       // optimizations need deoptimization info for non-deoptable instructions,
       // eg, LICM on GOTOs.
       if (instr->env() != nullptr) {
         env->DeepCopyToOuter(zone, instr, outer_deopt_id);
       }
     }
     if (instr->IsGoto()) {
       instr->AsGoto()->adjust_edge_weight(scale_factor);
     }
   }

   RemoveUnreachableExits(callee_graph);
 }

 void InlineExitCollector::AddExit(ReturnInstr* exit) {
   Data data = {NULL, exit};
   exits_.Add(data);
 }

 void InlineExitCollector::Union(const InlineExitCollector* other) {
   // It doesn't make sense to combine different calls or calls from
   // different graphs.
   ASSERT(caller_graph_ == other->caller_graph_);
   ASSERT(call_ == other->call_);
   exits_.AddArray(other->exits_);
 }

 int InlineExitCollector::LowestBlockIdFirst(const Data* a, const Data* b) {
   return (a->exit_block->block_id() - b->exit_block->block_id());
 }

 void InlineExitCollector::RemoveUnreachableExits(FlowGraph* callee_graph) {
   const GrowableArray<BlockEntryInstr*>& postorder = callee_graph->postorder();
   int j = 0;
   for (int i = 0; i < exits_.length(); ++i) {
     BlockEntryInstr* block = exits_[i].exit_return->GetBlock();
     if ((block != NULL) && (0 <= block->postorder_number()) &&
         (block->postorder_number() < postorder.length()) &&
         (postorder[block->postorder_number()] == block)) {
       if (i != j) {
         exits_[j] = exits_[i];
       }
       j++;
     }
   }
   exits_.TruncateTo(j);
 }

 void InlineExitCollector::SortExits() {
   // Assign block entries here because we did not necessarily know them when
   // the return exit was added to the array.
   for (int i = 0; i < exits_.length(); ++i) {
     exits_[i].exit_block = exits_[i].exit_return->GetBlock();
   }
   exits_.Sort(LowestBlockIdFirst);
 }

 Definition* InlineExitCollector::JoinReturns(BlockEntryInstr** exit_block,
                                              Instruction** last_instruction,
                                              intptr_t try_index) {
   // 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 == 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 (Z) JoinEntryInstr(
         join_id, try_index, CompilerState::Current().GetNextDeoptId());

     // 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
     // dominator of the join node from the intersection.
     //
     // block_dominators is the dominator set for each block, ordered from
     // the immediate dominator to the root of the dominator tree.  This is
     // the order we collect them in (adding at the end).
     //
     // join_dominators is the join's dominators ordered from the root of the
     // dominator tree to the immediate dominator.  This order supports
     // removing during intersection by truncating the list.
     GrowableArray<BlockEntryInstr*> block_dominators;
     GrowableArray<BlockEntryInstr*> join_dominators;
     for (intptr_t i = 0; i < num_exits; ++i) {
       // Add the control-flow edge.
       GotoInstr* goto_instr =
           new (Z) GotoInstr(join, CompilerState::Current().GetNextDeoptId());
       goto_instr->InheritDeoptTarget(zone(), ReturnAt(i));
       LastInstructionAt(i)->LinkTo(goto_instr);
       ExitBlockAt(i)->set_last_instruction(LastInstructionAt(i)->next());
       join->predecessors_.Add(ExitBlockAt(i));

       // Collect the block's dominators.
       block_dominators.Clear();
       BlockEntryInstr* dominator = ExitBlockAt(i)->dominator();
       while (dominator != NULL) {
         block_dominators.Add(dominator);
         dominator = dominator->dominator();
       }

       if (i == 0) {
         // The initial dominator set is the first predecessor's dominator
         // set.  Reverse it.
         for (intptr_t j = block_dominators.length() - 1; j >= 0; --j) {
           join_dominators.Add(block_dominators[j]);
         }
       } else {
         // Intersect the block's dominators with the join's dominators so far.
         intptr_t last = block_dominators.length() - 1;
         for (intptr_t j = 0; j < join_dominators.length(); ++j) {
           intptr_t k = last - j;  // Corresponding index in block_dominators.
           if ((k < 0) || (join_dominators[j] != block_dominators[k])) {
             // We either exhausted the dominators for this block before
             // exhausting the current intersection, or else we found a block
             // on the path from the root of the tree that is not in common.
             // I.e., there cannot be an empty set of dominators.
             ASSERT(j > 0);
             join_dominators.TruncateTo(j);
             break;
           }
         }
       }
     }
     // The immediate dominator of the join is the last one in the ordered
     // intersection.
     join_dominators.Last()->AddDominatedBlock(join);
     *exit_block = join;
     *last_instruction = join;

     // If the call has uses, create a phi of the returns.
     if (call_->HasUses()) {
       // Add a phi of the return values.
       PhiInstr* phi = new (Z) PhiInstr(join, num_exits);
       caller_graph_->AllocateSSAIndexes(phi);
       phi->mark_alive();
       for (intptr_t i = 0; i < num_exits; ++i) {
         ReturnAt(i)->RemoveEnvironment();
         phi->SetInputAt(i, ValueAt(i));
       }
       join->InsertPhi(phi);
       join->InheritDeoptTargetAfter(caller_graph_, call_, phi);
       return phi;
     } else {
       // In the case that the result is unused, remove the return value uses
       // from their definition's use list.
       for (intptr_t i = 0; i < num_exits; ++i) {
         ReturnAt(i)->UnuseAllInputs();
       }
       join->InheritDeoptTargetAfter(caller_graph_, call_, NULL);
       return NULL;
     }
   }
 }

 void InlineExitCollector::ReplaceCall(BlockEntryInstr* 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;

   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 (Z) TargetEntryInstr(
         caller_graph_->allocate_block_id(), call_block->try_index(),
         CompilerState::Current().GetNextDeoptId());
     false_block->InheritDeoptTargetAfter(caller_graph_, call_, NULL);
     false_block->LinkTo(call_->next());
     call_block->ReplaceAsPredecessorWith(false_block);

     ConstantInstr* true_const = caller_graph_->GetConstant(Bool::True());
     BranchInstr* branch = new (Z) BranchInstr(
         new (Z) StrictCompareInstr(InstructionSource(), Token::kEQ_STRICT,
                                    new (Z) Value(true_const),
                                    new (Z) Value(true_const), false,
                                    CompilerState::Current().GetNextDeoptId()),
         CompilerState::Current().GetNextDeoptId());  // No number check.
     branch->InheritDeoptTarget(zone(), call_);

     auto true_target = BranchSimplifier::ToTargetEntry(zone(), callee_entry);
     callee_entry->ReplaceAsPredecessorWith(true_target);

     *branch->true_successor_address() = true_target;
     *branch->false_successor_address() = false_block;

     call_->previous()->AppendInstruction(branch);
     call_block->set_last_instruction(branch);

     // Replace uses of the return value with sentinel constant to maintain
     // valid SSA form - even though the rest of the caller is unreachable.
     call_->ReplaceUsesWith(caller_graph_->GetConstant(Object::sentinel()));

     // Update dominator tree.
     for (intptr_t i = 0, n = callee_entry->dominated_blocks().length(); i < n;
          i++) {
       BlockEntryInstr* block = callee_entry->dominated_blocks()[i];
       true_target->AddDominatedBlock(block);
     }
     for (intptr_t i = 0, n = call_block->dominated_blocks().length(); i < n;
          i++) {
       BlockEntryInstr* block = call_block->dominated_blocks()[i];
       false_block->AddDominatedBlock(block);
     }
     call_block->ClearDominatedBlocks();
     call_block->AddDominatedBlock(true_target);
     call_block->AddDominatedBlock(false_block);

   } else {
     Definition* callee_result = JoinReturns(
         &callee_exit, &callee_last_instruction, call_block->try_index());
     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);
       }
     }

     // Callee entry in not in the graph anymore. Remove it from use lists.
     callee_entry->UnuseAllInputs();
   }
   // Neither call nor the graph entry (if present) are in the
   // graph at this point. Remove them from use lists.
   if (callee_entry->PredecessorCount() > 0) {
     callee_entry->PredecessorAt(0)->AsGraphEntry()->UnuseAllInputs();
   }
   call_->UnuseAllInputs();
 }

 bool SimpleInstanceOfType(const AbstractType& type) {
   // Bail if the type is still uninstantiated at compile time.
   if (!type.IsInstantiated()) return false;

   // Bail if the type is a function or a Dart Function type.
   if (type.IsFunctionType() || type.IsDartFunctionType()) return false;

   ASSERT(type.HasTypeClass());
   const Class& type_class = Class::Handle(type.type_class());

   // Bail if the type has any type parameters.
   if (type_class.IsGeneric()) {
     // If the interface type we check against is generic but has all-dynamic
     // type arguments, then we can still use the _simpleInstanceOf
     // implementation (see also runtime/lib/object.cc:Object_SimpleInstanceOf).
     const auto& rare_type = AbstractType::Handle(type_class.RareType());
     // TODO(regis): Revisit the usage of TypeEquality::kSyntactical when
     // implementing strong mode.
     return rare_type.IsEquivalent(type, TypeEquality::kSyntactical);
   }

   // Finally a simple class for instance of checking.
   return true;
 }

 }  // namespace dart
	// 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/compiler/frontend/flow_graph_builder.h"

	#include "vm/compiler/backend/branch_optimizer.h"
	#include "vm/compiler/backend/flow_graph.h"
	#include "vm/compiler/backend/il.h"
	#include "vm/compiler/compiler_timings.h"
	#include "vm/compiler/frontend/kernel_to_il.h"
	#include "vm/object.h"
	#include "vm/zone.h"

	namespace dart {

	// Quick access to the locally defined zone() method.
	#define Z (zone())

	// TODO(srdjan): Allow compiler to add constants as they are encountered in
	// the compilation.
	const double kCommonDoubleConstants[] = {
	-1.0, -0.5, -0.1, 0.0, 0.1, 0.5, 1.0, 2.0, 4.0, 5.0, 10.0, 20.0, 30.0, 64.0,
	255.0, NAN,
	// From dart:math
	2.718281828459045, 2.302585092994046, 0.6931471805599453,
	1.4426950408889634, 0.4342944819032518, 3.1415926535897932,
	0.7071067811865476, 1.4142135623730951};

	uword FindDoubleConstant(double value) {
	intptr_t len = sizeof(kCommonDoubleConstants) / sizeof(double); // NOLINT
	for (intptr_t i = 0; i < len; i++) {
	if (Utils::DoublesBitEqual(value, kCommonDoubleConstants[i])) {
	return reinterpret_cast<uword>(&kCommonDoubleConstants[i]);
	}
	}
	return 0;
	}

	void InlineExitCollector::PrepareGraphs(FlowGraph* callee_graph) {
	COMPILER_TIMINGS_TIMER_SCOPE(callee_graph->thread(), PrepareGraphs);
	ASSERT(callee_graph->graph_entry()->SuccessorCount() == 1);
	ASSERT(callee_graph->max_block_id() > caller_graph_->max_block_id());
	ASSERT(callee_graph->max_virtual_register_number() >
	caller_graph_->max_virtual_register_number());

	// Adjust the caller's maximum block id and current SSA temp index.
	caller_graph_->set_max_block_id(callee_graph->max_block_id());
	caller_graph_->set_current_ssa_temp_index(
	callee_graph->max_virtual_register_number());

	// Attach the outer environment on each instruction in the callee graph.
	ASSERT(call_->env() != NULL);
	ASSERT(call_->deopt_id() != DeoptId::kNone);

	auto zone = callee_graph->zone();
	auto env = call_->env();

	const intptr_t outer_deopt_id = call_->deopt_id();
	// Scale the edge weights by the call count for the inlined function.
	double scale_factor = 1.0;
	if (caller_graph_->graph_entry()->entry_count() != 0) {
	scale_factor =
	static_cast<double>(call_->CallCount()) /
	static_cast<double>(caller_graph_->graph_entry()->entry_count());
	}
	for (BlockIterator block_it = callee_graph->postorder_iterator();
	!block_it.Done(); block_it.Advance()) {
	BlockEntryInstr* block = block_it.Current();
	if (block->IsTargetEntry()) {
	block->AsTargetEntry()->adjust_edge_weight(scale_factor);
	}
	Instruction* instr = block;
	if (block->env() != nullptr) {
	env->DeepCopyToOuter(zone, block, outer_deopt_id);
	}
	for (ForwardInstructionIterator it(block); !it.Done(); it.Advance()) {
	instr = it.Current();
	// TODO(zerny): Avoid creating unnecessary environments. Note that some
	// optimizations need deoptimization info for non-deoptable instructions,
	// eg, LICM on GOTOs.
	if (instr->env() != nullptr) {
	env->DeepCopyToOuter(zone, instr, outer_deopt_id);
	}
	}
	if (instr->IsGoto()) {
	instr->AsGoto()->adjust_edge_weight(scale_factor);
	}
	}

	RemoveUnreachableExits(callee_graph);
	}

	void InlineExitCollector::AddExit(ReturnInstr* exit) {
	Data data = {NULL, exit};
	exits_.Add(data);
	}

	void InlineExitCollector::Union(const InlineExitCollector* other) {
	// It doesn't make sense to combine different calls or calls from
	// different graphs.
	ASSERT(caller_graph_ == other->caller_graph_);
	ASSERT(call_ == other->call_);
	exits_.AddArray(other->exits_);
	}

	int InlineExitCollector::LowestBlockIdFirst(const Data* a, const Data* b) {
	return (a->exit_block->block_id() - b->exit_block->block_id());
	}

	void InlineExitCollector::RemoveUnreachableExits(FlowGraph* callee_graph) {
	const GrowableArray<BlockEntryInstr*>& postorder = callee_graph->postorder();
	int j = 0;
	for (int i = 0; i < exits_.length(); ++i) {
	BlockEntryInstr* block = exits_[i].exit_return->GetBlock();
	if ((block != NULL) && (0 <= block->postorder_number()) &&
	(block->postorder_number() < postorder.length()) &&
	(postorder[block->postorder_number()] == block)) {
	if (i != j) {
	exits_[j] = exits_[i];
	}
	j++;
	}
	}
	exits_.TruncateTo(j);
	}

	void InlineExitCollector::SortExits() {
	// Assign block entries here because we did not necessarily know them when
	// the return exit was added to the array.
	for (int i = 0; i < exits_.length(); ++i) {
	exits_[i].exit_block = exits_[i].exit_return->GetBlock();
	}
	exits_.Sort(LowestBlockIdFirst);
	}

	Definition* InlineExitCollector::JoinReturns(BlockEntryInstr** exit_block,
	Instruction** last_instruction,
	intptr_t try_index) {
	// 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 == 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 (Z) JoinEntryInstr(
	join_id, try_index, CompilerState::Current().GetNextDeoptId());

	// 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
	// dominator of the join node from the intersection.
	//
	// block_dominators is the dominator set for each block, ordered from
	// the immediate dominator to the root of the dominator tree. This is
	// the order we collect them in (adding at the end).
	//
	// join_dominators is the join's dominators ordered from the root of the
	// dominator tree to the immediate dominator. This order supports
	// removing during intersection by truncating the list.
	GrowableArray<BlockEntryInstr*> block_dominators;
	GrowableArray<BlockEntryInstr*> join_dominators;
	for (intptr_t i = 0; i < num_exits; ++i) {
	// Add the control-flow edge.
	GotoInstr* goto_instr =
	new (Z) GotoInstr(join, CompilerState::Current().GetNextDeoptId());
	goto_instr->InheritDeoptTarget(zone(), ReturnAt(i));
	LastInstructionAt(i)->LinkTo(goto_instr);
	ExitBlockAt(i)->set_last_instruction(LastInstructionAt(i)->next());
	join->predecessors_.Add(ExitBlockAt(i));

	// Collect the block's dominators.
	block_dominators.Clear();
	BlockEntryInstr* dominator = ExitBlockAt(i)->dominator();
	while (dominator != NULL) {
	block_dominators.Add(dominator);
	dominator = dominator->dominator();
	}

	if (i == 0) {
	// The initial dominator set is the first predecessor's dominator
	// set. Reverse it.
	for (intptr_t j = block_dominators.length() - 1; j >= 0; --j) {
	join_dominators.Add(block_dominators[j]);
	}
	} else {
	// Intersect the block's dominators with the join's dominators so far.
	intptr_t last = block_dominators.length() - 1;
	for (intptr_t j = 0; j < join_dominators.length(); ++j) {
	intptr_t k = last - j; // Corresponding index in block_dominators.
	if ((k < 0) \|\| (join_dominators[j] != block_dominators[k])) {
	// We either exhausted the dominators for this block before
	// exhausting the current intersection, or else we found a block
	// on the path from the root of the tree that is not in common.
	// I.e., there cannot be an empty set of dominators.
	ASSERT(j > 0);
	join_dominators.TruncateTo(j);
	break;
	}
	}
	}
	}
	// The immediate dominator of the join is the last one in the ordered
	// intersection.
	join_dominators.Last()->AddDominatedBlock(join);
	*exit_block = join;
	*last_instruction = join;

	// If the call has uses, create a phi of the returns.
	if (call_->HasUses()) {
	// Add a phi of the return values.
	PhiInstr* phi = new (Z) PhiInstr(join, num_exits);
	caller_graph_->AllocateSSAIndexes(phi);
	phi->mark_alive();
	for (intptr_t i = 0; i < num_exits; ++i) {
	ReturnAt(i)->RemoveEnvironment();
	phi->SetInputAt(i, ValueAt(i));
	}
	join->InsertPhi(phi);
	join->InheritDeoptTargetAfter(caller_graph_, call_, phi);
	return phi;
	} else {
	// In the case that the result is unused, remove the return value uses
	// from their definition's use list.
	for (intptr_t i = 0; i < num_exits; ++i) {
	ReturnAt(i)->UnuseAllInputs();
	}
	join->InheritDeoptTargetAfter(caller_graph_, call_, NULL);
	return NULL;
	}
	}
	}

	void InlineExitCollector::ReplaceCall(BlockEntryInstr* 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;

	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 (Z) TargetEntryInstr(
	caller_graph_->allocate_block_id(), call_block->try_index(),
	CompilerState::Current().GetNextDeoptId());
	false_block->InheritDeoptTargetAfter(caller_graph_, call_, NULL);
	false_block->LinkTo(call_->next());
	call_block->ReplaceAsPredecessorWith(false_block);

	ConstantInstr* true_const = caller_graph_->GetConstant(Bool::True());
	BranchInstr* branch = new (Z) BranchInstr(
	new (Z) StrictCompareInstr(InstructionSource(), Token::kEQ_STRICT,
	new (Z) Value(true_const),
	new (Z) Value(true_const), false,
	CompilerState::Current().GetNextDeoptId()),
	CompilerState::Current().GetNextDeoptId()); // No number check.
	branch->InheritDeoptTarget(zone(), call_);

	auto true_target = BranchSimplifier::ToTargetEntry(zone(), callee_entry);
	callee_entry->ReplaceAsPredecessorWith(true_target);

	*branch->true_successor_address() = true_target;
	*branch->false_successor_address() = false_block;

	call_->previous()->AppendInstruction(branch);
	call_block->set_last_instruction(branch);

	// Replace uses of the return value with sentinel constant to maintain
	// valid SSA form - even though the rest of the caller is unreachable.
	call_->ReplaceUsesWith(caller_graph_->GetConstant(Object::sentinel()));

	// Update dominator tree.
	for (intptr_t i = 0, n = callee_entry->dominated_blocks().length(); i < n;
	i++) {
	BlockEntryInstr* block = callee_entry->dominated_blocks()[i];
	true_target->AddDominatedBlock(block);
	}
	for (intptr_t i = 0, n = call_block->dominated_blocks().length(); i < n;
	i++) {
	BlockEntryInstr* block = call_block->dominated_blocks()[i];
	false_block->AddDominatedBlock(block);
	}
	call_block->ClearDominatedBlocks();
	call_block->AddDominatedBlock(true_target);
	call_block->AddDominatedBlock(false_block);

	} else {
	Definition* callee_result = JoinReturns(
	&callee_exit, &callee_last_instruction, call_block->try_index());
	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);
	}
	}

	// Callee entry in not in the graph anymore. Remove it from use lists.
	callee_entry->UnuseAllInputs();
	}
	// Neither call nor the graph entry (if present) are in the
	// graph at this point. Remove them from use lists.
	if (callee_entry->PredecessorCount() > 0) {
	callee_entry->PredecessorAt(0)->AsGraphEntry()->UnuseAllInputs();
	}
	call_->UnuseAllInputs();
	}

	bool SimpleInstanceOfType(const AbstractType& type) {
	// Bail if the type is still uninstantiated at compile time.
	if (!type.IsInstantiated()) return false;

	// Bail if the type is a function or a Dart Function type.
	if (type.IsFunctionType() \|\| type.IsDartFunctionType()) return false;

	ASSERT(type.HasTypeClass());
	const Class& type_class = Class::Handle(type.type_class());

	// Bail if the type has any type parameters.
	if (type_class.IsGeneric()) {
	// If the interface type we check against is generic but has all-dynamic
	// type arguments, then we can still use the _simpleInstanceOf
	// implementation (see also runtime/lib/object.cc:Object_SimpleInstanceOf).
	const auto& rare_type = AbstractType::Handle(type_class.RareType());
	// TODO(regis): Revisit the usage of TypeEquality::kSyntactical when
	// implementing strong mode.
	return rare_type.IsEquivalent(type, TypeEquality::kSyntactical);
	}

	// Finally a simple class for instance of checking.
	return true;
	}

	} // namespace dart