Index: runtime/vm/flow_graph_optimizer.cc |
diff --git a/runtime/vm/flow_graph_optimizer.cc b/runtime/vm/flow_graph_optimizer.cc |
index b1a10b853c13453b59b130a7cc2f17cfb4eea976..f7db803b3ef25a1828f34e70bbf73cee056d16d3 100644 |
--- a/runtime/vm/flow_graph_optimizer.cc |
+++ b/runtime/vm/flow_graph_optimizer.cc |
@@ -84,7 +84,7 @@ bool FlowGraphOptimizer::TryCreateICData(InstanceCallInstr* call) { |
GrowableArray<intptr_t> class_ids(call->ic_data()->num_args_tested()); |
ASSERT(call->ic_data()->num_args_tested() <= call->ArgumentCount()); |
for (intptr_t i = 0; i < call->ic_data()->num_args_tested(); i++) { |
- intptr_t cid = call->ArgumentAt(i)->value()->ResultCid(); |
+ intptr_t cid = call->ArgumentAt(i)->value()->Type()->ToCid(); |
class_ids.Add(cid); |
} |
// TODO(srdjan): Test for other class_ids > 1. |
@@ -150,7 +150,7 @@ void FlowGraphOptimizer::SpecializePolymorphicInstanceCall( |
return; // Already specialized. |
} |
- const intptr_t receiver_cid = call->ArgumentAt(0)->value()->ResultCid(); |
+ const intptr_t receiver_cid = call->ArgumentAt(0)->value()->Type()->ToCid(); |
if (receiver_cid == kDynamicCid) { |
return; // No information about receiver was infered. |
} |
@@ -231,7 +231,7 @@ void FlowGraphOptimizer::InsertConversion(Representation from, |
Definition* converted = NULL; |
if ((from == kTagged) && (to == kUnboxedMint)) { |
ASSERT((deopt_target != NULL) || |
- (use->definition()->GetPropagatedCid() == kDoubleCid)); |
+ (use->Type()->ToCid() == kDoubleCid)); |
const intptr_t deopt_id = (deopt_target != NULL) ? |
deopt_target->DeoptimizationTarget() : Isolate::kNoDeoptId; |
converted = new UnboxIntegerInstr(new Value(use->definition()), deopt_id); |
@@ -251,7 +251,7 @@ void FlowGraphOptimizer::InsertConversion(Representation from, |
const intptr_t deopt_id = (deopt_target != NULL) ? |
deopt_target->DeoptimizationTarget() : Isolate::kNoDeoptId; |
ASSERT((deopt_target != NULL) || |
- (use->definition()->GetPropagatedCid() == kDoubleCid)); |
+ (use->Type()->ToCid() == kDoubleCid)); |
ConstantInstr* constant = use->definition()->AsConstant(); |
if ((constant != NULL) && constant->value().IsSmi()) { |
const double dbl_val = Smi::Cast(constant->value()).AsDoubleValue(); |
@@ -313,7 +313,7 @@ void FlowGraphOptimizer::SelectRepresentations() { |
for (intptr_t i = 0; i < join_entry->phis()->length(); ++i) { |
PhiInstr* phi = (*join_entry->phis())[i]; |
if (phi == NULL) continue; |
- if (phi->GetPropagatedCid() == kDoubleCid) { |
+ if (phi->Type()->ToCid() == kDoubleCid) { |
phi->set_representation(kUnboxedDouble); |
} |
} |
@@ -1965,192 +1965,13 @@ void FlowGraphOptimizer::VisitStrictCompare(StrictCompareInstr* instr) { |
// If one of the input is not a boxable number (Mint, Double, Bigint), no |
// need for number checks. |
- if (!MayBeBoxableNumber(instr->left()->ResultCid()) || |
- !MayBeBoxableNumber(instr->right()->ResultCid())) { |
+ if (!MayBeBoxableNumber(instr->left()->Type()->ToCid()) || |
+ !MayBeBoxableNumber(instr->right()->Type()->ToCid())) { |
instr->set_needs_number_check(false); |
} |
} |
-// SminessPropagator ensures that CheckSmis are eliminated across phis. |
-class SminessPropagator : public ValueObject { |
- public: |
- explicit SminessPropagator(FlowGraph* flow_graph) |
- : flow_graph_(flow_graph), |
- known_smis_(new BitVector(flow_graph_->current_ssa_temp_index())), |
- rollback_checks_(10), |
- in_worklist_(NULL), |
- worklist_(0) { } |
- |
- void Propagate(); |
- |
- private: |
- void PropagateSminessRecursive(BlockEntryInstr* block); |
- void AddToWorklist(PhiInstr* phi); |
- PhiInstr* RemoveLastFromWorklist(); |
- void ProcessPhis(); |
- |
- FlowGraph* flow_graph_; |
- |
- BitVector* known_smis_; |
- GrowableArray<intptr_t> rollback_checks_; |
- |
- BitVector* in_worklist_; |
- GrowableArray<PhiInstr*> worklist_; |
- |
- DISALLOW_COPY_AND_ASSIGN(SminessPropagator); |
-}; |
- |
- |
-void SminessPropagator::AddToWorklist(PhiInstr* phi) { |
- if (in_worklist_ == NULL) { |
- in_worklist_ = new BitVector(flow_graph_->current_ssa_temp_index()); |
- } |
- if (!in_worklist_->Contains(phi->ssa_temp_index())) { |
- in_worklist_->Add(phi->ssa_temp_index()); |
- worklist_.Add(phi); |
- } |
-} |
- |
- |
-PhiInstr* SminessPropagator::RemoveLastFromWorklist() { |
- PhiInstr* phi = worklist_.RemoveLast(); |
- ASSERT(in_worklist_->Contains(phi->ssa_temp_index())); |
- in_worklist_->Remove(phi->ssa_temp_index()); |
- return phi; |
-} |
- |
- |
-static bool IsDefinitelySmiPhi(PhiInstr* phi) { |
- for (intptr_t i = 0; i < phi->InputCount(); i++) { |
- const intptr_t cid = phi->InputAt(i)->ResultCid(); |
- if (cid != kSmiCid) { |
- return false; |
- } |
- } |
- return true; |
-} |
- |
- |
-static bool IsPossiblySmiPhi(PhiInstr* phi) { |
- for (intptr_t i = 0; i < phi->InputCount(); i++) { |
- const intptr_t cid = phi->InputAt(i)->ResultCid(); |
- if ((cid != kSmiCid) && (cid != kDynamicCid)) { |
- return false; |
- } |
- } |
- return true; |
-} |
- |
- |
-void SminessPropagator::ProcessPhis() { |
- // First optimistically mark all possible smi-phis: phi is possibly a smi if |
- // its operands are either smis or phis in the worklist. |
- for (intptr_t i = 0; i < worklist_.length(); i++) { |
- PhiInstr* phi = worklist_[i]; |
- ASSERT(phi->GetPropagatedCid() == kDynamicCid); |
- phi->SetPropagatedCid(kSmiCid); |
- |
- // Append all phis that use this phi and can potentially be smi to the |
- // end of worklist. |
- for (Value* use = phi->input_use_list(); |
- use != NULL; |
- use = use->next_use()) { |
- PhiInstr* phi_use = use->instruction()->AsPhi(); |
- if ((phi_use != NULL) && |
- (phi_use->GetPropagatedCid() == kDynamicCid) && |
- IsPossiblySmiPhi(phi_use)) { |
- AddToWorklist(phi_use); |
- } |
- } |
- } |
- |
- // Now unmark phis that are not definitely smi: that is have only |
- // smi operands. |
- while (!worklist_.is_empty()) { |
- PhiInstr* phi = RemoveLastFromWorklist(); |
- if (!IsDefinitelySmiPhi(phi)) { |
- // Phi result is not a smi. Propagate this fact to phis that depend on it. |
- phi->SetPropagatedCid(kDynamicCid); |
- for (Value* use = phi->input_use_list(); |
- use != NULL; |
- use = use->next_use()) { |
- PhiInstr* phi_use = use->instruction()->AsPhi(); |
- if ((phi_use != NULL) && (phi_use->GetPropagatedCid() == kSmiCid)) { |
- AddToWorklist(phi_use); |
- } |
- } |
- } |
- } |
-} |
- |
- |
-void SminessPropagator::PropagateSminessRecursive(BlockEntryInstr* block) { |
- const intptr_t rollback_point = rollback_checks_.length(); |
- |
- for (ForwardInstructionIterator it(block); !it.Done(); it.Advance()) { |
- Instruction* instr = it.Current(); |
- if (instr->IsCheckSmi()) { |
- const intptr_t value_ssa_index = |
- instr->InputAt(0)->definition()->ssa_temp_index(); |
- if (!known_smis_->Contains(value_ssa_index)) { |
- known_smis_->Add(value_ssa_index); |
- rollback_checks_.Add(value_ssa_index); |
- } |
- } else if (instr->IsBranch()) { |
- for (intptr_t i = 0; i < instr->InputCount(); i++) { |
- Value* use = instr->InputAt(i); |
- if (known_smis_->Contains(use->definition()->ssa_temp_index())) { |
- use->set_reaching_cid(kSmiCid); |
- } |
- } |
- } |
- } |
- |
- for (intptr_t i = 0; i < block->dominated_blocks().length(); ++i) { |
- PropagateSminessRecursive(block->dominated_blocks()[i]); |
- } |
- |
- if (block->last_instruction()->SuccessorCount() == 1 && |
- block->last_instruction()->SuccessorAt(0)->IsJoinEntry()) { |
- JoinEntryInstr* join = |
- block->last_instruction()->SuccessorAt(0)->AsJoinEntry(); |
- intptr_t pred_index = join->IndexOfPredecessor(block); |
- ASSERT(pred_index >= 0); |
- if (join->phis() != NULL) { |
- for (intptr_t i = 0; i < join->phis()->length(); ++i) { |
- PhiInstr* phi = (*join->phis())[i]; |
- if (phi == NULL) continue; |
- Value* use = phi->InputAt(pred_index); |
- const intptr_t value_ssa_index = use->definition()->ssa_temp_index(); |
- if (known_smis_->Contains(value_ssa_index) && |
- (phi->GetPropagatedCid() != kSmiCid)) { |
- use->set_reaching_cid(kSmiCid); |
- AddToWorklist(phi); |
- } |
- } |
- } |
- } |
- |
- for (intptr_t i = rollback_point; i < rollback_checks_.length(); i++) { |
- known_smis_->Remove(rollback_checks_[i]); |
- } |
- rollback_checks_.TruncateTo(rollback_point); |
-} |
- |
- |
-void SminessPropagator::Propagate() { |
- PropagateSminessRecursive(flow_graph_->graph_entry()); |
- ProcessPhis(); |
-} |
- |
- |
-void FlowGraphOptimizer::PropagateSminess() { |
- SminessPropagator propagator(flow_graph_); |
- propagator.Propagate(); |
-} |
- |
- |
// Range analysis for smi values. |
class RangeAnalysis : public ValueObject { |
public: |
@@ -2268,7 +2089,7 @@ void RangeAnalysis::CollectSmiValues() { |
Instruction* current = instr_it.Current(); |
Definition* defn = current->AsDefinition(); |
if (defn != NULL) { |
- if ((defn->GetPropagatedCid() == kSmiCid) && |
+ if ((defn->Type()->ToCid() == kSmiCid) && |
(defn->ssa_temp_index() != -1)) { |
smi_values_.Add(defn); |
} |
@@ -2281,7 +2102,7 @@ void RangeAnalysis::CollectSmiValues() { |
if (join != NULL) { |
for (PhiIterator phi_it(join); !phi_it.Done(); phi_it.Advance()) { |
PhiInstr* current = phi_it.Current(); |
- if (current->GetPropagatedCid() == kSmiCid) { |
+ if ((current->Type()->ToCid() == kSmiCid)) { |
smi_values_.Add(current); |
} |
} |
@@ -2736,261 +2557,6 @@ void FlowGraphOptimizer::InferSmiRanges() { |
} |
-void FlowGraphTypePropagator::VisitBlocks() { |
- ASSERT(current_iterator_ == NULL); |
- for (intptr_t i = 0; i < block_order_.length(); ++i) { |
- BlockEntryInstr* entry = block_order_[i]; |
- entry->Accept(this); |
- ForwardInstructionIterator it(entry); |
- current_iterator_ = ⁢ |
- for (; !it.Done(); it.Advance()) { |
- Instruction* current = it.Current(); |
- // No need to propagate the input types of the instruction, as long as |
- // PhiInstr's are handled as part of JoinEntryInstr. |
- |
- // Visit the instruction and possibly eliminate type checks. |
- current->Accept(this); |
- // The instruction may have been removed from the graph. |
- Definition* defn = current->AsDefinition(); |
- if ((defn != NULL) && |
- !defn->IsPushArgument() && |
- (defn->previous() != NULL)) { |
- // Cache the propagated computation type. |
- AbstractType& type = AbstractType::Handle(defn->CompileType()); |
- still_changing_ = defn->SetPropagatedType(type) || still_changing_; |
- |
- // Propagate class ids. |
- const intptr_t cid = defn->ResultCid(); |
- still_changing_ = defn->SetPropagatedCid(cid) || still_changing_; |
- } |
- } |
- current_iterator_ = NULL; |
- } |
-} |
- |
- |
-void FlowGraphTypePropagator::VisitAssertAssignable( |
- AssertAssignableInstr* instr) { |
- bool is_null, is_instance; |
- if (FLAG_eliminate_type_checks && |
- !instr->is_eliminated() && |
- ((instr->value()->CanComputeIsNull(&is_null) && is_null) || |
- (instr->value()->CanComputeIsInstanceOf(instr->dst_type(), &is_instance) |
- && is_instance))) { |
- // TODO(regis): Remove is_eliminated_ field and support. |
- instr->eliminate(); |
- |
- Value* use = instr->value(); |
- ASSERT(use != NULL); |
- Definition* result = use->definition(); |
- ASSERT(result != NULL); |
- // Replace uses and remove the current instruction via the iterator. |
- instr->ReplaceUsesWith(result); |
- ASSERT(current_iterator()->Current() == instr); |
- current_iterator()->RemoveCurrentFromGraph(); |
- if (FLAG_trace_optimization) { |
- OS::Print("Replacing v%"Pd" with v%"Pd"\n", |
- instr->ssa_temp_index(), |
- result->ssa_temp_index()); |
- } |
- |
- if (FLAG_trace_type_check_elimination) { |
- FlowGraphPrinter::PrintTypeCheck(parsed_function(), |
- instr->token_pos(), |
- instr->value(), |
- instr->dst_type(), |
- instr->dst_name(), |
- instr->is_eliminated()); |
- } |
- } |
-} |
- |
- |
-void FlowGraphTypePropagator::VisitAssertBoolean(AssertBooleanInstr* instr) { |
- bool is_null, is_bool; |
- if (FLAG_eliminate_type_checks && |
- !instr->is_eliminated() && |
- instr->value()->CanComputeIsNull(&is_null) && |
- !is_null && |
- instr->value()->CanComputeIsInstanceOf(Type::Handle(Type::BoolType()), |
- &is_bool) && |
- is_bool) { |
- // TODO(regis): Remove is_eliminated_ field and support. |
- instr->eliminate(); |
- Value* use = instr->value(); |
- Definition* result = use->definition(); |
- ASSERT(result != NULL); |
- // Replace uses and remove the current instruction via the iterator. |
- instr->ReplaceUsesWith(result); |
- ASSERT(current_iterator()->Current() == instr); |
- current_iterator()->RemoveCurrentFromGraph(); |
- if (FLAG_trace_optimization) { |
- OS::Print("Replacing v%"Pd" with v%"Pd"\n", |
- instr->ssa_temp_index(), |
- result->ssa_temp_index()); |
- } |
- |
- if (FLAG_trace_type_check_elimination) { |
- FlowGraphPrinter::PrintTypeCheck(parsed_function(), |
- instr->token_pos(), |
- instr->value(), |
- Type::Handle(Type::BoolType()), |
- Symbols::BooleanExpression(), |
- instr->is_eliminated()); |
- } |
- } |
-} |
- |
- |
-void FlowGraphTypePropagator::VisitInstanceOf(InstanceOfInstr* instr) { |
- bool is_null; |
- bool is_instance = false; |
- if (FLAG_eliminate_type_checks && |
- instr->value()->CanComputeIsNull(&is_null) && |
- (is_null || |
- instr->value()->CanComputeIsInstanceOf(instr->type(), &is_instance))) { |
- bool val = instr->negate_result() ? !is_instance : is_instance; |
- Definition* result = new ConstantInstr(val ? Bool::True() : Bool::False()); |
- result->set_ssa_temp_index(flow_graph_->alloc_ssa_temp_index()); |
- result->InsertBefore(instr); |
- // Replace uses and remove the current instruction via the iterator. |
- instr->ReplaceUsesWith(result); |
- ASSERT(current_iterator()->Current() == instr); |
- current_iterator()->RemoveCurrentFromGraph(); |
- if (FLAG_trace_optimization) { |
- OS::Print("Replacing v%"Pd" with v%"Pd"\n", |
- instr->ssa_temp_index(), |
- result->ssa_temp_index()); |
- } |
- |
- if (FLAG_trace_type_check_elimination) { |
- FlowGraphPrinter::PrintTypeCheck(parsed_function(), |
- instr->token_pos(), |
- instr->value(), |
- instr->type(), |
- Symbols::InstanceOf(), |
- /* eliminated = */ true); |
- } |
- } |
-} |
- |
- |
-void FlowGraphTypePropagator::VisitGraphEntry(GraphEntryInstr* graph_entry) { |
- // Visit incoming parameters. |
- for (intptr_t i = 0; i < graph_entry->initial_definitions()->length(); i++) { |
- ParameterInstr* param = |
- (*graph_entry->initial_definitions())[i]->AsParameter(); |
- if (param != NULL) VisitParameter(param); |
- } |
-} |
- |
- |
-void FlowGraphTypePropagator::VisitJoinEntry(JoinEntryInstr* join_entry) { |
- if (join_entry->phis() != NULL) { |
- for (intptr_t i = 0; i < join_entry->phis()->length(); ++i) { |
- PhiInstr* phi = (*join_entry->phis())[i]; |
- if (phi != NULL) { |
- VisitPhi(phi); |
- } |
- } |
- } |
-} |
- |
- |
-// TODO(srdjan): Investigate if the propagated cid should be more specific. |
-void FlowGraphTypePropagator::VisitPushArgument(PushArgumentInstr* push) { |
- if (!push->has_propagated_cid()) push->SetPropagatedCid(kDynamicCid); |
-} |
- |
- |
-void FlowGraphTypePropagator::VisitPhi(PhiInstr* phi) { |
- // We could set the propagated type of the phi to the least upper bound of its |
- // input propagated types. However, keeping all propagated types allows us to |
- // optimize method dispatch. |
- // TODO(regis): Support a set of propagated types. For now, we compute the |
- // least specific of the input propagated types. |
- AbstractType& type = AbstractType::Handle(phi->LeastSpecificInputType()); |
- bool changed = phi->SetPropagatedType(type); |
- if (changed) { |
- still_changing_ = true; |
- } |
- |
- // Merge class ids: if any two inputs have different class ids then result |
- // is kDynamicCid. |
- intptr_t merged_cid = kIllegalCid; |
- for (intptr_t i = 0; i < phi->InputCount(); i++) { |
- // Result cid of UseVal can be kIllegalCid if the referred definition |
- // has not been visited yet. |
- intptr_t cid = phi->InputAt(i)->ResultCid(); |
- if (cid == kIllegalCid) { |
- still_changing_ = true; |
- continue; |
- } |
- if (merged_cid == kIllegalCid) { |
- // First time set. |
- merged_cid = cid; |
- } else if (merged_cid != cid) { |
- merged_cid = kDynamicCid; |
- } |
- } |
- if (merged_cid == kIllegalCid) { |
- merged_cid = kDynamicCid; |
- } |
- changed = phi->SetPropagatedCid(merged_cid); |
- if (changed) { |
- still_changing_ = true; |
- } |
-} |
- |
- |
-void FlowGraphTypePropagator::VisitParameter(ParameterInstr* param) { |
- // TODO(regis): Once we inline functions, the propagated type of the formal |
- // parameter will reflect the compile type of the passed-in argument. |
- // For now, we do not know anything about the argument type and therefore set |
- // it to the DynamicType, unless the argument is a compiler generated value, |
- // i.e. the receiver argument or the constructor phase argument. |
- AbstractType& param_type = AbstractType::Handle(Type::DynamicType()); |
- param->SetPropagatedCid(kDynamicCid); |
- bool param_type_is_known = false; |
- if (param->index() == 0) { |
- const Function& function = parsed_function().function(); |
- if ((function.IsDynamicFunction() || function.IsConstructor())) { |
- // Parameter is the receiver . |
- param_type_is_known = true; |
- } |
- } else if ((param->index() == 1) && |
- parsed_function().function().IsConstructor()) { |
- // Parameter is the constructor phase. |
- param_type_is_known = true; |
- } |
- if (param_type_is_known) { |
- LocalScope* scope = parsed_function().node_sequence()->scope(); |
- param_type = scope->VariableAt(param->index())->type().raw(); |
- if (FLAG_use_cha) { |
- const intptr_t cid = Class::Handle(param_type.type_class()).id(); |
- if (!CHA::HasSubclasses(cid)) { |
- // Receiver's class has no subclasses. |
- param->SetPropagatedCid(cid); |
- } |
- } |
- } |
- bool changed = param->SetPropagatedType(param_type); |
- if (changed) { |
- still_changing_ = true; |
- } |
-} |
- |
- |
-void FlowGraphTypePropagator::PropagateTypes() { |
- // TODO(regis): Is there a way to make this more efficient, e.g. by visiting |
- // only blocks depending on blocks that have changed and not the whole graph. |
- do { |
- still_changing_ = false; |
- VisitBlocks(); |
- } while (still_changing_); |
-} |
- |
- |
static BlockEntryInstr* FindPreHeader(BlockEntryInstr* header) { |
for (intptr_t j = 0; j < header->PredecessorCount(); ++j) { |
BlockEntryInstr* candidate = header->PredecessorAt(j); |
@@ -3035,7 +2601,7 @@ void LICM::TryHoistCheckSmiThroughPhi(ForwardInstructionIterator* it, |
return; |
} |
- if (phi->GetPropagatedCid() == kSmiCid) { |
+ if (phi->Type()->ToCid() == kSmiCid) { |
current->UnuseAllInputs(); |
it->RemoveCurrentFromGraph(); |
return; |
@@ -3047,8 +2613,9 @@ void LICM::TryHoistCheckSmiThroughPhi(ForwardInstructionIterator* it, |
intptr_t non_smi_input = kNotFound; |
for (intptr_t i = 0; i < phi->InputCount(); ++i) { |
Value* input = phi->InputAt(i); |
- if (input->ResultCid() != kSmiCid) { |
- if ((non_smi_input != kNotFound) || (input->ResultCid() != kDynamicCid)) { |
+ if (input->Type()->ToCid() != kSmiCid) { |
+ if ((non_smi_input != kNotFound) || |
+ (input->Type()->ToCid() != kDynamicCid)) { |
// There are multiple kDynamicCid inputs or there is an input that is |
// known to be non-smi. |
return; |
@@ -3072,7 +2639,7 @@ void LICM::TryHoistCheckSmiThroughPhi(ForwardInstructionIterator* it, |
current->value()->set_definition(non_smi_input_defn); |
non_smi_input_defn->AddInputUse(current->value()); |
- phi->SetPropagatedCid(kSmiCid); |
+ phi->Type()->ReplaceWith(CompileType::FromCid(kSmiCid)); |
} |
@@ -4118,10 +3685,10 @@ void ConstantPropagator::VisitStrictCompare(StrictCompareInstr* instr) { |
if (IsNonConstant(left) || IsNonConstant(right)) { |
// TODO(vegorov): incorporate nullability information into the lattice. |
- if ((left.IsNull() && (instr->right()->ResultCid() != kDynamicCid)) || |
- (right.IsNull() && (instr->left()->ResultCid() != kDynamicCid))) { |
- bool result = left.IsNull() ? (instr->right()->ResultCid() == kNullCid) |
- : (instr->left()->ResultCid() == kNullCid); |
+ if ((left.IsNull() && instr->right()->Type()->HasDecidableNullability()) || |
+ (right.IsNull() && instr->left()->Type()->HasDecidableNullability())) { |
+ bool result = left.IsNull() ? instr->right()->Type()->IsNull() |
+ : instr->left()->Type()->IsNull(); |
if (instr->kind() == Token::kNE_STRICT) result = !result; |
SetValue(instr, result ? Bool::True() : Bool::False()); |
} else { |